置换多项式及rsa密码体制的实现.doc.doc

:传统的密码编制体制有着较多的缺陷,得益于置换多项式的诸多优点提出了RSA密码体制,很好的保证了密码体制的安全性。其中迪克逊多项式和有理置换函数在RSA系统中有重大的意义。关键字:置换多项式RSA系统迪克逊多项式置换多项式正文:第一章:置换多项式的简单性质数学王子高斯在1801年的著作《算术探讨》首先提出了完全剩余系的问题。设m是一个正整数,从模m的每一个剩余类中选取一个代表元组成的集,称为模m的一个完全剩余系。例如,组成的模m的一个完全剩余系,,,0,1......m也组成模m的一个完全剩余系。,,m,1,m,2,....2m完全剩余系的最简单的构造是,这里a是与m,,,,b,a,b,2a,b,...,m,1a,bax,b互素的一个整数。所以,可以用简单的线性多项式表示。即当x取值ax,b0,1,...,m-1时,刚好是所构造的完全剩余系。于是,有了置换多项式的定义:定义:设是一整系数多项式,如果当x为模m的一个完全剩余系时,,,fx,,也为模m的一个完全剩余系,则称,,是模m的置换多项式。也即,,,导fxfxfx出,,的一个置换。0,1......m不加证明的得到置换多项式的几条简单的性质:,,:从,,,,,,知,,,是模m的置换多项式相当于性质1fx,m,fxmodmfx,,,,,,,,是模m的一个完全剩余系。f0,f1,...,fm,12m性质:设,,,,是模m的两个置换多项式,,则,,,,不,,fx,,fx,gx2gx是模m的置换多项式。需要注意的是,当m为奇数时,性质不成立。例如,取,,,,,,,fx,gx2m,5,,,,,,,,,,gx,2x,,则fx,gx是模5的置换多项式,而fx,gx,3x也是模1/115的置换多项式。性质:设,是模m的两个置换多项式,则乘积不是,,,,,,,,,,3fxgxfx,gx模m的置换多项式。k,性质:设是m的标准分解式,则是模m的置换多项式当m,pi,,,,fx4,i,i1a,,pi,1,...,k且仅当是模的置换多项式。,,fxi第二章:迪克逊多项式有了置换多项式的这些基本的性质,我们着重的学****一类非常重要的置换多项式,即迪克逊多项式。定义迪克逊多项式如下:k,,,,2,,k-jk,,jk-2j,,-ax,,,其中,表示实数b的整数部分。,,gx,ab,,,,kk-jj,,j,0k,,,,aak易得等式=,,,,,特别的,当a=0时有,,gb,agy,a,y,,kk,,,,yy,,,,k,,=。gx,0xk下面证明两个非常重要的定理。a,0,a,FF定理:设。则由迪克逊多项式是的置换多项式,,,,1gx,appk22F,p-1,k,p,,,p-1当且仅当,=1;,,是得正则置换多项式当且仅当=1。,gx,akpk证明:首先证明定理的第一部分。2,F,k,p,,,p-1,,设=1。若有b,c使得,,=,,,只需证明b=c,gb,agc,apkk-1FF在的某一个二次扩域中取一非零元使,,a,,b;同样又在的另一,pp-1,,,a,,c个二次扩域中取一非零元使。FF,又因为的所有二次扩域都是同构的,所以,和都可以在的同一,pp个二次扩域中选取。F2p2/11kk,,,,aakk,,则有,===。,,,,gb,agc,a,,,,,,kk,,,,,,,,,,kkkkkkk,1因此,。由此有=或=。无论哪种情况都,,,,,,,,,,a,0,,a,,F有b,c。即是的置换多项式。,,gb,apk反证法。,,,22d2k,1设=d,若,则,p不能被2整除,则只含x的,,k,p-1,,gx,ak*偶数次方幂,因此对所有有=。F,,,,gc,ag-c,ac,Pkk而,固不是的置换多项式。下设2不能被d整除,则有d,,Fc,-cgx,aPk,,,,rp,1rkrp-1的奇数因子r,,或。分两种情况:*rr,,rp-1Fb,1当时,方程在中有r个解,因此存在b,,,,,,F1x,1b,1pP-1kk,b,1a。于是,则可以得到g,b,ab,a==,又,a。,,g1,a,ab,11,akk-1所以,这样就不是的置换多项式。,,Fgx,ab,ab,1,aPkp,1,,rp,1,当时,设是的二次扩域中的一元,使得,,a。F,,2F2Ppr-2r,1因为,在中有r个解,于是存在,,=1,,a,。,,,x,1FF22pp-1p,1k-1,,,,g,,,a,,,a,这样就有,,1,且g,,,a,,a=。,,1kk-1pp因为,中的所有零点组成,故有,,a,,,,,,Fx-xF2Pp-1p,,,,,,,a,,,,,,,=F。,P-1-2-1,,,,,,,a,,因为,,,所以则有,,,a,,因此,,不是Fgx,a,,1Pk的置换多项式。下面