数论在密码学中的应用new

1、 本科学生毕业论文（设计） 题目（中文）： 数论在密码学中的应用 （英文）： The Application of Number Theory in Cryptography 姓 名 龙 瑞 学 号 200805001104 院 （系） 湖南科技学院数学与计算科学系 专业、年级 数学与应用数学 0801班 指导教师 王启春（博士） 2012年 5 月 1日湖南科技学院本科毕业论文（设计）诚信声明本人郑重声明：所呈交的本科毕业论文（设计），是本人在指导老师的指导下，独立进行研究工作所取得的成果，成果不存在知识产权争议，除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经发表或撰写过的作品

2、成果。对本文的研究做出重要贡献的个人和集体均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 本科毕业论文（设计）作者签名： 二一二年五月一日 目录1绪论11.1引言11.2数学语言12数论22.1同余32.2质数与互质32.3因数分解42.4几个定理的证明53密码学64 RSA算法74.1公开密钥74.2现行公钥RSA加密算法的基本思想74.3公钥与密钥的产生94.4加密消息94.5解密消息94.6实例说明RSA算法的全过程104.7签名消息104.8安全性114.9 RSA前景115背包原理125.1背包原理125.2超递增序列135.3背包系统的加密和解密方法146结束

3、语15主要参考资料：16致谢17数论在密码学中的应用摘要论文介绍了一些数论的基本知识和密码学的主要思想。并着重从RSA算法与背包原理算法两个方面介绍了数论在密码学中的应用。而且构造了一个简单的数学语言体系对背包原理和RSA的实例讲解。本文把数论蕴含在整个密码学的两种算法的阐述之中，其重点是现行的公钥体制RSA，全面的介绍了其产生，运用，安全性，发展，未来前景及局限性。关键词： RSA算法，背包原理，数论，密码学，公钥体制The Application of Number Theory in CryptographyAbstractThis paper introduces some basic

4、 knowledge of number theory and cryptography, Emphasize from RSA algorithm and knapsack algorithm, it will introduce the two aspects of the application of number theory in cryptography. And constructed a simple mathematical language system on the backpack principle and RSA examples to explain.In thi

5、s paper, the number theory is described in all the two algorithms in cryptography, the focus is on current public key system RSA, a comprehensive introduction to the use of safety, development, future prospects and limitations.Key words: RSA algorithm, knapsack theory, number theory, cryptography, p

6、ublic key systemIII1绪论1.1引言数论是数学中最古老、最纯粹的一个重要数学分支。素有“数学王子”之称的19世纪德国数学大师高斯就曾说过，数学是科学的皇后，数论是数学的皇后。数论，顾名思义，是一门研究数字性质的学问。一般所谓的数论，特指正整数(即自然数)的许多性质，例如同余、质数、数论函数、有限域、背包原理等。密码学是研究编制密码和破译密码的技术科学。研究密码变化的客观规律，应用于编制密码以保守通信秘密的，称为编码学；应用于破译密码以获取通信情报的，称为破译学。总称密码学。密码学，起初是应用于军事信息的保密上，但是随着当今社会计算机网络的发展，尤其是电子商务的普及与深入，密码

7、设计在非军事领域也大有用武之地,密码已经与我们每一位息息相关。而密码学的发展到现在与数学，特别数学的基础数论已经密不可分，可以说密码学是数论从理论到现实的一个应用，而数论是密码学走向更高的基石。1.2数学语言为了本文的讨论方便，现就本文涉及到的自然语言与数学语言做如下规定；1.本文将一个字母代替整个传输过程中的数据，也就是一个字母成立则对于由字母构成的所有整体也成立。2.由于文字母只有26个，本文计算过程中，为了简化，不考虑语言中问号、惊叹号、逗号与句号等的区别，只考虑语言的停顿间隙，并一律用空格表示，那么，组成数字语言的基本单位就有了共27个（），将不使用ASCII值，只使用如下表所示的字母

