RSA演算过程的介绍
Rivest Shamir Adleman (RSA) Encryption Introduction and Sample Code
Seraph Chutium -- http://com.6to23.com/
先是本站留言本里的一点关于RSA的介绍。
| 61 |
Date: 2002-04-29 06:41:04 chutium RSA是用与两个极大质数(a,b)的积互素的一个整数(ency)对整个明文进行数学变换后得到加密的密文{n=ab,f(n)=(a-1)(b-1),encryp*decryp=1 mod f(n)}。为什么不一定可以显示？这个的资料在网上应该很好找，不过很少有说及它数学变化实质的，你最好到国外大学的BBS看看。大学教材里这些东西应该都有更详尽的介绍，不过年少时有谁真的塌实学了呢…… |
|
| 67 |
Date: 2002-04-30 06:52:38 liyx RSA的公钥和私钥都是两个大素数即大于100个十进制位的函数。 据猜测，从一个密钥和密文推断出明文的难度等同于分解两个大素数的积。 产生密钥时选择两个大素数，p和q。计算：n = p*q 然后随机选择加密密钥e，要求 e 和(p-1)*(q-1) 互质。最后，利用 Euclid 算法计算解密密钥d, 满足 e*d = 1(mod(p-1)*(q-1))其中n和d也要互质。数e和n是公钥，d是私钥(即你说的decrypt)。两个素数p和q不再需要，应该丢弃。 加密信息 m（二进制表示）时，首先把m分成等长数据块 m1 ,m2,..., mi ，块长s，其中 2^s<=n,s 尽可能的大。 对应的密文是：ci = mi^e(mod n)(a) 解密时作如下计算：mi = ci^d(mod n)(b) RSA数字签名是用(a)式签名，(b)式验证。具体操作时考虑到安全性和m信息量较大等因素，一般是先作HASH运算。 |
|
如果您是加密算法的爱好者，看上面两贴就可以了，下面是我通过上两贴和一些资料(见文末)整理的比较详细的加密过程，有比较好的数学基础的朋友如果有兴趣请继续看。
建议阅读者基本了解“因子、质数、同余式与费马、欧拉定理、Wilson定理、Lucas定理”等数论知识。
这个加密方法是上列三位科学家在1978所发表的，其步骤如下
-
1.收报者取两个相异的大质数p、q及另一与(p-1)(q-1)互质的数a，且a<w令
w=(p-1)(q-1),m=pq及p、q的较小者的位数（十进位）为k。 - 2.（公开）告诉发报者k，m与a。
-
3.发报者将他的信号分成许多段，每段含k-1位数（十进位）（若k=3（即p、q均为不小于二位的数），则信号
331414320001则应分成33,14,14,32,00,01一个一个的考虑发出），设发报者的信号的一为x（k-1位数，即上例中的33，或14，或32，…），则他将它作成发出。
-
4.收报者收到c之后，即可把原有的x求出来，因a与w互质，由定理2.2及系知，我们可找到二整数d、e；d>0使得
ad+we=1令则此y即发报者的x。我们先证明 y=x。
但因 w、a、d 均为大于 1 的整数，故 e 必为一负数，即 -e 为一正数，又因x小于质数 p、q，故 x 同 m 互质，由定理2.3的系得
但因y与x均取小于m的数，故y=x。故本程序的正确性得证。
我其它方面比较弱，所以对破解年限计算很不在行，这里是我手头《数学传播》上的资料，有增补。
这种密码关键在于p、q两个大质数的破解，据此文介绍，分解m成为p、q为一件极费时的工作，若分解不开m，则找不到w与d，因此就无法从c解得x，在不久以前，要分解一个数的因子仍停留在近乎硬试的阶段，即要从2，3，5，7，…，一直试到n^(1/2)附近才停止。若n是50位数而p、q均近25位数，则分解m要除约1025次，若以电子计算机以每秒106次的高速运算，这仍是一个1011年的工作，目前由于大家对这方面的重视，分解一个50位数的时间已可缩短至1010次运算。下面的表中列出了目前(1980年)，分解一个大数大概所需的时间。
| m的位数 | 分解m的最少运算次数 | 最快（1980年）电脑所费的时间 |
| 50 | 1.4 x 1010 | 3.9小时 |
| 70 | 9.0 x 1012 | 104天 |
| 80 | 1.3 x 1013 | 150天 |
| 100 | 2.3 x 1017 | 74年 |
| 200 | 1.2 x 1023 | 3.8 x 109年 |
（至于怎么算的，我也不清楚，可能用了组合学和统计学的知识，这方面我不灵的）
密码学资料
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.
2. Simmons, G. 《Cryptology : The mathematics of sewre communication》 The Mathematical Intelligencer, 1978, pp. 233-246.
3. Hellman，M.E. 《The mathematics of public-key cryptography》 Scientific American, August, 1979, pp. 146-157.
4. Pomerance, C. 《The search for prime numbers》 Scientific American, December, 1982, pp. 136-147.
5. Paul Fahn, 《About Today's Cryptography V2.0 draft 2f》 RSA Laboratories, September 20, 1993 ( http://www.surfsites.net/chutium/rsa/rsafaq.txt )
6. The Mathematical Basis of RSA Key-Pair Generation ( http://www.surfsites.net/chutium/rsa/rsakey.htm )
7. The Latest RSA FAQ ( http://www.rsasecurity.com/rsalabs/faq/3-1-1.html )
8. 杨照昆(台湾) 《数学传播》
相关文档
RSA Sample Code (C++) RSA.CPP RSA.HPP VLONG.CPP VLONG.HPP ; RSA Sample Code (VB) rsavb.txt
我的留言本： http://two.guestbook.de/gb.cgi?gid=584097&prot=uhsaif
其它文章： http://www.csdn.net/Develop/My_Article.asp?author=chutium
本文地址：http://www.45fan.com/dnjc/69006.html