RSA原理探究

封面

密码学发展史

讨论RSA原理之前，我们先了解一下密码学的发展史。因为RSA最终形成的数学算法，也是不断演变而来的。

历史上最早的加密算法

• 中国
  话说历史上最早的加密算法的记载出自于周朝兵书《六韬.龙韬》中的《阴符》和《阴书》。其原理是使用文字拆分和符号代替等方式来加密数据。其实密码学的诞生，就是为了运用在战场。
• 西方
  无独有偶，在遥远的西方加密算法也大规模使用于战争之中。在希罗多德（Herodotus）的《历史》中记载了公元前五世纪，希腊城邦和波斯帝国的战争中，广泛使用了移位法进行加密处理战争通讯信息。

凯撒密码

由古代密码演变而来的凯撒密码。相传凯撒大帝为了防止敌人窃取信息，就使用加密的方式传递信息。那么当时的加密方式非常的简单，就是对二十几个罗马字母建立一张对照表，将明文对应成为密文。那么这种方式其实持续了很久。甚至在二战时期，日本的电报加密就是采用的这种原始加密方式。（更多内容推荐大家阅读吴军老师《数学之美》）

凯撒密码
早期的密码学一直没有什么改进，几乎都是根据经验慢慢发展的。直到20世纪中叶，密码学的发展进入了”快车道“。由香农发表的《秘密体制的通信理论》一文，标志着加密算法的重心转移往应用数学上的转移。于是，逐渐衍生出了当今重要的三类加密算法：非对称加密、对称加密以及哈希算法（当然HASH严格说不是加密算法，但由于其不可逆性，已成为加密算法中的一个重要构成部分）。

1976年前

这段时间，所有的加密方式都是同一种模式：加密、解密使用同一种算法。加密和解密的规则（密钥）必须双方都知道。那么它的传递就成为了最大的隐患。这种加密方式被称为对称加密算法。

1976年

正是因为对称加密算法盛行（非对称那个时候还没有出现，但有些疯狂的数学家已经开始构思这种方案，但并未成功）。人们为了更好的保护密钥而绞尽脑汁。直到1976年，两位美国计算机学家。迪菲（W.Diffie）、赫尔曼（ M.Hellman ） 提出了一种崭新构思，可以在不直接传递密钥的情况下，完成密钥交换。这被称为“迪菲赫尔曼密钥交换”算法。也正是因为这个算法的产生！人类终于可以实现非对称加密了。那么我们一起来看看这个算法的数学原理。

牛人

由欧拉函数开始

在讨论迪菲赫尔曼密钥交换算法之前，我们先了解几个数学知识。并做一些公式的转换。这样你才能更好的体会到迪菲赫尔曼密钥交换算法它到底能发挥多么神奇的作用。

欧拉函数

什么是欧拉函数？先思考下面的问题。
思考
任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？

关于互质关系
如果两个正整数，除了1以外，没有其他公因数，我们就称这两个数是互质关系（coprime）。

计算这个值的方式叫做欧拉函数，使用：Φ(n)表示
如:

• 计算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

现在你会发现，并不是所有的欧拉函数都可以口算出来，有些甚至计算机都算不出来。当然你也发现了φ(56)似乎有些特殊。对了！欧拉函数有些特点是必须要知道的！
欧拉函数特点

• 当n是质数的时候，φ(n)=n-1。
• 如果n可以分解成两个互质的整数之积，如n=AB则：
  φ(AB)=φ(A)* φ(B)
• 根据以上两点得到：
  如果N是两个质数P1 和 P2的乘积则
  φ(N)=φ(P1)* φ(P2)=(P1-1)*(P2-1)

欧拉定理

了解了欧拉函数，接下来需要知道一个定理。既然是定理，就是恒古不变的，已经被数学家们证明过的，所以建议读者可以验证，但最好不要试图去证明，这个比较耗时（主要是耗脑，别玩着玩着怀疑智商了...）

欧拉定理
如果两个正整数m和n互质，那么m的φ(n)次方减去1，可以被n整除。
说白了就是：

