I'm working on factorizing a ~450 bit key that I know has been generated with RSALib and thus is vulnerable to ROCA. Now reading the original paper, I can see that the primes are generated in the following form:

$$p = k \cdot M + (65537^{\,\large{a}} \bmod M)$$

where $k$ and $a$ are unknown value to us but where $M$ is known and is in fact the product of the first $j$ primes. Now in the original paper I was able to find that we know $j$ for some intervals but I'm not quite sure how to derive it for key length that are below 512 bits. Is there a way to do it?

  • $\begingroup$ I'm a little bit confused, are you asking for the number of primes below a certain number, say the number of primes below 1000? $\endgroup$ Commented Aug 31, 2018 at 9:09
  • $\begingroup$ No, basically RSALib has a predefined method for generating primes but I couldn't find any documentation for primes where the keysize is < 512 bits. $\endgroup$
    – S. L.
    Commented Aug 31, 2018 at 16:04


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.