数学实验大作业——抽象群与应用“RSA加密系统”合作人：郭元镇尹庆宇杨瑞飞综述1）RSA 加密算法的历史RSA公钥加密算法是1977年由Ron Rivest、Adi Shamirh和LenAdleman在（美国麻省理工学院）开发的。
RSA取名来自开发他们三者的名字。
RSA是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的所有密码攻击，已被ISO推荐为公钥数据加密标准。
RSA算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但那时想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。
这种算法1978年就出现了，它是第一个既能用于数据加密也能用于数字签名的算法。
它易于理解和操作，也很流行。
早在1973年，英国国家通信总局的数学家Clifford Cocks就发现了类似的算法。
但是他的发现被列为绝密，直到1998年才公诸于世。
RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。
RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。
即RSA的重大缺陷是无法从理论上把握它的保密性能如何，而且密码学界多数人士倾向于因子分解不是NPC问题。
2）RSA 加密算法的原理RSA算法是一种非对称密码算法，所谓非对称，就是指该算法需要一对密钥，使用其中一个加密，则需要用另一个才能解密。
RSA的算法涉及三个参数，n、e1、e2。
其中，n是两个大质数p、q的积，n的二进制表示时所占用的位数，就是所谓的密钥长度。
e1和e2是一对相关的值，e1可以任意取，但要求e1与(p-1)*(q-1)互质；再选择e2，要求(e2*e1)mod((p-1)*(q-1))=1。
(n及e1),(n及e2)就是密钥对。
RSA加解密的算法完全相同,设A为明文，B为密文，则：A=B^e1 mod n；B=A^e2 mod n；e1和e2可以互换使用，即：A=B^e2 mod n；B=A^e1 mod n;3）RSA 加密算法的缺点1.产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。
2.安全性, RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价，而且密码学界多数人士倾向于因子分解不是NPC问题。
目前，人们已能分解140多个十进制位的大素数，这就要求使用更长的密钥，速度更慢；另外，目前人们正在积极寻找攻击RSA的方法，如选择密文攻击，一般攻击者是将某一信息作一下伪装(Blind)，让拥有私钥的实体签署。
然后，经过计算就可得到它所想要的信息。
实际上，攻击利用的都是同一个弱点，即存在这样一个事实：乘幂保留了输入的乘法结构：( XM )d = Xd *Md mod n前面已经提到，这个固有的问题来自于公钥密码系统的最有用的特征--每个人都能使用公钥。
但从算法上无法解决这一问题，主要措施有两条：一条是采用好的公钥协议，保证工作过程中实体不对其他实体任意产生的信息解密，不对自己一无所知的信息签名；另一条是决不对陌生人送来的随机文档签名，签名时首先使用One-Way Hash Function对文档作HASH处理，或同时使用不同的签名算法。
除了利用公共模数，人们还尝试一些利用解密指数或φ（n）等等攻击.3.速度太慢,由于RSA 的分组长度太大，为保证安全性，n 至少也要 600 bitx以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。
目前，SET(Secure Electronic Transaction)协议中要求CA采用2048比特长的密钥，其他实体使用1024比特的密钥。
为了速度问题,目前人们广泛使用单,公钥密码结合使用的方法,优缺点互补:单钥密码加密速度快,人们用它来加密较长的文件,然后用RSA来给文件密钥加密,极好的解决了单钥密码的密钥分发问题。
下表列出了对同一安全级别所对应的密钥长度。
保密级别对称密钥长度（bit）RSA密钥长度（bit）ECC密钥长度（bit）保密年限80 80 1024 160 2010 112 112 2048 224 2030 128 128 3072 256 2040 192 192 7680 384 2080 256 256 15360 512 21204）针对RSA 加密算法的几种攻击方式针对RSA最流行的攻击一般是基于大数因数分解。
1999年，RSA-155(512 bits)被成功分解，花了五个月时间（约8000 MIPS 年）和224 CPU hours 在一台有3.2G中央内存的Cray C916计算机上完成。
2002年，RSA-158也被成功因数分解。
1.RSA的选择密文攻击RSA在选择密文攻击面前很脆弱。
一般攻击者是将某一信息作一下伪装( Blind)，让拥有私钥的实体签署。
然后，经过计算就可得到它所想要的信息。
实际上，攻击利用的都是同一个弱点，即存在这样一个事实：乘幂保留了输入的乘法结构：( XM )^d = X^d *M^d mod n这个固有的问题来自于公钥密码系统的最有用的特征--每个人都能使用公钥。
但从算法上无法解决这一问题，主要措施有两条：一条是采用好的公钥协议，保证工作过程中实体不对其他实体任意产生的信息解密，不对自己一无所知的信息签名；另一条是决不对陌生人送来的随机文档签名，签名时首先使用One-Way HashFunction 对文档作HASH处理，或同时使用不同的签名算法。
2.RSA的公共模数攻击若系统中共有一个模数，只是不同的人拥有不同的e和d，系统将是危险的。
最普遍的情况是同一信息用不同的公钥加密，这些公钥共模而且互质，那么该信息无需私钥就可得到恢复。
设P为信息明文，两个加密密钥为e1和e2，公共模数是n，则：C1 = P^e1 mod nC2 = P^e2 mod n密码分析者知道n、e1、e2、C1和C2，就能得到P。
因为e1和e2互质，故用Euclidean算法能找到r和s，满足：r * e1 + s * e2 = 1假设r为负数，需再用Euclidean算法计算C1^(-1)，则( C1^(-1) )^(-r) * C2^s = P mod n另外，还有其它几种利用公共模数攻击的方法。
总之，如果知道给定模数的一对e和d，一是有利于攻击者分解模数，一是有利于攻击者计算出其它成对的e’和d’，而无需分解模数。
解决办法只有一个，那就是不要共享模数n。
RSA的小指数攻击。
有一种提高 RSA速度的建议是使公钥e取较小的值，这样会使加密变得易于实现，速度有所提高。
但这样做是不安全的，对付办法就是e和d都取较大的值。
5）本次实验中用到的4种算法1.平方-乘算法在RSA算法中，往往要计算ma mod r的值，由于ma的值可能会很大而产生溢出从而导致错误。
平方-乘算法：将a转换为二进制数b，用bi表示b的第i位值，L为b的二进制位数，则：（0）令c=1，i=L-1（1）计算c=c*c%r（2）若bi=1，则计算c=c*m%r，否则什么也不做（3）i=i-1（4）重复步骤1-3，直至i=0为止，此时c的值即为所求。
2.Rabin-Miller算法:数论学家利用费马小定理研究出了多种素数测试方法，目前最快的算法是拉宾米勒测试算法，（现在不是最快，印度的一名老师和他的两个本科生的算法是最快的：印度理工学院计算机科学与工程学系的科学家马宁德拉·阿格拉瓦和他的两位在校本科生尼拉叶·卡雅尔和尼汀·萨克斯特纳）其过程如下：（1）计算奇数M，使得N=(2**r)*M+1（2）选择随机数A<N（3）对于任意i<r，若A**((2**i)*M) MOD N = N-1，则N通过随机数A的测试（4）或者，若A**M MOD N = 1，则N通过随机数A的测试（5）让A取不同的值对N进行5次测试，若全部通过则判定N为素数若N 通过一次测试，则N 不是素数的概率为 25%，若N 通过t 次测试，则N 不是素数的概率为（1/4）的n次幂。
事实上取t 为5 时，N 不是素数的概率为 1/128，N 为素数的概率已经大于99.99%。
3.扩展欧几里德算法欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。
其计算原理依赖于下面的定理：定理：gcd(a,b) = gcd(b,a mod b)设两数为a、b(b＜a)，用gcd(a,b)表示a，b的最大公约数，r=a mod b 为a除以b以后的余数，辗转相除法即是要证明gcd(a,b)=gcd(b,r)。
第一步：令c=gcd(a,b)，则设a=mc，b=nc第二部：根据前提可知r =a-kb=mc-knc=(m-kn)c第三部：根据第二步结果可知c也是r的因数第四步：可以断定m-kn与n互素（否则，可设m-kn=xd，n=yd，(d>1)，则m=kn+xd=kyd+xd=(ky+x)d，则a=mc=(ky+x)dc，b=nc=ycd，故a与b最大公约数成为cd，而非c）从而可知gcd(b,r)=c，继而gcd(a,b)=gcd(b,r)。
扩展欧几里德算法是用来在已知a, b求解一组p，q使得p * a+q * b = Gcd(a, b) (解一定存在，根据数论中的相关定理)。
扩展欧几里德常用在求解模线性方程及方程组中。
4. 大数快速求模算法先承认两个公式:ab mod c=((a mod c)(b mod c)) mod c(a+b) mod c=(a mod c+b mod c) mod c然后递推，先算1 mod c,然后10 mod c ,100 mod c。
用数组存一下，递推方法是10^n mod c=((10^(n-1) mod c)*10) mod c再加，让k=0,for a:=1 to l dok:=(k+num[a]*exp10[a]) mod c这样最后k就是结果。
程序运行实例及结果分析初始运行界面自动生成密钥RSA加密RSA解密手动输入密钥输入密钥不符合要求时弹出警告窗口关于帮助对实验结果的看法和意见：实验结果并不很让人满意，只能完成3000-9000之内素数的输入运算过程，对于多位素数的运算进行了尝试但是仍有很多BUG，所以只暂时保留了小数量级的RSA加解密过程展示。
但是基本功能已经完成，只要找到一种适合大素数的运算算法，便可顺利进行大数量级素数的RSA加解密。
参考文献1）陈华，蔡光兴《基于Matlab/GUI的RSA密码演示系统》计算机与现代化2009（7）2）刘卫国《Matlab程序设计与应用》 20063）闫洪亮.牛军涛《实现RSA算法应注意的问题》计算机应用与软件 2008(5) 4）胡卫群《Euclidean算法》南京农专学报 1996（4）5）雒海涛《Matlab GUI教程》 2011合作分工郭元镇： GUI界面编程尹庆宇：资料查找和题目分析研究杨瑞飞：算法设计。