| Presentation | 2023-03-14 Full key recovery of RSA secret key from noisy binary GCD operation sequences Kenta Tani, Noboru Kunihiro, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | In CHES2019, Aldaya et al. reported a vulnerability of the binary GCD algorithm used in RSA key generation in OpenSSL.Furthermore, they proposed an attack that exploits this vulnerability.The attack consists roughly of (1) collecting the sequences of operations performed in the binary GCD algorithm using a side-channel attack, (2) error correction to generate candidate solutions for the LSBs of the secret key, and (3) full key recovery using Coppersmith's method.We proposed error correction algorithms in SCIS2021 and CSS2022.Furthermore, we analyzed the probability distribution of errors in SCIS2022.In SCIS2021 and CSS2022, We did not evaluate the overall attack, including the full key recovery phase.In this paper, we first optimize the parameters of the Coppersmith method.Using the optimized parameters, we actually apply the Coppersmith's method to the candidate solutions and evaluate the success rate and execution time.This allows for a more rigorous evaluation of the success rate and execution time of the overall attack. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | RSA / Error correction algorithm / Coppersmith's method / binary GCD algorithm |
| Paper # | IT2022-74,ISEC2022-53,WBS2022-71,RCC2022-71 |
| Date of Issue | 2023-03-07 (IT, ISEC, WBS, RCC) |
| Conference Information | |
| Committee | RCC / ISEC / IT / WBS |
|---|---|
| Conference Date | 2023/3/14(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Shunichi Azuma(Nagoya Univ.) / Noboru Kunihiro(Tsukuba Univ.) / Tetsuya Kojima(Tokyo Kosen) / Takashi Shono(Wind River) |
| Vice Chair | Shunichi Azuma(Hokkaido Univ.) / Koji Ishii(Kagawa Univ.) / Junji Shikata(Yokohama National Univ.) / Goichiro Hanaoka(AIST) / Yasuyuki Nogami(Okayama Univ.) / Hiroyasu Ishikawa(Nihon Univ.) / Hideki Ochiai(Yokohama National Univ.) |
| Secretary | Shunichi Azuma(CRIEPI) / Koji Ishii(Ritsumeikan Univ.) / Junji Shikata(AIST) / Goichiro Hanaoka(Ibaraki Univ.) / Yasuyuki Nogami(Saitamai Univ.) / Hiroyasu Ishikawa(Nagaoka Univ. of Tech.) / Hideki Ochiai(Okayama Prefectural Univ.) |
| Assistant | SHAN LIN(NICT) / Ryosuke Adachi(Yamaguchi Univ.) / Yoshikazu Hanatani(Toshiba) / Takayuki Nozaki(Yamaguchi Univ.) / Sun Ran(Ibaraki Univ.) / Chen Na(NAIST) |
| Paper Information | |
| Registration To | Technical Committee on Reliable Communication and Control / Technical Committee on Information Security / Technical Committee on Information Theory / Technical Committee on Wideband System |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Full key recovery of RSA secret key from noisy binary GCD operation sequences |
| Sub Title (in English) | |
| Keyword(1) | RSA |
| Keyword(2) | Error correction algorithm |
| Keyword(3) | Coppersmith's method |
| Keyword(4) | binary GCD algorithm |
| 1st Author's Name | Kenta Tani |
| 1st Author's Affiliation | University of Tsukuba(Univ. of Tsukuba) |
| 2nd Author's Name | Noboru Kunihiro |
| 2nd Author's Affiliation | University of Tsukuba(Univ. of Tsukuba) |
| Date | 2023-03-14 |
| Paper # | IT2022-74,ISEC2022-53,WBS2022-71,RCC2022-71 |
| Volume (vol) | vol.122 |
| Number (no) | IT-427,ISEC-428,WBS-429,RCC-430 |
| Page | pp.pp.41-48(IT), pp.41-48(ISEC), pp.41-48(WBS), pp.41-48(RCC), |
| #Pages | 8 |
| Date of Issue | 2023-03-07 (IT, ISEC, WBS, RCC) |