アニメーションで感覚的にハッシュ関数「SHA-256」の算出過程を理解できる「SHA-256 Animation」

電子証明書の暗号化やブロックチェーンは、入力された値からまったく異なる値であるハッシュ値を算出する「ハッシュ関数」によって成り立っています。エンジニアのGreg Walker氏が、代表的なハッシュ関数である「SHA-256」のハッシュ値算出の過程をアニメーションで表示できるプログラム「SHA-256 Animation」を公開しています。

GitHub - in3rsha/sha256-animation: Animation of the SHA-256 hash function in your terminal.
https://github.com/in3rsha/sha256-animation

実際にプログラムを動かしてみたムービーが以下のものです。

ハッシュ値が生成される様子を「SHA-256 Animation」で観察するとこんな感じ - YouTube

プログラムを動かすにあたり、今回はUbuntu 18.04を用いました。

SHA-256 AnimationはRubyで記述されたプログラムなので、下記コマンドを実行してあらかじめ実行環境をインストールしておきます。

sudo apt install ruby

GitHubからプログラムをクローン。

git clone https://github.com/in3rsha/sha256-animation.git

クローンしたディレクトリに入ると、プログラム群が配置されていました。

さっそくSHA-256 Animationの「sha256.rb」を使って、文字列「abc」のハッシュ値を計算してみます。

なにやら計算が始まりました。

1分ほど待つと、最後尾に「abc」のハッシュ値が表示されました。

SHA-256 Animationが公開されているGitHubのページには、どのようにしてSHA-256によるハッシュ値が算出されているかの解説も行われています。

SHA-256は4つの基本的な操作を入力値に対して行うとのこと。それぞれの操作はSHA-256 Animationのプログラムで実装されています。1つめの操作は2進数の右シフトで、0と1で表される2進数を指定した数だけ右にずらす操作です。SHA-256 Animationでは「shr.rb」によって実装されているとのこと。

2つめの操作はビット回転。右シフトが桁からあふれた数字を捨てるのに対し、ビット回転では桁からあふれた数字を左側からシフトさせます。SHA-256 Animationでは「rotr.rb」で実装されていると解説されています。

3つめの操作は排他的論理和(XOR)です。XORでは、2つのビットがともに0、もしくはともに1の場合は0を、0と1の場合は1を返します。SHA-256 Animationでは「xor.rb」により実装されているとのこと。

4つめの操作は通常の加算ですが、32bitの値を得るために2の32乗で加算後の値を除算し、余りを求める剰余演算を行っているとのこと。SHA-256 Animationでは「add.rb」によって実装されていると説明されています。

SHA-256ではこれらの操作を組み合わせ、4つの関数を実装しているとのこと。SHA-256 Animationで「sigma0.rb」として実装されているσ0関数では、入力値を右に7桁回転した値、右に18桁回転した値、右に3桁シフトした値をXOR演算し、その計算結果を返すとのこと。

「sigma1.rb」で実装されているσ1関数は、入力値を右に17桁回転した値、右に19桁回転した値、右に10桁した値をXOR演算した値を返します。

Σ0関数は「usigma0.rb」にて実装されており、入力値を右に2桁回転した値、右に13桁回転した値、右に22桁回転した値をXOR演算した値を返すとのこと。

「usigma1.rb」で実装されているΣ1関数は、入力値を右に6桁回転した値、右に11桁回転した値、右に25桁回転した値をXOR演算したビット列を返すと説明されています。

SHA-256の主な関数はもう2つ。Choice関数とMajority関数です。Choice関数は「ch.rb」によって実装されており、x、y、zの3つの入力値に対して、xが1であればyのビットを、xが0であればzのビットを選んで並べたビット列を算出するとのこと。

「maj.rb」が実装しているMajority関数は、x、y、zのそれぞれのビットで0と1の個数を比較し、多い方を並べた値を算出すると説明されています。例えばxが1、yが1、zが0の場合は1が返されるというわけ。

