23密码学数学基础

2.3密码学的数学基础密码学的数学基础•学习要点：–了解数论、群论、有限域理论的基本概念–了解模运算的基本方法–了解欧几里德算法、费马定理、欧拉定理、中国剩余定理–了解群的性质–了解有限域中的计算方法1、除数(因子)的概念：设z为由全体整数而构成的集合，若b≠0且a,b,m∈Z使得a=mb,此时称b整除a.记为b∣a,还称b为a的除数(因子).注:若a=mb+r且0rb,此时b不整除a,2、素数(质数)的概念:整数p1被称为素数是指p的因子仅有1,-1,p,-p。§4－1数论§算术基本定理：任何一个不等于0的正整数a都可以写成唯一的表达式a＝P1α1P2α2…Ptαt，这里P1＜P2＜P3…＜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*.相对于某个固定模数m的同余关系，是整数间的一种等价关系。具有等价关系的三点基本性质：自反性：对任意整数a有：a≡a（modm）对称性：如果a≡b(modm)，则b≡a（modm）传递性：如果a≡b(modm）b≡c（modm），则a≡c(modm)于是，全体整数集合z可按模m（m1）分成一些两两不交的等价类。带余除法：a∈z,0，可找出两个唯一确定的整数q和r,使a=qm+r,0=rm,q和r这两个数分别称为以m去除a所得到的商数和余数。(若r=0则m∣a）整数同余：定义：如果amodm=bmodm，则称整数a模正整数m同余于整数b，并写a≡b（modm）是指m∣（a－b）,m称为模数。注：1*.m∣a-ba=q1m+r,b=q2m+r即a和b分别除以m有相同的余数。“同余”二字的来源就在于此。二、模算术3*.对于某个固定模m的同余式可以象普通的等式那样相加、相减和相乘，可结合：(1)[a(modm)±b(modm)]modm=(a±b)(modm)(2)[a(modm)*b(modm)]modm=a*b(modm)(3)[(a*b)modm+(a*c)modm]=[a*(b+c)]modm例子.通过同余式演算证明：（1）560－1是56的倍数（2）223－1是47的倍数。解：注意53=125≡13(mod56)于是有56≡169≡1(mod56)对同余式的两边同时升到10次幂，即有56∣560-1。同理,注意到26=64≡17(mod47),于是223=(26)3·25=(26·26)26·25≡289*(17)*(32)mod47≡7*17*32(mod47)≡25*32(mod47)≡1(mod47)于是有47∣223-1定理：(消去律)对于ab≡ac（modm）来说，若gcd(a,m)＝1则b≡c(modm)•例如1：附加条件不满足的情况•6×3=18≡2mod8•6×7=42≡2mod8•但3≡7mod8•例如2：附加条件满足的情况5×3＝15≡7mod8•5×11=55≡7mod8•3≡11mod8扩展的欧几里德算法描述•ExtendedEUCLID(d,f)：•1）(X1,X2,X3)←(1,0,f)；(Y1,Y2,Y3)←(0,1,d)•2）如果Y3=0返回X3=gcd(d,f)；无逆元•3）如果Y3=1返回Y3=gcd(d,f)；Y2=d-1modf•4）Q=max_int(X3/Y3)•5）(T1,T2,T3)←(X1-Q·Y1,X2-Q·Y2,X3-Q·Y3)•6）(X1,X2,X3)←(Y1,Y2,Y3)•7）(Y1,Y2,Y3)←(T1,T2,T3)•8）回到2）例：求gcd(20,117)和20-1mod11711701171(*117)0(*20)020200(*117)1(*20)11720171-517203-1617326-35231-741Format定理§Format定理：如果p是素数并且a是不能被p整除的正整数,那么，ap-1≡1(modp)Format定理的另一种形式：如果p是素数,则对任意整数a有ap≡a(modp)例子：a=7,p=19,求ap-1modp解：72=49≡11mod1974≡121mod19≡7mod1978≡49mod19≡11mod19716≡121mod19≡7mod19ap-1=718=716×72≡7×11mod19≡1mod19例子：•比24小而与24互素的正整数为：1、5、7、11、13、17、19、23。故•比21小与21互素的数这12个数是：｛1,2,4,5,8,10,11,13,16,17,19,20｝欧拉定理（Euler）（文字表述）：若整数a与整数n互素，则aφ(n)≡1(modn)注：1*.n＝p时，有ap-1≡1(modp)为Format定理！2*.易见aφ(n)+1≡a(modn)阶与本原元•am=1modn，如果a与n互素，则至少有一个整数m（如m=phi(n)）满足这一方程，称满足方程的最小正整数m为模n下a的阶。•如果a的阶m=phi（n），则称a为n的本原元。–本原元并不一定唯一–并非所有的整数都有本原元，只有以下形式的整数才有本原元：2,4,pa,2pa（a为整数，p为奇素数）例子：•n＝19，a＝3，在mod19下的幂分别为3、9、8、5、15、7、2、6、18、16、10、11、14、4、12、17、13和1。即3的阶为18＝phi(19)，所以3为19的本原元。中国剩余定理例子：（孙子算经）今有物不知其数。三三数之余二；五五数之余三；七七数之余二。问物几何？答曰：二十三。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应同时是5和7的倍数，即应是35的倍数，于是可以假设x＝35y有：0(mod3)1(mod5)0(mod7)xxx0(mod3)0(mod5)1(mod7)xxx1000100011(mod3)0(mod5)0(mod7)xxx35y≡1(mod3)相当于2y≡1(mod)3解出y=2（mod3）于是x35*270(mod105)类似地得到（2）、（3）方程的模105的解21、15。于是有：得700012101015100)105(mod2315*221*370*2100201030012232中国剩余定理：设自然数m1,m2,…mr两两互素，并记M=m1m2…mr，b1…..br表示r个整数，则同余方程组（A）在模M同余的意义下有唯一解。1122(mod)(mod)...............(mod)rrxbmxbmxbm证明：M=m1m2…mr，令Mj=M/mj=m1m2…mj-1mj+1…mr求yj使：Mjyj≡1modmjj=1,2,….r由于（Mj,mj)=1，所以yj是存在的。令：x0≡b1M1y1+b2M2y2+…+brMryrmodM(B)可证明x0便是（A）式的解。为证明这一点，注意j=h时mh|Mj。故Mj≡0modmh,即x0中各项除第h项外，其余都模mh同余0。又Mhyh≡1modmh,所以：X0≡bhMhyhmodmh≡bhmodmh。即满足(A)式，x0是其解。下面证明x0是模M的唯一解。如若不然，设x1和x2是（A）式模M的两个解，则有：x1≡x2≡bjmodmj(j=1…r)那么，x1-x2≡0modmj,即mj|(x1-x2)（j=1…r)因此，M｜（x1-x2),即x1-x2≡0modM所以x1，x2是模M的相同解，从而证明了对于模M式（A）的解是唯一的。例如：x≡1mod2x≡2mod3x≡3mod5解：M=2×3×5=30M1=15,M2=10,M3=615y1≡1mod2,y1=110y2≡1mod3,y2=16y3≡1mod5,y3=1所以,x=1×15×1+2×10×1+3×6×1=53≡23mod30群论•群是一个集合G，连同一个运算·，它结合任何两个元素a和b而形成另一个元素，这个集合和运算必须满足叫做四个要求:–1.封闭性。对于所有G中a,b，运算a·b的结果也在G中。–2.结合性。对于所有G中的a,b和c，等式(a·b)·c=a·(b·c)成立。–3.单位元。存在G中的一个元素e，使得对于所有G中的元素a，等式成立。–4.反元素。对于每个G中的a，存在G中的一个元素b使得a·b=b·a=e，这里的e是单位元。交换群：G是群，若对任意a，b∈G都有ab=ba则称G是交换群有限群无限群有限群的阶循环群循环群的生成元群的性质•群中的单位元是唯一的•群中每一个元素的逆元是唯一的•(消去律)对任意的，如果，或，则cbGcba,,acabcaba§4－3有限域理论•域的概念–域是由一个非空集合F组成，在集合F中定义了两个二元运算符：“+”和“·”，并满足：–在加法和乘法上封闭。–加法和乘法符合结合律–加法和乘法符合交换律–符合乘法对加法的分配律–关于加法成群，单位元记作0–非0元乘法构成群，单位元记作1•域记为{F,+,·}两个定义：减法：a-b=a+(-b)除法：a/b=a(b-1)有限域有限域的阶域的实质：域是一个可以在其上进行加法、减法、乘法和除法运算而结果不会超出域的集合。如有理数集合、实数集合、复数集合都是域，但整数集合不是有限域的两个定理密码学常用素域GF(p)或阶为2m的域GF(2m)定理1：有限域的阶只能是素数幂。定理2：对于素数p，与任意正整数n，存在pn阶的域，记为GF(pn)，阶为p的域GF(p)称为素域。GF(5)有限域中的计算+01234001234112340223401334012440123×01234000000101234202413303142404321(a)模5的加法(b)模5的乘法图4－1GF(5)的代数运算生成元与逆元•生成元–可证明：在GF(p)中至少存在一个元素g，使得GF(p)中任意非零元素可以表示成g的某次方幂的形式，g称为GF(p)的生成元•逆元–GF(p)中任意元素aa-1=ap-2生成元的例子•有限域GF（23），5是GF（23）的生成元50＝151＝552＝253＝1054＝455＝2056＝857＝1758＝1659＝11510＝9511＝22512＝18513＝21514＝13515＝19516＝3517＝15518＝6519＝7520＝12521＝14522＝1GF(2m)域0,1系数的多项式加法：同次项系数异或乘法：单项式相乘，系数相乘，指数相加多项式相乘，两式的单项式相乘，然后相加0,1系数的多项式可以方便的用二进制数表示不可约多项式生成元与逆元•生成元：GF(2m)有生成元•逆元a∈GF(2m)，a≠0则a-1=a2m-2例子：GF（24）•取：GF（24）的元素：1)(4xxxf（0000）(0001)(0010)(0011)(0100)(0101)(0110)(0111)(1000)(1001)(1010)(1011)(1100)(110