RSA 数学原理

提起RSA大家一定不陌生，在开发中经常使用，也经常听同事说道。

前奏

对称加密

话说很久以前，人们就懂的了加密这个技术。在战争时期，间谍就会拿着 密文 和 密匙 来对信息就行传递。
这种简单的 密文 + 密匙（key） 就是 对称加密

加密: 明文 + 密匙

解密: 密文 + 密匙

非对称加密

由于这种加密方式过于简单，所以后来引入了数学算法。
RSA 就是由特殊的数学算法构成的，也是非对称加密算法。非对称加密需要两个密钥：公钥（public key） + 私钥（private key）

用公钥加密，私钥解密

私钥加密，公钥解密

相关数学原理

欧拉定理

如果两个正整数m和n互质，那么m的φ(n)次方减去1，可以被n整除。

image
一下是几种情况

• 定理0 算术函数f如果满足对于任意两个互质的正整数m和n，均有f(mn)=f(m)f(n)，就称f为积性函数（或乘性函数）。
  如果对于任意两个正整数m和n，均有f(mn)=f(m)f(n)，就称为完全积性函数。

• 定理1 对于素数p，ϕ(p)=p−1。

• 定理2 ϕ(pn)=pn−pn−1，因为素数幂pn不互质的只有p的倍数，一共有pn/p=pn−1个。

• 定理3 若m、n互质，ϕ(mn)=ϕ(m)ϕ(n)，所以欧拉函数是积性函数。
  因为mn互质NN，和m互质的数乘上和n互质的数就会和mn互质。

• 定理4 设n=p1a1p2a2...pkak为正整数n的素数幂分解，那么ϕ(n)=n(1−1/p1)(1−1/p2)...(1−1/pk)。
  由定理2，ϕ(pn)=pn−pn−1=pn (1-1/p)，又由定理3，ϕ(n)=p1a1p2a2...pkak(1−1/p1)(1−1/p2)...(1−1/pk)=n(1−1/p1)(1−1/p2)...(1−1/pk)

例如： 
ϕ(8) = ϕ(2^3) = 2^3 - 2^(2-1) = 8 - 4 = 4
ϕ(15) = ϕ(3) * ϕ(5) = 2 * 4 = 8

费马小定律

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

image

模反元素

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

image

迪菲赫尔曼密匙交换原理

image

那么，通过一系列的数学转换，最终得出了RSA算法

image

公钥：e 和 n
私钥：d 和 n
明文：m
密文：c

说明：

• n会非常大，长度一般为1024个二进制位。（目前人类已经分解的最大整数，232个十进制位，768个二进制位）
• 由于需要求出φ(n)，所以根据欧函数特点，最简单的方式n 由两个质数相乘得到: 质数：p1、p2
  Φ(n) = (p1 -1) * (p2 - 1)
• 最终由φ(n)得到e 和 d 。

总共生成6个数字：p1、p2、n、φ(n)、e、d

关于RSA的安全：

除了公钥用到了n和e 其余的4个数字是不公开的。
目前破解RSA得到d的方式如下：

• 要想求出私钥 d 。由于ed = φ(n)k + 1。要知道e和φ(n);
• e是知道的，但是要得到 φ(n)，必须知道p1 和 p2。
• 由于 n=p1*p2。只有将n因数分解才能算出。

那么RSA有优点和弊端是什么了？

优点

• 相对安全

缺点

• 速度慢，耗时（因为，起内部原理是一系列的数学计算）
• 加密数据量小