密码学笔记4——SHA1实现

发表于 | 分类于 |

SHA1实现

明文填充

对输入的字符串进行填充，首先在明文后面接上一比特的1，然后再添加若干个0使得总长度模512同余448，最后再添加64比特，其数值表示的是明文的长度。

因为输入的都是字符串，一个字符8个bit，我们首先可以算得:明文的比特数=字符数*8。从而可以计算出需要填充的0的个数为(447-明文比特数)%512

sha1面向字进行操作，因此我们可以创建一个关于字的vector作为返回结果。首先对于字符串，每4个字符为一个字，先将它们push进vector。然后讨论字符串剩余1，2，3个字符的情况，分别在其后面添加一个比特1和若干比特0，使得长度为32比特，作为一个字push进vector。接着，计算剩下还要push多少个字的0，把它们push进vector。最后分两个字来push那个表示明文原长度的64比特即可。

F函数

F函数读取B，C，D以及t的值作为输入，并根据t的不同值对BCD进行不同的运算并返回运算结果。实现的时候B，C，D都是bitset<32>，因此可以直接进行相对应的位运算。

1
2
3
4
5
6
7
8
9
10
11
12
Word F_function(Word B, Word C, Word D,int t){
    Word res(0);
    if(t <= 19)
        res = (B&C)|((~B)&D);
    else if(t <= 39)
        res = B^C^D;
    else if(t <= 59)
        res = (B&C)|(B&D)|(C&D);
    else
        res = B^C^D;
    return res;
}

加密算法

由于bitset没有内置的模2^32加法的功能，因此实现了一个add函数用于作模2^32加法操作。

设置全局变量H0,H1,H2,H3,H4和K数组，数值按照书上给出的来。

首先，对明文进行填充，填充的结果是一个关于字的vector，记为Y。由于512bit为一组，也就是16个字，计算n=Y.size()/16。进行n次的for循环，在每次循环中做如下操作：

  1. 计算W数组
  2. 通过一系列运算，更新H0,H1,H2,H3,H4的值

书上给出了伪代码，实现成c++具体的操作如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
for(int i = 0; i < n; i++){
        vector<Word> W_array;
        for(int j = 0; j < 16; j++){
            W_array.push_back(Y[i*16+j]);
        }
        for(int t = 16; t < 80; t++){
            Word temp(0);
            temp = W_array[t-3]^W_array[t-8]^W_array[t-14]^W_array[t-16];
            temp = temp << 1 | temp >>(32-1);
            W_array.push_back(temp);
        }
        Word A = H0;
        Word B = H1;
        Word C = H2;
        Word D = H3;
        Word E = H4;
        for(int t = 0; t < 80; t++){
            Word temp = A << 5 | A >> (32-5);
            temp = add(temp,F_function(B,C,D,t));
            temp = add(temp,E);
            temp = add(temp,W_array[t]);
            temp = add(temp,K[t/20]);
            E = D;
            D = C;
            C = B << 30 | B >>(32-30);
            B = A;
            A = temp;
        }
        H0 = add(H0,A);
        H1 = add(H1,B);
        H2 = add(H2,C);
        H3 = add(H3,D);
        H4 = add(H4,E);
    }

循环进行完之后，输出H0||H1||H2||H3||H4的指即为所求得的哈希值

main函数

从plaintext.txt中读入内容，这里读入的最长为8192字节，即最大可读入8k的文件。将读入内容构造成字符串，传入加密函数中进行加密。