[ 转载 ] 解开人人网登录密码的 RSA 加密

我很少转载别人的文章的。但这篇确实让我眼前一亮，希望各位看客也能有所收获。

From 91ri ： http://www.91ri.org/8928.html

世界上有两种密码：一种是防止你的小妹妹偷看你的文件；另一种是防止当局阅读你的文件。
—— Bruce Schneier《应用密码学》

传说中的 “明文密码” 有两种形式：明文传输和明文存储。明文传输的密码不一定明文存储，明文存储的密码也不一定明文传输。去年沸沸扬扬的明文密码事件，就是密码明文存储，网站的数据库一旦被窃取，用户的密码也就随之失窃了。密码明文传输也是非常危险的，网络中的很多位置都可能安装有嗅探装置，明文传输的密码对这些嗅探者来说也就无密可言了。本文关注的是密码传输中的安全问题。

什么是 “明文”？如果密码以 ASCII 字符的形式直接发出去，对任何人来说这都是明文；如果密码用 base64 编码一下（例如 123456 经过 base64 编码就是 MTIzNDU2），对多数人来说这也许是密文，而对任何专业程序员来说就是明文。有些人认为，把“加密”算法弄得复杂些，再用代码混淆工具弄乱，就没人能分析出来了。这样的做法叫做隐藏，而不是安全，属于防止小妹妹偷看文件的级别。真正的安全依赖于公开的、被广泛使用的密码学算法，靠密钥而不是算法本身来保证安全。

可惜，密码学算法和协议并不是随便拼凑起来就安全的。

观察人人网密码传输

很久很久以前，人人网的密码是使用没有经过任何编码的明文传输的。现在，人人网的登录密码是加密传输的。在浏览器的开发者工具中查看登录人人网的那个 HTTP POST 请求（/ajaxLogin/login），就能发现密码变成了长长的一串。

我最初想到的就是 hash 了，会不会是把用户输入的密码和 rkey 做某种运算，然后取 hash 值作为 password 呢？尝试字符串连接和常见的 hash 算法，发现并不是这样的。这个 rkey 是从哪里来的呢？ /getEncryptionKey HTTP 请求会返回包括 rkey 在内的一些数据。我看到 e: “10001″ 就猜到这可能是 RSA 加密，不过暂且按下不表。

插一句，这里发现一个重放攻击漏洞，在成功登录之后，rkey 并没有失效。使用同样的 POST 请求在大洋彼岸的机器上仍然可以成功登录，而且即使原来的用户登出也不影响 POST 登录的可用性，只有修改密码或者等足够长的时间才能使这个被嗅探到的 POST 请求无效。对想窥探他人隐私的脚本小子来说，这也许就足够了。但我们的目标是恢复明文密码，岂能就此止步？

分析混乱 JS 代码

看来，我们必须看源码了。人人网登录是 login-v6.js 处理的，这段 JavaScript 代码经过了混淆，用 JSBeautifier 处理后就好看多了。（处理后的代码片段如下图所示）

初学编程时，老师告诉我们 “程序要从 main 函数读起”，但对任何有一定规模的程序来说，如果从 main 读起，恐怕找到关心的代码片段时头发都白了，更可能的是还没找到关心的代码片段，大脑的栈先溢出了。不信你可以读读下面这段代码（RSA 加密库的一部分），读懂的举手。

分析大型程序的有力武器也许是字符串查找（grep）。这些字符串或者魔术数字（magic number）或者是屏幕上的提示，可以让我们知道这段代码的作用；或者是某个库的标识字符串。

从上面贴的第一段代码（用户输入密码）开始找，可以找到上面贴的第二段代码，这第二段代码看起来像是某些数学操作。其中的一组魔术数字泄露了天机：

在 Google 中搜索这两个魔术数字，估计是某个库的一部分：

进一步搜索可以发现，这是一个纯 JavaScript 实现的开源 RSA 库，主页是http://www.ohdave.com/rsa/。跟混淆过的人人网代码一对比，确定无误。大致过程如下：

