Celebratio Mathematica

An­drew Gleason was a seni­or at Yale on Decem­ber 7, 1941, when the Ja­pan­ese bombed Pearl Har­bor. He ap­plied for a com­mis­sion in the navy; upon his gradu­ation the fol­low­ing June he re­por­ted to their cryp­ana­lyt­ic ser­vice: the Of­fice of Chief of Nav­al Op­er­a­tions (OPNAV), 20th Di­vi­sion of the Of­fice of Nav­al Com­mu­nic­a­tions, G Sec­tion, Com­mu­nic­a­tions Se­cur­ity (OP-20-G). There he joined a group of eight to ten math­em­aticians work­ing to crack en­emy codes. The group in­cluded Robert E. Green­wood and Mar­shall Hall, Jr., one of Andy’s Yale pro­fess­ors. The Na­tion­al Archives con­tains de­clas­si­fied doc­u­ments de­scrib­ing much of the war­time work of OP-20-G. We found there a set called En­igma Stud­ies [e2], which de­scribes the group’s con­tri­bu­tions to the at­tack on the Ger­man En­igma ma­chine. These doc­u­ments show­case that part of Gleason’s work which we will de­scribe.

The En­igma ciphers presen­ted di­verse and rap­idly mutat­ing chal­lenges. The Ger­mans used sev­er­al dif­fer­ent mod­els of the En­igma ma­chine. Each day they changed the keys on each of per­haps a hun­dred or so dif­fer­ent com­mu­nic­a­tions net­works. Three of those net­works were “Shark”, used by the At­lantic U-boat fleet; “Sun­fish”, by block­ade run­ners and the Ger­man U-boats in the Pa­cific; and “Seahorse”, for traffic between Ger­man navy HQ and their at­taché in Tokyo. Break­ing one sys­tem or one day’s traffic provided only clues to­wards break­ing the oth­ers, clues which were some­times mis­lead­ing. Sev­er­al times dur­ing the war the Ger­mans made sig­ni­fic­ant modi­fic­a­tions to the En­igma.

OP-20-G worked on En­igma in col­lab­or­a­tion with the Brit­ish crypt­ana­lysts at the Gov­ern­ment Code and Cypher School at Bletch­ley Park, in par­tic­u­lar, with “Hut 8”, whose most fam­ous mem­ber was Alan Tur­ing. Shortly be­fore the U.S. entered the war the Brit­ish code break­ers began teach­ing their Amer­ic­an coun­ter­parts about the En­igma prob­lem: the gen­er­al the­ory and nota­tion (largely due to Tur­ing), a host of par­tic­u­lar solu­tion meth­ods, and the design of a spe­cial-pur­pose elec­tromech­an­ic­al com­put­ing ma­chine, the “Bombe”, which car­ried out one of the steps of the ar­du­ous con­strained tri­al-and-er­ror solu­tion pro­cess. Some of these les­sons the Brit­ish had learned from the Poles just be­fore the war; some they had de­veloped dur­ing the first two years of the war. At about the time the U.S. entered the war the Ger­man navy began us­ing a four-wheel mod­el of the En­igma ma­chine, against which the ex­ist­ing Bombes (de­signed for at­tack­ing three-wheel En­ig­mas) were com­par­at­ively in­ef­fect­ive. This ended the Al­lies’ abil­ity to read Shark in a timely man­ner dur­ing 1942 and early 1943, with dev­ast­at­ing con­sequences to Al­lied ship­ping.

In Novem­ber 1942 Tur­ing vis­ited the U.S. to as­sist the Amer­ic­ans in mas­ter­ing Bletch­ley’s meth­ods and to con­sult on the con­struc­tion of the Amer­ic­an Bombes de­signed to at­tack the four-wheel En­igma. An­drew Hodges’s bio­graphy of Tur­ing dis­cusses Tur­ing’s re­port back to Bletch­ley, in which he ex­presses some dis­may that the Amer­ic­ans really had not grasped the Brit­ish work-sav­ing al­gorithmic ideas, re­ly­ing in­stead on tech­no­lo­gic­al overkill. Nev­er­the­less, he was im­pressed with the math­em­aticians be­ing hired at OP-20-G, in par­tic­u­lar “the bril­liant young Yale gradu­ate math­em­atician, An­drew Gleason” ([e3], p. 243). Hodges relates an an­ec­dote from this vis­it:

