信息安全数学基础.pdf

网络空间安全系列教材网络空间安全系列教材 信息安全数学基础信息安全数学基础 姜正涛 编著 Publishing House of Electronics Industry 北京BEIJING 内 容 简 介 本书系统地介绍信息安全领域所涉及的数论、代数、椭圆曲线、线性反馈移位寄存器、计算复杂度、图论、信息论等内容。对信息安全实践中密切相关的数学知识做了较详细的讲述，并通过大量例题与密码算法介绍加深对数学原理的理解。每章配有适量习题，以供学习和巩固书中内容。本书可作为高等院校信息安全专业本科生或研究生的教材，也可作为信息安全、网络空间安全、计算机科学技术、通信工程等相关领域的科研或工程技术人员的参考书。未经许可，不得以任何方式复制或抄袭本书之部分或全部内容。版权所有，侵权必究。图书在版编目(CIP)数据 信息安全数学基础/姜正涛编著.北京：电子工业出版社，2017.12 ISBN 978-7-121-33185-5.信 .姜 .信息安全应用数学高等学校教材 .TP309 O29 中国版本图书馆 CIP 数据核字（2017）第 301196 号 策划编辑：章海涛 责任编辑：章海涛 文字编辑：孟 宇 印 刷：装 订：出版发行：电子工业出版社 北京市海淀区万寿路 173 信箱 邮编：100036 开 本：7871092 1/16 印张：15.25 字数：390 千字 版 次：2017 年 12 月第 1 版 印 次：2017 年 12 月第 1 次印刷 定 价：52.00 元 凡所购买电子工业出版社图书有缺损问题，请向购买书店调换。若书店售缺，请与本社发行部联系，联系及邮购电话：（010）88254888，88258888。质量投诉请发邮件至 ，盗版侵权举报请发邮件至 。本书咨询联系方式：192910558（QQ 群）。III 前 言 信息安全与国家的军事、外交、政治、金融甚至我们的日常生活息息相关，已成为信息科学领域、社会科学领域重要的研究课题。数学基础犹如信息安全学科之根茎，支撑着信息安全领域的理论创新与技术进步。信息安全是计算机、通信、电子、数学、物理、法律、管理等多学科的交叉学科，所涉及的数学内容极为宽泛。本书系统地介绍信息安全领域涉及的主要数学理论，有选择性地略去了较为繁杂的证明过程，希望深入探讨相关理论的读者可查阅书末的参考文献。本书共分为 15 章：第 1 章至第 5 章是数论基础，包括整数的整除与因子分解、同余式、二次剩余、原根、素性检测等内容；第 6 章至第 9 章是代数系统，包括群、环、域的概念，重点介绍群的性质，有限域的性质、构造以及本原多项式；第 10 章是椭圆曲线，主要介绍椭圆曲线方程与椭圆曲线群加法运算；第 11 章是线性反馈移位寄存器，包括线性反馈移位寄存器序列的周期、m 序列、m 序列的随机性及安全分析等内容；第 12 章是计算复杂度理论，重点介绍 P 类问题、NP 问题、NPC 问题及其典型实例；第 13 章是图论，主要包括邻接矩阵与关联矩阵、连通性、最短路问题以及树的概念与性质；第 14 章与第 15 章是信息论，主要包括信息论与编码、完善保密性、唯一解距离等内容。本书稿已连续多年作为信息安全本科教学讲义，对内容编排进行了多次修正，以符合教学之用。由于作者水平有限，一些错误或不妥之处可能尚未发现，敬请老师和学生提出宝贵意见，以便呈现更完善的内容。感谢为本书初稿部分章节提出改进意见的同仁：天津大学的孙达志老师（第 15 章）；漳州师范学院的郝艳华老师（第 6、10 章）；西安电子科技大学的张卫国老师与电子科技大学的李发根老师（第 79 章）；西安电子科技大学的高军涛老师（第 11 章）；北京航空航天大学的伍前红老师（第 12 章）；鲁东大学的黄兆红老师与中山大学的田海博老师（第 13章）；北方工业大学的张键红老师（第 1415 章）。特别感谢西安电子科技大学王育民教授提出的宝贵改进意见。作 者 2017 年 12 月于中国传媒大学 电子邮箱： IV V 符号说明|整除 不整除 x 取整函数(a,b)a 与 b 的最大公因子 a,b a 与 b 的最小公倍数 mod m 模整数 m 同余 不同余 Z 整数集 空集 Q 有理数集 Zx 整数上的多项式全体 Zm 模 m 的剩余类环 Zm*0,1,m 1中与 m 互素的数 Zm0 集合1,m 1()欧拉函数 QRm 模 m 的二次剩余 QNRm 模 m 的二次非剩余 ap a 模 p 的勒让德符号 ordgm g 模 m 的阶 indga(m)以 g 为底的 a 模 m 的指数 H G H 是群 G 的子群(a)由元素 a 生成的主理想 由元素 a 生成的循环群|G|集合 G 中元素个数|a|元素 a 的阶 Pk|a pk|a,但 pk+1 a N?G N 为群 G 的正规子群 G/N 商群 ker(f)映射 f 的核 im(f)映射 f 的像 Fq,GF(q)q 元有限域 Fq*域 Fq除去 0 元的乘法群 VIChar(F)域 F 的特征 Fx 域 F 上的多项式全体 deg f(x)多项式 f(x)的次数 E:F 域的扩张次数 ord(f(x)多项式的阶（周期）椭圆曲线的判别式 O(f)算法复杂度与 f 同数量级 信道容量 H 极限熵（实际熵）BSC 二元对称信道 L L 长明文中单个符号的冗余度 明文信源的实际冗余度 V0 唯一解距离 VII 目 录 第 1 章 整数的整除与唯一分解 1 1.1 整除和带余除法 1 1.2 整数的表示 3 1.3 最大公因子与辗转相除法 5 1.4 最小公倍数 9 1.5 整数的唯一分解 12 1.6 素数有无穷多 14 1.7 麦什涅数与费马数*15 1.8 素数的著名问题*17 习题 1 18 第 2 章 同余式 20 2.1 同余的定义 20 2.2 剩余类 22 2.3 欧拉函数 24 2.4 同余方程 28 2.5 中国剩余定理 31 2.6 RSA 公钥密码体制 34 习题 2 36 第 3 章 二次剩余 40 3.1 二次剩余概述 40 3.2 勒让德符号 41 3.3 二次互反律 44 3.4 雅可比符号 45 3.5 二次同余式的解法 50 3.6 Rabin 公钥密码体制 52 习题 3 54 第 4 章 原根与阶 57 4.1 模一个整数的阶与原根 57 4.2 原根的性质 63 4.3 指数*65 习题 4 66 第 5 章 素性检测 68 5.1 素数的简单判别法 68 VIII5.2 素数的确定判别法 68 5.3 拟素数 72 5.4 欧拉拟素数 76 5.5 强拟素数 78 5.6 AKS 素性检测*82 习题 5 82 第 6 章 群 84 6.1 群的定义 84 6.2 群的性质 86 6.3 群的陪集 89 6.4 正规子群、商群 90 6.5 群的同态定理 92 6.6 循环群 95 6.7 有限生成交换群*99 6.8 置换群*100 习题 6 104 第 7 章 环 106 7.1 环的定义 106 7.2 零因子和特征 109 7.3 理想*111 7.4 NTRU 公钥密码体制 116 习题 7 118 第 8 章 域 119 8.1 域的定义 119 8.2 域上的多项式 121 8.3 域的扩张 126 8.4 单扩域 127 8.5 代数扩域 130 8.6 多项式的分裂域*131 习题 8 134 第 9 章 有限域 136 9.1 有限域的性质 136 9.2 有限域的构造 139 9.3 多项式的根、迹与范数*142 9.4 本原多项式 145 9.5 Diffie-Hellman 密钥协商算法 146 9.6 AES 中的有限域运算 147 习题 9 150 IX第 10 章 有限域上的椭圆曲线 152 10.1 椭圆曲线的定义 152 10.2 不同域上的椭圆曲线 153 10.3 椭圆曲线的群加法运算 155 10.3.1 椭圆曲线加法运算规则 155 10.3.2 椭圆曲线加法公式 156 10.4 不同特征有限域上的椭圆曲线群加法 158 10.5 椭圆曲线群阶 162 10.6 椭圆曲线密码体制 165 习题 10 166 第 11 章 线性反馈移位寄存器 167 11.1 移位寄存器概念 167 11.2 LFSR 的特征多项式与周期 169 11.3 LFSR 序列的随机性 173 11.4 LFSR 序列的安全性 176 11.5 非线性序列生成器*177 11.5.1 Geffe 序列生成器 177 11.5.2 JK 触发器 178 11.5.3 Pless 生成器 179 11.6 SNOW 流密码算法 179 习题 11 181 第 12 章 计算复杂度 182 12.1 算法和计算模型 182 12.2 图灵机 184 12.3 P 类问题 185 12.4 NP 问题 187 12.5 NPC 问题 187 12.6 NP 困难问题 188 12.7 典型的 NPC 问题 189 12.8 背包公钥密码算法*190 习题 12 192 第 13 章 图论 193 13.1 图的基本概念 193 13.2 邻接矩阵与关联矩阵 194 13.3 同构与顶点的度 194 13.4 路和连通性 195 13.5 最短路问题 196 13.6 树 198 X13.7 二叉树 200 13.8 Merkle 树签名方案*202 13.8.1 一次性签名方案 202 13.8.2 Merkle 树签名方案 203 习题 13 206 第 14 章 信息论与编码 207 14.1 通信系统模型 207 14.2 信息的统计度量 208 14.2.1 自信息量 208 14.2.2 互信息量 209 14.2.3 信息熵 211 14.2.4 条件熵 211 14.2.5 联合熵 212 14.2.6 平均互信息量 213 14.3 信道容量 213 14.4 平稳信源的熵 217 14.5 信源编码*220 习题 14 221 第 15 章 信息论与保密 223 15.1 完善保密性 223 15.2 唯一解距离 225 15.3 实际密码的唯一解距离 227 习题 15 229 索引 230 参考文献 233 001 第 1 章 整数的整除与唯一分解 整数性质是初等数论最重要的内容，包括整数的整除和同余等。本章主要介绍整除、带余除法、最大公因子、最小公倍数，以及求最大公因子的算法，并给出整数唯一分解定理。1.1 整除和带余除法 正整数（如 1,2,3,）、负整数（如 1,2,3,）与零（0）统称为整数整数。通常，用符号 Z=0,1,2,3,表示整数集合，零与正整数称为自然数自然数。两个整数的和、差、积仍然是整数，但两个整数相除得到的商未必是整数。为此，我们引入整除、带余除法等概念。定义 1.1 任意两个整数 a,b，其中 b 0，如果存在一个整数 q，使等式 a=bq(1.1)成立，我们就说 b 整除整除 a，或 a 被 b 整除，记为 b|a。此时，称 b 为 a 的因子因子，a 为 b 的倍数倍数。0 是任何非零整数的倍数，1 是任何整数的因子。若 b|a，且 b 1,b a，就称 b 是 a 的真因子真因子，否则就称 b 为 a 的平凡因子平凡因子。任何非零整数是自身的因子和倍数。式(1.1)中的整数 q 常写成 a/b 或ab。如果不存在整数q满足式(1.1)，我们就说b不整除不整除a，记为b a。设a,b,c为整数，根据整除的定义，可以得到以下性质：若c|b,b|a，则c|a（传递性）；若b|a，c 0，则cb|ca；若cb|ca，则b|a；若b|a且a 0，则|b|a|；若b|a,a 0，则|aab；若c|a,c|b，则对任意整数m,n，有c|ma nb。一般地，余数定理如下。定理 1.1（带余除法）设a,b是两个整数，其中b 0，则存在唯一的整数q和r，使得 a=bq+r,0 r b(1.2)成立。证明 考虑