1.浏览器发起 getEncryptionKey 请求，服务器生成一对 256 位的 RSA 公私钥，随机生成一个 rkey，以 rkey 为索引把公私钥存储起来。

2.服务器把 e（固定为 16 进制的 10001）、n（16 进制表示的 256 位公钥）、rkey 发回给浏览器。

3.用户输入密码并点击登录时，浏览器把密码用公钥 n 和指数 e 加密，得到 password（16 进制表示的 256 位），连同 rkey 发送给服务器。

4.服务器根据 rkey 取出私钥，解密 password 得到明文密码，然后就是常规的密码检查流程了。

看到 “RSA” 这个字眼，很多人也许认为破解无望了；而我分析到这里，就仿佛看到了胜利的曙光。

RSA 为什么需要长密钥

1976 年，Diffie 和 Hellman 发表了世界上第一个基于公开密钥的公共秘密生成协议，掀开了密码学史上新的一页。在此之前，人们一直认为在双方事先没有共同秘密的情况下，不可能在被监听的信道上实现安全通信，而 Diffie-Hellman 协议正是在被监听的信道上安全地生成共同秘密的算法。一年后的 1977 年，Rivest，Shamir 和 Adleman 发表了 RSA 公开密钥加密算法。

公开密钥密码学本质上是基于一些历史悠久的数学难题，如背包问题、离散对数问题、因子分解问题。Diffie-Hellman 算法是基于离散对数问题，而 RSA 算法是基于因子分解问题。每个公钥都是一道数学难题，只要攻击者设法解出了这道难题，就能得到私钥、解密信息。这跟我们通常说的 “用密码加密”（学名对称加密）完全是两回事。

对称加密的安全性依赖于密码的保密性，对理想的对称加密算法，只能穷举所有密码来解密，因此 16 位大小写字母加数字的随机密码大致相当于 96 位二进制，也就是平均要试验四万亿亿亿次才能猜出密码，有生之年是试不出来的。而 96 位（二进制）规模的数学难题在计算机面前根本算不上什么难题，分解这么大的合数，1 秒钟足够了。

我们常见 RSA 的密钥长达 2048 位、4096 位，而对称密钥 128 位、256 位就足够了，公开密钥往往比对称密钥长很多，就是这个道理。

让我们具体看看 RSA 是如何工作的。首先找两个位数相同的大质数 p 和 q，计算它们的乘积 pq 作为公钥 n。计算 φ(n) = φ(p)φ(q) = (p − 1)(q − 1)。选取与 φ(n) 互质的 e 作为指数（exponent）。欲加密信息（message）设为 m，me mod n 就是密文（cipher-text）。为了快速加密，在实际中这个 e 一般取定值，例如 e = hex 10001 = 65537，这样加密只需要 17 次乘法。

解密的时候，找 d 使得 de mod φ(n) = 1，这可以用辗转相除法快速求得，不再赘述。只需计算密文的 d 次幂 cd mod n 即可还原出明文 m。这里 d 就是私钥。这里的数学原理是 med – 1 mod n = 1，这又是由于欧拉函数 φ(n) 的性质，感兴趣的可以查阅 Wikipedia。

我们已经知道，RSA 公钥 n 就是两个大质数 p 和 q 的乘积。只要把这两个质数因子求出来，就可以得到私钥 d，进而解密信息。人人网用了 256 位的 RSA 公钥，也就是一个 77 位的十进制整数，在个人 PC 上两三分钟就可以分解，这就是短公开密钥的可怕之处。

分解质因数

我们都学过的分解质因数做法，是试除法，从 1 到根号 n 一个个试一遍。对 77 位的十进制整数，需要试除 1038 次，这显然是不可接受的。

费马的平方差公式

费马的质因数分解算法是在试除法和筛法之后的第一次重大改进。这个算法的出发点是平方差公式 (a-b)(a+b) = a2 – b2。如果我们找到两个小于 n 的正整数 u 和 v，u + v ≠ n，且 (u2 – v2) 能被 n 整除，则 (u+v)(u-v) 能被 n 整除。由于 n 是两个质数 p 和 q 的乘积，u+v 和 u-v 都不能被 n 整除，那么 p 和 q 两个因子只好分居 u+v 和 u-v 中了。u-v 与 n 的最大公约数就是 p 或者 q。计算 u-v 与 n 的最大公约数是个很快的过程，与把它们相乘的时间复杂度是相当的。

