Википедија

Бил Тат

Razbijač šifri i matematičar

Вилијам Томас "Бил" Тат (14. мај 1917 - 2. мај 2002) био је британски разбијач шифара и математичар. Током Другог светског рата направио је фундаментални напредак у криптоанализи Лоренцове шифре, великог немачког шифарског система који је коришчен за тајне комуникације унутар Врховне команде Вермахта. Стратешка природа интелигенције добијене из Татовог кључног продора, у великом дешифрованју Лоренцових шифрованих порука, увелико је допринела, а можда и одлучно, поразу нацистичке Немачке[1][2]. Он је такође имао низ математичких достигнућа, укључујући и рад на темелјима из области теорије графова и теорије матроида[3][4].

Бил Тат
Пуно имеВилијам Томас Тат
Датум рођења(1917-05-14)14. мај 1917.
Место рођењаЊумаркет, Уједињено Краљевство
Датум смрти2. мај 2002.(2002-05-02) (84 год.)
Место смртиКиченер, Канада

Татово истраживање у области графова показало се од изузетног значаја. У време када је теорија графова још увек била примитивна тема, Тат је почео да проучава матроиде (уређене парове) и развио их у теорију проширујући рад који је Хаслер Витни развио око средине 1930-их[5]. Иако су Татови доприноси теорији графова имали утицај на савремену теорију графова и многе од његових теорема су коришћене да наставе напредак на том пољу, већина његове терминологије није била у складу са њиховом конвенцијалном употребом. Самим тим његову терминологију не користе данашњи теоретичари графова[6].

Детињство, младост и школовање уреди

Тат је рођен у Њумаркету у Сафоку. Он је био млађи син Вилијама Џона Тата (1873 – 1944), баштована, и Ени (1881 – 1956), кућне помоћнице. У Енглеској је похађао основну школу и са десет година освојио стипендију на Кембриџу. Године 1935. добио је стипендију за факултет природних наука на Тринити колеџу где се специализовао у области хемије и дипломирао са првокласним почастима 1938[3]. Наставио је са физичком хемијом као апсолвент али се касније пребацио на области математике крајем 1940[3]. Као студент (уз своја три пријатеља) први је решио проблем дељења квадрата на квадрате. Сва четворица су заједно створила псеудоним Бланш Декарт иза кога се Тат крио годинама[7].

Други светски рат уреди

Убрзо након избијања Другог светског рРата, Татов учитељ, Патрик Даф, предложио га је за ратни посао у Владиној школи за Кодирање и Шифру у Блечли Парку (БП). Интервјуисан је, и послат на обуку у Лондону пре одласка у Блечли парк, где се придружио Истраживачком Одсеку. У почетку, радио је на Хагелиновој шифри, коју је користила Италијанска морнарица. Била је то ротор шифрирајућа машина која је доступна комерцијално, па је механика шифровања била позната, а дешифровање порука захтевало само схватање како је машина постављена[8].

У лето 1941, Тат је пребачен да ради на пројекту назван Риба(енгл. FISH). Обавештајне информације су откриле да су Немци  позвали бежични телепринтер преносни систем  "Sägefisch" (sawfish – риба тестерача). Ово је навело британце да користе код Риба (енгл. Fish) за немачки телепринтер шифрирајући систем. Надимак Тани (енгл. Tunny - tunafish, туна) је коришћен за први не-Морзеов линк, и то је субсеквентно коришћено за Лоренцову СЗ машину и поруке које је она кодирала[9].

Телеграфија је користила 5-битну Међународну Телеграфску Абецеду Бр. 2 (енгл. ITA2)  Ништа се није знало о механизму шифровања, осим тога да је порукама претходио индикатор од 12 слова који је подразумевао ротор шифрирајућу машину са 12 точкова. Први корак морао је да бити дијагностиковање машина успостављањем логичке структуре и тиме функционисање машина. Тат је овде одиграо кључну улогу, недуго пре победе савезника у Европи 1945,  када је Блечли парк купио Тани Лоренцву машину за шифровање[10]. Татова истраживања на крају су довела до дешифровања Тани-шифрованих порука између немачке Врховне команде Вермахта (OKW)  у Берлину и њихових војних команди широм окупиране Европе, и допринеле су - можда по највише- поразу Немачке[1][2].

