CONCURRENCES, OR SIMILAR ACTIONS 

I NAME OR TITI.E CIRCULATE 

ORGANIZATION AND LOCATION COORDINATION 

2 FILE 

INFORMATION 

3 

4 SEE ME 

SIGNATURE 

ORGANIZATION AND LOCATIO • TELEPHONE 

·DD FORM 9 5 ep aces DA AGO Form 890, 1 Apr cs, and .A.FBQ I FEB 50 Form 12, 10 Nov 47, whieh D1B.7 be uaecL 
' . REF ID:A66757 
MEMO ROUTING SLIP J:<.f Jf Nil.-~ ;,~--..:.~P~LS. DISAPPROVALS I I CONCURRENCES. OR SIMILAR ACTIONS • 

1 NAME OR TITLE INITIALS 

ORGANIZATION AND LOCATION DATE 

2 

3 

4 

REMARKS 

p y. t'a."""' t>a,. ( '11 K ~ (Jt!:I ::J .S 

tl ioou'f"· The. al4ssr.J:e4f-t1..,. •( 

~ tt ~.S ~ .:J sf-"""' s- '' N h yew e ~ ' s 

+" -,, h7 hOt CO~i.Ntt S5t II~ t!_fAPc..i~ ei 

CIRCULATE 

COORDINATION 

FILE 

INFORMATION 

NECESSARY 

ACTION 

NaTE AND RETURN 

SEE ME 

SIGNATURE 

wArrA"'-\ ~~.scch'oa fj ~CA. ~ $e?ltj.S 

/haf :J·Pc.t. a.~,/. i,,,,~sel-P A,,r~ 

!IA~ 0,\A.f'j CJCA..IS' wk1 h4(/L . .:Set!!CA. ~~ 

f>Oi (J4Y A.wd as ;/A Y' 7h .e. ill. ~te.I 

~II" tJ.l~ssnhJ<t.A'b 1.S eo~cFJfl'u4d.1 ::f"c.1. 

ca..,. Jue(' ~ f' D~ f-u.1e ./,.., :j "a r.s tt-1 t/L s. 

I 

·~~~:;;:::-~~~~~~,;~r ORGANIZATION AND LOCATION TELEPHONE 

FROM NAME OR TITLE ' ~ 
1 NAME OR TITLE -

2 

3 

4 

ROM NAME dll TITLE -

REF ID:A66757 

' -

~ 

I • 

NECESSARY 

ACTION 

llOTEAND 

RETURN 

"SEE ME 

- SIGNATURE 

. DD I ~,~.50 9 4' REPLACES NME FORM 94 I FEB. WHICH !!AY IE USED ........... - * 
- ---------~-------------· 

.. 

'\ Excursus on Randm J 

28 May 1954. . .· . ~ .. .. . by H. Campaigne 

Many cipher systems depend on a stream of' 11 random11 information, 

called "key". This concept Of random is a very elusive one. Random 

can be defined to a certain approximation in mathem.a~ical. te:nns, and 

this approximation can be tightened to any extent 0ne is willing to 

undertake, rut it is still an approximation to- our elusi~e concept. 

A dietionary gives for "at randan: without aim, direction, rule, 

of method; haphazard, aimless; irregularly". It lists as antoll1Ill8, 

"planned,, designed, considered, deliberate". · To the cryptologist it 

means "unpredictable". Mathematically it is a. process, not a finite 

sample 1 which is random. ·By a proces~ I mean a procedure which. on 

demand will. produce digits indefinitely 'such that each digit accurs 

1:..... of the time, each possible pair of digits occurs L of the time, 

10 . . 102 

and so forth, until for sane n each of the ltfl ~ombinations of n 

letters occttr .L of the time. Clearly in a practical ~ase we can 

. lOn 

test only a finite sample, and must limit our testing to some maximum n • 

It is the finiteness of the number of statements lthich makes this 

definition fall short of the ideal of random. For example, suppose we~. 

take n = 3; and have each q.igit occv L of the time, each pair _!_, . 10 100 

and eaclil ·triple __!... of the time. Now :i.:f we take the follo'wing example 1000 - . . 

we see that it· satisfies the three critecla approximately but is perfectly pre~ctabl~ from·a.n:y 4 consecutive di&its •. This pro~ess is 

defined by induction. Let ~ = <1zi-4 + ~-'.3 ·{10), and select dv d2, d3, 

~~ d

4 arhl:trarily. , ~his process al.most p\it not ~it~ fits tht 3 criteria. 

I 

The mathematical rule given above is tao rigid, of course. One 

can change it to read thus: In any sample of M diyts the number of 

occurrences .of a s:Pecific n-nome will differ from .1L by sY Mn .. C1t 

lcf 10 

more in ~~y a small number of cases. Here S is a suitably chosen 

number, sai 3, and the number of exceptions te the rule is ch95en 

accorciingly, say once in lo,opo. This definition is harder to apply~ 

If we apply it to our c0W1ter-example we find tha.tv"passes for n = 3 

.or less. Here is another sequence t't 

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

·. 
·, 

which is also uniqu.ely detennined by amy 4 adjacent digits (and the 

·rule of genez:ation). · 

. . · · The import.ant property for a cryptanalyst is predictability. If 

· fram a small· stretch he can predict the rest, then no other property is 

of a:ny- significance; the cryptanalyst c~ guess at plain-text, derive 

key; predict more key, and ve~y his guess. Therefore the problem of 

reading any message is solved, in theory a:t least. Even if the pre-. 

'. diction is only statistical the cryptanalyst can use the in£ormati9n. 

He can do this in two ways: He can search for l 11 cliches 11 er long repeats 

in the key.· Or he can use the fact, if it is a fact, that digits tend 

to. be alike~ 

Now this last is usabl~. even if the key came from a stochastic 

process which is unpredictable-except that the digits come with various 

prob°a:bilities. Thus we see that the ·mathmiatical· definition givel'l above· 

is a necessary co:ndition for secure key.· Whether it is sui'ficient is . · ·' 

another question. ' · " '-

. 'On ·the other hand key can -be predictable and yet be "secure im the 

following· sense. If the law of generat:i,on of the key (assumed· to be. . 

reproducible by·the legitimate recipient) is unJa?.own to .. the cryptanalyst, 'and it h.e is unable ta reconstruct .it ·fr.om the data a:t hand, 

then so far. as he is comaerned it is, unpredictable •. Taus 11 prediatqble 11 

is a subjective te:nn.. · It is this theory-.which has been widely used by. 

cryptographers, who ~tternpt to design laws .. af generation· sa complex 

that they believe reconstruction is virtua.P-y. im.possil;>le. · Many U. s. · 

systems are based on this· theory, and th,e2.~~y is tre<lll:eiit.ly. ref'erre~ 

. to as "random1t · .' · · . · . • • 'ff',' I -G 00 

To return to the ·mathematic~ definition ol random. - .Thls definition 

has two drawbactts froin the viewpoint of the cryptographer~ ·One is that 

it says nothing about predictability, and the other is that f'or true 

random the definition states an infinite number of conditions. It is . impossible of c01:1rse for any periodic process ta satisfy. all these 

conditions, ~d ·it is equally impossible to set up a law of generation 

(reproducible) whi'ch will satisfy all of them. It is not practicable 

for .a ltaw· of generation to satisfy more than a few of the conditions. 

A standard procedure for a cryptanalyst is to check his material against 

these conditions one at a time, the silliplest first. Experience has · 

shown that usually some of the simpler conditions ~re not satisfied., 

and the way these ·conditions are violated generally gives clues to the 

\·law of generation. Only the work' of.cheeking the conditions, and the 

l small size of the sample of key' prevents. this from being· a general 

solution. 

2 

.'' 

·,~ 
REF ID:A66757 ---------------

,., We see then that the ceypt,ogra.pher is on the defensive,, trying to 

protect his material on each of an infinite number of sides with only 

finite, even severely ll.IDJ.ted, resources. The cryptanalyst, be:uig on 

the offensive, has only to fJ..nd a side wtu.ch is undefended. 

r 

t:Q~~i_p~a·'Q t b~L-- "".... "'("I .I 

3 

1 

, .1