毕业论文-中国剩余定理在RSA算法中的应用论文.doc
《毕业论文-中国剩余定理在RSA算法中的应用论文.doc》由会员分享，可在线阅读，更多相关《毕业论文-中国剩余定理在RSA算法中的应用论文.doc（39页珍藏版）》请在冰点文库上搜索。
沈阳航空工业学院毕业设计论文
中国剩余定理在RSA算法中的应用
院（系）：
计算机学院
专业：
计算机科学与技术
班级：
学号：
姓名：
指导教师：
摘要
本文主要介绍了网络安全和密码学的相关概念。
分析了课题的背景以及研究的主要意义，详述了RSA公钥算法原理以及中国剩余定理加速RSA模幂运算的流程。
重点研究了RSA公开密钥体制的加密技术，并在此基础上给出了一种加入中国剩余定理提高模幂运算速度。
本文也设计出计时系统来对其进行比较演示，以清楚地显示还原密文的运行处理的时间。
旨在证明此种方式可以在保证正常运行得到正确明文的情况下较高速的运行。
加入中国剩余定理的解密算法要明显比普通加密算法具备更快的运行速度，使得RSA算法具有更高的效率，同时消耗更少的运行成本。
同时文中也探讨了密钥管理的一些重要方面，为以后在该方式上研究打下坚实的理论基础。
关键字公开密钥算法RSA算法中国剩余定理
Abstract
Thisarticlemainlyintroducedthenetworksecurityandthecryptologyrelatedconcept.Hasanalyzedthetopicbackgroundaswellastheresearchmainsignificance,hasrelatedindetailtheRSApublickeyalgorithmprincipleaswellastheChineseremaindertheoremacceleratestheRSAmoldpoweroperationflow.HaswithemphasisstudiedtheRSApublickeysystemencryptiontechnology,andgaveonekindinthisfoundationtojointheChineseremaindertheoremtoenhancethemoldpoweroperatingspeed.
Thisarticlealsodesignsthetimingsystemtocometoittocarryonthecomparisondemonstration,bydemonstratesthereturntooriginalstatescrambledtextclearlythemovementprocessingtime.Isforthepurposeofprovingthiswaymayobtaininthecorrectdefiniteorderssituationintheguaranteenormaloperationthehighspeedmovement.JoinstheChineseremaindertheoremthedecipheralgorithmtohaveobviouslytohavethequickerrunningratecomparedtotheordinaryencryptionalgorithm,enablestheRSAalgorithmtohaveahigherefficiency,simultaneouslyconsumesthelessmovementcost.
Simultaneouslyinthearticlehasalsodiscussedsomeimportantaspectswhichthekeymanages,willstudyforlaterinthiswaybuildsthesolidrationale.
KeywordsPublickeyalgorithm,RSAalgorithm,Chineseremaindertheorem
-4-
沈阳航空工业学院毕业设计论文
目录
第一章绪论 1
1.1课题背景 1
1.2密码学介绍 2
1.2.1密码学发展 2
1.2.2数据加密和解密 3
1.2.3密钥体制 4
1.3研究的意义 4
第二章需求分析与方案设计 6
2.1需求分析 6
2.2经济技术分析 6
2.3开发工具 7
第三章系统实现主要技术说明 8
3.1数论基础 8
3.1.1求素数 8
3.1.2求互质 9
3.1.3模运算与大数模运算 10
3.1.4求模逆 13
3.1.5中国剩余定理 14
3.1.6费尔马小定理 15
3.1.7欧拉函数 15
3.2RSA算法 16
3.2.1算法概述 17
3.2.2RSA 的安全性 18
3.2.3RSA的速度 19
3.2.4RSA的缺点 19
3.3中国剩余定理加速RSA的模幕运算原理简介 20
第四章系统实现 21
4.1算法设计 21
4.1.1加密过程概述 21
4.1.2解密过程概述 21
4.1.3加解密算法流程 21
4.2加速过程设计 25
第五章系统的运行与测试 27
5.1系统的运行环境 27
5.2单元测试 27
5.2.1运行程序 27
5.2.2输入明文 28
5.2.3对明文进行加密 29
5.2.4进行密文的解密 29
5.3加速测试 30
结论 32
参考文献 33
致谢 34
沈阳航空工业学院毕业设计论文绪论
第一章绪论
1.1课题背景
伴随网络技术的发展，Internet技术迅速在全球范围内普及，现在已经进入了人们生活的方方面面，并且正在以不可替代的趋势推动社会各个领域的前进和相应变革。
人类实际上己经进入了“网络时代”。
随着计算机网络在电子政务、电子商务，网络金融等与国民经济和人民生活息息相关的领域的广泛应用，网络安全问题也日益成为人们关注的焦点。
网络安全是涉及面广的问题，不仅涉及到计算机科学一门学科，也涉及到数学、管理、法律等学科，网络安全主要包括:
数据保密、访问控制、身份认证、不可否认和信息完整性。
其中首要的是数据保密，要保证被保密处理的数据不能被非法用户获取以及解密从而获得明文。
而访问控制，是指系统对用户和资源分配不同的权限，根据各自相应的权限，系统可以分配用户资源，可以控制用户对资源的访问。
身份认证是在网络中实现对对方身份的数据核实。
数字签名则是用来防止签署方否认或抵赖。
完整性是指用户获取的数据没有被非法篡改过。
为解决Internet上的数据保密问题，世界各国进行了多年的研究，提出了一系列加/解密算法。
公钥密码学的出现，使得现代密码学终于有了划时代的发展。
传统的单钥密码体制（又称为对称密码体制）使用相同加密解密密钥对消息进行加密和解密，所以必须对密钥严格保密，以防止密钥丢失会造成对加密信息的泄露。
公钥密码体制（又称为非对称密码体制）与传统密码体制的根本不同在于——它拥有一对不同的加密密钥和解密密钥，加密密钥可以公开，不用保密；而解密密钥只要不能在合理的时间内根据公开的加密密钥计算出来即可，这样就给密钥管理提供了更大的发挥空间。
公开密钥密码体制可以在以下两方面得到应用:
一方面是信息的加密，即发送方用接收方的公钥加密某一消息得到秘密信息，而接收方用自己的私钥解密，从而恢复这一消息；另一方面是公钥体制新发展出的应用——数字签名，即发送方用私钥加密某一消息（或其单向函数散列值），得到秘密信息，接收方用发送方的公钥恢复出发送方的信息；这种应用的重点不在于加密，而是验证，即只要接收方可以确定发送方的身份即可，而不用在意这条消息是否保密。
1.2密码学介绍
数据保密技术或密码技术，是对计算机当中关键信息进行保护的最实用和最可靠的方法。
这样相应的就出现了两门学问:
密码编码学（进行密码体制设计）和密码分析学（在未知密钥的情况下，从密文推出明文或密钥的技术）。
这两门学问共同构成了密码学。
密码编码学主要研究对信息进行编码，实现对信息的隐蔽。
而密码分析学主要研究加密消息的破译或消息的伪造。
这两者就象一矛一盾，在相互的斗争当中，密码学就这样发展起来。
1.2.1密码学发展
早在远古时代，人类就有了密码技术的概念了。
在英文单词中，密码学（Cryptology）一词源自希腊词语Krvntos和Grannein，意思是秘密写。
正如历史上其他技术的发展一样，密码技术的发展最早也是源于人工阶段，然后相应的经历了机械阶段，最后发展到目前所用的电子阶段，而且该技术也正与其他技术日益结合，近代密码技术己经成为一门和数学紧密相连的学科，最终演变为密码学。
在第一次世界大战之前，密码技术的进展很少见诸于世，一直到1918年，WilliamF.Friedman的论文“重合指数及其在密码学中的应用”发表时，情况才有所好转。
1949年，ClaudeShannon的奠基性论文“保密系统的通信理论”在《贝尔系统技术杂志》上发表，莫定了密码学的理论基础。
此后，直到1967年，密码学文献几乎空白。
1967年，DavidKahn收集整理了一战和二战的大量史料，创作出版了《破译者》，为密码技术的公开化、大众化拉开了序幕。
此后，密码学的文献大量涌现。
20世纪70年代，是密码学发展的重要时期，有两件重大事件发生。
一是美国国家标准局（NBS，即现在的国家标准与技术研究所NIST）开始数据加密标准的征集工作。
1975年3月17日NBS在FederalRegiste:
上公布了一个候选算法，于次年被正式确认为联邦标准DES，并授权在政府通信中使用，并被美国国家标准局于1977年公布实施，而且公开了它的加密算法。
密码学的神秘面纱从此被揭开。
二是1976年11月Diffie与Hellman的革命性论文“密码学新方向”发表，开辟了公开密钥密码学的新领域，成为现代密码学的一个里程碑。
1978年R.L.Rivest,A.Shamir和L.Adleman实现了RSA公钥密码体制，它成为公钥密码的杰出代表和事实标准。
在密码学的发展过程中，数学和计算机科学都做出了相当卓越的贡献。
密码学涉及到数学中的许多分支知识，诸如数论、概率统计。
近世代数、信息论、椭圆曲线理论、算法复杂性理论、自动机理论、编码理论等都可以在其中找到各自的位置。
并且密码学的迅速发展还推动了并行算法的开发和研究，从而成为近若干年来一个极其引人入胜的研究领域。
随着计算机、电子通讯技术的飞速发展，现代密码学及其应用也得到了重大发展。
数字签名，身份认证及鉴别都是由密码学派生出来的新技术和应用。
1.2.2数据加密和解密
数据加密即是对明文（未经加密的数据）按照某种的加密算法（数据的变换算法）进行处理，而形成难以理解的密文（经加密后的数据）。
即使是密文被截获，截获方也无法或难以解码，从而防止泄露信息。
数据加密和数据解密是一对可逆的过程，数据加密技术的关键在于：
（1）密钥的管理：
包括密钥的产生、选择、分发、更换和销毁等。
密钥的安全程序直接影响着数据的安全，一旦密钥外泄，加密后的数据也就不存在任何安全性可言了。
（2）加密解密算法：
在数据加密过程中，必须选用适当的加密解密算法。
一方面要保证达到给定的安全级别，另一方面也必须控制加密和解密的开销以保证性欲比。
加密和解密算法的设计通常需要满足三个条件：
1）可逆性
2）密钥安全：
在攻击者掌握了明文和相应的加密方式，甚至知晓加密解密算法的情况下，无法或者很难从中计算出密钥来。
3）数据安全：
攻击者在不知道密钥的情况下，不可能或者极其艰难地根据密文，推算出明文来。
1.2.3密钥体制
按照加密密钥和解密密钥的异同，有两种密钥体制
（1）秘密密钥加密体制
加密和解密采用相同的密钥，因而又称为对称密码体制。
因为其加密速度快，通常用来加密大批量的数据的方法有美国的数据加密标准DES。
DES是国际标准化组织核准的一加密算法。
自1976年颂以来得到广泛的应用，但近年来对它的安全性提出了疑问。
1986年美国政府宣布不再支持DES作为美国国家数据加密标准，但同时又不准颂用来替代DES的加密算法。
其他各国也都有自己的商业得病和安全考虑。
所以ISo标准中核准的加密算法至今未见有大的变化。
由于DES算法本身存在固有的弱点以及人已有对它进行攻击的办法，发达国家都在考虑亲的算法以替代DES。
（2）公开密钥加密体制
又称不对称密码体制，其加密和解密使用不同的密钥，其中一个密钥是公开的，另一个密钥是保密的。
由于加密速度较慢，所以往往用在少量数据的通信中。
典型的公开密钥加密方法有RSA和NTT的ESIGn。
RSA算法的保密性取决于数学上将一个大数分解为两个素数的问题的难度。
根据已有的数学方法，其计算量极大，破解很难。
但加密解密时要进行的大指数模运算，因此加密解密速度很慢，影响推广使用。
一般DES算法的密钥长度为56位，RSA算法的密钥长度为512位。
为了加速DES算法和RSA算法的执行过程，可以用硬件电路来实现加密和解密。
1.3研究的意义
RSA体制算法完善（既可用于数据加密，又可用于数字签名），安全性良好，易于实现和理解。
使用RSA体制作为课题算法和方案的实现基础，我们可以有效地利用RSA体制的优点。
同时，关于RSA体制的大量的研究工作的文献和成果为本文研究工作的开展提供了良好的基础。
RSA体制是最具代表性的公钥密码体制。
RSA体制的特点使得它成为公钥密码体制研究的一个标准模板。
同时，由于RSA算法发展至今，在实现技术上己经相当成熟，因此本文算法的实现在许多方面都可以利用己有的技术，这对增强算法的实用性是非常有益的。
RSA算法计算复杂，实现的难度大。
软件实现主要问题是加密、解密操作要计算位数达十进制百位以上的模幂乘函数。
执行的时间长，难以满足实际使用要求。
在实际应用中，其加密和解密的速度是主要的问题，所以研究RSA的快速算法具有非常重要的现实意义。
本论文主要研究了密码学尤其是RSA的发展历程，及目前RSA在应用中面临的问题。
在大量阅读国内外重要文献资料的基础上，深入剖析了RSA算法的精要。
在第五章介绍了作者对RSA算法有关实现细节进行的改进及改进前后的对比。
沈阳航空工业学院毕业设计论文第二章需求分析与方案设计
第二章需求分析与方案设计
2.1需求分析
RSA算法的主要优点之一在于原理简单，方便人们编程应用。
但是随着大数分解方法的进步以及计算机计算速度的日新月异，尤其是计算机网络和分布式计算（对一个大数用上万台电脑协同处理进行分解）等因素，RSA的安全性已远不能停留在原来的基础上了，其中关键的就是要保证密钥位数足够的长，并且要一直加长，以前认为RSA密钥需要1024位（二进制）长度就比较安全了，但随着计算机运行速度和破译手段的发展，这个长度开始受到威胁。
本文设计的系统中，密钥认证部分可以产生长至600位（十六进制，也即2400位二进制）的RSA公/私钥。
密钥越长，对其分解越困难，系统也就越安全，但对由此产生的加解密速度也提出了更高的要求，相应的硬件实现也变的越困难。
在该设计中，主要以基本的RSA算法为主，进行该算法规定的数学运算以达到将明文加密解密的作用，并加入中国剩余定理提高RSA算法中的模幂运算，比较两者的效率，，在本次课题设计中，主要以该算法的加密解密功能为主，运用中国剩余定理提速来实现对密文的解密作用。
2.2经济技术分析
1、基建投资：
开发本系统需要PC机1台，WindowsXP操作系统，MicroSoftVisualC++6.0。
其中MicroSoftVisualC++6.0可以从网上免费下载。
基建投资基本上只需要五千元人民币。
2、其它一次性支出：
由于该程序算法已经被公开，根据本系统的功能要求，编程时间大约为2个月，人员费用及大约2千元左右。
3、效益：
由于该软件的特殊性，其具体经济价值不容易估计，但是可以知道使用该软件进行的签名带来的社会和经济效益将是巨大的，所以在经济技术方面是完全可行的。
4、技术性：
RSA公钥算法的原理简单，它既能用于数据加/解密，也能用于数字签名的算法。
由于其易于理解和操作，实际中也很流行，并己获得一定推广使用的公开密钥算法。
许多大型软件公司已研发出基于RSA算法的加解密软件。
模幂运算的效率决定了RSA密码系统的执行速度。
由于中国剩余定理对于提高RSA算法的模幂运算效率有显著作用，已经广泛的应用于RSA算法之中。
2.3开发工具
开发工具的选择是基于题目的需要，和开发工具的特点来选用的。
前端开发工具选用MicroSoftVisualC++6.0，操作系统是WindowsProfessionalXPSP2，以下将对VisualC++6.0的特点做以下介绍。
VisualC++6.0编程语言是由Microsoft公司推出的目前极为广泛的可视化开发工具，利用VisualC++6.0可以开发基于Widnows平台的32位应用程序，依靠强大的编译器以及网络与数据库的开发能力，用VisualC++6.0可以开发出功能强大的应用程序。
-33-
沈阳航空工业学院毕业设计论文第三章系统实现主要技术说明
第三章系统实现主要技术说明
3.1数论基础
本系统采用的RSA算法是建立在严密的数论基础之上的，如果没有一定的数论基础将无法理解其核心算法，因此有必要先对本论文所涉及到的相关数论知识进行介绍和研究，这将有助于对RSA算法及后续核心算法实现的分析。
3.1.1求素数
boolisprime（intp）
{
inti,n=（int）sqrt（p）;
for（i=2;i<=n;i++）
{
if（p%i==0）
return0;
}
return1;
}
从上面的函数来看，求素数的过程的实现看起来似乎并不困难，但在想要在越大的范围里找到一个素数就是越难，也就是所需要的计算量就越大，这个时间的变化是很大的，但是并不能因此而限制素数的搜索范围，因为必须要随机的产生一个很难在近期内再次使用的素数，这样才能保证加密算法的可靠性。
生成算法流程如下
图3-1求素数流程图
3.1.2求互质
两个数互素是指：
当它们除了一之外没有共同的因子，换句话说，如果a和n的最大公因子等于一，那么可以写作gcd（a,n）=1
数15和28是互素的，15和27不是，而13和500是。
一个素数与它的倍数以外的任何其他数都是互素的。
计算两个数的最大公因子最容易的方法是用欧几里德算法。
这个算法并非是他发明，历史学家相信这个算法在当时已有二百年的历史了。
它的幸存到现在的最古老的非凡算法，至今它仍是完好的。
他的C语言描述如下：
intgcd（intx,inty）
{
intg;
if（x<0）
x=-x;
if（y<0）
y=-y;
if（x+y==0）
ERROR;
g=y;
while（x>0）
{
g=x;
x=y%x;
y=g;
}
returng;
}
3.1.3模运算与大数模运算
本质上，如果成立，那么。
如果a为正，b在0和n之间，那么你可将b看作a被n整除后的余数。
有时，b被叫做a模n的余数。
有时a被叫做与b模n同余。
这些都是对同一事物的不同说法而已。
从0到n-1的整数组成的集合构成的集合构成了模n的完全剩余集。
这意味着，对于每一个整数a，它的模n的余项是从0到n-1的某个数。
a模n的运算给出了a的余数，余数是从0到n－1的某个整数，这个运算称为模变换。
在这里模的定义与一些编程语言中的模定义或许有些不同。
例如，PASCAL的模操作符有时返回一个负数。
它返回一个从－（n-1）到n－1之间的数。
在C语言中，除操作返回第一个表示项被第二个表示项相除所得出的余数，如果其中任意一个操作项是负的，那么结果可能为负。
在此处的说明是，如果它返回一个负数，那么应该将n加到这个模去运算操作的结果上。
模去运算就像普通的运算一样，它是可交换的、可结合的、可分配的。
而且，简化运算每一个中间结果的模n运算，其作用与先进行全部去运算，然后再简化模n运算是一样的。
密码学用了许多模n去处，因为像计算离散对数和平方根这样的问题很困难，而模运算可将所有中间结果和最后结果限制在一个范围内，所以用它进行计算较为容易。
对一个k位的模数n，任何加减乘的中间结果将不会超过2k位长。
因此可以用模去运算进行指数运算而又不会产生巨大的中间结果。
虽然计算某数的乘方并对某数取模的运算：
将导致一毓的乘法和除法运算，但有加速的方法：
一种方法旨在最小化模乘法运算的数量；另一种旨在优化单个模乘法运算。
因为操作划分后，当完成一串乘法，并且每次都进行模运行后，指数运算就更快了，这样就与一般取幂没有多大差别，但当你用200位的数进行操作的时候情况就不同了。
例如，如果要计算，不要直接进行七次乘法和一个大数的模化简：
相反，应进行较小的乘法和三次较小的模化简：
依此类推：
当x不是2的幂次方时，计算要难一些。
可将x表示成2的幂次方之和：
在二进制中，25是11001，因此。
下面给出大数模运算的C语言实现。
intdashumod（intch,intd,intn）//tmodn
{
inta,b,c;
a=ch,b=d,c=1;
while（b!
=0）
{
if（b%2==0）
{
b=b/2;
a=mod（（a*a）,n）;
}
else
{
b--;
c=mod（（c*a）,n）;
}
}
returnc;
}
intmod（intt,intn）//tmodn
{
intq,moshu=-1;
if（t>=0）
returnt%n;
else
{
q=abs（t）/n;
return（n*（q+1）+t）%n;
}
3.1.4求模逆
4的乘法逆元是1/4，因为。
在模运算的领域，这个问题更复杂：
这个议程造价于寻找一组x和k，以使：
x和k在此为整数
更为一般的问题是寻找一个x，使得：
也可
升级会员 