Kryptologisk bombe

Den kryptologiske bombe ( polsk Bomba kryptologiczna ) er et apparat foreslået af den polske kryptolog Marian Rejewski og udviklet i 1938 sammen med to af hans matematikere Jerzy Rozicki og Henryk Zygalski til systematisk at dekryptere beskeder krypteret af tyskerne ved hjælp af Enigma . Forudsætningen for oprettelsen af ​​maskinen var den upålidelige procedure for at fordoble den nøgle, tyskerne brugte, hvilket gjorde det muligt at bestemme de daglige indstillinger for Enigma [1] .

Historie

Efter opfindelsen af ​​Enigma i 1917 blev denne innovative krypteringsmetode fra 1930 regelmæssigt brugt i Tyskland. Dets naboer, især Frankrig , Storbritannien og Polen , var mistænksomme over for det, især efter nazisternes opståen til magten, da Enigma begyndte at spille en nøglerolle i oprustningen af ​​Wehrmacht. På trods af at franske og britiske kryptoanalytikere ikke kunne knække det og klassificerede det som ubrydeligt [2] , var den 27-årige polske matematiker Marian Rejewski i stand til at knække Enigma allerede i 1932 [3] , efter at have opdaget en alvorlig sårbarhed i beskeden. afsendelsesprocedure.

Nøglefordoblingsprocedure

Dechifrering af meddelelser ved hjælp af Enigma krævede at kende flere parametre: rækkefølgen af ​​rotorerne, deres startpositioner, positionerne af rotorringene og stikpladeforbindelserne. Rotorernes positioner var en nøgle med tre bogstaver (f.eks. "PDN") og var en del af dagnøglen. For at øge sikkerheden blev hver enkelt besked imidlertid krypteret ved hjælp af en ekstra nøglemodifikation. Operatøren valgte tilfældigt rotorindstillingerne for hver besked (f.eks. "PDN"). Nøglen til denne besked blev indtastet to gange ("PDNPDN") og krypteret med dagens nøgle. Operatøren nulstillede derefter maskinen til beskedtasten, som blev brugt senere. [1] Fordi Enigmas interne ledninger ændrede sig med hvert tastetryk, ville gentagelser ikke være synlige i chifferteksten, da de samme almindelige bogstaver ville blive kodet til forskellige chiffertekstbogstaver (f.eks. "PDNPDN" kunne blive "ZRSJVL").

I stedet for at gentage nøglen og derefter kryptere den, kunne tyskerne blot kryptere beskednøglen og sende den to gange i træk (f.eks. "ZRSZRS"), eller i begyndelsen og slutningen af ​​beskeden. Dette vil stadig opnå den ønskede redundans for fejldetektionsevne . Dette ville dog være en åbenlys ulempe, da mistænkelig gentagelse ville tiltrække sig kryptanalytikeres opmærksomhed. For at forhindre en sådan situation begyndte de ved første øjekast at bruge en pålidelig mulighed med kopiering af nøglen og dens efterfølgende kryptering, da gentagelsen i chifferteksten ikke var mærkbar. Faktisk førte denne metode til en grov kryptografisk fejl.

Det er også værd at bemærke, at enhedsoperatøren frit kunne vælge nøglen. De, især i stressede situationer, valgte meget simple nøgler. I stedet for den ønskede tilfældige tast blev der ofte valgt simple kombinationer af bogstaver som "AAA", "ABC" eller "ASD" (ved siden af ​​tasterne på enhedens tastatur), som kikserne blot kunne gætte. [4] Derudover blev den valgte nøgle krypteret af Enigma selv, hvilket afslørede den valgte enhedskonfiguration. På den anden side, hvis en uafhængig metode til kryptering af beskednøglen blev brugt, kunne Enigmas interne struktur ikke bestemmes. Faktisk var nøglekryptering slet ikke påkrævet. Det kunne udsendes i ukrypteret form, gentaget to eller endda tre gange (i dette tilfælde ville det være muligt ikke kun at opdage interferens, men også at eliminere dem). På grund af den ukendte position af rotorringene, rummer selve rotorernes position ingen vigtig information for kryptanalytikeren. I stedet tillod nøglefordoblingsproceduren polske kryptoanalytikere at dekryptere meddelelserne [5] .

Cyklometeret som en forløber

