Edgar Allan Poe, the renowned American poet and writer, was captiva...
The price of sending a letter in the United States has steadily inc...
### One-time pad
The one-time pad (OTP) is a type of encryption th...
According to historical accounts, such as Suetonius' "Lives of the ...
Rudolf Ivanovich Abel, whose real name was William August Fisher, w...
#### Caesar cipher
A Caesar cipher, also known as a shift cipher, ...
Whitfield Diffie and Martin Hellman are two renowned American crypt...
The message encoded in this ciphertext was deciphered in 1994. The ...
RSA is an asymmetric encryption algorithm that builds upon the grou...
Fermat's little theorem is named after the 17th-century French math...
Despite the original estimate, the prime factors were actually foun...
Two numbers are considered relatively prime (or coprime) if their g...
I -
f
MATHEMATICAL
GAMES
A new kind of cipher that would
take millions of
years
to break
by Martin Gardner
i
v.
;
"Few persons can be made to believe
that it is not quite an easy thing to invent
a method of secret writing which shall
baffle investigation. Yet it may be
roundly asserted that human ingenuity
cannot concoct a cipher which human
ingenuity cannot resolve."
—EDGAR ALLAN POE
T
he upward creep of postal rates
accompanied by the deterioration
of postal service is a trend that
>
inay or may not continue, but as far as
"[most private communication is con-
cerned, in a few decades it probably will
«ot
;
matter. The reason is simple. The
: transfer of information will probably be
much faster and much cheaper by "elec-
tronic mail" than by conventional postal
- systems. Before long it should be possi-
ble to go to any telephone, insert a mes-
sage into an attachment and dial a num-
ber. The telephone at the other end will
print out the message at once.
Government agencies and large busi-
nesses will presumably be the first to
make extensive use of electronic mail,
followed by small businesses and pri-
vate individuals. When this starts to
happen, it will become increasingly de-
. sirable to have fast, efficient ciphers to
safeguard information from electronic
eavesdroppers. A similar problem is in-
volved in protecting private information
stored in computer memory banks from
snoopers who have access to the mem-
. ory through data-processing networks.
It is hardly surprising that in recent
years a number of mathematicians have
asked themselves: Is it possible to devise
a cipher that can be rapidly encoded and
decoded by computer, can be used re-
peatedly without changing the key and
ABCDEFGHI JKLMNOPQR
01 23456789ABCDEFGH
STUVWXYZ0123456789
IJKLMNOPQRSTUVWXYZ
A Caesar cipher with a 10-shift
is unbreakable by sophisticated crypt-
analysis? The surprising answer is yes.
The breakthrough is scarcely two years
old, yet it bids fair to revolutionize the
entire field of secret communication. In-
' deed, it is so revolutionary that all previ-
ous ciphers, together with the tech-
niques for cracking them, may soon
fade into oblivion.
An unbreakable code can be unbreak-
able in theory or unbreakable only in
practice. Edgar Allan Poe, who fancied
himself a skilled cryptanalyst, was con-
vinced that no cipher could be invented
that could not also be "unriddled." Poe
was certainly wrong. Ciphers that are
unbreakable even in theory have been in
use for half a century. They are "one-
time pads," ciphers that are used only
once,
for a single message. Here is a sim-
ple example based on a shift cipher,
sometimes called a Caesar cipher be-
cause Julius Caesar used it.
First write the alphabet, followed by
the digits 0 through 9. (For coding pur-
poses 0 represents a space between
words, and the other digits are assigned
to punctuation marks.) Below this write
the same sequence cyclically shifted to
the right by an arbitrary number of
units,
as is shown in color in the illustra-
tion on this page. Our cipher consists in
taking each symbol in the plaintext (the
message), finding it in the top row, and
replacing it with the symbol directly be-
low it. The result is a simple substitution
cipher, easily broken by any amateur.
In spite of its simplicity, a shift cipher
can be the basis of a truly unbreakable
code.
The trick is simply to use a dif-
ferent shift cipher for each symbol in
the plaintext, each time choosing the
amount of shift at random. This is easily
done with the spinner shown in the top
illustration on the opposite page. Sup-
pose the first word of plaintext is
THE.
We spin the arrow and it stops on
K.
This
tells us to use for encoding T a Caesar
cipher in which the lower alphabet is
shifted 10 steps to the right, bringing A
below K as is shown in the illustration.
T, therefore, is encoded as J. The same
procedure is followed for every symbol
in the plaintext. Before each symbol is
encoded, the arrow is spun and the low-
er sequence is shifted accordingly. The
result is a ciphertext starting with j and
a cipher "key" starting with K. Note
that the cipher key will be the same
length as the plaintext.
To use this one-time cipher for send-
ing a message to someone—call him Z—
we must first send Zthe key. This can be
done by a trusted courier. Later we send
to Z, perhaps by radio, the ciphertext. Z
decodes it with the key and then de-
stroys the key. The key must not be used
again because if two such ciphertexts
were intercepted, a cryptanalyst might
have sufficient structure for breaking
them.
It is easy to see why the one-time ci-
pher is uncrackable even in principle.
Since each symbol can be represented
by any other symbol, and each choice of
representation is completely random,
there is no internal pattern. To put it
another way, any message whatever
having the same length as the ciphertext
is as legitimate a decoding as any other.
Even if the plaintext of such a coded
message is found, it is of no future help
to the cryptanalyst because the next
time the system is used the randomly
chosen key will be entirely different.
One-time pads are in constant use to-
day for special messages between high
military commanders, and between gov-
ernments and their high-ranking agents.
The "pad" is no more than a long list of
random numbers, perhaps printed on
many pages. The sender and receiver
must of course have duplicate copies.
The sender uses page 1 for a cipher, then
destroys the page. The receiver uses his
page 1 for decoding, then destroys his
page.
When the Russian agent Rudolf
Abel was captured in New York in
1957,
he had a one-time pad in the form
of a booklet about the size of a postage
stamp. David Kahn, who tells the story
in his marvelous history The Codebreak-
ers,
says that the one-time pad is the
standard method of secret radio com-
munication used by the U.S.S.R. The fa-
mous "hot line" between Washington
and Moscow also makes use of a one-
time pad, the keys being periodically de-
livered through the two embassies.
If the one-time pad provides absolute
secrecy, why is it not used for all secret
communication? The answer is that it is
too impractical. Each time it is em-
ployed a key must be sent in advance,
and the key must be at least as long as
the anticipated message. "The problem
of producing, registering, distributing
and canceling the keys," writes Kahn,
"may seem slight to an individual who
has not had experience with military
communications, but in wartime the
volumes of traffic stagger even the signal
staffs.
Hundreds of thousands of words
may be enciphered in a day; simply to
generate the millions of key characters
required would be enormously expen-
sive and time-consuming. Since each
messaj
cation
shippii
equiva
volum
Let i
ing it i
peated
Until r
kind v
breaka
has en<
Then i
propos
ation \
"unbre
from t
known
cipher;
in the
practic
strong!
ly desi;
ciple tl
but on]
for mi]
The
marka
Dime
electric
sity. T
by the
in 197
per "N
(IEEE
ory, Ni
Hellm;
able ci
sendin;
the mi
can be
they c;
and th
provid
unlike
forged
from y
A actu
As sig
eavesd
The;
made ]
man c;
Such a
erties:
teger x
it has a
back ti
for col
tion an
tion a
known
to disc
The
that gi'
a trapi
hard H
possibJ
less on
is hide
"trapd'
cannot
the bui
message must have its unique key, appli-
cation of the ideal system would require
shipping out on tape at the very least the
equivalent of the total communications
volume of a war."
Let us qualify Poe's dictum by apply-
ing it only to ciphers that are used re-
peatedly without any change in the key.
Until recently all cipher systems of this
kind were known to be theoretically
breakable provided the code breaker
has enough time and enough ciphertext.
Then in 1975 a new kind of cipher was
proposed that radically altered the situ-
ation by supplying a new definition of
"unbreakable," a definition that comes
from the branch of computer science
known as complexity theory. These new
ciphers are not absolutely unbreakable
in the sense of the one-time pad, but in
practice they are unbreakable in a much
stronger sense than any cipher previous-
ly designed for widespread use. In prin-
ciple these new ciphers can be broken,
but only by computer programs that run
for millions of years!
The two men responsible for this re-
markable breakthrough are Whitfield
Difne and Martin E. Hellman, both
electrical engineers at Stanford Univer-
sity. Their work was partly supported
by the National Science Foundation
in 1975 and was reported in their pa-
per "New Directions in Cryptography"
(IEEE
Transactions
on Information The-
ory, November, 1976). In it Dime and
Hellman show how to create unbreak-
able ciphers that do not require advance
sending of a key or even concealment of
the method of encoding. The ciphers
can be efficiently encoded and decoded,
they can be used over and over again
and there is a bonus: the system also
provides an "electronic signature" that,
unlike a written signature, cannot be
forged. If Zreceives a "signed" message
from A, the signature proves to Z that
A actually sent the message. Moreover,
A's
signature cannot be forged by an
eavesdropper or even by Z
himself!
These seemingly impossible feats are
made possible by what Dime and Hell-
man call a trapdoor one-way function.
Such a function has the following prop-
erties:
(1) it will change any positive in-
teger x to a unique positive integer y; (2)
it has an inverse function that changes y
back to x; (3) efficient algorithms exist
for computing both the forward func-
tion and its inverse: (4) if only the func-
tion and its forward algorithm are
known, it is computationally infeasible
to discover the inverse algorithm.
The last property is the curious one
that gives the function its name. It is like
a trapdoor: easy to drop through but
hard to get up through. Indeed, it is im-
possible to get up through the door un-
less one knows where the secret button
is hidden. The button symbolizes the
"trapdoor information." Without it one
cannot open the door from below, but
the button is so carefully concealed that
9 A
w
u
S R
Randomizer for encoding a "one-time pad"
the probability of finding it is practically
zero.
Before giving a specific example, let
us see how such functions make the new
cryptographic systems possible. Sup-
pose there is a group of businessmen
who want to communicate secrets to one
another. Each devises his own trapdoor
function with its forward and backward
algorithms. A handbook is published in
which each company's encoding (for-
ward) algorithm is given in full. The de-
coding (inverse) algorithms are kept se-
cret. The handbook is public. Anyone
can consult it and use it for sending a
secret message to any listed company.
Suppose you are not a member of the
group but you want to send a secret mes-
sage to member Z First you change
your plaintext to a long number, using a
standard procedure given in the hand-
book. Next you look up Z's forward al-
gorithm and your computer uses it for
rapid encoding of the ciphertext. This
new number is sent to Z. It does not
matter at all if the ciphertext is over-
heard or intercepted because only Z
knows his secret decoding procedure.
There is no way a curious cryptanalyst,
studying Z's public encoding algorithm,
can discover Z's decoding algorithm. In
principle he might find it, but in practice
that would require a supercomputer and
a few million years of running time.
An outsider cannot "sign" a message
to Z, but any member of the group can.
Here is the devilishly clever way the sig-
nature works. Suppose A wants to sign a
message to Z. He first encodes the plain-
text number by using his own secret in-
verse algorithm. Then he encodes the
ciphertext number a second time, using
Z's public algorithm. After Z receives
the ciphertext he first transforms it by
applying his own secret decoding algo-
rithm, then he applies A s public encod-
ing algorithm. Out comes the message!
Z knows that only A could have sent
this doubly encoded ciphertext because
it made use of A s secret algorithm. A
*s
"signature" is clearly unforgeable. Z
cannot use it to send a message purport-
ing to come from A because Z still does
9686
1477
8829
7431
0816
3569
8962
1829
9613
1409
0575
9874
2982
3147
8013
9451
7546
2225
9991
6951
2514
6622
3919
5781
2206
4355
1245
2093
5708
8839
9055
5154
A ciphertext challenge worth $100
121
1
1
J
1
1
j
1
I
I
I
I
-
r
\
10
The answers to last month's bisection problems
1
__ 1
I
1
|
i
r~
i
1
1
H
1
H
•
i
L.
1—
.J
1
H
r
.j
i
i j
1
r-
Dividing polyominoes into four congruent parts
not know ,4 's secret decoding algorithm.
Not only that, but if it were to become
necessary at some future time to prove
to a third party, say a judge in a court of
law, that A did in fact send the message,
this can be done in a way that neither A,
Z nor anyone else can dispute.
Dime and Hellman suggested in their
paper a variety of trapdoor functions
that might be used for such systems.
None is quite what is desired, but early
this year there was a second break-
through. Ronald L. Rivest, Adi Shamir
and Leonard Adleman, computer scien-
tists at the Massachusetts Institute of
Technology, developed an elegant way
to implement the Diffie-Hellman system
by using prime numbers.
Rivest obtained his doctorate in com-
puter science from Stanford University
in 1973 and is now an associate profes-
sor at M.I.T. Once he had hit on the
brilliant idea of using primes for a pub-
lic cipher system, he and his two collab-
orators had little difficulty finding a sim-
ple way to do it. Their work, supported
by grants from the NSF and the Office of
Naval Research, appears in On Digital
Signatures and Public-Key Cryptosystems
(Technical Memo 82, April, 1977), is-
sued by the Laboratory for Comput-
er Science, Massachusetts Institute of
Technology, 545 Technology Square,
Cambridge, Mass. 02139. The memo-
randum is free to anyone who writes
Rivest at the above address enclosing
a self-addressed, 9-by-12-inch clasp en-
velope with 35 cents in postage.
To explain Rivest's system we need a
bit of background in prime-number the-
ory. The fastest-known computer pro-
grams for deciding whether a number is
prime or composite (the product of
primes) are based on a famous theory of
Fermat's stating that if p is prime, and a
is any positive number less than p. then
a
p-\
= i (modulo p). Suppose we want
to test a large odd number n (all primes
except 2 are of course odd) for primali-
ty. A number a is selected at random
and raised to the power of n — 1, then
divided by n. If the remainder is not
1,
n cannot be prime. For example,
22i-i = 4 (modulo 21), therefore 21 is
composite. What, however, is the con-
nection between 2 (the randomly chosen
a) and 3 and 7, the two prime factors of
21? There seems to be no connection
whatever. For this reason Fermat's test
is useless in finding prime factors. It
does,
however, provide a fast way of
proving that a number is composite.
Moreover, if an odd number passes the
Fermat test with a certain number of
random as, it is almost certainly prime.
This is not the place to go into more
details about computer algorithms for
testing primality, which are extremely
fast, or algorithms for factoring com-
posites, all of which are infuriating-
ly slow. I content myself with the fol-
lowing facts, provided by Rivest. They
dramatize the staggering gap in the re-
quired computer time between
the two
kinds
of
testing.
For
example,
to
test
a
130-digit
odd
number
for
primality
re-
quires
at the
most (that
is,
when
the
number actually
is
prime) about seven
minutes
on a
PDP-10 computer.
The
same algorithm takes only
45
seconds
to
find
the
first prime after
2
200
.
(It is a 61-
digit number equal
to
2200
+ 235.)
Contrast this with
the
difficulty
of
finding
the two
prime factors
of a 125-
or 126-digit number obtained
by
multi-
plying
two
63-digit primes.
If the
best
algorithm known
and the
fastest
of to-
day's computers were used, Rivest esti-
mates that
the
running time required
would
be
about
40
quadrillion years!
(For
a
good discussion
of
computer
methods
of
factoring into primes,
see
Donald
E.
Knuth's Seminumerical Algo-
rithms, Section 4.5.4.)
It is
this practical
impossibility,
in any
foreseeable future,
of factoring
the
product
of two
large
primes that makes
the
M.I.T. public-key
cipher system possible.
To explain
how the
system works,
the
M.I.T. authors take
as an
example
of
plaintext
a
paraphrase
of a
remark
in
Shakespeare's Julius Caesar
(Act 1,
Scene 2):
ITS ALL
GREEK
TO ME.
This
is
first changed
to a
single
num-
ber, using
the
standard
key: A = 01, B
=
02 z =
26, with
00
indicating
a
space between words.
The
number
is
09201900011212000718050511002015
001305.
The entire number
is now
encoded
by
raising
it to a
fixed power
s,
modulo
a
certain composite number
r. The com-
posite
r is
obtained
by
randomly select-
ing (using
a
procedure given
in the
M.I.T. memorandum)
two
primes,
p and
q, each
of
which
is at
least
40
digits long,
and multiplying them together.
The
number
s
must
be
relatively prime
to
p
- 1 and q - 1.
Numbers
s and r are
made public,
to be
used
in the
encoding
algorithm.
The
encoding operation
can
be done very efficiently even
for
enor-
mous values
of r;
indeed,
it
requires less
than
a
second
of
computer time.
The
two
prime factors
of r are
with-
held,
to
play
a
role
in the
secret inverse
algorithm. This inverse algorithm, used
for decoding, consists
in
raising
the ci-
phertext number
to
another power
/,
then reducing
it to
modulo
r. As
before,
this takes less than
a
second
of
computer
time.
The
number
/,
however,
can be
calculated only
by
someone
who
knows
p
and q, the two
primes that
are
kept
secret.
If
the
message
is too
long
to be han-
dled
as a
single number,
it can be
broken
up into
two or
more blocks
and
each
block
can be
treated
as a
separate
num-
ber.
I
shall
not go
into more details.
They
are a bit
technical
but are
clearly
explained
in the
M.I.T. memo.
To encode ITS ALL
GREEK
TO ME,
the M.I.T. group
has
chosen
s =
9,007
and
r=
1143816257578888676692357
79976146612010218296721242362562
A
^_—-—
[
i*
)
C
Solutions
to
four equal-division problems
56184293570693524573389783059712
35639587050589890751475992900268
79543541.
The number
r is the
product
of a
64-digit prime
p and a
65-digit prime
q,
each randomly selected.
The
encoding
algorithm changes
the
plaintext
num-
ber (09201...)
to the
following cipher-
text number: 1999$ 513\149780510045
23171227402606474232040170583914
63103703717406259716089489275043
09920962672582675012893554461353
823769748026.
As
a
challenge
to
Scientific American
readers
the
M.I.T. group
has
encoded
another message, using
the
same public
algorithm.
The
ciphertext
is
shown
in
the bottom illustration
on
page 121.
Its
plaintext
is an
English sentence.
It was
first changed
to a
number
by the
stan-
dard method explained above, then
the
entire number
was
raised
to the
9,007th
power (modulo
r) by the
shortcut meth-
od given
in the
memorandum.
To the
first person
who
decodes this message
the M.I.T. group will give
$100.
To prove that
the
offer actually comes
from
the
M.I.T. group,
the
following
signature
has
been added: 1671786
v\ 5
031808442460152t713 89168$ 982^54369
01D32
J15
83
hi
21783 5O0'8446929j)626l55
£792£37llr4490S09}5786p865lS662y9
\^ 84dj)040$702P3 73.
The signature
was
encoded
by
using
the secret inverse
of the
encoding algo-
rithm. Since
the
reader
has no
public
en-
coding algorithm
of his own, the
second
encoding operation
has
been omitted.
Any reader who
has
access
to a
comput-
er
and the
instructions
in the
M.I.T.
memorandum
can
easily read
the
signa-
ture
by
applying
the
M.I.T. group's
public encoding algorithm, that
is, by
raising
the
above number
to the
power
of 9,007, then reducing
it to
modulo
r.
The result
is
060918192000191512220
51800230914190015140500082114041
805040004151212011819.
It
translates
(by the use of the standard key) to
FIRST
SOLVER WINS
ONE
HUNDRED DOLLARS.
This signed ciphertext could only come
from
the
M.I.T. group because only
its
members know
the
inverse algorithm
by which
it was
produced.
Rivest
and his
associates have
no
proof that
at
some future time
no one
will discover
a
fast algorithm
for
factor-
ing composites
as
large
as the r
they used
or will break their cipher
by
some other
scheme they have
not
thought
of.
They
consider both possibilities extremely
re-
mote.
Of
course
any
cipher system that
cannot
be
proved unbreakable
in the ab-
solute sense
of
one-time pads
is
open
to
sophisticated attacks
by
modern crypt-
analysts
who are
trained mathemati-
cians with powerful computers
at
their
elbow.
If the
M.I.T. cipher withstands
such attacks,
as it
seems almost certain
it
will, Poe's dictum will
be
hard
to
defend
in
any
form.
Even
in the
unlikely event that
the
M.I.T. system
is
breakable there
are
probably
all
kinds
of
other trapdoor
functions that
can
provide virtually
un-
breakable ciphers. Dime
and
Hellman
are applying
for
patents
on
cipher devic-
es based
on
trapdoor functions they
have
not yet
disclosed. Computers
and
complexity theory
are
pushing cryptog-
123
A bilaterally symmetric tetrad with
18
sides
raphy into
an
exciting phase,
and one
that
may be
tinged with sadness.
All
over
the
world there
are
clever
men and
women, some
of
them geniuses,
who
have devoted their lives
to the
mastery
of modern cryptanalysis. Since World
War
II
even those government
and
mili-
tary ciphers that
are not
one-time pads
have become
so
difficult
to
break that
the talents
of
these experts have gradu-
ally become less useful.
Now
these
peo-
ple
are
standing
on
trapdoors that
are
about
to
spring open
and
drop them
completely from sight.
T
he
top
illustration
on
page
122
shows
how the 12
shapes given last
month
can be
divided into congruent
halves.
The
bottom illustration
on the
same page shows
how
nine,
of the 12
order-5 polyominoes
can be
dissected
into
the
same four congruent parts.
The
three blank polyominoes cannot
be cut
into four congruent parts
of any
shape.
The illustration
on the
preceding page
answers
the
four problems
at the end of
last month's column.
To
bisect
the
nine
squares draw
the 10th
square shown
with broken lines. Rule
AB to get
point
C,
then join
P to C. If the
squares have
sides
of
length
1,
then
CD
equals
1/4,
and
it is
easy
to see
that
PC
bisects
the
original figure.
To
bisect
the
five circles
add three additional circles
as
shown
by
the broken lines.
The
line through
the
centers
of two
circles obviously halves
the total area. (Both problems
are
from
A Problem
a
Day,
by R. M.
Lucey,
Pen-
guin Books, 1937.)
The hexagon
at the
bottom
is
trisected
by joining
/"to
Cand
D.
the
midpoints
of
two sides. Assume that
the
equilateral
triangles have areas
of 1. The
area
of
PAB
is 1,
therefore
the
area
of
PBE
is 2
and
the
rest follows.
I
was
unable
to
find
any comparably simple
way to
trisect
a
regular pentagon with
a
line through
a
corner.
The middle
two
hexagons show
how
Leo Moser proved that
the
minimum-
length curve bisecting
an
equilateral
tri-
angle
is the arc of a
circle. Whatever
the
shape
of the
bisecting curve,
it
will form
a closed curve
if the
triangle
is
reflected
around
one
vertex
as is
shown. Such
a
curve cuts
the
hexagon
in
half,
and it has
a fixed area.
The
figure
of
minimum
pe-
rimeter that encloses
a
given area
is the
circle, therefore
the
minimum-length
bisecting curves inside each triangle
are
arcs
of a
circle. (This exercise
is
from
Mathematical Quickies,
by
Charles
W.
Trigg, McGraw-Hill, 1967.)
C
omments
on the
mail response
to
April's short problems follow:
The generalization
of the
pool-ball
problem
to
triangles
of
order
n,
bearing
consecutive numbers starting with
1, has
been solved. Herbert Taylor found
an
ingenious
way to
prove that
no TAD
(triangle
of
absolute differences) could
be made with triangular arrays
of
order
9
or
higher. Computer programs elimi-
nated TAD's
of
orders
6, 7 and 8,
there-
fore
the
unique solution
for the 15
pool
balls
is the
largest
TAD of
this type.
A Cipher that Defeated Poe
"Ge Jeasgdxv,
Zij
gl mw,
laam.
xzy
zmlwhfzek
ejlvdxw kwke
tx lbr
atgh lbmx aanu
bai Vsmukkss
pwn
vlwk
agh
gnumk
wdlnzweg jnbxw oaeg enwb zwmgy
mo
mlw
wnbx
mw al
pnfdcfpkh wzkex
hssf xkiyahul.
Mk num
yexdm wbxy
sbc
hv wyx
Phwkgnamcuk?"
In
1839, in a
regular column Edgar
Allan
Poe
contributed
to a
Philadelphia
•periodical, Alexander's Weekly Messen-
ger,
Poe
challenged readers
to
send
him
{cryptograms (monoalphabetic substitu-
tion ciphers), asserting that
he
would
solve them
all
"forthwith."
One G. W.
Kulp submitted
a
ciphertext
in
longhand.
It
was
printed
as
shown above
in the is-
sue
of
February
26, 1840.
Poe
"proved
"
in
a
subsequent column that
the
cipher
•
was
a
hoax—"a jargon
of
random char-
acters having
no
meaning whatsoever."
In
1975
Brian J.Winkel,
a
mathemati-
cian
at
Albion College,
and
Mark
Lys-
ter,
a
chemistry major
in
Winkel's cryp-
tology class, cracked Kulp's cipher.
It is
not
a
simple substitution—Poe
was
right
—but neither
is it
nonsense.
Poe can
hardly
be
blamed
for his
opinion.
In ad-
dition
to a
major error
by
Kulp there
are
15 minor errors, probably printer's
mis-
takes
in
reading
the
longhand.
Winkel
is an
editor
of a
new
quarterly,
Cryptologia,
available from Albion
Col-
lege,
Albion, Mich. 49224,
at $16 per
year.
The
magazine stresses
the
mathe-
matical
and
computational aspects
of
cryptology.
The
first issue (January.
1977) tells
the
story
of
Kulp's cipher
and
gives
it as a
challenge
to
readers.
So far
only three readers have broken
it. I
shall
give
the
solution next month.
Solomon
W.
Golomb proposed three
candidates
for
further investigation:
1.
If all
numbers
in a TAD of
order
greater than
5 are
distinct
but not con-
secutive,
how big is the
largest number
forced
to be?
(Example:
An
order-6
TAD
is
possible with
the
largest number
as
low as 22.)
2.
Using
all
numbers from
1 to k, but
allowing repeats,
how big can k b,e in a
TAD
of
order n?(Example:
An
order-6
TAD
is
possible with
k as
high
as 20.)
3.
For
what orders
is it
possible
to
form
a TAD
modulo
m,
where
m is the
number
of
elements
in the
triangle
and
the numbers
are
consecutive from
1 to
m?Each difference
is
expressed modulo
m.
Such triangles
can be
rotated
so
that
every element below
the top row is the
sum (modulo
m) of the two
numbers
above
it.
Here,
in
rotated form,
are the
four order-4 solutions:
1694 2783 6149 7238
753 951 753 951
28 46 28 46
0 0 0 0
A backtrack program
by
Golomb
and
Taylor found
no
solution
for
order
5.
Col. George Sicherman,
who
invented
the original pool-ball problem, reports
a
computer proof
of
impossibility
for or-
der
6.
Higher orders remain open.
Robert Ammann, Greg Frederickson
and Jean
L.
Loyer each found
an
18-sid-
ed polygonal tetrad with bilateral
sym-
metry
[see
illustration
on
this page],
thus improving
on the
22-sided solution
I
had
published.
Dan Eilers, Allen
I.
Janis, Scott
Kim,
P.
H.
Lyons, Robert Mathews (with
Martin
G.
Wallser), James Newton
and
Mike Tempest each found
a
second
so-
lution (there
are no
more)
for the
lost-
king tour
on the
order-5 square.
When
I
ended
the
column with limer-
icks
of
decreasing length,
I
referred
to
the one-line limerick
as the
"last
of
four." Draper
L.
Kauffman, John Little,
John McKay, Thomas
D.
Nehrer
and
James
C.
Vibber were
the
first
of
many
who told
me I
should have called
it the
last-but-one
of
five.
The
fifth,
of
course,
has
no
lines, which
is why
other readers
failed
to
notice
it.
Tom Wright
of
Ganges, British
Co-
lumbia, wrote:
"I was
interested
in the
limerick paradox, particularly
in the de-
creasing two-line
and
one-line limericks.
I wondered
if
you had,
in
fact, added
the
no-line limerick (about
the man
from
Nepal),
and I
looked minutely
to see if it
wasn't there.
On
examination,
my
first
impulse
was to
assume that
it was in-
deed
not
there, since
no
space
was pro-
vided,
but
further cogitation suggested
that
a
no-line poem, requiring
no
space,
might indeed
be
there. Unable
to
resolve
this paradox
by any
logical
proof,
I am
abjectly reduced
to
asking
you
whether
or
not a
no-line limerick
was
not
printed
in
the
space
not
provided,
or not."
CO
ap
ar
ta
L
I
IS—
i
_
tf
OF
<3
42205.
A DI
Edited
by
Sle,
geology,
geo
paleontology,
ogy, cartogra]
00470.
VAN
CLOPEDIA.
prehensive
o
thoroughly
re
1
photographs.
Counts
as 3
of
66570.
AN C
OGY. Bruce I
Williams.
Up-
tural geology-
latest informal
55000.
THE
1
ASTRONOV
full range
of a'
tion, from
anc
70170. PRIN
Edition.
Hou
rigorous theoi
tions.
44900.
THE
SCIENCE.
£
Meek.
A
mom
densed, accur;
from theory
tc
the logical
des
lean algebra
cross referenci
tables.
Counts
70190. PRIf
SEARCH.
Se
1039-page
boc
fundamental
o
49340. FUND
SYSTEM
AN
our assault
on
earliest sensoi
tronomical
tho
«1530.
MAT
Edition. Edite
enbach Revisi
definitions
of i
Edgar Allan Poe, the renowned American poet and writer, was captivated by the art of secret writing. In 1841, he published an essay titled "A Few Words on Secret Writing" in Graham's Magazine, where he explored various methods of encryption. Poe was particularly interested in substitution ciphers, a technique in which each letter is replaced by a different one. He even challenged his readers to submit their own encrypted messages, offering to decipher them personally. Poe's fascination with cryptography stemmed from his passion for puzzles and codes, as well as his experience as a military officer and journalist, where secure communication was of utmost importance. He even incorporated cryptographic elements into some of his literary works, such as "The Gold-Bug”, which includes a detailed description of a cipher.
*Edgar Allan Poe*
Fermat's little theorem is named after the 17th-century French mathematician Pierre de Fermat, who first stated the theorem in 1640. However, Fermat did not provide a proof for the theorem, as was common in his work. The first published proof was given by Leonhard Euler in 1736, almost a century after Fermat's claim.
The theorem is particularly relevant for primality testing because it provides a quick and efficient way to determine whether a number is potentially prime or definitely composite. Primality tests based on Fermat's little theorem work as follows:
To test if a number $n$ is prime, choose a random integer $a$ between 2 and $n-1$. Then, compute $a^{n-1} \bmod n$. If the result is not 1, then $n$ is definitely composite. If the result is 1, then $n$ might be prime, and the test is repeated with several different randomly chosen $a$ values. If the result is always 1, then there is a high probability that $n$ is prime.
For example, let's test if $n = 17$ is prime.
1. Choose $a = 3$, then $3^{16} \bmod 17 = 1$.
2. Choose $a = 5$, then $5^{16} \bmod 17 = 1$.
3. Choose $a = 7$, then $7^{16} \bmod 17 = 1$.
Since the test passed for multiple random $a$ values, there is a high probability that 17 is prime.
This primality test is probabilistic, meaning that it can identify composite numbers with certainty but can only give a probability that a number is prime. If a number passes the test for many different random $a$ values, it is very likely to be prime.
RSA is an asymmetric encryption algorithm that builds upon the groundbreaking work of Diffie and Hellman. Developed in 1977, just a year after the publication of Diffie and Hellman's "New Directions in Cryptography”, RSA is a practical implementation of the public-key cryptography concept introduced by Diffie and Hellman.
While Diffie and Hellman's paper laid the theoretical foundation for asymmetric encryption, they did not provide a concrete implementation. RSA fills this gap by using the mathematical properties of prime numbers to create a pair of keys: a public key for encryption and a private key for decryption. The security of RSA relies on the difficulty of factoring large composite numbers, a problem closely related to the discrete logarithm problem that underlies the Diffie-Hellman key exchange.
The development of RSA marked a significant milestone in the history of cryptography, as it turned the abstract concept of public-key cryptography into a practical and widely adopted encryption system that continues to be used extensively for secure digital communication and transactions.
#### Caesar cipher
A Caesar cipher, also known as a shift cipher, is one of the simplest and most widely known encryption techniques. While the Caesar cipher is simple to understand and implement, it is not secure by modern standards and can be easily broken.
In a Caesar cipher, each letter of the alphabet is shifted along some number of places. For example, in a Caesar cipher of shift 3, A would become D, B would become E, Y would become B and so on.
*Caesar cipher of shift 3*
Here is an example:
```
fermat
------
ihupdw
```
The price of sending a letter in the United States has steadily increased since the time of writing of this article (1977) as Martin Gardner predicted. In contrast, the volume of letters being sent peaked in the early 2000s, and today it is roughly at the same level as in the 70s.
### One-time pad
The one-time pad (OTP) is a type of encryption that is unbreakable when used correctly. Here is how a simple implementation of a one time pad would work:
Encryption
- A random key, as long as the message, is generated.
- The message is converted into a numerical format (e.g., ASCII code).
- The key is added to the message, bit-by-bit or character-by-character, using modular addition (e.g., XOR).
- The resulting ciphertext is sent to the recipient.
Decryption
- The recipient has a copy of the same random key.
- The key is added to the ciphertext, bit-by-bit or character-by-character, using modular addition (e.g., XOR).
- The resulting plaintext is the original message.
According to historical accounts, such as Suetonius' "Lives of the Twelve Caesars", Caesar used a simple shift cipher to protect sensitive military and personal communications.
> if there was occasion for secrecy, he wrote in cyphers; that is, he used the alphabet in such a manner, that not a single word could be made out. The way to decipher those epistles was to substitute the fourth for the first letter, as d for a, and so for the other letters respectively.
This suggests that Caesar employed a uniform shift of three positions, meaning that each letter in the plaintext was replaced by the letter three positions down the alphabet.
Rudolf Ivanovich Abel, whose real name was William August Fisher, was a notorious Soviet spy during the Cold War era. In 1948, Abel was sent to the United States as part of a Soviet espionage network tasked with gathering classified information about U.S. military and nuclear secrets. Operating under the alias "Emil Goldfus," Abel posed as a photographer and artist in Brooklyn, New York.
He maintained contact with Moscow using a variety of covert communication methods, including the use of a miniature one-time pad disguised as a small booklet. In 1957, Abel was apprehended by the FBI in a New York hotel room, marking the end of his nine-year espionage career in the United States.
The discovery of his one-time pad during the arrest was a significant piece of evidence in the case against him. Abel was eventually exchanged for Gary Powers, the U-2 pilot shot down over the Soviet Union in 1960.
*One-time pad booklet*
Despite the original estimate, the prime factors were actually found just 17 years after the paper's publication. In 1994, a team led by Derek Atkins, Michael Graff, Arjen Lenstra, and Paul Leyland successfully factored the 129-digit number used in the RSA-129 challenge employing a combination of the quadratic sieve algorithm and a distributed computing approach involving about 1600 volunteers and their computers. This achievement highlighted the rapid advancements in both computational power and algorithmic efficiency that have occurred in recent decades.
Today you can find the factors to RSA-129 for ~30$ using a public cloud like Google Cloud ([blogpost](https://natmchugh.blogspot.com/2015/03/the-magic-words-are-squeamish-ossifrage.html))
1994 announcement that a factorization of RSA-129
```
We are happy to announce that
RSA-129 = 1143816257578888676692357799761466120102182967212423625625618429\
35706935245733897830597123563958705058989075147599290026879543541
= 3490529510847650949147849619903898133417764638493387843990820577 *
32769132993266709549961988190834461413177642967992942539798288533
The encoded message published was
968696137546220614771409222543558829057599911245743198746951209308162\
98225145708356931476622883989628013391990551829945157815154
This number came from an RSA encryption of the `secret' message using the
public exponent 9007. When decrypted with he `secret' exponent
106698614368578024442868771328920154780709906633937862801226224496631\
063125911774470873340168597462306553968544513277109053606095
this becomes
200805001301070903002315180419000118050019172105011309190800151919090\
618010705
Using the decoding scheme 01=A, 02=B, ..., 26=Z, and 00 a space between
words, the decoded message reads
THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE
To find the factorization of RSA-129, we used the double large prime
variation of the multiple polynomial quadratic sieve factoring method.
The sieving step took approximately 5000 mips years, and was carried
out in 8 months by about 600 volunteers from more than 20 countries,
on all continents except Antarctica. Combining the partial relations
produced a sparse matrix of 569466 rows and 524338 columns. This matrix
was reduced to a dense matrix of 188614 rows and 188160 columns using
structured Gaussian elimination. Ordinary Gaussian elimination on this
matrix, consisting of 35489610240 bits (4.13 gigabyte), took 45 hours
on a 16K MasPar MP-1 massively parallel computer. The first three
dependencies all turned out to be `unlucky' and produced the trivial
factor RSA-129. The fourth dependency produced the above factorization.
We would like to thank everyone who contributed their time and effort
to this project. Without your help this would not have been possible.
Derek Atkins
Michael Graff
Arjen Lenstra
Paul Leyland
```
The message encoded in this ciphertext was deciphered in 1994. The message was:
`The Magic Words are Squeamish Ossifrage`
Two numbers are considered relatively prime (or coprime) if their greatest common divisor (GCD) is 1. In other words, they have no common factors other than 1.
For example, 12 and 25 are relatively prime because their GCD is 1, even though neither number itself is prime. On the other hand, 12 and 18 are not relatively prime because they share a common factor of 6 (besides 1).
In the RSA system, the number s must be carefully chosen so that it is relatively prime to both p - 1 and q - 1. This is a crucial condition for the encoding and decoding process to work correctly, allowing the efficient computation of modular exponentiation in the encryption and decryption steps.
Whitfield Diffie and Martin Hellman are two renowned American cryptographers who made groundbreaking contributions to the field of cryptography. In 1976, they published a seminal paper titled "New Directions in Cryptography," which introduced the concept of public-key cryptography. This revolutionary idea allowed for secure communication between parties without the need for a pre-shared secret key. Diffie and Hellman's work laid the foundation for the development of asymmetric encryption algorithms, such as RSA (Rivest-Shamir-Adleman), which are widely used today for secure online transactions, digital signatures, and encrypted communication.
*Martin Hellman, left, and Whitfield Diffie*