计算机安全保密：第二讲 密码学数学基础课件.ppt

计算机安全保密第二讲密码学数学基础,本次课的内容,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发表“Communication Theory of Secrecy Systems” 一条消息中的信息量，形式上由该消息的熵来度量。,一、自信息和熵,1、自信息 文字、图象、声音是消息，信息是消息的有价值内容。给定一离散事件集X，它含有N 个事件x1,x2,xN，事件xi 出现的概率记作pi，1pi0且 自信息定义定义 事件xi的自信息，记作I(xi),定义为 注意：自信息的定义没有规定对数的底！对数底为2时，自信息单位为比特（bit）；对数底取为e时，自信息单位为奈特（nat）；对数底为10时，自信息单位为哈特（hart）。,自信息的含义自信息度量了一个随机事件xi未出现时所呈现的不确定性，也度量了该事件xi出现后所给出的信息量。 事件的不确定性越大，则一旦出现给出的信息量也就越大。举例例 计算从英文字母表中任选一个字母时所给出的自信息量。 因为从26个字母中任取一个字母的概率为，所以任选一个字母所给出的信息量为,一、自信息和熵,2、熵自信息描述了事件集X中一个事件出现给出的信息量，整个集X的平均信息量是该集所有事件自信息的统计平均值（数学期望），称作集X的熵。 定义2.2 集X的熵，记作H(X)，定义为 定义中，规定0log0=0。H（X）度量了集X中各个事件未出现时所呈现的平均不确定性(疑义度)，也度量了集X中一个事件出现时所给出的平均信息量。,疑义度：消息的熵同时也可衡量其不确定性（疑义度），即将消息隐藏在密文中时，要破译它所需的明文比特数（即当消息被加密成密文时，为了获取明文需要解密的明文的位数）。,一、自信息和熵,2、熵举例例 给出集按定义有:I(x1) =-log2 1/2=log2 2 =1比特，I（x2）=I（x3）=-log2 1/4=log2 4=2比特。于是一个事件集的熵越大，其不确定性越高。,。,比特。,关于熵的实际例子,例：X可能在下周某天去钓鱼。星期一，星期日共有七种可能（x1，x7），假设各种可能性出现概率相等，则：P（Xi）=1/7，H（x）=7(1/7)log21/7=log21/7= log27同时，H（x）也指出了X中的信息量将消息中所有可能的值进行编码时所需的最少比特数。 2 H(x)= log27 3b1b2b3可以表示一周的7个状态：000 星期日001 星期一110 星期六保留,关于熵的实际例子,甲任意取一个不超过15的整数，由乙来猜，但允许乙提K个问题，甲只回答“是”或者“非”，问K多大时可以确定猜到该数。,解：若令乙猜想作为事件V，V可能有16种结果，假定这16种结果是等概率的，V的熵为：H（V）= log216令事件Ak=U1U2U3Uk为提问k个问题，但Ui的熵不超过log22=1，（因为只有“是”或者“非”），故Ak的熵为不超过k比特，则：log216 klog22 =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=U1U2U3Uk为连续用k次天平的事件， klog23 log225 k （log225）/ log23=2.93故 k最少为3次,继续前面的例子,一种解决方案：25=8+8+9（第一次）天平两端各放8个，如果平衡，则伪币在剩余的9个之中，跳到ii；如果不平衡，则伪币在较轻的8个之中，跳到iii。9=3+3+3（第二次）天平两端各放3个，如果平衡，则从剩下3个中寻找伪币。否则，从较轻的3个中寻找伪币。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） = log2k,2.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空间问题同等困难。指数时间问题,2.3 初等数论,2.3.1 模运算2.3.2 素数2.3.3 最大公因数2.3.4 乘法逆元素2.3.5 Fermat小定理及欧拉函数2.3.6 中国剩余定理2.3.7 二次剩余2.3.8 Legendre（勒让得）符号2.3.9 Jacobi（雅各比）符号2.3.10 生成元2.3.11 有限域中的计算,2.3.1 模运算,同余：如果a = b + kn，k为整数，则a b（mod n）a mod n ：a模n操作，表示a除以n的余数，为 0到n 1之间的整数。例如：(79) mod 12 = 16 mod 12 = 4,模运算（+、 ）满足交换律、结合律和分配律。(a+b) mod n=(a mod n)+(b mod n)mod n(a-b) mod n=(a mod n)-(b mod n)mod n(a*b) mod n=(a mod n)*(b mod n) mod n(a*(b+c) mod n=(a*b mod n)+(a*c mod n) mod n,按模计算原理：对中间结果作模运算与做完了全部运算后再做模运算结果相同。求:1711mod 26=?,按模指数运算：am mod n将指数运算作为一系列乘法运算，每次做一次模运算。例：a8 mod n = (a2 mod n)2 mod n)2 mod n当m不是2的乘方时，将m表示成2的乘方和的形式。例如：25=(11001)2，即25=24+23+20 a25 mod n = (a16 a8 a) mod n = (a2)2)2)2 (a2)2)2 a) mod n = (a2 a)2)2)2 a) mod n适当存储中间结果，则只需6次乘法：(a2mod n) a)mod n)2mod n)2mod n)2mod n) a)mod n,求1711mod26=?,2.3.2 素数,素数（质数）：大于1的整数，只能被1和本身整除。有无穷多个素数。如：2，73，2521，2365347734339，2756839-1,2.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 (mod c)，则 gcd(a,c) = gcd(b,c)这里，gcd(15,36) = gcd(15,6) = gcd(6,3) = 3理论基础:若a=bq+r，则gcd（a,b）=gcd（b,r）,定理：若a=bq+r，则gcd（a,b）=gcd（b,r） 那么：gcd（a,b）=gcd(b, a mod b) until a mod b =0 then b is the result.证明：d=（a,b），d=（b,r）d|(a bq) d|r，d为b,r的公因数；d|d d=hdd|(bq+r) d|a，d为a,b的公因数；d|d d=kd所以 kh=1,由于d,d都为正整数，所以k和h也都为正整数，故： k=h=1；,2.3.4 乘法逆元素,定理：axb mod n有解的充要条件是d|b，其中d=gcd（a，n）。我们关心下列同余式：（b=1时）当b=1时，d=1，即可得：如果gcd(a,n)=1，则ax 1 mod n有解。如果ax 1 mod n有解，则gcd(a,n)=1。,2.3.4 乘法逆元素,求x，满足 (a x) mod n = 1, 即 x a-1(mod n)当a与n互素时, 方程 x a-1(mod n) 有唯一解；当a与n不互素时, 此方程无解。如果n为素数，则从1到n-1的任意整数都与n互素，即在1到n-1之间都恰好有一个关于模n的乘法逆元。求乘法逆元：扩展的Euclid算法例：求5关于模14的乘法逆元素辗转相除：14 = 5 2 + 4 5 = 4 + 1逆推：1 = 5 - 4 = 5 - （14 - 5 2）= 5 3 - 14 因此，5关于模14的乘法逆元为3。,练习,练习：求17关于模26的乘法逆元素。,答案：2326 = 17 + 9 1 = 9 - 817 = 9 + 8 = 9 - (17 - 9)9 = 8 + 1 = 9 2 - 17 = (26 - 17) 2 - 17 = 26 2 - 17 3 = 17 (-3) + 26 2(17 23 - 26 15),2.3.5 Fermat小定理及欧拉函数,Fermat小定理：如果m为素数，a不能被m整除，则 am-1 1 (mod m)n为正整数，Zn=0，1，2，n-1为模n的集合，Zn为模n的完全剩余集。Zn*=a Zn| gcd(a,n)=1称为模n的简化剩余集。（n）=| Zn*|, 表示Zn*元素的个数。称为欧拉函数, （n）为n的欧拉函数值。 如果n是素数，则(n) = n-1设n = p1r1 p2r2 pmrm, 其中p1, p2, ,pm是n的素数因子, 则(n) = n (1-1/p1) (1-1/p2) (1-1/pm)=(n/ (p1 p2 pm) (p1-1) (p2-1) (pm-1) (8)=？,如果n = pq，其中p和q为素数，则(n)= (p 1)(q 1)。 例：n=15,求(15).解：Zn=0，1，2，3，4，14Zn*=1，2，4，7，8，11，13，14，因此 (15)=815=3*5 （15）= (3-1)*(5-1)=8 ,欧拉扩展的Fermat小定理,欧拉扩展的Fermat小定理：如果gcd(a,n) = 1，则 a(n) mod n = 1。即：如果gcd(a,n) = 1，则a*a (n)-1 mod n=1即a关于mod n的乘法逆元素为a (n)-1 再求：17关于模26的乘法逆元素？,中国剩余定理-韩信点兵,秦朝末年，楚汉相争。一次，韩信将1500名将士与楚王大将李锋交战。苦战一场，楚军不敌，败退回营，汉军也死伤四五百人，于是韩信整顿兵马也返回大本营。当行至一山坡，忽有后军来报，说有楚军骑兵追来。只见远方尘土飞扬，杀声震天。汉军本来已十分疲惫，这时队伍大哗。韩信兵马到坡顶，见来敌不足五百骑，便急速点兵迎敌。他命令士兵3人一排，结果多出2名；接着命令士兵5人一排，结果多出3名；他又命令士兵7人一排，结果又多出2名。韩信马上向将士们宣布：我军有1073名勇士，敌人不足五百，我们居高临下，以众击寡，一定能打败敌人。汉军本来就信服自己的统帅，这一来更相信韩信是“神仙下凡”、“神机妙算”。于是士气大振。一时间旌旗摇动，鼓声喧天，汉军步步进逼，楚军乱作一团。交战不久，楚军大败而逃。,我国古代数学名著孙子算经中，提出了闻名于世的“物不知数”问题。原文是：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？”,这个问题的解法,()“笨”算法 原来的问题题意是：求一数，三除余二，五除余三，七除余二。因为以3除余2，以7除余2的数，所以以21除也余2而23是以3，7除余2的最小数，它刚好又是以5除余3的数。,()古代的口诀解法 程大位著的算法统宗，对“物不知其数”的问题的解答方法用下面的口诀标出：“三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知。”,“三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知。”,它的意义是：以70乘用3除的余数2，21乘用5除的余数3，15乘用7除的余数2，然后总加起来。如果它大于105，则减105，若仍大再减，最后得出来的正整数就是答案了。,它的形式是：270321215=233，两次减去105，得23，这就是答案了。,70，21，15的性质,70是用3除余1，5与7都除得尽的数，所以70a是一个用3除余a而5与7除都除得尽的数。21是用5除余1，3与7除得尽的数，所以21b是用5除余b，而3与7除得尽的数。同理，15c是用7除余c而3与5除得尽的数。因而：70a21b15c 是一个3除余a，5除余b，7除余c的数，也就是可能的解答之一，但可能不是最小的。这数加减105后都仍然有同样的性质，所以可以多次减去105而得到答案。,“三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知”。用现代术语翻译，其口诀实际上是：N=70r121r215r3-105p，其中ri(i=1，2，3)分别是余数，p是使N0的任一整数。,推广开来,若某数N分别被称为定母的d1，d2，d3，dn除得的余数为r1，r2，r3，rn，则N=k1r1k2r2k3r3knrn-pq，其中k1是d2，d3，d4，dn的公倍数，且被d1除余1；k2是d1，d3，d4，dn的公倍数，且被d2 除余1；kn是d1，d2，d3，dn-1的公倍数，且被dn除余1p是任意整数，q是d1，d2，d3，dn的最小公倍数。,上式的关键在于“求一”，即求“一个数的多少倍除以另一数，所得余数为1”的方法，也即求出公式中的“ki”,这个方法的研究，是由我国宋代著名数学家秦九韶(约12021261)在其名著数书九章一书中完满解决的。他把它称作“大衍求一术”。类似的理论成果，在欧洲直到18，19世纪才由著名数学家欧拉和高斯获得，最早出现在高斯1801年出版的算术研究一书里。而这，已是秦九韶之后500多年的事了。因而，上述成果被称为“中国剩余定理”，或“孙子定理”。,思考?,“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩四。问物几何？”（70*2+21*3+15*4）mod 3*5*7=?=53,2.3.6 中国剩余定理,定理：如果n的素数因子分解式为p1p2 pt，则一组方程 (x mod pi）= ai，其中i = 1,2,t，有唯一解x，其中x小于n（其中某些pi可能相等）。例：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？x mod 3 = 2x mod 5 = 3x mod 7 = 2,定理：令d1，d2，,dt为两两互素，并令n=d1d2dt，则 x mod di xi (I=1, t)在0，n-1范围内有公共解x：x= mod n其中：mi=n/di，yi=mi-1 mod di,解法：令a1=2，a2=3，a3=2，p1=3，p2=5，p3=7，n=p1 p2 p3=105，M1=n/p1=35, M2=n/p2=21, M3=n/p3=15求解 35 x1 mod 3=1, 得x1=2求解 21 x2 mod 5=1, 得x2=1求解 15 x3 mod 3=1, 得x3=1则 x = (M1 x1 a1+M2 x2 a2+M3 x3 a3 ) mod n = (35 2 2+21 1 3+15 1 2) mod 105 = 233 mod 105 = 23,2.3.7 二次剩余,定义：设整数n1。对于aZn*，如果存在x Zn ，满足x2a（modn）有解，则称a为模n的二次剩余（或平方剩余）；否则，称a为模n二次非剩余（或平方非剩余）。用QRn表示模n的二次剩余集合，用QNRn表示模n的二次非剩余集合。,例如： 322（mod7），则2 QR7求QR7 =？ QNR7 =？,2.3.8 Legendre（勒让德）符号,记为L(a,p)，叫做a模p的勒让德符号。其中a为任意整数，p为大于2的素数。定义：L(a,p) = 0，如果a能被p整除；L(a,p) = 1，如果a是模p的二次剩余；L(a,p) = -1，如果a是模p的非二次剩余；计算：L(a,p) = a(p-1)/2 mod p计算法则（略）,计 算,L(1,7) =？L(2,7) =？L(3,7) =？L(4,7) =？L(5,7) =？L(6,7) =？,2.3.9 Jacobi（雅各比）符号,记为J(a,n)，是Legendre符号的扩展，其中a为任意整数，而n为任意奇数。定义：J(a,n)只对n为奇数时有意义J(0,n)=0如果n为素数，且n|a，则J(a,n)=0如果n为素数，且a是模n的二次剩余，则J(a,n) = 1如果n为素数，且a是模n的非二次剩余，则J(a,n) = -1如果n是合数，则J(a,n)=J(a,p1)J(a,p2)J(a,pm)，其中将n因数分解为p1p2pm,Jacobi符号的计算（P19）Blum整数：若p和q为两个素数，且都与3模4同余，则n = pq称为Blum整数。若n为Blum整数，则每个模n的二次剩余恰好有4个平方根，其中一个也是一个二次剩余，称为原平方根。例如，139的模437的原平方根为24，另三个平方根为185，252和413。,2.3.10 生成元,定义：如果p为素数，g小于p，如果对每个b从1到p-1，存在a，使ga b (mod p)，则g为模p的生成元。或者说g是关于模p的原根。 例：p=11，2为模11的生成元 P20,生成元的测试,测试一个数是否为生成元不太容易。如果知道p 1的因数分解式，就很容易。令q1，q2，qn为p 1的素数因子，且q1，q2，qn两两不同，则测试给定数g是否为p的生成元时，对所有的q = q1，q2，qn计算 g（p - 1）/ q mod p若对某个q值，g（p - 1）/ q mod p为1，则g不是生成元。反之，则是生成元。,生成元的测试,测试3是否为模11的生成元.,测试如下：即p=11，则p-1=10=2*5g（p - 1）/ q mod p=？3（11-1）/2 mod 11=13（11-1）/5 mod 11=9,所以3不是模11的生成元。,伽罗瓦Galois, Evariste （1811-1832）,Galois（伽罗瓦）一共参加了2次Ecole Polytechnique（巴黎理工大学）的考试第一次，由于口试的时候不愿意做解释，并且显得无理，结果被据了。他当时大概十七八岁，年轻气盛，大部分东西的论证都是马马虎虎，一般懒的写清楚,并且拒绝采取考官给的建议。第二次口试的时候，逻辑上的跳跃使考官Dinet感到困惑，后来Galois感觉很不好，一怒之下，把黑板擦掷向Dinet,并且直接命中。最后和Galois决斗的那个人，是当时法国最好的枪手，Galois的勇气令人钦佩。两个人决斗的时候，相距25步，Galois被击中了腹部。,伽罗瓦(Evariste Galois)1811年10月25日生于巴黎附近的一个小城。1829年他两次投考巴黎理工大学，却因思想激进，两次被拒绝录取，最后只好进入高等师范学校学习。1829年5月，17岁的他写出了关于五次方程的代数解法的论文，论文中首次引入“群”的概念。他把论文寄给柯西，请他交给法兰西科学院审查。柯西对此根本不屑一顾，把这个中学生的文章给弄丢了。1830年2月伽罗瓦再次将他的研究成果写成一篇详细的论文，寄给科学院秘书傅立叶，希望能得到数学大奖，不料当年5月傅立叶病死，伽罗瓦的文稿再次被丢失。1831年伽罗瓦第三次将论文送交法国科学院。泊松院士看了4个月，最后在论文上批道：“完全无法理解”。泊松的不公正评价，使他受到很大打击。这些大数学家的傲慢和自大，使得伽罗瓦的理论被埋没了将近50年。,伽罗瓦因为政治激进，被阴谋的政客们用一件小事怂恿和一个军官决斗。在决斗前一个晚上，他急切地写着他的遗言。想在死亡来临之前尽快把他的思想中那些有意义的东西写出来。他不时中断，在纸边空白处写上“我没有时间，我没有时间。”接着伽罗瓦又写下一个潦草的大纲。他在天亮之前那最后几个小时写出的东西，一劳永逸地给一个折磨了数学家几个世纪的难题找到了真正的答案，开创了数学上的一个重要的分支群论。伽罗瓦在决斗中被打成重伤，死在家里，年仅21岁。,年，也就是伽罗瓦死后年，他的遗稿才得以发表。随着数学的发展和时间的推移，伽罗瓦研究成果的重要意义愈来愈为人们所认识。他的最主要成就是提出了群的概念，用群论彻底解决了根式求解代数方程的问题，而且由此发展了一整套关于群和域的理论，为了纪念他，人们称之为伽罗瓦理论。伽罗瓦理论对近代数学的发展产生了深远影响，它已渗透到数学的很多分支中。,2.3.11 有限域中的计算,有限域：元素个数有限的域，也叫伽罗瓦（Galois）域。在有限域中，非0数的加、减、乘、除都有定义。加法单位元是0，乘法单位元是1，每个非0元素都有一个唯一的乘法逆元。有限域中运算满足交换律、结合律和分配律。有限域中元素个数为素数或素数的乘方：设p为素数，则有限域可记为GF(p)或GF(pn)。,不可约多项式：一个多项式如果除了1和本身外，不能分解成其他多项式的乘积形式，则成为不可约多项式。本原多项式：一个有限域内的生成元多项式，其系数是互素的。在GF(qn)中，所有运算都是模p(x)的运算，其中p(x)是n阶不可约多项式。,一般研究GF（2n），如GF（25）：a(x)=x4+x3+1表示11001。若p（x）不能分解为次数小于n的多项式之积，则p（x）称既约多项式。二元多项式系数的运算：（U +V）mod 2 =U VUV = U VUV = U V,例：GF（25）：a(x)= x4+x2+1,b(x)= x3+ x2ab=10101+01100=11001例：a=101，p（x）=x+x+1，GF（2），求（aa）mod p（x）aa=10001，p（x）= x+x+1=1011（aa）mod p（x）=10001 mod 1011 = 111 =x+x+1,2.4 因数分解,对一个数进行因数分解，是指找出这个数的素数因子。60=2*2*3*5252601=41*61*1012113-1=3391*23279*现代因数分解的一些算法P21,2.5 素数的产生,2.5.1 Solovay-Strassen方法2.5.2 Lehmann法2.5.3 Rabin-Miller法2.5.4 实际应用2.5.5 强素数,2.5.1 Solovay-Strassen方法,用Jacobi符号来测试p是否为素数：（1）选择一个随机数a，ap；（2）如果gcd(a,p)1，则p是合数，停止检测；（3）计算i=a(p-1)/2 mod p； =L(a,p)?（4）计算Jacobi符号J(a,p)；（5）如果i J(a,p)，则p不是素数；（6）如果i= J(a,p)，则p不是素数的概率小于50%。对t个不同的随机数a，重复进行这个测试。能通过所有t个测试的奇数是合数的概率小于1/2t。,2.5.2 Lehmann法,测试p是否为素数：（1）选择一个小于p的随机数a；（2）计算a(p-1)/2 mod p；（3）如果a(p-1)/2 mod p 1或1( mod p) ，则p不是素数；（4）如果a(p-1)/2 mod p 1或1( mod p) ，则p不是素数的概率小于50%。,2.5.3 Rabin-Miller法,选择一个随机数p，进行测试。计算b，其中b是能整除p-1的2的次方数（即2b是指整除p-1的最大的2的幂），然后计算m，使得p=1+2b*m。（1）选择一个随机数a，使a小于p；（2）令i=0，Z=am mod p；（3）如果Z=1，或Z=p-1，则p可能是素数，通过了检测；（4）如果i0，且Z=1，则p不是素数；（5）令i=i+1，如果ib且Z p-1，令Z=Z2 mod p，返回第（4）步。如果Z =p-1，则p通过检测，可能是素数；（6）如果i=b且Z p-1，则p不是素数。一个奇合数通过t次测试的概率小于1/4t。,2.5.4 实际应用,（1）产生一个n位随机数p（n位二进制）；（2）将最高位和最低位置为1；（3）检查p是否能被小素数整除：3，5，7，11，等等。许多实际应用中都用小于256地所有素数去除p；（4）对于随机数a，进行Rabin-Miller测试，如果p通过了，则产生另一个随机数a，再进行测试。选择值小一些的a可以令计算更快。做5次测试，如果p没通过其中的一次，则产生另一个p再测试。,2.5.5 强素数,强素数p,q：能令乘积n难以用特定的因数分解算法进行因数分解的素数。性质：p-1和q - 1的最大公因数很小p-1和q-1都有大素数因子，记为p，q；p -1和q-1都有大素数因子；p +1和q+1应该都有大素数因子；(p-1)/2和(q-1)/2都是素数。,2.6 有限域内的离散对数,求x，使ax b (mod n)当n很大时，这是一个困难的问题并非所有的离散对数问题都有解密码学中常用的离散对数：GF(p)的乘法群GF(2n)的乘法群EC(F),2.7 单向哈希函数,定义：一个单向哈希函数H(M)，操作一个任意长度的消息M，返回一个固定长度的值h。h = H(M) 。性质：给定M，很容易计算h；给定h，很难计算M，使H(M)=h；给定M，很难找到另一个消息M，使H(M)=H(M)。,MD5算法(P27),输入：将明文分成512位的块,再将其分成16个32位的子块M0M15输出：4个32位的块（a,b,c,d），将这四个32位分组级联后将生成一个128位散列值。,消息填充,在md5算法中，首先需要对信息进行填充，使其字节长度对512求余的结果等于448。因此，信息的字节长度（bits length）将被扩展至n*512+448，即n*64+56个字节（bytes），n为一个正整数。填充方法：在信息的后面填充一个1和无数个0，直到满足上面的条件时才停止用0对信息的填充。然后，在在这个结果后面附加一个以64位二进制表示的填充前信息长度。经过这两步的处理，现在的信息字节长度=n*512+448+64=(n+1)*512，即长度恰好是512的整数倍。这样做的原因是为满足后面处理中对信息长度的要求。,md5中有四个32位被称作链接变量（chaining variable）的整数参数，他们分别为：A=0 x01234567，B=0 x89abcdef，C=0 xfedcba98，D=0 x76543210。 当设置好这四个链接变量后，就开始进入算法的四轮循环运算。循环的次数是信息中512位信息分组的数目。 将上面四个链接变量复制到另外四个变量中：A到a，B到b，C到c，D到d。,主循环有四轮（md4只有三轮），每轮循环都很相似。每轮进行16次操作。每次操作对a、b、c和d中的其中三个作一次非线性函数运算，然后将所得结果加上第四个变量，文本的一个子分组和一个常数。再将所得结果向右环移一个不定的数，并加上a、b、c或d中之一。最后用该结果取代a、b、c或d中之一。,以下是每次操作中用到的四个非线性函数（每轮一个）。 f(x,y,z) =(x&y)|(x)&z) g(x,y,z) =(x&z)|(y&(z) h(x,y,z) =xyz i(x,y,z)=y(x|(z) （&是与，|是或，是非，是异或）,每圈的操作函数,假设mj表示消息的第j个子分组（从0到15），ff(a,b,c,d,mj,s,ti) 用于第一圈表示a=b+(a+f(b,c,d)+mj+ti) s)gg(a,b,c,d,mj,s,ti)用于第二圈表示 a=b+(a+g(b,c,d)+mj+ti)s)hh(a,b,c,d,mj,s,ti)用于第三圈表示a=b+(a+h(b,c,d)+mj+ti)s)ii(a,b,c,d,mj,s,ti) 用于第四圈表示a=b+(a+i(b,c,d)+mj+ti)s),每圈的具体操作P29,其中在第i步中，ti是4294967296*abs(sin(i)的整数部分，i的单位是弧度。(4294967296等于2的32次方)如何计算？1弧度=多少度？T1=?T16=?T24=?T32=?我们把长度等于半径的弧所对的圆心角叫做1弧度的角。,所有这些完成之后，将a、b、c、d分别加上a、b、c、d。然后用下一分组数据继续运行算法，最后的输出是a、b、c和d的级联。参考P28图2.6,验证自己的函数正确性,md5 () = d41d8cd98f00b204e9800998ecf8427e md5 (a) = 0cc175b9c0f1b6a831c399e269772661 md5 (abc) =900150983cd24fb0d6963f7d28e17f72 md5 (message digest) =f96b697d7cb7938d525a2f31aaf161d0 md5 (abcdefghijklmnopqrstuvwxyz) = c3fcd3d76192e4007dfb496cca67e13b md5(abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz0123456789) = d174ab98d277d9f5a5611c2c9f419d9f,