网络安全理论与应用第三章

1、第三章 公钥密码体制网络平安实际与运用卫文学信息科学与工程学院2003.3 山东科技大学.3.1 数论导引1 、素数和数的互素 除数(因子)的概念：设z为有全体整数而构成的集合，假设 b0且 a, b, m属于z 使得a=mb,此时称b整除a.记为ba,还称b为a的除数(因子).注:假设a=mb+r且0r1被称为素数是指p的因子仅有1,-1,p,-p。.算术根本定理： 任何一个不等于0的正整数a都可以写成独一的 表达式aP11P22Ptt ， 这里P1P2P3Pt是素数，其中i0最大公约数： 假设a,b,cz，假设ca，cb，称c是a和b的公约数。正整数d称为a和b的最大公约数，假设它满足d是

2、a和b的公约数。对a和b的任何一个公约数c有cd。注：1*. 等价的定义方式是： gcda,bmaxk ka，kb 2*假设gcda,b=1，称a与b是互素的。.2 、模 算术 全体整数构成的集合对整数的加法和乘法的两种运算是封锁的且满足算术运算的一切定律，此时我们称整数集合z为整数环。整数环z对除法运算不封锁。带余除法：az,0，可找出两个独一确定的整数q和r,使a=qm+r, 0=r1分成一些两两不交的等价类。3*.整数模m同余类共有m个，他们分别为mk+0,mk+1, mk+2,mk+(m-1); kz，每一个算一类，每一类都可以选一个代表元，普通选这一类中的最小的非负整数。于是称0,1

3、,2,m-1为规范完全剩余系。Z模12的规范剩余系Z12为：0,1,2,3,4,5,6,7,8,9,10,11.4*. 对于某个固定模m的同余式可以象普通的等式那样相加相减和相乘： (1)a(mod m)b(mod m)=(ab)(mod m) (2)a(mod m)*b(mod m)=a*b(mod m)例子.经过同余式演算证明5601是56的倍数。 解： 留意53=12513(mod56) 于是有561691(mod56) 对同余式的两边同时升到10次幂， 即有56560-1。. 证明：2231是47的倍数： 留意26=64 - 30(mod47),于是 223=(26)325=(26 2

4、6)26 25 900*(-30)*(32) mod(47) (7)(-30)*(32) (mod47) 1(mod47) 于是有 47223-1 定理：(消去率)对于abacmod m来说，假设 gcd(a,m)1那么bc(mod m)5*.一次同余方程axb(mod m)这个方程有没有解，相当于问有没有那样一个整数x，使得对于某个整数y来说，有ax+my=b 定理：如记gcd (a,m)=d,那么同余方程axb(mod m)有解的充分必要条件是db。当这个条件满足时，恰有d个模m同余类中的整数是上述方程的解。 证明：略。从ax+my=b入手.6*.加法逆元与乘法逆元 对加法而言，对每一x，

5、都有一y，使得x+y0 mod m 如：对于2，有6，使得2+60 mod 8， 称y为x的负数，也称加法逆元。 假设(a+b)(a+c)mod n，那么bc mod n，称为加法的可约率。 然而类似的性质对乘法不一定成立。如6x36x72mod 8，但37mod 8。缘由是6乘0到7得到的8个数仅为Z8的一部分。即假设将用6乘Z8中每一数看作Z8到Z8的映射的话， Z8中至少有两个数映射到同一个数，因此映射是多到一的，所以对6来说，没有独一的乘法逆元。但对5来说，5X5 1mod 8，因此5有乘法逆元5，不仅如此，凡是与8互素的几个数1，3，5，7都有乘法逆元。.6*.加法逆元与乘法逆元 这

6、一结论可以推行到任一Zn ，设a1时，它的值(n)等于比n小而与n互素的正整数的个数。 以n24为例，比24小而与24 互素的正整数为：1，5，7，11，13，17，19，23因此，我们有(24)8。 易见，假设p为素数，那么(p)p1。注：1*.假设p，q都为素数且pq，此时有(pq)(p)(q)=p1q1证明：思索zpq剩余类的集合是0，1，2，pq-1集合中与pq不互素的元素子集为p,2p,(p-1)q和子集 q,2q,(p-1)q以及0，于是假设设npq，有 (n)=pq-(q-1)+(p-1)+1 =(p-1)(q-1)=(p)(q) 例：(21)=(3*7)=(3)(7)=2*6=

7、12. 欧拉定理Euler： 假设整数a与整数n互素，那么a(n)1(mod n)证明：设小于n而和n互素的正整数为 r1,r2,r3,r(n)(1) 他们是模n两两互不同余的。对每一个定数i来说，由于a和ri都与n互素，所以gcd(ari,n)=1， 所以ari同余于1中的某个ri即ariri (mod n)，1=i=(n) 并且当ij时有ari arj(mod n).于是, 为 的置换.所以有 由(ri,n)=1, 所以.4 中国剩余定理 在中国数学史上，广泛流传着一个“韩信点兵的故事： 韩信是汉高祖刘邦手下的大将，他英勇善战，智谋超群，为汉朝的建立了卓绝的功绩。听说韩信的数学程度也非常高

