费马小定理与RSA的实现

方案：

1.选取两个不同的素数p，q，令m=pq，本文中我们设p=5741，q=7687，那么m=pq=5741×7687=44131067

2.再选取一个与φ（m）=（p-1）（q-1）互素的正整数E，直接计算可得φ（m）=（p-1）（q-1）=5740×7696=44117640，令E=1l ，即保证它与φ（m）互素。（人們一般把E称为公钥）

3.由参数m，E给出的RSA加密函数为x^E（mod m），我们在这里取最小剩余，简单的说，这个加密函数是对自变量X在模m的意义下取E次幂。

根据刚才的叙述，我们需要传译的密码为：

282136 3735 29212136 1736 24312921

加密过程为：

282136¹¹=6656289（mod 44131067）

3733¹¹=18838101（mod 44131067）

1736¹¹=18930561（mod 44131067）

24312921¹¹=25581695（mod 44131067）

根据计算，编译成的密文为：

6656289 18838101 42759181 1893056125581695

根据计算解出的明文为;

282136 3735 29212136 1736 24312921

再次核对密码本我们知道，需要传递的信息就是Let us meet at home。

参考文献：

[1]高斯（著）算术研究[M].潘承彪，张明尧（译）.哈尔滨工业大学出版社，2001.

[2]韦伊（著）.数论：从汉穆拉比到勒让德的历史导引[M].胥鸣伟（译）高等教育出版社出版，2010.

[3]吴军（著）.数学之美[M].人民邮电出版社出版，2014.

推荐访问:定理 费马小 RSA