RSA加密算法，已知e=31、n=35 求d，C=10怎么得出明文M和私钥d，最好能有详细的计算过程~

RSA加密算法，已知e=31、n=35 求d，C=10怎么得出明文M和私钥d，最好能有详细的计算过程~

n = p * q ,其中p，q是素数。由此可以得出p = 5,q=7
所以现在就是计算 e乘以d的逆模 模（p-1）（q-1）同余于1。经过扩展的欧几里得算法（不知道网上搜），可以计算出d=7.

通过下述程序计算的M为10.
#include <iostream>
using namespace std;
unsigned long momi(unsigned long a,unsigned long e,unsigned long m)
{
unsigned long s ,t ,u;

s = 1; t = a; u = e;
while(u)
{
if (u & 1) s = (s * t)%m;
u >>= 1;
t = (t*t)%m;
}
return s;

}

int main(int argc, char* argv[])
{
for(int i = 0; i < 35; i++)
{
if (momi(i, 31, 30) == 10)
{
cout<<momi(i, 31, 35)<<endl;
cout<<i<<endl;
break;
}
}
return 0;
}

1)φ(n)=i*44，n=69；2)私钥d=9；3)密文c＝36

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息