计算机安全保密第二讲

计算机安全保密第二讲密码学数学基础唐明武汉大学计算机学院本次课的内容2.1信息论2.2复杂性理论2.3初等数论2.4因数分解2.5素数的产生2.6有限域内的离散对数2.7单向哈希函数2.1信息论2.1.1熵与疑义度2.1.2自然语言率2.1.3密码系统的安全性2.1.4确定性距离2.1.5混乱与扩散2.1.1熵与疑义度1949年，Shannon发表“CommunicationTheoryofSecrecySystems”一条消息中的信息量，形式上由该消息的熵来度量。一、自信息和熵1、自信息文字、图象、声音是消息，信息是消息的有价值内容。①给定一离散事件集X，它含有N个事件x1,x2,…,xN，事件xi出现的概率记作pi，1≥pi≥0且②自信息定义定义事件xi的自信息，记作I(xi),定义为注意：自信息的定义没有规定对数的底！对数底为2时，自信息单位为比特（bit）；对数底取为e时，自信息单位为奈特（nat）；对数底为10时，自信息单位为哈特（hart）。Niip11iipxIlog)(离散随机事件概率对数值的绝对值。③自信息的含义–自信息度量了一个随机事件xi未出现时所呈现的不确定性，也度量了该事件xi出现后所给出的信息量。–事件的不确定性越大，则一旦出现给出的信息量也就越大。④举例例计算从英文字母表中任选一个字母时所给出的自信息量。因为从26个字母中任取一个字母的概率为，所以任选一个字母所给出的信息量为261p4.7261log2I一、自信息和熵2、熵自信息描述了事件集X中一个事件出现给出的信息量，整个集X的平均信息量是该集所有事件自信息的统计平均值（数学期望），称作集X的熵。定义2.2集X的熵，记作H(X)，定义为定义中，规定0log0=0。H（X）度量了集X中各个事件未出现时所呈现的平均不确定性(疑义度)，也度量了集X中一个事件出现时所给出的平均信息量。NiiippXH1log)(疑义度：消息的熵同时也可衡量其不确定性（疑义度），即将消息隐藏在密文中时，要破译它所需的明文比特数（即当消息被加密成密文时，为了获取明文需要解密的明文的位数）。一、自信息和熵2、熵举例例给出集按定义有:I(x1)=-log21/2=log22=1比特，I（x2）=I（x3）=-log21/4=log24=2比特。于是一个事件集的熵越大，其不确定性越高。41,41,21,,,321321pppxxxX。5.1412412211)(XH比特。关于熵的实际例子例：X可能在下周某天去钓鱼。星期一，……，星期日共有七种可能（x1，…，x7），假设各种可能性出现概率相等，则：P（Xi）=1/7，H（x）=－7·(1/7)·log21/7=－log21/7=log27同时，H（x）也指出了X中的信息量将消息中所有可能的值进行编码时所需的最少比特数。2H(x)=log273b1b2b3可以表示一周的7个状态：–000星期日–001星期一–……–110星期六–保留关于熵的实际例子甲任意取一个不超过15的整数，由乙来猜，但允许乙提K个问题，甲只回答“是”或者“非”，问K多大时可以确定猜到该数。解：若令乙猜想作为事件V，V可能有16种结果，假定这16种结果是等概率的，V的熵为：H（V）=log216令事件Ak=U1U2U3…Uk为提问k个问题，但Ui的熵不超过log22=1，（因为只有“是”或者“非”），故Ak的熵为不超过k比特，则：log216k·log22=k，k4故k=4继续前面的例子0到15之间的数可以由4比特信息来表示。即————————而上面的问题实际上可以转化为如何获得这4个比特信息。因为每个问题的答案只有两种，故每个问题的答案最多只能提供1比特的信息。因而如果要确保得到正确结果，则至少需要4次。那如何保证每次可以获得1位的信息呢？最直接的四个问题：这个数被表示为四位二进制后，第一位是0吗？这个数被表示为四位二进制后，第二位是0吗？……这样，我们可以确保每次都可以得到一位信息。思考？假设乙的第一个问题是“这个数字是a吗？”–其中a是0-15之间的任意一个确定的数。如果乙得到“是”的回答，请问该事件提供的信息量是多少？如果乙得到“否”的回答，请问乙是否还能够确保在规定次数之内得到正确结果？为什么？思考？假设乙的第一个问题是“这个数字大于11吗？”如果乙得到“是”的回答，请问该事件提供的信息量是多少？如果乙得到“否”的回答，请问乙是否还能够确保在规定次数之内得到正确结果？为什么？关于熵的实际例子有25个外表完全相同的硬币，其中24个重量完全一样，有一个较轻的伪币，用无砝码的天平，试问要做多少次的比较，可以找到这枚伪币？继续前面的例子解：事件V为找出伪币，可能有25个结论，他们是等概率，故：H（V）=log225，事件U为天平称的结果，可能有3种情况：1.左右平衡；2.左边重；3.右边重；故：H（U）=log23令Ak=U1U2U3…Uk为连续用k次天平的事件，k·log23log225k（log225）/log23=2.93故k最少为3次继续前面的例子一种解决方案：i.25=8+8+9（第一次）•天平两端各放8个，如果平衡，则伪币在剩余的9个之中，跳到ii；•如果不平衡，则伪币在较轻的8个之中，跳到iii。ii.9=3+3+3（第二次）•天平两端各放3个，如果平衡，则从剩下3个中寻找伪币。否则，从较轻的3个中寻找伪币。iii.8=3+3+2（第二次）•天平两端各放3个，如果平衡，则从剩下2个中寻找伪币。否则，从较轻的3个中寻找伪币。思考？有25个外表完全相同的硬币，其中24个重量完全一样，伪币重量不一样，但不知是轻还是重，用无砝码的天平，试问要做多少次的比较，可以找到这枚伪币？2.1.2自然语言率自然语言率：对于给定的一种语言，其自然语言率为r=H(M)/N其中N为消息长度。–英语的自然语言率：1.0比特/字母～1.5比特/字母–它是一个语言系统的实际表现力，实际上是一个语言系统的实际熵。绝对语言率绝对语言率：每个字符编码的最大比特数，这里假设每个字符序列出现的机会相等。–若语言中有L个字母，则绝对语言率为：R=log2L为单个字母的最大熵。–英语的绝对语言率：log2264.7比特/字母–它是一个语言系统理论上的最大表现力。当每个字符出现的概率相同时，其具有最大表现力。实际上是语言系统的最大熵。冗余度：语言的冗余度记为D，定义为：D=R-r其中，R为绝对语言率，r为自然语言率。–英语：r=1.3比特/字母，则D=3.4比特/字母。2.1.3密码系统的安全性绝对安全的密码系统：–M：明文空间；K：密钥空间；C：密文空间；c=E(m,k)。E：M→C。–H(M),H(K)–绝对保密的密码系统的必要条件：H(K)H(M)卢开澄，计算机密码学，清华大学出版社。即：一次一密（密钥与消息本身一样长，且密钥不重复使用）系统。密码系统的熵：衡量密钥空间K的大小的一个标准，通常是密钥数以2为底的对数。H（K）=log2k2.1.4确定性距离对于长度为n的消息，能够将一段密文消息解密成与原始明文同种语言的可懂文本的密钥个数为：2H(K)-nD-1确定性距离：能够唯一地确定密钥的最短的密文长度的近似值。–对称密码系统的确定性距离：定义为密码系统的熵除以语言的冗余度。U=H（K）/D理想安全的密码系统：确定性距离无限大的密码系统。2.1.5混乱与扩散混乱：在加密变换中，让密钥与密文的关系尽可能复杂的做法。–实现混乱的方法：代替扩散：在加密过程中，尽可能将明文的位置统计特性在密文中消除。–实现扩散的方法：换位2.2复杂性理论2.2.1算法复杂性2.2.2问题复杂性2.2.1算法复杂性算法的复杂性通常由两个变量来衡量：T（时间复杂性）和S（空间复杂性，或存储需求）。T和S都用n的函数来表示，其中n为输入的大小。数量级法：当n增大时，复杂性函数中增加得最快的一项。多项式时间算法：–O(1)：常数的–O(n)：线性的–O(n2)：平方的–…–O(nm)：m为常数指数时间算法：O(tf(n))，其中t为大于1的常数，f(n)为n的多项式函数。–超多项式时间算法：O(cf(n))，其中c为大于1的常数，f(n)大于常数，小于线性。2.2.2问题复杂性图灵机：一个有限状态机，具有无限的读写存储磁带，是一个理想化的计算模型。问题：–易解的问题：可以在多项式时间内求解–难解的问题：只能在指数时间内求解–不确定的问题：找不出解决的算法，不考虑算法的时间复杂性问题复杂性的划分：–P问题：可以在多项式时间内求解的问题。–NP问题：只能在一个非确定性的图灵机（能够进行猜测的一种图灵机）上在多项式时间内求解的问题。•NP完全问题：一些特定的NP问题，与其他NP问题同等困难。–P空间问题：可以在多项式空间内求解，但不能在多项式时间内求解的问题。•P空间完全问题：与其他P空间问题同等困难。–指数时间问题PNPNP完全的P空间P空间完全的指数时间的2.3初等数论2.3.1模运算2.3.2素数2.3.3最大公因数2.3.4乘法逆元素2.3.5Fermat小定理及欧拉函数2.3.6中国剩余定理2.3.7二次剩余2.3.8Legendre（勒让得）符号2.3.9Jacobi（雅各比）符号2.3.10生成元2.3.11有限域中的计算2.3.1模运算同余：如果a=b+kn，k为整数，则–ab（modn）amodn：a模n操作，表示a除以n的余数，为0到n－1之间的整数。–例如：(7＋9)mod12=16mod12=4模运算（+、－、）满足交换律、结合律和分配律。–(a+b)modn=((amodn)+(bmodn))modn–(a-b)modn=((amodn)-(bmodn))modn–(a*b)modn=((amodn)*(bmodn))modn–(a*(b+c))modn=((a*bmodn)+(a*cmodn))modn按模计算原理：对中间结果作模运算与做完了全部运算后再做模运算结果相同。求:1711mod26=?按模指数运算：ammodn–将指数运算作为一系列乘法运算，每次做一次模运算。–例：a8modn=((a2modn)2modn)2modn–当m不是2的乘方时，将m表示成2的乘方和的形式。–例如：25=(11001)2，即25=24+23+20a25modn=(a16a8a)modn=((((a2)2)2)2((a2)2)2a)modn=((((a2a)2)2)2a)modn–适当存储中间结果，则只需6次乘法：(((((((a2modn)a)modn)2modn)2modn)2modn)a)modn求1711mod26=?2.3.2素数素数（质数）：大于1的整数，只能被1和本身整除。有无穷多个素数。如：2，73，2521，2365347734339，2756839-12.3.3最大公因数公因数：两个整数a，b的公因数定义为能同时整除a，b的所有整数。最大公因数：a与b的公因数中能被所有a，b的公因数整除的正整数，记为gcd(a，b)。互素（互质）：两个整数称为互素的，如果它们除了1以外没有其他的公因数，即gcd(a,b)=1。最大公因数的求法：辗转相除法即Euclid算法–例如：求gcd(15,36)36=152+615=62+36=32+0因此，gcd(15,36)=3–原理：若ab(modc)，则gcd(a,c)=gcd(b,c)–这里，gcd(15,36)=gcd(15,6)=gcd(6,3)=3理论基础:若a=b·q+r，则gcd（a,b）=gcd（b,r）定理：若a=b·q+r，则gcd（a,b）=gcd（b,r）那么：gcd（a,b）=gcd(b,amodb)untilamodb=0thenbistheresult.证明：d=（a,b），d’=（b