8、和数学语言的简单对应如表1。表1字母二进制数十进制数字母二进制数十进制数a000011o0111115b000102p1000016c000113q1000117d001004r1001018e001015s1001119f001106t1010020g001117u1010121h010008v1011022i010019w1011123j0101010x1100024k0101111y1100125l0110012z1101026m0110113空格000000n01110142数论数论就是指研究整数性质的一门理论。整数的基本元素是素数，所以数论的本质是对素数性质的研究。2000年前，欧几

9、里得证明了有无穷个素数。寻找一个表示所有素数的素数通项公式，或者叫素数普遍公式，是古典数论最主要的问题之一。它是和平面几何学同样历史悠久的学科。高斯誉之为“数学中的皇冠” 按照研究方法的难易程度来看，数论大致上可以分为初等数论（古典数论）和高等数论（近代数论）。 初等数论主要包括整除理论、同余理论、连分数理论。它的研究方法本质上说，就是利用整数环的整除性质。初等数论也可以理解为用初等数学方法研究的数论。其中最高的成就包括高斯的“二次互反律”等。高等数论则包括了更为深刻的数学研究工具。它大致包括代数数论、解析数论、算术代数几何等等。下面粗略的介绍一些在本文中需要应用的数论中的知识。2.1同余设m

10、是大于1的正整数，a,b是整数，如果ma-b,则称a，b关于模m同余，记作ab(mod m),读作a同余b模m。通俗的讲就是m除a,b余数相同则a,b关于m同余。例如5和7除以2，余数都是1，则5和7关于2同余。同余有如下性质:(1) ；(2)若，则；(3)如果， ，那么；(4)如果， 那么，；(5)若，则； (6)如果那么 ；(7)若， 则；(8)若，则，其中表示的最小公倍数；(9)欧拉定理：设 ，指模m的简系个数，；2.2质数与互质如果一个整数（1除外）只有1和它本身两个约数，则这个数是质数（即素数）。若两正整数p,q的最大公因子(约数)是1，则我们称p,q互质，以(p,q)=1表示之。如

11、13是质数，13与28互质。素性检测是数论中一个经典的问题 ，近代密码学的兴起给它注入了新的活力 ，其中最重要的是素数的判定 ，特别是在素数的生成和分解。强素数的提出源自RSA对p,q两素数的要求。椭圆曲线公钥密码中所涉及到大特征基域的尺寸和安全椭圆曲线的基点 的阶也需要是确定意义下的素数 ，而不是概率素数 。 目前，学术界关于素性证明的算法有两种 ：一种是椭圆曲线素性证明，现已列入IEEE标准P1363中；另一种是现行公开密钥码系统最常用的 Miller-Rabin素数测试 。 1)素数分布定理：设为小于或等于的全部素数个数 ，则 。2)威尔逊定理：n是素数的充要条件下有： 。威尔逊定理给出

12、判定素数充要条件 ，有很高的理论价值 。但用来寻找素数不适当 。 3)Fermat 定理（费马小定理）：关于素数还有一个 Fermat 定理。此定理给出素数的必要条件 p ，若不满足 ，则可断定它为素数 定理内容为，若p是素数 ，则对于任意的整数a ，应有 。2.3因数分解整数分解（质因子分解）问题是指：给出一个正整数，将其写成几个质数的乘积。例如，给出45这个数，它可以分解成32 ×5。本文接下来要着重介绍的RSA算法就是一个基于大数分解的算法。而RSA用到都是128bit及以上的大数，用计算机和人脑都是很难分解的。下面给大家介绍一种大数分解的方法让大家体验一下大数分解的难度：几率

13、演算法：首先选定一个简单的整数多项式,如，再任选并且依序计算。然后计算，且，若q可以整除n，则q是n的一个因数。例如： 所以我们得到了91的一个质因数7，另外一个13也可以用类似方法求出。但是这还只是两位的，要是对于更大的数，我们要处理的次数就越多，它的质因数每增加一个，计算量就成指数增加，所以即使你懂得了分解方法，要用计算机去分解一个大数（128bit及以上）要需要几十年年的时间。2.4几个定理的证明1)若两正整数互质，则可以找到二整数(不一定正) 使得证明：令A为含所有为整数之集合，此集合显然不是空集合，因可取。令d为此集合中之最小者，若，则本定理得证，若，令，则任取此集中之另一数。，则我

