第4章公钥密码 (现代密码学)

第4章公钥密码4.1数论简介4.2公钥密码体制的基本概念4.3RSA算法4.4背包密码体制4.5Rabin密码体制4.6椭圆曲线密码体制习题数论是密码学特别是公钥密码学的基本工具，本章首先介绍密码学中常用的一些数论知识，然后介绍公钥密码体制的基本概念和几种重要算法。1.因子设a，b(b≠0)是两个整数，如果存在另一整数m，使得a=mb，则称b整除a，记为b|a，且称b是a的因子。4.1数论简介4.1.1素数和互素数整数具有以下性质：①a|1，那么a=±1。②a|b且b|a，则a=±b。③对任一b(b≠0)，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|(mg+nh)。2.素数称整数p(p1)是素数，如果p的因子只有±1，±p。任一整数a(a1)都能惟一地分解为以下形式：其中p1p2…pt是素数，ai0(i=1,…,t)。例如91=7×11，11011=7×112×131212ttappp这一性质称为整数分解的惟一性，也可如下陈述：设P是所有素数集合，则任意整数a(a1)都能惟一地写成以下形式：其中ap≥0,等号右边的乘积项取所有的素数，然而大多指数项ap为0。相应地，任一正整数也可由非0指数列表表示。例如：11011可表示为{a7=1,a11=2,a13=1}。两数相乘等价于对应的指数相加，即由k=mn可得：对每一素数p,kp=mp+np。而由a|b可得：对每一素数p,ap≤bp。这是因为pk只能被pj(j≤k)整除。papPap3.互素数称c是两个整数a、b的最大公因子，如果①c是a的因子也是b的因子，即c是a、b的公因子。②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=22×31×5218=21×32gcd(18,300)=21×31×50=6一般由c=gcd(a,b)可得：对每一素数p，cp=min(ap,bp)。由于确定大数的素因子不很容易，所以这种方法不能直接用于求两个大数的最大公因子，如何求两个大数的最大公因子在下面介绍。如果gcd(a,b)=1，则称a和b互素。设n是一正整数，a是整数，如果用n除a，得商为q，余数为r，则a=qn+r,0≤rn,其中x为小于或等于x的最大整数。用amodn表示余数r，则。如果(amodn)=(bmodn)，则称两整数a和b模n同余，记为a≡bmodn。称与a模n同余的数的全体为a的同余类，记为[a]，称a为这个同余类的表示元素。注意：如果a≡0(modn)，则n|a。4.1.2模运算aqnmodaanann同余有以下性质：①若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。性质①的证明：设（amodn）=ra，(bmodn)=rb，则存在整数j、k使得a=jn+ra，b=kn+rb。因此(a+b)modn=[(j+k)n+ra+rb]modn=(ra+rb)modn=[(amodn)+(bmodn)]modn（证毕）性质②、③的证明类似。例4.1设Z8={0,1,…,7}，考虑Z8上的模加法和模乘法，结果如表4.1所示。（见77页表4.1）从加法结果可见，对每一x，都有一y，使得x+y≡0mod8。如对2，有6，使得2+6≡0mod8，称y为x的负数，也称为加法逆元。对x，若有y，使得x×y≡1mod8，如3×3≡1mod8，则称y为x的倒数，也称为乘法逆元。本例可见并非每一x都有乘法逆元。一般地，定义Zn为小于n的所有非负整数集合，即Zn={0,1,…,n-1}，称Zn为模n的同余类集合。其上的模运算有以下性质：①交换律(w+x)modn=(x+w)modn(w×x)modn=(x×w)modn②结合律[(w+x)+y]modn=[w+(x+y)]modn[(w×x)×y]modn=[w×(x×y)]modn③分配律[w×(x+y)]modn=[w×x+w×y]modn④单位元(0+w)modn=wmodn(1×w)modn=wmodn⑤加法逆元对w∈Zn，存在z∈Zn，使得w+z≡0modn，记z=-w。此外还有以下性质：如果(a+b)≡(a+c)modn，则b≡cmodn，称为加法的可约律。该性质可由(a+b)≡(a+c)modn的两边同加上a的加法逆元得到。然而类似性质对乘法却不一定成立。例如6×3≡6×7≡2mod8，但37mod8。原因是6乘以0到7得到的8个数仅为Z8的一部分，见例4.1。即如果将对Z8作6的乘法6×Z8（即用6乘Z8中每一数）看作Z8到Z8的映射的话，Z8中至少有两个数映射到同一数，因此该映射为多到一的，所以对6来说，没有惟一的乘法逆元。但对5来说，5×5≡1mod8，因此5有乘法逆元5。仔细观察可见，与8互素的几个数1，3，5，7都有乘法逆元。这一结论可推广到任一Zn。定理4.1设a∈Zn，gcd(a,n)=1，则a在Zn中有乘法逆元。证明：首先证明a与Zn中任意两个不相同的数b、c（不妨设cb）相乘，其结果必然不同。否则设a×b≡a×cmodn，则存在两个整数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的一个因子，设k1-k2=k3a，所以a(b-c)=k3an，即b-c=k3n，与0cbn矛盾。所以|a×Zn|=|Zn|，又知a×ZnZn，所以a×Zn=Zn。因此对1∈Zn，存在x∈Zn，使得a×x≡1modn，即x是a的乘法逆元。记为x=a-1。（证毕）设p为一素数，则Zp中每一非0元素都与p互素，因此有乘法逆元。类似于加法可约律，可有以下乘法可约律：如果(a×b)≡(a×c)modn且a有乘法逆元，那么对(a×b)≡(a×c)modn两边同乘以a-1，即得b≡cmodn费尔玛(Fermat)定理和欧拉(Euler)定理在公钥密码体制中起着重要作用。4.1.3费尔玛定理和欧拉定理1.费尔玛定理定理4.2(Fermat)若p是素数，a是正整数且gcd(a,p)=1，则ap-1≡1modp。证明：由4.1.2的讨论知当gcd(a,p)=1时,a×Zp=Zp，其中a×Zp表示a与Zp中每一元素做模p乘法。又知a×0≡0modp，所以a×Zp-{0}=Zp-{0}，a×(Zp-{0})=Zp-{0}。即{amodp,2amodp,…,(p-1)amodp}={1,2,…,p-1}所以a×2a×…×(p-1)a≡[(amodp)×(2amodp)×…×((p-1)amodp)]modp≡(p-1)!modp另一方面a×2a×…×(p-1)a=(p-1)!ap-1因此(p-1)!ap-1≡(p-1)!modp由于(p-1)!与p互素，因此(p-1)!有乘法逆元，由乘法可约律得ap-1≡1modp。（证毕）Fermat定理也可写成如下形式：设p是素数，a是任一正整数，则ap≡amodp。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}，且A∩B=Φ，否则ip=jq，其中1≤i≤q-1，1≤j≤p-1,则p是jq的因子，因此是j的因子，设j=kp，k≥1。则ip=kpq，i=kq，与1≤i≤q-1矛盾。所以φ(n)=|Zn|-[|A|+|B|+|C|]=pq-[(q-1)+(p-1)+1]=(p-1)×(q-1)=φ(p)×φ(q)（证毕）例如：由21=3×7，得φ(21)=φ(3)×φ(7)=2×6=12。3.欧拉定理定理4.4（Euler）若a和n互素，则aφ(n)≡1modn。证明：设R={x1,x2,…,xφ(n)}是由小于n且与n互素的全体数构成的集合，a×R={ax1modn,ax2modn,…,axφ(n)modn}，对a×R中任一元素aximodn，因a与n互素，x1与n互素，所以axi与n互素，且aximodnn，因此aximodn∈R，所以a×RR。又因a×R中任意两个元素都不相同，否则aximodn=axjmodn，由a与n互素知a在modn下有乘法逆元，得xi=xj。所以|a×R|=|R|，得a×R=R，所以，,，由每一xi与n互素，知与n互素，在modn下有乘法逆元。所以aφ(n)≡1modn。(证毕）()()11(mod)nniiiiaxnx()()11(mod)nniiiiaxxn()()()11(mod)nnniiiiaxxn()1niix()1niix素性检验是指对给定的数检验其是否为素数。对于大数的素性检验来说没有简单直接的方法，本节介绍一个概率检验法，为此需要以下引理。4.1.4素性检验引理如果p为大于2的素数，则方程x2≡1(modp)的解只有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≡-1(modp)。类似地可得x≡1(modp)。（证毕）引理的逆否命题为：如果方程x2≡1modp有一解x0{-1,1}，那么p不为素数。例如：考虑方程x2≡1(mod8)由4.1.2节Z8上模乘法的结果得12≡1mod8,32≡1mod8,52≡1mod8,72≡1mod8又5≡-3mod8，7≡-1mod8，所以方程的解为1，-1，3，-3，可见8不是素数。下面介绍Miller-Rabin的素性概率检测法。首先将n-1表示为二进制形式bkbk-1…b0，并给d赋初值1，则算法Witness(a,n)的核心部分如下：fori=kdownto0do{x←d;d←(d×d)modn;ifd=1and(x≠1)and(x≠n-1)thenreturnFalse;ifbi=1thend←(d×a)modn}ifd≠1thenreturnFalse;returnTrue.此算法有两个输入参数，n是待检验的数，a是小于n的整数。如果算法的返回值为False，则n肯定不是素数，如果返回值为True，则n有可能是素数。for循环结束后，有d≡an-1modn，由Fermat