首页
社区
课程
招聘
问答 CTF 排行榜 知识库 工具下载 峰会 看雪商城 证书查询
  1. 社区
  2. 编程技术
    3. 发新帖
[原创]加解密快速入门
发表于: 2023-2-7 08:41 9379

[原创]加解密快速入门

公众号坚毅猿 活跃值
2023-2-7 08:41
9379

本公众号分享的所有技术仅用于学习交流，请勿用于其他非法活动，如果错漏，欢迎留言指正

《加密与解密》第4版

加解密

  • 安全领域的重要分支和基础设施
  • 互联网重要数据的传输需要加解密
    • TCP/IP协议本身是明文的,不安全
    • 比如登陆时候用户名和密码
    • 比如收发的电子邮件。
    • QQ聊天内容(对公安机关开放解密接口，可以看到聊天记录)，曾经恐怖分子还列出一份安全IM工具列表
    • 加密议包括:https/tls/ssl等
      • http是明文的(所以有可能是钓鱼网站)，https是加密的，即使被嗅探到，解密可能需要耗费的时间是10W年级别，几乎不可能。
  • 重要数据存储也需要加密:
    • NTFS的EFS(合法用户登陆进入系统才能看到硬盘的内容，如果硬盘被拆下来装在其他的电脑上看到的是加密后的密文，破解需要耗费时间是10W年的级别，对称加密和非对称加密结合起来的方式，是现在最安全的一种加密方式)
    • WINRAR的文件加密等
      • res加密算法，美国推荐的标准加密算法
      • 密钥随机，包含数字，字母，符号
      • 备份自己的密码(显示密码中的几位作为提示)，避免自己忘了，自己都解不开
  • 防止文件被篡改，也需要数字签名
    • dll文件等
    • 公安犯罪记录保存，防止被篡改

      一、加解密算法的分类

      1. 对称加密

  • 单钥密码系统的加密方法，同一个密钥可以同时用作信息的加密和解密，这种加密方法称为对称加密，也称为单密钥加密。
    • 密钥是控制加密及解密过程的指令，在对称加密中，数据发送方用加密密钥和特殊加密算法对明文(原始数据)加密，使其变成复杂的加密密文发送出去。接收方收到密文后,若想解读原文，则需要使用加密密钥及相同算法的逆算法对密文进行解密,才能使其恢复成可读明文。
    • 在对称加密算法中，使用的密钥只有一个，发收信双方都使用这个密钥对数据进行加密和解密。
    • 优点：算法公开、计算量小、加密速度快、加密效率高
    • 缺点：密钥管理

      2. 非对称加密

  • 非对称加密算法需要两个密钥来进行加密和解密，这两个密钥是公开密钥( public key，简称公钥)和私有密钥(private key，简称私钥)
  • 如果用公钥对数据进行加密，只有对应的私钥才能解密。如果用私钥对数据进行加密，那么只有对应的公钥才能解密。因为加密和解密使用的是两个不同的密钥，所以这种算法叫做非对称加密算法。
  • eg: A，B用非对称加密通信:
    • 1）A生成一对密钥(公钥和私钥)并将公钥向其它方公开，私钥独自严格保密。
    • 2）得到该公钥的B使用该密钥对机密信息进行加密后再发送给A方。
    • 3）A方再用自己保存的另一把专用密钥(私钥)对加密后的信息进行解密。A方只能用其专用密钥(私钥)解密由对应的公钥加密后的信息。
    • 在传输过程中，即使攻击者截获了传输密文，并得到A的公钥，也无法破解密文，因为只有A的私钥才能解密密文。
    • 同样，如果A回复加密信息给B，那么需要B先公布B的公钥给A用于加密，B自己保存B的私钥用于解密。
  • 优点：密钥管理的安全性更好（不需要像对称加密那样，要把密钥告诉很多人，只需要把公钥告诉其他人）
  • 缺点：加密和解密花费时间长、速度慢，只适合对少量数据进行加密。所以一般是是对称加密与非对称加密相结合。
    • 加密：用对称加密来加密数据得到密文A，用非对称加密加密对称加密的密钥得到密文B，把AB放到一起
    • 解密：先用非对称解密密文B得到对称加密的密钥，用这个密钥再去解密密文A得到原来的数据

      3. 散列算法

  • 散列(Hash)函数对不同长度的输入消息，产生固定长度(比如MD5是16字节(128位)的输出
    • 这个固定长度的输出称为原输入消想的“散列"或“消息摘要”(Message digest)。
  • 一个安全的哈希函数H必须具有以下属性:
    • 1）能够应用到大小不一的数据上。
    • 2）H能够生成大小固定的输出
    • 3）对于任意给定的x，H(×)的计算相对简单。
    • 4）对于任意给定的代码h，要发现满足H(x)=h的x在计算上是不可行的。(通过hash值无法反推出原数据，但可以破解，比如可以通过设定一个字典，计算出每一个单词的hash值，通过一一碰撞，就得到加密前的原文)
    • 5）对于任意给定的块x，要发现满足H=H(x）而y=×在计算上是不可行的。(两个hash值相同，但不能推断出原来两个值也相同)
  • 应用：错误矫正，文件校验（奇偶校验,CRC,无防篡改功能)，数字签名等

4. 侧重点

  • 对称加密:
    • XOR
    • DES、3DES
    • AES Advanced Encryption Standard（工业标准）
    • Blowfish
    • twofish
  • 非对称加密:
    • RSA(两个大的素数(几十个字节的长度)之积，很难进行因式分解还原回原来的两个素数)
    • Elgamal
    • 背包算法
    • Rabin
    • D-H
    • ECC（圆曲线加密算法)
  • 散列HASH算法:
    • MD5 Message-Digest Algorithm5
    • SHA1 SHA2 (SHA-256,512)Secure Hash Algorithm.
  • 重点在加密解密的接口调用和应用，而不是加密解密算法本身的实现(数论，矩阵等)

    二、加解密算法详解

    1. 对称加密：异或算法

  • A为明文，B为密文
    • 加密:B=A^key
    • 解密:A=B^key
  • 丑闻：360密盘号称10W年无法破解，但一下子就被破解了，当时360把密盘项目外包出去了，外包人员图方便使用了异或算法，而且把密钥放在密文前面，最离谱的是把代码提交给360审计的时候还通过了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
#include <string.h>
#include <tchar.h>
 
/// 异或加密解密是一样的操作
void f(char *data, int datalen,char *key, int keylen)
{ 
    int i; 
    for (i = 0; i < datalen; i++) 
        data[i] = (char) (data[i] ^ key[i%keylen]); ///data轮流和key对应的字节进行异或
} 
 
int _tmain(int argc, _TCHAR* argv[])
{
 
    char buff[]="hello encrypt&decrypt";
    char key[]="1234abcd";
    f(buff,strlen(buff),key,strlen(key)); //XOR加密
    printf("encrypted:%s\n",buff);
    f(buff,strlen(buff),key,strlen(key)); //XOR解密
    printf("decrypted:%s\n",buff);
 
    return 0;
}

