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$ – AleksanderRas Aug 31 '18 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. Aug 31 '18 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.