信息安全数学基础——算法、应用与实践（第2版）

本书包括初等数论、抽象代数、椭圆曲线论等方面的内容，该书选材合理、难度适中、层次分明、内容系统。书中以大量例题深入浅出地阐述信息安全数学基础各分支的基本概念、基本理论与基本方法。注重将抽象的理论与算法和实践相结合，并强调理论在信息安全特别是密码学中的具体应用实例。本书语言通俗易懂，容易自学。
本书可作为高等院校信息安全、网络空间安全、计算机科学与技术、密码学、通信工程、信息对抗、电子工程等领域的研究生和本科生相关课程的教科书，也可作为这些领域的教学、科研和工程技术人员的参考书。

 

本书介绍了信息安全数学的基础内容,包括初等数论、抽象代数、椭圆曲线论等，全书选材合理、难度适中、层次分明、内容系统,书中以大量例题深入浅出地阐述信息安全数学基础各分支的基本概念、基本理论与基本方法,注重将抽象的理论与算法和实践相结合，并强调理论在信息安全特别是密码学中的具体应用实例。本书语言通俗易懂，容易自学。
本书可作为高等院校信息安全、网络空间安全、计算机科学与技术、密码学、通信工程、信息对抗、电子工程等领域的研究生和本科生相关课程的教材，也可作为这些领域的教学、科研和工程技术人员的参考书。

目录

第1章整除3
1.1整除的概念3
1.2Euclid算法6
1.3扩展的Euclid算法10
1.4算术基本定理15
思考题16

第2章同余18
2.1同余和剩余类18
2.2简化剩余系、欧拉定理与费马小定理20
2.3模运算和同余的应用24
2.3.1密码系统的基本概念模型24
2.3.2移位密码25
2.3.3Vigenere密码25
2.3.4Hill密码26
思考题26

第3章同余式28
3.1一次同余式28
3.1.1一次同余式的求解28
3.1.2一次同余式在仿射加密中的应用31
3.2中国剩余定理32
3.3同余式的应用35
3.3.1RSA公钥密码系统35
3.3.2CRT在RSA中的应用37
3.3.3模重复平方算法38信息安全数学基础——算法、应用与实践（第2版）目录思考题40

第4章二次同余式和平方剩余42
4.1二次同余式和平方剩余42
4.2Legendre符号及其计算方法45
4.3Rabin公钥密码系统51
思考题54

第5章原根与指数55
5.1原根和阶的概念55
5.2原根与阶的计算59
5.3DiffieHellman密钥协商63
5.4ElGamal公钥密码系统65
思考题67

第6章群69
6.1群的简介69
6.2子群、陪集、拉格朗日定理72
6.3正规子群、商群、同态76
6.4循环群79
6.5置换群83
6.5.1置换群的概念83
6.5.2置换群的应用86
思考题88

第7章环与域89
7.1环89
7.1.1环的概念89
7.1.2环同态、环同构94
7.1.3子环、理想95
7.1.4多项式环99
7.2域106
7.2.1素域、域的扩张106
7.2.2域上多项式110
7.2.3有限域112
7.3环和域在AES加密中的应用116
7.3.1AES的设计思想116
7.3.2AES中S盒的设计117
7.3.3AES中列变换的设计120
7.4环在NTRU密码体制中的应用123
思考题125

第8章素性检测126
8.1素数的一些性质126
8.2Fermat测试127
8.3SolovayStrassen测试128
8.4MillerRabin测试131
思考题132

高级篇

第9章椭圆曲线群135
9.1椭圆曲线群的概念135
9.2椭圆曲线群的构造136
9.3椭圆曲线密码141
9.3.1椭圆曲线上的DH密钥协商协议141
9.3.2ElGamal加密的椭圆曲线版本141
9.3.3椭圆曲线快速标量点乘算法142
思考题143

第10章大整数分解算法144
10.1Pollard Rho方法144
10.2Pollard p-1分解算法145
10.3随机平方法147
思考题148

第11章离散对数算法149
11.1小步大步算法149
11.2Pollard Rho算法150
11.3指数演算法152
11.4PohligHellman算法153
思考题155第12章其他高级应用156
12.1平方剩余在GM加密中的应用156
12.2CRT在秘密共享中的应用158
12.2.1秘密共享的概念158
12.2.2基于CRT的简单门限方案159
12.2.3AsmuthBloom秘密共享方案160
思考题162

参考文献163

