3
$\begingroup$

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$?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – puzzlepalace Feb 27 '18 at 0:54
2
$\begingroup$

A similar observation as yours was the starting point for the ROCA attack. In 2016, some of the authors of the ROCA attack (with other coauthors) had published a paper a USENIX about determining the origin of RSA keys. Some SW-libraries or smart cards generate public RSA-keys with certain characteristics that allow to identify with high probability which library was used given in some cases just one and in other cases just few public RSA keys.

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.

| improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.