SecureHashAlgorithm

2022-03-17

字数统计: 7.8k字 | 阅读时长≈ 45分

复习SHA。很久以前实现过，没记笔记，现在又忘光了。

SecureHashAlgorithm

概要

关于

SHA-1
SHA-384
SHA-256
SHA-512

算法的规定与实现。

fips标准是几个混在一起讲的。

规范

参数名

$$
a,b,c,…h
$$

临时变量，是w比特位宽的，在计算哈希值H时使用。
$$
H^{(i)}
$$
第i个哈希值H。因为哈希计算需要多轮。H^{0}是初始哈希值。H^{N}是最终哈希值。
$$
H^{(i)}_{j}
$$
从左往右，一个哈希值H^{i}中第j个字。
$$
K_t
$$
用于t迭代的常量值。
$$
k
$$
padding时需要添加0的个数。
$$
l
$$
消息M的比特长度。
$$
m
$$
一个消息需要拆成若干定长消息块分别进行哈希。m为一个消息块的比特长度。
$$
M
$$
待哈希的消息。
$$
M^{(i)}
$$
第i个消息块。
$$
M^{(i)}_j
$$
第i个消息块中从左到右的第j个字。
$$
n
$$
出现于ROTL(x, n)等运算中，表示了要进行位移或旋转的比特个数。
$$
N
$$
消息需要拆成消息块，但是消息的长度不一定是消息块长度的整数倍。所以需要padding填充0。

N代表了填充后消息块的个数。
$$
T
$$
临时变量，w比特位宽的字。
$$
w
$$
一个字的比特个数。一般是32（SHA1，SHA256）或64（SHA384，SHA512）
$$
W_t
$$
消息队列（message schedule）中的第t个字。

比特串与整数

1	0b0000-0b1111 = 0x0-0xF = '0'-'F'

比如32位比特串

1	1010 0001 0000 0011 1111 1110 0010 0011

可以表示为

1	"a103fe23"

$$
0\le Z\lt 2^{64},Z=2^{32}X+Y
$$

64位长整型数Z可以表示为两个32位整数X与Y的拼接，即可记为一对(x, y)。此方法用于SHA1与SHA256。

同理，128位可以拆成2个64位。用于SHA384与SHA512。

位宽与消息块长度

SHA1与SHA256：消息块长m为512位，64字节；字长w为32位，4字节。
SHA384与SHA512：消息块长m为1024位，128字节；字长w为64位，8字节。

字上的操作

即以一个字为单元的运算。即一般C语言运算。

// 位宽32
#define AND &
#define XOR ^
#define OR |
#define ROTL(x,n) ((x<<n)|(x>>(32-n)))
#define ROTR(x,n) ROTL((x),(32-n))

SHA1

函数

3个函数Ch，Parity，Maj；由func_t函数封装。

// SHA-1函数
uint32_t Ch(uint32_t x, uint32_t y, uint32_t z){
    uint32_t t = (x & y) ^ (~x & z);
    //printf("t from Ch():%8x\n", t);
    return t;
}

uint32_t Parity(uint32_t x, uint32_t y, uint32_t z){
    return x ^ y ^ z;
}

uint32_t Maj(uint32_t x, uint32_t y, uint32_t z){
    return (x & y) ^ (x & z) ^ (y & z);
}

uint32_t func_t(uint32_t t, uint32_t x, uint32_t y, uint32_t z){
    //printf("t:%8x\tx:%8x\ty:%8x\tz:%8x\t\n", t, x, y, z);
    if( t>=0 & t<=19){
        return Ch(x, y, z);
    }
    else if( t>=20 & t<=39){
        return Parity(x, y, z);
    }
    else if( t>=40 & t<=59){
        return Maj(x, y, z);
    }
    else if( t>=60 & t<=79){
        return Parity(x, y, z);
    }
    else{
        puts("Error!");
        exit(0);
    }
}

常量

使用了80个32位整数，可以在C语言中被定义为

// 返回SHA-1常量
uint32_t K_t(uint32_t t){

    if( t>=0 & t<=19){
        return 0x5a827999;
    }
    else if( t>=20 & t<=39){
        return 0x6ed9eba1;
    }
    else if( t>=40 & t<=59){
        return 0x8f1bbcdc;
    }
    else if( t>=60 & t<=79){
        return 0xca62c1d6;
    }
    else{
        puts("Error!");
        exit(0);
    }
}

预处理

填充（padding）

设消息M的长度是l。

添加比特1，

然后添加k个0比特，其中k要满足
$$
l+1+k=448\ mod\ 512
$$
此式最小的非负整数。

然后再添加64比特长的len(l)。

比如M为abc，则len(l)为3*8=24，即添加0b11000（前面得跟上若干0比特来凑成64位长整型）。

实现：

// 返回`M`的比特长度
uint64_t getLenBits(const char* input){
    uint64_t len = 0;
    for(len = 0; input[len]; len++){
        ;
    }
    return len*8;
}

// 返回满足要求的 k+1 比特值
// 通过while暴力穷举
uint64_t getK_1(const char* message){
    uint64_t len = getLenBits(message);
    uint64_t m = 0;
    //printf("len:%llu\n", len);
    int64_t jde;
    jde = 448 + m*512 - len;
    //printf("jde:%lld\n", jde);
    while( (jde = 448 + m*512 - len) < 1){
        m++;
    }
    //printf("m:%llu\n", m);
    return 448 + m*512 - len;
}

// malloc, memcpy等实现创建并拼接，得到padded message
char * Padding(const char* message, uint64_t* BlockNum){
    uint64_t lb = getLenBits(message);
    uint64_t l = lb/8;
    // uint64_t --> char[8]
    char *parr = longlong2strBE(lb);
    // k+1 in bits
    uint64_t k_1_b = getK_1(message);
    //printf("lb:%10llu l:%10llu\nk_1_b:%10llu\n", lb, l, k_1_b);

    // k + 1 + l + 8(64bits for len(l)) in bytes
    uint64_t retlen = ((k_1_b+lb)/8 + 8);
    //printf("retlen:%10llu\n", retlen);
    *BlockNum = (k_1_b + lb + 64)/512;
    //printf("Numof Block: %llu\n", BlockNum);
    char *parrret = (char*)malloc(retlen);

    if(parrret == NULL){
        puts("Error while malloc Padding.");
        exit(1);
    }
    memset(parrret, 0, retlen);
    memcpy(parrret, message, l);
    memset(&parrret[l], 128, 1);
    memcpy(&parrret[(k_1_b+lb)/8], parr, 8);

    return parrret;
}

解析

padded message还需要拆分成若干512比特长的消息块
$$
M^{(N)}
$$
每个消息块又有16个字，所以每个字可以从左往右记作
$$
M^{(N)}_j
$$
我的实现：

typedef struct {
    uint32_t m[16];
} M;

M * Parsing(const char* input, int BlockNum){
    M * pM = (M*)malloc(BlockNum*sizeof(M));

    memset(pM, 0, BlockNum*sizeof(M));
    memcpy((char*)pM, input, BlockNum*512/8);

    return pM;
}

初始化哈希值

对于SHA1，哈希值由5个32位字组成。

typedef struct {
    uint32_t h[5];
} H;

H H_0 = {
    0x67452301,
    0xefcdab89,
    0x98badcfe,
    0x10325476,
    0xc3d2e1f0
};

哈希运算

遍历每个消息块
$$
M^{(1)},M^{(2)},…,M^{(N)}
$$

1	for(int i=0; i<N; i++)

1

初始化W_t