网络空间安全重点规划丛书编审委员会顾问委员会主任： 沈昌祥（中国工程院院士）
特别顾问： 姚期智（美国国家科学院院士、美国人文及科学院院士、中国科学院院士、“图灵奖”获得者）
何德全（中国工程院院士）蔡吉人（中国工程院院士）
方滨兴（中国工程院院士）吴建平（中国工程院院士）
王小云（中国科学院院士）
主任： 封化民
副主任： 韩臻李建华张焕国冯登国
委员： （按姓氏拼音为序）
蔡晶晶曹珍富陈克非陈兴蜀杜瑞颖杜跃进
段海新范红高岭宫力谷大武何大可
侯整风胡爱群胡道元黄继武黄刘生荆继武
寇卫东来学嘉李晖刘建伟刘建亚马建峰
毛文波潘柱廷裴定一钱德沛秦玉海秦志光
卿斯汉仇保利任奎石文昌汪烈军王怀民
王劲松王军王丽娜王美琴王清贤王新梅
王育民吴晓平吴云坤徐明许进徐文渊
严明杨波杨庚杨义先俞能海张功萱
张红旗张宏莉张敏情张玉清郑东周福才
左英男
丛书策划： 张民21世纪是信息时代，信息已成为社会发展的重要战略资源，社会的信息化已成为当今世界发展的潮流和核心，而信息安全在信息社会中将扮演极为重要的角色，它会直接关系到国家安全、企业经营和人们的日常生活。 随着信息安全产业的快速发展，全球对信息安全人才的需求量不断增加，但我国目前信息安全人才极度匮乏，远远不能满足金融、商业、公安、军事和政府等部门的需求。要解决供需矛盾，必须加快信息安全人才的培养，以满足社会对信息安全人才的需求。为此，教育部继2001年批准在武汉大学开设信息安全本科专业之后，又批准了多所高等院校设立信息安全本科专业，而且许多高校和科研院所已设立了信息安全方向的具有硕士和博士学位授予权的学科点。
信息安全是计算机、通信、物理、数学等领域的交叉学科，对于这一新兴学科的培养模式和课程设置，各高校普遍缺乏经验，因此中国计算机学会教育专业委员会和清华大学出版社联合主办了“信息安全专业教育教学研讨会”等一系列研讨活动，并成立了“高等院校信息安全专业系列教材”编审委员会，由我国信息安全领域著名专家肖国镇教授担任编委会主任，指导“高等院校信息安全专业系列教材”的编写工作。编委会本着研究先行的指导原则，认真研讨国内外高等院校信息安全专业的教学体系和课程设置，进行了大量前瞻性的研究工作，而且这种研究工作将随着我国信息安全专业的发展不断深入。系列教材的作者都是既在本专业领域有深厚的学术造诣、又在教学第一线有丰富的教学经验的学者、专家。
该系列教材是我国第一套专门针对信息安全专业的教材，其特点是：
① 体系完整、结构合理、内容先进。
② 适应面广：能够满足信息安全、计算机、通信工程等相关专业对信息安全领域课程的教材要求。
③ 立体配套：除主教材外，还配有多媒体电子教案、习题与实验指导等。
④ 版本更新及时，紧跟科学技术的新发展。
在全力做好本版教材，满足学生用书的基础上，还经由专家的推荐和审定，遴选了一批国外信息安全领域优秀的教材加入到系列教材中，以进一步满足大家对外版书的需求。“高等院校信息安全专业系列教材”已于2006年年初正式列入普通高等教育“十一五”国家级教材规划。
2007年6月，教育部高等学校信息安全类专业教学指导委员会成立大会暨第一次会议在北京胜利召开。本次会议由教育部高等学校信息安全类专业教学指导委员会主任单位北京工业大学和北京电子科技学院主办，清华大学出版社协办。教育部高等学校信息安全类专业教学指导委员会的成立对我国信息安全专业的发展起到重要的指导和推动作用。2006年教育部给武汉大学下达了“信息安全专业指导性专业规范研制”的教学科研项目。2007年起该项目由教育部高等学校信息安全类专业教学指导委员会组织实施。在高教司和教指委的指导下，项目组团结一致，努力工作，克服困难，历时5年，制定出我国第一个信息安全专业指导性专业规范，于2012年年底通过经教育部高等教育司理工科教育处授权组织的专家组评审，并且已经得到武汉大学等许多高校的实际使用。2013年，新一届“教育部高等学校信息安全专业教学指导委员会”成立。经组织审查和研究决定，2014年以“教育部高等学校信息安全专业教学指导委员会”的名义正式发布《高等学校信息安全专业指导性专业规范》（由清华大学出版社正式出版）。
信息安全数学基础——算法、应用与实践（第2版）出版说明2015年6月，国务院学位委员会、教育部出台增设“网络空间安全”为一级学科的决定，将高校培养网络空间安全人才提到新的高度。2016年6月，中央网络安全和信息化领导小组办公室（下文简称中央网信办）、国家发展和改革委员会、教育部、科学技术部、工业和信息化部及人力资源和社会保障部六大部门联合发布《关于加强网络安全学科建设和人才培养的意见》（中网办发文[2016]4号）。为贯彻落实《关于加强网络安全学科建设和人才培养的意见》，进一步深化高等教育教学改革，促进网络安全学科专业建设和人才培养，促进网络空间安全相关核心课程和教材建设，在教育部高等学校信息安全专业教学指导委员会和中央网信办资助的网络空间安全教材建设课题组的指导下，启动了“网络空间安全重点规划丛书”的工作，由教育部高等学校信息安全专业教学指导委员会秘书长封化民校长担任编委会主任。本规划丛书基于“高等院校信息安全专业系列教材”坚实的工作基础和成果、阵容强大的编审委员会和优秀的作者队伍，目前已经有多本图书获得教育部和中央网信办等机构评选的“普通高等教育本科国家级规划教材”、“普通高等教育精品教材”、“中国大学出版社图书奖”和“国家网络安全优秀教材奖”等多个奖项。
“网络空间安全重点规划丛书”将根据《高等学校信息安全专业指导性专业规范》（及后续版本）和相关教材建设课题组的研究成果不断更新和扩展，进一步体现科学性、系统性和新颖性，及时反映教学改革和课程建设的新成果，并随着我国网络空间安全学科的发展不断完善，力争为我国网络空间安全相关学科专业的本科和研究生教材建设、学术出版与人才培养做出更大的贡献。
我们的Email地址是： [email protected]，联系人： 张民。