Indtil september 1938 var alle beskednøgler, der blev sendt på én dag, krypteret med den samme dagsnøgle. Dusinvis, hvis ikke hundredvis af beskeder var tilgængelige i luften hver dag, alle krypteret med den samme nøgle. Ved at bruge to procedurefejl lavet af tyskerne konstruerede polske kryptoanalytikere en enhed kaldet et cyklometer, bestående af to gåder forbundet i serie, med rotorernes positioner forskudt med tre i forhold til hinanden.

Cyklometeret gjorde det muligt for polakkerne at bestemme, for hver af de seks mulige rækkefølger af rotorerne, karakteristiske permutationer for hver af de 26 3 = 17.576 startpositioner af rotorerne. Cyklometeret forenklede i høj grad det kedelige og tidskrævende arbejde med at finde karakteristika i hver af 6 × 17.576 = 105.456 mulige tilfælde. De opnåede egenskaber blev registreret i kataloget. Arbejdet med at udvikle funktionskataloget, som Rejewski bemærkede, "var kedeligt og tog over et år, men når det var afsluttet, kunne de daglige nøgler bestemmes på 15 minutter" [6] .

Efter udskiftningen af ​​reflektoren UKW-A med UKW-B den 1. november 1937 [7] måtte polske kryptoanalytikere udarbejde et nyt katalog over egenskaber. Men før de kunne fuldføre denne proces, ændrede tyskerne protokollen for videregivelse af beskednøglen [5] . I stedet for en bestemt position af rotorerne til at kryptere beskednøglen, kunne operatøren nu vælge den vilkårligt og sende den i klar form i begyndelsen af ​​beskeden [8] . Pludselig blev featurekataloget ubrugeligt, og Cipher Bureau begyndte at arbejde på nye metoder til at angribe Enigma-cifferet. Dette førte til oprettelsen af ​​Zygalski-arkene og Rejewski-bomben.

Navnets oprindelse

Oprindelsen af ​​navnet "bombe" forbliver et mysterium. Selv efter krigen kunne Marian Rejewski ikke huske det [9] . Ifølge Tadeusz Lissitzky spiste Rejewski, Rozhitsky og Zygalsky en "bombe"-kage, da Rozhitsky foreslog enhedens navn. Ifølge en anden version mindede lyden fra enheden under dens drift om tikken af ​​en bombes urværk, hvilket var årsagen til et sådant navn. Da ikke en eneste bil har overlevet den dag i dag, kan denne version ikke verificeres. Ifølge Rejewski selv, "på grund af manglen på en bedre mulighed, kaldte vi dem bomber" [1] .

Enhed

Idéen med bomben er udelukkende baseret på den upålidelige nøglefordoblingsprocedure. Polakkerne kendte hverken rotorernes positioner eller ringenes positioner. Derudover var rotorernes begyndelsesposition ikke entydig, men blev frit valgt af kryptografen. På trods af dette forblev det klart, at sessionsnøglen først blev fordoblet og derefter krypteret. Heraf kunne polske kryptoanalytikere konkludere, at det første og fjerde, andet og femte samt tredje og sjette bogstav i chifferteksten svarede til de samme bogstaver i klarteksten. Denne vigtige bemærkning gjorde det muligt at søge ved hjælp af mønsteret "123123". [ti]

Den tekniske udførelse af angrebet på Enigma-chifferet var at skabe en elektromekanisk maskine, der omfattede seks sæt Enigma-rotorer. Polakkerne var ikke kun i stand til hurtigt at udvikle bombekonceptet, men også at samle og sætte dem i drift med støtte fra AVA (AVA Wytwórnia Radiotechniczna) . Da der var seks forskellige ordrer af Enigma-rotorer på det tidspunkt, blev der bygget seks bomber, en for hver ordre. Drevet af en elektrisk motor rejste bomben gennem alle 17.576 forskellige rotorpositioner (AAA til ZZZ) på omkring 110 minutter [11] .

Angrebet bestod i at søge efter positioner, hvor, når et bestemt testbogstav blev indtastet, output-bogstavet matchede output-bogstavet for positionen rykket tre frem. Da hver bombe havde seks sæt rotorer, var det muligt at teste tre beskeder på samme tid. Vi ledte efter stillinger, hvor alle tre par havde de samme bogstaver. [en]

