Scholarlink

In CHES2019, Aldaya et al. reported a vulnerability of the binary GCD algorithmBinary 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 the Coppersmith algorithm. Tani and Kunihiro proposed novel error correction algorithms in ACNS2023. In ACNS2023, they presented no experimental results about the overall attack, concretely the full key recovery phase. In this paper, we first optimize the parameters of the Coppersmith algorithm. Using the optimized parameters, we apply the Coppersmith algorithm 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.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Full Key Recovery on RSA from Noisy Binary GCD Operation Sequences

  • 章节

  • 出版模式：

    开放获取

  • 发表日期：

    2026年

查看全文
  • Kenta Tani,
  • Noboru Kunihiro

摘要

In CHES2019, Aldaya et al. reported a vulnerability of the binary GCD algorithmBinary 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 the Coppersmith algorithm. Tani and Kunihiro proposed novel error correction algorithms in ACNS2023. In ACNS2023, they presented no experimental results about the overall attack, concretely the full key recovery phase. In this paper, we first optimize the parameters of the Coppersmith algorithm. Using the optimized parameters, we apply the Coppersmith algorithm 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.