[ Pobierz całość w formacie PDF ]
in the ship s amphorae for better or for worse, wine is
often preserved over millenia. I have drank ancient Greek
wine, and, believe me, it tastes worse than retsina, if any-
one can imagine that.
Gregory Ian Stevens III, New Haven
PS: A repository of information about the ancient world is
available at http://www.perseus.tufts.edu. For an inter-
esting discussion of the Antikythera mechanism, marine
archeology in the Aegean (and its joys and perils), and the
glory of Rhodos, see the document http://ccat.sas.upenn
.edu/rrice/usna_pap.html.
The best source of information and interpretation on the
Antikythera mechanism is still the book Gears from the
Greeks: The Antikythera Mechanism, a Calendar Computer
ca. 80 B.C. by D. D. Price (Science History Publications,
Turing (A Novel about Computation) 269
New York, 1974). But see also, for example, http://www
.giant.net.au/users/rupert/kythera/kythera.htm.
Subject: Cryptic about crypto
From: todo@cogsci.ucsd.edu
Date: September 10, 2002. 14:34 (GST)
Dear members of the book club, please pardon the pseudo-
nym and the phony untraceable address, routine precau-
tions for people with my skills, persuasion, and enemies.
(And gentlemen of the government: please leave my host
alone, cogsci.ucsd.edu was completely unaware of my exis-
tence until I broke in, from another temporary location, ten
minutes ago.)
Now, onward to our subject: The shallow, cavalier, and ul-
timately timid treatment of cryptography in the manuscript
Turing is the unmistakable sign that the author chose to
play it safe with a certain three-lettered government agency,
and cleared his text in advance with them (as is routinely
done these days with most publications dealing even tan-
gentially with cryptography). In case you are interested in a
less fictional (and less polyannaish) account, here goes:
In the early 1970s, the government, realizing that the
mushrooming computational technology would soon en-
able unbreakable codes and privacy for all citizens, con-
spired with IBM (then a virtual computer monopoly) to
launch the loathed data encryption standard (DES), a code
that only the government knew how to break. The DES used
a key of 64 bits, of which it inexplicably utilized only 56, to
define a sequence of murky transformations which, to the
untrained eye, looked cryptographically secure and un-
breakable. (However, as its designers knew, and certain
dedicated revolutionaries suspected, deep in the structure
of DES lay its planted and well-hidden weakness.)
270 Christos H. Papadimitriou
Enter public key cryptography. Rediscovered in the United
States in the late 1970s (after it was successfully sup-
pressed in England for two decades by the British branch of
the enemy), and popularly known by the first letters of the
last names RSA of the three people who discovered its
most clever embodiment, it seemed for the longest time the
world s great hope for achieving the goal of universal pri-
vacy, free of any government intrusion. Its description in
the manuscript is, not surprisingly, way too sketchy. Here
is mine:
As Turing explains, RSA is a public key cryptosystem. Bob
(the party wanting to receive secure messages) creates two
keys, of which one is kept secret, while the other is publicly
and proudly announced. The public key is the product n
of two primes p and q. (In the manuscript s example, which
is of course too small by a factor of 50 or so to be of any
cryptographic value, n is 1216592820951929, which is
indeed the product of two primes, p = 28173527 and q =
43182127 the manuscript curiously neglected to mention
that they should have remainder 2 when divided by 3 or
p = q =2 mod 3, as this is written in math (you see, mod x
added after an equation means that one should take the re-
mainders of both sides by x).
First question: How does one go about finding huge primes?
(You need to do that is you want to start your own bootleg
public key cryptosystem behind the back of the govern-
ment, right?) Easy. You see, primes have the following dis-
tinguishing property besides not being divisible by any
number besides 1 and themselves: If p is a prime, and you
raise any number x between 1 and p to the pth power, al-
ways taking the remainder by p, then the answer will be x,
the same number you started with. Try it. Raise 2 to the 7th
power, you get 128, which, when divided by 7 gives you re-
mainder 2. If p is not a prime and you try the same thing,
then the chances are overwhelming that you won t get x
back, and so you ll know p is not a prime. Repeat many
Turing (A Novel about Computation) 271
times to be sure, and you ve got your prime. (Oh, well, there
are these freak composite numbers called Carmichael
numbers, 561 is the smallest among them, that break this
rule. They behave like primes, but they are so rare, I per-
sonally guarantee to you you ll never stumble upon one.)
Now, to find a new prime, repeat this test for many numbers
x, and finally you ll get your prime. You see, if you have
a number with D decimal digits, and its last digit is
not 0,2,4,5,6,8 that would be stupid, right? then the
[ Pobierz całość w formacie PDF ]