セミナー「数体篩い法による素因子分解」

久しぶりに素因数分解ネタです。早稲田整数論セミナーで、上智大学の和田先生が数体篩法を紹介されるそうです。

• 日時：2009年06月26日(金) 15時30分～17時
• 会場：早稲田大学大久保キャンパス  51号館18階 第12教室 (51–18–12)
• 講演者：和田 秀男 (上智大学)
• 題名：数体篩い法による素因子分解

RSA合成数の素因数が見つかった件のさらなるその後

ちょっと昔の話になってしまいましたが、2009年5月3日に NHK のITホワイトボックス第３回「メールは盗み見られないのか？」が再放送されました。本ブログでは、この番組で紹介されていたRSA合成数は小さな素因数を持っていて実際の利用には不向きであることを指摘させていただきましたが、その後に再放送では訂正を施すことがNHKからアナウンスされていたため、どのように変更されているかが気になって視聴しました。

RSA合成数の素因数が見つかった件のその後

2009年4月16日(木)および2009年4月19日(日)にNHKの教育テレビで放映された「ＩＴホワイトボックス第３回 メールは盗み見られないのか？」という番組において、RSA暗号が使用している公開鍵の例として紹介された363桁の合成数が部分的に素因数分解できることを以前の記事で指摘させていただきました。この情報がNHKに届いたかどうかはわかりませんが、2009年4月23日(木)付けの What's New において、この合成数が実例として好ましくないこと、また同番組の再放送時には適切な合成数に差し替えることがアナウンスされていました。

本ブログでは、いろいろな記事・番組の内容の誤りを指摘されていただくことが多いのですが、今回のように、誤りを認めて新たな対応をとっていただける例は少なく、さらにはとても素早い対応であることから、その紳士的な態度に感心してしまいました。（お疲れさまです >> 中の方。また、このブログが発端だったのであれば、申し訳ありませんでした。）

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

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

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

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

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

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

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

NHK のITホワイトボックスという番組の第３回「メールは盗み見られないのか？」が今晩23時30分より放送予定の模様です。「暗号化」、「公開鍵暗号」、「クラック」がキーワードとのことです。要チェックかも。

関連記事

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

新しい素因数分解法？

Pollard がこんな素因数分解法を開発していたとは知りませんでした (via Tさんからのタレこみ)。

一瞬で素因数分解する方法

ちょっと煽りぎみのタイトルですが ^^;、興味ある方はこちらをどうぞ。

ITpro: 『なぜ暗号は当事者しか読めないのか？』

ITpro の『なぜ暗号は当事者しか読めないのか？』(2008年11月12日公開)という解説記事より。

タイトル通り、暗号の性質とアルゴリズムが紹介されているのですが、このお題に対する内容としてはおなじみの流れになっています。共通鍵暗号についてはふんふんといった感じで読み進められたのですが、公開鍵暗号(RSA暗号)にきては、どうしても突っ込みたくなる記述が出てきました。

IEICE: 『素因数分解の世界記録はいかに作られたか』 (会誌2008年6月号)

電子情報通信学会の学会誌の中から話題の記事を公開しているページを見つけました。2008年6月号の「素数」特集号に関しては、青木さんの『素因数分解の世界記録はいかに作られたか』が紹介されていました。このような、決して論文には載ることのない研究の進展は(素因数分解でなくとも)非常に貴重な経験の紹介だと思います。

Workshop on Integer Factorization

INRIA で素因数分解のワークショップが開催されるようです。日本からは Kazumaro Aoki さんが講演者として参加されるとのことです。