## Lesson 17: Headline Puzzles, Playfair, Foursquare Fractination And Delastelle Systems

```
CLASSICAL CRYPTOGRAPHY COURSE
BY LANAKI

September 9, 1996

LECTURE 17

FRACTIONATION AND DELASTELLE SYSTEMS

SUMMARY

I think this lecture is both interesting and perhaps
difficult.  We start off with PHOTON's Headliner Cipher
which combines many of the principles found in Lectures
1 and 10 - 12 of this course.   We then shift into
Digraphic systems with the Playfair and Foursquare
Ciphers.  We develop the theory of fractionation and
illustrate it with difficult classical systems known as
the Bifid and Trifid ciphers.  Both of these latter
cipher systems were invented by the French cryptographer
Delastelle. We develop our lecture with the help of the
following references: [ELCY], [BOW1], [BOW2], [BOW3],
[BOW4], [HITT], [LEWI], [NICH] and [PHOT].   At the end
of my lecture is a special note regarding Diophantine
equations, a subject which is a bit esoteric and has
interested several of our class.

Thirty years ago, Paul Derthick began publishing the
professional cryptologists. Paul is no longer with us,
but his puzzles continue to be written monthly by Larry
Gray to challenge and frustrate his successors.  We
thank PHOTON for exposing us to this wonderful cipher.
I have condensed his soon to be published paper.  [PHOT]

Headline Puzzles demonstrate a variety of cryptographic
principles.  Each puzzle contains five headlines from
recent daily newspapers. Each of the five is a different
monoalphabetic substitution, and all five are derived
from the same mixed alphabet at different settings
against itself. A complete solution includes recovering
the headlines, the key, the setting and the hat.

In Paul's words, "The use of headlines was a happily
malicious thought. It permits the inclusion of
outrageous proper names, and has the tendency to exclude
the commonest words." But even though the five headlines
may include some tough problems, finding the three words
(key, setting and hat) needed for a complete solution
may be even more challenging.

WALKING THROUGH A SOLUTION

Given:

1. AMHXZLX ALXNSTXO APYBX NLJXHXK LI ZJL AHWHMHBX
BHUAUBIZ;

2. GHDMRJGB MCGHE CKXCDMCQH SP RLCEE OSEE, ZHMCGHE MSU
DJCC EOSM;

3. WYNAJSM PYXMKANWAJKANB VNYLXPA MAFN-VANWAPK CXMLNAL
LYQQFN IJQQB;

4. XOAJRH DOHU XFNIRA MPS GRNC RBQTSPBIRBHNF FNG
RBMPSDRIRBH;

5. FRHRXIQ ALVTURXF RQX. VALPPF SI VXCMRLP XLVJ LPFPVLXU

The general outline of solution is to: 1) solve any two
headlines and use them to find a mixed alphabet that
solves all five headlines; 2) solve the rest of the
headlines and use all five to recover the setting; 3)
recover the key block and the sequence of transposition;
4) recover the original mixed alphabet by decimation;
and 5) finally, recover the hat (the word whose
alphabetic sequence of letters determines the
transposition sequence from the keyblock).

Since the initial step is to solve any two headlines, we
look for nice wedges in any two. The first probable
wedges to catch my eye in this example are the long
pattern words in headlines 3 and 4. The 14 letter word
in headline 3.  has the pattern ABCDEFGHFIEFGJ, yielding
"counterfeiters" from the pattern word dictionary.
Substituting the letters in the headline produces a nice
wedge! Then a little trial and error produces, "Foreign
counterfeiters produce near-perfect hundred dollar
bills":

forei n counterfeiters  ro uce ne r- erfect  un re
3. WYNAJSM PYXMKANWAJKANB VNYLXPA MAFN-VANWAPK CXMLNAL
ABCDEFGHFIEFGJ

o   r   i  s
LYQQFN  IJQQB

The 13 letter pattern word in headline 4. has the
pattern ABCDEFBGABHIJ, yielding "environmental" from the
pattern word dictionary. Substituting the letters in the
headline also produces a nice wedge; not as nice, but
good enough to produce "Budget cuts blamed for weak
environmental law enforcement":

et    t    lame    or   ea   environmental  la
4. XOAJRH  DOHU  XFNIRA  MPS  GRNC  RBQTSPBIRBHNF  FNG
ABCDEFBGABHIJ
en or ement
RBMPSDRIRBH

Solving the first two headlines is seldom this easy; but
as you can see, long pattern words make nice wedges when
they are available. We assume that the reader knows how
to solve monoalphabetic ciphers with word divisions
(Aristocrats - see chapter 1 in [NICH]).

The current recovery of plain-text to cipher-text is:

a b c d e f g h i j k l m n o p q r s t u v w x y z
1.
2.
3. F I P L A W S C J     Q   M Y V   N B K X
4. N X D A R M J   T   C F I B P     S U H O Q G
5.

Figure 17-1.

Step 2:FIND A MIXED ALPHABET THAT SOLVES ALL FIVE

The columns in Figure 17-1 are arranged alphabetically
by the plain letters for ease in building chains. Each
vertical column is fixed, regardless of the sequence of
the columns because each plain letter stands for only
one cipher letter in each of the headlines. The purpose
of chaining is to find an alphabetic sequence for the
fixed columns that is the same in each row. The sequence
we derive from chaining will not necessarily be the
original mixed sequence; but it will solve all five
headlines when the rows are set against themselves.
For the rest of this section we will refer to the mixed
alphabet derived from chaining as an equivalent
alphabet.

Note that the equivalent alphabet is not unique. There
are 6 equivalent alphabets which are odd decimations of
the original (e.g.  every third letter, every fifth
letter etc.  in a 26 letter cycle), 6 odd decimations
that are the same as the first six, but in the reverse
order; 6 even decimations that give two cycles of
thirteen letters each (rather than a single cycle of 26
letters); 6 even decimations that are the same as the
first six even decimations, but reversed; and a single
decimation with the same two letters repeated 13
times. Only the 26-letter cycles are useful results from
chaining, so we will look only for odd decimations when
recovering the keyblock and the original mixed alphabet.

Chaining capitalizes on the symmetry of letter positions
in the fixed columns and their relative distances apart
in related alphabets. For example: if  plain A equals
cipher F in line 3, and plain F equals cipher W, then
the distance between plain A and plain F is the same as
the distance between cipher F and cipher W in their
respective alphabets.  A two-dimensional chain combines
the relationships of the  plain alphabet and two
different cipher alphabets.  In this example, we put
line 3. cipher-text letters vertically under the plain-
text letters; and put line 4. cipher-text letters
horizontally to the right of the plain-text letters. In
that way we generate a two-dimensional interactive chain
with the same equivalent alphabet in each vertical line,
and a different equivalent alphabet in each horizontal
line.  Please refer to Figures 17-2 and 17-3 for what
the display looks like on graph paper.

Arbitrarily starting with the plain A and cipher F (line
3) gives me part of the vertical chain (A over F ). Then
looking at plain F over cipher W adds W to the chain
(under the F).  Looking at plain W, however, shows that
no cipher letter has been identified in line 3 for plain
W, so we show "." as a place-filler. Returning to cipher
A (line 3), we find cipher A under plain E, but no
cipher E to continue the chain, so we show "." as a
place-filler. See the diagram in Figure 17-2 for the
vertical chain fragment EAFW.

Then we make a horizontal chain on each of the letters
of the vertical chain, using the plain alphabet and
cipher line 4.  The first horizontal line is from cipher
R to the right of plain E, cipher S to the right of
plain R, etc.  giving the horizontal chain fragment
ERSUOP.  Similarly, completing the next three horizontal
fragments looks like the matrix in Figure 17-2.

.
. E R S U O P .
. K C D A N B X .
. L F M I T H .
. W G J .
.

Figure 17-2

Continuing to expand the chains shows quickly that the
horizontal chain repeats with a 13 letter cycle,
indicating that it is from an even decimation (and
therefore not useful a this time). The vertical chain,
however, contains a full 26 letter mixed alphabet,
indicating a useful decimation. The result looks like
the matrix in Figure 17-3 after only a few iterations.

I
J
U
X
T
K
O
Y
H
C
P
V
.
D
L
Y V Q W G J K C D A N B X Y V  (13 LETTER CYCLE)
I T H E R S U O P L F M I T H    (13 LETTER CYCLE)
J K C D A N B X Y V
P L F M I T H .
Q W G J K C D A N B X
E R S U O P
C D A N B X Y V
M
G
S
B
I

Figure 17-3

Note how the chain fragments grow interactively, with
the horizontal chain providing letters for the vertical
chain and visa versa. Also note that all the vertical
segments are parts of the same equivalent alphabet. When
an overlap is discovered, the chain can be expanded by
inspection.  Look, for example, at the bottom vertical
segment NMGSBI and see how it came from combining
segments from the two columns to its right. Similarly,
the horizontal chain segments are, by chance, part of
two independent 13 letter cycles which can be expanded
to other horizontal chains by inspection.

Only one letter eluded detection by two-dimensional
chaining; so it isn't hard to identify it and fill in
the "Z".  There is no need to activate a third dimension
or solve another aristocrat in this example. We have
been able to find a complete 26-letter alphabet with
only two solved headlines in almost every case.  The
equivalent alphabet in this example is:

I J U X T K O Y H C P V Z D L Q E A F W R N M G S B

Step 3: RECOVER THE SETTING AND THE INDEX LETTER

Any of the equivalent alphabets will solve the remainder
waiting until recovery of the original alphabet. Now
that we have an alphabet to slide against itself, we
simply write out the alphabet on a sheet of graph paper,
and write it twice on a second sheet that we slide along
the first.  Then we attack the unsolved headlines at
their shortest (usually two letter) words.  Recognizing
that one of those letters will be a vowel, we simply try
all the vowels on one letter until the second letter
makes a good word.  Then we keep that slide position and
try another word to verify it.  R.  MASTERTON observes
another type wedge, in "Solving Cipher Problems"; "You
would be amazed at the number of times the second word
ends with S and the third is a short word such as TO."

Attacking  headline 1. with the slide setting in Figure
17-4  shows that LI = of  (verified with ZJL = two), and
downing of two civilian aircraft".

i j u x t k o y h c p v z d l q e a f w r n m g s b
O Y H C P V Z D L Q E A F W R N M G S B I J U X T K O Y

H C . .

Figure 17-4

After applying the same technique to headlines 2 (SP =
of) and 5 (SI = to), the setting for each headline  is
shown in Figure 17-5. The setting word "SHARP" shows
clearly under the index letter "e". We'll need both the
setting and the index later.

i j u x t k o y h c p v z d l q e a f w r n m g s b
---------------------------------------------------
1. H C P V Z D L Q E A F W R N M G S B I J U X T K O Y
2. F W R N M G S B I J U X T K O Y H C P V Z D L Q E A
3. J U X T K O Y H C P V Z D L Q E A F W R N M G S B I
4. T K O Y H C P V Z D L Q E A F W R N M G S B I J U X
5. R N M G S B I J U X T K O Y H C P V Z D L Q E A F W

Setting = SHARP  Index = E

Figure 17-5

Note: The setting might read up the column, rather than
down, or be derived from plain-text alphabets under a
single cipher-text alphabet, rather than cipher-text
alphabets under a single plain-text alphabet.

Step 4:RECOVER THE KEY BLOCK

The literature suggests that we examine the equivalent
alphabet looking for sequences of letters (like ABC in
this example).  Then examine the alphabet to see if
another sequence is a uniform distance from each letter
(viz: L is 3 before A, M is 3 before B, O is 3 before C)
and decimate by the uniform distance. That works, but
it's not always obvious (to me). So we force the display
to show me sequences by aligning the equivalent alphabet
vertically in strips. For convenience we order them
across the middle in alphabetic sequence (similar to the
sequence of unused letters in a keyblock). Then the
appropriate decimation is much more obvious. See Figure
17-6.  Sometimes the key is in plain view. We made the
matrix in Figure 17-6. by hand the first couple of
times; and then wrote a short computer program to do the
drudgery.  The rows and columns are numbered for
convenience in referring to them.

Since we look for the key word and for alphabetic
sequences of unused letters in the key block, and for
them horizontally in Figure 17-6. The highest
concentration of alphabetic sequences are in rows -6, -
3, 3 and 6 indicating that a decimation of three might
be a good choice. We call this a goodness test in the
computer program; and it has always led me to the right
decimation.  The "goodness" column from PHOTON'S
computer program is merely the sum of alphabetically
adjacent letters in a horizontal row - indicating
likelihood of finding significant pieces of the unused
letters in a keyblock.

-12 k d g j t o v m l q w u p c r s x h z f e b y a n i
-11 o l s u k y z g q e r x v p n b t c d w a i h f m j
-10 y q b x o h d s e a n t z v m i k p l r f j c w g u
-9 h e i t y c l b a f m k d z g j o v q n w u p r s x
-8 c a j k h p q i f w g o l d s u y z e m r x v n b t
-7 p f u o c v e j w r s y q l b x h d a g n t z m i k
-6 v w x y p z a u r n b h e q i t c l f s m k d g j o
-5 z r t h v d f x n m i c a r j k p q w b g o l s u y
-4 d n k c z l w t m g j p f a u o v e r i s y q b x h
-3 l m o p d q r k g s u v w f x y z a n j b h e i t c
-2 q g y v l e n o s b x z r w t h d f m u i c a j k p
-1 e s h z q a m y b i t d n r k c l w g x j p f u o v
Ref A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
1 f i p l a w s c j u o q g m y v e n b k x z r t h d
2 w j v q f r b p u x y e s g h z a m i o t d n k c l
3 r u z e w n i v x t h a b s c d f g j y k l m o p q
4 n x d a r m j z t k c f i b p l w s u h o q g y v e
5 m t l f n g u d k o p w j i v q r b x c y e s h z a
6 g k q w m s x l o y v r u j z e n i t p h a b c d f
7 s o e r g b t q y h z n x u d a m j k v c f i p l w
8 b y a n s i k e h c d m t x l f g u o z p w j v q r
9 i h f m b j o a c p l g k t q w s x y d v r u z e n
10 j c w g i u y f p v q s o k e r b t h l z n x d a m
11 u p r s j x h w v z e b y o a n i k c q d m t l f g
12 x v n b u t c r z d a i h y f m j o p e l g k q w s
13 t z m i x k p n d l f j c h w g u y v a q s o e r b

1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6

Figure 17-6

Note in column 1, for example, that the alphabetic
sequence reading up the column from the reference line
to -3 and -6 is ALV, and in column 2 it is BMW, and in
column 3 it is COX (all in alphabetic sequence).  So the
apparent order of the key block is up the columns. Since
we wrote the equivalent alphabets down the columns, the
decimation must be in the opposite (minus) direction.
Figure 17-7.  shows the likely keyblock lines arranging
from top to bottom for ease in reading.

In forming the keyblock, the columns must stay intact to
maintain the integrity of the mixed alphabet, but the
rows can be rearranged because the horizontal alphabetic
sequence was artificially created to get a sense of
order.  The key word will be on the top line of the
keyblock, perhaps wrapped around onto the second line.

3 r u z e w n i v x t h a b s c d f g j y k l m o p q
Ref A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
-3 l m o p d q r k g s u v w f x y z a n j b h e i t c
-6 v w x y p z a u r n b h e q i t c l f s m k d g j o

1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6

Figure 17-7

Figure 8. shows the result of developing the keyblock
from the information in Figure 17-7. Look at line -3 in
Figure 17-7. and strike through the columns that were
not in alphabetical sequence (columns 5, 8, 9, 14, 20,
21, 22, 23, 24, and 26). Then we looked at what remained
in row 3, and saw the word "zenith". Noticing that the
letter C was in the reference row under the Z in zenith,
Terminate the first row at B. The resulting perfect
keyblock confirms the decimation of minus three.

z e n i t h a b
c d f g j k l m
o p q r s u v w
x y

KEY =ZENITH

Figure 17-8

Step 5:RECOVER THE MIXED ALPHABET

The original alphabet in Figure 17-9 can now be read
directly from Figure 17-6 by starting with the index
letter "e" and reading every third letter vertically in
any column:

E D P Y T J S N F Q Z C O X I G R A L V H K U B M W

Figure 17-9

Step 6:RECOVER THE HAT

Two essential elements are needed to recover the hat.
First, the transposition sequence of reading columns
from the keyblock. And second, the relationship between
the words used for the setting, the key and the hat. The
transposition sequence is the alphabetic sequence of
letters in the hat word. The relationship of the hat to
the setting and the key comes from your determination of
the relationship between the setting and the key alone.
The transposition sequence from the keyblock to the
mixed alphabet can be read directly.  From the original
alphabet in Figure 17-9,  refer to the keyblock in
EDPY,  then down TJS, then down NFQ etc. The full
sequence is shown in Figure 17-10.

4 1 3 5 2 7 6 8
---------------
Z E N I T H A B
C D F G J K L M
O P Q R S U V W
X Y

Figure 17-10

And now we know that the alphabetic sequence of letters
in the hat word is 4 1 3 5 2 7 6 8; and that the word is
related to the key word (ZENITH) and to the setting word
(SHARP).

There are at least two ways to find the hat. The method
illustrated in Figure 17-11 uses the alphabetic sequence
of each letter position in the hat and defines the
limits for each position. In the first text line of
Figure 17-11 the letter A could be at positions 1 and 2,
but not at the other position.  Only position 3 could
have a letter as low as B, positions 4, 5 and 7 could
have letters as low as C, depending on the letter in
position, positions 7 and 8 could have letters as
low as D, depending on the values above.  Likewise at
the high end, only positions 7 and 8 could have a letter
as high as Z etc.

4 1 3 5 2 7 6 8
C A B C A D C D
D B C D B E D E
E C D E C F E F
F D E F D G F G
G E F G E H G H
H F G H F I H I
I G H I G J I J
J H I J H K J K
K I J K I L K L
L J K L J M L M
M K L M K N M N
N L M N L O N O
O M N O M P O P
P N O P N Q P Q
Q O P Q O R Q R
R P Q R P S R S
S Q R S Q T S T
T R S T R U T U
U S T U S V U V
V T U V T W V W
W U V W U X W X
X V W X V Y X Y
Y W X Y W Z Y Z

Figure 17-11

In each of the HEADLINE PUZZLES,  research on the
relationships recovers the hat faster and with more
enjoyment than working the positional possibilities.
Relating the words SHARP and ZENITH suggests manu -
facturers of electronic stuff like computers and radios
and television sets. So we examined the names of other
manufacturers, like Toshiba, Panasonic, Motorola,
Magnavox, Pioneer, Hitachi etc.  only MAGNAVOX matches
the length and alphabetic sequence.  The name "HAT" came
from the position of the transcription word on top of
the keyblock.

M A G N A V O X         Hat = MAGNAVOX
4 1 3 5 2 7 6 8
Z E N I T H A B         Key = ZENITH
C D F G J K L M
O P Q R S U V M         Setting =SHARP
X Y

e d p y t j s n f q z c o x I g r a l v h k u b m w
---------------------------------------------------
1. S N F Q Z C O X I G R A L V H K U B M W E D P Y T J
2. H K U B M W E D P Y T J S N F Q Z C O X I G R A L V
3. A L V H K U B M W E D P Y T J S N F Q Z C O X I G R
4. R A L V H K U B M W E D P Y T J S N F Q Z C O X I G
5. P Y T J S N F Q Z C O X I G R A L V H K U B M W E D

Figure 17-12

Now that we've completed the solution, it's interesting
to confirm that the original mixed alphabet in Figure
17-12 gives the same solution to the headlines as the
equivalent alphabet developed earlier in Figure 17-5.

Step 7:Complete Solution:

1. CLINTON CONDEMNS CUBAN DOWNING OF TWO CIVILIAN
AIRCRAFT;

2. KENTUCKY TAKES ADVANTAGE OF UMASS LOSS, RETAKES TOP
NCAA SLOT;

3. FOREIGN COUNTERFEITERS PRODUCE NEAR-PERFECT HUNDRED
DOLLAR BILLS;

4. BUDGET CUTS BLAMED FOR WEAK ENVIRONMENTAL LAW
ENFORCEMENT;

5. SILICON GRAPHICS INC. AGREES TO ACQUIRE CRAY RESEARCH

Setting = SHARP    Key = ZENITH    Hat = MAGNAVOX

Along with Paul Derthick's notes, "Introduction to the
HEADLINE PUZZLE", other references are: [LEWI], [NICH],
[ELCY], [SINK], [FRE1] [FRE2]. The HEADLINE PUZZLES
in this section are used with permission of PHOTON and

DIGRAPHIC CIPHERS: PLAYFAIR

Perhaps the most famous cipher of 1943 involved the
future president of U.S., J. F. Kennedy, Jr. [KAHN]
On 2 August 1943, Australian Coastwatcher Lieutenant
Arthur Reginald Evans of the Royal Australian Naval
Volunteer Reserve saw a pinpoint of flame on the dark
waters of Blackett Strait from his jungle ridge on
Kolombangara Island, one of the Solomons. He did not
know that the Japanese destroyer Amagiri had rammed and
sliced in half an American patrol boat PT-109, under
the command of Lieutenant John F. Kennedy, United States
Naval Reserve.  Evans received the following message at
0930 on the morning of the 2 of August 1943:

29gps

KXJEY  UREBE  ZWEHE  WRYTU  HEYFS
KREHE  GOYFI  WTTTU  OLKSY  CAJPO
BOTEI  ZONTX  BYBWT  GONEY  CUZWR
GDSON  SXBOU  YWRHE  BAAHY  USEDQ

/0930/2

Translation:

PT BOAT ONE ONE NINE LOST IN ACTION IN BLACKETT
STRAIT TWO MILES SW MERESU COVE X CREW OF TWELVE
X REQUEST ANY INFORMATION.

The coastwatchers regularly used the Playfair system.
Evans deciphered it with the key ROYAL NEW ZEALAND NAVY
and learned of Kennedy's fate. Evans reported back to
the coastwatcher near Munda, call sign PWD, that Object
still floating between Merusu and Gizo, and at 1:12 pm,
Evans was told by Coastwatcher KEN on Guadalcanal that
there was a possibility of survivors landing either on
Vangavanga or near islands.  That is what Kennedy and
on the Southeastern tip of Gizo Island.

Several messages passed between PWD, KEN and GSE
(Evans). The Japanese made no attempt to capture Kennedy
importance to them was missed even though many P-40's
were spotted in the Search and Rescue (SAR) attempt.
maybe the Japanese didn't want to waste the time or men
because the exact location of the crew was not
specified. A Japanese barge chugged past Kennedy's
hideout. On 0920 a.m. on Saturday morning 7 August 1943,
two natives found the sailors, who had moved to Gross
Island, and had reported to find Evans. He wrote a brief
message: Eleven survivors PT boat on Gross Is X Have
sent food and letter advising senior come here without
delay X Warn aviation of canoes crossing Ferguson RE.
The square Evans used was based on the key PHYSICAL
EXAMINATION :

P H Y S I
C A L E X
M N T O B
D F G K Q
R U V W Z

The encipherment did not split the doubled letters as is
the rule:

XELWA  OHWUW  YZMWI  HOMNE  OBTFW
MSSPI  AJLUO  EAONG  OOFCM  FEXTT
CWCFZ  YIPTF  EOBHM  WEMOC  SAWCZ
SNYNW  MGXEL  HEZCU  FNZYL  NSBTB
DANFK  OPEWM  SSHBK  GCWFV  EKMUE

There were 335 letters in 5 messages, in the same key
beginning XYAWO  GAOOA  GPEMO  HPQCW  IPNLG  RPIXL
TXLOA  NNYCS  YXBOY  MNBIN  YOBTY  QYNAI ..., for
Lieut. Kennedy considers it advisable that he pilot PT
boat tonight X ...  These five messages detailed the
rescue arrangements, which offered the Japanese a chance
to not only get the crew (and change all history!) and
the force coming out to save it. The Japanese failed to
solve what an experienced crypee could solve in one
hour. At 1000 hours that same day Kennedy and his crew
was rescued.

Digraphic substitution refers to the use of pairs of
letters to substitute for other pairs of letters. The
Playfair system was originated by the noted British
scientist, Sir Charles Wheatstone (1802 - 1875) but, as
far as known, it was not employed for military  or
adopted for use by the British Foreign Office on the
recommendation of Lord Lyon Playfair (1818-1898) and

Encipherment

The Playfair is based on a 25 letter alphabet (omit J)
set up in a 5 X 5 square.  A keyword is written in
horizontally into the top rows of the square and the
remaining letters follow in regular order.  So for the
key = LOGARITHM, we have:

L O G A R
I T H M B
C D E F K
N P Q S U
V W X Y Z

In preparation for encipherment, the plaintext is
separated into pairs. Doubled letters such as SS or NN
are separated by a null.

For example, "COME QUICKLY WE NEED HELP"  we have

CO ME QU IC KL YW EN EX ED HE LP

There are three rules governing encipherment:

1.   When the two letters of a plain text pair are in
the same column of the square, each is enciphered
by the letter directly below it in that column. The
letter at the bottom is enciphered by the letter at
the top of the same column.

Plain       Cipher
OP           TW
IC           CN
EX           QG

2.   When the two letters of a plain text pair are in
the same row of the square, each is enciphered by
the letter directly to its right in that row.  The
letter at the extreme right of the row is enciph-
ered by the letter at the extreme left of the same
row.

Plain       Cipher
YW           ZX
ED           FE
QU           SN

3.   When two letters are located in different rows and
columns, they are enciphered by the two letters
which form a rectangle with them, beginning with
the letter in the SAME ROW with the first letter of
the plaintext pair. (This occurs about 2/3 of the
time.)

Plain       Cipher
CO           DL
ME           HF
KL           CR
LP           ON

Decipherment, when the keyword is known, is accomplished
by using the rules in reverse.

Identification Of The Playfair

The following features apply to the Playfair:

1. It is a substitution cipher.

2. The cipher message contains an even number of
letters.

3. A frequency count will show no more than 25 letters.

4. If long repeats occur, they will be at irregular
intervals.  In most cases, repeated sequences will be
an even number of letters.

5. Many reversals of digraphs.

Peculiarities

1. No plaintext letter can be represented in the cipher
by itself.

2. Any given letter can be represented by 5 other
letters.

3. Any given letter can represent 5 other letters.

4. Any given letter cannot represent a letter that it
combines with diagonally.

5. It is twice as probable that the two letters of any
pair are at the corners of a rectangle, than as in
the same row or column.

6. When a cipher letter has once been identified as a
substitute for a plaintext letter, their is a 20%
chance that it represents the same plaintext letter
in each other appearance.

The goal of recovery of the 5 X 5 square and various
techniques for accomplishing this are the focus for
solving the Playfair.   Colonel Parker Hitt describes
Lieutenant Frank Moorman's approach to solving the
Playfair which addresses the keyword recovery logically.
[HITT].  Other writers [ELCY], [BOW2], [FRE4], and
[MAST] do an admirable job of discussing the process.
However, W. M. Bowers Volume I on Digraphic Substitution
presents the easiest protocol for students. [BOWE]

PLAYFAIR CRYPTANALYSIS

Our preliminary step is to perform individual letter
frequency and digraphic counts.  The former because high
frequency ciphertext letters follow closely the high
frequency letters they represent and will be located in
the upper rows; similarly, low frequency letters follow
their plain counterparts (UVWXYZ) and may be located at
the last row of the square.  A digraph count is useful
because cipher digraphs follow closely the frequency of
their plaintext digraphs. i.e. TH = HM. The frequency of
HM must be high for a normal length message. Also
tetragraphs may be tested THAT, TION, THIS for
corresponding their frequencies in the square.

All the authors agree that a probable word is need for
entry into the Playfair. Due to its inherent
characteristics, Playfair cipher words will follow the
same pattern as their plaintext equivalents; they carry
their pattern into the cipher.

Given:   Tip "er one day entere"     Hampian. 10/1952

EU  SM  FV  DO  VC  PB  FC  GX  DZ  SQ  DY  BA  AQ  OB
ZD  AC  OC  ZD  ZC  UQ  HA  FK  MH  KC  WD  QC  MH  DZ
BF  NT  BP  OF  HA  SI  KE  QA  KA  NH  EC  WN  HT  CX
SU  HZ  CS  RF  QS  CX  DB  SF  SI  KE  FP  (106)

We set up a combined frequency tally with letters to the
right and left of the reference letter shown:

K Q H H B   . A .   Q C
D O P   . B .   A F P
E Q K Z O A F V   . C .   X S X
W Z Z   . D .   O Z Y Z B
K K   . E .   U C
S R O B   . F .   V C K P
. G .   X
N M M   . H .   A A T Z
S S   . IJ.
F   . K .   C E A E
. L .
S   . M .   H H
W   . N .   T H
D   . O .   B C F
F B   . P .   B
U A S   . Q .   C A S
. R .   F
Q C   . S .   M Q I U F I
H N   . T .
S E   . U .   Q
F   . V .   C
. W .   D N
C C G   . X .
D   . Y .
H D D   . Z .   D D C

This particular message has no significant repeats.

Cipher  GX  DZ  SQ  DY  BA  AQ  OB  ZD  AC
Plain   ..  ER  ON  ED  AY  EN  TE  RE  ..

Note the first and last pair reversal.

It is necessary to take each set of these pair
equalities and establish the position of the four
letters with respect to each other. They must conform to
the above three rules for row, column, and rectangle.

The six different sets of pairs of know equalities are
set up:

1          2          3         4        5
er = DZ    on = SQ    ed = DY   ay = BA   en = AQ
------     -------    ------    -------   -------
E D R Z    O S N Q    E D Y     Y A B     E A N Q
D          S          D         A         A
R   E D    N   O S    Y         B         N   E A
Z   Z R    Q   Q N                        Q   Q N

6
te = OB
-------
T O E B
O
E   T O
B   B E

The three possible relations of the letters are labeled
Vertical (v), Horizontal (h), Diagonal (d).  Our object
is to combine the letters in each of the set of pairs.

Combine 1 and 3:  E R D Z Y

1/v - 3/v        1/h - 3/h        1/d - 3/h
---------        ---------        ---------
E            E D Y R Z          E D Y
D                               Z R
Y
R
Z

Combine 2 and 5: O N S Q E A

2/h - 5/d        2/d - 5/h         2/d - 5/d
---------        ---------         ---------
O S N Q          E A N Q             S O
A E              S O             N Q
A E

Note that all the equalities hold for all letters.

Set number 6 combines only with the last combination: T
E O B N S Q A

2/d - 5/d - 6/v                2/d - 5/d - 6/d
----------------                ---------------
T                          S O T
S O                          N Q
A E                          A E B
B
N Q

which we now combine with 4:

2/d - 5/d - 6/d - 4/h
---------------------
S T O
Y A E B           (rearranged and
N   Q            equalities hold)

only one combination of 1 and 3 will combine with the
above: S T O Y A B E D N Q Z R

1/d - 2/d - 3/h - 4/h - 5/d - 6/d
---------------------------------
S T O
Y A E B D
N   Q
Z R

Arranged in a 5 X 5 square:

. . S T O
D Y A B E
. . . . .
. . N . Q
R . . . Z

We see that O is in the keyword, the sequence NPQ
exists, the letters S T Y are in the keyword, and three
of the letters U V W X  are in needed to fill the bottom
row.

----------
. . S T O| C
D Y A B E|
. . . . .|
. . N P Q|
R . . . Z| U V W X

With the exception of F G H I K L M which must in order
fill up the 3rd and 4th rows, the enciphering square is
found as:

C U S T O
D Y A B E
F G H I K
L M N P Q
R V W X Z

Our plaintext message starts off: YOUNG RECRUIT DRIVER
ONE DAY ENTERED STORE ROOM ....

SERIATED PLAYFAIR

Perhaps the best known variation of the Playfair system,
and one which adds greatly to its security, is called
the Seriated Playfair.

The plain text is written horizontally in two line
periodic groups as shown below in period six

C O M E Q U    E N E E D H    M E D I A T
I C K L Y W   (X)E L P I M    E L Y T O M

The vertical pairs are formed and enciphered by the
regular Playfair rules. Based on the keyword LOGARITHM,
the above message is enciphered:

L O G A R                  Cipher:
I T H M B    N L B C S P   Q Q C D C M   H C F T R H
C D E F K    C D F G X Z   G C G Q T B   F G W H G B
N P Q S U
V W X Y Z

we take the ciphertext off horizontally by the same
route by which the plain text was written in for
encipherment:

NLBCS  PCDFG  XZQQC  DCMGC  GQTBH  CFTRH  FGWHG  B.

Solution of Seriated Playfair:

We assume a period of 4 - 10 which fits most of the
cases encountered.  Of prime importance is determination
of the period. We test the various periods and eliminate
any test where we find a vertical pair consisting of two
appearances of the same letter.

If the message enciphered above is tested this way, in
all periods from 4 - 10, it will be found that period 6
is correct. All others will show a doubled vertical
pair.

Charles A. Leonard [PLAf] detailed a method to determine
impossible periods mathematically:

S2
-------    = Q & R
S2 - S1

where: S2 - S1 = Period, Q = quotient, R = remainder

Substituting known S values in this formula and solving
for Q and R, a doubled vertical pair will occur in
period S2 - S1 in the following cases:

1.  When Q is an odd number and R is greater than
zero;
2.  When Q is an even number and R is zero.

Cipher letter position numbers in our message are:

A   B   C   D   E   F   G   H   I   K   L    etc.
3   4   8       9  10  25           2
24   7  16      27  19  30
36  15          31  21  34
17              32
20              35
26

Period  Letter  S2 - S1     Q   R   Result
4       F     31 - 27     7   3   Eliminated-Case 1
5       C     20 - 15     4   0   Case 2
6       C     26 - 20     4   2   possible
7       H     34 - 30             Eliminate-last gp
8       D     16 - 8      2   0   Case 2
9       C     26 - 17     2   8   possible
G     19 - 10     2   1   possible
H     34 - 25     3   7   Case 1
10      C     17 - 7      1   7   Case 1

When a periodic group S2 - S1 does not occur in message
the last group is inspected. If it is shorter than the
regular groups of the period being tested, a double
vertical pair may show at S2- S1 value equal to the
length of this final group. If so, eliminate.

The mono and digraphic frequency counts are made.
Plaintext high frequency digraphs and tetragraphs do not
carry their identity over into the cipher and are not
recognizable. Entry must be made with a probable word.
Patterns do carry over to the two line groups and will
repeat.

The placing of the probable word is important. Given a
cipher text slice with period 6 found using the Leonard
procedure:

HKILVP   PBVBAA   BHRPOU   TBITFE   UCEVZK
RNFTZU   HZWVFR   UDTKBD   UIBYNS   EXBZAR

and the probable phrase "is destined to", the word
destined could be in any of the following positions when
enciphered in period 6:

DESTIN  .DESTI   ..DEST   ...DES    ....DE
ED....  NED...   INED..   TINED.    STINED

The DE = ED reversal in all arrangements is noted and
found in the cipher text portion:

BHRPOU   TBITFE   UCEVZK
UDTKBD   UIBYNS   EXBZAR
.desti
ned..

BHRPOU   TBITFE   UCEVZK
UDTKBD   UIBYNS   EXBZAR
.   sdesti
i   nedto.

we develop several equations:

ed = IB
-I = UD, sn = TU, de = BI, ST = TY, to =FN, I- =ES

these translate to the following equalities:

1          2          3         4        5
SN = TU    DE = BI    ST = TY   TO = FN   I- = ES
-------    -------    ------    -------   -------
S T N U    D B E I    S T Y     T F O N   I E - S
T          B          T         F         E
N   S T    E   D B    Y         O   T F   -   I E
U   U N    I   I E              N   N O   S   S -

6         7
-I = UD    ED = IB
-------    -------
- U I D    E I D B
U          I
I   - U    D   E I
D   D I    B   B D

After some work (and with some assumptions to be tested
we develop a tentative square for the system:

1/d-2/d -3/h-4/v- 5/h -6/h
--------------------------
-
O U N
I E
D B
F S T Y

check:
TO=FN+   + = yes
SN=TU+
ST=TY+                        letters left: A C E G H K
I-=ES -=t  IT =ES                           L M P Q R V
DE=BI+                                      W X Z
ED=IB+
-I=UD+

from here we need to expand on the cipher text or choose
another probable word.

DELASTELLE SYSTEMS - FOURSQUARE CIPHER

The enigmatic Frenchman, Felix Delastelle created
several nasty but very interesting cipher systems.
We will discuss three of his systems. They are the
Foursquare, Bifid, and Trifid.  [DELA]

The Four Square employs four 25-letter alphabets set up
in four 5 X 5 squares.  The alphabets in the upper left
and lower right squares are straight alphabets sans J.

Plaintext letters are found in these two alphabets when
the message is enciphered. The opposite squares are used
for ciphertext.

Encipherment follows only one rule. The plaintext
letters are divided into pairs. The first letter is
found in square 1, 2nd in square three. The two cells
are thought of as opposite corners of diagonals of an
imaginary rectangle.  The first cipher letter is found
in square 2 and the 2nd is found in square 4. The
operation continues until all letters are enciphered.

For example, given:

1           2
.....................
A B C D E . G R D L U
F G H I K . E Y F N V
L M N O P . O A H P W
Q R S T U . M B I Q X
V W X Y Z . T C K S Z
.....................
L I C N V . A B C D E
O T D P W . F G H I K
G H E Q X . L M N O P
A M F S Y . Q R S T U
R B K U Z . V W X Y Z
.....................
4           3

Plain    CO ME QU IC KL YW EN EE DH EL PX
Cipher   LE WI XA FN EX CU DX UV DP GX HZ

Decipherment, when keywords are known is the reverse.
Using GEOM(E)TRY and LOGARITHM squares for the following
cipher text:

Plain     XF WX PO DY DG GN AH
Cipher    SU PP LI ES AN DA MM

Identification of the Four Square

1. It is a substitution cipher.
2. It has an even number of letters.
3. Frequency count of 25 letters without J.
4. Doubled letters may occur eliminating a Playfair.
5. Long repeats occur at irregular intervals.  Even
sequences are most frequent.
6. Few reversals in comparison to Playfair.

Peculiarities of the Four Square

1. A plaintext can be represented by itself in the
cipher.
2. Any ciphertext letter can be represented by five
letters.
3. Any given plaintext letter can be represented by five
ciphertext letters.
4. A cipher letter can represent itself or the other
letter of the pair.
5. Every cell frequency is known or can be calculated
because of the straight alphabets.
6. The fixed locations of the letters in squares 1 and 3
makes it possible to spot the location of probable
words which form a pattern when enciphered by the
Four Square.

Cell Frequencies

Bower and Meaker have derived the probabilities of the
normal ciphertext based on the normal distributions for
the straight alphabets in 1 and 3 based on 100
diagraphs.  [BOWE]

1           2
.....................
A B C D E . 5 5 8 8 4
F G H I K . 2 1 4 5 2
L M N O P . 4 4 4 8 5
Q R S T U . 2 2 8 8 5
V W X Y Z . 1 1 1 2 1
.....................
4 5 8 5 5 . A B C D E
2 2 4 8 2 . F G H I K
4 2 4 8 5 . L M N O P
4 2 5 8 8 . Q R S T U
1 1 1 1 1 . V W X Y Z
.....................
4           3

The Four Square follows the normal distribution of
letters:

High
Letter               E  T  A  O  N  I  R  S  H
Normal frequency    13  9  8  8  7  7  7  6  6

Normal 4-square freq.8  8  8  8  8  5  5  5  5  5
Square 2 cell       44 14 13 34 43 12 45 24 11 35
Square 4 cell       13 44 34 24 45 14 12 15 43 35

Medium                      Low
L  D  C  U  P  F    M  W  Y  B  G  V  K  Q  X  Z
4  4  3  3  3  3    2  2  2  1  1  1  0  0  0  0

Square 2 cell = A
Square 4 cell = B

4  4  4  4  4       2  2  2  2  2  1  1  1  1  1
A=31 33 32 23 15      25 41 21 42 54 22 55 53 51 52
B=31 41 23 33 11      22 32 42 21 25 54 51 55 53 52

The figures represent row X column frequencies.

Bowers presents an interesting Four Square problem known
as the Stock Exchange Cipher. It supposedly is a message
to a broker. The investor sold 'rails' and probable
words such as Texas Eastern, Consolidated, and Columbia.
The message deciphered represents the process fairly
well:

UL RQ GW FO WQ CF PF FG EA GX LH DI OP MM LA LT
OF YQ CD HU GA LA FO EW EA VT YP QS UF WF RI CF
YQ QD LN QI WP YF OY MY AX FO WQ CF PF WF RC HQ
BT GW AQ SY QI WP GB BW HR WB EO EX GT LV PX OO
FO BQ HQ UM QS HE LT TM YM PN QI WP LB LO QO DP
SY BP QI YL LI MP DI OD NM UT ZH GT YM LQ HP HQ
QE IE XO MI.

2nd letter                                  1st letter
frequency                                   frequency

5             E L G L E .A. X Q                    2
3                 L W G .B. T W Q P                4
1                     R .C. F D F F                4
4               O O Q C .D. I P I                  3
3                 I Q H .E. A W A O X              5
10  W P C Y C W U O P C .F. O G O O O              5
1                     F .G. W X A W B T T          7
2                   Z L .H. U Q R Q E P Q          7
9     M D L Q Q Q Q R D .I. E                      1
0                       .K.                        0
2                   Y U .L. H A T A N V T B O I Q  11
6           Y N Y T U M .M. M Y P I                4
2                   P L .N. M                      1
8        X Q L F E F F F O. P F Y D D              5
9      H M B D W W W Y O P. F F X N                4
11H L H B A H W Y Y W R .Q. S D I I S I O I E      9
1                     H .R. Q I C                  3
2                   Q Q .S. Y Y                    2
7         G U L G B V L .T. M                      1
1                     H .U. L M F T                4
1                     L .V. T                      1
4               B G E G .W. Q F P Q F P B P        8
4               P E A G .X. O                      1
4               S S M O .Y. Q P Q F M L M          7
0                       .Z. H                      1
100                                               100

Long Sequences           Repeated Digraphs

FO WQ CF PE -2           FO-4   CF-3
QI WP       -3           QI-4   HQ-3
WP-3

Compare to normal square frequencies:

1st letter
L Q W G H Y E F O B C M P U D R A S I N T V X Z K
Frequency square #2
119 8 7 7 7 5 5 5 4 4 4 4 4 3 3 2 2 1 1 1 1 1 1 0
Normal
88 8 8 8 5 5 5 5 5 4 4 4 4 4 2 2 2 2 2 1 1 1 1 1
Frequency square #4
11109 9 8 7 6 5 4 4 4 4 3 3 2 2 2 2 1 1 1 1 1 0 0
2nd letter
Q F I P O T M A D W X Y B E H L N S C G R U V K Z

Lets assume the word CONSOLIDATED.

Plain     CO NS OL ID AT ED
Cipher    LH DI OP MM LA LT
*           *  *

1           2
.....................
A B C D E . - - - L -
F G H I K . - - - M -
L M N O P . O - D - -
Q R S T U . - - - - -
V W X Y Z . - - - - -
.....................
- - - M T . A B C D E
- - - - - . F G H I K
- - H P - . L M N O P
A - I - - . Q R S T U
- - - - - . V W X Y Z
.....................
4           3

LM and HI imply that the keywords have been written in
vertically. Check against frequencies.

Square #2             Square #4
Cell     14 24 31 43         15 24 33 34 41 43
Norm      8  5  4  8          5  8  4  8  4  5
Cipher    L  M  O  D          T  M  H  P  A  I
Freq.    11  4  5  3          7  6  2  9  5  9

The check works.  Additional plaintext found:

Cipher      Plaintext
LI            ct
MP            io
MI            ht
DP            on

Insert the new values into the cipher.

Cipher   QI WP LB LO QO DP SY BP QI YL LI MP DI OD NM
Plain                   ON             CT IO NS

This might imply 'directions' or 'instructions'.

Since O is in the keyword for cipher square 2, the
letter after LM must be N P or Q.

>From our frequency chart:

N P Q R S T U
1 4 9 3 2 1 4

Tentatively, lets put P in cell 32 and Q in 34 giving us
the new ciphertext pair QI =ST; the QIWP is repeated
three times and might be the word STOP.  We add to our
partially filled in matrix.

1           2
.....................
A B C D E . - - - L -
F G H I K . - - - M -
L M N O P . O - D P W
Q R S T U . - - - Q -
V W X Y Z . - - - - -
.....................
- - - M T . A B C D E
- - - - - . F G H I K
- - H P - . L M N O P
A - I - - . Q R S T U
- - - - - . V W X Y Z
.....................
4           3

So:

Cipher   QI WP LB LO QO DP SY BP QI YL LI MP DI OD NM
Plain    ST OP    DI TI ON       ST    CT IO NS

Cell 53 of square 4 is K.  QO =ti,  LO = di.

>From here it is not a far stretch to fill in the blanks:

Cipher   QI WP LB LO QO DP SY BP QI YL LI MP DI OD NM
Plain    ST OP    DI TI ON       ST    CT IO NS

Back to the Four Square to place additional values.

1           2
.....................
A B C D E . S - - L -
F G H I K . - - B M -
L M N O P . O - D P W
Q R S T U . - - F Q Y
V W X Y Z . - - - - Z
.....................
B - - M T . A B C D E
- - - - - . F G H I K
Y - H P - . L M N O P
A L I Q - . Q R S T U
- - K R - . V W X Y Z
.....................
4           3

A righteous guess would be STOCK and BUY AND SELL for

Cipher          FO WQ CF PF FG EA GX LH DI OP MM LA LT
Plain           th ou                co ns ol id at ed
'F' in 13                nd
'G' in 23                   sh
probable        th ou sa nd sh ar es co ns ol id at ed

Putting these in confirm our guess as to the keywords:

1           2
.....................
A B C D E . S E G L U
F G H I K . T X B M V
L M N O P . O H D P W
Q R S T U . C A F Q Y
V W X Y Z . K N I R Z
.....................
B D F M T . A B C D E
U S G O V . F G H I K
Y E H P W . L M N O P
A L I Q X . Q R S T U
N C K R Z . V W X Y Z
.....................
4           3

Keywords= STOCK EXCHANGE; BUY AND SELL
Cipher starts off: UL RQ GW
Bu yt en

Observations

1. Nulls are not required as in Playfair.
2. Probable position of letters can be spotted
through cell frequency.
3. Probable words can be definitely placed if they
produce a pattern.

There is no reason why all the squares can not be mixed
for additional security. This destroys the frequency
distribution attack; but digraphic and longer repeats
will still show through to the ciphertext. The most
reliable attack on the Four Square is via a probable
word.

DELASTELLE SYSTEMS - BIFID CIPHER

Friedman, Bowers and Lewis discuss the intricacies of
the Bifid cipher.  [FRE4], [BOWE], [MAST] You will find
many references to the Bifid cipher in the Cryptographic
Resources Section, many of them developed from ACA
materials.  Dr. Linz (LEDGE) covers the BIFID in some
detail. [LEDG]

The Bifid and Trifid ciphers represent a new and tougher
breed of classical cipher - Fractionated Ciphers. The
process of fractionation, whereby the substitute unit is
1/2 or 1/3 or 1/part for each letter represents a more
involved problem for analysis that some of the ciphers
presented to date.  What we do is combine substitution
and transposition processes to produce a clever mixed
cipher.  Modern ciphers do the same thing many times
over (called rounds or S-Boxes in DES).

Method of Encipherment By Bifid

The secretive Delastelle designed the Bifid to use a
checkerboard square with 25 letters, sans J.  We start
with a keyworded square:

1 2 3 4 5
1 M A N Y O
2 T H E R S
3 B C D F G
4 I K L P Q
5 U V W X Z

Key = MANY OTHERS

The encipherment process is periodic and the number of
letters in each group is usually an odd number. Even
Bifids are actually easier to solve than odd. We will
focus on the odd Bifid to illustrate the process. Period
lengths of 7, 9, 11, or 13 are those most frequently
employed.

Encipherment is a combination of substitution and
transposition which is best shown by example.  We will
encipher the message COME QUICKLY WE NEED HELP in period
7.

Step 1: Period Length.

First divide the plaintext message into groups of 7
letters. Write the numerical equivalents for row and
column vertically under the plaintext letters.

C O M E Q U I   C K L Y W E N   E E D H E L P
Row  3 1 1 2 4 5 2   3 4 4 1 5 2 1   2 2 3 2 2 4 4
Col  2 5 1 3 5 1 1   2 2 3 4 3 3 3   3 3 3 2 3 3 4

Step 2: Horizontal Transposition and Take Off

The next step is a form of transposition, wherein the
numerical substitutes are taken off horizontally by
pairs. In each individual group this take-off continues,
without interruption, through the two rows of numbers.
The last number of the top row pairs with the first
number of the bottom row. The first number of each
horizontal pair indicates the row of a cipher letter and
the second number of the pair indicates the column of
that cipher letter.

Step 3:

Find the cipher letters in the square using the new row
X column coordinates.

Plain         C O M E Q U I
Row         3 1 1 2 4 5 4
Col         2 5 1 3 5 1 1
Cipher        B A Q K U G M

31 = B; 12 = A; 45 = Q; 42 = K; 51= U; 35 = G; 11 =M

The process might be more clear if we look at the
encipherment this way:

Row             Column
C O M E Q U I   C O M E Q U I
3 1 1 2 4 5 4   2 5 1 3 5 1 1
B   A   Q    K    U   G   M

We see that cipher 'B"' has the same row 3 as 'C' row
and  'B' column (1) has the same number as O row (1).
This reasoning holds for the second and third cipher
letters 'A' and 'Q'.  The fourth cipher letter 'K' has
the same row (40 as plain 'I' and the same column number
(2) as plain 'C', which are the last and first letters
of the group. The fifth, sixth and seventh cipher
letters are derived the same way, except that we deal
with columns. The fifth cipher letter 'U', is the result
of 'U' row (5) and 'M' column (1).

Each cipher letter results from the some combination of
half values of the two plaintext letters. Due to this
characteristic, the Bifid (and Trifid with thirds) is
classified as Fractional Substitution.

Deciphering the Bifid with Known Elements:

Step 1: Fractionate the cipher letters into their row
and column components.

Step 2: Write into two rows horizontally of periodic
length.

Step 3: Write the numerical values into the two
horizontal rows below the fractionated letters.

Step 4: Recover Plain text letters vertically.

Cipher Fractionated   Br Bc Ar Ac Qr Qc Kr
Kc Ur Uc Gr Gc Mr Mc
--------------------
Plaintext Row         3  1  1  2  4  5  4
Plaintext Column      2  5  1  3  5  1  1
Plaintext             C  O  M  E  Q  U  I

Identification of the Bifid

1. It is a substitution cipher with substitution units =
to 1/2 of the cipher letter, represented by row or
column index.

2. Frequency count of 25 letters (J omitted) but not
more for 5 X 5 Bifid.  MASTERTON describes a 6 X 6
Bifid with letters and symbols included. [LEWI]

3. Long repeats occur at irregular intervals.

4. Repeated patterns dependent upon the length of the
repeated sequence and the period, ex.:

AB .. D         A .. CD
AB .. DE        AB . CD

5. A frequency count will show a flat profile compared
to normal plaintext.

Peculiarities of the Bifid

1. When the cipher letters are set up in the correct
period a few 'naturals' will occur. A natural  is the
term for a vertical cipher pair, arranged row-column
order, in which both components are the same letter.
When this happens the plaintext letter is revealed.
This is not true when the cipher letters are column-
row unless the letter happens to be one of the five
on the diagonal of the square running from 1-1 to
5-5.

For:
1 2 3 4 5
1 M A N Y O
2 T H E R S
3 B C D F G
4 I K L P Q
5 U V W X Z

Cipher   Hr hc Ar Ac Hr
Hc Cr Cc Ar Ac
--------------
Plain    H  E  A  T  H
*

The first plaintext letter  H is a natural but the T on
the fourth is not.  The great majority of naturals will
be high frequency plaintext letters. If low frequency
plaintext letters appear as naturals, it is almost a
certainty that the cipher message is set up in an
incorrect period.

2. Half-naturals occur quite frequently, when the cipher
is set up in the correct period. One of the letters
of the vertical pair, in row-column order, is the
same as the plaintext letter it represents.

Cipher   Tr Tc Qr Qc Sr
Sc Wr Wc Er Ec
--------------
Plain    S  O   L  V  E
*            *

The probability that one of the letters in row-column
pair is a half-natural is 8 in 25, or 32%  The
probability of a half-natural in column-row order (along
the diagonal) is 1/5 of 32% or 6.4%  Half naturals are a
function of the expected appearances of the plain text
letter. For instance, in a cipher of 100 letters, we
find 10 'E's and 10 'Z's.

Cipher Letter E = 10 X 0.32 = 3.2 half-naturals
Cipher Letter Z = 10 X 0.32 = 3.2 half-naturals

but the E is 13 times more likely than the Z. So the E
is expected to appear 13 times in 100 letters so the 3-4
half-naturals is possible but the Z will occur only 1
time in 100, so we may expect no half-naturals.

3. Half-naturals are the Bifid's most vulnerable
feature because it plays a large part in spotting
probable words.

4. The Bifid, fractionated for decipherment, engenders
two separate and different alphabets. One applies to
odd numbered vertical pairs, found in the basic
square and the other applies to even vertical pairs
in each periodic group.

5. Repeated plaintext sequences produce patterns as long
as the repeat starts in the same relative location in
the group as of its first appearance.

Odd                      Even
1   3   5   7            2   4   6
Plain    H O M E I S A          A H O M E I S
2 1 1 2 4 2 1          1 2 1 1 2 4 2
2 5 1 3 1 5 2          2 2 5 1 3 1 5
-------------          -------------
Cipher   T A K A U B V          A M R H S N O

Odd                      Even
1   3   5   7            2   4   6
Plain    G O H O M E N          T H E H O M E
3 1 2 1 1 2 1          2 2 2 2 1 1 2
5 5 2 5 1 3 4          1 2 3 2 5 1 3
-------------          -------------
Cipher   B T A O V U F          H H M A E S N

The spacing for repeated cipher letters varies for
different periods. For four letter repeats it is:

Odd                     Even
Period 5   T A . U                 M . S N
7   T A . . U               M . . S N
9   T A . . . U             M . . . S N
11   T A . . . . U           M . . . . S N

Repeats of the other lengths generate their own
individual patterns. For period 7 these are:

Odd              Even
3 letter repeats   A . . . D         U . . X
4                  A B . . D         U . . X Y
5                  A B . . D E       U V . X Y
6                  A B C . D E       U V . X Y Z

The search for repeated patterns is the first step to
finding the correct period for solution of the Bifid.
Patterns are formed by plaintext components which serve
to make up complete cipher pairs. It does not make any
difference what letters may be in other places of the
group, the same patterns will always show for the word
in question, whenever it is enciphered in the same
period.  For example, for period 9:
Odd                      Even
1   3   5   7   9        2   4   6   8
Plain    . . b i f i d . .      . b i f i d . . .
. . 3 4 3 4 3 . .      . 3 4 3 4 3 . . .
. . 1 1 4 1 3 . .      . 1 1 4 1 3 . . .
-----------------      -----------------
Cipher   . F F . . . Y N .      . L L . . M I . .

THE THREE SQUARE TECHNIQUE

There are two basic ways to cryptanalyze the Bifid. One
involves placing of a probable word after determination
of the correct period and manipulating the rows and
columns of the Bifid decipherment square until it is
fully recovered or the keyword is found.  Friedman
discusses this method in detail. [FRE4] Bowers also
covers this approach but introduces the reader to a more
comfortable method for solution using the square itself
as a indicator of the letter indexes. Developed by
William A Lee (TONTO) in June, 1945, it uses three
squares to eliminate the requirement for numerical
indices.

The setup is as follows:

. . . . . . .
. E S C L V .   Top Square
. N I D O W .   Row used as
. T A F P X .   Column
. H M G Q Y .   Indicators
. U B K R Z .
. . . . . . . . . . . . .
. E S C L V . E N T H U .
Left Square  . N I D O W . S I A M B .   Basic Square
Column used  . T A F P X . C D F G K .    Normal
as row       . H M G Q Y . L O P Q R .   row and column
indicator    . U B K R Z . V W X Y Z .
. . . . . . . . . . . . .

Rules for encipherment and decipherment under three
square approach

We are always starting with fractions of two letters and
searching for the single letter that it represents by
these half values.

For encipherment, pairs will be fractionated like this:

SrXr        SrXc       ScXc

For decipherment, the fractionated pairs will be:

SrXc        ScXr

1.  When one or both of the fractions is in the true
position in a pair, it/they are found in the Basic
Square.

SrXc  - both in basic
SrXr     S in basic
ScXc     X in basic

2.  When one of the fractional letters of the pair
indicates that its row designates a column of the
letter it is to represent, then it will be found in
the top square.

SrXr -  X in top square
ScXr    X in top square

3.  When one of the fractional letters of the pair
indicates that its column designates the row of the
letter it is to represent, then it is found in the
left square.

ScXc - S in left square
ScXr   S in left square

Using the word SOLVE we visualize:

Sr Or Lr Vr Er
Sc Oc Lc Vc Ec

---   ----   -
S  O  L  V   E
-  ---   ----

SrOr - S row (basic); Orow as col (top),= M (basic)
LrVr -L row (basic); Vrow as col(top), =  R  "
ErSc -E row (basic); Scol (basic) =       E  "
OcLc- O col as row(left); L col (basic) = S  "
VcEc - Vcol as row(left);E col(basic) =   E  "

The same rules apply in reverse when the vertical pairs
are fractionated and the plain text equivalents are
found at the intersections.

CHI-SQUARE

Karl Pearson's Chi-Square test, which we described
previously, was adapted by D. Morgan in 1946 to
determine the period of a Bifid. Excluding middle
letters, letters fall into one of two families, the row
and column. Chi-Square tests the dissimilarity of
probable groups of different lengths. The periodic
length for which the difference is the greatest
represents the correct period. We calculate D**2/S,
where S equals the sum of the appearances in both row
and column families of any letter. D equals the
difference between the family appearances of any letter.

When D**2/S is calculated for every letter, these values
are summed and their sum is the Chi-Square value for
period under consideration.
If we were to find the following:

Period       Chi-Square
5            19.2
7            19.4
9            28.0
11            12.0

Our choice would be period 9.  Morgan's article in the
JJ 1946 Cryptogram details the procedure. [BIF3]

Lets try to solve an Odd period Bifid.

Given:  The Master Spy Cipher - Concerning espionage,
and the man who was Hitler's Chief of Intelligence
during WWII.

FRIEN  ILOSV  FDYAE  MWDAH  IALTN  IBLVY  EQATP  TNTTI
XLPNP  HIVIR  TDZKK  LVNDE  ASBTI  CWDNH  YLZZK  LOEPE
ARFSI  VHILT  ZRKRS  ENTWE  ONXEN  CITOI  VRPMP  ENLEY
FQTLK  HZHIN  IPKHT  TLBDT  TPBOZ  OTKTD  SBTLF  TLRIW
YIHKV  DZPXT  FIIZ.

Inspection of this message reveals a repeat in the form
of A B . . . C D. This 5 letter repeat at the odd
position is in period 9. The fractionated cipher letters
would be located as shown, depending on the starting
position.

1st position       3rd position       5th position
K K L L . . . . .  . . K K L L . . .  . . . . K K L L .
. E E A A . . . .  . . . E E A A . .  . . . . . E E A A
x x x x x              x x x x x              x x x x x

The first appearance of the repeat starts at letter 55
and the second at the letter 75.

55 / 9 = 6 plus 1
75 / 9 = 8 plus 3

Hence in period 9, the first repeat starts in group 7,
position 1 and the second in group 9, position 5.

We accept the period and rewrite the ciphertext. Using
the skip hit form of the three square, eliminate the
even vertical pairs, recognizing that they are column -
row pairs and that they may be visualized as a diagonal
from the top letter to next bottom letter in the two
rows.

F  R  I  E  N | V  F  D  Y  A | A  H  I  A  L |
N  I  L  O  S | A  E  M  W  D | L  T  N  I  B |

L  V  Y  E  Q | N  T  T  I  X | H  I  V  I  R |
Q  A  T  P  T | X  L  P  N  P | R  T  D  Z  K |

K  L  V  N  D | T  I  C  W  D | Z  Z  K  L  O |
D  E  A  S  B | D  N  H  Y  L | O  E  P  E  A |

R  F  S  I  V | Z  R  K  R  S | E  O  N  X  E |
V  H  I  L  T | S  E  N  T  W | E  N  C  I  T |

O  I  V  R  P | L  E  Y  F  Q | Z  H  I  N  I |
P  M  P  E  N | Q  T  L  K  H | I  P  K  H  T |

T  L  B  D  T | Z  O  T  K  T | L  F  T  L  R |
T  T  P  B  O | T  D  S  B  T | R  I  W  Y  I |

H  K  V  D  Z | I  I
Z  P  X  T  F | I  Z .

We have four naturals present: E-T-T-I.
We know from the pattern repeat that:

K   L   Vr    and    K   L   Or
Dc  E   A            Pc  E   A
----------           ---------

represent the same five plaintext letters, so D and P
are co-column and V and O are co-row.  we start the
recovery of the basic square.

D . . . .
P . . . .
. V O . .
. . . . .
. . . . .

we test the probable word ESPIONAGE.

Locations  E S P I O N A G E
1-4               x x   x
2-3     x           x
5-7         x x
6-4           x         x
9-3     x   x       x       ***
10-4       x   x
10-9       x        x
12-1     x               x
12-9     x     x

Z   K   L   O  | R   F
E   P   E   A  | V   H
---------------------
E S P I O N A    G E
*   *       *

3 half-naturals!

5 letter repeat: P I O N A and 3 half-naturals. Wow.
Good hit.

Compare to location 6-8 (group and position):

I   R | K   L   V   N
Z   K | D   E   A   S
--------------------
E S   P I O N A G E

Combine both into one three square diagram:

. - - - - - .
. H - - L - .
. P E R O - .
. I Z S V - .
. K N G A - .  - - - D -
. . . . . . . . . . . . .
. - - R L I . E - Z N - .
. - - - - N . O L V - - .  A - - - -
. - - V Z G . S R G - - .
. - E S O K . K I - - - .  - P H - -
. - - - - - . - - - - - .
- - - - -                - D - - -
- - - P D
- - - - H
- - - - A

numbered pairs to fill in the left and top squares
quickly. We then write in the known odd pairs. we write
the odd pairs into unallocated rows and columns and then
consolidate them.

Plaintext can be recovered which leads to new ciphertext
square letters being recovered. The phrase FOR NINE
YEARS at Groups 1 and 2; The Name HITLER in groups
17 and 18; the phrase FOR HITLERS THIRD REICH in groups
10-11-12.

Placed in our squares:

Y D Q C X .
. H T F L M .
. P E R O U .    Master
. I Z S V B .     Spy
. K N G A W .
. . . . . . . . . . . . .
. W T R L I . E T Z N D .
. B C H F N . O L V C A .
. U Y V Z G . S R G F Q .
. X E S O K . K I Y H P .
. M Q A P D . X W U B M .

The entire message can be read. The letters which fall
on the diagonal are known because they are repeated in
the left square in the same long row and in the top
square in the same long column. These letters can be
shifted along the diagonal, but cannot be moved away
from it. Doing so we have the enciphering square and the
true transposition that generated it.

C A L V O
B M W U X
N D T Z E
F Q R G S
H P I Y K

from:

C O U N T E R S P Y
A B - D - F G H I K
L M - - - Q - - - -
V W X - Z

F   R   I   E   N|V   F   D   Y   A|A   H   I   A  L
N   I   L   O   S|A   E   M   W   D|L   T   N   I  B
----------------------------------------------------
f o r n i n e y e a r s a d m i r a l w i l h i l m c

L   V   Y   E   Q|N   T   T   I   X|H   I   V   I   R
Q   A   T   P   T|X   L   P   N   P|R   T   D   Z   K
-----------------------------------------------------
a n a r i s d i r e c t e d t h e m i l i t a r y e s

K   L   V   N   D|T   I   C   W   D|Z   Z   K   L   O
D   E   A   S   B|D   N   H   Y   L|O   E   P   E   A
-----------------------------------------------------
p i o n a g e a n d t h e c o u n t e r e s p i o n a

R   F   S   I   V|Z   R   K   R   S|E   O   N   X   E
V   H   I   L   T|S   E   N   T   W|E   N   C   I   T
-----------------------------------------------------
g e f o r h i t l e r s t h i r d r e i c h n o w i t
O   I   V   R   P|L   E   Y   F   Q|Z   H   I   N   I
P   M   P   E   N|Q   T   L   K   H|I   P   K   H   T
-----------------------------------------------------
a p p e a r s t h a t t h e s s o f t g p o k e n l i

T   L   B   D   T|Z   O   T   K   T|L   F   T   L   R
T   T   P   B   O|T   D   S   B   T|R   I   W   Y   I
-----------------------------------------------------
t t l e m a n b e t r a y e d h i t l e r a t e v e r

H   K   V   D   Z|I   I
Z   P   X   T   F|I   Z
-----------------------
y o p p o r t u n i t y

The Even period Bifid is covered in copious detail in
Bowers. [BOWE]

DELASTELLE SYSTEMS - TRIFID CIPHER

Both Bowers and Linz covers the Trifid in detail. [BOW2]
[LEDG]  Bowers covers the Trifid in detail. Topics
include Keyword Block recovery, periodic group
structure, Trifid patterns, pattern uncertainty,
tetragraphic patterns and part naturals.

We know that P = n**r represents the permutations with
repetitions, n = number of different things, r = number
of things used at a time. The normal Bifid square shown
below, thought of as a 5 X 5 block with external
coordinates.

1 2 3 4 5
1 B I F D A
2 L P H E T
3 C G K M N
4 O Q R S U
5 V W X Y Z

But 5 x 5 block is also 5 x 5 = n**2, the right hand
portion of the formula. Look at it a new way:

r=2
-----------------------------------------------------
Row     1         2         3         4         5
Col 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
B I F D A L P H E T C G K M N O Q R S U V W X Y Z
-----------------------------------------------------
P = 25

In the case of the Trifid, the block takes the same form

r=3
-------------------------------------------------------
1         1                 2                 3
2   1     2     3     1     2     3     1     2     3
3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3
T R I F D A L P H B E C G J K M N O Q S U V W X Y Z #
-------------------------------------------------------
P = 27

I like to work with compact matrices so here is another
way to show the structure in three directions:

2nd Comp

1 1 1 2 2 2 3 3 3
-----------------
1 T R I F D A L P H
1st Comp    2 B E C G J K M N O
3 Q S U V W X Y Z #
-----------------
1 2 3 1 2 3 1 2 3

3rd Comp

For the purpose of this lecture, the Trifid setup will
be shown as a 27 X 3 block containing all possible
changes in order of the three numbers 1-2-3, taken three
at a time and arranged in ascending order. The numbers
within the block, when read vertically, serve as
components of the letters of the alphabet which is
added, externally, to the block. So:

Comp
| T R I F D A L P H B E C G J K M N O Q S U V W X Y Z #
| -----------------------------------------------------
1|1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3
2|1 1 1 2 2 2 3 3 3 1 1 1 2 2 2 3 3 3 1 1 1 2 2 2 3 3 3
3|1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3
------------------------------------------------------

The fact that 27 letters are required for the Trifid is
a weak feature of the system. we can use a ZA and ZB to
represent the 27 letter and the true Z respectively.
A scrambled alphabet is always used to prevent some
letters being represented all the time by the same
combination.   Based on keyword COUNTERSPY:

1 2 3 4 5 6 7 8 9 10
-------------------
C O U N T E R S P Y
A B D F G H I J K L
M Q V W X Z #
-------------------

The letters are taken off vertically in order of
columns. We set up two tables:

Deciphering Table

C A M O B Q U D V N F W T G X E H Z R I # S J P K Y L
-----------------------------------------------------
|1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3|
|1 1 1 2 2 2 3 3 3 1 1 1 2 2 2 3 3 3 1 1 1 2 2 2 3 3 3|
|1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3|
------------------------------------------------------

Enciphering Table

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z #
-----------------------------------------------------
|1 1 1 1 2 2 2 2 3 3 3 3 1 2 1 3 1 3 3 2 1 1 2 2 3 2 3|
|1 2 1 3 3 1 2 3 1 2 3 3 1 1 2 2 2 1 2 2 3 3 1 2 3 3 1|
|2 2 1 2 1 2 2 2 2 2 1 3 3 1 1 3 3 1 1 1 1 3 3 3 2 3 3|
------------------------------------------------------

Method of Encipherment

Encipherment follows the same general pattern as the
Bifid. the plaintext is divided into groups of a chosen
periodic length and the numerical components are written
vertically below each letter. Periods of multiples of
3+1 are popular such 7 -10- 13 , with 10 being the most
popular. For example, with period = 10:

Plain     C O M E Q U I C K L|Y I N E E D H E L P
-------------------|-------------------
1 1 1.2 1 1.3 1 3.3|3 3 2.2 2 1.2 2 3.3
1 2.1 3 2.3 1 1.3 3|3 1.1 3 3.3 3 3.3 2
1.1 3 1.3 1 2.1 1 3|2.2 1 1.1 2 2.1 3 3
---------------------------------------
Cipher    C N # I D R K U I M|Y T X K V L J N B V

The first letter C is represented by vertical 111; plain
O by 121; M by 113; etc.

The first cipher letter C is derived by the horizontal
take off 111. The dot represents the break between
trigraphic units. Note that the C is derived from the
1st three components from COM. The fourth cipher letter
I derives from the first component of the tenth letter L
and the 2nd 2 components of CO. We go to the end of the
row and back to the first letter on the second row, to
the end and drop down to the third row first letter.

Decipherment

The decipherment process reverses that of encipherment,
in that the numerical components of the cipher letters
are written horizontally in three rows of periodic
length and are then read vertically to produce the
plaintext.
Identification of the Trifid

1. It is a substitution (fractionated) cipher with 27
letters.

2. If long repeats occur, they will be at irregular
intervals.

3. Repeated patterns will occur:

for period 10:

6 letters    A D . . C . . B . .
5 letters    A . . . C . . B . .
4 letters    A . . . . . . B . .

Peculiarities of the Trifid

1. Naturals, similar to those of the Bifid, are
extremely rare.

2. Each plaintext letter can be represented by 729 (**3)
different arrangements of fractions of itself and
other letters.

3. The table of numerical components is inflexible. Any
given digit - 1 - 2 -3 must appear 1st, 2nd, and 3rd
component for nine letters - no more, no less.

4. Not more than three letters can have the same two
components identical; and for these three letters the
other component must be a different figure in each
case.  This is a good rule for cryptanalysis.

5. Repeated plaintext sequences produce patterns that
are recognizable. Bower devotes a substantial chapter
to this rule. [BOWE]   The surest way to determine
the period is through repeat patterns.

6. Repeated cipher patterns do not always represent the
same plaintext letters. The period is key.

SOLUTION OF A TRIFID WHEN PLAINTEXT WORDS ARE GIVEN

Solution of a Trifid cipher requires that the individual
trio of numerical components having the correct
arrangement of the components must be determined for
each letter of the alphabet.  Sacco advises that a
probable word is essential. [SACC]

Given: Trifid, "The first" starts message and repeats at
RQOTUILR.

HRNGQ  SSXDI  TSIZB  BZBZB  TUPRE  IMQYS
BJPKV  RQOTU  ILRSI  MKZBI  RUXPS  OGWQQ
FMKIC  ISXOY  BSFVP  HGHLZ  AOQEU  CRMNJ
BZBVO  LCUJB  AZBGL  FVUDH  AMYHK  VMRGZ
BRTID  XUJQN  IZBIL  CUFSF  FHDJZ  BHSCM
KECEF  QOMKY  PNSSV  GHFSB  BBOUJ  SQAXX
DWJMU  ZBBTX  HHRHV  ZAZBB  PTEGY  NHZBI
BRWNO  VODZA  TAJVL  KKIVZ  A.

The triple repetition of ZB, in groups of three and
four. So set ZB = # and ZA = Z.  We place the tip and
repeat.

HRNGQ  SSXDI  TSI#  B##  TUPRE  IMQYS  BJPKV
thefi  rst

KVRQO  TUILR  SIMK#  IRUXP  SOGWQ
the  first

We see a 6 letter repeat in period 10:

Letter 12:  S I # B # # T U P
Letter 41:  S I M K # I R U X
* *     *     *

We accept the period as 10 and set up the message as
such.

An accepted method of setting-up a Trifid for solution
is to write the cipher message on quadrille paper
leaving a minimum of five blank rows between the lines
of letters. These are written horizontally in continuous
order, limiting the number of letters in each row to a
multiple of the periodic length.

HRNGQSSXDI    TSI#B##TUP    REIMQYSBJP
----------    ----------    ----------
----------    ----------    ----------
----------    ----------    ----------
thefirst
----------    ----------    ----------
KVRQOTUILR    SIMK#IRUXP    SOGWQQFMKI
----------    ----------    ----------
----------    ----------    ----------
----------    ----------    ----------
thefirst
----------    ----------    ----------

We now fractionate the letters that we know to be
present and then set-up chains of equivalents. Like
Bifid, having two separate alphabets to contend with,
the Trifid has three separate alphabets to recovery
piece by piece. We must tabulate our known values.

The fractionated plaintext letters are to be vertically
aligned and the fractionated cipher letters must be in
horizontal alignment.

T1 H1 E1 F1 I1 R1 S1 T1 .  .
T2 H2 E2 F2 I2 R2 S2 T2 .  .
T3 H3 E3 F3 I3 R3 S3 T3 .  .

H1 H2 H3 R1 R2 R3 N1 N2 .  .
G2 G3 Q1 Q2 Q3 S1 S2 S3 .  .
S3 X1 X2 X3 D1 D2 D3 I1 .  .

.  .  K3 V1 V2 V3 R1 R2 R3 Q1
.  .  O1 O2 O3 T1 T2 T3 U1 U2
.  .  I2 I3 L1 L2 L3 R1 R2 R3

Set       Chain of Equivalents

(a)       T1 H1 K3 N2 Q1 Q2 F2 E2 O3 H2 V1 G3 O2

(b)       T2 G2 O1 S3 U2 Q3 I2 T3 I1 R3 R2 R1 D2 S1 D3
N1 F1 V3

(c)       H3 X1 I3 E1 V2 D1 L3

(d)       E3 X2 L1

(e)       F3 X3 L2

(f)       S2 U1

All the above fractions are equivalent to each other.
There are six separate sets of equivalents, which means
three are duplicates and equal to each other. Set (a)
and (b) are not equal. The latter contains R1 R2 R3 and
Q3 ; while (a) contains Q2 Q3.  If both sets were equal
to each other they would violate the rule governing the
same identical numerical components, an impossible
condition.  We can give both sets numerical values of 1
and 2 arbitrarily, then check the assignment as we fill
in the holes.

Enciphering Table

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z #
------------------------------------------------------
2   1 2         2 2   1 2 2 1   1
2 1 1 2 1 2         1 1   1 2   2 2
2     1       1       1   2 2 2 2   2
------------------------------------------------------

Having established a few values, set (c)  cannot have
the value 1 because rule 4 for E1 and V1. Also it cannot
have the value 2 because of a conflict with the letter D
=222 which is already in use by T.

We set (c) with a value of 3 and add the fractions to
our table.

Enciphering Table

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z #
------------------------------------------------------
3 3 2   1 2         2 2   1 2 2 1 3 1   3
2 1 1 2 1 2         1 1   1 2 3 2 2 3
2     1 3 3   1 3     1   2 2 2 2   2
------------------------------------------------------

Further determinations are possible:

O = 211 , F is 212 or 213
N is 212 or 213

Rule 4 prevents S2 to be 1 since FNO are 21.

S2 cannot be 2 because it conflicts with R ; S2 =3.

So the (f) takes on the value 3 and U1 = 3; F3 = 2 or 3;
D = 322 implies that U3 = 1 or 3. We set a decipher
table with known and derived values. Letters are added
externally.

Deciphering Table

Q H   T     V   O       R I   S           D
-----------------------------------------------------
|1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3|
|1 1 1 2 2 2 3 3 3 1 1 1 2 2 2 3 3 3 1 1 1 2 2 2 3 3 3|
|1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3|
------------------------------------------------------
?      G             F F G           E E E G
N N                   U   U

We substitute know values in the message and recover
more plain text.

Group 12 and 13 gives us the word RIVERS, which yields
some new values.

L = 123        E = 311
F = 212        U = 323
N = 213        X = 3?2

Deciphering Table

Q H   T L   V   O F N   R I   S   E       D U
-----------------------------------------------------
|1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3|
|1 1 1 2 2 2 3 3 3 1 1 1 2 2 2 3 3 3 1 1 1 2 2 2 3 3 3|
|1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3|
------------------------------------------------------
?      G                 G             X   G       X

Enciphering Table

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z #
------------------------------------------------------
3 3 2   1 2     1   2 2   1 2 2 1 3 1   3
2 1 1 2 1 2     2   1 1   1 2 3 2 2 3
2 1 2 1 3 3   1 3   3 1   2 2 2 2 3 2   2
------------------------------------------------------

We next look for the trigram THE.  We hit a possible
bonanza with groups 6,7, 9,11, 14, 17, 19, 21:

We are looking for the  1 1 3   components.
2 1 1
2 3 1
-----
t h e

Group 7 tends to be the clincher with the words THE
DIFFERENCE.  We accept new values of B=131, C=332, P=
3??, Y=121 and W=1??.  The word BETWEEN is logical for
group 8. When placed we find G=321, P=313, W=133, Z=111.
Only a few letter components are unknown and they fall
when the known values are placed in the quadrille.

Deciphering Table

Z Q H Y T L B V W O F N # R I K S J E X P G D U M C A
-----------------------------------------------------
|1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3|
|1 1 1 2 2 2 3 3 3 1 1 1 2 2 2 3 3 3 1 1 1 2 2 2 3 3 3|
|1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3|
------------------------------------------------------
?      G                 G             X   G       X

Enciphering Table

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z #
------------------------------------------------------
3 1 3 3 3 2 3 1 2 2 2 1 3 2 2 3 1 2 2 1 3 1 1 3 1 1 2
3 3 3 2 1 1 2 1 2 3 3 2 3 1 1 1 1 2 3 2 2 3 3 1 2 1 2
3 1 2 2 1 2 1 3 3 3 1 3 1 3 1 3 2 2 2 2 3 2 3 2 1 1 1
------------------------------------------------------

The first part of our message in detail reads:

HRNGQSSXDI    TSI#B##TUP    REIMQYSBJP
1132222133    1222322232    2223112233
2111223223    2113122122    3111212123
2312322223    1122323313    2131233313
thefirstda    yofspringi    sonethinga

The first day of spring is one thing and the first
spring day is another. The difference between them is
sometimes as great as a month period. It is with rivers
as it is with people, the greatest are not always the
most agreeable nor the best to live with. Henry Van
Dyke.

Keyword Recovery

A little inspection of the letters reveals that the take
off method is reverse and decimates as follows:

A C M U D G P X E J S K I R # N F O W V B L T Y H Q Z

we see:

V -- W -- X -- Z

-DV -FW - GX -HZ - I#

F    G           B C       H I
O    P    and    L M  and  Q R
W    X           T U       Z #

which yields:

V A N D Y K
B C F G H I
L M O P Q R
T U W X Z #

and finally;

6 1 5 2 7 4 3
V A N D Y K E
B C F G H I J
L M O P Q R S
T U W X Z #

So we have just a small glimpse at the Trifid. Read Linz
and Bowers for a significantly better picture of this
cipher. There are whole issues surrounding period, part-
naturals, patterns and tetragraphic equivalents. [LEDG],
[BOWE]. The Resources section has many ACA articles
regarding the Trifid. Lastly, the reprints of three of
Delastelle's books are the most interesting (in French)
pertaining to the Trifid. Delastelle did not consider
the 27th letter an issue. (Maybe in French it was not.)
[DELA], [DEL1], [DEL2]

1. Complete columnar transposition.

WKAII  GLFGA  TEYHN  ONSOH  LGIRI  IAAIR  LGAMO
IMHSF  IDFGW  NNEYH  NEFNH  SLNSE  THS.  (63)

ANS: ENGRAVE; A MAN WHO THINKS HE'S  REALLY FLYING
HIGH IS IN DANGER OF MELTING OFF HIS WINGS.

2. Nihilist transposition.

UCTEO  UAMAA  LTDMI  SUDDS  SISNU  OLNNH  AALTA
EYELB  NEANU  NRAPH  SNENX  ESTAE  ASJH.
ANS: 16384257;  UNUSUAL PUNISHMENT ..

3. Incomplete columnar

IENOR  RENHR  NAITI  ETTEC  FCOIP  TREYA  RCHTH
SPOAL  YONCW  SNARL  TEESN  TOYEL  ERSOL  UAIOE
VEPOR  LNRTS  HIMIM E. (relatively)

ANS: 64287153; SHALL I CONTINUE WITH ..

4. Myszkowski.  Battlefield.

YIITU  HSATS  OIRLF  TSTFD  NCUAW  WGSUS  NYATO
EBEHR  GIPNP  OUSOM  ELEPO  YOONR  AYOIO  URTES

ANS: APPETITE ; ....

5. Amsco.

HENTI  DAHOS  CLOSN  PRNSA  FENTT  TIOAM  LROTE RTLEI
ANCSC  RCISO  EMGRI  YOUIT  EMTAC  AIAME ILIVI SPAEW
AMIFA. (propaganda)

ANS: 4162375; MOST VIOLENT ANTISEMITE..

6. Tramp.

CGHES  NOONE  NAETT  SHTIA  NEQCB  AWRSI  LTAOH
OAUEY  OCENA  TOMRT  HAEFO  ROEAU  PLNSD  STHIG.
(QCTCLYAPMQQ)

ANS: CAN YOU PLACE EIGHT QUEENS .

IRHRC  GRETR  ESDEE  OFOWN  ETLNS  EOTIG  IMNEI
TSONH  LTIID  DVLTS  NIADS  LSRAM  TSORU  HSCNE
DNIHU  EAGCD  IGIRS  WSLSH  BITNI  IHNNH  DNICD

ANS: ANDES; IN FLIGHT THE CONDOR

8. Railfence.

TOEYC  SOEFO  MSAHH  RMOYU  LDTAC  LATYA  LFLME
EBGOP  VIPRV  IEEVS  ALUDO  WTGIG  THILL  CONT.

ANS: TELEVISED FOOTBALL GAMES ..

9. Redefence. Astronomic improbability.
tip = THE MOON TO

REOEN  IOFGS  AITWE  UMTBA  PITNP  ACOUH  OTICN
SAGFP  TRLEE  HTREN  MROOH  LEORN  SIVSE  ONTAC
SRSEL TUERS  HDTRO  AGYAH  TRAON  LE.

ANS: 6 - RAILS; THERE ARE NO ATMOSPHERIC

10. Turning grille.

TIP = the most serious and; NQEJPGUU

STTAH  IRNED  GSERL  GEOGM  AETON  ENBIE  DOTNH
EAEOS  MSTFI  LSOCI  OEHST  SNIER  CNTEN  SHTEC
SOIOS  LHOAU  SUSIS  EANWA  TMNER  BOECD  OSKRC
MSILT  EONMB  TLAEA  CTNID  DIEKD  OFNMF  AXVEF
ESEU.

ANS: THE LEGEND OF LOCH NESS HAS

11. Swagman. Agreeable toil.

NNWTI  HYORS  TEKKR  IENII  VNLSN  LOTOO  SLAVT
RETSI  ROSIM  KSCFR  SEEAO  OMTAC  HETTI  IWEVO
RHEII N.

ANS: WORK IS NOT IRKSOME WHEN I ..

LECTURE 17 PROBLEMS

Paul Derthick's HEADLINE PUZZLE  . by Larry Gray

The following are all headlines from a recent daily
newspaper. Each of the five is a different mono -
alphabetic substitution, and all five are derived from
the same mixed alphabet at different settings against
itself.

1.  PXYWFXKLJE DFYMJYV VGHKJ `DFYM-US' GF ZYFGJVG
PJEJYHW VLXGEFDS;

