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

第三章公钥密码体制网络安全理论与应用卫文学信息科学与工程学院2003.3山东科技大学3.1数论导引1、素数和数的互素除数(因子)的概念：设z为有全体整数而构成的集合，若b≠0且a,b,m属于z使得a=mb,此时称b整除a.记为b∣a,还称b为a的除数(因子).注:若a=mb+r且0rb,此时b不整除a,记为b|a素数(质数)的概念:整数p1被称为素数是指p的因子仅有1,-1,p,-p。§算术基本定理：任何一个不等于0的正整数a都可以写成唯一的表达式a＝P1α1P2α2…Ptαt，这里P1P2P3…Pt是素数，其中αi0§最大公约数：若a,b,c∈z，如果c∣a，c∣b，称c是a和b的公约数。正整数d称为a和b的最大公约数，如果它满足d是a和b的公约数。对a和b的任何一个公约数c有c∣d。注：1*.等价的定义形式是：gcd（a,b）＝max{k∣k∣a，k∣b}2*．若gcd（a,b）=1，称a与b是互素的。2、模算术全体整数构成的集合对整数的加法和乘法的两种运算是封闭的且满足算术运算的所有定律，此时我们称整数集合z为整数环。整数环z对除法运算不封闭。带余除法：a∈z,0，可找出两个唯一确定的整数q和r,使a=qm+r,0=rm,q和r这两个数分别称为以m去除a所得到的商数和余数。(若r=0则m∣a）整数同余式和同余方程：定义（同余）称整数a模正整数m同余于整数b，并写a≡b（modm）是指m∣a－b,m称为模数。注：1*.m∣a-ba=q1m+r,b=q2m+r即a和b分别除以m有相同的余数。“同余”二字的来源就在于此。2*.相对于某个固定模数m的同余关系，是整数间的一种等价关系。具有等价关系的三点基本性质：自反性：对任意整数a有a≡a（modm）对称性：如果a≡b(modm)则b≡a（modm）传递性：如果a≡b(modm）b≡c（modm）则a≡c(modm)于是，全体整数集合z可按模m（m1）分成一些两两不交的等价类。3*.整数模m同余类共有m个，他们分别为mk+0,mk+1,mk+2,…mk+(m-1);k∈z，每一个算一类，每一类都可以选一个代表元，一般选这一类中的最小的非负整数。于是称[0],[1],[2],…[m-1]为标准完全剩余系。Z模12的标准剩余系Z12为：[0],[1],[2],[3],[4],[5],[6],[7],[8],[9],[10],[11]4*.对于某个固定模m的同余式可以象普通的等式那样相加相减和相乘：(1)a(modm)±b(modm)=(a±b)(modm)(2)a(modm)*b(modm)=a*b(modm)例子.通过同余式演算证明560－1是56的倍数。解：注意53=125≡13(mod56)于是有56≡169≡1(mod56)对同余式的两边同时升到10次幂，即有56∣560-1。证明：223－1是47的倍数：注意26=64≡-30(mod47),于是223=(26)3·25=(26·26)26·25≡900*(-30)*(32)mod(47)≡(7)(-30)*(32)(mod47)≡1(mod47)于是有47∣223-1定理：(消去率)对于ab≡ac（modm）来说，若gcd(a,m)＝1则b≡c(modm)5*.一次同余方程ax≡b(modm)这个方程有没有解，相当于问有没有那样一个整数x，使得对于某个整数y来说，有ax+my=b定理：如记gcd(a,m)=d,则同余方程ax≡b(modm)有解的充分必要条件是d∣b。当这个条件满足时，恰有d个模m同余类中的整数是上述方程的解。证明：略。（从ax+my=b入手）6*.加法逆元与乘法逆元对加法而言，对每一x，都有一y，使得x+y≡0modm如：对于2，有6，使得2+6≡0mod8，称y为x的负数，也称加法逆元。如果(a+b)≡(a+c)modn，则b≡cmodn，称为加法的可约率。然而类似的性质对乘法不一定成立。如6x3≡6x7≡2mod8，但3≡7mod8。原因是6乘0到7得到的8个数仅为Z8的一部分。即如果将用6乘Z8中每一数看作Z8到Z8的映射的话，Z8中至少有两个数映射到同一个数，因此映射是多到一的，所以对6来说，没有惟一的乘法逆元。但对5来说，5X5≡1mod8，因此5有乘法逆元5，不仅如此，凡是与8互素的几个数1，3，5，7都有乘法逆元。6*.加法逆元与乘法逆元这一结论可以推广到任一Zn，设an，gcd(a,n)=1，则a与Zn中任意两个整数b，c相乘，其结果必然不同。因此对1属于Zn，存在x属于Zn，使得a*x≡1modn，即x是a的乘法逆元。记为：x=a-1设p为一素数，则Zp中每一非零元素都与p互素，因此有乘法逆元，类似于加法可约率，有如下乘法可约率：如果(axb)≡(axc)modn且a有乘法逆元，那么对(axb)≡(axc)modn两边都可以乘以a-1，使得b≡cmodn。3Fermat定理和Euler定理§Fermat定理：如果p是素数并且a是正整数,gcd(a,p)=1，那么，ap-1≡1(modp)证明：z*p≡{α∈zp∣(α,p)=1}易见，z*p={1,2,3,…,(p-1)}且因为gcd(a,p）＝1知az*p={[a],[2a],[3a],…,[(p-1)a]}=z*p，原因是az*p内的元素两两不同。他们刚好为1，2，3…，（p－1）的一个排列(证明见P61第一自然段)。所以[a]*[2a]*[3a]*…[(p-1)a]≡1*2*3*…(p-1)(modp)[ap-1]*[(p-1)!]≡1*2*3*…(p-1)(modp)由（(p－1)！，p）＝1，所以ap-1≡1(modp)也可写成：若（a，p）＝1则有ap≡a(modp)§Eulerφ函数定义(Eulerφ函数φ(n))：φ(n)是这样来定义的，当n＝1时，φ(1)＝1；当n1时，它的值φ(n)等于比n小而与n互素的正整数的个数。以n＝24为例，比24小而与24互素的正整数为：1，5，7，11，13，17，19，23因此，我们有φ(24)＝8。易见，若p为素数，则φ(p)＝p－1。注：1*.若p，q都为素数且p≠q，此时有φ(pq)＝φ(p)φ(q)=（p－1）（q－1）证明：考虑zpq剩余类的集合是{0，1，2，…，（pq-1）}集合中与pq不互素的元素子集为{p,2p,…,(p-1)q}和子集{q,2q,…(p-1)q}以及0，于是若设n＝pq，有φ(n)=pq-[(q-1)+(p-1)+1]=(p-1)(q-1)=φ(p)φ(q)例：φ(21)=φ(3*7)=φ(3)φ(7)=2*6=12.§欧拉定理（Euler）：若整数a与整数n互素，则aφ(n)≡1(modn)证明：设小于n而和n互素的正整数为r1,r2,r3…,rφ(n)(1)他们是模n两两互不同余的。对每一个定数i来说，由于a和ri都与n互素，所以gcd(ari,n)=1，所以ari同余于（1）中的某个ri`即ari≡ri`(modn)，1=i=φ(n)并且当i≠j时有ari≡arj(modn).于是,为的置换.所以有由(ri,n)=1,所以)(21,,nrrr)(,21,,nrrr)(mod)(21)(21)(21)(nrrrrrrrrrannnn1),,,()(,21nrrrn)(mod1)(nan4中国剩余定理在中国数学史上，广泛流传着一个“韩信点兵”的故事：韩信是汉高祖刘邦手下的大将，他英勇善战，智谋超群，为汉朝的建立了卓绝的功劳。据说韩信的数学水平也非常高超，他在点兵的时候，为了保住军事机密，不让敌人知道自己部队的实力，先令士兵从1至3报数，然后记下最后一个士兵所报之数；再令士兵从１至５报数，也记下最后一个士兵所报之数；最后令士兵从1至7报数，又记下最后一个士兵所报之数；这样，他很快就算出了自己部队士兵的总人数，而敌人则始终无法弄清他的部队究竟有多少名士兵。4中国剩余定理例子：（孙子算经）今有物不知其数。三三数之余二；五五数之余三；七七数之余二。问物几何？答曰：二十三。23≡2*70+3*21+2*15(mod105)（口诀：三人同行七十稀，五树梅花廿一枝，七子团圆月正半，除百零五便得知。）问，70，21，15如何得到的？原问题为：求解同余方程组2(mod3)3(mod5)2(mod7)xxx注意：若x0为上述同余方程组的解，则x0=x0+105*k(k∈z)也为上述同余方程组的解。有意义的是，解题口诀提示我们先解下面三个特殊的同余方程组(1)(2)(3)的特殊解=?=?=?以方程（1）为对象，相当于解一个这样的同余方程35y≡1(mod3)，为什么呢？原因是，从（1）的模数及条件知，x应是35的倍数，于是可以假设x＝35y有1(mod3)0(mod5)0(mod7)xxx0(mod3)1(mod5)0(mod7)xxx0(mod3)0(mod5)1(mod7)xxx10001000135y≡1(mod3)相当于//35y=33y+2y2y≡1(mod3)//同乘2的乘法逆元2-1解出y=2（mod3）//y=3k+2于是x35*270(mod105)//x=35y=105k+70类似地得到（2）、（3）方程的模105的解21、15。于是有得700012101015100)105(mod2315*221*370*2100201030012232《孙子算经》的“物不知数”题虽然开创了一次同余式研究的先河，但由于题目比较简单，甚至用试猜的方法也能求得，所以尚没有上升到一套完整的计算程序和理论的高度。真正从完整的计算程序和理论上解决这个问题的，是南宋时期的数学家秦九韶。秦九韶在他的《数书九章》中提出了一个数学方法“大衍求一术”，系统地论述了一次同余式组解法的基本原理和一般程序。中国剩余定理：设自然数m1,m2,…mr两两互素，并记N=m1m2…mr，则同余方程组在模N同余的意义下有唯一解。1122(mod)(mod)...............(mod)rrxbmxbmxbm证明：考虑方程组，(1=i=r)由于诸mi(1=i=r)两两互素，这个方程组作变量替换，令x=(N/mi)*y，方程组等价于解同余方程：(N/mi)y≡1(modmi)1110(mod)........0(mod)1(mod)0(mod)...............0(mod)iiirxmxmxmxmxm若要得到特解yi,只要令xi=(N/mi)yi则方程组的解为x0=b1x1+b2x2+…+brxr(modN)模N意义下唯一。例一：由以下方程组求xx1mod2x2mod3x3mod5x5mod7解：M=2*3*5*7=210M1=105M2=70M3=42M4=30再求得M1-1MOD21，M2-1MOD31，M3-1MOD53M4-1MOD74所以XMOD210=(1*105*1+2*70*1+3*42*3+5*30*4)MOD210173或写为X173MOD210从《孙子算经》到秦九韶《数书九章》(1247年)对一次同余式问题的研究成果，在１９世纪中期开始受到西方数学界的重视。１８５２年，英国传教士伟烈亚力向欧洲介绍了《孙子算经》的“物不知数”题和秦九韶的“大衍求一术”；１８７６年，德国人马蒂生指出，中国的这一解法与西方１９世纪高斯《算术探究》(1801年)中关于一次同余式组的解法完全一致。从此，中国古代数学的这一创造逐渐受到世界学者的瞩目，并在西方数学史著作中正式被称为“中国剩余定理”。3.2公钥密