1、第第4章章 公钥密码公钥密码4.1 数论简介数论简介4.2 公钥密码体制的基本概念公钥密码体制的基本概念4.3 RSA算法算法4.4 背包密码体制背包密码体制4.5 Rabin密码体制密码体制4.6 椭圆曲线密码体制椭圆曲线密码体制习题习题数论是密码学特别是公钥密码学的基本工具，本章数论是密码学特别是公钥密码学的基本工具，本章首先介绍密码学中常用的一些数论知识，然后介绍首先介绍密码学中常用的一些数论知识，然后介绍公钥密码体制的基本概念和几种重要算法。公钥密码体制的基本概念和几种重要算法。1.因子因子设设a，b(b0)是两个整数，如果存在另一整数是两个整数，如果存在另一整数m，使使得得a=mb，
2、则称则称b整除整除a，记为记为b|a，且称且称b是是a的因子。的因子。4.1 数论简介数论简介 4.1.1 素数和互素数素数和互素数整数具有以下性质：整数具有以下性质：a|1，那么那么a=1。a|b且且b|a，则则a=b。对任一对任一b(b0)，b|0。b|g，b|h，则对任意整数则对任意整数m、n有有b|(mg+nh)。这里只给出的证明，其他这里只给出的证明，其他3个性质的证明都很简个性质的证明都很简单。单。性质的证明：性质的证明：由由b|g，b|h知，存在整数知，存在整数g1、h1，使得使得g=bg1,h=bh1所以所以mg+nh=mbg1+nbh1=b(mg1+nh1),因此因此b|(m
3、g+nh)。2.素数素数称整数称整数p(p1)是素数，如果是素数，如果p的因子只有的因子只有1，p。任一整数任一整数a(a1)都能惟一地分解为以下形式：都能惟一地分解为以下形式：其中其中p1p2pt是素数，是素数，ai0(i=1,t)。例如例如91=711，11011=7112131212ttappp这一性质称为整数分解的惟一性，也可如下陈述：这一性质称为整数分解的惟一性，也可如下陈述：设设P是所有素数集合，则任意整数是所有素数集合，则任意整数a(a1)都能惟一都能惟一地写成以下形式：地写成以下形式：其中其中ap0,等号右边的乘积项取所有的素数，然而大等号右边的乘积项取所有的素数，然而大多指数
4、项多指数项ap为为0。相应地，任一正整数也可由非。相应地，任一正整数也可由非0指指数列表表示。例如：数列表表示。例如：11011可表示为可表示为a7=1,a11=2,a13=1。两数相乘等价于对应的指数相加，即由两数相乘等价于对应的指数相加，即由k=mn 可得：可得：对每一素数对每一素数p,kp=mp+np。而由而由a|b可得：可得：对每一素对每一素数数p,apbp。这是因为这是因为pk只能被只能被pj(jk)整除。整除。pap Pap3.互素数互素数称称c是两个整数是两个整数a、b的最大公因子，如果的最大公因子，如果 c是是a的因子也是的因子也是b 的因子，即的因子，即c是是a、b的公因子。
5、的公因子。a和和b的任一公因子，也是的任一公因子，也是c的因子。的因子。表示为表示为c=gcd(a,b)。由于要求最大公因子为正，所以由于要求最大公因子为正，所以gcd(a,b)=gcd(a,-b)=gcd(-a,b)=gcd(-a,-b)。一般一般gcd(a,b)=gcd(|a|,|b|)。由任一非由任一非0整数能整除整数能整除0，可得，可得gcd(a,0)=|a|。如果将如果将a，b都表示为素数的乘积，则都表示为素数的乘积，则gcd（a,b）极易确定。极易确定。例如：例如：300=22315218=2132gcd(18,300)=213150=6一般由一般由c=gcd(a,b)可得：可得：
6、对每一素数对每一素数p，cp=min(ap,bp)。由于确定大数的素因子不很容易，所以这种方法不由于确定大数的素因子不很容易，所以这种方法不能直接用于求两个大数的最大公因子，如何求两个能直接用于求两个大数的最大公因子，如何求两个大数的最大公因子在下面介绍。大数的最大公因子在下面介绍。如果如果gcd(a,b)=1，则称则称a和和b互素。互素。设设n是一正整数，是一正整数，a是整数，如果用是整数，如果用n除除a，得商为得商为q，余数为余数为r，则则a=qn+r,0rn,其中其中x为小于或等于为小于或等于x的最大整数。的最大整数。用用a mod n表示余数表示余数r，则则 。如果如果(a mod n
7、)=(b mod n)，则称两整数则称两整数a和和b模模n同同余，记为余，记为ab mod n。称与称与a模模n同余的数的全体为同余的数的全体为a的同余类，记为的同余类，记为a，称称a为这个同余类的表示元素。为这个同余类的表示元素。注意：注意：如果如果a0(mod n)，则则n|a。4.1.2 模运算模运算aqnmodaanann同余有以下性质：同余有以下性质：若若n|(a-b)，则则ab mod n。(a mod n)(b mod n)，则则ab mod n。ab mod n,则则ba mod n。ab mod n,bc mod n,则则ac mod n。从以上性质易知，同余类中的每一元素都
8、可作为这从以上性质易知，同余类中的每一元素都可作为这个同余类的表示元素。个同余类的表示元素。求余数运算（简称求余运算）求余数运算（简称求余运算）a mod n将整数将整数a映射映射到集合到集合0,1,n-1，称求余运算在这个集合上的称求余运算在这个集合上的算术运算为模运算，模运算有以下性质：算术运算为模运算，模运算有以下性质：(a mod n)+(b mod n)mod n=(a+b)mod n。(a mod n)-(b mod n)mod n=(a-b)mod n。(a mod n)(b mod n)mod n=(ab)mod n。性质的证明：性质的证明：设（设（a mod n）=ra，(b
9、 mod n)=rb，则存在整数则存在整数j、k使得使得a=jn+ra，b=kn+rb。因此因此(a+b)mod n=(j+k)n+ra+rb mod n=(ra+rb)mod n=(a mod n)+(b mod n)mod n （证毕）证毕）性质、的证明类似。性质、的证明类似。例例4.1 设设Z8=0,1,7，考虑考虑Z8上的模加法和模乘法，上的模加法和模乘法，结果如表结果如表4.1所示。（见所示。（见77页表页表4.1）从加法结果可见，对每一从加法结果可见，对每一x，都有一都有一y，使得使得x+y0 mod 8。如对如对2，有，有6，使得，使得2+60 mod 8，称称y为为x的的负数，
10、也称为加法逆元。负数，也称为加法逆元。对对x，若有若有y，使得使得xy1 mod 8，如如331 mod 8，则称则称y为为x的倒数，也称为乘法逆元。本例可见并非的倒数，也称为乘法逆元。本例可见并非每一每一x都有乘法逆元。都有乘法逆元。一般地，定义一般地，定义Zn为小于为小于n的所有非负整数集合，即的所有非负整数集合，即Zn=0,1,n-1，称称Zn为模为模n的同余类集合。其上的同余类集合。其上的模运算有以下性质：的模运算有以下性质：交换律交换律 (w+x)mod n=(x+w)mod n(wx)mod n=(xw)mod n 结合律结合律 (w+x)+y mod n=w+(x+y)mod n
11、(wx)y mod n=w(xy)mod n 分配律分配律 w(x+y)mod n=wx+wy mod n 单位元单位元 (0+w)mod n=w mod n(1w)mod n=w mod n 加法逆元加法逆元 对对wZn，存在存在zZn，使得使得w+z0 mod n，记记z=-w。此外还有以下性质：此外还有以下性质：如果如果(a+b)(a+c)mod n，则则bc mod n，称为加法称为加法的可约律。的可约律。该性质可由该性质可由(a+b)(a+c)mod n的两边同加上的两边同加上a的加的加法逆元得到。法逆元得到。然而类似性质对乘法却不一定成立。例如然而类似性质对乘法却不一定成立。例如6
12、3672 mod 8，但但37 mod 8。原因是原因是6乘以乘以0到到7得到的得到的8个数仅为个数仅为Z8的一部分，见例的一部分，见例4.1。即如。即如果将对果将对Z8作作6的乘法的乘法6Z8（即用即用6乘乘Z8中每一数）中每一数）看作看作Z8到到Z8的映射的话，的映射的话，Z8中至少有两个数映射到中至少有两个数映射到同一数，因此该映射为多到一的，所以对同一数，因此该映射为多到一的，所以对6来说，来说，没有惟一的乘法逆元。但对没有惟一的乘法逆元。但对5来说，来说，551 mod 8，因此因此5有乘法逆元有乘法逆元5。仔细观察可见，与。仔细观察可见，与8互素的几互素的几个数个数1，3，5，7都
13、有乘法逆元。都有乘法逆元。这一结论可推广到任一这一结论可推广到任一Zn。定理定理4.1 设设aZn，gcd(a,n)=1，则则a在在Zn中有乘法中有乘法逆元。逆元。证明：证明：首先证明首先证明a与与Zn中任意两个不相同的数中任意两个不相同的数b、c（不妨设不妨设cb）相乘，其结果必然不同。否则设相乘，其结果必然不同。否则设abac mod n，则存在两个整数则存在两个整数k1,k2，使得使得ab=k1n+r，ac=k2n+r，可得可得a(b-c)=(k1-k2)n，所以所以a是是(k1-k2)n的一个因子。又由的一个因子。又由gcd(a，n)=1，得得a是是k1-k2的一个因子，设的一个因子，
14、设k1-k2=k3a，所以所以a(b-c)=k3an，即即b-c=k3n，与与0cbn矛盾。所以矛盾。所以|aZn|=|Zn|，又知又知aZnZn，所以所以aZn=Zn。因此对因此对1Zn，存在存在xZn，使得使得ax1 mod n，即即x是是a的乘法逆的乘法逆元。记为元。记为x=a-1。（证毕）证毕）设设p为一素数，则为一素数，则Zp中每一非中每一非0元素都与元素都与p互素，因互素，因此有乘法逆元。类似于加法可约律，可有以下乘法此有乘法逆元。类似于加法可约律，可有以下乘法可约律：可约律：如果如果(ab)(ac)mod n且且a有乘法逆元，那么对有乘法逆元，那么对(ab)(ac)mod n两边
15、同乘以两边同乘以a-1，即得即得bc mod n费尔玛费尔玛(Fermat)定理和欧拉定理和欧拉(Euler)定理在公钥密定理在公钥密码体制中起着重要作用。码体制中起着重要作用。4.1.3 费尔玛定理和欧拉定理费尔玛定理和欧拉定理1.费尔玛定理费尔玛定理定理定理4.2(Fermat)若若p是素数，是素数，a是正整数且是正整数且gcd(a,p)=1，则则ap-11 mod p。证明：由证明：由4.1.2的讨论知当的讨论知当gcd(a,p)=1时时,aZp=Zp，其中其中aZp表示表示a与与Zp中每一元素做模中每一元素做模p乘法。又知乘法。又知a00 mod p，所以所以aZp-0=Zp-0，a(
16、Zp-0)=Zp-0。即即a mod p,2a mod p,(p-1)a mod p=1,2,p-1所以所以 a2a(p-1)a(a mod p)(2a mod p)(p-1)a mod p)mod p(p-1)!mod p另一方面另一方面a2a(p-1)a=(p-1)!ap-1因此因此(p-1)!ap-1(p-1)!mod p由于由于(p-1)!与与p互素，因此互素，因此(p-1)!有乘法逆元，由乘有乘法逆元，由乘法可约律得法可约律得ap-11 mod p。（证毕）证毕）Fermat定理也可写成如下形式：定理也可写成如下形式：设设p是素数，是素数，a是是任一正整数，则任一正整数，则apa m
17、od p。2.欧拉函数欧拉函数设设n是一正整数，小于是一正整数，小于n且与且与n互素的正整数的个数互素的正整数的个数称为称为n的欧拉函数，记为的欧拉函数，记为(n)。例如：例如：(6)=2，(7)=6，(8)=4。若若n是素数，则显然有是素数，则显然有(n)=n-1。定理定理4.3 若若n是两个素数是两个素数p和和q的乘积，则的乘积，则(n)=(p)(q)=(p-1)(q-1)。证明：考虑证明：考虑Zn=0,1,pq-1，其中不与其中不与n互素的数互素的数有有3类，类，A=p,2p,(q-1)p，B=q,2q,(p-1)q,C=0，且且AB=，否则否则ip=jq，其中其中1iq-1，1jp-1
18、,则则p是是jq的因子，因此是的因子，因此是j的因子，设的因子，设j=kp，k1。则则ip=kpq，i=kq，与与1iq-1矛盾。所以矛盾。所以(n)=|Zn|-|A|+|B|+|C|=pq-(q-1)+(p-1)+1 =(p-1)(q-1)=(p)(q)（证毕）证毕）例如：例如：由由21=37，得，得(21)=(3)(7)=26=12。3.欧拉定理欧拉定理定理定理4.4（Euler）若若a和和n互素，则互素，则a(n)1 mod n。证明：证明：设设R=x1,x2,x(n)是由小于是由小于n且与且与n互素的互素的全体数构成的集合，全体数构成的集合，aR=ax1 mod n,ax2 mod n
19、,ax(n)mod n，对对aR中任一元素中任一元素axi mod n，因因a与与n互素，互素，x1与与n互素，所以互素，所以axi与与n互素，且互素，且axi mod nd。Euclid（f,d）1.Xf;Yd；2.if Y=0 then return X=gcd(f,d)；3.R=X mod Y；4.X=Y；5.Y=R；6.goto 2。例例4.2 求求gcd(1970,1066)。1970=11066+904,gcd(1066,904)1066=1904+162,gcd(904,162)904=5162+94,gcd(162,94)162=194+68,gcd(94,68)94=168+
20、26,gcd(68,26)68=226+16,gcd(26,16)26=116+10,gcd(16,10)16=110+6,gcd(10,6)10=16+4,gcd(6,4)6=14+2,gcd(4,2)4=22+0,gcd(2,0)因此因此gcd(1970,1066)=2。2.求乘法逆元求乘法逆元如果如果gcd(a,b)=1，则则b在在mod a下有乘法逆元（不下有乘法逆元（不妨设妨设ba），），即存在一即存在一x(xd）1.(X1,X2,X3)(1,0,f);(Y1,Y2,Y3)(0,1,d);2.if Y3=0 then return X3=gcd(f,d)；no inverse;3.i
21、f Y3=1 then return Y3=gcd(f,d)；Y2=d-1 mod f;4.Q=X3Y3；5.(T1,T2,T3)(X1-QY1,X2-QY2,X3-QY3);6.(X1,X2,X3)(Y1,Y2,Y3);7.(Y1,Y2,Y3)(T1,T2,T3);8.goto 2。算法中的变量有以下关系：算法中的变量有以下关系：fT1+dT2=T3;fX1+dX2=X3;fY1+dY2=Y3在算法在算法EUCLID(f,d)中，中，X等于前一轮循环中的等于前一轮循环中的Y，Y等于前一轮循环中的等于前一轮循环中的X mod Y。而在算法而在算法Extended Euclid(f,d)中，中，
22、X3等于前一轮循环中的等于前一轮循环中的Y3，Y3等于前一轮循环中的等于前一轮循环中的X3-QY3，由于由于Q是是Y3除除X3的商，因此的商，因此Y3是前一轮循环中的是前一轮循环中的Y3除除X3的余的余数，即数，即X3 mod Y3，可见可见Extended Euclid(f,d)中的中的X3、Y3与与Euclid(f,d)中的中的X、Y作用相同，因此可作用相同，因此可正确产生正确产生gcd(f,d)。如果如果gcd(f,d)=1，则在最后一轮循环中则在最后一轮循环中Y3=0，X3=1，因此在前一轮循环中因此在前一轮循环中Y3=1。由由Y3=1可得可得:fY1+dY2=Y3，fY1+dY2=1
23、，dY2=1+(-Y1)f，dY21 mod f，所以所以Y2d-1 mod f。例例4.3 求求gcd(1769,550)。算法的运行结果及各变量的变化情况如表算法的运行结果及各变量的变化情况如表42所示。所示。（见（见83页表页表4.2）所以所以gcd(1769,550)=1，550-1 mod 1769=550。中国剩余定理是数论中最有用的一个工具，定理说中国剩余定理是数论中最有用的一个工具，定理说如果已知某个数关于一些两两互素的数的同余类集，如果已知某个数关于一些两两互素的数的同余类集，就可重构这个数。就可重构这个数。例如：例如：Z10中每个数都可从这个数关于中每个数都可从这个数关于2
24、和和5（10的的两个互素的因子）的同余类重构。比如已知两个互素的因子）的同余类重构。比如已知x关于关于2和和5的同余类分别是的同余类分别是0和和3，即，即x mod 20，x mod 53。可知是偶数且被可知是偶数且被5除后余数是除后余数是3，所以可得，所以可得8是是满足这一关系的惟一的满足这一关系的惟一的x。4.1.6 中国剩余定理中国剩余定理定理定理4.5（中国剩余定理）（中国剩余定理）设设m1,m2,mk是两两互是两两互素的正整数，素的正整数，则一次同余方程组则一次同余方程组对模对模M有惟一解有惟一解:其中其中ei满足满足1122modmodmodkkamxamxamx1kiiMm1 1
25、2212modkkkMMMxe ae ae aMmmm1 mod1,2,iiiMemikm证明：设证明：设 ,i=1,2,k，由由Mi的定的定义得义得Mi与与mi是互素的，可知是互素的，可知Mi在模在模mi下有惟一的下有惟一的乘法逆元，即满足乘法逆元，即满足 的的ei是惟一的。是惟一的。1kilill iMMmm1 modiiiMemm下面证明对下面证明对i1,2,k，上述上述x满足满足ai(mod mi)x。注意到当注意到当ji时，时，mi|Mj，即即Mj0(mod mi)。所以所以(Mjej mod mj)mod mi (Mj mod mi)(ej mod mj)mod mi)mod mi
26、 0而而(Mi(ei mod mi)mod mi(Miei)mod mi1所以所以x(mod mi)ai，即即ai(mod mi)x下面证明方程组的解是惟一的。设下面证明方程组的解是惟一的。设x是方程组的另是方程组的另一解，即一解，即xai(mod mi)(i=1,2,k)由由xai(mod mi)得得x-x0(mod mi)，即即mi|(x-x)。再再根据根据mi两两互素，有两两互素，有M|(x-x)，即即x-x0(mod M)，所以所以x(mod M)=x(mod M)。(证毕证毕)中国剩余定理提供了一个非常有用的特性，即在模中国剩余定理提供了一个非常有用的特性，即在模M下可将非常大的数下
27、可将非常大的数x由一组小数由一组小数(a1,a2,ak)表达。表达。例例4.4 由以下方程组求由以下方程组求x。解：解：M=2357=210，M1=105，M2=70，M3=42，M4=30,易求易求e1M-11 mod 21,e2M-12mod 31,e3M-13 mod 53,e4M-14 mod 74,所以所以x mod 210(10511+7012+4233+3045)mod 210173，或写成或写成x173 mod 210。1mod22mod33mod55mod7xxxx例例4.5 将将973 mod 1813由模数分别为由模数分别为37和和49的两个的两个数表示。数表示。解：解：
28、取取x=973,M=1813,m1=37,m2=49。由由a1973 mod m111,a2973 mod m342得得x在模在模37和模和模49下的表达为（下的表达为（11,42）。）。1.求模下的整数幂求模下的整数幂Euler定理指出如果定理指出如果gcd(a,n)=1，则则a(n)1 mod n。现在考虑如下的一般形式现在考虑如下的一般形式:am1 mod n如果如果a与与n互素，则至少有一整数互素，则至少有一整数m（比如比如m=(n)）满足这一方程。称满足方程的最小正整数满足这一方程。称满足方程的最小正整数m为模为模n下下a的阶。的阶。4.1.7 离散对数离散对数例如：例如：a=7，n
29、=19，则易求出则易求出717 mod 19,7211 mod 19,731 mod 19，即即7在模在模19下的阶为下的阶为3。由于由于73+j=737j7j mod 19,所以所以747 mod 19,7572 mod 19,即从即从74 mod 19开始所求的幂出现循环，开始所求的幂出现循环，循环周期为循环周期为3，即循环周期等于元素的阶。，即循环周期等于元素的阶。定理定理4.6 设设a的阶为的阶为m，则则ak1 mod n的充要条件是的充要条件是k为为m的倍数。的倍数。证明：设存在整数证明：设存在整数q，使得使得k=qm，则则ak(am)q1 mod n。反之，假定反之，假定ak1 m
30、od n，令令k=qm+r,其中其中00,a1)的逆函数称为以的逆函数称为以a为底为底x的对数，记为的对数，记为y=logax。对数函数有以下性质：对数函数有以下性质：loga1=0,logaa=1,logaxy=logax+logay,logaxy=ylogax在模运算中也有类似的函数。设在模运算中也有类似的函数。设p是一素数，是一素数，a是是p的本原根，则的本原根，则a,a2,ap-1产生出产生出1到到p-1之间的所有之间的所有值，且每一值只出现一次。因此对任意值，且每一值只出现一次。因此对任意b1,p-1，都存在惟一的都存在惟一的i(1ip-1)，使得使得bai mod p。称称i为模为
31、模p下以下以a为底为底b的指标，记为的指标，记为i=inda,p(b)。指标有以下性质：指标有以下性质：inda,p(1)=0。inda,p(a)=1。分别由以下关系得出：分别由以下关系得出：a0 mod p=1 mod p=1,a1 mod p=a。以上假定模数以上假定模数p是素数，对于非素数也有类似的结是素数，对于非素数也有类似的结论。论。例例4.6 设设p=9，则则(p)=6，a=2是是p的一个本原根，的一个本原根，a的不同的幂为（模的不同的幂为（模9下）下）201,212,224,238,247,255,261由此可得由此可得a的指数表如表的指数表如表4.3（a）所示。所示。重新排列表
32、重新排列表4.3（a），），可求每一与可求每一与9互素的数的指互素的数的指标如表标如表4.3（b）所示。（见所示。（见86页表页表4.3）在讨论指标的另两个性质时，需要利用如下结论：在讨论指标的另两个性质时，需要利用如下结论：若若azaq mod p，其中其中a和和p互素，则有互素，则有zq mod(p)。证明：因证明：因a和和p互素，所以互素，所以a在模在模p下存在逆元下存在逆元a-1，在在azaq mod p两边同乘以两边同乘以(a-1)q，得得az-q1 mod p。由由Euler定理定理a(p)1 mod p知存在一整数知存在一整数k，使得使得z-qk(p)，所以所以zq mod(p)
33、。由上述结论可得指标的以下两个性质：由上述结论可得指标的以下两个性质：inda,p(xy)=inda,p(x)+inda,p(y)mod(p)。inda,p(yr)=rinda,p(y)mod(p)。性质的证明：设性质的证明：设由模运算的性质得：由模运算的性质得：所以所以inda,p(xy)=inda,p(x)+inda,p(y)mod(p)（证毕）证毕）,mod,mod,mod,a pa pa pindxindyindxyxap yap xyap ,mod(mod)(mod)()moda pa pa pa pa pindxyindxindyindxindyapapapap性质是性质的推广。性
34、质是性质的推广。从指标的以上性质可见，指标与对数的概念极为相从指标的以上性质可见，指标与对数的概念极为相似。似。3.离散对数离散对数设设p是素数，是素数，a是是p的本原根，即的本原根，即a1,a2,ap-1在在 mod p下产生下产生1到到p-1的所有值，所以对的所有值，所以对b1,p-1，有惟一的有惟一的i1,p-1使得使得bai mod p。称称i为模为模p下下以以a为底为底b的离散对数，记为的离散对数，记为ilogab(mod p)。当当a、p、i已知时，用已知时，用4.3.2节将介绍的快速指数算节将介绍的快速指数算法可比较容易地求出法可比较容易地求出b，但如果已知但如果已知a、b和和p
35、，求求i则非常困难。目前已知的最快的求离散对数算法其则非常困难。目前已知的最快的求离散对数算法其时间复杂度为：时间复杂度为：所以当所以当p很大时，该算法也是不可行的。很大时，该算法也是不可行的。2133explnln lnOpp设设p是一素数，是一素数，a小于小于p，称称a是是p的平方剩余，如果的平方剩余，如果方程方程x2a(mod p)有解。否则称为非平方剩余。有解。否则称为非平方剩余。4.1.8 平方剩余平方剩余例如：例如：x21 mod 7有解有解x=1，x=6；x22 mod 7有解有解x=3，x=4；x23 mod 7无解；无解；x24 mod 7有解有解x=2，x=5；x25 mo
36、d 7无解；无解；x26 mod 7无解。无解。可见共有可见共有3个数（个数（1、2、4）是模）是模7的平方剩余，且的平方剩余，且每个平方剩余都有两个平方根（即例中的每个平方剩余都有两个平方根（即例中的x）。）。容易证明，模容易证明，模p的平方剩余的个数为的平方剩余的个数为(p-1)/2，且与且与模模p的非平方剩余的个数相等。如果的非平方剩余的个数相等。如果a是模是模p的一个的一个平方剩余，那么平方剩余，那么a恰有两个平方根，一个在恰有两个平方根，一个在0到到(p-1)/2之间，另一个在之间，另一个在(p-1)/2到到(p-1)之间，且这两个之间，且这两个平方根中的一个也是模平方根中的一个也是
37、模p的平方剩余。的平方剩余。定义定义4.1 设设p是素数，是素数，a是一整数，符号是一整数，符号 的定义如的定义如下：下：称符号称符号 为为Legendre符号。符号。ap011apaappap如果被整除如果是模的平方剩余如果是模的非平方剩余ap例如：例如：计算计算 有一个简单公式：有一个简单公式：例如：例如：p=23，a=5，a(p-1)/2 mod p511 mod p=-1，所所以以5不是模不是模23的平方剩余。的平方剩余。1241777 3561777 ap(1)/2modpaappLegendre符号有以下性质：符号有以下性质：定理定理4.7 设设p是奇素数，是奇素数，a和和b都不能
38、被都不能被p除尽，则除尽，则 若若ab mod p，则则证明从略。证明从略。abppababppp 21apapapp以下定义的以下定义的Jacobi符号是符号是Legendre符号的推广。符号的推广。定义定义4.2 设设n是正整数，且是正整数，且 ，定定义义Jacobi符号为符号为其中右端的符号是其中右端的符号是Legendre符号。符号。当当n为素数时，为素数时，Jacobi符号就是符号就是Legendre符号。符号。1212kaaaknppp 1212kaaakaaaapnpp Jacobi符号有以下性质：符号有以下性质：定理定理4.8 设设n是正合数，是正合数，a和和b是与是与n互素的
39、整数，则互素的整数，则 若若ab mod n，则则对一些特殊的对一些特殊的a，Jacobi符号可如下计算：符号可如下计算：abnn ababnnn 2abann anann 211281121,1,1nnnnn 定理定理4.9（Jacobi符号的互反律）符号的互反律）设设m、n均为大于均为大于2的奇数，则的奇数，则若若mn3 mod 4，则则 ；否则否则 。1141mnmnnm mnnm mnnm以上性质表明：以上性质表明：为了计算为了计算Jacobi符号（包括符号（包括Legendre符号作为它的特殊情形），并不需要求素符号作为它的特殊情形），并不需要求素因子分解式。例如因子分解式。例如10
40、5虽然不是素数，在计算虽然不是素数，在计算Legendre符号符号 时，可以先把它看作时，可以先把它看作Jacobi符符号来计算，由上述两个定理得号来计算，由上述两个定理得105317 10531721317105105一般在计算一般在计算 时，如果有必要，可用时，如果有必要，可用m mod n代代替替m，而互反律用以减小而互反律用以减小 的分母。的分母。可见，引入可见，引入Jacobi符号对计算符号对计算Legendre符号是十分符号是十分方便的，但应强调指出方便的，但应强调指出Jacobi符号和符号和Legendre符号符号的本质差别是：的本质差别是：Jacobi符号符号 不表示方程不表示
41、方程x2a mod n是否有解。比如是否有解。比如n=p1p2，a关于关于p1和和p2都不是平都不是平方剩余，即方剩余，即x2a mod p1和和x2a mod p2都无解，由都无解，由中国剩余定理知中国剩余定理知x2a mod n也无解。但是，由也无解。但是，由于于 ,所以所以 。即即x2a mod n虽虽无解，但无解，但Jacobi符号符号 却为却为1。mn mn an an121papa 121aaanpp例例4.7 考虑方程考虑方程x22 mod 3599，由于由于3599=5961，所以方程等价于方程组所以方程等价于方程组由于由于 ，所以方程组无解，但，所以方程组无解，但Jacobi
42、符号符号222 mod592 mod61xx2159 23599182113599 下面考虑公钥密码体制中一个非常重要的问题。下面考虑公钥密码体制中一个非常重要的问题。设设n是两个大素数是两个大素数p和和q的乘积。由上述结论，的乘积。由上述结论，1到到p-1之间有一半数是模之间有一半数是模p的平方剩余，另一半是模的平方剩余，另一半是模p的的非平方剩余，对非平方剩余，对q也有类似结论。另一方面，也有类似结论。另一方面，a是模是模n的平方剩余，当且仅当的平方剩余，当且仅当a既是模既是模p的平方剩余也是的平方剩余也是模模q的平方剩余。所以对满足的平方剩余。所以对满足0an,gcda,n=1的的a，有
43、一半满足有一半满足 ，另一半满足另一半满足 。而在而在满足满足 的的a中，有一半满足中，有一半满足 ，这些这些a就是模就是模n的平方剩余；另一半满足的平方剩余；另一半满足 ，这些这些a是模是模n的非平方剩余。的非平方剩余。1an 1an 1an1aapq1aapq 设设a是模是模n的平方剩余，即存在的平方剩余，即存在x使得使得x2a mod n成成立，因立，因a既是模既是模p的平方剩余，又是模的平方剩余，又是模q的平方剩余，的平方剩余，所以存在所以存在y、z，使得使得(y)2a mod p,(z)2a mod q，因此因此xy mod p,xz mod q由中国剩余定理可求得由中国剩余定理可求
44、得a mod n的的4个平方根，记为个平方根，记为u mod n和和w mod n，且且uw mod n。以上结果表明，已知以上结果表明，已知n的分解的分解n=pq，且且a是模是模n的平的平方剩余，就可求得方剩余，就可求得a mod n的的4个平方根。个平方根。下面考虑相反的问题，即已知下面考虑相反的问题，即已知a mod n的两个不同的两个不同的平方根（的平方根（u mod n和和w mod n，且且uw mod n），），就可分解就可分解n。事实上由事实上由u2w2 mod n得得(u+w)(u-w)0 mod n，但但n不能整除不能整除u+w也不能整也不能整除除u-w，所以必有所以必有p
45、|(u+w),q|(u-w)或或p|(u-w),q|(u+w)所以所以gcd(n,u+w)=p,gcd(n，u-w)=q或或gcd(n,u-w)=p,gcd(n,u+w)=q因此得到了因此得到了n的分解式。的分解式。将以上讨论总结为：将以上讨论总结为：定理定理4.10 求解方程求解方程x2a mod n与分解与分解n是等价的。是等价的。第第2个重要结论是：个重要结论是：当当pq3 mod 4时，时，a mod n的的两个不同的平方根两个不同的平方根u和和w的的Jacobi符号有如下关系：符号有如下关系：证明：证明：由以上讨论知，由以上讨论知，u、w满足满足p|(u+w),q|(u-w)或或p|
46、(u-w),q|(u+w)即即u-w mod p,uw mod q或或uw mod p,u-w mod q。uwnm 若为第一种情况，若为第一种情况，（证毕）证毕）同理可证第二种情况。同理可证第二种情况。1uuuwwwwwwwnpqpqppqpqn 在公钥密码体制以前的整个密码学史中，所有的密在公钥密码体制以前的整个密码学史中，所有的密码算法，包括原始手工计算的、由机械设备实现的码算法，包括原始手工计算的、由机械设备实现的以及由计算机实现的，都是基于代换和置换这两个以及由计算机实现的，都是基于代换和置换这两个基本工具。而公钥密码体制则为密码学的发展提供基本工具。而公钥密码体制则为密码学的发展提
47、供了新的理论和技术基础，一方面公钥密码算法的基了新的理论和技术基础，一方面公钥密码算法的基本工具不再是代换和置换，而是数学函数；另一方本工具不再是代换和置换，而是数学函数；另一方面公钥密码算法是以非对称的形式使用两个密钥，面公钥密码算法是以非对称的形式使用两个密钥，两个密钥的使用对保密性、密钥分配、认证等都有两个密钥的使用对保密性、密钥分配、认证等都有着深刻的意义。可以说公钥密码体制的出现在密码着深刻的意义。可以说公钥密码体制的出现在密码学史上是一个最大的而且是惟一真正的革命。学史上是一个最大的而且是惟一真正的革命。4.2 公钥密码体制的基本概念公钥密码体制的基本概念公钥密码体制的概念是在解决
48、单钥密码体制中最难公钥密码体制的概念是在解决单钥密码体制中最难解决的两个问题时提出的，这两个问题是密钥分配解决的两个问题时提出的，这两个问题是密钥分配和数字签字。和数字签字。单钥密码体制在进行密钥分配时（看第单钥密码体制在进行密钥分配时（看第5章），要章），要求通信双方或者已经有一个共享的密钥，或者可籍求通信双方或者已经有一个共享的密钥，或者可籍助于一个密钥分配中心。对第一个要求，常常可用助于一个密钥分配中心。对第一个要求，常常可用人工方式传送双方最初共享的密钥，这种方法成本人工方式传送双方最初共享的密钥，这种方法成本很高，而且还完全依赖信使的可靠性。第二个要求很高，而且还完全依赖信使的可靠性
49、。第二个要求则完全依赖于密钥分配中心的可靠性。则完全依赖于密钥分配中心的可靠性。第二个问题数字签字考虑的是如何为数字化的消息第二个问题数字签字考虑的是如何为数字化的消息或文件提供一种类似于为书面文件手书签字的方法。或文件提供一种类似于为书面文件手书签字的方法。1976年年W.Diffie和和M.Hellman对解决上述两个问题对解决上述两个问题有了突破，从而提出了公钥密码体制。有了突破，从而提出了公钥密码体制。公钥密码算法的最大特点是采用两个相关密钥将加公钥密码算法的最大特点是采用两个相关密钥将加密和解密能力分开，其中一个密钥是公开的，称为密和解密能力分开，其中一个密钥是公开的，称为公开密钥，
50、简称公开钥，用于加密；另一个密钥是公开密钥，简称公开钥，用于加密；另一个密钥是为用户专用，因而是保密的，称为秘密密钥，简称为用户专用，因而是保密的，称为秘密密钥，简称秘密钥，用于解密。因此公钥密码体制也称为双钥秘密钥，用于解密。因此公钥密码体制也称为双钥密码体制。算法有以下重要特性：密码体制。算法有以下重要特性：已知密码算法已知密码算法和加密密钥，求解密密钥在计算上是不可行的。和加密密钥，求解密密钥在计算上是不可行的。4.2.1 公钥密码体制的原理公钥密码体制的原理图图4.1是公钥体制加密的框图，加密过程有以下几是公钥体制加密的框图，加密过程有以下几步：步：要求接收消息的端系统，产生一对用来加