2. 对称加密：DES算法

  • DES全称为Data Encryption Standard,即数据加密标准，是一种使用密钥加密的块算法。
    • DES是可以被破解的，可能一本书的某一句话就是密钥。
    • DES算法的入口参数有三个:Key、Data、Mode。其中Key为7个字节共64位，是DES算法的工作密钥; Data为8个字节64位(加密以8Byte为基本单位)，是要被加密或被解密的数据;Mode为DES的工作方式,有两种：加密或解密
    • 比如加密数据有20Byte，以8Byte为基本单位，后面4个Byte不足8个Byte，填4Byte的0组成8个Byte进行加密。
  • 3DES (即Triple DES是DES向AES过渡的加密算法,它使用3条56位的密钥对数据进行三次加密。是DES的个更安全的变形。它以DES为基本模块，通过组合分组方法设计出分组加密算法。比起最初的DES，3DES更为安全。
  • 纯C写的和OpenSSL都是可移植的，比微软的CryptoAPI好(只能在windows下使用)，des.c和des.h是des加解密算法的实现
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
// des_test.c
//
#include "stdio.h"
#include "stdlib.h"  
#include "des.h"
#include <conio.h>
 
#pragma warning(disable:4996)
int main()  
{     
    char *file_In = "in.txt";
    char *file_Out = "out.txt";
    char *file_tmp = "des.dat";
    char *key = "key.txt";
    //DES加密 
    DES_Encrypt_File(file_In,key,file_tmp);  
    printf("DES_E OK!\n");
 
    //DES解密 
    DES_Decrypt_File(file_tmp,key,file_Out);
    if(remove(file_tmp)){}  
    printf("DES_D OK!\n");
 
    //3重DES加密
    D3DES_Encrypt_File(file_In,key,file_tmp);  
    printf("D3DES_E OK!\n");
 
    //3重DES解密 
    D3DES_Decrypt_File(file_tmp,key,file_Out);
    if(remove(file_tmp)){}  
    printf("D3DES_D OK!\n");
    /// 1.getchar()先将输入的字符保存在缓冲区，然后再从缓冲区读取这个字符，是间接读取；
    /// 2.getche()和getch()不需要将输入的字符保存在缓冲区，而是即输即取，也就是说，一输入一个字符，它立即直接读取；
    /// 1.执行到getchar()函数时，光标闪动，等待输入字符：输入字符后无变化，需要按回车键， 按回车键后，getchar读取了这个字符,并将其赋值给变量a。
    /// 2.执行到getche()函数时，光标闪动，等待输入字符：输入字符后，不需按回车键，在输入后，getche立即读入并赋值给b。
    /// 3.执行到getch()函数时，光标闪动，等待输入字符：输入字符，并不能看到你输入的字符，屏幕仍是； 但在输入后瞬间，getch()函数就读取并赋值给了c。
    getchar(); 
    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
/// des.h
#include "stdio.h"  
#include "memory.h"   
#include "stdlib.h"  
 
#define PLAIN_FILE_OPEN_ERROR -1  
#define KEY_FILE_OPEN_ERROR -2  
#define CIPHER_FILE_OPEN_ERROR -3  
#define DES_OK 1 
#define BUFFER_SIZE 1024
#define ROUND 16//迭代次数，16次以上破解时只能使用穷举法
 
typedef char ElemType; 
 
int ByteToBit(ElemType ch,ElemType bit[8]);//字节转换成二进制 
int BitToByte(ElemType bit[8],ElemType *ch);//二进制转换成字节
int Char8ToBit64(ElemType ch[8],ElemType bit[64]);//将长度为8的字符串转为二进制位串 
int Bit64ToChar8(ElemType bit[64],ElemType ch[8]);//将二进制位串转为长度为8的字符串 
int DES_MakeSubKeys(ElemType key[64],ElemType subKeys[16][48]);//生成子密钥 
int DES_PC1_Transform(ElemType key[64], ElemType tempbts[56]);//密钥置换1
int DES_PC2_Transform(ElemType key[56], ElemType tempbts[48]);//密钥置换2
int DES_ROL(ElemType data[56], int time);//循环左移
int DES_IP_Transform(ElemType data[64]);//IP置换  
int DES_IP_1_Transform(ElemType data[64]);//IP逆置换 
int DES_E_Transform(ElemType data[48]);//扩展置换
int DES_P_Transform(ElemType data[32]);//P置换 
int DES_SBOX(ElemType data[48]);//S盒置换  
int DES_XOR(ElemType R[48], ElemType L[48],int count);//异或
int DES_Swap(ElemType left[32],ElemType right[32]);//交换
int DES_EncryptBlock(ElemType plainBlock[8], ElemType subKeys[16][48], ElemType cipherBlock[8]);//加密单个分组  
int DES_DecryptBlock(ElemType cipherBlock[8], ElemType subKeys[16][48], ElemType plainBlock[8]);//解密单个分组  
//DES算法
int DES_Encrypt(ElemType *plainBuffer, ElemType *keyBuffer, ElemType *cipherBuffer, int n);//加密数据
int DES_Decrypt(ElemType *cipherBuffer, ElemType *keyBuffer, ElemType *plainBuffer, int n);//解密数据
int DES_Encrypt_File(char *plainFile, char *keyStr,char *cipherFile);//加密文件 
int DES_Decrypt_File(char *cipherFile, char *keyStr,char *plainFile);//解密文件
//3DES算法
int D3DES_Encrypt(ElemType *plainBuffer, ElemType *keyBuffer, ElemType *cipherBuffer, int n);//加密数据
int D3DES_Decrypt(ElemType *cipherBuffer, ElemType *keyBuffer, ElemType *plainBuffer, int n);//解密数据
int D3DES_Encrypt_File(char *plainFile, char *keyStr,char *cipherFile);//加密文件 
int D3DES_Decrypt_File(char *cipherFile, char *keyStr,char *plainFile);//解密文件
 
//初始置换表IP
static int IP_Table[64] = {  57,49,41,33,25,17,9,1,  
                     59,51,43,35,27,19,11,3,  
                     61,53,45,37,29,21,13,5,  
                     63,55,47,39,31,23,15,7,  
                     56,48,40,32,24,16,8,0,  
                     58,50,42,34,26,18,10,2,  
                     60,52,44,36,28,20,12,4,  
                     62,54,46,38,30,22,14,6}; 
 
//逆初始置换表IP^-1
static int IP_1_Table[64] = {39,7,47,15,55,23,63,31,  
                       38,6,46,14,54,22,62,30,  
                       37,5,45,13,53,21,61,29,  
                       36,4,44,12,52,20,60,28,  
                       35,3,43,11,51,19,59,27,  
                       34,2,42,10,50,18,58,26,  
                       33,1,41,9,49,17,57,25,  
                       32,0,40,8,48,16,56,24};
 
//扩充置换表E 
static int E_Table[48] = {31, 0, 1, 2, 3, 4,  
                  3,  4, 5, 6, 7, 8,  
                  7,  8,9,10,11,12,  
                  11,12,13,14,15,16,  
                  15,16,17,18,19,20,  
                  19,20,21,22,23,24,  
                  23,24,25,26,27,28,  
                  27,28,29,30,31, 0};  
 
//置换函数P 
static int P_Table[32] = {15,6,19,20,28,11,27,16,  
                  0,14,22,25,4,17,30,9,  
                  1,7,23,13,31,26,2,8,  
                  18,12,29,5,21,10,3,24};  
 
//S盒    
static int S[8][4][16] =//S1  
            {{{14,4,13,1,2,15,11,8,3,10,6,12,5,9,0,7},  
              {0,15,7,4,14,2,13,1,10,6,12,11,9,5,3,8},  
                {4,1,14,8,13,6,2,11,15,12,9,7,3,10,5,0},  
                {15,12,8,2,4,9,1,7,5,11,3,14,10,0,6,13}},  
                //S2  
              {{15,1,8,14,6,11,3,4,9,7,2,13,12,0,5,10},  
              {3,13,4,7,15,2,8,14,12,0,1,10,6,9,11,5},  
              {0,14,7,11,10,4,13,1,5,8,12,6,9,3,2,15},  
              {13,8,10,1,3,15,4,2,11,6,7,12,0,5,14,9}},  
              //S3  
              {{10,0,9,14,6,3,15,5,1,13,12,7,11,4,2,8},  
              {13,7,0,9,3,4,6,10,2,8,5,14,12,11,15,1},  
                {13,6,4,9,8,15,3,0,11,1,2,12,5,10,14,7},  
              {1,10,13,0,6,9,8,7,4,15,14,3,11,5,2,12}},  
              //S4  
              {{7,13,14,3,0,6,9,10,1,2,8,5,11,12,4,15},  
              {13,8,11,5,6,15,0,3,4,7,2,12,1,10,14,9},  
              {10,6,9,0,12,11,7,13,15,1,3,14,5,2,8,4},  
              {3,15,0,6,10,1,13,8,9,4,5,11,12,7,2,14}},  
              //S5  
              {{2,12,4,1,7,10,11,6,8,5,3,15,13,0,14,9},  
              {14,11,2,12,4,7,13,1,5,0,15,10,3,9,8,6},  
              {4,2,1,11,10,13,7,8,15,9,12,5,6,3,0,14},  
              {11,8,12,7,1,14,2,13,6,15,0,9,10,4,5,3}},  
              //S6  
              {{12,1,10,15,9,2,6,8,0,13,3,4,14,7,5,11},  
              {10,15,4,2,7,12,9,5,6,1,13,14,0,11,3,8},  
              {9,14,15,5,2,8,12,3,7,0,4,10,1,13,11,6},  
              {4,3,2,12,9,5,15,10,11,14,1,7,6,0,8,13}},  
              //S7  
              {{4,11,2,14,15,0,8,13,3,12,9,7,5,10,6,1},  
              {13,0,11,7,4,9,1,10,14,3,5,12,2,15,8,6},  
              {1,4,11,13,12,3,7,14,10,15,6,8,0,5,9,2},  
              {6,11,13,8,1,4,10,7,9,5,0,15,14,2,3,12}},  
              //S8  
              {{13,2,8,4,6,15,11,1,10,9,3,14,5,0,12,7},  
              {1,15,13,8,10,3,7,4,12,5,6,11,0,14,9,2},  
              {7,11,4,1,9,12,14,2,0,6,10,13,15,3,5,8},  
              {2,1,14,7,4,10,8,13,15,12,9,0,3,5,6,11}}};
 
//置换选择1              
static int PC_1[56] = {56,48,40,32,24,16,8,  
              0,57,49,41,33,25,17,  
              9,1,58,50,42,34,26,  
              18,10,2,59,51,43,35,  
              62,54,46,38,30,22,14,  
              6,61,53,45,37,29,21,  
              13,5,60,52,44,36,28,  
              20,12,4,27,19,11,3};  
 
//置换选择2
static int PC_2[48] = {13,16,10,23,0,4,2,27,  
              14,5,20,9,22,18,11,3,  
              25,7,15,6,26,19,12,1,  
              40,51,30,36,46,54,29,39,  
              50,44,32,46,43,48,38,55,  
              33,52,45,41,49,35,28,31};
 
//左移次数规定  
static int MOVE_TIMES[16] = {1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1};
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
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
/// des.c
#include "des.h"
 
#pragma warning(disable:4996)
 
//字节转换成二进制 
int ByteToBit(ElemType ch, ElemType bit[8]){  
    int cnt;  
    for(cnt = 0;cnt < 8; cnt++){  
        *(bit+cnt) = (ch>>cnt)&1;  
    }  
    return 0;  
}  
 
//二进制转换成字节
int BitToByte(ElemType bit[8],ElemType *ch){  
    int cnt;  
    for(cnt = 0;cnt < 8; cnt++){  
        *ch |= *(bit + cnt)<<cnt;  
    }  
    return 0;  
}  
 
//将长度为8的字符串转为二进制位串  
int Char8ToBit64(ElemType ch[8],ElemType bit[64]){  
    int cnt;  
    for(cnt = 0; cnt < 8; cnt++){          
        ByteToBit(*(ch+cnt),bit+(cnt<<3));  
    }  
    return 0;  
}  
 
//将二进制位串转为长度为8的字符串   
int Bit64ToChar8(ElemType bit[64],ElemType ch[8]){  
    int cnt;  
    memset(ch,0,8);  
    for(cnt = 0; cnt < 8; cnt++){  
        BitToByte(bit+(cnt<<3),ch+cnt);  
    }  
    return 0;  
}  
 
//生成子密钥     
int DES_MakeSubKeys(ElemType key[64],ElemType subKeys[16][48]){  
    ElemType temp[56];  
    int cnt;  
    DES_PC1_Transform(key,temp);//PC1置换  
    for(cnt = 0; cnt < ROUND; cnt++){//16轮跌代，产生16个子密钥  
        DES_ROL(temp,MOVE_TIMES[cnt]);//循环左移  
        DES_PC2_Transform(temp,subKeys[cnt]);//PC2置换，产生子密钥    
    }  
    return 0;  
}  
 
//密钥置换1
int DES_PC1_Transform(ElemType key[64], ElemType tempbts[56]){  
    int cnt;      
    for(cnt = 0; cnt < 56; cnt++){  
        tempbts[cnt] = key[PC_1[cnt]];  
    }  
    return 0;  
}  
 
//密钥置换2    
int DES_PC2_Transform(ElemType key[56], ElemType tempbts[48]){  
    int cnt;  
    for(cnt = 0; cnt < 48; cnt++){  
        tempbts[cnt] = key[PC_2[cnt]];  
    }  
    return 0;  
}  
 
//循环左移    
int DES_ROL(ElemType data[56], int time){     
    ElemType temp[56];  
    //保存将要循环移动到右边的位 
    memcpy(temp,data,time);  
    memcpy(temp+time,data+28,time);  
    //前28位移动     
    memcpy(data,data+time,28-time);  
    memcpy(data+28-time,temp,time);  
    //后28位移动  
    memcpy(data+28,data+28+time,28-time);  
    memcpy(data+56-time,temp+time,time);      
 
    return 0;  
}  
 
//IP置换
int DES_IP_Transform(ElemType data[64]){  
    int cnt;  
    ElemType temp[64];  
    for(cnt = 0; cnt < 64; cnt++){  
        temp[cnt] = data[IP_Table[cnt]];  
    }  
    memcpy(data,temp,64);  
    return 0;  
}  
 
//IP逆置换   
int DES_IP_1_Transform(ElemType data[64]){  
    int cnt;  
    ElemType temp[64];  
    for(cnt = 0; cnt < 64; cnt++){  
        temp[cnt] = data[IP_1_Table[cnt]];  
    }  
    memcpy(data,temp,64);  
    return 0;  
}  
 
//扩展置换  
int DES_E_Transform(ElemType data[48]){  
    int cnt;  
    ElemType temp[48];  
    for(cnt = 0; cnt < 48; cnt++){  
        temp[cnt] = data[E_Table[cnt]];  
    }     
    memcpy(data,temp,48);  
    return 0;  
}  
 
//P置换  
int DES_P_Transform(ElemType data[32]){  
    int cnt;  
    ElemType temp[32];  
    for(cnt = 0; cnt < 32; cnt++){  
        temp[cnt] = data[P_Table[cnt]];  
    }     
    memcpy(data,temp,32);  
    return 0;  
}  
 
//异或 
int DES_XOR(ElemType R[48], ElemType L[48] ,int count){  
    int cnt;  
    for(cnt = 0; cnt < count; cnt++){  
        R[cnt] ^= L[cnt];  
    }  
    return 0;  
}  
 
//S盒置换    
int DES_SBOX(ElemType data[48]){  
    int cnt;  
    int line,row,output;  
    int cur1,cur2;  
    for(cnt = 0; cnt < 8; cnt++){  
        cur1 = cnt*6;  
        cur2 = cnt<<2;  
        //计算在S盒中的行与列  
        line = (data[cur1]<<1) + data[cur1+5];  
        row = (data[cur1+1]<<3) + (data[cur1+2]<<2)  
            + (data[cur1+3]<<1) + data[cur1+4];  
        output = S[cnt][line][row];  
        //化为2进制  
        data[cur2] = (output&0X08)>>3;  
        data[cur2+1] = (output&0X04)>>2;  
        data[cur2+2] = (output&0X02)>>1;  
        data[cur2+3] = output&0x01;  
    }     
    return 0;  
}  
 
//交换 
int DES_Swap(ElemType left[32], ElemType right[32]){  
    ElemType temp[32];  
    memcpy(temp,left,32);     
    memcpy(left,right,32);    
    memcpy(right,temp,32);  
    return 0;  
}  
 
//加密单个分组
int DES_EncryptBlock(ElemType plainBlock[8], ElemType subKeys[16][48], ElemType cipherBlock[8]){  
    ElemType plainBits[64];  
    ElemType copyRight[48];  
    int cnt;  
 
    Char8ToBit64(plainBlock,plainBits);       
    //初始置换（IP置换）
    DES_IP_Transform(plainBits);  
    //16轮迭代  
    for(cnt = 0; cnt < ROUND; cnt++){         
        memcpy(copyRight,plainBits+32,32);  
        //将右半部分进行扩展置换，从32位扩展到48位  
        DES_E_Transform(copyRight);  
        //将右半部分与子密钥进行异或操作  
        DES_XOR(copyRight,subKeys[cnt],48);   
        //异或结果进入S盒，输出32位结果  
        DES_SBOX(copyRight);  
        //P置换
        DES_P_Transform(copyRight);  
        //将明文左半部分与右半部分进行异或  
        DES_XOR(plainBits,copyRight,32);  
        if(cnt != ROUND - 1){  
            //最终完成左右部的交换  
            DES_Swap(plainBits,plainBits+32);  
        }  
    }  
    //逆初始置换（IP^1置换）  
    DES_IP_1_Transform(plainBits);  
    Bit64ToChar8(plainBits,cipherBlock);  
    return 0;  
}  
 
//解密单个分组
int DES_DecryptBlock(ElemType cipherBlock[8], ElemType subKeys[16][48],ElemType plainBlock[8]){  
    ElemType cipherBits[64];  
    ElemType copyRight[48];  
    int cnt;  
 
    Char8ToBit64(cipherBlock,cipherBits);         
    //初始置换（IP置换）  
    DES_IP_Transform(cipherBits);  
 
    //16轮迭代  
    for(cnt = ROUND - 1; cnt >= 0; cnt--){        
        memcpy(copyRight,cipherBits+32,32);  
        //将右半部分进行扩展置换，从32位扩展到48位  
        DES_E_Transform(copyRight);  
        //将右半部分与子密钥进行异或操作  
        DES_XOR(copyRight,subKeys[cnt],48);       
        //异或结果进入S盒，输出32位结果 
        DES_SBOX(copyRight);  
        //P置换  
        DES_P_Transform(copyRight);       
        //将明文左半部分与右半部分进行异或  
        DES_XOR(cipherBits,copyRight,32);  
        if(cnt != 0){  
            //最终完成左右部的交换  
            DES_Swap(cipherBits,cipherBits+32);  
        }  
    }  
    //逆初始置换（IP^1置换）  
    DES_IP_1_Transform(cipherBits);  
    Bit64ToChar8(cipherBits,plainBlock);  
    return 0;  
}  
 
/*加密数据（字符串）
 *plainBuffer:输入数据
 *keyBuffer:密钥（8字节）
 *cipherBuffer:输出数据
 *n:加密数据长度
 */
int DES_Encrypt(ElemType *plainBuffer, ElemType *keyBuffer, ElemType *cipherBuffer, int n){
    int des_size = n;
    int des_count = 0;
    int count = 0;
    ElemType plainBlock[8],cipherBlock[8],keyBlock[8];
    ElemType bKey[64];  
    ElemType subKeys[16][48];  
 
    //设置密钥  
    memcpy(keyBlock,keyBuffer,8);
    //将密钥转换为二进制流  
    Char8ToBit64(keyBlock,bKey);  
    //生成子密钥  
    DES_MakeSubKeys(bKey,subKeys);
 
    while (des_count + 8 <= des_size){
        memcpy(plainBlock,plainBuffer + des_count,8);
        DES_EncryptBlock(plainBlock,subKeys,cipherBlock); 
        memcpy(cipherBuffer + des_count,cipherBlock,8) ;  
        des_count += 8;
    }
 
    if((count = des_size - des_count)){
        memcpy(plainBlock,plainBuffer + des_count,count);
        //填充  
        memset(plainBlock + count,'\0',7 - count);
        //最后一个字符保存包括最后一个字符在内的所填充的字符数量  
        plainBlock[7] = 8 - count;  
        DES_EncryptBlock(plainBlock,subKeys,cipherBlock);  
        memcpy(cipherBuffer + des_count,cipherBlock,8);
    } 
    return DES_OK;
}
 
/*解密数据（字符串）
 *cipherBuffer:输入数据
 *keyBuffer:密钥（8字节）
 *plainBuffer:输出数据
 *n:解密数据长度
 *返回解密后数据长度
 */
int DES_Decrypt(ElemType *cipherBuffer, ElemType *keyBuffer, ElemType *plainBuffer, int n){
    int des_size = n;
    int des_count = 0;
    int count = 0;
    ElemType plainBlock[8],cipherBlock[8],keyBlock[8];
    ElemType bKey[64];  
    ElemType subKeys[16][48];  
 
    //设置密钥  
    memcpy(keyBlock,keyBuffer,8);
    //将密钥转换为二进制流 
    Char8ToBit64(keyBlock,bKey);  
    //生成子密钥 
    DES_MakeSubKeys(bKey,subKeys);
 
    while(1){  
        memcpy(cipherBlock,cipherBuffer + des_count,8);
        DES_DecryptBlock(cipherBlock,subKeys,plainBlock);
        if(des_count + 8 < des_size){  
            memcpy(plainBuffer + des_count,plainBlock,8);
            des_count += 8;
        } else { 
            break;  
        }  
    }
 
    //判断末尾是否被填充
    if(plainBlock[7] < 8){
      for(count = 8 - plainBlock[7]; count < 7; count++){  
        if(plainBlock[count] != '\0'){  
          break;  
        }  
      }  
    }
    if(count == 7){
      memcpy(plainBuffer + des_count,plainBlock,8 - plainBlock[7]);
      return des_count +8 - plainBlock[7];
    } else {
        memcpy(plainBuffer + des_count,plainBlock,8);
      return des_count +8 ;
    }
    return des_count + 8;
}
 
//加密文件 
int DES_Encrypt_File(char *plainFile, char *keyStr,char *cipherFile){  
    FILE *plain,*cipher,*key;
    ElemType *plainBlock,*cipherBlock,keyBlock[8];   
    long fileLen_in,fileLen_out;
    int count;
    if((plain = fopen(plainFile,"rb")) == NULL){  
        return PLAIN_FILE_OPEN_ERROR;  
    }     
    if((key = fopen(keyStr,"rb")) == NULL){  
        return KEY_FILE_OPEN_ERROR;  
    }    
    if((cipher = fopen(cipherFile,"wb")) == NULL){  
        return CIPHER_FILE_OPEN_ERROR;  
    }
    if((count = fread(keyBlock,sizeof(char),8,key)) == 8){
    }
 
    fseek(plain,0,SEEK_END);//将文件指针置尾     
    fileLen_out = fileLen_in = ftell(plain);//取文件指针当前位置      
    rewind(plain);//将文件指针重指向文件头 
 
    if (fileLen_in % 8 != 0)
      fileLen_out = (fileLen_in/8+1)*8;
    plainBlock = (ElemType *)malloc(fileLen_out * sizeof(ElemType));
    cipherBlock = (ElemType *)malloc(fileLen_out * sizeof(ElemType));
    fread(plainBlock,sizeof(char),fileLen_in,plain);  
 
    DES_Encrypt(plainBlock,keyBlock,cipherBlock,fileLen_in);
    fwrite(cipherBlock,sizeof(char),fileLen_out,cipher); 
 
    fclose(plain);  
    fclose(cipher);
    fclose(key);
    free(plainBlock);
    free(cipherBlock);
    return DES_OK;
}
 
//解密文件
int DES_Decrypt_File(char *cipherFile, char *keyStr,char *plainFile){  
FILE *plain,*cipher,*key;
    ElemType *plainBlock,*cipherBlock,keyBlock[8];   
    int count;
    long fileLen_in,fileLen_out;
 
    if((plain = fopen(plainFile,"wb")) == NULL){  
        return PLAIN_FILE_OPEN_ERROR;  
    }     
    if((key = fopen(keyStr,"rb")) == NULL){  
        return KEY_FILE_OPEN_ERROR;  
    }    
    if((cipher = fopen(cipherFile,"rb")) == NULL){  
        return CIPHER_FILE_OPEN_ERROR;  
    }
    if((count = fread(keyBlock,sizeof(char),8,key)) == 8){
    }
 
    fseek(cipher,0,SEEK_END);//将文件指针置尾     
    fileLen_out = fileLen_in = ftell(cipher);//取文件指针当前位置      
    rewind(cipher);//将文件指针重指向文件头 
 
    plainBlock = (ElemType *)malloc(fileLen_in * sizeof(ElemType));
    cipherBlock = (ElemType *)malloc(fileLen_in * sizeof(ElemType));
    fread(cipherBlock,sizeof(char),fileLen_in,cipher);  
 
    count = DES_Decrypt(cipherBlock,keyBlock,plainBlock,fileLen_in);
    fwrite(plainBlock,sizeof(char),count,plain);
 
    fclose(plain);  
    fclose(cipher);
    fclose(key);
    free(plainBlock);
    free(cipherBlock);
    return DES_OK;  
} 
 
/*3DES加密数据（字符串）
 *对区块使用3个64位密钥进行3次加密，相当于增加了密钥长度
 *plainBuffer:输入数据
 *keyBuffer:密钥（24字节）
 *cipherBuffer:输出数据
 *n:加密数据长度
 */
int D3DES_Encrypt(ElemType *plainBuffer, ElemType *keyBuffer, ElemType *cipherBuffer, int n){
    int des_size = n;
    int des_count = 0;
    int count = 0;
    int i;
    ElemType plainBlock[8],cipherBlock[8],keyBlock[24];
    ElemType bKey[3][64];
    ElemType subKeys[3][16][48];
 
    for (i = 0; i < 3 ; i++)
    {
        //设置密钥  
        memcpy(keyBlock+i*8,keyBuffer+i*8,8);
        //将密钥转换为二进制流  
        Char8ToBit64(keyBlock+i*8,bKey[i]);  
        //生成子密钥  
        DES_MakeSubKeys(bKey[i],subKeys[i]);
    }
 
    while (des_count + 8 <= des_size){
        memcpy(plainBlock,plainBuffer + des_count,8);
        for (i = 0; i < 3 ; i++)
        {
            DES_EncryptBlock(plainBlock,subKeys[i],cipherBlock);  
        }
        memcpy(cipherBuffer + des_count,cipherBlock,8) ; 
        des_count += 8;
    }
 
    if((count = des_size - des_count)){
        memcpy(plainBlock,plainBuffer + des_count,count);
        //填充  
        memset(plainBlock + count,'\0',7 - count);
        //最后一个字符保存包括最后一个字符在内的所填充的字符数量  
        plainBlock[7] = 8 - count;  
        {
            for (i = 0; i < 3 ; i++)
            {
                DES_EncryptBlock(plainBlock,subKeys[i],cipherBlock);  
            }
        }
        memcpy(cipherBuffer + des_count,cipherBlock,8);
    } 
    return DES_OK;
}
 
/*3DES解密数据（字符串）
 *cipherBuffer:输入数据
 *keyBuffer:密钥（24字节）
 *plainBuffer:输出数据
 *n:解密数据长度
 *返回解密后数据长度
 */
int D3DES_Decrypt(ElemType *cipherBuffer, ElemType *keyBuffer, ElemType *plainBuffer, int n){
    int des_size = n;
    int des_count = 0;
    int count = 0;
    int i;
    ElemType plainBlock[8],cipherBlock[8],keyBlock[24];
    ElemType bKey[3][64];  
    ElemType subKeys[3][16][48];  
 
    for (i = 0; i < 3 ; i++)
    {
        //设置密钥  
        memcpy(keyBlock+i*8,keyBuffer+i*8,8);
        //将密钥转换为二进制流  
        Char8ToBit64(keyBlock+i*8,bKey[i]);  
        //生成子密钥  
        DES_MakeSubKeys(bKey[i],subKeys[i]);
    }
 
    while(1){  
        memcpy(cipherBlock,cipherBuffer + des_count,8);
        for (i = 0; i < 3 ; i++)
        {
            DES_DecryptBlock(cipherBlock,subKeys[i],plainBlock);    
        }
        if(des_count + 8 < des_size){  
            memcpy(plainBuffer + des_count,plainBlock,8);
            des_count += 8;
        } else { 
            break;  
        }  
    }
 
    //判断末尾是否被填充
    if(plainBlock[7] < 8){
      for(count = 8 - plainBlock[7]; count < 7; count++){  
        if(plainBlock[count] != '\0'){  
          break;  
        }  
      }  
    }
    if(count == 7){
      memcpy(plainBuffer + des_count,plainBlock,8 - plainBlock[7]);
      return des_count +8 - plainBlock[7];
    } else {
      memcpy(plainBuffer + des_count,plainBlock,8);
      return des_count +8 ;
    }
    return des_count + 8;
}
 
//3DES加密文件
int D3DES_Encrypt_File(char *plainFile, char *keyStr,char *cipherFile){  
    FILE *plain,*cipher,*key;
    ElemType *plainBlock,*cipherBlock,keyBlock[24];   
    long fileLen_in,fileLen_out;
    int count;
    if((plain = fopen(plainFile,"rb")) == NULL){  
        return PLAIN_FILE_OPEN_ERROR;  
    }     
    if((key = fopen(keyStr,"rb")) == NULL){  
        return KEY_FILE_OPEN_ERROR;  
    }    
    if((cipher = fopen(cipherFile,"wb")) == NULL){  
        return CIPHER_FILE_OPEN_ERROR;  
    }
    if((count = fread(keyBlock,sizeof(char),24,key)) == 24){
    }
 
    fseek(plain,0,SEEK_END);//将文件指针置尾     
    fileLen_out = fileLen_in = ftell(plain);//取文件指针当前位置      
    rewind(plain);//将文件指针重指向文件头 
 
    if (fileLen_in % 8 != 0)
        fileLen_out = (fileLen_in/8+1)*8;
    plainBlock = (ElemType *)malloc(fileLen_out * sizeof(ElemType));
    cipherBlock = (ElemType *)malloc(fileLen_out * sizeof(ElemType));
    fread(plainBlock,sizeof(char),fileLen_in,plain);  
 
    D3DES_Encrypt(plainBlock,keyBlock,cipherBlock,fileLen_in);
    fwrite(cipherBlock,sizeof(char),fileLen_out,cipher); 
 
    fclose(plain);  
    fclose(cipher);
    fclose(key);
    free(plainBlock);
    free(cipherBlock);
    return DES_OK;
}
 
//3DES解密文件
int D3DES_Decrypt_File(char *cipherFile, char *keyStr,char *plainFile){  
    FILE *plain,*cipher,*key;
    ElemType *plainBlock,*cipherBlock,keyBlock[24];   
    int count;
    long fileLen_in,fileLen_out;
 
    if((plain = fopen(plainFile,"wb")) == NULL){  
        return PLAIN_FILE_OPEN_ERROR;  
    }     
    if((key = fopen(keyStr,"rb")) == NULL){  
        return KEY_FILE_OPEN_ERROR;  
    }    
    if((cipher = fopen(cipherFile,"rb")) == NULL){  
        return CIPHER_FILE_OPEN_ERROR;  
    }
    if((count = fread(keyBlock,sizeof(char),24,key)) == 24){
    }
 
    fseek(cipher,0,SEEK_END);//将文件指针置尾     
    fileLen_out = fileLen_in = ftell(cipher);//取文件指针当前位置      
    rewind(cipher);//将文件指针重指向文件头 
 
    plainBlock = (ElemType *)malloc(fileLen_in * sizeof(ElemType));
    cipherBlock = (ElemType *)malloc(fileLen_in * sizeof(ElemType));
    fread(cipherBlock,sizeof(char),fileLen_in,cipher);  
 
    count = D3DES_Decrypt(cipherBlock,keyBlock,plainBlock,fileLen_in);
    fwrite(plainBlock,sizeof(char),count,plain);
 
    fclose(plain);  
    fclose(cipher);
    fclose(key);
    free(plainBlock);
    free(cipherBlock);
    return DES_OK;  
}

3. 对称加密：AES算法

  • 高级加密标准（英语:Advanced Encryption Standard，缩写:AES) ,是美国联邦政府采用的一种区块加密标准这个标准用来替代原先的DES,已经被多方分析且广为全世界所使用,成为对称密钥加密中最流行的算法之一。
  • AES加密数据块分组长度必须为128比特(16字节)，密钥长度可以是128比特、192比特、256比特中的任意一个（如果数据块及密钥长度不足时,会补齐)
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
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
/*
 * Advanced Encryption Standard
 * @author Dani Huertas
 * @email huertas.dani@gmail.com
 *
 * Based on the document FIPS PUB 197
 */