14、们若以d除，则得代入则得此r必为0，否则r为A集中一小于d之数，与假设d为最小数相矛盾，因r=0故d为A集中任何一数之因子。因故d为之公因子。但之最大公因子为1，故d=1，定理证毕。2)若w与m为二互质的正整数且，则可找到一正整数使得证明：由定理知，有二整数使得，因为之倍数，故令则得且因不可能为0，故得证。3)若为质数，为任一与互质之整数，则证明：先把w写成w个1的和，则由多项式定理知之展开式中除w个1之外，都含有之因子，(为质数中之不可能消去)，故两边乘以2)中之a，即得本定理证毕。3密码学密码学是研究编制密码和破译密码的技术科学。研究密码变化的客观规律，应用于编制密码以保守通信秘密的，称为

15、编码学；应用于破译密码以获取通信情报的，称为破译学。总称密码学。 密码学是研究如何隐密地传递信息的学科。在现代特别指对信息以及其传输的数学性研究，常被认为是数学和计算机的分支，密码学的首要目的是隐藏信息的涵义，并不是隐藏信息的存在。密码学也促进了计算机科学，特别是在于电脑与网络安全所使用的技术，如访问控制与信息的机密性。密码学已被应用在日常生活：包括银行卡的优盾、电脑使用者存取密码、qq等网络应用密码等等。 密码是通信双方按约定的法则进行信息特殊变换的一种重要保密手段。依照这些法则，变明文为密文，称为加密变换；变密文为明文，称为脱密变换。密码在早期仅对文字或数码进行加、脱密变换，随着通信技术的

16、发展，对语音、图像、数据等都可实施加、脱密变换。 密码学是在编码与破译的斗争实践中逐步发展起来的，并随着先进科学技术的应用，已成为一门综合性的尖端技术科学。它与语言学、数学、电子学、声学、信息论、计算机科学等有着广泛而密切的联系。它的现实研究成果，特别是各国政府现用的密码编制及破译手段都具有高度的机密性。 4 RSA算法4.1公开密钥进行明密变换的法则，称为密码的体制。指示这种变换的参数，称。为密钥。它们是密码编制的重要组成部分。密码体制的基本类型可以分为四种：错乱即按照规定的图形和线路，改变明文字母或数码等的位置成为密文；代替即用一个或多个代替表将明文字母或数码等代替为密文；密本即用预先编定

17、的字母或数字密码组，代替一定的词组单词等变明文为密文；加乱即用有限元素组成的一串序列作为乱数，按规定的算法，同明文序列相结合变成密文。以上四种密码体制，既可单独使用，也可混合使用 ，以编制出各种复杂度很高的实用密码。公开密钥算法是在1976年由当时在美国斯坦福大学的迪菲（Diffie）和赫尔曼(Hellman)两人首先发明的（论文”New Direction in Cryptography”）。但目前最流行的RSA是1977年由MIT教授Ronald L.Rivest,Adi Shamir和Leonard M.Adleman共同开发的,分别取自三名数学家的名字的第一个字母来构成的。4.2现行公

18、钥RSA加密算法的基本思想公钥加密算法中使用最广的是RSA。RSA使用两个密钥，一个公共密钥，一个专用密钥。因为公钥是公开对外发布的，所以想给私钥持有者发送信息的人都可以取得公钥，用公钥加密后，发送给私钥持有者，即使被拦截或窃取，没有私钥的攻击者也无法获得加密后的信息，可以保证信息的安全传输 另外，先用私钥加密，再用公钥解密，可以完成对私钥持有者的身份认证，因为公钥只能解开有私钥加密后的信息。 虽然公钥和私钥是一对互相关联的密钥，但是并不能从两者中的任何一把，推断出另一把。如用其中一个加密，则可用另一个解密，密钥长度从40到2048bit可变，加密时也把明文分成块，块的大小可变，但不能超过密钥

