250 15. A Glimpse of Complexity and Cryptography
You know the remainderr(this is the intercepted message). You also know
Alice’s public keye, and the numberm. One could think of two lines of
attack: Either you can figure out her private keydand then decrypt the
message just as she does, or you could somehow more directly find the
integerx, knowing the remainder ofxemodulom.
Unfortunately, there is no theorem stating that either of this is impossible
in less than astronomical time. But one can justify the security of the system
with the following fact:if one can break the RSA system, then one can use
the same algorithm to find the prime factors ofm(see Exercise 15.6.1). The
factorization problem has been studied by many people, and no efficient
method has been found, which makes the security of RSA quite probable.
15.6.1Suppose that Bob develops an algorithm that can break RSA in the
first, more direct, way described above: Knowing Alice’s public keymande,he
can find her private keyd.
(a) Show that he can use this to find the number (p−1)(q−1);
(b) from this, he can find the prime factorizationm=pq.The real world.How practical could such a complicated system be? It
seems that only a few mathematicians could ever use it. But in fact you
have probably used it yourself hundreds of times! RSA is used in SSL
(Secure Socket Layer), which in turn is used in https (secure http). Any
time you visit a “secure site” on the Internet (to read your e-mail or to
order merchandise), your computer generates a public and private key for
you, and uses them to make sure that your credit card number and other
personal data remain secret. It does not have to involve you in this at all;
all you notice is that the connection is a bit slower.
In practice, the two 100-digit primes are not considered sufficiently se-
cure. Commercial applications use more than twice this length, military
applications, more than 4 times.
While the hairy computations of raising the plain textxto an exponent
that itself has hundreds of digits are surprisingly efficient, it would still be
too slow to encrypt and decrypt each message this way. A way out is to
send, as a first message, the key to a simpler encryption system (think of
a one-time pad, although one uses a more efficient system in practice, like
DES, the Digital Encryption Standard). This key is then used for a few
minutes to encode the messages going back and force, then thrown away.
The idea is that in a short session, the number of encoded messages is not
enough for an eavesdropper to break the system.