#include <stdio.h>
#include <stdlib.h>
#include "stdint.h"
 
/*
 * Addition in GF(2^8)
 * http://en.wikipedia.org/wiki/Finite_field_arithmetic
 */
uint8_t gadd(uint8_t a, uint8_t b) {
    return a^b;
}
 
/*
 * Subtraction in GF(2^8)
 * http://en.wikipedia.org/wiki/Finite_field_arithmetic
 */
uint8_t gsub(uint8_t a, uint8_t b) {
    return a^b;
}
 
/*
 * Multiplication in GF(2^8)
 * http://en.wikipedia.org/wiki/Finite_field_arithmetic
 * Irreducible polynomial m(x) = x8 + x4 + x3 + x + 1
 */
uint8_t gmult(uint8_t a, uint8_t b) {
 
    uint8_t p = 0, i = 0, hbs = 0;
 
    for (i = 0; i < 8; i++) {
        if (b & 1) {
            p ^= a;
        }
 
        hbs = a & 0x80;
        a <<= 1;
        if (hbs) a ^= 0x1b; // 0000 0001 0001 1011   
        b >>= 1;
    }
 
    return (uint8_t)p;
}
 
/*
 * Addition of 4 byte words
 * m(x) = x4+1
 */
void coef_add(uint8_t a[], uint8_t b[], uint8_t d[]) {
 
    d[0] = a[0]^b[0];
    d[1] = a[1]^b[1];
    d[2] = a[2]^b[2];
    d[3] = a[3]^b[3];
}
 
/*
 * Multiplication of 4 byte words
 * m(x) = x4+1
 */
void coef_mult(uint8_t *a, uint8_t *b, uint8_t *d) {
 
    d[0] = gmult(a[0],b[0])^gmult(a[3],b[1])^gmult(a[2],b[2])^gmult(a[1],b[3]);
    d[1] = gmult(a[1],b[0])^gmult(a[0],b[1])^gmult(a[3],b[2])^gmult(a[2],b[3]);
    d[2] = gmult(a[2],b[0])^gmult(a[1],b[1])^gmult(a[0],b[2])^gmult(a[3],b[3]);
    d[3] = gmult(a[3],b[0])^gmult(a[2],b[1])^gmult(a[1],b[2])^gmult(a[0],b[3]);
}
 
/*
 * The cipher Key.   
 */
int K;
 
/*
 * Number of columns (32-bit words) comprising the State. For this
 * standard, Nb = 4.
 */
#define Nb 4
 
/*
 * Number of 32-bit words comprising the Cipher Key. For this
 * standard, Nk = 4, 6, or 8.
 */
int Nk;
 
/*
 * Number of rounds, which is a function of  Nk  and  Nb (which is
 * fixed). For this standard, Nr = 10, 12, or 14.
 */
int Nr;
 
/*
 * S-box transformation table
 */
static uint8_t s_box[256] = {
    // 0     1     2     3     4     5     6     7     8     9     a     b     c     d     e     f
    0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76, // 0
    0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0, // 1
    0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc, 0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15, // 2
    0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75, // 3
    0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0, 0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84, // 4
    0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf, // 5
    0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85, 0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8, // 6
    0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5, 0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2, // 7
    0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17, 0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73, // 8
    0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88, 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb, // 9
    0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c, 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79, // a
    0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9, 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08, // b
    0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6, 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a, // c
    0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e, 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e, // d
    0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94, 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf, // e
    0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16};// f
 
/*
 * Inverse S-box transformation table
 */
static uint8_t inv_s_box[256] = {
    // 0     1     2     3     4     5     6     7     8     9     a     b     c     d     e     f
    0x52, 0x09, 0x6a, 0xd5, 0x30, 0x36, 0xa5, 0x38, 0xbf, 0x40, 0xa3, 0x9e, 0x81, 0xf3, 0xd7, 0xfb, // 0
    0x7c, 0xe3, 0x39, 0x82, 0x9b, 0x2f, 0xff, 0x87, 0x34, 0x8e, 0x43, 0x44, 0xc4, 0xde, 0xe9, 0xcb, // 1
    0x54, 0x7b, 0x94, 0x32, 0xa6, 0xc2, 0x23, 0x3d, 0xee, 0x4c, 0x95, 0x0b, 0x42, 0xfa, 0xc3, 0x4e, // 2
    0x08, 0x2e, 0xa1, 0x66, 0x28, 0xd9, 0x24, 0xb2, 0x76, 0x5b, 0xa2, 0x49, 0x6d, 0x8b, 0xd1, 0x25, // 3
    0x72, 0xf8, 0xf6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xd4, 0xa4, 0x5c, 0xcc, 0x5d, 0x65, 0xb6, 0x92, // 4
    0x6c, 0x70, 0x48, 0x50, 0xfd, 0xed, 0xb9, 0xda, 0x5e, 0x15, 0x46, 0x57, 0xa7, 0x8d, 0x9d, 0x84, // 5
    0x90, 0xd8, 0xab, 0x00, 0x8c, 0xbc, 0xd3, 0x0a, 0xf7, 0xe4, 0x58, 0x05, 0xb8, 0xb3, 0x45, 0x06, // 6
    0xd0, 0x2c, 0x1e, 0x8f, 0xca, 0x3f, 0x0f, 0x02, 0xc1, 0xaf, 0xbd, 0x03, 0x01, 0x13, 0x8a, 0x6b, // 7
    0x3a, 0x91, 0x11, 0x41, 0x4f, 0x67, 0xdc, 0xea, 0x97, 0xf2, 0xcf, 0xce, 0xf0, 0xb4, 0xe6, 0x73, // 8
    0x96, 0xac, 0x74, 0x22, 0xe7, 0xad, 0x35, 0x85, 0xe2, 0xf9, 0x37, 0xe8, 0x1c, 0x75, 0xdf, 0x6e, // 9
    0x47, 0xf1, 0x1a, 0x71, 0x1d, 0x29, 0xc5, 0x89, 0x6f, 0xb7, 0x62, 0x0e, 0xaa, 0x18, 0xbe, 0x1b, // a
    0xfc, 0x56, 0x3e, 0x4b, 0xc6, 0xd2, 0x79, 0x20, 0x9a, 0xdb, 0xc0, 0xfe, 0x78, 0xcd, 0x5a, 0xf4, // b
    0x1f, 0xdd, 0xa8, 0x33, 0x88, 0x07, 0xc7, 0x31, 0xb1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xec, 0x5f, // c
    0x60, 0x51, 0x7f, 0xa9, 0x19, 0xb5, 0x4a, 0x0d, 0x2d, 0xe5, 0x7a, 0x9f, 0x93, 0xc9, 0x9c, 0xef, // d
    0xa0, 0xe0, 0x3b, 0x4d, 0xae, 0x2a, 0xf5, 0xb0, 0xc8, 0xeb, 0xbb, 0x3c, 0x83, 0x53, 0x99, 0x61, // e
    0x17, 0x2b, 0x04, 0x7e, 0xba, 0x77, 0xd6, 0x26, 0xe1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0c, 0x7d};// f
 
 