Gleason and Joe Eachus “looked after Alan dur­ing his peri­od in Wash­ing­ton. Once Gleason took Alan to a crowded res­taur­ant on 18th Street. They were sit­ting at a table for two, just a few inches from the next one, and talk­ing of stat­ist­ic­al prob­lems, such as that of how to best es­tim­ate the total num­ber of tax­icabs in a town, hav­ing seen a ran­dom se­lec­tion of their li­cense num­bers. The man at the next table was very up­set by hear­ing this tech­nic­al dis­cus­sion, which he took to be a breach of ‘se­cur­ity’. …Alan said, ‘Shall we con­tin­ue our con­ver­sa­tion in Ger­man?’ ”

At first OP-20-G was the ju­ni­or part­ner to Hut 8, but later it took the lead in at­tack­ing Seahorse. A re­cent pa­per [e6] de­scribes the Seahorse story in con­sid­er­able de­tail. We draw on that ac­count. The Hut 8 team had failed to solve Seahorse be­cause traffic ex­tern­als con­vinced them that en­cryp­tion was be­ing done not by a stand­ard nav­al En­igma ma­chine but by a sim­pler ver­sion of En­igma. In March 1943 the prob­lem was turned over to OP-20-G. Their ana­lys­is re­vealed new struc­ture in the traffic that al­lowed them to re­ject the hy­po­thes­ized sim­pler ver­sion of En­igma to cor­rectly dia­gnose an un­der­ly­ing nav­al En­igma and to spe­cify a menu (i.e., a pro­gram) for the nav­al Bombes so they could ef­fi­ciently read the traffic.

Read­ing the first-hand ac­counts of this work in the En­igma Stud­ies E-2 and E-4, one can share the ex­cite­ment, the frus­tra­tions, and fi­nally the ela­tion when suc­cess was achieved. Green­wood’s “His­tory of Kriegs­mar­ine at­tack” (pa­per 6 in E-2) de­scribes how the group first dis­covered the work­ing of Seahorse’s “in­dic­at­ors”, which told the mes­sage re­cip­i­ent how to set up his re­ceiv­ing En­igma ma­chine. These were ap­pen­ded to the mes­sage, en­cryp­ted in a “throw-on” cipher. The stand­ard meth­od of at­tack re­quired in­ter­cep­tion of a large num­ber of mes­sages from the same day. A suc­cess­ful at­tack re­vealed which set of four wheels was be­ing used in the ma­chine and the set­ting used to en­cipher all the in­dic­at­ors. One could then de­cipher the in­dic­at­ors and in turn use them to de­cipher all the day’s mes­sages.

Mar­shall Hall no­ticed an in­ter­est­ing fea­ture of the throw-on in­dic­at­ors. On a giv­en day the set of first let­ters of en­cryp­ted in­dic­at­ors for Ber­lin-to-Tokyo mes­sages was dis­joint from the set of first let­ters for Tokyo to Ber­lin, but the sets changed from day to day. Gleason came up with and stat­ist­ic­ally tested a simple hy­po­thes­is ex­plain­ing this, namely, that the wheel set­tings — the un­en­cryp­ted form of the in­dic­at­ors — star­ted with let­ters A–M for mes­sages from Tokyo to Ber­lin and let­ters N–Z for the op­pos­ite dir­ec­tion.

In “Kriegs­mar­ine in­dic­at­ors” (pa­per 5 in E-2) Gleason, Green­wood, and Hall show how this struc­ture al­lowed one to de­rive ex­tra equa­tions, which led to much more ef­fi­cient Bombe runs. The prac­tic­al im­plic­a­tion was that far few­er mes­sages needed to be in­ter­cep­ted in any one day to be able to work out that day’s key. In Au­gust 1943 a Bombe run at Bletch­ley us­ing these ideas broke the first Seahorse mes­sages. This con­firmed the mod­el for the un­der­ly­ing En­igma and its in­dic­at­or sys­tem and veri­fied the cor­rect­ness of their at­tack pro­grams. This con­cluded the re­search phase. The prob­lem was then turned over to a de­vel­op­ment team. Us­ing the newly avail­able four-wheel nav­al Bombes and the spe­cial tricks dis­covered for Seahorse, they were able to read Seahorse sporad­ic­ally in 1943 and al­most con­tinu­ously in 1944 and 1945, res­ult­ing in the de­cryp­tion of thou­sands of mes­sages.

