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

置换多项式及RSA密码体制的实现.doc 置换多项式及RSA密码体制的实现 摘要:传统的密码编制体制有着较多的缺陷，得益于置换多项式的诸多优点提出了RSA密码体制，很好的保证了密码体制的安全性。其中迪克逊多项式和有理置换 函数 excel方差函数excelsd函数已知函数     2 f x m x mx m      2 1 4 2拉格朗日函数pdf函数公式下载 在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，b ax，b互素的一个整数。所以，可以用简单的线性多项式表示。即当x取值 ax，b0,1，...，m-1时，刚好是所构造的完全剩余系。 于是，有了置换多项式的定义: 定义:设是一整系数多项式，如果当x为模m的一个完全剩余系时，，，fx ，，也为模m的一个完全剩余系，则称，，是模m的置换多项式。也即，，，导fxfxfx出,,的一个置换。 0,1......m 不加证明的得到置换多项式的几条简单的性质: ，，:从，，，，， ，知，，，是模m的置换多项式相当于性质1fx，m,fxmodmfx ,,，，，，，，是模m的一个完全剩余系。 f0,f1,...,fm,1 2m性质:设，，，，是模m的两个置换多项式，，则，，，，不，，fx，，fx，gx2gx 是模m的置换多项式。 需要注意的是，当m为奇数时，性质不成立。例如，取，，，，，，，fx,gx2 m,5，，，，，，，，，，gx,2x，，则fx,gx是模5的置换多项式，而fx，gx,3x也是模 1 / 11 5的置换多项式。 性质:设，是模m的两个置换多项式，则乘积不是，，，，，，，，，，3fxgxfx,gx模m的置换多项式。 k,性质:设是m的 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 分解式，则是模m的置换多项式当m,pi，，，，fx4,i,i1 a，，pi,1,...,k且仅当是模的置换多项式。 ，，fxi 第二章:迪克逊多项式 有了置换多项式的这些基本的性质，我们着重的学习一类非常重要的置换多项式，即迪克逊多项式。 定义迪克逊多项式如下: k，，,,2，，k-jk,,jk-2j，，-ax，，,其中，表示实数b的整数部分。 ,,gx，ab,,,,kk-jj,,j,0 k,,,,aak易得等式=,,,,，特别的，当a=0时有，，gb，agy，a,y，，kk,,,,yy,,,, k，，=。 gx，0xk 下面证明两个非常重要的定理。 a,0，a,FF定理:设。则由迪克逊多项式是的置换多项式，，，，1gx，appk 22F，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个二次扩域中选取。 F2p 2 / 11 kk,,,,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，aPk p，1，，rp，1,当时，设是的二次扩域中的一元，使得,,a。 F，，2F2Pp r-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 的置换多项式。 下面证明定理的第二部分。 kaa,,,kx，，gx，，a我们有=，对x求导，可得,,,kxx,,, 3 / 11 kk2kaaaa，，x-ak,,,,,,k-1kgx，a1-，，=-，因此有==hx，，，，，kgx，akx,,,,kkk-12k-12k，1，，xx-axxxxx,,,, 。 ，，，，hx,Z,,x* ,如果是的正则置换多项式，则有在中无零点。而从上，，FFgx，a，，gx，aPPkk 2式可以得到p不能被k整除。结合定理的第一部分得到=1。 ，k，p，，，p-1，k， ,2反过来，设，=1。若有s，使得，在的某二k，p，，，p-1FF，k，,，，gs，a,0PPk au，,s次扩域中任取一元u,0使得，代入式得=0。 ，，，，*huu k222k2，，=，从=1得，因此有于是有，，u-ahu，，k，p-1，，u-a,0u,a k-1k-1k-1pk，所以必有，得出矛盾。 a,ka,0,,j0 故是得正则置换多项式。 ，，Fgx，aPk 定理(二)在多项式的合成运算下是封闭的当且仅当，且此P(a)a,0,,1 Fg(x,a),g(g(x,a),a)时还有关系，因此是由的置换多项式作成的一P(a)pkmkm 个交换群(阿贝尔群)。 ，a,F,k,m,Z 证 设，则 p am g(g(y，,a),a)kmy mamm,g(y，,a) kmy kmakm,y， kmy a ,g(y，,a) kmy 由(1.6)得 mg(x,a),g(g(x,a),a) (1.10) kmkm 4 / 11 如果在合成运算下是封闭的，则有在中，比较的次数g(g(x,a),a)P(a)P(a)xkm 得 g(g(x,a),a),g(x,a) kmkm 再由(1.10)知 mg(g(x,a),a),g(g(x,a),a) kmkm 因不是常数，故又有 g(x,a)m mg(x,a),g(x,a) kk k,2m当k,1时，比较的系数得。 xa,a 2ma,0g(x,a),P(a)a,,1如果，因，则，再从得。 (m,p,1),1a,am 反过来，若，由上述过程验证知在合成运算下是封闭的。? a,0,,1P(a) 上述定理表明，当时，作成一交换群。 a,0,,1P(a) 第三章:置换多项式及RSA密码体制的实现 置换多项式在公开密码中有非常重要的应用。 通讯就是发送或接受信息。在发送信息时，需要先将被发送的信息转换成数字。例如，在英文中有26个字母，设a=0，b=1，、、、,x=23,y=24,z=25。这样，信息便可被转换为一组数字。 既然信息可看成一组数字，因此，对信息加密的问题就可转化为对数字编码的问题。 最简单的编码方法是将26个字母放在圆周上，每一个字母经编码后变成它后面的一个字母。用对应的数字来说，编码就是同余式 ，， C,P，1mod26,0,C,25 (1) PC其中，对应于要发送的字母，对应于编码后的字母。 例如，假设需要发送的信息是 s e c r e t 第一步，将其转换成对应的数字得到 18 4 2 17 4 19 5 / 11 第二步，利用同余式(1)编码得到 19 5 3 18 5 20 第三步，再转换成对应的字母得到 t f d s f u 这就是secret的密文。同样，接收方在收到密文时，可利用P,C,1进行解码。 ，，mod26 所以，可以看到密码编制的基本原理。 SR假设发送信息的一方为，接受信息的一方为,收方有密码钥匙，发DR方有加密钥匙。这两个密码是互逆的。即有 ED,E,E,D,1RRRRR MSM假设要发送一个密码信息，发方将用加密得到，然后将，，EEMRR R此密文发出。收方得到密文，，后，用解密钥匙作用于密文，，上即EMDEMRRR 得 ，，，，，， D,EM,D,EM,MRRRR M这样就获得了原始信息。 然而这种传统的保密系统有非常大的缺陷。 在传统的保密系统中，为使发送的密码信息不被第三者破译，必须严格保密，。这样，由于每两方都有一对保密的钥匙，当系统中用户较多时，密DERR 码的数量就很大，难以分配和管理。 1978年，里维斯特，夏米尔，阿德利曼构造了一种新的密码系统。在这种系统中，由于加密密钥E几乎不可能导出解密密钥D，因此，加密密钥E是RRR公开的。 这种非常重要的系统就是RSA系统。 在RSA系统中的每一方均有一对互逆的密钥，，，其中仅有解密密钥E,DRR 是保密的。加密密钥全部被收集到一个密码簿内，供系统中的任何一方查阅。ER 假设发方S要把信息M发给收方R。S先在密码簿内查出R方的加密密钥，用ER 加密M得到，，，然后将密文，，发给收方R。R收到，，后，用自EMEMEMERRRR ，，，，，，己的解密密钥于密文EM上得D,EM=EM,D=M，即获得了发方SDRRRRRR 6 / 11 的原始信息。 重要的是，因为从几乎不可能导出，固第三方根本无法破译密文，DERR 这就保证了RSA系统的可行性。 事实上，利用置换多项式来构造RSA系统是一个理想的 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 。迪克逊多项式和置换有理函数对构造RSA系统非常有意义。 迪克逊多项式与RSA系统 ，，一 相当于一个数集A的置换，而解密密钥则在RSA系统中，加密密钥EDRR相当于置换的逆置换。当A是剩余类环时，这些置换可取为模m的置换，，EzmR 多项式。 k里维斯特，夏米尔和阿德里曼所取的模m的置换多项式为，，，，，，k,,m,1xm,pq，p，q是不同的大素数。设是一正整数，满足 ，则，，，，kkk,1mod,m11 k1kkk1m,pq当，，时，有， ，，。因为无平方因子，，M,m,1modm*，，M,M,M 当,1时，式仍然成立。 ，，，，M,m* kk1这样可取加密密钥为，解密密钥为。在这个系统中，只有k和m是xx 公开的。要求得解密密钥，必须先求出，，，，，，，而p，q,m,p-1q-1,m-p-q，1k1 m,pq只能从分解m才能得到。由于p，q是保密的大素数，要分解几乎是不可能的。正是分解大素数的困难性保证了RSA系统的可靠性。 kxk,1,2，多项式簇{???}有下面三条性质 kklkllk,,x1:在多项式的合成运算下，作为一个交换群。即 x,x,x,x,x kkkk112:对于每一正整数k，，，，，，存在正整数，使得=k，,m,1kx,xx,x1 是模m的单位置换多项式，也即该置换多项式也可等价的化为单位置换多项式x。 kkkk113:给定一个正整数k，满足，，，，，很难求的使是k，,m,1kx,x,x1 模m的单位置换多项式 7 / 11 k上述的三个性质保证了多项式簇{???}能够构造一个RSA系统。 xk,1,2， k而多项式簇{???}正是当a=0时的迪克逊多项式簇xk,1,2， {???}。于是用迪克逊多项式={???}，，，，gx，a，，gx，aPak,1,2k,1,2kk k(a,,1)来代替多项式簇=来构造新的RSA系统。 ,,x,,，，gx，0k k，，,,2，，k-jk,,jk-2j，，-ax我们在上文中已经证明迪克逊多项式 ，，gx，a,,,,kk-jj,,j,0 ,1当a=时，多项式簇作成一阿贝尔群，且满足，，，，1gx，ak ,=满足条件1。 ，，，，，，gx，agx，agx，aknkn 当a=1时，=的递归关系为g-xg，g,0,g,2,g,x，，，，，2gx，1gk，2k，1k01kk 因此，g可用上述递归关系来计算。 k 如果m=pq，p，q是不相同的素数，则上文证明了是模m的置换多，，gx，ak项式。 22事实上，有限域上某些有理式当且仅当，，k,，，，，p,1q,1,1。进一步， 22，，gx,a是的逆当且仅当kk，，,1mod，，，，p,1q,1，满足条件2。 ，，gx，akk11 ，，由上式可以看出，如果仅知道k和m，要求求出几乎是不可能的。所3k1以条件3成立。 k，，，，,,，，gx,1gx,,1,,xgx,0这样，和多项式簇=一样，迪克逊多项式{}和也kkk 可用来构造RSA系统。 ,,，，gx,a可以证明三类迪克逊多项式簇，，在本质上给出了所有满足a,0,,1k 下列条件的多项式类: ，，1对于任何正整数k，在这个类中存在一次数为k的多项式。 ，，，，，，该类中的任何两个多项式在合成运算下是可换的，也即fg,gf成2 立。 这样，有构造RSA系统的多项式类所具有的性质知，三类迪克逊多项式 8 / 11 在某种意义上给出了所有构造RSA系统的多项式类。 ,,，，gx,a，，a,0,,1k 置换有理函数与RSA系统 ，，二 gx，，rx,设是两个整系数多项式的商，其中g，h在中是互素的多项，，,,Zx，，hx ,Z式。如果对于任何的b 有,并且映射 ，，，，hb，m,1 ZZ ,:,，，，，mm -1，，hb= ，，，，,bgb 是模m的一个置换,则称为模m的置换有理函数. ，，rx ，，gx多项式是模m的置换多项式当且仅当是模m的置换有理函数。如，，gx1果，，易得是模m的置换有理函数当且仅当是模，，，，，，m,mmm，m,1rxrxm12121 和模的置换有理函数。 m2 函数导出的置换可以来构造新的RSA系统。 ，，rxn ,,,,aa,,,,a,0设是一非平方整数，，，这里p，q是不同的奇素数。 ,-1,-1,,,,pq,,,, n，，，，,gx，hxa令，其中，，，，，可表述为 gxhx，，x，annnn n2n,,in-2i,,ax= ，，gx,n,,2ii0,,, n2n,,in-2i-1,,ax，，= hx,n,,2i，1i0,,, ，，gxn定义有理函数，，=，并且证明如果素数，且n为奇数，fxp,2n，，hxn ，，，，n，p，1,1，p不能被n整除，则fx是模p的置换有理函数。 n n,,，，，fxax，a，，f，，f，，xa，，fxakknnn,,，，显然fx满足=，于是，=，n,,，，，，，，，，ffx-afx-afx-ax-anknk,,n ，，，，，，fx，，，，因此有==，这是构造RSA系统所需的一个最基本的性质。 ffxffxkknnkn 9 / 11 可以证明，映射，=满足=当且仅当，，，，，，，，,:Zp,Zp,bfbππkkkkn,k。其中，，为单位映射。 ，，，，，，nmodp，1fx,x,11 可以得到，在上有===当且仅当，，，，，，，，，，，，Zpffxffxfxxknnk1 kn,。 ，，，，1modp，1 综合上述结论可以看出可用来构造新的RSA系统。 ，，fxn 设m=pq，p，q是不同的大素数，p，q是保密的。设n是正的奇整数，p，q ==1。 都不能被n整除，且，，，，n，p，1n，q，1 ,,,,aa,,,,取a是一非平方整数且满足，则是模m的一个置换有理,,-1，，fxn,,,,pq,,,, 函数。 构造加密密钥 ，解密密钥 ，其中k，，，，，，E,fxmod，D,fxmod，mmRnRk nk,1满足 ，这样就够早了一个密码系统。同样在不知道m，，mod,,p，1，q，1 的因子p，q的情况下，从加密密钥几乎不可能求出解密密钥。 3n1965年，诺鲍尔证明，除开a的无平方因子部分是3且外，存在无限多 ,,,,aa,,,,个素数p，q满足=，，其中n是奇数，a是，，，，,,-1p，1，nq，1，n,1,,,,pq,,,, 非平方数。这个结果表明用置换有理函数构造RSA系统是非常有意义的。 第四章: 论文 政研论文下载论文大学下载论文大学下载关于长拳的论文浙大论文封面下载 心得 从杨益宁老师得到题目后，在杨老师的悉心的帮助下，我认真的研究了置换多项式和RSA密码体制的相关知识，并且有非常大的收获。 1:学到了的置换多项式的性质，密码体制的发展，RSA体制的建立等相关知识。 2:认识到了从发现问题到用数学中丰富的性质解决现实问题的一般规律。 3:分解大素数的困难性保证了RSA系统的可靠性。所以我觉得，快速有效地大素数分解方法将是突破RSA系统的关键。而这又将进一步的推动RSA系统的发展。 10 / 11 参考文献: 置换多项式及其应用 孙琦，万大庆 抽象代数 丘维声 11 / 11