Question

RSA加密算法简易演示

一个C++关于 RSA加密算法 的演示

验证步骤如下：
1、由用户输入两个大于10小于100的质数p、q，要求验证p、q均为质数。
2、计算n=p*q和m=(p-1)*(q-1)。
3、输入一个e1，要求与m互质。
4、计算e1的乘法逆元e2 即实现 (e2*e1)mod((p-1)*(q-1))=1
5、输入明文A，对A加密为B，加密方法：B=A^e2 mod n
6、对密文B进行解密，解密方法：A=B^e1 mod n

计算e1的乘法逆元e2 即实现 (e2*e1)mod((p-1)*(q-1))=1
加密方法：B=A^e2 mod n
这是什么意思？因为要答辩，我必须说出什么意思，关于乘法逆元的百度我实在看不懂

Answer 1

RSA算法安全性本质是三大数学困难问题之一也就是大数分解问题，因为目前尚没有一种有效的方法可以在短时间内分解两个大素数的乘积。验证步骤如上面所说的，原理书上有，具体程序实现简单讲一下

1. 判断质数，这是基本水平，可以穷举也可以建表，按自己喜好

2. 这一步是计算两个大素数乘积没什么好说的

3. 判断两个数互质，一般采用欧几里得算法，辗转相除直到得到gcd(e1,m)=1。当然你也可以穷举公因数一直到sqrt(min{e1,m})

4. 计算乘法逆元是依靠广义欧几里得算法，乘法逆元的意思是形如a*a1 ≡ 1(mod m)这样的（因为这里的群的乘法定义就是数学乘法），a和a1互为彼此模m的逆元，记作a1=a^-1 mod m，只有gcd(a,m)=1时才有唯一解否则无解。

   计算方法是广义欧几里得除法，设r0=m，r1=a，s0=1，s1=0，t0=0，t1=1；

   计算ai=[r(i-1)/ri]，r(i+1)=r(i-1)-airi，s(i+1)=s(i-1)-aisi，t(i+1)=t(i-1)-aiti，直到ri=0

   举例如a=7,m=13，计算a^-1 mod m：

   a1=[13/7]=1,r2=r0-a1r1=6,s2=s0-a1s1=1,t2=t0-a1t1=-1;

   a2=[7/6]=1,r3=r1-a2r2=1,s3=s1-a2s2=-1,t3=t1-a2t2=2;

   a3=[6/1]=6,r4=r2-a3r3=0.

   取s=s3=-1，t=t3=2，则有7*2-1*13=1，故a^-1 mod m=t=2。

   把上面的方法写成C++算法应该很简单

5和6都是计算同余没什么好说的，记得要用到a^e≡b^e(mod m)化简

要毕业了还搞不懂逆元有点拙计啊，回去好好看看离散数学吧