SHA-256 Animationの「constants.rb」は、SHA-256で使用する定数を算出するためのプログラムです。SHA-256では、小さい順に並べた最初の64個の素数の立方根に2の32乗をかけた値が定数として使用されており、これらの定数は無理数であるため、ランダムなビット列を得るのに都合がいいとのこと。64個の定数は順番にK0～K63という名前が付けられています。

ここまでのプログラムで32bitの2進数からハッシュ値を得ることができますが、文字列を32bitのビット列に変換する操作が残っています。SHA-256 Animationでは「message.rb」にて、まずは入力した文字列をASCIIコード表と照会し、コード表の10進数を2進数に変換した値を連結してビット列を作成していると説明されています。

SHA-256では512bitごとに入力を区切ってハッシュ値を計算するので、「message.rb」で算出したビット列の大きさが512の倍数になるようにパディングする必要があります。SHA-256 Animationでは、入力したビット列の直後のビットに1をセットし、448bitまでは0でパディングして、残りの64bitは入力したビット列のサイズでパディングすることで、ハッシュ値の衝突を防いでいるとのこと。

入力値がパディングできたら、512bitごとにパディング後の入力値を切り取る操作が「blocks.rb」によって行われます。このブロックひとつは「メッセージブロック」と呼ばれるとのこと。

最後に、512bitのメッセージブロックを大きさが32bitである64個のビット列に変換し、それぞれにW0～W63の番号が割り当てられます。64個のビット列のうち、最初の16個はメッセージブロックを32bitごとにそのまま切り取ったもので「schedule.rb」によって行われるとのこと。

残りの48個のビット列は、「schedule.rb」でメッセージブロックから切り取った16個のビット列を起点にして「expansion.rb」によって作成されます。「expansion.rb」では、生成するビット列の番号から2個前の番号のビット列をσ1関数に入力したビット列、7個前の番号のビット列、15個前のビット列をσ0関数に入力したビット列、16個前のビット列を加算して値を計算していると説明されています。

「schedule.rb」と「expansion.rb」の動作を数式に表すとこんな感じです。

いよいよここからハッシュ値を算出していきます。ハッシュ値の元となる値は、「initial.rb」によって小さい順に並べた最初の8個の素数の平方根を計算し、その小数部分に2の32乗を乗じて2進数に変換したa～hからなるビット列を用います。この操作もハッシュ値をより強固なものにするためだそうです。

入力した文字列から算出した64個の値、「constants.rb」による64個の定数、「initial.rb」による8個の定数を圧縮します。圧縮した値は一時的にT1とT2という名前の変数に格納されるとのこと。T1への圧縮は「t1.rb」によって行われ、これまで説明したΣ1関数、Choice関数が用いられています。

数式で「t1.rb」の圧縮方法を表現するとこんな感じ。

もう一つの変数であるT2は「t2.rb」によって計算され、Σ0関数とMajority関数が使われています。

「t2.rb」の処理を数式で表すと以下のようになるとのこと。

こうして生成されたT1、T2を用いて、再帰的に圧縮を行っていきます。T1とT2を加算した値を、8個の定数のうちの「a」に、T1を「e」にセットして、入力した文字列から算出したW0～W63からなる64個のビット列と「constants.rb」によって素数から算出された64個の定数K0～K63を順番に利用してT1とT2を計算していくというわけ。アニメーションは画像をクリックすると確認できます。

今回の例では処理するメッセージのサイズが512bitであり、SHA-256のブロックサイズと同じであるため、圧縮処理は1回で終了しますが、メッセージのサイズが512bitよりも大きい場合は、一つ前のメッセージブロックに対する圧縮で算出されたハッシュ値を、、最初の8個のハッシュ値「a～h」にセットして同じく圧縮処理を繰り返していく、と説明されています。

最後に算出された8個のビット列を16進数に変換し、順番に連結すれば256bitのハッシュ値が完成です。この処理は「final.rb」によって行われます。

これまでの説明を理解したうえでもう一度ムービーを見ると、アニメーションがより面白く感じるかもしれません。