东南大学信息安全课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,大家好,*,第二章 信息安全数学基础,胡爱群 教授,1,大家好,主要内容,素数、素数性质、大素数生成方法；,同余、中国剩余定理；,群、环、域、有限域。,2,大家好,素数,定义：设整数,n,0,1,。如果除了,1,和,n,外，,n,没有其它因数（因子），则,n,是素数（或质数、不可约数）。否则,n,叫合数。,素数总是指正整数，通常写成,p,.,例子：,2,，,3,，,5,，,7,都是素数，而,4,，,6,，,10,，,15,，,21,都是合数。,3,大家好,互素的概念,(,a,b,)=(,b,a,);,如果,b|a,则,（,a,b,）,=b;,如果,pa,，,则,（,p,a,）,=,1,即互素,。,a,b,是整数,，,p,是素数,4,大家好,素数的判定和生成,5,大家好,练习：,判断,139,为素数还是合数？,6,大家好,同余的概念,练习：,39=4,mod,(7);61=5,mod,(7).,7,大家好,Euler,函数,定义,：,设,m,是一个正整数，把,0,1,m,-1,中与,m,互素的数的个数记作,(,m,),(,m,),就叫做,Euler,函数。,练习：,求,(,10,)=,？,(,77,)=?,定理,：,设,m,、,n,是两个互素的正整数，则,(,mn,)=,(,m,),(,n,).,对于素数,m,，,(,m,)=?,8,大家好,Euler,函数的推论,设,p,、,q,是不同的素数，,则 （,1,）,(,pq,)=,pq-p-q+1,.,设,n=pq,则（,2,）如果知道,n,和,(n),，,就可求出,p,和,q,.,练习,：证明素数的性质（,1,）和（,2,）。,可求解该二元方程组得到,p,和,q,.,9,大家好,Euler,定理,设,m,是大于,1,的整数，,(,m,),是,m,的,Euler,函数。,如果,a,是满足（,a,m,）,=1,的整数，则,练习,：验证,2,10,=1,mod,(11),。,解：,m,=11,a,=2,(,m,)=10,(2,11)=1,根据,Euler,定理，上式成立。,也可以这样做：,2,10,=1024=1023+1=93,*,11+1=1 mod(11),10,大家好,Fermat,定理,练习,：,p,=17,a,=4,4,17,=4 mod(17),11,大家好,大素数的生成,逐个查找太费时间，可以利用,Euler,定理进行检验，称为,Fermat,素性检验。,Euler,定理：设,n,是大于,1,的整数，,(,n,),是,n,的,Euler,函数。,如果,a,是满足（,a,n,）,=1,的整数，则,如果,n,是一个素数，则,(,n,)=,n,-1,有,a,n,-1,=1 mod(,n,).,反过来说，如果有一个整数,a,且（,a,n,）,=1,使得,a,n,-1,1 mod(,n,),那么,n,是一个合数，不是素数。,例子：,n,=63.,假定,a,=2,2,62,=2,60,2,2,=(2,6,),10,2,2,=64,10,2,2,1 mod(63),因此,63,不是素数。,=1 mod(63),12,大家好,素性检验,给定奇数,n,3,和安全参数,t,，,随机选取整数,b,2,b,n,-2;,计算,r,=,b,n,-1,(mod,n,);,如果,r,1,则,n,是合数；,重复上述过程,t,次。,注意,：上述方法可以检验出来是合数，但若满足,r,=1,的,n,未必是素数。,练习：,n,=561,是合数，但依然满足,r,=1.,提示：,561=3,.,11,.,17,13,大家好,中国剩余定理,14,大家好,15,大家好,求解韩信点兵问题,：,16,大家好,利用中国剩余定理求解大的幂次数,17,大家好,Euclid,除法,及,广义,Euclid,除法,任意两个整数,a,、,b,(,b,0),则对于任意的整数,c,存在唯一的整数,q,、,r,，使得,a=qb+r,，,crb+c,.,例子：,121=2,48+25,例子,：设,a,=169,b,=121,求,a,和,b,的最大公因子，即（,a,b,）,利用广义,Euclid,除法：,169=1,121+48,121=2,48+25,48=1 25+23,25=1 23+2,23=11 2+1,2=2 1,因此（,169,，,121,）,=1.,18,大家好,RSA,算法中私钥的计算,设有两个素数,p,=719,q,=1283.,n=p,q=,719,1283=922477,(,n,)=,(,p,),(,q,)=(,p,-1)(,q,-1)=920476,随机选取整数,e,1,e,(,n,),使得（,e,(,n,),）,=1.,公钥是,K,p,=,n,e,私钥为,d,1,d,d,=657483,19,大家好,群的概念,定义,：设,G,是一个具有结合法的非空集合，如果：,（,1,）满足结合律：,a,b,c,G,都有,(,ab,),c,=,a,(,bc,);,（,2,）,G,中存在单位元：,e,G,对任意,a,G,，都有,ae=ea=a,;,（,3,）,G,中的元素具有可逆元：,对任意,a,G,，,a,-1,G,使得,aa,-1,=,a,-1,a,=,e,.,G,的结合法写作乘法时，,G,称为乘群；,G,的结合法写作加法时，,G,称为加群。,20,大家好,同态的概念,设,G,、,G,是两个群，,f,是,G,到,G,的一个映射，如果对任意的,a,、,b,G,，,都有,f,(,ab,)=,f,(,a,)f(,b,),则,f,叫做,G,到,G,的一个,同态,。,如果,f,是一个加密过程，即,E,(,ab,)=,E,(,a,)E(,b,),称为乘同态。,E,(,a,+,b,)=,E,(,a,)+,E,(,b,),称为加同态。,21,大家好,环的概念,定义：,设,R,具有两种结合法（通常表示为加法和乘法）的非空集合，如果下列条件成立：,（,1,）,R,对于加法构成一个交换群；,（,2,）（结合律）,a,b,c,R,都有,(,ab,),c,=,a,(,bc,);,（,3,）（分配律）,a,b,c,R,都有,a,(,b+c,),=,ab+ac,;,则,R,叫做环。,22,大家好,有限域的概念,集合,F,=,a,，,b,，,，对,F,的元素定义了两种运算：“,+”,和“*”，并满足以下,3,个,条件：,（,1,）,F,的元素关于运算“,+”,构成交换群，设其单位元素为,0,；,（,2,）,F,0,的元素关于运算“*”构成交换群。即,F,中元素排除元素,0,后，,关于“*”法,构成交换群。,（,3,）分配律,成立，即对于任意,元素,a,，,b,，,c,F,，恒有,a,*(,b+c,)=(,b+c,)*,a=a*,b+a,*c,。,p,是素数时,，,F,0,，,1,，,2,，,，,p,-1,，在,mod,p,意义下，关于求和运算“,+”,及,乘积“*”，构成了域。,F,域的元素数目有限时称为,有限域,记为,GF(,p,),。,有限域,元素的,数目称为,有限域的阶,。,23,大家好,GF(p),有限域中的运算,p,=5,24,大家好,三大难解数学问题,1,、大整数的因数分解问题,给定两个大的素数,p,、,q,计算乘积,p,q=n,很容易；,给定大整数,n,，求,n,的素因数,p,、,q,，使得,n=p q,非常困难。,如：,p=200002559,q=80001239,是两个大素数，它们的乘积,n=1670601,但要分解这个数很困难。,25,大家好,2,、离散对数问题,已知有限循环群,G=g,k,|k=0,1,2,及其生成元,g,和阶,n,=|,G,|.,给定整数,a,计算元素,g,a,=h,很容易；,给定元素,h,计算整数,x,0,x,n,使得,g,x,=h,非常困难。,例如：给定,p,=200002559,g,=11,a,=20030428,可以计算出,g,a,=17235257(mod,p,),但要求整数,x,使得,g,x,=17235257(mod,p,),非常困难。,26,大家好,3,、椭圆曲线离散对数问题,已知有限域,F,p,上的椭圆曲线点群,E,(,F,p,)=(,x,y,),F,p,F,p|y,2,=x,3,+ax+b,a,b,F,p,U,O,点,P,=(,x,y,),的阶为一个大的素数。,给定整数,a,计算点,Q=,a,P=(,x,a,y,a,),很容易；,给定点,Q,，计算整数,x,使得,x,P=Q,非常困难。,27,大家好,习题,1.,利用素数判定定理，求所有不超过,110,的素数,.,2.,证明,N=131,为素数,.,3.,求,m=,91,的,Euler,函数,(,91,)=?,4.,用,Euler,定理，验证,2,12,=1,mod,(11).,5.,用中国剩余定理，求,x,=2,100000,mod(55).,28,大家好,结束,29,大家好,