“网络空间安全重点规划丛书”编审委员会当前信息安全进入公众的视野，它不仅关系到国防军事等重大战略问题以及国计民生等新兴战略产业的发展，而且与每个人日常生活息息相关。目前，我国信息安全所面临的形势十分严峻，信息安全学科的发展已经刻不容缓，国家已经将信息安全学科升级为一级学科。
信息安全数学是信息安全学科的理论基础，其内容涉及面较广，如数论与有限域等在信息安全的重要基础课（如密码学）中有大量的应用。信息安全数学基础是信息安全专业一门重要的基础必修课程。此外，信息安全数学在计算机科学、信息与通信工程、网络工程、电子对抗等学科中也都有着重要的应用。
信息安全数学方面的书籍难以读懂，这在一定程度上阻碍了信息安全学科以及信息安全知识的普及。目前的大多数教材对抽象的数学知识介绍较多，虽然在一定程度上可以锻炼学生的抽象思维能力，但容易使学生对所学内容产生畏难情绪。另外，单纯的理论知识介绍会导致学生不清楚这些理论如何应用，从而对所学内容不能留下较深刻的印象。一些来自计算机科学、通信工程、网络工程等专业的学生虽然对信息安全方向感兴趣，但是因为信息安全数学知识的抽象和难以普及，导致无法将本专业与信息安全方向结合起来。
本书重点强调信息安全数学基础在信息安全中的应用，并通过实践（算法与编程）环节强化对理论的理解。减少了一些在信息安全中应用较少的非重点数学理论，注重从计算机科学（算法）角度介绍而不是从纯数学角度介绍。强调抽象知识的算法解释和形象化，便于读者自学和易于教学。
本书在写作过程中特别遵循了以下思路。
（1） 体例新颖活泼、语言通俗易懂、精心安排示例。注意到目前市场上“大话×××”“×××趣谈”“图解×××”等图书深受读者喜爱，本书在保证论述严谨性的情况下，语言尽量形象生动,文风尽量活泼，以激发学习者的兴趣。根据作者对“信息安全数学基础”这一课程多年的教学实践经验，给出一些较为独特的比喻，虽然有些比较浅显，但主要目的是让读者特别是初学者快速理解、印象深刻、阅读轻松。
（2） 内容编排独特、循序渐进、由浅入深。注重内容之间的联系和讲解先后次序。内容选取尽量考虑到重要性和必要性。注重给出一些浅显易懂的类比，便于读者建立所学知识与前后内容之间的联系。信息安全数学基础——算法、应用与实践（第2版）前言（3） 以应用为导向，理论联系实际。不单纯讲解数学基础，而是从应用需要的角度出发，着重讲解基础知识点和关键点，突出实用性和可操作性。注重对算法和实践能力的培养，书中重点介绍计算数论（算法数论）中的算法，鼓励读者自主实现这些算法来提高实践能力。
（4） 注重启发性和对创新能力的培养。通过在正文中设立“思考”环节，以提高启发性并激发读者思考。在内容组织中潜移默化地强调数学素养的培养，根据数学内容的需要，采用合情猜想、归纳法、演绎法、公理集合论方法等多种论述方法。
（5） 尝试和实践探索教育数学与数学教育。教育数学应该注重还原数学定理的发现过程，探索数学发现的规律，启发读者回味数学发现的内在动因。数学教育应该在培养抽象化推理能力的同时，提高对数学的直觉、形象化能力、想象力、触类旁通能力、知识的关联类比性以及对数学内在结构性的总结。
全书共分12章。第1章整除；第2章同余；第3章同余式；第4章二次同余式和平方剩余；第5章原根与指数；第6章群；第7章环与域；第8章素性检测；第9章椭圆曲线群；第10章大整数分解算法；第11章离散对数算法；第12章其他高级应用。其中，第9～12章为高级部分，高级部分与部分打星号的章节可选学。全书授课学时为40～64学时。
本书得到了湖北省高等学校教学研究项目的支持（2015146）和本科教学质量工程项目（2016039）的支持，在此表示感谢。感谢学生肖睿阳的辅助性工作。
由于编者水平和学识有限，书中难免存在不足之处，在此衷心恳请广大读者批评指正。联系方式是[email protected]。

编者2018年7月基础篇

