A Practical Collision-Based Power Analysis on RSA Prime Generation and Its Countermeasure

Sangyub Lee, Sung Min Cho, Heeseok Kim, Seokhie Hong

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


We analyze the security of RSA prime generation implemented on embedded devices by a practical power analysis attack. Unlike previous differential power analysis-based attack on primality tests of RSA prime generation exploiting the deterministic relationship among multiple prime candidates manipulated by consecutive primality tests, we propose a collision-based power analysis attack on the Miller-Rabin test for a single prime candidate which can recover the secret prime with a single attempt by exploiting collision characteristics of simple power analysis resistant modular exponentiation algorithms. Hence, our attack does not require the incremental prime search assumption and is applicable when countermeasures against previous attacks are deployed since it also does not require the assumption of trial divisions with small primes on prime candidates. For a realistic setting, where five 512-bit modular exponentiations are operated on an ARM Cortex-M4 microcontroller as recommended by FIPS 186-4 standard, we successfully recover the secret exponent to an extent that a feasible exhaustive search is needed for the full recovery of the secret prime. This is a first practical result of recovering a full secret of modular exponentiation which manipulates 512-bit RSA primitives with collision-based power analysis in a single attempt, where the previous attack demonstrates the result for 192-bit ECC primitive implementations. We also present a countermeasure against our attack which requires only one additional modular subtraction for the loop of square-and-multiply-always exponentiation algorithm. An experimental result for the effectiveness of our proposed countermeasure is presented.

Original languageEnglish
Article number8681035
Pages (from-to)47582-47592
Number of pages11
JournalIEEE Access
Publication statusPublished - 2019

Bibliographical note

Funding Information:
This work was supported by the Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Science and ICT under Grant NRF-2017R1C1B2004583.

Publisher Copyright:
© 2013 IEEE.


  • Cryptography
  • Digital signatures
  • Public key
  • Side-channel attacks

ASJC Scopus subject areas

  • General Computer Science
  • General Materials Science
  • General Engineering


Dive into the research topics of 'A Practical Collision-Based Power Analysis on RSA Prime Generation and Its Countermeasure'. Together they form a unique fingerprint.

Cite this