作者：李超,付绍静
出版社：电子工业出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
信息安全数学基础试读：
前言
随着信息技术的不断发展，信息安全的内涵也在不断地延伸。从最初的信息保密性发展到信息的保密性、完整性、可用性和不可否认性，进而发展到网络攻防、安全控制、安全测评和安全管理等多方面的理论与技术。
近半个世纪以来，信息安全有了很大的发展，数学研究对信息安全的发展起了巨大的推动作用。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月于长沙第1章 数论基础
数论研究整数环中整数最基本性质，整除理论、同余理论和不定方程求解构成数论的基本内容。随着信息技术的飞速发展，数论所涉及的知识在信息领域特别是信息安全领域具有广泛的应用，公钥密码标准RSA算法是基于大整数分解困难性而设计的，通信系统中广泛使用的Diffie-Hellmen协议与整数的同余和原根密切相关。掌握数论的基本知识，对于从事信息安全理论与应用研究具有重要作用。1.1 整数的整除
全体整数的集合通常用Z来表示，即
在整数集合Z中，两个整数可以进行加、减、乘三种运算，并且运算后的结果仍为整数。但两个整数进行除法运算后所得的结果未必为整数，比如4除以2所得结果为2，它是一个整数，而4除以3所得结果为，它不是整数。
定义1.1 设a，b是任意两个整数，b≠0，如果存在整数c，使得a=bc，则称b整除a，记做b|a，否则称b不整除a，记做ba。
如果有b|a，称b为a的因数，a为b的倍数。显然±1是任何整数的因数，所有的非零整数均为0的因数。由整除的定义，易知如下性质成立：（1） 如果c|b，b|a，则c|a；（2）如果c|b，c|a，则对任意m，n∈Z，均有c|（ma+nb）；（3）如果b|a，且a≠0，则|b|≤|a|；（4）如果a|b，b|a，则 a=b，即a=±b。
例1.1 证明：对任意正整数n，均有6|n（n+1）（2n+1）。
证明 当n=1时，n（n+1）（2n+1）=1×2×3=6，它是6的倍数，结论成立。
假设当n=k时，结论成立，即
则当n=k+1时，有2
由归纳假设，6|k（k+1）（2k+1），并且6|6（k+1），从而根据整除的性质（3），得到
由归纳法原理，6|n（n+1）（2n+1）对任意正整数n成立。
例1.2 如果m，n，r，q∈Z，并且（m-p）|（mn+pq），证明（m-p）|（mq+np）。
证明 由于
上式右边三项都是m-p的倍数，从而有
定理1.1（带余除法） 设a，b∈Z，b≠0，则存在唯一的q，r∈Z，使得a=bq+r，这里0≤r＜|b|。
证明 不妨设b>0。当b<0时，类似可证。
考虑如下整数序列
则对任意a∈Z，必存在q∈Z，使得
令r=a-qb，则0≤r 下面讨论q和r的唯一性。 如果a=qb+r=qb+r，这里0≤r，r 若q≠q，则|r-r|≥b，这与0≤r，r 定义1.2 设a，b∈Z，b≠0，如果a=bq+r，这里0≤r＜|b|，则称q为b除a所得商，r为b除a所得的余数。 利用带余除法容易判定两个整数的整除关系，即定理1.2。 定理1.2 设a，b∈Z，b≠0，则b|a当且仅当b除a所得余数为0。 例1.3 从176～545的所有整数中，13的倍数有多少个？ 解 对实数x而言，记［x］为小于或等于x的最大整数。由带余除法，从1～176的所有整数中，13的倍数有个，从1～545的所有整数中，13的倍数有个，从而从176～545的所有整数中，13的倍数有41-13=28个。□ 定义1.3 设d，a，a，…，a∈Z，并且a，a，…，a不全为0，12n12n如果对每个a，均有d|a，则称d为a，a，…，a的一个公因数。整ii12n数a，a，…，a的所有公因数中最大的正因数称为a，a，…，a12n12n的最大公因数，记为（a，a，…，a）。12n 对于任意一组不全为零的整数a，a，…，a，由于不为零整数12n的因数只有有限个。从而a，a，…，a的公因数也只有有限个，故12n其最大公因数一定存在。如何计算最大公因数（a，a，…，a），12n这是整除理论中一个基本问题。下面介绍求最大公因数的辗转相除法。 定理1.3 设a，b，c∈Z，并且b≠0，如果 则（a，b）=（b，c）。 证明 设（a，b）=d，（b，c）=d。由于（a，b）=d，则d|1211a，d|b，又c=a-bq，故d|c，从而d为b和c的一个公因子，于是d≤1111d。同理可证d≤d，故 （a，b）=（b，c）。□221 由定理1.3，可以求两个不全为0的整数的最大公因数。 设a，b∈Z，并且a，b不全为0，不妨设b≠0。由带余除法，必存在正整数n，满足 由定理1.3，得到 上面求两个整数的最大公因数的方法称为辗转相除法，由辗转相除法的推导过程反推回去，便有如下定理1.4。 定理1.4 设a，b∈Z，a，b不全为0，则存在m，n∈Z，使得 一般而言，定理1.4中m，n不一定唯一，比如 由定理1.4可以看出，a和b的任意公因数都是a和b的最大公因数的因数。反过来，a和b的最大公因数的因数也一定是a和b的公因数。这说明两个不全为零的整数的公因数与它们最大公因数的因数一致。 例1.4 计算（2295，4471），并求整数x，y，使得（2295，4471）=2295x+4471y。 于是（2295，4471）=17。利用上述算式可得 故（2295，4471）=4471×（-58）+2295×113。□ 用辗转相除法可以求两个整数的最大公因数，而多个整数的最大公因数的求法可以转化为两个整数的最大公因数的求法，即有如下定理1.5。 定理1.5 设a，a，…，a是一组全不为0的整数，并且12n 则（a，a，…，a）=d。12nn 证明 由条件d|a，d|d，又d|a，d|d，故d|a，nnnn-1n-1n-1n-1n-2nn-1d|d。以此类推，最后得到n-1n-2 即d为a，a，…，a的一个公因数。n12n 设d为a，a，…，a的任一个公因数，则d|a，d|a，从而d|12n12d。又d|a，从而d|a，故d|d。由此类推，最后得到d|d。于是d≤d，2333nnd是a，a，…，a的最大公因数。□n12n 对于一组给定的不全为0的整数a，a，…，a，在求其最大公12n因数时，考虑到数0是任何非零整数的倍数，不失一般性，我们只需要求那些不为0的整数的最大公因数，并利用定理1.5由辗转相除法求得。 定义1.4 设a，b是两个不为0的整数，如果（a，b）=1，则称a与b互素。 定理1.6 设a，b∈Z，则（a，b）=1当且仅当存在m，n∈Z，使得ma+nb=1。 证明 如果（a，b）=1，由定理1.4可知存在m，n∈Z，使得 反过来，如果ma+nb=1，则对a与b的任意公因子d，均有d|a，d|b，从而d|1，又1显然为a与b的公因子，从而（a，b）=1。□ 利用定理1.6，可以推出互素的下述基本性质：（1） 如果（a，b）=1，（a，c）=1，则（a，bc）=1；（2） 如果a|bc，并且（a，b）=1，则a|c；（3） 如果a|c，b|c，并且（a，b）=1，则ab|c。 与公因数与最大公因数相应的，还有公倍数与最小公倍数的概念。 定义1.5 设a，a，…，a，m∈Z，如果对每个a，均有a|m，则12nii称m为a，a，…，a的公倍数，a，a，…，a的一切公倍数中最12n12n小的正整数，叫做a，a，…，a的最小公倍数，记为[a，a，…，12n12a]。n 同最大公因数一样，最小公倍数是否存在？如果存在，又怎样求最小公倍数呢？首先，由于最小公倍数只涉及整数的整除性，而整数的整除性与整数的正负号无关，故不妨设所有a均为正整数。其次，i当a，a，…，a均为正整数时，乘积aa…a显然为a，a，…，a12n12n12n的一个公倍数，从而a，a，…，a的最小公倍数一定存在。12n 定理1.7 设a，b为两个正整数，则下列结论成立：（1） a，b的所有公倍数就是［a，b］的所有倍数； (2). 证明 设m是a，b的任一公倍数，不妨m>0，则存在正整数k和l，使得m=ak=bl。令a=a（a，b），b=b（a，b），则（a，b）=1，1111并且 于是ak=bl。又由于（a，b）=1，故根据互素的性质（2）得1111到b|k，不妨设k=bt，t∈Z，因此有11 从而a，b的公倍数都是的倍数。又是a和b的公倍数，从而其为a，b的最小公倍数，即 多个整数的最小公倍数，可以通过两个整数的最小公倍数求得。从而有如下定理。 定理1.8 设a，a，…，a（n≥2）为正整数，并且［a，a］12n12=m，［m，a］=m，…，［m，a］=m，则2233n-1nn 证明 由定理1.7，m|m（2≤i≤n-1），a|m，a|m（2≤i≤n），故ii+112iim是a，a，…，a的一个公倍数。又设m为a，a，…，a的任意n12n12n公倍数，则a|m，a|m，于是m|m。再由a|m，故m|m。以此类12233推，最后得m|m，于是m为a，a，…，a最小公倍数。□nn12n 例1.5 计算［2295，4471］。
试读结束[说明：试读内容隐藏了图片]