有了这些知识, 我们就可以看懂 RSA 算法这是目前地球上最重要的加密算法
六密钥生成的步骤
我们通过一个例子, 来理解 RSA 算法假设爱丽丝要与鲍勃进行加密通信, 她该怎么生成公钥和私钥呢?
第一步, 随机选择两个不相等的质数 p 和 q
爱丽丝选择了 61 和 53(实际应用中, 这两个质数越大, 就越难破解)
第二步, 计算 p 和 q 的乘积 n
爱丽丝就把 61 和 53 相乘
n = 61×53 = 3233
n 的长度就是密钥长度 3233 写成二进制是 110010100001, 一共有 12 位, 所以这个密钥就是 12 位实际应用中, RSA 密钥一般是 1024 位, 重要场合则为 2048 位
第三步, 计算 n 的欧拉函数φ(n)
根据公式:
φ(n) = (p-1)(q-1)
爱丽丝算出φ(3233)等于 60×52, 即 3120
第四步, 随机选择一个整数 e, 条件是 1< e < φ(n), 且 e 与φ(n) 互质
爱丽丝就在 1 到 3120 之间, 随机选择了 17(实际应用中, 常常选择 65537)
第五步, 计算 e 对于φ(n)的模反元素 d
所谓 "模反元素" 就是指有一个整数 d, 可以使得 ed 被φ(n)除的余数为 1
ed 1 (mod φ(n))
这个式子等价于
ed - 1 = kφ(n)
于是, 找到模反元素 d, 实质上就是对下面这个二元一次方程求解
ex + φ(n)y = 1
已知 e=17, φ(n)=3120,
17x + 3120y = 1
这个方程可以用 "扩展欧几里得算法" 求解, 此处省略具体过程总之, 爱丽丝算出一组整数解为 (x,y)=(2753,-15), 即 d=2753
至此所有计算完成
第六步, 将 n 和 e 封装成公钥, n 和 d 封装成私钥
在爱丽丝的例子中, n=3233,e=17,d=2753, 所以公钥就是 (3233,17), 私钥就是(3233, 2753)
实际应用中, 公钥和私钥的数据都采用 ASN.1 格式表达(实例)
七 RSA 算法的可靠性
回顾上面的密钥生成步骤, 一共出现六个数字:
p
q
n
φ(n)
e
d
这六个数字之中, 公钥用到了两个(n 和 e), 其余四个数字都是不公开的其中最关键的是 d, 因为 n 和 d 组成了私钥, 一旦 d 泄漏, 就等于私钥泄漏
那么, 有无可能在已知 n 和 e 的情况下, 推导出 d?
(1)ed1 (mod φ(n))只有知道 e 和φ(n), 才能算出 d
(2)φ(n)=(p-1)(q-1)只有知道 p 和 q, 才能算出φ(n)
(3)n=pq 只有将 n 因数分解, 才能算出 p 和 q
结论: 如果 n 可以被因数分解, d 就可以算出, 也就意味着私钥被破解
可是, 大整数的因数分解, 是一件非常困难的事情目前, 除了暴力破解, 还没有发现别的有效方法维基百科这样写道:
" 对极大整数做因数分解的难度决定了 RSA 算法的可靠性换言之, 对一极大整数做因数分解愈困难, RSA 算法愈可靠
假如有人找到一种快速因数分解的算法, 那么 RSA 的可靠性就会极度下降但找到这样的算法的可能性是非常小的今天只有短的 RSA 密钥才可能被暴力破解到 2008 年为止, 世界上还没有任何可靠的攻击 RSA 算法的方式
只要密钥长度足够长, 用 RSA 加密的信息实际上是不能被解破的 "
举例来说, 你可以对 3233 进行因数分解(61×53), 但是你没法对下面这个整数进行因数分解
1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413
它等于这样两个质数的乘积:
33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489
×
36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917
事实上, 这大概是人类已经分解的最大整数 (232 个十进制位, 768 个二进制位) 比它更大的因数分解, 还没有被报道过, 因此目前被破解的最长 RSA 密钥就是 768 位
八加密和解密
有了公钥和密钥, 就能进行加密和解密了
(1)加密要用公钥 (n,e)
假设鲍勃要向爱丽丝发送加密信息 m, 他就要用爱丽丝的公钥 (n,e) 对 m 进行加密这里需要注意, m 必须是整数(字符串可以取 ascii 值或 unicode 值), 且 m 必须小于 n
所谓 "加密", 就是算出下式的 c:
me c (mod n)
爱丽丝的公钥是 (3233, 17), 鲍勃的 m 假设是 65, 那么可以算出下面的等式:
6517 2790 (mod 3233)
于是, c 等于 2790, 鲍勃就把 2790 发给了爱丽丝
(2)解密要用私钥(n,d)
爱丽丝拿到鲍勃发来的 2790 以后, 就用自己的私钥(3233, 2753) 进行解密可以证明, 下面的等式一定成立:
cd m (mod n)
也就是说, c 的 d 次方除以 n 的余数为 m 现在, c 等于 2790, 私钥是(3233, 2753), 那么, 爱丽丝算出
27902753 65 (mod 3233)
因此, 爱丽丝知道了鲍勃加密前的原文就是 65
至此,"加密 -- 解密" 的整个过程全部完成
我们可以看到, 如果不知道 d, 就没有办法从 c 求出 m 而前面已经说过, 要知道 d 就必须分解 n, 这是极难做到的, 所以 RSA 算法保证了通信安全
你可能会问, 公钥(n,e) 只能加密小于 n 的整数 m, 那么如果要加密大于 n 的整数, 该怎么办? 有两种解决方法: 一种是把长信息分割成若干段短消息, 每段分别加密; 另一种是先选择一种 "对称性加密算法"(比如 DES), 用这种算法的密钥加密信息, 再用 RSA 公钥加密 DES 密钥
九私钥解密的证明
最后, 我们来证明, 为什么用私钥解密, 一定可以正确地得到 m 也就是证明下面这个式子:
cd m (mod n)
因为, 根据加密规则
me c (mod n)
于是, c 可以写成下面的形式:
c = me - kn
将 c 代入要我们要证明的那个解密规则:
(me - kn)d m (mod n)
它等同于求证
med m (mod n)
由于
ed 1 (mod φ(n))
所以
ed = hφ(n)+1
将 ed 代入:
mhφ(n)+1 m (mod n)
接下来, 分成两种情况证明上面这个式子
(1)m 与 n 互质
根据欧拉定理, 此时
mφ(n) 1 (mod n)
得到
(mφ(n))h × m m (mod n)
原式得到证明
(2)m 与 n 不是互质关系
此时, 由于 n 等于质数 p 和 q 的乘积, 所以 m 必然等于 kp 或 kq
以 m = kp 为例, 考虑到这时 k 与 q 必然互质, 则根据欧拉定理, 下面的式子成立:
(kp)q-1 1 (mod q)
进一步得到
[(kp)q-1]h(p-1) × kp kp (mod q)
即
(kp)ed kp (mod q)
将它改写成下面的等式
(kp)ed = tq + kp
这时 t 必然能被 p 整除, 即 t=t'p
(kp)ed = t'pq + kp
因为 m=kp,n=pq, 所以
med m (mod n)
原式得到证明
来源: http://www.jianshu.com/p/ffbfa1e96830