19、的长度，RSA算法把每一块明文转化为与密钥长度相同的密文块。密钥越长，加密效果越好，但加密解密的开销也大，所以要在安全与性能之间折衷考虑，一般64位是较合适的。RSA的一个比较知名的应用是SSL，在美国和加拿大SSL用128位RSA算法，由于出口限制，在其它地区（包括中国）通用的则是40位版本。下面用一个简单的示意图，帮助大家理解基于RSA算法的数据传输（加密与解密）过程。基于RSA算法的数据传输过程图3.1数据传送方的数据加密后的数据加密RSA算法数据接收方的公钥解密RSA算法数据接收方的私钥数据接收方获得原始数据从图3.1中我们可以看出所谓的公开密钥密码体制（下文通常默认指RSA）就是使用

20、不同的加密密钥与解密密钥(两者都由数据接收者持有，公钥是公开的，而私钥是接收者所独有的)。RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现在的三十多年里，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。在公开密钥密码体制中，加密密钥（即公开密钥）PK是公开信息，而解密密钥（即秘密密钥）SK是需要保密的。加密算法E和解密算法D也都是公开的。虽然秘密密钥SK是由公开密钥PK决定的，但却不能根据PK计算出SK。4.3公钥与密钥的产生假设A给B传送一个消息，A可以用以下的方式来产生一个公钥和一个私钥：1. 根据欧

21、拉函数，不大于且与互质的整数个数为.选择一个整数与互质，并且小于.用以下这个公式计算.将和的记录销毁。是公钥，是私钥。是秘密的。A将她的公钥传给B，而将她的私钥藏起来。4.4加密消息因为B知道产生的和。他使用起先与A约好的格式将转换为一个小于N的整数n，比如他可以将每一个字转换为这个字的Unicode码，然后将这些数字连在一起组成一个数字。假如他的信息非常长的话，他可以将这个信息分为几段，然后将每一段转换为n。用下面这个公式他可以将n加密为c：。计算c并不复杂。B算出c后就可以将它传递给A。4.5解密消息A得到B的消息c后就可以利用她的密钥d来解码。他可以用以下这个公式来将c转换为n：。得到n

22、后，他可以将原来的信息m重新复原。解码的原理是以及和。由费马小定理可证明（因为p和q是质数）和。这说明（因为p和q是不同的质数，所以p和q互质）。4.6实例说明RSA算法的全过程下文将通过一个数据传输假设（此假设省略了加密过程中的数据转换过程）为大家讲解RSA加密算法的实现。现在假设数据发送方（A）要给数据接受方（B）发送一个私人数据sa,按照表1不烦把sa对应成数学语言1901（十进制对应）。比如传输1901的时候我们选取p=47,q=59则n=2773。不妨选择d=157,则根据4.3中可以算出e=17。把明文1901自乘e（=17）次，并模n（=2773）得到余数1281，就是密文。这就

23、是加密的全过程了，而解密的时候我们接收方已经知道了密文1281，密钥d=157以及公钥n=2773利用4.5中的公式，也就是说我们只要把模去若干个n即可得到明文1901，再把1901根据表1翻译成自然语言就是sa。这里牵涉到两个很大的数的同余问题，可以参考一下高等教育出版社的竞赛数学教程第二版。以第一个计算除以2773的余数为例，很容易看出，进而进而可以算得，从而，这样我们就得到密文了。4.7签名消息RSA也可以用来为一个消息署名。假如甲想给乙传递一个署名的消息的话，那么她可以为她的消息计算一个散列值(Message digest)，然后用她的密钥(private key)加密这个散列值并将这

24、个“署名”加在消息的后面。这个消息只有用她的公钥才能被解密。乙获得这个消息后可以用甲的公钥解密这个散列值，然后将这个数据与他自己为这个消息计算的散列值相比较。假如两者相符的话，那么他就可以知道发信人持有甲的密钥，以及这个消息在传播路径上没有被篡改过。4.8安全性假设偷听者乙获得了甲的公钥N和e以及丙的加密消息c，但她无法直接获得甲的密钥d。要获得d，最简单的方法是将N分解为p和q，这样她可以得到同余方程并解出d，然后代入解密公式导出n（破密）。但至今为止还没有人找到一个多项式时间的算法来分解一个大的整数的因子，同时也还没有人能够证明这种算法不存在。至今为止也没有人能够证明对N进行因数分解是唯一

