《现代密码学课件110讲第10讲》由会员分享，可在线阅读，更多相关《现代密码学课件110讲第10讲（22页珍藏版）》请在金锄头文库上搜索。
1、2019/6/21,1,第五章 公钥密码,2019/6/21,2,公钥密码,数论简介 公钥密码体制的基本概念 RSA算法 椭圆曲线密码体制,2019/6/21,3,数论简介,2019/6/21,4,模运算,设n是一正整数,a是整数,若 a=qn+r, 0rn, 则a mod n=r 若(a mod n)=(b mod n),称为a,b模n同余，记为ab mod n 称与a模n同余的数的全体为a的同余类，记为a，a称为这个同余类的代表元素,2019/6/21,5,模运算,同余的性质 若n|(a-b)，则ab mod n (a mod n) (b mod n),则ab mod n ab mod n
2、，则ba mod n ab mod n， bc mod n，则ac mod n 求余运算a mod n将a映射到集合0,1,n-1,求余运算称为模运算,2019/6/21,6,模运算,模运算的性质 (a mod n)+(b mod n) mod n=(a+b) mod n (a mod n)-(b mod n) mod n=(a-b) mod n (a mod n)(b mod n) mod n=(ab) mod n,2019/6/21,7,模运算,例：Z8=0,1,2,3,4,5,6,7,模8加法和乘法,2019/6/21,8,模运算,若x+y=0 mod n, y为x的加法逆元。每一元素都
3、有加法逆元 若对x，有xy=1 mod n，称y为x的乘法逆元。在上例中，并非所有x都有乘法逆元 定义Zn=0,1,n-1为模n的同余类集合。,2019/6/21,9,模运算,Zn上模运算的性质 交换律 （x+w) mod n=(w+x) mod n (xw) mod n=(wx) mod n 结合律 (x+w)+y mod n=x+(w+y) mod n (xw) y mod n=x(wy) mod n 分配律 w(x+y) mod n=wx+wy) mod n,2019/6/21,10,模运算,单位元 (0+w) mod n=w mod n (1w) mod n=w mod n 加法逆元：
4、对wZn,有zZn，满足w+z=0 mod n, z为w的加法逆元，记为z=-w。 加法的可约律 (a+b)(a+c) mod n, 则bc mod n 对乘法不一定成立，因为乘法逆元不一定存在。,2019/6/21,11,模运算,定理:设aZn,gcd(a,n)=1,则a在Zn有逆元 证明思路： 用反证法证明a和Zn中任何两个不同的数相乘结果都不相同 从1得出aZn=Zn,因此存在xZn,使ax=1 mod n 设p为素数，Zp中每一个非零元素都与p互素，因此有乘法逆元，有乘法可约律 (ab)=(ac) mod n, b=c mod n,2019/6/21,12,费尔玛定理和欧拉定理,费尔玛
5、定理 若p是素数，a是正整数且gcd(a,p)=1，则ap-11 mod p 证明： gcd(a,p)=1,则aZp=Zp, a(Zp-0)=Zp-0 a mod p,2a mod p,(n-1)a mod p =0,1,p-1 (a mod p) (2a mod p) (n-1)a mod p=(p-1)! mod p (p-1)! ap-1=(p-1)! mod p (p-1)!与p互素，所以乘法可约律，ap-1=1 mod p,2019/6/21,13,费尔玛定理和欧拉定理,欧拉函数 设n为一正整数，小于n且与n互素的正整数的个数称为n的欧拉函数，记为j(n) 定理：若n是两个素数p和q
6、的乘积，则j(n) j(p) j(q)=(p-1)(q-1) 欧拉定理 若a和n互素,则aj(n)=1 mod n,2019/6/21,14,素性检验,引理：如果p为大于2的素数，则方程x21 mod p的解只有和x1和x-1 证明: x21 mod p x2 -1 0 mod p (x+1)(x-1)0 mod p 所以,p|(x+1)或p|(x-1) 或p|(x+1)且p|(x-1)存在k,j，x+1=kp, x-1=jp2=(k-j)p, 这是不可能的。 引理的逆命题：若方程x21 mod p有唯一解x不为+1或-1，p不是素数,2019/6/21,15,素性检验,Miller-Rabi
7、n素性概率检测法 n为待检测数，a为小于n的整数，将n-1表示为二进制形式bkbk-1b0,d赋初值为1，算法核心如下 for i=k downto 0 do xd; d(dd) mod n; if d=1 and (x1)and(xn-1) then return False if bi=1 the d(da) mod n if d 1 then return False; return True 若返回False,n不是素数,若返回True,有可能是素数。,2019/6/21,16,素性检测,For循环结束,有dan-1 mod n.由费尔玛定理,若n为素数,d为1.所以d1，则d不是素数
8、 n-1-1 mod n,所以x 1和x n-1指x21 mod n 有非1的根,n不是素数 该算法对s个不同的a，重复调用，如果每次都返回true，则n是素数的概率大于等于1-2-s,2019/6/21,17,欧几里德算法,求两个正整数的最大公因子 两个正整数互素，可以求一个数关于另一个数的乘法逆元 性质: 对任意非负整数a和正整数b,有 gcd(a,b)=gcd(b,a mod b) 证明： a=kb+rr mod ba mod b=a-kb 设d|a,d|b, 所以d|kb. 由d|a和d|kb，得d|(a mod b) 故d是b和a mod b的公因子。 a,b以及b,a mod b公
9、因子集合相同，故最大公因子也相同,2019/6/21,18,Euclid(f,d) fd 1. Xf;Yd; 2. If Y=0 then return X=gcd(f,d) 3. R=X mod Y 4. X=Y; 5. Y=R 6. Goto 2,欧几里德算法,例:gcd(55,22)=gcd(22,11)=gcd(11,0)=11,2019/6/21,19,欧几里德算法,求乘法逆元 若gcd(a,b)=1, b在模a下有乘法逆元(设bd) 1.（X1 X2 X3)(1,0,f);(Y1Y2 Y3)(0,1,d); 2. If Y3=0, then return X3=gcd(f,d);n
10、o 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. (Y1Y2 Y3)(T1 T2 T3); 8.Goto 2,2019/6/21,20,中国剩余定理,如果已知某个数关于一些量量互素的数的同余类集，就可以重构这个数 定理(中国剩余定理)： 设m1,m2,mk是两两互素的正整数， 则一次同余方程组 对模M有唯一解,2019/6/21,21,中国剩余定理,中国剩余定理可以
11、将一个很大的数x表示为一组较小的数(a1,ak) 例：x1 mod 2, x2 mod 3, x3 mod 5 x5 mod 7,求x 解：M2357210，M1=105, M2=70, M3=42, M4=30, (Mi=M/mi),可以求得e1=1, e2=1, e3=3, e4=4,所以x=10511701242333045 mod 210173,2019/6/21,22,离散对数,求模下的整数幂 根据欧拉定理，若gcd(a,n)=1,则af(n) 1 mod n。考虑一般am 1 mod n, 如果a,n互素，至少有一个整数m满足这一方程。称满足这一方程的最小正整数m为模n下a的阶。 例：a=7,n=19. 71 7 mod 19, 72 11 mod 19, 73 1 mod 19,所以7模19的阶为3。从幂次为4开始出现循环，循环周期与元素的阶相同,
