RSA算法详解及C语言实现

1、什么是RSA
RSA公钥加密算法是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。1987年首次公布，当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。
RSA是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的绝大多数密码攻击，已被ISO推荐为公钥数据加密标准。
今天只有短的RSA钥匙才可能被强力方式解破。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长，用RSA加密的信息实际上是不能被解破的。但在分布式计算和量子计算机理论日趋成熟的今天，RSA加密安全性受到了挑战。
RSA算法基于一个十分简单的数论事实：将两个大质数相乘十分容易，但是想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。
RSA算法是现今使用最广泛的公钥密码算法，也是号称地球上最安全的加密算法。在了解RSA算法之前，先熟悉下几个术语
根据密钥的使用方法，可以将密码分为对称密码和公钥密码
对称密码：加密和解密使用同一种密钥的方式
公钥密码：加密和解密使用不同的密码的方式，因此公钥密码通常也称为非对称密码。
2. RSA加密
RSA的加密过程可以使用一个通式来表达

密文=$明文^E$ mod N

也就是说RSA加密是对明文的E次方后除以N后求余数的过程。
从通式可知，只要知道E和N任何人都可以进行RSA加密了，所以说E、N是RSA加密的密钥，也就是说E和N的组合就是公钥，我们用(E,N)来表示公钥

公钥 = （E，N）

不过E和N不并不是随便什么数都可以的，它们都是经过严格的数学计算得出的，关于E和N拥有什么样的要求及其特性后面会讲到。E是加密（Encryption）的首字母，N是数字（Number）的首字母。

3.RSA解密

明文 = $密文^D$ mod N

也就是说对密文进行D次方后除以N的余数就是明文，这就是RSA解密过程。知道D和N就能进行解密密文了，所以D和N的组合就是私钥

私钥＝(D,N)

从上述可以看出RSA的加密方式和解密方式是相同的，加密是求“E次方的mod N”;解密是求“D次方的mod N” 此处D是解密（Decryption）的首字母；N是数字（Number）的首字母。
4. 生成密钥对

生成密钥对（E，D，N）的步骤：
4.1 求N
准备两个质数p，q。这两个数不能太小，太小则会容易破解，将p乘以q就是N

N = p * q

4.2 求L（L为中间过程的中间数）
L 是 p－1 和 q－1的最小公倍数，可用如下表达式表示

L=lcm（p－1，q－1）

4.3 求E
E必须满足两个条件：E是一个比1大比L小的数，E和L的最大公约数为1
用gcd(X,Y)来表示X，Y的最大公约数则E条件如下：

1 < E < L
gcd（E，L）=1

之所以需要E和L的最大公约数为1是为了保证一定存在解密时需要使用的数D。现在我们已经求出了E和N也就是说我们已经生成了密钥对中的公钥了。

4.4 求D
数D是由数E计算出来的。D、E和L之间必须满足以下关系：

1 < D < L
E＊D mod L ＝ 1

只要D满足上述2个条件，则通过E和N进行加密的密文就可以用D和N进行解密。
简单地说条件2是为了保证密文解密后的数据就是明文。 现在私钥自然也已经生成了，密钥对也就自然生成了。

C语言实现：

#include<stdio.h>  
#include<stdlib.h>  

/* 函数申明 */  
int long_n(int n);  
int shuru(char *arr, int k, char *wei, int is_first);  
void jiami(char *arr, int k, int e, int n);  

/* 输入函数，记录从键盘输入的明文*/  
int shuru(char *arr, int k, char *wei, int is_first)  
{  
    int i;  
    char ch;  
    /*判断是否为第一分组的输入，如果是则获取输入的字符，否则就将上一分组最后获取的字符作为这一分组的第一个字符*/  
    if (is_first == 1)      
        ch = getchar();  
    else  
        ch = *wei;  
    for (i = 0; (i < k) && (ch != '\n');i++)  //获取字符直到获取到回车符为止  
    {  
        arr[i] = ch;  
        ch = getchar();  
    }  
    *wei = ch;  //最后获取到的字符准备作为下一分组的第一个字符  
    for (i = i; i < k; i++)  
        arr[i] = 'a';  //输入不够一组个数的整数倍则补'a'(即为补零)  
    if (ch == '\n')  //接收到回车符返回0，否则为1  
        return 0;  
    else  
        return 1;  
}   

