algorithm - RSA 密码系统 - 检索 m

Question

在 RSA 密码系统中，给定 e=3，我想知道如果我知道 d，我该如何检索 m = (p-1)(q-1)。 换句话说，我认为这与一些数学主张有关，即我有 3 及其相反的倍数，我如何检索该组？ N = pq (p,q 素数)。 m = (p-1)(q-1) gcd(e,m) = 1 d = e^-1 mod m

Answer 1

任意e的通解

由于 d 和 e 是模逆模 m，对于某个常量 c，您还有 de-1 = cm。

当 gcd(k,n) = 1 时，我们也有 k^m = 1 (mod n)，因此也有 k^(de-1) = 1 (mod n)。

m 至少可以被 4 整除(因为 p 和 q 是奇数)所以将 d*e-1 分成 t*2^s，t 为奇数并计算 k^t (mod n)，当你对结果 s 求平方时次 (mod n) 你最终会达到 1，可能早于 s 平方之后。

到达1之前的中间结果可以是-1(mod n)；如果发生这种情况，请尝试另一个 k。

如果您从另一个数字得出 1，比如 x，我们发现 x 不是 1 或 -1，并且 x^2 = 1 (mod n)。换句话说，x^2 -1 = (x-1)*(x+1) = 0 (mod n) 和 gcd(x-1,n) 是 n(比如说 q)的一个重要因素。现在你已经找到了 q 和 p=n/q 并且可以很容易地计算出 m。

e=3 的特例

假设 p,q > 3。

d 和 e=3 是模逆，所以 3d-1=cm。由于 d < m 我们立即知道 c 只能是 1 或 2。

此外，由于 e 具有模逆，m 以及 p-1 和 q-1 都不能被 3 整除。

p 和 q 都不能被 3 整除，这只剩下 p 和 q 同余 2 (mod 3) 并且因此 p-1 和 q-1 同余 1 (mod 3) 的情况。但这也使得 m 与 1 (mod 3) 一致

采用等式 3d-1=cm 模 3，我们有 0*d-1 = c*1 (mod 3) 或 c = 2 (mod 3)。由于 c 只有 2 种可能性，因此只剩下 c=2。

因此:m = (3d-1)/2