algorithm - RSA 公共指数也在解密消息

Question

我正在尝试用我自己的数字制定一个非常简单的RSA算法，但我似乎遇到了问题。

我选择素数 13 和 17，给我一个模数 221。φ(221)=12∗16=192 然后我选择公共指数 r=19，并使用extended euclidean algorithm我发现私人指数 s=91。(19⋅91=1 模 192)

现在我将我的消息 42 加密为：42^19 mod 221=172. 使用解密172^91 mod 221确实返回了 42 的原始值。但是，如果我使用 19 作为指数 ( 172^19 mod 221)，我也会得到 42，这显然不是应该发生的。我哪里做错了？

Answer 1

19 次幂是 19×19 = 169 (mod 192) 的幂。问题是，为什么 x = 42 和许多其他 x 值时 x ¹⁶⁹ = x (mod 221)？

让我们专注于乘法群模 221。由于 221=13×17，这个群有 12×16 = 192 个元素，它同构于 C ₁₂ ×C ₁₆（其中 C _n是 n 阶循环群）。

请注意，x ¹⁶⁹ = x (mod 221) 等价于 x ¹⁶⁸ = 1 (mod 221)。让我们定义 f(x) = x ¹⁶⁸。

• 由于 168 = 0 (mod 12)，f 将 C ₁₂中的每个元素映射到中性元素 1。
• 由于 168 = 8 (mod 16)，f 将 C ₁₆的所有偶数元素映射到中性元素 1，它是群的一半。

因此，对于乘法群的一半模 221，f(x) = 1 (mod 221)。

但是 x ¹⁶⁹ = x·x ¹⁶⁸，所以对于乘法组的一半，我们有 x ¹⁶⁹ = x (mod 221)。

检查不属于乘法组的 29 个模 221 的整数，我们看到其中 21 个也存在同余性。这可以进一步调查。所以总的来说，所有消息的一半多一点（96+21 = 117）是使用指数 19 “解密”的。

这是否意味着这个 RSA 系统坏了？我不这么认为；要看到公共指数可以解密一半的消息，您需要知道 221 的因式分解是 13×17。攻击者也可以选择一个随机指数。

更新：这个问题可以通过选择不同的公共指数来​​避免吗？

由于 192 = 2 ⁶ ×3 指数不能是 2 或 3 的倍数，所以它必须是 e = 6k±1。它的平方是 e² = (6k±1)² = 36k² ± 12k + 1 = 12k(3k ± 1) + 1。我们看到在调用案例中 e² = 1 (mod 12)。

• 如果 k = 4j，e² = 48j(12j ± 1) + 1 = 1 (mod 16)
• 如果 k = 4j+1，e² = (48j+12)(12j + 3 ± 1) + 1 = 48j(12j+3±1)+144j+36±12+1 = 5∓4 (mod 16)，所以对于 e = 6k+1 e² = 1 (16) 并且对于 e=6k-1 e²=9 (16)。
• 如果 k = 4j+2，e² = (48j+24)(12j + 6 ± 1) + 1 = 48j(12j+6±1)+288j+144±24+1 = 1±8 = 9 (mod 16)
• 如果 k = 4j+3，e² = (48j+36)(12j + 9 ± 1) + 1 = 48j(12j+9±1)+432j+324±36+1 = 5±4 (mod 16)，所以对于 e = 6k+1 e² = 9 (16) 并且对于 e=6k-1 e²=1 (16)。

因此，对于这个模数，没有选择比 19 更好的公共指数：使用公共指数解密将适用于至少一半的消息（当 e²=9 (16) 时），并且在许多情况下几乎适用于所有消息（当 e²=1 (16) 时）。