密钥
如何求出 d:扩展欧几里得算法
每一行都由上面两行相除得到。在余数为 1 的那一行,最后一列就是 d(如果是负数,就加上 φ(n))。
| 商 | 余数 | e 的系数 |
|---|
消息
经网络发送
| 位 | 平方 | 乘以 m |
|---|
破解密钥
RSA 加密演示
有了 RSA,任何人都可以用你的公钥把消息锁上,而只有你能用自己的私钥打开它。它背后只是几行学校里学过的算术:两个素数、一次乘法、一个余数和一个巧妙的逆元。用你自己选的素数构建一对密钥,逐个字符地加密和解密消息,为消息签名,让任何人都能验证它出自你手,然后扮演攻击者分解 n,看看为什么真正的密钥需要几百位数字。 选两个素数 p 和 q,或按“新素数”。应用会构建公钥 (e, n) 和私钥 d,并展示扩展欧几里得算法如何求出 d。输入一条消息:每个字符都用公钥加密,再用私钥解密。点击某一行,查看用反复平方法计算幂的过程。切换到“签名”可改用私钥签名,按“分解 n”则可看到小密钥多快就会被破解。
它是如何运作的
- 输入两个素数 p 和 q,或选择大小并按“新素数”;应用会计算 n、φ(n)、e 和 d,并展示如何求出 d。
- 输入一条消息,选择“加密”或“签名”。每个字符都会被转换成一个数,再取幂并模 n;点击某一行即可查看反复平方的过程。
- 按“分解 n”,让伊芙把 n 拆成两个素数并恢复出私钥。
密钥如何运作
把两个素数相乘:n = p × q。取 p = 61、q = 53,则 n = 3233。数 φ(n) = (p − 1)(q − 1) = 3120 统计的是小于 n 且与 n 没有公因数的数的个数,只有知道 p 和 q 的人才能算出它。选 e = 17,它与 3120 没有公因数,再求出 d,使 e × d 比 φ(n) 的某个倍数多 1:这里 d = 2753,因为 17 × 2753 = 46801 = 15 × 3120 + 1。公开 (e, n),保留 d。消息 m 变为 c = mᵉ mod n,而欧拉定理保证 cᵈ mod n 能还原出 m。
为什么它难以破解
攻击者需要的一切都隐藏在 n 的因数中。n = 3233 时,这毫无保护作用:尝试奇数除数,大约试二十几次就能找到 53。但所需的工作量随 n 的平方根增长。2048 位的模数大约有 617 位十进制数字,在现有的任何计算机上,任何已知方法都无法在有意义的时间内分解它。签名是把 RSA 反过来用:s = mᵈ mod n 只能用私钥生成,而任何人都能验证 sᵉ mod n 是否还原出 m。
常见问题
为什么没人能从公钥算出 d?
要求出 d,需要 φ(n) = (p − 1)(q − 1),而要得到 φ(n),需要 p 和 q。从 n 恢复出它们就意味着分解 n,而对于几百位的数,目前还不知道有快速的方法。本演示让你在不到一秒内分解玩具密钥,这恰恰说明了为什么真正的密钥如此之大。
为什么消息要一次加密一个字符?
因为玩具密钥很小:RSA 只能加密小于 n 的数。n = 3233 时,每个字符编码都放得下,但整句话就不行了。真正的 RSA 使用 2048 位或更长的模数,用随机字节填充消息,使同一条消息每次加密的结果都不同,而且在实践中只加密一个短密钥,供 AES 等更快的密码使用。
反复平方法有什么用?
它可以计算像 m²⁷⁵³ mod n 这样巨大的幂,而无需写出那个巨大的数。把指数写成二进制,然后逐位处理:每一位都把当前结果平方,遇到 1 就再乘以 m,每次都取模 n 的余数。2048 位的指数只需大约 2048 次平方。
加密和签名有什么区别?
加密使用接收者的公钥,这样只有接收者的私钥才能解开。签名使用发送者的私钥,这样任何人都能用发送者的公钥验证,并确认消息来自该密钥的持有者,而且没有被篡改。
我的消息会被发送到任何地方吗?
不会。所有内容都在你的浏览器中计算,你的素数和消息保存在此浏览器的本地存储中。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
前往编辑器