文章源自略懂百科-http://wswcn.cn/22910.html
密码学发展史文章源自略懂百科-http://wswcn.cn/22910.html
讨论RSA原理之前，我们先了解一下密码学的发展史。因为RSA最终形成的数学算法，也是不断演变而来的。文章源自略懂百科-http://wswcn.cn/22910.html
历史上最早的加密算法文章源自略懂百科-http://wswcn.cn/22910.html
中国话说历史上最早的加密算法的记载出自于周朝兵书《六韬.龙韬》中的《阴符》和《阴书》。其原理是使用文字拆分和符号代替等方式来加密数据。其实密码学的诞生，就是为了运用在战场。西方无独有偶，在遥远的西方加密算法也大规模使用于战争之中。在希罗多德（Herodotus）的《历史》中记载了公元前五世纪，希腊城邦和波斯帝国的战争中，广泛使用了移位法进行加密处理战争通讯信息。文章源自略懂百科-http://wswcn.cn/22910.html
凯撒密码文章源自略懂百科-http://wswcn.cn/22910.html
由古代密码演变而来的凯撒密码。相传凯撒大帝为了防止敌人窃取信息，就使用加密的方式传递信息。那么当时的加密方式非常的简单，就是对二十几个罗马字母建立一张对照表，将明文对应成为密文。那么这种方式其实持续了很久。甚至在二战时期，日本的电报加密就是采用的这种原始加密方式。（更多内容推荐大家阅读吴军老师《数学之美》）文章源自略懂百科-http://wswcn.cn/22910.html
早期的密码学一直没有什么改进，几乎都是根据经验慢慢发展的。直到20世纪中叶，密码学的发展进入了快车道。由香农发表的《秘密体制的通信理论》一文，标志着加密算法的重心转移往应用数学上的转移。于是，逐渐衍生出了当今重要的三类加密算法：非对称加密、对称加密以及哈希算法（当然HASH严格说不是加密算法，但由于其不可逆性，已成为加密算法中的一个重要构成部分）。文章源自略懂百科-http://wswcn.cn/22910.html
1976年前文章源自略懂百科-http://wswcn.cn/22910.html
这段时间，所有的加密方式都是同一种模式：加密、解密使用同一种算法。加密和解密的规则（密钥）必须双方都知道。那么它的传递就成为了最大的隐患。这种加密方式被称为对称加密算法。文章源自略懂百科-http://wswcn.cn/22910.html
1976年文章源自略懂百科-http://wswcn.cn/22910.html
正是因为对称加密算法盛行（非对称那个时候还没有出现，但有些疯狂的数学家已经开始构思这种方案，但并未成功）。人们为了更好的保护密钥而绞尽脑汁。直到1976年，两位美国计算机学家。迪菲（W.Diffie）、赫尔曼（ M.Hellman ） 提出了一种崭新构思，可以在不直接传递密钥的情况下，完成密钥交换。这被称为迪菲赫尔曼密钥交换算法。也正是因为这个算法的产生！人类终于可以实现非对称加密了。那么我们一起来看看这个算法的数学原理。文章源自略懂百科-http://wswcn.cn/22910.html
由欧拉函数开始文章源自略懂百科-http://wswcn.cn/22910.html
在讨论迪菲赫尔曼密钥交换算法之前，我们先了解几个数学知识。并做一些公式的转换。这样你才能更好的体会到迪菲赫尔曼密钥交换算法它到底能发挥多么神奇的作用。文章源自略懂百科-http://wswcn.cn/22910.html
欧拉函数文章源自略懂百科-http://wswcn.cn/22910.html
什么是欧拉函数？先思考下面的问题。文章源自略懂百科-http://wswcn.cn/22910.html
思考文章源自略懂百科-http://wswcn.cn/22910.html
任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？文章源自略懂百科-http://wswcn.cn/22910.html
关于互质关系文章源自略懂百科-http://wswcn.cn/22910.html
如果两个正整数，除了1以外，没有其他公因数，我们就称这两个数是互质关系（coprime）。文章源自略懂百科-http://wswcn.cn/22910.html
计算这个值的方式叫做欧拉函数，使用：Φ(n)表示文章源自略懂百科-http://wswcn.cn/22910.html
如:文章源自略懂百科-http://wswcn.cn/22910.html
计算8的欧拉函数，和8互质的1、2、3、4、5、6、7、8φ(8) = 4计算7的欧拉函数，和7互质的1、2、3、4、5、6、7φ(7) = 6计算56的欧拉函数φ(56) = φ(8) * φ(7) = 4 * 6 = 24文章源自略懂百科-http://wswcn.cn/22910.html
现在你会发现，并不是所有的欧拉函数都可以口算出来，有些甚至计算机都算不出来。当然你也发现了φ(56)似乎有些特殊。对了！欧拉函数有些特点是必须要知道的！文章源自略懂百科-http://wswcn.cn/22910.html
欧拉函数特点文章源自略懂百科-http://wswcn.cn/22910.html
当n是质数的时候，φ(n)=n-1。如果n可以分解成两个互质的整数之积，如n=AB则：φ(AB)=φ(A)* φ(B)根据以上两点得到：如果N是两个质数P1 和 P2的乘积则φ(N)=φ(P1)* φ(P2)=(P1-1)*(P2-1)文章源自略懂百科-http://wswcn.cn/22910.html
欧拉定理文章源自略懂百科-http://wswcn.cn/22910.html
了解了欧拉函数，接下来需要知道一个定理。既然是定理，就是恒古不变的，已经被数学家们证明过的，所以建议读者可以验证，但最好不要试图去证明，这个比较耗时（主要是耗脑，别玩着玩着怀疑智商了...）文章源自略懂百科-http://wswcn.cn/22910.html
欧拉定理文章源自略懂百科-http://wswcn.cn/22910.html
如果两个正整数m和n互质，那么m的φ(n)次方减去1，可以被n整除。文章源自略懂百科-http://wswcn.cn/22910.html
说白了就是：文章源自略懂百科-http://wswcn.cn/22910.html
费马小定理文章源自略懂百科-http://wswcn.cn/22910.html
欧拉定理的特殊情况：如果两个正整数m和n互质，而且n为质数！那么φ(n)结果就是n-1。文章源自略懂百科-http://wswcn.cn/22910.html
那么也就是：文章源自略懂百科-http://wswcn.cn/22910.html
等式转换文章源自略懂百科-http://wswcn.cn/22910.html
1、根据欧拉定理文章源自略懂百科-http://wswcn.cn/22910.html
2、由于1^k ≡ 1，等号左右两边都来个k次方文章源自略懂百科-http://wswcn.cn/22910.html
3、由于1* m ≡ m，等号左右两边都乘上m文章源自略懂百科-http://wswcn.cn/22910.html
接下来，我们还需要进行等式转换。那么等式转换4的前提是模反元素文章源自略懂百科-http://wswcn.cn/22910.html
模反元素文章源自略懂百科-http://wswcn.cn/22910.html
如果两个正整数e和x互质，那么一定可以找到整数d，使得 ed-1 被x整除。文章源自略懂百科-http://wswcn.cn/22910.html
那么d就是e对于x的模反元素文章源自略懂百科-http://wswcn.cn/22910.html
说白了就是文章源自略懂百科-http://wswcn.cn/22910.html
这个模反元素的等式也可以进一步转换，因为e*d 一定是x的倍数加1。所以如下：文章源自略懂百科-http://wswcn.cn/22910.html
那么千辛万苦！我们通过多次的等式转换。终于可以将这两个等式进行合并了！如下：文章源自略懂百科-http://wswcn.cn/22910.html
这个等式成立有一个前提！就是关于模反元素的。说白了就是当整数e和φ(n)互质！一定有一个整数d是e相对于φ(n)的模反元素。文章源自略懂百科-http://wswcn.cn/22910.html
我们可以测试一下。文章源自略懂百科-http://wswcn.cn/22910.html
m4文章源自略懂百科-http://wswcn.cn/22910.html
n15文章源自略懂百科-http://wswcn.cn/22910.html
φ(n)8文章源自略懂百科-http://wswcn.cn/22910.html
e如果取值为3文章源自略懂百科-http://wswcn.cn/22910.html
d可以为 11、19...(模反元素很明显不止一个，其实就是解二元一次方程)文章源自略懂百科-http://wswcn.cn/22910.html
如果你测试了，那么你可以改变m的值试一下。其实这个等式不需要m和n 互质。只要m小于n 等式依然成立。文章源自略懂百科-http://wswcn.cn/22910.html
这里需要注意的是，我们可以看做 m 通过一系列运算 得到结果任然是 m。这一系列运算中，分别出现了多个参数n、φ(n)、e还有d 。文章源自略懂百科-http://wswcn.cn/22910.html
文章源自略懂百科-http://wswcn.cn/22910.html
评论