In the ROCA paper the authors define an integer M (which they call a primorial) as follows:
M = \prod_{i=1}^{n} P_i = 2 * 3 * ... * P_n
Said another way, M is the product of the first n primes. What the authors observed is that the factors of a vulnerable RSA modulus N have the following form:
p = k*M + (65537^a \text{ mod } M)
The 65537 (= \mathtt{0x10001}) might look a little odd hardcoded, but it's a common choice for the public exponent of an RSA key as it has a low hamming weight and thus allows some speed gains in common public key operations.
In the case you are interested in, where |N| = 512 bits, we have n = 39 and thus |M| = 219 bits. Since the size of the prime factors of N is \frac{|N|}{2} = 256 bits this implies:
|k| = \frac{|N|}{2} - |M| = 256 - 219 = 37
|a| = \mathbb{log}_{2}(\mathbb{order}_M(65537)) = 62
So to generate a vulnerable 512 bit RSA public key do the following:
- Randomly sample a 62 bit value a' and a 37 bit value k'.
- Compute p' = k'*M + (65537^{a'} \text{ mod } M).
- Check that p' is prime, if yes it is one of your factors p, if not go back to step 1.
- Sample another prime q using steps 1-3.
Your vulnerable RSA public key (N, e) = (p*q, 65537).
On to the attack. If M is known, our prime factor p now only has |k| + |a| = 37 + 62 = 99 bits of entropy rather than the 256 bits of entropy that it should. This is not good. The "naive" ROCA attack works in the following way:
- Select a guess for the value of a and compute 65537^{a} \text{ mod } M.
- Given 65537^{a} \text{ mod } M and the relationship p = k*M + (65537^a \text{ mod } M) use Coppersmith's Algorithm to recover k.
- Compute p using the recovered k and check if N \text{ mod } p = 0. If so, p is a factor of N. If not,go back to step 1. and select the next guess for a.
The time complexity for this attack is \mathcal{O}(2^{|a|}) = \mathcal{O}(2^{62}) since in the worst case we have to check every possible value of a. Note that the search space of a is the size of the group that 65537 generates \text{ mod } M.
Now I said "naive" ROCA attack above because the authors optimize this attack by finding a value M' such that the following relationship still holds:
p = k*M' + (65537^a \text{ mod } M')
But they find M' in such a way that the size of the group 65537 generates \text{ mod } M' is much smaller than \text{ mod }M. Thus the search space for a is also much smaller, and ends up bringing the time complexity down to \mathcal{O}(2^{20}). The actual process for finding M' is rather involved, if you'd like to know the details I'd suggest diving into the paper.