著者

青木 和麻呂

雑誌

情報処理

巻号頁・発行日

vol.51, no.8, pp.1030-1038, 2010-08-15

---

2009年12月12日(日本時間では13日),RSA-768と呼ばれる768ビットの合成数が素因数分解された.特別な形の合成数では以前に,より大きいものが素因数分解されているが,RSA公開鍵暗号に利用される大きな2素数の積の素因数分解に対しては,世界記録更新である.この記録は瑞,日,独,仏,蘭の5カ国の機関の研究者の共同作業の成果であり,筆者もこの作業に参加した.この素因数分解では,一般数体篩法(いっぱんすうたいふるいほう; GNFS)と呼ばれる代数的整数論を応用した方法が使われた.数体篩法を実際に実現するためには,概念的なアルゴリズムばかりではなく,細部の実装や計算資源の配分などが効率の重要な鍵を握っている.本稿では,数体篩法の概略を説明し,各ステップでの実装や計算機運用の問題点を紹介する.最後に,従来よりRSA公開鍵暗号で1024ビットの公開鍵の新規利用は推奨できないことが指摘されていたが,今回768ビットの合成数が現実に素因数分解されたことはこの指摘を補強するものであることを付け加えておく.

著者

佐々木 悠 王 磊 太田 和夫 青木 和麻呂 國廣 昇

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会ソサイエティ大会講演論文集

巻号頁・発行日

vol.2008, 2008-09-02

---

本稿では,MD4を用いたチャレンジ&レスポンス型パスワード認証に対し,現実的な計算量のパスワード復元攻撃を提案する.これらの方式では,ユーザとサーバはパスワードPを事前共有する.認証の手順は以下の通り:1.サーバはチャレンジCを生成しユーザに送る.2.ユーザはレスポンスRとしてResponse(P,C)を計算しサーバに送る.3.サーバは自分でRを計算し,送られてきたRと一致したならば正規ユーザと判定する. 手順2.のRの計算方法として,MD4(P∥C)を用いるPrefix法とMD4(P∥C∥P)を用いるHybrid法が有力である.これらに対する攻撃結果を以下に示す.

著者

青木 和麻呂

出版者

一般社団法人情報処理学会

雑誌

情報処理 (ISSN:04478053)

巻号頁・発行日

vol.51, no.8, pp.1030-1038, 2010-08-15

参考文献数

6

---

2009年12月12日(日本時間では13日),RSA-768と呼ばれる768ビットの合成数が素因数分解された.特別な形の合成数では以前に,より大きいものが素因数分解されているが,RSA公開鍵暗号に利用される大きな2素数の積の素因数分解に対しては,世界記録更新である.この記録は瑞,日,独,仏,蘭の5カ国の機関の研究者の共同作業の成果であり,筆者もこの作業に参加した.この素因数分解では,一般数体篩法(いっぱんすうたいふるいほう; GNFS)と呼ばれる代数的整数論を応用した方法が使われた.数体篩法を実際に実現するためには,概念的なアルゴリズムばかりではなく,細部の実装や計算資源の配分などが効率の重要な鍵を握っている.本稿では,数体篩法の概略を説明し,各ステップでの実装や計算機運用の問題点を紹介する.最後に,従来よりRSA公開鍵暗号で1024ビットの公開鍵の新規利用は推奨できないことが指摘されていたが,今回768ビットの合成数が現実に素因数分解されたことはこの指摘を補強するものであることを付け加えておく.

著者

青木 和麻呂 太田 和夫 荒木 志帆 松井 充

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. ISEC, 情報セキュリティ

巻号頁・発行日

vol.94, no.56, pp.47-60, 1994-05-20

被引用文献数

2

---

線形解読法をFEAL-8に適用した場合の安全性評価の実験結果を報告する。線形解読法では1)偏差率の大きい線形表現を見つれること、2)解読の計算量と記憶容量を計算機実験可能な範囲におさまるように実効ビット数を押えること、が重要である。従来知られているBihamの線形表現(偏差率は2^-11>)より大きい偏差率(1.149×2^-8>)の7段線形表現を発現し、線形表現における鍵ビット、テキストビットの影響を注意深く観測することで実効ビット数を削減して、FEAL-8に対する線形攻撃法をワークステーションで実装可能にした。計算機実験(SPARCstation 10 Model 30)を行なったところ、既知平文数2^25>個では1時間程度で70%以上、2^26>個では1時間強でほぼ100%の成功率ですべての拡大鍵を導けることを確認した。