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

《置换多项式及rsa密码体制的实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、置换多项式及RSA密码体制的实现摘要：传统的密码编制体制有着较多的缺陷，得益于置换多项式的诸多优点提出了RSA密码体制，很好的保证了密码体制的安全性。其中迪克逊多项式和有理置换函数在RSA系统中有重大的意义。关键字：置换多项式RSA系统迪克逊多项式置换多项式正文：第一章：置换多项式的简单性质数学王子高斯在1801年的著作《算术探讨》首先提出了完全剩余系的问题。设m是一个正整数，从模m的每一个剩余类中选取一个代表元组成的集，称为模m的一个完全剩余系。例如，组成的模m的一个完全剩余系，也组成模m的一个完全剩余系。完全剩余系的最简单的构造是，这里a是与m互素的一个整数

2、。所以，可以用简单的线性多项式表示。即当x取值0,1，...，m-1时，刚好是所构造的完全剩余系。于是，有了置换多项式的定义：定义：设是一整系数多项式，如果当x为模m的一个完全剩余系时，也为模m的一个完全剩余系，则称是模m的置换多项式。也即，导出的一个置换。不加证明的得到置换多项式的几条简单的性质：性质：从知，是模m的置换多项式相当于是模m的一个完全剩余系。性质：设，，是模m的两个置换多项式，，则不是模m的置换多项式。需要注意的是，当m为奇数时，性质不成立。例如，取，，，则是模5的置换多项式，而11/11也是模5的置换多项式。性质:设，是模m的两个置换多项式，则

3、乘积不是模m的置换多项式。性质：设是m的标准分解式，则是模m的置换多项式当且仅当是模的置换多项式。第二章：迪克逊多项式有了置换多项式的这些基本的性质，我们着重的学习一类非常重要的置换多项式，即迪克逊多项式。定义迪克逊多项式如下：,其中，表示实数b的整数部分。易得等式=，特别的，当a=0时有=。下面证明两个非常重要的定理。定理：设。则由迪克逊多项式是的置换多项式当且仅当，=1；是得正则置换多项式当且仅当=1。证明：首先证明定理的第一部分。设=1。若有b，c使得=，只需证明b=c在的某一个二次扩域中取一非零元使；同样又在的另一个二次扩域中取一非零元使。又因为的所有二

4、次扩域都是同构的，所以，和都可以在的同一个二次扩域中选取。11/11则有，===。因此，。由此有=或=。无论哪种情况都有。即是的置换多项式。反证法。设=d，若，则，p不能被2整除，则只含x的偶数次方幂，因此对所有有=。而，固不是的置换多项式。下设2不能被d整除，则有d的奇数因子r，，或。分两种情况：当时，方程在中有r个解，因此存在b，，，a。于是，则可以得到==，又，a。所以，这样就不是的置换多项式。当时，设是的二次扩域中的一元，使得。因为，在中有r个解，于是存在，=1，，。这样就有，且=。因为，中的所有零点组成，故有，=。因为，，，所以则有，，因此不是的置换多

5、项式。下面证明定理的第二部分。我们有=，对x求导，可得=-11/11，因此有==，。如果是的正则置换多项式，则有在中无零点。而从上式可以得到p不能被k整除。结合定理的第一部分得到=1。反过来，设=1。若有s，使得，在的某二次扩域中任取一元使得，代入式得=0。于是有=，从=1得，因此有，所以必有，得出矛盾。故是得正则置换多项式。定理（二）在多项式的合成运算下是封闭的当且仅当，且此时还有关系，因此是由的置换多项式作成的一个交换群（阿贝尔群）。证设，则由（1.6）得（1.10）如果在合成运算下是封闭的，则有在中，比较的次数得11/11再由（1.10）知因不是常数，故又

6、有当时，比较的系数得。如果，因，则，再从得。反过来，若，由上述过程验证知在合成运算下是封闭的。□上述定理表明，当时，作成一交换群。第三章：置换多项式及RSA密码体制的实现置换多项式在公开密码中有非常重要的应用。通讯就是发送或接受信息。在发送信息时，需要先将被发送的信息转换成数字。例如，在英文中有26个字母，设a=0，b=1，、、、,x=23,y=24,z=25。这样，信息便可被转换为一组数字。既然信息可看成一组数字，因此，对信息加密的问题就可转化为对数字编码的问题。最简单的编码方法是将26个字母放在圆周上，每一个字母经编码后变成它后面的一个字母。用对应的数字来说

7、，编码就是同余式(1)其中，对应于要发送的字母，对应于编码后的字母。例如，假设需要发送的信息是secret第一步，将其转换成对应的数字得到184217419第二步，利用同余式(1)编码得到195318520第三步，再转换成对应的字母得到tfdsfu11/11这就是secret的密文。同样，接收方在收到密文时，可利用进行解码。所以，可以看到密码编制的基本原理。假设发送信息的一方为，接受信息的一方为,收方有密码钥匙，发方有加密钥匙。这两个密码是互逆的。即有假设要发送一个密码信息，发方将用加密得到，然后将此密文发出。收方得到密文后，用解密钥匙作用于密文上即得这样就获得

8、了原始信息。然而这种传统