// 递归版，符合fips原标准，但是效率太低
uint32_t W(int t, M* pm, int i){
    if(t>=0 & t<=15){
        return pm[i].m[t];
    }
    else if(t>=16 & t<=79){
        ROTL(W(t-3,pm,i)^W(t-8,pm,i)^W(t-14,pm,i)^W(t-16,pm,i),1);
        //ROTL(pm[i].m[t-3]^pm[i].m[t-8]^pm[i].m[t-14]^pm[i].m[t-16],1);
    }
    else{
        puts("Error while message schedule");
        exit(1);
    }
}

// 打表法，无递归，速度显著提升
uint32_t* compileW(M* pm, int i){
    uint32_t* locpm = (uint32_t*)malloc(sizeof(uint32_t)*80);

    uint32_t tmp;

    memset(locpm, 0, 80);
    for(int t=0; t<16; t++){
        locpm[t] = intLE2BE(pm[i].m[t]);
    }
    for(int t=16; t<80; t++){
        tmp = ROTL((locpm[t-3]^locpm[t-8]^locpm[t-14]^locpm[t-16]),1);
        locpm[t] = tmp;
        //W[i] = SHA1_ROTL((W[i - 3] ^ W[i - 8] ^ W[i - 14] ^ W[i - 16]), 1)
    }
    return locpm;
}

2

初始化5个工作变量a，b，c，d，e，使用第i-1个哈希值

a = H.h[0];
b = H.h[1];
c = H.h[2];
d = H.h[3];
e = H.h[4];

3

For t = 0 to 79: 
{
    T = ROTL5 (a) + f_t(b,c,d) + e + K_t + W_t
    e = d 
    d = c 
    c = ROTL30(b) 
    b = a 
    a = T 
}

for(int t=0; t<=79; t++){
    tmp1 = ROTL(a,5);
    tmp2 = func_t(t, b, c, d);
    tmp3 = e;
    tmp4 = K_t(t);
    tmp5 = pW[t];
    //printf("ROTL():%8x\tfunc_t():%8x\te:%8x\tK_t():%8x\tW_t:%8x\n", tmp1, tmp2, tmp3, tmp4, tmp5);
    T = tmp1 + tmp2 + tmp3 + tmp4 + tmp5;
    //T = ROTL(a,5) + func_t(t, b, c, d) + e + K_t(t) + intLE2BE(retW[t]);
    e = d;
    d = c;
    c = ROTL(b,30);
    b = a;
    a = T;

    //printf("t=%2d\ta=%8x\tb=%8x\tc=%8x\td=%8x\te=%8x\t\n", t, a, b, c, d, e);
}

4

更新哈希值
$$
H^{(i)}=a+H^{(i-1)}
$$

// update
H.h[0] = a + H.h[0];
H.h[1] = b + H.h[1];
H.h[2] = c + H.h[2];
H.h[3] = d + H.h[3];
H.h[4] = e + H.h[4];

输出

步过N次后，就可以输出160位的哈希值了
$$
H_0|H_1|H_2|H_3|H_4
$$

源码

纯手工打造，仅做了少量优化，效率一般

/*
SHA-1 Algorithm By Bytes
*/

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <cstring>
#include <time.h>

#define AND &
#define XOR ^
#define OR |
#define ROTL(x,n) ((x<<n)|(x>>(32-n)))
#define ROTR(x,n) ROTL((x),(32-n))

// SHA-1函数
uint32_t Ch(uint32_t x, uint32_t y, uint32_t z){
    uint32_t t = (x & y) ^ (~x & z);
    //printf("t from Ch():%8x\n", t);
    return t;
}

uint32_t Parity(uint32_t x, uint32_t y, uint32_t z){
    return x ^ y ^ z;
}

uint32_t Maj(uint32_t x, uint32_t y, uint32_t z){
    return (x & y) ^ (x & z) ^ (y & z);
}

uint32_t func_t(uint32_t t, uint32_t x, uint32_t y, uint32_t z){
    //printf("t:%8x\tx:%8x\ty:%8x\tz:%8x\t\n", t, x, y, z);
    if( t>=0 & t<=19){
        return Ch(x, y, z);
    }
    else if( t>=20 & t<=39){
        return Parity(x, y, z);
    }
    else if( t>=40 & t<=59){
        return Maj(x, y, z);
    }
    else if( t>=60 & t<=79){
        return Parity(x, y, z);
    }
    else{
        puts("Error!");
        exit(0);
    }
}

// 返回SHA-1常量
uint32_t K_t(uint32_t t){

    if( t>=0 & t<=19){
        return 0x5a827999;
    }
    else if( t>=20 & t<=39){
        return 0x6ed9eba1;
    }
    else if( t>=40 & t<=59){
        return 0x8f1bbcdc;
    }
    else if( t>=60 & t<=79){
        return 0xca62c1d6;
    }
    else{
        puts("Error!");
        exit(0);
    }
}

// Padding
uint64_t getLenBits(const char* input){
    uint64_t len = 0;
    for(len = 0; input[len]; len++){
        ;
    }
    return len*8;
}

char readlonglongBE(uint64_t t, int n){
    if(n>=0 & n<=7){
        return (t >> (56-n*8)) & 0xff;
    }
    else{
        puts("Error");
        exit(1);
    }
    
}

char* longlong2strBE(uint64_t t){
    char* arr = (char*)malloc(8);

    if(arr == NULL){
        puts("Error while malloc!");
        exit(1);
    }

    for(int i=0; i<8; i++){
        arr[i] = readlonglongBE(t, i);
    }
    return arr;
}

// k + 1
uint64_t getK_1(const char* message){
    uint64_t len = getLenBits(message);
    uint64_t m = 0;
    //printf("len:%llu\n", len);
    int64_t jde;
    jde = 448 + m*512 - len;
    //printf("jde:%lld\n", jde);
    while( (jde = 448 + m*512 - len) < 1){
        m++;
    }
    //printf("m:%llu\n", m);
    return 448 + m*512 - len;
}

char * Padding(const char* message, uint64_t* BlockNum){
    uint64_t lb = getLenBits(message);
    uint64_t l = lb/8;
    // uint64_t --> char[8]
    char *parr = longlong2strBE(lb);
    // k+1 in bits
    uint64_t k_1_b = getK_1(message);
    //printf("lb:%10llu l:%10llu\nk_1_b:%10llu\n", lb, l, k_1_b);

    // k + 1 + l + 8(64bits for len(l)) in bytes
    uint64_t retlen = ((k_1_b+lb)/8 + 8);
    //printf("retlen:%10llu\n", retlen);
    *BlockNum = (k_1_b + lb + 64)/512;
    //printf("Numof Block: %llu\n", BlockNum);
    char *parrret = (char*)malloc(retlen);

    if(parrret == NULL){
        puts("Error while malloc Padding.");
        exit(1);
    }
    memset(parrret, 0, retlen);
    memcpy(parrret, message, l);
    memset(&parrret[l], 128, 1);
    memcpy(&parrret[(k_1_b+lb)/8], parr, 8);

    return parrret;
}

//test
/*
int main(void){
    char *string = Padding("aaa");

    for(int i=0; i<64; i++){
        printf("%2x ", string[i]);
    }
    putchar('\n');

    return 0;
}
*/
//parsing
typedef struct {
    uint32_t m[16];
} M;

M * Parsing(const char* input, int BlockNum){
    M * pM = (M*)malloc(BlockNum*sizeof(M));

    memset(pM, 0, BlockNum*sizeof(M));
    memcpy((char*)pM, input, BlockNum*512/8);

    return pM;
}

