Cryptography Reference
In-Depth Information
schemes. Each of these problems involves different
computational assump-
tions
, distinct conjectures about the difficulty of calculating inverse func-
tions for the scheme. The RSA paper also spurred immediate interest in
several hitherto obscure areas of applied mathematics: factoring, prime
number generation, and modular exponentiation, the main numerical
operation in RSA encryption and decryption.
13
To cryptography's public image as an esoteric alchemical experiment
with the mathematics of language, number theory added an equally pow-
erful mystique: prime numbers and their mysterious Platonic properties.
No other mathematical object conjures such powerful feelings among
mathematicians: “Upon looking at these numbers, one has the feeling of
being in the presence of one of the inexplicable secrets of creation.”
14
In
his final collection of essays, popular scientist Martin Gardner uses them
to justify his unwavering commitment to mathematical Platonism: “If all
sentient beings in the universe disappeared,” he writes, “there would
remain a sense in which mathematical objects and theorems would con-
tinue to exist even though there would be no one around to write or talk
about them. Huge prime numbers would continue to be prime even if no
one had proved them prime.”
15
Combined with binary encoding, they
are the purest expression of signal versus noise, enabling the creation of
messages “that makes communication transparently simple.”
16
Indeed,
the binary encoding of prime numbers forms the basis for the messages
sent by extraterrestrial beings in Carl Sagan's
Contact
and part of the
message sent to potential alien life forms by the Arecibo radio telescope.
The publication of the RSA paper (first as a technical report) was imme-
diately picked up by science journalists: Gina Kolata reported on it in
Science
, and Martin Gardner devoted a column to the “MIT cipher” in the
August 1977 issue of
Scientific American
.
17
Gardner's column, “A New Kind
of Cipher That Would Take Millions of Years to Break,” gave birth to an
enduring genre of cryptographic research rhetoric, the
key factorization
contest
, as he called readers to a challenge to break a message enciphered
with RSA using a key of 129 bits by recovering the factors
p
and
q
of the
public key. “Millions of years” turned into the slightly shorter period of
seventeen years, as the ciphertext “the magic words are squeamish ossi-
frage” was revealed in 1994.
18
Spurred on by the increase of interest in
public key cryptography, mathematicians had significantly improved the
efficiency of existing factoring algorithms, and in the ensuing decades,
