RSA加密算法简易演示

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

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

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

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

计算乘法逆元是依靠广义欧几里得算法，乘法逆元的意思是形如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)化简

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

那我给你解释下RSA吧，尽量让你看懂：

*RSA是非对称加密体系，也就是说加密用一个公钥，解密用一个私钥，这2个密钥不同，这点非常非常重要。

其实RSA非常简洁，但很美

流程

1，寻找2个大的素数p，q n=p*q=33 N=（p-1）*（q-1）=20

公钥e一般是3 私钥d要通过公钥e去算出来

e*d=1(mod N) 就是说e和d的乘积模N得1 也就是e和d关于模N互为逆元

3*7=1（mod 20） 可知d=7

加密的明文设为M 加密后的密文设为c

加密过程：C=M^e(mod n)

解密过程：M=C^d(mod n)

举个具体的例子 假如M=2

加密过程：C=2^3(mod 33)=8(mod 33)

解密过程：M=8^7(mod 33)=2097152(mod 33)=2(mod 33) 可以看出和和本来的明文是相同的。

原理可以理解为 M=M^(ed) (mod n)

本例中 e*d=21 也就是是M^21次方等于M

RSA这个特性是数论中的费马定理推出的

在讲讲细节 比如楼主加密的是26的字母 就当明文的值是从1到26

就拿n=33说吧 加密后的密文的值是1到33 这很正常

但是解密后 一定和明文的值相同 也就是1到26

实际情况中 公钥e是公开的 私钥d是保密的

比如甲要给乙发个东西 乙的公钥由于是公开的 所以甲知道 但甲不知道乙的私钥

甲先用乙的公钥加密 之后 这个密文只能用乙的私钥 由于乙的私钥是保密的 只有他自己知道 所以保证了安全

RSA最大的安全问题是 n的分解 只要把n分解为p*q 则N=（p-1）（q-1）

根据 e*d=1（mod N） 就可以通过e算出d 那么私钥都被人算出来了 也就没安全性而言了

不过可惜的是 大数分解是一个单向的函数 你算知道p，q算n很容易，但是知道n算出p，q相当难

强调一句 n是加密解密用的 N是知道e算d的

楼主也没说你要干嘛 想看懂就这么多

如果要实现这个算法：

必须知道2点：

1.p，q这个两个大素数的生成，这牵扯到素性检验，数论中是一章的内容，没法和你展开

2.取模运算，由于加密解密过程可能取一个数的几十次方的模数，所以这个必须用简便的算法来化解复杂度，也就是模重复平方算法。

如果要编程中使用，太容易了

去下个dll

在java中 直接有可用于RSA的类 相当容易

如果楼主想研究的更深 可以把邮箱 发我 RSA我以前做过一个ppt

---