2019年12月
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31        
無料ブログはココログ

« NHK: ITホワイトボックス第3回「メールは盗み見られないのか?」 | トップページ | 暗号商売ウォッチング: USBメモリ »

ITホワイトボックス第3回「メールは盗み見られないのか?」を見ました

ITホワイトボックスの第3回目のテーマが電子メイルの暗号化であることをオンエア前に気づいたため、生で鑑賞してみました。この番組は、あるIT技術(今回はメイルの暗号化)についてその道の専門家が仕組みを教えるという構成になっており、実際の内容は次のような感じでした(以下、ネタバレになっていますので、要注意!なお2009年4月19日(日)14時から再放送があるそうです):

  • 電子メイルの内容は送信者・受信者以外でも盗み見ることができる
  • 電子メイルの内容を知られないようにするには暗号化が必要
  • 暗号化の具体的な手順例
  • DESの説明
  • 送信者と受信者の鍵の共有法?→公開鍵暗号
  • RSAの説明
  • 暗号は安全か?→攻撃(クラック)と改良の繰り返しで強くなる
  • 松井さんによるDES解読実験の紹介
  • 量子暗号

見終わった印象は、全体的に丁寧に説明されており、特に暗号の処理内容の「見える化」が上手いと思いました。是非、今後の参考にしたいところです。

しかし残念ながら、ちょっと引っかかった部分があったことも事実です。列挙すると、暗号文の復号を「解読」と説明した点、DESの処理内容の紹介でデータの置換をトランプのシャッフリングに例えていた点(シャッフリングだと元に戻せるかどうかがわかりにくいように感じた)、そして素因数分解するには素数で順番に割っていくしかないという点などです。この番組を見た視聴者が、電子メイルの暗号化を試みようと思っても、どうして良いかわからない、というのもありますが、まあ、そこは仕方ないところでしょう。

しかし、今回はもっと大きな問題点に気づいてしまいました。それは...

Cap001 RSA の説明で例示された363桁の公開鍵 N が(部分的に)素因数分解できるのです!番組では、RSA が2つの素数P,Qの積である合成数 N が公開鍵として使用することを説明した上で、実際に用いられている N の例として画面のような数字を例示しました。一見すると桁数も363桁と大きく、何の問題もなさそうなのですが、ちゃんとながめるとすぐに不自然さを感じてしまいます。一番わかりやすいのは、1行目の終わりの方にある 70707 という文字列で、この文字列が3行目・5行目・7行目・9行目・10~11行目にも登場すること、しかも位置が規則的に左にずれてっていくことに気づきます。素数P,Qがちゃんと(ランダムに)生成されていればこんなことはあり得ませんので、明らかにおかしいことに気づきます。

そこでもう少し調べてみようということで、この合成数Nを実際に入力してみました(注意:、この入力値に誤りがあれば、以下の記述は全く意味を持たなくなりますが、2回入力して同じ値になり、さらには協力者の方にも入力してもらって同じ値となったので、大丈夫とは思いますが、万が一、誤っていた場合は、おさわがせしてすいません)。まず画面と同じフォーマットで表記すると

503850234850348523627070710808502
038502808793160513738582034850385
023485034852362707071080850203850
285087931605137385820348503850234
850348523627070710808502038502850
879316051373858203485038502348503
485236270707108085020385028508793
160513738582034850385023485034852
362707071080850203850285087931605
137385820348503850234850348523627
070710808502038502850879316051373

となります。さきほど指摘したように、70707 がだんだん左にずれることを考慮してフォーマットをいじると、実はこの合成数は

5038502348503485236270707108085020385028 087931605137385820348
50385023485034852362707071080850203850285087931605137385820348
50385023485034852362707071080850203850285087931605137385820348
50385023485034852362707071080850203850285087931605137385820348
50385023485034852362707071080850203850285087931605137385820348
503850234850348523627070710808502038502850879316051373

という文字列になっていることがわかります(1行目の途中の1文字分のスペースは意識的に入れています)。つまりこの合成数は「50385023485034852362707071080850203850285087931605137385820348」の(ほぼ)繰り返しとなっているのです。この数字が何を意味するかは調べていませんので、興味がある方におまかせしたいと思います。

では、ということで、番組内ではスーパーコンピュータを使ってもこの合成数の素因数分解は無理と言っていましたが、手元の計算機を使って素因数分解にチャレンジしてみました。まずは小さな素数による試し割り算。この段階で何と P1=23 で割り切れることが判明しました!余因子(N を P1 で割った値)は合成数のため、さらに楕円曲線法により、この合成数は

  • P1 = 23
  • P2 = 3993359999
  • P3 = 270147724086077
  • P4 = 105540293482603433
  • P5 = 122128379182503903409

という5個の素因数を持っていることが判明しました!!余因子(N. を P1*P2*P3*P4*P5 で割った値) はまだ合成数なのですが、これ以上の素因数は求められていません(現在でも計算中ですので、求められれば、また、報告したいと思います)。

まとめると、今回の番組で紹介していた RSA 用の合成数 N は2個の素数の積になっておらず、入門用としては不適です。番組内容に好印象を持っていただけに、かなりがっかりしてしまいました。

(20090418追記) 楕円曲線法による素因数分解を計算中ですが、合成数 N はP1~P5以外に35桁以下の素因数を持たなそうです。

(20090419追記) 話題に出た 50385023485034852362707071080850203850285087931605137385820348 を素因数分解できました。
50385023485034852362707071080850203850285087931605137385820348
= 2 * 2 * 3 * 3 * 23737837390833143 * 58960046050188669524134760945664857422166401
だからといって、特に何もわかりませんでした...

(20090423追記) その後の楕円曲線法による素因数分解実験の結果、合成数 N がP1~P5以外に40桁以内の素因数を持つ確率が低いことがわかりました。

関連記事

« NHK: ITホワイトボックス第3回「メールは盗み見られないのか?」 | トップページ | 暗号商売ウォッチング: USBメモリ »

素因数分解」カテゴリの記事

コメント

コメントを書く

(ウェブ上には掲載しません)

トラックバック

« NHK: ITホワイトボックス第3回「メールは盗み見られないのか?」 | トップページ | 暗号商売ウォッチング: USBメモリ »

リンク