2.  JUBHFGO EUHKEOF HR WEUDBGO, FHSJF DKD RO ZGI YRE
FUNROI HUED;

3.  NEZZY AEZYVKU AEVP NFUVLKY LR ALVVKU JLBPV ECKU
AWGBKV;

4.  ZEHCGOL LZCCOMMSS WEMSAQ MZALD AFB AZFMS MZ DZBZA
MDZAGS;

5.  PTQQU WQRKWCQBSD WQEKLLQUBX BZOKWEQ MKW ENJWSQX JUB
BZ

In case you'd like to confirm your solution of this
example, but not be influenced by seeing the answers
beforehand, the setting, key and hat are provided here
in a Caesar cipher, offset by 6.

Setting = GTURK    Key = MKIQU    Hat = INGSKRKUT

17-2  Playfair. While Rome Burns.  BARRISTER: ON44:CE17
Tip= "ers are"

OCMAF  ZDAPZ  BYPGY  BOKYT  BYVMT  AVIBY PVGPP  RBCFH
XEAPI  VTCPV  VBKGV  MEWCB  IEGMQ  PPBOL ENRHZ  MRFSC
DRNAI  ZEITN  SUNA.

TWO HINTS: The title is significant and does not follow
LANAKI's Red Herring rule and look for naturals such as
PO = QP or OPQ.  A Natural is a cipher digraph not in
the keyword whose letters because of the standard
alphabetical relationships stay in the natural
alphabetical order in the cipher square.