En sådan tilfældighed skete ret sjældent og var et stærkt tegn på succes, det vil sige korrekt bestemt rækkefølgen af ​​rotorerne og ringenes placering. Men fejl var også at forvente, sådanne indstillinger, der også giver parvise match af bogstaver, men som ikke er nøglen. [10] I gennemsnit var der én fejl pr. rotorposition. Polske kryptoanalytikere brugte specialdesignede Enigma-replikaer til at opdage fejl og finde korrekte plugboard-forbindelser. De blev indstillet ved hjælp af den mulige rækkefølge af rotorerne og placeringen af ​​ringene opnået fra bomben. [ti]

Til sidst blev der forsøgt at dekryptere beskedteksten. Hvis teksten på tysk blev sporet, betød det, at rækkefølgen af ​​rotorerne, ringenes placering og i det mindste en del af panelpropperne var korrekt bestemt. Det var tilbage at endelig bestemme panelets resterende forbindelser og måske ændre indstillingen af ​​ringene lidt. Herefter var dagsnøglen fuldt fastlagt, og det var muligt at dekryptere beskederne.

Eksempel

Den specifikke brug af bomben kan demonstreres ved det følgende eksempel. Lad os antage, at nøglefordoblingsproceduren blev anvendt, som den var i perioden fra 15. september 1938. Antag som dagnøgle, at rotorens rækkefølge var "B123", positionen af ​​rotorringene var "abc", og plugboardet var "DE", "FG", "HI", "JK" og "LM ". Operatøren valgte tilfældigt en startposition, såsom "BVH", og en beskedtast, såsom "WIK". Som forklaret tidligere blev beskednøglen fordoblet og krypteret med den valgte dagsnøgle og rotorernes startposition. Resultatet (som kan verificeres af frit tilgængelige Enigma-simulatorer) er en krypteret beskednøgle, som sendes sammen med den ukrypterede startposition som en chiffertekstindikator, i dette eksempel "BVH BPLBKM".

Kryptanalytikerne skulle først opsnappe så mange meddelelser som muligt og overveje indikatorer i hvert enkelt tilfælde. Målet var at finde tre krypterede beskednøgler, hvor det første og fjerde, andet og femte og til sidst det tredje og sjette bogstav matchede. [1] Eksemplet ovenfor opfylder denne betingelse. Det er tilbage at finde yderligere to indikatorer, hvor det andet og femte eller tredje og sjette bogstav også er "B".

I princippet kunne man i stedet for at søge efter tre identiske fikspunkter (som de parrede bogstaver blev kaldt i den fordoblede og krypterede nøgle) [10] bruge tre forskellige punkter. Dette ville gøre det lettere at finde passende indikatorer, da indikatorer med tre forskellige par er mere almindelige. På grund af tilstedeværelsen af ​​koblingspanelet bliver parrene dog konverteret før og efter passagen af ​​panelet på en måde, der er ukendt for polakkerne. Der var behov for at vælge et bogstav, der ikke ændrer sig i panelet (selvtilsluttet) [12] , ellers ville dekrypteringen mislykkes. Med fem til otte panelledninger, som det var sædvanligt i 1938, er sandsynligheden for et vellykket hack 50%. På den anden side, når du bruger tre forskellige par, falder denne sandsynlighed til 12,5% [10] . Af denne grund valgte polakkerne en sjældnere, men mere effektiv kombination af tre identiske fikspunkter.

Antag, at efter aflytning af flere tyske beskeder blev indikatorerne "DCM WBVHBM" og "EJX NVBUUB" også fundet. Der er således et sæt af tre sammenfaldende fikspunkter:

For yderligere forståelse bør begrebet forskel (eller afstand) mellem to positioner af rotorerne introduceres. Det vides ikke med sikkerhed, hvordan stillingerne i Cipher Bureau var nummereret. Briterne i Bletchley Park brugte følgende konvention: hver position svarede til et trecifret tal i det seksogtyve talsystem , hvor "Z" var nul, "A" var en, og så videre, indtil "Y" var 25. [13] Så var forskellen mellem de to positioner forskellen mellem deres respektive tal. I vores eksempel vil forskellen mellem positionerne "BVH" og "DCM" være "AGE", og mellem "DCM" og "EJX" - "AGK".