/*
 * Generates the round constant Rcon[i]
 */
uint8_t R[] = {0x02, 0x00, 0x00, 0x00};
 
uint8_t * Rcon(uint8_t i) {
 
    if (i == 1) {
        R[0] = 0x01; // x^(1-1) = x^0 = 1
    } else if (i > 1) {
        R[0] = 0x02;
        i--;
        while (i-1 > 0) {
            R[0] = gmult(R[0], 0x02);
            i--;
        }
    }
 
    return R;
}
 
/*
 * Transformation in the Cipher and Inverse Cipher in which a Round
 * Key is added to the State using an XOR operation. The length of a
 * Round Key equals the size of the State (i.e., for Nb = 4, the Round
 * Key length equals 128 bits/16 bytes).
 */
void add_round_key(uint8_t *state, uint8_t *w, uint8_t r) {
 
    uint8_t c;
 
    for (c = 0; c < Nb; c++) {
        state[Nb*0+c] = state[Nb*0+c]^w[4*Nb*r+4*c+0];   //debug, so it works for Nb !=4
        state[Nb*1+c] = state[Nb*1+c]^w[4*Nb*r+4*c+1];
        state[Nb*2+c] = state[Nb*2+c]^w[4*Nb*r+4*c+2];
        state[Nb*3+c] = state[Nb*3+c]^w[4*Nb*r+4*c+3];   
    }
}
 
/*
 * Transformation in the Cipher that takes all of the columns of the
 * State and mixes their data (independently of one another) to
 * produce new columns.
 */
void mix_columns(uint8_t *state) {
 
    uint8_t a[] = {0x02, 0x01, 0x01, 0x03}; // a(x) = {02} + {01}x + {01}x2 + {03}x3
    uint8_t i, j, col[4], res[4];
 
    for (j = 0; j < Nb; j++) {
        for (i = 0; i < 4; i++) {
            col[i] = state[Nb*i+j];
        }
 
        coef_mult(a, col, res);
 
        for (i = 0; i < 4; i++) {
            state[Nb*i+j] = res[i];
        }
    }
}
 
/*
 * Transformation in the Inverse Cipher that is the inverse of
 * MixColumns().
 */
void inv_mix_columns(uint8_t *state) {
 
    uint8_t a[] = {0x0e, 0x09, 0x0d, 0x0b}; // a(x) = {0e} + {09}x + {0d}x2 + {0b}x3
    uint8_t i, j, col[4], res[4];
 
    for (j = 0; j < Nb; j++) {
        for (i = 0; i < 4; i++) {
            col[i] = state[Nb*i+j];
        }
 
        coef_mult(a, col, res);
 
        for (i = 0; i < 4; i++) {
            state[Nb*i+j] = res[i];
        }
    }
}
 
/*
 * Transformation in the Cipher that processes the State by cyclically
 * shifting the last three rows of the State by different offsets.
 */
void shift_rows(uint8_t *state) {
 
    uint8_t i, k, s, tmp;
 
    for (i = 1; i < 4; i++) {
        // shift(1,4)=1; shift(2,4)=2; shift(3,4)=3
        // shift(r, 4) = r;
        s = 0;
        while (s < i) {
            tmp = state[Nb*i+0];
 
            for (k = 1; k < Nb; k++) {
                state[Nb*i+k-1] = state[Nb*i+k];
            }
 
            state[Nb*i+Nb-1] = tmp;
            s++;
        }
    }
}
 
/*
 * Transformation in the Inverse Cipher that is the inverse of
 * ShiftRows().
 */
void inv_shift_rows(uint8_t *state) {
 
    uint8_t i, k, s, tmp;
 
    for (i = 1; i < 4; i++) {
        s = 0;
        while (s < i) {
            tmp = state[Nb*i+Nb-1];
 
            for (k = Nb-1; k > 0; k--) {
                state[Nb*i+k] = state[Nb*i+k-1];
            }
 
            state[Nb*i+0] = tmp;
            s++;
        }
    }
}
 
/*
 * Transformation in the Cipher that processes the State using a non­
 * linear byte substitution table (S-box) that operates on each of the
 * State bytes independently.
 */
void sub_bytes(uint8_t *state) {
 
    uint8_t i, j;
    uint8_t row, col;
 
    for (i = 0; i < 4; i++) {
        for (j = 0; j < Nb; j++) {
            row = (state[Nb*i+j] & 0xf0) >> 4;
            col = state[Nb*i+j] & 0x0f;
            state[Nb*i+j] = s_box[16*row+col];
        }
    }
}
 
/*
 * Transformation in the Inverse Cipher that is the inverse of
 * SubBytes().
 */
void inv_sub_bytes(uint8_t *state) {
 
    uint8_t i, j;
    uint8_t row, col;
 
    for (i = 0; i < 4; i++) {
        for (j = 0; j < Nb; j++) {
            row = (state[Nb*i+j] & 0xf0) >> 4;
            col = state[Nb*i+j] & 0x0f;
            state[Nb*i+j] = inv_s_box[16*row+col];
        }
    }
}
 
/*
 * Function used in the Key Expansion routine that takes a four-byte
 * input word and applies an S-box to each of the four bytes to
 * produce an output word.
 */
void sub_word(uint8_t *w) {
 
    uint8_t i;
 
    for (i = 0; i < 4; i++) {
        w[i] = s_box[16*((w[i] & 0xf0) >> 4) + (w[i] & 0x0f)];
    }
}
 
/*
 * Function used in the Key Expansion routine that takes a four-byte
 * word and performs a cyclic permutation.
 */
void rot_word(uint8_t *w) {
 
    uint8_t tmp;
    uint8_t i;
 
    tmp = w[0];
 
    for (i = 0; i < 3; i++) {
        w[i] = w[i+1];
    }
 
    w[3] = tmp;
}
 
/*
 * Key Expansion
 */
void key_expansion(uint8_t *key, uint8_t *w) {
 
    uint8_t tmp[4];
    uint8_t i;
    uint8_t len = Nb*(Nr+1);
 
    for (i = 0; i < Nk; i++) {
        w[4*i+0] = key[4*i+0];
        w[4*i+1] = key[4*i+1];
        w[4*i+2] = key[4*i+2];
        w[4*i+3] = key[4*i+3];
    }
 
    for (i = Nk; i < len; i++) {
        tmp[0] = w[4*(i-1)+0];
        tmp[1] = w[4*(i-1)+1];
        tmp[2] = w[4*(i-1)+2];
        tmp[3] = w[4*(i-1)+3];
 
        if (i%Nk == 0) {
 
            rot_word(tmp);
            sub_word(tmp);
            coef_add(tmp, Rcon(i/Nk), tmp);
 
        } else if (Nk > 6 && i%Nk == 4) {
 
            sub_word(tmp);
 
        }
 
        w[4*i+0] = w[4*(i-Nk)+0]^tmp[0];
        w[4*i+1] = w[4*(i-Nk)+1]^tmp[1];
        w[4*i+2] = w[4*(i-Nk)+2]^tmp[2];
        w[4*i+3] = w[4*(i-Nk)+3]^tmp[3];
    }
}
 
void cipher(uint8_t *in, uint8_t *out, uint8_t *w) { //加密，w为key
 
    uint8_t state[4*Nb];
    uint8_t r, i, j;
 
    for (i = 0; i < 4; i++) {
        for (j = 0; j < Nb; j++) {
            state[Nb*i+j] = in[i+4*j];
        }
    }
 
    add_round_key(state, w, 0);
 
    for (r = 1; r < Nr; r++) {
        sub_bytes(state);
        shift_rows(state);
        mix_columns(state);
        add_round_key(state, w, r);
    }
 
    sub_bytes(state);
    shift_rows(state);
    add_round_key(state, w, Nr);
 
    for (i = 0; i < 4; i++) {
        for (j = 0; j < Nb; j++) {
            out[i+4*j] = state[Nb*i+j];
        }
    }
}
 
void inv_cipher(uint8_t *in, uint8_t *out, uint8_t *w) { //解密函数
 
    uint8_t state[4*Nb];
    uint8_t r, i, j;
 
    for (i = 0; i < 4; i++) {
        for (j = 0; j < Nb; j++) {
            state[Nb*i+j] = in[i+4*j];
        }
    }
 
    add_round_key(state, w, Nr);
 
    for (r = Nr-1; r >= 1; r--) {
        inv_shift_rows(state);
        inv_sub_bytes(state);
        add_round_key(state, w, r);
        inv_mix_columns(state);
    }
 
    inv_shift_rows(state);
    inv_sub_bytes(state);
    add_round_key(state, w, 0);
 
    for (i = 0; i < 4; i++) {
        for (j = 0; j < Nb; j++) {
            out[i+4*j] = state[Nb*i+j];
        }
    }
}
 
int main(int argc, char *argv[]) {
 
    uint8_t i;
 
    /*
     * Appendix A - Key Expansion Examples
     */
 
    /* 128 bits */
    /* uint8_t key[] = {
        0x2b, 0x7e, 0x15, 0x16,
        0x28, 0xae, 0xd2, 0xa6,
        0xab, 0xf7, 0x15, 0x88,
        0x09, 0xcf, 0x4f, 0x3c}; */
 
    /* 192 bits */
    /* uint8_t key[] = {
        0x8e, 0x73, 0xb0, 0xf7,
        0xda, 0x0e, 0x64, 0x52,
        0xc8, 0x10, 0xf3, 0x2b,
        0x80, 0x90, 0x79, 0xe5,
        0x62, 0xf8, 0xea, 0xd2,
        0x52, 0x2c, 0x6b, 0x7b}; */
 
    /* 256 bits */
    /* uint8_t key[] = {
        0x60, 0x3d, 0xeb, 0x10,
        0x15, 0xca, 0x71, 0xbe,
        0x2b, 0x73, 0xae, 0xf0,
        0x85, 0x7d, 0x77, 0x81,
        0x1f, 0x35, 0x2c, 0x07,
        0x3b, 0x61, 0x08, 0xd7,
        0x2d, 0x98, 0x10, 0xa3,
        0x09, 0x14, 0xdf, 0xf4};
    */
 
    /* uint8_t in[] = {
        0x32, 0x43, 0xf6, 0xa8,
        0x88, 0x5a, 0x30, 0x8d,
        0x31, 0x31, 0x98, 0xa2,
        0xe0, 0x37, 0x07, 0x34}; // 128
    */
 
    /*
     * Appendix C - Example Vectors
     */
 
    /* 128 bit key */
    /* uint8_t key[] = {
        0x00, 0x01, 0x02, 0x03,
        0x04, 0x05, 0x06, 0x07,
        0x08, 0x09, 0x0a, 0x0b,
        0x0c, 0x0d, 0x0e, 0x0f}; */
 
    /* 192 bit key */
    /* uint8_t key[] = {
        0x00, 0x01, 0x02, 0x03,
        0x04, 0x05, 0x06, 0x07,
        0x08, 0x09, 0x0a, 0x0b,
        0x0c, 0x0d, 0x0e, 0x0f,
        0x10, 0x11, 0x12, 0x13,
        0x14, 0x15, 0x16, 0x17}; */
 
    /* 256 bit key */
    uint8_t key[] = {
        0x00, 0x01, 0x02, 0x03,
        0x04, 0x05, 0x06, 0x07,
        0x08, 0x09, 0x0a, 0x0b,
        0x0c, 0x0d, 0x0e, 0x0f,
        0x10, 0x11, 0x12, 0x13,
        0x14, 0x15, 0x16, 0x17,
        0x18, 0x19, 0x1b, 0x1b,
        0x1c, 0x1d, 0x1e, 0x1f};
 
    /// data,AES加密数据块分组长度必须为128比特(16字节)
    uint8_t in[] = {
        0x00, 0x11, 0x22, 0x33,
        0x44, 0x55, 0x66, 0x77,
        0x88, 0x99, 0xaa, 0xbb,
        0xcc, 0xdd, 0xee, 0xff};
 
    uint8_t out[16]; // 128
 
    uint8_t *w; // expanded key
 
    switch (sizeof(key)) {
        default:
        case 16: Nk = 4; Nr = 10; break;
        case 24: Nk = 6; Nr = 12; break;
        case 32: Nk = 8; Nr = 14; break;
    }
 
    w = malloc(Nb*(Nr+1)*4);
 
    key_expansion(key, w);
 
    cipher(in /* in */, out /* out */, w /* expanded key */); ///加密
 
    printf("out:\n");
 
    for (i = 0; i < 4; i++) {
        printf("%02x %02x %02x %02x ", out[4*i+0]&0xff, out[4*i+1]&0xff, out[4*i+2]&0xff, out[4*i+3]&0xff);
    }
 
    printf("\n");
 
    memset(in,0,sizeof(in));
 
    inv_cipher(out, in, w); ///解密
 
    printf("msg:\n");
    for (i = 0; i < 4; i++) {
        printf("%02x %02x %02x %02x ", in[4*i+0]&0xff, in[4*i+1]&0xff, in[4*i+2]&0xff, in[4*i+3]&0xff);
    }
 
    printf("\n");
 
    exit(0);
 
}

4. 非对称加密：RSA算法

  • RSA公钥加密算法是1977年由罗纳德-本维斯特（ Ron Rivest)）、阿迪·萨莫尔
    (Adishamir)伦纳德·阿曼德(Leonard Adleman）一起提出的。1987年首次
    当时他们三人都行麻省理工学院工作。RSA就是他们兰人姓氏开头字母拼在
    起组成的。
  • RSA是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的绝大多数密码攻击，被ISO推荐为公钥数据加密标准。
  • RSA算法是一种非对称密码算法，所谓非对称，就是指该算法需要一对密钥，使用其中一个加密则需要用另一个才能解密。
  • RSA的算法涉及三个参数，n、e1、e2。
    • 其中，n是两个大质数p、q的积（n分解为p，q是数学难题),n的二进制表示时所占用的位数，就是所谓的密钥长度。而且根据n来计算出一次加解密的数据长度。
    • e1和e2是一对相关的值，e1可以任意取，但要求e1与(p-1)**(q-1)互质(没有公因数)；再选择e2,要求(e2*e1)mod((p-1)*(q-1))=1.。
  • ( n,e1),(n,e2)就是密钥对。其中(n,e1)为公钥,(n,e2)为私钥。
  • RSA加解密的算法完全相同，设A为明文,B为密文,则:
    • 加密：B=A^e1 mod n;(指数运算)
    • 解密A=B^e2 mod n;(公钥加密体制中，一般用公钥销加密，私钥解密)
    • e1保和e2可以互换使用，即:A=B^e1 mod n;B=A^e2 mod n;

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
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <limits.h>
 
#include <conio.h>
 
/* Accuracy with which we test for prime numbers using Solovay-Strassen algorithm.
 * 20 Tests should be sufficient for most largish primes */
#define ACCURACY 20
 
