前言
信息安全不仅关系到国防、军事等重大战略问题以及国计民生等新兴战略产业的发展,而且与每个人的日常生活息息相关。目前,我国信息安全面临的形势十分严峻,信息安全学科的发展已经刻不容缓。
信息安全数学是信息安全学科的理论基础,其内容涉及面较广,例如,数论与有限域等在密码学等信息安全的重要基础课程中有大量的应用。信息安全数学基础是信息安全专业一门重要的基础必修课程。此外,信息安全数学在计算机科学、信息与通信工程、网络工程、电子对抗等学科中也都有着重要的应用。
信息安全数学方面的图书普遍难以读懂,这在一定程度上阻碍了信息安全学科以及信息安全知识的普及。偏重于抽象的数学知识,虽然一定程度上可以锻炼学生的抽象思维能力,但容易造成学生对所学内容的畏难情绪。另外,单纯的理论知识介绍会导致学生不清楚这些理论如何应用,从而对所学内容不能留下较深刻的印象。一些来自计算机科学、通信工程、网络工程等专业的学生虽然对信息安全方向感兴趣,但是信息安全数学知识的抽象导致这些学生无法将自己的专业与信息安全方向结合起来。
本书重点强调信息安全数学基础在信息安全中的应用,并通过实践(算法与编程)环节强化对理论的理解。减少了一些在信息安全中应用较少的非重点数学理论,注重从计算机科学(算法)角度介绍而不是从纯数学角度介绍,强调抽象知识的算法解释和形象化,便于读者自学,易于教学。
本书在写作过程中遵循了以下思路:
(1) 内容编排循序渐进、由浅入深。注重内容之间的联系和讲解的先后次序。内容选取充分考虑到重要性和必要性,注重类比,便于读者建立知识体系。
(2) 以应用为导向,理论联系实际。不单纯讲解数学基础,而是从应用的角度出发,着重讲解基础知识点和关键点,突出实用性和可操作性,注重对算法和实践能力的培养,重点介绍计算数论(算法数论)中的算法,鼓励读者自主实现这些算法以提高实践能力。
(3) 注重启发性和对创新能力的培养。通过“思考”环节提高启发性并激发读者思考。在内容组织中强调数学素养潜移默化的培养,根据数学内容的需要,采用合情猜想、归纳法、演绎法、公理集合论方法等多种论述方法。
(4) 探索和实践教育数学与数学教育。教育数学注重还原数学定理的发现过程,探索数学发现的规律,启发读者体验数学发现的内在动因。数学教育应该在培养抽象化推理能力的同时提高对数学的直觉、形象化思维能力、想象力、触类旁通能力、知识的关联类比能力以及对数学内在结构性的理解。
全书共13章,主要内容包括整除、同余、同余式、二次同余式、原根与阶、群、环与域、素性检测、椭圆曲线群、格及其算法、大整数分解算法、离散对数算法以及其他高级应用。其中,第11~13章为高级部分,这3章与加星号的章节可选学。使用本书授课可安排40~64学时。
本书面向的主要读者对象包括高等院校信息安全、计算机科学与技术等相关专业本科生、研究生以及从事信息安全技术研发、应用和管理的专业人员。
本书得到了中央高校教育教学改革基金(本科教学工程)以及本科教学质量工程教材建设类项目(ZL202047)的资助。同时,以下机构向作者提供了研究条件: 数据安全保护与智能治理教育部重点实验室(四川大学),项目号: SCU2023D008;计算科学与应用海南省重点实验室(海南师范大学),项目号: JSKX202302;CCF绿盟鲲鹏研究基金,项目号: CCFNSFOCUS2023009。学生肖睿阳为本书的编写做了辅助性工作。作者在此一并表示感谢。
限于作者水平,书中不足之处在所难免,恳请广大读者批评指正。
任伟2025年11月于武汉
目录
第1章整除1
1.1整除的概念1
1.2欧几里得算法3
1.3扩展的欧几里得算法8
1.4算术基本定理12
思考题14第2章同余15
2.1同余和剩余类15
2.2简化剩余系、欧拉定理与费马小定理17
2.3模运算和同余的应用21
2.3.1密码系统的基本概念模型21
2.3.2移位密码算法22
2.3.3维吉尼亚密码算法22
2.3.4希尔密码算法23
思考题23第3章同余式25
3.1一次同余式25
3.1.1一次同余式的求解方法25
3.1.2一次同余式在仿射加密中的应用28
3.2中国剩余定理及其算法29
3.3同余式的应用32
3.3.1RSA公钥密码系统32
3.3.2中国剩余定理在RSA中的应用34
3.3.3模重复平方算法35
思考题37第4章二次同余式39
4.1二次同余式和平方剩余394.2勒让德符号及其计算方法42
4.3Rabin公钥密码系统49
思考题52第5章原根与阶53
5.1原根与阶的概念53
5.2原根与阶的计算方法57
5.3DiffieHellman密钥协商协议62
5.4ElGamal公钥密码系统64
思考题66第6章群67
6.1群的相关概念67
6.2子群、陪集和拉格朗日定理70
6.3正规子群、商群和同态75
6.4循环群77
6.5置换群81
6.5.1置换群的概念81
6.5.2置换群的应用84
思考题86第7章环与域87
7.1环87
7.1.1环的概念87
7.1.2环同态、环同构92
7.1.3子环、理想93
7.1.4多项式环及其求逆元算法97
7.2域104
7.2.1子域、扩域、素域和商域104
7.2.2域上多项式107
7.2.3有限域及其高斯算法求生成元108
7.3环和域在AES加密中的应用116
7.3.1AES的设计思想116
7.3.2AES中S盒的设计117
7.3.3AES中列混合的设计120
7.4环在NTRU密码体制中的应用122
思考题124第8章素性检测126
8.1素数的一些性质126
8.2费马测试算法127
8.3SolovayStrassen测试算法127
8.4MillerRabin测试算法130
思考题132第9章椭圆曲线群133
9.1椭圆曲线群的概念133
9.2椭圆曲线群的构造方法134
9.3椭圆曲线密码139
9.3.1椭圆曲线上的DiffieHellman密钥协商协议139
9.3.2ElGamal加密的椭圆曲线版本139
9.3.3椭圆曲线快速标量点乘算法140
思考题141第10章格及其算法142
10.1格、格基和正交化算法142
10.2格困难问题、高斯约减算法和LLL算法146
思考题151第11章大整数分解算法153
11.1Pollard Rho方法153
11.2Pollard p-1分解算法154
11.3随机平方法155
思考题156第12章离散对数算法157
12.1小步大步算法157
12.2Pollard Rho算法158
12.3指数演算法160
12.4PohligHellman算法161
思考题163第13章其他高级应用164
13.1平方剩余在GM加密中的应用164
13.2中国剩余定理在秘密共享中的应用166
13.2.1秘密共享的概念166
13.2.2基于中国剩余定理的简单门限方案167
13.2.3AsmuthBloom秘密共享方案168
思考题170参考文献171