//test
/*
int main(void){
    char input[] = "0123456789abcdef0123456789abcdef0123456789abcdef";
    M * m = Parsing(input);

    for(int i=0; i<getBlockNum(input); i++){
        for(int j=0; j<16; j++){
            printf("%#x\n", m[i].m[j]);
        }
    }

    return 0;
}
*/

//Initial Hash Value(H0)
typedef struct {
    uint32_t h[5];
} H;

H H_0 = {
    0x67452301,
    0xefcdab89,
    0x98badcfe,
    0x10325476,
    0xc3d2e1f0
};

//test
/*
int main(void){

    for(int i=0 ; i<5; i++){
        printf("%#x\n", H_0.h[i]);
    }

    return 0;
}
*/
uint32_t W(int t, M* pm, int i){
    if(t>=0 & t<=15){
        return pm[i].m[t];
    }
    else if(t>=16 & t<=79){
        ROTL(W(t-3,pm,i)^W(t-8,pm,i)^W(t-14,pm,i)^W(t-16,pm,i),1);
        //ROTL(pm[i].m[t-3]^pm[i].m[t-8]^pm[i].m[t-14]^pm[i].m[t-16],1);
    }
    else{
        puts("Error while message schedule");
        exit(1);
    }
}

uint32_t intLE2BE(uint32_t a){
    return ((a&0xff)<<24)|((a&0xff00)<<8)|((a&0xff0000)>>8)|((a&0xff000000)>>24);
}

uint32_t* compileW(M* pm, int i){
    uint32_t* locpm = (uint32_t*)malloc(sizeof(uint32_t)*80);

    uint32_t tmp;

    memset(locpm, 0, 80);
    for(int t=0; t<16; t++){
        locpm[t] = intLE2BE(pm[i].m[t]);
    }
    for(int t=16; t<80; t++){
        tmp = ROTL((locpm[t-3]^locpm[t-8]^locpm[t-14]^locpm[t-16]),1);
        locpm[t] = tmp;
        //W[i] = SHA1_ROTL((W[i - 3] ^ W[i - 8] ^ W[i - 14] ^ W[i - 16]), 1)
    }
    return locpm;
}



void HashComputation(const char* input){
    uint64_t N;
    //puts("Padding...");
    char *padded_input = Padding(input, &N);
    //puts("Padded");
    //puts("Parsing...");
    //printf("Numof Block: %lld\n", N);
    M * Marr = Parsing(padded_input, N);
    //puts("Parsed");

    //uint32_t retW[80];
    uint32_t* pW;

    H H = {
    0x67452301,
    0xefcdab89,
    0x98badcfe,
    0x10325476,
    0xc3d2e1f0
    };

    uint32_t a, b, c, d, e;

    uint32_t T;

    for(int i=0; i<N; i++){
        // Prepare the message schedule
        //puts("compilingW...");
        pW = compileW(Marr, i);
        //puts("compiled");
        //for(int j=0; j<80; j++){
            //printf("%X\n", (pW[j]));
        //}
        // init five working variables
        a = H.h[0];
        b = H.h[1];
        c = H.h[2];
        d = H.h[3];
        e = H.h[4];
    
        uint32_t tmp1, tmp2, tmp3, tmp4, tmp5;
        // 
        //puts("hashing...");
        for(int t=0; t<=79; t++){
            tmp1 = ROTL(a,5);
            tmp2 = func_t(t, b, c, d);
            tmp3 = e;
            tmp4 = K_t(t);
            tmp5 = pW[t];
            //printf("ROTL():%8x\tfunc_t():%8x\te:%8x\tK_t():%8x\tW_t:%8x\n", tmp1, tmp2, tmp3, tmp4, tmp5);
            T = tmp1 + tmp2 + tmp3 + tmp4 + tmp5;
            //T = ROTL(a,5) + func_t(t, b, c, d) + e + K_t(t) + intLE2BE(retW[t]);
            e = d;
            d = c;
            c = ROTL(b,30);
            b = a;
            a = T;

            //printf("t=%2d\ta=%8x\tb=%8x\tc=%8x\td=%8x\te=%8x\t\n", t, a, b, c, d, e);
        }

        // update
        H.h[0] = a + H.h[0];
        H.h[1] = b + H.h[1];
        H.h[2] = c + H.h[2];
        H.h[3] = d + H.h[3];
        H.h[4] = e + H.h[4];
    }

    printf("%08x%08x%08x%08x%08x\n", H.h[0], H.h[1], H.h[2], H.h[3], H.h[4]);
    free(padded_input);
    free(Marr);
    free(pW);
}

int main(void){
    //HashComputation("abc");
    //HashComputation("abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq");
    // clock_t start, end;
    // double duration;
    // char m[1000001];
    // memset(m, 0, 1000001);
    // memset(m, 'a', 1000000);
    // start = clock();
    // HashComputation(m);
    // end = clock();
    // duration = (double)(end-start)/CLOCKS_PER_SEC;
    // printf("time used:%f", duration);
    // //printf("%#x\n", ROTL(1, 8));

    clock_t start, end;
    double duration;
    char m[1000001];
    memset(m, 0, 1000001);
    memset(m, 'a', 1000000);
    start = clock();
    HashComputation(m);
    end = clock();
    duration = (double)(end-start)/CLOCKS_PER_SEC;
    printf("time used:%f", duration);
    //printf("%#x\n", ROTL(1, 8));

}

SHA256

SHA256和SHA1在一些设定上类似，比如一个消息块512比特，一个字32比特。

函数

数学式子懒得再打出来了。Sigma就是求和的意思，Σ。lSigma是小写希腊字母σ。

#define AND &
#define XOR ^
#define OR |
#define ROTL(x,n) ((x<<n)|(x>>(32-n)))
#define ROTR(x,n) ROTL((x),(32-n))
#define SHR(x,n) ((x)>>(n))


// SHA-1函数
// Ch函数不知道干啥的
uint32_t Ch(uint32_t x, uint32_t y, uint32_t z){
    uint32_t t = (x & y) ^ (~x & z);
    //For Debug
    //printf("t from Ch():%8x\n", t);
    return t;
}

uint32_t Maj(uint32_t x, uint32_t y, uint32_t z){
    return (x & y) ^ (x & z) ^ (y & z);
}

uint32_t Sigma_0_256(uint32_t x){
    uint32_t t,a,b,c;
    a = ROTR(x,2);
    b = ROTR(x,13);
    c = ROTR(x,22);
    t = a^b^c;
    return t;
}

uint32_t Sigma_1_256(uint32_t x){
    uint32_t t,a,b,c;
    a = ROTR(x,6);
    b = ROTR(x,11);
    c = ROTR(x,25);
    t = a^b^c;
    return t;
}

//一个大写一个小写，注意！
uint32_t lSigma_0_256(uint32_t x){
    uint32_t t,a,b,c;
    a = ROTR(x,7);
    b = ROTR(x,18);
    c = SHR(x,3);
    t = a^b^c;
    return t;
}

uint32_t lSigma_1_256(uint32_t x){
    uint32_t t,a,b,c;
    a = ROTR(x,17);
    b = ROTR(x,19);
    c = SHR(x,10);
    t = a^b^c;
    return t;
}

常量

选取了前64个素数的立方根的分数部分的首32比特。

uint32_t SHA256_Constants[64] = {
    0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5,
    0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
    0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3,
    0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
    0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc,
    0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
    0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7,
    0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
    0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13,
    0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
    0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3,
    0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
    0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5,
    0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
    0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208,
    0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
};

预处理

填充

与SHA1一模一样

解析

与SHA1一模一样