#define FACTOR_DIGITS 100
#define EXPONENT_MAX RAND_MAX
#define BUF_SIZE 1024
 
/* Initial capacity for a bignum structure. They will flexibly expand but this
 * should be reasonably high to avoid frequent early reallocs */
#define BIGNUM_CAPACITY 20
 
/* Radix and halfradix. These should be changed if the limb/word type changes */
#define RADIX 4294967296UL
#define HALFRADIX 2147483648UL
 
#define MAX(a,b) ((a) > (b) ? (a) : (b))
 
/**
 * Basic limb type. Note that some calculations rely on unsigned overflow wrap-around of this type.
 * As a result, only unsigned types should be used here, and the RADIX, HALFRADIX above should be
 * changed as necessary. Unsigned integer should probably be the most efficient word type, and this
 * is used by GMP for example.
 */
typedef unsigned int word;
 
/**
 * Structure for representing multiple precision integers. This is a base "word" LSB
 * representation. In this case the base, word, is 2^32. Length is the number of words
 * in the current representation. Length should not allow for trailing zeros (Things like
 * 000124). The capacity is the number of words allocated for the limb data.
 */
typedef struct _bignum {
    int length;
    int capacity;
    word* data;
} bignum;
 
/**
 * Some forward delcarations as this was requested to be a single file.
 * See specific functions for explanations.
 */
void bignum_iadd(bignum* source, bignum* add);
void bignum_add(bignum* result, bignum* b1, bignum* b2);
void bignum_isubtract(bignum* source, bignum* add);
void bignum_subtract(bignum* result, bignum* b1, bignum* b2);
void bignum_imultiply(bignum* source, bignum* add);
void bignum_multiply(bignum* result, bignum* b1, bignum* b2);
void bignum_idivide(bignum* source, bignum* div);
void bignum_idivider(bignum* source, bignum* div, bignum* remainder);
void bignum_remainder(bignum* source, bignum *div, bignum* remainder);
void bignum_imodulate(bignum* source, bignum* modulus);
void bignum_divide(bignum* quotient, bignum* remainder, bignum* b1, bignum* b2);
 
/**
 * Save some frequently used bigintegers (0 - 10) so they do not need to be repeatedly
 * created. Used as, NUMS[5] = bignum("5"), etc..
 */
word DATA0[1] = {0}; word DATA1[1] = {1}; word DATA2[1] = {2};
word DATA3[1] = {3}; word DATA4[1] = {4}; word DATA5[1] = {5};
word DATA6[1] = {6}; word DATA7[1] = {7}; word DATA8[1] = {8};
word DATA9[1] = {9}; word DATA10[1] = {10};
bignum NUMS[11] = {{1, 1, DATA0},{1, 1, DATA1},{1, 1, DATA2},
                   {1, 1, DATA3},{1, 1, DATA4},{1, 1, DATA5},
                   {1, 1, DATA6},{1, 1, DATA7},{1, 1, DATA8},
                   {1, 1, DATA9},{1, 1, DATA10}};
 
/**
 * Initialize a bignum structure. This is the only way to safely create a bignum
 * and should be called where-ever one is declared. (We realloc the memory in all
 * other cases which is technically safe but may cause problems when we go to free
 * it.)
 */
bignum* bignum_init() {
    bignum* b = malloc(sizeof(bignum));
    b->length = 0;
    b->capacity = BIGNUM_CAPACITY;
    b->data = calloc(BIGNUM_CAPACITY, sizeof(word));
    return b;
}
 
/**
 * Free resources used by a bignum. Use judiciously to avoid memory leaks.
 */
void bignum_deinit(bignum* b) {
    free(b->data);
    free(b);
}
 
/**
 * Check if the given bignum is zero
 */
int bignum_iszero(bignum* b) {
    return b->length == 0 || (b->length == 1 && b->data[0] == 0);
}
 
/**
 * Check if the given bignum is nonzero.
 */
int bignum_isnonzero(bignum* b) {
    return !bignum_iszero(b);
}
 
/**
 * Copy from source bignum into destination bignum.
 */
void bignum_copy(bignum* source, bignum* dest) {
    dest->length = source->length;
    if(source->capacity > dest->capacity) {
        dest->capacity = source->capacity;
        dest->data = realloc(dest->data, dest->capacity * sizeof(word));
    }
    memcpy(dest->data, source->data, dest->length * sizeof(word));
}
 
/**
 * Load a bignum from a base 10 string. Only pure numeric strings will work.
 */
void bignum_fromstring(bignum* b, char* string) {
    int i, len = 0;
    while(string[len] != '\0') len++; /* Find string length */
    for(i = 0; i < len; i++) {
        if(i != 0) bignum_imultiply(b, &NUMS[10]); /* Base 10 multiply */
        bignum_iadd(b, &NUMS[string[i] - '0']); /* Add */
    }
}
 
/**
 * Load a bignum from an unsigned integer.
 */
void bignum_fromint(bignum* b, unsigned int num) {
    b->length = 1;
    if(b->capacity < b->length) {
        b->capacity = b->length;
        b->data = realloc(b->data, b->capacity * sizeof(word));
    }
    b->data[0] = num;
}
 
/**
 * Print a bignum to stdout as base 10 integer. This is done by
 * repeated division by 10. We can make it more efficient by dividing by
 * 10^9 for example, then doing single precision arithmetic to retrieve the
 * 9 remainders
 */
void bignum_print(bignum* b) {
    int cap = 100, len = 0, i;
    char* buffer = malloc(cap * sizeof(char));
    bignum *copy = bignum_init(), *remainder = bignum_init();
    if(b->length == 0 || bignum_iszero(b)) printf("0");
    else {
        bignum_copy(b, copy);
        while(bignum_isnonzero(copy)) {
            bignum_idivider(copy, &NUMS[10], remainder);
            buffer[len++] = remainder->data[0];
            if(len >= cap) {
                cap *= 2;
                buffer = realloc(buffer, cap * sizeof(char));
            }
        }
        for(i = len - 1; i >= 0; i--) printf("%d", buffer[i]);
    }
    bignum_deinit(copy);
    bignum_deinit(remainder);
    free(buffer);
}
 
/**
 * Check if two bignums are equal.
 */
int bignum_equal(bignum* b1, bignum* b2) {
    int i;
    if(bignum_iszero(b1) && bignum_iszero(b2)) return 1;
    else if(bignum_iszero(b1)) return 0;
    else if(bignum_iszero(b2)) return 0;
    else if(b1->length != b2->length) return 0;
    for(i = b1->length - 1; i >= 0; i--) {
        if(b1->data[i] != b2->data[i]) return 0;
    }
    return 1;
}
 
/**
 * Check if bignum b1 is greater than b2
 */
int bignum_greater(bignum* b1, bignum* b2) {
    int i;
    if(bignum_iszero(b1) && bignum_iszero(b2)) return 0;
    else if(bignum_iszero(b1)) return 0;
    else if(bignum_iszero(b2)) return 1;
    else if(b1->length != b2->length) return b1->length > b2->length;
    for(i = b1->length - 1; i >= 0; i--) {
        if(b1->data[i] != b2->data[i]) return b1->data[i] > b2->data[i];
    }
    return 0;
}
 
/**
 * Check if bignum b1 is less than b2
 */
int bignum_less(bignum* b1, bignum* b2) {
    int i;
    if(bignum_iszero(b1) && bignum_iszero(b2)) return 0;
    else if(bignum_iszero(b1)) return 1;
    else if(bignum_iszero(b2)) return 0;
    else if(b1->length != b2->length) return b1->length < b2->length;
    for(i = b1->length - 1; i >= 0; i--) {
        if(b1->data[i] != b2->data[i]) return b1->data[i] < b2->data[i];
    }
    return 0;
}
 
/**
 * Check if bignum b1 is greater than or equal to b2
 */
int bignum_geq(bignum* b1, bignum* b2) {
    return !bignum_less(b1, b2);
}
 
/**
 * Check if bignum b1 is less than or equal to b2
 */
int bignum_leq(bignum* b1, bignum* b2) {
    return !bignum_greater(b1, b2);
}
 
/**
 * Perform an in place add into the source bignum. That is source += add
 */
void bignum_iadd(bignum* source, bignum* add) {
    bignum* temp = bignum_init();
    bignum_add(temp, source, add);
    bignum_copy(temp, source);
    bignum_deinit(temp);
}
 
/**
 * Add two bignums by the add with carry method. result = b1 + b2
 */
void bignum_add(bignum* result, bignum* b1, bignum* b2) {
    word sum, carry = 0;
    int i, n = MAX(b1->length, b2->length);
    if(n + 1 > result->capacity) {
        result->capacity = n + 1;
        result->data = realloc(result->data, result->capacity * sizeof(word));
    }
    for(i = 0; i < n; i++) {
        sum = carry;
        if(i < b1->length) sum += b1->data[i];
        if(i < b2->length) sum += b2->data[i];
        result->data[i] = sum; /* Already taken mod 2^32 by unsigned wrap around */
 
        if(i < b1->length) {
            if(sum < b1->data[i]) carry = 1; /* Result must have wrapped 2^32 so carry bit is 1 */
            else carry = 0;
        }
        else {
            if(sum < b2->data[i]) carry = 1; /* Result must have wrapped 2^32 so carry bit is 1 */
            else carry = 0;
        }
    }
    if(carry == 1) {
        result->length = n + 1;
        result->data[n] = 1;
    }
    else {
        result->length = n;
    }
}
 
/**
 * Perform an in place subtract from the source bignum. That is, source -= sub
 */
void bignum_isubtract(bignum* source, bignum* sub) {
    bignum* temp = bignum_init();
    bignum_subtract(temp, source, sub);
    bignum_copy(temp, source);
    bignum_deinit(temp);
}
 
/**
 * Subtract bignum b2 from b1. result = b1 - b2. The result is undefined if b2 > b1.
 * This uses the basic subtract with carry method
 */
void bignum_subtract(bignum* result, bignum* b1, bignum* b2) {
    int length = 0, i;
    word carry = 0, diff, temp;
    if(b1->length > result->capacity) {
        result->capacity = b1->length;
        result->data = realloc(result->data, result->capacity * sizeof(word));
    }
    for(i = 0; i < b1->length; i++) {
        temp = carry;
        if(i < b2->length) temp = temp + b2->data[i]; /* Auto wrapped mod RADIX */
        diff = b1->data[i] - temp;
        if(temp > b1->data[i]) carry = 1;
        else carry = 0;
        result->data[i] = diff;
        if(result->data[i] != 0) length = i + 1;
    }
    result->length = length;
}
 
/**
 * Perform an in place multiplication into the source bignum. That is source *= mult
 */
void bignum_imultiply(bignum* source, bignum* mult) {
    bignum* temp = bignum_init();
    bignum_multiply(temp, source, mult);
    bignum_copy(temp, source);
    bignum_deinit(temp);
}
 
/**
 * Multiply two bignums by the naive school method. result = b1 * b2. I have experimented
 * with FFT mult and Karatsuba but neither was looking to be  more efficient than the school
 * method for reasonable number of digits. There are some improvments to be made here,
 * especially for squaring which can cut out half of the operations.
 */
void bignum_multiply(bignum* result, bignum* b1, bignum* b2) {
    int i, j, k;
    word carry, temp;
    unsigned long long int prod; /* Long for intermediate product... this is not portable and should probably be changed */
    if(b1->length + b2->length > result->capacity) {
        result->capacity = b1->length + b2->length;
        result->data = realloc(result->data, result->capacity * sizeof(word));
    }
    for(i = 0; i < b1->length + b2->length; i++) result->data[i] = 0;
 
    for(i = 0; i < b1->length; i++) {
        for(j = 0; j < b2->length; j++) {
            prod = (b1->data[i] * (unsigned long long int)b2->data[j]) + (unsigned long long int)(result->data[i+j]); /* This should not overflow... */
            carry = (word)(prod / RADIX);
 
            /* Add carry to the next word over, but this may cause further overflow.. propogate */
            k = 1;
            while(carry > 0) {
                temp = result->data[i+j+k] + carry;
                if(temp < result->data[i+j+k]) carry = 1;
                else carry = 0;
                result->data[i+j+k] = temp; /* Already wrapped in unsigned arithmetic */
                k++;
            }
 
            prod = (result->data[i+j] + b1->data[i] * (unsigned long long int)b2->data[j]) % RADIX; /* Again, should not overflow... */
            result->data[i+j] = prod; /* Add */
        }
    }
    if(b1->length + b2->length > 0 && result->data[b1->length + b2->length - 1] == 0) result->length = b1->length + b2->length - 1;
    else result->length = b1->length + b2->length;
}
 
/**
 * Perform an in place divide of source. source = source/div.
 */
void bignum_idivide(bignum *source, bignum *div) {
    bignum *q = bignum_init(), *r = bignum_init();
    bignum_divide(q, r, source, div);
    bignum_copy(q, source);
    bignum_deinit(q);
    bignum_deinit(r);
}
 
/**
 * Perform an in place divide of source, also producing a remainder.
 * source = source/div and remainder = source - source/div.
 */
void bignum_idivider(bignum* source, bignum* div, bignum* remainder) {
    bignum *q = bignum_init(), *r = bignum_init();
    bignum_divide(q, r, source, div);
    bignum_copy(q, source);
    bignum_copy(r, remainder);
    bignum_deinit(q);
    bignum_deinit(r);
}
 
/**
 * Calculate the remainder when source is divided by div.
 */
void bignum_remainder(bignum* source, bignum *div, bignum* remainder) {
    bignum *q = bignum_init();
    bignum_divide(q, remainder, source, div);
    bignum_deinit(q);
}
 
/**
 * Modulate the source by the modulus. source = source % modulus
 */
void bignum_imodulate(bignum* source, bignum* modulus) {
    bignum *q = bignum_init(), *r = bignum_init();
    bignum_divide(q, r, source, modulus);
    bignum_copy(r, source);
    bignum_deinit(q);
    bignum_deinit(r);
}
 
/**
 * Divide two bignums by naive long division, producing both a quotient and remainder.
 * quotient = floor(b1/b2), remainder = b1 - quotient * b2. If b1 < b2 the quotient is
 * trivially 0 and remainder is b2.
 */