For at bryde gåden satte kryptoanalytikere bomber op på følgende måde. Hver af de seks maskiner svarede til forskellige rækkefølger af rotorer, hvoraf den ene er den ønskede "B123"-variant. Seks sæt rotorer på en bombe dannede tre par. Afstanden mellem rotorerne i et par var lig med tre, og afstanden mellem parrene svarede til afstandene mellem konfigurationerne i de opsnappede meddelelser. [14] Så blev motoren startet, og alle 17576 positioner blev dækket på mindre end to timer.

Målet var at finde positioner, hvor alle sæt rotorer i bomben giver det samme bogstav i den tilsvarende position. Sådan en kamp blev kontrolleret ved hjælp af et simpelt relæ [10] . For eksemplet ovenfor med rotorer "B123" og testbogstavet "B" opnås kun to positioner. Den første viser sig at være en miss, og den anden giver tre indledende positioner (stadig normaliseret til positionen for "aaa"-ringene) "BUF", "DBK" og "EIV".

Ved blot at lede efter forskellen mellem de fundne positioner og positionerne i de opsnappede indikatorer og summere den op med "aaa", kan rotorringenes position bestemmes. [15] I eksemplet ovenfor er resultatet "abc" i alle tre tilfælde.

De resulterende positioner af rotorerne, positionerne af ringene og de oprindelige positioner af rotorerne blev indstillet i Enigma-replikaen, og forsøg på at dechifrere beskederne gav følgende resultater:

Det ønskede mønster "123123" er allerede synligt i det tredje tilfælde, men indtil videre er resultatet ikke nødvendigvis korrekt. Årsagen til dette er den stadig tomme omstilling. Den sidste opgave tilbage var at bestemme denne indstilling brugt af tyskerne (fra fem til otte ledninger). Der var ingen klar søgealgoritme, i stedet blev der brugt en trial and error-metode til at finde en sådan indstilling, hvor der i alle tre tilfælde blev opnået en meddelelse på formen "123123". [14] En god fremgangsmåde ville være at forbinde bogstaver, der endnu ikke matcher i par, for eksempel "H" og "I" i det andet tilfælde. Dette forbedrer den mulige beskednøgle fra "HPDIPZ" til "IPDIPZ". Der er nu to matchende par i stedet for ét. Dette er et stærkt tegn på en korrekt defineret forbindelse. Et andet lovende forsøg er at forbinde de tilsvarende chiffertekstbogstaver i stedet for almindelige bogstaver. Som du ved, passerer strømmen gennem panelet to gange, en gang i form af almindelig tekst, en gang efter passagen af ​​rotorerne. For eksempel, i det første tilfælde matcher den tredje ("H") og sjette ("F") af den mulige beskednøgle "WHHWSF" ikke. "FH"-forbindelsen forbedrer ikke situationen. På den anden side resulterer sammenkædning af tredje og sjette chiffertekstbogstav ("L" og "M") i "WHYWSY". Igen svarer et par identiske chiffertekstbogstaver nu til et par identiske almindelige tekstbogstaver, hvilket betyder, at endnu en panelforbindelse er blevet korrekt defineret. Nu, med parrene "HI" og "LM" forbundet, giver afkodningen i det første tilfælde teksten "WIJWSJ", og i det andet - "IPDIPD", hvor mønsteret "123123" allerede er sporet. Ved korrekt at identificere forbindelsen "JK", som kan gættes ud fra de resulterende bogstaver, vil den første besked, når den dekrypteres, også opfylde det ønskede mønster, og beskednøglen "WIKWIK" vil til sidst blive knækket. De sidste to forbindelser "DE" og "FG" kan findes ved at forsøge at dechifrere meddelelsen med startpositionen af ​​rotorerne "WIK", hvorefter Enigma daglige indstillinger vil blive fundet, og dechifrering af resten af ​​meddelelserne vil ikke være svært.

Slut på bomben

De seks bomber hjalp polakkerne med at fortsætte med at tyde beskeder efter indførelsen af ​​rotorernes frie begyndelsestilstand den 15. september 1938. Men den 15. december 1938 opstod et nyt problem. Tyskerne begyndte at bruge to nye rotorer (IV og V). Følgelig er antallet af forskellige positioner af rotorerne steget fra seks (=3•2•1) til tres (=5•4•3) [5] . I stedet for 6•17'576=105'456 mulige stillinger blev deres antal tidoblet og begyndte at overstige en million. Pludselig blev det nødvendigt at bruge 60 bomber, hvilket i høj grad oversteg polakkernes evner.

