RSA 详解
每当浏览器显示一把挂锁、一条消息被签名或软件检查更新时,公钥密码学都在发挥作用,而 RSA 是其中最著名的形式。它的思想是:锁上消息的密钥可以公开,而打开它的密钥保持私密。值得一提的是,整个系统建立在学校里教的算术之上:素数、乘法和余数。
RSA 解决的问题
较早的密码,从凯撒移位密码到现代的 AES,都用同一个密钥加锁和解锁,因此双方必须先私下共享一个秘密密钥。公钥密码学省去了这一步。每个人都有两个密钥:一个是公钥,任何人都可以用它给此人加密消息;另一个是私钥,只有此人持有,也只有它能解密。惠特菲尔德·迪菲和马丁·赫尔曼在 1976 年描述了这一思想,一年后,麻省理工学院的罗纳德·李维斯特、阿迪·萨莫尔和伦纳德·阿德曼找到了实现方法,并以三人姓氏的首字母命名为 RSA。
生成密钥
选两个大素数 p 和 q,把它们相乘:n = p × q。计算欧拉函数 φ(n) = (p − 1)(q − 1),它统计的是小于 n 且与 n 没有公因数的数的个数。选一个与 φ(n) 没有公因数的公钥指数 e;通常选 65537。然后求出私钥指数 d,使 e × d 除以 φ(n) 余 1。扩展欧几里得算法可以快速做到这一点。公钥是数对 (e, n);私钥是 d。取 p = 61、q = 53,得到 n = 3233、φ(n) = 3120、e = 17 和 d = 2753。
加密与解密
消息首先被转换成一个小于 n 的数 m。要加密,计算 c = mᵉ mod n,即 mᵉ 除以 n 的余数。要解密,计算 cᵈ mod n。欧拉定理保证这会还原出 m,因为 e × d 比 φ(n) 的某个倍数多 1。用上面的密钥,字母 A(编码 65)变为 65¹⁷ mod 3233 = 2790,而 2790²⁷⁵³ mod 3233 又等于 65。这么大的幂从来不会被完整写出来:反复平方法对指数的每一位做一次平方,每一步都取余数,从而算出结果。
数字签名
RSA 也可以反过来用。把消息取私钥指数次幂,s = mᵈ mod n,就得到一个只有密钥所有者才能生成的签名。任何人都可以用公钥验证它:如果 sᵉ mod n 还原出 m,那么消息就来自 d 的持有者,而且在途中没有被篡改。在实践中,被签名的是消息的一个简短哈希值,而不是消息本身。这样的签名保护着软件更新、安全网站和电子文档。
为什么它是安全的
每个人都能看到 n 和 e。要找到 d,攻击者需要 φ(n),而要找到 φ(n),需要 p 和 q,所以破解 RSA 归根结底就是分解 n。计算机把两个素数相乘只需不到一微秒;而把乘积重新拆回这两个素数,被认为是极其困难的。迄今为止被分解的最大 RSA 挑战数是 2020 年的 RSA-250,它有 829 位,耗费了大约 2700 年的计算机时间。如今使用的密钥至少有 2048 位,约合 617 位十进制数字。
一个被发现两次的秘密
1973 年,也就是 RSA 问世的四年前,英国数学家克利福德·柯克斯在情报机构 GCHQ 工作时,在同事詹姆斯·埃利斯的一个想法的基础上,发现了同样的方案。这项工作被列为机密,直到 1997 年才公开。RSA 本身于 1983 年在美国获得专利;该专利于 2000 年 9 月到期,而在此两周前,这一算法已被发布到公有领域。
实践中的 RSA
真正的 RSA 从不直接加密文本。消息会使用 OAEP 等方案以随机字节进行填充,使同一条消息每次加密的结果都不同,规律也无从泄露。由于 RSA 速度较慢,它主要用来交换或保护 AES 等快速对称密码的短密钥,或者用来签名。足够大的量子计算机可以用 1994 年提出的肖尔算法迅速分解 n,这就是为什么新的后量子方法正在与 RSA 并行引入。
动手探索
打开 RSA 加密演示,用你自己的素数或 2 到 8 位的随机素数构建密钥,逐行观看扩展欧几里得算法如何求出 d,逐个字符地加密或签名消息,并跟踪任意字符的反复平方过程。然后让伊芙分解 n,看看她所需的时间如何随素数的大小增长。
常见问题
RSA 为什么需要素数?
因为只有当你知道 n 如何分解成素数时,φ(n) 才容易计算。对于 n = p × q,其中 p 和 q 是素数,φ(n) = (p − 1)(q − 1)。素数还能让 n 在同等大小下尽可能难以分解,因为它根本没有小因数。
为什么 e 常常是 65537?
65537 = 2¹⁶ + 1 是素数,二进制中只有两个 1,所以用它加密只需 16 次平方和一次乘法。它也足够大,可以避免像 3 这样非常小的指数所带来的弱点。
RSA 和迪菲-赫尔曼有什么区别?
迪菲-赫尔曼让两个人通过公开信道商定一个共享秘密密钥;它本身并不加密或签名任何东西。RSA 则直接用密钥对进行加密和签名。两者都建立在正向容易、反向困难的问题之上:RSA 依赖因数分解,迪菲-赫尔曼依赖离散对数。
演示中的密钥能用于真正的加密吗?
不能。它的素数最多只有十二位左右,所以它生成的任何密钥都能在几秒甚至更短的时间内被分解,而且它对每个字符单独加密,不做填充。它的用途是展示 RSA 如何运作,而不是保护任何东西。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
打开 RSA 加密演示