void bignum_divide(bignum* quotient, bignum* remainder, bignum* b1, bignum* b2) {
    bignum *b2copy = bignum_init(), *b1copy = bignum_init();
    bignum *temp = bignum_init(), *temp2 = bignum_init(), *temp3 = bignum_init();
    bignum* quottemp = bignum_init();
    word carry = 0;
    int n, m, i, j, length = 0;
    unsigned long long factor = 1;
    unsigned long long gquot, gtemp, grem;
    if(bignum_less(b1, b2)) { /* Trivial case, b1/b2 = 0 iff b1 < b2. */
        quotient->length = 0;
        bignum_copy(b1, remainder);
    }
    else if(bignum_iszero(b1)) { /* 0/x = 0.. assuming b2 is nonzero */
        quotient->length = 0;
        bignum_fromint(remainder, 0);
    }
    else if(b2->length == 1) { /* Division by a single limb means we can do simple division */
        if(quotient->capacity < b1->length) {
            quotient->capacity = b1->length;
            quotient->data = realloc(quotient->data, quotient->capacity * sizeof(word));
        }
        for(i = b1->length - 1; i >= 0; i--) {
            gtemp = carry * RADIX + b1->data[i];
            gquot = gtemp / b2->data[0];
            quotient->data[i] = gquot;
            if(quotient->data[i] != 0 && length == 0) length = i + 1;
            carry = gtemp % b2->data[0];
        }
        bignum_fromint(remainder, carry);
        quotient->length = length;
    }
    else { /* Long division is neccessary */
        n = b1->length + 1;
        m = b2->length;
        if(quotient->capacity < n - m) {
            quotient->capacity = n - m;
            quotient->data = realloc(quotient->data, (n - m) * sizeof(word));
        }
        bignum_copy(b1, b1copy);
        bignum_copy(b2, b2copy);
        /* Normalize.. multiply by the divisor by 2 until MSB >= HALFRADIX. This ensures fast
         * convergence when guessing the quotient below. We also multiply the dividend by the
         * same amount to ensure the result does not change. */
        while(b2copy->data[b2copy->length - 1] < HALFRADIX) {
            factor *= 2;
            bignum_imultiply(b2copy, &NUMS[2]);
        }
        if(factor > 1) {
            bignum_fromint(temp, factor);
            bignum_imultiply(b1copy, temp);
        }
        /* Ensure the dividend is longer than the original (pre-normalized) divisor. If it is not
         * we introduce a dummy zero word to artificially inflate it. */
        if(b1copy->length != n) {
            b1copy->length++;
            if(b1copy->length > b1copy->capacity) {
                b1copy->capacity = b1copy->length;
                b1copy->data = realloc(b1copy->data, b1copy->capacity * sizeof(word));
            }
            b1copy->data[n - 1] = 0;
        }
 
        /* Process quotient by long division */
        for(i = n - m - 1; i >= 0; i--) {
            gtemp = RADIX * b1copy->data[i + m] + b1copy->data[i + m - 1];
            gquot = gtemp / b2copy->data[m - 1];
            if(gquot >= RADIX) gquot = UINT_MAX;
            grem = gtemp % b2copy->data[m - 1];
            while(grem < RADIX && gquot * b2copy->data[m - 2] > RADIX * grem + b1copy->data[i + m - 2]) { /* Should not overflow... ? */
                gquot--;
                grem += b2copy->data[m - 1];
            }
            quottemp->data[0] = gquot % RADIX;
            quottemp->data[1] = (gquot / RADIX);
            if(quottemp->data[1] != 0) quottemp->length = 2;
            else quottemp->length = 1;
            bignum_multiply(temp2, b2copy, quottemp);
            if(m + 1 > temp3->capacity) {
                temp3->capacity = m + 1;
                temp3->data = realloc(temp3->data, temp3->capacity * sizeof(word));
            }
            temp3->length = 0;
            for(j = 0; j <= m; j++) {
                temp3->data[j] = b1copy->data[i + j];
                if(temp3->data[j] != 0) temp3->length = j + 1;
            }
            if(bignum_less(temp3, temp2)) {
                bignum_iadd(temp3, b2copy);
                gquot--;
            }
            bignum_isubtract(temp3, temp2);
            for(j = 0; j < temp3->length; j++) b1copy->data[i + j] = temp3->data[j];
            for(j = temp3->length; j <= m; j++) b1copy->data[i + j] = 0;
            quotient->data[i] = gquot;
            if(quotient->data[i] != 0) quotient->length = i;
        }
 
        if(quotient->data[b1->length - b2->length] == 0) quotient->length = b1->length - b2->length;
        else quotient->length = b1->length - b2->length + 1;
 
        /* Divide by factor now to find final remainder */
        carry = 0;
        for(i = b1copy->length - 1; i >= 0; i--) {
            gtemp = carry * RADIX + b1copy->data[i];
            b1copy->data[i] = gtemp/factor;
            if(b1copy->data[i] != 0 && length == 0) length = i + 1;
            carry = gtemp % factor;
        }
        b1copy->length = length;
        bignum_copy(b1copy, remainder);
    }
    bignum_deinit(temp);
    bignum_deinit(temp2);
    bignum_deinit(temp3);
    bignum_deinit(b1copy);
    bignum_deinit(b2copy);
    bignum_deinit(quottemp);
}
 
/**
 * Perform modular exponentiation by repeated squaring. This will compute
 * result = base^exponent mod modulus
 */
void bignum_modpow(bignum* base, bignum* exponent, bignum* modulus, bignum* result) {
    bignum *a = bignum_init(), *b = bignum_init(), *c = bignum_init();
    bignum *discard = bignum_init(), *remainder = bignum_init();
    bignum_copy(base, a);
    bignum_copy(exponent, b);
    bignum_copy(modulus, c);
    bignum_fromint(result, 1);
    while(bignum_greater(b, &NUMS[0])) {
        if(b->data[0] & 1) {
            bignum_imultiply(result, a);
            bignum_imodulate(result, c);
        }
        bignum_idivide(b, &NUMS[2]);
        bignum_copy(a, discard);
        bignum_imultiply(a, discard);
        bignum_imodulate(a, c);
    }
    bignum_deinit(a);
    bignum_deinit(b);
    bignum_deinit(c);
    bignum_deinit(discard);
    bignum_deinit(remainder);
}
 
/**
 * Compute the gcd of two bignums. result = gcd(b1, b2)
 */
void bignum_gcd(bignum* b1, bignum* b2, bignum* result) {
    bignum *a = bignum_init(), *b = bignum_init(), *remainder = bignum_init();
    bignum *temp = bignum_init(), *discard = bignum_init();
    bignum_copy(b1, a);
    bignum_copy(b2, b);
    while(!bignum_equal(b, &NUMS[0])) {
        bignum_copy(b, temp);
        bignum_imodulate(a, b);
        bignum_copy(a, b);
        bignum_copy(temp, a);
    }
    bignum_copy(a, result);
    bignum_deinit(a);
    bignum_deinit(b);
    bignum_deinit(remainder);
    bignum_deinit(temp);
    bignum_deinit(discard);
}
 
/**
 * Compute the inverse of a mod m. Or, result = a^-1 mod m.
 */
void bignum_inverse(bignum* a, bignum* m, bignum* result) {
    bignum *remprev = bignum_init(), *rem = bignum_init();
    bignum *auxprev = bignum_init(), *aux = bignum_init();
    bignum *rcur = bignum_init(), *qcur = bignum_init(), *acur = bignum_init();
 
    bignum_copy(m, remprev);
    bignum_copy(a, rem);
    bignum_fromint(auxprev, 0);
    bignum_fromint(aux, 1);
    while(bignum_greater(rem, &NUMS[1])) {
        bignum_divide(qcur, rcur, remprev, rem);
        /* Observe we are finding the inverse in a finite field so we can use
         * a modified algorithm that avoids negative numbers here */
        bignum_subtract(acur, m, qcur);
        bignum_imultiply(acur, aux);
        bignum_iadd(acur, auxprev);
        bignum_imodulate(acur, m);
 
        bignum_copy(rem, remprev);
        bignum_copy(aux, auxprev);
        bignum_copy(rcur, rem);
        bignum_copy(acur, aux);
    }
 
    bignum_copy(acur, result);
 
    bignum_deinit(remprev);
    bignum_deinit(rem);
    bignum_deinit(auxprev);
    bignum_deinit(aux);
    bignum_deinit(rcur);
    bignum_deinit(qcur);
    bignum_deinit(acur);
}
 
/**
 * Compute the jacobi symbol, J(ac, nc).
 */
int bignum_jacobi(bignum* ac, bignum* nc) {
    bignum *remainder = bignum_init(), *twos = bignum_init();
    bignum *temp = bignum_init(), *a = bignum_init(), *n = bignum_init();
    int mult = 1, result = 0;
    bignum_copy(ac, a);
    bignum_copy(nc, n);
    while(bignum_greater(a, &NUMS[1]) && !bignum_equal(a, n)) {
        bignum_imodulate(a, n);
        if(bignum_leq(a, &NUMS[1]) || bignum_equal(a, n)) break;
        bignum_fromint(twos, 0);
        /* Factor out multiples of two */
        while(a->data[0] % 2 == 0) {
            bignum_iadd(twos, &NUMS[1]);
            bignum_idivide(a, &NUMS[2]);
        }
        /* Coefficient for flipping */
        if(bignum_greater(twos, &NUMS[0]) && twos->data[0] % 2 == 1) {
            bignum_remainder(n, &NUMS[8], remainder);
            if(!bignum_equal(remainder, &NUMS[1]) && !bignum_equal(remainder, &NUMS[7])) {
                mult *= -1;
            }
        }
        if(bignum_leq(a, &NUMS[1]) || bignum_equal(a, n)) break;
        bignum_remainder(n, &NUMS[4], remainder);
        bignum_remainder(a, &NUMS[4], temp);
        if(!bignum_equal(remainder, &NUMS[1]) && !bignum_equal(temp, &NUMS[1])) mult *= -1;
        bignum_copy(a, temp);
        bignum_copy(n, a);
        bignum_copy(temp, n);
    }
    if(bignum_equal(a, &NUMS[1])) result = mult;
    else result = 0;
    bignum_deinit(remainder);
    bignum_deinit(twos);
    bignum_deinit(temp);
    bignum_deinit(a);
    bignum_deinit(n);
    return result;
}
 
/**
 * Check whether a is a Euler witness for n. That is, if a^(n - 1)/2 != Ja(a, n) mod n
 */
int solovayPrime(int a, bignum* n) {
    bignum *ab = bignum_init(), *res = bignum_init(), *pow = bignum_init();
    bignum *modpow = bignum_init();
    int x, result;
 
    bignum_fromint(ab, a);
    x = bignum_jacobi(ab, n);
    if(x == -1) bignum_subtract(res, n, &NUMS[1]);
    else bignum_fromint(res, x);
    bignum_copy(n, pow);
    bignum_isubtract(pow, &NUMS[1]);
    bignum_idivide(pow, &NUMS[2]);
    bignum_modpow(ab, pow, n, modpow);
 
    result = !bignum_equal(res, &NUMS[0]) && bignum_equal(modpow, res);
    bignum_deinit(ab);
    bignum_deinit(res);
    bignum_deinit(pow);
    bignum_deinit(modpow);
    return result;
}
 
/**
 * Test if n is probably prime, by repeatedly using the Solovay-Strassen primality test.
 */
int probablePrime(bignum* n, int k) {
    if(bignum_equal(n, &NUMS[2])) return 1;
    else if(n->data[0] % 2 == 0 || bignum_equal(n, &NUMS[1])) return 0;
    while(k-- > 0) {
        if(n->length <= 1) { /* Prevent a > n */
            if(!solovayPrime(rand() % (n->data[0] - 2) + 2, n)) return 0;
        }
        else {
            int wit = rand() % (RAND_MAX - 2) + 2;
            if(!solovayPrime(wit, n)) return 0;
        }
    }
    return 1;
}
 
/**
 * Generate a random prime number, with a specified number of digits.
 * This will generate a base 10 digit string of given length, convert it
 * to a bignum and then do an increasing search for the first probable prime.
 */
void randPrime(int numDigits, bignum* result) {
    char *string = malloc((numDigits + 1) * sizeof(char));
    int i;
    string[0] = (rand() % 9) + '1'; /* No leading zeros */
    string[numDigits - 1] = (rand() % 5) * 2 + '1'; /* Last digit is odd */
    for(i = 1; i < numDigits - 1; i++) string[i] = (rand() % 10) + '0';
    string[numDigits] = '\0';
    bignum_fromstring(result, string);
    while(1) {
        if(probablePrime(result, ACCURACY)) {
            free(string);
            return;
        }
        bignum_iadd(result, &NUMS[2]); /* result += 2 */
    }
}
 
/**
 * Choose a random public key exponent for the RSA algorithm. The exponent will
 * be less than the modulus, n, and coprime to phi.
 */
void randExponent(bignum* phi, int n, bignum* result) {
    bignum* gcd = bignum_init();
    int e = rand() % n;
    while(1) {
        bignum_fromint(result, e);
        bignum_gcd(result, phi, gcd);
        if(bignum_equal(gcd, &NUMS[1])) {
            bignum_deinit(gcd);
            return;
        }
        e = (e + 1) % n;
        if(e <= 2) e = 3;
    }
}
 
/**
 * Read the file fd into an array of bytes ready for encryption.
 * The array will be padded with zeros until it divides the number of
 * bytes encrypted per block. Returns the number of bytes read.
 */
int readFile(FILE* fd, char** buffer, int bytes) {
    int len = 0, cap = BUF_SIZE, r;
    char buf[BUF_SIZE];
    *buffer = malloc(BUF_SIZE * sizeof(char));
    while((r = fread(buf, sizeof(char), BUF_SIZE, fd)) > 0) {
        if(len + r >= cap) {
            cap *= 2;
            *buffer = realloc(*buffer, cap);
        }
        memcpy(&(*buffer)[len], buf, r);
        len += r;
    }
    /* Pad the last block with zeros to signal end of cryptogram. An additional block is added if there is no room */
    if(len + bytes - len % bytes > cap) *buffer = realloc(*buffer, len + bytes - len % bytes);
    do {
        (*buffer)[len] = '\0';
        len++;
    }
    while(len % bytes != 0);
    return len;
}
 
/**
 * Encode the message m using public exponent and modulus, result = m^e mod n
 */
void encode(bignum* m, bignum* e, bignum* n, bignum* result) {
    bignum_modpow(m, e, n, result);//result=m^e mod n
}
 
/**
 * Decode cryptogram c using private exponent and public modulus, result = c^d mod n
 */
void decode(bignum* c, bignum* d, bignum* n, bignum* result) {
    bignum_modpow(c, d, n, result);//result=c^d mod n
}
 
/**
 * Encode the message of given length, using the public key (exponent, modulus)
 * The resulting array will be of size len/bytes, each index being the encryption
 * of "bytes" consecutive characters, given by m = (m1 + m2*128 + m3*128^2 + ..),
 * encoded = m^exponent mod modulus
 */
bignum *encodeMessage(int len, int bytes, char *message, bignum *exponent, bignum *modulus) {
    /* Calloc works here because capacity = 0 forces a realloc by callees but we should really
     * bignum_init() all of these */
    int i, j;
    bignum *encoded = calloc(len/bytes, sizeof(bignum));
    bignum *num128 = bignum_init(), *num128pow = bignum_init();
    bignum *x = bignum_init(), *current = bignum_init();
    bignum_fromint(num128, 128);
    bignum_fromint(num128pow, 1);
    for(i = 0; i < len; i += bytes) {
        bignum_fromint(x, 0);
        bignum_fromint(num128pow, 1);
        /* Compute buffer[0] + buffer[1]*128 + buffer[2]*128^2 etc (base 128 representation for characters->int encoding)*/
        for(j = 0; j < bytes; j++) {
            bignum_fromint(current, message[i + j]);
            bignum_imultiply(current, num128pow);
            bignum_iadd(x, current); /*x += buffer[i + j] * (1 << (7 * j)) */
            bignum_imultiply(num128pow, num128);
        }
        encode(x, exponent, modulus, &encoded[i/bytes]);
#ifndef NOPRINT
        bignum_print(&encoded[i/bytes]);
        printf(" ");
#endif
    }
    return encoded;
}
 
/**
 * Decode the cryptogram of given length, using the private key (exponent, modulus)
 * Each encrypted packet should represent "bytes" characters as per encodeMessage.
 * The returned message will be of size len * bytes.
 */
