《密码学的数学引论》由会员分享，可在线阅读，更多相关《密码学的数学引论（73页珍藏版）》请在金锄头文库上搜索。
1、1,第4章密码学的数学引论,学习要点：了解信息论基本概念，熵和不确定性，完全保密了解数论、群论、有限域理论的基本概念熟悉模运算的基本方法熟悉欧几里德算法、费马定理、欧拉定理、中国剩余定理了解群、有限域的概念,2,信息存在于语言、文字、数据、图像等消息之中，是通信系统传输、交换、存储和处理的对象。信息和消息紧密相连。同样的消息，不同的人可能从中可获得不一样的信息。,4-1 信息论基本概念,3,信息论是应用近代概率统计方法来研究信息传输、交换、存储和处理的一门学科，进一步地讲，它是研究信息率、信道容量、噪声以及其他影响信息传输因素的一种数学理论。美国著名的密码学家Shannon是信息论的创始人，1
2、948年发表了“通信的数学理论”，确立了信息论。,4,Shannon从概率统计的观点出发研究信息的传输和保密问题 公共通信系统设计的目的是在信道有干扰的情况下，使接收的信号无差错或差错尽可能小,公共通信系统,5,保密通信系统,保密通信系统的设计目的是使窃听者即使在完全准确的收到了信号的情况下也无法恢复出原始信息,6,Shannon用信息论的观点回答了如下问题,当密码分析者有无限的时间和人力可用于分析密文时，一个体制能抗得住密码分析的能力有多大？密文是否有一个唯一解？为得到唯一解必须截获多少电文？如果不存在唯一解，那他有多少个合理的解？是否存在敌人无论截获多少电文也得不到任何信息的密码体制？,7
3、,熵和不确定性,信息量：假设所有信息是等可能的，对消息中所有可能的值进行编码所需要的最少的位数。熵：是一种表示信息量的方法，即为了表示不同的信息所需的二进制位（bit）的数目。表示方法: H(M),其中M表示信息，H(M)表示信息M的熵。,8,一周中某一天信息的熵值小于3（记为H(M)3），因为3 bit可以表示8个不同的状态：001，001，010，011，100，101，110，111 比如，设000 = 星期天 001 = 星期一 010 = 星期二 011 = 星期三 100 = 星期四 101 = 星期五 110 = 星期六还剩一个状态111没有使用,9,熵的计算方法,一条信息的熵是
4、: H(M)=Log2n其中n是信息所有可能的值思考：一年中月份的信息量是多少？,10,不确定性,熵又可以从另外一个角度来理解，其值能表示某些事件的不确定性。一个系统中可能会发生许多事件，但只是 “可能”，不等于“必然”，事件是不确定的。 当系统中事件等可能发生时，不确定的程度最大，也就是熵最大；而当系统中某一个事件必然发生，其他事件必然不发生，不确定的程度就是0，即熵为0。,11,多余度,多余度：指的是在通信的过程中，所传输的符号比信息所需要的符号要多多余用于检错和纠错，但不利于密码学比如：the、of、and、to、a、in、that、it、is和I这10个词单独无意义，但占1/4篇幅，可
5、用于分析Shannon指出：多余度为密码分析奠定了基础，多余度越小，破译分析越困难一种语言的冗余度用D表示,12,密码系统的安全性,密码分析者的目的是获取密钥K或明文P,或者两者都要。然而，他们也乐于得到一些有关P的统计信息：是否是英文的，是否电子表格等。,13,完全保密,Shannon从理论上证明，仅当可能的密钥数至少与可能的消息数目一样多时，完全保密才是可能的。 简言之，仅有一次一密的密码系统可获得完全保密,14,从完全保密的角度而言密文给出一些有关其对应的明文的信息是不可避免的一个好的密码算法可是这样的信息最少一个好的密码分析者利用这类信息可确定明文密码系统的熵可由密钥空间大小K来衡量：
6、 H(K)=log2K 密钥为64位的密钥系统的熵是64，一般来说，密码系统的熵越大，破译它就越困难,15,唯一解距离,怎样来衡量破译分析的困难性呢？Shannon定义了一个称作“唯一解距离”的量，其含义是当密码分析者进行穷举攻击时，可能解密出唯一有意义的明文所需要的最少的密文量。利用数学公式来计算：U=H(K)/D其中U：唯一解距离 H(K)：密钥的熵值 D：语言的多余度,16,可变密钥长度的ASCII文本加密算法的唯一解距离,17,说明：,唯一解距离，与所有统计的或信息论的指标一样，只能给出可能的结果，并不能给出肯定的预测。 唯一解距离指出了当进行穷举攻击时，可能 解密出唯一有意义的明文所
7、需要的最少密文量。唯一解距离越长，密码系统越好。,18,复杂性理论,复杂性理论提供了一种分析不同密码技术和算法的计算复杂性的方法。对密码算法和技术进行比较，然后确定它们的安全性。算法的复杂性问题的复杂性,19,算法的复杂性,时间复杂性和空间复杂性近代密码算法的破译取决于攻击方法在计算机上编程实现时所需的计算时间（时间复杂性T）和占用的硬件资源（空间复杂性S）平均复杂度O(n) n为问题的大小（输入的长度）计算复杂性的数量级，较低阶形式的函数均忽略不计,20,不同算法族的运行时间（n=106）,21,理论上，密码设计者都期望对其密码的任何攻击算法具有指数级的时间复杂性 事实上，根据目前计算复杂性
8、理论的状况而言， “所有已知的攻击算法均具有超多项式时间复杂性”,22,这个理论可以看作在被称作图灵机的理论计算机上解决最难的问题实例所需要的最小的时间和空间能够用多项式时间算法解决的问题称之为易处理的不能在多项式时间内解决的问题称之为难处理的能够用超多项式阶算法求解的问题在计算上是很难的。,问题的复杂性,23,问题复杂度,Alan Turing 证明了某些问题是不可判断的。不管算法的时间复杂性如何，编制一个算法来解决他们都是不可能的。,P类包括所有能用多项式时间解决的问题,NP类包括所有非确定型图灵机上可用多项式时间解决的问题,NP问题可以转换为NPC(NP完全问题)，NP类中困难最大的问题
9、,由于NPC问题目前没有找到有效的算法，因此适合用来构造密码体制。,24,1、除数(因子)的概念：设z为由全体整数构成的集合，若 b0且 使得a=mb,此时称b整除a.记为ba, 还称b为a的一个除数(因子).注:若a=mb+r且0r1，且因子仅有1, p，p被称为素数例：100以内的素数共有25个，它们是2，3，5，7，11，13，17，19，23，29，31，37，41，43，47，53，59，61，67，71，73，79，83，89，97,26,算术基本定理任何一个不等于0的正整数a都可以写成唯一的表达式aP11P22Ptt (4-1) 这里P1P2P3Pt是素数，其中ai0例：91=7
10、13 11011=711213 通过简单列出公式中的非0指数分量表示例：a=12=2231 表示为a2=2,a3=1 a=18=2132 表示为a2=1,a3=2 k=1218=216 k2=2+1=3 , k3=1+2=3 所以216=2332,27,最大公约数与互为素数,若a,b,cZ，如果ca，cb，称c是a和b的公约数。 正整数d称为a和b的最大公约数，如果它满足d是a和b的公约数。对a和b的任何一个公约数c有cd。记为：gcd(a,b)=d注：1等价的定义形式是： gcd（a,b）maxk ka且kb2若gcd（a,b）=1，称a与b是互素的。例：8的因子1,2,4,8; 15的因子
11、1,3,5,15 gcd(8,15)=1,28,1.带余除法：aZ且a0，可找出两个唯一确定的整数q和r,使a=qm+r, 0r m,q和r这两个数分别称为以m去除a所得到的商数和余数。 (若r=0则m|a) a除以n的余数用 a mod n 表示例：11 mod 7 =4 -11 mod 7 =3,二、模运算,29,2.整数同余：定义：如果(a mod n)=(b mod n)，则称整数a和b模n同余，记为： ab(mod n)，n称为模数。例：73 mod 23=4;4 mod 23=4; 73 4 mod 23,30,3.模运算 a mod n 的运算给出了a对模数n的余数，称为模运算模
12、运算具有如下的性质：(1) 如果m|(a-b) ab(mod m) a=q1m+r,b=q2m+r即a和b分别 除以m有相同的余数。“同余”二字的来源就在于此。,31,(2)相对于某个固定模数m的同余关系，是整数间的一种等价关系。具有等价关系的三点基本性质：自反性:对任意整数a有：aa(mod m)对称性:如果ab(mod m),则ba(mod m)传递性:如果ab(mod m),bc(modm), 则ac(mod m)(3)模m运算将所有整数映射到集合0,1,(m-1),称为剩余类集合Zm。,32,模运算的交换律、结合律和分配律(1)a(mod m)b(mod m)mod m=(ab)(mo
13、d m)(2)a(mod m)b(mod m)mod m=(ab)(mod m)(3)(ab)mod m+(ac)mod m=a(b+c)mod m例子.通过同余式演算证明560-1是56的倍数解： 注意53=12513(mod56) 于是有56=(53)2(13)2 mod 56 169 mod 56 1(mod56) 对同余式的两边同时升到10次幂,560 1mod 56 即有56560-1。,33,（2）通过同余式演算证明223 -1是47的倍数。同理, 注意到26=6417(mod47),于是223=(26)325=(26 26)26 25 289*(17)*(32) mod47 7*17*32 (mod47) 25*32(mod47) 1(mod47) 于是有 47223-1,34,定理：,(加法消去律)如果(a+b) (a+c) mod m, 则bc (mod m)(乘法消去律)对于(ab) (ac)mod m 若gcd(a,m)=1, 则bc (mod m),35,例1：附加条件不满足的情况 63=182 mod 8 67=422 mod 8 但3与7模8不同余，因为6和8 不互素。例2：附加条件满足的情况 53157 mod 8 511=557 mod 8 311 mod 8 3和11模8同余，因为6和8 互素。,
