RSA算法

RSA算法可以说在我们使用计算机的每一方面都在发挥着作用, EXE文件的签名算法用的是SHA1 + RSA. 我们每天登陆网银, 使用QQ 无时不刻都在使用着RSA算法. 发明这算法的人, 真心牛逼.

搞这种算法才知道, 数学基础是那么的重要. 尼玛, 以前老师教的时候, 为什么不这样说. 不如是的告诉我们. 工作以后才发现, 在计算机领域数学是必备的学科, 数学学的是否良好. 直接关系到在计算机领域能够专研的深度. 再说回来, 发明这算法的人也太牛逼了.

所以我不准备详细的说这个算法的细节, 估计讲也讲不清楚, 这里有一篇文章讲RSA非常的不错.

http://www.ruanyifeng.com/blog/2013/06/rsa_algorithm_part_one.html

在我们写代码的过程中也是经常会接触这种算法的. 主要了解如何使用这种算法..

RSA算法简单描述

找两素数p和q 取n=pq 取t=(p-1)(q-1) 取任何一个数e,要求满足e<t并且e与t互素(就是最大公因数为1) 取d *e%t ==1

这样最终得到三个数： n d e

设消息为数M (M <n) 设c=(Md)%n 就得到了加密后的消息c 设m=(ce)%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里面有一个例子我准备贴出来.

```c++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46


//
// 初始化MIRACL系统, 初始化500位的10进行制数
//
mip = mirsys( 500, 16 );

/* MIRACL大数运算库运算
 * p=C75CB54BEDFA30AB
 * q=A554665CC62120D3
 * n=80C07AFC9D25404D6555B9ACF3567CF1
 * d=651A40B9739117EF505DBC33EB8F442D
 * e=10001
 * 128 bit
 */
mip->IOBASE = 16;             // 设定16进制模式
n = mirvar( 0 );              // 初始化变量
e = mirvar( 0 );
m = mirvar( 0 );              // m 放明文：注册码
c = mirvar( 0 );              // c 放密文

cinstr( m, szSerial );              // 将输入的序列号转换成大数 ，这里szSerial
cinstr( n, "80C07AFC9D25404D6555B9ACF3567CF1" );    // 初始化模数n
cinstr( e, "10001" );

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 从大数转换成字节数组

    mirkill( n );
    mirkill( e );
    mirkill( m );
    mirkill( c );
    mirexit();

    if( lstrcmp( szName, szBuffer ) != 0 )         // 比较姓名与序列号加密后数据的是否相等？
    {
        SetDlgItemText( hWnd, IDC_Serial, "Wrong Serial!" );
        return FALSE;
    }
    else
    {
        SetDlgItemText( hWnd, IDC_Serial, "Success!" );
        return TRUE;
    }
}

```

事实上, RSA算法也是可逆的. 用私钥加密出来的, 用公钥也可以解.. 上面这段代码是加密解密3里面的, 正常来说, 这段代码会出现在发布的程序里面, 用来验证用户名. 是否正确. 这里匹配的是用公钥和密文做运算, 计算出明文.. 这段代码有点奇怪, 和我们理解RSA算法有点相反.重点是记住, 虽然RSA是非对称加密算法, 但是如果你有公钥, 私钥. 其实是可逆的. 下面这段代码是用私钥求序列号的.

```c++ mip = mirsys( 500, 16 ); /* MIRACL大数运算库运算 * p=C75CB54BEDFA30AB * q=A554665CC62120D3 * n=80C07AFC9D25404D6555B9ACF3567CF1 * d=651A40B9739117EF505DBC33EB8F442D * e=10001 * 128 bit */ mip->IOBASE = 16; // 16进制模式 c = mirvar( 0 ); // MIRACL的大数类型 n = mirvar( 0 ); d = mirvar( 0 ); m = mirvar( 0 );

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


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 );

mirkill( c );
mirkill( n );
mirkill( d );
mirkill( m );
mirexit();

```

正如看雪加密解密3中所说的, 在实际应用中, 如果我们跟出来了. n和e.. 这个在用公钥计算密文的时候会用到, 跟到n和e以后, 我们就可以利用RSATool之类的工具生成与目标软件中的n相同位数的长度的n, 这时候的 d, p, q我们都知道了. 然后替换软件中的n. 然后利用自己的d就可以写出注册机了.. 当然在网络传输的过程当中也差不多. 实在不行就模拟一个服务端, 改写本地平台的n. 模拟一个d解密.

还有, 实际使用的时候, n一定要搞长一点, 1024. 以上才能保证安全, 刚才用RSATool算了一个128位的因式分解. 一会就求出来了.. 如果太短了. 形同虚设.. 另外加密解密3. 另外一个客户端, 服务端的例子也很不错..

文章目录