信息安全数学基础

本书更加关注知识结构的合理性、系统性和应用性。在知识结构的合理性方面，按照由浅入深、由易入难的理念组织内容，编写过程中力求做到叙述自然流畅，文字生动活泼，例题充实新颖；在知识结构的系统性方面，突出数论、代数、组合、信息论和计算复杂性的一体化融合，前后内容相互呼应，相互支撑；在知识结构的应用性方面，突出内容在信息安全领域中的应用。 

    本书系统地介绍了数论、代数、组合、信息论和计算复杂性等数学理论与方法，突出数论、代数、组合、信息论和计算复杂性的一体化融合，前后内容相互呼应，相互支撑。在知识结构的应用性方面，突出教材内容在信息安全领域中的应用。数论部分给出了代换密码、RSA算法、DiffieHellman协议的数学原理刻画；代数部分给出了AES算法、EIGmal算法、Schnorr算法和DSS算法的数学原理刻画；组合部分给出了Hash函数和Bent函数的设计与分析方面所涉及的组合知识；信息论部分给出了完善保密性的信息论刻画；计算复杂性部分给出了基于计算安全的密码方案分析原理的刻画。 本书可作为信息安全领域相关专业本科生和研究生的教材，也可供从事信息安全和其他信息技术工作的科研和工程技术人员参考。

    李超，自1990年至今在国防科技大学任教，现为国防科技大学理学院教授，从事应用数学、密码学研究。为中国密码学会理事，湖南省数学会常务理事。曾负责国家自然科学基金面上项目，高度非线性函数的性质、构造与应用，2010/01-2013/12；973专题，****系统并行计算的表示与存储，2012/01-2014/12；863课题，****攻击技术与方法研究，2012/06-2016/7。曾获军队科技进步一等奖1项、湖南省科技进步二等奖1项、霍英东青年教师奖三等奖1项，军队院校育才奖金奖和银奖各1项。出版过多部图书。

第1章  数论基础  
  1.1  整数的整除
  1.2  算术基本定理
  1.3  整数的同余
  1.4  同余式
  1.5  Legendre符号和Jacobi符号
  1.6  数论在信息安全中的应用
  习题一 
第2章  代数基础  
  2.1  群的定义与例子
  2.2  子群、正规子群与商群
  2.3  群同态与群同构 
  2.4  环的定义与例子
  2.5  子环、理想与商环
  2.6  环同态与环同构
  2.7  有限域
  2.8  代数在信息安全中的应用
  习题二
第3章  组合数学  
  3.1  排列与组合
  3.2  容斥原理与鸽笼原理 
  3.3  母函数
  3.4  递推关系
  3.5  区组设计 
  3.6  组合数学在信息安全中的应用 
习题三 
第4章  信息论基础    
  4.1  通信系统的数学模型 
  4.2  信息的度量 
  4.3  联合熵与条件熵 
  4.4  互信息与平均互信息
  4.5  离散信源 
  4.6  信息论在密码学中的应用 
  习题四 
第5章  计算复杂性基础    
  5.1  时空复杂性与算法分析 
  5.2  确定图灵机与P类问题 
  5.3  RAM模型 
  5.4  非确定性图灵机与NP类问题 
  5.5  NP完全性 
  5.6  若干典型的NP完全问题
  5.7  计算复杂性理论在密码学中的应用 
  习题五

前 言

随着信息技术的不断发展，信息安全的内涵也在不断地延伸。从初的信息保密性发展到信息的保密性、完整性、可用性和不可否认性，进而发展到网络攻防、安全控制、安全测评和安全管理等多方面的理论与技术。
近半个世纪以来，信息安全有了很大的发展，数学研究对信息安全的发展起了巨大的推动作用。20世纪70年代公开密钥密码体制的提出，是信息安全领域的一场革命。目前采用的两种主要的公开密钥密码体制（RSA密码体制和椭圆曲线密码体制）均源于数论（大整数分解理论和椭圆曲线算术理论）。21世纪初美国公布的高级加密标准（AES算法）是当前信息安全领域的研究热点，该算法的设计采用了有限域上基本代数运算。近年来，人们对于数字签名、身份认证、密钥共享和多方安全计算等问题，均采用了数论工具（指数和估计）和组合工具（组合设计和Matroid理论）。与此同时，信息领域为数学提出了大量的数学问题，也促进了数学的发展，增强了数学研究的活力。
本书主要介绍从事信息安全研究所需要的基本数学知识，包括数论、代数、组合、信息论和计算复杂性等数学理论与方法。与其他同类型的教材相比，本书更加关注知识结构的合理性，更加关注知识结构的系统性，更加关注知识结构的应用性。在知识结构的合理性方面，按照由浅入深、由易入难的理念组织教材内容，编写过程中力求做到叙述自然流畅，文字生动活泼，例题充实新颖；在知识结构的系统性方面，突出数论、代数、组合、信息论和计算复杂性的一体化融合，前后内容相互呼应，相互支撑。在知识结构的应用性方面，突出教材内容在信息安全领域中的应用。数论部分给出了代换密码、RSA算法、Diffie-Hellman协议的数学原理刻画；代数部分给出了AES算法、EIGmal算法、Schnorr算法和DSS算法的数学原理刻画；组合部分给出了Hash函数和Bent函数的设计与分析方面所涉及的组合知识；信息论部分给出了完善保密性的信息论刻画；计算复杂性部分给出了基于计算安全的密码方案分析原理的刻画。
本书是作者长期从事信息安全教学和科研基础上完成的。其研究工作先后得到国家自然科学基金项目（61070215、 61103191和61103192）、 国家863项目（2011AA7114065和2012AA7114065）、国家973项目（2013CB338002和613203032012）的资助。书中前三章由李超编写，后两章由付绍静编写，全书由李超负责统稿。本教材内容已经在国防科学技术大学计算机学院信息安全本科专业进行了多次教学实践。
由于作者水平所限，书中难免会有不妥和错误之处，恳请读者批评指正。

作者
2014年6月于长沙