Method for Approximating RSA Prime Factors
Aykan Inan · 2022
The security of Prime-Number-Generators (PNGs) is measured by the difficulty to predict their output. A PNG is defined to be correctly implemented if the next output sequence cannot be predicted with more than 0.5 (50%) chance of success without knowing the initial seed value. However, it was recently questioned in [14] if this criterion is still sufficient to provide adequate security if the generated primes are used for RSA encryption. This paper reinforces this claim and demonstrates how the entropy of randomly generated RSA prime factors p and q could be reduced by predicting up to seven decimal digits through a statistical distance analysis. As a proof of concept, two billion generated prime pairs were evaluated based on N = p · q and . Upper and lower boundaries as well as prime subregions related to could be identified. This allows to predict the first digits of a generated RSA prime with a probability up to 60%. Additionally, the PNG implementation only generates primes within a certain upper and lower boundary depending on their bit size.