17-3   Foursquare   'anasonly'           ZEMBIE

UB XB MS SF SQ MS TH DE UB HM GL NL BW GB LW NQ NF UB FM
QH EM BW BI GT LD UQ IG WM CF TQ ET CT NF IP LS UQ FK UH
IZ UQ YF TN XP NS FF UV HV NF HI CE NQ UO UQ GK ET HT ND
PV BI BE ND BD YM DE LX UB GA CX ET XT DE PE NL BF PY IQ
NG QW IS NC CK XB TF GK ED LA EL LE RW MI EX SF MS UP XQ
NF EV FF BI KK NA MX.
17-4 Short Bifid. Clue - DIAMONDS is there somewhere and
the text talks about them being HIDDEN. Period = 7.

ETIALIG   LDMNITV   NFEMISI   EEIDGEI
HPCEDUT   PINOFLW   INDLEEK

SPECIAL NOTE RE: DIOPHANTINE EQUATIONS

For some time now, Dr. Michael Anshel of CCNY and I have been
following the development of crypto from some early roots.
Here are short excerpts from our correspondence.  Jump in if
you can help us:

==============================================================

>From Michael to LANAKI:

Wallis was involved in solving certain diophantine problems
particularly the Fermat-Pell equation, which in turn led to the
study on continued fractions, and ultimately to the study of
automatic sequences which are of interest to contemporary
cryptographers.  Were these very gifted 17th century
cryptographers aware of this possibility? - Michael Anshel.