例如，n = 2041，u = 1416，v = 311，可以验证 (u2 – v2) 能被 n 整除，则取 u-v 与 n 的最大公约数 (1416-311, 2041) = 13，13 必为 n 的一个质因数。事实上 2041 = 13 × 157。

问题是，去哪里寻找这样的 u 和 v 呢？一种方法是令 u = sqrt(n)（根号 n 上取整，即 u 是不小于根号 n 的最小正整数），看 (u2 – n) 是否平方数，如果是则 u2 – n = v2。如果不是则递增测试更大的 n。例如，n = 2041，sqrt(n) = 46，试验过程如下：

46*46 – 2041 = 75
47*47 – 2041 = 168
48*48 – 2041 = 263
49*49 – 2041 = 360
50*50 – 2041 = 459
51*51 – 2041 = 560
……

显然，这条路走不远。

乘积是平方数也行

在上述 (u2 – n) 中，如果其中的某几个的乘积是平方数，那么也行。在上面的例子中，假如我们突然发现 75 * 168 * 360 * 560 是平方数，那么 (462 – 2041) * (472 – 2041) * (492 – 2041) * (512 – 2041) = 75 * 168 * 360 * 560 = 504002。

注意到我们想找的平方关系是 mod n 的，那么就有 462  472  492  512 mod 2041 = 504002 mod 2041，也就是 (46474951)2 mod 2041 = 504002 mod 2041。u = 464749*51 mod 2041 = 311，v = 50400 mod 2041 = 1416，这就是我们要找的 u 和 v。

问题又来了：怎么找到 75, 168, 263, 360, 459, 560… 中哪些的乘积是平方数呢？聪明的读者也许会想到，对这些数进行质因数分解，然后只要找到若干个数，使得它们质因子分解式中每个质数的幂次之和为偶数，这些数的乘积就是平方数。例如

75 = 3 * 52
168 = 23 * 3 * 7
360 = 23 * 32 * 5
560 = 24 * 5 * 7

上述四个数对 2、3、5、7 的质因子的幂次加起来，分别是 10、4、4、2，都是偶数，因此它们的乘积 = (25  32  52 * 71)2 是平方数。

筛出“容易分解”的数

分解质因数并不容易，即使对 (u2 – n) 这样比较接近 n 的数，仍然是相当费时间的。不过我们已经接近终点了！我们可以只考虑能被比较小的质数整除的数。如果要求 1~N 的范围内能被小于 B 的素数整除的数，最常用的就是筛法，我们在求 1~N 的质数时都使用过。首先划掉所有 2 的倍数，接着划掉所有 3 的倍数……划掉所有质数的倍数后，剩下的就都是质数了。

现在我们要求的是 u=0,1,2… 构成的 (u2 – n) 序列中的质数。筛法在稍微修改之后仍然能用。在筛掉 p 的倍数时，我们不需要一个个试除 p。如果 (u2 – n) 能被 p 整除，那么 u2 mod p = n mod p。由于 p 是质数，这样的小于 p 的 u 最多有两个（当然也可能没有）。用某个比较快的算法求出一个 u 后，(n – u)2 mod p = n mod p，就找到了另一个 u，在 mod p 的意义下可以称为 -u。在 ±u 的基础上加 p 的倍数，其平方 mod p 仍然与 n 同余。因此我们只要划去数组下标为 u, u+p, u+2p, u+3p… 和 -u+p, -u+2p, -u+3p… 的元素，就能筛掉所有 p 的倍数。

由于我们是要做质因数分解，不能把这些 p 的倍数删掉，而是要不断除以 p，直到不能除尽为止，这样就得到了这个元素中 p 的幂次。

