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

MPQS (1985). Ironically, this possibility was addressed in the aforementioned
article: “Rivest and his associates have no proof that at some future time no
one will discover a fast algorithm for factoring composites as large as .... [but]
they consider the possibility extremely remote.” What was a problem that could
take millions of years in 1977; was reduced to mere months by 1994 owing to
such breakthroughs.
This is an appropriate juncture to introduce the notion of a mips year which
is defined to being equivalent to the computational power of a computer rated
at one million instructions per second (mips) and used for one year, which
is tantamount to approximately 3 10 13 instructions. The RSA-129 challenge ·

number took 5000 mips years.
There are numerous cryptosystems that are called equivalent to the di : culty
of factoring . For instance, there are RSA-like cryptosystems whose di8culty to
break is as hard as factoring the modulus. It can be shown that any cryptosys-
tem for which there is a constructive proof of equivalence to the di8culty of
factoring, is vulnerable to a chosen-ciphertext attack. 4.3 We have already seen
that factoring an RSA modulus allows the breaking of the cryptosystem, but
the converse is not known. In other words, it is not known if there are other
methods of breaking RSA, but some new attacks presented concerns.

Attacks on RSA
In what follows, the attacks on RSA must really be seen as attacks on par-
ticular implementations of RSA. Hence, taken together, the following present a
cogent argument and criteria for secure implementations of RSA.
In 1995, Paul Kocher, then a Stanford undergraduate, (see [139]) discovered
that RSA could be cryptanalyzed by recovering the decryption exponent through
a careful timing of the computation times for a sequence of decryptions. This
weakness was a surprising and unexpected discovery, 4.4 and although there are
means of thwarting the attack, it was another wake-up call. This is another
lesson for cryptographers: never to be overconfident, and always be alert to the
unexpected.
In order to understand this new attack, we need some statistical notions and
probabilistic notions; see Appendix E. Let R be a randomized algorithm (see
page 500) that produces t

as output where t is the amount of time it takes for
the computer to complete a calculation for a given input. We record the outputs
t 1 ,t 2 ,...,t r for given inputs and compute the mean m =( t 1 + t 2 +

∈ R

··· t r ) /r .

4.3 In a chosen-ciphertext attack, the cryptanalyst chooses the ciphertext and is given the
corresponding plaintext. This attack is most effective against public-key cryptosystems, but
sometimes is effective against symmetric-key ciphers as well. One way of mounting a chosen-
ciphertext attack is to obtain access to the machinery used to do the encryption. This was
accomplished prior to World War II when the Americans were able to replicate the Japanese
cipher machine, Purple (see page 89).
4.4 Two of the major reasons this attack was so stunning were that it came from a completely
unexpected area, and it is a ciphertext-only attack, which means the cryptanalyst has access
only to the ciphertext, obtained through interception of some cryptograms, from which to
deduce the plaintext, without any knowledge whatsoever of the plaintext.