Fermat's Library | A new kind of cipher that would take millions of years to break annotated/explained version.

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 -

MATHEMATICAL

GAMES

A new kind of cipher that would

take millions of

years

to break

by Martin Gardner

;

"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

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

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

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

"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

The answers to last month's bisection problems

__ 1

•

1—

i j

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

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

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

testing.

For

example,

test

130-digit

odd

number

for

primality

re-

quires

at the

most (that

is,

when

the

number actually

prime) about seven

minutes

on a

PDP-10 computer.

The

same algorithm takes only

seconds

find

the

first prime after

200

(It is a 61-

digit number equal

2200

+ 235.)

Contrast this with

the

difficulty

finding

the two

prime factors

of a 125-

or 126-digit number obtained

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

about

quadrillion years!

(For

good discussion

computer

methods

factoring into primes,

see

Donald

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

plaintext

paraphrase

of a

remark

Shakespeare's Julius Caesar

(Act 1,

Scene 2):

ITS ALL

GREEK

TO ME.

This

first changed

to a

single

num-

ber, using

the

standard

key: A = 01, B

02 z =

26, with

indicating

space between words.

The

number

09201900011212000718050511002015

001305.

The entire number

is now

encoded

raising

it to a

fixed power

modulo

certain composite number

r. The com-

posite

r is

obtained

randomly select-

ing (using

procedure given

in the

M.I.T. memorandum)

two

primes,

p and

q, each

which

is at

least

digits long,

and multiplying them together.

The

number

must

relatively prime

- 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,

requires less

than

second

computer time.

The

two

prime factors

of r are

with-

held,

play

role

in the

secret inverse

algorithm. This inverse algorithm, used

for decoding, consists

raising

the ci-

phertext number

another power

then reducing

it to

modulo

r. As

before,

this takes less than

second

computer

time.

The

number

however,

can be

calculated only

someone

who

knows

and q, the two

primes that

are

kept

secret.

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.

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

1143816257578888676692357

79976146612010218296721242362562

^_—-—

[

)

Solutions

four equal-division problems

56184293570693524573389783059712

35639587050589890751475992900268

79543541.

The number

r is the

product

of a

64-digit prime

p and a

65-digit prime

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.

challenge

Scientific American

readers

the

M.I.T. group

has

encoded

another message, using

the

same public

algorithm.

The

ciphertext

shown

the bottom illustration

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

21783 5O0'8446929j)626l55

£792£37llr4490S09}5786p865lS662y9

\^ 84dj)040$702P3 73.

The signature

was

encoded

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-

and the

instructions

in the

M.I.T.

memorandum

can

easily read

the

signa-

ture

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

The result

060918192000191512220

51800230914190015140500082114041

805040004151212011819.

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

proof that

some future time

no one

will discover

fast algorithm

for

factor-

ing composites

large

as the r

they used

or will break their cipher

some other

scheme they have

not

thought

of.

They

consider both possibilities extremely

re-

mote.

course

any

cipher system that

cannot

proved unbreakable

in the ab-

solute sense

one-time pads

open

sophisticated attacks

modern crypt-

analysts

who are

trained mathemati-

cians with powerful computers

their

elbow.

If the

M.I.T. cipher withstands

such attacks,

as it

seems almost certain

will, Poe's dictum will

hard

defend

any

form.

Even

in the

unlikely event that

the

M.I.T. system

breakable there

are

probably

all

kinds

other trapdoor

functions that

can

provide virtually

un-

breakable ciphers. Dime

and

Hellman

are applying

for

patents

cipher devic-

es based

trapdoor functions they

have

not yet

disclosed. Computers

and

complexity theory

are

pushing cryptog-

123

A bilaterally symmetric tetrad with

sides

raphy into

exciting phase,

and one

that

may be

tinged with sadness.

All

over

the

world there

are

clever

men and

women, some

them geniuses,

who

have devoted their lives

to the

mastery

of modern cryptanalysis. Since World

War

even those government

and

mili-

tary ciphers that

are not

one-time pads

have become

difficult

break that

the talents

these experts have gradu-

ally become less useful.

Now

these

peo-

ple

are

standing

trapdoors that

are

about

spring open

and

drop them

completely from sight.

top

illustration

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.

bisect

the

nine

squares draw

the 10th

square shown

with broken lines. Rule

AB to get

point

then join

P to C. If the

squares have

sides

length

then

equals

1/4,

and

it is

easy

to see

that

bisects

the

original figure.

bisect

the

five circles

add three additional circles

shown

the broken lines.

The

line through

the

centers

of two

circles obviously halves

the total area. (Both problems

are

from

A Problem

Day,

by R. M.

Lucey,

Pen-

guin Books, 1937.)

The hexagon

at the

bottom

trisected

by joining

/"to

Cand

the

midpoints

two sides. Assume that

the

equilateral

triangles have areas

of 1. The

area

PAB

is 1,

therefore

the

area

PBE

is 2

and

the

rest follows.

was

unable

find

any comparably simple

way to

trisect

regular pentagon with

line through

corner.

The middle

two

hexagons show

how

Leo Moser proved that

the

minimum-

length curve bisecting

equilateral

tri-

angle

is the arc of a

circle. Whatever

the

shape

of the

bisecting curve,

will form

a closed curve

if the

triangle

reflected

around

one

vertex

as is

shown. Such

curve cuts

the

hexagon

half,

and it has

a fixed area.

The

figure

minimum

pe-

rimeter that encloses

given area

is the

circle, therefore

the

minimum-length

bisecting curves inside each triangle

