# Biased RSA moduli and ROCA

Say I can generate many 1024-bit RSA public keys $(N,e)$ with fixed public exponent $e = 65537$. They turn out to be heavily biased when computing $N \bmod x$ for small primes $x$. These congruences always seem to hold:

• $N \equiv 1 \pmod 2$
• $N \equiv 1 \pmod 3$
• $N \equiv 1 \pmod 5$
• $N \equiv 1 \pmod{11}$
• $N \equiv 1 \pmod{89}$

So $N = 29370 * k + 1$. What does this mean for $p$ and $q$? Can a ROCA-style attack be carried out? How does one use this information to factor $N$?

• Note that for the ROCA attack we know something about the form of $p$, a factor of $N$, namely $p = k * M + (65537^a \bmod{M})$. This reduces the total entropy of $p$ and allows us to brute force all possible values. I don't see a similar attack being in the cards with the relationship in your post. I make no statement on whether that means this form of modulus can or cannot be exploited. – puzzlepalace Feb 27 '18 at 0:54

The five equations you found are for sure not enough to break a 1024-bit key. Your first two equations one can easily explain. Being odd is necessary. Having $N = 1\bmod 3$ can come from the fact that the implementor of the library chose to generate only primes that are $2\bmod 3$ (like I always do). The reason for this choice is that usually one first tests the prime candidate $q$ (after a pre-selection using trial division or a sieve or something more creative) with a Fermat test, before inverting $e \bmod q-1$. But if $q = 1\bmod 3$ and a public exponent $e$ is given that is a multiple of $3$ (some like $e=3$), then the inversion always fails, so that a Fermat test would have been a waste of time.
For your other three equations I cannot imagine any reason. So try to find other restrictions for the RSA-keys generated by your library. What you should look for is if for some other small primes $p$ not all values $\ne 0\bmod p$ are possible, and if maybe the set of possible values is a subgroup of the multiplicative group $\mod p$ (i.e., closed under multiplication $\bmod p$). If you find such subgroups for different primes $p_1$ and $p_2$, you should then take a look also at the values $\bmod (p_1\cdot p_2)$, and if there are more restrictions. If, for example, you see that only the values $\pm 1\bmod 7$ and $\pm 1\bmod 13$ show up, then check if all values are $\pm 1\bmod 91$ or if also $27\bmod 91$ and $64\bmod 77$ are possible (which would be worse for the attacker).
For a successful attack you would have to hope that the modulus $N$ is modulo some small primes in certain subgroups, because both primes lie in those subgroups. This does not have to be so (it's quite easy to generate RSA-keys that look like they are vulnerable to the ROCA attack, but are perfectly safe), but it is a reasonable assumption for the lack of any other reason for it.
For using Coppersmith's method one would need to know the value of one of the primes $q$ modulo a product $\Pi$ of small primes which has bitlength more than 256 (for 1024-bit modulus $N$), better at least 270. For $\Pi$ big enough, a simple application of Coppersmith takes less than a second, so one can try it for some billions of possible values of $q\bmod \Pi$ to factor $N$.
So Coppersmith's method allows to factor $N$ even if the remaining entropy for the prime $q$ is still $>100$ bit (this was verified in the certification of the Infineon key generation), as long the entropy of $q\bmod\Pi$ is low enough.