算法篇——小谈RSA加密算法

18 October 2013

数论一直被认为是一种无用的学科，尽管其拥有美妙的数学原理。想想看，就算你解决了那著名的“哥德巴赫猜想”，那又有什么实际用处呢？它不像那些经典的牛顿定律，拥有广阔的实际应用。谢天谢地，基于大素数的加密算法让数论得以走下神坛，走进人类的世界，没有这些加密算法，试想一下，在这个网络时代会多么没有安全感。

之前写过一篇博客——《加密永胜》来阐述加密对整个网络安全的意义，今天我就来讲讲基于大素数的RSA加密算法。

要说RSA，总要知道RSA三个字母是什么意思，为什么叫这个吧？RSA实际上是该算法的三名设计者Rivest、Shamir 和 Adleman，当然就用设计者的名字来命名啦。

在早期，一直被广泛使用的“对称加密算法”，即甲用什么方法加密，乙就用什么方法解密。问题就出现了，我与你通信，总要告诉你加密方法吧，那这个告知过程如果被窃听，那不是无论怎么加密第三方都会解密的了么，总不会给加密方法再加密传输吧。

于是，类似RSA的“非对称加密算法”得到了广泛的应用。其主要原理是：乙方生成两把密钥（公钥和私钥）。公钥是公开的，任何人都可以获得，私钥则是保密的。甲方获取乙方的公钥，然后用它对信息加密。乙方得到加密后的信息，用私钥解密。这种方法，只要保存好私钥，妈妈就再也不用担心我的网络通信安全了。

RSA的基本原理，当然也可以称作流程或方法如下：

1 随机选取两个不同的素数p和q，令N = pq。

2 找到与(p-1)(q-1)互素的整数e。

3 计算出e的乘法逆元d。

4 P=(e, N)作为RSA的公钥。

5 S=(d, N)作为RSA的私钥（秘钥）。

6 加密过程为(x^e)^d ≡ x mod N。(^表示求指数，下同)

什么是逆元？如果x可以使ax ≡ 1 (mod n)成立，则x是a模n的一个乘法逆元。举个例子，要计算11模25的逆元，即找到一个x，使ax模25时等于1，我们可以得到x为-34。展开写就是15·25-34·11=1。

那我们再来举一个RSA的例子。取p=5，q=11，那么N=pq=55。找到(p-1)(q-1)=40的互素的整数e=3，计算出e的逆元d=27。到此，RSA算法已经发成。比如我们发送x=13，加密后，即为y = x^e mod N = 13^3 mod 55 = 52。解密端则得到x = y^13 mod N = 52^27 mod 55 = 13。

为什么(x^e)^d ≡ x mod N会成立？我们来证明一下其可行性。因为e与(p-1)(q-1)互素，则ed ≡ 1 mod (p-1)(q-1)，即存在k使得ed = 1+k(p-1)(q-1)。所以：

x^ed - x = x^[1+k(p-1)(q-1))] - x = x[x^k(p-1(q-1)) - 1]

根据费马小定理：

x^(p-1) % p = 1
y^(q-1) % q = 1
x^(p-1)(q-1) % pq = 1（替代准则）
x^k(p-1)(q-1) % N = 1

所以：

x^ed - x (mod N) = x^[1+k(p-1)(q-1))] - x (mod N) 
                 = x[x^k(p-1(q-1)) - 1] (mod N) = 0
(x^e)^d ≡ x mod N

得证。

那RSA的安全性到底好不好呢？其安全性主要来源于对大整数进行因子分解的困难性。一种方法是尝试所有的x，以满足y = x^e mod N，这实在是太费时的工作。还有一种方法就是尝试因子分解N，得到p和q，再依RSA算法求得d。可是大整数分解何其难也。多大整数算大啊？几百位的基本上就难以破解了。

本文讲述了RSA加密算法的基本原理和加密方法，并证明了这种算法的可行性，以及分析了RSA加密算法的破解难度。另外关于更加细节的内容，如费马小定理、逆元的求法，素数的求法等，本文不过多介绍。最后要说，多亏了RSA加密算法，让我们的网络更加安全！

参考资料：

algorithm 5

algorithm 5