现代密码学课件第10讲-公钥密码

公钥密码数论简介公钥密码体制的基本概念RSA算法椭圆曲线密码体制2022/12/11公钥密码数论简介2022/12/11数论简介2022/12/12数论简介2022/12/12模运算设n是一正整数,a是整数,若a=qn+r,0≤r<n,则amodn=r若(amodn)=(bmodn),称为a,b模n同余，记为a≡bmodn称与a模n同余的数的全体为a的同余类，记为[a]，a称为这个同余类的代表元素

2022/12/13模运算设n是一正整数,a是整数,若2022/12/13模运算同余的性质若n|(a-b)，则a≡bmodn(amodn)≡(bmodn),则a≡bmodna≡bmodn，则b≡amodna≡bmodn，b≡cmodn，则a≡cmodn求余运算amodn将a映射到集合{0,1,…,n-1},求余运算称为模运算2022/12/14模运算同余的性质2022/12/14模运算模运算的性质[(amodn)+(bmodn)]modn=(a+b)modn[(amodn)-(bmodn)]modn=(a-b)modn[(amodn)×(bmodn)]modn=(a×b)modn2022/12/15模运算模运算的性质2022/12/15模运算例：Z8={0,1,2,3,4,5,6,7},模8加法和乘法＋01234567001234567112345670223456701334567012445670123556701234667012345770123456×012345670000000001012345672024602463036147254040404045052741636064206427076543212022/12/16模运算例：Z8={0,1,2,3,4,5,6,7},模8加法模运算若x+y=0modn,y为x的加法逆元。每一元素都有加法逆元若对x，有xy=1modn，称y为x的乘法逆元。在上例中，并非所有x都有乘法逆元定义Zn={0,1,..,n-1}为模n的同余类集合。2022/12/17模运算若x+y=0modn,y为x的加法逆元。每一元素模运算Zn上模运算的性质交换律（x+w)modn=(w+x)modn(x×w)modn=(w×x)modn结合律[(x+w)+y]modn=[x+(w+y)]modn[(x×w)×y]modn=[x×(w×y)]modn分配律[w×(x+y)]modn=[w×x+w×y)]modn2022/12/18模运算Zn上模运算的性质2022/12/18模运算单位元(0+w)modn=wmodn(1×w)modn=wmodn加法逆元：对w∈Zn,有z∈Zn，满足w+z=0modn,z为w的加法逆元，记为z=-w。加法的可约律(a+b)≡(a+c)modn,则b≡cmodn对乘法不一定成立，因为乘法逆元不一定存在。2022/12/19模运算单位元2022/12/19模运算定理:设a∈Zn,gcd(a,n)=1,则a在Zn有逆元证明思路：用反证法证明a和Zn中任何两个不同的数相乘结果都不相同从1得出a×Zn=Zn,因此存在x∈Zn,使a×x=1modn设p为素数，Zp中每一个非零元素都与p互素，因此有乘法逆元，有乘法可约律(a×b)=(a×c)modn,b=cmodn2022/12/110模运算定理:设a∈Zn,gcd(a,n)=1,则a在Zn有逆费尔玛定理和欧拉定理费尔玛定理

若p是素数，a是正整数且gcd(a,p)=1，则ap-1≡1modp证明：gcd(a,p)=1,则a×Zp=Zp,a×(Zp-{0})=Zp-{0}{amodp,2amodp,…,(n-1)amodp}={0,1,…,p-1}(amodp)×(2amodp)×…×(n-1)amodp=(p-1)!modp(p-1)!×ap-1=(p-1)!modp(p-1)!与p互素，所以乘法可约律，ap-1=1modp2022/12/111费尔玛定理和欧拉定理费尔玛定理2022/12/111费尔玛定理和欧拉定理欧拉函数设n为一正整数，小于n且与n互素的正整数的个数称为n的欧拉函数，记为j(n)定理：若n是两个素数p和q的乘积，则j(n)＝j(p)j(q)=(p-1)(q-1)欧拉定理若a和n互素,则aj(n)=1modn2022/12/112费尔玛定理和欧拉定理欧拉函数2022/12/112素性检验引理：如果p为大于2的素数，则方程x2≡1modp的解只有和x≡1和x≡-1证明:

