第12次课-密码学中常用数学知识

公钥密码密码学中常用的数学知识公钥密码体制的基本概念RSA算法4.1.1群、环、域群G,*的定义:一些数字组成的集合一个二元运算，运算结果属于此集合（封闭性）服从结合律。有单位元，逆元。如果是可交换的，则成为Abel群*为乘法时，称为乘法群逆元（a-1）*为加法时，称为加法群逆元（-a）环R,+,*的定义:Abel群，及一个乘法运算：满足结合律与加法的分配律如果加法满足交换律,则称交换环例：整数modN（foranyN）域F,+,*的定义：F,+是Abel加群环F-{0},*是Abel乘群例：整数modP（P为素数）Galois域：如果n是素数p，则模运算modulop形成GaloisFieldmodulop记为：GF(p)4.1.2素数和互素数因子：•对整数b!=0及a,如果存在整数m使得a=mb,称b整除a,也称b是a的因子。•记作b|a•例1,2,3,4,6,8,12,24整除24素数：•素数:只有因子1和自身•1是一个平凡素数•例2,3,5,7是素数,4,6,8,9,10不是200以内的素数：•2357111317192329313741434753596167717379838997101103107109113127131137139149151157163167173179181191193197199素数分解：•把整数n写成素数的乘积•分解整数要比乘法困难•整数n的素数分解是把它写素数的乘积eg.91=7×13;3600=24×32×52互素数：•整数a,b互素是指它们没有除1之外的其它因子。8与15互素8的因子1,2,4,815的因子1,3,5,151是唯一的公因子•记为：gcd(8,15)=14.1.3模运算•设n是一正整数,a是整数,若a=qn+r,0≤rn,则amodn=r•若(amodn)=(bmodn),称为a,b模n同余，记为a≡bmodn•称与a模n同余的数的全体为a的同余类，记为[a]，a称为这个同余类的代表元素。-21-20-19-18-17-16–15-14-13-12-11-10-9-8-7-6-5-4-3-2-1012345678910111213141516171819202122232425262728293031323334同余的性质：•若n|(a-b)，则a≡bmodn•(amodn)≡(bmodn),则a≡bmodn•a≡bmodn，则b≡amodn•a≡bmodn，b≡cmodn，则a≡cmodn求余运算amodn将a映射到集合{0,1,…,n-1},求余运算称为模运算。模运算的性质–[(amodn)+(bmodn)]modn=(a+b)modn–[(amodn)-(bmodn)]modn=(a-b)modn–[(amodn)×(bmodn)]modn=(a×b)modn定理:设a∈Zn,gcd(a,n)=1,则a在Zn有逆元。证明思路：1.用反证法证明a和Zn中任何两个不同的数相乘结果都不相同2.从1得出a×Zn=Zn,因此存在x∈Zn,使a×x=1modn•设a为素数，Zp中每一个非零元素都与a互素，因此有乘法逆元，有乘法可约律(a×b)=(a×c)modn,b=cmodn定义Zn为小于n的所有非负整数集合Zn={0,1,2,…,n-1}4.1.4费尔玛定理和欧拉定理费尔玛定理：若p是素数，a是正整数且gcd(a,p)=1，则ap-1≡1modp•证明：当gcd(a,p)=1,则a×Zp=Zp。又因为a×0≡0modp,所以a×(Zp-{0})=Zp-{0}即：{amodp,2amodp,…,(n-1)amodp}={1,…,p-1}(amodp)×(2amodp)×…×(n-1)amodp=(p-1)!ap-1modp因此：(p-1)!ap-1modp=(p-1)!modp(p-1)!与p互素，所以乘法可约律，ap-1=1modp•欧拉函数–设n为一正整数，小于n且与n互素的正整数的个数称为n的欧拉函数，记为φ(n)•欧拉定理若a和n互素,则aφ(n)=1modn例：Φ(6)=2,Φ(7)=6,Φ(8)=4显然，若n是素数，Φ(n)=n-1定理：若n是两个素数p和q的乘积，则Φ(n)＝Φ(p)Φ(q)=(p-1)(q-1)例：21=3×7，因此φ(21)=φ(3)×φ(7)=2×6=124.1.5素性检验•爱拉托斯散(Eratosthenes)筛法定理：设n是正整数，若对所有满足p≤的素数p，都有p|n，那么n一定是素数。对给定的数检验其是否为素数n若要找出不大于n的所有素数：先将2到n之间的整数列出，从中删除小于等于的所有素数的倍数，余下的整数即是所要求的素数。n此方法在n很大时，实际上是不可行的。Miller-Rabin素性概率检测法引理：如果p为大于2的素数，则方程x2≡1modp的解只有和x≡1和x≡-1证明:x2≡1modpx2-1≡0modp(x+1)(x-1)≡0modp所以：p|(x+1)或p|(x-1)或p|(x+1)且p|(x-1)若p|(x+1)且p|(x-1)，则存在k,j，使x+1=kp,x-1=jp可得：2=(k-j)p,这是不可能的。所以：p|(x+1)或p|(x-1)设：p|(x+1)，则x+1=kpx=-1modp设：p|(x-1)，则x-1+1=kpx=1modp引理的逆命题：若方程x2≡1modp，有唯一解x不为+1或-1，p不是素数。例：x2=1(mod8)12=1mod832=1mod852=1mod872=1mod8又5=-3mod8，7=-1mod8，所以方程的解为：1，-1，3，-38不是素数。•Miller-Rabin素性概率检测法–n为待检测数，a为小于n的整数，将n-1表示为二进制形式bkbk-1…b0,d赋初值为1，算法核心如下：fori=kdownto0do{xd;d(d×d)modn;ifd=1and(x≠1)and(x≠n-1)thenreturnFalseifbi=1thed(d×a)modn}ifd≠1thenreturnFalse;returnTrue–若返回False,n不是素数,若返回True,有可能是素数。For循环结束,有d≡an-1modn。由费尔玛定理,若n为素数,d为1。所以d≠1，则d不是素数。n-1≡-1modn,所以x≠1和x≠n-1指x2≡1modn有非±1的根,n不是素数。4.1.6欧几里得算法2.两个正整数互素，可以求一个数关于另一个数的乘法逆元•性质:对任意非负整数a和正整数b,有gcd(a,b)=gcd(b,amodb)•证明：1.求两个正整数的最大公因子a=kb+r≡rmodbamodb=a-kb设d是a，b的公因子，即d|a,d|b,所以d|kb.由d|a和d|kb，得d|(amodb)，故d是b和amodb的公因子。a,b以及b,amodb公因子集合相同，故最大公因子也相同。gcd(55,22)=gcd(22,11)=gcd(11,0)=11gcd(11,10)=gcd(10,1)=1Euclid(f,d)fd1.Xf;Yd;2.IfY=0thenreturnX=gcd(f,d)3.R=XmodY4.X=Y;5.Y=R6.Goto2假定输入是两个正整数Euclid算法：gcd(55,22)=gcd(22,11)=gcd(11,0)=11gcd(11,10)=gcd(10,1)=1•欧几里德算法--求乘法逆元–若gcd(a,b)=1,b在模a下有乘法逆元(设ba)。即存在xa,bx≡1moda思路：求gcd(a,b)，当gcd(a,b)=1时，则返回b的逆元。整除中的一个论断：若gcd(a,b)=d，则存在m,n，使得d=ma+nb。那么当gcd(a,b)=1时，有ma+nb=1，即m是a模b的逆元，n是b模a的逆元。ExtendedEuclid(f,d)(fd)1.（X1X2X3)(1,0,f);(Y1Y2Y3)(0,1,d);2.IfY3=0,thenreturnX3=gcd(f,d);停止，没有逆元;3.IfY3=1,thenreturnX3=gcd(f,d);Y2=d-1modf;4.Q=X3divY3（整数除）;5.(T1T2T3)(X1-QY1,X2-QY2,X3-QY3);6.(X1X2X3)(Y1Y2Y3);7.(Y1Y2Y3)(T1T2T3);8.Goto2扩展欧几里德算法：求d模f的逆元例：求解11d(mod51)=1的步骤。即求11-1mod51=？循环次数QX1X2X3Y1Y2Y3初值--10510111ExtendedEuclid(f,d)(fd)1.（X1X2X3)(1,0,f);(Y1Y2Y3)(0,1,d);2.IfY3=0,thenreturnX3=gcd(f,d);停止，没有逆元;3.IfY3=1,thenreturnX3=gcd(f,d);Y2=d-1modf;4.Q=X3divY3（整数除）;5.(T1T2T3)(X1-QY1,X2-QY2,X3-QY3);6.(X1X2X3)(Y1Y2Y3);7.(Y1Y2Y3)(T1T2T3);8.Goto21411-1mod51=14Q=X3divY3=51/11=4T1=X1-Q*Y1=1-4*0=11-470111211-47-15431-1542-93412-93-3141f*X1+d*X2=X3f*Y1+d*Y2=Y3f*T1+d*T2=T3