1、2022-12-151公钥密码公钥密码n数论简介数论简介n公钥密码体制的基本概念公钥密码体制的基本概念nRSARSA算法算法n椭圆曲线密码体制椭圆曲线密码体制2022-12-152数论简介数论简介2022-12-153模运算模运算n设设n n是一正整数是一正整数,a,a是整数是整数,若若 a=qn+r,0rn,a=qn+r,0rd1.Xf;Yd;2.If Y=0 then return X=gcd(f,d)3.R=X mod Y4.X=Y;5.Y=R6.Goto 2欧几里德算法欧几里德算法n例例:gcd(55,22)=gcd(22,11)=gcd(11,0)=112022-12-1518欧几里
2、德算法欧几里德算法n求乘法逆元求乘法逆元n若若gcd(a,b)=1,bgcd(a,b)=1,b在模在模a a下有乘法逆元下有乘法逆元(设设ba)ba)。即存在即存在xa,bx1 mod axd)1.（X1 X2 X3)(1,0,f);(Y1Y2 Y3)(0,1,d);2.If Y3=0,then return X3=gcd(f,d);no inverse;3.If Y3=1,then return X3=gcd(f,d);Y2=d-1 mod f;4.Q=X3 div Y3;5.(T1 T2 T3)(X1-QY1,X2-QY2,X3-QY3);6.(X1 X2 X3)(Y1Y2 Y3);7.(
3、Y1Y2 Y3)(T1 T2 T3);8.Goto 22022-12-1519中国剩余定理中国剩余定理n如果已知某个数关于一些量量互素的数的同余类如果已知某个数关于一些量量互素的数的同余类集，就可以重构这个数集，就可以重构这个数n定理定理(中国剩余定理中国剩余定理)：设设m1,m2,mk是两两互素的正整数，是两两互素的正整数，则一次同余方程组则一次同余方程组 对模对模M有唯一解有唯一解 kiimM1kkamxamxamxmodmodmod2211iiiikkkmemMeMaemMaemMaemMxmod1mod)(222111满足2022-12-1520中国剩余定理n中国剩余定理可以将一个很大的数中国剩余定理可以将一个很大的数x表示为一表示为一组较小的数组较小的数(a1,ak)n例：例：x1 mod 2,x2 mod 3,x3 mod 5 x5 mod 7,求求xn解：解：M2357210，M1=105,M2=70,M3=42,M4=30,(Mi=M/mi),可以可以求得求得e1=1,e2=1,e3=3,e4=4,所以所以x=10511701242333045 mod 210173