初始化哈希值

由8个字组成。

typedef struct {
    uint32_t h[8];
} H;

H H_0 = {
    0x6a09e667,
    0xbb67ae85,
    0x3c6ef372,
    0xa54ff53a,
    0x510e527f,
    0x9b05688c,
    0x1f83d9ab,
    0x5be0cd19
};

哈希运算

遍历每个消息块
$$
M^{(1)},M^{(2)},…,M^{(N)}
$$

1	for(int i=0; i<N; i++)

1

准备W_t

uint32_t* compileW(M* pm, int i){
    uint32_t* locpm = (uint32_t*)malloc(sizeof(uint32_t)*64);

    uint32_t tmp;

    memset(locpm, 0, 80);
    for(int t=0; t<16; t++){
        locpm[t] = intLE2BE(pm[i].m[t]);
    }
    for(int t=16; t<64; t++){
        tmp = lSigma_1_256(locpm[t-2]) + locpm[t-7] + lSigma_0_256(locpm[t-15]) + locpm[t-16];
        locpm[t] = tmp; 
        //W[i] = SHA1_ROTL((W[i - 3] ^ W[i - 8] ^ W[i - 14] ^ W[i - 16]), 1)
    }
    return locpm;
}

2

初始化8个变量

a = H.h[0];
b = H.h[1];
c = H.h[2];
d = H.h[3];
e = H.h[4];
f = H.h[5];
g = H.h[6];
h = H.h[7];

3

for(int t=0; t<=63; t++){
    T1 = h + Sigma_1_256(e) + Ch(e, f, g) + SHA256_Constants[t] + pW[t];
    T2 = Sigma_0_256(a) + Maj(a, b, c);
    h = g;
    g = f;
    f = e;
    e = d + T1;
    d = c;
    c = b;
    b = a;
    a = T1 + T2;
}

4

更新哈希值

H.h[0] = a + H.h[0];
H.h[1] = b + H.h[1];
H.h[2] = c + H.h[2];
H.h[3] = d + H.h[3];
H.h[4] = e + H.h[4];
H.h[5] = f + H.h[5];
H.h[6] = g + H.h[6];
H.h[7] = h + H.h[7];

输出

8个字拼一块就好了。

源码

/*
SHA-256 Algorithm By Bytes
字: 32比特,4字节
*/

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <cstring>
#include <time.h>

#define AND &
#define XOR ^
#define OR |
#define ROTL(x,n) ((x<<n)|(x>>(32-n)))
#define ROTR(x,n) ROTL((x),(32-n))
#define SHR(x,n) ((x)>>(n))

// SHA-1函数
// Ch函数不知道干啥的
uint32_t Ch(uint32_t x, uint32_t y, uint32_t z){
    uint32_t t = (x & y) ^ (~x & z);
    //For Debug
    //printf("t from Ch():%8x\n", t);
    return t;
}

uint32_t Maj(uint32_t x, uint32_t y, uint32_t z){
    return (x & y) ^ (x & z) ^ (y & z);
}

uint32_t Sigma_0_256(uint32_t x){
    uint32_t t,a,b,c;
    a = ROTR(x,2);
    b = ROTR(x,13);
    c = ROTR(x,22);
    t = a^b^c;
    return t;
}

uint32_t Sigma_1_256(uint32_t x){
    uint32_t t,a,b,c;
    a = ROTR(x,6);
    b = ROTR(x,11);
    c = ROTR(x,25);
    t = a^b^c;
    return t;
}

//一个大写一个小写，注意！
uint32_t lSigma_0_256(uint32_t x){
    uint32_t t,a,b,c;
    a = ROTR(x,7);
    b = ROTR(x,18);
    c = SHR(x,3);
    t = a^b^c;
    return t;
}

uint32_t lSigma_1_256(uint32_t x){
    uint32_t t,a,b,c;
    a = ROTR(x,17);
    b = ROTR(x,19);
    c = SHR(x,10);
    t = a^b^c;
    return t;
}

uint32_t SHA256_Constants[64] = {
    0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5,
    0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
    0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3,
    0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
    0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc,
    0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
    0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7,
    0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
    0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13,
    0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
    0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3,
    0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
    0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5,
    0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
    0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208,
    0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
};

// Padding
uint64_t getLenBits(const char* input){
    uint64_t len = 0;
    for(len = 0; input[len]; len++){
        ;
    }
    return len*8;
}

char readlonglongBE(uint64_t t, int n){
    if(n>=0 & n<=7){
        return (t >> (56-n*8)) & 0xff;
    }
    else{
        puts("Error");
        exit(1);
    }
    
}

char* longlong2strBE(uint64_t t){
    char* arr = (char*)malloc(8);

    if(arr == NULL){
        puts("Error while malloc!");
        exit(1);
    }

    for(int i=0; i<8; i++){
        arr[i] = readlonglongBE(t, i);
    }
    return arr;
}

uint64_t getK_1(const char* message){
    uint64_t len = getLenBits(message);
    uint64_t m = 0;
    //printf("len:%llu\n", len);
    int64_t jde;
    jde = 448 + m*512 - len;
    //printf("jde:%lld\n", jde);
    while( (jde = 448 + m*512 - len) < 1){
        m++;
    }
    //printf("m:%llu\n", m);
    return 448 + m*512 - len;
}

char * Padding(const char* message, uint64_t* BlockNum){
    uint64_t lb = getLenBits(message);
    uint64_t l = lb/8;
    char *parr = longlong2strBE(lb);

    uint64_t k_1_b = getK_1(message);
    //printf("lb:%10llu l:%10llu\nk_1_b:%10llu\n", lb, l, k_1_b);
    uint64_t retlen = ((k_1_b+lb)/8 + 8);
    //printf("retlen:%10llu\n", retlen);
    *BlockNum = (k_1_b + lb + 64)/512;
    //printf("Numof Block: %llu\n", BlockNum);
    char *parrret = (char*)malloc(retlen);

    if(parrret == NULL){
        puts("Error while malloc Padding.");
        exit(1);
    }
    memset(parrret, 0, retlen);
    memcpy(parrret, message, l);
    memset(&parrret[l], 128, 1);
    memcpy(&parrret[(k_1_b+lb)/8], parr, 8);

    return parrret;
}

//test
/*
int main(void){
    char *string = Padding("aaa");

    for(int i=0; i<64; i++){
        printf("%2x ", string[i]);
    }
    putchar('\n');

    return 0;
}
*/
//parsing
typedef struct {
    uint32_t m[16];
} M;

M * Parsing(const char* input, int BlockNum){
    M * pM = (M*)malloc(BlockNum*sizeof(M));

    memset(pM, 0, BlockNum*sizeof(M));
    memcpy((char*)pM, input, BlockNum*512/8);

    return pM;
}

//test
/*
int main(void){
    char input[] = "0123456789abcdef0123456789abcdef0123456789abcdef";
    M * m = Parsing(input);

    for(int i=0; i<getBlockNum(input); i++){
        for(int j=0; j<16; j++){
            printf("%#x\n", m[i].m[j]);
        }
    }

    return 0;
}
*/

//Initial Hash Value(H0)
typedef struct {
    uint32_t h[8];
} H;

H H_0 = {
    0x6a09e667,
    0xbb67ae85,
    0x3c6ef372,
    0xa54ff53a,
    0x510e527f,
    0x9b05688c,
    0x1f83d9ab,
    0x5be0cd19
};

//test
/*
int main(void){

    for(int i=0 ; i<5; i++){
        printf("%#x\n", H_0.h[i]);
    }

    return 0;
}
*/

