RSA 加密算法

2016-11-27 2016-11-27 约 2647 字预计阅读 6 分钟

周五在上 c 语言课的时候，有幸接触了著名的 rsa 加密算法。rsa 算法作为目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的绝大多数密码攻击，已被 ISO 推荐为公钥数据加密标准。回寝室后我感觉这种算法很有趣并且以我们目前的学习进度可以进行编写，便进行了尝试。在开始前我也找到了一些资料，下面和大家分享一下。

1 RSA

1.1 rsa 算法的由来

1976 年以前，所有的加密方法都是同一种模式：

甲方选择某一种加密规则，对信息进行加密；
乙方使用同一种规则，对信息进行解密。

由于加密和解密使用同样规则（简称“密钥”），这被称为“对称加密算法”（Symmetric-key algorithm）。这种加密模式有一个最大弱点：甲方必须把加密规则告诉乙方，否则无法解密。保存和传递密钥，就成了最头疼的问题。

1976 年，两位美国计算机学家 Whitfield Diffie 和 Martin Hellman，提出了一种崭新构思，可以在不直接传递密钥的情况下，完成解密。这被称为“Diffie-Hellman 密钥交换算法”。这个算法启发了其他科学家。人们认识到，加密和解密可以使用不同的规则，只要这两种规则之间存在某种对应关系即可，这样就避免了直接传递密钥。这种新的加密模式被称为非对称加密算法：

乙方生成两把密钥（公钥和私钥）。公钥是公开的，任何人都可以获得，私钥则是保密的。
甲方获取乙方的公钥，然后用它对信息加密。
乙方得到加密后的信息，用私钥解密。

如果公钥加密的信息只有私钥解得开，那么只要私钥不泄漏，通信就是安全的。 1977 年，三位数学家 Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名，叫做 RSA 算法。从那时直到现在，RSA 算法一直是最广为使用的” 非对称加密算法”。毫不夸张地说，只要有计算机网络的地方，就有 RSA 算法。

1.2 rsa 算法的步骤

随机选择两个不相等的质数 $p$ 和 $q$。（实际应用中，这两个质数越大，就越难破解。）
计算 $p$ 和 $q$ 的乘积 $n$ 。$n$ 的长度就是密钥长度。3233 写成二进制是 110010100001，一共有 12 位，所以这个密钥就是 12 位。实际应用中，RSA 密钥一般是 1024 位，重要场合则为 2048 位。
计算 $n$ 的欧拉函数 $\varphi(n)$。根据公式：$\varphi(n) = (p-1)(q-1)$
随机选择一个整数 $e$ ，条件是 $1<e<\varphi(n)$ ,且 $e$ 与 $\varphi(n)$ 互质。
计算 $e$ 对于 $\varphi(n)$ 的模反元素 $d$
将 $n$ 和 $e$ 封装成公钥，$n$ 和 $d$ 封装成私钥

实际应用中，公钥和私钥的数据都采用 ASN.1 格式表达。

1.3 加密和解密

有了公钥和密钥，就能进行加密和解密了。

加密要用公钥 $(n,e)$ 所谓“加密”，就是算出下式的 $c$ ： $$m^e\equiv c \pmod{n}$$ 其中 $c$ 就是密文
解密要用私钥 $(n,d)$ 可以证明，下面的等式一定成立： $$ c^d\equiv m \pmod{n}$$ 也就是说，$c$ 的 $d$ 次方除以 $n$ 的余数为 $m$ 。$m$ 就是明文

至此，“加密–解密” 的整个过程全部完成。

2 后续

这种算法非常可靠，密钥越长，它就越难破解。根据已经披露的文献，目前被破解的最长 RSA 密钥是 768 个二进制位。也就是说，长度超过 768 位的密钥，还无法破解（至少没人公开宣布）。因此可以认为，1024 位的 RSA 密钥基本安全，2048 位的密钥极其安全。由于 rsa 的公钥 $(n,e)$ 只能加密小于 $n$ 的整数 $m$ ，那么如果要加密大于 $n$ 的整数，就要采用这么两种解决方法：一种是把长信息分割成若干段短消息，每段分别加密；另一种是先选择一种” 对称性加密算法”（比如 DES），用这种算法的密钥加密信息，再用 RSA 公钥加密 DES 密钥。

3 代码

由于时间与水平有限，目前编写的 rsa 还比较简陋，而且素数也不够大，只编写了的一个加密解密和在一起的程序，和单独加密的程序，还有单独随机公钥的程序，后续将会在时间充裕的时候补上有关明文字母分开的代码，以便于编写单独解密的程序。下面是我写的代码，欢迎大家的讨论。

  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
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <math.h>
int fun_1(int e,int fn);
int fun_2(int e,int fn);
int zhuan_huan(int b,int a[],int k);
int js_mod(int a,int b,int n);