Blot to uger senere, ved årsskiftet 1938/39, begyndte endnu en komplikation af sagerne at finde sted, som ikke kun forårsagede kvantitative problemer for polakkerne, men også kvalitative. I stedet for at bruge fem til otte tavleforbindelser (og derfor skifte fra 10 til 16 bogstaver) begyndte tyskerne fra 1. januar 1939 at bruge 7-10 forbindelser. Derfor forblev kun seks til tolv bogstaver ud af 26 Enigma-breve uden forbindelse. I betragtning af at panelet bruges to gange i transformationen, forværrede dette markant (med en faktor to) chancen for at "fange" et brev upåvirket af panelet, hvilket i høj grad reducerede bombernes effektivitet, og fra begyndelsen af ​​1939 bidrog de knap nok til bestemmelse af Enigma dagtimerne nøgler. Til sidst, med opgivelsen af ​​fordoblingen af ​​beskednøglen den 1. maj 1940, blev ideen om en "bombe" fuldstændig ubrugelig [10] [16] .

På dette tidspunkt eksisterede "bomber" imidlertid ikke længere: i september 1939, efter den tyske invasion af Polen , blev kryptoanalytikere tvunget til at ødelægge maskinerne og flygte fra Warszawa [7] .

Turing bombe som efterfølger

Den 26.-27. juli 1939 fandt et møde mellem polske, franske og britiske kryptoanalytikere sted i Pyry , 20 km syd for Warszawa [17] . På den delte polakkerne med deres kolleger deres metoder til at angribe Enigma-chifferet, to replikaer af enheden og tegninger af et cyklometer og en bombe. Baseret på denne viden udviklede Alan Turing en ny Enigma-brydende maskine kaldet bomben . I modsætning til den polske "bombe" var dens funktionsprincip ikke baseret på sårbarheder i den tyske meddelelsesoverførselsprotokol, men på sårbarhederne i selve Enigma. Bombe havde, i modsætning til de polske maskiner, mere processorkraft og arbejdede på en mere effektiv algoritme end brute force, og kunne også dekryptere meddelelser, selvom alle 13 patch-panelforbindelser blev brugt [18] .

Noter