uint32_t intLE2BE(uint32_t a){
    return ((a&0xff)<<24)|((a&0xff00)<<8)|((a&0xff0000)>>8)|((a&0xff000000)>>24);
}

// uint32_t W(int t, M* pm, int i){
//     if(t>=0 & t<=15){
//         return pm[i].m[t];
//     }
//     else if(t>=16 & t<=79){
//         ROTL(W(t-3,pm,i)^W(t-8,pm,i)^W(t-14,pm,i)^W(t-16,pm,i),1);
//         //ROTL(pm[i].m[t-3]^pm[i].m[t-8]^pm[i].m[t-14]^pm[i].m[t-16],1);
//     }
//     else{
//         puts("Error while message schedule");
//         exit(1);
//     }
// }


uint32_t* compileW(M* pm, int i){
    uint32_t* locpm = (uint32_t*)malloc(sizeof(uint32_t)*64);

    uint32_t tmp;

    memset(locpm, 0, 80);
    for(int t=0; t<16; t++){
        locpm[t] = intLE2BE(pm[i].m[t]);
    }
    for(int t=16; t<64; t++){
        tmp = lSigma_1_256(locpm[t-2]) + locpm[t-7] + lSigma_0_256(locpm[t-15]) + locpm[t-16];
        locpm[t] = tmp; 
        //W[i] = SHA1_ROTL((W[i - 3] ^ W[i - 8] ^ W[i - 14] ^ W[i - 16]), 1)
    }
    return locpm;
}

void HashComputation(const char* input){
    uint64_t N;
    //puts("Padding...");
    char *padded_input = Padding(input, &N);
    //puts("Padded");
    //puts("Parsing...");
    //printf("Numof Block: %lld\n", N);
    M * Marr = Parsing(padded_input, N);
    //puts("Parsed");

    //uint32_t retW[80];
    uint32_t* pW;

    H H = {
    0x6a09e667,
    0xbb67ae85,
    0x3c6ef372,
    0xa54ff53a,
    0x510e527f,
    0x9b05688c,
    0x1f83d9ab,
    0x5be0cd19
    };

    uint32_t a, b, c, d, e, f, g, h;

    uint32_t T1, T2;

    for(int i=0; i<N; i++){
        // Prepare the message schedule
        //puts("compilingW...");
        pW = compileW(Marr, i);
        //puts("compiled");
        //for(int j=0; j<80; j++){
            //printf("%X\n", (pW[j]));
        //}
        // init five working variables
        a = H.h[0];
        b = H.h[1];
        c = H.h[2];
        d = H.h[3];
        e = H.h[4];
        f = H.h[5];
        g = H.h[6];
        h = H.h[7];
    
        uint32_t tmp1, tmp2, tmp3, tmp4, tmp5, tmp6, tmp7;
        // 
        //puts("hashing...");
        for(int t=0; t<=63; t++){
            T1 = h + Sigma_1_256(e) + Ch(e, f, g) + SHA256_Constants[t] + pW[t];
            T2 = Sigma_0_256(a) + Maj(a, b, c);
            h = g;
            g = f;
            f = e;
            e = d + T1;
            d = c;
            c = b;
            b = a;
            a = T1 + T2;
        }
        
        // update
        H.h[0] = a + H.h[0];
        H.h[1] = b + H.h[1];
        H.h[2] = c + H.h[2];
        H.h[3] = d + H.h[3];
        H.h[4] = e + H.h[4];
        H.h[5] = f + H.h[5];
        H.h[6] = g + H.h[6];
        H.h[7] = h + H.h[7];
    }

    printf("%08x%08x%08x%08x%08x%08x%08x%08x\n", H.h[0], H.h[1], H.h[2], H.h[3], H.h[4], H.h[5], H.h[6], H.h[7]);
    free(padded_input);
    free(Marr);
    free(pW);
}

int main(void){
    //HashComputation("abc");
    //HashComputation("abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq");
    // clock_t start, end;
    // double duration;
    // char m[1000001];
    // memset(m, 0, 1000001);
    // memset(m, 'a', 1000000);
    // start = clock();
    // HashComputation(m);
    // end = clock();
    // duration = (double)(end-start)/CLOCKS_PER_SEC;
    // printf("time used:%f", duration);
    // //printf("%#x\n", ROTL(1, 8));

    clock_t start, end;
    double duration;
    char m[1000001];
    memset(m, 0, 1000001);
    memset(m, 'a', 1000000);
    start = clock();
    HashComputation("abc");
    HashComputation("abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq");
    HashComputation(m);
    end = clock();
    duration = (double)(end-start)/CLOCKS_PER_SEC;
    printf("time used:%f", duration);
    //printf("%#x\n", ROTL(1, 8));

}

SHA512

函数

#define AND &
#define XOR ^
#define OR |
#define ROTL(x,n) (((x)<<(n))|((x)>>(64-n)))
#define ROTR(x,n) ROTL((x),(64-n))
#define SHR(x,n) ((x)>>(n))

// SHA-1函数
// Ch函数不知道干啥的
uint64_t Ch(uint64_t x, uint64_t y, uint64_t z){
    uint64_t t = (x & y) ^ (~x & z);
    //For Debug
    //printf("t from Ch():%8x\n", t);
    return t;
}

uint64_t Maj(uint64_t x, uint64_t y, uint64_t z){
    return (x & y) ^ (x & z) ^ (y & z);
}

uint64_t Sigma_0_512(uint64_t x){
    uint64_t t,a,b,c;
    a = ROTR(x,28);
    b = ROTR(x,34);
    c = ROTR(x,39);
    t = a^b^c;
    return t;
}

uint64_t Sigma_1_512(uint64_t x){
    uint64_t t,a,b,c;
    a = ROTR(x,14);
    b = ROTR(x,18);
    c = ROTR(x,41);
    t = a^b^c;
    return t;
}

//一个大写一个小写，注意！
uint64_t lSigma_0_512(uint64_t x){
    uint64_t t,a,b,c;
    a = ROTR(x,1);
    b = ROTR(x,8);
    c = SHR(x,7);
    t = a^b^c;
    return t;
}

uint64_t lSigma_1_512(uint64_t x){
    uint64_t t,a,b,c;
    a = ROTR(x,19);
    b = ROTR(x,61);
    c = SHR(x,6);
    t = a^b^c;
    return t;
}

常量