===========================================================

To Michael from LANAKI:

In RE WALLIS:

"Arithimetica Infinitorium"  and Opera mathematica (Oxoniae,
1699), III 674,687,688,693 and 695 give solutions to
nomenclators based on pre-calculus theory.  Wallis' "Letter-
Book" gives some of his important papers (Smith op cit, p32,
p499)

Samuel Pepys Notes, Sir Christopher Wren's Discourses, Mr.
Robert Hookes' Diary, and Dr. William Holder's notes all praise
his mathematical ability and scholarly side but seem to put
Wallis as a "extremely greedy of glorie, steales feathers from
other to adorne his own cap."  They do not give us a clue as to
what Wallis might have in his hip pocket regarding diophantine
problems.

In RE DIOPHANTINE EQUATIONS:

I did find some interesting references on this subject in my
library.

>From the Seminaire de Theorie des Nombres, Paris 1980-81,
Marie-Jose Bertin, ed.:

1)  C. L. Stewart, "On some Diophantine Equations and Related
Linear Recurrence Sequences." Univ. of Waterloo,

2)  R. Tijdeman, "Exponential Diophantine Equations" Proc.
Intern. Congress Math., Helsinki (1978) p381-387.

3)  T. N Shorey et al., "Applications of the Gel'fond-Baker
method to Diophantine equations, Transcendence Theory;

