\ 

• 

REF ID:A66796 

Mr. F~ied.man s 

1. Thi!ii paper used to be CONFIJm.,'TIAL and 

registered in its previous edition. We sent a 

l•tt•r to the Navy in Aprit requesting this 

paper, and we still have no answer: this is indicative or the state or chaos existing in their 

training section. 

2. There are two footnotes (pp. 7, 12) that 

refer to Gaines' ''Elementary Cryptanalysis". This 

is a sad commentary on the Navy's training resolirces 

in that they make their only references to a book 

available on the public markets this exaggerates 

the wo_rth and importance of the Gaines book, and 

minimizes the resources of the Navy. Certainly 

a paning. mention could have been Jri&.de of the Army's 

teats on cryptanalysis, especially since the Navy } 

has no_·text, or its #!''¥).• ••• - 't", ~ ll.~u. ... 

cw..u. IJ) .. .., ~- --~" "'?C~· . .,, ............. ~ ~. 3. 01;herhan the t?oor tenninology emplo)fed, 

and the plethora of mathematical eyewash that 

makes a simple subject difficult, this paper is 

potentially very good, after substantial editing 

and liberal re-writing. 

- Capt 6. 

eclassified and a roved for release b NSA on 03-10-2014 
RilB'fRIBHB 

REF ID:A66796 . 

(~:ti 

·THE INDEX OF COINCIDENCE 

FOREWORD 

The subject of this pamphlet is coincidence. 

The student may well ask, "What is coincidence and what applications has it?" 

"Coincidence" as the term is used here may be defined as a recurrence of a letter in the same place, or in ·a corresponding place, as when two texts are lined up 

one under the other, letter for letter. 

This mathematical evaluation assists the cryptanalyst first in prepar1ng his 

material for attack, and later in the actual attack itself. It assists specifically in answering the following questions. 

1l How much like random, or how different from random, is this text? 

2) How similar are these texts? 

3) How significant is this variation from random? 

4) How significant is this s im-ilar it y? 

--
REF ID:A66796 \ 

I SIMPLE MONOGRAPHIC COINCIDENCE 

The te's't of coincidence is the evaluation of the coincidences of letters, or of 

digraphs, etc., between two or more messages, or within the same message. 

The coincidence' or "pairing" test may be consolidated into one final number or . "statistic". That statistic is called the "index of coincidence" and is defined as the ratio of the actual coincidences to the coincidences to be expected from chance 

(coincidences in random text). For English text the expected I.e. is 1.75. For 

most European languag~s the expected I.e. is about 2.SO. For random text the expected I.e. is 1.00. 

Assume two pages of cipher text based on a complex cipher which will give a "flat" frequency table for the entire message. Select a letter at random (say the 

3rd) from one page and another from the other page (say the 3rd also). 

Taere is 1 chance in 26 of the first letter's being an ·~~ 

There is 1 cb.ance in 26 of the second letter's being an "A" 

There is 1. chal}ce in 676 ,of both letter's being "A" 

There is also 1 chance in 676 of both letter'i:; being ''B" 

Therefore, the chances of° both letters being the same letter (in a chance selection 

of cipher text) -are: 

26 chances in 676, or 1 chance in 26, or 3.8462%. 

If we select many p~irs of cipher letters, the average number of identical 

letters to be expected "in the long run" will be 3,846% (or 1/26) of the total 

number of possible coincidences; We call this number the "Expected Coincidence due 

to Chance" (random text). -

With English text it is different. Take two pages of English text. Make a chance selection from each page. 

There are about ~chances in.!......!@..!! of the first letter's being an "E" 

Tnerc are about ~chances in~ of the second letter's being an "E" 

There are about 16,9@0 chances in 1,000 000 of both letters' being an "E" 

Likewise, there are 8.464 chances in 1.~10.000 of both being "T" 

"' 6,400 .chances in 1,f.1(1!0,000 of both being "N", etc. 

(See table following). 

- 2 -
REF ID:A66796 

Text Letter Chances in I Chances in Chances in 

(Telegraphic 1,000 of 1st 1,000 of 2nd 1,000,00£1 of both 

Text) letter's be- I letter's be- letters' being -ing this ltr. ing this ltr. this letter 

E 130 130 16,909 

0 75 75 5,625 

A 74 74 5,476 

I 73 73 5,329 

N 80 80 6' 100 

R 76 76 5,776 

s 61 61 3,729 

T 92 92 8,464 

D 42 42 1,764 

H 34 34 1,156 

L 36 36 1,296 

c 31 31 961 

M 25 25 625 

u 26 26 676 

p 27 27 729 

F 28 28 784 

G 16 16 256 

y 19 19 361 

B 10 10 100 

v 15 15 225 

w 16 1.6 256 

K 4 4 16 

J 2 ·2 4 

Q 2 2 4 

x 5 5 25 

z 1 1 1 

, Any letter 1J000 1,000 66,930 

Finally there are 66,939 chances in 1,000,0op (the sum of the chances for the 

individual letters) of both letters' being the same plain text letter in a chance 

selection. Therefore, if we select many pairs of plain text letter~, the average 

·number of identical letters to be expected "in the long run" will be G.693% 

(about 1/15) of the total number of Possible Coincidences, 

We ma~ call this number the Expected Coincidences in English Text 

In actual practice we are concerned with the coincidences between our two texts, o or within our alphabet, etc. The tally or count of these coincidence;; we call the 

Actual Coincidences. 

To permit comparisons between results obtained from texts of varying amounts, 

it is most conv~ni~nt to convert to an index number. We call this fhe Index of 

Coincidence and use the abbreviation I.e. or L. 

By definition l = Ac1tual Coincidences 

Expected Coincidences due to Chance. 

The expected I.C. for English (or mono-alphabetical cipher text) is: 

•96693 • 1 75 approximate~y • • 93846 • ' 

The actual I.e. of unknown cipher text may take almost any value but in practice the 

range will ;enerally extend from about .80 to about 2.00 (simple monographic index 

of coincidence). 

The value of the index of coincidence for a given English text will depend on the actual distribution of letters in that text. Repetitions in short texts will 

increase the index of coincidence. Unrelated text (that is, text with few ~epetitions) will give an I.C. approachinr. the ~heoretical 1.75. As the expected number 

of chance coincidences is based on a flat frequency (where each cipher letter is 

ultimately used the same number of times) any cipher text that differs radically , from such frequency distribution will have a correspondingly higher I.C. This is 

especially ·noticeable in short cipher texts where the frequency table has not had an opportunity to "flatten out". 

- 3 -
7. 

REF ID:A66796 

The mono-graphic I,C, of English naval text will increase with small amounts 

of text to 1.80 - 2.00 (as compared with the theoretical 1.75) and small amounts 

of random text will give I.C.'s of 1,10 - 1.20 (as compared with the theoretical 

1,00). The amount of excess attributable to the sample size will be discussed later, 

under "standard deviation". , 

For most European languages the expected I.C, is higher than in English, due to 

the more irregular letter distributi_on of their normal alphabets, namely: 

Language 

Random text 

English 

Italian 

Spanish 

French 

German 

II POLYGRAPHIC COINCIDENCE 

1.0 

1,7 

1.9 

2.0 

2.0 

2.0 

In addition to the simple monographic index of coincidence (l ), there are occasions when the digraphic index of coincidence (t 2 ), trigraphic I.e. (t 3 ), 

tetragraphic I.C. (t 4 ), pentagraphic I,C. (t_,.), etc., can be used to advantage. 

They are derived from the normal digraphic (trigraphic, etc) frequency tabl~s in 

the manner indicated in paragraphs 3 to 7. 

Expected values for thefi'e simple polygraphic indices of coincidence are as follows: 

Language l.2 /, J /, 4 l.5 

