| Presentation | 2014-07-03 Security of RSA with Many Decryption Exponents Atsushi TAKAYASU, Noboru KUNIHIRO, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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)>>. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | RSA / Lattices / Coppersmith's method |
| Paper # | ISEC2014-19,SITE2014-14,ICSS2014-23,EMM2014-19 |
| Date of Issue |
| Conference Information | |
| Committee | SITE |
|---|---|
| Conference Date | 2014/6/26(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Social Implications of Technology and Information Ethics (SITE) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Security of RSA with Many Decryption Exponents |
| Sub Title (in English) | |
| Keyword(1) | RSA |
| Keyword(2) | Lattices |
| Keyword(3) | Coppersmith's method |
| 1st Author's Name | Atsushi TAKAYASU |
| 1st Author's Affiliation | The University of Tokyo() |
| 2nd Author's Name | Noboru KUNIHIRO |
| 2nd Author's Affiliation | The University of Tokyo |
| Date | 2014-07-03 |
| Paper # | ISEC2014-19,SITE2014-14,ICSS2014-23,EMM2014-19 |
| Volume (vol) | vol.114 |
| Number (no) | 116 |
| Page | pp.pp.- |
| #Pages | 4 |
| Date of Issue | |