|
ICSA Guide to Cryptography Randall Nichols $69.95 0-07-913759-8 |
|
| Chapter: 1 | 2 | 3 | 4 | 5 | 6 | 7 | 9 | 10 |
| Reserve your copy at a Beta Bookstore near you! |
Contact Bet@books © 1998 The McGraw-Hill Companies, Inc. All rights reserved. Any use of this Beta Book is subject to the rules stated in the Terms of Use. |
Zen Crypto
For the first few chapters, we have chosen not to indulge in any of the rigorous mathematics of cryptography. Everything to be presented can be reduced to mathematical models and computerized for ease of work.
BUT those who embark on a course of 'only the computer' do this without knowing the real effort - the brain power - the shortcuts - the tradecraft - the historical implications; in our opinion, they have lost the real heart of cryptography. The "ah-ha's" of inspiration are what make the difference. The hours of writing/testing, the sleepless nights, the rush we feel when the letters fall in place, these are the delights of real cryptographers.
There are several problems with the "computer only" solution. First, there is a fundamental problem in that computer models do not apply to all variant cases.
Simple changes to the system can fool even the most adept computer program. For example, placing clever nulls (arbitrary letters, having no meaning inserted into the plain text to complete a geometric pattern or to confuse or confound the cryptanalyst) will defeat many a statistical based model.
Second, we lose the sense of urgency that was required for wartime cryptography.
If John F. Kennedy's Playfair (a form of simple substitution cipher using pairs of letters) message [that's right, it was not English and was not plain text, as in the movie "PT-109"] on the back of a coconut had been intercepted and deciphered by the Japanese [which they were very capable of doing], we might not have had the graceful light of his Presidency or, who knows, the moon landings. As another case in point, the solution of ENIGMA during the mid-final Atlantic Campaigns of World War II reduced the operational effectiveness of the U-boat to one day and hence saved allied tonnage and warships supplying Europe. The American and British cryptographers thought like their German counterparts and so could develop clues that enabled them to gain access into the cryptosystems. Because of the types of computers available during World War II, computer solutions were bulky, machine dependent and not reliable until 1945. People made the difference. They always will.
A very brilliant engineer died recently. His name was Seymour Cray. In his lifetime, he did more for the advancement of computers than many could imagine. Ask CDC. Ask General Motors. Ask NSA. His life was a bit quirky and secluded.
He thought about super-cooling systems, Josephson Junctions, parallel processing, distributed work loads, optical computing, laser-sound interaction, super-charged transfer devices, and computing machines capable of one quadrillion operations per second. When you brought him down from high altitude, he advocated that one must understand the problem, its growth, its effects and its conscience before you apply the computer to bring forth a 'better' solution.
Simple Route Transpositions (TRAMPS)
Transposition ciphers have been defined as that type of cipher in which the elements or units of the plain text; whether one is dealing with individual letters or groups of letters, retain their original identities but undergo some change in their relative positions or sequences so that the message becomes unintelligible. The majority of transposition methods involve the use of a design or geometric figure, such as a square, rectangle, triangle, trapezoid, etc., in which the letters of the plain text are first inscribed or written into the design according to a previously agreed upon direction of writing and then transcribed or taken off according to another and different previously agreed-upon direction, to form the text of the cryptogram.
In their simplest form, TRAMPS may take any of the following routes when employing rectangles or squares for transposing text of a message as illustrated below. The plain-text message is assumed to be merely the normal sequence from A to X, for ease in following the route.
Any geometrical form can be used, but it must be full block; if the letters of a message do not complete the assigned block, nulls (arbitrary letters) must be added.
Example 1 - Let the message be (military text):
At fourteen hundred sighted submarine bearing two three five degrees true. (63 letters)
Suppose we agree to use a completely filled square of eight rows by eight columns, then we add 1 null to give us a multiple of eight (64 letters). We agree that alternate diagonals will be used for inscription.
1 2 3 4 5 6 7 8
1 A T R T R E M A
2 F U E D D B R O
3 O E N S U I W T
4 N U I S N T H E
5 H G D E G R DG
6 H E B N E E R R
7 T E I E V E T U
8 A R F I E S E N
Next the letters are taken off by simple vertical to form the cryptogram:
AFONH HTATU EUGEE RRENI DBIFT DSSEN
EIRDU NGEVE EBITR EESMR WHDRT EAOTE GRUN
To decipher the cryptogram, the process is reversed. The total number of letters in the cipher text is used to reconstruct the rectangle. Then the cryptogram is inscribed by the agreed upon route and the plain text is taken off by the other agreed upon route. It should be noted that legitimate correspondents know the system and the key(s). The cryptanalyst would break into this type of system by searching for common trigraphs (the, and,) and common digraphs (er, th,)
and the columns until reasonable plain text appeared in each row.
Transposition ciphers come in several simple varieties. The oldest form may be reversed writing. The reversing process may be applied to regular or irregular groups of plain text letters:
Let the plain text be: Bridge destroyed at eleven PM.
Words Reversed:
E G D I R B D E Y O R T S E D T A N E V E L E M P
Words Reversed and Regrouped into False Lengths:
E G D I R B D E Y O R T S E D T A N E V E L E M P
Text Reversed and Regrouped into Five’s:
MPNEV ELETA DEYOR TSEDE GDIRB
Text Reversed and Regrouped into Five’s With Nulls every Fifth Position:
TRIMM PNEVP ELETA ADEYR ORTSL EDEGU DIRBM
Rail Fence Cipher
Just as the name implies, the Rail Fence Cipher resembles an old rail fence found in many parts of New England today; with its zigzag appearance.
Plain: Prepare to get underway.
P E A E O E U D R A
R P R T G T N E W Y
Ciphertext is taken off horizontally:
PEAEO EUDRA RPRTG TNEWY
It may be composed of any number of rails (or letters in depth) which may be written up or down, coming from a point and then reversing the direction to the end of the message, either filling the final stroke or being short a letter or more.
Any message may be written in with the normal sequence up and down, or visa versa, or it may be written into the points first, and then into successive horizontal rows. It is then taken out by the alternate process.
Example:
TAOET NMFOA TNEHM NHWKS POIDI SLFMU HSOBE ALEEW AUFHE ASNES P. (51 letters)
Any figure can be used for cipher transposition, including stars, polygons and irregulars. It is merely necessary to agree on the figure and the starting points for inscription and transcription processes.
Civil War Messages
David Kahn, author of The Codebreakers, gives us an interesting look at Civil War Cryptography. One of the reasons that the North won was it practiced superior cryptography. Anson Stager first superintendent of the Western Union Telegraph Company, was charged by Major General George B. McClellan with drawing up a military cipher along the lines that Stager had devised for Governor Dennison
of Ohio.
Stager complied. Soon McClellan was relying on the cipher to protect his communications during his successful campaign in West Virginia. One of the first users was Allan Pinkerton, founder of the agency that bears his name and bodyguard to President Lincoln. The key was very short; it was dependable and was used by the Union forces throughout the Civil War. It was used extensively because the Civil War first employed the telegraph on a large scale.
Communications from Washington could take 10 days to their troops depending on weather, health of the telegrapher operators and availability of lines (which sometimes took a circuitous route). During Sherman's march to the sea, the Union had to rely on Southern newspapers for accounts of his slash and burn campaign.
So effective was the Stager cipher that those same Southern newspapers advertised for help from anyone who recognized or could break the Yankee cipher.
Stager's cipher was a word transposition. Stager's telegraphic experience evidently led him to a system in which the ciphertext consisted - as in the new telegraph codes - of ordinary words, which are far less subject to dangerous garbles than groups of incoherent letters. There is a funny story how one of the Rebel commanders could not read the cipher message sent to him by one of his forward patrols - prior to Gettysburg no less - so he sent a messenger to the forward post to get a clarification of the cryptogram received. The messenger returned to find his commander under arrest. The message was a warning of a Union trap. The lines were effected by rain that particular day.
The Stager cipher was appealing because of its simplicity: the plaintext was written out in lines and transcribed by columns, up some and down others in a specified order. His cipher was improved by adding nulls mazed routes of diagonals and interrupted columns through larger rectangles and per Samuel H. Beckwith, Grants cipher operator, important terms were represented by codewords, which were carefully chosen to minimize telegraph error. The cipher expanded from one listed on a single card to one that by the, end of the war, required 12 pages to list routes and 36 pages for the 1,608 codewords. This was Cipher 4, the last of a series of 12 that the North employed at various times during the war.
A good example of the system is given by encipherment of the message by
President Lincoln on 1 June 1863:
"For Colonel Ludlow. Richardson and Brown, correspondents of the Tribune, captured at Vicksburg, are detained in Richmond. Please ascertain why they are detained and get them off if you can. The President."
Cipher No 9 was in use and provided for the following codeword substitutions:
VENUS for colonel, WAYLAND for captured ODOR for Vicksburg, NEPTUNE for Richmond, ADAM for President of U.S. and NELLY for 4:30 PM time of dispatch. The keyword of GUARD set the size of the rectangle and routes. Nulls were added to the end of each column.
The encipherer chose to write out the message in seven lines of five words each with three nulls to complete the rectangle. The plaintext was:
For VENUS Ludlow Richardson and
Brown correspondents of the Tribune
WAYLAND at ODOR are detained
At NEPTUNE please ascertain why
they are detained and get
them off if you can
ADAM NELLY THIS FILLS UP
Ciphertext: [up the first column,(kissing=null),down second,(turning=null),up fifth,(times=null),down fourth, (belly=null), up third column]
GUARD ADAM THEM THEY AT WAYLAND BROWN FOR KISSING VENUS CORRESPONDENTS AT NEPTUNE ARE OFF NELLY TURNING UP CAN GET WHY DETAINED TRIBUNE AND TIMES RICHARDSON THE ARE ASCERTAIN AND YOU FILLS BELLY THIS IF DETAINED PLEASE ODOR OF LUDLOW COMMISSIONER.
Confederate cryptography centered on the Vigenere polyalphabetic cipher. The south employed only three keywords: MANCHESTER BLUFF, COMPLETE VICTORY and COME RETRIBUTION. Known also as the Vicksburg cipher
the team of Tinker, Chandler and Bates, very early yuppies, were able to read a whopping 90% of the Confederates messages and report them to Lincoln.
For example, Grant's troops intercepted a message on eight captured rebels at Vicksburg trying to slip into Vicksburg with 200,000 percussion caps.
The ciphertext message read:
Jackson, May 25, 1863
Lieutenant General Pemberton: My XAFV. USLX WAS VVUFLSJP by the BRCYAJ. 200000 VEGT. SUAJ. NERP. ZIFM. It will be GFOECSZOD as they NTYMNX. Bragg MJTPHINZG a QRCMKBSE. When it DDZGJX. I will YOIG. AS. QHY. NITWM do you YTIAM the IIKM. VFVEY. How and where is the JSQMLGUGSFTVE. HBFY is your ROEEL.
J. E. Johnston.
Note the flow of the message and hints along the way. The word separators, the clear text leads you into the next word. The size of the words is known and might be guessed.
The Plaintext based on the Keywords MANCHESTER BLUFF is:
Lieutenant General Pemberton: My last note was captured by the picket. 200000 caps have been sent. It will be increased as they arrive. Bragg is sending a division. When it joins I will come to you. Which do you think the best route? How and where is the enemy encamped? What is your force?
J. E. Johnston.
AMSCO
The AMSCO Cipher is another type of incomplete columnar transposition. Its column-letters are not limited to a column of single letters, but rather alternating single, double, single, double throughout the plain text length. A numerical key is employed. For example:
3 1 4 2 5 2 4 6 1 5 3
TH E WE A RI T HE W EA R IN
N GO F DE C GO F DE C OR A
OR A TI V EM T IV E ME D AL
E DA L SW A SW A SC O MM O
SC O MM O NI N IN E NG L AN
N EN G LA N DD U RI N GT H
DD U RI N GT E RE I GN O FH
H ER E IG N EN R YT H EE I
OF H EN R YT G HT H
H EE I GH T
HX
(A) (B)
In matrix (A) the alternating pattern of 2-1-2-1 follows from one end of one line to the next line but in matrix (B) it is possible to have two 1's or two 2's in the continuation from one line to the next. This is a peculiarity of this cipher. Use of a probable word is important for this cipher. Columns are extracted in numerical order.
Polyalphabetic Substitution
A cipher system, which employs two or more cipher alphabets and includes a method for designating which cipher alphabet is to be used for the encipherment of each plain-text letter, is called a polyalphabetic substitution system. What is amazing about these systems is how long they remained secure. The Vigenere system was considered unbreakable for over 200 years. Along comes Major Kasiski, and poof, we have recreational cryptography.
Cipher systems employing variant values may appear to use more than one alphabet, but they have characteristics of monoalphabetic substitution and are properly classified as such.
Polyalphabetic substitution systems consist of two general types: periodic and non-periodic.
(a) In the periodic type the text of a message is divided into definite, regular groups or cycles of letters which are enciphered with identical portions of the key. Periodic systems are further subdivided as follows:
(b) In the non-periodic type there are no cyclic repetitions of the key.
The cipher alphabets employed in multiple alphabet substitution systems may be constructed by any number of methods.
Example:
Plain 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
Cipher 1 R T U V W X Y Z P E N C I L S A B D F G H J K M O Q
2 E N C I L S A B D F G H J K M O Q R T U V W X Y Z P
3 D F G H J K M O Q R T U V W X Y Z P E N C I L S A B
Here the plain component is a normal sequence and the cipher component is identical keyword sequences. The same keyword sequences may be used in both the plain cipher components, or different sequences may be used. The key, which determines the setting of the cipher alphabets against the plain component (RED), may be any prearranged word or phrase. Also, each cipher alphabet may be assigned a number and the alphabets used in accordance with a prearranged numerical key.
The process of enciphering a message with the multiple alphabet system above would appear as follows:
Cipher Alphabet No.
1- 2-3-1- 2-3- 1-2-3-1-2-3- 1-2-3-1- 2-3-1 -2- 3-1- 2- 3
Plain - M Y C O U R S E Z E R O T H R E E Z E R O A T T
Cipher - I Z G S V P F L B W R X G B P W L B W R X R U N
1-2-3-1-2-3-1-2-3-1-2-3-1-2-3-1-2- 3
Plain - H I R T E E N T H I R T Y T H R E E
Cipher - Z D P G L J L U O P R N O U O D L J
In order to reduce the chances of encipherment by the wrong alphabet, the plain text is often written so that the letters designated by the key for encipherment by each alphabet are placed in the same vertical column and each entire column is enciphered in turn.
Solving A Periodic Polyalphabetic Cipher
There are three fundamental steps to solve a Periodic cipher.
Principles of Factoring
Major Friedrich W. Kasiski (1805-1881) was a career officer in East Prussia's 33 Infantry Regiment. He is credited with a revolutionary insight regarding polyalphabetic repeating key systems - that the conjuction of a repeated portion of the key with the repetition in the plain text produces a repetition in the cipher text. Like causes produce like effects. The interval between plain text or cipher text repetitions is noted throughout the cryptogram, factored and the commonality of the factor is a good indication of the key and number of alphabets used to encipher the original methods. The fall of the Vigenere family of ciphers is attributed to Kasiski's examination.
If there are several long repetitions in the cipher text of an unknown system, the intervals between the initial letters of this repetition have a common factor, this factor represents the number of alphabets used to encipher the message and the exact number of repetitions of the key.
A simple example: Given the cryptogram:
IZGSV PFLBW RXGBP WLBWR XRUNZ
DPGLJ LUOPR NOUOD LJ
Factoring:
Repetition Interval Factors Common Factor(s)
LBWRX 9 3,3 3
LJ 12 2,2,3 3
UO 6 2,3 3
The "period" or common factor is three and this is the number of alphabets employed.
Digraph and trigraph repetitions may be the result of chance instead of plain text repetitions.
When factoring results in more than one common factor we shall use the highest common factor and check with frequencies of the expected alphabets to see how close to normal they are. Only short messages fail to lead to the correct determination of the number of cipher alphabets employed in the system. When factoring fails on a longer message, an aperiodic cipher may have been employed.
The Long and Short of Kasiski
Step one is finding the period. There are at least two ways to find the period. The short approach makes use of the distances between patent cipher text repetitions and factors the differentials. The long approach is used when there are no patent repetitions to factor. In this case we set up a possibility matrix and factor every combination looking for the highest probable common factor. Both methods are attributed to Kasiski. As an example of the first case take:
10 20 30 40
BGZEY DKFWK BZVRM LUNYB QNUKA YCRYB GWMKC DDTSP
50 60 70 80
OFIAK OWWHM RFBLJ JQFRM PNIQA VQCUP IFLAZ HKATJ
90 100 110 120
UVVQE EKESZ DUDWE KKESL IZQAT SBYUZ UUVAZ IXYEZ
130 140
JFTAJ EMRAS QKZSQ FOPHM W.
We tabulate the repetitions and the cipher text letter differences between repetitions.
Delta Factors
BG 29 -
RM 45 3,5,9
KA 53 -
MR 77 7,11
QA 39 3,13
VQ 17 -
AZ 40 4,5,8,10
AT 26 13
UV 31 -
EK 9 3,9
KES 10 5,10 *
SQ 4 4
Trigraph KES is more important than QA or AT digraphs. This suggests that the period is either 5 or 10. The larger number is usually the proper guess. But suppose there are no repeats or those that do exist do not establish a period. What then?
Given:
10 20 30 40
RNQJH AUKGV WGIVO BBSEJ CRYUS FMQLP OFTLC MRHKB
50 60 70 80
BUTNA WXZQS NFWLM OHYOF VMKTV HKVPK KSWEI TGSRB
90 100 110 120
LNAGJ BFLAM EAEJW WVGZG SVLBK IXHGT JKYUC HLKTU
MWWK.
We set up the following vertical tally. We note the actual position of every letter.
A 6 45 83 89 92 115
B 16 17 40 41 80 86 104
C 21 35
D ---
E 19 74 91 93
F 26 32 52 60 87
G 9 12 77 84 98 100 109
H 5 38 57 66 108 116
I 13 75 106
J 4 20 85 94 111
K 8 39 63 67 70 71 105 112 118 124
L 29 34 54 81 88 103 117
M 27 36 55 62 90 121
N 2 44 51 82
O 15 31 56 59
P 30 69
Q 3 28 49
R 1 22 37 79
S 18 25 50 72 78 101
T 33 43 64 76 110 119
U 7 24 42 114 120
V 10 14 61 65 68 97 102
W 11 46 53 73 95 96 122 123
X 107
Y 23 47 58 113
Z 48 99
Now we take each and every difference in each case. For example, A45-6, 83-6,89-6,92-6,115-6; and 83- 45,89-45,92-45,115-45; and 89-83,92-83,115-83; and 92- 89,115-89, and 115-92. Then we factor these differences, setting up a matrix (Table 4-1) of potential periods from 3 -12 inclusive and total the tabulations for each factor in each of the letters of the alphabet. The highest column total represents the period. This number is correct more than 98 per cent of the time.
Table 4-1
3 4 5 6 7 8 9 10 11 12
--------------------------------------
S ( A,…,Z) 87 61 47 43 57 30 35 21 25 16
Column Totals X Period
----------------------
87 x 3 = 261
61 x 4 = 244
47 x 5 = 235
43 x 6 = 258
57 x 7 = 399 ***
30 x 8 = 240
35 x 9 = 315
21 x 10 = 210
25 x 11 = 275
16 x 12 = 192
The period is 7.
Viggy’s Family
The Vigenere Family is a group of ciphers related to each other by the polyalphabetic system used for encipherment. These ciphers were invented at
different times by different authors, sometimes with confusion of authorship, and in different countries. They are similar in that they represent permutations of the same cryptographic concept and can be cracked with the same general methodology, albeit with slight variations in procedure. What is also interesting is that these ciphers can be viewed in tableau form, in slide form or matrix form.
The theory of polyalphabetic substitution is simple. The encipherer has at his disposal several simple substitution alphabets, usually 26. He uses one such alphabet to encipher only one letter, another alphabet for the second letter, and so forth, until some established plan has been followed. The earliest known ciphers of this kind, the Porta (1563) and the Vigenere (1586) used tableaus for encipherment, in which all the alphabets were written out in full below each other. The Gronsfield (1655) had a mental key, and the Beaufort (1857) which came two hundred years later, again used the tableaux. The process was reduced to strips or slides in 1880 at the French military academy at Saint-Cyr. The polyalphabetic deciphering slides now bear that name.
The Vigenere Cipher
The father of the Viggy family is the Vigenere Cipher. Like most of the periodic ciphers, the 'Viggy' is actually a series of monoalphabetic substitutions. The plain text is divided into groups which are the same length as the keyword and each group is written below the keyword. The keyword establishes the starting letter for each column and then the Vigenere Table (Figure 4-2) is used to determine the substitution for each letter of the message.
Attributed to Blaise de Vigenere, the cipher was invented by him in 1586 and published in his "Traite des Chiffres." He also invented an autokey system which used a priming key and which did not recommence his plain text key with each word, but kept it running continuously. He described a second autokey system which was more open but still secure. Both systems were forgotten and then were re-invented in the 19th century. Historians have credited Vigenere with the simpler polyalphabetic substitution system. Legend grew around this cipher that it was "impossible of translation" as late as 1917.
The original Viggy was composed of an enciphering and deciphering tableau. Letters were enciphered and deciphered one letter at a time. The modern Vigenere tableaux is shown in Table 4-2.
Table 4-2
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
A 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
B 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 A
C C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
D D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
E E F G H I J K L M N O P Q R S T U V W X Y Z A B C D
F F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
G G H I J K L M N O P Q R S T U V W X Y Z A B C D E F
H H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
I I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
J J K L M N O P Q R S T U V W X Y Z A B C D E F G H I
K K L M N O P Q R S T U V W X Y Z A B C D E F G H I J
L L M N O P Q R S T U V W X Y Z A B C D E F G H I J K
M M N O P Q R S T U V W X Y Z A B C D E F G H I J K L
N N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
O O P Q R S T U V W X Y Z A B C D E F G H I J K L M N
P P Q R S T U V W X Y Z A B C D E F G H I J K L M N O
Q Q R S T U V W X Y Z A B C D E F G H I J K L M N O P
R R S T U V W X Y Z A B C D E F G H I J K L M N O P Q
S S T U V W X Y Z A B C D E F G H I J K L M N O P Q R
T T U V W X Y Z A B C D E F G H I J K L M N O P Q R S
U U V W X Y Z A B C D E F G H I J K L M N O P Q R S T
V V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
W W X Y Z A B C D E F G H I J K L M N O P Q R S T U V
X X Y Z A B C D E F G H I J K L M N O P Q R S T U V W
Y Y Z A B C D E F G H I J K L M N O P Q R S T U V W X
Z Z 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
The normal alphabet at the top of the tableau is for Pplain text and the keyletters are shown at the extreme left under the 'A' of the top row. Where the two lines intersect in the body of Figure 4-1, the cipher text is found.
For example, using the keyword TENT, we encipher "COME AT ONCE"
we have:
TENT TENT
COME VSZX (cipher text)
ATON TXBG
CE VI--
The enciphering and deciphering problem are done as a group of letters to improve speed and accuracy of the process.
Which Way ?
Does it matter with the Viggy, that we encipher S by B (B alphabet or Key B) to find cipher T or encipher B by S (S alphabet or Key S) to find T? No. This is an interesting characteristic not shared by all in the Viggy family. It also was its downfall.
For instance, the message:
"Send Supplies To Morley's Station" enciphered with the repeating key, BED under the original method of encipherment as might be described by Blaise de Vigenere would be:
Key : BEDB EDBEDBE DB EDBEDBE DBEDBED
Plain : SEND SUPPLIES TO MORLEYS STAT I ON
Cipher: TIQE WXQTOJIV US PPVOFCV TXDUMRO
Decipherment by Probable Word
Modern cryptographers use automated attacks that are similar to the their historical antecedents.
Deciphering with the Key:
Key : B E D B E D B E D B E D
Cipher: T I Q E W X Q T O J I V
Plain : S E N D S U P P L I E S
Deciphering with the Message:
Plain : S E N D S U P P L I E S .…..... (trial key)
Cipher: T I Q E W X Q T O J I V
Key : B E D B E D B E D B E D ........ (true key)
The message fragment works well as a trial key, and if applied in the same manner as the true key, the true original key will be revealed. The Vigenere Cipher works equally well in reverse. It is this peculiarity that portends the use of a probable word attack.
Suppose we have the cryptogram:
U S Z H L W D B P B G G F S ...
which we suspect that the presence of the word SUPPLIES.
We decipher the first 8 letters using this probable word as a trial key, and obtain the jumbled series: C Y K S A O Z J, which is unsatisfactory. We next drop the first U, and obtain group : A F S W L V X X. We fail again on the third and fourth trials. The fifth decipherment obtains the series TCOMETCO. We see the TCO repeats and the key word COMET. A more organized approach is shown in Figure 4-3:
Figure 4-3
Cryptogram Fragment: U S Z H L W D B P B G G F S ......
Probable Word:
S C A H P T E L J X J O O N A
U Y F N R C J H V H M M L Y
P S W H O M A M R R Q D
P W H O M A M R R Q D
L L S Q E Q V V U H
I V T H T Y Y X K
E X L X C C B O
S O
Look down the diagonals we find the key word COMET. The first letter S was used to decipher every possible key letter which can produce S. The entire row of equivalents were produced at the same time. The resulting rows of decipherment indicate all the possible key letters that could produce S, then U, then P, and so on. Carter actually shortened the procedure to three full rows and then partials thereafter. He assumed that the keyword was readable and discarded non readable text.
Primary Components
Equivalents obtainable from use of square tables may be duplicated by slides or revolving disks or computer models. Cryptographically, the results may be quite diverse from different methods of using such paraphernalia, since the specific equivalents obtained from one method may be altogether different from those obtained from another method. But from the cryptanalytic point of view the diversity referred to is of little significance.
There are, not two but four letters involved in every case of finding equivalents by means of sliding components; furthermore, the determination of an equivalent for a given plain text letter is represented by two equations involving four equally important elements, usually letters. Consider this juxtaposition:
1. 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. F B P Y R C Q Z I G S E H T D J U M K V A L W N O X
Question - what is the equivalent of Plain when the Key letter is K? Answer - without further specification, the cipher equivalent can not be stated. Which letter do we set K against and in which alphabet? We have previously assumed that the K cipher would be put against A in the plain. But this is only a convention.
Figure 4-4
Index Plain
* *
1. Plain: ABCDEFGHIJKLMNOPQRSTUVWXYZ
2. Cipher: FBPYRCQZIGSEHTDJUMKVALWNOXFBPYRCQZIGSEHTDJUMK
* *
Key Cipher
With this setting Pplain = Zcipher.
The four elements are:
1. The Key letter, Q k
2. The index letter, Q 1
3. The plain text letter, Q p
4. The cipher letter. Q c
The index letter is commonly the initial letter of the component, but by convention only. We will assume from now on that Q 1 is the initial letter of the component in which it is located.
The enciphering equations above are:
(I) Kk = A1 ; Pp = Zc Eq. 4 -1
k=key, p=plain, c=cipher, 1= initial
There is nothing sacred about the sliding components. Consider Figure 4-5
Figure 4-5
Index Cipher
* *
1. Plain: ABCDEFGHIJKLMNOPQRSTUVWXYZ
2. Cipher: FBPYRCQZIGSEHTDJUMKVALWNOXFBPYRCQZIGSEHTDJUMKV
* *
Key Plain
Thus… (II) Kk = A1; Pp = Kc Eq. 4 - 2
Since equations (I) and (II) yield different results even with the same index, key and plain text letters, it is obvious that a more precise formula is required. Adding locations to these equations does the trick.
(I) Kk in component (2) =A1 in component (1); Eq. 4 - 3
Pp in component (1) = Zc in component (2). Eq. 4 - 4
(II) Kk in component (2) =A1 in component (1); Eq. 4 - 5
Pp in component (2) = Zc in component (1). Eq. 4 - 6
In shorthand notation:
(1) Kk/2 = A1/1; Pp/1 + Zc/2 Eq. 4 - 7
(2) Kk/2 = A1/1; Pp/2 + Zc/1 Eq. 4 - 8
Employing two sliding components and four letters implies twelve different resulting systems for the same set of components and twelve enciphering conditions. These constitute the Viggy Family:
Table 4-2
(1) Θk/2= Θ1/1; Θp/1= Θc/2 (7) Θk/2=Θp/1; Θ1/2=Θc/1
(2) Θk/2= Θ1/1; Θp/2= Θc/1 (8) Θk/2=Θc/1; Θ1/2=Θp/1
(3) Θk/1= Θ1/2; Θp/1= Θc/2 (9) Θk/1=Θp/2; Θ1/1=Θc/2
(4) Θk/1= Θ1/2; Θp/2= Θc/1 (10) Θk/1=Θc/2; Θ1/1=Θp/2
(5) Θk/2= Θp/1; Θ1/1= Θc/2 (11) Θk/1=Θp/2; Θ1/2=Θc/1
(6) Θk/2= Θc/1; Θp/1= Θp/2 (12) Θk/1=Θc/2; Θ1/2=Θp/1
Equations 4 - 9 to 4-20 inclusive
The first two equations (1) and (2) define the Vigenere type of encipherment and are widely used. Equations (5) and (6) define the Beaufort type and Equations (9) and (10) define the Delastelle type of encipherment.
Beaufort Cipher
Another member of the Viggy family, is the Beaufort. While the same procedure is applied, the slides (or tables) are different. One is a normal alphabet, extending double length A-Z; the other is reversed, double length Z-A. So if I = T at one setting, then T=I at the same setting. It does not matter what the index for the key is; the results are the same. So:
ABCDEFGHIJKLMNOBQRSTUVWXYZABCDEFGHIJKL
TSRQPONMLKJIHGFEDCBAZYWXVUTSRQPONMLKJI
Again the simple example.
T E N T T E N T
C O M E R Q B P
A T O N T L Z G
C E - - R A --
Some interesting relationships between the Vigenere, Variant and Beaufort are as follows: Let A=0, B=1, C=2 .. Z=25, then:
O Vigenere: Cipher Letter = Plain text letter + keyletter (modulo 26)
O Variant: Cipher letter = Plain text letter - keyletter (modulo 26)
O Beaufort: Cipher letter = Keyletter - Plain text letter (modulo 26)
Suppose plain text = B and Key = C. Since B=1 and C=2, Vigenere cipher text = 1 + 2 = 3 or D; For Variant cipher text 1 - 2=-1 +26 = 25 = Z. For Vigenere and Variant if key letter = A, since A=0,the cipher text = plain text. If we reconstruct a cipher assuming it is a Vigenere, but it is actually a Variant, we will get the true plain text but strange keyword. By subtracting the Variant equation from the Vigenere equation and setting cipher text (Viggy) = cipher text (Variant) and similarly plain text (Viggy) = plain text (Variant), we get the keyletter (Variant) = - keyletter(Vigenere) the same relationship as that between cipher text and plain text when the keyletter is A in the Beaufort (since A=0). Hence, we encipher our strange keyword with the A Beaufort alphabet to get the Variant key. The same holds true if we have a Variant and assume it a Viggy.
If we have a Vigenere and a fragment of the same message enciphered with the same key in Variant (or visa versa) then,
a. Plain text = (Cipher text(Variant)) + Cipher text(Vigenere))/2(modulo 13) Eq. 4-21
b. Key = (Cipher text(Vigenere) - Cipher text (Variant))/2 (modulo 13) Eq. 4-22
If we have a Vigenere and a fragment of a Beaufort for the same key and plain text or visa versa then:
c. Plain text = (Cipher text(Vigenere)) - Cipher text(Beaufort))/2(modulo 13) Eq. 4-23
d. Key = (Cipher text(Vigenere) + Cipher text(Beaufort))/2(modulo 13) Eq. 4-24
In equations a-d, two answers are produced because modulo 13 will give one number from 0-12 and another 13-25.
PORTA (aka Napoleon’s Table)
Table 4- 3 defines the PORTA Cipher. In this table the alphabets are all reciprocal, for example Gplain(Wkey) =Rcipher, Rplain(Wkey)=Gcipher. They are called complementary alphabets. Either of two letters may serve as a key letter: Gplain(Wkey) or Gplain(Xkey) = Rcipher.
Table 4-3
A B C D E F G H I J K L M
AB N O P Q R S T U V W X Y Z
A B C D E F G H I J K L M
CD O P Q R S T U V W X Y Z N
A B C D E F G H I J K L M
EF P Q R S T U V W X Y Z N O
A B C D E F G H I J K L M
GH Q R S T U V W X Y Z N O P
A B C D E F G H I J K L M
IJ R S T U V W X Y Z N O P Q
A B C D E F G H I J K L M
KL S T U V W X Y Z N O P Q R
A B C D E F G H I J K L M
MN T U V W X Y Z N O P Q R S
A B C D E F G H I J K L M
OP U V W X Y Z N O P Q R S T
A B C D E F G H I J K L M
QR V W X Y Z N O P Q R S T U
A B C D E F G H I J K L M
ST W X Y Z N O P Q R S T U V
A B C D E F G H I J K L M
UV X Y Z N O P Q R S T U V W
A B C D E F G H I J K L M
WX Y Z N O P Q R S T U V W X
A B C D E F G H I J K L M
YZ Z N O P Q R S T U V W X Y
The Porta Cipher permits 13 different ways to disguise a plain letter.
Nihilist Substitution
Gaines suggests that cracking this cipher parallels the Viggy to the extent of determining the period (keyword length). The period is found through repeated sequences, or in their absence, through repeated single letters, yielding individual frequency counts on the several alphabets of the period. If the arrangement of the cipher text follows the normal Polybius (aka Checkerboard) Square, the frequency counts will follow the graph of the normal alphabet less one letter. Even with the keyword mixed cipher text alphabet, no matter how badly mixed, the frequency counts are parallel and the several alphabets combined follow one graph, and can be "lined up."
The primary alphabet contains only the digits 1- 2-3-4-5. The maximum difference is 4 and addition of any number to all of them does not change this fact. The maximum difference between any two sums is still 4. Now the number added during encipherment is also a number containing no digit other than 1-2-3-4-5; thus any number found in the cryptogram can be considered as carrying two separate additions, one for tens and one for ones. The two 5's added give us the revealing 0; the carried digit 1 can be mentally borrowed back, by decreasing the size of the digit preceding the zero. If we find a 40 , we look at it as 3 tens with ten units or finding 110, we may regard this as ten tens and ten units. If we find the numbers 29 and 87 in the cryptogram, we know they were not enciphered by the same key. This is because a difference greater than 4 in the respective tens units exists and no digit whatever added to any two digits of the original square can produce a difference greater than 4. Say we have 30 and 77, with no difference greater than 4, the presence of the zero needs to be accounted for. The number 30 has 2 tens and ten units; 7 - 2 >4, hence, we reject the same key hypothesis.
Consider the following challenge:
24 66 35 77 37 77 55 59 55 45 55 88 28 66 46
88 37 67 33 59 58 65 45 66 67 58 44 55 34 79
44 59 55 45 42 87 28 76 43 78 46 86 26 67 24
85 26 67 28 76 26 78 46 65 65 88 36 49 54 67
28 65 42 88 36 49 44 89 57 58 54 66 47 67 26
Try period = 2. Starting at the first number 24, we scan the line looking for differences greater than 4 using a constant difference of 2. We come to 33 and 38 and stop.
Try period = 3. The first comparison fails at 24 and 77.
Try period = 4. We are able to go through the entire cryptogram, comparing numbers at an interval of 4, without find any difference in either tens or units greater than 4. We now must look at the numbers collectively in columns to verify the period is 4. We recopy the cryptogram into a block.
Key = 4?
24 66 35 77
37 77 55 59
55 45 55 88
28 66 46 88
37 67 33 59
58 65 45 66
67 58 44 55
34 79 44 59
55 45 42 87
28 76 43 78
46 86 26 67
28 76 26 78
46 65 65 88
36 49 54 67
28 65 42 88
36 49 44 89
57 58 54 65
47 67 26 -
Alphabet 1: The tens-half of the first column contains the digit 2 and since this can only come from the addition of 1 plus 1, the only possible key digit is 1. The units-half has a range of 4-5-6-7-8, maximum range possible. The smallest digit to result in 8 is 3, the largest digit to result in 4 is also 3, that is the only digit which can result in all of the digits 4-5-6-7-8 is 3, so that the cipher key for this column is 13. It cannot be anything else.
Alphabet 2: The tens-half of the second column ranges over the full five digits 4-5-6-7-8 (key 3), and the units-half ranges over 5-6-7-8-9 (key 4). This suggests the key digit
is 34.
Alphabet 3: The tens-half of the third column contains the 'giveaway' digit of 2 and the units-half also contains the digit 2. The key digit to produce this situation is 11.
Alphabet 4: The tens-half of the fourth column ranges only over the digits 5-6-7-8, with nothing to indicate whether the missing digit is 4 or 9. The key might be either 3 or 4. The units has the full range of digits 5-6-7-8-9, hence key = 4. So we have either 34 o 44 for our key digit. The normal square suggests COAO or COAT as the key word. We decipher the whole cryptogram a column at a time:
C O A T
--------------------
A M I N
I S T E
R A T T
E M P T
I N G E
U L O G
Y I N A
F U N E
R A L S
E R M O
M W E H
A V E H
E R E O
N L Y T
H E S H
E L L T
H E N U
T I S G
O N E
Reads: A minister attempting eulogy in a funeral sermon: We have here only the shell, the nut has gone.
For the difficult case presenting multiple key possibilities, we line up the alphabets graphically against their frequency counts to eliminate the extra key digits.
Digraphic Ciphers: Playfair
Perhaps the most famous cipher of 1943 involved the future president of U.S., J. F. Kennedy. 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:
20 groups
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 OWE NINE LOST IN ACTION IN BLACKETT STRAIT TWO MILES SW MERESU COVE X CREW OF TWELVE
X REQUEST ANY INFORMATION.
The coast-watchers regularly used the Playfair system. Evans deciphered it with the key ROYAL NEW ZEALAND NAVY and learned of Kennedy's fate. Evans reported the find to the coastwatcher near Munda, call sign PWD, that Object still floating between Merusu and Gizo. 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 his crew had done. They had swum to Plum Pudding Island on the Southeastern tip of Gizo Island.
Several messages passed between PWD, KEN and GSE (Evans). The Japanese made no attempt to capture Kennedy even though they had access to the various messages. The 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. At 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 diplomatic use during his lifetime. About 1890 it was adopted for use by the British Foreign Office on the recommendation of Lord Lyon Playfair (1818-1898) and thereafter identified with its sponsor.
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 enciphered 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.
(The letter J is not found.)
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
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. 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 and the alphabet in the upper right and lower left squares are mixed, usually by means of a keyword.
Plaintext letters are found in the two straight alphabet squares and the cipher equivalents are located in the two mixed alphabet squares.
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.
Decipherment 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
Peculiarities of 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.
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.
Observations
Delastelle Systems - Bifid Cipher
Friedman, Bowers and Lewis discuss the intricacies of the Bifid cipher. 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 of 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
Column 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
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.
3. Long repeats occur at irregular intervals.
4. Repeated patterns dependent upon the length of the repeated sequence and the period
5. A frequency count will show a flat profile compared to normal plaintext.
Peculiarities of the Bifid
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.
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.
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.
Delastelle Systems - Trifid Cipher
Both Bowers and Linz covers the Trifid in detail. Topics include Keyword Block recovery, periodic group structure, Trifid patterns, pattern uncertainty,
tetragraphic patterns and part naturals. In the case of the Trifid, the block takes the same form with an additional dimension. 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:
Component
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
Peculiarities of the Trifid
Wrap-Up
The diversity of classical cryptosystems prepares us for their modern encryption equivalents. Many of the more elegant attacks on cryptosystems are not brute force search of entire keyspaces but revolve around finding the appropriate wedge(s) or weaknesses in a cryptosystem as shown using classical techniques. Cryptography has evolved from the language structures and pattern recognition techniques via known or natural relationships in the plaintext - ciphertext to solutions based on mathematical or structural constructs. Modern cryptography rests on the shoulders of its cryptographic predecessors.
Chapter: 1 | 2 | 3 | 4 | 5 | 6 | 7 | 9 | 10 |
| Reserve your copy at a Beta Bookstore near you! |
Contact Bet@books © 1998 The McGraw-Hill Companies, Inc. All rights reserved. Any use of this Beta Book is subject to the rules stated in the Terms of Use. |