int *decodeMessage(int len, int bytes, bignum *cryptogram, bignum *exponent, bignum *modulus) {
    int *decoded = malloc(len * bytes * sizeof(int));
    int i, j;
    bignum *x = bignum_init(), *remainder = bignum_init();
    bignum *num128 = bignum_init();
    bignum_fromint(num128, 128);
    for(i = 0; i < len; i++) {
        decode(&cryptogram[i], exponent, modulus, x);
        for(j = 0; j < bytes; j++) {
            bignum_idivider(x, num128, remainder);
            if(remainder->length == 0) decoded[i*bytes + j] = (char)0;
            else decoded[i*bytes + j] = (char)(remainder->data[0]);
#ifndef NOPRINT
            printf("%c", (char)(decoded[i*bytes + j]));
#endif
        }
    }
    return decoded;
}
 
/**
 * Main method to demostrate the system. Sets up primes p, q, and proceeds to encode and
 * decode the message given in "text.txt"
 */
int main(void) {
    int i, bytes, len;
    bignum *p = bignum_init(), *q = bignum_init(), *n = bignum_init();
    bignum *phi = bignum_init(), *e = bignum_init(), *d = bignum_init();
    bignum *bbytes = bignum_init(), *shift = bignum_init();
    bignum *temp1 = bignum_init(), *temp2 = bignum_init();
 
    bignum *encoded;
    int *decoded;
    char data[]="hello rsa";
    int data_len = strlen(data);
    char *buffer;
 
    srand(time(NULL));
    printf ("Press any key to create p:\n");
    getchar();
    printf("begin to create...\n");
    randPrime(FACTOR_DIGITS, p); ///生产第一个大素数p
    printf("Got first prime factor, p = ");
    bignum_print(p);
    printf("\n\n");
    //getchar();
 
    printf ("Press any key to create q:\n");
    getchar();
    printf("begin to create...\n");
    randPrime(FACTOR_DIGITS, q); ///生产第二个大素数q
    printf("Got second prime factor, q = ");
    bignum_print(q);
    printf("\n\n");
 
    printf ("Press any key to create n=p*q:\n");
    getchar();
    bignum_multiply(n, p, q);
    printf("Got modulus, n = pq = ");
    bignum_print(n);
    printf("\n\n");
 
    printf ("Press any key to create phi=(p-1)*(q-1):\n");
    getchar();
    bignum_subtract(temp1, p, &NUMS[1]); ///temp1=p-1
    bignum_subtract(temp2, q, &NUMS[1]); ///temp2=q-1
    bignum_multiply(phi, temp1, temp2); /* phi = (p - 1) * (q - 1) */
    printf("Got totient, (p-1)*(q-1),phi = ");
    bignum_print(phi);
    printf("\n\n");
 
    printf ("Press any key to create e1:\n");
    getchar();
    randExponent(phi, EXPONENT_MAX, e);
    printf("Chose public exponent, e1 = ");
    bignum_print(e);
 
    printf("\n\nPublic key(e1,n) is (");
    bignum_print(e);
    printf(", ");
    bignum_print(n);
    printf(") ");
    printf("\n\n");
 
    printf ("Press any key to create e2:\n");
    getchar();
    bignum_inverse(e, phi, d);
    printf("Calculated private exponent, e2 = ");
    bignum_print(d);
    printf("\n\nPrivate key(e2,n) is (");
    bignum_print(d);
    printf(", ");
    bignum_print(n);
    printf(")");
    printf("\n\n");
 
    /* Compute maximum number of bytes that can be encoded in one encryption */
    /// 根据n计算出一次能加密的数据长度，bytes
    bytes = -1;
    bignum_fromint(shift, 1 << 7); /* 7 bits per char */
    bignum_fromint(bbytes, 1);
    while(bignum_less(bbytes, n)) {
        bignum_imultiply(bbytes, shift); /* Shift by one byte, NB: we use bitmask representative so this can actually be a shift... */
        bytes++;
    }
 
    printf("maximum number of bytes encoded in one encryption:%d\n\n",bytes);
 
    /// 加密长度len必须是bytes的整数倍，不够则补齐
    len = data_len+bytes-data_len%bytes;
 
    buffer=(char *)malloc(len);
    if(buffer==NULL)
        return -1;
    memset(buffer,0,len);
    memcpy(buffer,data,data_len);
 
    /// 最终要加密的数据是：buffer,len
 
    printf ("Press any key to encode:%s\n",buffer);
    getchar();
    printf("\nEncoding finished successfully and the result is:\n");
    //buffer存放着明文数据
    //len是buffer的长度，必须是bytes的整数倍
    //bytes是RSA算法一次能加密的宽度
    //(e,n)就是公钥
    //encoded就是密文存放的内存
    encoded = encodeMessage(len, bytes, buffer, e, n);
 
    printf("\n\n");
 
    printf ("Press any key to decode:\n");
    getchar();
    printf("Decode result:\n");
 
    //encoded:密文
    //bytes:一次能解密的宽度
    //len/bytes：就是解密的次数
    //(d,n)：私钥
    //decode:存放明文
    decoded = decodeMessage(len/bytes, bytes, encoded, d, n);
    printf("\nFinished RSA demonstration!\n");
 
    /* Eek! This is why we shouldn't of calloc'd those! */
    for(i = 0; i < len/bytes; i++) free(encoded[i].data);
    free(encoded);
    free(decoded);
    free(buffer);
    bignum_deinit(p);
    bignum_deinit(q);
    bignum_deinit(n);
    bignum_deinit(phi);
    bignum_deinit(e);
    bignum_deinit(d);
    bignum_deinit(bbytes);
    bignum_deinit(shift);
    bignum_deinit(temp1);
    bignum_deinit(temp2);
 
    return EXIT_SUCCESS;
}

5. 基于OpenSSL库的RSA和ASE算法

  • OpenSSL (Open Secure Sockets Layer安全套接层）是一个安全套接字层密码库，囊括主要的密码算法、常用的密钥和证书封装管理功能及SSL协议，并提供丰富的应用程序供测试或其它目的使用。
  • 由加拿大人Eric A. Young和Tim J.Hudson自1995年开始编写。并产生巨大影响，这是一个没有太多限制的开放源代码的软件包。1998年，OpenSSL项目组接管了OpensSL的开发工作。
  • OpenSSL包含一个命令行工具用来完成OpenSSL库中的所有功能。Apache使用它加密'HTTP, OpensSH使用它加密SSH,但是，你不应该只将其作为一个库来使用，它还是一个多用途的、跨平台的密码工具。
  • OpenSSL采用C语言作为开发语言，这使得OpenSSL具有优秀的跨平台性能。OpenSSL整个软件包大概可以分成三个主要的功能部分:SSL协议库、应用程序以及密码算法库。
  • OpenssL一共提供了8种对称加密算法，其中7种是分组加密算法，仅有的一种流加密算法是RC4。这7种分组加密算法分别是AES、DES、Blowfish、CAST、IDEA、RC2、MRC5。OpenSSL一共实现了4种非对称加密算法，包括DH算法、RSA算法、DSA算法和椭圆曲线算法(EC)
  • OpenSSL曾曝出严重的“心脏流血"漏洞。

    编译和使用OpenSSL加解密的方法

    准备环境
    1) 下载并解压openssl源代码
    https://www.openssl.org/source/openssl-1.0.2l.tar.gz
    2) 下载并安装ActivePerl
    http://downloads.activestate.com/ActivePerl/releases/5.20.2.2002/ActivePerl-5.20.2.2002-MSWin32-x86-64int-299195.msi
    并设置perl的安装路径到环境变量Path中。
    3) 下载并安装nasm
    http://www.nasm.us/pub/nasm/releasebuilds/2.11.08/win32/nasm-2.11.08-installer.exe
    执行nasm安装目录下的 nasmpath.bat （这个文件用于设置nasm的环境变量，如果依然找不到nasm，那么也可以手动设置nasm安装路径到环境变量Path中）
    4) 打开任务栏开始菜单=>所有程序=>打开的VC命令行中切换到openssl解压出来的目录，如：cd E:\openssl-1.0.2d
    5) 输入 perl Configure VC-WIN32 回车执行
    6) 输入 ms\do_nasm.bat回车执行
    7) 输入 nmake -f ms\ntdll.mak -a 回车执行动态库编译（此为动态链接库，输出目录out32dll）
    8) 输入 nmake -f ms\nt.mak -a 回车执行静态库编译（此为静态链接库，输出目录out32）
    9) 运行out32目录中的openssl.exe命令生成公钥和私钥：
  • 生成密钥：openssl genrsa -out test.key 1024
  • 生成公钥：openssl rsa -in test.key -pubout -out test_pub.key
    使用openssl
    接下来，在VC项目中调用OpenSSL库中的接口：
    1) 设置OpenSSL的头文件目录：
    2) 设置OpenSSL的库文件目录：
    3) 设置OpenSSL的库文件名称：
    4) 在项目中包含OpenSSL的头文件：
1
2
3
4
#include "openssl/rsa.h"
#include "openssl/pem.h"
#include "openssl/err.h"
#include "openssl/applink.c"//防止：OPENSSL_Uplink(0098E000,07): no OPENSSL_Applink

然后就可以在项目中使用OpenSSL的接口来进行RSA,AES等加解密了

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
// openssl-rsa.cpp : Defines the entry point for the console application.
//
 
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include "openssl/rsa.h"
#include "openssl/pem.h"
#include "openssl/err.h"
#include "openssl/applink.c"//防止：OPENSSL_Uplink(0098E000,07): no OPENSSL_Applink
#define OPENSSLKEY "test.key"
#define PUBLICKEY "test_pub.key"
#define BUFFSIZE 1024
char *my_encrypt(char *str,char *path_key,char **out,int *size);//加密，size为密文长度
char* my_decrypt(char *str,char *path_key,char **out,int *size);//解密，size为明文长度
 
void print_encode(char *p,int size)
{
    printf("after encrypt:\n");
    for(int i=0;i<size;i++)
    {
        printf("%02x",p[i]);
 
    }
    printf("\n");
}
int main(void){
    char *source="hello openssl rsa";
    char *ptr_en,*ptr_de;
    int en_size=0;
    int de_size=0;
    printf("source is:%s\n",source);
    my_encrypt(source,PUBLICKEY,&ptr_en,&en_size);
    //printf("after encrypt:%s\n",ptr_en);
    print_encode(ptr_en,en_size);
    my_decrypt(ptr_en,OPENSSLKEY,&ptr_de,&de_size);
    printf("after decrypt:%s\n",ptr_de);
    if(ptr_en!=NULL){
        free(ptr_en);
    }  
    if(ptr_de!=NULL){
        free(ptr_de);
    }  
    return 0;
}
char *my_encrypt(char *str,char *path_key,char **out,int *size){
    char *p_en;
    RSA *p_rsa;
    FILE *file;
    int flen,rsa_len;
    if((file=fopen(path_key,"r"))==NULL){
        perror("open key file error");
        return NULL;   
    }  
    if((p_rsa=PEM_read_RSA_PUBKEY(file,NULL,NULL,NULL))==NULL){
        //if((p_rsa=PEM_read_RSAPublicKey(file,NULL,NULL,NULL))==NULL){   换成这句死活通不过，无论是否将公钥分离源文件
        ERR_print_errors_fp(stdout);
        return NULL;
    }  
    flen=strlen(str);
    rsa_len=RSA_size(p_rsa);
    p_en=(char *)malloc(rsa_len+1);
    memset(p_en,0,rsa_len+1);
    if(RSA_public_encrypt(rsa_len,(unsigned char *)str,(unsigned char*)p_en,p_rsa,RSA_NO_PADDING)<0){
        return NULL;
    }
    RSA_free(p_rsa);
    fclose(file);
    *out =p_en;
    *size=rsa_len;
    return p_en;
}
char *my_decrypt(char *str,char *path_key,char **out,int *size){
    char *p_de;
    RSA *p_rsa;
    FILE *file;
    int rsa_len;
    if((file=fopen(path_key,"r"))==NULL){
        perror("open key file error");
        return NULL;
    }
    if((p_rsa=PEM_read_RSAPrivateKey(file,NULL,NULL,NULL))==NULL){
        ERR_print_errors_fp(stdout);
        return NULL;
    }
    rsa_len=RSA_size(p_rsa);
    p_de=(char *)malloc(rsa_len+1);
    memset(p_de,0,rsa_len+1);
    if(RSA_private_decrypt(rsa_len,(unsigned char *)str,(unsigned char*)p_de,p_rsa,RSA_NO_PADDING)<0){
        return NULL;
    }
    RSA_free(p_rsa);
    fclose(file);
 
    *out = p_de;
    *size=rsa_len;
    return p_de;
}

6. 散列算法：MD5

  • MD5Message-Digest Algorithm 5(信息-摘要算法5)，用于确保信息传输完整一致。是计算机广泛使用的哈希算法，将数据运算为另一固定长度值，是哈希算法的基础原理，MD5的前身有MD2、 MD3和MD4。
  • MD5算法具有以下特点:
    • 1、压缩性：任意长度的数据，算出的MD5值长度都是固定的。
    • 2、容易计算：从原数据计算出MD5值很容易。
    • 3、抗修改性：对原数据进行任何改动，哪怕只修改1个字节，所得到的MD5值都有很大区别。
    • 4、强抗碰撞：己知原数据和其MD5值，想找到个具有相同MD5值的数据（即伪造数据)是非常困难的
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
// md5test.cpp : Defines the entry point for the console application.
//
 
#include "md5c.h"
#include <stdio.h>
#include <conio.h>
#include <tchar.h>
 
void printf_md5(unsigned char *str)
{
    int i=0;
    for(;i<16;i++)
    {
        printf("%02x",str[i]);
    }
    printf("\n");
}
int _tmain(int argc, _TCHAR* argv[])
{
    unsigned char digest[16];  //存放结果
    //第一种用法:
    MD5_CTX md5c;
    MD5Init(&md5c); //初始化
    MD5UpdaterString(&md5c,"1234");
    MD5FileUpdateFile(&md5c,"1.txt");//"56" saved in 1.txt
    MD5Final(digest,&md5c);
 
    printf_md5(digest);
 
    //第二种用法:
    MDString("123456",digest); //直接输入字符串并得出结果
    printf_md5(digest);
    //第三种用法:
    MD5File("2.txt",digest); //直接输入文件路径并得出结果,2.txtc存放着"123456"
    printf_md5(digest);
    getchar();
    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
/// md5.h
/* POINTER defines a generic pointer type */
typedef unsigned char * POINTER;
 
/* UINT2 defines a two byte word */
//typedef unsigned short int UINT2;
 
/* UINT4 defines a four byte word */
typedef unsigned long int UINT4;
 
 
/* MD5 context. */
typedef struct {
    UINT4 state[4];                                   /* state (ABCD) */
    UINT4 count[2];        /* number of bits, modulo 2^64 (lsb first) */
    unsigned char buffer[64];                         /* input buffer */
} MD5_CTX;
 
void MD5Init (MD5_CTX *context);
void MD5Update (MD5_CTX *context, unsigned char *input, unsigned int inputLen);
void MD5UpdaterString(MD5_CTX *context,const char *string);
int MD5FileUpdateFile (MD5_CTX *context,char *filename);
void MD5Final (unsigned char digest[16], MD5_CTX *context);
void MDString (char *string,unsigned char digest[16]);
int MD5File (char *filename,unsigned char digest[16]);
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
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
/// md5.c
/* MD5C.C - RSA Data Security, Inc., MD5 message-digest algorithm
 */
 
/* Copyright (C) 1991-2, RSA Data Security, Inc. Created 1991. All
rights reserved.
 
License to copy and use this software is granted provided that it
is identified as the "RSA Data Security, Inc. MD5 Message-Digest
Algorithm" in all material mentioning or referencing this software
or this function.
 
License is also granted to make and use derivative works provided
that such works are identified as "derived from the RSA Data
Security, Inc. MD5 Message-Digest Algorithm" in all material
mentioning or referencing the derived work.
 
RSA Data Security, Inc. makes no representations concerning either
the merchantability of this software or the suitability of this
software for any particular purpose. It is provided "as is"
without express or implied warranty of any kind.
 
These notices must be retained in any copies of any part of this
documentation and/or software.
 */
#include "md5c.h"
#include <string.h>
#include <stdio.h>
 
/* Constants for MD5Transform routine.
*/
 
 
#define S11 7
#define S12 12
#define S13 17
#define S14 22
#define S21 5
#define S22 9
#define S23 14
#define S24 20
#define S31 4
#define S32 11
#define S33 16
#define S34 23
#define S41 6
#define S42 10
#define S43 15
#define S44 21
 
static void MD5_memcpy (POINTER output, POINTER input, unsigned int len);
static void MD5Transform (UINT4 state[4], unsigned char block[64]);
static void Encode (unsigned char *output, UINT4 *input, unsigned int len);
static void MD5_memset (POINTER output, int value, unsigned int len);
static void Decode (UINT4 *output, unsigned char *input, unsigned int len);
 
static unsigned char PADDING[64] = {
    0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
};
 
/* F, G, H and I are basic MD5 functions.
*/
#define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
#define G(x, y, z) (((x) & (z)) | ((y) & (~z)))
#define H(x, y, z) ((x) ^ (y) ^ (z))
#define I(x, y, z) ((y) ^ ((x) | (~z)))
 
/* ROTATE_LEFT rotates x left n bits.
*/
#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))
 
/* FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4.
Rotation is separate from addition to prevent recomputation.
*/
#define FF(a, b, c, d, x, s, ac) { \
    (a) += F ((b), (c), (d)) + (x) + (UINT4)(ac); \
    (a) = ROTATE_LEFT ((a), (s)); \
    (a) += (b); \
    }