x2≡1modpx2-1≡0modp(x+1)(x-1)≡0modp所以,p|(x+1)或p|(x-1)或p|(x+1)且p|(x-1)存在k,j，x+1=kp,x-1=jp2=(k-j)p,这是不可能的。引理的逆命题：若方程x2≡1modp有唯一解x不为+1或-1，p不是素数2022/12/113素性检验引理：如果p为大于2的素数，则方程x2≡1mod素性检验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,有可能是素数。2022/12/114素性检验Miller-Rabin素性概率检测法2022/12素性检测For循环结束,有d≡an-1modn.由费尔玛定理,若n为素数,d为1.所以d≠1，则d不是素数n-1≡-1modn,所以x≠1和x≠n-1指x2≡1modn有非±1的根,n不是素数该算法对s个不同的a，重复调用，如果每次都返回true，则n是素数的概率大于等于1-2-s2022/12/115素性检测For循环结束,有d≡an-1modn.由费尔玛欧几里德算法求两个正整数的最大公因子两个正整数互素，可以求一个数关于另一个数的乘法逆元性质:对任意非负整数a和正整数b,有

gcd(a,b)=gcd(b,amodb)证明：a=kb+r≡rmodbamodb=a-kb设d|a,d|b,所以d|kb.由d|a和d|kb，得d|(amodb)故d是b和amodb的公因子。a,b以及b,amodb公因子集合相同，故最大公因子也相同2022/12/116欧几里德算法求两个正整数的最大公因子2022/12/116Euclid(f,d)f>d1.Xf;Yd;2.IfY=0thenreturnX=gcd(f,d)3.R=XmodY4.X=Y;5.Y=R6.Goto2欧几里德算法例:gcd(55,22)=gcd(22,11)=gcd(11,0)=112022/12/117Euclid(f,d)f>d欧几里德算法例:gcd(55欧几里德算法求乘法逆元若gcd(a,b)=1,b在模a下有乘法逆元(设b<a)。即存在x<a,bx≡1modaExtendedEuclid(f,d)(f>d)1.（X1X2X3)(1,0,f);(Y1Y2Y3)(0,1,d);2.IfY3=0,thenreturnX3=gcd(f,d);noinverse;3.IfY3=1,thenreturnX3=gcd(f,d);Y2=d-1modf;4.Q=X3div

Y3;5.(T1T2T3)(X1-QY1,X2-QY2,X3-QY3);6.(X1X2X3)(Y1Y2Y3);7.(Y1Y2Y3)(T1T2T3);8.Goto22022/12/118欧几里德算法求乘法逆元2022/12/118中国剩余定理如果已知某个数关于一些量量互素的数的同余类集，就可以重构这个数定理(中国剩余定理)：设m1,m2,…,mk是两两互素的正整数，则一次同余方程组对模M有唯一解

2022/12/119中国剩余定理如果已知某个数关于一些量量互素的数的同余类集，就中国剩余定理中国剩余定理可以将一个很大的数x表示为一组较小的数(a1,…ak)例：x≡1mod2,x≡2mod3,x≡3mod5x≡5mod7,求x解：M＝2×3×5×7＝210，M1=105,M2=70,M3=42,M4=30,(Mi=M/mi),可以求得e1=1,e2=1,e3=3,e4=4,所以x=105×1×1＋70×1×2＋42×3×3＋30×4×5mod210＝1732022/12/120中国剩余定理中国剩余定理可以将一个很大的数x表示为一组较小的公钥密码数论简介公钥密码体制的基本概念RSA算法椭圆曲线密码体制2022/12/121公钥密码数论简介2022/12/11数论简介2022/12/122数论简介2022/12/12模运算设n是一正整数,a是整数,若a=qn+r,0≤r<n,则amodn=r若(amodn)=(bmodn),称为a,b模n同余，记为a≡bmodn称与a模n同余的数的全体为a的同余类，记为[a]，a称为这个同余类的代表元素

