No294 MD5の基本構造をフツーの人向けに解説してみる

前回はハッシュ関数の計算方法について簡単な例（ハッシュＡ〜ハッシュＣ）を使って解説をしました。

今回は、前回の内容を踏まえて、実際のハッシュ関数(MD5)をベースにぐっと単純化したハッシュ関数を解説します。

単純化したものとはいえ、基本構造はMD5そのものですので、ハッシュ関数についてはかなり深い理解をしていただけるのではないかと思います。

なお、前回のラストで「SHA-256をベースに」と書きましたが今回はMD5ベースの解説となります。もっともMD5はSHA-256のご先祖様なので「似たようなもの」なのですが。


1. ハッシュ関数のおさらい

ハッシュ関数というのは、元の情報をルールに従って計算する計算方法のことを言います。ハッシュ関数を使って計算した結果の値を「ハッシュ値」と呼びます。

なんとか関数というと数学の公式のようなものをイメージされるかもしれませんが、そんな大層なものではありません。ハッシュ値の計算方法の総称です。

日常的に使うことは少ないでしょうが、コンピュータ内部ではハッシュ関数を使いまくっています。
特に、ChromeやEdgeといったブラウザでインターネットを使う際の暗号化通信（HTTPS）ではハッシュ値による計算を頻繁に行っています。

コンピュータは複雑な計算を高速に行うのは得意中の得意ですが、逆に「適当な値をピックアップする」といった計算で求められない作業は極端に苦手です。

その点、質の良いハッシュ関数はランダムとしか思えないような値を簡単に得ることができます。HTTPSなどの暗号化通信では、通信鍵のランダム性が非常に重要となるため、結果としてハッシュ関数が多用されるということになっています。

また、ハッシュ値は電子証明書にも必ずと言っていいほど使われます。
この場合は、ハッシュ値をデータが正しいことの証明に使っています。


2. 理想的なハッシュ関数

前回は、数値の合計値を得るハッシュ関数や加減算を繰り返すハッシュ関数というものを例に、元のデータパターンによって、違った値を得られる方法というものを示しました。

前回のハッシュ関数はどれも質の良いハッシュ関数とは言えません。

例えば、元データの順序が入れ換わっても同じハッシュ値になることは好ましくありません。
また、元データが増えたからといって、ハッシュ値がどんどん大きくなると計算が大変になりますから、それも良くありません。

こういった条件を逆にとらえると理想的なハッシュ関数に求められる条件が見えてきます。
　1) 元データが同じなら、毎回同じハッシュ値を得られること。
　2）元データの一部が違えば、全く異なった（思いがけない）値となること。
　3）元データの多寡に関わらず、同じケタ数のハッシュ値が得られること。
　4）手順がシンプルで素早く計算できること。
　5）逆算（ハッシュ値から元データを得ること）が難しいこと。

2023年時点で最も利用されている実用的なハッシュ関数はSHA-2（シャーツー）です。中でもハッシュ値が256ビット（＝32バイト）となるSHA-256はよく使われます。

過去にはSHA-1（シャーワン）やMD5（エムディーファイブ）もよく使われていましたが、現在は安全とは言えないため、新たに採用されることはまずありません。


3. 実用的っぽい感じがするハッシュ関数

さすがにこのメルマガでSHA-2の計算手順（アルゴリズム）を書くのはやりすぎですので、ここではSHA-2の元祖にあたるMD5をさらに単純にしたアルゴリズムの解説をします。

あくまでここで書くのは「実用っぽい感じがする」レベルであり、実際のMD5のアルゴリズムにはここで触れていない手順がいくつか存在しています。
それでも、前回までのテキトーな計算に比べれば格段に複雑です。

今回のハッシュ関数は前回の続きで、ハッシュＤと呼ぶことにします。

ハッシュＤの計算方法は次の手順になります。

　事前準備
　1) ハッシュ値の計算結果を格納するハコとしてAとBを用意します。
　2) A=3、B=5とします。
　3) 元データの1つ目をM1、2つ目をM2、3つ目をM3...と呼ぶことにします。
　計算
　4) AにM1とBを加えます（A+M1+BをAに入れ直す）
　5) Aが10を越えている場合は下1ケタだけを残します。
　6) AとBを入れ換えます。
　※同様の計算をM2〜M10についても繰り返します。
　結果
　7) 結果、得られたAとBを並べた値がハッシュ値になります。

これだけだとイメージしにくいですね。
いつものように実例でいきましょう。

サンプルなので、元データは、5 8 6 の３つとしましょう。
ですので、元データは
　M1=5
　M2=8
　M3=6
となります。

まず、上記の2)の通りAとBの値を設定します。
　A=3　B=5

次に最初の計算（A+M1+BをAに入れ直す）を行います。
　A=3、M1=5、B=5ですので、
　A=3+5+5=13 となります。（Bは5のまま）