Random text 1.00 1.00 1.00 1.00 1.00 

Englisn 1.75 4.75 27.89* x x 

Italian 1.92 5.68 x x x 

Spanish 2.02 6.29 x x x 

French 2.02 6.29 x x x 

German 1.98 6.57 x x x 

Notes: X =Not computed. 

~ * =(.Computed from the only known trigraphic table. \ 'The correct index might vary widely from this estimate' 

In practice the actual polygraphic I.C,'s will usually run higher than their 

theoretical values, and a repeated word or two in short texts will made them sky 

rocket. As typical examples, we have taken the plain text of four problems in the 

elementary and secondary courses and computed the various I .c. 's (from t , to t 5 , 

that is the monographic, digraphic, trigraphic, tetragraphic and pentagraphic 

indices of coincidence). 

Text /, L2 /, J l4 /, 5 

Expected random 1.00 1.00 1.00 1.~0 1.00 

Expected pla~n 1,75 4.75 27.89 ? ? 

Problem No. 1 1.80 5.23 29.11 427. 7240. 

.Problem No. 2 2.00 7.73 66.04' 1062. 14900. 

Problem No. 3 1.91 5.60 42.04 666. 12070. 

Problem No. 4 1.74 4.90 31,70 456. 9190. 

III THEORETICAL RECAPITULATION 

Suppose we have a language for which we know the overall proportions of the 

letters are P1, P2 1 - - -, Pc· 

~ p·· = I. (1) , t 

Suppose further that we have two pieces of text from this language and line 

them up one above the other, and then count coincident letters, What is the ex- pected nwnber? 

- 4 -

, 

, 

'=-·""" 

-·-
REF ID:A66796 

At a particular place the probability of a coincidence involving the i th 

letter is Pi2. There fore, the C cases being mutually exclusive, the probability of an incidence is 

-~ 2 4- Pi · 

If the length of overlap is N, then the expected number of incidences is 

N :f I 

(2) 

If the text is such that Pt = will refer to it as "flat", I /c J we 

or "random". The probability 

expected number is N !. 

c 

The ratio of the number 

"index of coincidence", 

is ;f 

I 

of an incidence , !rnd the 

found in a comparison to that expected is called the 

I - £l.. - cg/ ~ - /~c - /N. (3) 

The expected value 'Y of for our language fs given by taking the expected 

= c 

c 2 

g= NL Pi 

I • 

value of 

7 = N 

over the expected value for c 

LP· 2 

I L 

flat text or 

(4) 

Notice that the expected value of the I.C. for flat text is 1. 

IV PRACTICAL APPLICATIONS 

(A) TO DETERMINE WHETHER TWO MESSAGES ARE IN THE SAME KEY 

During u.s. Fleet Problem V (1925) the Battle Fleet used a cipher of their own design. A total of 13 messages in this cipher were submitted to the Code and Signal 

Section for attack. Although a different indicator was used in each case, it was suspected that some of the messages might be in the same key, Two messages in one key (example No. 1) and two more in another key (example No. 2) were discovered. 

(The messages were eventually solved), 

Each message was "lined up" with each other message and the coincidences were noted, (See examples No, 1 and No. 2), 

Example No. 1 

KT XV H.J GP Z J W BJ MF SU GP NS VS 0 P NF D NG 

R 0 A A 0 R GP Z E Z G !l_F R Z PS 0 I U IQ MM FD H 0 F 

J H U Y L I M A L S B N B J X W M P W G W V C U C D F G R L 

M N R J 0 G 0 S I C Y U G U D I. !. D C K W Z P R P J L E .! R 

V G P U B X P M W C 0 B G X R J S P V P W C F W P G J V Q B KLAGPADXYYKHHKCI~QPYUOPJJFRBGX 

Y F B D S L J 0 C N V V S L J 0 D S 0 0 L P R 0 C G S P U A 

Z B N 0 P 0 J N Y Z V T Z L S K R A J 0 P F Y F R X N D G E , - - - C D B 0 C V D K Q B S P E L T R N V I U 

G Q Q M N L Q V V A G ~ T Y C G C P N X J Q U E R D Q W W Q 

---- _,_ Q Q U I I V H B K Q 

Coincident letters are underscored, 12 coincidences in 149 pairs of letters. 

- 5 -
REF ID:A66796 

.simple monographic coincidence. 

Expected ~ = 140 = ~ 5. 4 Where N = number of units examined. 

Coincidences C ~ C : number of cells for single letter 

examination : 26. 

IC • 12.9 = 2.2 

5.4 (Messages are in same key). 

There is one repeated trigraph, GPZ, in the messages under examination. This 

coincidence indicates that the keys correspond at that point, but does not necessarily indicate that the keys correspond throughout the message. To prove coincidence of the keys throughout the"two messages, we must have our coincidences spread through the messages in question. (As they were in the above example). Likewise, 

digraphic and trigraphic coincidences may be compared and evaluated to an index of 

coincidence. 

For example, in the above messages, 2 coincident digraphs were found (GP and PZ) 

(also one coincident trigraph). In this message there were 139 digraphs and 138 

trigraphs in alignment with possibilities of coincidence. I 

1i - 139 - .206 

676 - 676 -

digraphs were to be expected from chance. Two were found, giving an IC : ~ = 9.70 • • 296 

This value, far above the normal 4.75 index of coincidence, does" not necessarily 

indicate the messages are in the same key. All we really know is that the two keys 

are identical in the second group, The extremely high I.C., 9.70, is due entirely 

to the small amount of text involved in this example. As the amount of text 

decreases, the variation of the I,C, from the expected will become more pronounced, until at times it is possible that small amounts of text may give entirely false 

indications. This effect will be discussed more fully under "standard deviation". 

Example No.' 2 

A Z E P U U Y C N 0 Z E S F J X. C T A T M J C G G P F K U B 

BCAEZQQVUQOOEJWWD1QQSPFWCTOHPZ 

PEKDAPNUTJDauwQQITNPEXTGHTKDCL 

JSDNDUJKLUZJCS£H~OZHUKE&XDEPWT 

. . Z R P W A M M T I Q J F P K F D C 0 V P D U C H Z W X M G E P~FRXPIQVAFQRPLEAQPQEWOYEGXROY 

QVRITAFFZRYEGOAZBABGDWBJAUBEEP 

YPGAVSLAXQEOLJOU~R~SF~JWDDJPSS 

NMKOCZDIXBYALVSPGPXFNUEFXNWDFL' 

D T E P PD Z'G T J 0 C V H TR MR PH T Y1C Q .! L L V R N 

AKNAVQAXPOPRPPRPPQPUDBLMNJQXUE 

0 FY.! X G_Q LU P Q FDR W D L Z WIT,! D ~ IP Y Y·V G 

QAWSQJNGPEOAMDNZAAPFAZYOTNQWVX 

UMNGCFJFLQRME~FOZNSPECDSLIZQYA 

I I D T W W C C Y B X o· Y U 0 S Q D N 0 B A S R H C T D D U 

H N I X Y A 0 J B K - - - - - - ~ - - - - - -

14 coincidences in 220 pairs of letters. 

I • .aa! = 8.46 coincidences expected. 

c 26 