2022/12/123模运算设n是一正整数,a是整数,若2022/12/13模运算同余的性质若n|(a-b)，则a≡bmodn(amodn)≡(bmodn),则a≡bmodna≡bmodn，则b≡amodna≡bmodn，b≡cmodn，则a≡cmodn求余运算amodn将a映射到集合{0,1,…,n-1},求余运算称为模运算2022/12/124模运算同余的性质2022/12/14模运算模运算的性质[(amodn)+(bmodn)]modn=(a+b)modn[(amodn)-(bmodn)]modn=(a-b)modn[(amodn)×(bmodn)]modn=(a×b)modn2022/12/125模运算模运算的性质2022/12/15模运算例：Z8={0,1,2,3,4,5,6,7},模8加法和乘法＋01234567001234567112345670223456701334567012445670123556701234667012345770123456×012345670000000001012345672024602463036147254040404045052741636064206427076543212022/12/126模运算例：Z8={0,1,2,3,4,5,6,7},模8加法模运算若x+y=0modn,y为x的加法逆元。每一元素都有加法逆元若对x，有xy=1modn，称y为x的乘法逆元。在上例中，并非所有x都有乘法逆元定义Zn={0,1,..,n-1}为模n的同余类集合。2022/12/127模运算若x+y=0modn,y为x的加法逆元。每一元素模运算Zn上模运算的性质交换律（x+w)modn=(w+x)modn(x×w)modn=(w×x)modn结合律[(x+w)+y]modn=[x+(w+y)]modn[(x×w)×y]modn=[x×(w×y)]modn分配律[w×(x+y)]modn=[w×x+w×y)]modn2022/12/128模运算Zn上模运算的性质2022/12/18模运算单位元(0+w)modn=wmodn(1×w)modn=wmodn加法逆元：对w∈Zn,有z∈Zn，满足w+z=0modn,z为w的加法逆元，记为z=-w。加法的可约律(a+b)≡(a+c)modn,则b≡cmodn对乘法不一定成立，因为乘法逆元不一定存在。2022/12/129模运算单位元2022/12/19模运算定理:设a∈Zn,gcd(a,n)=1,则a在Zn有逆元证明思路：用反证法证明a和Zn中任何两个不同的数相乘结果都不相同从1得出a×Zn=Zn,因此存在x∈Zn,使a×x=1modn设p为素数，Zp中每一个非零元素都与p互素，因此有乘法逆元，有乘法可约律(a×b)=(a×c)modn,b=cmodn2022/12/130模运算定理:设a∈Zn,gcd(a,n)=1,则a在Zn有逆费尔玛定理和欧拉定理费尔玛定理

若p是素数，a是正整数且gcd(a,p)=1，则ap-1≡1modp证明：gcd(a,p)=1,则a×Zp=Zp,a×(Zp-{0})=Zp-{0}{amodp,2amodp,…,(n-1)amodp}={0,1,…,p-1}(amodp)×(2amodp)×…×(n-1)amodp=(p-1)!modp(p-1)!×ap-1=(p-1)!modp(p-1)!与p互素，所以乘法可约律，ap-1=1modp2022/12/131费尔玛定理和欧拉定理费尔玛定理2022/12/111费尔玛定理和欧拉定理欧拉函数设n为一正整数，小于n且与n互素的正整数的个数称为n的欧拉函数，记为j(n)定理：若n是两个素数p和q的乘积，则j(n)＝j(p)j(q)=(p-1)(q-1)欧拉定理若a和n互素,则aj(n)=1modn2022/12/132费尔玛定理和欧拉定理欧拉函数2022/12/112素性检验引理：如果p为大于2的素数，则方程x2≡1modp的解只有和x≡1和x≡-1证明:

x2≡1modpx2-1≡0modp(x+1)(x-1)≡0modp所以,p|(x+1)或p|(x-1)或p|(x+1)且p|(x-1)存在k,j，x+1=kp,x-1=jp2=(k-j)p,这是不可能的。引理的逆命题：若方程x2≡1modp有唯一解x不为+1或-1，p不是素数2022/12/133素性检验引理：如果p为大于2的素数，则方程x2≡1mod素性检验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,有可能是素数。2022/12/134素性检验Miller-Rabin素性概率检测法2022/12素性检测For循环结束,有d≡an-1modn.由费尔玛定理,若n为素数,d为1.所以d≠1，则d不是素数n-1≡-1modn,所以x≠1和x≠n-1指x2≡1modn有非±1的根,n不是素数该算法对s个不同的a，重复调用，如果每次都返回true，则n是素数的概率大于等于1-2-s2022/12/135素性检测For循环结束,有d≡an-1modn.由费尔玛欧几里德算法求两个正整数的最大公因子两个正整数互素，可以求一个数关于另一个数的乘法逆元性质:对任意非负整数a和正整数b,有

gcd(a,b)=gcd(b,amodb)证明：a=kb+r≡rmodbamodb=a-kb设d|a,d|b,所以d|kb.由d|a和d|kb，得d|(amodb)故d是b和amodb的公因子。a,b以及b,amodb公因子集合相同，故最大公因子也相同2022/12/136欧几里德算法求两个正整数的最大公因子2022/12/116Euclid(f,d)f>d1.Xf;Yd;2.IfY=0thenreturnX=gcd(f,d)3.R=XmodY4.X=Y;5.Y=R6.Goto2欧几里德算法例:gcd(55,22)=gcd(22,11)=gcd(11,0)=112022/12/137Euclid(f,d)f>d欧几里德算法例:gcd(55欧几里德算法求乘法逆元若gcd(a,b)=1,b