RSA算法和实现及实例

1、RSA算法和实现及实例v基础RSA算法非常简单，概述如下：找两素数P和q取 n = p*q取t=(p-l)*(q-l)取任何一个数e,要求满足et并且e与t互素(就是最大公因数为1)取 d*e%t=l这样最终得到三个数：11 d e设消息为数M (M perl -e foreach $i (1.9999) print($i),last if$产63%2668= = 1 “847即d=847最终我们获得关键的n=2773d=847e=63取消息M二244我们看看加密：c=M*dVbn = 244*847perl -Mbigint -e print 244*847perl -Mbigint -e

2、print 465*63Vb2773,f244即用e对(:解密后获得m=244 z该值和原始信息M相等。 字符串加密把上面的过程集成一下我们就能实现一个对字符串加密解密的示例了。每次取字符串中的一个字符的ascii值作为M进行计算，其输出为加密后16进制 的数的字符串形式，按3字节表示，如01F代码如下：#!/usr/bin/perl -w#RSA计算过程学习程序编写的测试程序#watercloud 2003-8-12#use strict;use Math:BigInt;my 2773,e二63川二847); #p=47,q二59my $N = new Math:BigInt($RSA_CO

3、REn);my $E = new Math:BigInt($RSA_COREe);my $D=new Math:BigInt($RSA_COREd);print MN = $N D = $D E = $Enf,;sub RSA_ENCRYPTmy $r_mess = shiftmy ($c,$/$M,$Cz$cmess);for($i=0;$i new($c);$C=$M-copy(); $C-bmodpow($D,$N);$c=sprintf %03X：$C;$cmess. = $c;return $cmess;sub RSA_DECRYPTmy $r_mess = shiftmy ($c/

4、$i,$M,$C,$dmess);for($i=0;$i V length($r_mess);$i + = 3)$c=substr($r_messz$i,3);$c=hex($c);$M = Math:BigInt-new($c);$C=$M-copy(); $C-bmodpow($E,$N);$c=chr($C);$dmess. = $c;return $dmess;my $mess=nRSA娃哈哈哈；$mess=$ARGVO if ARGV = 1;print 始串:”,$mess,”n“；my $r_cmess = RSA_ENCRYPT($mess);print 加密串：,$r_cme

5、ss/rr；my $r_dmess = RSA_DECRYPT($r_cmess);print 解密串：爲# EOF测试一下：C:Tempperl rsa-test.plN=2773 D=847 E=63原始串：RSA娃哈哈哈加密串：5CB6CD6BC58A7709470AA74A0AA74A0AA74A6C70A46C70A46C70A4解密串：RSA娃哈哈哈C:Tempperl rsa-test.pl 安全焦点(xfocus)N=2773 D=847 E二63原始串：安全焦点（xfocus）加密串：3393EC12F0A466E0AA9510D025D7BA0712DC3379F47D51

6、C325D67B解密串：安全焦点（xfocus）V四提奇前面已经提到，sa的安全来源于n足够大，我们测试中使用的n是非常小的，根本不能保障 安全性，我们可以通过RSAKit、RSATool之类的工具获得足够大的N及D E。通过工具，我们获得1024位的N及D E来测试一下：n=0x328C74784DF31119C526D18098EBEBB943B0032B599CEE13CC2BC E7B5FCD15F90B66EC3A85F5005DBDCDED9BDFCB3C4C265AF164AD55884D8278F791C7A6BFDAD55EDBC4 F017F9CCF1538D4C20134

7、33B383B 47D80EC74B51276CA05B5D6346B9EE5AD2D7BE7ABFB36E37108DD604 38941D2ED173CCA50E114705D7E2BC511951d二0x10001 e=0xE760A3804ACDElE8E3D7DC0197F9CEF6282EF552E8CEBBB7434B0 1CB19A9D87A3106DD28C523C29954C5D86B36E943080E4919CA8CE08718C3B0930867A98F635EB9EA9200 B25906D91B80A47B77324E66AFF2C4D70D8B1C69C50A9

8、D8B4B7A3C9EE05FFF3A16AFC023731D80634763D A1DCABE9861A4789BD782A592D2B1965设原始信息M=0xllllllllllll22222222222233333333333完成这么大数字的计算依赖于大数运算库，用perl来运算非常简单：A）用d对M进行加密如下：c=M*d（Vbn :C:Tempperl -Mbigint -e ,f $x=Math:BigInt-bmodpow（0xllllllllllll22222222222233 333333333, 0x10001, 0x328C74784DF31119C526D18098E

9、BEBB943B0032B599CEE13CC2BCE7 B5FCD15F90B66EC3A85F5005DBDCDED9BDFCB3C4C265AF164AD55884D82 78F791C7A6BFDAD55EDBC4F0 17F9CCF1538D4C2013433B383B47D80EC74B51276CA05B5D6346B9EE5 AD2D7BE7ABFB36E37108DD60438941D2ED173CCA50E114705D7E2BC511951);print $x-as_hex” 0xl7b287be418c69ecd7c39227ab681ac422fcc84bb35d8a

10、632543b304de 288a8d4434b73d2576bd 45692b007f3a2f7c5f5aald99ef3866af26a8e876712edld4cc4b293e26bc 0aldc67e247715caa6b 3028f9461a3bl533ec0cb476441465fl0d8ad47452al2db0601c5e8beda6 86dd96d2acd59ea89b91fl834580c3f6d90898即用d对M加密后信息为：c=0xl7b287be418c69ecd7c39227ab681ac422fcc84bb35d8a632543b304 de288a8d4434

11、b73d2576bd45692b007f3a2f7c5f5aald99ef3866af26a8e876712edld4cc4b293e26bc 0aldc67e247715caa6b3028f9461a3bl533ec0cb476441465fl0d8ad47452al2db0601c5e8beda6 86dd96d2acd59ea89b91fl834580c3f6d90898B)用e对c进行解密如下：m二；C:Tempperl -Mbigint -e $x=Math:BigInt-bmodpow(0xl7b287be418c69ecd7c39227ab 681ac422fcc84bb35d8

12、a632543b304de288a8d4434b73d2576bd45692b0 07f3a2f7c5f5aald99ef3 866af26a8e876712edld4cc4b293e26bc0aldc67e247715caa6b3028f946 la3bl533ec0cb4764414 65fl0d8ad47452al2db0601c5e8beda686dd96d2acd59ea89b91fl834580 c3f6d90898, 0xE760A 3804ACDE1E8E3D7DC0197F9CEF6282EF552E8CEBBB7434B01CB19A9D8 7A3106DD28C523C2

13、9954C5D 86B36E943080E4919CA8CE08718C3B0930867A98F635EB9EA9200B2590 6D91B80A47B77324E66AFF 2C4D70D8B1C69C50A9D8B4B7A3C9EE05FFF3A16AFC023731D80634763 DA1DCABE9861A4789BD782A592D2B1965, 0x328C74784DF31119C526D18098EBEBB943B0032B599 CEE13CC2BCE7B5FCD15F90 B66EC3A85F5005DBDCDED9BDFCB3C4C265AF164AD55884D8278F791C 7A6BFDAD55EDBC4F017F9CCF 1538D4C2013433B383B47D80EC74B51276CA05B5D6346B9EE5AD2D7BE 7ABFB36E37108DD60438941D2ED173CCA50E114705D7E2BC511951);print $x-as_hexM 0x11111111111122222222222233333333333(我的P4 1.6G的机器上计算了约5秒钟)得至U用 e 解密后