plus 13 lesser references p321.ff.   and,

>From the Seminaire de Theorie des Nombres, Paris 1984-85,
Catherine Goldstein, ed.: Serge Lang {in FRENCH}:  "Varietes
Hyperboliques et Analyse Diophantienne,"  Univ of California,
Berkley, 1986.

4) Kobayashi et T. Ochiai, "Meromorphic mappings into compact
complex spaces of general type," Invent. Math. 31 (1975), 7-
16.

5)  S. Lang. - "Hyperbolic and Diophantine analysis,
aparaitre," Bull. AMS, 1986.

6)  D. Riebensehl, "Hyperbolische Komplex Raume und die
Vermutung von Mordell,"  Math Ann. 257, (1981), 99-110.

plus 19 ancillary references.

=========================================

Further To Michael after intervening letters:

DIOPHANTUS

Diophantus of Alexandria (ca. 250) wrote three works that
influenced greatly the later European number theorists.
"Arithmetica", (6 out of 13 extant), "On Polygonal Numbers",
(fragments survived), and "Porisms"  which was lost.
Translations of Arithmetica were made first by Xylander in 1575
[aka Dr.  Wilhelm Holtzman at the Univ. Heidelberg] and then by
Frenchman Bachet de Meziriac in 1621. A second carelessly
printed edition in 1670 became historically important because
it contained Fermat's famous marginal notes which stimulated
extensive number theory research.  Indeterminate algebraic
problems where one must find only the rational solutions were
named after him.  Modern usage implies the restriction to
integers.  Diophantus did not originate problems of this sort
but did originate the algebraic notation in the form of
stenographic abbreviations.

