Edited at

繰り返し MD5 関数

More than 5 years have passed since last update.

おしゃれなお店で同僚とランチを食べていたので、自然と MD5 の話になった。


自分自身の MD5 を含むスクリプトを実現できるか?

自分が書き換えられていたら例外を出すスクリプトについて話していて、以下のようなガードを入れられるかどうか考えていた。

# いろいろな処理

raise LoadError unless Digest::MD5(IO.binread(__FILE__)) == "自分のMD5"

これは、自分自身の MD5 をファイルの最後の文字列リテラルの部分に含んでいる Ruby スクリプトだ。こんなもの実現できるんだろうか?


MD5 関数の不動点は存在するか?

そういうケースの一番単純な場合は「自分自身の MD5 が自分自身である」ような文字列だろうと考えた。この文字列は MD5 関数の不動点だ。MD5 関数に不動点なんてあるんだろうか?

ツイッターで尋ねてみたら、knu さんが以下のサイトを見つけてくれた (twitter の埋め込みがうまく行かない):

MD5 関数の不動点が一大ムーブメントがこんなに流行っていたなんて・・・


繰り返し MD5 関数

学生の頃、totalistic 2D cellular automata (ライフゲームのような遷移規則を持つ CA) の状態遷移グラフを採取して調べていた事がある。

MD5 関数の結果に次々と MD5 関数を適用していくと、値はどう変化していくだろう?元の値に戻るループは存在するだろうか?

0 から初めて最初の100個だけ、ワンライナで出力させてみた。

$ ruby -rdigest/md5 -e 'puts 1.upto(100).inject("0"*32) {|x,| x = Digest::MD5.hexdigest(x).tap { puts x } }'

00000000000000000000000000000000
cd9e459ea708a948d5c2f5a6ca8838cf
521214d453fe36d20ac094dec9916bbd
5def46e8712a2b9eb859e52455d49799
d352005575e7e1ffef66d7ce7c6f3a19
820bd31177566332d41b33c992f4d9c1
2ae819205908d37cb15d94a32a1f4ec5
a5bbf9dcff567b5a86b323a91891910a
5d754d29e026ecb71649245b4828cc48
3bbd2d5371eb16909c2d1357b5632f37
1a31af46b0ed8e74fc5531376100da45
bc8922eaa3e53a800b85c8894fe65f10
6fd44e9b63872f257560416d165937b7
63295150e40557295ab76aa15025c144
ad9cc46414be76fa81e5b768de883452
443e2a592b08704a42630b10ecef05ea
30c774e00c562818ceb3f98cae85c316
73f4697f90c7392ce18f9dc72bbe87fb
0c0777a0ab32498cd077b25f767971f4
44d44a20f65658701f241c2dd14e7a2e
dd17d45d0510a9e640377a91b39aaf5a
ac07bfb3b1342ffa48f9ff1874106fd9
e0d0e0442c3a4ff5a30dfdea78f1be26
f14e4dfc567d510a4a824b2a1148ead4
0194c5a15e73ce6712710e34424ab819
3ce82a116cdd08ff877ad4cb61e671ba
f514040310930786f1d3b2de5999efcb
645b6ca1fb9f2b159f89b723179768b8
038d9a5323fcf7b27c22028b6a1986f1
fbf4ba1a9e03c1406196ec288f25d6bc
48ba690586c8758f78e144f720d4356d
3e60024779d314fba34450f55dfe2a9e
3a8e3beede74c69e3eacf7a399c3413e
6501f856618511eef9decb04f0e90559
ce8bf49e7b82c41e9c9b8c349c931ba2
7a2c99281c01c182576658a688e21242
03c1560853f3379769e3463791d6f677
2e46aa660e5bee9595752c563aa47ee6
b6fa920c7fb860e16ed93cdeaaca7c9a
938ae4fe27ff9edd598f8474453786a4
6b0234a2683c33df6e79cd3c762fae67
11d9dc8c4ef8705cf8fec86f27881fdd
513389d7da468f1eef8f39964967ecc6
fb65b1ac26f1660a850f6c743a29a265
7fd6b7cd60144b61bcb1201cc9fb64fe
1f2e48acc6718c8dd544f5698c971245
5c6591f88b00001478a70e4d74f00d76
7d4f6f73ea9ad510e383fa3d3baaaed7
d18de9ad6e93cb84743e90d72a49bc66
67f48388e41658ac6f97f91d120c334b
50cd468edf81260d04f34a7afa951f96
22c97e5c7425cd63306fa5322afd8f35
1375c9eb5901623a3134cc71dfa6e73f
557885cb80fe1672841bcd7f86309715
25a4a0b9181e6e02762cac8eb03ee059
9422781bd8f70bf666f2edf9d2b3d8c5
3ce77361f11bfe9baa57ef37588847c8
a317f3a374c8378e388fa4535c6af16d
cb16f94f4b94af853f07308a42fe068a
1b26fab09e104406ce3e8ffa9faaef1f
144e0a83c798ea71e6fb568747fefb1a
44e36b602094901d7493cd8412684a1a
2332b889e55af53a8eaed455aa6d4fec
83fe8da90824b85af92f66157892d2c1
65872657aee37eb2ea84d6b3883a2f81
d04b40ee218a006f1a0d9bebe6faf228
5ddc231f49d3a96236c306525649b9f6
bb9695c5afc5261144c4a64335f5b6d5
dde9d11b6175905bbf56532223abd3c7
c9ed72aa6a458cec37cd22ba98c9d30c
b99a3d2b99e6490091fbdabd2fb0c786
ca2b3d3fadcd0f84792fdaa27ae841fb
d66973bc4e6321170276b9a72706c2bc
2e9b8c5c6a97d7e520340ccbd3c7d58d
abd96a129a268c820f62eaac32d9a54c
a9f61948f4529bdde552bcf32b336e17
eb5b78fbf223da85568eaf14ed673ad3
8ddfe86a42d2257878d92d74ecace730
87ed2b8cfc9bcc690ba7c79adc77b2e8
ff5b2bf208c29fa1ffb46ba13b39499f
1af34f764fb00db5b278fe9bb62b7f6f
4df0bb1db6828c9eb9ae7c6f849eeaec
3130539fd7c12a618bb4391f9a510190
66d3ca0df537a65f3b1e93dea5663bc1
5cff2c90763a247e44a2279e60d07cb1
25753d35f4f5384afff96dc8596b5bed
eccbc5b7cacc0066ac53aa4d0b4cfc3f
09d84581b02395067295fee85a88f112
f7631bf9931433deebd817754014278d
fdb0cabd2b11d6a409f81dd0d1c527c5
abcf6829f70f921698b941a07a064a3d
680d716baeb94f0963e0f77950d45c2c
20d5fe04e43ccbd39ffa30fe9769db31
714f779d48318f70854e23c21ddcced9
eaffc54475f5b9b88ff46053d06f9398
0c7b37781635e3665b6f5ce82d87b011
0c051a5b931ff9d15889eb728dd6902d
41baecd02c586559668d6fce8382feef
7bc66893838827fd7ab214680b6879c7
5a2a1a66530eddb9a2396c021388034a
d8127005f2d0d6321851bffc0ffd1f3a