1. ↑ 1 2 3 4 5 Marian Rejewski. Hvordan polske matematikere brød gådeciferen  // IEEE Annals of the History of Computing. - 1981. - T. 3 , no. 3 . — S. 213–234 . - ISSN 1058-6180 . - doi : 10.1109/mahc.1981.10033 . Arkiveret fra originalen den 7. december 2017.
2. ↑ Simon Singh. Chiffer bog. Chiffernes hemmelige historie og deres dechifrering . - Moskva: AST, 2007. - 447 s. — ISBN 5170384777 .
3. ↑ Marian Rejewski. En anvendelse af teorien om permutationer i at bryde gådeciferen  // Applicationes Mathematicae. - 1980. - Nr. 16 (4) . - S. 543-559 . Arkiveret fra originalen den 17. januar 2021.
4. ↑ RICHARD A. WOYTAK. En samtale med Marian Rejewski  // Cryptologia. - 1982-01-01. - T. 6 , nej. 1 . — S. 50–60 . — ISSN 0161-1194 . - doi : 10.1080/0161-118291856830 .
5. ↑ 1 2 3 Welchman, Gordon . The Hut Six-historien: at bryde Enigma-koderne . - Cleobury Mortimer, Shropshire: M&M Baldwin, 1997. - xiv, 263 s. Med. — ISBN 0947712348 .
6. ↑ Marian Rejewski, "Sammendrag af vores metoder til at rekonstruere ENIGMA og rekonstruere daglige nøgler, og af tyske bestræbelser på at frustrere disse metoder," Appendiks C til Władysław Kozaczuk, Enigma: How the German Machine Cipher blev brudt, og hvordan den blev læst af Allierede i Anden Verdenskrig , 1984, s. 241-45.
7. ↑ 1 2 Kippenhahn, Rudolf, 1926-. Kodebrud: en historie og udforskning . — Revideret og ajourført udg. - New York: Overlook Duckworth, 2012. - 301 sider s. — ISBN 1468300741 .
8. ↑ Sebag Montefiore, Hugh. Enigma: kampen om koden . - London: Cassell Military, 2004. - S. 355. - 491 s. — ISBN 0304366625 .
9. ↑ Sebag Montefiore, Hugh. Enigma: kampen om koden . - London: Cassell Military, 2004. - S. 46. - 491 s. — ISBN 0304366625 .
10. ↑ 1 2 3 4 5 6 7 Bauer, Friedrich Ludwig, 1924-. Dekrypterede hemmeligheder: metoder og maksimer for kryptologi . — 3. rev. og opdateret udg. - Berlin: Springer, 2002. - S. 439-443. — 473 s. — ISBN 3540426744 . Arkiveret 1. maj 2021 på Wayback Machine
11. ↑ Sebag Montefiore, Hugh. Enigma: kampen om koden . - London: Cassell Military, 2004. - S. 434. - 491 s. — ISBN 0304366625 .
12. ↑ Sebag Montefiore, Hugh. Enigma: kampen om koden . - London: Cassell Military, 2004. - S. 422. - 491 s. — ISBN 0304366625 .
13. ↑ Carter, Frank. Juli 1999. The First Breaking of Enigma. Nogle af de banebrydende teknikker udviklet af det polske chifferbureau. Bletchley Park-rapport nr. 10. Milton Keynes: Bletchley Park Trust.
14. ↑ 12 David Link . Resurrecting Bomba Kryptologiczna: Archaeology of Algorithmic Artefacts, I (engelsk)  // Cryptologia. — Bd. 33 , udg. 2 . — S. 166–182 . - doi : 10.1080/01611190802562809 .  
15. ↑ Marian Rejewski, "How Polish mathematicians broken the Enigma cipher", appendiks D til Władysław Kozaczuk,  Enigma: How the German Machine Cipher Was Broken, and How It Was Read by the Allies in World War Two , 1984, s. 241-45.
16. ↑ Sebag Montefiore, Hugh. Enigma: kampen om koden . - London: Cassell Military, 2004. - S. 357. - 491 s. — ISBN 0304366625 .
17. ↑ Ralph Erskine. Polakkerne afslører deres hemmeligheder: Alastair Dennistons beretning om mødet i juli 1939 i Pyry  // Cryptologia. — 2006-12-01. - T. 30 , nej. 4 . — S. 294–305 . — ISSN 0161-1194 . - doi : 10.1080/01611190600920944 .
18. ↑ Sebag Montefiore, Hugh. Enigma: kampen om koden . - London: Cassell Military, 2004. - S. 391. - 491 s. — ISBN 0304366625 .

Links

• Online Enigma Simulator
• Jeg, David. Genoplivning af Bomba Kryptologiczna: Arkæologi af algoritmiske  artefakter . Link Udgivet online: s.167-168 (9. juli 2009). Hentet 11. december 2013.
• US 6812 Div. Bombe-rapport  (engelsk) (1944). Hentet 11. december 2013. Arkiveret fra originalen 23. maj 2006.

Litteratur

• Rejewski, Marian. Sammenfatning af vores metoder til at rekonstruere ENIGMA og rekonstruere daglige nøgler og af tyske bestræbelser på at frustrere disse metoder:. - 1984c. Appendiks C til Kozaczuk, 1984, pp=241-245
• Rejewski, Marian. Den matematiske løsning af Enigma Cipher:. - 1984e. Appendiks D til Kozaczuk, 1984, pp=272-291 (polsk)
• Kozaczuk, Władysław . Enigma: Hvordan den tyske maskincipher blev ødelagt, og hvordan den blev læst af de allierede i Anden Verdenskrig . - Frederick, Maryland: University Publications of America, 1984. - ISBN 978-0-89093-547-7 . (oversat af Christopher Kasparek . Suppleret med materiale fra bogen Marian Rejewski . "W kręgu enigmy" . - Warszawa : Książka i Wiedza, 1979. (polsk)
• Rejewski, Marian. "Bemærkninger til appendiks 1 til den britiske efterretningstjeneste i Anden Verdenskrig af Harry Hinsley". - 1980.

Ordbøger og encyklopædier	Britannica (online)