FERMAT

Fermat (1601 -1665), of his varied contributions to
mathematics, the most outstanding is the founding of the modern
theory of numbers.  He possessed nothing less than
extraordinary intuition.  Many of his contributions appear as
marginal notes in Bachet's translation, including his last
theorem that n>2 there do not exist positive integers x,y,z
such that x**n +y**n = z**n.  Fermat's famous "little theorem"
regarding primes was dictated to Frenicle de Bessey, dated Oct.
18, 1640. It was not proved until 1736 by Euler. By 1770,
Fermats theorems on prime numbers were proved by Euler and
Lagrange.

Gauss conjectured the prime number theorem (distribution of
primes) from both Fermat and Eulers work.  J.  H Rabin in 1659
published extensive factor tables for numbers up to 24,000 and
in 1668 John Pell of England extended the table up to 100,000.

WALLIS

Wallis (1616-1703) was Newtons predecessor.  His work with
conics in "Arithmetica Infinatorum" was hailed for more than a
century.  His "De algebra tractatus, historicus & practicus",
written in 1673 and published in 1685 was a serious attempt at
the history of mathematics in England.  Wallis edited parts of
famous Greek mathematicians works for the Royal Society - one
of which was our friend Diophantus.  His contributions to the
theory of integration are historic.

BARROW