are

arcs

of a

circle. (This exercise

from

Mathematical Quickies,

Charles

Trigg, McGraw-Hill, 1967.)

omments

on the

mail response

April's short problems follow:

The generalization

of the

pool-ball

problem

triangles

order

bearing

consecutive numbers starting with

1, has

been solved. Herbert Taylor found

ingenious

way to

prove that

no TAD

(triangle

absolute differences) could

be made with triangular arrays

order

higher. Computer programs elimi-

nated TAD's

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

mlw

wnbx

mw al

pnfdcfpkh wzkex

hssf xkiyahul.

Mk num

yexdm wbxy

sbc

hv wyx

Phwkgnamcuk?"

1839, in a

regular column Edgar

Allan

Poe

contributed

to a

Philadelphia

•periodical, Alexander's Weekly Messen-

ger,

Poe

challenged readers

send

him

{cryptograms (monoalphabetic substitu-

tion ciphers), asserting that

would

solve them

all

"forthwith."

One G. W.

Kulp submitted

ciphertext

longhand.

was

printed

shown above

in the is-

sue

February

26, 1840.

Poe

"proved

subsequent column that

the

cipher

•

was

hoax—"a jargon

random char-

acters having

meaning whatsoever."

1975

Brian J.Winkel,

mathemati-

cian

Albion College,

and

Mark

Lys-

ter,

chemistry major

Winkel's cryp-

tology class, cracked Kulp's cipher.

It is

not

simple substitution—Poe

was

right

—but neither

is it

nonsense.

Poe can

hardly

blamed

for his

opinion.

In ad-

dition

to a

major error

Kulp there

are

15 minor errors, probably printer's

mis-

takes

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

cryptology.

The

first issue (January.

1977) tells

the

story

Kulp's cipher

and

gives

it as a

challenge

readers.

So far

only three readers have broken

it. I

shall

give

the

solution next month.

Solomon

Golomb proposed three

candidates

for

further investigation:

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:

order-6

TAD

possible with

the

largest number

low as 22.)

Using

all

numbers from

1 to k, but

allowing repeats,

how big can k b,e in a

TAD

order n?(Example:

order-6

TAD

possible with

k as

high

as 20.)

For

what orders

is it

possible

form

a TAD

modulo

where

m is the

number

elements

in the

triangle

and

the numbers

are

consecutive from

1 to

m?Each difference

expressed modulo

Such triangles

can be

rotated

that

every element below

the top row is the

sum (modulo

m) of the two

numbers

above

it.

Here,

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

Golomb

and

Taylor found

solution

for

order

Col. George Sicherman,

who

invented

the original pool-ball problem, reports

computer proof

impossibility

for or-

der

Higher orders remain open.

Robert Ammann, Greg Frederickson

and Jean

Loyer each found

18-sid-

ed polygonal tetrad with bilateral

sym-

metry

[see

illustration

this page],

thus improving

on the

22-sided solution

had

published.

Dan Eilers, Allen

Janis, Scott

Kim,

Lyons, Robert Mathews (with

Martin

Wallser), James Newton

and

Mike Tempest each found

second

so-

lution (there

are no

more)

for the

lost-

king tour

on the

order-5 square.

When

ended

the

column with limer-

icks

decreasing length,

referred

the one-line limerick

as the

"last

four." Draper

Kauffman, John Little,

John McKay, Thomas

Nehrer

and

James

Vibber were

the

first

many

who told

me I

should have called

it the

last-but-one

five.

The

fifth,

course,

has

lines, which

is why

other readers

failed

notice

it.

Tom Wright

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

you had,

fact, added

the

no-line limerick (about

the man

from

Nepal),

and I

looked minutely

to see if it

wasn't there.

examination,

first

impulse

was to

assume that

it was in-

deed

not

there, since

space

was pro-

vided,

but

further cogitation suggested

that

no-line poem, requiring

space,

might indeed

there. Unable

resolve

this paradox

by any

logical

proof,

I am

abjectly reduced

asking

you

whether

not a

no-line limerick

was

not

printed

the

space

not

provided,

or not."

IS—

42205.

A DI

Edited

Sle,

geology,

geo

paleontology,

ogy, cartogra]

00470.

VAN

CLOPEDIA.

prehensive

thoroughly

photographs.

Counts

as 3

66570.

AN C

OGY. Bruce I

Williams.

Up-

tural geology-

latest informal

55000.

THE

ASTRONOV

full range

of a'

tion, from

anc

70170. PRIN

Edition.

Hou

rigorous theoi

tions.

44900.

THE

SCIENCE.

Meek.

mom

densed, accur;

from theory

the logical

des

lean algebra

cross referenci

tables.

Counts

70190. PRIf

SEARCH.

1039-page

boc

fundamental

49340. FUND

SYSTEM

our assault

earliest sensoi

tronomical

tho

«1530.

MAT

Edition. Edite

enbach Revisi

definitions

of i

Discussion

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. ![](https://i.imgur.com/yVvhgnR.jpeg) *Edgar Allan Poe* 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. ![](https://i.imgur.com/L36uCQl.png) *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. ![](https://i.imgur.com/5WByGv3.png) ### 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. ![](https://i.imgur.com/HiQradF.png) *One-time pad booklet* 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. ![](https://i.imgur.com/F7935bZ.jpeg) *Martin Hellman, left, and Whitfield Diffie* 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 ``` 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. The message encoded in this ciphertext was deciphered in 1994. The message was:  `The Magic Words are Squeamish Ossifrage` 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.

Comments

Products

Project