25、的从c导出n的方法，但今天还没有找到比它更简单的方法。（至少没有公开的方法。）因此今天一般认为只要N足够大，那么黑客就没有办法了。假如N的长度小于或等于256位，那么用一台个人电脑在几个小时内就可以分解它的因子了。1999年，数百台电脑合作分解了一个512位长的N。今天对N的要求是它至少要1024位长。1994年彼得·秀尔（Peter Shor）证明一台量子计算机可以在多项式时间内进行因数分解。假如量子计算机有朝一日可以成为一种可行的技术的话，那么秀尔的算法可以淘汰RSA和相关的衍生算法。（即依赖于分解大整数困难性的加密算法）假如有人能够找到一种有效的分解大整数的算法的话，或者假如量

26、子计算机可行的话，那么在解密和制造更长的钥匙之间就会展开一场竞争。但从原理上来说RSA在这种情况下是不可靠的。4.9 RSA前景针对RSA最流行的攻击一般是基于大数因数分解。1999年，RSA-155（512 bits）被成功分解，花了五个月时间（约8000 MIPS年）和224 CPU hours在一台有3.2G中央内存的Cray C916计算机上完成 。2002年，RSA-158也被成功因数分解。RSA-158表示如下：39505874583265144526419767800614481996020776460304936454139376051579355626529450683609

27、727842468219535093544305870490251995655335710209799226484977949442955603= 3388495837466721394368393204672181522815830368604993048084925840555281177×116588234066712599031483765583832708181310122581463926004395209941313443341629245361392009年12月12日，编号为RSA-768 （768 bits, 232 digits）数也被成功分解1。这一事件威胁了

28、现通行的1024-bit密钥的安全性，普遍认为用户应尽快升级到2048-bit或以上。RSA-768表示如下：1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413= 33478071698

29、956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489×6032283815739666511279233373417143396810270092798736308917尽管这样RSA加密在相当一段时间内还是很有市场的，除非量子计算机真正的问世，还有就是RSA由于需求的位数越来越高，计算的速度也会越来越慢，对计算机的要求也会越高，个人认为终有被取代的一天，而且其中新加密方法也要必不可少的运用到数学的思想！5背包原理5.1背包原理

30、设想有一个长方体形状的背包，里面恰好装满一组大小不等、形状各 异的积木块。又，旁边还有一堆积木块。如果把背包里的积木块倒在这一堆积木块里搅匀，那么再从中挑出一组积术块使它们恰好装满背包是十分困难的。类似的数学问题可表述为 ：背包问题： 设，n是正整数，也是正整数。问是否存在使 A称为背包矢量或背包序列。 这里A就像那一大堆积木块，a是背包，能不能从A中挑出 恰好装满n是很难判断的。用专业语言来说，这是一个NP完全问题(见本节后注1)。 不过对于某些背包矢量A，上述问题是容易解决的，这就是矢量A构成超递增数列的情形。 5.2超递增序列 定义1正整数序列 叫超递增序列，如果 这一定义对有限序列也适

31、用。通俗地说，每一项都大于它前面各项之和的正整数序列叫超递增序列。下面就是两个超 递增序列： ，。对于超递增序列A而言，如果给定了一个正整数a是很容易判断a是否能表示为A中的若 干个项之和的。比如序列A ，a=52。因为n>41，41必须被选中，否则其它各项全选也不 够41，从而更达不到52。然后算出5241：11。因为11恰大于A中的9，9必须被选中， 否则前面各项加起来也不到9，更达不到11。同理，算出119=2正好是A中的项，这样就 得到52=41+9+2。再如序列B，a=10000。如果a能表示为B中的若干项之和，那么 从a恰大于6907知6907是一个加项，然后算出100006

32、907=3093。3093恰大于B中的 1718，30391718=1375，1375863=512，512430=82。因为82不是B中的项，所以 a=10000不能表示为B中的若干项之和。 背包系统就是将超递增序列用于秘密地传递数字语言的一种密码系统。事实上，只要会 秘密地传送一个字母，也就会传送整个语言了。而由表1知一个字母可以看成一个5位的二进制数，比如i可看成01001。选取一个超递增序列把i也想成一个矢量 并作A与 的内积。基于超递增序列A就可以把i以数字22的形式发送给对方，对方收到数字22后，如果他 也知道这个超递增序列A，就很容易算出(0，1，0，0，1)这个序列从而可以恢复

33、出文字来。如果敌方截获了数字22，因为他不知道A，也就恢复不出i来。但以上所述不是真正的背包系统。在实用的背包系统中，序列A的长度 远远大于5，可以达到 100。同时序列A经过用数论方法进行变换后可将所得的非超递增序列B公诸与众，但控制一些秘钥仅为友方所知。5.3背包系统的加密和解密方法 用机器语言作加密对象，以传送两个英文字母为例进行说明。为了方便，不妨取i 。（字母i和空格） 加密方法 选取一个超递增序列比如A为前文中所给出的。以 记A中各项之和，则 =55205。取整数m使，比如取m =55207。再取整 数 t使且 与m互素，即1,比如取t=25236。用t乘A的各项后再 用m去除所得

34、各项，以C记所得余数依次构成的序列，即， 这里的等于t除以m所得的余数。经计算得 这个C可以公之于众，友方敌方都知道，但请注意C已经不是超递增序列了。 设为待传送的i (i和空格)，由表1知（二进制对应）。将 与C作内积得。这个77426就是密文，敌方截获了也很难从B和口算出，因为C已经不是超递增的了，正像想从一大堆积木块中找出恰好装满背包的那些积木块一样。当n=100时，如果不借助其它数学理论 ，用计算机去试探性地破译背包系统得花上30年的时间 ! 解密方法 友方在收到信息 后是容易基于C而恢复出来的，因为t与m这两个密钥是 通知了友方的。利用t和m，根据公式，可以很快算出u=1061。有了

35、u “就可以从C中恢复出超递增序列A来，用u去乘C的各项再摸去若干个m记得A。下面以C的第一项4579为例，因为所以A的第一项是103。同理可以求得A的其他各项。现在我们知道了A还有t与m就可以算出非递增序列C，然后进而求出，这些只要对加密方法进行逆运算就可以很快得到。再把机器语言，翻译出来即可。 注1：NP完全问题，是世界七大数学难题之一。 NP的英文全称是Non-deterministic Polynomial的问题，即多项式复杂程度的非确定性问题。简单的写法是 NP=P？，问题就在这个问号上，到底是NP等于P，还是NP不等于P。NP就是Non-deterministic Polynomi

36、al的问题，也即是多项式复杂程度的非确定性问题。 有些计算问题是确定性的，比如加减乘除之类，你只要按照公式推导，按部就班一步步来，就可以得到结果。但是，有些问题是无法按部就班直接地计算出来。比如，找大质数的问题。有没有一个公式，你一套公式，就可以一步步推算出来，下一个质数应该是多少呢？这样的公式是没有的。再比如，大的合数分解质因数的问题，有没有一个公式，把合数代进去，就直接可以算出，它的因子各自是多少？也没有这样的公式。这种问题的答案，是无法直接计算得到的，只能通过间接的“猜算”来得到结果。这就是非确定性问题。而这些问题的通常有个算法，它不能直接告诉你答案是什么，但可以告诉你，某个可能的结果是正确的答案还是错误的。这个可以告诉你“猜算”的答案正确与否的算法，假如可以在多项式时间内算出来，就叫做多项式非确定性问题。而如果这个问题的所有可能答案，都是可以在多项式时间背包问题实际上是一个NP完全问题内进行正确与否的验算的话，就叫完全多项式非确定问题完全多项式非确定性问题可以用穷举法得到答案，一个个检验下去，最终便能得到结果。但是这样算法的复杂程度，是指数关系，因此计算的时间随问题的复杂程度成指数的增长，很快便变得不可计算了。6结束语在着手这篇论文的时候作者一直都是力求用最简单的文字向大家展示数论在密码学中的两方面应用。其中RSA算法是先摆理论后举事