| 講演名 | 2014-07-03 複数の復号指数を持つRSA暗号の安全性解析 高安 敦, 國廣 昇, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | RSA暗号の復号指数dが小さいときには,RSA法Nが効率的に素因数分解されることは広く知られている.BonehとDurfeeは,Coppersmithの格子を用いた攻撃を使い,d |
| 抄録(英) | When we use small secret exponents, RSA becomes efficient for its decryption cost and signature generation cost. However, it is widely known that too small secret exponents enables attackers to factor RSA modulus N efficiently. Boneh and Durfee used lattice based Coppersmith's method and proposed polynomial time algorithm to factor the modulus when d < N^<1-1/√<2>>. So far, the variants of the problem have been considered when there are k encryption/decryption exponents pairs. Howgrave-Graham and Seifert solved diophanine approximation problems and proposed a polynomial time algorithm to factor RSA modulus. When k → ∞, the algorithm works for even full size decryption exponents. Aono used the Coppersmith's method and proposed an algorithm. Though Aono's algorithm is better than the all previous ones for small k ≧ 2, when k → ∞, the algorithm only works when d < N^<3/4>. In this paper, we use the Coppersmith's method as Aono and propose improved algorithm. Our algorithm works when d < N^<1-√<2/(3k+1)>>. |
| キーワード(和) | RSA暗号 / 格子 / Coppersmithの手法 |
| キーワード(英) | RSA / Lattices / Coppersmith's method |
| 資料番号 | ISEC2014-19,SITE2014-14,ICSS2014-23,EMM2014-19 |
| 発行日 |
| 研究会情報 | |
| 研究会 | EMM |
|---|---|
| 開催期間 | 2014/6/26(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Enriched Multimedia (EMM) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 複数の復号指数を持つRSA暗号の安全性解析 |
| サブタイトル（和） | |
| タイトル（英） | Security of RSA with Many Decryption Exponents |
| サブタイトル（和） | |
| キーワード(1)（和/英） | RSA暗号 / RSA |
| キーワード(2)（和/英） | 格子 / Lattices |
| キーワード(3)（和/英） | Coppersmithの手法 / Coppersmith's method |
| 第 1 著者 氏名（和/英） | 高安 敦 / Atsushi TAKAYASU |
| 第 1 著者 所属（和/英） | 東京大学 The University of Tokyo |
| 第 2 著者 氏名（和/英） | 國廣 昇 / Noboru KUNIHIRO |
| 第 2 著者 所属（和/英） | 東京大学 The University of Tokyo |
| 発表年月日 | 2014-07-03 |
| 資料番号 | ISEC2014-19,SITE2014-14,ICSS2014-23,EMM2014-19 |
| 巻番号（vol） | vol.114 |
| 号番号（no） | 118 |
| ページ範囲 | pp.- |
| ページ数 | 4 |
| 発行日 | |