RSA算法产生的公钥和私钥在什么条件下是可逆的？

Question

如果p=7，q= 13，则可以得到n= 91，d= 29，e= 5。但是，对于值小于模数的明文，公钥和私钥(n，d)和(n，e)都是可逆的，即用任一密钥加密明文值，然后第二次使用相同的密钥返回原始值。

这是什么原因，在什么情况下会发生这种情况？

这个问题指出，p和q的值将产生公钥，使得用公钥加密的消息也可以用公钥对小于模数的消息值进行解密。同样，由此生成的私钥可用于解密用同一私钥加密的消息。此问题不询问消息是否可以用公钥加密并用私钥解密。

丹尼尔·S的回答提供了我想要的信息。

Answer 1

尽管RSA密钥通常被描述为de\equiv 1\pmod{\phi(N)}的解决方案，但是有一个更精确的方程de\equiv 1\pmod{\lambda(N)}，其中\lambda是卡迈克尔函数。通常方程的任何解都是更精确方程的解。

在您的例子中，Carmichael函数是\mathrm{LCM}(p-1,q-1)=12。e=5的选择导致精确方程的d\equiv 5\pmod{12}解，d=29是一个等价的解密指数。

一般来说，当选择e是一个模Carmichael函数的平方根时就会发生这种情况(在本例中是5^2\equiv 1\pmod{12}，但1、7和11是其他例子)。通常，一个数字n有1的2^{\omega(n)}平方根，其中\omega(n)是n的不同素数。