uint64_t K[80] = {
    0x428a2f98d728ae22ULL, 0x7137449123ef65cdULL, 0xb5c0fbcfec4d3b2fULL, 0xe9b5dba58189dbbcULL,
    0x3956c25bf348b538ULL, 0x59f111f1b605d019ULL, 0x923f82a4af194f9bULL, 0xab1c5ed5da6d8118ULL,
    0xd807aa98a3030242ULL, 0x12835b0145706fbeULL, 0x243185be4ee4b28cULL, 0x550c7dc3d5ffb4e2ULL,
    0x72be5d74f27b896fULL, 0x80deb1fe3b1696b1ULL, 0x9bdc06a725c71235ULL, 0xc19bf174cf692694ULL,
    0xe49b69c19ef14ad2ULL, 0xefbe4786384f25e3ULL, 0x0fc19dc68b8cd5b5ULL, 0x240ca1cc77ac9c65ULL,
    0x2de92c6f592b0275ULL, 0x4a7484aa6ea6e483ULL, 0x5cb0a9dcbd41fbd4ULL, 0x76f988da831153b5ULL,
    0x983e5152ee66dfabULL, 0xa831c66d2db43210ULL, 0xb00327c898fb213fULL, 0xbf597fc7beef0ee4ULL,
    0xc6e00bf33da88fc2ULL, 0xd5a79147930aa725ULL, 0x06ca6351e003826fULL, 0x142929670a0e6e70ULL,
    0x27b70a8546d22ffcULL, 0x2e1b21385c26c926ULL, 0x4d2c6dfc5ac42aedULL, 0x53380d139d95b3dfULL,
    0x650a73548baf63deULL, 0x766a0abb3c77b2a8ULL, 0x81c2c92e47edaee6ULL, 0x92722c851482353bULL,
    0xa2bfe8a14cf10364ULL, 0xa81a664bbc423001ULL, 0xc24b8b70d0f89791ULL, 0xc76c51a30654be30ULL,
    0xd192e819d6ef5218ULL, 0xd69906245565a910ULL, 0xf40e35855771202aULL, 0x106aa07032bbd1b8ULL,
    0x19a4c116b8d2d0c8ULL, 0x1e376c085141ab53ULL, 0x2748774cdf8eeb99ULL, 0x34b0bcb5e19b48a8ULL,
    0x391c0cb3c5c95a63ULL, 0x4ed8aa4ae3418acbULL, 0x5b9cca4f7763e373ULL, 0x682e6ff3d6b2b8a3ULL,
    0x748f82ee5defb2fcULL, 0x78a5636f43172f60ULL, 0x84c87814a1f0ab72ULL, 0x8cc702081a6439ecULL,
    0x90befffa23631e28ULL, 0xa4506cebde82bde9ULL, 0xbef9a3f7b2c67915ULL, 0xc67178f2e372532bULL,
    0xca273eceea26619cULL, 0xd186b8c721c0c207ULL, 0xeada7dd6cde0eb1eULL, 0xf57d4f7fee6ed178ULL,
    0x06f067aa72176fbaULL, 0x0a637dc5a2c898a6ULL, 0x113f9804bef90daeULL, 0x1b710b35131c471bULL,
    0x28db77f523047d84ULL, 0x32caab7b40c72493ULL, 0x3c9ebe0a15c9bebcULL, 0x431d67c49c100d4cULL,
    0x4cc5d4becb3e42b6ULL, 0x597f299cfc657e2aULL, 0x5fcb6fab3ad6faecULL, 0x6c44198c4a475817ULL
};

预处理

$$
l+1+k=896\ mod\ 1024
$$

uint64_t getK_1(const char* message){
    uint64_t len = getLenBits(message);
    uint64_t m = 0;
    //printf("len:%llu\n", len);
    int64_t jde;
    jde = 896 + m*1024 - len;
    //printf("jde:%lld\n", jde);
    while( (jde = 896 + m*1024 - len) < 1){
        m++;
    }
    //printf("m:%llu\n", m);
    return 896 + m*1024 - len;
}

char * Padding(const char* message, uint64_t* BlockNum){
    uint64_t lb = getLenBits(message);
    uint64_t l = lb/8;

    //还没完成128位int的实现，暂时先这样
    char *parr = int128ToBE(0, lb);

    uint64_t k_1_b = getK_1(message);
    //printf("lb:%10llu l:%10llu\nk_1_b:%10llu\n", lb, l, k_1_b);
    uint64_t retlen = ((k_1_b+lb)/8 + 16);
    //printf("retlen:%10llu\n", retlen);
    *BlockNum = (k_1_b + lb + 128)/1024;
    //printf("Numof Block: %llu\n", *BlockNum);
    char *parrret = (char*)malloc(retlen);

    if(parrret == NULL){
        puts("Error while malloc Padding.");
        exit(1);
    }
    memset(parrret, 0, retlen);
    memcpy(parrret, message, l);
    memset(&parrret[l], 128, 1);
    memcpy(&parrret[(k_1_b+lb)/8], parr, 16);

    return parrret;
}

typedef struct {
    uint64_t h[8];
} H;

H H_0 = {
    0x6a09e667f3bcc908ULL, 
    0xbb67ae8584caa73bULL, 
    0x3c6ef372fe94f82bULL, 
    0xa54ff53a5f1d36f1ULL, 
    0x510e527fade682d1ULL, 
    0x9b05688c2b3e6c1fULL, 
    0x1f83d9abfb41bd6bULL,
    0x5be0cd19137e2179ULL
};

哈希运算

uint64_t* compileW(M* pm, int i){
    uint64_t* locpm = (uint64_t*)malloc(sizeof(uint64_t)*80);

    uint64_t tmp;

    memset(locpm, 0, 80);
    for(int t=0; t<16; t++){
        locpm[t] = swap(pm[i].m[t]);
    }
    for(int t=16; t<80; t++){
        tmp = lSigma_1_512(locpm[t-2]) + locpm[t-7] + lSigma_0_512(locpm[t-15]) + locpm[t-16];
        locpm[t] = tmp; 
        //W[i] = SHA1_ROTL((W[i - 3] ^ W[i - 8] ^ W[i - 14] ^ W[i - 16]), 1)
    }
    return locpm;
}

void HashComputation(const char* input){
    uint64_t N;
    //puts("Padding...");
    char *padded_input = Padding(input, &N);
    //puts("Padded");
    //puts("Parsing...");
    //printf("Numof Block: %lld\n", N);
    M * Marr = Parsing(padded_input, N);
    // for(int j=0; j<N; j++){
    //     for(int k=0; k<16; k++){
    //         printf("%016llx ", swap(Marr[j].m[k]));
    //     }
    //     putchar('\n');
    // }
    // puts("Parsed");

    //uint64_t retW[80];
    uint64_t* pW;

    H H = {
    0x6a09e667f3bcc908ULL, 
    0xbb67ae8584caa73bULL, 
    0x3c6ef372fe94f82bULL, 
    0xa54ff53a5f1d36f1ULL, 
    0x510e527fade682d1ULL, 
    0x9b05688c2b3e6c1fULL, 
    0x1f83d9abfb41bd6bULL,
    0x5be0cd19137e2179ULL
    };

    uint64_t a, b, c, d, e, f, g, h;

    uint64_t T1, T2;

    for(int i=0; i<N; i++){
        // Prepare the message schedule
        //puts("compilingW...");
        pW = compileW(Marr, i);
        //puts("compiled");
        // for(int j=0; j<80; j++){
        //     printf("%016llx\n", (pW[j]));
        // }
        // init five working variables
        a = H.h[0];
        b = H.h[1];
        c = H.h[2];
        d = H.h[3];
        e = H.h[4];
        f = H.h[5];
        g = H.h[6];
        h = H.h[7];
    
        uint64_t tmp1, tmp2, tmp3, tmp4, tmp5, tmp6, tmp7;
        // 
        //puts("hashing...");
        for(int t=0; t<=79; t++){
            T1 = h + Sigma_1_512(e) + Ch(e, f, g) + K[t] + pW[t];
            T2 = Sigma_0_512(a) + Maj(a, b, c);
            h = g;
            g = f;
            f = e;
            e = d + T1;
            d = c;
            c = b;
            b = a;
            a = T1 + T2;

            //printf("%2d: %016llx %016llx %016llx %016llx\n    %016llx %016llx %016llx %016llx \n\n", t, a, b, c, d, e, f, g, h);

        }
        
        // update
        H.h[0] = a + H.h[0];
        H.h[1] = b + H.h[1];
        H.h[2] = c + H.h[2];
        H.h[3] = d + H.h[3];
        H.h[4] = e + H.h[4];
        H.h[5] = f + H.h[5];
        H.h[6] = g + H.h[6];
        H.h[7] = h + H.h[7];
    }

    printf("%016llx%016llx%016llx%016llx%016llx%016llx%016llx%016llx\n", H.h[0], H.h[1], H.h[2], H.h[3], H.h[4], H.h[5], H.h[6], H.h[7]);
    free(padded_input);
    free(Marr);
    free(pW);
}