欧拉定理

费马小定理
欧拉定理的特殊情况：如果两个正整数m和n互质，而且n为质数！那么φ(n)结果就是n-1。
那么也就是：

费马小定理

等式转换

1、根据欧拉定理

欧拉定理

2、由于1^k ≡ 1，等号左右两边都来个k次方

等式转换2

3、由于1* m ≡ m，等号左右两边都乘上m

等式转换3

接下来，我们还需要进行等式转换。那么等式转换4的前提是 模反元素

模反元素
如果两个正整数e和x互质，那么一定可以找到整数d，使得 ed-1 被x整除。
那么d就是e对于x的模反元素
说白了就是

d是模反元素
这个模反元素的等式也可以进一步转换，因为e*d 一定是x的倍数加1。所以如下：
等式转换

那么千辛万苦！我们通过多次的等式转换。终于可以将这两个等式进行合并了！如下：

等式终极转换

这个等式成立有一个前提！就是关于模反元素的。说白了就是当整数e和φ(n)互质！一定有一个整数d是e相对于φ(n)的模反元素。
我们可以测试一下。
m 4
n 15
φ(n) 8
e 如果取值为3
d 可以为 11、19...(模反元素很明显不止一个，其实就是解二元一次方程)

如果你测试了，那么你可以改变m的值试一下。其实这个等式不需要m和n 互质。只要m小于n 等式依然成立。
这里需要注意的是，我们可以看做 m 通过一系列运算 得到结果任然是 m。这一系列运算中，分别出现了多个参数n、φ(n)、e还有d 。

那么我们思考一下！

m 的 e乘上d 次方为加密运算 得到结果 c
c 模以 n 为解密运算 得到结果 m
这似乎可以用于加密和解密。但这样，加密的结果会非常大。明文数据将非常小（虽然RSA用于加密的数据也很小，但是没这么大悬殊）
真正的RSA要更加强大，那么RSA是怎么演变来的呢？？
早期很多数学家也停留在了这一步！直到1967年迪菲赫尔曼密钥交换打破了僵局！

迪菲赫尔曼密钥交换

那么为什么说 这个密钥交换当时轰动了整个数学界！而且对人类密码学的发展非常重要呢？因为这个伟大的算法！能够拆分刚才的等式。
当非对称加密算法没有出现以前，人类都是用的对称加密。
所以密钥的传递，就必须要非常小心。
迪菲赫尔曼密钥交换 就是解决了 密钥传递 的保密性！！我们来看一下

迪菲赫尔曼密钥交换
们来假设一个传递密钥的场景。算法就是用3 的次方 去模以17。 三个角色

• 服务器 随机数 15
  • 这个15只有服务器才知道。通过算法!! 得到结果 6 因为 3的15次方 mod 17 = 6 。然后将结果 6 公开发送出去!!
  • 拿到客户端的 6 ，然后用6^15 mod 17 得到结果10(10就是交换得到的密钥)
• 客户端 随机数13
  • 得到结果 3 的 13次方 mod 17 = 12 然后将12公布出去。
  • 拿到服务器的 12 ，然后用12^13 mod 17 得到结果10(10就是交换得到的密钥)
• 黑客
  它只能拿到6 和 12 。因为没有私密数据13、15所以它没法得到结果10.

那么这里可能一眼看过去不好理解!对吧!!
为什么 6的13次方会和12的15次方得到一样的结果呢?
因为这就是规律!! 可以用小一点的数字测试一下!!
3^3 mod 17 = 10
10 ^ 2 mod 17 = 3 ^ 3 ^ 2 mod 17 结果都是15 !!

迪菲赫尔曼密钥交换最核心的地方就在于这个规律！

迪菲赫尔曼密钥交换

RSA的诞生

一张图看懂一切

以上就是RSA的数学原理，关于RSA的运用后面再慢慢阐述。本人才疏学浅，如果有地方写得不对，请留言指出。也欢迎大家留言交流。