cryptography - 当给定 2 个密文且公钥相差 1 位时，在 RSA 中查找原始消息

Question

使用 RSA， 已知：

• K_1- 公钥
• K_2- 公钥
• C_1= E(M,K_1)- 密文
• C_2= E(M,K_2)- 密文
• 密钥 K_1 和 K_2 仅在一位不同（我们不知道是哪一位）。

如何找到原始的纯文本 M？ 注意：不能使用蛮力。

我在某处读到 r*K_1 + s*K_2 = 1 modN,和r（或s）也可能是负面的。

因此，可以这样找到 M： ((C_1 )^-1)^-r * (C_2)^s = M

注意： ((C_1 )^-1)可以计算C_1，所以M可以计算。

问题：谁说的gcd(K_1,K_2) = 1,那怎么可能是真的r*K_1 + s*K_2 = 1 modN？

其次，如果该解决方案不正确，任何人都可以告诉我他如何解决这个问题？

标签： cryptographyrsa

Answer 1

假设 K_1 和 K_2 是合法的密钥，则应该存在以下内容：

gcd(K_1, φ(φ(N))=1欧拉函数gcd(K_2, φ(N))=1在哪里。φ

鉴于此，我们知道 K_1 和 K_2 一定是奇数。根据这些密钥仅相差 1 位的信息，我们知道gcd(K_1, K_2)=1. 这意味着r s存在诸如rK_1 + sK_2 = 1（定义gcd）。

我们知道C_1 = E(M,K_1)和C_2 = E(M,K_2)。

让我们乘以C_1^r，C_2^s看看我们得到了什么：

C_1^r * C_2^s = (M^K_1)^r * (M^K_2)^s = M^(rK_1 + sK_2) = M^1 = M

我们找到了原始消息 M。