输出

输出8个64比特字即可。

SHA384

基本与SHA256一致，除了初始化哈希值，以及最后输出的比特数。

常量

typedef struct {
    uint64_t h[8];
} H;

H H_0 = {
0xcbbb9d5dc1059ed8uLL, 
0x629a292a367cd507uLL, 
0x9159015a3070dd17uLL, 
0x152fecd8f70e5939uLL, 
0x67332667ffc00b31uLL, 
0x8eb44a8768581511uLL, 
0xdb0c2e0d64f98fa7uLL, 
0x47b5481dbefa4fa4uLL
};

输出

只需要输出前面6个64比特字即可。

源码

/*
SHA-384 Algorithm By Bytes
字: 64比特，8字节
*/

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <cstring>
#include <time.h>

#define AND &
#define XOR ^
#define OR |
#define ROTL(x,n) (((x)<<(n))|((x)>>(64-n)))
#define ROTR(x,n) ROTL((x),(64-n))
#define SHR(x,n) ((x)>>(n))

// SHA-1函数
// Ch函数不知道干啥的
uint64_t Ch(uint64_t x, uint64_t y, uint64_t z){
    uint64_t t = (x & y) ^ (~x & z);
    //For Debug
    //printf("t from Ch():%8x\n", t);
    return t;
}

uint64_t Maj(uint64_t x, uint64_t y, uint64_t z){
    return (x & y) ^ (x & z) ^ (y & z);
}

uint64_t Sigma_0_512(uint64_t x){
    uint64_t t,a,b,c;
    a = ROTR(x,28);
    b = ROTR(x,34);
    c = ROTR(x,39);
    t = a^b^c;
    return t;
}

uint64_t Sigma_1_512(uint64_t x){
    uint64_t t,a,b,c;
    a = ROTR(x,14);
    b = ROTR(x,18);
    c = ROTR(x,41);
    t = a^b^c;
    return t;
}

//一个大写一个小写，注意！
uint64_t lSigma_0_512(uint64_t x){
    uint64_t t,a,b,c;
    a = ROTR(x,1);
    b = ROTR(x,8);
    c = SHR(x,7);
    t = a^b^c;
    return t;
}

uint64_t lSigma_1_512(uint64_t x){
    uint64_t t,a,b,c;
    a = ROTR(x,19);
    b = ROTR(x,61);
    c = SHR(x,6);
    t = a^b^c;
    return t;
}

uint64_t K[80] = {
    0x428a2f98d728ae22ULL, 0x7137449123ef65cdULL, 0xb5c0fbcfec4d3b2fULL, 0xe9b5dba58189dbbcULL,
    0x3956c25bf348b538ULL, 0x59f111f1b605d019ULL, 0x923f82a4af194f9bULL, 0xab1c5ed5da6d8118ULL,
    0xd807aa98a3030242ULL, 0x12835b0145706fbeULL, 0x243185be4ee4b28cULL, 0x550c7dc3d5ffb4e2ULL,
    0x72be5d74f27b896fULL, 0x80deb1fe3b1696b1ULL, 0x9bdc06a725c71235ULL, 0xc19bf174cf692694ULL,
    0xe49b69c19ef14ad2ULL, 0xefbe4786384f25e3ULL, 0x0fc19dc68b8cd5b5ULL, 0x240ca1cc77ac9c65ULL,
    0x2de92c6f592b0275ULL, 0x4a7484aa6ea6e483ULL, 0x5cb0a9dcbd41fbd4ULL, 0x76f988da831153b5ULL,
    0x983e5152ee66dfabULL, 0xa831c66d2db43210ULL, 0xb00327c898fb213fULL, 0xbf597fc7beef0ee4ULL,
    0xc6e00bf33da88fc2ULL, 0xd5a79147930aa725ULL, 0x06ca6351e003826fULL, 0x142929670a0e6e70ULL,
    0x27b70a8546d22ffcULL, 0x2e1b21385c26c926ULL, 0x4d2c6dfc5ac42aedULL, 0x53380d139d95b3dfULL,
    0x650a73548baf63deULL, 0x766a0abb3c77b2a8ULL, 0x81c2c92e47edaee6ULL, 0x92722c851482353bULL,
    0xa2bfe8a14cf10364ULL, 0xa81a664bbc423001ULL, 0xc24b8b70d0f89791ULL, 0xc76c51a30654be30ULL,
    0xd192e819d6ef5218ULL, 0xd69906245565a910ULL, 0xf40e35855771202aULL, 0x106aa07032bbd1b8ULL,
    0x19a4c116b8d2d0c8ULL, 0x1e376c085141ab53ULL, 0x2748774cdf8eeb99ULL, 0x34b0bcb5e19b48a8ULL,
    0x391c0cb3c5c95a63ULL, 0x4ed8aa4ae3418acbULL, 0x5b9cca4f7763e373ULL, 0x682e6ff3d6b2b8a3ULL,
    0x748f82ee5defb2fcULL, 0x78a5636f43172f60ULL, 0x84c87814a1f0ab72ULL, 0x8cc702081a6439ecULL,
    0x90befffa23631e28ULL, 0xa4506cebde82bde9ULL, 0xbef9a3f7b2c67915ULL, 0xc67178f2e372532bULL,
    0xca273eceea26619cULL, 0xd186b8c721c0c207ULL, 0xeada7dd6cde0eb1eULL, 0xf57d4f7fee6ed178ULL,
    0x06f067aa72176fbaULL, 0x0a637dc5a2c898a6ULL, 0x113f9804bef90daeULL, 0x1b710b35131c471bULL,
    0x28db77f523047d84ULL, 0x32caab7b40c72493ULL, 0x3c9ebe0a15c9bebcULL, 0x431d67c49c100d4cULL,
    0x4cc5d4becb3e42b6ULL, 0x597f299cfc657e2aULL, 0x5fcb6fab3ad6faecULL, 0x6c44198c4a475817ULL
};

// Padding
uint64_t getLenBits(const char* input){
    uint64_t len = 0;
    for(len = 0; input[len]; len++){
        ;
    }
    return len*8;
}

char readint128BE(uint64_t head, uint64_t tail, int n){
    if(n>=0 & n<=7){
        return (head >> (7*8-n*8)) & 0xff;
    }
    else if(n>=8 & n<=15){
        return (tail >> (7*8-n*8)) & 0xff;
    }
    else{
        puts("Error");
        exit(1);
    }
    
}

char* int128ToBE(uint64_t head, uint64_t tail){
    char* arr = (char*)malloc(16);

    if(arr == NULL){
        puts("Error while malloc!");
        exit(1);
    }

    for(int i=0; i<16; i++){
        arr[i] = readint128BE(head, tail, i);
    }
    return arr;
}

uint64_t getK_1(const char* message){
    uint64_t len = getLenBits(message);
    uint64_t m = 0;
    //printf("len:%llu\n", len);
    int64_t jde;
    jde = 896 + m*1024 - len;
    //printf("jde:%lld\n", jde);
    while( (jde = 896 + m*1024 - len) < 1){
        m++;
    }
    //printf("m:%llu\n", m);
    return 896 + m*1024 - len;
}

