The dark side of the web - The Computing Universe: A Journey through a Revolution - page 257

quick to do with a computer, but the reverse problem of factoring N - deduc-
ing the prime numbers that when multiplied together produce N - is very
difficult. Martin Gardner, in his “Mathematical Games” column in Scientific
American , explained public-key cryptography and the RSA asymmetric cipher
in August 1977. He issued a challenge to his readers by giving them a cipher-
text to decode that had been encrypted using a public key N, which he pub-
lished. The public key was a 129-digit number known as RSA-129. To decrypt
the message, the readers had to factor (break up) this number into its two
prime factors , the prime numbers that were multiplied together to produce the
129-digit number. It was almost seventeen years before a team of six hundred
volunteers assembled sufficient computing power to discover the two prime
number factors (see Fig. 12.15 ). When at last deciphered, Gardner's message
read, “The magic words are squeamish ossifrage” ( Fig. 12.16 ). Nowadays, given
the huge increase in computing power since 1977 generated by Moore's law,
much larger values than RSA-129 need to be used to secure messages and infor-
mation. These numbers are so large that it is estimated it would take all the
computing resources on the planet many thousands of years to factorize such
large numbers. However, as we will see later, such public-key systems could
be vulnerable to attack by a quantum computer if such a computer could be
built.
In the 1980s, only governments, the military, and large businesses had
computers that were powerful enough to use RSA efficiently. Phil Zimmermann
( B.12.8 ), a software engineer specializing in cryptography and data security,
believed that everyone should have the same guarantee of privacy in commu-
nications made possible by RSA encryption. Such a capability is particularly
important for human rights activists operating in countries with repressive
regimes. Even in more open countries, privacy of communications can be
regarded as a basic democratic freedom. The problem is that this same freedom
would also severely limit the ability of governments to monitor communica-
tions between criminals.
Zimmermann wrote a program that he called Pretty Good Privacy (PGP), a
name inspired by Ralph's Pretty Good Grocery , a business in Garrison Keillor's fic-
tional town of Lake Wobegon. In his PGP program, Zimmermann implemented
a fast version of the RSA public-key system. Unfortunately, he also chose to
ignore the fact that the RSA technology was patented. Zimmerman apparently

Fig. 12.15. The number RSA-129.
Multiplication is computationally “very
easy” whereas factorization of a number
into its constituent prime numbers is
computationally “very hard.” This is the
basis for the security of the RSA Public-
Key Cryptographic system.

Fig. 12.16. The original encrypted text of
Gardner's challenge.

B.12.7. Ron Rivest, Adi Shamir, and Len Adleman are the inventors of RSA public-key
cryptography protocol, which is now in widespread use. In their scheme, Alice now has
two keys - an encryption key that she makes public and her private decryption key.