Дијагностиковање машине за шифровање уреди

Дана 31. август 1941, две верзије исте поруке су послате коришћењем идентичног кључа, који је садржао дубину. Ово је дозволило Џон Тилтману, Блечлипаркском ветерану и изразито талентованом криптоанализеру, да закључи да је у питању Вемам кодер који користи функцију искључиве дисјункције (XОР) - означава се са "⊕", и да декодира обе поруке, тиме добијајући нејасан кључ. Након бесплодног периода током ког је Истраживачки Одсек криптоанализера покушавало да закључи како Тани машина функционише, овај и неки други кључеви су предати Туту, од кога су затражили да "види шта може да учини од њих"[8].

Током своје обуке, Тат је научио Касиски технику прегледања писања на кбадратни папир, започињући ноби ред после дефинисаног броја карактера за које је сматрало да је фреквенција понављања кључа[11]. Ако је број тачан, колоне матрице би показале више понављања секвенци него случајно. Тат је знао да Танијеви индикатори користе 25 слова(укључујући ј) за 11 позиција, али само 23 слова за остале. Тако је покушао Касискијебу технику на првом импулсу кључа карактера користећи понављања 25 х 23 = 575. Није посматрао велики број понављања у колони са овим периодом, него феномен дијагонале. Тако је опет покушао са 574, које је показивало понављање у колонама. Препознајући да су прости чиниоци овог броја 2, 7 и 41, покушао је опет са периодом од 41 и добио "троугао тачака и крстова који је испуњен понављањима".[8]

Било је очигледно да први импулс клјуча био компликованији него онај направљен од једног точка са 4 чегтрдесет једним кључним импулсом. Тат је ово назвао компонентом кључа Х1 (χ1). Схватио је да постоји друга компонента која је XOR-ована са овом, која се није убек мењала са сваким новим карактером, и да је то продукт точка који је назвао PSY1. Исто се примењивало за сваки од 5 импулса (χ1χ2χ3χ4χ5 и ψ1ψ2ψ3ψ4ψ5). Дакле за појединачни карактер, цео књуч К се састојао из две компоненте:

К=χ XOR ψ

У Блечли парку, маркирани импулси су означавани са x, а просторни импулси са •. На пример, слово Х би се кодирало "••x•x"[12]. Татова деривација chi и psi компонената је постала могућа захваљујући чињеници да је иза тачке вероватније да долази још једна тачка, него што није, такође и за крст (вероватније је да долази још један крст, него да не докази). Ово је резултат слабости Немачког кључа, који су касније елеминисали. Једном кад је Тат дошао до тог открића, остатак Истраживачког Одсека се придружио у проучавању осталих импулса, и откривено је да пет chi точкова напредовало сваким новим карактером и да је пет psi точкова померано заједно под контролом mu или "мотор" точкова. У току следећа два месеца, Тат и остатак чланова Истраживачког Одсека су схватили комплетну логичку структуру машине, са њеним скупом точкова који су садржали брегове који су могли бити или у позицији (подигнути) да додају x у низ карактера, или у алтернативној позицији да додају •[8] .

Дијагностикованје функционалне Танијебе машине на овај начин је истински значајано криптоаналитичко достигнуће које је, у цитату за Татубу индукцију као Officer of the Order of Canada, је описано као једно од "највећих интелектуалних достигнућа Другог светског ратa"[4].

Татов статистички метод уреди

За декодирање Тани(енгл. Tunny) поруке било је потребно знање не само логичког начина функционисања машине, али такође и почетни положај сваког ротора за одређену поруку. Истразивао је начин на који би манипулацијом чиптекста створио спектар фреквенција који би одударао облику који је тај процес тежио да створи. Док је био упућен на Истраживачки Одсек у јулу 1942, Алан Тјуринг је схватио да је нили комбинација вредности узастопних карактера у реду шифрованог текста и кључ је наглашавао на било каква одступања од стандардне дистибуције. Резултантни ток (симболизован грчким словом "делта" Δ) назван је разликом јер је нили комбинација иста као одузимање по модулу 2.

