转：http://www.joenchen.com/archives/979
RSA算法可以说在我们使用计算机的每一方面都在发挥着作用, EXE文件的签名算法用的是SHA1 + RSA. 我们每天登陆网银, 使用QQ 无时不刻都在使用着RSA算法. 发明这算法的人, 真心牛逼.
搞这种算法才知道, 数学基础是那么的重要. 尼玛, 以前老师教的时候, 为什么不这样说. 不如是的告诉我们. 工作以后才发现, 在计算机领域数学是必备的学科, 数学学的是否良好. 直接关系到在计算机领域能够专研的深度. 再说回来, 发明这算法的人也太牛逼了.
所以我不准备详细的说这个算法的细节, 估计讲也讲不清楚, 这里有一篇文章讲RSA非常的不错.
http://www.ruanyifeng.com/blog/2013/06/rsa_algorithm_part_one.html
在我们写代码的过程中也是经常会接触这种算法的. 主要了解如何使用这种算法..
RSA算法简单描述
找两素数p和q
取n=p*q
取t=(p-1)*(q-1)
取任何一个数e,要求满足e<t并且e与t互素(就是最大公因数为1)
取d *e%t ==1
这样最终得到三个数： n d e
设消息为数M (M <n)
设c=(M**d)%n 就得到了加密后的消息c
设m=(c**e)%n 则 m == M, 从而完成对c的解密.
注：**表示次方, 上面两式中的d和e可以互换.
在非对称加密中：
n e两个数构成公钥，可以告诉别人.
n d两个数构成私钥，d自己保留, 不让任何人知道。
给别人发送的信息使用e加密，只要别人能用d解开就证明信息是由你发送的，构成了签名机制。
别人给你发送信息时使用e加密，这样只有拥有d的你能够对其解密。
RSA的安全性在于对于一个大数n,没有有效的方法能够将其分解, 从而在已知n d的情况下无法获得e,同样在已知n e的情况下无法求得d.为什么无法求的. 这个就不管了. 数学家搞这个吧.
实际生成p, q的过程, 一般使用工具来做RSATool就是一款非常优秀的工具, 可以指定生成多少位的RSA. 指定好E. p, q, n, d都帮我们生成好了.看雪加密解密3里面有一个例子我准备贴出来.
// 初始化MIRACL系统, 初始化500位的10进行制数 |
* n=80C07AFC9D25404D6555B9ACF3567CF1
|
* d=651A40B9739117EF505DBC33EB8F442D
|
mip->IOBASE = 16; // 设定16进制模式
|
n = mirvar( 0 ); // 初始化变量
|
m = mirvar( 0 ); // m 放明文：注册码
|
c = mirvar( 0 ); // c 放密文
|
cinstr( m, szSerial ); // 将输入的序列号转换成大数 ，这里szSerial
|
cinstr( n, "80C07AFC9D25404D6555B9ACF3567CF1" ); // 初始化模数n
|
if( compare( m, n ) == -1 ) // m < n ,才能对消息m加密
|
powmod( m, e, n, c ); // 计算明文 c= m ^ e mod n
|
big_to_bytes( 0, c, szBuffer, FALSE ); // 将 c 从大数转换成字节数组
|
if( lstrcmp( szName, szBuffer ) != 0 ) // 比较姓名与序列号加密后数据的是否相等？
|
SetDlgItemText( hWnd, IDC_Serial, "Wrong Serial!" );
|
SetDlgItemText( hWnd, IDC_Serial, "Success!" );
|
事实上, RSA算法也是可逆的. 用私钥加密出来的, 用公钥也可以解.. 上面这段代码是加密解密3里面的, 正常来说,
这段代码会出现在发布的程序里面, 用来验证用户名. 是否正确. 这里匹配的是用公钥和密文做运算, 计算出明文.. 这段代码有点奇怪,
和我们理解RSA算法有点相反.重点是记住, 虽然RSA是非对称加密算法, 但是如果你有公钥, 私钥. 其实是可逆的.
下面这段代码是用私钥求序列号的.
* n=80C07AFC9D25404D6555B9ACF3567CF1
|
* d=651A40B9739117EF505DBC33EB8F442D
|
mip->IOBASE = 16; // 16进制模式
|
c = mirvar( 0 ); // MIRACL的大数类型
|
bytes_to_big( dtLength, szName, c ); // 将姓名转换成大数
|
cinstr( n, "80C07AFC9D25404D6555B9ACF3567CF1" ); // 初始化模数n
|
cinstr( d, "651A40B9739117EF505DBC33EB8F442D" ); // 初始化私钥d
|
powmod( c, d, n, m ); // 计算m = (c ^ d) mod n
|
cotstr( m, szSerial ); // 将m的16进制串表示写入szSerial中，即为注册码
|
SetDlgItemText( hWnd, IDC_Serial, szSerial ); |
正如看雪 加密解密3中所说的, 在实际应用中, 如果我们跟出来了. n和e.. 这个在用公钥计算密文的时候会用到, 跟到n和e以后,
我们就可以利用RSATool之类的工具生成与目标软件中的n相同位数的长度的n, 这时候的 d, p, q我们都知道了. 然后替换软件中的n.
然后利用自己的d就可以写出注册机了.. 当然在网络传输的过程当中也差不多. 实在不行就模拟一个服务端, 改写本地平台的n. 模拟一个d解密.
还有, 实际使用的时候, n一定要搞长一点, 1024. 以上才能保证安全, 刚才用RSATool算了一个128位的因式分解. 一会就求出来了.. 如果太短了. 形同虚设.. 另外加密解密3. 另外一个客户端, 服务端的例子也很不错..