Вилијам Томас "Бил" Тат (14. мај 1917 - 2. мај 2002) био је британски разбијач шифара и математичар. Током Другог светског рата направио је фундаментални напредак у криптоанализи Лоренцове шифре, великог немачког шифарског система који је коришчен за тајне комуникације унутар Врховне команде Вермахта. Стратешка природа интелигенције добијене из Татовог кључног продора, у великом дешифрованју Лоренцових шифрованих порука, увелико је допринела, а можда и одлучно, поразу нацистичке Немачке. Он је такође имао низ математичких достигнућа, укључујући и рад на темелјима из области теорије графова и теорије матроида, University of St Andrews, retrieved 28 April 2013.
Татово истраживање у области графова показало се од изузетног значаја. У време када је теорија графова још увек била примитивна тема, Тат је почео да проучава матроиде (уређене парове) и развио их у теорију проширујући рад који је Хаслер Витни развио око средине 1930-ихJohnson, Will. "Matroids" (PDF). Retrieved 16 October 2014.. Иако су Татови доприноси теорији графова имали утицај на савремену теорију графова и многе од његових теорема су коришћене да наставе напредак на том пољу, већина његове терминологије није била у складу са њиховом конвенцијалном употребом. Самим тим његову терминологију не користе данашњи теоретичари графова..
Детињство, младост и школовање Тат је рођен у Њумаркету у Сафоку. Он је био млађи син Вилијама Џона Тата (1873 – 1944), баштована, и Ени (1881 – 1956), кућне помоћнице. У Енглеској је похађао основну школу и са десет година освојио стипендију на Кембриџу. Године 1935. добио је стипендију за факултет природних наука на Тринити колеџу где се специализовао у области хемије и дипломирао са првокласним почастима 1938. Наставио је са физичком хемијом као апсолвент али се касније пребацио на области математике крајем 1940. Као студент (уз своја три пријатеља) први је решио проблем дељења квадрата на квадрате. Сва четворица су заједно створила псеудоним Бланш Декарт иза кога се Тат крио годинама.
Други светски рат Убрзо након избијања Другог светског рРата, Татов учитељ, Патрик Даф, предложио га је за ратни посао у Владиној школи за Кодирање и Шифру у Блечли Парку (БП). Интервјуисан је, и послат на обуку у Лондону пре одласка у Блечли парк, где се придружио Истраживачком Одсеку. У почетку, радио је на Хагелиновој шифри, коју је користила Италијанска морнарица. Била је то ротор шифрирајућа машина која је доступна комерцијално, па је механика шифровања била позната, а дешифровање порука захтевало само схватање како је машина постављена.
У лето 1941, Тат је пребачен да ради на пројекту назван Риба(). Обавештајне информације су откриле да су Немци позвали бежични телепринтер преносни систем "Sägefisch" (sawfish – риба тестерача). Ово је навело британце да користе код Риба () за немачки телепринтер шифрирајући систем. Надимак Тани (, туна) је коришћен за први не-Морзеов линк, и то је субсеквентно коришћено за Лоренцову СЗ машину и поруке које је она кодирала.
Телеграфија је користила 5-битну Међународну Телеграфску Абецеду Бр. 2 () Ништа се није знало о механизму шифровања, осим тога да је порукама претходио индикатор од 12 слова који је подразумевао ротор шифрирајућу машину са 12 точкова. Први корак морао је да бити дијагностиковање машина успостављањем логичке структуре и тиме функционисање машина. Тат је овде одиграо кључну улогу, недуго пре победе савезника у Европи 1945, када је Блечли парк купио Тани Лоренцву машину за шифровањеSale, Tony, The Lorenz Cipher and how Bletchley Park broke it, retrieved 21 October 2010. Татова истраживања на крају су довела до дешифровања Тани-шифрованих порука између немачке Врховне команде Вермахта (OKW) у Берлину и њихових војних команди широм окупиране Европе, и допринеле су - можда по највише- поразу Немачке.
Дијагностиковање машине за шифровање Дана 31. август 1941, две верзије исте поруке су послате коришћењем идентичног кључа, који је садржао дубину. Ово је дозволило Џон Тилтману, Блечлипаркском ветерану и изразито талентованом криптоанализеру, да закључи да је у питању Вемам кодер који користи функцију искључиве дисјункције (XОР) - означава се са "⊕", и да декодира обе поруке, тиме добијајући нејасан кључ. Након бесплодног периода током ког је Истраживачки Одсек криптоанализера покушавало да закључи како Тани машина функционише, овај и неки други кључеви су предати Туту, од кога су затражили да "види шта може да учини од њих".
Током своје обуке, Тат је научио Касиски технику прегледања писања на кбадратни папир, започињући ноби ред после дефинисаног броја карактера за које је сматрало да је фреквенција понављања кључа. Ако је број тачан, колоне матрице би показале више понављања секвенци него случајно. Тат је знао да Танијеви индикатори користе 25 слова(укључујући ј) за 11 позиција, али само 23 слова за остале. Тако је покушао Касискијебу технику на првом импулсу кључа карактера користећи понављања 25 х 23 = 575. Није посматрао велики број понављања у колони са овим периодом, него феномен дијагонале. Тако је опет покушао са 574, које је показивало понављање у колонама. Препознајући да су прости чиниоци овог броја 2, 7 и 41, покушао је опет са периодом од 41 и добио "троугао тачака и крстова који је испуњен понављањима".
Било је очигледно да први импулс клјуча био компликованији него онај направљен од једног точка са 4 чегтрдесет једним кључним импулсом. Тат је ово назвао компонентом кључа Х1 (χ1). Схватио је да постоји друга компонента која је XOR-ована са овом, која се није убек мењала са сваким новим карактером, и да је то продукт точка који је назвао PSY1. Исто се примењивало за сваки од 5 импулса (χ1χ2χ3χ4χ5 и ψ1ψ2ψ3ψ4ψ5). Дакле за појединачни карактер, цео књуч К се састојао из две компоненте:
К=χ XOR ψ
У Блечли парку, маркирани импулси су означавани са x, а просторни импулси са •. На пример, слово Х би се кодирало "••x•x". Татова деривација chi и psi компонената је постала могућа захваљујући чињеници да је иза тачке вероватније да долази још једна тачка, него што није, такође и за крст (вероватније је да долази још један крст, него да не докази). Ово је резултат слабости Немачког кључа, који су касније елеминисали. Једном кад је Тат дошао до тог открића, остатак Истраживачког Одсека се придружио у проучавању осталих импулса, и откривено је да пет chi точкова напредовало сваким новим карактером и да је пет psi точкова померано заједно под контролом mu или "мотор" точкова. У току следећа два месеца, Тат и остатак чланова Истраживачког Одсека су схватили комплетну логичку структуру машине, са њеним скупом точкова који су садржали брегове који су могли бити или у позицији (подигнути) да додају x у низ карактера, или у алтернативној позицији да додају • .
Дијагностикованје функционалне Танијебе машине на овај начин је истински значајано криптоаналитичко достигнуће које је, у цитату за Татубу индукцију као Officer of the Order of Canada, је описано као једно од "највећих интелектуалних достигнућа Другог светског ратa".
Татов статистички метод За декодирање Тани() поруке било је потребно знање не само логичког начина функционисања машине, али такође и почетни положај сваког ротора за одређену поруку. Истразивао је начин на који би манипулацијом чиптекста створио спектар фреквенција који би одударао облику који је тај процес тежио да створи. Док је био упућен на Истраживачки Одсек у јулу 1942, Алан Тјуринг је схватио да је нили комбинација вредности узастопних карактера у реду шифрованог текста и кључ је наглашавао на било каква одступања од стандардне дистибуције. Резултантни ток (симболизован грчким словом "делта" Δ) назван је разликом јер је нили комбинација иста као одузимање по модулу 2.
Разлог због којег је то омогућило дешифровање машине био је да, иако се фреквентна расподела знакова у шифрираном тексту не може разликовати од случајног тока, исто тако није важило за верзију шифрираног текста из које је чи (енг. chi) елемент кључа био уклоњен. У том случају, због тога што је отворени текст садржао поновљени карактер и пси точкови нису кренули даље, диференцирани пси карактер (Δ) би био нулти карактер ('/' у Блетчли Парку()). Када би била извршена операција нили (XOR) са било којим знаком, овај карактер не би имао ефекта. Поновљени знакови у отвореном тексту били су чешћи како због карактеристика немачког језика (ЕЕ, ТТ, ЛЛ и СС (немачки: EE, TT, LL и SS) су релативно чести)Singh, Simon, The Black Chamber, retrieved 28 April 2012, тако и због тога што су телеграфи често понављали знакове великих бројева и великих словаNewman c. 1944 , који би својим губитаком у обичној телеграфској поруци могли довести до бесмислица.
Генерални Извештај о Тани:Турингери () је увео принцип да би кључна разлика у једном, сада названа ΔΚ, могла донети информације које се не могу добити од обичног кључа. Овај принцип Δ био је основна основа готово свих статистичких метода разбијања точкова. Good, Michie & Timms 1945, p. 6 in 1. Introduction: German TunnyТат је искористио ово појачање неједнакости у диференцираним вредностима, а до новембра 1942. произвео је начин за откривање полазних тачака точкова машине која је постала позната као "Статистичка метода". Суштина ове методе била је да се пронађу почетна подешавања чи (chi) компоненте кључа исцрпним испробавањем свих позиција његове комбинације са шифрираним текстом и тражењем доказа о неједнакости која одражава карактеристике оригиналног отвореног текста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. Зато што би сви понављани знакови у отвореном тексту увек генерисали • и слично ∆ψ1 ⊕ ψ∆2 би генерисао • кад год се пси(psi) точкови не померају, а око пола времена када су радиле - укупно око 70%.
Поред примене диференцијације на пуне 5-битне знакове ИТА2 ()кода, Тат га је применио на појединачне импулсе (битове). Поставке тренутног чи (chi) котура требало је да буду успостављене како би се омогућила релевантна секвенца знакова да се генеришу чи (chi) точкови. Било је потпуно непрактично генерисати 22 милиона знакова из свих пет чи (chi) точкова, тако да је у почетку била ограничена на 41 × 31 = 1271 од прва два. Након што је објаснио своје налазе Маку Њуману, Њуман је добио задатак да развије аутоматизовани приступ поређењу шифрираног текста и кључа за тражење одступања од случајности. Прва машина је названа Хит Робинсон (), али много бржи рачунар Колос (), који је развио Томи Фловерс () и користећи алгоритме које је написао Тат и његове колеге, убрзо је преузео разбијање кодова.Younger, Dan (August 2002). "Biography of Professor Tutte". CMS Notes. Retrieved 24 June2018 – via University of Waterloo.
Докторат и каријера Тат је докторирао математику на Кембриџу 1948. године под монторством Шауна Вилија, који је такође радио у Блетчли Парку на Танију. Крајем 1945. године, Тате је наставио студије на Кембриџу, сада као дипломирани студент математике. Он је објавио неке раније започете радове, један од данас познатих радова који карактеришу графикони који имају савршено подударање, а други који конструише не-Хамилтонов граф(енг. non-Hamiltonian graph). Он је створио револуционарну докторску тезу, Алгебарска теорија графова, о теми касније познатој као теорија матроида.
Исте године, позван од Харолда Скота Макдоналда Коксетера(), прихватио је позицију на Универзитету у Торонту. Године 1962. преселио се на Универзитет Вотерлу у Вотерлуу, Онтарио, где је остао до краја академске каријере. Званично је пензионисан 1985. године, али је остао активан као редовни професор у пензији. Тате је помогао у оснивању Одељења за комбинаторику и оптимизацију на Универзитету Вотерлу.