Разлог због којег је то омогућило дешифровање машине био је да, иако се фреквентна расподела знакова у шифрираном тексту не може разликовати од случајног тока, исто тако није важило за верзију шифрираног текста из које је чи (енг. chi) елемент кључа био уклоњен. У том случају, због тога што је отворени текст садржао поновљени карактер и пси точкови нису кренули даље, диференцирани пси карактер (Δ) би био нулти карактер ('/' у Блетчли Парку(енгл. Bletchley Park)). Када би била извршена операција нили (XOR) са било којим знаком, овај карактер не би имао ефекта. Поновљени знакови у отвореном тексту били су чешћи како због карактеристика немачког језика (ЕЕ, ТТ, ЛЛ и СС (немачки: EE, TT, LL и SS) су релативно чести)[13], тако и због тога што су телеграфи често понављали знакове великих бројева и великих слова[14], који би својим губитаком у обичној телеграфској поруци могли довести до бесмислица[15].

Генерални Извештај о Тани:

Турингери (енгл. Turingery) је увео принцип да би кључна разлика у једном, сада названа ΔΚ, могла донети информације које се не могу добити од обичног кључа. Овај принцип Δ био је основна основа готово свих статистичких метода разбијања точкова. [16]

Тат је искористио ово појачање неједнакости у диференцираним вредностима, а до новембра 1942. произвео је начин за откривање полазних тачака точкова машине која је постала позната као "Статистичка метода"[17]. Суштина ове методе била је да се пронађу почетна подешавања чи (chi) компоненте кључа исцрпним испробавањем свих позиција његове комбинације са шифрираним текстом и тражењем доказа о неједнакости која одражава карактеристике оригиналног отвореног текста[18][19]. Зато што би сви понављани знакови у отвореном тексту увек генерисали • и слично ∆ψ1 ⊕ ψ∆2 би генерисао • кад год се пси(psi) точкови не померају, а око пола времена када су радиле - укупно око 70%.

Поред примене диференцијације на пуне 5-битне знакове ИТА2 (енгл. ITA2)кода, Тат га је применио на појединачне импулсе (битове). Поставке тренутног чи (chi) котура требало је да буду успостављене како би се омогућила релевантна секвенца знакова да се генеришу чи (chi) точкови. Било је потпуно непрактично генерисати 22 милиона знакова из свих пет чи (chi) точкова, тако да је у почетку била ограничена на 41 × 31 = 1271 од прва два. Након што је објаснио своје налазе Маку Њуману, Њуман је добио задатак да развије аутоматизовани приступ поређењу шифрираног текста и кључа за тражење одступања од случајности. Прва машина је названа Хит Робинсон (енгл. Heath Robinson), али много бржи рачунар Колос (енгл. Colossus computer), који је развио Томи Фловерс (енгл. Tommy Flowers) и користећи алгоритме које је написао Тат и његове колеге, убрзо је преузео разбијање кодова.[20][21][22]

Докторат и каријера уреди

Тат је докторирао математику на Кембриџу 1948. године под монторством Шауна Вилија, који је такође радио у Блетчли Парку на Танију. Крајем 1945. године, Тате је наставио студије на Кембриџу, сада као дипломирани студент математике. Он је објавио неке раније започете радове, један од данас познатих радова који карактеришу графикони који имају савршено подударање, а други који конструише не-Хамилтонов граф(енг. non-Hamiltonian graph). Он је створио револуционарну докторску тезу, Алгебарска теорија графова, о теми касније познатој као теорија матроида.[23]

Исте године, позван од Харолда Скота Макдоналда Коксетера(енгл. Harold Scott MacDonald Coxeter), прихватио је позицију на Универзитету у Торонту. Године 1962. преселио се на Универзитет Вотерлу у Вотерлуу, Онтарио, где је остао до краја академске каријере. Званично је пензионисан 1985. године, али је остао активан као редовни професор у пензији. Тате је помогао у оснивању Одељења за комбинаторику и оптимизацију на Универзитету Вотерлу.