/************
*   主函数   *
*************/
void main()
{
    int p,q,e,d,n,fn;
    long m[10000],c[100000];//c[10000]存放加密后的数字密文，m[1000]存放解密后的数字明文，即英文明文在zimu_biao[69]中的下标。
    int i,j;        //i,j用于循环遍历数组
    int mi_yue;    //用户输入的密钥
    int count=1;    //统计输入密钥的次数，count>3时将不允许用户再输入。
    char min_wen[10000],re_min_wen[10000];//分别为用户输入的明文、密文，解密后的明文。
    //密钥生成
    char zimu_biao[69]="abcdefghijklmnopqrstuvwxyz,ABCDEFGHIJKLMNOPQRSTUVWXYZ 0123456789'.?!";
    printf("请输入您要发送的明文文件（小写英文表示）:\n");
    printf("******************************************************\n");
    gets(min_wen);
    printf("******************************************************\n");
    srand((unsigned) time(NULL));
    printf("\n加密开始\n\n");

    do
    {
    p=rand()%201+101;
    for(i=2;i<=sqrt(p);i++)
        {
            if(p%i==0)
                break;
        }
    }while(i<=sqrt(p));

    do
    {
    q=rand()%201+101;
    for(i=2;i<=sqrt(q);i++)
        {
            if(q%i==0)
                break;
        }
    }while(i<=sqrt(q)||q==p);

    n=p*q;
    fn=(p-1)*(q-1);

    do
    {
        e=rand()%(fn)+1;
    }while(fun_1(e,fn));

    d=fun_2(e,fn);        //求解密指数d

    printf("******************************************************\n");
    printf("\n明文长度:%d\n",strlen(min_wen));
    printf("\n您的两个大素数分别为p=%d(保密),q=%d(保密)\n模数n=%d(公开),欧拉函数fn=%d(保密)\n",p,q,n,fn);
    printf("Public Key:%10d %10d(公钥,公开)\n",n,e);
    printf("Private Key:%10d %10d(私钥,保密)\n\n",n,d);

    //明文转换过程
    for(i=0;i<strlen(min_wen);i++)
        for(j=0;j<68;j++)
            if(min_wen[i]==zimu_biao[j])
                m[i]=j;//将字符串明文换成数字，并存到整型数组m里面，即明文的另一种表示方法

    //加密过程
    for(i=0;i<strlen(min_wen);i++)
        c[i]=js_mod(m[i],e,n);
    printf("输出密文：\n");
    printf("******************************************************\n");
    for(i=0;i<strlen(min_wen);i++)
        printf("%d",c[i]);
    printf("\n******************************************************\n");


    //提示用户解密
    printf("\n\n您有3次输入密钥（只需要输入私钥的d）的机会，3次输入错误将无法解密\n\n");
    while(1)
        {
            scanf("%d",&mi_yue);
            if(mi_yue==d)
            {
                printf("密钥输入正确，您得到的明文为：\n\n");
                for(i=0;i<strlen(min_wen);i++)
                    m[i]=js_mod(c[i],d,n);
                for(i=0;i<strlen(min_wen);i++)
                    re_min_wen[i]=zimu_biao[m[i]];
                for(i=0;i<strlen(min_wen);i++)
                    printf("%c",re_min_wen[i]);
                printf("\n\n");
                break;
            }
            else
            {
                printf("您第%d次输入的密钥错误，请重新输入。。。\n",count);
                count++;
                if(count>3)
                {
                    printf("\n您已%d次输入的密钥错误，将不允许继续输入\n",count-1);
                    break;
                }
            }
        }
}

//判断fn和e是否互素
int fun_1(int e,int fn)
{
    int i,null=0;
    for(i=2;i<=fn;i++)
    {
        if(e%i==0&&fn%i==0)
            null=1;
    }
    return null;
}

//扩展欧几里得算法求乘法逆元，即求解密指数d
int fun_2(int e,int fn)
{
    int d=1;
    while((e*d)%fn!=1)
    {
            d++;
    }
    return d;
}

//将十进制数转换成二进制
int zhuan_huan(int b,int a[],int k)
{
    int t,temp=-1;
    while(b>0){
        t=b%2;
        temp++;
        a[temp]=t;
        b=b/2;
    }
    return temp;
}

//快速计算模指数
int js_mod(int a,int b,int n)
{
    int x=0,y=1,k,i,s[1000];
    k=zhuan_huan(b,s,1000);
    for(i=k;i>=0;i--){
        x=2*x;
        y=(y*y)%n;
        if(s[i]==1){
            x++;
            y=(y*a)%n;
        }
    }
    return y;
}