Bad choice of parameters: common modulus, Wiener

Even with good padding, RSA falls if the parameters are badly chosen. Here are the classic mistakes on p, q, d and n.

The common modulus

Dangerous belief: "you can share the same n between several people, each having their own pair (e, d)". This is false. Two users who share n can read each other's messages: each knows the factorisation of n (or can recover it from their own d), thus reconstructs φ(n), thus the neighbour's private key. A modulus must serve only one single key pair.

The private exponent too small: Wiener

One may be tempted to choose a small d to speed up decryption. Mistake. The Wiener attack (1990) exploits the relation e × d ≡ 1 (mod φ(n)). By expanding the fraction e / n into continued fractions, you recover d as soon as:

d < (1/3) × n^(1/4)

The attack is fast and requires only the public key (n, e). Moral: keep d large (and rather choose a small e, like 65537, which is harmless).

Primes too close: Fermat

If p and q are close to each other, Fermat factorisation breaks n in a few attempts. It looks for n = a^2 - b^2 = (a-b)(a+b) starting from a = ceil(sqrt(n)) and going up. When p and q are neighbours, a is barely larger than sqrt(n) and b is small: found almost immediately. So you need distant and well-randomised primes.

Weak randomness: the shared GCD

If two moduli n1 = p × q1 and n2 = p × q2 share by bad luck a same factor p (faulty randomness generators), a simple GCD breaks them both:

pgcd(n1, n2) = p        puis   q1 = n1 / p,   q2 = n2 / p

In 2012, a study collected millions of public keys on the Internet and, by computing pairwise GCDs, factorised tens of thousands of real RSA keys, solely because their randomness was bad. This is the "key debacle" (Mining your Ps and Qs).

Table of parameter mistakes

+---------------------------+------------------------+---------------------------+
| Erreur                    | Attaque                | Parade                    |
+---------------------------+------------------------+---------------------------+
| Module n partagé          | lecture croisée        | 1 module = 1 seule paire  |
| Exposant prive d trop petit| Wiener (fract. cont.) | d grand, e petit (65537)  |
| p et q trop proches       | factorisation de Fermat| premiers eloignes         |
| Alea faible (p commun)    | PGCD de deux modules   | bon generateur aleatoire  |
+---------------------------+------------------------+---------------------------+

In summary

RSA requires impeccable parameters: never a common modulus, a sufficiently large d (otherwise Wiener), primes p and q that are distant (otherwise Fermat) and truly random (otherwise a shared GCD, as in 2012). The security of RSA is decided as much in key generation as in the algorithm.