📄 778.html
字号:
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html>
<head>
<title>RSA算法基础->实践 </title>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<meta name="Keywords" content="安全焦点, xfocus, 陷阱网络, honeynet, honeypot, 调查取证, forensic, 入侵检测, intrusion detection, 无线安全, wireless security, 安全论坛, security forums, 安全工具, security tools, 攻击程序, exploits, 安全公告, security advisories, 安全漏洞, security vulnerabilities, 安全教程, security tutorials, 安全培训, security training, 安全帮助, security help, 安全标准, security standards, 安全代码, security code, 安全资源, security resources, 安全编程, security programming, 加密, cryptography,RSA 算法 加密 perl 大数运算" />
<link rel="stylesheet" href="../../css/plone.css" type="text/css">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div class="top">
<div class="searchBox">
<form name="searchform" action="http://www.google.com/search" method="get">
<input type="hidden" name="domains" value="www.xfocus.net">
<input type="hidden" name="sitesearch" value="www.xfocus.net">
<input type="text" name="q" size="20">
<input type="submit" name="btnG" value="Google Search">
</form>
</div>
<img src="../../images/logo.gif" border="0" width="180" height="80" alt="xfocus logo">
<img src="../../images/title.gif" border="0" width="230" height="20" alt="xfocus title">
</div>
<div class="tabs">
<a href="../../index.html" class="plain">首页</a>
<a href="../../releases/index.html" class="plain">焦点原创</a>
<a href="../../articles/index.html" class="selected">安全文摘</a>
<a href="../../tools/index.html" class="plain">安全工具</a>
<a href="../../vuls/index.html" class="plain">安全漏洞</a>
<a href="../../projects/index.html" class="plain">焦点项目</a>
<a href="https://www.xfocus.net/bbs/index.php?lang=cn" class="plain">焦点论坛</a>
<a href="../../about/index.html" class="plain">关于我们</a>
</div>
<div class="personalBar">
<a href='https://www.xfocus.net/php/add_article.php'>添加文章</a> <a href='http://www.xfocus.org/'>English Version</a>
</div>
<table class="columns">
<tr>
<td class="left">
<div class="box">
<h5> 文章分类 </h5>
<div class="body">
<div class="content odd">
<div style="white-space: nowrap;">
<img src='../../images/folder_icon.gif' border='0'> <a href='../../articles/4.html'><b>专题文章 <<</b></a><br><img src='../../images/folder_icon.gif' border='0'> <a href='../../articles/2.html'>漏洞分析</a><br><img src='../../images/folder_icon.gif' border='0'> <a href='../../articles/3.html'>安全配置</a><br><img src='../../images/folder_icon.gif' border='0'> <a href='../../articles/1.html'>黑客教学</a><br><img src='../../images/folder_icon.gif' border='0'> <a href='../../articles/5.html'>编程技术</a><br><img src='../../images/folder_icon.gif' border='0'> <a href='../../articles/7.html'>工具介绍</a><br><img src='../../images/folder_icon.gif' border='0'> <a href='../../articles/6.html'>火墙技术</a><br><img src='../../images/folder_icon.gif' border='0'> <a href='../../articles/8.html'>入侵检测</a><br><img src='../../images/folder_icon.gif' border='0'> <a href='../../articles/9.html'>破解专题</a><br><img src='../../images/folder_icon.gif' border='0'> <a href='../../articles/11.html'>焦点公告</a><br><img src='../../images/folder_icon.gif' border='0'> <a href='../../articles/12.html'>焦点峰会</a><br>
</div>
</div>
</div>
</div>
<div class="box">
<h5> 文章推荐 </h5>
<div class="body">
<div class="content odd">
<img src='../../images/document_icon.gif' border='0'> <a href='../../articles/200408/733.html'>补丁管理最佳安全实践之资产评估</a><br><img src='../../images/document_icon.gif' border='0'> <a href='../../articles/200404/689.html'>国内网络安全风险评估市场与技术操作</a><br><img src='../../images/document_icon.gif' border='0'> <a href='../../articles/200410/743.html'>协作的信息系统风险评估</a><br>
</div>
</div>
</div>
</td>
<td class="main">
<h1>RSA算法基础->实践</h1><br>创建时间：2005-03-02<br>文章属性：原创<br>文章提交：<a href='https://www.xfocus.net/bbs/index.php?lang=cn&act=Profile&do=03&MID=991'>watercloud</a> (watercloud_at_xfocus.org)<br><br>RSA算法基础->实践<br />
<br />
<br />
讲讲自己学习RSA中的实践过程，已经对RSA熟悉的看家就不用在此浪费时间了。<br />
<br />
<一>基础<br />
<br />
RSA算法非常简单，概述如下：<br />
找两素数p和q<br />
取n=p*q<br />
取t=(p-1)*(q-1)<br />
取任何一个数e,要求满足e<t并且e与t互素（就是最大公因数为1）<br />
取d*e%t==1<br />
<br />
这样最终得到三个数： n d e<br />
<br />
设消息为数M (M <n)<br />
设c=(M**d)%n就得到了加密后的消息c <br />
设m=(c**e)%n则 m == M，从而完成对c的解密。<br />
注：**表示次方,上面两式中的d和e可以互换。<br />
<br />
在对称加密中：<br />
n d两个数构成公钥，可以告诉别人；<br />
n e两个数构成私钥，e自己保留，不让任何人知道。<br />
给别人发送的信息使用e加密，只要别人能用d解开就证明信息是由你发送的，构成了签名机制。<br />
别人给你发送信息时使用d加密，这样只有拥有e的你能够对其解密。<br />
<br />
rsa的安全性在于对于一个大数n，没有有效的方法能够将其分解<br />
从而在已知n d的情况下无法获得e；同样在已知n e的情况下无法<br />
求得d。<br />
<br />
<br />
<br />
<二>实践<br />
<br />
接下来我们来一个实践，看看实际的操作：<br />
找两个素数：<br />
p=47<br />
q=59<br />
这样<br />
n=p*q=2773<br />
t=(p-1)*(q-1)=2668<br />
取e=63，满足e<t并且e和t互素<br />
用perl简单穷举可以获得满主 e*d%t ==1的数d：<br />
C:\Temp>perl -e "foreach $i (1..9999){ print($i),last if $i*63%2668==1 }"<br />
847<br />
即d＝847<br />
<br />
最终我们获得关键的<br />
n=2773<br />
d=847<br />
e=63<br />
<br />
取消息M=244我们看看<br />
<br />
加密：<br />
<br />
c=M**d%n = 244**847%2773<br />
用perl的大数计算来算一下：<br />
C:\Temp>perl -Mbigint -e "print 244**847%2773"<br />
465<br />
即用d对M加密后获得加密信息c＝465<br />
<br />
解密：<br />
<br />
我们可以用e来对加密后的c进行解密，还原M：<br />
m=c**e%n=465**63%2773 ：<br />
C:\Temp>perl -Mbigint -e "print 465**63%2773"<br />
244<br />
即用e对c解密后获得m=244 , 该值和原始信息M相等。<br />
<br />
<br />
<三>字符串加密<br />
<br />
把上面的过程集成一下我们就能实现一个对字符串加密解密的示例了。<br />
每次取字符串中的一个字符的ascii值作为M进行计算，其输出为加密后16进制<br />
的数的字符串形式，按3字节表示，如01F<br />
<br />
代码如下：<br />
<br />
#!/usr/bin/perl -w<br />
#RSA 计算过程学习程序编写的测试程序<br />
#watercloud 2003-8-12<br />
#<br />
use strict;<br />
use Math::BigInt;<br />
<br />
my %RSA_CORE = (n=>2773,e=>63,d=>847); #p=47,q=59<br />
<br />
my $N=new Math::BigInt($RSA_CORE{n});<br />
my $E=new Math::BigInt($RSA_CORE{e});<br />
my $D=new Math::BigInt($RSA_CORE{d});<br />
<br />
print "N=$N D=$D E=$E\n";<br />
<br />
sub RSA_ENCRYPT <br />
{<br />
my $r_mess = shift @_;<br />
my ($c,$i,$M,$C,$cmess);<br />
<br />
for($i=0;$i < length($$r_mess);$i++)<br />
{<br />
$c=ord(substr($$r_mess,$i,1));<br />
$M=Math::BigInt->new($c);<br />
$C=$M->copy(); $C->bmodpow($D,$N);<br />
$c=sprintf "%03X",$C;<br />
$cmess.=$c;<br />
}<br />
return \$cmess;<br />
}<br />
<br />
sub RSA_DECRYPT <br />
{<br />
my $r_mess = shift @_;<br />
my ($c,$i,$M,$C,$dmess);<br />
<br />
for($i=0;$i < length($$r_mess);$i+=3)<br />
{<br />
$c=substr($$r_mess,$i,3);<br />
$c=hex($c);<br />
$M=Math::BigInt->new($c);<br />
$C=$M->copy(); $C->bmodpow($E,$N);<br />
$c=chr($C);<br />
$dmess.=$c;<br />
}<br />
return \$dmess;<br />
}<br />
<br />
my $mess="RSA 娃哈哈哈～～～";<br />
$mess=$ARGV[0] if @ARGV >= 1;<br />
print "原始串：",$mess,"\n";<br />
<br />
my $r_cmess = RSA_ENCRYPT(\$mess);<br />
print "加密串：",$$r_cmess,"\n";<br />
<br />
my $r_dmess = RSA_DECRYPT($r_cmess);<br />
print "解密串：",$$r_dmess,"\n";<br />
<br />
#EOF<br />
<br />
测试一下：<br />
C:\Temp>perl rsa-test.pl<br />
N=2773 D=847 E=63<br />
原始串：RSA 娃哈哈哈～～～<br />
加密串：5CB6CD6BC58A7709470AA74A0AA74A0AA74A6C70A46C70A46C70A4<br />
解密串：RSA 娃哈哈哈～～～<br />
<br />
<br />
C:\Temp>perl rsa-test.pl 安全焦点（xfocus）<br />
N=2773 D=847 E=63<br />
原始串：安全焦点（xfocus）<br />
加密串：3393EC12F0A466E0AA9510D025D7BA0712DC3379F47D51C325D67B<br />
解密串：安全焦点（xfocus）<br />
<br />
<br />
<br />
<四>提高<br />
<br />
前面已经提到，rsa的安全来源于n足够大，我们测试中使用的n是非常小的，根本不能保障安全性，<br />
我们可以通过RSAKit、RSATool之类的工具获得足够大的N 及D E。<br />
通过工具，我们获得1024位的N及D E来测试一下：<br />
<br />
n=0x328C74784DF31119C526D18098EBEBB943B0032B599CEE13CC2BCE7B5FCD15F90B66EC3A85F5005D<br />
BDCDED9BDFCB3C4C265AF164AD55884D8278F791C7A6BFDAD55EDBC4F017F9CCF1538D4C2013433B383B<br />
47D80EC74B51276CA05B5D6346B9EE5AD2D7BE7ABFB36E37108DD60438941D2ED173CCA50E114705D7E2<br />
BC511951<br />
<br />
d=0x10001<br />
<br />
e=0xE760A3804ACDE1E8E3D7DC0197F9CEF6282EF552E8CEBBB7434B01CB19A9D87A3106DD28C523C2995<br />
4C5D86B36E943080E4919CA8CE08718C3B0930867A98F635EB9EA9200B25906D91B80A47B77324E66AFF2<br />
C4D70D8B1C69C50A9D8B4B7A3C9EE05FFF3A16AFC023731D80634763DA1DCABE9861A4789BD782A592D2B<br />
1965<br />
<br />
<br />
设原始信息<br />
M=0x11111111111122222222222233333333333<br />
<br />
完成这么大数字的计算依赖于大数运算库，用perl来运算非常简单：<br />
<br />
A) 用d对M进行加密如下：<br />
c=M**d%n :<br />
C:\Temp>perl -Mbigint -e " $x=Math::BigInt->bmodpow(0x11111111111122222222222233<br />
333333333, 0x10001, 0x328C74784DF31119C526D18098EBEBB943B0032B599CEE13CC2BCE7B5F<br />
CD15F90B66EC3A85F5005DBDCDED9BDFCB3C4C265AF164AD55884D8278F791C7A6BFDAD55EDBC4F0<br />
17F9CCF1538D4C2013433B383B47D80EC74B51276CA05B5D6346B9EE5AD2D7BE7ABFB36E37108DD6<br />
0438941D2ED173CCA50E114705D7E2BC511951);print $x->as_hex"<br />
0x17b287be418c69ecd7c39227ab681ac422fcc84bb35d8a632543b304de288a8d4434b73d2576bd<br />
45692b007f3a2f7c5f5aa1d99ef3866af26a8e876712ed1d4cc4b293e26bc0a1dc67e247715caa6b<br />
3028f9461a3b1533ec0cb476441465f10d8ad47452a12db0601c5e8beda686dd96d2acd59ea89b91<br />
f1834580c3f6d90898<br />
<br />
即用d对M加密后信息为：<br />
c=0x17b287be418c69ecd7c39227ab681ac422fcc84bb35d8a632543b304de288a8d4434b73d2576bd<br />
45692b007f3a2f7c5f5aa1d99ef3866af26a8e876712ed1d4cc4b293e26bc0a1dc67e247715caa6b<br />
3028f9461a3b1533ec0cb476441465f10d8ad47452a12db0601c5e8beda686dd96d2acd59ea89b91<br />
f1834580c3f6d90898<br />
<br />
<br />
<br />
B) 用e对c进行解密如下：<br />
<br />
m=c**e%n ：<br />
C:\Temp>perl -Mbigint -e " $x=Math::BigInt->bmodpow(0x17b287be418c69ecd7c39227ab<br />
681ac422fcc84bb35d8a632543b304de288a8d4434b73d2576bd45692b007f3a2f7c5f5aa1d99ef3<br />
866af26a8e876712ed1d4cc4b293e26bc0a1dc67e247715caa6b3028f9461a3b1533ec0cb4764414<br />
65f10d8ad47452a12db0601c5e8beda686dd96d2acd59ea89b91f1834580c3f6d90898, 0xE760A<br />
3804ACDE1E8E3D7DC0197F9CEF6282EF552E8CEBBB7434B01CB19A9D87A3106DD28C523C29954C5D<br />
86B36E943080E4919CA8CE08718C3B0930867A98F635EB9EA9200B25906D91B80A47B77324E66AFF<br />
2C4D70D8B1C69C50A9D8B4B7A3C9EE05FFF3A16AFC023731D80634763DA1DCABE9861A4789BD782A<br />
592D2B1965, 0x328C74784DF31119C526D18098EBEBB943B0032B599CEE13CC2BCE7B5FCD15F90<br />
B66EC3A85F5005DBDCDED9BDFCB3C4C265AF164AD55884D8278F791C7A6BFDAD55EDBC4F017F9CCF<br />
1538D4C2013433B383B47D80EC74B51276CA05B5D6346B9EE5AD2D7BE7ABFB36E37108DD60438941<br />
D2ED173CCA50E114705D7E2BC511951);print $x->as_hex"<br />
0x11111111111122222222222233333333333<br />
(我的P4 1.6G的机器上计算了约5秒钟）<br />
<br />
得到用e解密后的m=0x11111111111122222222222233333333333 == M<br />
<br />
<br />
C) RSA通常的实现<br />
RSA简洁幽雅，但计算速度比较慢，通常加密中并不是直接使用RSA 来对所有的信息进行加密，<br />
最常见的情况是随机产生一个对称加密的密钥，然后使用对称加密算法对信息加密，之后用<br />
RSA对刚才的加密密钥进行加密。<br />
<br />
<br />
最后需要说明的是，当前小于1024位的N已经被证明是不安全的<br />
自己使用中不要使用小于1024位的RSA，最好使用2048位的。<br />
<br />
watercloud [at] xfocus.org<br />
2005-2-21
</td>
</tr>
</table>
<div class="footer">
Copyright © 1998-2003 XFOCUS Team. All Rights Reserved
</div>
</body>
</html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -