Keccak256(SHA3-256) を実装したので備忘録

## TL;DR
Keccak256というハッシュ関数をご存知でしょうか。Ethereumで使われているアレです。公開鍵からアドレスを導出するのに使われている奴です。SHA3-256とも呼ばれる奴です。
Pythonなどのいくつかの言語では標準のライブラリに入っていたりしますが、未実装の言語もまだまだ多いです。

```python:Pythonだと標準で使える
>>> from hashlib import sha3_256
>>> sha3_256(b'Hello, World!!').hexdigest()
'a2590767a13b13c73ac7388ba21ea6403f9833e9436209da7baa67d9c6b259f5'
```

SHA3(Secure Hash Algorithm 3)と呼ばれていますが、SHA2のような以前のSHAとは根本的にアルゴリズムの設計が異なります。SHA-256とSHA3-256は似たような名前ですが、全くの別物です(対照的に、SHA1およびSHA2はSHA0の改良系です)。

本稿は、このSHA3-256を実装することで一定の理解を得ることを目的としています。

## 実装の前に
本稿では、Nim言語を実装に用います。また、Keccak256を実装するにあたって、あらかじめ以下の型を定義しておきます。

```nim
type
    HashWords {.union.} = object
        words: array[5, array[5, uint64]]
        bytes: array[200, uint8]

    HashState = ref object
        hw: HashWords
        reading: 0..135
```

## アルゴリズム構造
Keccakの中核を成すのは、${\rm Keccak-}f_{[b]}$　という関数です。$b$はパラメータで、内部状態のサイズを表します。Keccak256においては$b = 1600_{\rm [bits]}$で、200バイトとなります。また、内部状態はあらかじめ0で初期化されます。

```nim
proc keccakF1600(state: var HashState) =
    ## keccak-f関数
    # 1回あたり24ラウンド処理する
    for i in 0..23:
        round(state, i)
```

${\rm Keccak-}f_{[b]}$ 関数は、内部状態に対して単純に$\rm round_{[{\it b}]}$関数を24回適用(計算)する関数です。
さらにこの${\rm round}_{[b]}$関数は、$\theta$過程、$\rho$過程、$\pi$過程、$\chi$過程および$\iota$過程の5段階で構成されています。

全体の流れを見てみます。Keccakは大きく分けて2つの処理過程を持つアルゴリズムです。
最初の段階は、**absorb**です。その名の通り、データを内部状態に吸収していきます。Keccak256においては、データは17個の64bit整数、つまり136バイトを1ブロックとして処理します。

absorb過程では、入力を1ブロックづつ内部状態とXORし、それを${\rm Keccak-}f_{[1600]}$にかけた結果で内部状態を上書きしていきます。

```nim
proc update(state: var HashState, bytes: openArray[uint8]) =
    ## absorb過程
    for c in bytes:
        # バイト単位で内部状態とxor
        state.hw.bytes[state.reading] = state.hw.bytes[state.reading] xor c
        # ブロックに書き込んだバイト数を更新する
        # 136バイトづつなので、135の次は0に戻る
        state.reading = if (state.reading == 135): 0 else: state.reading + 1

        # 1ブロック分読み込んだら keccak-f関数にかける
        if state.reading == 0:
            state.keccakF1600()
```

1ブロックに満たない場合パティングをおこないますが、丁度1ブロックとなる場合でも**パディング自体は行われ**、この場合は1ブロック分がまるまるパディングされます。
パディング処理は単純です。読み込んだバイト列の終端の1つ次(1ブロックちょうどであった場合は先頭)をある定数(Keccak256の場合は`0x06`)とし、ブロックの最後を`0x80`、それ以外の中間のバイト列を`0x00`とします。
例外的に、最後の入力データが135バイトあった場合、パディングとなる1バイトは定数と`0x80`をXORして求めたものとなります。

```nim
proc padding(state: var HashState) =
    state.hw.bytes[state.reading] = state.hw.bytes[state.reading] xor 0x06
    state.hw.bytes[135] = state.hw.bytes[135] xor 0x80

    state.keccakF1600()
```

さて、2つめの過程は**sqeeze**です。sqeeze過程では、実際のハッシュ値を求めます。とはいっても、Keccak256の場合は内部状態を先頭から32バイト分読み出すだけでハッシュ値がもとまります。136バイトを超える長さが必要な場合は、136バイトごとに${\rm Keccak-}f_{[b]}$関数を適用してまた先頭から読み出します。

```nim
proc digest(state: var HashState): string =
    ## ハッシュ値を計算する関数
    ## 一度計算すると内部状態が壊れ、再度初期化されます。
    # パディングする
    state.padding()

    # 戻り値を空文字列で初期化
    result = ""

    # 32バイト分出力文字列に追加
    for i in 0..31:
        result.add(cast[char](state.hw.bytes[i]))

    # 内部状態を再初期化
    state.reading = 0
    for i in 0..24:
        state.hw.words[i] = 0
```

これで処理の大まかな流れはおしまいです。

### round関数
round関数の中身について説明します。この関数は、5つの過程から成ります。

#### Theta過程
この過程は、2つの内部変数を利用します。

