rsa解密算法

来源：百度知道 编辑：UC知道 时间：2024/05/23 11:24:31
算法过程 我基本了解 我想问下 解密时候的计算过程
比入 产生密钥对：p=7，q=17，e=5 n=pq=119
∮（n）=(p-1)(q-1)=96 ed=1 mod ∮(n) d=77
公钥为{e，n} ={5,119},私钥为{d，n}={77，119}
加密 明文S=19 则密文C=66
解密 密文C=66 则明文为S=19
我想问下 由密文C=66 怎么算出S=19 这个如果不是有特殊算法要涉及很大很大的数 根本无法计算
上课老师讲了 我没记下来 特来问问 请把计算过程写详细些 谢谢
莫非我不问老师 不找班上的美女 就没人能回答我了吗0.0！

我刚刚复习完关于rsa的算法知识，告诉你吧:
RSA公钥密码系统：
1.密钥对的产生：随机产生两个大的素数：p，q 计算n=p×q
2.随机产生加密密钥e：选择一个随机的e使Gcd（e，（p-1）*(q-1)）= 1就是选择一个随机的e，使e和 (p-1)*(q-1)互素。通常e也选择成素数。
这样，公钥对（n，e）就产生了
3.计算解密密钥d：计算一个数d 条件是使得e*d mod (p-1)*(q-1)=1,其中n与d也要互素。
这样就产生了私钥对（n，d）

发送者给持有密钥（n，d）的人发送某数M
发送密文C=M^e mod n

接受者利用私钥解密M=C^d mod n

计算模指数当然需要特殊的算法啦，要不然计算机也没办法算啊：算法如下：
#include <iostream>
#include <cmath>
using namespace std;

int exp_mod(int a,int n,int z)
{
int exp = 1;
int x = a % z;
while (n>0)
{
if(n%2==1)
exp = (exp * x) % z;
x = (x * x) % z;
n = n/2;
}
return exp;

}

int main()
{
int a,n,z;
cout<< "请输入底数: ";
cin>>a;
cout<< "请输入指数: ";
cin>>n;
cout<< "请输入被模数: ";
cin>>z;
int result = exp_m