Goで学ぶSHA-3
この記事は、ex-handslab Advent Calendar 2018 1日目の記事です。
最近会社で結城先生の暗号技術入門の最新版を輪読して、自分はSHA-3の所を重点的に読んだのでそのあたりの話をします。
SHA-3 is 何
- 一方向ハッシュ関数のアルゴリズムのひとつの呼称
- 2012年に Keccak が採択された https://keccak.team/keccak_specs_summary.html
- SHA-1, SHA-2 と完全に異なる構造をもったアルゴリズムのため、既存の構造に起因する脆弱性の影響を潜在顕在しているもの問わず受けない
- 実行環境を問わず、いずれの環境でも高速に動作する
細かい仕様は内部実装などは上記公式仕様や結城先生の書籍を読んで頂ければわかるので省略しますが、個人的な印象としては SHA-1 よりシンプルな記述で理解しやすい印象を受けました。
SHA-3 in Go
既に標準ライブラリで実装されています。（詳細は以下ディレクトリに全部あるぞという雑スタイル）
ざっくりいうと、吸収フェーズと搾出フェーズに分かれている。
吸収フェーズは以下の様な感じ。
- 入力データをrビット毎に分割。キリの悪いところは適切にパディングされる。
- はじめのビット列について、 Keccak が別のビット列として保持している内部状態と排他的論理和をとる
- 2つめ以降のビット列について、 1つ前のブロックでの関数fの出力とのXOR をとり、これを再度関数fへの入力とする
- 入力ブロックが枯渇するまで繰り返す
搾出フェーズは以下の様な感じ。
- 吸収フェーズの最後の出力 r+c ビットのうち先頭rビットを最初の出力ブロックとする。最後の出力全体を関数fへの入力とする。
- 直前の関数fの出力のうち先頭rビットに対して同様の捜査を行い、出力ブロックの総和が必要な出力サイズとなるまで繰り返す。
ここで、天下り的に出てきている内部状態と関数fですが、それぞれ以下の様にいえます。 - 内部状態: ハッシュ値を計算するための入力メッセージと異なる値の集合 - 関数f: 計算時のビット列を格子点の集合とみなしたとき、その状態を幾何学的に撹拌するような操作
という感じでしょうか。
まとめ
Goはいろんな有用なアルゴリズムや処理が良い感じに可読性高く記述されていて、標準ライブラリ見てるだけでもかなり勉強になります。 以前gzipのライブラリを同様に読んでみたのですが、下手な図解を読み解くより完全に学びがありました。
参考文献
- 暗号技術入門 第3版 秘密の国のアリス