char * Padding(const char* message, uint64_t* BlockNum){
    uint64_t lb = getLenBits(message);
    uint64_t l = lb/8;

    //还没完成128位int的实现，暂时先这样
    char *parr = int128ToBE(0, lb);

    uint64_t k_1_b = getK_1(message);
    //printf("lb:%10llu l:%10llu\nk_1_b:%10llu\n", lb, l, k_1_b);
    uint64_t retlen = ((k_1_b+lb)/8 + 16);
    //printf("retlen:%10llu\n", retlen);
    *BlockNum = (k_1_b + lb + 128)/1024;
    //printf("Numof Block: %llu\n", *BlockNum);
    char *parrret = (char*)malloc(retlen);

    if(parrret == NULL){
        puts("Error while malloc Padding.");
        exit(1);
    }
    memset(parrret, 0, retlen);
    memcpy(parrret, message, l);
    memset(&parrret[l], 128, 1);
    memcpy(&parrret[(k_1_b+lb)/8], parr, 16);

    return parrret;
}

typedef struct {
    uint64_t m[16];
} M;

M * Parsing(const char* input, int BlockNum){
    M * pM = (M*)malloc(BlockNum*sizeof(M));

    memset(pM, 0, BlockNum*sizeof(M));
    memcpy((char*)pM, input, BlockNum*1024/8);

    return pM;
}

//Initial Hash Value(H0)
typedef struct {
    uint64_t h[8];
} H;

H H_0 = {
0xcbbb9d5dc1059ed8uLL, 
0x629a292a367cd507uLL, 
0x9159015a3070dd17uLL, 
0x152fecd8f70e5939uLL, 
0x67332667ffc00b31uLL, 
0x8eb44a8768581511uLL, 
0xdb0c2e0d64f98fa7uLL, 
0x47b5481dbefa4fa4uLL
};

//test
/*
int main(void){

    for(int i=0 ; i<5; i++){
        printf("%#x\n", H_0.h[i]);
    }

    return 0;
}
*/

uint64_t swap(uint64_t a){
    uint64_t b,c,d,e,f,g,h,i;
    b = (a&0xff);
    c = (a&0xff00)>>8;
    d = (a&0xff0000)>>16;
    e = (a&0xff000000)>>24;
    f = (a&0xff00000000)>>32;
    g = (a&0xff0000000000)>>40;
    h = (a&0xff000000000000)>>48;
    i = (a&0xff00000000000000)>>56;
    //printf("%016x\n%016x\n%016x\n%016x\n%016x\n%016x\n%016x\n%016x\n", b,c,d,e,f,g,h,i);
    return (b<<56)|(c<<48)|(d<<40)|(e<<32)|(f<<24)|(g<<16)|(h<<8)|(i);
}

// uint64_t W(int t, M* pm, int i){
//     if(t>=0 & t<=15){
//         return pm[i].m[t];
//     }
//     else if(t>=16 & t<=79){
//         ROTL(W(t-3,pm,i)^W(t-8,pm,i)^W(t-14,pm,i)^W(t-16,pm,i),1);
//         //ROTL(pm[i].m[t-3]^pm[i].m[t-8]^pm[i].m[t-14]^pm[i].m[t-16],1);
//     }
//     else{
//         puts("Error while message schedule");
//         exit(1);
//     }
// }


uint64_t* compileW(M* pm, int i){
    uint64_t* locpm = (uint64_t*)malloc(sizeof(uint64_t)*80);

    uint64_t tmp;

    memset(locpm, 0, 80);
    for(int t=0; t<16; t++){
        locpm[t] = swap(pm[i].m[t]);
    }
    for(int t=16; t<80; t++){
        tmp = lSigma_1_512(locpm[t-2]) + locpm[t-7] + lSigma_0_512(locpm[t-15]) + locpm[t-16];
        locpm[t] = tmp; 
        //W[i] = SHA1_ROTL((W[i - 3] ^ W[i - 8] ^ W[i - 14] ^ W[i - 16]), 1)
    }
    return locpm;
}

void HashComputation(const char* input){
    uint64_t N;
    //puts("Padding...");
    char *padded_input = Padding(input, &N);
    //puts("Padded");
    //puts("Parsing...");
    //printf("Numof Block: %lld\n", N);
    M * Marr = Parsing(padded_input, N);
    // for(int j=0; j<N; j++){
    //     for(int k=0; k<16; k++){
    //         printf("%016llx ", swap(Marr[j].m[k]));
    //     }
    //     putchar('\n');
    // }
    // puts("Parsed");

    //uint64_t retW[80];
    uint64_t* pW;

    H H = {
    0xcbbb9d5dc1059ed8, 
    0x629a292a367cd507, 
    0x9159015a3070dd17, 
    0x152fecd8f70e5939, 
    0x67332667ffc00b31, 
    0x8eb44a8768581511, 
    0xdb0c2e0d64f98fa7, 
    0x47b5481dbefa4fa4
    };

    uint64_t a, b, c, d, e, f, g, h;

    uint64_t T1, T2;

    for(int i=0; i<N; i++){
        // Prepare the message schedule
        //puts("compilingW...");
        pW = compileW(Marr, i);
        //puts("compiled");
        // for(int j=0; j<80; j++){
        //     printf("%016llx\n", (pW[j]));
        // }
        // init five working variables
        a = H.h[0];
        b = H.h[1];
        c = H.h[2];
        d = H.h[3];
        e = H.h[4];
        f = H.h[5];
        g = H.h[6];
        h = H.h[7];
    
        uint64_t tmp1, tmp2, tmp3, tmp4, tmp5, tmp6, tmp7;
        // 
        //puts("hashing...");
        for(int t=0; t<=79; t++){
            T1 = h + Sigma_1_512(e) + Ch(e, f, g) + K[t] + pW[t];
            T2 = Sigma_0_512(a) + Maj(a, b, c);
            h = g;
            g = f;
            f = e;
            e = d + T1;
            d = c;
            c = b;
            b = a;
            a = T1 + T2;

            //printf("%2d: %016llx %016llx %016llx %016llx\n    %016llx %016llx %016llx %016llx \n\n", t, a, b, c, d, e, f, g, h);

        }
        
        // update
        H.h[0] = a + H.h[0];
        H.h[1] = b + H.h[1];
        H.h[2] = c + H.h[2];
        H.h[3] = d + H.h[3];
        H.h[4] = e + H.h[4];
        H.h[5] = f + H.h[5];
        H.h[6] = g + H.h[6];
        H.h[7] = h + H.h[7];
    }

    printf("%016llx%016llx%016llx%016llx%016llx%016llx\n", H.h[0], H.h[1], H.h[2], H.h[3], H.h[4], H.h[5]);
    free(padded_input);
    free(Marr);
    free(pW);
}

int main(void){
    clock_t start, end;
    double duration;
    char m[1000001];
    memset(m, 0, 1000001);
    memset(m, 'a', 1000000);
    start = clock();
    HashComputation("abc");
    HashComputation("abcdefghbcdefghicdefghijdefghijkefghijklfghijklmghijklmnhijklmnoijklmnopjklmnopqklmnopqrlmnopqrsmnopqrstnopqrstu");
    HashComputation(m);
    end = clock();
    duration = (double)(end-start)/CLOCKS_PER_SEC;
    printf("time used:%f", duration);
    //printf("%#x\n", ROTL(1, 8));

}

// int main(void){
//     uint64_t x = 0x1234567890abcdef;
//     printf("%#llx\n", x);
//     uint64_t m = swap(x);
//     printf("%#llx\n", m);

//     return 0;
// }

参考

https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.180-4.pdf

fips180-2

本文作者： Taardis
本文链接： https://taardisaa.github.io/2022/03/17/SHA/
版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！