IC = _!!_ • 1,66 (almost normal for EnglishJ. 8.46 

These two messages probably are in the same key (and actually proved to be). Note 

that there are no repeated digraphs or trigraphs. Note also that coincidences are 

well spread out. 

- 6 -

;~ • I 
REF ID:A66796 

(B) TO DETERMINE WHETHER TWO MESSAGES "()VERLAP" IN THE SAME RUNNING KEY 

Copy each message on a single line, omitting all spacing. "Line up" the 

messages and note coincidences. Then shift one message one place to the right and 

note the coincidences. Repeat this process to the en~. 

- If the index at any point is 1.75 or higher, for mono-graphic ex:imination, the 

position and the fact of the "overlap'1 is probable. In thio; application the digraphic 

and trigraphic indices are useful adjuncts to the monographic index, 

For some purposes the fundamental unit may be taken to ba a set of letters, 

digraphs, trigraphs, etc. Suppose we are interested in digraphic coincidences. 

the digraphic I.e., te , will be calculated as above, noting that.the size C of 

alphabet is larger this time. 

V RELATIONS AMONG THESE STATISTICS 

llS 

Then 

the 

The monographic and digraphic I.C.'s are not independent. For if the 

probabilities of the various letters are P1, P2 , - - -, Pc, then the probability 7iJ 

of the ijl.b. digraph is Pi P; ignoring the cohesion of the lani;uaJe, :rnd for 

the moment treating it like newsp~per which had been cut into little pieces, one letter to a piece, a~d then shuffled and arranged in a line. Using this cstimage 

of 7 i j we get the I.e. 

~ = c2 ~ ;f: '>iJ2:: c2 ± -5- Pie e Pj T j=I I "T-

= c2 +Pi e ? P1 e:: ( c_? Pie = -ye) (5) 

It is true however that language has cohesion, 311d that each letter affects the 

probability of occurrence of others in its vicinity. Usually then t 2 is in excess of the estimate t 2 above. We will sometimes calculate the ratio 

=>i;,and call it the digraphic "index of cohesion·~ (6) . 

Estimates can be made in the same way far higher I.C.s. One can show that 

11.-' = l..i-1 I. or 

7; I 

I.. = 'i-; /,} (7) 

In these equations the right members are thought of as quantities already com- puted; while the ?''son the left are estimates or predictions of quantities which can be computed from the definition (4). 

An application of these relations occurs in the study of fractionating* systems, 

where as a preliminary to enciphering the text is expressed as a product of two com- ponents, and each component is enciphered.separately, and then the c,ipher text is re- combined to ordinary letters. For instance, each of 25 letters may be represented by a two digit number, ~here the first di~it comes from 0, 1, 2, 3, 4, and the second 

from 5, 6, 7, 8, 9, The argument for these proceeds as for digraphs, and the I.C. of 

the combined text is the product of those of the fractions. However, here any significant deviation from this estimate is not adequately described as cohesion, but must 

be due to the dependence of the, two fraction streams. 

VI THE ROUGHNESS OF A SINGLE SAMPLE 

We have introdtaced the I.C. as a measure of the match between two pieces of text. 

We can extend th is ide,a now to a measure of the rourrhness 'of a single sample. Suppose we have a piece of text which we duplicate on twc> slips of paper and then place them one under the other for the purpose of countin~ c<>incidences. There will be one position of total coincidence, which we will rule out. If we com,ute the I.C. for all 

other positions, we will have what we call the "'index of coincidence of a sin~le sam- ple. 

*Consult Gaines "Elementary Cryptanalysis," Chapter XXII 

- 7 -
REF ID:A66796 ·, 

If there are M letters in our sample, we will have looked in N = l/2M(M-l) distinct places. (8) 

If the text is ~lat we would expect N _ M(M-1) coincidences. 

-c·-,c (9) 

If the text is not flat but have proportions P1 , P2 1 ---, Pc of letters, then 

there are fi= P~M occurences of the i th letter .. In the course of our counting we will(l9) 

compare every letter with every other, so that the.ith letter will give rise to 1/2 

f, Cf, -1) coincidences, or c 

?, 

Comparing this with the expected ·in flat text we get the I.C. 

o = ;f ~ f;, ( Fj, - I ) 

I 

Vzc M (M-1) 

6' = c f !;, ( 1-1) 

M (M-1) 

in all. 

In theoret1c'll ·context· (12) is more useful than (13), but (13) is a little simpler for 

computational purposes. 

Notice that this formula is different from (4). This is because of the omission 

of the perfect hit. If 111 1s large enough then ft -1 can be replaced by f L = PiM and 

M-1 by M, so that 

= c 

is an asymptotic expression for 

Kot ice that C z ?' _2 I 

We see that 

M-1 C 

o ~= ')' - M 

or lotM-1) =7M-C 

0 = ')' M- c 

M-1 or ")' = 

Me 

0 

= c 

o(M-l)f-c 

M 

± p.2 I L 

= ')' 

The ('rror in using ?'(usually more convenient) in place of 

d' IS '>'-o= 

\ -

c - ")' 

M-1 = c - cf' 

M 

This error is always positive, that 'is, ?'is an over-estimate of <f'. The error is smaller for laricer values of ?', or larger values of M. 

- 8 -

(11) 

(12) 

.(13) 

(14) 

(15) 

(16) 

(17) 

-~, ·--

I~. 
---- - - -- -

REF ID:A66796 

Notice that ?'is a m~asure of the shape of the distribution only, and is indei:0ndent of the sample s1ze, ac; is 

c ~ f-1

2 

"Y = ---~-- M 2 = M ,2 

l 

= c2Ji/ 

But <J dnes depend on the ;::ample size M. which is a desirable chnracteristic, 

since random rnusbne~s is usually present in sma)l samples. For smaller samples 

0 = ?'- c-. ')' 

M-1 

is seen to be smaller. thus autom~tically compensatin~ to some degree for small sample errors. We will usually me:asure the r:rn~hness of sing-le samp-les by rJ, using ?' as an asymptotic approximation. 

VII EXM-TINATIOK C'F CIPHER ALPHABETS AND CIPHER TEXTS 

Thl' inchc<:-s nf cn1nc1dences discussed in the previous paragraphs may be :1sed in 

analy.1.ing the intc>rnnl structure nf a c1p'.1er alphabet. A messag;e of 173 letters has 

a tr~q~0nc\ table a~ ~ivcn belov: 

,, B c ll l ~· G !I J K L \I R s T u v \I" x _y z 

r; .. 

.. 14 2 2 111 2~ 6 1 8 13 1 13 2 13 7 19 1 2 1 

I 

We mak.;o ~ tn 11 ~ .. :.,un t. i. c .. the "::mb0r pf time;; :1 let tcr ncc•irs \\'l th the ~amc frcq·.1ency, thuc;-

:~umber o1 

.!:!.1.11' Ta 1l 1e;; f(f-1) n(x) f(f-1) 

f - n 2 