第5章〓原根与指数〖MZ）〗〖HT#〗〖BG)W〗〖HT〗〖ST〗〖WT〗〖CSX〗〖CSD〗〖CSX〗〖WTBX〗〖HJ*5/9〗在研究了平方（二次）剩余之后，下面讨论n次剩余。讨论使得同余式an≡1 (mod m)成立的整数n。这里主要关心最小的正整数e，因为找到了e，则e的倍数均为上式的解。另外，由Euler定理可知，当(a，m)=1时，有aφ(m)≡1 (mod m)。于是，关心一个问题，就是这个最小的正整数e会不会就是φ(m)？什么情况下就是φ(m)？〖WT〗本章的重点是原根、阶及其计算方法；难点是DH密钥协商和ElGamal公钥密码系统。〖HJ〗〖KH*2D〗〖BG（〗〖BHDWG17mm，WK5mm，WK13mm，WKZQ0W〗〖SQ 3.5mm〗〖CSX%0，0，0，40〗〖ZZ（F〗〖HT2”,15.H〗〓〖HT〗〖ZZ）〗〖〗〖TPJ.TIF;S*2%〗〖SQ 5.5mm〗〖WT15.FZ〗〖STFZ〗5.1〖HT〗〖ST〗〖WT〗〖〗〖SQ 3.5mm〗〖ZZ（F〗〖HT2”H〗〖WTHZ〗〓〖KG-*2〗〓〖MZ(2H〗〖BP(〗5.1〓〖BP)〗原根和阶的概念〖MZ)〗〓〖KG-*2〗〓〖ZZ）〗〖CSX〗〖WT〗〖HT〗〖BG）W〗〓〓〖HJ*5/9〗〖HTH〗〖STHZ〗〖WTHZ〗定义5.1〖STBZ〗〖WTBX〗〖HTSS〗〓设m>1是整数，a是正整数，(a,m)=1，则使得ax≡1 (mod m)成立的最小正整数x叫作a模m的阶（order）。记为ordm(a)。〖HTH〗〖STHZ〗〖WTHZ〗例5.1〖STBZ〗〖WTBX〗〖HTSS〗〓设整数m=7，计算a=1，2，3，4，5，6的阶。〖HTH〗解答〖HTSS〗〓〖ZK(〗11≡1 (mod 7)；〓〓〓〓〖WB〗23≡1 (mod 7)；〓〓〓〓〖WB〗33≡1 (mod 7)；43≡(-3)3≡1 (mod 7)；〖DW〗53≡(-2)3≡1 (mod 7)；〖DW〗62≡(-1)2≡1 (mod 7)。〖ZK)〗计算结果见表5.1。〖KH*2D〗〖HT5”H〗〖STHZ〗〖WTHZ〗〖JZ〗表5.1〓例5.1计算结果〖HTSS〗〖STBZ〗〖WTBZ〗〖BG(!〗〖BHDFG2,WK8，K6，K6，K6，K6，K6，K6W〗〖HJ*3〗a〖〗1〖〗2〖〗3〖〗4〖〗5〖〗6〖BHD〗ordm(a)〖〗1〖〗3〖〗6〖〗3〖〗6〖〗2〖BHDFG1,WKW〗〖BG）W〗〖HT〗〖HJ〗〓〓〖WTBX〗容易看到，由于φ(m)=φ(7)=6，于是，ordm(a)中最大为6。〖HTH〗〖STHZ〗〖WTHZ〗定义5.2〖STBZ〗〖WTBX〗〖HTSS〗(原根,primitive root）〓如果ordm(a)=φ(m)，则a叫作m的原根。〖HTH〗〖STHZ〗〖WTHZ〗思考5.1〖STBZ〗〖WTBZ〗〖HTSS〗〓原根的英文可能初学者觉得很难理解，如果称为“生成元（generator）”可能更容易理解这个“本原（primitive）”的含义，即可以生成群中其他所有元素的“本原”元。〖WTBX〗容易看到例5.1中，因为3和5的阶为φ(7)，所以3和5为原根。〖HJ〗〖LM〗〓〓从生成元的角度更加容易理解，但需要群的概念。群(〖WTHZ〗Z〖WTBX〗/7〖WTHZ〗Z〖WTBX〗)中元素的个数为φ(7)=6，因为3和5的阶为φ(7)，故3和5可以生成群(〖WTHZ〗Z〖WTBX〗/7〖WTHZ〗Z〖WTBX〗)中的任意元素（即1～6）。〖BW（S（S1*2,,）〗〖BG（〗〖BHDWG7mm,WK150mmZQ0W〗〖TPz1a.TIF;Z-9mm,Z%〗〓[SQ*3/4][HT11.K]信息安全数学基础——算法、应用与实践（第2版）[HT][TPz1.tif;Z24*3,Z%]〖BG）W〗〖BW）〗〖BW（D（S1*2,-10mm,-10mm）MD2〗〖BG（〗〖BHDWG7mm,WK150mmYQ0W〗〖TPz1b.TIF;Y-9mm,Y%〗[SQ*3/4][HT11.K]第5章〓原根与指数[HT]〓[TPz1.tif;Y11*3,Y%]〖BG）W〗〖BW）〗〖BW（S（X1，-2*2,-2*2）MD2〗〖TP页码.TIF;Z1mm,Z,BP%〗〖BW）〗〖BW（D（X1,-2*2,-2*2）MD2〗〖TP页码.TIF;Y1mm,Y,BP%〗〖BW）〗〓〓下面首先考察3（图5.1）。〖FC(〗31≡3 (mod 7)〓〓32≡2 (mod 7)〓〓33≡6 (mod 7)34≡4 (mod 7)〓〓35≡5 (mod 7)〓〓36≡1 (mod 7)〖FC)〗〓〓容易看到这是一个循环群，3可以生成群中的元素1～6。〖TP5-1.TIF;S*2;Z1;Y1,BP#〗〖TS(2〗〖HT5″SS〗〖WTBZ〗〖STBZ〗〖JZ〗图5.1〓3作为生成元生成(〖WTHZ〗Z〖WTBZ〗/7〖WTHZ〗Z〖WTBZ〗)中所有元素〖HT7SS〗〖TS)〗再来考察5。〖FC(〗51≡5 (mod 7)〓〓52≡4 (mod 7)〓〓53≡6 (mod 7)54≡2 (mod 7)〓〓55≡3 (mod 7)〓〓56≡1 (mod 7)〖FC)〗〓〓除了3和5外，其他都不是原根，因为其阶均小于φ(7)，即无法生成“所有”元素，“回到原点”1的过程过快，导致只能生成群中的“部分”元素。考察2（图5.2）。21≡2 (mod 7)〓〓22≡4 (mod 7)〓〓23≡1 (mod 7)〖TP5-2.TIF;S*2;Z1;Y1,BP#〗〖TS(2〗〖HT5″SS〗〖WTBZ〗〖STBZ〗〖JZ〗图5.2〓2只能生成(Z/7Z)中3个元素〖HT7SS〗〖TS)〗〓〓容易看到，2无法生成3，5，6。看图5.1和图5.2，就容易理解为什么原根的阶为φ(m)了。下面看一个m不为素数的例子。〖HTH〗〖STHZ〗〖WTHZ〗例5.2〖STBZ〗〖WTBX〗〖HTSS〗〓设整数m=14，计算a=1,3,5，9,11,13的阶，指出其中的原根。〖HTH〗解答〖HTSS〗〓〖ZK(〗11≡1 (mod 14)〓〓〖WB〗33≡-1 (mod 14)〓〓〖WB〗53≡-1 (mod 14)93≡1 (mod 14)〖DW〗113≡1 (mod 14)〖DW〗132≡1 (mod 14)〖ZK)〗〖LM〗〓〓计算结果见表5.2。〖HJ〗〖KH*2〗〖HT5”H〗〖STHZ〗〖WTHZ〗〖JZ〗表5.2〓例5.2计算结果〖STBZ〗〖WTBZ〗〖HT5″SS〗〖BG(!BTXDF〗〖BHDFG1*3/4,WK8，K6，K6，K6，K6，K6，KW〗〖HJ*3〗a〖〗1〖〗3〖〗5〖〗9〖〗11〖〗13〖BHD〗ordm(a)〖〗1〖〗6〖〗6〖〗3〖〗3〖〗2〖BHDFG1,WKW〗〖BG）W〗〖HT〗〖HJ〗〖WTBX〗〓〓由于φ(14)=φ(2)·φ(7)=φ(7)=6，因此原根为3和5。下面的定理给出了计算阶的一个算法依据。〖HTH〗〖STHZ〗〖WTHZ〗定理5.1〖STBZ〗〖WTBX〗〖HTSS〗〓设m>1是整数，a为整数，（a,m）=1，则整数d使得ad≡1 (mod m)成立的充要条件是ordm(a)|d〓〓〖HTH〗证明〖HTSS〗〓先证明充分性。如果ordm(a)|d，则存在整数k，使得d=k·ordm(a)。因此，有ad =(aordm(a))k ≡1 (mod m)〓〓再证明必要性。如果ordm(a)|d不成立，则存在整数q,r使得d=ordm(a)·q r〓01是整数，a为整数，（a,m）=1，则ordm(a)|φ(m)。〖HTH〗证明〖HTSS〗〓根据Euler定理，有aφ(m)≡1 (mod m)〓〓由定理5.1，于是ordm(a)| φ(m)。〖JY〗■由推论5.1可知，可以从φ(m)中寻找ordm(a)。〖HTH〗〖STHZ〗〖WTHZ〗例5.3〖STBZ〗〖WTBX〗〖HTSS〗〓求整数5模17的阶ord17(5)。〖HTH〗解答〖HTSS〗〓因为φ(17)=16，只需要对16的因数d=1,2,4,8,16计算5d (mod 17)，看是否等于1。因为〖FC(〗51≡5 (mod 17)52≡8 (mod 17)54≡64≡13≡-4 (mod 17)58≡(-4)2≡16≡-1 (mod 17)516≡(-1)2≡1 (mod 17)〖FC)〗所以5是模17的原根。有了原根的概念后，可以给出指数（index）的概念。〖HTH〗〖STHZ〗〖WTHZ〗定义5.3〖STBZ〗〖WTBX〗〖HTSS〗〓设g是正整数m的原根，若gcd(a,m)=1，则称同余式gx≡a (mod m)的唯一整数解x（1≤x≤φ(m)）为a模m以g为底的指数，也称为指标或离散对数，记为Indg,m(a)，或简记为Indga。〖ZW(〗有些书籍在英译方面把ord译为“指数”，而用“指标”表示离散对数。本书倾向于ord译为“阶”的缩写，“指数”和“指标”与离散对数等同，缩写为ind。〖HJ〗〖ZW)〗离散对数问题是一个计算上困难的问题，目前还没有找到有效的算法。5.3节和5.4节会给出基于该困难问题构造密码系统。第11章会讲解离散对数算法。〖HTH〗〖STHZ〗〖WTHZ〗例5.4〖STBZ〗〖WTBX〗〖HTSS〗〓设m=7，由例5.1知，3为原根。计算指数表。〖HTH〗解答〖HTSS〗〓计算指数表见表5.3。〖KH*2D〗〖HT5”H〗〖STHZ〗〖WTHZ〗〖JZ〗表5.3〓例5.4计算结果〖HTSS〗〖STBZ〗〖WTBZ〗〖BG(!〗〖BHDFG2,WK8，K6，K6，K6，K6，K6，KW〗〖HJ*3〗a〖〗1〖〗2〖〗3〖〗4〖〗5〖〗6〖BHD〗Ind3a〖〗6〖〗2〖〗1〖〗4〖〗5〖〗3〖BHDFG1,WKW〗〖BG）W〗〖HT〗〖HJ〗〓〓〖HTH〗〖STHZ〗〖WTHZ〗思考5.2〖STBZ〗〖WTBX〗〖HTSS〗〓“阶”和“指数”的主要区别是什么?容易看到，阶与模m和整数a有关，指数则与模m，整数a及底（原根g）有关。阶可以用来判断原根，指数主要用来计算元素相对于原根的离散对数。〖HTH〗〖STHZ〗〖WTHZ〗定理5.2〖STBZ〗〖WTBX〗〖HTSS〗（指数定理）〓若g是模m的一个原根，则gx≡gy (mod m)当且仅当x≡y (mod φ(m))。〖HTH〗证明〖HTSS〗〓假设x≡y (mod φ(m))，则x=y kφ(m)，k∈〖WTHZ〗Z〖WTBX〗，所以〖FC(〗gx〖〗≡gy kφ(m) (mod m)〖〗≡gy（gφ(m)）k (mod m)〖〗≡gy1k (mod m)〖〗≡gy (mod m)〖FC)〗〓〓必要性留作练习。〖JY〗■〖WT〗这个证明和RSA的解密过程有相似之处。〖HTH〗〖STHZ〗〖WTHZ〗定理5.3〖STBZ〗〖WTBX〗〖HTSS〗〓设g是模素数p的一个原根，且gcd(a,p)=1，则gk≡a (mod p)当且仅当k≡indga (mod p-1)〓〓〖HTH〗〖STHZ〗〖WTHZ〗定理5.4〖STBZ〗〖WTBX〗〖HTSS〗〓设m是有原根g的正整数，a与b是与m相互素的整数，则（1） 若b≡a (mod m)，则indgb≡indga  (mod φ(m))。（2） indg1≡0 (mod φ(m))。（3） indg(a·b)≡indga indgb (mod φ(m))。（4） indgak ≡k·indga (mod φ(m))，k是一个正整数。〖HTH〗〖STHZ〗〖WTHZ〗定义5.4〖STBZ〗〖WTBX〗〖HTSS〗〓设m是大于1的整数，a是与m互素的整数，如果n次同余式xn≡a (mod m)有解，则a叫作模m的n次剩余；否则，a称为模m的n次非剩余。〖HTH〗〖STHZ〗〖WTHZ〗定理5.5〖STBZ〗〖WTBX〗〖HTSS〗〓设m是大于1的整数，g是模m的原根，a是与m互素的整数，则同余式xn≡a (mod m)有解的充要条件是(n，φ(m))| indga且在有解的条件下，解数为(n，φ(m))。〖HTH〗证明〖HTSS〗〓由同余式xn≡a (mod m)和(a,m)=1，可得(x,m)=1，于是以g为底的x的对模m的指数存在，设为y，即x≡gy (mod m)，同余式可转化为gny≡a (mod m)〓〓由定理5.4知ny≡indga (mod φ(m))这是关于y的一次同余式，根据定理3.1，其有解的充要条件是(n，φ(m))| indga，且解数为(n，φ(m))。〖JY〗■〖HTH〗〖STHZ〗〖WTHZ〗例5.5〖STBZ〗〖WTBX〗〖HTSS〗〓求解同余式4x≡16 (mod 17)所有解。〖HTH〗解答〖HTSS〗〓两边取底为5模17的指数，得到ind5(4x)≡ind516≡8 (mod 16)即ind5(4x)≡x·ind54≡12x≡8 (mod 16)因此12x≡8 (mod 16)〓〓利用一次同余式的解法（定理3.1），因为(12,16)=4，因此12x≡8 (mod 16)有4个不同余的解，为x≡14，2，6，10 (mod 16)这即为同余式4x≡16 (mod 17)的所有解。〖KH*2D〗〖BG（〗〖BHDWG17mm，WK5mm，WK13mm，WKZQ0W〗〖SQ 3.5mm〗〖CSX%0，0，0，40〗〖ZZ（F〗〖HT2”,15.H〗〓〖HT〗〖ZZ）〗〖〗〖TPJ.TIF;S*2%〗〖SQ 5.5mm〗〖WT15.FZ〗〖STFZ〗5.2〖HT〗〖ST〗〖WT〗〖〗〖SQ 3.5mm〗〖ZZ（F〗〖HT2”H〗〖WTHZ〗〓〖KG-*2〗〓〖MZ(2H〗〖BP（〗5.2〓〖BP）〗原根与阶的计算〖MZ)〗〓〖KG-*2〗〓〖ZZ）〗〖CSX〗〖WT〗〖HT〗〖BG）W〗〓〓〖WTBX〗不是所有的模n都有原根，下面的定理给出存在原根的条件。〖HTH〗〖STHZ〗〖WTHZ〗定理5.6〖STBZ〗〖WTBX〗〖HTSS〗〓模m的原根存在的充要条件是m=2，4，pα，2pα，其中p是奇素数，α是一个正整数。定理的证明包括以下几项。(1) 每个素数都有原根。(2) 奇素数的幂都有原根。(3) 2的幂次中，只有2和4有原根。(4) 被两个或者更多素数整除的整数中，只有那些奇素数的幂次的2倍的整数才有原根。〖HTH〗〖STHZ〗〖WTHZ〗定理5.7〖STBZ〗〖WTBX〗〖HTSS〗〓设m>1，φ(m)的所有不同素因子是q1,q2,…,qk，则g是模m的一个原根的充要条件是gφ(m)/qi1 (mod m)〓i=1,…,k〓〓〖HTH〗证明〖HTSS〗〓先证明必要性。设g是模m的一个原根，则g模m的阶是φ(m)。但是01的整数，a为整数且（a,m）=1，d≥0为整数，则ad≡ak (mod m)的充要条件是d≡k (mod ordm(a))〓〓〖HTH〗证明〖HTSS〗〓根据Euclid除法，存在整数q,r和q′,r′有〖FC(〗d=ordm(a)q r〓0 ≤r1的整数，a为整数且（a,m）=1，d≥0为整数，则ordm(ad)=〖SX(〗ordm(a)〖〗(ordm(a),d)〖SX)〗〓〓〖HTH〗〖STHZ〗〖WTHZ〗思考5.3〖STBZ〗〖WTBX〗〖HTSS〗〓如何利用图5.1和图5.2给出一个对上述定理的直观解释。如图5.3所示,通俗地说，以原根3为度量，2≡32 (mod 7)，视为2“行走”1步相当于3“行走”2步，于是对于2而言，“行走”一周6步就需要6/2=3步，即ord7(2)=3。〖TP5-3.TIF;S*2;Z1;Y1,BP#〗〖TS(2〗〖HT5″SS〗〖WTBZ〗〖STBZ〗〖JZ〗图5.3〓帮助初学者理解定理的直观解释〖HT7SS〗〖TS)〗〖HTH〗〖STHZ〗〖WTHZ〗推论5.2〖STBZ〗〖WTBX〗〖HTSS〗〓设m>1是整数，g是模m的原根，d≥0为整数，则gd是模m的原根当且仅当(d,φ(m))=1。〖HTH〗〖STHZ〗〖WTHZ〗推论5.3〖STBZ〗〖WTBX〗〖HTSS〗〓设m>1是整数，m有φ(φ(m))个不同的原根。例如，设素数p=47，则存在φ(47-1)=22个模47的原根。目前还没有一种方法可以预知一个给定素数p的最小原根，对φ(p-1)个原根在模p的最小剩余系中的分布也知之甚少。定理5.9给出了从一个原根求其他原根的算法基础。〖HTH〗〖STHZ〗〖WTHZ〗例5.8〖STBZ〗〖WTBX〗〖HTSS〗〓已知5.9是41的原根，求41的所有原根。〖HTH〗解答〖HTSS〗〓由定理5.9知，(d，φ(41))=1时，ord41(gd)=ord41(g)，因此，当d遍历模φ(41)=40的简化剩余系，即〖JZ〗1,3,7,9,11,13,17,19,21,23,27,29,31,33,37,39共φ(φ(41))=16个数时，6d遍历41的所有原根,即〖JZ〗〖WT〗〖HL（4:1,Z;2,Z;3,Z;4,Z〗61≡6 (mod 41)〖〗63≡11 (mod 41)〖〗67≡29 (mod 41)〖〗69≡19 (mod 41)611≡28 (mod 41)〖〗613≡24 (mod 41)〖〗617≡26 (mod 41)〖〗619≡34 (mod 41)621≡35 (mod 41)〖〗623≡30 (mod 41)〖〗627≡12 (mod 41)〖〗629≡22 (mod 41)631≡13 (mod 41)〖〗633≡17 (mod 41)〖〗637≡15 (mod 41)〖〗639≡7 (mod 41)〖HL）〗综合定理5.7和定理5.9，构成了求原根的算法基础。〖WT〗〖KH*2D〗〖FK（。38ZQ*2〗〖SQ*2〗〓〖KG*4〗〖ZK(〗〖HTH〗〖STHZ〗〖WTHZ〗算法5.1〖HT〗〖ST〗〖WT〗〓原根算法, 输出给定素数的所有原根。输入: 素数模m以及m-1的素因子分解m-1=p1e1 p2e2…pkek。输出: m的所有原根。〖HT〗〖WT#〗〖HJ〗〖ZK）〗〖HJ0〗〖HJ〗〖FK)〗〖LM〗〖FK（。38ZQ*2〗〖SQ*2〗〓〖KG*4〗〖ZK(〗[ZK（][HT5”SS][WT《Courier New》][HJ4]GetPrimitiveRoot(){(1) 随机选择一个数a，2≤a≤m-〖KG-*3〗1(2) 对i从1到k执行以下计算:〓〓计算b←a(m-〖KG-*3〗1)/pi (mod m);〓〓如果b=〖KG-*3〗1则转到步骤(1);(3) 对d从1到m-〖KG-*2/5〗1，执行以下计算:〓〓若gcd(d, m-〖KG-*2/5〗1)=〖KG-*3〗1，则输出ad (mod m);}〖ZK）〗〖HT〗〖WT#〗〖HJ〗〖ZK）〗〖HJ0〗〖HJ〗〖FK)〗〖KH*2〗〖HTH〗〖STHZ〗〖WTHZ〗思考5.4〖HT〗〖ST〗〖WT〗〓根据定理5.9给出求阶表的算法。输入为素数模和原根，输出为阶表。〖KH*2D〗〖FK（。38ZQ*2〗〖SQ*2〗〓〖KG*4〗〖ZK(〗〖HTH〗〖STHZ〗〖WTHZ〗算法5.2〖HT〗〖ST〗〖WT〗〓输出阶表的算法。输入: 素数模m,原根a。输出: 阶表。〖KH2D][ZK（][HT5”SS][WT《Courier New》][HJ4]GetOrder(){对i从1到m-〖KG-*2/5〗1执行以下计算: 〓〓Return  ai (mod m), (m-〖KG-*2/5〗1)/gcd(m-〖KG-*2/5〗1,i);}〖ZK）〗〖HT〗〖WT#〗〖HJ〗〖ZK）〗〖HJ0〗〖HJ〗〖FK)〗〖KH*2〗〖HTH〗〖STHZ〗〖WTHZ〗定理5.10〖STBZ〗〖WTBX〗〖HTSS〗〓设m>1是整数，a为整数且(a,m)=1，则：（1） 设a-1使得a-1a≡1 (mod m)，则ordm(a-1)=ordm(a)。（2） 若b≡a (mod m)，则ordm(b)=ordm(a)。〖HTH〗证明〖HTSS〗〓（1） 因为(a-1)ordm(a)≡(aordm(a))-1 ≡1(mod m)因此，ordm(a-1)|ordm(a)。同理可证ordm(a)| ordm(a-1)，于是有ordm(a-1)=ordm(a)。（2） 若b≡a (mod m)，则bordm(a)≡aordm(a) ≡1(mod m)于是ordm(b)|ordm(a)。同理可证ordm(a)|ordm(b)，于是ordm(b)=ordm(a)。〖JY〗■该定理结论（1）也可以从图5.3中有直观地解释，3和5互为逆元，5相当于“反着走”了一圈（图5.4）。因为5“走”一步到5，5“走”两步到4，依此类推，5“走”6步到1。所以，5的阶为6。〖TP5-4.TIF;S*2;Z1;Y1,BP〗〖TS(2〗〖HT5″SS〗〖WTBZ〗〖STBZ〗〖JZ〗图5.4〓帮助初学者理解的对定理5.10的直观解释〖HT7SS〗〖TS)〗同理，2和4互为逆元。读者也可以画个类似的示意图。下面的定理将原根、阶以及简化剩余系等概念联系到一起。〖HTH〗〖STHZ〗〖WTHZ〗定理5.11〖STBZ〗〖WTBX〗〖HTSS〗〓设m>1是整数，a为整数且(a,m)=1，则1=a0，a1，…，aordm(a)-1模m两两不同余。特别地，当a是模m的原根，即ordm(a)=φ(m)时，这φ(m)个数组成模m的简化剩余系。〖HTH〗证明〖HTSS〗〓反证法。如果ordm(a)个数中有两个数模m同余，则存在整数0≤k,l≤ordm(a)使得ak≡al (mod m)不妨设k>l，则由(a,m)=1和定理2.4，得到ak-l≡1 (mod m)但是0≤k,l≤ordm(a)，这与ordm(a)的最小性矛盾。因此，原结论成立。当a为原根时，即ordm(a)=φ(m)时，共有φ(m)个数1=a0，a1，…，aφ(m)-1且模m两两不同余，由定理2.8知，这φ(m)个数组成模m的简化剩余系。〖JY〗■在下一章将看到，模m的简化剩余系构成一个乘法群，其生成元为a，a生成了该群中的所有元素。这个群其实还是一个循环群。〖WT〗〖KH*2D〗〖BG（〗〖BHDWG17mm，WK5mm，WK13mm，WKZQ0W〗〖SQ 3.5mm〗〖CSX%0，0，0，40〗〖ZZ（F〗〖HT2”,15.H〗〓〖HT〗〖ZZ）〗〖〗〖TPJ.TIF;S*2%〗〖SQ 5.5mm〗〖WT15.FZ〗〖STFZ〗5.3〖HT〗〖ST〗〖WT〗〖〗〖SQ 3.5mm〗〖ZZ（F〗〖HT2”H〗〖WTHZ〗〓〖KG-*2〗〓〖MZ(2H〗〖BP（〗5.3〓〖BP）〗DiffieHellman密钥协商〖MZ)〗〓〖KG-*2〗〓〖ZZ）〗〖CSX〗〖WT〗〖HT〗〖BG）W〗〓〓原根和指数，尤其是循环群的原根，在密码学中有重要的应用。例如，基于离散对数问题的DiffieHellman密钥协商协议，以及基于DH密钥协商协议的ElGamal公钥加密系统。问题的提出： 在定义2.7的注解中曾经指出对称密码中加密密钥和解密密钥是相同的，因此，对称密码的困难之处有以下两点。（1） 密钥的管理。对称加密中加密解密双方使用相同的密钥，因此每一对加密方和解密方就需要一个密钥。而且，密钥必须保密，因此对密钥的存储和管理难度增大。（2） 当加密方和解密方在不同地理位置时，通信双方如何确定一个秘密的密钥，或者是通信发送方如何将密钥传递给通信接收方，都不是很容易的事情。〖HTH〗〖STHZ〗〖WTHZ〗思考5.5〖STBZ〗〖WTBX〗〖HTSS〗〓对于共有n个通信方的两两通信，需要多少密钥？对称密码需要的密钥数量： 对单个个体而言，需要保存n-1个秘密密钥；对总体而言，需要保存n(n-1)/2个秘密密钥。定义3.2曾经指出，公钥密码使用公开的公钥进行加密和保密的私钥进行解密。需要的密钥数量： 对单个而言，需要保存n个公钥和一个私钥，对总体而言，需要保存n个公钥和n个私钥。所需密钥的数量减少，而且需要秘密保存的密钥数量大量减少。〖TP5-5.TIF;S*2;Z3;Y3,Y#〗〖TS(3〗〖HT5″SS〗〖WTBZ〗〖STBZ〗〖JZ〗图5.5〓〖WB〗离散对数问题的〖DW〗单向性示意图〖HT7SS〗〖TS)〗因此，需要解决的一个安全问题是： 在公开信道上如何协商一个秘密密钥，用于后续的对称密码加密通信。〖WT〗W.Diffie与M.Hellman利用离散对数问题的困难性，在1976年提出了DiffieHellman密钥协商协议。首先看离散对数问题中的某种单向性（图5.5）。〖WTBX〗设G是生成元为g的n阶循环群，则（1）  给定整数a，计算元素ga=y是容易的。（2）  给定G中元素y，计算整数x（1≤x≤n），使得gx=y 通常被认为是困难的（is believed to be hard）。“被认为是困难的”是指目前公认是困难的，也就是说，目前没有高效率（如多项式时间复杂性）的算法来解决这一问题，但没有人能够证明其就是困难的。下面给出一个较严格的定义（需要用到第6章中群的概念）。〖HTH〗〖STHZ〗〖WTHZ〗定义5.5〖STBZ〗〖WTBX〗〖HTSS〗〓乘法群〖WTHZ〗Z〖WTBX〗p上的离散对数问题（discrete logarithm problem，DLP）： 给定一个素数p，乘法群〖WTHZ〗Z〖WTBX〗p上的生成元g，以及〖WTHZ〗Z〖WTBX〗p上的随机选取的元素y，寻找整数x（2≤x≤p-2），使得y=gx mod p。这个整数x记为loggy，称为离散对数。易知，〖WTHZ〗Z〖WTBX〗p中元素的个数为p-1，即{1,2,…,p-1}。DiffieHellman密钥协商协议是2轮协议，即共有两个消息在信道中传递。每个通信方发送一个消息，并接收一个消息。协议的描述如下，如图5.6所示。〖TP5-6.TIF;S*2;Z1;Y1,BP#〗〖TS(2〗〖HT5″SS〗〖WTBZ〗〖STBZ〗〖JZ〗图5.6〓DiffieHellman密钥协商过程〖HT7SS〗〖TS)〗（1） A随机选择a∈［2,p-2］，计算Ya=ga mod p，将Ya发送给B。（2） B随机选择b∈［2,p-2］，计算Yb=gb mod p，将Yb发送给A。协议交互完成后，A方以Yba mod p为密钥，B方以Yab mod p为密钥。A方和B方之间的后续通信可以使用这个密钥进行加密。〖HTH〗〖STHZ〗〖WTHZ〗例5.9〖STBZ〗〖WTBX〗〖HTSS〗〓p=41是一个素数，(〖WTHZ〗Z〖WTBX〗/41〖WTHZ〗Z〖WTBX〗)是一个乘法循环群，生成元为6。实体A生成随机整数a=6，计算Ya=66 mod 41=39，将Ya 发送给B。实体B生成随机整数b=29，计算Yb=629 mod 41=22，将Yb 发送给A。A用自己的a和收到的Yb计算： 226 (mod 41)=21。B 用自己的b和收到的Ya计算： 3929 (mod 41)=21。协商后的秘密密钥是21。为了对这个例子有更直观的理解，图5.7给出一个使用计算机代数系统软件PARI作为演示。〖TP5-7.TIF;S*2;Z1;Y1,BP#〗〖TS(2〗〖HT5″SS〗〖WTBZ〗〖STBZ〗〖JZ〗图5.7〓对DiffieHellman密钥协商（例5.9）中计算过程的演示〖HT7SS〗〖TS)〗〖HTH〗〖STHZ〗〖WTHZ〗思考5.6〖STBZ〗〖WTBX〗〖HTSS〗〓为什么A方和B方可以公开地协商出一个秘密的密钥？