例如，对 n = 2041，取 B = 10，也就是只找小于 10 的质数，即 2、3、5、7。如果一个 (X2 – n) 在经过筛子后变成了 1，则说明这个数是可以被完全分解为 2、3、5、7 的乘积的；否则，这个数不被考虑。

把上表中能被完全分解的数取出来，记录它们对 2、3、5、7 的幂次：

找出平方数乘积

由于我们的目标是找出若干个数的乘积是平方数，也就是幂次之和为偶数，我们只对幂次的奇偶性感兴趣，因此全部 mod 2 得到下表：

我们要找出若干列，使得这些列之和为偶数，或者说这些列 mod 2 之和为零向量。这不是标准的线性方程组吗？是的，高斯消元法可以派上用场了（事实上可以采用更高效的 Lanczos 算法）。

我们得到三组非平凡解：(46, 47, 49, 51)，(51, 54)，(46, 53)，事实上得到一组解就足够了。这三组解都分别对应一组 (u, v)，进而得到 n = 2041 的质因数：

(46, 47, 49, 51): 46*47*49*51 mod 2041 = 311，23 * 32 * 52 * 7 mod 2041 = 1416，(1416 – 311, 2041) = 13
(51, 54): 51*54 mod 2041 = 713，22 * 52 * 7 mod 2041 = 700，(713 – 700, 2041) = 13
(46, 53): 46*53 mod 2041 = 397，24 * 3 * 5 mod 2041 = 240，(397 – 240, 2041) = 157

在实际计算的时候，像 459 = 33 * 17 这样的分解未必要扔掉，最后剩下的 17 可以保存在临时表里，如果恰好有另一个数也分解出了 17，例如 u = 52 时 663 = 3 * 13 * 17（假定用于筛法的质数集合包含 2、3、5、7、11、13），这个 17 就配上了对，仍然是可以用的。如果找不到配对，不能完全分解的数就只能扔掉了。

上述算法基本上是基于初等数论的，也不算复杂，但这个被称为二次筛法（quadratic sieve）的算法至今仍是小于 100 位十进制数质因数分解的最快算法。

实战 RSA 分解

很多科学计算软件都已经内置了大数分解功能，并不需要自己实现高精度计算。这里我用了一个小巧的开源工具 msieve，实现了包括二次筛法在内的质因数分解算法。

把前面给的人人网公钥拿进来分解：

$ ./msieve 0x8ca2ddaf2a8da3c3c6ed795b87eca0d33827c82b31b6282a5045bc75e9b83153

在 Core i7 的个人 PC 上（msieve 是单线程的），用时 2 分 55 秒（换用不同的 256 位 RSA key 试验，分解用时在 2 到 4 分钟之间），完整的输出如下。

其中，前面 170 秒用来筛出“容易分解”的数，后面 4 秒用来解线性方程组。从这段输出中我们看到，为了分解这个 77 位的整数，选取 B = 919223，也就是用 B 以下的 36471 个质数进行筛选。而被筛选的 u 的范围则是 12 * 32768 = 393216。在这些 u 中，找到了 19614 个能在 B 的范围内被完全分解的数；还有 188575 个数不能被完全分解，但它们除掉 B 以下所有质数后的“尾巴”能够配对，形成了 16981 个能够配对的“尾巴”。经过一些优化之后，得到一个大约 2 万阶的矩阵，求出了 n 的质因数分解：220575968563521666214098235031226805271 和 288388433467298454747300239713114570277（十进制），它们都是 39 位的整数。

见证奇迹的时刻就要到了。首先，计算 φ(n) = (p-1)(q-1)，然后计算 e = 65537 在 mod φ(n) 意义下的乘法逆元 d：

然后把密文（HTTP POST 请求中的 password）c = 0x8a6a4d053859f6a35b6532fc15062f9b1f08535e9fc238e0c1d13cdf78c72247 传进来，求 cdmod n，就得到了明文密码 0x64726f7773736150656854746f4e734973696854。

用 ASCII 字符显示出来，就是 drowssaPehTtoNsIsihT。人人网所用的 RSA 库在将密码字符串转换成整数时，字符串的开头是低位，字符串末尾是高位，因此我们刚才输入的密码是 ThisIsNotThePassword。任务完成！

