题目

RSA算法
用RSA算法 试给出m=student的加解密过程
Eucliden算法 得出d

提问时间：2021-03-30

答案

没有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后把我以前的压缩包打不开了 也可能损坏了