「Keccak specifications summary」の翻訳と実装

# はじめに（Introduction）

SHA3をガチで理解しようとすると大変なので、とりあえず以下の仕様概要を翻訳して実装してみます。

https://keccak.team/keccak_specs_summary.html

# 翻訳（Traslate）

基本的に [Goggle翻訳](https://translate.google.com/) を使用していますが多少修正を入れています。

## Keccak仕様概要（Keccak specifications summary）

Keccak（[kɛtʃak] と発音します、「ケチャック」のように） は、SHAKE128 および SHAKE256 拡張可能な出力関数、cSHAKE128、cSHAKE256、および [NIST SP 800-185](https://keccak.team/specifications.html#SP_800_185) のその他の関数のように、[FIPS 202](https://keccak.team/specifications.html#FIPS_202) の SHA3-224 から SHA3-512 ハッシュ関数の形で標準化されたスポンジ関数のファミリーです。
以下のテキストは、疑似コードを使用した Keccak の簡単な説明です。
この紹介文は、決して Keccak の正式な参考説明としてみなされるべきではありません。
代わりに、ここでの目標は、読みやすさと明瞭さに重点を置いて Keccak を提示することです。 
より正式な説明については、[参照仕様](https://keccak.team/files/Keccak-reference-3.0.pdf)または [FIPS 202](https://keccak.team/specifications.html#FIPS_202) 標準を読むことをお勧めします。

補足として、次のような読みやすさと明瞭さに重点を置いたいくつかの単純な実装を確認することもできます。

- Markku-Juhani O. Saarinen の [tiny_sha3](https://github.com/mjosaarinen/tiny_sha3);
- [C](https://github.com/XKCP/XKCP/blob/master/Standalone/CompactFIPS202/C/Keccak-readable-and-compact.c) または [Python](https://github.com/XKCP/XKCP/blob/master/Standalone/CompactFIPS202/Python/CompactFIPS202.py) による独自の読みやすくコンパクトな実装。

### Keccakの構造（Structure of Keccak）

Keccak は[スポンジ構造](https://keccak.team/sponge_duplex.html)に基づいたハッシュ関数ファミリーであり、したがってスポンジ関数ファミリーです。
Keccak では、基礎となる関数は 7 つの Keccak-$f$ 順列のセットで選択された順列であり、Keccak-$f[b]$ で示されます。ここで、$b\in\set{25,50,100,200,400,800,1600}$ は順列の幅です。
順列の幅はスポンジ構造における状態（state）の幅でもあります。

状態（state）は、それぞれの長さ $w\in\set{1,2,4,8,16,32,64}$ および $b=25w$ の $5\times5$ レーンの配列として編成されます。
64 ビット プロセッサ上で実装すると、Keccak-$f[1600]$ のレーンは 64 ビット CPU ワードとして表現できます。

スポンジ構造を Keccak-$f[r+c]$ に適用し、メッセージ入力に特定のパディングを適用すると、パラメータ容量 $c$ とビットレート $r$ を持つ Keccak$[r,c]$ スポンジ関数が得られます。

### 順列の擬似コードの説明（Pseudo-code description of the permutations）

まず、以下の疑似コードの Keccak-$f$ の説明から始めます。
ラウンド数 $n$ は順列幅に依存し、 $n=12+2l$ ( $2^l=w$ ) で与えられます。
これにより、 Keccak-$f[1600]$ に 24 ラウンドが与えられます。

```
Keccak-f[b](A) {
  for i in 0…n-1
    A = Round[b](A, RC[i])
  return A
}

Round[b](A,RC) {
  # θ 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)

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

  # χ 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)

  # ι step
  A[0,0] = A[0,0] xor RC

  return A
}

```

上記の疑似コードでは、次の規則が使用されています。
インデックスに対するすべての演算は 5 を法として実行されます。
`A` は完全な順列状態配列を示し、`A[x,y]` はその状態（state）の特定のレーンを示します。
`B[x,y]`、`C[x]`、`D[x]`は中間変数です。
定数 `r[x,y]` は回転オフセット ([表 2](https://keccak.team/keccak_specs_summary.html#rotationOffsets) を参照) で、`RC[i]` はラウンド定数 ([表 1](https://keccak.team/keccak_specs_summary.html#roundConstants) を参照) です。
`rot(W,r)` は通常のビット単位の巡回シフト演算で、位置 `i` のビットを位置 `i+r` (レーン サイズを法とする) に移動します。

### スポンジ関数の疑似コードの説明（Pseudo-code description of the sponge functions）

次に、パラメータ容量 $c$ とビットレート $r$ を指定した Keccak$[r,c]$ スポンジ関数の疑似コードを示します。
簡単にするために、標準インスタンスの場合と同様に、$r$ がレーン サイズの倍数であると仮定します。

以下の説明では、入力 `M` がバイト列 `Mbytes` の後に後続ビット `Mbits` の数（おそらくゼロ、最大7）が続く形で表されると仮定します。
標準インスタンスでは通常、ドメイン分離のためにいくつかの末尾ビットが追加されます。
バイトで構成される場合、これらの関数の入力は `Mbytes` になりますが、`Mbits` は使用されるインスタンスによってのみ決定されます ([表 3](https://keccak.team/keccak_specs_summary.html#suffixes) を参照)。

```
Keccak[r,c](Mbytes || Mbits) {
  # Padding
  d = 2^|Mbits| + sum for i=0..|Mbits|-1 of 2^i*Mbits[i]
  P = Mbytes || d || 0x00 || … || 0x00
  P = P xor (0x00 || … || 0x00 || 0x80)

  # Initialization
  S[x,y] = 0,                               for (x,y) in (0…4,0…4)

  # Absorbing phase
  for each block Pi in P
    S[x,y] = S[x,y] xor Pi[x+5*y],          for (x,y) such that x+5*y < r/w
    S = Keccak-f[r+c](S)

  # Squeezing phase
  Z = empty string
  while output is requested
    Z = Z || S[x,y],                        for (x,y) such that x+5*y < r/w
    S = Keccak-f[r+c](S)

  return Z
}
```


上記の疑似コードでは、`d` は区切られたサフィックスであり、後続ビット `Mbits` とその長さをエンコードします。
パディングされたメッセージ `P` は、ブロック `Pi` の配列として編成され、それ自体がレーンの配列として編成されます。
変数 `S` は状態（state）をレーンの配列として保持します。
`||` 演算子は通常の文字列連結を示します。
詳細については、[ビットとバイトの規則](https://keccak.team/keccak_bits_and_bytes.html)に関するページも参照してください。

### 標準インスタンス（Standard instances）

標準インスタンスを定義するパラメータを次の表に示します。

表 3: 標準 FIPS 202 および SP 800-185 インスタンスのパラメーター。
`Mbits` と `d` の値は、これらの関数への入力がバイトで構成されていることを前提としています。

||$r$|$c$|Output<br> length<br> (bits)|Security<br> level<br> (bits)|`Mbits`|`d`|
|:--|--:|--:|--:|--:|:--|:--|
|SHAKE128|1344|256|unlimited|128|1111|`0x1F`|
|SHAKE256|1088|512|unlimited|256|1111|`0x1F`|
|SHA3-224|1152|448|224|112|01|`0x06`|
|SHA3-256|1088|512|256|128|01|`0x06`|
|SHA3-384|832|768|384|192|01|`0x06`|
|SHA3-512|576|1024|512|256|01|`0x06`|
|cSHAKE128|1344|256|unlimited|128|00|`0x04`|
|cSHAKE256|1088|512|unlimited|256|00|`0x04`|

容量 $c$ の値とサフィックス `Mbits` の値は共同して、異なるインスタンス間のドメイン分離を提供します。
Keccak への入力は決して衝突しないため、ドメインで分離されたインスタンスは無関係な出力を提供し、独立した関数として機能します。

[SP 800-185](https://keccak.team/specifications.html#SP_800_185) のカスタマイズ可能な拡張可能な出力関数 cSHAKE128 および cSHAKE256 には、独自のドメイン分離メカニズムがあります。
メイン入力に加えて、これらの関数は関数名入力 (NIST によって定義) およびカスタマイズ文字列入力 (ユーザー定義) を受け入れます。
これら 2 つの追加入力が両方とも空の文字列である場合、cSHAKE128 と cSHAKE256 は対応する SHAKE 関数にフォールバックします。
関数 KMAC128、KMACXOF128、TupleHash128、TupleHashXOF128、ParallelHash128、ParallelHashXOF128 は cSHAKE128 の上に定義されており、KMAC256、KMACXOF256、TupleHash256、TupleHashXOF256、ParallelHash256、ParallelHashXOF256 についても同様に定義されています。

### 付録（Appendices）

#### ラウンド定数（Round constants）

最大レーン サイズ 64 の場合のラウンド定数 `RC[i]` を以下の表に示します。
小さいサイズの場合は、単純に切り詰められます。
計算式は[参考仕様](https://keccak.team/files/Keccak-reference-3.0.pdf)に記載されています。

表 1: ラウンド定数 RC[i]


|||||
|:--|:--|:--|:--|
|RC[0]|0x0000000000000001|RC[12]|0x000000008000808B|
|RC[1]|0x0000000000008082|RC[13]|0x800000000000008B|
|RC[2]|0x800000000000808A|RC[14]|0x8000000000008089|
|RC[3]|0x8000000080008000|RC[15]|0x8000000000008003|
|RC[4]|0x000000000000808B|RC[16]|0x8000000000008002|
|RC[5]|0x0000000080000001|RC[17]|0x8000000000000080|
|RC[6]|0x8000000080008081|RC[18]|0x000000000000800A|
|RC[7]|0x8000000000008009|RC[19]|0x800000008000000A|
|RC[8]|0x000000000000008A|RC[20]|0x8000000080008081|
|RC[9]|0x0000000000000088|RC[21]|0x8000000000008080|
|RC[10]|0x0000000080008009|RC[22]|0x0000000080000001|
|RC[11]|0x000000008000000A|RC[23]|0x8000000080008008|

#### ローテーションオフセット（Rotation offsets）

ローテーションオフセット `r[x,y]` を以下の表に示します。
計算式は[参考仕様](https://keccak.team/files/Keccak-reference-3.0.pdf)に記載されています。

表 2: ローテーションオフセット

||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|14|18|2|61|
|y=3|21|8|41|45|15|

# 実装（Reference implementation）

JavaScriptで実装しようと思います。
基本的には疑似コードをそのまま実装します。（そのままの実装を見たことない・・・）
したがって、ちょっと使いづらいかもしれません。
（通常は、updateとdigestとか徐々に反映していくパターンが主流？）

## 準備（Preparation）

疑似コードに書かれていない部分を実装します。

__レーンサイズ__
レーンサイズは64ビット（$w=64$）となります、したがって状態（state）の幅は $b=1600$ となります。

__ラウンド数__
> ラウンド数 $n$ は順列幅に依存し、 $n=12+2l$ ( $2^l=w$ ) で与えられます。

本文にはラウンド数だけ書いてありますが、式から求めてみます。
$w=2^l=64$ より $l=6$ となり、$n=12+2\cdot6=24$ なのでラウンドは $24$ となります。

__rot関数__
> rot(W,r) は通常のビット単位の巡回シフト演算で、位置 i のビットを位置 i+r (レーン サイズを法とする) に移動します。

`rot`関数を作成します。
本実装では、JavaScriptの`BigInt`を利用するので、左シフトで64ビットMASKで必要な部分だけ取り出しています。

__ラウンド定数__
表１を定数としています。

__ローテーションオフセット__
表２を定数としています。
表２だと、$x$ と $y$ が順序になってないません。

```javascript
'use strict';

// lane lengths
const w = 64;

// This gives 24 rounds for Keccak-f[1600]
const ROUND = 24;

// rot(W,r) is the usual bitwise cyclic shift operation,
// moving bit at position i into position i+r (modulo the lane size).
function rot(W, r) {
    return ((W << r) & 0xffffffffffffffffn) + (W >> (64n - r));
}

// Table 1: The round constants RC[i]
const RC = [
    0x0000000000000001n, 0x0000000000008082n, 0x800000000000808An, 0x8000000080008000n,
    0x000000000000808Bn, 0x0000000080000001n, 0x8000000080008081n, 0x8000000000008009n,
    0x000000000000008An, 0x0000000000000088n, 0x0000000080008009n, 0x000000008000000An,
    0x000000008000808Bn, 0x800000000000008Bn, 0x8000000000008089n, 0x8000000000008003n,
    0x8000000000008002n, 0x8000000000000080n, 0x000000000000800An, 0x800000008000000An,
    0x8000000080008081n, 0x8000000000008080n, 0x0000000080000001n, 0x8000000080008008n,
];

// Table 2: the rotation offsets
const r = [
    [0n, 36n, 3n, 41n, 18n],
    [1n, 44n, 10n, 45n, 2n],
    [62n, 6n, 43n, 15n, 61n],
    [28n, 55n, 25n, 21n, 56n],
    [27n, 20n, 39n, 8n, 14n],
];
```

### 順列の実装（Implementation of permutations）

疑似コードとの違いについて解説します。

__状態（state）の幅（$b$）__
状態（state）の幅は $b=1600$ の固定なので、関数名に含めました。

__初期化__
変数の初期化を追加しています。

__インデックス__
> インデックスに対するすべての演算は 5 を法として実行されます。

とあるので、インデックスで演算のあるものは`% 5`を追加しています。
（一か所マイナスになる可能性があるので、あらかじめ `5` を加算しています。）

__ビット演算__
JavaScriptのビット演算子は `xor` は `^` 、 `not` は `~` となります。

```javascript
// Keccak-f[b](A) {
function Keccak_f1600(A) {
    // for i in 0…n-1
    for (let i = 0; i < ROUND; i++) {
        // A = Round[b](A, RC[i])
        A = Round1600(A, RC[i]);
    }
    // return A
    return A;
    // }
}

// Round[b](A,RC) {
function Round1600(A, RC) {
    let C = [0n, 0n, 0n, 0n, 0n];
    let D = [0n, 0n, 0n, 0n, 0n];

    // # θ 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
    for (let x = 0; x < 5; x++) {
        C[x] = A[x][0] ^ A[x][1] ^ A[x][2] ^ A[x][3] ^ A[x][4];
    }
    // D[x] = C[x-1] xor rot(C[x+1],1),                             for x in 0…4
    for (let x = 0; x < 5; x++) {
        D[x] = C[(5 + x - 1) % 5] ^ rot(C[(x + 1) % 5], 1n);
    }
    // A[x,y] = A[x,y] xor D[x],                           for (x,y) in (0…4,0…4)
    for (let y = 0; y < 5; y++) {
        for (let x = 0; x < 5; x++) {
            A[x][y] = A[x][y] ^ D[x];
        }
    }

    let B = [
        [0n, 0n, 0n, 0n, 0n],
        [0n, 0n, 0n, 0n, 0n],
        [0n, 0n, 0n, 0n, 0n],
        [0n, 0n, 0n, 0n, 0n],
        [0n, 0n, 0n, 0n, 0n],
    ];

    // # ρ and π steps
    // B[y,2*x+3*y] = rot(A[x,y], r[x,y]),                 for (x,y) in (0…4,0…4)
    for (let y = 0; y < 5; y++) {
        for (let x = 0; x < 5; x++) {
            B[y][(2 * x + 3 * y) % 5] = rot(A[x][y], r[x][y]);
        }
    }

    // # χ 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)
    for (let y = 0; y < 5; y++) {
        for (let x = 0; x < 5; x++) {
            A[x][y] = B[x][y] ^ ((~B[(x + 1) % 5][y]) & B[(x + 2) % 5][y]);
        }
    }

    // # ι step
    // A[0,0] = A[0,0] xor RC
    A[0][0] = A[0][0] ^ RC;

    // return A
    return A;
    // }
}
```

### スポンジ関数の実装（Implementation of sponge function）

疑似コードとの違いについて解説します。

__関数の引数__
（`r`、`c`、`Mbytes`、`Mbits`） から  （`r`、`OutputLength`、`Mbytes`、`d`） に変更しています。
`c` は、`r+c` で使われていますが、__1600__ 固定なので不要としました。
`SHAKE128`、`SHAKE256` などは出力のビット数が可変なので、`OutputLength` を追加しました。
`Mbits`は `d` を生成する為に使われます、疑似コードに `Mbits` から `d` を生成するロジックが記述されていますが、表３に生成後の値が記載されているのでそれを使用します。

__パティング（ `P` の長さ）__
ビットレート `r` をレーン長 `w` 毎に区切るので、`r/w` の倍数分のレーン長が必要です。
レーン長 `w` あたり `w/8` バイト必要です。
したがって、バイト配列 `P` の長さは、`r/w*(w/8)` なので `r/8` の倍数分必要です。

__`P`からブロック`Pi`の生成__
`P` から `r/8` バイト分が１ブロックとなります。
`r/8` バイトから レーン長 `w` 毎（`w=64`ビット、`64/8=8`バイト）に分割します。
`Pi` の各値はレーン長 `w` （`64`ビット、`8`バイト）を __リトルエンディアン__ でBigIntに変換します。
したがって、`Pi` はのBigInt配列です。

__状態（state）から出力の生成__
状態（state）は、長さ $w=64$ の $5\times5$ レーンの配列（BigInt）なので、これを出力（16進数）に変換します。
`S[0][0],S[1][0],...` の順番に指定された出力長まで変換していきます。
状態（state）の各値は、__リトルエンディアン__ のBigIntとして出力します。


```javascript
// Keccak[r, c](Mbytes || Mbits) {
function Keccak(r, OutputLength, Mbytes, d) {
    // # Padding
    // d = 2 ^| Mbits | + sum for i = 0..| Mbits | -1 of 2 ^ i * Mbits[i]
    // P = Mbytes || d || 0x00 || … || 0x00
    let P = [];
    for (let i = 0; i < Mbytes.length; i++) {
        P.push(Mbytes[i] & 0xff);
    }
    P.push(d);
    while (P.length % (r / 8) != 0) {
        P.push(0);
    }
    // P = P xor(0x00 || … || 0x00 || 0x80)
    for (let i = 0; i < P.length - 1; i++) {
        P[i] = P[i] ^ 0x00;
    }
    P[P.length - 1] = P[P.length - 1] ^ 0x80;

    // # Initialization
    // S[x, y] = 0,                               for (x, y) in (0…4, 0…4)
    let S = [
        [0n, 0n, 0n, 0n, 0n],
        [0n, 0n, 0n, 0n, 0n],
        [0n, 0n, 0n, 0n, 0n],
        [0n, 0n, 0n, 0n, 0n],
        [0n, 0n, 0n, 0n, 0n],
    ];

    // # Absorbing phase
    // for each block Pi in P
    for (let i = 0; i < P.length; i += (r / 8)) {
        let Pi = [];
        for (let j = 0; j < (r / 8); j += 8) {
            let bi = 0n;
            for (let k = 0; k < 8; k++) {
                bi = bi << 8n;
                bi = bi + BigInt(P[i + j + (7 - k)]);
            }
            Pi.push(bi);
        }
        //   S[x, y] = S[x, y] xor Pi[x + 5 * y],          for (x, y) such that x + 5 * y < r / w
        for (let y = 0; y < 5; y++) {
            for (let x = 0; x < 5; x++) {
                if (x + 5 * y < r / w) {
                    S[x][y] = S[x][y] ^ Pi[x + 5 * y];
                }
            }
        }
        // S = Keccak - f[r + c](S)
        S = Keccak_f1600(S);
    }

    // # Squeezing phase
    // Z = empty string
    let Z = "";
    // while output is requested
    let blakeFlg = false;
    while (!blakeFlg) {
        // Z = Z || S[x, y],                        for (x, y) such that x + 5 * y < r / w
        outlen: for (let y = 0; y < 5; y++) {
            for (let x = 0; x < 5; x++) {
                if (x + 5 * y < r / w) {
                    for (let i = 0n; i < 8n; i++) {
                        Z = Z + ((S[x][y] >> (i * 8n)) & 0xffn).toString(16).padStart(2, "0");
                        if (Z.length == (OutputLength / 8) * 2) {
                            blakeFlg = true;
                            break outlen;
                        }
                    }
                }
            }
        }
        if (!blakeFlg) {
            // S = Keccak - f[r + c](S)
            S = Keccak_f1600(S);
        }
    }

    // return Z
    return Z;
    // }
}
```

### ハッシュ関数の実装（Implementation of hash function）

表３から関数を生成します。
`SHA3_224`、`SHA3_384`、`SHA3_256`、`SHA3_512` は引数 `Mbytes` を持ちます。
`SHAKE128` と `SHAKE128` は出力が可変長なので引数に `OutputLength` が追加されています。

```javascript
function SHAKE128(Mbytes, OutputLength) {
    if (OutputLength % 8 != 0) {
        throw new Error("Illegal OutputLength");
    }
    return Keccak(1344, OutputLength, Mbytes, 0x1F);
}

function SHAKE256(Mbytes, OutputLength) {
    if (OutputLength % 8 != 0) {
        throw new Error("Illegal OutputLength");
    }
    return Keccak(1088, OutputLength, Mbytes, 0x1F);
}

function SHA3_224(Mbytes) {
    return Keccak(1152, 224, Mbytes, 0x06);
}

function SHA3_256(Mbytes) {
    return Keccak(1088, 256, Mbytes, 0x06);
}

function SHA3_384(Mbytes) {
    return Keccak(832, 384, Mbytes, 0x06);
}

function SHA3_512(Mbytes) {
    return Keccak(576, 512, Mbytes, 0x06);
}
```

### テスト（Test）

他の実装（[jsSHA](https://github.com/Caligatio/jsSHA)）と比べてます。

#### 準備（Preparing for the test）

テスト用データとして長さ0～1024までの`Uint8Array`のランダムな配列を生成します。

```javascript
const TEST_BYTES = [];

const TEST_LENGTH = 1024;

for (let i = 0; i <= TEST_LENGTH; i++) {
    let bs = new Uint8Array(i);
    for (let j = 0; j < bs.length; j++) {
        bs[j] = Math.floor(Math.random() * 256);
    }
    TEST_BYTES.push(bs);
}
```

#### SHA3関数のテスト（Testing SHA3 functions）

各テスト用データに対して、今回作成した関数から求めたハッシュ値と、[jsSHA](https://github.com/Caligatio/jsSHA) で求めた値と同じであるか判定します。

```javascript
const SHA3_FUNC = {
    224: SHA3_224,
    256: SHA3_256,
    384: SHA3_384,
    512: SHA3_512,
};

// TEST SHA3
for (let key in SHA3_FUNC) {
    console.log(">>> SHA3_" + key);
    let t1 = new Date();
    for (let i = 0; i < TEST_BYTES.length; i++) {
        let bs = TEST_BYTES[i];
        let hash1 = SHA3_FUNC[key](bs);
        let shaObj = new jsSHA("SHA3-" + key, "UINT8ARRAY");
        shaObj.update(bs);
        let hash2 = shaObj.getHash("HEX");
        if (hash1 != hash2) {
            console.log("Not Match!");
            let hex = Buffer.from(bs).toString("hex");
            console.log(hex);
            console.log(hash1);
            console.log(hash2);
            break;
        }
    }
    let t2 = new Date();
    console.log("<<< SHA3_" + key + " " + (t2.getTime() - t1.getTime()));
}
```

#### SHAKE関数のテスト（Testing SHAKE functions）

SHAKE関数は出力の長さが可変長なので、`8, 160, 256, 512, 1024, 2048` の中からランダムに出力の長さを選びます。
SHA3と同様に、各テスト用データに対して、今回作成した関数から求めたハッシュ値と、[jsSHA](https://github.com/Caligatio/jsSHA) で求めた値と同じであるか判定します。

```javascript
const SHAKE_FUNC = {
    "SHAKE128": SHAKE128,
    "SHAKE256": SHAKE256,
};

const LENGTH_LIST = [8, 160, 256, 512, 1024, 2048];

// TEST SHAKE
for (let key in SHAKE_FUNC) {
    console.log(">>> " + key);
    let t1 = new Date();
    for (let i = 0; i < TEST_BYTES.length; i++) {
        let len = LENGTH_LIST[Math.floor(Math.random() * LENGTH_LIST.length)];
        let bs = TEST_BYTES[i];
        let hash1 = SHAKE_FUNC[key](bs, len);
        let shaObj = new jsSHA(key, "UINT8ARRAY");
        shaObj.update(bs);
        let hash2 = shaObj.getHash("HEX", { outputLen: len });
        if (hash1 != hash2) {
            console.log("Not Match!");
            let hex = Buffer.from(bs).toString("hex");
            console.log(hex);
            console.log(hash1);
            console.log(hash2);
            break;
        }
    }
    let t2 = new Date();
    console.log("<<< " + key + " " + (t2.getTime() - t1.getTime()));
}
```

# keccak256とsha3の違い（Difference between keccak256 and sha3）

Ethereum 系で使われているハッシュ関数を keccak256 と呼ぶことにします。
今回実装した SHA3-256 とは結果が異なります。

経緯としては以下となるようです。

> Keccak（ケチャック）-256 は、2007年に NIST によって開催されて SHA-3 暗号ハッシュ関数のコンペに応募するために設計されました。
> Keccak はこのコンペで優勝し、のちに SHA-3 として採用され、2015年に FIPS 202 として標準化されました。
> ここで注意しないといけないのが、Keccak が SHA-3 として採用されましたが、 Keccak ＝ SHA-3 ではなく、Keccak から変更が加えられて SHA-3 になっています。
> そして、SHA-3 の標準化が大幅に遅れたため、イーサリアムでは Keccak の採用を決めたようです。

詳細は以下のリンク先を参照してください。

https://www.think-self.com/money/cryptocurrency/keccak-256/

違いを探したのですが、ちゃんとした仕様書は見つかりませんでした。（知っていたら教えてください！）
とりあえず、以下をみると `SHA3-256` では `0x06` を設定しているが、`keccak256` では `0x01` を設定しているようです。

https://ethereum.stackexchange.com/questions/30369/difference-between-keccak256-and-sha3

## keccak256関数の実装とテスト（Implementation and testing of keccak256 function）

どうやら、`SHA3-256` の `d` を `0x06` から `0x01` に変更すれば良さそうです。

```javascript
function Keccak_256(Mbytes) {
    return Keccak(1088, 256, Mbytes, 0x01);
}
```

テストも実行してみます。
比較するライブラリは [ethers](https://docs.ethers.org/) を利用します。

```javascript
// TEST Keccak
console.log(">>> Keccak_256");
let t1 = new Date();
for (let i = 0; i < TEST_BYTES.length; i++) {
    let bs = TEST_BYTES[i];
    let hash1 = "0x" + Keccak_256(bs);
    let hash2 = ethers.keccak256(bs);
    if (hash1 != hash2) {
        console.log("Not Match!");
        let hex = Buffer.from(bs).toString("hex");
        console.log(hex);
        console.log(hash1);
        console.log(hash2);
        break;
    }
}
let t2 = new Date();
console.log("<<< Keccak_256 " + (t2.getTime() - t1.getTime()));
```

# まとめ（Conclusion）

とりあえず、翻訳と実装をしてみました。
SHA2ほどではないですが、案外短いコードで書けると思いました。

ただ、中身（スポンジ構造など）を理解するには [参照仕様](https://keccak.team/files/Keccak-reference-3.0.pdf) や [FIPS 202](https://keccak.team/specifications.html#FIPS_202) 標準 を読む必要がありそうです。