有没有办法判断 RSA public 密钥对是否正确？

Question

我有一个测验问题，询问以下哪对 (n,e) 是正确的 RSA public 密钥？

1. n = 437 和 e = 7
2. n = 437 和 e = 11

提示437 = 19*23

有没有办法判断 RSA public 密钥是否正确？或者我一定是错过了一些重要的内容

Answer 1

简答：

第二一个不正确。因为gcd(e, lambda(n))一定是1，但是第二种情况就不是了。

长答案：

通过 RSA key generation:

n=437 and 437=19*23,所以p,q是19, 23.

lambda(437)=(p-1)*(q-1)=18*22

现在我们需要 select e 1<e<lambda(n) 和 gcd(e, lambda(n))=1 意思是 e 和lambda(n) 互质。

但是在第二种情况下，gcd(11, lambda(437))=11，所以它们不是互质的，我们不能使用 e=11。