Q 1 A 0 

]- :~ (I 0 

2 ·I 1 ·1 

3 l 3 n 

·1 1 6 6 

" 2 15 :HJ 

7 1 21 21 

8" 1 ·28 28 

10 2 4!'i 90 

13 3 78 23·1 

1-1 2 91 182 

19 1 171 171 

22 1 231 _i3-1 

C..., 1nc idences 1(1(1(1 

(IR) 

(19) 

l'·C' f1nd thit 111t'rt.• arc U1!11i l'••1ncidt.'ncec,. ,,lthn•l!th 11e c:1.n n . ...,t count the C•'inc1dcnccs 

1n th0 PX:tmin:itinn nf ,, ..,1n:le cipher text_ 1ve> c.111 cvali:nte the various frequency 

._•,•uni::. 111tn :1C"t11.1l co111c1dt•nc~s- :rnv1n·~ tlie actual cn1nc1dence.::; 1rnm the table 

(1000). 1•.(' nhtn in th<" I.C. by -fnr;n11la ci:n · 

S11h..;t 1t11t 111 ~. 6 -

0: 

- 9 -

c L-1 (~·-I} 

M (M - I) 
REF ID:A66796 

As a second example to show the results obtained from small texts, we calculate as follows from a frequency count of 36 letters assum~d to be monoalphabetic. 

A 3 N 2 

B 0 1 

c 5 p 

D Q 

E R 1 

F 3 s 3 

G 1 T 1 

H 1 u 2 

I 1 v 

J w 1 

·K x 4 

L 3 y 4 

M z 

Tally or Cells 

(f) n l/2f(f-1) T fC3 T T 

fJ 111 

1 7 "' A "' '"' . Ill A 

2 2 1 2 6 " -...f! " 3 4 3 12 1 4 

4 2 6 12 4 8 

5 1 lA 19 16 16 

fl'-....._ fJ 

1 "---- 2 5 ·--5 

36 22 7 

IC 36 x 26 x 2 = 36 x 35 = 1.49. 

The alphabet in question was actually a monoalphabetic substitution. With a small 

amount of text, the simple index is somewhat indeterminate, Using the'triple and quadruple indicen, the results are even more so, and at times may give even.false indications. It is again emphasized that sufficient text must be used to give positive indications. 

As anot~er elementary example of the ·application of the index of coincidence to 

the internal examination of a cipher text, we have, for example, a 5-letter repetition 

at an interval of 85. Is the cipher a polyalphabet cipher of 5 or 17 alphabets? By means of internal examination with the index of coincidence we can determine what type 

of cipher we have. Make a frequency count of the cipher alphabets assuming 5 and then 

17 alphabets. 

Calculate the index of coincidence in each case for one. or more alphabets. The indices 

of higher value will indicate which assumption is correct. If neither assumption shows 

positive results (an index aro'und 1.7) we may have a progressive cipher, running key 

cipher, auto key cipher, or cipher of even more complex nature. ', 

Another elementary application is as follows. We have a cipher message which has b~en intercepted. The I.C. is computed and found to be d'=l.79. 

This is so rough as to resemble plain text. A simple substitution has the property of leavin~ d' unchanged, and so has a transposition. Multi-alphabet substitutions lower 

the I.C.. So we are reduced to three hypotheses, that our sample is either transposed 

plain text, a simple substitutiop, or both substitution and transposition. 

The digraphic I.C, is computed, d'2 =4.85. Remember that its expected value is 

3. fl5 = d 2 in view of the known roughness. Therefore the index of coherence is K2 = 

4. 85 =1 56 

3. 05 . 

Since a transposition destroys coherence we can assert that no transposition is involved. Multigraphic Indices of coincidence are preserved by a simple substit'ution. 

- 19 -
- - -------~-----------

REF ID:A66796 

VIII THE STANDARD DEVIATION 

We have already several times referred to the fact that these statistics are useful 

only if the sample is large enough. To get an idea as to whether th is is the case 01· 

not we measure our results in terms of a standard deviation, "sigma". One standard 

deviation is roughly one half the widt:h of a band which when placed about the average 

will include two-thirds of the data. It is a measure of the dispersion. If si~ma is 

large the data is spread out v.ide, and if it is small the numbers are close to~ether. 

In a binomial distribution the standard de'vrntion isO"-"VN ,. pq where N is the 

number of observations and p and q are the probab i l lt iec; of success and failure. 

To estimate the significance of o , we refe1· to (12), where the denominator is 

the expected number of incidences in flat text. and the numerator is the number found. 

Assuming a binomial distribution of the incidences we find the variance cr2 =Npq = 

M(M-l)~C-1). 

2C (26) 

If s is the "sigmage" or deviation of the number found divided by 0- we have 

s = 

c L ft (ft - I) - M (M - I) 

= v2rc-1 J(MJ(M-11 

o- I 

= \12-;:=rc=-=-1 J ~) 

~ ~ ' fi (Fj_-1)-.MfM-IJ ?-- 2C 

VM(M- l)(C-1} 

2C2 

c 2ft (ft. -I) 

M (M-!) 

V2 C-1 

Ill fill-fl 

-I 

= r=:J-1·-----,;J 

~(C-1!__. _____ J 

For M>51 error is less than 1%. 

tJ - I 

Notice that the sigmagc is a linear function of the s:i.mple size M, and also 

linear with the "bulge" d'-1 . The denominator is relatively unimportant to the es- timation of S exc~pt in shifting from code to cipher, when C can change from 500,000 

to as small as 10. 

The bulge d'-/ is' a quantity which will recur frequently. 

Formula (23) does not apply to the iota I.C. 

g and % found. Then d 1 = ~c (I - Ye J 

g- 'tc g~N I t - I 

s::--::;::::=== V%r1-YcJ 

=-:--===-- v _£:!___ N ~ 

For that ~e have the expected number 

and the si~mage is 

In this case the si~mage is linear with the bulqe 

square root of the sample size. 

l - I , hut varies only as the 

The significance of s is given in the following table, which lists the probability of getting s or a larger result from chanc~. 

- 11 -

(21) 

(22) 

(23) 

(24) 
REF ID:~66796 

Table I 

s 

.1 

.2 

.3 

.4 

.5 

.6 

.7 

.8 

.9 

1.0 

1.1 • 1.2 

1.3 

1.4 

1.5 

1.6 

1.7 

1.8 

1.9 

2.0 

2.1 

2.2 

2.3 

2.4 

2.5 

2.6 

2.7 

2.8 

prob, 

.4602 

.4207 

.3821 

.3446 

.3085 

.2743 

.2420 

.2119 

.1841 

.1587 

.1357 

.1151 

.0968 

.0808 

.0668 

.0548 

.0446 

.0359 

.0287 

.0228 

.0179 

.01:39 

.01C:f7 

.0082 

.0062 

.0047 

.0035 

.0026 

EXAMPLE 

s 

2.9 

3. fJ 

3.2 

'3.4 

3.6 

3.8 

4.0 

4.101 

4.200 

4.299 

4.398 

4.497 

4.596 

4.695 

4.794 

4.907 

5.006 

5.105 

5.209 

5.303 

5.402 

5.501 

5.601.l 

5.798 

6.{680 

6.503 

6.785 

, 

prob. 

.0019 

• 00135 -= 1/BfJff . fffl11169 

.00034 .: 1/3000 . 01111116 

.00fl07 

.00003 ~ 1/33.000 

.0000206 

.0000134 

.0000086 

.0000055 

.0000035 ~ 1/30~.0110 

.00910022 

.011100014 .: 1/711,11100 

.0000008 = 1/1,25",900 

.00000046164 

.0001CJ0027741 

.0000tl016513 

.0'0000009736 

.00000005686 ~ 1/18 million 

.00000003290 -=1/30 million 

.flfl0110001850 

.00000001070 

.00001J000335 

.00000000060 

.00000000004 

.000000000"1 1/l~~.OA0 million 

Suppose an unknown cipher in four digit groups is being investigated and the question 

is whether it is reenciphered• or not. If it is the text can be expected to resemble 

random more than if it is not. We make a frequency count on the 10,000 groups and then 

determine how likely such .a distribution is by chance. If it is not likely we must 

seek an explanation. . . If 560 groups are counted and I fi, (fi-1)-= 76 then fl.: 2.41 Thi:'s give~ a sigmage s-= 56. The table shows that we would have to repeat this procedure 

about 120 million times on random material to get a like result. We can say that this 

result is unlikely by chance and that an explanation is called for. The obvious one is that there is no reencipherment, or that it is very feeble. Tests to check this 

further hypothesis can be quickly dP.vised. 

•See Gaines "Elementary Cryptanalysis" page 2. '/ 

- 12 -

: 

· ..." 
REF ID:A66796 

IX TO DETERMINE WHETHER TWO ALPHABETS ARE IDENTICAL ALPHABETS 

Assume that a complex cipher using secondary alphabets has been analyzed and reduced to 5~ alphabets, There are only 26 possible secondary alphabets, so some of 

these 50 alphabets can be combined. Visual inspection is too inaccurate to be trusted, except within an abnormally large amount of text. 

Four sample alphabets are given in the- table following, A and B. 

Table "A'' -- Frequency Tables 

No. I No. 2. No. 3 No. 4 

A A A 2 A 2 

B 2 B B 2 B 

c 1 c c I c 1 

D D 1 D D 1 

E 3 E 3 E 2 E 

F 1 F F F 1 

G G G 2 G 

H 2 H ff H 

I 2 I I 3 I 2 

J 1 J 1 J J 

K K 2 K K 

L L 1 L L 

M 2 M .M 1 M 

N 3 N 2 N 3 N 1 

0 0 0 0 2 

p p 1 p p 1 

Q Q 1 Q Q 

R R 1 R R 

s s s s 3 

T T 1 T T 

u u u u 

v v 2 v v 

\\' w ,. 1 \f 3 

x x 2 x x 2 

y 2 y 2 y 1 y 1 

z 1 z z 2 Z· --- --- 20 20 213 20 

Table ''B" -- Reeeated Letters 

No.l-&-2 No.l-&-3 No.l-&-4 No.2-&-3 No.2-&-4 No.3-&-4 

A A A A A A 4 

B B 4 B B B 8 

c c 1 c 1 c c c 1 

D D D D D 1 D 

E 9 E 6 E E 6 E E 

F F F 1 F F F 

G G G G G G 

H H H ff ff H 

I I 6 I 4 I I I 6 

J J J J J J 

K K K K K K 

L L L L L L 

M M 2 M M M M 

N 6 N 9 N 3 N 6 N 2 N 3 

0 0 0 0 0 0 

p p p p p 1 p 

Q Q Q Q Q Q 

R R R R R R 

s s s s s s 

T T T r T T 

u u u u u u 

v v v ·v v v 

w y; w w w w 3 

x x x x x 4 x 

y 4 y 2 y 2 y ·? y 2 y 1 

19 Total 32 11 14 10 18 

coincidences 

Chance coincidences = 400 = ~ 15.4 

- 13 -
REF ID:A66796 

Line up two alphabets at a time and cross multiply the repetitions for each letter (see tablt> 11 8 11 ). "E" occurs 3 times in No. 1 alphabet and 3 times in No. 2. 

There are 9 pairs of "E's" in No. 1 and No. 2. Add the coincidences noted for a pair 

of alphabets. 

There are 2" letters in each' alphabet which gives 400 pairs of letters to deal 

with. Chance would give 400/26, or 15.4 repeated letters in two alphabets. The index of coincidence is the sum of the actual coincidences divided by 15.4. 

The indices are as follows: 

No. 1-&-2 1.23 

No. 1-&-3 2.68 (above the normal 1. 75) 

No. 1-&-4 .71 (alphabets No.l-&-3 must be identical) 

No. 2-&-3 .91 

No. 2-&-4 ,65 

X THE CROSS I. C. 

Suppose we have t\\o stretches of text of which the distributions are ~iven by 

Pl, P2, Pc and ql, q2, ---, qc 

c L" P.·=1,. I - L 

If these are placed one above the other the proba~1lity of an incidence at any one position is 

c 

z L=I 

and the I .C. is 

e.=cL"pi~ 

We can show that the expected value of g is 1. Suppose that we apply a permutation to the q's and recompute ( If we do. this for all C! permutations and av- erage them we get 

c 

Ert'J = ~.zt = ~.z c z Ah All I permo1ldhD~ p('rrm.la11"ns 

P· l 

I Q· 

-l 

(25) 

where q l' is one of the q's, depending on the permutation. Each q comes into a given 

position (C-1)! times. Thus 

E rt; = %1 

Notice that this 

If one of the samples 

For 

f = c ~ 

L qi.= (c-1) .' and 

c 

z P: 

l•I l 

Al p:rmut.t.lmr.:1 

2--

All pe-rmutalloru. 

q·' L 

result is independent 

of text is flat, say 

t =I 

p· Q· = /, 7t: l 

c = CfC-IJ• --c-,,-- LP: = I. 

I t 

of the roughness of either 

Qi= Ye ' then 

z Pj ::: t~I ::: I 

distribution. 

If both samples are very rough, then' fluctuates 1•.idely as the q's are permuted. 

The quest ion aru=es, how wide is the distribution of ~ ? 

- H -

(26) 
.• 

REF ID:A66796 

A standard measure is the "variance" 

where ~ is understood to mean the .sum over all possible permutations of the q's. 

Then c c 

Ere)=%12J 22.L°P· q P· q. T l= I j = I L l j '} 

.: %t ~ ~P· p· . _Lqi q. 

}'=I L j I l; I T 

The term 2-" qt q. ,can be evaluilted lfi each 

7 ') 

We will use 

c P=c L p.2 I L 

and 0 = C Z qi 2 

as the l.C.'s of the two samples. C 

For itj zq. q. = (c-2)' ~ q. ·q. 7 Lj frf'"7 L j 

of 

c 

-= rc-211 z qi 

c 

> q·= (c-2 )I tfJ 'J 

c 

~Q:(l-q,.) Ft I ~ t=I 

c -= (c-2).'(;

1 

(qi q{) .: (c- 2) .' (I - % ) • 

c 

the 

For i .: j Z q / = ( c - I) I x = ( c - I)/ %. r t. =I 

Thus (29) becomes' 

cases L -% j 

2 c 

P: (c -2)1 ..£:2- + ~c,X°. p/ (c -I}/ I . c t=I 

2 fk, 

c2 = /c1 

c c (c-2)1.c~Q L LPL Pj+ cJ.trc-1)/ ~c L=/ j:ft 

and i = j 

% 

c2 . = :i-' (c- 2; 1 c-o c-P +c~, (c-I)/ % ~c = (c-o}_(~~':..! __ + r; P 

· C -C C (C- I ) C 

= c 2 -CP- CQ I- PQ 

c ( c- 1) 

= c2- f.!:_:::_t;_q_!:__f_q_t:_ ____ _ 

C (C-IJ 

+ 

= __ <;__-:!' :- o_ +_ f._r; __ _ 

C-/ 

- 15 -

(27) 

(28) 

(29) 

(30) 

(31) 

' (32) 
REF ID:A66796 

Then since Ere J = 1 , we have 

= 

C-P-Q + PO - I 

C- I 

C-P-Q f PQ - C + I 

C-1 

PQ - P- Q + I 

C-1 

(P-1)(0 - I} E -------- -- ---- -- ----~-~! __________ J 

This says that the square of a standard deviation a-- is the. product of the bulges 

over c-1. t-1 

5 = \11---:(~P=-1=) =ro=-=, 1= = ( e -I ) 

C-1 

V-c-1 

(P-1) (0-1) 

a measure of the significance which can be judged from table I. 

IS 

The function t' 

lions. 

can be used ,1s l me.1s:1re of c<lrrel.a t ion between t l"o d 1str 1buXI THE COINCIDENCE TEST USED TO ALIGN 

SECONDARY ALPHABETS INTO A PRIMARY ALPHABET 

(33) 

We give here a special appl1cc1t1on of the I.C. statistic. An actual problem from 

the elementary cour~e 1s u$ed. problem 4 of assignment 6. Special frequency distr1but ion tables •ere made of the sample lined up into 2fi columns. 1.e., lines of 26 letters 

each. 

This problem happens to be enc1pher~d by means of :i. V1genere table. the columns 

be1111$ used 1n success1onc;. Cnnsequently 1f the' cipher text is lined up 26 wide each 

column 1s enc1phcrl:'d by a monnalphabct1c substit~t1on. Each alphabet is a slide on 

that 1n fh1e next column. If \le knew the plain dnd cipher :=:C'quences the text could be 

d.:ocrypted. The problc--m 1s to recover these sequence's. Since the sequence is not alph:lbct 1ca l, adJact>nt frequency counts .as given 1n table C appear unrelated. But if 

~~ look at l~c row5 they must be related by being slides on each other. If we can es1abl15h tlH'SC.' sl1d·~S will hnve the cipher sequence. 

- lf; -
Table "C" -- Frequency Table of the Cryptogram 

Col 

Cip 

umn - her -

A 

B 

c 

D 

E 

F 

G 

H 

I 

J 

K 

L 

M 

N . 0 

p 

Q 

R 

s 

T 

u 

v 

w 

x 

y 

z 

. 

1 26 

1 3 

1 

2 

1 1 

3 

1 

4 1 

1 

......._ 1 ~ 

3 

1 

2 

2 

1 

4 2 

4 

1 

1 

1 1 

25 24 23 

3 

3 1 

1 1 

1 

1 2 2 

1 

1 

2 1 

2 

3 1 3 

2 

1 

1 3 

2 1 

3 3 

1 

1 2 

3 1 

1 1 

1 1 

1 

1 1 

1 

2 

22 21 20 19 18 17 16 

--

2 5 3 

4 4 1 

1 

1 2 1 1 

2 3 

1 1 2 

5 -~ ,_!_ 2 1 

1 2 

1 1 1 

3 1 

1 3 1 

4 3 2 

1 1 1 2 3 

3 3 

1 1 

1 

1 5 1 

1 2 4 1 1 

2 4 

4 

4 1 3 1 2 

1 1 1 

1 2 1 

2 1 1 

1 2 3 1 .1 2 

1 2 1 

15 14 

2 

2 5 

3 

1 

1 

1 

1 

1 

3 1 

4 3 

2 

2 

2 

3 1 

1 

·. 1 

1 

1 

13 12 11 10 9 8 7 

1 ·---5 2 3 1 

2 1 1 

7 4 

1 1 1 

1 1 2 1 

2 1 1 

2 I 1 1 

1 2 1 

2 1 4 1 

2 2 2 

3 1 3 

5 1 1 

1 1 2 ·2 1 --1 1 

1 4 4 

1 1 2 

1 3 1 1 

1 2 

3 5 

2 

1 1 3 2 

3 3 1 3 2 

1 4 1 

1 3 1 

2 1 1 1 

6 5 4 

2 1 

1 

3 

3 

1 4 5 

1 2 

1 2 

"i 1 

3 . 1 

3 

1 

1 

2 - 2 

2 

1 

1 3 

1 3 

2 

3 2 

1 

1 2 

2 

1 

3 2 

2 

1 2 

1 2 

1 

1 

1 

3 2 

1 

4 

2 

2 

1 1 

1 

2 

1 

1 

2 

2 

2· 

3 1 

1 

1 

Tot 

Lett 

25 

36 

1.8 

22 

25 

14 

26 

·17 

18 

22 

27 

2Cl 

22 

24 

16 

17 

16 

24 

21 

26 

19 

27 

13 

17 

19 

15 

al. 

ers 
REF ID:A66796 

By use of this special table, table "C", we can build up the cipher component 

used by matching these frequency distributions. In selecting distributions to match 

we want to obtain: "t 

(a) A maximum total number of letters involved (as the distribution will then 

be more reliable). 

(b) A distribution with a normal count (i.e., ·similar to normal alphabet). 

(c) A distribution without any pne letter of abnormal frequency (as this gives 

too much weight to one letter). 

When frequency distributions of two letters are properly matched, high should 

pair with high, low with low, blank with blank, etc. The mathematical value of each 

.relative posi.tion is found as follows: 

(a) With the two frequency distributions in question written on paper strips and 

slid one against the other, for any one position we cross multiply the frequencies in 

alignment, and then add the products of all these multiplications. This is the total 

number of parts or coincidences involved (see table ''D"). 

(b) Cross-multiply the total count of the distribution of t~e first letter by the 

count of the second letter. This is the total number of possible pairs of letters. 

Chance would produce one coincidence in twenty-six. Therefore, divide this product by 

twenty-six, which gives the number of expected chance coincidences. 

(c) Divide the number of the actual coincidences by the expected number of chance 

coincidences (that is, divide (1) by (2)). The resulting number is the Index of 

Coincidence. 

To prove correct alignment: 

(a) The index-for the given relative position of two distributions must be higher 

than for all other positions, with no close second. 

(b) The index shoul'd be l.5fl or higher (prefer~bly 1.75 or higher). 

(c) There must be only one acceptable alignment. 

Indeterminate results will be encountered in some cases, particularly with insufficient text. 

Table "E" gives the total coincidences at the various positions of one strip 

slid against another. 

From table "C"', it is seen that certain distributions have the following propertie~ (referring to our three desired properties): 

B (cipher) has a total of 36 letters, with 14 different cells involved. Its 

highest frequency is 5. Good. Approaches normality. Maximum text. 

V (cipher) has a total of 27 letters with 15 different cells involved. Its 

highest frequency is 4. Not good -- too flat. 

K (cipher) has a total of 27 letters with 13 different cells involved. Its 

highest frequency is 4. Not good - too flat. 

G (cipher) has a total of 25 lett~rs with 15 different 'cells involved. Its 

highest frequency is 5. Not good -- too flat. 

D (cipher) has a total of 22 letters with only lfl different cells involved, but 

its highest frequency is 7. Not good -- too peaked. 

T (cipher) has a total of 26 letters with 11 different cells involved. Its 

highest frequency is 5. Good. Approaches normality. 

A (cipher) has a totil of 25 letter~ with 11 different cells involved. Its 

hi5hest frequency is 5, Good. Approaches normality. 

N (cipher) has a total of 24 letters with 11 different cells involved. Its 

hi6hest frequency is 4. GoQd. Ap.proaches normality. 

B, T, A and N are the best choices. Match T, A and N against B, then match A 

and N against T, finally match N against A. One of these combinations should 

give a positive index of coincidence, and thus serve as a starting point. / 

- 18 -
1:~~l: i.':1:1" : II :wil:: '/::~\ff.; C<' t:1 '.'J) ff~ ~~~~~~~~~~~ 

I 

ITab le "D" --- Sliding StriEs 

Plain 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26: "B" Master Distribution 

Cipher B 

: 

Freq. 1 3 1 4 4 1 2 5 5 2 3 1 1 1 2: 1 3 1 4 4 1 2 5 

2 1 1 4 3 1 3 5 1 3 2: "T" set at 2 on the "B" 

T Master Distribution. 

1 3 3 , 2 5 3 2 1 2 1 2 

A 

I-' 1 3 3 4 3 1 1 2 2 2 2 

IC N 

Plain 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26: T-1- -- N-5- Master 

Cipher T N D!l.stribut'ion. 

: 

Freq. 4 3 1 1 7 6 1 7 3 1 5 2 5 4: 4 3 1 1 7 6 1 

1 3 1 4 4 1 2 5 5 2 3 1 1 1 2 

:B 

1 3 5 2 5 3 2 1 2 1 

:A 
Table "E" -- 'fable of Total Coincidences 

B = Master Distribution 

Chance 

Plain -1 2 3 4 5 6 7 8 9 llJ 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 CoinciCipher-B dences 

T -x 43 49 39 53 4t 40' 37' -- 61J 64 -- 39 36 

A -x -- 38 66 59 -- 42 -- -- -- 58 -- 42 35 

N -x -- 53 41J -- -- -- -- 43 39 63 33 

NOTE: The numbers 43, 49, etc., represent the successive 

"total coincidences", i.e., the sum~ of products of. 

• frequencies at successive points of coincidence. 

T = Master Distribution 

Plain -1 2 3 4 -5 6 7 8 9 llJ 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 

I Cipher-T 

A -x 32 --.28 29 42 31 51 43 -- 25 

ti) N tx --'28 51J -- 28 26 34 -- 34 -- 31 32 34 24 & 

A = Master Distribution 

Plain -1 2 3 4 5 6 1 8 9 10 11: 12 13 14 15 f 6 17 18 19 20 21 22 23 24 25 26 

Cipher-A 

N -x 26 28 26 . -- 43 34 27 27 29 27 23 

T - 1 , N - 5 = Master Distribution 

N 

Plain -1 2 3 4 5 6 7 8 9 llJ 11 ,12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 

Cipher-·r N - B -x x llJIJ - 123 - 80 78 74 82 75 73 89 96 69 

A -x -- 57 56 -- 61 -- -- 65 -- 94 -- 65 48 

,,-
I 

Table "F" -- Table of Coincidences 

Master Dist~ibution T-1 N-5 B-11 A-17 

Pl ain 1 2 3 4 5 6 7 8 9 1£1 11· 12 113 ~4 15 16 17 18 19 :l£1 21 ~2 23 24 ~5 26 Chance 

CoinCi pher T v I D N y u F p M B K H Q z E A L G x R J w s c 0 cidenT N B A ces 

K x 14~ - - x - - - - - x 17li - - - - x - - - - - - - - L:')r l:.!!H 

v x 181 - - x - - - - - x x - - - - x - - - - 14~ - - - 158 120 

D x x - 19" x - - 16~ - - x x - - - - x - - - - il.43 - - - - 94 

E x x 135 - x - - - - - x x - - - 19Cl x - - - 1413 - - - - - 102 

w x x - - x - - - - 12~ x x - - - x x - - - .. - 20fcl - - - 102 

G x x - - x - - - - - x x - - 143 x x - 19:l - 131 - x - - - UJ7 

R x x - - x - - - 1133 - x x - - - x x - x - 15S - x - - - 1£12 

M x x 133 - x - - - - 15~ x x - 144 - x x - x - x - x - - - 94 

J x x - - x - - - - - x x - - - x x - x - x 17' x - - - 90 

L x x - - x 144 - - - - x x - - - x x 154 x - x x x - - - 90 

s x x - - x - - lUl - - x x - - 110~ x x - x - .x x x 15~ - - 9£1 

c x x L17 - x - - - - - x x - - - x x - x - x x x x 172 - 81 

u x x - - x - U9 9£1 - - x x - - - x x - x - x x x x x - 81 

y x x - - x 153 - 93 - 96 x x - - - x x - x - x x x x x x 81 

I x x 121 - x x x 94 - - x x 0~ - - x x x x - - x x x x x 7.7 

H x x x - x x x - - - x x 11.~ - 86 x x x x - x x x x x 91: 73 

p x x x - x x x - 142 - x x x - - x x x x 116 x x x x x - 73 

x x x x - x x x 110 x - x x x - - x x x x 139 x x x. x x - 73 

0 x x x - x x x - x - x - x x - - - x x x x x x x x ll 7 68 

Q x x x - x x x - x 81 x x x 1£11:! - x x x x x x x x· x x x 68 

z x x x - x x x - x x x x x x 113 , .. ..... x x x x x x x x x x 64 

F x x x 72 x x x 87 x x x x x x x x x x x 1X x x x x x x 60 
REF ID:A66796 

BUILDING UP THE CIPHER COMPONENT 

By utilizing the principles describ~d in the previous sections, we can build up 

the cipher component. Take B (cipher) as the master distribution, since it is accepttable and contains the highest count. Copy the frequencies of· B (from "C") at the 

bottom of a strip of paper, and repeat this sequence to the right. -Over the first 

sequence write the numbers 1 to 26 as shown in table _"D". Under No, 1 write the 

letters"B". The numbers represent the various unknown letters of the cipher component. 

Make similar master distribution strips for T and A. Next, copy the distribution of 

T <cipher) (from table "D") at the top of a strip of paper. Only one sequence is re- quired for this strip, and the numbers are omitte.d. Indicate the space corresponding 

to column No. 1 (table "D") by the letter. T (see table "E"). In a like manner make 

strips for A and N: · 

Note: The letter on each strip is an indicator to mark column No. 1 for that 

letter. When strips are properly-aligned, the indicators show the relatlve 

positions of these letters in the cipher component. The student is advised 

to prepare strips for himself and follow these processes. 

First, match T against B. As no two letters can occupy the same position 

in the cipher component, begin by setting the T indicator at No. 2 on the B master 

alphabet. . Note the coincidences.. Next, slide 'f to Ho. 3, and note the coinciden~es. 

Continue this process to No. 26, and record the succesive coincidences in tabular ~orm 

(see table ''F"). In many cases lack of good coincidences will be obvious by inspection 

tion and the count need not be made. In this way we discover that B and T give high 

indices.of coincidence in two different alignments (indices computed in accordance 

with_rule in page 23). 

Index of B (1) - T (7) §J. • 1.77 (good) 

36 

Index of B (1) T (11) §f! = 1.67 (good) 

36 

All other alignments give such low indices that they can be at once eliminated. The 

above two indices, however, are both high enough to be significant, and as the second 

is so close to the first, it cannot be disregarded. 

There can be only one acceptable point of coincidence; therefore, it is necessary to 

match A against B, and·N against B, to see if more conclusive results can be attained. 

Index of B (1) - A (5) .6.6 .. 1.89 (excellent) 

36 

Index of B (1) - A (7) ~ .. 1.69 (good) 

35 

Cother alignments are eliminated) 

Index of B (1) - N (21) jiJ • 1.91 (excellent)' 

33 

Index.of B (1) - N (6) -Sa • 1.69 (fair) 

33 

(other alignments are eliminate~) 

- 22 -
REF ID:A66796 

Since there is no outstanding coincidence with ''B" as the "master-alphabet", try 

"T'' and "A" as the ''master-alphabet.,: · 

Index of T (1) - A (17) .5..1 = 2.04 (excellent) 

25 

Index of T (1) - A (19) ~3 

' 25 

1. 72 (good) 

.Index of T (1) - A (11) ~2 = 1.68 (good) 

25 

Index of T (1) N (5) ,..5.fl = 2.08 (excelknt) 

24 

index of T (1) - N (12) .3.i 1.42 (poor) 

(16) 24 

(26) 

Index of A (1) - N (15) .i3. 1.87 (good) 

23 

Index Of A (1) - N (17) .3.4 = 1.48 (poor) 

23 ' 

The most certain combination is T-(1) - N (5), and there is no doubt as to its 

correctness. This located "N" relative to ''T" in the cipher compont'nt, and allows us to consolidate their frequencies. 

For a new master distribution add the frequencies of T (at space No. 1) to those 

of N (at space No. 5), (see table "E"). Match ''B" and "A" against this new 111astt-r 

distribution: 

Index of T (1) - N 

Index of T (1) - N 

Index of T (1) - N 

Index of T (1) - N 

Index of T (1) - N 

Index of T (1) - N 

"B" and "A'' 

but ion" as can now be 

follows: 

:Plain - 1 

:Cipher - T 

:T Ir. 

B 

A 

Plain - 14 

Cipher 

T Ir. 1 

B 1 

i\ 1 

(5) - B (11) 

(5) - .B (7) 

(5) - B (26) 

(5) - A (17) 

(5) - A (15) 

(5) .- A (19) 

consolidated 

2 

4 

2 

3 

3 

3 

3 

2 

4 

1 

' 

12.3 1.81 

69 

.lJlil 1.45 

69 

16 .• 1.40 

69 

.9.4 

48 

.25 

48 

.25 

·48 

with 

5 

N 

1 

1.96 

1.35 

1.35 

"T" and 

6 

1 

7 

1 

(good) 

(poor) 

(poor) 

(excellent) 

(very poor) 

· (very poor) 

"N" for th(' 

8 9 10 

1 2 

1 

15 16 17 18 19 20 21 22 23 

7 3 1 5 2 

4 4 1 ·2 

2 1 3 3 

final ''mast l'r 

.. 11 12 13 

7 6 

1 3 

2 

24· 25 26: 

5 4: 

5 5: 

2 5: ~~~~~~~~~~~~~~-

- 23 -

distri-
For 

REF ID:A66796 

This locates "B" and "A" relative to "T'' and "N" in the cipher component, in addition 

to giving the combined f1equencies of all four letters. 

1:1641.! MASIEB DISTRIB:L!!IQli 

:Plain .1 1 2 3 4 5 6 7 8 9 1fl 11 12 13 

:Comp. 

:Cipher - T N B 

:Comp. 

:Comb. 9 8 1 1 1 1 1 3 10 9 

:Freq. 

Plain 14 15 16 17 18 19 20 21 22 23 24 25 26: 

Comp. 

Cipher - A 

Comp. 

Comb. 3 2 4 12 7 1 8 4 12 14: 

Freq. 

Analyze the preceding steps. T gave two possible alignments with B, and, as we now see, the incorrect position gave the higher index. N also gave two possible 

alignments with B. (B was at fault due to its erratic letter distribution). However, 

when T and N are combined, giving twice as manY. letters in the master distribution, 

B fitted in with only one possible alignment. 'Adding 8 and A gives twice as man)' 

letters in the master distribution and this should make future results even more positive. The master distribution (of UJ0 letters or more) should approximate a normal 

frequency distribution and will give a standard to which all the other distributions can be referred. Hereafter, variations in the highest iqdex of coincidence will be 

due entirely to letter distribution of the various distributions themselves." 

example: 

If the highest index.is 1,7 letter distribution is normal. 

If the highest index is 2.0 high frequency letters predominate. 

' If the highest index is 1.4 the intermediate and low frequency letters 

predominate. 

Therefore, when matching the remaining letters, we can accept the highest index of 

coincidence as establishing coincidence, unless the second highest is practically the same. 

Continue the matching process and the reconstruction of the cipher component, notfng 

that T, N,· 8 and A are already located and thus may be deleted at once from further 

test. Begin with the letters of the highest frequency, as they should give the most 

positive results. When a letter is placed, delete this location from further test, as two letters connot occupy the same space in the cipher component. 

Letters are added to the cipher component in the following order (see table "F"): 

"Master alphabet" T (1) - N (5) - B (11) - A (17) 

K (12) 

v (2) 

D (4) 

D (8) 

E (16) 

w (23) 

G (19) 

~= 

1.46 " (poor - but acceptable) 

1,51 (poor - but acceptable) 

2.05 (excellent) 

1,76 (goQd)(D - ~ot certa~n) 

1.86 (excellent) 

1.96 (excellent) 

1. 80 (good) 

With; this many values a key-word (if any) sequence' could be completed by 

inspection. In this case, the partially reconstructed cipher component 

gives no suggestion of a key-word sequence. 

- 24 -
REF ID:A66796 

R (21) 1,55 (fair but acceptable) 

M (10) 1.65 (good) 

M (14) 1.53 (M - not certain) 

J (22) 1.89 (excellent) 

L (18) 1.71 (good) 

L (6) 1.60 (fair)(L - not certain) 

S (24) 1.77 (good) 

C (25) 2.12 (excellent) ' 

U (7) 1.47 (poor but acceptable) 

Y (6) 1.89 (excellent) 

~: This throws out L (6), but leaves L (18) as correct. 

I (3) (fair) 

I (13) 1.42 (poor)(I - not certain) 

H (131 ~.63 (good) 

1!..Q!!!.: This throws out I (13) and leaves I (3) as correct. 

P (9) 1.95 (excellent) 

X (20) 1.90 (excellent) 

O (26) 1.J2 (good) 

Q (14) 1.59 (fair and acceptable) 

Note: This throws out M (14) and leaves M (10) as correct. 

Z (15) i.77 (good) 

F (8) 1.45 (poor but acceptable) 

F (4) 1.20 (very poor) 

F (8) is correct and D (4) is correct 

The cipher component has now been completely recovered . 

Note: 

. The process described above has actually built up the complete squaredcipher-table of a modified Vigenere table (it remains only to recover the 

plain component to complete the Vigenere table). We have written down 

the cipher component rather than the complete-squared-table merely to save time and effort. 

XII THE ROUGHNESS OF MlXED TEXTS 

What happens when two different distributions are 'mixed? -As a simple case, let us suppose we mix some text of I.C. ?'with flat text in the proportions R: (1 - Rl. 

Then the ith letter has probability, 

and the I. c. is 

c ±, 

, ( P, R + (I - R) ~ } 2 

c 

= R 2 7 - R2 + I = I -f ( 'Y - I) R 2 . 

- 25 -

(34) 
' 

REF ID:A66796 

That is, the rough text contributes its bulge in the proportion a2. 

Now as a more complicated case suppose that we mix two rough texts in the 

proportions R: (1 - R). Suppose further that the distributions are P1, P2 1 Pc 

and q1 , q2 , ---, qc and C? p;_2: p I C 2: q/: Q 

Then the mixture will have as probability of the ith letter Pi R + Qj (1-R) 

and /' = c 2 ( P1..R +Qi (I- R) ) 2 

::PR2 + 2R(l-R)c~p,-.q. + Q(l-R)'. L__ L L (35) 

The expressio~ c L Pi Qi :: e we have examined before I and seen ;o be a measure of the correlation of the distributions. Since the expected value of l$ is 1, 

the exp~cted value of ')' will be -

£ ( Y):: PR'+ 2R ( 1-R) + Q (I - R )

2 

::R2 f- (P-l)R2 +2R-2R2 + (!-R)2 + (0-1) (!-R) 2 •· 

::/ + (P-l)R 2 f (Q-l)(l-R) 2 • 

Here again each contributes its bulge in proportion to the square of ite weight. 

Now that we have seen how the argument goes, we can a mixture of K samples with distributions Pil• Pi2• ---, 

generalize this result to 

Pie• 

and ~:: C ~ P· .2 

j=/ _LJ 

the I.C. of the ith sample, 

which we will suppose present in the proportion Ri* -:t: R· 

The mixture will have 

p· j 

so that its I. c. is 

c K K 

the Jth K 

:: 

~ 

letter 

Rt 

present in 

PL j 

P. .. )' 

'1 

= c .LL°~" R.· L Pij R,, PLj j=I i=I L =I 

K K c 

= ?. z R• L RL c -L P;j '::/ L= I j:: I 

- 26 -

the 

~ j 

t:/ L 

proportion 

. 

:: I 

(36) 

I 
The internal sum is the measure which we will designate by 

Notice that ~ii =. Yi 

K K 

REF ID:A66796 

of the correlation of the ith and L th sa~ples, 

c 

t:.,·L = c L' Pz . P. . ':/ j Lj • 

is the I~C. of the rth sample. 

Now ")'becomes /'=L LRj i=I L=/ 

K K 

=L • LR· • L L= I L It 

I( ~ =? L._ 

1.=/ LIL 

R· L 

Since E (~L ) = I 

K I( 

E (")')= .L .L 

J=/ L=I. 

K K 

= :2: R· I. .L 

t =I L=I 

K 

LR' 2 

. l 

t =I 

we have 

I( 

'R· l RL + z ( ')'; L - I ) 

i. =/ 

K 

Rl + 2 ()/.·-/) R·2 I. 

i.=I 

E(J')= I +- Zrx-11 R·2 

i=I I. L 

Again each sample contributes its bulge according to the 

- 27 -

R·2 L 

square of its presence. 

(37) 

(38).