cryptography - RSA私有(private)指数确定

Question

我的问题是关于 RSA 签名的。

如果是 RSA 签名:

加密 -> y = x^d mod n,
解密 -> x = y^e mod n

x -> 原始消息

y -> 加密消息

n -> 模数(1024 位)

e -> 公共(public)指数

d -> 私有(private)指数

我知道 x、y、n 和 e。知道这些我可以确定d吗？

Answer 1

如果可以分解 n = p*q，则 d*e ≡ 1 (mod m) 其中 m = φ(n) = (p-1)*(q-1)，(φ(m) 为 Euler's totient function )在这种情况下，您可以使用 extended Euclidean algorithm从 e 确定 d。 (对于某些 k，d*e - k*m = 1)

所有这些都非常容易计算，除了因式分解，它被设计为非常困难，因此公钥加密是一种有用的技术，除非您知道私钥，否则无法解密。

因此，从实际意义上回答您的问题，不，您不能从公钥中导出私钥，除非您可以等待数百或数千个 CPU 年来分解 n。

公钥加密和解密是逆运算:

x = ye mod n = (xd)e mod n = xde mod n = xkφ(n)+1 mod n = x * (xφ(n))k mod n = x mod n

其中 (xφ(n))k = 1 mod n 因为 Euler's theorem .