Math in CS: 数论和公钥密码学

1940年，英国数学家哈代在他的一本小书《一个数学家的辩白》(A Mathematician's Apology)中说：“如果有用的知识是这样的知识（我们暂时同意这样说）：它大概会在现在或相对不远的未来，为人类在物质上的享受方面作出贡献，因而，它是否在单纯的智力上满足人们乃是无关紧要的，那么，大量更高级的数学就是无用的。现代几何和代数、数论、集合论和函数论、相对论、量子力学——没有一种比其它的更经得住这种检验，也没有真正的数学家的生涯可以在这个基础上被证明是有价值的。”但是我们会看到，哈代这个断定在当时“不远的未来”几乎被一一证明是错误的，数论就是其中一个。

在 1970 年代以前，人们所知道的密码学都是对称密码学，就是在加密和解密过程中需要使用同一个密钥。在那个时代，一些密码算法已经能保证足够的安全性，比如数据加密标准 DES。但是人类的需求是很难完全得到满足的，他们为每次密钥交换的复杂度而苦恼，比如在战时如果密码本被敌方获得，就必须重新向无线电收发员分发密码本，这个工作量和代价是相当大的；还有一个需求就是数字签名，能不能用加密实现对数字文件的签名，像手写的签名一样，确保该文件出自谁人之手？

上述问题，就是 Whitfield Diffie 和 Martin Hellman 1976 年在他们那篇划时代的论文《密码学的新方向》(New Directions in Cryptography)中提出的，他们也给出了其中一个问题的解决办法，那就是 Deffie-Hellman 密钥交换算法（后来被改为 Deffie-Hellman-Merkle 密钥交换算法，里面还有一段小故事。）。但是 DH 没做完的功课，仅仅在一年后就被 RSA 解决了，那就是 Ron Rivest, Adi Shamir, 和 Leonard Adleman 的 "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems"。RSA 的加密和解密使用的是不同的密钥，即公钥和私钥，你可以将你的公钥扔到世界上任何一个位置，我用你的公钥加密一段信息，除了你用自己的私钥解密，没有别的人能从中得到原始消息。就相当于你把打开了的箱子扔的满世界都是，但箱子一旦锁上，就只有你能再打开。

RSA 算法自其诞生之日起就成为被广泛接受且被实现的通用公钥算法，但是 RSA 算法还带来一个另外的意义，那就是：数论知识从未像现在这样被广泛地使用着。RSA 程序的普及率要远远大于 Windows，因为每台 Windows 上都装配着 RSA 算法程序，但 RSA 并不仅仅装配 Windows。每当你登录邮箱、网上银行、聊天软件、安全终端，你都在使用着数论带来的好处。而且相比之前密码学的字母替换和置换，混淆和扩散，DH 和 RSA 使用的东西更有资格说自己是数学。

大概也是由于其基于数学的简洁性，RSA 和 DH 算法描述要比 DES, AES 简练许多，我在这篇小文中都能写完。

RSA

RSA 用到了数论中的三个基本定理：费马小定理、欧拉定理和中国剩余定理（几乎处处都在），和一个古典难题：大整数分解问题。如果你是数学系的学生，对这些概念一定不会陌生。

费马小定理：若 p 是素数，a 是正整数且不能被 p 整除，则： a^p-1 = 1(mod p)。或者另一种形式：a^p=a(mod p)，这种形式不要求 a 与 p 互素。

欧拉定理：对任意互素的 a 和 n，有 a^Φ(n) = 1(mod n)。其中，Φ(n)是欧拉函数，即小于 n 且与 n 互素的正整数的个数。

大整数分解问题：将两个整数乘起来是简单的，但是将一个整数分解为几个整数的乘积是困难的，尤其是当这个数比较大的时候。迄今为止没有有效的算法来解决这个问题，甚至我们连这个问题的计算复杂度量级是多少都不知道。

那么 RSA 算法是什么样的呢？

密钥的产生：
1. 选择两个素数 p 和 q.
2. 计算 n = p*q.
3. 计算 Φ(n) = (p-1)(q-1) （这是欧拉函数的性质）
4. 选择 e<Φ(n) 并使得其与 Φ(n) 互素。
5. 确定 d<Φ(n) 并使得 d*e = 1(mod Φ(n))。
6. 这时候，私钥就是{d, n}，公钥就是{e, n}。
加密算法：
假设 M 是明文（M<n），那么密文就是 C = M^emod n。（为什么明文是数字？在计算机科学里任何数据最终表示都是数字。）
解密算法：
假设 C 是密文，那么明文就是 M = C^d mod n。

我们来证明一下算法是否正确，由于 C^d = M^e*d = M^k*Φ(n)+1 (mod n)。

如果 M 和 n 是互素的，显然直接由欧拉定理我们就能得到：
C^d = M^k*Φ(n)*M¹ = M (mod n) = M
说明算法是正确的；
如果 M 和 n 不互素，由于 n 是两个素数 p 和 q 的乘积且 M<n，那么 M 要么是 p 的倍数，要么是 q 的倍数，由 e*d = 1(mod Φ(n)) = 1(mod (p-1)(q-1)) 我们可得：
e*d = 1(mod (p-1)) 且 e*d = 1(mod (q-1))
则 e*d 可以写成： e*d = k*(p-1)+1, e*d = h*(p-1)+1
由费马小定理，我们有：M^e*d = M^k*(p-1)+1 = M(mod p) 和 M^e*d = M^h*(q-1)+1 = M(mod q)。
由于 p 和 q 均为素数，且 p, q 均整除 M^e*d-M，所以我们有：
C^d = M^e*d = M (mod p*q) = M (mod n) = M

从上面我们可以看到 RSA 算法实现了加密和解密使用不同密钥，而且证明了这个算法的正确性。但 RSA 算法要想实用，光有正确性还不够，最重要的一点是安全性，即从公钥{e, n}无法推导出私钥{d, n}。在 RSA 算法中我们可以看到，关键要知道 Φ(n)，知道了 Φ(n)，使用欧几里德算法就能求出 e 的逆元，就得到了用户的私钥{d, n}。要求出 Φ(n)，就必须知道 p,q，但 p,q 是不公开的，仅仅知道 p,q 的乘积 n 去求 p,q，根据大整数分解古典难题，当 n 比较大时其分解在计算上是不可行的。这就保证了 RSA 算法的安全性。

而且 RSA 算法是可逆的，所以它就有能力同时实现加密和签名的功能。由于公钥是公开的，每个人都可以用你的公钥加密一段信息发给我，而私钥是保密的，所以只有你能看到别人用你的公钥加密的消息；而也因为可逆性，如果你用私钥解密一段明文（实际是加密），所有人都可以用你的公钥加密它来得到明文（实际是解密），因为私钥只有你一个人知道，这个消息只有可能是你发出的，就相当于你对这段明文做了一个签名。

DH 密钥交换算法

DH 密钥交换算法较 RSA 算法更为简单，它也是基于数论中的一个古典难题：离散对数问题。

离散对数问题：若 p 是素数，p 已知，考虑方程 y = g^x mod p，给定 g,x 求 y 是简单的，但给定 y,g 求 x，即求 x = log_g,py mod p，在计算上是不可行的。

DH 密钥交换算法的描述如下：
已知公开的素数 p 和 p 的本原根 α
1. 用户 A 选择秘密的 Xa<p，计算 Ya = α^Xa mod p，将其发送给 B。
2. 用户 B 选择秘密的 Xb<p，计算 Yb = α^Xb mod p，将其发送给 A。
3. A 和 B 分别计算 Ka = (Yb)^Xa mod p 和 Kb = (Ya)^Xb mod p，就同时得到了共享的密钥 K=Ka=Kb，然后就可以用 K 进行加密传输了。

DH 密钥交换算法的优点在于：双方在通信前不需要知道任何共享的密钥，而是通过公开的 p 和 α 协商出一个密钥来进行加密通信。

先看一下算法的正确性，Ka = Kb 是否成立：
Ka = (Yb)^Xa = (α^Xb)^Xa = α^Xa*Xb (mod p)
Kb = (Ya)^Xb = (α^Xa)^Xb = α^Xa*Xb (mod p)
Bingo! Ka 和 Kb 是相同的。

再来看一下算法的安全性，就是能否从公开的信息推导出 K 来：
由于密钥是 K = α^Xa*Xb，那么攻击者必须知道 Xa 和 Xb 才能得到共享的密钥 K，而公开的信息只有 Ya 和 Yb，由离散对数问题，从 Ya,Yb 求出 Xa,Xb 在计算上是不可行的，就保证了算法的安全性。

从上面两个算法我们可以看出，数论在公钥密码学中的重要地位，恐怕哈代当时怎么也想不到三十多年后人人都在使用他所认为在实际生活中毫无用处的数论吧！