次に、Aが10を越えていますので、下1ケタだけを残します。
　A=13-10=3

最後に、AとBを入れ換えます。
　A=5　B=3
　
これで１ラウンドが終了です。

次はM2について計算します。
　A=5、M2=8、B=3ですので、
　A=5+8+3=16、そこから10を引くので A=16-10=6 です。
そして、またAとBを入れ換えます。
　A=3　B=6
　
最後にM3も同様に計算します。
　A=3、M3=6、B=6ですので、
　A=3+6+6=15、そこから10を引くので A=15-10=5 です。
そして、AとBを入れ換えます。
　A=6　B=5

最終的にハッシュ値はこの２つの値を並べて 65 となります。

どうでしょうか。前回のハッシュＡやハッシュＢに比べるとはるかに複雑ですね。
とはいっても、足し算と引き算だけですので、コンピュータにとっては楽な計算です。

また、前回のハッシュＣは元データが増えた分だけハッシュ値が大きくなりましたが、今回のハッシュＤは元データの量に関わらず結果は必ずAとBの2ケタになります。

前述の理想のハッシュ関数のスタイルにかなり近づいていますよね。


4. ハッシュＤの計算例

実際の例をいくつか示してみましょう。

いずれも、最初の数字列が元データで、最後の値がハッシュ値です。

  1 2 3 → 68
  1 2 4 → 69 
  1 4 2 → 89
  3 2 1 → 80

いかがでしょう。順序が違っているだけでも異なる値になっていますね。
また、前回提示したパターンについても調べてみましょう。

  1 2 3 4 5 6 7 8 9  → 68
　1 2 3 4 5 6 7 8 8  → 67
  1 2 3 4 5 6 7 9 8  → 78
  1 2 3 4 5 8 9 6 7  → 04

ハッシュＡやＢでは同じ値になったのに全てが異なる値となっています。
また、ハッシュＣのように答えが大きくなることもありません。

前回の足し算ハッシュ関数などに比べるとかなり優秀だと言えそうです。

余談：
　さて、上記のハッシュ関数の答えは00〜99の100種類しかありません。
　元データのパターンは無限にあるのですから、全く違う元データから同じハッシュ値が算出されることが当然発生します。
　実は、上記の中でも同じハッシュ値が現れています。
  　1 2 3 → 68
  　1 2 3 4 5 6 7 8 9  → 68
  これをハッシュ値の衝突と言いますが、これはハッシュ関数の性質（元データを短かい値で表現する）上避けられません。
  とはいえ、これは今回のハッシュ関数ではハッシュ値が10進数2ケタだから容易に発生するだけで、実用的なハッシュ関数ではSHA-256のように256ビット（10進数なら77ケタ程度の値）もあれば、衝突はあまり問題となりません。


5. （余談）現実のMD5ハッシュ関数の手順

この章はMD5に興味のある方に向けての余談です。

ハッシュＤはMD5を大巾に省略していますと書きましたが、実際のMD5とどう違うのかを書いておきます。

　・ハッシュＤではAとBは1ケタの値でしたが、MD5はA〜Dまであり、それぞれが32ビット　　（9ケタ程度の値）です。
　・ハッシュＤではハッシュ値は2ケタで100種類でしたが、MD5では38ケタあるため、1兆の1兆倍の1兆倍くらいの種類があります。
　・ハッシュＤでは手順4でAとM1とBを足し算するだけでしたが、MD5では4つの計算方法があり、一定のルールで使い分けています。
　・ハッシュＤでは手順4〜6は１度しか行っていませんが、MD5では同じ手順の計算を64回繰り返します。
　・ハッシュＤでは省略していますが、MD5ではデータ処理の後に特定の値の足し算とシフト演算（ケタずらし）の計算を行います。

逆に言えば、上記以外についてはハッシュＤはMD5の手法で計算をしています。

なお、SHA-2はこのMD5をさらに改善した方式になっており、ハッシュ値の範囲はさらに広がっています。（SHA-256で77ケタくらいの値）


6. まとめ

前回と今回の２回に分けてハッシュ関数の計算方法について解説をしました。

前回のハッシュＡからハッシュＣに比べて、今回のハッシュＤはSHA-2のご先祖にあたるMD5の基本構造を利用しています。かなり単純化していますが、それでもそれなりの値を得ることができました。

このように、ハッシュ関数の考え方はそれほど難しいものではないのですが、これが「質の良い」ハッシュ関数となりますと、かなり高度な数学が求められうようで、筆者程度の知識では全く理解できない領域となります。

これはコンピュータの知識がどうこうという領域ではなく、数学者の研究領域となります。ハッシュ関数に限らず、現代暗号も同様ですね。

ハッシュ関数の計算方法などかな

"