csdn_+-
来自「密码学我所知」· 代码 · 共 357 行 · 第 1/2 页
TXT
357 行
<P> </P>
<P>先是本站留言本里的一点关于RSA的介绍。</P>
<P><A
href="http://two.guestbook.de/gb.cgi?gid=584097&prot=uhsaif">http://two.guestbook.de/gb.cgi?gid=584097&prot=uhsaif</A></P>
<TABLE>
<TBODY>
<TR>
<TD align=right vAlign=top><B><FONT
size=+2>61</FONT></B> </TD>
<TD colSpan=2>Date: 2002-04-29 06:41:04
<EM><B>chutium</B></EM><BR>RSA是用与两个极大质数(a,b)的积互素的一个整数(ency)对整个明文进行数学变换后得到加密的密文{n=ab,f(n)=(a-1)(b-1),encryp*decryp=1
mod
f(n)}。为什么不一定可以显示？这个的资料在网上应该很好找，不过很少有说及它数学变化实质的，你最好到国外大学的BBS看看。大学教材里这些东西应该都有更详尽的介绍，不过年少时有谁真的塌实学了呢……</TD></TR></TBODY></TABLE>
<TABLE>
<TBODY>
<TR>
<TD align=right vAlign=top><B><FONT
size=+2>67</FONT></B> </TD>
<TD colSpan=2>Date: 2002-04-30 06:52:38
<EM><B>liyx</B><BR></EM>RSA的公钥和私钥都是两个大素数即大于100个十进制位的函数。<BR>据猜测，从一个密钥和密文推断出明文的难度等同于分解两个大素数的积。<BR>产生密钥时选择两个大素数，p和q。计算：n
= p*q<BR>然后随机选择加密密钥e，要求 e 和(p-1)*(q-1) 互质。最后，利用 Euclid
算法计算解密密钥d, 满足 e*d =
1(mod(p-1)*(q-1))其中n和d也要互质。数e和n是公钥，d是私钥(即你说的decrypt)。两个素数p和q不再需要，应该丢弃。<BR>加密信息
m（二进制表示）时，首先把m分成等长数据块 m1 ,m2,..., mi ，块长s，其中 2^s<=n,s
尽可能的大。<BR>对应的密文是：ci = mi^e(mod n)(a)<BR>解密时作如下计算：mi = ci^d(mod
n)(b)<BR>RSA数字签名是用(a)式签名，(b)式验证。具体操作时考虑到安全性和m信息量较大等因素，一般是先作HASH运算。</TD></TR></TBODY></TABLE>
<P> </P>
<P>如果您是加密算法的爱好者，看上面两贴就可以了，下面是我通过上两贴和一些资料(见文末)整理的比较详细的加密过程，有比较好的数学基础的朋友如果有兴趣请继续看。</P>
<P>建议阅读者基本了解“因子、质数、同余式与费马、欧拉定理、Wilson定理、Lucas定理”等数论知识。</P>
<P> </P>
<P>这个加密方法是上列三位科学家在1978所发表的，其步骤如下
<DL>
<DD>1.收报者取两个相异的大质数<I>p</I>、<I>q</I>及另一与(<I>p</I>-1)(<I>q</I>-1)互质的数<I>a</I>，且<I>a</I><<I>w</I>令<BR>
<DIV align=center><I>w</I>=(<I>p</I>-1)(<I>q</I>-1), </DIV>
<DIV align=center><I>m</I>=<I>pq</I>
</DIV>及<I>p</I>、<I>q</I>的较小者的位数（十进位）为<I>k</I>。
<DT>
<DD>2.（公开）告诉发报者<I>k</I>，<I>m</I>与<I>a</I>。
<DT>
<DD>3.发报者将他的信号分成许多段，每段含<I>k</I>-1位数（十进位）（若<I>k</I>=3（即<I>p</I>、<I>q</I>均为不小于二位的数），则信号<BR>
<DIV align=center>331414320001 </DIV>则应分成
<DIV align=center>33,14,14,32,00,01
</DIV>一个一个的考虑发出），设发报者的信号的一为<I>x</I>（<I>k</I>-1位数，即上例中的33，或14，或32，…），则他将它作成
<DIV align=center><IMG border=0 height=28
src="CSDN_文档中心_分析 RSA 算法演算过程及VB和C++的实现方法.files/rsa1.gif"
width=121> </DIV>发出。
<DT>
<DD>4.收报者收到<I>c</I>之后，即可把原有的<I>x</I>求出来，因<I>a</I>与<I>w</I>互质，由定理：若两正整数
p,q 互质，则可以找到二整数(不一定正) a,b，使得 ap+bq=1
知，我们可找到二整数<I>d</I>、<I>e</I>；<I>d</I>>0使得<BR>
<DIV align=center><I>ad</I>+<I>we</I>=1 </DIV>令
<DIV align=center><IMG border=0 height=28
src="CSDN_文档中心_分析 RSA 算法演算过程及VB和C++的实现方法.files/rsa2.gif"
width=121> </DIV>则此<I>y</I>即发报者的<I>x</I>。我们先证明
<I>y</I>=<I>x</I>。<BR>
<DIV align=center><IMG border=0 height=28
src="CSDN_文档中心_分析 RSA 算法演算过程及VB和C++的实现方法.files/rsa3.gif"
width=400> </DIV><BR clear=all>但因 <I>w</I>、<I>a</I>、<I>d</I> 均为大于
1 的整数，故 <I>e</I> 必为一负数，即 -<I>e</I> 为一正数，又因<I>x</I>小于质数
<I>p</I>、<I>q</I>，故 <I>x</I> 同 <I>m</I> 互质，<BR>
<DIV align=center><IMG border=0 height=28
src="CSDN_文档中心_分析 RSA 算法演算过程及VB和C++的实现方法.files/rsa4.gif"
width=221> </DIV><BR
clear=all>但因<I>y</I>与<I>x</I>均取小于<I>m</I>的数，故<I>y</I>=<I>x</I>。故本程序的正确性得证。
</DD></DL>
<P> </P>
<P>我其它方面比较弱，所以对破解年限计算很不在行，这里是我手头《数学传播》上的资料，有增补。</P>
<P>这种密码关键在于<I>p</I>、<I>q</I>两个大质数的破解，据此文介绍，分解<I>m</I>成为<I>p</I>、<I>q</I>为一件极费时的工作，若分解不开<I>m</I>，则找不到w与d，因此就无法从c解得x，在不久以前，要分解一个数的因子仍停留在近乎硬试的阶段，即要从2，3，5，7，…，一直试到n^(1/2)附近才停止。若<I>n</I>是50位数而<I>p</I>、<I>q</I>均近25位数，则分解<I>m</I>要除约10<SUP>25</SUP>次，若以电子计算机以每秒10<SUP>6</SUP>次的高速运算，这仍是一个10<SUP>11</SUP>年的工作，目前由于大家对这方面的重视，分解一个50位数的时间已可缩短至10<SUP>10</SUP>次运算。下面的表中列出了目前(1980年)，分解一个大数大概所需的时间。
<P>
<DIV align=center>
<TABLE border=1 cellPadding=5 cellSpacing=0>
<TBODY>
<TR>
<TD align=middle><I>m</I>的位数</TD>
<TD align=middle>分解<I>m</I>的最少运算次数</TD>
<TD align=middle>最快（1980年）电脑所费的时间</TD></TR>
<TR>
<TD align=middle>50</TD>
<TD align=middle>1.4 x 10<SUP>10</SUP></TD>
<TD align=middle>3.9小时</TD></TR>
<TR>
<TD align=middle>70</TD>
<TD align=middle>9.0 x 10<SUP>12</SUP></TD>
<TD align=middle>104天</TD></TR>
<TR>
<TD align=middle>80</TD>
<TD align=middle>1.3 x 10<SUP>13</SUP></TD>
<TD align=middle>150天</TD></TR>
<TR>
<TD align=middle>100</TD>
<TD align=middle>2.3 x 10<SUP>17</SUP></TD>
<TD align=middle>74年</TD></TR>
<TR>
<TD align=middle>200</TD>
<TD align=middle>1.2 x 10<SUP>23</SUP></TD>
<TD align=middle>3.8 x
10<SUP>9</SUP>年</TD></TR></TBODY></TABLE></DIV>
<P align=center>（至于怎么算的，我也不清楚，可能用了组合学和统计学的知识，这方面我不灵的）</P>
<P> </P>
<P>密码学资料</P>
<P>1. Rivest, R. L; Shemir, A.; Adleman, L. 《A method for obtaining
digital signature and public-key cryptasystem》 Communication of ACM,
1978, pp. 120-126.</P>
<P>2. Simmons, G. 《Cryptology : The mathematics of sewre
communication》 The Mathematical Intelligencer, 1978, pp.
233-246.</P>
<P>3. Hellman，M.E. 《The mathematics of public-key cryptography》
Scientific American, August, 1979, pp. 146-157.</P>
<P>4. Pomerance, C. 《The search for prime numbers》 Scientific
American, December, 1982, pp. 136-147.</P>
<P>5. Paul Fahn, 《About Today's Cryptography V2.0 draft 2f》 RSA
Laboratories, September 20, 1993 ( <A
href="http://secu.zzu.edu.cn/chutium/software/rsa/rsafaq.txt">http://secu.zzu.edu.cn/chutium/software/rsa/rsafaq.txt</A>
)</P>
<P>6. The Mathematical Basis of RSA Key-Pair Generation ( <A
href="http://secu.zzu.edu.cn/chutium/software/rsa/rsakey.htm">http://secu.zzu.edu.cn/chutium/software/rsa/rsakey.htm</A>
)</P>
<P>7. The Latest RSA FAQ ( <A
href="http://www.rsasecurity.com/rsalabs/faq/3-1-1.html">http://www.rsasecurity.com/rsalabs/faq/3-1-1.html</A>
)</P>
<P>8. 杨照昆(台湾) 《数学传播》</P>
<P> </P>
<P>相关文档</P>
<P>RSA Sample Code (C++) <A
href="http://secu.zzu.edu.cn/chutium/software/rsa/rsa.txt">RSA.CPP</A>
<A
href="http://secu.zzu.edu.cn/chutium/software/rsa/rsah.txt">RSA.HPP</A>
<A
href="http://secu.zzu.edu.cn/chutium/software/rsa/vlong.txt">VLONG.CPP</A>
<A
href="http://secu.zzu.edu.cn/chutium/software/rsa/vlongh.txt">VLONG.HPP</A>
; RSA Sample Code (VB) <A
href="http://secu.zzu.edu.cn/chutium/software/rsa/rsavb.txt">rsavb.txt</A></P>
<P> </P>
<P>我的留言本： <A
href="http://two.guestbook.de/gb.cgi?gid=584097&prot=uhsaif">http://two.guestbook.de/gb.cgi?gid=584097&prot=uhsaif</A></P><BR><!--内容结束//--></TD></TR></TBODY></TABLE></TD></TR></TBODY></TABLE><BR><!--文章评论开始//-->
<TABLE align=center bgColor=#006699 border=0 cellPadding=0 cellSpacing=0
width=770>
<TBODY>
<TR bgColor=#006699>
<TD align=middle bgColor=#006699 id=white><FONT
color=#ffffff>对该文的评论</FONT></TD>
<TD align=middle><!--文章人气开始//-->
<SCRIPT
src="CSDN_文档中心_分析 RSA 算法演算过程及VB和C++的实现方法.files/readnum.htm"></SCRIPT>
<!--文章人气开始//--></TD></TR></TBODY></TABLE>
<TABLE align=center bgColor=#666666 border=0 cellPadding=2 cellSpacing=1
width=770>
<TBODY>
<TR>
<TD bgColor=#cccccc colSpan=3><SPAN style="COLOR: #cccccc"><IMG height=16
hspace=1 src="CSDN_文档中心_分析 RSA 算法演算过程及VB和C++的实现方法.files/ico_pencil.gif"
width=16> </SPAN> idler <I>(2003-1-28
21:06:18)</I> </TD></TR>
<TR>
<TD bgColor=#ffffff colSpan=3 width=532><BR>VLONG是一个比较慢的MP库，建议用Gnu
MP一类的专门的MP库。 <BR></TD></TR></TBODY></TABLE>
<TABLE align=center bgColor=#666666 border=0 cellPadding=2 cellSpacing=1
width=770>
<TBODY>
<TR>
<TD bgColor=#cccccc colSpan=3><SPAN style="COLOR: #cccccc"><IMG height=16
hspace=1 src="CSDN_文档中心_分析 RSA 算法演算过程及VB和C++的实现方法.files/ico_pencil.gif"
width=16> </SPAN> chutium <I>(2003-1-28
12:45:20)</I> </TD></TR>
<TR>
<TD bgColor=#ffffff colSpan=3
width=532><BR>对前篇文章的定理做了修改（上篇文章没有直接给出定理，而是直接引的定理名）另外把以前的图片改过来了……原来那个免费空间已经没有了~
<BR></TD></TR></TBODY></TABLE><!--文章评论结束//--><BR>
<DIV align=center>
<TABLE align=center bgColor=#cccccc border=0 cellPadding=2 cellSpacing=1
width=770>
<TBODY>
<TR>
<TH bgColor=#006699 id=white><FONT
color=#ffffff>我要评论</FONT></TH></TR></TBODY></TABLE></DIV>⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?