中国剩余定理.pdf
《中国剩余定理.pdf》由会员分享,可在线阅读,更多相关《中国剩余定理.pdf(21页珍藏版)》请在咨信网上搜索。
1、本科毕业论文(设计)题目 中国剩余定理与RSA公钥体制学院数学与统计学院专业 数学与应用数学(师范)年级2009 级学号222009323012023姓名唐蓉指 导 教 师包小敏成绩2013 年 4 月 24 日中国剩余定理与RSA公钥体制唐蓉西南大学数学与统计学院,重庆400715摘要:本文从数论中的中国剩余定理出发,主要做了以下工作:第一,阐述了中国剩余定理的由来。本文从中国剩余定理的历史起源来理解该定理及其证明方法,并讨论和分析该定理的思想和原则。另外讨论了中国剩余定理在计算机大数计算方面的应用。第二,在密码学方面,本文讨论了基于中国剩余定理的一种快速公钥加密算法,并针对该算法进一步分析
2、其原理,过程和性能。关键词:密码学;中国剩余定理;大数计算;RSA公钥体制Chinese Remainder Theorem and RSA Public KeySystemTang RongSchool of Mathematics&Statistics,Southwest University,Chongqing 400715Abstract:Based on the Chinese remainder theorem in number theory,this papermainly do the following:First,this paper expounds the origi
3、n of the Chinese remainder theorem.Thisarticle from the historical origin of the Chinese remainder theorem to understandthis theorem and its proof method,and discuss and analyze the ideas and princi-ples of the theorem.In addition this paper also discussed the Chinese remaindertheorem in computer ap
4、plication of big numbers.Second,from the perspective of cryptography,a fast public-key encryption al-gorithm based on Chinese remainder theorem is discussed in this paper and itsprinciple,process and performance is analyzed.Key words:cryptography;Chinese remainder theorem;big number calcula-tion;RSA
5、 public key system第 1 页 共 14 页1.中国剩余定理的由来1.1孙子问题中国剩余定理起源于我国南北朝时期的数学著作 孙子算经,因此又名为孙子剩余定理,古有“韩信点兵”、“鬼谷算”、“求一术”、“隔墙算”、“剪管术”、“秦王暗点兵”、“物不知数”、“孙子定理”之名,是数论中主要命题,在计算机以及日常生活领域都有广泛应用。首先,引述 孙子算经1中“物不知数”的原文为:今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何?答曰:二十三术曰:三三数之剩二,置一百四十;五五数之剩三,置六十三;七七数之剩三,置三十。并之得二百三十三。以二百一十减之,即得。凡三三数之剩
6、一,则置七十,五五数之剩一,则置二十一,七七数之剩一,则置十五。一百六以上,以一百五减之,即得。这就是求解一次同余式组:x 2 mod 3(1)x 3 mod 5(2)x 2 mod 7(3)孙子算经简要给出了该问题的解法和答案,首先将该问题用算式求解即可表示即为:70 2+21 3+15 2 105 2=23鉴于孙子算经对于这类问题的讨论存在没有总结成文以及推及到一般的缺陷,因此也并没有达到理论的高度。秦九韶在1247年完成的数书九章中推广了“孙子定理”形成“中国剩余定理”。在 数书九章2中,秦九韶提出系统的叙述了“大衍求一术”,来归纳求解一次同余组的计算步骤,并提出了乘率、定数、衍母和衍数
7、等一系列数学概念。到此,“物不知数”所引出的一次同余式组问题,才真正得到了一般的解法,上升到中国剩余定理的高度。明代程大位所编撰的 算法统宗3用歌谣的形式给出了物不知数问题的解:三人同行七十稀,五树梅花廿一枝。七子团圆正半月,除百零五便得知。该歌谣中的“七十稀”、“廿一枝”和“正半月”,就是暗指70、21和15这三个重要数字。中国剩余定理的解法以歌谣的存在形势更加便于记诵,使得该解法也更为普及,甚而远渡重洋,流传到日本。但是以上解法都没有说明这三个数的缘由。下面介绍同余解法和不定方程解法来说明这三个数字的来历。首先,可以将孙子问题的解法分三步:(1)找出这样三个数,15(从3和5的公倍数中找出
8、被7除余1的最小数),21(从3和7的公倍数中找出被5除余1 的最小数),70(从5和7的公倍数中找出被3除余1的最小数)。第 2 页 共 14 页(2)用15乘以2(2为所求数除以7的余数),用21乘以3(3为所求数除以5的余数),用70乘以2(2为所求数除以3的余数),然后把三个式子的乘积相加,就可以得到15 2+21 3+70 2=233。(3)再用233除以3、5、7三个数的最小公倍数105,得余数23,则这个余数就是符合条件的最小数。我们将这种求解的方法称为同余算法,这种算法的依据如下。首先,假设k1满足除以3余2,k2满足除以5余3,k3满足除以7余2。从k1出发,y 由于k1满足
9、除以3余2,依据定理“如果a/b=c,则有(a+kb)/b=c(k为非零整数),即如果一个出发运算的余数为c,那么被除数与n倍的除数相加(减)的和(差)再余除数相除,余数不改变”,可以使得k1+k2的和仍然满足除3余2,同理,可以使得k1+k2+k3的和仍然满足除3余2,对于k2,k3有类似推导。综上可以得出:(1)k2和k3是3的倍数,则k1+k2+k3的和满足除3余2;(2)k1和k3是5的倍数,则k1+k2+k3的和满足除5余3;(3)k1和k2是7的倍数,则k1+k2+k3的和满足除7余2;所以为了使得k1+k2+k3的和为所求解,只要满足:(1)k1除3余2,且是5和7的公倍数;(2
10、)k2除5余3,且是3和7的公倍数;(3)k3除7余2,且是3和5的倍数。因此,问题可以归结为从5和7的公倍数中找到一个数使得其除3余2的数,极为k1;从3和7的公倍数中再找出一个数使得其除以5余3,记为k2;最后从3和5的公倍数中找一个数使得其除7余2,记为k3。最后再把三个数相加就是所求数,尽管这时还不是最小解。在求解k1,k2,k3时,以求解k1为例,并不是直接从5和7的公倍数中直接找除3余2的数,而是先找到除3余1的数,再乘2。1.2不定方程解法设所求数为w,w被3、5、7除所得的余数分别为x、y、z 则有:w=3x+2(4)w=5y+3(5)w=7z+2(6)消去w,得到3x 5y=
11、1(7)3x=7z(8)第 3 页 共 14 页由(5)式得x=7z/3,令z=3k,k N,得x=7k 从而有y=(21k 1)/5=4+(k 1)/5再令(k 1)/5=t1,t1 N,则k=5t1+1,所以x=35t1+7(9)y=t1+4(10)z=15t1+3(11)w=105t1+23(12)得到孙子问题的通解,显然当t1=0时,最小整数解为w=23。1.3中国剩余定理的发展在中国数学史上,还流传着一个关于孙子问题的“韩信点兵”的故事:韩信乃是汉高祖刘邦手下的一员文武兼备的猛将,为大汉朝的开创立下了卓绝功劳。据说韩信十分擅长于数学,因此他在点兵的时候,为了保住军事机密以免让敌人知道
12、他手下的兵力,往往先让士兵从1至3报数,然后记下最后一个士兵所报之数;再从1至5报数,也记下最后一个士兵所报之数;最后从1至7报数,又记下最后一个士兵所报之数;通过这样韩信自己很快就算出了他的士兵人数,但是敌人则始终无法清楚他所在部队究竟士兵有多少。孙子算经 对这类问题的研究只是初具雏形,远远谈不上完整,其不足之处在于:(1)未把解法总结成文,使得后人研究多凭猜测;(2)模数仅限于两两互质的正整数,没涉及一般情况;(3)没能进一步探究同余组有解的条件等理论问题。因此,后人把这一命题及其解法称为“孙子定理”主要是推崇孙子算经在同余问题的处理上时间领先,其实想方法还并不成熟。为解决“孙子问题”对于
13、此类问题讨论的不足,秦九韶从孙子定理中推广其求解过程形成了中国剩余定理。秦九韶为南宋时期人,酷爱数学,经过长期积累和细心钻研,于公元1247年完成 数书九章。这部中世纪的数学著作,在许多方面都作出了贡献,其中最具代表性的是提出了求解一次同余组的“大衍求一术”和求高次方程数值解的“正负开方术”,并详细的叙述了“大衍求一术”的完整过程。到此,由 孙子算经 题开创的一次同余式问题,才真正得到了一个一般的解法,上升到了中国剩余定理的高度。但是欧洲最早出现一次同余式组问题,是和秦九韶同时期的裴波那契(意大利,11701250)4。裴波那契在 算法之书 中提出了两个一次同余问题,但均没有一般的解法。这两个
14、问题从形式到内容都和“物不知数”问题类似,但整体水平却并没有超越孙子算经。直到1801年,数学王子高斯(德国,17771855)对一次同余式组的解法进行研究,并且在 算术探究 上发表与秦九韶的“大衍求一术”的相同第 4 页 共 14 页定理,并对模两两互质的情况给出严格的证明。对比孙子定理和高斯定理可以得出:高斯定理实质就是孙子定理的推广。但此时,高斯定理已比孙子定理晚了一千五百多年。因此,秦九韶和他的“大衍求一术”在中国乃至世界数学史上都一直占有毋庸置疑的重要地位。感叹于中国古代数学家对一次同余组求解理论较早的研究成果,在西方的数学史上,一致公正地命名求解一次同余式组问题的理论为“中国剩余定
15、理”(Chinese RemainderTheorem)。1.4中国剩余定理的证明中国剩余定理是初等数论的重要基本定理之一,其主要是刻画剩余系的结构和求解形如x dimod pi(1 i s)的一次同余式方程组5。定理 1(中国剩余定理).设m1,m2,m3,mk为两两互质的正整数,a1,a2,a3,ar是整数,则同余方程组x ai(modmi),i=1,2,3,r模M=m1,m2,m3,mk有惟一解x=rXi=1aiMiyimod M其中Mi=M mi,i=1,2,3,r。证明.下面我们来证明这个定理。因为(Mi,mi)=1,因此用辗转相除法求出M0i与yi,使得MiM0i+yimi=1,即
16、M0i满足MiM0i 1(modmi),MiM0i 0 mod mi,1 j i,i 6=j;则x0 aiMiM0i ai(modmi),1 j i,若x也使同余方程组成立,则x x0(modmi),1 j i,因此x x0(modm1,m2,m3,mr)。又已知(mi,mj)=1,m1,m2,m3,mr=m,这就证明了x0 x0mod m1.5大整数计算机算术在计算机技术方面,中国剩余定理提供了大数计算的方法。假定m1,m2,mn为两两互质且大于或等于2的整数,令M 为它们的乘积。由中国剩余定理可知每个整数a,0 a m,均可以唯一的表示为n元组。这个n元组由a除以mi的余数组成,也就是说a
17、可以唯一地表示为(a mod m1,a mod m2,a mod mn)这样大整数算术运算就可以在表示这些整数的n元数组的分量上来完成,每个分量都是用大整数除以mi的余数,若计算出的大整数运算结果用n元组表示,就可以求解出这n个同余方程找出结果。通过以上数学过程,在计算机的大数运算中利用数论中的中国剩余定理有以下两个优势:(1)可以用该方法完成一台计算机上不能完成的大整数算术;(2)对不同的模数的计算可以并列操作,加快计算速度。第 5 页 共 14 页例如,假定在某台计算机上做100以内的整数运算比100以上的整数运算快得多,那么只需要将整数表示为模两两互素的100以内的整数的余数的多元组,这
18、样就可以将很多整数计算限制在100以内的整数上6。例如,可以用99,98,97和95为模数。由中国剩余定理,所有小于99 98 97 95=89403930的非负整数均可唯一地用该整数除以这四个模的余数表示。例如把123684表示为(33,8,9,89),因为123684 mod 99=33,123684mod98=8,123684 mod 97=9及123684 mod 95=89。类似的,我们可以将413456表示为(32,92,42,16)。要求得123684和413456的和,只要把四元组的对应分量相加,再按相应的模减小各分量。这样可得(33,8,9,89)+(32,92,42,16)
19、=(65 mod 99,100 mod 98,51 mod 97,105 mod 95)=(65,2,51,10)因而,为求123684和413456的和,即求(65,2,51,10)表示的整数,只要求解同余方程组x65 mod 99x2 mod 98x51 mod 97x10 mod 95利用中国剩余定理解法,可以得65 98 9795+2 99 97 95+51 99 98 95+10 99 98 97=3397886480 537140 mod 89403930因为0 x=y 89403930,所以所求和为537140。2.RSA体制2.1公钥密码算法人类一直以来都对信息安全都有着强烈的
20、兴趣。在如今的信息时代,伴随着社会的发展,对于信息安全的要求也越来越高。密码学的目的就是使得在不安全信道中通信的双方,能够以一种他们敌方不能理解的通信方式进行通信。这里的不安全信道是广泛存在的,例如计算机网络等媒介。几乎所有的传统密码以及部分的现代密码算法(如DES和AES)都是一种对称算法7,即解密密钥通常完全等于加密密钥。这种密码体制被成为对称密码体制,在应用过程中,如果一个网络中有n个用户相互之间都需要进行秘密通信,这时网络中就需要有n(n 1)/2个密钥,并且网络中的每个用户都需要保存(n 1)个密钥。对称密钥密码体制存在两方面的局限性。一方面,假若网络中的用户n是较大的一个数值,则就
21、需要分配n(n 1)/2个密钥,以及每个用户需要保存(n 1)个密钥,可见在n值较大的时候分配和管理密钥都是相当困难的。另一方面,第 6 页 共 14 页对称密钥密码体制需要在秘密通信的双方之间传输密文之前使用一个安全信道来交换密钥而不被窃取,这也是十分困难的。这就使得萌生了一种新的密码体制公开密钥密码体制(或称为非对称密钥密码体制),也即是使得需要保密通信的用户都有两个密钥:加密密钥和解密密钥,并且二者并不相同且没有本质关系8。另外,如果仅有加密密钥无法计算获得解密密钥,因此,允许加密和解密密钥其中之一是公开的,另一个保密,则可以有多个不同的人加密,但是只有一个人可以解密。以一种非数学的方式
22、来理解公开密钥算法,相当于要获取信息的B方给了A方一个未上锁的盒子,A将信息放入盒子,用公开密钥锁上盒子,然后传递给B,显然只有B可以打开盒子读取信息。公钥密钥密码体制的思想是在1976年由Diffie和Hellman发表在密码学的新方向一文中,为密码学的研究开创了全新领域,随后几年有许多应用被提出来,其中最著名的就是由Rivest,Shamir和Adleman于1977年提出,并以它的三个发明者的名字明明为RSA算法9。RSA算法符合对于公开密钥密码体制的要求,并且是目前应用最为广泛和成功的公开密钥密码算法。其实在此之前政府加密机构就已经发现并开始应用RSA算法,早在1970年James E
23、l-lis就发现了公开密钥密码体制,而RSA算法在Clifford Cocks在1973年写下的一份内部文件中已被详细描述。2.2RSA体制的数学背景RSA算法的安全性是基于把一个大整数分解是极困难的问题。该问题的完整表述可以为:选择两个不相同的大素数p和q 的乘积n,即n=pq,求解p与q 的值。这样一个大整数的分解为素数的计算是相当困难的,目前还不存在一般性的解决方法。倘若需要正确完整的了解RSA密码体制如何让工作,就需要用到一些数论的知识,以及两个重要的数学工具:欧拉(Euler)定理和中国剩余定理。以下介绍RSA体制的有关数学背景10。定义 1(欧拉函数).设n是一个正整数,小于n且与
24、n互素的正整数的个数成为n的欧拉函数,记为(n)。例 1.(6)=2,(8)=4,(7)=6。如果n是素数,则有(n)=n 1。定理 2(欧几里得算法).欧几里德算法又称辗转相除法,用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理:gcd函数就是用来求(a,b)的最大公约数的。gcd函数的基本性质:gcd(a,b)=gcd(b,a)=gcd(a,b)=gcd(|a|,|b|)RSA密码体制的加密和解密的过程互逆性主要基于欧拉定理。定理 3(欧拉定理).设n,a为正整数。若(a,n)=1,则a(n)1 mod n.第 7 页 共 14 页证明.设(a1,a2,a3,a(n)是模n的
25、一个简化剩余系,由于(a,n)=1,根据同余式的性质容易证明(aa1,aa2,a3,aa(n)也是模n的一个简化剩余系。因此,(n)Yi=1ai=kYi=1aaimod n此时a(n)1 mod n,证毕。特别的,当n为素数时,由欧拉定理可以得到费马小定理。推论 4(费尔马小定理).如果p是一个素数,且p不能够被a N整除,则ap1 1 mod p根据欧拉定理,同样可以证明以下定理,它将更加直接的给出关于RSA公钥体制中解密到加密过程逆的证明11。推论 5.设p和q 是两个不同的素数,n=p q,对任意的整数x(0 x n)及任意的非负整数k,有xk(n)+1 x mod n。证明.如果p-x
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 中国 剩余 定理
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【快乐****生活】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【快乐****生活】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。