An ex­cel­lent dis­cus­sion of the ap­plic­a­tion of group the­or­et­ic ideas to the solu­tion of En­igma prob­lems is giv­en in Green­wood, Gleason, Clif­ford, and Han­son’s “En­igma wir­ing re­cov­ery from the read­ing of a depth” (pa­per 7 in E-4, dated 19 April 1945).1 Sim­pli­fy­ing slightly, they re­duce the prob­lem of find­ing the four per­muta­tions per­formed by the En­igma wheels to one of solv­ing a sys­tem of sim­ul­tan­eous equa­tions in per­muta­tions. The right side of the \( t \)-th equa­tion is the per­muta­tion ef­fected by En­igma to en­cipher the \( t \)-th plain text char­ac­ter. These are as­sumed “known” (at least in part) by “depth read­ing”. The left side of the \( t \)-th equa­tion ex­presses the known way the En­igma ma­chine com­poses the un­known ro­tor wir­ings at time \( t \). The pa­per shows how this prob­lem can be broken in­to a series of sub­prob­lems of the form “giv­en sev­er­al per­muta­tion pairs \( (\pi_i , \sigma_i) \), find a single per­muta­tion \( x \) for which \( \pi_i = x\sigma_i x^{-1} \) for all \( i \).” In­ter­est­ingly, one of these sub­prob­lems is solved by ex­hib­it­ing an iso­morph­ism of a pair of labeled graphs. The ex­plan­a­tion, un­like most tech­nic­al En­igma ex­pos­i­tion of the era, such as found in [e1], is couched in stand­ard math­em­at­ic­al ter­min­o­logy.2 Ac­cord­ing to one mod­ern com­ment­at­or, [e7], the meth­od in this pa­per “is a lot more power­ful than the ‘Rod­ding’ and ‘But­ton­ing-up’ meth­ods de­scribed by Alan Tur­ing, mainly be­cause it al­lows re­cov­ery of the wir­ing even when the Steck­er is un­known.” The ex­pos­i­tion is both com­pel­ling and charm­ing. One can ima­gine one is listen­ing to the young Andy Gleason in some of the in­form­al asides:

The read­er may won­der why so much is left to the read­er. A book on swim­ming strokes may be nice to read, but one must prac­tice the strokes while ac­tu­ally in the wa­ter be­fore one can claim to be a swim­mer. So if the read­er de­sires to ac­tu­ally pos­sess the know­ledge for re­cov­er­ing wir­ing from a depth, let the read­er get his pa­per and pen­cils, us­ing per­haps four col­ors to avoid con­fu­sion in the con­nect­ing links, and go to work…. Note: the writ­ing of \( C^{-1} C^2 \) in­stead of \( C^1 \) is a whim of the writer. Please hu­mor him to this ex­tent….

The fi­nal page of the typescript (shown to the right) con­cludes:

The re­cov­ery of wir­ing from a depth can be a very in­ter­est­ing prob­lem. Let the read­er sur­round him­self with pleas­ant work­ing con­di­tions and try it.

 — as if this were a prob­lem in pure math­em­at­ics, not an ur­gent war­time en­deavor.

The mass pro­duc­tion of four-wheel Bombes led to dra­mat­ic suc­cesses against Seahorse and the oth­er nav­al En­igma prob­lems. Re­search then fo­cused on Ja­pan­ese ma­chine ciphers. A ma­jor achieve­ment of this ef­fort was the dia­gnos­is of the nav­al cipher Cor­al and the sub­sequent de­cryp­tion of Cor­al traffic throughout 1944–45. This re­quired, as in En­igma, a painstak­ing ex­am­in­a­tion of the traffic to find and ex­plain stat­ist­ic­al struc­ture and the design and pro­gram­ming of new spe­cial pur­pose ma­chines. Gleason’s math­em­at­ic­al con­tri­bu­tions to this work in­cluded the eponym­ous “Gleason crutch”, a meth­od for es­tim­at­ing ex­treme tail prob­ab­il­it­ies for sums of ran­dom vari­ables. It can be re­garded as a ver­sion of Chernoff’s the­or­em in large de­vi­ations the­ory, and like it, it is based on the idea of ex­po­nen­tial tilt­ing.

As the war came to an end, Gleason par­ti­cip­ated in ef­forts to sys­tem­at­ic­ally doc­u­ment the tech­niques de­veloped by OP-20-G and to set up a post­war cur­riculum for train­ing crypt­ana­lysts. He also par­ti­cip­ated in courses and sem­inars on both ap­plied meth­ods and math­em­at­ic­al found­a­tions, in­clud­ing (proph­et­ic­ally) one based on Pon­trja­gin’s new book on to­po­lo­gic­al groups.3

