高级密码学数论初步.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,3,部分数论初步,3.1,素 数,定义,2.1,（,整除、倍数、因数）,设,a,、,b,为整数，,例如,30=2,15=310=56,2,，,3,，,5,都是,30,的因数，,30,是,2,，,3,，,5,的倍数。,若存在整数,c,，使,b=ac,，则称,a,可整除,b,。,记作,a|b,。,b,叫做,a,的倍数，,a,叫做,b,的因数。,若不存在这样的整数,c,，则称,a,不能整除,b,。,记作,ab,。,我 们有,2,，,3,，,5,分别整除,30,。,记作分别记为：,2|30,，,3|30,5|30,。,或,30,被,2,，,3,，,5,分别整除。,如果,a|1,，则,a=1,事实上，对于,g=bg,1,（,g,1,为整数），有,b|g,。,又例如,7|84,，,-7|84,，,5|20,，,19|171,，,13|0,38,，,512,。,0,是任何非零整数的倍数，,1,是任何整数的因数，任何非零整数,a,是其自身的倍数。,由此我们可以得出这样的结论,如果,a|b,、,b|a,，则,a=b,如果,b0,，,b,则可整除,0,。,如果,b|g,、,b|h,，对于任何整数,m,和,n,，则满足,b|(mg+nh),。,对于,h=bh,1,（,h,1,为整数），满足,b|h,。,所以有,mg+nh=mbg,1,+nbh,1,=b(mg,1,+nh,1,),所以,b,能整除,mg+nh,。,例,b=7,，,g=14,，,h=63,，,m=3,，,n=2,7|14,，,7|63,，必满足,7|(314+263),。,又由于（,314+263,）,=7(32+29),所以有：,7|(314+263)=7|(7(32+29),定义,2.2,（公约数、最大公约数、素数、互素、两两互素）,设整数,a,b,.l,若有整数,d,满足,d|a,，,d|b,，,.,，,d|l,，则称,d,为它们的公约数。,公约数中最大者成为它们的最大公约数。,记作：,gcd(a,b,.,l),如果,gcd(a,b,.,l)=1,则说,a,b,l,互素。,如果,a,b,.,l,中的每个数都与其它数互素，则称它们两两互素。,性质,2,若,关于公约数有以下性质：,性质,1,若,a,是,b,的倍数，则,gcd,（,a,，,b,）,=b,。,则,gcd(a,b)=gcd(b,c),定义,2.3(,素数,),只有,1,和自身为其因数的大于,1,的整数叫素数。,显然除,2,外，所有素数都是奇数。,寻找素数的方法：,设,n,是一个正整数，如果对所有素数,p,有,其中,p1,、,p2,、,.,、,pt,，,p1p2.Pt,，,ai0,利用按模计算原理也可以用于形如,例,3.7 91=713,，,11011=711,2,13,有了这公式，对于较高指数运算，可以将一个较复杂的运算，变为较简单的运算。下面具一个例子来说明。,例,2.8,求,解,按最普通的算法，首先计算,3,的次方，然后对结果作取模运算。,（,1,）,3,的平方,（,2,）再次平方,（,3,）再乘以,3,利用按模计算原理，即对每次计算的中间结果作取模运算。,(4),取模运算,（,1,）,3,的平方,（,2,）再次平方,（,3,）再乘以,3,对于上式指数运算作取模运算时，我们必须要小心，不能冒然作取指数运算，因为,一般不等于,但,定理,3.3,设,n,是一正整数，,a,1,，,a,2,，,b,1,，,b,2,是四个整数，如果,a,1,b,1,(modn),a,2,b,2,(mod,n,),则：,a,1,+,a,2,b,1,+,b,2,(modn),a,1,a,2,b,1,b,2,(modn),a,1,-,a,2,b,1,-,b,2,(modn),证,:,因为,a,1,b,1,(,mod,n),，,a,2,b,2,(,modn,),，所以存在,k,1,，,k,2,使得,a,1,=b,1,+k,1,n,a,2,=b,2,+k,2,n,a,1,+a,2,=b,1,+b,2,+(k,1,+k,2,)n,a,1,a,2,=b,1,b,2,+(k,1,b,2,+k,2,b,1,+k,1,k,2,n)n,因为,k,1,+k,2,，,k,1,b,2,+k,2,b,1,+k,1,k,2,n,都是整数，所以我们有,a,1,+,a,2,b,1,+,b,2,(modn),a,1,a,2,b,1,b,2,(modn),推理,2.1,设,n,是一正整数，设,a,1,，,a,2,，,a,t,，,b,1,，,b,2,，,b,t,如果有,a,1,b,1,(,mod,n),a,2,b,2,(,modn,),a,t,b,t,(,mod,n),(1)a,1,+a,2,+a,t,b,1,+b,2,+b,t,(modn),(2)a,1,-a,2,-a,t,b,1,-b,2,-b,t,(modn),特别,当,b,1,=b,2,=b,t,=b,时，则：,（,1,）,a,1,+a,2,+a,t,tb(modn),(2),a,1,a,2,a,t,b,t,(modn),2.3,一次同余方程,定义,2.9,设,n,位自然数，,f(x),为正系数多项式，,且,nam,其表现形式,则方程,称为关于模,n,的,x,的,m,次同余方程。,定理,2.2,（素数模的同余方程解的个数）设,n,为素数，则同余方程,的解的个数（包括重解的重数在内），小于等于,n,例,x,5,+x+1=0 mod(7),首项系数为,1,的模,7,同余式。,而,X=2(mod7),是该同余式的解，事实上，我们有,2,5,+2+1=350,（,mod7,）,还有解,x4(mod7),所以解个数为,2,在一次同余方程中我们特别感兴趣的是形如,这个方程的含义是，必存在,x,的值满足在,modn,的条件下，其余数为,1,。,它是我们以后将上密钥体制是要经常用到。,引理,2.1,若,gcd(k,n)=1,则,为,n,的一个完全剩余系。,证 根据完全剩余系的定义，我们只要证明,ik,个属于,分别属于,n,的对模,n,的不同的同余类即可。,若,而,则有,由,推出,但,i,、,j,都大于,0,且小于,n,，因此是不可能的，故必有,定理,2.2,若,gcd,（,a,，,n,）,=1,，则一次同余方程,有解，且有唯一的解。,定义,2.9,（乘法逆元）令,b,的解，,则说在关于模,n,乘法运算中，,a,与,b,互逆，,b,是,a,关于模,n,的乘法逆元。,有了乘法逆元为解方程创造一个条件，,axmodn=1,例：求,5,关于模,14,的乘法逆元。,的解，,引理,2.3,若 为模,n,的一个缩剩余系，又 ，则,也为一个缩剩余系,证,显然有,故每个,ka,i,，都属于,n,的互素的同余类。,我们只要证明彼此的不同，即可证明,了此引理,。,若,，同时有,则有,或,由（,k,，,n,）,=1,得,即,这与,a,i,、,a,j,为缩剩余系的不同元素矛盾，所以必有,即,分别属于不同的同余类。,对于任一素数,p,，小,0,于,p,且与,p,互素的数正数的个数显然等于,p-1,，从而,下面我们将引入两个素数,p,和,q,的积的定理。,定理,2.3,当,p,、,q,为素数时，对 ，有,证,考虑,n,的完全剩余系,，除,p-1,个元素,和,q-1,个元素,以及,0,除外，其余所有元素都与,n,互素，因此有,下面我们将举一个例子对此定理的理解。,例,2.7,求,解，,3,和,5,皆为素数，有定理,2.3,得：,15,的缩剩余系确有,8,个元素，它们是,1,，,2,，,4,，,7,，,8,，,11,，,13,，,14,定理,2.4,对任意整数,n,，若其标准分解式为,则其,Euler,函数为,：,例,2.8,求,所以,24,的剩余系包含,8,个元素。它们是,1,，,3,，,7,，,11,，,13,，,17,，,19,，,23,。,定理,2.5,（,Euler,定理）对任意整数,k,和,n,，若（,k,，,n,）,=1,，则,证,若,为模,n,的一个缩剩余系，则,即：,约简之后，得,当,n,为素数时，,，所以,Euler,定理也可以用来对,来对素数检测。若对任意,有,例,2.9 K=3,，,n=10,，,(10)=4,，所以,3,4,=81,1,（,mod10,）；,k=2,，,n=11,，,(11)=10,，所以,2,10,=10241,（,mod11,）,定理,2.5,（,Fermat,定理）设,P,为素数，则对任意整数,a,，有,证,由于,p,是素数，显然有,。于是,当,时，由,Euler,定理，有：,在,时，,由于,p,为素数，必有,，定理显然成立,。,例,2.10,若,p=5,，,a=3,，所以有,3,5,=243,3,（,mod5,）,若,p=5,，,a=10,，所以有,105=100000,10,（,mod5,）,0,（,mod5,）,Fermat,定理和,Euler,给出了方程,的解为,若,n,为素数，可进一步简化上式为,例：,解：,得：,下面验算之,我们很容易进一步扩充此算法，以求解一般一次同余方程,若,gcd,（,a,，,n,）,=1,，,方法,第一步：求,ax 1(modn),可得,第二步：求,ax b (modn),由,可得,所以方程的解为,定理,2.7(,孙子定理，又称为中国剩余定理,),令,n,k,=d,1,d,2,.d,k,，且,d,1,d,2,.,d,k,两两互素,则方程组,x x,1,(modd,1,),x x,2,(modd,2,),.,x x,k,(modd,k,),在（,0,，,n-1,）内有惟一解。,证 对任意,i=1,2,k,有,为了便于理解我们将上式写成,所以存在,y,i,满足：,令：,又令：,即,我们注意到,d,j,是,n,k,/d,i,的因子,对于,i,j,所以,x,是方程组,的解,现在我们来证明，它也是方程组在（,0,，,n-1,）内的唯一解。,设,x,是方程组的第一个方程的解，所以可得,将它代入,得：,由于,gcd,故由定理,2.2,知，以上方程中的,k,1,对,d,2,是唯一的解,于是满足第一、二个方程的,x,对模,d,1,、,d,2,也是惟一的解,设,将它代入第三个方程，仿照以上证明，又可证的,k,2,对,d,3,也是惟一的解既满足第一、二、三个方程的,x,对模,d,1,d,2,d,3,也是惟一的解。,如此类推，可以证明满足全部方程的,x,对模,d,1,d,2,d,k,是惟一解。,例,1.5,解方程,解 由于,所以,我们首先分别求解方程,的解,解出：,x1=1,，,x2=2,然后用孙子定理求解方程,为此首相找出满足,Y1=1,y2=3,于是得到,2.4,二次剩余,定义,2.10,（二次剩余、二次非剩余、平方根）,设,n,为大于,1,的整数（,a,，,n,）,=1,，若二次同余方程,有解，则称,a,为对模,n,的二次剩余。,否则，则称之为对模,n,的二次非剩余。,满足以上方程的,x,成为未对模,n,的,a,的平方根。,定义,2.10,（二次剩余系）在小于,n,正整数中，模,n,的二次剩余的集合称为二次剩余系。记作。,R,2,定理,2.6,对于任何奇素数,p,和任意,a,0ap,方程,密码学中相关算法,在密码学中为了考虑更高级别的安全性需要密钥较长。,如,RSA,密码体制有时需要密钥长度达到,1024bit,长，使得现有一般计算机无法满足对此的计算，产生溢出，造成运算结果错误。,因此就有必要设计一个算法来解决运算产生溢出问题。,为了解决以上问题我们主要从以下两个方面考虑：,组织参与运算的数据,根据所组织参与运算的数据设计算法,（,1,）组织参与运算的数据,假设实现运算的计算机的字长为,W,位。,W,通常是,8,的整数倍。,通常工作站的字长为,64,位或,32,位。,而低档的计算机字长,w,可能还小些。,如某些嵌入式计算机的字长是,16,位，而智能卡的字长可能只有,8,位。,设整数,m,的二进制长度为,p,t=m/W,表示,W,位子的个数,显然整数,m,以二进制形式存储在一个,t,个,w,位字的数组,A,A,为,At-1,，,At-2,，,.A2,A1,A0,其中最右边的,A0,是存放最低的数据部分。,At-1,.,A2,A1,A0,如果两个数大数分别为,m,1,，,m,2,按照以上的组合方法,将,m1,从高位到低位分别存放到数组,A:,即：,At-1,At-2,.A2,A1,A0,M2,从高位到低位分别存放到数组,B,中即：,Bt-1,Bt-2,.B2,B1,B0,(2),设计算法,加法,设加的结果放在数组元素,C,中即：,Ct-1,Ct-2,.C2,C1,C0,设,用来存放,进位位,执行以下算法,减法运算,步骤,1.(,C0,),A0+B0,步骤,2.1.(,Ci,),Ai+Bi+,步骤,2.,对于,i,从,1,到,t-1,重复执行。,步骤,3.,输出（,C),设加的结果放在数组元素,C,中即：,设,用来存放,借位位,Ct-1,Ct-2,.C2,C1,C0,执行以下算法,步骤,1.(,C0,),A0-B0,步骤,2.,对于,i,从,1,到,t-1,重复执行。,乘法运算,设乘的结果放在数组元素,C,中即：,Ct-1,Ct-2,.C2,C1,C0,设（,U,V),表示一个,2W,位的变量，,这两个变量用于存放运算的中间结果,执行以下算法,步骤,1.0=i0,则存在惟一的整数,q,，,r,使得：,a=bq+r 0=rb,反复运用欧几里德除法得：,r,0,=r,1,q,1,+r,2,0=r,2,r,1,r,1,=r,2,q,2,+r,3,0=r,3,r,2,.,r,n-2,=r,n-1,q,n-1,+r,n,0=r,n,r,n-1,r,n-1,=r,n,q,n,+r,n+1,r,n+1,=0,定理 设,a,b,是任意两个整数，则,gcd(a,b)=r,n,。,其中,r,n,是广义欧几里得除法中最后一个非,0,余数。,设,a=1859,b=1573,计算,gcd(a,b),1859=1,1573+286,1573=5286+143,286=2143,