SHA-3とは

一方向ハッシュ関数の一種、KECCAKというアルゴリズムが用いられており、ビットコインをはじめ様々なブロックチェーンで用いられている。生成するビット列の長さに応じてSHA3-224,SHA3-256,SHA3-384,SHA3-512といった規格が定義されている。

一方向ハッシュ関数とは

任意長のメッセージを入力すると固定長のハッシュ値を返す関数であるハッシュ関数の一種。ハッシュ値から元のメッセージを推測できない、異なるメッセージに対しては異なるハッシュ値が対応するという特徴を持つ。改竄の検出や電子署名などに用いられている。

衝突

異なるメッセージが同一のハッシュ値を持つことを衝突と呼ぶ。この衝突は必ず起こるので、一方向ハッシュ関数は衝突を見つけることが事実上不可能である必要がある。衝突の見つけにくさを衝突耐性と呼ぶ。衝突耐性にはあるメッセージと同じハッシュ値を持つメッセージの見つけにくさである弱衝突耐性とハッシュ値が一致する二つのメッセージの見つけにくさである強衝突耐性がある。

xor

バイト列同士の足し算。0+0=0,0+1=1,1+0=1,1+1=0。

KECCAK

スポンジ構造

KECCAKでは上図のようなスポンジ構造が用いられている。吸収フェーズと搾出フェーズに分かれており、r+cの長さの内部状態を持つ。メッセージMはpadにてパディング(rで割り切れるように足りないバイト列を足す)を施され長さrの入力ブロックi(1,2,3,,,)に分割される。そして入力ブロックが尽きるまで1から順に長さrの内部状態とxor、関数fによる処理を繰り返す(図では左から順に入力ブロック1,2,3,4が入力として使われる、また長さcの部分は入力の影響を受けない)。搾出フェーズでは長さrの内部状態を出力iとして出力、関数fによる処理を出力iの合計長が出力Zの固定長に達するまで繰り返して結合する。

内部状態と関数f

KECCAKはr+cビットの内部状態を持つが、それは上図のような5*5*(r+c)/25の立方体が集合した直方体として扱われている。
１ビットが一つの立方体である。関数fはこの直方体に対して決められた操作(足したり入れ替えたり)を行うことに相当する。

参考