RSA

RSA(非对称加密)

从对称加密到非对称加密

对称加密

  • 服务端 使用某一种加密规则,对信息进行加密。
  • 客户端 使用同一种规则,对信息进行解密。
    这种加密模式有一个最大弱点:服务端必须把加密规则告诉客户端,否则无法解密。保存和传递密钥,就成了最头疼的问题。

Diffie–Hellman key exchange

1976年,Whitfield Diffie 和 Martin Hellman,提出Diffie–Hellman key exchange算法,可以在不直接传递密钥的情况下,完成解密。只要服务端和客户端的规则存在某种对应关系即可。

非对称加密

  • 服务端生成两把密钥(公钥和私钥)。公钥是公开的,任何人都可以获得,私钥则是保密的,只有自己知道。
  • 客户端获取服务端的公钥,然后用它对信息加密。
  • 服务端得到加密后的信息,用私钥解密。

RSA来源

RSA加密算法是一种非对称加密算法。在公开密钥加密和电子商业中RSA被广泛使用。RSA是1977年由Ron Rivest、Adi Shamir、Leonard Adleman 一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。

RSA基本原理

$密文=明文^E mod N$ RSA加密 明文的E次方对N求余就是密文
$明文=密文^D mod N$ RSA解密 密文的D次方对N求余就是明文

E是(Encrytion)的首字母
D是(Decrytion)的首字母
N是(Number)的首字母

公钥就是{E,N} 密钥就是{D,N}

公钥{E,N}和密钥{D,N}的生成步骤

  1. 求N
  2. 求L(L仅在过程中使用的数)
  3. 求E
  4. 求D

N

有互质关系的两个数的乘积,假设p和q具有互质关系,则N=p*q

互质关系: 如果两个正整数,除了1以外,没有其他公因子,我们就称这两个数是互质关系(coprime)
3和16 公因子是1 是互质关系
6和27 公因子是1,3 不是互质关系

L

L 是 p - 1 和 q - 1的最小公倍数。

欧拉函数:φ(n) 任意给定正整数n,请问在小于等于n的正整数之中,有多少个与n构成互质关系?

在1到8之中,有多少个数与8构成互质关系? 存在互质关系的有1、 3、 5、 7。所以 φ(8) = 4。

第一种情况

如果n=1,则 φ(1) = 1 。因为1与任何数(包括自身)都构成互质关系

第二种情况

如果n是质数,则 φ(n)=n-1 。因为质数与小于它的每一个数,都构成互质关系。比如5与1、2、3、4都构成互质关系。

第三种情况

如果n是质数的某一个次方,即 $n = p^k$ (p为质数,k为大于等于1的整数),则$φ(p^k) = p^k - p^{k-1}$

例如:
$φ(8) = φ(2^3) =2^3 – 2^{3-1} = 8 - 4 = 4$

这是因为只有当一个数不包含质数p,才可能与n互质。而包含质数p的数一共有$p^{k-1}$个,即$1×p$、$2×p$、$3×p$、…、$p^{k-1}×p$,把它们去除,剩下的就是与n互质的数。

0至p中,只有一个数,p与n不是互质
p至2p中,只有一个数,2p与n不是互质
2p至3p中,只有一个数,3p与n不是互质
……
$p^{k-2}$至$p^{k-1}$中,只有一个数,$p^{k-1}$与n不是互质

$φ(n) = p^k(总数) - p^{k-1}(不是互质的数) = p^k(1-\frac{1}{k})$

第四种情况

如果n可以分解成两个互质的整数之积n = p1 * p2,则 φ(n) = φ(p1*p2) = φ(p1) * φ(p2)

第五种情况

因为任意一个大于1的正整数,都可以写成一系列质数的积。

$n = p1^{k1} × p2^{k2} × ⋅⋅⋅ × pr^{kr}$
根据第四种情况
$φ(n) = φ(p1^{k1}) + φ(p2^{k2}) + ⋅⋅⋅ + φ(pr^{kr})$
再根据第三种情况
$φ(n) = p1^{k1} × p2^{k2} × ⋅⋅⋅ × pr^{kr}(1-\frac{1}{p1})(1-\frac{1}{p2})(1-\frac{1}{p3})⋅⋅⋅(1-\frac{1}{pr})$
$φ(n) = n(1-\frac{1}{p1})(1-\frac{1}{p2})(1-\frac{1}{p3})⋅⋅⋅(1-\frac{1}{pr})$

$φ(1323)=φ(3^3 × 7^2)=1323(1-\frac{1}{3})(1-\frac{1}{7})=756$

E

E 是比1大比L小的数,E和L的最大公约数为1

D

D 是比1大比L小的数,E和D的乘积对L求余为1
1 < D < L
E x D mod L = 1

举例说明

求N

随机选择两个不相等的质数p和q,p=17,q=19

N = p x q = 17 x 19 = 323

求L

L = 最小公倍数(17 - 1) x (19 - 1) = 144

16 x 9 = 144
18 x 8 = 144

求E

满足条件的E有很多,例如:5,7,11,13,17….

我们选择E=5,则公钥就是E=5,N=323

求D

E x D mod L = 1
5 x D mod 144 = 1

当D=29时,满足上面的条件。

加密

明文=123
$密文 = 明文^E mod N = 123^5 mod 323 = 225$

解密

$明文 = 密文^D mod N = 225^29 mod 323 = 123$

参考资料
https://mp.weixin.qq.com/s/J6UCbHPOBJyrHQwCz1eF4g
https://mp.weixin.qq.com/s/kVXROoRulq1jYt--sU_9Xw
http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_one.html
http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html
图解密码技术

xpisme wechat
微信号