/*加密函数*/  
void jiami(char *arr, int k, int e, int n)  
{   
    int m = 0,c=1, i, j,t=0, shu,temp,num=0;  
    int *array;  
    /*Mi赋值过程*/  
    for (i = 0; i < k; i++)  
    {  
        temp = 1;  
        for (j = 0; j < (k-i-1)*2; j++)  
            temp = temp * 10;  
        shu = (int)arr[i] - 97;  
        m = m + temp * shu;  
    }  
    temp = e;  
    /*获取e的二进制表达形式的位数*/  
    do{  
        temp = temp / 2;  
        num++;  
    } while (temp != 0);  
    array = (int *)malloc(sizeof(int)*k);   //申请动态数组  
    temp = e;  
    /*动态数组存储e的二进制表达形式*/  
    for (i = 0; i < num; i++)  
    {  
        array[i] = temp % 2;  
        temp = temp / 2;  
    }  
    /*避免出现天文数字的算法，详情见上文文字说明*/  
    for (i = num - 1; i >= 0; i--)  
    {  
        t = t * 2;  
        temp = c*c;  
        if (temp > n)  
        {  
            for (j = 0; temp - n*j >= 0; j++);  
            j--;  
            c = temp - n*j;  
        }  
        else  
            c = temp;  
        if (array[i] == 1)  
        {  
            t = t + 1;  
            temp = c*m;  
            if (temp > n)  
            {  
                for (j = 0; temp - n*j >= 0; j++);  
                j--;  
                c = temp - n*j;  
            }  
            else  
                c = temp;         
        }  

        e = e / 2;  
    }  
    temp = c;  
    i = 0;  
    /*c的位数小于分组长度则在前补零*/  
    do{  
        temp = temp / 10;  
        i++;  
    } while (temp != 0);  
    for (i; i < num; i++)  
        printf("0");  
    printf("%d", c);  
}   

/*获取分组的长度*/  
int long_n(int n)  
{   
    int temp,i,j,k,shi,comp=0;  
    temp = n;  
    /*获取n的位数*/  
    for (i = 1; temp / 10 != 0; i++)  
    {  
        temp = temp / 10;  
    }  
    temp = i;  
    /*若n的位数为基数*/  
    if (i % 2 != 0)  
    {  
        i = i - 1;  
        return i;  
    }  
    /*若位数为偶数*/  
    else  
    {  
        for (j = 0; j < i/2; j++)  
        {  
            shi = 1;  
            for (k = 0; k < temp - 2; k++)  
                shi = shi * 10;  
            comp = comp + shi * 25;  
            temp = temp - 2;  
        }  
        if (comp <= n)  
            return i;  
        else  
        {  
            i = i - 2;  
            return i;  
        }  
    }  
}   

/*主函数*/  
int main()  
{  
    int p, q, e, d, n, fai_n, k, i,is_first=1;  
    char ch,*arr,wei='a';  
    printf("请输入p、q、e值，用空格间隔开\n");  
    scanf_s("%d%d%d", &p, &q, &e);  //从键盘获取p、q、e值  
    n = p*q;    
    fai_n = (p-1)*(q-1);   //Φ(n)  
    for (k = 0; (k*n + 1) % e != 0; k++);  
    if ((k*n + 1) % e == 0)  
        d = (k*n + 1) / e;  //d * e ≡ 1 (mod Φ(n))  
    k = long_n(n);  
    k = k / 2;  //分组的长度  
    ch = getchar(); //缓冲回车符  
    arr = (char *)malloc(sizeof(char)*k);  //申请动态数组  
    printf("请输入明文\n");  
    while (1)  
    {  
            i=shuru(arr,k,&wei,is_first);  //调用输入字符的函数，接收到回车符返回0，否则为1  
        is_first = 0;  //第一分组录入结束设为0  
        jiami(arr,k,e,n);  //调用加密函数  
        if (i == 0)  //接收到返回值为0跳出循环  
            break;  
    }  
    printf("\n");  
    return 0;  
} 
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
164
165
166
167