Public-Key Cryptography - Codes: The Guide to Secrecy from Ancient to Modern Times - page 175

spectively. Given that gcd( e A ,e B ) = 1, the extended Euclidean algorithm allows
Eve to solve e A x + e B y = 1 for some x, y ∈ Z . Then, Eve calculates:

c A c B ≡ ( m e A ) x ( m e B ) y m e A x + e B y ≡ ≡ m (mod n ) ,

and this is done without knowledge of a factorization of n or of knowledge of
either private keys. This is called common modulus protocol failure (CMPF).
This is not a failure of the RSA cryptosystem, rather a very bad implementation
of it. In fact, the CMPF shows, in no uncertain terms, that an RSA modulus
should never be used by more than one entity. The CMPF illustrates the fact
that no matter how strong a cipher might be, a bad implementation of it will
render the scheme to be insecure, and useless. The true security of RSA requires
a proper implementation. For instance, even the RSA modulus size of 2048 bits
suggested above, is useless in the face of a bad implementation such as the
CMPF. We will come back to implementation issues below.
On pages 169 and 170, we discussed an instance that is tantamount to the
encryption and decryption of the RSA cipher. Therein, we talked about a notion
that we can now name.

The RSA Conjecture
Cryptanalyzing RSA must be as di8cult as factoring.

Although there is no proof of this conjecture, the aforementioned discussion
in the previous section tells us that the evidence is strong and the general
consensus is that the conjecture is valid. A good reason for believing this is
that the only known method for finding d given e is the extended Euclidean
algorithm applied to e and φ ( n ). Yet, to compute φ ( n ), we need to know p and
q , namely, we need to know how to factor n .
Given the above statement, it is worth a few more words on the extended
Euclidean algorithm. This algorithm calculates the gcd( e, φ ( n )), and when
gcd( e, φ ( n )) = 1, it calculates the e − 1 (mod φ ( n )). This is accomplished rel-
atively quickly.
Although factoring is indeed an intrinsically di8cult problem, it is nowhere
nearly as hard as it was at the inception of RSA. In Martin Gardiner's Scientific
American article [100], in 1977, it was trumpeted that it would take millions
of years to factor the RSA-129 challenge number. A reward of $100 (U.S.) was
offered at that time (see page 174). In 1994, however, reality got in the way of
that perception. After only eight months of trying, the authors of [10] factored
it. They used a variation of a factoring algorithm called the Multipolynomial
Quadratic Sieve (MPQS) (the details of which we discuss, along with other
factoring issues, in Appendix C. In fact, the reader desiring an in-depth look
at factoring and its consequences should consult this appendix for the details.)
The authors used over 600 researchers by distributing their quadratic sieve op-
erations to hundreds of physically separated computers all over the world. The
term for this is factoring by electronic mail coined by Lenstra and Manasse
in [148]. The lesson here is that we should never underestimate the potential
breakthroughs in mathematical factoring techniques such as CFRAC (1970) and