密码学 第8章 公钥密码

第8章公钥密码数论简介公钥密码体制的基本概念RSA算法背包密码体制Rabin密码体制椭圆曲线密码体制数论简介素数和互素数因子设a,b(b≠0)是两个整数，如果存在另一整数m，使得amb，则称b整除a，记为b|a，且称b是a的因子。整数具有以下性质：①a|1，那么a=±1。②a|b且b|a，则a=±b。③对任一b(b≠0)，b|0。④b|g，b|h，则对任意整数m、n有b|(mg+nh)。素数称整数p(p1)是素数，如果p的因子只有±1，±p。任一整数a(a1)都能惟一地分解为以下形式：1212taaatappp其中p1p2…pt是素数，0(1,2,)iait。例如91=7×13，11011=7×112×13整数分解的惟一性：设P是所有素数集合，则任意整数a(a1)都能惟一地写成以下形式：papPap其中0pa,等号右边的乘积项取所有的素数，然而大多指数项pa为0。相应地，任一正整数也可由非0指数列表表示。例如：11011可表示为{a7=1,a11=2,a13=1}。两数相乘等价于对应的指数相加，即由k=mn可得：对每一素数p,kp=mp+np。而由a|b可得：对每一素数p,ap≤bp。这是因为kp只能被()jpjk整除。互素数称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,aqn其中x为小于或等于x的最大整数。用amodn表示余数r，则modaanann。如果(amodn)=(bmodn)，则称两整数a和b模n同余，记为a≡bmodn。称与a模n同余的数的全体为a的同余类，记为[a]，称a为这个同余类的表示元素。注意：如果a≡0(modn)，则n|a。同余有以下性质：①若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。例：设Z8={0,1,…,7}，考虑Z8上的模加法和模乘法。+01234567×01234567001234567000000000112345670101234567223456701202460246334567012303614725445670123404040404556701234505274163667012345606420642770123456707654321加法：对每一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的加法逆元得到。类似性质对乘法不一定成立。例如6×3≡6×7≡2mod8，但37mod8。原因：6乘以0到7得到的8个数仅为Z8的一部分。即如果将对Z8作6的乘法6×Z8（即用6乘Z8中每一数）看作Z8到Z8的映射的话，Z8中至少有两个数映射到同一数，因此该映射为多到一的。所以对6来说，没有惟一的乘法逆元。但对5来说，5×5≡1mod8，因此5有乘法逆元5。仔细观察可见，与8互素的几个数1，3，5，7都有乘法逆元。这一结论可推广到任一Zn。定理：设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×ZnZn，所以a×Zn=Zn。因此对a∈Zn，存在x∈Zn，使得a×x≡1modn，即x是a的乘法逆元。记为1xa。（证毕）设p为一素数，则Zp中每一非0元素都与p互素，因此有乘法逆元。类似于加法可约律，可有以下乘法可约律：如果(a×b)≡(a×c)modn且a有乘法逆元，那么对(a×b)≡(a×c)modn两边同乘以a-1，即得b≡cmodn费尔玛（Fermat）定理若p是素数，a是正整数且gcd(a,p)=1，则ap-1≡1modp。证明：当gcd(a,p)=1时,a×Zp=Zp。又知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。欧拉函数设n是一正整数，小于n且与n互素的正整数的个数称为n的欧拉函数，记为φ(n)。例如：φ(6)=2，φ(7)=6，φ(8)=4。若n是素数，则显然有φ(n)=n-1。定理：若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。定理2.2假定,1nieiipm这里ip均为素数且互不相同，niei1,0。则：nieieiiippm11)()(.若,mpqp、q是素数,则)1)(1()(qpm回顾欧拉函数的求值公式：欧拉（Euler）定理若a和n互素，则()1modnan。证明：设12(){,,,}nRxxx是由小于n且与n互素的全体数构成的集合，12(){mod,mod,,mod}naRaxnaxnaxn，先证aRR：对a×R中任一元素modiaxn，因a与n互素，xi与n互素，所以axi与n互素，且modiaxnn，因此modiaxnR，所以aRR。又因a×R中任意两个元素都不相同，否则modmodijaxnaxn，由a与n互素知a在modn下有乘法逆元，得xi=xj。所以|a×R|=|R|，得aRR。由aRR，有()()11(mod)nniiiiaxnx，即()()11(mod)nniiiiaxxn，即()()()11(mod)nnniiiiaxxn因为每一xi与n互素，知()1niix与n互素，()1niix在modn下有乘法逆元。所以()1modnan。(证毕）欧几里得算法求两个正整数的最大公因子推广的Euclid算法不仅可求两个正整数的最大公因子，而且当两个正整数互素时，还可求出其中一个数关于另一个数的乘法逆元。求最大公因子定理：对任意非负整数a和正整数b，有gcd(a,b)=gcd(b,amodb)。证明：b是正整数，因此可将a表示为a=kb+r≡rmodb，amodb=r,其中k为一整数，所以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,55mod22)=gcd(22,11)=gcd(11,0)=11。gcd(18,12)=gcd(12,6)=gcd(6,0)=6,gcd(11,10)=gcd(10,1)=gcd(1,0)=1。Euclid算法描述：因gcd(a,b)=gcd(|a|,|b|)，因此可假定算法的输入是两个正整数，设为d，f，并设fd。Euclid（f,d）1.X←f;Y←d；2.ifY=0thenreturnX=gcd(f,d)；3.R=XmodY；4.X=Y；5.Y=R；6.goto2。1970=1×1066+904,gcd(1066,904)1066=1×904+162,gcd(904,162)904=5×162+94,gcd(162,94)162=1×94+68,gcd(94,68)94=1×68+26,gcd(68,26)68=2×26+16,gcd(26,16)26=1×16+10,gcd(16,10)16=1×10+6,gcd(10,6)10=1×6+4,gcd(6,4)6=1×4+2,gcd(4,2)4=2×2+0,gcd(2,0)因此gcd(1970,1066)=2。例:求gcd(1970,1066)。求乘法逆元如果gcd(a,b)=1，则b在moda下有乘法逆元（不妨设ba），即存在一x(xa)，使得bx≡1moda。推广的Euclid算法先求出gcd(a,b)，当gcd(a,b)=1时，则返回b的逆元。ExtendedEuclid(f,d)（设fd）1.(X1,X2,X3)←(1,0,f);(Y1,Y2,