第五讲 公钥密码体制

1Chapter8NumberTheoryandRSA公开密钥密码学计算机学院孟博[e-mail]2Chapter8NumberTheoryandRSA内容数论简介公钥密码学RSA算法3Chapter8NumberTheoryandRSA素数和互素模运算费尔玛定理欧拉函数中国剩余定理离散对数数论简介4Chapter8NumberTheoryandRSA素数和互素数数论简介1.因子设a，b(b≠0)是两个整数，如果存在另一整数m，使得a=mb，则称b整除a，记为b|a，且称b是a的因子。5Chapter8NumberTheoryandRSA2.素数称整数p(p1)是素数，如果p的因子只有±1，±p。任一整数a(a1)都能唯一地分解为以下形式(这一性质称为整数分解的惟一性)：其中p1p2…pt是素数，ai0(i=1,…,t)。例如:91=7×131212ttappp6Chapter8NumberTheoryandRSA3.互素称c是两个整数a、b的最大公因子，如果①c是a的因子也是b的因子，即c是a、b的公因子。②a和b的任一公因子，也是c的因子。表示为c=gcd(a,b)。如果gcd(a,b)=1，则称a和b互素。7Chapter8NumberTheoryandRSA设n是一正整数，a是整数，如果用n除a，得商为q，余数为r，则a=qn+r,0≤rn,其中为小于或等于x的最大整数。用amodn表示余数r，则。如果(amodn)=(bmodn)，则称两整数a和b模n同余，记为a≡bmodn。称与a模n同余的数的全体为a的同余类，记为[a]，称a为这个同余类的表示元素。注意：如果a≡0(modn)，则n|a。xaqnmodaanann模运算8Chapter8NumberTheoryandRSA同余有以下性质：①若n|(a-b)，则a≡bmodn。②(amodn)≡(bmodn)，则a≡bmodn。③a≡bmodn,则b≡amodn。④a≡bmodn,b≡cmodn,则a≡cmodn。9Chapter8NumberTheoryandRSA求余数运算（简称求余运算）amodn将整数a映射到集合{0,1,…,n-1}，称求余运算在这个集合上的算术运算为模运算，模运算有以下性质：①[(amodn)+(bmodn)]modn=(a+b)modn。②[(amodn)-(bmodn)]modn=(a-b)modn。③[(amodn)×(bmodn)]modn=(a×b)modn。10Chapter8NumberTheoryandRSA模8运算11Chapter8NumberTheoryandRSA例:设Z8={0,1,…,7}，考虑Z8上的模加法和模乘法，结果如上表所示。从加法结果可见，对每一x，都有一y，使得x+y≡0mod8。如对2，有6，使得2+6≡0mod8，称y为x的负数，也称为加法逆元。对x，若有y，使得x×y≡1mod8，如3×3≡1mod8，则称y为x的倒数，也称为乘法逆元。本例可见并非每一x都有乘法逆元。12Chapter8NumberTheoryandRSA一般地，定义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)]modn13Chapter8NumberTheoryandRSA③分配律[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的加法逆元得到。14Chapter8NumberTheoryandRSA定理设a∈Zn，gcd(a,n)=1，则a在Zn中有乘法逆元。设p为一素数，则Zp中每一非0元素都与p互素，因此有乘法逆元。类似于加法可约律，可有以下乘法可约律：如果(a×b)≡(a×c)modn且a有乘法逆元，那么对(a×b)≡(a×c)modn两边同乘以a-1，即得b≡cmodn15Chapter8NumberTheoryandRSA费尔玛定理(Fermat)若p是素数，a是正整数且gcd(a,p)=1，则ap-1≡1modp。Fermat定理也可写成如下形式：设p是素数，a是任一正整数，则ap≡amodp。16Chapter8NumberTheoryandRSA设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)例如：由21=3×7，得φ(21)=φ(3)×φ(7)=2×6=12。欧拉函数17Chapter8NumberTheoryandRSA欧拉定理若a和n互素，则aφ(n)≡1modn18Chapter8NumberTheoryandRSA欧几里得算法欧几里得（Euclid）算法是数论中的一个基本技术，是求两个正整数的最大公因子的简化过程。而推广的Euclid算法不仅可求两个正整数的最大公因子，而且当两个正整数互素时，还可求出其中一个数关于另一个数的乘法逆元。19Chapter8NumberTheoryandRSA1.求最大公因子Euclid算法是基于下面一个基本结论：对任意非负整数a和正整数b，有gcd(a,b)=gcd(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。20Chapter8NumberTheoryandRSAEuclid算法就是用这种方法，因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。21Chapter8NumberTheoryandRSA求gcd(1970,1066)。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。22Chapter8NumberTheoryandRSA2.求乘法逆元如果gcd(a,b)=1，则b在moda下有乘法逆元（不妨设ba），即存在一x(xa)，使得bx≡1moda。推广的Euclid算法先求出gcd(a,b)，当gcd(a,b)=1时，则返回b的逆元。23Chapter8NumberTheoryandRSA它是数论中非常有用的一个工具，定理说如果已知某个数关于一些两两互素的数的同余类集，就可重构这个数。例如：Z10中每个数都可从这个数关于2和5（10的两个互素的因子）的同余类重构。比如已知x关于2和5的同余类分别是[0]和[3]，即xmod2≡0，xmod5≡3。可知被2除后余数是0且被5除后余数是3，所以可得8是满足这一关系的惟一的x。中国剩余定理24Chapter8NumberTheoryandRSA中国剩余定理:设m1,m2,…,mk是两两互素的正整数，，则一次同余方程组对模M有惟一解:其中ei满足1kiiMm1122modmodmodkkamxamxamx112212modkkkMMMxeaeaeaMmmm1mod1,2,,iiiMemikiiMMm25Chapter8NumberTheoryandRSA由以下方程组求x。解：M=2·3·5·7=210，M1=105，M2=70，M3=42，M4=30,易求e1≡M-11mod2≡1,e2≡M-12mod3≡1,e3≡M-13mod5≡3,e4≡M-14mod7≡4,所以xmod210≡(105×1×1+70×1×2+42×3×3+30×4×5)mod210≡173，或写成x≡173mod210。1mod22mod33mod55mod7xxxx26Chapter8NumberTheoryandRSA中国剩余定理提供了一个非常有用的特性，即在模M下可将非常大的数x由一组小数(a1,a2,…,ak)表达。27Chapter8NumberTheoryandRSAChineseRemainderTheoremtocomputeA(modM)firstcomputeallai=Amodmiseparatelydetermineconstantscibelow,whereMi=M/mithencombineresultstogetanswerusing:28Chapter8NumberTheoryandRSA29Chapter8NumberTheoryandRSA例：要计算（678＋973）mod1813解：(1)将973mod1813由模数分别为37和49的两个数表示。取x=973,M=1813,m1=37,m2=49。由a1≡973modm1≡11,a2≡973modm2≡42得973在模37和模49下的表达为（11,42）(2)同理可将678mod1813模数分别为37和49的两个数表示:(678mod37,678mod49)=(12,41)(3)计算(11+12mod37,42+41mod49)=(23,34)30Chapter8NumberTheoryandRSA1.求模下的整数幂Euler定理指出如果gcd(a,n)=1，则aφ(n)≡1modn。现在考虑如下的一般形式:am≡1modn如果a与n互素，则至少有一整数m（比如m=φ(n)）满足这一方程。称满足方程的最小正整数m为模n下a的阶。离散对数31Chapter8NumberTheoryandRSA例如：a=7，n=19，则易求出71≡7mod19,72≡11mod19,73≡1mod19，即7在模19下的阶为3。由于73+j=73·7j≡7jmod19,所以74≡7mod19,75≡72mod19,…,即从74mod19开始所求的幂出现循环，循环周期为3，即循环周期等于元素的阶。定理：设a的阶为m，则ak≡1modn的充要条件是k为m的倍数。32Chapter8NumberTheoryandRSA推论：a的阶m整除φ(n)。如果a的阶m等于φ(n)，则称a为n的本原根。如果a是n的本原根，则a,a2,…,aφ(n)在modn下互不相同且都与n互素。特别地，如果a是素数p的本原根，则a,a2,…,ap-1在modp下都不相同。33Chapter8NumberTheoryandRSA例如：n=9，则φ(n)=6，考虑2在mod9下的幂2