keccak256初探

keccak256初探

仅做了解

介绍 背景

以太坊在许多地方使用_Keccak-256_加密哈希函数。Keccak-256被设计为于2007年举行的SHA-3密码哈希函数竞赛的候选者。Keccak是获胜的算法，在2015年被标准化为 FIPS（联邦信息处理标准）。

不过NIST接受原始的Keccak256设计后，更改了Padding的格式， 以太坊坚持使用了原始的方案，因为这一更改存在争议，导致了正式的SHA3实现和原始的Keccak不兼容。

用途

为了隐藏起某些信息，且保证这些信息不被篡改，需要用到哈希算法。keccak256算法则可以将任意长度的输入压缩成64位16进制的数，且哈希碰撞的概率近乎为0.

输出样例如下：

keccak256("aaaab");
//6e91ec6b618bb462a4a6ee5aa2cb0e9cf30f7a052bb467b0ba58b8748c00d2e5
keccak256("aaaac");
//b1f078126895a1424524de5321b339ab00408010b7cf0e6ed451514981e58aa9

实现原理 符号定义

Keccak算法使用以下符号与函数：

符号

r：比特率(比特 rate)，其值为每个输入块的长度
c：容量(capacity)，其长度为输出长度的两倍

b：向量的长度，b=r+c，而b的值依赖于指数I，即b=25×2I

整体架构

吸入与挤出 吸入主要是对输入进行补0 *** 作，挤出是将处理后的输出转为固定长度的输出，挤出的主要流程如下： Theta Step (θ)

  C[x] = A[x,0] xor A[x,1] xor A[x,2] xor A[x,3] xor A[x,4],   for x in 0…4
  D[x] = C[x-1] xor rot(C[x+1],1),                             for x in 0…4
  A[x,y] = A[x,y] xor D[x],                           for (x,y) in (0…4,0…4)

Rho (ρ) and Pi (π) Steps

  B[y,2*x+3*y] = rot(A[x,y], r[x,y]),                 for (x,y) in (0…4,0…4)

Chi (χ) Step

  A[x,y] = B[x,y] xor ((not B[x+1,y]) and B[x+2,y]),  for (x,y) in (0…4,0…4)

Iota (ι) Step

  A[0,0] = A[0,0] xor RC

代码

#include "keccak.h"
#include 
#include 

//rot(num, offset)表示将w比特的num向z轴正方向循环移动offset位。具体实现中，可以当成循环左移offset位
uint64_t Keccak::rot(uint64_t num, int offset) {
    if (offset == 0) {
        return num;
    }
    return (num << offset) | (num >> (64 - offset));
}

void Keccak::theta(uint64_t input[MAT][MAT], uint64_t output[MAT][MAT]) {
//    整行异或生成一个值，二维变一维
    for (int i = 0; i < MAT; ++i) {
        theta_C[i] = 0x0;
        for (int j = 0; j < MAT; ++j) {
            theta_C[i] ^= input[i][j];
        }
    }

//    之前得到的一维数组再次异或变换
    for (int i = 0; i < MAT; ++i) {
        theta_D[i] = theta_C[(i - 1 + MAT) % MAT] ^ rot(theta_C[(i + 1) % MAT], 1);
    }

//    输入数组与变换后的一维数组异或
    for (int i = 0; i < MAT; ++i) {
        for (int j = 0; j < MAT; ++j) {
            output[i][j] = input[i][j] ^ theta_D[i];
        }
    }
}

//将数组数组向z方向位移，再赋给输出
void Keccak::rho_pi(uint64_t input[MAT][MAT], uint64_t output[MAT][MAT]) {
  for (int i = 0; i < MAT; ++i) {
        for (int j = 0; j < MAT; ++j) {
            output[j][(2 * i + 3 * j) % MAT] = rot(input[i][j], R_CONS[i][j]);
        }
    }
    // printf("%lld\n", output[0][0]);
}

//取反异或
void Keccak::chi(uint64_t input[MAT][MAT], uint64_t output[MAT][MAT]) {
    for (int i = 0; i < MAT; ++i) {
        for (int j = 0; j < MAT; ++j) {
            output[i][j] = input[i][j] ^ ((~input[(i + 1) % MAT][j]) & input[(i + 2) % MAT][j]);
        }
    }
}

//首元素初始化
void Keccak::iota(uint64_t input[MAT][MAT], int round) {
    input[0][0] ^= RC[round];
}

void Keccak::keccak_f(int round) {
//    主要在做输入的异或变换
    theta(after_f, after_theta);
//   输入转输出
    rho_pi(after_theta, after_rho_pi);
//  取反异或
    chi(after_rho_pi, after_f);
//  首元素初始化
    iota(after_f, round);
}

unsigned char* Keccak::encrypt(unsigned char*seq, int seq_len) {
    uint8_t *pad_seq;
    int block;
    int pad_zero = 0;
    if ((seq_len + MIN_PAD) % r != 0) {
        pad_zero = r - (seq_len + MIN_PAD) % r;
    }
    block = (seq_len + MIN_PAD + pad_zero) / r;
//    输入字符串进行pad，补0
    pad_seq = new uint8_t[seq_len + MIN_PAD + pad_zero];
    memcpy(pad_seq, seq, seq_len);
//    输入字符串添加结束符P
    pad_seq[seq_len] = P;
    if (pad_zero > 0) {
        memset(pad_seq + seq_len + 1, 0, pad_zero);
    }

    pad_seq[seq_len + MIN_PAD + pad_zero - 1] |= 0x80;

    for (int i = 0; i < MAT; ++i) {
        for (int j = 0; j < MAT; ++j) {
            after_f[i][j] = 0;
        }
    }

    for (int i = 0; i < block; ++i) {
        int pos = 0;
        for (int j = i * r; j < (i + 1) * r; j += 8) {
            uint64_t t = 0;
            for (int k = j + 7; k >= j; --k) {
                t = (t << 8) | pad_seq[k];
            }
//            pad字符串转为二维数组
            after_f[pos % MAT][pos / MAT] ^= t;
            pos++;
        }
        for (int j = 0; j < nr; ++j) {
            keccak_f(j);
        }
    }

    for (int i = 0; i < output_len; ) {
        for (int j = 0; j < 8; ++j) {
            result[i] = after_f[(i / 8) % MAT][(i / 8) / MAT] & 0xff;
            after_f[(i / 8) % MAT][(i / 8) / MAT] >>= 8;
            i++;
            if (i >= output_len) {
                break;
            }
        }
    }
    return result;
}

//int main() {
//
//    unsigned char chs[7]  = "ssss1s";
//    uint8_t * temp ;
//    temp = Keccak("256").encrypt(chs, 6);
//
//    for (int i=0;i<256;i++){
//        printf("%d",temp[i]);
//    }
//
//    return 0;
//}

输出

通过海绵结构中的挤出阶段，可以获得任意长度的输出。在Keccak-224/256/384/512中，我们只需要获得y0中的前224/256/384/512个bit作为输出即可。

参考

现代密码学：Hash函数Keccak_ayang1986的博客-CSDN博客_keccak