8、超，他在点兵的时候，为了保住军事，不让敌人知道本人部队的实力，先令士兵从1至3报数，然后记下最后一个士兵所报之数；再令士兵从至报数，也记下最后一个士兵所报之数；最后令士兵从1至7报数，又记下最后一个士兵所报之数；这样，他很快就算出了本人部队士兵的总人数，而敌人那么一直无法弄清他的部队终究有多少名士兵。 .4 中国剩余定理例子：孙子算经今有物不知其数。三三数之余二；五五数之余三；七七数之余二。问物几何？答曰：二十三。232*70+3*21+2*15(mod 105)口诀：三人同行七十稀，五树梅花廿一枝， 七子聚会月正半，除百零五便得知。问，70，21，15如何得到的？原问题为：求解同余方程组.留

9、意：假设x0为上述同余方程组的解，那么x0=x0+105*k(kz) 也为上述同余方程组的解。有意义的是，解题口诀提示我们先解下面三个特殊的同余方程组(1) (2) (3)的特殊解 =? =? =?以方程1为对象，相当于解一个这样的同余方程 35y1(mod 3)，为什么呢？缘由是，从1的模数及条件知，x应是35的倍数，于是可以假设x35y有. 35y1(mod 3)相当于 /35y=33y+2y 2y1 (mod 3) /同乘2的乘法逆元2-1 解出y=2mod 3 /y=3k+2 于是x35*2 70(mod 105) /x=35y=105k+70 类似地得到2、3方程的模105的解21、

10、15。于是有得. 孙子算经的“物不知数”题虽然开创了一次同余式研究的先河，但由于题目比较简单，甚至用试猜的方法也能求得，所以尚没有上升到一套完整的计算程序和理论的高度。真正从完整的计算程序和理论上解决这个问题的，是南宋时期的数学家秦九韶。 秦九韶在他的数书九章中提出了一个数学方法“大衍求一术”，系统地论述了一次同余式组解法的基本原理和一般程序。.中国剩余定理：设自然数m1,m2,mr两两互素，并记N=m1m2mr，那么同余方程组在模N同余的意义下有独一解。.证明：思索方程组，(1=i=r)由于诸mi(1=i=r)两两互素，这个方程组作变量交换，令x=(N/mi)*y，方程组等价于解同余方程：

11、(N/mi)y1(mod mi).假设要得到特解yi,只需令xi=(N/mi)yi那么方程组的解为x0=b1x1+ b2x2+ + brxr (mod N)模N意义下独一。例一：由以下方程组求x x 1mod 2 x 2mod 3 x 3mod 5 x 5mod 7解：M=2*3*5*7=210 M1=105 M2= 70 M3=42 M4=30 再求得M1-1MOD 2 1，M2-1 MOD 3 1，M3-1 MOD 53 M4-1MOD 7 4 所以X MOD 210 = (1*105*1+2*70*1+3*42*3+5*30*4) MOD 210 173 或写为X 173 MOD 210

12、. 从到秦九韶(1247年 )对一次同余式问题的研讨成果，在世纪中期开场遭到西方数学界的注重。年，英国传教士伟烈亚力向欧洲引见了的“物不知数题和秦九韶的“大衍求一术；年，德国人马蒂生指出，中国的这一解法与西方世纪高斯(1801年)中关于一次同余式组的解法完全一致。从此，中国古代数学的这一发明逐渐遭到世界学者的瞩目，并在西方数学史著作中正式被称为“中国剩余定理。 .3.2 公钥密码学问题的提出1 、密钥管理量的困难 传统密钥管理两两分别用一对密钥时那么n个用 户需求C(n,2)=n(n-1)/2个密钥当用户量增大时密 钥空间急剧增大如: n=100 时C(100,2)=4,995 n=5000时

13、C(5000,2)=12,497,5002 、数字签名的问题 传统加密算法无法实现抗抵赖的需求.单钥加密模型.1、什么是公钥密码体制 公钥密码又称为双钥密码和非对称密码，是1976年由Diffie和Hellman在其“密码学新方向一文中提出的，见划时代的文献： W.Diffie and M.E.Hellman, New Directrions in Cryptography, IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976, PP.644-654 单向陷门函数是满足以下条件的函数f： (1) 给定x，计算y=f(x)