Gleason’s codebreak­ing work ex­hib­its some of his char­ac­ter­ist­ic traits. One is his ex­traordin­ary quick­ness in grasp­ing the heart of a prob­lem and re­think­ing how to solve it from first prin­ciples. He says of him­self, “I have al­ways felt that it’s more cru­cial for me to come to grips on my terms with the most ele­ment­ary as­pects of a sub­ject. I haven’t wor­ried much about the ad­vanced as­pects” ([e4], p. 88). He was par­tic­u­larly ef­fect­ive as a crypt­ana­lyst, be­cause (in his own words) he “learned to do something that a lot of pure math­em­aticians don’t know how to do…how to do quick and dirty math­em­at­ics. It’s an in­ter­est­ing knack to be able to make a quick ap­prais­al as to wheth­er there is suf­fi­cient stat­ist­ic­al strength in a situ­ation so that hope­fully you will be able to get an an­swer out of it” ([e4], p. 87).

Gleason’s in­sight in­to the math­em­at­ics un­der­ly­ing cryp­to­graphy was great­er than that of most of his col­leagues. Even dur­ing the war he pre­pared lec­tures and notes for them to help de­vel­op their un­der­stand­ing and work­ing know­ledge of the math­em­at­ic­al fun­da­ment­als. His OP-20-G lec­ture notes and ex­er­cises on prob­ab­il­ity and stat­ist­ics were later gathered up and ed­ited in­to a short text­book used for years in in­tro­duct­ory courses at NSA and sub­sequently re­prin­ted com­mer­cially [3]. We were amused to find that one of the ex­er­cises in the book is to es­tim­ate the num­ber of tax­icabs in a town, hav­ing seen a ran­dom se­lec­tion of their li­cense num­bers.

Le­gend has it that, in gen­er­al, the crypt­ana­lysts in World War II did not think much of the math­em­aticians down the hall, who were al­ways telling them what was wrong with their counts and sug­gest­ing “prop­er” stat­ist­ics, which in the end didn’t pro­duce plain text. But Gleason was dif­fer­ent. He was ap­proach­able. He listened care­fully to their prob­lems and ideas, and his ad­vice was al­ways use­ful.

After the war Gleason began his aca­dem­ic ca­reer at Har­vard. He was re­act­iv­ated in 1950, at the start of the Korean War, and served at the nav­al fa­cil­ity on Neb­raska Av­en­ue. Cryp­to­graph­ic sys­tems had in­creased in com­plex­ity, in­cor­por­at­ing di­git­al tech­no­logy that posed new chal­lenges and dra­mat­ic­ally in­creased the need for trained math­em­aticians. Many of Gleason’s col­leagues at Neb­raska Av­en­ue went on to sig­ni­fic­ant ca­reers at the newly formed NSA and in emer­ging aca­dem­ic areas of math­em­at­ics and com­puter sci­ence. These in­cluded Mar­shall Hall, Joe Eachus, Dick Lei­bler, Oscar Rothaus, How­ie Cam­paigne, Bill Blankin­ship, and Ned Neuburg. In the spring of 1951, Lt. Cm­dr. Gleason, Lt. Cm­dr. Hall, and Cm­dr. Miller4 were sent to vis­it math­em­at­ics de­part­ments around the coun­try to re­cruit math­em­aticians with ad­vanced de­grees. They found sixty to eighty. One of them, R. High­bar­ger, told us, “After a few weeks at train­ing school we loc­ated in a base­ment room next to the kit­chen grease pit at Ar­ling­ton Hall Sta­tion…. There, we took vari­ous CA [crypt­ana­lys­is] courses and a bunch of math courses, the best of which were taught by Andy Gleason.” Some twenty of these “ju­ni­or math­em­aticians” were to be­come the pro­fes­sion­al lead­ers of the na­tion’s crypt­ana­lyt­ic ef­fort in the 1960s and 1970s.

Most of Gleason’s ap­plied work dur­ing this peri­od re­mains clas­si­fied. In his spare time he worked on Hil­bert’s Fifth Prob­lem. He later said, “there wasn’t a single day that I didn’t think about it some of the time…. I made a real break­through on the prob­lem around Feb­ru­ary of 1952” ([e4], p. 91). R. A. Lei­bler drove Gleason to Prin­ceton to present a talk on his new res­ult at the In­sti­tute for Ad­vanced Study. It was snow­ing hard. Go­ing up Al­ex­an­der Road they were nearly hit when their car slid through a red light. Lei­bler told us that Gleason came in dressed in his navy uni­form. This caused some ini­tial sur­prise, which soon turned to ex­cite­ment and en­thu­si­asm. Gleason lec­tured all day.

