假如Alice和Bob需要经过一个不可靠媒介传送一条消息, 他们大概会把这条消息加密, 而普遍使用的字母移位法(凯撒加密法)太容易被破解, 所以他们可能会考虑使用更加安全的加密法.

在上个世纪70年代被麻省理工学院的三位教授发明的RSA加密算法就是一个足够安全的加密法, 当今互联网的SSL安全连接协议的重要加密算法就包括了RSA加密算法. 连接到你的网上银行, 查看这个安全连接的证书, 证书上很可能写的就是“RSA加密”.

当然, RSA被广泛使用的原因还有一个, 那就是它的加密钥匙是公开的, 也就是说, 任何人都可以使用公开的密钥给消息加密, 却无法给刚加密的消息解密.

现在, 若Alice需要接收一条来自Bob的消息, 她可以这样来生成密钥:

1. 随机选取两个不相等的较大素数p和q, 计算N=pq.

2. 根据欧拉函数, 计算不大于N且与N互质的正整数个数 φ(N) = (p-1)(q-1).

3. 选取小于φ(N)且与φ(N)互质的正整数e.

4. 选取小于φ(N)的正整数d, 使得e和d满足 (d×e) Mod φ(N)=1.

5. 将公钥N和e公开, 保存好私钥d, 销毁p和q的记录.

关于私钥d的计算, 在实际应用中经常通过对e做模逆运算来得到d, 而高效解模逆运算的算法就是扩展Euclid算法.

此时, Bob已经知道了公钥N和e, 对于他要发送的消息n (n<N), 他可以计算出把n加密后的消息c=n^e Mod N. Bob此时可以放心地把c发送给Alice了.

对于Alice收到的加密消息c, 她可以解密出原消息n=c^d Mod N.

这样解密的原理是: 因为 c≡n^e (Mod N), 所以 c^d≡n^ed (Mod N), 又因为(ed) Mod φ(N)=1, 根据费马小定理, 会有 n^ed≡n (Mod N) , 从而 n=c^d Mod N.

若中间偷听者Eve截获了密文c, 目前直接由公钥N, e,密文c导出原消息n的唯一方法就是将公钥N因式分解得到p和q, 计算得φ(N)后, 再由公钥e计算出私钥d, 而目前因式分解的较优算法仍然有O(n^1/2)的复杂度, 所以Eve想要还原消息n是相当困难的.

上个世纪90年代, 数百台计算机用了五个月的时间合作因式分解了一个长达512位的RSA-155号公钥N, 所以, 现代SSL安全协议对公钥N的要求是起码1024位, 而且φ(N)不应有过小的质因数, 所以在生成p,q时, 通常是选取随机值再用Miller-Rabin测试来检验随机值是否为素数.

现在的RSA加密算法看起来无懈可击, 但是若多项式时间的因式分解算法被发现, 或者能在多项式时间内分解因式的量子计算机被发明, 那么RSA也会变得跟凯撒加密法一样脆弱, 到那时, 我们就需要发明新的加密传输方法了.

参考资料:

1. Classical and Contemporary Cryptology, Richard Spillman.

2. RSA entry from Wikipedia.