#define GG(a, b, c, d, x, s, ac) { \
    (a) += G ((b), (c), (d)) + (x) + (UINT4)(ac); \
    (a) = ROTATE_LEFT ((a), (s)); \
    (a) += (b); \
    }
#define HH(a, b, c, d, x, s, ac) { \
    (a) += H ((b), (c), (d)) + (x) + (UINT4)(ac); \
    (a) = ROTATE_LEFT ((a), (s)); \
    (a) += (b); \
    }
#define II(a, b, c, d, x, s, ac) { \
    (a) += I ((b), (c), (d)) + (x) + (UINT4)(ac); \
    (a) = ROTATE_LEFT ((a), (s)); \
    (a) += (b); \
    }
 
/* MD5 initialization. Begins an MD5 operation, writing a new context.
 */
void MD5Init (MD5_CTX *context)                                     /* context */
{
    context->count[0] = context->count[1] = 0;
    /* Load magic initialization constants.
    */
    context->state[0] = 0x67452301;
    context->state[1] = 0xefcdab89;
    context->state[2] = 0x98badcfe;
    context->state[3] = 0x10325476;
}
 
/* MD5 block update operation. Continues an MD5 message-digest
  operation, processing another message block, and updating the
  context.
 */
void MD5Update (MD5_CTX *context, unsigned char *input, unsigned int inputLen)
 
{
    unsigned int i, index, partLen;
 
    /* Compute number of bytes mod 64 */
    index = (unsigned int)((context->count[0] >> 3) & 0x3F);
 
    /* Update number of bits */
    if ((context->count[0] += ((UINT4)inputLen << 3))
        < ((UINT4)inputLen << 3))
        context->count[1]++;
    context->count[1] += ((UINT4)inputLen >> 29);
 
    partLen = 64 - index;
 
    /* Transform as many times as possible.
    */
    if (inputLen >= partLen) {
        MD5_memcpy((POINTER)&context->buffer[index], (POINTER)input, partLen);
        MD5Transform (context->state, context->buffer);
 
        for (i = partLen; i + 63 < inputLen; i += 64)
            MD5Transform (context->state, &input[i]);
 
        index = 0;
    }
    else
        i = 0;
 
    /* Buffer remaining input */
    MD5_memcpy((POINTER)&context->buffer[index], (POINTER)&input[i],inputLen-i);
}
 
/* MD5 finalization. Ends an MD5 message-digest operation, writing the
  the message digest and zeroizing the context.
 */
void MD5Final (unsigned char digest[16], MD5_CTX *context)                                
{
    unsigned char bits[8];
    unsigned int index, padLen;
 
    /* Save number of bits */
    Encode (bits, context->count, 8);
 
    /* Pad out to 56 mod 64.
    */
    index = (unsigned int)((context->count[0] >> 3) & 0x3f);
    padLen = (index < 56) ? (56 - index) : (120 - index);
    MD5Update (context, PADDING, padLen);
 
    /* Append length (before padding) */
    MD5Update (context, bits, 8);
 
    /* Store state in digest */
    Encode (digest, context->state, 16);
 
    /* Zeroize sensitive information.
    */
    MD5_memset ((POINTER)context, 0, sizeof (*context));
}
 
/* MD5 basic transformation. Transforms state based on block.
 */
static void MD5Transform (UINT4 state[4], unsigned char block[64])
{
    UINT4 a = state[0], b = state[1], c = state[2], d = state[3], x[16];
 
    Decode (x, block, 64);
 
    /* Round 1 */
    FF (a, b, c, d, x[ 0], S11, 0xd76aa478); /* 1 */
    FF (d, a, b, c, x[ 1], S12, 0xe8c7b756); /* 2 */
    FF (c, d, a, b, x[ 2], S13, 0x242070db); /* 3 */
    FF (b, c, d, a, x[ 3], S14, 0xc1bdceee); /* 4 */
    FF (a, b, c, d, x[ 4], S11, 0xf57c0faf); /* 5 */
    FF (d, a, b, c, x[ 5], S12, 0x4787c62a); /* 6 */
    FF (c, d, a, b, x[ 6], S13, 0xa8304613); /* 7 */
    FF (b, c, d, a, x[ 7], S14, 0xfd469501); /* 8 */
    FF (a, b, c, d, x[ 8], S11, 0x698098d8); /* 9 */
    FF (d, a, b, c, x[ 9], S12, 0x8b44f7af); /* 10 */
    FF (c, d, a, b, x[10], S13, 0xffff5bb1); /* 11 */
    FF (b, c, d, a, x[11], S14, 0x895cd7be); /* 12 */
    FF (a, b, c, d, x[12], S11, 0x6b901122); /* 13 */
    FF (d, a, b, c, x[13], S12, 0xfd987193); /* 14 */
    FF (c, d, a, b, x[14], S13, 0xa679438e); /* 15 */
    FF (b, c, d, a, x[15], S14, 0x49b40821); /* 16 */
 
    /* Round 2 */
    GG (a, b, c, d, x[ 1], S21, 0xf61e2562); /* 17 */
    GG (d, a, b, c, x[ 6], S22, 0xc040b340); /* 18 */
    GG (c, d, a, b, x[11], S23, 0x265e5a51); /* 19 */
    GG (b, c, d, a, x[ 0], S24, 0xe9b6c7aa); /* 20 */
    GG (a, b, c, d, x[ 5], S21, 0xd62f105d); /* 21 */
    GG (d, a, b, c, x[10], S22,  0x2441453); /* 22 */
    GG (c, d, a, b, x[15], S23, 0xd8a1e681); /* 23 */
    GG (b, c, d, a, x[ 4], S24, 0xe7d3fbc8); /* 24 */
    GG (a, b, c, d, x[ 9], S21, 0x21e1cde6); /* 25 */
    GG (d, a, b, c, x[14], S22, 0xc33707d6); /* 26 */
    GG (c, d, a, b, x[ 3], S23, 0xf4d50d87); /* 27 */
    GG (b, c, d, a, x[ 8], S24, 0x455a14ed); /* 28 */
    GG (a, b, c, d, x[13], S21, 0xa9e3e905); /* 29 */
    GG (d, a, b, c, x[ 2], S22, 0xfcefa3f8); /* 30 */
    GG (c, d, a, b, x[ 7], S23, 0x676f02d9); /* 31 */
    GG (b, c, d, a, x[12], S24, 0x8d2a4c8a); /* 32 */
 
    /* Round 3 */
    HH (a, b, c, d, x[ 5], S31, 0xfffa3942); /* 33 */
    HH (d, a, b, c, x[ 8], S32, 0x8771f681); /* 34 */
    HH (c, d, a, b, x[11], S33, 0x6d9d6122); /* 35 */
    HH (b, c, d, a, x[14], S34, 0xfde5380c); /* 36 */
    HH (a, b, c, d, x[ 1], S31, 0xa4beea44); /* 37 */
    HH (d, a, b, c, x[ 4], S32, 0x4bdecfa9); /* 38 */
    HH (c, d, a, b, x[ 7], S33, 0xf6bb4b60); /* 39 */
    HH (b, c, d, a, x[10], S34, 0xbebfbc70); /* 40 */
    HH (a, b, c, d, x[13], S31, 0x289b7ec6); /* 41 */
    HH (d, a, b, c, x[ 0], S32, 0xeaa127fa); /* 42 */
    HH (c, d, a, b, x[ 3], S33, 0xd4ef3085); /* 43 */
    HH (b, c, d, a, x[ 6], S34,  0x4881d05); /* 44 */
    HH (a, b, c, d, x[ 9], S31, 0xd9d4d039); /* 45 */
    HH (d, a, b, c, x[12], S32, 0xe6db99e5); /* 46 */
    HH (c, d, a, b, x[15], S33, 0x1fa27cf8); /* 47 */
    HH (b, c, d, a, x[ 2], S34, 0xc4ac5665); /* 48 */
 
    /* Round 4 */
    II (a, b, c, d, x[ 0], S41, 0xf4292244); /* 49 */
    II (d, a, b, c, x[ 7], S42, 0x432aff97); /* 50 */
    II (c, d, a, b, x[14], S43, 0xab9423a7); /* 51 */
    II (b, c, d, a, x[ 5], S44, 0xfc93a039); /* 52 */
    II (a, b, c, d, x[12], S41, 0x655b59c3); /* 53 */
    II (d, a, b, c, x[ 3], S42, 0x8f0ccc92); /* 54 */
    II (c, d, a, b, x[10], S43, 0xffeff47d); /* 55 */
    II (b, c, d, a, x[ 1], S44, 0x85845dd1); /* 56 */
    II (a, b, c, d, x[ 8], S41, 0x6fa87e4f); /* 57 */
    II (d, a, b, c, x[15], S42, 0xfe2ce6e0); /* 58 */
    II (c, d, a, b, x[ 6], S43, 0xa3014314); /* 59 */
    II (b, c, d, a, x[13], S44, 0x4e0811a1); /* 60 */
    II (a, b, c, d, x[ 4], S41, 0xf7537e82); /* 61 */
    II (d, a, b, c, x[11], S42, 0xbd3af235); /* 62 */
    II (c, d, a, b, x[ 2], S43, 0x2ad7d2bb); /* 63 */
    II (b, c, d, a, x[ 9], S44, 0xeb86d391); /* 64 */
 
    state[0] += a;
    state[1] += b;
    state[2] += c;
    state[3] += d;
 
    /* Zeroize sensitive information.
    */
    MD5_memset ((POINTER)x, 0, sizeof (x));
}
 
/* Encodes input (UINT4) into output (unsigned char). Assumes len is
  a multiple of 4.
 */
static void Encode (unsigned char *output, UINT4 *input, unsigned int len)
{
    unsigned int i, j;
 
    for (i = 0, j = 0; j < len; i++, j += 4) {
        output[j] = (unsigned char)(input[i] & 0xff);
        output[j+1] = (unsigned char)((input[i] >> 8) & 0xff);
        output[j+2] = (unsigned char)((input[i] >> 16) & 0xff);
        output[j+3] = (unsigned char)((input[i] >> 24) & 0xff);
    }
}
 
/* Decodes input (unsigned char) into output (UINT4). Assumes len is
  a multiple of 4.
 */
static void Decode (UINT4 *output, unsigned char *input, unsigned int len)
{
    unsigned int i, j;
 
    for (i = 0, j = 0; j < len; i++, j += 4)
        output[i] = ((UINT4)input[j]) | (((UINT4)input[j+1]) << 8) |
        (((UINT4)input[j+2]) << 16) | (((UINT4)input[j+3]) << 24);
}
 
/* Note: Replace "for loop" with standard memcpy if possible.
 */
 
static void MD5_memcpy (POINTER output, POINTER input, unsigned int len)
{
    unsigned int i;
 
    for (i = 0; i < len; i++)
        output[i] = input[i];
}
 
/* Note: Replace "for loop" with standard memset if possible.
 */
static void MD5_memset (POINTER output, int value, unsigned int len)
{
    unsigned int i;
 
    for (i = 0; i < len; i++)
        ((char *)output)[i] = (char)value;
}
/* Digests a string and prints the result.
 */
void MDString (char *string,unsigned char digest[16])
{
    MD5_CTX context;
    unsigned int len = strlen (string);
 
    MD5Init (&context);
    MD5Update (&context, (unsigned char *)string, len);
    MD5Final (digest, &context);
}
/* Digests a file and prints the result.
 */
int MD5File (char *filename,unsigned char digest[16])
{
    FILE *file;
    MD5_CTX context;
    int len;
    unsigned char buffer[1024];
    errno_t err;
    if ((err = fopen_s (&file,filename, "rb")) != 0)
        return -1;
    else {
        MD5Init (&context);
        while (len = fread (buffer, 1, 1024, file))
            MD5Update (&context, buffer, len);
        MD5Final (digest, &context);
 
        fclose (file);
    }
    return 0;
}
void MD5UpdaterString(MD5_CTX *context,const char *string)
{
    unsigned int len = strlen (string);
    MD5Update (context, (unsigned char *)string, len);
}
int MD5FileUpdateFile (MD5_CTX *context,char *filename)
{
    FILE *file;
    int len;
    unsigned char buffer[1024];
    errno_t err;
    if ((err = fopen_s (&file,filename, "rb")) != 0)
        return -1;
    else {
        while (len = fread (buffer, 1, 1024, file))
            MD5Update (context, buffer, len);
        fclose (file);
    }
    return 0;
}

三、应用

1. 数字签名防篡改

  • 计算文件的HASH值（比如MD5值）
  • 以私钥将HASH值加密，然后存储在文件中某个位置（比如头部或者尾部）
  • 使用的时候，通过公钥将文件中这个位置的加密数据解密得到HASH值,和文件当前的HASH值进行比对
  • 匹配，则文件未被修改;不匹配，文件已被修改

    2. 对称与非对称结合加解密

  • 对称加密:.快
  • 非对称加密:慢
  • 对称加密加密数据+非对称加密加密其密钥
    Aeskey_encrypt(data)+publickey_encrypt(aes_key)=发送=>privatekey_decrypt(aes_key)+Aeskey_decrypt(data)

[招生]科锐逆向工程师培训(2024年11月15日实地，远程教学同时开班, 第51期)

收藏
免费 ・9
支持
分享
最新回复 (2)
Halo。
雪    币： 0
活跃值： (884)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
2 楼
收藏了，最近正在学习加解密相关的，每次IDA认一个算法都很麻烦。感觉还是看得少了，充充电
2023-2-7 16:39
1
万里星河
雪    币： 116
活跃值： (1012)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
3 楼
支持一下
2023-2-28 20:19
0
游客
登录 | 注册 方可回帖
回帖 表情 雪币赚取及消费
高级回复
返回
//