Isaac Barrow ( 1630 - 1677) used Wallis' work to develop the
theory of differentiation.  He published his work in "Lectiones
Opticae et geometricae."  Wallis was a reviewer.

Newton (1642 - 1727) read Euclid's "Elements", Descartes' "La
Geometrie", Oughtred's "Clavis", works by Kepler and Viete and
the famous "Arithmetica infinitorum" by our boy Wallis.   From
his "Principia" has come much of our modern day math and
physics.

ROSSIGNOL

Rossignol (1600 -1682) may have been familiar with Rene
Descarte's ( 1596 - 1650) work on geometry and knew Pascal
(1623 - 1662) from court and was aware of Pascal's letter to
Fermat suggesting a solution to a problem proposed by Chevalier
de Mere regarding the theory behind gambling.  The
correspondence between Pascal and Fermat regarding the "problem
of points" laid the foundations of the science of probability.
Rossignol used this theory for his cryptographic finds.
Remember though it was the legendary William Friedman who did
the pioneering work in the statistical side of crypto in the
1930's.

CONCLUSION

This historical tour leads me to believe that Wallis was aware
of the preliminary implications of diophantine problems and
that Rossignol was aware of the potential of probability in
terms of cryptographic solutions.   Could they have seen beyond
the Fermat - Pell's work is difficult to prove.