Његова математичка каријера била је усредсређена на комбинаторику, посебно на теорију графова, за коју је сматрао да је помогао у стварању модерне форме и теорији матроида, на коју је дао значајан допринос; један колега га је описао као "водећег математичара у комбинаторици три деценије". Био је главни уредник Журнала комбинаторне теорије (енгл. Journal of Combinatorial Theory) док се није повукао из Ватерлуа 1985[23]. Такође је био члан уредничких одбора неколико других часописа за математичка истраживања.

Доприноси математици уреди

Тат је такође развио алгоритам за одређивање да ли је задат бинаран матроид цикличан.

Тат је написао рад са насловом Како нацртати граф? у коме је доказао да је свака област у 3-повезаном графу ограђена периферним циклусом. Користећи ову чињеницу, Тат је развио алтернативни доказ да је сваки граф Куратовског је непланаран показавши да графови К5 и К3,3 садрже по 3 различита периферна циклуса са заједничком граном. Осим што је користећи периферне циклусе да докаже да су графови Куратовског непланарни, Тат је доказао да сваки 3-повезан граф може да с нацрта са свим конвексним областима, и осмислио алгоритам који конструише раван решавањем систем линеарних једначина. Резултујућа скица је позната као Татово уграђивање. Татов алгоритам користи барицентарни кординатни систем периферних циклуса једноставних 3-повезаних графова.

Успоставило се да су тврђења која је објавивао у својим радовима од веома великог значаја зато што су алгоритми које је Тат развио постали популарне методе цртања планарних графова. Једно од главних разлога због кога је Татеово уграђивање популарно је зато што су неопходна израчунавања у његових алгоритаму јендоставна и гарантују 1-1 однос између графа и његовог приказа у Еуклидском простору, што је кључно када желимо да параметризујемо тродимензионалну мрежу на раван. "Татеова теорема је основа решења за све остале проблеме компјутерске графике, као што је претапање слика.

Тат је примарно заслужан за напредак теорије нумерације планарних графова, који садрже блиске повезаности са хроматским и дихроматским полиномијама. Његов рад је укључио неке веома напредне технологије које је он изумео, садржавши значајне степене редове (чији коефицијенти броје одговарајуће врсте графова) и функције које испливавају као њихове суме, као и геометријску спретност у уочавању тих редова у контексту теорије графова.

Тат је сав свој рад сумирао у књизи "Изабрани радови В. Т. Татеа", 1979 и у "Теорија графова као што је знамо" 1998.

Позиције, почаствовања и награде уреди

Татов рад током Другог светског рата заједно, као и касније у пољу комбинаторике, донео му је разне позиције, почаствовања и награде:

Тат је био библиотекар у Елитном астрономском друштву у Канади 1959-1960. године, чак је и астероид 14989 Тат (1997 УБ7) назбан по њему.

Као последица Татеовог рада у парку Блетчер, канадска комуникациона заштита је назвала међународну организацију са циљем да промовише криптографију, Татеов инстиТат математике и рачунарства (енг. Tutte Institute for Mathematics and Computing (TIMC)), у његову част 2011.

У септембру 2014, Тат је прослављен у свом родном граду, са сопственом скулптуром, након сто су локалне новине започеле кампању у мемориам њему.

Блечли парк у Милтон Кајнесу је прославио Татеов рад са изложбом под називом Бил Тат: Математичар + Декодер која је била заказана за 15. мај 2017. године све до 2019, којој је претходило предавање о његовом животу и раду током Бил Татеовог вековног симпозијума 14. маја 2017. године са.

Приватни живот и смрт уреди

Поред предности у сопственој каријери рад у Универзитету у Ватерлоу, живот у руралном делу Батерлуа се његовој жени Доротеји и њему свидела. Купили су кућу близу места Источна Монтроза у Онтарију где су уживали у планинарењу и провођењу времена у сопственој башти на Великој реци. Чак су и дозвољавали и другима да уживају у лепоти њиховог поседа.