```nim
var c: array[5, uint64]
var d: array[5, uint64]
```

$\theta$過程では、まず25個のuint64で表現される内部状態を5個のuint64に圧縮します。

```nim
for x in 0..4:
    c[x] = state.hw.words[0][x] xor state.hw.words[1][x] xor state.hw.words[2][x] xor state.hw.words[3][x] xor state.hw.words[4][x]
```

次に、それを攪拌します。

```nim
for i in 0..4:
    d[i] = c[(i + 4) mod 5] xor rot64(c[(i + 1) mod 5], 1)
```

ちょっとわかりにくいので、for文を展開してみます。

```nim
d[0] = c[4] xor rot64(c[1], 1)
d[1] = c[0] xor rot64(c[2], 1)
d[2] = c[1] xor rot64(c[3], 1)
d[3] = c[2] xor rot64(c[4], 1)
d[4] = c[3] xor rot64(c[0], 1)
```

`rot64`は64bit整数をnビット分左に「回す」処理です：

```nim:rot64
proc rot64(x: uint64, k: uint64): uint64 = (x shl k) or (x shr (64 - k))
```

たとえば、`rot64(0x000000000000000F, 4)`は`0xF000000000000000`です。

最後に、それを内部状態に戻せば終わりです。

```nim
for x in 0..4:
    for y in 0..4:
        state.hw.words[y][x] = state.hw.words[y][x] xor d[x]
```

#### Rho過程
$\rho$過程では、25個それぞれの内部状態をテーブルに従って「回し」ます。ここで利用する`rot64`関数は先に上げたものと同じです。

```nim
for x in 0..4:
    for y in 0..4:
        state.hw.words[y][x] = rot64(state.hw.words[y][x], rotOffsets[y][x])
```

オフセット(`rotOffset[y][x]`)は以下のように定義されます。

```nim
const rotOffsets: array[25, uint64] = [
    [ 0'u64,  1'u64, 62'u64, 28'u64, 27'u64],
    [36'u64, 44'u64,  6'u64, 55'u64, 20'u64],
    [ 3'u64, 10'u64, 43'u64, 25'u64, 39'u64],
    [41'u64, 45'u64, 15'u64, 21'u64,  8'u64],
    [18'u64,  2'u64, 61'u64, 56'u64, 14'u64],
]
```

#### Pi過程
$\pi$過程では、内部状態をシャッフルします。

```nim
let copy: array[5, array[5, uint64]]

for x in 0..4:
    for y in 0..4:
        copy[y][x] = state.hw.words[y][x]

for x in 0..4:
    for y in 0..4:
        state.hw.words[(2*x + 3*y) mod 5][y] = copy[y][x]
```

どの要素がどこに移されるのかを有向グラフで表現してみました。$\pi$過程を1回行うごとに要素が1つずつ矢印の先へと移ります。

![shuffle.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/209421/e554f826-4ade-0d4a-b703-56ad48e48789.png)

たとえば、`state.hw.words[1][1]`は`state.hw.words[1][0]`に移ります。`state.hw.words[0][0]`や`state.hw.words[3][1]`などは移動しません。

#### Chi過程
$\chi$過程では、それぞれの要素をもう一度攪拌します。

```nim
let copy: array[5, array[5, uint64]]

for x in 0..4:
    for y in 0..4:
        copy[y][x] = state.hw.words[y][x]

for x in 0..4:
    for y in 0..4:
        let val = (not copy[y][(x + 1) mod 5]) and b[y][(x + 2) mod 5]
        state.hw.words[y][x] = copy[y][x] xor val
```

`and`および`not`はそれぞれbitwise and、bitwise notです。

#### Iota過程
最後に$\iota$過程です。この過程では、24ラウンドのそれぞれに固有の定数を利用します。
単純にこの定数と内部変数の先頭と`xor`して先頭に上書きすれば完了です。

```nim
state.hw.words[0][0] = state.hw.words[0][0] xor iotaConstants[roundN]
```

このときに利用する定数を以下に示します。

```nim
const iotaConstants: array[24, uint64] = [
        0x0000000000000001'u64, 0x0000000000008082'u64, 0x800000000000808a'u64,
        0x8000000080008000'u64, 0x000000000000808b'u64, 0x0000000080000001'u64,
        0x8000000080008081'u64, 0x8000000000008009'u64, 0x000000000000008a'u64,
        0x0000000000000088'u64, 0x0000000080008009'u64, 0x000000008000000a'u64,
        0x000000008000808b'u64, 0x800000000000008b'u64, 0x8000000000008089'u64,
        0x8000000000008003'u64, 0x8000000000008002'u64, 0x8000000000000080'u64,
        0x000000000000800a'u64, 0x800000008000000a'u64, 0x8000000080008081'u64,
        0x8000000000008080'u64, 0x0000000080000001'u64, 0x8000000080008008'u64,
]
```

`round`関数は以上です。

## Keccak256の全体像
最後に、ここまで実装してきた内容をまとめます。
以下に示すコードでは、モジュールとして使えるようにするための微修正と、ちょっとした最適化が入っています。

