Question

RSA算法 写出加解密过程

用RSA算法 试给出m=student的加解密过程
尽量详细点
Eucliden算法 得出d 也详细一点

Answer 1

没有e没法求d p和q也没给 我郁闷
先说欧几里得算法，这个是一个函数，求的话累死。
欧几里得算法是求最大公约数的，求逆元用扩展的欧几里得算法
原理：
如果gcd(a，b)=d，则存在m，n，使得d = ma + nb，称呼这种关系为a、b组合整数d，m，n称为组合系数。当d=1时，有 ma + nb = 1 ，此时可以看出m是a模b的乘法逆元，n是b模a的乘法逆元。
int gcd(int a， int b ， int&； ar，int &； br)
{
int x1，x2，x3；
int y1，y2，y3；
int t1，t2，t3；
if(0 == a)
{//有一个数为0，就不存在乘法逆元

ar = 0；

br = 0 ；

return b；
}
if(0 == b)
{

ar = 0；

br = 0 ；

return a；
}
x1 = 1；x2 = 0；x3 = a；
y1 = 0；y2 = 1；y3 = b；
int k；
for( t3 = x3 % y3 ； t3 ！= 0 ； t3 = x3 % y3)
{

k = x3 / y3；t2 = x2 - k * y2；t1 = x1 - k * y1；

x1 = y1；x1 = y2；x3 = y3；

y1 = t1；y2 = t2；y3 = t3；
}
if( y3 == 1)
{ //有乘法逆元

ar = y2；

br = x1；

return 1；
}

else

{ //公约数不为1，无乘法逆元。这个是存在逆元的充要条件

ar = 0；

br = 0；

return y3；
}
}
核心是
for( t3 = x3 % y3 ； t3 ！= 0 ； t3 = x3 % y3)
{

k = x3 / y3；t2 = x2 - k * y2；t1 = x1 - k * y1；

x1 = y1；x1 = y2；x3 = y3；

y1 = t1；y2 = t2；y3 = t3；
}
一共有三行
x1 ，x2 ，x3
y1 ，y2 ，y3
t1 ，t2 ，t3
每次循环第三行都是算出来的 然后 把第一行y的值放到x t的值放到y
这三行都满足一个共同的性质
第一个数*a+第二个数*b=第三个数
比如x1*a+x2*b=x3
每次循环问题都会简化，距离结果更进
直到
当最终t3迭代计算到1时，有t1× a + t2 × b = 1，显然，t1是a模b的乘法逆元，t2是b模a的乘法逆元。

生成p，q两个素数，产生方法就是随机产生一个数，然后用素性检验算法判断是不是素数，如果不是再随机产生一个判断。关于素性经验，这个问题很大，是本数论书都有，这里没法展开讲。
比如p=3，q=11
生成n=p*q=33
生成n的欧拉函数 N=(p-1)*(q-1)=20
选取公钥e=3 然后计算d
e*d=1（mod N） e和d是关于模N的互为逆元的关系，用扩展的欧几里得算法
得出来d=7 也就是说3*7=1（mod 20）
加密用e M的每个字母转换成ASCII码 设明文字母为m 密文为c
加密过程：c=m的e次方（mod n） 也就说c=m的三次方（mod 33）
解密过程：m=c的d次方（mod n） 也就是说m=c的7次方（mod 33）

百度知道没有公式编辑器让我很痛苦
注意别把N=（p-1）*（q-1）和n=p*q搞混了 N用于求d n用于加密解密

RSA我熟的很 还做过一个ppt 实现还有简单的一些弱点 本来想发给楼主 但是貌似我换了7-zip后把我以前的压缩包打不开了 也可能损坏了

Answer 2

ssss