peanutsjamjamの日記

MD5-Ring

数学

MD5

MD5 とは何か、というような話は以下のサイト等を確認してください。

MD5(Wikipedia)

http://ja.wikipedia.org/wiki/MD5

簡単に言ってしまえば、MD5 とは、「バイト列を与えると、16 バイトのデータを返してくれる関数」です。関数ですから、同じデータを 2 回与えれば、2 回とも、返ってくる値は同じです。そして、どんなに長いバイト列を与えようが、長さの無い（ゼロバイトの）バイト列を与えようが、16 バイトを返してくれるのです。

ループ

という事は、MD5 関数から返ってきた 16 バイトのデータをそのまま、再度 MD5 関数に与えてみると、また何らかの 16 バイトのデータを返してくるわけです。これを延々と続けると、どっかでループするんじゃないか、すなわち、16 バイトのデータ a, b, c があったとして、

MD5(a) = b, MD5(b) = c, MD5(c) = a

というようになったりするんじゃないか、と思ったのです。

MD5-Ring

上記のようにループしているダイジェスト値のことを、Ring （リング）と呼びたいと思います。MD5 のループは、MD5-Ring です。

また、各 Ring 内に存在するダイジェスト値の個数を、Ring の大きさ、と呼びたいと思います。上記の例でいくと、a, b, c の 3 つのダイジェストが Ring 内に存在しているので、Ring の大きさは 3 です。

さて、一体いくつの MD5-Ring が存在しているのでしょう。そして、それぞれの大きさはどれくらいなのでしょう。

ホントにループするの？

します。（きっぱり！）

「ループなんてしないんじゃないかな」とお考えの方は、悔い改めてください。

でも、どこでループするのか、まだ一箇所も確認できていません。（笑）

ふーん、じゃあプログラム書いて見っけりゃいいんでしょ？

はい。

Ring を発見できた方は是非お知らせください。また、Ring の大きさと、Ring 内の最小のダイジェスト値もお知らせください。

でも簡単じゃないですよ。（笑）

16 バイト

16 バイトの数って、どれくらいの大きさなのか、ちょっと調べてみましょう。

1 バイトは 8 ビットですから、16 バイトは 128 ビット。128 個のゼロかイチが並んだ数です。

n ビットであらわすことのできる情報量は、2 の n 乗で計算できますので、http://www.google.co.jp/ に行って、検索窓に「2^128」と入れてやります。

すると、「3.40282367 × 10 の 38 乗」と答えが返ってきます。すごく大きな数ですね。

どのくらい大きな数かというと･･････

宇宙の直径は（諸説ありますが）200 億光年とか 400 億光年と言われています。400 億光年を書き直すと、「4.0 × 10 の 10 乗光年」。「1光年」を google で引くと「9.4605284 × 10 の15 乗メートル」と教えてくれます。計算（掛け算）すると、「3.78 × 10 の 26 乗 メートル」。これが宇宙のだいたいの直径。

ここに、小さなものを並べてみましょう。たとえば水素原子の直径は、だいたい 100 億分の 1 メートルですから、「1.0 × 10 のマイナス 10 乗メートル」。これで、宇宙の直径を割ってみると、「3.78 × 10 の 36 乗個」。

「2^128」として調べた「3.40282367 × 10 の 38 乗」に、まだ及びませんねぇ。ということは、「2の128乗」という数は、宇宙の端から端まで水素原子をぎっちり一直線に並べて、その一つ一つに番号を振るのに必要な数の100倍くらいの数ということです。

はぁ･･････。

keywords: MD5 | バイト | ビット | ハッシュ | 宇宙 | 水素 | 原子

関連する記事

MD5-Ring その２ - peanutsjamjamの日記

http://d.hatena.ne.jp/peanutsjamjam/20080122/p1

MD5-Ring その３ - peanutsjamjamの日記

http://d.hatena.ne.jp/peanutsjamjam/20080902/p1

Permalink | コメント(0) | トラックバック(0)