14、是容易的； (2) 给定y, 计算x使y=f(x)是困难的。 (所谓计算x=f-1(Y)困难是指计算上相当复杂，已无实践意义。). (3)存在，知 时,对给定的任何y，假设相应的x存在，那么计算x使y=f(x)是容易的。 注：1*. 仅满足(1)、(2)两条的称为单向函数；第(3)条称 为陷门性， 称为陷门信息。 2*. 当用陷门函数f作为加密函数时，可将f公开，这 相当于公开加密密钥。此时加密密钥便称为公开 钥，记为Pk。 f函数的设计者将 严密，用作解 密密钥，此时 称为钥匙，记为Sk。由于加 密函数时公开的，任何人都可以将信息x加密成 y=f(x)，然后送给函数的设计者当然可以经过 不平

15、安信道传送；由于设计者拥有Sk，他自然 可以解出x=f-1(y)。 3*.单向陷门函数的第(2)条性质阐明窃听者由截获的 密文y=f(x)推测x是不可行的。.2、算法代表背包算法 RSA 椭圆曲线ECC.3 RSA公钥算法 RSA公钥算法是由Rivest,Shamir和Adleman在1978年提出来的见Communitions of the ACM. Vol.21.No.2. Feb. 1978, PP.120-126)该算法的数学根底是初等数论中的Euler欧拉)定理，并建立在大整数因子的困难性之上。 .例子：假设Bob选择了p=101和q113，那么，n=11413, (n)=10011

16、211200；然而1120026527，一个正整数e能用作加密指数，当且仅当e不能被2，5，7所整除现实上，Bob不会分解(n)，而且用辗转相除法欧式算法来求得e，使e, (n)=1)。假设Bob选择了e=3533，那么用辗转相除法将求得： d=e -1 6597(mod 11200), 于是Bob的解密密钥d=6597. Bob在一个目录中公开n=11413和e=3533, 现假设Alice想发送明文9726给Bob，她计算： 97263533(mod 11413)=5761. 且在一个信道上发送密文5761。当Bob接纳到密文5761时，他用他的解密指数私钥d6597进展解密：576165

17、97mod 11413)=9726 注：RSA的平安性是基于加密函数ek(x)=xe(mod n)是一个单向函数，所以对的人来说求逆计算不可行。而Bob能解密的陷门是分解n=pq，知 (n)=(p-1)(q-1)。从而用欧氏算法解出解密私钥d.4、RSA密码体制的实现实现的步骤如下：Bob为实现者 (1) Bob寻觅出两个大素数p和q (2) Bob计算出n=pq和 (n)=(p-1)(q-1). (3) Bob选择一个随机数e(0e (n)，满足e， (n)1 (4) Bob运用辗转相除法计算d=e-1(mod (n)p64 (5) Bob在目录中公开n和e作为她的公开钥。 密码分析者攻击R

18、SA体制的关键点在于如何分解n。假设分解胜利使n=pq，那么可以算出(n)p-1)(q-1)，然后由公开的e，解出的d。猜测：攻破RSA与分解n是多项式等价的。然而，这个猜测至今没有给出可信的证明！. 于是要求：假设使RSA平安，p与q必为足够大的素数，使分析者没有方法在多项式时间内将n分解出来。建议选择p和q大约是100位的十进制素数。 模n的长度要求至少是512比特。EDI攻击规范运用的RSA算法中规定n的长度为512至1024比特位之间，但必需是128的倍数。国际数字签名规范ISO/IEC 9796中规定n的长度位512比特位。 为了抵抗现有的整数分解算法，对RSA模n的素因子p和q还有

19、如下要求： (1) |p-q|很大，通常 p和q的长度一样； (2) p-1 和q-1分别含有大素因子p1和q1 (3) P1-1和q1-1分别含有大素因子p2和q2 (4) p+1和q+1分别含有大素因子p3和q3.RSA算法中的计算问题(P75).5、RSA签名方案签名的根本概念传统签名手写签名的特征：1一个签名是被签文件的物理部分；2验证物理部分进展比较而到达确认的目的。(易伪造)3不容易忠实地“copy!定义： (数字签名方案一个签名方案是有签署算法与验证算法两部分构成。可由五元关系组P,A,K,S,V来刻化：(1) P是由一切能够音讯(messages)所构成的有限集合；(2) A是

20、一切能够的签名的有限集合；(3) k为有限密钥空间，是一些能够密钥的有限集合；(4) 恣意k K，有签署算法Sigk S且有对应的验证算法 VerkV,对每一个 Sigk:p A 和Verk:PA 真，假.满足条件：恣意x P,y A.有签名方案的一个签名：Ver(x,y)= 注：1*.恣意kK, 函数Sigk和Verk都为多项式时间函数。2*.Verk为公开的函数，而Sigk为函数。3*.假设坏人如Oscar)要伪造Bob的对X的签名，在计算上是不能够的。也即,给定x，仅有Bob能计算出签名y使得Verk(x,y)真。4*.一个签名方案不能是无条件平安的，有足够的时间，Oscar总能伪造Bob的签名。RSA签名：n=pq,P=A=Zn,定义密钥集合K=(