```nim
type
    HashWords {.union.} = object
        words: array[25, uint64]
        bytes: array[200, uint8]

    HashState* = ref object
        hw: HashWords
        reading: 0..135

const iotaConstants: array[24, uint64] = [
        0x0000000000000001'u64, 0x0000000000008082'u64, 0x800000000000808a'u64,
        0x8000000080008000'u64, 0x000000000000808b'u64, 0x0000000080000001'u64,
        0x8000000080008081'u64, 0x8000000000008009'u64, 0x000000000000008a'u64,
        0x0000000000000088'u64, 0x0000000080008009'u64, 0x000000008000000a'u64,
        0x000000008000808b'u64, 0x800000000000008b'u64, 0x8000000000008089'u64,
        0x8000000000008003'u64, 0x8000000000008002'u64, 0x8000000000000080'u64,
        0x000000000000800a'u64, 0x800000008000000a'u64, 0x8000000080008081'u64,
        0x8000000000008080'u64, 0x0000000080000001'u64, 0x8000000080008008'u64,
]

const rotOffsets: array[25, uint64] = [
     0'u64,  1'u64, 62'u64, 28'u64, 27'u64,
    36'u64, 44'u64,  6'u64, 55'u64, 20'u64,
     3'u64, 10'u64, 43'u64, 25'u64, 39'u64,
    41'u64, 45'u64, 15'u64, 21'u64,  8'u64,
    18'u64,  2'u64, 61'u64, 56'u64, 14'u64,
]

const hexDigits = "0123456789abcdef"

template rot64(x: uint64, k: uint64): uint64 = (x shl k) or (x shr (64 - k))

template round(state: var HashState, iterations: int) =
    var b: array[25, uint64]
    var c: array[5, uint64]
    var d: array[5, uint64]

    for i in 0..4:
        c[i] = state.hw.words[i] xor state.hw.words[i + 5] xor state.hw.words[i + 10] xor state.hw.words[i + 15] xor state.hw.words[i + 20]

    for i in 0..4:
        d[i] = c[(i + 4) mod 5] xor rot64(c[(i + 1) mod 5], 1)

    for i in 0..24:
        state.hw.words[i] = state.hw.words[i] xor d[i mod 5]

    for x in 0..4:
        for y in 0..4:
            let i = x + 5*y
            b[((2*x + 3*y) mod 5) * 5 + y] = rot64(state.hw.words[i], rotOffsets[i])

    for x in 0..4:
        for y in 0..4:
            let i = x + 5*y
            state.hw.words[i] = b[i] xor ((not b[(x + 1) mod 5 + y*5]) and b[(x + 2) mod 5 + y*5])

    state.hw.words[0] = state.hw.words[0] xor iotaConstants[iterations]

template keccakF1600(state: var HashState) =
    for i in 0..23:
        round(state, i)

proc initState*(): HashState =
    ## initialize hash state
    runnableExamples:
        var state = initState()
        state.update("Hello, World!!")
        echo state.digest()

    new result
    for i in 0..24:
        result.hw.words[i] = 0
    result.reading = 0

proc update*(state: var HashState, bytes: openArray[uint8]) =
    ## feed data to hasher
    for c in bytes:
        state.hw.bytes[state.reading] = state.hw.bytes[state.reading] xor c
        state.reading = if (state.reading == 135): 0 else: state.reading + 1

        if state.reading == 0:
            state.keccakF1600()

proc update*[T: string or openArray[byte]](state: var HashState, bytes: T) =
    ## feed data to hasher
    for c in bytes:
        state.hw.bytes[state.reading] = state.hw.bytes[state.reading] xor cast[uint8](c)
        state.reading = if (state.reading == 135): 0 else: state.reading + 1

        if state.reading == 0:
            state.keccakF1600()

proc digest*(state: var HashState): string =
    ## calculate digest
    ## please note this procedure breaks the hasher internal state and re-initializes it.
    result = ""

    state.hw.bytes[state.reading] = state.hw.bytes[state.reading] xor 0x06
    state.hw.bytes[135] = state.hw.bytes[135] xor 0x80

    state.keccakF1600()

    for i in 0..31:
        result.add(cast[char](state.hw.bytes[i]))

    state.reading = 0
    for i in 0..24:
        state.hw.words[i] = 0

proc hex*(str: string): string =
    ## convert string to hexadecimal string
    result = ""

    for c in str:
        result.add(hexDigits[cast[uint8](c) shr 4])
        result.add(hexDigits[cast[uint8](c) and 0x0f])

when isMainModule:
    var state = initState()
    state.update("Hello, Nim-lang!!")
    let dig = state.digest().hex()
    assert dig == "0f3be9c96b48b5e4dd07da8e0141ba75ee3b6fcbc75cb1323225d09084344af1"

```

## 参考文献
- [Keccak specifications summary - Keccak Team](https://keccak.team/keccak_specs_summary.html) Keccakの処理を疑似コードで解説しています
- [XKCP/Keccak-readable-and-compact.c at master · XKCP/XKCP](https://github.com/XKCP/XKCP/blob/master/Standalone/CompactFIPS202/C/Keccak-readable-and-compact.c) KeccakのCで書かれたリファレンス実装