REFERENCES

1) Meschkowski, H., "Ways of Thought of Great Mathematicians,
tr by John Dyer-Bennet. San Francisco: Holden-Day 1948.

2) Ore, Oystein, Number Theory and Its History, New York:
McGraw-Hill, 1948.

3) Pollard, H. The Theory of Algebraic Numbers, Carus
Mathematical Mono., No. 9, New York: John Wiley, 1950.

4) Turnbull, H. W., The Great Mathematicians, New York: NYU
Press, 1961.

5) Bell, E. T., Men of Mathematics, New York: Simon and
Schuster, 1937.

6) David, F. Games, Gods and Gambling, New York: Haftner,
1962.

7) MacFarlane, A. Lectures on Ten British Mathematicians of
the Nineteen Century, Math. Mono. No 17, New York: John
Wiley, 1916.

8) Eve's H, Introduction to the History of Mathematics, 4th
ed., New York: Holt, Rinehart and Winston, 1964.

============================================================

>From Michael to LANAKI
Subj:  Diophantine revisited

There are several more threads in this search.  What needs to
be done is to trace back from contemporary (20th) century
researchers to see what lines of work emerged.  Lets see what
can be found regarding D. E. Littlewood the prominent British
mathematician and associate of G. H. Hardy and S. Ramanujan.
The nineteenth century had Charles Babbage.  The Willes family
was prominent over several centuries but I do not know if
Andrew Wiles is in this family tree.  Tracing the men (women)
and their methods around the Cambridge-Oxford researchers
should reveal new information.  Are their ACA members in
England who could help? - Michael

===============================================================

BINO, FOOT, G4EGG and  THE DOC were suggested as possible