Они су имали широко знање о птицама њихове баште. Доротеја, страствени баштован, је била и планинар. Заједно са Билом су организовали планинарске излете. Пред крај свог живота Бил је идаље уживао у дугим шетњама[6][24]. Након смрти његове жене 1994, вратио се у Њумаркет у Суфолку, али се ипак 2000. године вратио у Батерлу, где је и две године касније и умро.[25] Сахрањен је на гробљу у Источној Монтози.[23][26]

Референце уреди

  1. ^ а б Hinsley 1993, стр. 8
  2. ^ а б Brzezinski 2005, стр. 18
  3. ^ а б в Younger, D. H. (2012). „William Thomas Tutte. 14 May 1917 — 2 May 2002”. Biographical Memoirs of Fellows of the Royal Society. 58: 283—297. S2CID 73088374. doi:10.1098/rsbm.2012.0036. 
  4. ^ а б O'Connor, J J; Robertson, E F (2003), MacTutor Biography: William Thomas Tutte, University of St Andrews, retrieved 28 April 2013
  5. ^ Johnson, Will. "Matroids" (PDF). Retrieved 16 October 2014.
  6. ^ а б Hobbs, Arthur M.; James G. Oxley (март 2004). „William T. Tutte (1917–2002)” (PDF). Notices of the American Mathematical Society. 51 (3): 322. .
  7. ^ Smith, Cedric A. B.; Abbott, Steve (2003). „The Story of Blanche Descartes”. The Mathematical Gazette. 87 (508): 23—33. ISSN 0025-5572. JSTOR 3620560. S2CID 192758206. doi:10.1017/S0025557200172067. 
  8. ^ а б в г Tutte, William T. (2006), My Work at Bletchley Park
  9. ^ Hinsley & Stripp 2001, стр. 141–148
  10. ^ Sale, Tony, The Lorenz Cipher and how Bletchley Park broke it, retrieved 21 October 2010
  11. ^ Bauer, Friedrich L. (2006), The Tiltman Break
  12. ^ Copeland, B. Jack, ур. (2006). Colossus: The Secrets of Bletchley Park's Codebreaking Computers. Oxford: Oxford University Press. ISBN 978-0-19-284055-4. 
  13. ^ Singh, Simon, The Black Chamber, retrieved 28 April 2012
  14. ^ Newman c. 1944 p. 387
  15. ^ Carter 2004, стр. 3
  16. ^ Good, Michie & Timms 1945, p. 6 in 1. Introduction: German Tunny
  17. ^ Tutte, W. T. (1998). Graph Theory as I Have Known it. Oxford: Clarendon Press. ISBN 978-0-19-850251-7. 
  18. ^ Good, Jack; Michie, Donald; Timms, Geoffrey (1945), General Report on Tunny: With Emphasis on Statistical Methods, UK Public Record Office HW 25/4 and HW 25/5, retrieved 15 September 2010
  19. ^ Budiansky 2006, стр. 58–59
  20. ^ Copeland, B. Jack (2011), Colossus and the Dawning of the Computer Age
  21. ^ Younger, Dan (August 2002). "Biography of Professor Tutte". CMS Notes. Retrieved 24 June2018 – via University of Waterloo.
  22. ^ Roberts 2017
  23. ^ а б в „Biography of Professor Tutte | Combinatorics and Optimization | University of Waterloo”. Архивирано из оригинала 19. 08. 2019. г. Приступљено 17. 03. 2019. 
  24. ^ "Bill Tutte". Telegraph Group Limited. Archived from the original on 27 September 2013. Retrieved 21 May 2013.
  25. ^ van der Vat, Dan (10 May 2002), "Obituary: William Tutte", The Guardian, London, retrieved 28 April2013
  26. ^ „ON: West Montrose United Cemetery (William T. TUTTE), CanadaGenWeb's Cemetery Project”. Архивирано из оригинала 01. 02. 2017. г. Приступљено 17. 03. 2019. 

Литература уреди


Преузето из „https://sr.wikipedia.org/w/index.php?title=Бил_Тат&oldid=27675306”