漏洞还没完

如果人人网的程序员把 RSA 密钥改成 2048 位就去睡大觉了，那么这个加密还是不堪一击。我们假定用户的密码是 ruby1111（扯一句，很多人都在用四位字母加四位数字的密码吧），按照人人网所用 RSA 库的方法，字符串长度不足时末尾补零，变成整数后就是高位补零。也就是用于加密的消息 m = 0×3131313179627572。

我们对 m = 0×3131313179627572 进行因子分解：m = 2 * 17 * 397 * 193679 * 1355887523。这些因子可以组合成两个相近的整数：m = 2614279142 * 1355887523，这两个整数都是 232 以内的，设 a = 1355887523，b = 2614279142。由于 c = me mod n = (ae mod n) * (be mod n) mod n，我们有 (c / (ae mod n)) mod n = be mod n。也就是，我们只要在 232 范围内找到 a 和 b 满足上式，就能还原出 m。

有了公开的 n（2048 位）和 e = 0×10001，对 b = 1,2,… 232，分别计算 be mod n，并保存在一张大 hash 表里。然后对 a = 1,2,… 232，分别计算 (c / (ae mod n)) mod n，其中除法可以用前面提到的求乘法逆元来实现。一旦发现结果在大 hash 表里，则找到了一组满足条件的 a 和 b，乘起来就得到明文 m。

为什么说这样的攻击是有效的呢？首先，相当比例的大整数可以分解成两个相差不大的整数之积，这使得上述“打表”攻击成为可能；其次，上述攻击恢复长度为 L 的明文，只需要 O(2L/2) 的时间和空间复杂度，也就是密码的有效长度减小了一半。

不要把明文直接传入 RSA 算法

密码学教材和 Wikipedia 上似乎都把明文直接作为 m，直接乘上 e 次幂 mod n 作为密文。而在广泛使用的 PKCS 等加密标准中，要么是把明文用随机填充字节补齐到 n 的位数，要么是生成另一个随机字符串作为 m，再用 m 作为对称密钥来加密明文。

人人网所使用的 RSA 库要防御上述攻击，最简单的修改方法是模仿 PKCS 最初版本，不要在明文密码前补零，而是先补一个 0xFF 字节，再用非 0xFF 的随机字节填充到 n 的位数（如 2048 位公钥，补齐到 256 字节）。这里的伪随机数生成器一定要使用比较好的种子，千万不能搞成确定的序列。服务器端解密后，从高位开始找到第一个 0xFF，这个 0xFF 后面的就是原始明文密码。当然，这种做法在寻找 0xFF 的过程中是存在时间攻击（timing attack）的，只是利用这个信息恢复明文需要发送相当大量的请求，在 Internet 上并不现实。

结语

我不希望这篇文章给人人网的程序员带来任何麻烦，能想到用公开密钥密码学对密码加密传输，已经是不错的主意了。不过密码学实在是一个专业的领域，密钥长度、消息填充等问题需要理解算法背后的数学原理才能想到。

大公司创造的弱加密协议的例子比比皆是。我们不是密码学家，千万不要自己设计加密协议，更不要自作聪明地对加密算法进行“优化”，一定要使用久经考验的密码学库，如 OpenSSL、GnuPG。因为浏览器端没有成熟的密码学库，人人网使用一个代码质量看起来还不错的库，实在不能怪罪程序员。

最后给大家一个用来装 X 的东西：本文所介绍的二次筛法的时间复杂度是 exp(sqrt(log N * log log N) / 2)，其中 N 是欲分解的数。它高于任何多项式算法，而低于指数复杂度。下次有人问 “有没有一种算法，比多项式算法慢，又比 NP 完全问题的已知最好算法快” 时，就可以用这个来装 X 了。事实上，因子分解问题渐进意义上目前已知的最好算法（数域筛法）的时间复杂度也是高于任何多项式算法，而低于指数的。因子分解问题的时间复杂度是一个开放问题。

参考文献

msieve, sourceforge project: http://sourceforge.net/projects/msieve/