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

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

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

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

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

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

RSA の説明で例示された363桁の公開鍵 N が（部分的に）素因数分解できるのです！番組では、RSA が２つの素数Ｐ，Ｑの積である合成数 N が公開鍵として使用することを説明した上で、実際に用いられている N の例として画面のような数字を例示しました。一見すると桁数も３６３桁と大きく、何の問題もなさそうなのですが、ちゃんとながめるとすぐに不自然さを感じてしまいます。一番わかりやすいのは、１行目の終わりの方にある 70707 という文字列で、この文字列が３行目・５行目・７行目・９行目・１０～１１行目にも登場すること、しかも位置が規則的に左にずれてっていくことに気づきます。素数Ｐ，Ｑがちゃんと（ランダムに）生成されていればこんなことはあり得ませんので、明らかにおかしいことに気づきます。

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

503850234850348523627070710808502
038502808793160513738582034850385
023485034852362707071080850203850
285087931605137385820348503850234
850348523627070710808502038502850
879316051373858203485038502348503
485236270707108085020385028508793
160513738582034850385023485034852
362707071080850203850285087931605
137385820348503850234850348523627
070710808502038502850879316051373

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

5038502348503485236270707108085020385028 087931605137385820348
50385023485034852362707071080850203850285087931605137385820348
50385023485034852362707071080850203850285087931605137385820348
50385023485034852362707071080850203850285087931605137385820348
50385023485034852362707071080850203850285087931605137385820348
503850234850348523627070710808502038502850879316051373

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

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

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

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

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

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

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

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

関連記事

• 2009年4月16日(木) 『NHK: ITホワイトボックス第３回「メールは盗み見られないのか？』
• 2009年4月24日(金) 『RSA合成数の素因数が見つかった件のその後』
• 2009年5月16日(土)『RSA合成数の素因数が見つかった件のさらなるその後』