本页面已浏览320次
公钥密码就是所谓通过公开的加密方法加密而得到的密码，也就是说，所有人都可以进行加密。但只有接收方才可以解密一个被加密的信息。
所谓的公钥密码是如何工作的？答案是：有些数学运算很容易进行，但有些却非常困难。我们本章讨论一种特定的公钥密码体系，它被称为RSA加密，并首先由Ronald Rivest，Adi Shamir和Leonard Adelman发布。
假定我们选择两个非常大的素数——比如说，各有200位数字。然后将它们相乘。然后将结果告诉一位朋友，要他进行分解。将两个数字相乘对计算机而言是很容易的，但要将一个数字分解成两个数字的乘积就十分困难。
所以，我们可以将这个400位的数字公诸于世，但其分解方式却只有我们知道。但是，“谁会在乎一个400位数字的分解呢？”答案是：你必定在乎。无法分解一个数字正是公钥加密系统的核心。
首先来看几个定理。
定理5.1：如果\(p, q\)是两个不同的素数，而\(W\)是一个自然数且\((W, pq)=1\)，那么\(W^{(p-1)(q-1)}\equiv 1\pmod{pq}\)。
证明：
这个证明不难。根据定理4.21：
定理4.21：令\(m, n\in\mathbb{N}, (m, n)=1, a\in\mathbb{Z}\)。\(x\equiv a\pmod{m}\)且\(x\equiv a\pmod{n}\implies x\equiv a\pmod{mn}\)。
以及费马小定理就可以证明。
定理5.2：令\(p, q\)是两个不同的素数，\(k\)是一个自然数，而\(W\in\mathbb{N}, W\lt pq\)，那么\(W^{1+k(p-1)(q-1)}\equiv W\pmod{pq}\)。
证明：
先假定\((W, pq)=1\)，那么根据定理5.1，有\(W^{(p-1)(q-1)}\equiv 1\pmod{pq}\implies (W^{(p-1)(q-1)})^k=W^{k(p-1)(q-1)}\equiv 1\pmod{pq}\implies W^{1+k(p-1)(q-1)}\equiv W\pmod{pq}\)。
如果\((W, pq)\ne 1\)，我们不妨先假设\(p\mid W\)，于是\(W\equiv 0\equiv W^{1+k(p-1)(q-1)}\pmod{p}\)。注意到，此时\((W, q)=1\)，于是\(W^{1+k(p-1)(q-1)}=W\times W^{k(p-1)(q-1)}=W\times (W^{k(p-1)})^{q-1}\equiv W\times 1\equiv W\pmod{q}\)。同样可以得到\(W^{1+k(p-1)(q-1)}\equiv W\pmod{p}\)。由于\((p, q)=1\)，所以\(W^{1+k(p-1)(q-1)}\equiv W\pmod{pq}\)。QED。
（补充一个定理）
补充定理：\(\phi(ab)=\phi(a)\phi(b)\iff (a, b)=1\)。
这个定理其实可以帮助证明上面的两个定理，而且更快。
定理5.3：令\(p, q\)为两个不同的素数，而\(E\in\mathbb{N}, (E, (p-1)(q-1))=1\)，那么存在一个自然数\(D\)，使得\(ED=1+y(p-1)(q-1)\)。
证明：（略）
定理5.4：令\(p, q\)为两个不同的素数，而\(W\in\mathbb{N}, W\lt pq\)，而\(E, D, y\in\mathbb{N}, ED=1+y(p-1)(q-1)\)，那么\(W^{ED}\equiv W\pmod{pq}\)。
证明：（略）
我们已经有了构造RSA公钥加密系统的所有组件。我们将通过如下的练习来探索如何构造RSA加密。
请自行研究这个过程和之前提到的那些定理有怎样的关联。
让我们来用几个比较小的素数进行如上所述的过程。
本例中令\(p=61, q=53\)。
\(n=p\times q=61\times 53=3233\)
我们可以借助工具得出\(\phi(3233)=(p-1)\times(q-1)=3120\)。
我们随便挑一个，比如\(e=17\)。
\(d=2753\)
最后得到公钥对\((3233, 17)\)，私钥对\((3233, 2753)\)。
RSA加密、解密的准备工作已经完成！
我们来看看如何加密。
假定我们要对数字\(65\)（你也可以把它认为是字母A）进行加密。
首先，计算\(m^e\equiv c\pmod{n}\)，也就是\(65^{17}\)除以\(3233\)的余数。该余数是\(2790\)。
我们可以将\(2790\)交给拥有私钥的对方，他将这样来解密：
\(2790^{2753}\equiv 65\pmod{3233}\)
我们重新得到了\(65\)！加密、解密工作全部完成！
思考问题是：如何在得到公钥和密文的情况下进行破解？
RSA加密系统有两个键，一个是公开的加密键，一个是私有的解密键。这样的系统被称为非对称加密，与之相对应的就是所谓对称加密。在实际使用中，RSA在加解密大量数据时并不是很有效，而所谓的AES（
Advanced Encryption Standard
）更有效——但要求在发送方和接收方间传递一个密钥，而传递密钥的过程可能存在风险。
所以在实践中，往往采用混合加密方式：用RSA方式加密AES的密钥。然后在发送给对方的时候，发送两个内容：一个是经RSA加密的AES密钥，一个是经AES加密的密文。对方首先用RSA私钥解密得到AES密钥，然后再用AES密钥解密密文。所以，RSA更多地用在密钥的交换。
RSA的强度取决于这样一个事实：因子分解非常困难。有多难？按照RSA官网的说法，2005年11月，30个2.2G的CPU用了5个月才将一个193位的数字进行了因子分解。
但是，因子分解并不是唯一困难的问题。
1970年中期，斯坦福大学研究生Whitfield Diffie和他的导师Martin Hellman基于计算logarithms modulo \(p\)开发了一种公钥交换系统，也就是著名的Diffie-Hellman加密。
1980年中期，Victor Miller和Neal Koblitz独立地提出使用所谓椭圆曲线（Elliptic Curves）来生成公钥密码。目前认为，这个方法比上面提到的Diffie-Hellman方法更难破解。
这些都是数论在实践中的应用。数论学家进行基础工作时，根本想不到这些成就会有这样的实际应用。但是，公钥加密这一应用表明，人们应该继续探究数学和科学领域的那些想法，因为这些想法是美的。实践应用早晚必然会出现。