fortran66のブログ

fortran について書きます。

芹沢正三『素数入門』の宿題の暗号解読

目がかゆくて鼻づまりで頭が重くて何もやる気がしません。バリントン・J・ベイリーの『カエアンの聖衣』を読み返してヤクーサ・ボンズに爆笑しつつ、竹本泉の『さよりな・パラレル』の端々に影響があるなと思いつつ、イブリン・ウォー『大転落』中の「やるねえ、プレンディ!隠れた元気を引き出すのには衣替えが一番さ。初めてカーキ色の軍服を着たときは、ぼくもそう感じたよ。じゃあ、失敬。パブが私を呼んでいる。一緒にどうだいプレンディー?」というキャプテン・グライズムの台詞を思い出す。

初読の時、グライムズ先生が妙にクラターバック少年をえこひいきしているなと思ったら、案の定「わしには理解のできん、勘弁ならん犯罪」というか「一連の行為」を行っていましたw 池田潔の『自由と規律』では、記憶違いでか、キャプテン・グライムズが主人公とされていてずっこけます。

それにつけても最近、まったく小説とかを読まなくなりました。

その後もやる気がないので芹沢正三著『素数入門』の問題を解くことにしましたが、第9章末(217頁)の宿題にだいぶてこずりました。暗号をより難しくするためなのか、誤植というか誤りなのか、そのままでは解けません。特に2.のエルガマル暗号はちょっと苦労しました。

著者は正誤表を出しておられますが、この暗号に関しては何も書いておられません。
http://shop.kodansha.jp/bc/books/bluebacks/seigo.html

1. RSA式暗号
n = 95, c = 7 (n = 5*19, f=4*18=72, d = 31)
x = y^31 (mod 95)

15 11 55 70 54 31 18 19 82 57 82 71 15 81 31 82 67 82 2 57 42
i f y o u h a v e d e c i p h e r e d

31 15 22 28 88 22 22 21 87 77 20 82 2 42 42 82 67 88 82 81 20
h i s m e s s a g e l e t t e r m e p l

81 18 22 82 08
e a s e .

If you have deciphered his message
letter me please.

余計な数字が紛れ込んでいて、途中でずれて解読不能になります。お尻側から解読することで比較的容易に訂正できます。(追記 H21-11-3:見直してみれば his message でなくて、 this message かなw)

2.エルガマル暗号
p=97, g=5, y=2728
(a = 3)

0588 4317 0579 2112 3055 2580 0839 2188 2719 2127
0588 4317 0579 2112 3055 2580 0839 2188 2809 2112
w e n n s i e e n t

0661 3049 4071 3083 2811 2507 2864 0603 4340 0823
0661 3046 4017 3083 2811 2507 2864 0603 4340 0823
z i f f e r t h a b

2587 0845 4375 2848 2857 0692 2811 2580 4062 3006
e n s c h r e i b e

2112 0133 2580 0621 0670 4358 0573 3011 4091 0508
2112 0133 2380 0621 0670 4358 0573 3011 4061 0508
n s i e m i r b i t

0877 3006 2834
0877 3006 2034
t e .

Wenn Sie entziffert haben
Schreiben Sie mir bitte.

そもそも公開鍵が間違っているという暗黒トラップw

ー推定の時系列
最後の文字はピリオドだろうと思って逆算してもうまく行かない。(なぜなら最後の文字のデータも間違っていたからw)
暗号文中に92という大きな数字が出ているので、p=97は正しいだろうと推測。暗号が3桁区切りだとすると数字が大きくなりすぎるので、暗号もpも2桁なのは確かだろう。
a=2から97まで総当り式で行く覚悟で始めると、a=3で早くもドイツ語らしい単語が現れて色めき立つが、すぐ解読不能文字が出てしまう。1. の文章と似ているし、著者は25頁でグルッペがどうのこうのと言っているのでドイツ語の可能性は大と思うが、尻からやってみてもやはり解読不能文字が出て放棄。(しかしこれが正解だったw)
g=5以外の数字を試すが、うまく行かない。g=5は正しいだろうという直感を得るw
特定の暗号文字に対して解読可能な文字を返すaのリストを作って、異なる暗号文字で重なるaのリストをつくってゆくが、すぐにすべての暗号に解読可能な値を返すaは存在しないことが分かる。つまり暗号文自体が間違っていることが分かるw 
もはや手がないので、寝ることにして布団に入るがやっぱりドイツ語説に戻るw a=3に対するyを求めると28が出たので誤植っぽくてもっともらしい。確信を得たので、後はdecipherに当たるドイツ語をネットで検索して、つじつまが合うように元の数字を修正する。ほとんどは誤植くさい間違いだが、entziffertをeinziffertと元々つづりを間違っている可能盛大。

UBASIC

最後の計算では数論用BASIC『UBASIC』のお世話になりました。
http://www.rkmath.rikkyo.ac.jp/~kida/ubasic.htm
BASICのプログラムを書いたのは何年ぶりか!10行くらいだけどw