密码学中常用数学知识市公开课一等奖省赛课获奖

公钥密码密码学中惯用数学知识公钥密码体制基本概念RSA算法第1页4.1.1群、环、域群<G,*>定义:一些数字组成集合一个二元运算，运算结果属于此集合（封闭性）服从结合律。有单位元，逆元。假如是可交换，则成为Abel群*为乘法时，称为乘法群逆元（a-1）*为加法时，称为加法群逆元（-a）环<R,+,*>定义:

Abel群，及一个乘法运算：满足结合律与加法分配律

假如加法满足交换律,则称交换环例：整数modN（foranyN）第2页域<F,+,*>定义：

<F,+>是Abel加群环<F-{0},*>是Abel乘群例：整数modP（P为素数）Galois域：假如n是素数p

，则模运算modulop

形成GaloisFieldmodulop

记为：GF(p)

第3页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不是第4页200以内素数：2357111317192329313741434753596167717379838997101103107109113127131137139149151157163167173179181191193197199素数分解：把整数n写成素数乘积分解整数要比乘法困难整数n素数分解是把它写素数乘积

eg.91=7×13;3600=24×32×52

第5页互素数：整数a,b

互素是指它们没有除1之外其它因子。

8与15互素

8因子1,2,4,8 15因子1,3,5,15 1是唯一公因子记为：gcd(8,15)=1第6页4.1.3模运算设n是一正整数,a是整数,若a=qn+r,0≤r<n,

则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-10123456

78910111213141516171819202122232425262728293031323334第7页同余性质：若n|(a-b)，则a≡bmodn(amodn)≡(bmodn),则a≡bmodna≡bmodn，则b≡amodna≡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第8页定理:设a∈Zn,gcd(a,n)=1,则a在Zn有逆元。证实思绪：用反证法证实a和Zn中任何两个不一样数相乘结果都不相同从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}第9页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第10页欧拉函数设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=12第11页4.1.5素性检验爱拉托斯散(Eratosthenes)筛法定理：设n是正整数，若对全部满足p≤素数p，都有p|n，则n一定是素数。对给定数检验其是否为素数若要找出小于n全部素数：

先将2到n之间整数列出，从中删除小于等于全部素数倍数，余下整数即是所要求素数。此方法在n很大时，实际上是不可行。第12页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不是素数。第13页Miller-Rabin素性概率检测法n为待检测数，a为小于n整数，将n-1表示为二进制形式bkbk-1…b0,d赋初值为1，算法关键以下：

fori=kdownto0do{xd;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不是素数。第14页4.1.6欧几里得算法2.两个正整数互素，能够求一个数关于另一个数乘法逆元性质:

对任意非负整数a和正整数b,

有gcd(a,b)=gcd(b,amodb)证实：

1.求两个正整数最大公因子a=kb+r≡rmodbamodb=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)=11gcd(11,10)=gcd(10,1)=1第15页Euclid(f,d)f>d1.Xf;Yd;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)=11gcd(11,10)=gcd(10,1)=1第16页欧几里德算法--求乘法逆元若gcd(a,b)=1,b在模a下有乘法逆元(设b<a)。即存在x<a,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逆元。第17页ExtendedEuclid(f,d)(f>d)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逆元第18页例：求解11d(mod51)=1步骤。即求11-1mod51=？循环次数QX1X2X3Y1Y2Y3初值--10510111ExtendedEuclid(f,d)(f>d)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