RSA算法的C实现专业课程设计方案报告.doc

课程设计汇报

------------------RSA算法实现

院 （系）：
专 业：
班 级：
学 生：
学 号：
指导老师：

10月10日

目 录
1. RSA算法介绍和应用现………………………………….3
2. 算法原理…………………………………………………..3
3. RSA算法数论基础………………………………………..4
3.1.单向和陷门单向函数………………………………………..4
3.2.同余及模运算………………………………………………..4
3.3.欧拉函数、欧拉定理和费尔马定理………………………..5
3.4.乘法逆元及其求法…………………………………………..5.
4. RSA算法各步骤………………………………………..6
4.1.RSA公钥加密解密概述…………………………………….6
4.2. RSA署名算法………………………………………………6
4.3.大数运算处理………………………………………………..7
4.4.大素数产生………………………………………………..8
5. RSA安全性……………………………………………..8
6. 代码实现：………………………………………………..10
7. RSA算法结果分析……………………………………….15
7.1.主界面初始化…………………………………………………15
7.2.设置密钥……………………………………………………..15
7.3.对明文加密……………………………………………………16
7.4.对密文解密……………………………………………………17
8. 总结和展望………………………………………………..17
9. 参考文件…………………………………………………18
1.RSA算法介绍和应用现实状况
RSA公开密钥加密算法自20世纪70年代提出以来，已经得到了广泛认可和应用。发展至今，电子安全领域各方面已经形成了较为完备国际规范。RSA作为最关键公开密钥算法，在各领域应用数不胜数。RSA在硬件方面，以技术成熟IC应用于多种消费类电子产品。
RSA在软件方面应用，关键集中在Internet上。加密连接、数字署名和数字证书关键算法广泛使用RSA。日常应用中，有比较著名工具包Open SSL(SSL，Security Socket Layer,是一个安全传输协议，在Internet上进行数据保护和身份确定。Open SSL是一个开放源代码实现了SSL及相关加密技术软件包，由加拿大Eric Yang等提议编写。Open SSL应用RSA实现署名和密钥交换，已经在多种操作系统得到很广泛应用。另外，家喻户晓IE浏览器，自然也实现了SSL协议，集成了使用RSA技术加密功效，结合MD5和SHA1，关键用于数字证书和数字署名，对于习惯于使用网上购物和网上银行用户来说，几乎天天全部在使用RSA技术。
RSA更出现在要求高度安全稳定企业级商务应用中。在当今企业级商务应用中，不得不提及使用最广泛平台j2ee。实际上，在j2se标准库中，就为安全和加密服务提供了两组API：JCA和JCE。 JCA (Java Cryptography Architecture)提供基础加密框架，如证书、数字署名、报文摘要和密钥对产生器； JCA由多个实现了基础加密技术功效类和接口组成，其中最关键是java.security包，此软件包包含是一组关键类和接口，Java中数字署名方法就集中在此软件包中。JCE(Java Cryptography Extension) 在JCA基础上作了扩展，JCE也是由多个软件包组成，其中最关键是javax.crypto包，此软件包提供了JCE加密技术操作API。javax.crypto中Cipher类用于具体加密和解密。在上述软件包实现中，集成了应用RSA算法多种数据加密规范(RSA算法应用规范介绍参见： ，这些API内部支持算法不仅仅只有RSA，不过RSA是数字署名和证书中最常见)，用户程序能够直接使用java标准库中提供API进行数字署名和证书多种操作。
单机应用程序使用RSA加密尚比较少见，比如使用RSA加密任意一个文件。
RSA算法能够简单叙述以下：
<密钥生成>
取素数p，q，令n=p×q.
取和(p-1)×(q-1)互素整数e，
由方程d×e=1 (mod (p-1)×(q-1))解出d，
二元组(e,n)作为公开密钥，
二元组(d,n)作为私有密钥．
<加密解密>
b=ae mod n，c=bd mod n.

2.算法原理

1．选择两个不一样大素数p、q
(现在两个数长度全部靠近512bit是安全）；
2. 计算n = p*q。 
3. 计算n欧拉函数 t=(p-1)(q-1)。 
4. 选择整数e作为公钥，使e和t互素，且1<e< t。 
5. 用欧几里得算法计算d作为私钥,使d*e=1 mod t。
6. 加密：C=M^e mod n 
7. 解密：M＝C^d mod n=(M^e)^d mod n= M^e^d mod n 。

3.RSA算法数论基础

RSA算法数学理论基础
在密码学中需要使用到很多数学理论，比如数论、信息论、复杂度理论等，
它们是设计密码系统及协议不可或缺工具，其中数论是密码学中(尤其是公开密
钥密码系统中)最关键数学基础，所以有必需对相关数论理论做一介绍。下面介绍RSA算法数学基础知识。
3.1单向和陷门单向函数
RSA安全性关键取决于结构其加密算法数学函数求逆困难性，这同大多
数公钥密码系统一样(譬如EIGamal算法就是基于离散对数问题困难性)，我
们称这么函数为单向函数。单向函数不能直接用作密码体制，因为假如用单向
函数对明文进行加密，即使是正当接收者也不能还原出明文，因为单向函数
逆运算是困难。和密码体制关系更为亲密陷门单向函数，即函数及其逆函数
计算全部存在有效算法，而且能够将计算函数方法公开。单向和陷门单向函
数概念是公钥密码学关键，它对公钥密码系统结构很关键，甚至能够说
公钥密码体制设计就是陷门单向函数设计。
定义2. 1：令函数f是集合A到集合B映射，以f：A→B表示。若对任意x1≠x2，x1,x2∈A，有f(x1)≠f(x2)，则称f为1一l映射，或可逆函数。
定义2. 2：一个可逆函数厂，若它满足：
1．对全部X∈A，易于计算f(x)；
2．对“几乎全部"x∈A，由f(x)求x“极为困难”，以至于实际上不可能做到。则称f为单向函数 (One-way function)
上述定义中“极为困难”是对现有计算机能力和算法而言，Massey称此为视在困难性，对应函数称之为视在单向函数。以此来和本质上困难性相区分。现在，还没有些人能够从理论上证实单向函数是存在。
3.2同余及模运算
同余：假定有三个整数a，b，n(n≠0)，当我们称a在模n时和b同余，是指当且仅当a和b差为n整数倍，即a-b=kn，其中k为任一整数。若a和b在模n中同余， 我们可写为a≡ b(mod n)或n l(a-b)。
剩下类(Residue Class)：很显著地，利用同余概念，全部整数在模n中被分成n个不一样剩下类；为n所整除数(即余数为0)为一剩下类，被n所除余数为1数为另一剩下类，余2数又为一剩下类，以这类推。
完全剩下系(Complete Set of Residues)：若将每一剩下类中取一数为代表，形成一个集合，则此集合称为模n完全剩下系，以Zn表示。很显著地，集合(0，l，
2，．．．，n-1}为模n一完全剩下系。
从0到n-1整数组成集合组成了模n“完全剩下系”。这意味着，对每一个整数a，它模n剩下是从0到n-1之间某个整数。
所谓运算a mod n表示求a被n除余数，成为模运算。
既约剩下系(Reduced Set of Residues)：在模n完全剩下系中，若将全部和n 互素剩下类形成一个集合，则称此集合为模n既约剩下系，以Zn表示。比如n=10时，{0，1，2，3，4，5，6，7，8，9)为模10完全剩下系；而{1，3，7，9)为模10既约剩下系。
3.3欧拉函数、欧拉定理和费尔马定理
欧拉函数≯(n)：是一个定义在正整数上函数，其值等于序列0，1，2，3，…… n-1 中和n互素数个数。即fn为模n既约剩下系中全部元素个数。
由定义知，当P是素数时，≯ (p)=P-1。
定理2．1欧拉定理：若m，a为正整数，有g c d(a，m)=l(g c d，Greatest Common Divisor，最大条约数)，则a≯(m) (mod m)。其中≯m称为欧拉函数，它是比m小但和m互素正整数个数。欧拉定理也有一个等价形式：a≯(m)+1 =a(mod m)。
定理2．2设P和q是两个不一样素数，n=p×q，则≯(n)=(p-1)×(q-1)，对任意x∈Zn及任意非负整数k，有x k≯(n)+1≡x (mod n)。
定理3费尔马定理：假如P是素数，且g c d(m ,p)=l(可表示为(m , p)=1)， 则mp-1≡l(mod p)，费尔马定理还存在另一个等价形式：假如P是素数，m是任意正整数，则mp≡m(mod p)。
对于素数P来说，≯ (p)=p-1，所以费尔马定理实际是欧拉定理一个推论。费尔马定理和欧拉定理及其推论在组成了RSA算法关键理论基础。
3.4乘法逆元及其求法
乘法逆元定义：若a b≡l(mod n)，则称b为a在模n乘法逆元，b可表示为a-1。
利用Euclid(欧几里德)算法(辗转相除法)求乘法逆元：己知a及n且(a ,n) =1，求a a –l=1(mod n)。
欧几里德算法是古希腊数学家欧几里德给出求两个自然数最大条约数方法，假如(a，n)=1，则b一定存在。首先介绍利用欧几里德算法求g c d(a，n)方
法，再介绍求乘法逆元方法。
令r0=n，r l=a，a≤n，利用辗转相除法可得
r0=r1+g1+r2 0≤r2< r l
r1=r2g2+r3 0≤r3<r 2
:
:
rj-2=r j-l g j-1+rj 0≤r j<r j-1
rm-3=rm-2 gm-2+rm-1 0≤rm-1<rm-2
rm-2=rm-1 gm-1+rm 0≤r m<rm-1
rm-1= r m gm
则r m为a及n最大公因子。(欧几里德算法求g c d关键概念在于：若c=d g + r， 则(c，d)=(d，r)。所以在上述算法中，(a，n)=(r0，r1) =(r l，r2)=……= (r(m-1)，r m)=(r m，o)=r m。
能够经过举例说明利用欧几里德算法求逆元方法，如：求1001b=lmod 3837，
b是1001相关模3837乘法逆元。
因为(1001，3837)=l，而
3837=3×1001+834
1001=1×834+1 67
834=4×167+166
167=1 ×166+1
所以l=167—166=167--(834--4×167)=5×167—834
=5×(1001—834)一834
=5×1001--6×834
=5×1001--6×(3837—3×1001)
=23× 1001--6×3837
所以23×1001≡l(mod 3837)，故1001相关模3837乘法逆元为23。通常求乘法逆元以欧几里德算法为佳。
4.RSA算法各步骤
RSA算法是1978年由R.L.Rivest，A.Shamir和L.Adleman提出一个用数论结构、也是迄今为止理论上最为成熟完善公钥密码体制。RSA理论基础是数论中欧拉定理,它安全性依靠于大数因子分解，但并没有从理论上证实破译RSA难度和大数分解难度等价。

4.1 RSA公钥加密解密概述
RSA算法采取下述加密/解密变换。
1．密钥产生
①选择两个保密大素数P和q。
②计算N=p q，≯(N) =(p-1)(g-1)，其中≯(N)是N欧拉函数值。
③选择一个整数e，满足l<e<≯(N)，且g c d(≯(N)，e)≡1。
④计算私钥d(解密密钥)，满足e d≡l(mod≯(N))，d是e在模≯(N)下乘法逆元。
⑤以(e, n)为公钥，(d ,N)为密钥，销毁p，q，≯(N)。
2．加密
加密时首先将明文比特串进行分组，使得每个分组对应得串在数值上小于N， 即分组二进制长度小于l092N。然后，对每个明文分组M，作加密运算：
C=E k(M)=M e mod N
3．解密
对密文分组解密运算为：
M=D k (C) =C d mod N
由定理1和定理2能够证实解密运算能恢复明文M
4.2 RSA署名算法
并非全部公开密钥系统，均可同时达成秘密性和数字署名功效。通常而言， 一公开密钥系统若作为密码系统，则无法作为数字署名，反之亦然。只有极少数
系统可同时作为密码系统和数字署名，如本文讨论RSA系统。RSA署名算
法以下：
设N=p q，且p和q是两个大素数，e和d满足e d≡l(mod ≯(N))。
公开密钥：N，e
私有密钥：d
署名过程：发送方使用自己私钥d对明文m进行数字署名变换： y=x d mod N：并将加密后消息和署名y发送给接收方；
验证过程：接收方使用发送方公钥e对收到消息y进行数字署名验证变换x’=ye mod N，并使用发送方密钥解密恢复消息x，比较x’和x，假如x’=x则证实发送方身份正当。
这么，用户A若想用RSA署名方案对消息x署名，她只需公开她公钥N和e，因为署名算法是保密，所以A是唯一能产生署名人，任何要验证用户A 署名用户只需查到A公钥即可验证署名。
对于实现署名和公钥加密组合，常见方法是：假定通信双方为A和B。对于明文x，A计算她署名y=x d mod N，然后利用B公开加密函数EB对信息对(x, y)加密得到Z，将密文Z传送给B，当B收到密文Z后，她首先用她解密函数DB来解密得到(x，y)=DB (Z)= DB (EB(x，y))，然后利用A验证算法来检验x’=x=y e mod N是否成立。
4.3 大数运算处理．
RSA依靠大数运算，现在主流RSA算法全部建立在1024位大数运算之上。而大多数编译器只能支持到64位整数运算，即我们在运算中所使用整数必需小于等于64位，即：0xffffffffffffffff也就是，这远远达不到RSA需要，于是需要专门建立大数运算库来处理这一问题。最简单措施是将大数看成数组进行处理，数组各元素也就是大数每一位上数字，通常采取最轻易了解十进制数字0~9。然后对“数字数组”编写加减乘除函数。不过这么做效率很低，因为二进制为1024位大数在十进制下也有三百多位，对于任何一个运算，全部需要在两个有数百个元素数组空间上数次重循环，还需要很多额外空间存放计算进退位标志及中间结果。另外，对于一些特殊运算而言， 采取二进制会使计算过程大大简化，而这种大数表示方法转化成二进制显然很麻烦，所以在一些实例中则干脆采取了二进制数组方法来统计大数，当然这么效率就更低了。一个有效改善方法是将大数表示为一个n进制数组，对于现在32位系统而言n能够取值为232次方，即0x，假如将一个二进制为1024位大数转化成0x10000000进制，就变成了32位，而每一位取值范围不再是二进制0~ 1或十进制0~9，而是0~0xffffffff我们恰好能够用一个32位DWORD(如：无符号长整数，unsigned long)类型来表示该值。所以1024位大数就变成一个含有32个元素DWORD数组，而针对DWORD 数组进行多种运算所需循环规模至多32次而已。
比如大数1 9551 61 5，等于0Xffffffff ffffffff其表示方法就相当于十进制99：有两位，只是每位上元素不是9而全部是0xffffffff。而等于0x00000001 00000000 00000000，就相当于十进制100：有三位，第一位是l，其它两位全部是0，如此等等。在实际应用中，“数字数组"排列次序采取低位在前高位在后方法，这么，大数A就能够方便地用
数学表示式来表示其值：
X=ΣXi r i (r=0x，0<Xi <r)
任何整数运算最终全部能分解成数字和数字之间运算，在Oxl00000000进制下其“数字"最大达成Ox腼筒，其数字和数字之间运算，结果也肯定超出了现在32位系统字长。在VC++中，存在一个int64类型能够处理64位整数，所以不用担心这一问题，而在其它编译系统中假如不存在64位整形，就需要采取更小进制方法来存放大数，比如16位WORD类型能够用来表示0x10000进制。但效率更高措施还是采取32位DWORD类型。
4.4 大素数产生
依据RSA算法加解密变换，需要产生两个保密大素数作为基础运算。在前欧几里德证实了素数有没有穷多个，这自然就引出一个问题：既然素数有没有穷个，那么是否有一个计算素数通项公式?两千年来，数论学一个关键任务，就是寻求一个能够表示全体素数素数普遍公式。为此，人类花费了巨大心血。希尔伯特认为，假如有了素数统一素数普遍公式，那么这些哥德巴赫猜想和孪生素数猜想全部能够得四处理。“研究多种多样素数分布情况，一直是数论中最关键和最有吸引力中心问题之一。相关素数分布性质很多著名猜想是经过数值观察计算和初步研究提出，大多数至今仍未处理”。所以，欲得到素数，必需另寻出路。
大素数产生应是现代密码学应用中最关键步骤。几乎全部公开密钥系统均需要用到大素数，若此素数选择不妥，则此公开密钥系统安全性就岌岌可危。通常而言，素数产生通常有两种方法，一为确定性素数产生方法，一为概率性素数产生方法，现在后者是当今生成素数关键方法。所谓概率性素数产生法，是指一个算法，其输入为一奇数，输出为两种状态YES或NO之一。若输入一奇数n，输出为NO，则表示11为合数，若输出为YES，则表示n为素数概率为1-r，其中r为此素数产生法中可控制任意小数，但不能为0。这类方法中较著名有Solovay-Strassen算法、Lehmann算法、Miller-Rabin算法等。在实际应用中，通常做法是先生成大随机整数，然后经过素性检测来测试其是否为素数。数论学家利用费尔马定理研究出了多个素数测试方法，现在最快算法是Miller-Rabin(拉宾米勒)测试算法(也称为伪素数检测)，其过程以下：首先选择一个待测随机数N计算r，2r是能够整除N-12最大幂数。
1．计算M，使得N=2r×M+1。
2．选择随机数A<N。
3．若AM mod N =l，则N经过随机数A测试。
4．让A取不一样值对N进行5次测试，若全部经过则判定N为素数。
若N经过一次测试，则N为合数(非素数)概率为25％，若N经过t次测试，则为合数(非素数)概率为1／4t。实际上取t为5时，N为合数概率为1／128，N为素数概率已经大于99．99％。

5. RSA安全性
密码学所讨论系统，其安全性是最高评价准则。再好密码系统，若安全性不足则一文不值，同时，密码系统安全性极难用理论证实(实际上证实一个安全系统是安全极难，但若该系统不安全，证实它是不安全则很轻易).
RSA从提出到现在已近二十年，经历了多种攻击考验，逐步为大家接收，普遍认为是现在最优异公钥方案之一。不过在特定条件下，RSA实现细节疏忽会造成对RSA算法有效攻击。所以，对RSA体制实现各个步骤进
行充足考虑，避免安全性缺点是很有必需。
RSA安全性分析:
理论上，RSA安全性取决于因式分解模数N困难性。从严格技术角度上来说这是不正确，在数学上至今还未证实分解模数就是攻击RSA最好方法， 也未证实分解大整数就是NP问题(表示那些能在多项式时间内利用“不确定性" 图灵机能够求解问题)。事实情况是，大整数因子分解问题过去数百年来一直是令数学家头疼而未能有效处理世界性难题。大家设想了部分非因子分解路径来攻击RSA体制，但这些方法全部不比分解n来得轻易。所以，严格地说，RSA安全性基于求解其单向函数逆困难性。RSA单向函数求逆安全性没有真正因式分解模数安全性高，而且现在大家也无法证实这二者等价。很多研究人员全部试图改善RSA体制使它安全性等价于因式分解模数。
对RSA算法攻击关键有以下多个：
1．对分解模数N攻击
分解模数N是最直接也是最显然攻击目标，同时也是最困难。攻击者能够正当取得公开密钥e和模数N；假如N=p q被因式分解，则攻击者经过p、q便可计算出≯(N)=(p-1)(q-1)，进而e d≡l(mod ≯(N))而得到解密密钥d，大整数分解研究一直是数论和密码理论研究关键课题。
2．对RSA选择密文攻击
选择密文攻击是攻击者对RSA等公钥算法最常见攻击，也是最有效攻击手段之一。选择密文攻击通常是由RSA加密变换性质诱发，常见对RSA选择密文攻击有三种：
①明文破译。攻击者取得某用户A使用公钥e加密密文y=x e (mod n)，并试图恢复出消息x。随机选择r<n，计算y1=r e (mod n )，这意味，r=y1d(mod n)。计算y2=(yy1)(mod n)。令t=r-1 (mod n )，则t=y1d(mod n )，现在攻击者请A对消息y2，进行署名，得到S=y2d (mod n)。攻击者计算t l=t s=(y1-d y2d)(mod n)=(y1-dy1dyd)(mod n)= yd (mod n)=x，得到明文。
②骗取仲裁署名。在有仲裁情况下，若某用户A有一个文件要求仲裁，可先将其送给仲裁T，T使用RSA解密密钥进行署名后送给A。攻击者有一个消息想要T署名，因为因为可能有伪造时戳或来自非法使用者消息，T并不署名。但攻击者可用下述方法取得T署名。令攻击者消息为X，她首先任选一个数N， 计算y=Ne (mod n)(e是T公钥)，然后计算M=y x，送给T，T将署名结果M d mod n送给攻击方，则有：
M d N一1≡(y x)d N-1≡(x d y d N-1)≡x d NN-1≡x d(mod n)
攻击者成功骗取T对x署名。
③伪造正当署名。攻击者利用自己伪造两个消息x1和x2，来拼凑所需要x3=(x1x2)(mod n)。攻击者假如得到用户A对而和x2署名x1d(mod n)和x2d(mod n)，就能够计算屯署名，x3d=(x1d(mod n))(x2d(mod n))(mod n)。
3．对RSA小指数攻击
这类攻击专门针对RSA算法实现细节。采取小e、d能够加紧加密和验证署名速度，而且所需存放空间小，不过假如e、d太小，则轻易受到小指数攻击，包含低加密指数攻击和低解密指数攻击。经过独立随机数字对明文消息x进行填充，这么使得x e(mod n)≠xe，能够有效地抗击小指数攻击。
4．对RSA共模攻击
在RSA公钥密码实现中，为简化问题，可能会采取给每个人相同n值， 但不一样指数值e和d。这么做问题是，假如同一信息用两个不一样指数加密， 这两个指数是互素，则不需要任何解密密钥就能恢复明文。
设m是明文，两个加密密钥分别为e1，e2，共同模数为n，两个密文为：
c1=m e1 mod n
c2=me2 mod n
因为el，e2是互素，由扩展欧几里德算法能够找到r和s，使之满足
Re1+se2=1
假设r是负数(其中必有一个为负数)，再次使用欧几里德算法能够求得Ct对模数N逆元c1-1，故能够得到
(c1-1)-r c2r(mod n)≡mre1mse2(mod n)三m(mod n)
即密码分析者知道n，e1，e2，c1和c2，则能够恢复出明文m。
5．相关RSA算法明文部分信息安全性
同RSA算法一样，大多数公钥密码体制安全性是建立在单向函数之上， 即所谓单向函数模型密码体制。RSA算法使用单向函数安全性是基于大数分解困难性，即攻击者在多项式时间内不能分解模数n。但这并不能确保攻击者极难使用概率方法来推算明文一些特征或用二进制表示某个或一些比特值(即明文部分信息)。攻击者经过获取明文消息部分信息，进而能够破译或恢复整个明文信息。这就是RSA安全性另一个关键方面，能够称之为比特安全性， 即RSA算法中密文所泄漏相关明文二进制表示一些有效位部分安全性。相关RSA体制部分信息安全性最好结果是由W.Aiexi等人得出。她们证实了任何由密文E(x)(E为加密函数)以大于1／2+1／ploy(㏒N)正确概率猜对最末有效位算法F，全部可诱导出一个由密文E(x)破译出x相对于算法F非确定多项式算法，即所谓最末有效位1／2+l／ploy(㏒N)安全性。

6. 代码实现：
#include<iostream.h>
#include<math.h>
#include<stdio.h>
typedef int Elemtype;
Elemtype p,q,e;
Elemtype fn;
Elemtype m,c;
int flag=0;
typedef void(*Msghandler)(void);
struct MsgMap{
char ch;
Msghandler handler;
};
/*公钥*/
struct PU{
Elemtype e;
Elemtype n;
}pu;
/*私钥*/
struct PR{
Elemtype d;
Elemtype n;
}pr;
/*判定一个数是否为素数*/
bool test_prime(Elemtype m){
if(m<=1){
return false;
}
else if(m==2){
return true;
}
else{
for(int i=2;i<=sqrt(m);i++){
if((m%i)==0){
return false;
break;
}
}
return true;
}
}
/*将十进制数据转化为二进制数组*/
void switch_to_bit(Elemtype b,Elemtype bin[32]){
int n=0;
while(b>0){
bin[n]=b%2;
n++;
b/=2;
}
}
/*初始化主界面*/
void Init(){
cout<<"******************************************"<<endl;
cout<<"*** Welcome to use RSA encoder ***"<<endl;
cout<<"*** 1.setkey ***"<<endl;
cout<<"*** 2.加密 ***"<<endl;
cout<<"*** 3.解密 ***"<<endl;
cout<<"*** 4.退出 ***"<<endl;
cout<<"******************************************"<<endl;
cout<<"press a key:"<<endl;
}
/*将两个数排序，大在前面*/
void order(Elemtype &in1,Elemtype &in2){
Elemtype a=(in1>in2?in1:in2);
Elemtype b=(in1<in2?in1:in2);
in1=a;
in2=b;
}
/*求最大条约数*/
Elemtype gcd(Elemtype a,Elemtype b){
order(a,b);
int r;
if(b==0){
return a;
}
else{
while(true){
r=a%b;
a=b;
b=r;
if(b==0){
return a;
break;
}
}
}
}
/*用扩展欧几里得算法求乘法逆元*/
Elemtype extend_euclid(Elemtype m,Elemtype bin){
order(m,bin);
Elemtype a[3],b[3],t[3];
a[0]=1,a[1]=0,a[2]=m;
b[0]=0,b[1]=1,b[2]=bin;
if(b[2]==0){
return a[2]=gcd(m,bin);
}
if(b[2]==1){
return b[2]=gcd(m,bin);
}
while(true){
if(b[2]==1){
return b[1];
break;
}
int q=a[2]/b[2];
for(int i=0;i<3;i++){
t[i]=a[i]-q*b[i];
a[i]=b[i];
b[i]=t[i];
}
}
}
/*快速模幂算法*/
Elemtype modular_multiplication(Elemtype a,Elemtype b,Elemtype n){
Elemtype f=1;
Elemtype bin[32];
switch_to_bit(b,bin);
for(int i=31;i>=0;i--){
f=(f*f)%n;
if(bin[i]==1){
f=(f*a)%n;
}
}
return f;
}
/*产生密钥*/
void produce_key(){
cout<<"输入素数 p 和 q:";
cin>>p>>q;
while(!(test_prime(p)&&test_prime(q))){
cout<<"输入错误，请重新输入!"<<endl;
cout<<"输入素数 p 和 q:";
cin>>p>>q;
};
pr.n=p*q;
pu.n=p*q;
fn=(p-1)*(q-1);
cout<<"fn为："<<fn<<endl;
cout<<"输入随机数e:";
cin>>e;
while((gcd(fn,e)!=1)){
cout<<"e输入错误，请重新输入!"<<endl;
cout<<"输入随机数e:";
cin>>e;
}
pr.d=(extend_euclid(fn,e)+fn)%fn;
pu.e=e;
flag=1;
cout<<"公钥(e,n）:"<<pu.e<<","<<pu.n<<endl;
cout<<"私钥d:"<<pr.d<<endl;
cout<<"请输入下一步操作序号:"<<endl;
}
/*加密*/
void encrypt(){
if(flag==0){
cout<<"setkey first:"<<endl;
produce_key();
}
cout<<"输入明文 m:";
cin>>m;
c=modular_multiplication(m,pu.e,pu.n);
cout<<"密文c 为:"<<c<<endl;
cout<<"请输入下一步操作序号:"<<endl;
}
/*解密*/
void decrypt(){
if(flag==0){
cout<<"setkey first:"<<endl;
produce_key();
}
cout<<"输入密文 c:";
cin>>c;
m=modular_multiplication(c,pr.d,pr.n);
cout<<"明文m 为:"<<m<<endl;
cout<<"请输入下一步操作序号:"<<endl;
}
/*消息映射*/
MsgMap Messagemap[]={
{'1',produce_key},
{'3',decrypt},
{'2',encrypt},
{'4',NULL}
};
/*主函数，提供循环*/
void main(){
Init();
char d;
while((d=getchar())!='4'){
int i=0;
while(Messagemap[i].ch){
if(Messagemap[i].ch==d){
Messagemap[i].handler();
break;
}
i++
;}
}
}
7. RSA算法结果分析：
7.1 主界面初始化

7.2 设置密钥

输入57不是素数，报错，要求重新输入

输入素数61 67，随机数e=1，,得到公钥e=17,n=4087私钥d=233
7.3 对明文加密

输入明文m=1234，得到密文c=2793
7.4 对密文解密

对密文c=2793进行解密，得到明文m=1234

8. 总结和展望：
经过此次对RSA算法学习，明白了该算法加密解密原理，和她安全性问题和缺点，经过这几周试验，在学习中累计经验处理问题，让我对RSA算法有了较通透了解,受益匪浅。伴随Internet发展，实现电子商务是未来时尚和趋势，基于Internet开放环境下信息安全将越来越受到重视，而RSA算法在身份认证，数字署名，信息加密等方面得到很广泛应用，对它作深入了解是很有必需。即使RSA算法可靠性较高，不过还是有部分缺点，就是运算量太大，速度太慢，适合加密比较短明文。RSA方法既可用于保密，也可用于署名和认证，现在已经广泛应用和多种产品，平台等软件上。很多流行操作系统上如微软，Apple,Sun和Novell全部是在其产品上融入RSA。在硬件上，如安全电话，以太网和智能卡全部使用了RSA技术。而且几乎全部Internet安全协议如S/MIME,SSL和S/WAN全部引入了RSA加密方法。ISO9796标准把RSA列为一个兼容加密算法。能够预见，在不远几年内，RSA 应用未来会越来越广泛。

9. 参考文件：1刘嘉勇，应用密码学，清华大学出版社，；
2陈天华，面向对象程序设计和Visual C++6.0教程，清华大学出版社，