Hash函數(shù)的核心在于設(shè)計(jì)壓縮函數(shù)「宕妫可以證明，如果壓縮函數(shù)具有抗碰撞能力瞳秽，那么迭代Hash函數(shù)也具有抗碰撞能力瓣履。
2007年起，NIST開始向全球征集新的安全Hash算法SHA-3寂诱，最后的優(yōu)勝者是Keccak拂苹。Keccak以及SHA-3在正式成為標(biāo)準(zhǔn)之前有很多不同程度的更改，我想這也是網(wǎng)上有關(guān)Keccak和SHA-3算法的資料都多多少少不太一致的原因痰洒。本文僅介紹Keccak-224/256/384/512，以當(dāng)前Keccak官網(wǎng)中的算法描述為準(zhǔn)浴韭。參考文獻(xiàn)中列出了該算法的一些詳細(xì)描述丘喻，需要說明的是，除官網(wǎng)外的參考文獻(xiàn)都與官網(wǎng)中的描述有些出入念颈，請(qǐng)仔細(xì)甄別泉粉。
整體描述
Keccak算法采用海綿結(jié)構(gòu)（sponge construction），在預(yù)處理（padding并分成大小相同的塊）后榴芳，海綿結(jié)構(gòu)主要分成兩部分：
- 吸入階段（absorbing phase）：將塊x_i傳入算法并處理嗡靡。
- 擠出階段（squeezing phase）：產(chǎn)生一個(gè)固定長(zhǎng)度的輸出。
Keccak算法的整體結(jié)構(gòu)如圖：
在這兩個(gè)階段要是使用同一個(gè)壓縮函數(shù)Keccak-f窟感，下圖展示了算法“吸入”一個(gè)塊x_i并處理讨彼，最后擠出輸出的過程：
從圖中我們可以歸納出大致的流程：
- 對(duì)輸入串x做padding，使其長(zhǎng)度能被r整除柿祈，將padding后分割成長(zhǎng)度為r的塊哈误，即x=x_0||x_1||x_2||...||x_t-1。
- 初始化一個(gè)長(zhǎng)度為r+c bit的全零向量躏嚎。
- 輸入塊x_i蜜自，將x_i和向量的前r個(gè)bit亦或，然后輸入到Keccak-f函數(shù)中處理卢佣。
- 重復(fù)上一步重荠，直至處理完x中的每個(gè)塊。
- 輸出長(zhǎng)為r的塊作為y_0虚茶，并將向量輸入到Keccak-f函數(shù)中處理戈鲁，輸出y_1仇参，以此類推。得到的Hash序列即為y=y_0||y_1||y_2||...||y_u荞彼。在Keccak-224/256/384/512中冈敛，只需要在y_0中取出對(duì)應(yīng)長(zhǎng)度的前綴即可。
針對(duì)圖中的參數(shù)鸣皂，做出如下定義：
- r：比特率（bit rate）抓谴，其值為每個(gè)輸入塊的長(zhǎng)度。
- c：容量（capacity）寞缝，其長(zhǎng)度為輸出長(zhǎng)度的兩倍癌压。
- b：向量的長(zhǎng)度，b=r+c荆陆。b的值依賴于指數(shù)l滩届，即b=25*(2^l)。當(dāng)l=0,1時(shí)被啼，b=25,50帜消。由于這時(shí)b太小，通常不能作為實(shí)際算法使用浓体。在本文中泡挺，取l=6，b=1600命浴。
在Keccak-224/256/384/512中娄猫，b、r生闲、c及輸出長(zhǎng)度的取值見下表媳溺。
| b/bits | r/bits | c/bits | 輸出長(zhǎng)度/bits | 安全級(jí)別/bits |
|---|---|---|---|---|
| 1600 | 1152 | 448 | 224 | 112 |
| 1600 | 1088 | 512 | 256 | 128 |
| 1600 | 832 | 768 | 384 | 192 |
| 1600 | 576 | 1024 | 512 | 256 |
Padding
由于目前計(jì)算機(jī)大多按照字節(jié)尋址，輸入的最小單位為字節(jié)碍讯，因此以下的描述中默認(rèn)輸入bit長(zhǎng)度能整除8悬蔽。
按照官網(wǎng)的描述，padding偽代碼如下：
P = Mbytes || d || 0x00 || … || 0x00
P = P xor (0x00 || … || 0x00 || 0x80)
Mbytes為輸入串冲茸，“||”符號(hào)表示比特串串聯(lián)屯阀。在SHA3的標(biāo)準(zhǔn)中，d為0x06轴术。由于Keccak中按照字節(jié)序?yàn)樾《四阉ィ陨厦枋鱿喈?dāng)于在輸入比特串后接0110*1以將長(zhǎng)度補(bǔ)齊到能被r整除。關(guān)于Keccak中字節(jié)序的問題可以參考官網(wǎng)中的Bits and bytes in Keccak逗栽。
壓縮函數(shù)Keccak-f
壓縮函數(shù)以b比特作為輸入盖袭，b比特作為輸出。內(nèi)部結(jié)構(gòu)如下：
Keccak-f包含n_r輪。n_r的取值與我們之前計(jì)算b時(shí)用到的指數(shù)l有關(guān)鳄虱，具體地弟塞，n_r=12+2*l。Keccak-224/256/384/512中拙已，取l=6决记，因此n_r=24。在每一輪中倍踪，要以此執(zhí)行五步系宫，即θ(theta)、ρ(rho)建车、π(pi)扩借、χ(chi)、ι(iota)缤至。在處理過程中潮罪，我們把b=1600個(gè)比特排列成一個(gè)5*5*w的矩陣，其中w=2^l=64比特领斥，如圖：
接下來嫉到，我們來描述這五步的具體內(nèi)容。
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)
該步驟的輸入輸出均存在A矩陣中月洛。額外說明一點(diǎn)是屯碴，rot(num, offset)表示將w比特的num向z軸正方向循環(huán)移動(dòng)offset位。具體實(shí)現(xiàn)中膊存，可以當(dāng)成循環(huán)左移offset位，我在代碼中的實(shí)現(xiàn)如下：
uint64_t Keccak::rot(uint64_t num, int offset) {
if (offset == 0) {
return num;
}
return (num << offset) | (num >> (64 - offset));
}
（一個(gè)玄學(xué)問題：zp同學(xué)向我指出忱叭，如果不加offset==0的特判隔崎，當(dāng)offset==0時(shí)，num>>64的值不一定為0韵丑，而是一個(gè)不確定的值爵卒，這會(huì)導(dǎo)致該函數(shù)的輸出錯(cuò)誤。但是我加不加特判對(duì)結(jié)果的正確性沒有影響撵彻。為了保險(xiǎn)起見钓株，這里還是將特判加上了。）
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)
該步的輸入為A數(shù)組陌僵，輸出為B數(shù)組轴合。rot含義同上一步，其中作為offset的r數(shù)組定義如下：
| x=3 | x=4 | x=0 | x=1 | x=2 | |
|---|---|---|---|---|---|
| y=2 | 25 | 39 | 3 | 10 | 43 |
| y=1 | 55 | 20 | 36 | 44 | 6 |
| y=0 | 28 | 27 | 0 | 1 | 62 |
| y=4 | 56 | 18 | 14 | 2 | 61 |
| y=3 | 21 | 8 | 41 | 45 | 15 |
代碼中定義如下：
const int R_CONS[MAT][MAT] = {
{0, 36, 3, 41, 18},
{1, 44, 10, 45, 2},
{62, 6, 43, 15, 61},
{28, 55, 25, 21, 56},
{27, 20, 39, 8, 14}};
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)
該步驟中碗短，輸入為B矩陣受葛，輸出為A矩陣。
Iota (ι) Step
A[0,0] = A[0,0] xor RC
該步驟輸入和輸出均為A矩陣。RC值與輪數(shù)有關(guān)总滩，RC在24輪中的定義如下：
const uint64_t RC[nr] = {
0x0000000000000001, 0x0000000000008082, 0x800000000000808A, 0x8000000080008000,
0x000000000000808B, 0x0000000080000001, 0x8000000080008081, 0x8000000000008009,
0x000000000000008A, 0x0000000000000088, 0x0000000080008009, 0x000000008000000A,
0x000000008000808B, 0x800000000000008B, 0x8000000000008089, 0x8000000000008003,
0x8000000000008002, 0x8000000000000080, 0x000000000000800A, 0x800000008000000A,
0x8000000080008081, 0x8000000000008080, 0x0000000080000001, 0x8000000080008008};
輸出
通過海綿結(jié)構(gòu)中的擠出階段纲堵，可以獲得任意長(zhǎng)度的輸出。在Keccak-224/256/384/512中闰渔，我們只需要獲得y0中的前224/256/384/512個(gè)bit作為輸出即可席函。
具體實(shí)現(xiàn)
最后，附上Keccak的代碼實(shí)現(xiàn)冈涧。在使用時(shí)茂附，通過Keccak("224")（或"256" "384" "512"）來指定Keccak的類型并初始化。通過uint8_t* encrypt(uint8_t *seq, int len);函數(shù)來獲得Hash序列炕舵。其中seq為輸入串（以字節(jié)為單位）何之，len為輸入的長(zhǎng)度（以字節(jié)為單位）。
keccak.h：
#include <cstdio>
#include <string>
#include <cstdint>
#include <iostream>
class Keccak {
const int b = 200;
int r, c; // In bytes
uint8_t P;
static const int nr = 24;
const int w = 64;
int output_len;
static const int MAT = 5;
const int R_CONS[MAT][MAT] = {
{0, 36, 3, 41, 18},
{1, 44, 10, 45, 2},
{62, 6, 43, 15, 61},
{28, 55, 25, 21, 56},
{27, 20, 39, 8, 14}};
const uint64_t RC[nr] = {
0x0000000000000001, 0x0000000000008082, 0x800000000000808A, 0x8000000080008000,
0x000000000000808B, 0x0000000080000001, 0x8000000080008081, 0x8000000000008009,
0x000000000000008A, 0x0000000000000088, 0x0000000080008009, 0x000000008000000A,
0x000000008000808B, 0x800000000000008B, 0x8000000000008089, 0x8000000000008003,
0x8000000000008002, 0x8000000000000080, 0x000000000000800A, 0x800000008000000A,
0x8000000080008081, 0x8000000000008080, 0x0000000080000001, 0x8000000080008008};
const int MIN_PAD = 1;
uint64_t theta_C[MAT];
uint64_t theta_D[MAT];
uint64_t after_theta[MAT][MAT];
uint64_t after_rho_pi[MAT][MAT];
uint64_t after_chi[MAT][MAT];
uint64_t after_f[MAT][MAT];
public:
Keccak(std::string type) {
if (type == "224") {
output_len = 28;
c = 56;
// P = 0xCC;
} else if (type == "256") {
output_len = 32;
c = 64;
// P = 0xEC;
} else if (type == "384") {
output_len = 48;
c = 96;
// P = 0xCC;
} else if (type == "512") {
output_len = 64;
c = 128;
// P = 0xEC;
} else {
printf("Wrong type!\n");
}
P = 0x06;
r = b - c;
}
private:
uint64_t rot(uint64_t num, int offset);
void theta(uint64_t input[MAT][MAT], uint64_t output[MAT][MAT]);
void rho_pi(uint64_t input[MAT][MAT], uint64_t output[MAT][MAT]);
void chi(uint64_t input[MAT][MAT], uint64_t output[MAT][MAT]);
void iota(uint64_t input[MAT][MAT], int round);
void keccak_f(int round);
public:
uint8_t result[64];
uint8_t* encrypt(uint8_t *seq, int len);
};
keccak.cpp：
#include "keccak.h"
#include <cstring>
#include <cstdio>
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];
}
}
}
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);
}
uint8_t* Keccak::encrypt(uint8_t *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_seq = new uint8_t[seq_len + MIN_PAD + pad_zero];
memcpy(pad_seq, seq, seq_len);
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];
}
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;
}
參考文獻(xiàn)
- Keccak官網(wǎng)
- Keccak算法介紹與分析 （注：本文中的padding方法和官網(wǎng)不一致）
- SHA-3 and The Hash Function Keccak（注：本文中的r咽筋、c的設(shè)置以及padding方法和官網(wǎng)不一致）
文中圖片均來自參考文獻(xiàn)[3]溶推，偽代碼均來自參考文獻(xiàn)[1]。
