C
C言語

「クリプタン帝国の暗号文を解読しよう!」の解答可能性について

問題:https://codeiq.jp/ace/yuki_hiroshi/q781

解答例:https://gist.github.com/cielavenir/10002153

今まで結城先生の問題は14連覇であったが、この問題に正解することはできなかった。

否、厳密には問1は正解できたが問2は正解できなかった。

問題の解説を読み、一度は納得し、私の答案を修正することに成功した。

だが、この問題は本当に普通の方法で解答可能なのか、検証することにした。

結城先生の実装では、 Digest::SHA1が内部状態を持つ ことを前提としたコードになっている。

確かに長いファイルのSHA1を算出するときは、ファイルを一度に読み込むのではなく、ブロックごとに読み込み、何度もupdate(sha1_loop())を呼び出して、最後に結果を出力するのが普通である。

しかし、私の記憶が確かならば、SHA1は最終状態を出力する際にパディングを付与するはずだ。

検証してみよう。

https://gist.github.com/cielavenir/10002153#file-codeiq781_2-c

ビンゴだ。 このif 1をif 0に書き換えた瞬間、このプログラムは正常に動作しなくなる。つまり、sha1_result()を実行した瞬間に内部状態は破壊される。 Rubyではこのコピーを内部的に行っているだけなのだ。

この問題では何度もsha1_result()を呼び出す必要がある。そのたびにsha1_ctxのコピーが必要となるとなれば、SHA1が この問題で示されるような 内部状態を持つとは考えにくいのではないだろうか?

(i.e.このような解法は普通とは考えにくい。)

ここに問題の不備を指摘し、結びとさせて頂く。