中国剩余定理在密码学中的应用研究.doc
《中国剩余定理在密码学中的应用研究.doc》由会员分享，可在线阅读，更多相关《中国剩余定理在密码学中的应用研究.doc（88页珍藏版）》请在冰点文库上搜索。
分类号TP309密级公开
UDC学号20090713009
青海师范大学
硕士学位论文
中国剩余定理在密码学中的应用研究
研究生姓名刘媛
导师姓名张秉儒（教授）
申请学位类别硕士申请学位名称理学
学科专业名称基础数学研究方向名称代数组合与密码
论文提交日期2012年4月论文答辩日期2012年6月
学位授予单位学位授予日期
答辩委员会主席评阅人
III
V
青海师范大学学位论文独创性声明
本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。
尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得青海师范大学或其它教育机构的学位或证书而使用过的材料。
与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。
研究生签名：
日期：
青海师范大学学位论文使用授权声明
青海师范大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。
本人电子文档的内容和纸质论文的内容相一致。
除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布（包括刊登）论文的全部或部分内容。
论文的公布（包括刊登）授权由青海师范大学研究生部办理。
研究生签名：
导师签名：
日期
中国剩余定理在密码学中的应用研究
中文摘要
中国剩余定理是我国古代数学家为世界数学发展作出的巨大贡献，其数学思想在近代数学、当代密码学以及日常生活中都有着广泛的应用和影响。
在此基础上，本文主要做了一下的研究工作:
第一,详细论述了中国剩余定理在数字签名中的运用。
基于中国剩余定理的性质，在群签名方案中有很好的性质：
可以在不影响其他成员的签名私钥的情况下，实现高效的群成员的加入和撤销，只要设计得当，避免共模，就可以满足签名的安全性要求，如基本的匿名性、不可伪造性、抵抗联合攻击，并且在此基础上的各种改进方案还可以满足其他一些特性，如不可关联性等等。
第二，从计算复杂性的角度分析和证明了中国剩余定理在改进运算效率上的作用。
利用中国剩余定理的数学思想，把大整数模分解成为较小模数上的运算，在模指数运算效率的改进上，效果尤其显著。
而当下使用的几乎所有密码协议和密码程序，模幂运算都是主要的实现手段。
第三，将中国剩余定理引入其他密码协议的各个方面，在密钥分配、密钥恢复、信道编码、叛逆者追踪、数字防伪等领域做了探索性研究，从不同的侧面对密码协议方案的进行了优化。
关键词：
密码学；中国剩余定理；数字签名；安全性分析
ApplicationsofChinese Remainder Theorem
incryptography
Abstract
TheancientChinesepeopleandmathematiciansputforwardtheChineseRemainderTheorem,whichhasmadeatremendouscontributiontotheworldmathematics.TheCRTnotonlydeeplyinfluencedmodernmathematicsbutalsohadagreatmanyapplicationsincryptologyanddailylife.Onthiscase,thispaperdosomeresearchasfollowed:
Firstly,thispaperdeeplydiscussestheapplicationsofChineseRemainderTheoremindigitalsignature.Basedonthenatureofthistheorem,ithasmanygoodpropertiesingroupsignatureschemes.Somenewmumber’sjoin-inorhis/herleavingwhoseauthorityhasbeenrevokedwillnotaffectothermembers’privatekey.Thetwoprocessesaboveofcoursewillbeimplementedrapidly.Whileproperlydesigned,thecommonmodeattackswillbeavoidedandalltheseschemescanmeetalmostalltherequirementsofsecurityindigitalsignatures,saybasicanonymity,unforgeability,resistanceagainstjoint-attack.Wecanalsodosomefurtherimprovementindetailstomeetotherspecificproperties,sayunlinkabilityandsoon.
Secondly,intheperspectiveofcomputationalcomplexity,thispaperprovesandanalysestheroleoftheCRTinimprovingtheoperationalefficiency.WiththehelpoftheCRT,thelargeintegermodehasbeendecompositedintosmallermodulussothatthecalculationinmodularexponentiationhasbeenremarkblyspeedup,whichisthemaincoreofthecryptologyschemes.
finally,thispaperintroducestheCRTtoothercrytographicprotocolsanddosomereserchinkeydistribution,keyrecovery,channelcoding,traitortracing,digitalsecurity.Theauthorachievethegoalofoptimizingmanycrytographicprotocolsinvariousaspects.
Keywords:
cryptography;Chineseremaindertheorem;digitalsignature;securityanalysis
目录
第一章绪论 1
第一章中国剩余定理在密码学中的应用发展 3
1.1密码学发展概述 3
1.2中国剩余定理在密码学中的发展概述 5
第二章中国剩余定理 6
2.1同余理论基础 6
2.2Euclidean算法 9
2.3中国剩余定理与代数结构 10
2.3.1整环上的中国剩余定理 10
2.3.2多项式上的中国剩余定理 11
2.4素性判定和大数分解 12
2.5计算复杂性理论 14
第三章中国剩余定理与加密技术 16
3.1公钥密码体制 16
3.1.1RSA加密体制 16
3.1.2ElGamal加密体制 17
3.1.3椭圆曲线密码密码体制 19
3.2基于中国剩余定理的加密技术 23
3.2.1基于中国剩余定理的加密技术 23
3.2.2中国剩余定理结合矩阵的加密技术 24
3.3中国剩余定理与快速运算 27
3.3.1快速运算 28
3.3.2基于中国剩余定理的模幂乘法 29
3.3.3基于广义中国剩余定理的快速算法 30
3.4针对中国剩余定理上快速算法的攻击 32
3.4.1攻击类型 32
3.4.2抵御各种类型攻击的中国剩余定理上的快速算法 32
第四章中国剩余定理与数字签名 35
4.1中国剩余定理上的的数字签名综述 35
4.2数字签名 38
4.2.1数字签名的安全性要求 38
4.2.2数字签名的基本原理 39
4.2.3数字签名技术 39
4.2.4数字签名的现状和发展 40
4.3中国剩余定理应用于群签名 41
4.3.1典型的引入中国剩余定理的群签名方案 42
4.3.2基于中国剩余定理的群签名的性能分析 42
4.4针对中国剩余定理的群签名的攻击类型 44
4.4.1RSA的共模攻击 44
4.4.2抵御抗共模攻击 45
4.4.3群签名的不可关联 46
第五章中国剩余定理定理与密钥管理 48
5.1中国剩余定理定理应用于密钥管理 48
5.1.1数据库中密钥的灵活分配 48
5.1.2基于中国剩余定理的密钥分配方案 48
5.1.3方案的性能分析 50
5.2一个新的中国剩余定理上的密钥分配方案 51
5.3基于中国剩余定理的密钥恢复方案 52
5.3.1密钥恢复类型 52
5.3.2基于中国剩余定理的密钥恢复方案 52
5.3.3方案的性能评价 53
5.4基于中国剩余定理的等级密钥分配 53
5.5中国剩余定理应用于秘密共享组播密钥管理 56
第六章中国剩余定理应用与实际生活 59
6.1中国剩余定理应用于认证存取系统 59
6.2中国剩余定理应用于数字指纹技术 63
6.3中国剩余定理应用于组播安全 64
6.3.1组播及其安全性要求 64
6.3.2组播密钥管理 66
6.3.3组播的源认证 67
6.3.4基于中国剩余定理的叛逆者追踪技术组播方案-Lyuu 68
6.3.5笔者的基于中国剩余定理的叛逆追踪方案 70
结束语 71
参考文献 70
中国剩余定理在密码学中的应用研究
第一章绪论
在中国数学史上，广为流传着一个“韩信点兵”的故事：
为了保住军事机密，不让敌人知道自己部队的实力，韩信先让士兵从1至3报数，记下最后一个士兵所报之数；再令士兵从1至5报数，记下最后一个士兵所报之数；最后令士兵从1至7报数，记下最后一个士兵所报之数；这样，他很快就算出了自己部队士兵的总人数，而敌人却无法弄清他的部队究竟有多少名士兵。
韩信点兵的计算方法，就是现在被称为“中国剩余定理”的一次同余式解法。
它是中国古代数学的一项重大创造，在世界数学史上具有重要的地位。
最早提出并记叙这个数学问题的，是南北朝时期的数学著作《孙子算经》[参考文献
[]《孙子算经》约成书于四、五世纪，作者生平和编写年代不详
]中的“物不知数”题目：
“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何?
”并给出了这类一次同余式组的一般解。
明朝程大位编著的《算法统宗》[[]《新编直指算法统宗》.明代数学家程大位（1533-1606）著
]用歌谣给出了物不知数问题的解，增加了趣味性神秘性，也便于记诵：
三人同行七十稀，五树梅花二一枝。
七子团圆正半月，除百零五便得知。
物不知数题虽然开创了一次同余式研究的先河，但由于题目比较简单，试猜也能求得，没有上升到完整的计算程序和理论的高度。
完整的推广到一次同余方程组的一般计算程序，从理论上给出完整证明的，是南宋时期的数学家秦九韶（1202-1261）。
秦九韶在他的《数书九章》[[]《数书九章》.南宋数学家秦久韶著，1247（淳佑七年）
]中提出“大衍求一术”，系统地论述了一次同余式组解法。
直到此时，物不知数开创的一次同余式问题，才真正得到了一个普遍的解法，上升到了中国剩余定理的高度。
秦九韶在《数书九章》中采集了大量例题，如“古历会积”、“积尺寻源”、“推计土功”、“程行计地”等等，广泛应用大衍求一术来解决历法、工程、赋役和军旅等实际问题。
在这些实际问题中，模数并不总是两两互素的整数。
秦九韶区分了“元数”“收数”“通数”等不同情形，并且对每种情形给出了处理方法。
“大衍总术”把“收数”和“通数”化成“元数”的情形来计算，而对于元数不两两互素的情形，给出了可靠的程序，适当选取那些元数的因子作定数而把问题归结为两两互素的情形。
所有这些系统的理论，周密的考虑，即使以今天的眼光看来也很不简单，充分显示了秦九韶高超的数学水平和计算技巧。
中国剩余定理出现在公元四世纪的中国算书中并不是偶然的。
一次同余问题的研究，明显地受到天文、历法需要的推动，如三国魏施行的《景初历》、南北朝时期祖冲之的《大明历》中上元积年的计算，差不多相当于解十个同余式。
天文历法数据一般十分庞杂，所以，在魏晋南北朝时期，我国的天文历算家无疑已经能够求解比“物不知数”复杂得多的一次同余式，长期沿用孙子算法推算上元积年，必然会持续有更加深入的探讨。
到公元十三世纪，秦九韶集前法之大成，终于在一次同余式的研究上获得了超越前人的辉煌成果。
但是“大衍求一术”似乎没有为同时代的人所充分理解。
明中叶以后几乎失传。
一直到清代，“大衍求一术”又重新被发掘出来，引起了许多学者如张敦仁、李锐、骆腾凤、黄宗宪等的兴趣。
他们对“大衍求一术”进行了解释、改进和简化，其中黄宗宪《求一术通解》对模数非两两互素的情形给出了更加简明的方法，但是时代已是晚清。
在欧洲最早接触一次同余式的，是和秦九韶同时代的意大利数学家裴波那契（1170—1250），他在《算法之书》中给出了两个一次同余问题，但是没有一般的算法。
这两个问题从形式到数据都和物不知数题相仿，整体水平没有超过《孙子算经》。
直到十八、十九世纪，大数学家欧拉（1707—1783）于公元1743年、高斯（1777—1855）于公元1801年对一般一次同余式进行了详细研究，才重新获得和秦九韶“大衍求一术”相同的定理，并且对模数两两互素的情形给出了严格证明。
欧拉和高斯事先并不知道中国人的工作。
公元1852年英国传教士伟烈亚力（1815—1887）向欧洲介绍了物不知数问题和“大衍求一术”，引起欧洲学者的重视；1876年，德国马蒂生指出这一解法和高斯的解法一致；当时德国著名数学史家康托看到马蒂生的文章以后，高度评价了“大衍术”，并且称赞发现这一方法的中国数学家是“最幸运的天才”。
直到今天，“大衍求一术”仍然引起西方数学史家浓厚的研究兴趣。
如1973年，美国出版的一部数学史专著《十三世纪的中国数学》[[]UlrichLibbrecht.Chinesemathematicsinthethirteenthcentury[M].OverseaPublishingHouse,2006
]中，系统介绍了中国学者在一次同余论方面的成就，作者力勃雷希（比利时人）在评论秦九韶的贡献的时候说：
“秦九韶在不定分析方面的著作时代颇早，考虑到这一点，我们就会看到，萨顿称秦九韶为他那个民族、他那个时代、并且确实也是所有时代最伟大的数学家之一，是毫不夸张的。
”
中国古代数学家对一次同余论的研究有明显的独创性和继承性，“大衍求一术”在世界数学史上有着毋庸置疑的崇高地位。
也正因为此，西方数学史方面的著作中，一直公正地称求解一次同余式组的的剩余定理为“中国剩余定理”（Chinese Remainder Theorem）。
第一章中国剩余定理在密码学中的应用发展
1.1密码学发展概述
计算机网络技术已经渗透到我们日常生活的方方面面。
在网络给我们带来巨大经济效益和便利的同时，利用网络和系统漏洞的黑客也令人头痛不已。
如何有效的保障信息安全，已经成为影响全球经济安全、政治安全、国家安全的关键问题之一。
人们寄希望于密码技术，来实现信息安全、有效、高质量的服务于人类。
信息安全的五个要素包括信息的机密性（confidentiality）、信息的完整性（integrity）、目标可实现性（availability）、操作的可控性（controllability）与不可抵赖性（non-repudiation）。
信息安全就是要通过计算机技术、网络技术、密码技术和网络安全技术等保护网络信息在传输、交换和存储过程中的机密性、完整性、可用性、可控性和不可抵赖性。
密码学是信息安全的核心和基石。
密码学实际上包括密码编码学和密码分析学两个分支。
1949年ClaudeShannon发表了题为《CommunicationTheoryofSecrecySystem》的论文，标志着现代密码学的诞生，1972年美国国家标准局拟定了一个旨在保护计算机和通信数据的计划，由IBM在70年代初开发，经过NSA的修改以及一年多的公开评论之后，DES被定为美国联邦标准，授权在非密级的政府通信中使用。
军事上秘密使用多年的密码学开始走进寻常百姓家。
1977年至今，DES已经发展了数千个变体，好多密码分析并未对DES的安全性产生实际影响。
1997年又开始了DES的替代者——高级加密标准AES的遴选工作。
DES属于对称密码系统，也称为通用加密算法。
这种算法的特点是简单高效、易于硬件实现，安全性基于密钥的保密以及密钥空间的大小。
但是传送和保管密钥在现实中是个难题。
随着对称密码使用年数的增加，人们不断地修改密钥的长度，来加强方案的安全性能。
虽然改进后的对称密码体系仍然被认为是安全的，但是相关学者还是在不断地探索新的途径。
1976年公钥密码体制的提出使得密码学发生了一场变革，在密码学的发展历史上具有里程碑式的重要意义。
大量的公钥体制被提出，但有些已经被证明是不安全的方案。
剩下的一些被证明安全或者认为安全的算法，有的为了保证安全性，不得不将密钥的长度保证在某个比特位之上，这时的密钥往往因为太大，密文远远长于明文等问题而缺乏实用性。
仅存的为数不多的算法中，有些适用于密钥分配，有些仅适用于签名，有些仅仅适用于加密，到目前为止，能够很好的同时用于加密和签名的算法有RSA，ElGamal和Rabin。
但是他们的计算速度远远低于通用加密算法。
那么采用对称密钥加密消息，用公钥算法加密会话密钥，兼顾了效率与安全性，是当下密码工作者通常采用的折中体制。
数字签名是实现数据完整性和抗否认性的重要手段，随着计算机应用在社会生活中的普及，人们希望不同的签名方式满足不同的应用背景，于是群签名思想应运而生。
目前群签名方案多事基于密码学上的一些非对称算法，而这些非对称算法的安全性是基于数学难题，例如离散对数难题、大数分解难题等。
群签名首先由Chaum和VanHeyst在1991年提出[[]ChaumDandVanHeystE.Groupsignatures[A].ProcofEUTOCRYPT’91[C].LectureNotesinComputerScience,Berlin:
Springer-verlag,1991:
257~265
]，在一个群签名方案中，任意群成员都可以代表群体对消息匿名的进行签名。
在有争议的时候可以由群管理员打开签名，确定签名人的身份。
由于群签名在电子投票、电子商务等实际问题中具有广泛的应用，因此引起许多研究者的注意。
LChen和TPedesen提出了几个新的群签名方案，并回答了文献60中的一些公开问题，同时首次提出了允许在一个群体中增加新成员的群签名方案[[]ChenL,PedersenT.Newgroupsignatureschemes[A].Proc.ofEUROCRYPT’94[C].LectureNotesinComputerScience.1995,950:
171~181
]。
一个群签名应该满足的基本安全性包括：
（1）匿名性，即同一个群中的成员不能识别其他群成员的签名；
（2）不相关性：
判断两个不同的签名是否来自同一个成员，在计算上是不可行的；（3）不可伪造性：
任意多个成员都不能伪造其他成员的群签名。
1997年JCamenish和MStadler首次提出了适用于大的群体的群签名方案，从那以后，人们提出了各种各样的群签名方案，这些研究主要考虑的是安全性和效率。
1998年Lee和Chang提出了一种高效的基于离散对数问题的群签名方案，还有其他的一些基于DLP的群签名方案也被陆续提出[[]LeeWB,ChangCC.EfficientGroupSignatureSchemeBasedontheDiscreteLogarithm[J].IEEProcComputeDigitTech,1998,145
（1）:
15~18
[]徐光宝,张建中.一种基于离散对数的群签名方案[J].计算机工程,2005,31（9）:
143~144
]。
Tseng和Jan指出Lee-Chang方案不具备不可关联性，由于每个成员的不同群签名包含有自己的身份证书信息，一旦某个签名泄露，这个签名成员以前的签名和以后他的合法签名都会被泄露，使得该成员的签名不满足匿名性[[]TengYM,JanJK.Improvedgroupsignatureschemebasedonthediscretelogrithmproblem[J].ElectronicsLetters,1999,35
（1）:
37~38
]。
防止联合攻击和成员的撤销是群签名领域的两个重要问题[[]AtenieseGandTsudikG.Someopenissuesandnewdirectionsingroupsignature[A].FinancialCryptography1999,Berlin:
Springer-Verlag,1999:
196~211
]。
近年来提出了许多在联合攻击下安全的群签名方案[[]AtenieseG,CamenishJ,JoyeM,TsudikG.APracticalandprovablysecurecoalition-resistantgroupsignaturescheme[A].Crypt’2000[C],Berlin:
Springer-Verlag,2000,1880:
255~270
]，方案[[]CamenishJandStadlerM.Efficientgroupsignaturesforlargegroups[A].Proc.ofCRYPTO’97[C].LectureNotesinComputerScience,Berlin:
Springer-Verlag,1997,1296:
410~424
]已经被证明可以抵抗自适应联合攻击。
在效率方面也远远优于其他典型群签名方案。
然而在成员撤销问题上许多安全的群签名都没有很好的实现安全高效的成员撤
升级会员 