After the Korean War, Gleason re­turned to the Har­vard fac­ulty but con­tin­ued as an ad­visor to the na­tion’s in­tel­li­gence and se­cur­ity pro­grams for fifty years. He served on the NSA Sci­entif­ic Ad­vis­ory Board from the mid-1950s through the mid-1960s, where he helped shape the NSA’s re­sponse to the evolving chal­lenges of the cold war. He con­tin­ued as an act­ive re­cruit­er for the NSA and for the Com­mu­nic­a­tions Re­search Di­vi­sion (CRD) of the In­sti­tute for De­fense Ana­lyses, of­ten writ­ing or call­ing the dir­ect­or to re­com­mend a math­em­atician who might be par­tic­u­larly well suited for an ap­point­ment to the pro­gram. He par­ti­cip­ated in NSA sum­mer re­search pro­jects (SCAMP) and in the form­at­ive tech­nic­al pro­grams of the CRD. He was a mem­ber of the first CRD ad­vis­ory com­mit­tee in 1959, then served from 1976 to 1979, from 1986 to 1988, and again from 2004 to 2006.

L. P. Neuwirth, writ­ing in 1992, re­called Gleason’s par­ti­cip­a­tion in the CRD pro­grams:

He in­vari­ably had something use­ful to con­trib­ute, and the work of oth­ers be­nefited enorm­ously, either dir­ectly or in­dir­ectly (some­times with at­tri­bu­tion, some­times without) from his ideas. His con­tri­bu­tions have in many cases been last­ing, and were made in suf­fi­cient gen­er­al­ity and depth that they still find ap­plic­a­tion 45 years later. His name is as­so­ci­ated with some of these no­tions…the Gleason semig­roup, Gleason weights, and the Gleason crutch… [his] 22 pa­pers in crypto­lo­gic math­em­at­ics span the time peri­od from 1945 to 1980. Their con­tent range is wide, and in­cludes al­gebra, com­bin­at­or­ics, ana­lys­is, stat­ist­ics and com­puter sci­ence.

Gleason did pi­on­eer­ing work in com­pu­ta­tion­al al­gebra in re­sponse to the emer­ging need for good pseu­dor­an­dom num­ber gen­er­at­ors and ef­fi­cient er­ror cor­rect­ing codes. In 1955 the Gleason–Marsh The­or­em [1]5 provided a meth­od for gen­er­at­ing ir­re­du­cible poly­no­mi­als of huge de­gree over \( \mathrm{GF}(q) \). (For any \( d \), one could gen­er­ate ir­re­du­cibles of de­gree \( q^d - 1 \).) In 1961 in a 10-page typescript [2] Gleason de­scribed al­gorithms he de­vised for factor­ing and ir­re­du­cib­il­ity test­ing of uni­vari­ate poly­no­mi­als over \( \mathrm{GF}(q ) \). Pro­grams im­ple­ment­ing these ideas had many years of util­ity. We do not un­der­take to com­pare Gleason’s un­pub­lished ap­proach to oth­er meth­ods soon to fol­low: Ber­lekamp (1967), Zassen­haus (1969), Can­tor–Zassen­haus (1981). For a re­cent his­tor­ic­al sur­vey of the field, see, for ex­ample, [e5]. Neuwirth con­cluded:

This un­for­tu­nately re­stric­ted list of some of the ideas he had and some of the areas to which he con­trib­uted per­haps sheds a little light on his many con­tri­bu­tions to a very much hid­den sci­ence, and gives some un­der­stand­ing of the un­usu­ally high re­gard in which he is held by the in­tel­li­gence com­munity… ([4], pp. 65–66).

Note on the ref­er­ences: [e2] is a nine-volume an­tho­logy of tech­nic­al pa­pers, com­piled at the end of the war, cov­er­ing all of OP-20-G’s En­igma re­search activ­it­ies. The volume titles are E-1, Click Pro­cess; E-2, In­dic­at­or At­tacks; E-3, Stat­ist­ic­al Stud­ies; E-4, Wir­ing Re­cov­ery; E-5, Bomb Com­pu­ta­tion; E-6, Du­enna; E-7, Mis­cel­laneous; E-8, Re­ports from Eng­land; and E-9, Bull­dozer. Each bears a Ra­dio In­tel­li­gence Pub­lic­a­tion (RIP) num­ber. Volumes 1 through 8 are RIP num­bers 603 through 610, and volume 9 is RIP 601. We will make avail­able on­line art­icles from E-2, E-4, and E-9 writ­ten by Gleason and his col­leagues.6

We are also grate­ful to R. Er­skine and F. Weierud for search­ing through the war­time di­ar­ies of OP-20-G and the his­tory of Cor­al, which they had copied at the Na­tion­al Archives. They loc­ated in­form­a­tion about Gleason’s activ­it­ies and for­war­ded many in­ter­est­ing items to us.