Playfair chiffer - Playfair cipher

För att inte förväxla med Wadsworths chiffer .
Playfair -krypteringen använder ett 5 × 5 rutnät med bokstäver och krypterar ett meddelande genom att dela upp texten i bokstavspar och byta dem efter deras positioner i en rektangel inom det rutnätet: "HI" blir "BM".
Playfair -systemet uppfanns av Charles Wheatstone , som först beskrev det 1854.

Den Playfair chiffer eller Playfair torg eller Wheatstone-Playfair chiffer är en manuell symmetrisk kryptering teknik och var den första bokstavlig digram substitution chiffer. Systemet uppfanns 1854 av Charles Wheatstone , men bär namnet Lord Playfair för att främja dess användning.

Tekniken krypterar par bokstäver ( bigram eller digram ) i stället för enkla bokstäver som i den enkla substitutionskodaren och ganska mer komplexa Vigenère -krypteringssystem som sedan används. Playfair är därmed betydligt svårare att bryta eftersom frekvensanalysen som används för enkla substitutionschiffer inte fungerar med den. Frekvensanalys av bigrams är möjlig, men betydligt svårare. Med 600 möjliga bigram snarare än de 26 möjliga monogrammen (enkelsymboler, vanligtvis bokstäver i detta sammanhang) krävs en betydligt större chiffertext för att vara användbar.

Historia

Lord Playfair , som starkt främjade dess användning.

Playfair -krypteringen var den första krypteringen som krypterade par bokstäver i kryptologisk historia. Wheatstone uppfann krypteringen för sekretess inom telegrafi , men den bär namnet på hans vän Lord Playfair , första Baron Playfair i St. Andrews, som främjade användningen. Den första inspelade beskrivningen av Playfair -krypteringen fanns i ett dokument signerat av Wheatstone den 26 mars 1854.

Det avvisades ursprungligen av det brittiska utrikesdepartementet när det utvecklades på grund av dess upplevda komplexitet. Wheatstone erbjöd sig att visa att tre av fyra pojkar i en närliggande skola skulle kunna lära sig att använda den på 15 minuter, men undersekreteraren för utrikesdepartementet svarade: "Det är mycket möjligt, men du kan aldrig lära det för attachéer."

Den användes dock senare för taktiska ändamål av brittiska styrkor under andra boerkriget och under första världskriget och för samma ändamål av britterna och australierna under andra världskriget . Detta berodde på att Playfair är relativt snabb att använda och inte kräver någon specialutrustning - bara en penna och lite papper. Ett typiskt scenario för Playfair-användning var att skydda viktiga men icke-kritiska hemligheter under den faktiska striden, t.ex. det faktum att en artillerigång av rökskal skulle börja inom 30 minuter för att täcka soldaternas framsteg mot nästa mål. När fiendens kryptanalytiker kunde avkoda sådana meddelanden timmar senare skulle sådan information vara värdelös för dem eftersom den inte längre var relevant.

Under andra världskriget använde Nya Zeelands regering den för kommunikation mellan Nya Zeeland , Chatham -öarna och kustbevakarna på Stilla havet. Coastwatchers etablerade av Royal Australian Navy Intelligence använde också denna chiffer.

Ersatt

Playfair används inte längre av militära styrkor på grund av tillkomsten av digitala krypteringsenheter. Denna chiffer anses nu vara osäker för alla ändamål, eftersom moderna datorer lätt kan bryta den inom mikrosekunder.

Den första publicerade lösningen för Playfair-krypteringen beskrevs i en 19-sidig broschyr av löjtnant Joseph O. Mauborgne , publicerad 1914.

Beskrivning

Playfair -krypteringen använder en 5 x 5 -tabell som innehåller ett nyckelord eller en fras . Memorisering av nyckelordet och 4 enkla regler var allt som krävdes för att skapa tabellen 5 för 5 och använda krypteringen.

För att generera nyckeltabellen skulle man först fylla i blankstegen i tabellen (en modifierad Polybius -kvadrat ) med nyckelordets bokstäver (släppa alla dubbletter), sedan fylla de återstående blankstegen med resten av bokstäverna i alfabetet i ordning (vanligtvis utelämnar "J" eller "Q" för att minska alfabetet så att det passar; andra versioner sätter både "I" och "J" i samma mellanslag). Nyckeln kan skrivas i de översta raderna i tabellen, från vänster till höger eller i något annat mönster, till exempel en spiral som börjar i övre vänstra hörnet och slutar i mitten. Nyckelordet tillsammans med konventionerna för att fylla i tabellen 5 för 5 utgör krypteringsnyckeln.

För att kryptera ett meddelande skulle man dela upp meddelandet i digram (grupper om 2 bokstäver) så att till exempel "HelloWorld" blir "HE LL OW OR LD". Dessa digram kommer att ersättas med nyckeltabellen. Eftersom kryptering kräver par bokstäver, bifogar meddelanden med ett udda antal tecken vanligtvis en ovanlig bokstav, till exempel "X", för att slutföra den sista digramen. Digramens två bokstäver anses vara motsatta hörn av en rektangel i tangentbordet. För att utföra substitutionen, tillämpa följande fyra regler i ordning på varje bokstavspar i klartext:

  1. Om båda bokstäverna är desamma (eller bara en bokstav finns kvar), lägg till ett "X" efter den första bokstaven. Kryptera det nya paret och fortsätt. Vissa varianter av Playfair använder "Q" istället för "X", men alla bokstäver, som i sig är ovanliga som ett upprepat par, kommer att göra.
  2. Om bokstäverna visas på samma rad i ditt bord, ersätt dem med bokstäverna till höger om respektive (omsluter till vänster om raden om en bokstav i det ursprungliga paret fanns på höger sida av raden).
  3. Om bokstäverna visas på samma kolumn i ditt bord, ersätt dem med bokstäverna omedelbart nedanför (svep runt till kolumnens övre sida om en bokstav i det ursprungliga paret fanns på kolumnens undersida).
  4. Om bokstäverna inte finns på samma rad eller kolumn, ersätt dem med bokstäverna på samma rad respektive i det andra hörnparet i rektangeln som definieras av det ursprungliga paret. Ordningen är viktig - den första bokstaven i det krypterade paret är den som ligger på samma rad som den första bokstaven i klartextparet.

För att dekryptera, använd den omvända (motsatta) av de tre senaste reglerna och den första som är (släpp eventuella extra "X" eller "Q" som inte är vettiga i det slutliga meddelandet när det är klart).

Det finns flera mindre variationer av den ursprungliga Playfair -krypteringen.

Exempel

Med hjälp av "playfair -exempel" som nyckel (förutsatt att jag och J är utbytbara) blir tabellen (utelämnade bokstäver i rött):

Playfair Cipher byggnadsnät utelämnat letters.png

Det första steget med att kryptera meddelandet "göm guldet i trädstubben" är att konvertera det till bokstäverna "HI DE TH EG OL DI NT HE TR EX ES TU MP" (med noll "X" används för att separera de upprepade "E": erna). Sedan:

1. Paret HI bildar en rektangel, ersätt det med BM Playfair Cipher 01 HI till BM.png
2. Paret DE finns i en kolumn, ersätt det med OD Playfair Cipher 02 DE till OD.png
3. Paret TH bildar en rektangel, ersätt det med ZB Playfair Cipher 03 TH till ZB.png
4. Paret EG bildar en rektangel, ersätt den med XD Playfair Cipher 04 EG till XD.png
5. Paret OL bildar en rektangel, ersätt det med NA Playfair Cipher 05 OL till NA.png
6. Paret DI bildar en rektangel, ersätt det med BE
7. Paret NT bildar en rektangel, ersätt den med KU
8. Paret HE bildar en rektangel, ersätt det med DM
9. Paret TR bildar en rektangel, ersätt det med UI
10. Paret EX (X infogat för att dela EE) är i rad, ersätt det med XM Playfair Cipher 10 EX till XD.png
11. Paret ES bildar en rektangel, ersätt det med MO
12. Paret TU är i rad, ersätt det med UV
13. Paret MP bildar en rektangel, ersätt det med IF

Således blir meddelandet "göm guldet i trädstubben" "BM OD ZB XD NA BE KU DM UI XM MO UV IF", som kan omstruktureras som "BMODZ BXDNA BEKUD MUIXM MOUVI F" för att lätt kunna läsa chiffertexten.

Förtydligande med bild

Antag att man vill kryptera digram ELLER. Det finns fem allmänna fall:

1) 
* * * * *
* O Y R Z
* * * * *
* * * * *
* * * * *

Därför OR → YZ

2) 
* * O * *
* * B * *
* * * * *
* * R * *
* * Y * *

Därför ELLER → BY

3) 
Z * * O *
* * * * *
* * * * *
R * * X *
* * * * *

Därför OR → ZX

4) 
* * * * *
* * * * *
* O R C *
* * * * *
* * * * *

Därför OR → RC

5) 
* * * * *
* * R * *
* * O * *
* * I * *
* * * * *

Därför OR → IO

Kryptanalys

Liksom de flesta klassiska chiffer kan Playfair -krypteringen lätt knäckas om det finns tillräckligt med text. Att skaffa nyckeln är relativt enkelt om både klartext och kryptext är kända. När endast chiffertexten är känd, involverar brutal kraftkrypteringsanalys av krypteringen sökning genom nyckelutrymmet efter matchningar mellan frekvensen av förekomst av digram (bokstavspar) och den kända frekvensen för förekomst av digram i det antagna språket i det ursprungliga meddelandet.

Kryptanalys av Playfair liknar den för fyra-kvadratiska och två-kvadratiska chiffer, även om den relativa enkelheten i Playfair-systemet gör det lättare att identifiera kandidat-klartextsträngar. Framför allt kommer en Playfair digraph och dess baksida (t.ex. AB och BA) att dekryptera till samma bokstavsmönster i klartext (t.ex. RE och ER). På engelska finns det många ord som innehåller dessa omvända digrafer som REceivER och DEpartED. Att identifiera närliggande omvända digrafer i chiffertexten och matcha mönstret med en lista över kända klartextord som innehåller mönstret är ett enkelt sätt att generera möjliga klartextsträngar för att börja bygga nyckeln.

Ett annorlunda tillvägagångssätt för att hantera en Playfair -kryptering är hagelklättringsmetoden . Detta börjar med en slumpmässig kvadrat med bokstäver. Sedan införs mindre ändringar (dvs. byter bokstäver, rader eller återspeglar hela rutan) för att se om kandidatens klartext mer liknar vanlig klartext än före ändringen (kanske genom att jämföra digramen med ett känt frekvensdiagram). Om det nya torget anses vara en förbättring, antas det och muteras sedan ytterligare för att hitta en ännu bättre kandidat. Så småningom finner man att klartext eller något mycket nära uppnår maximal poäng med vilken betygsmetod som helst som väljs. Detta är uppenbarligen utanför det typiska mänskliga tålamodet, men datorer kan använda denna algoritm för att knäcka Playfair -chiffer med en relativt liten mängd text.

En annan aspekt av Playfair som skiljer den från fyrkantiga och tvåkvadratiga chiffer är det faktum att den aldrig kommer att innehålla en digram med två bokstäver, t.ex. EE. Om det inte finns några dubbelbokstäver i krypteringen och meddelandets längd är tillräckligt lång för att göra detta statistiskt signifikant är det mycket troligt att krypteringsmetoden är Playfair.

En bra handledning om hur man rekonstruerar nyckeln till en Playfair-chiffer finns i kapitel 7, "Solution to Polygraphic Substitution Systems", i Field Manual 34-40-2 , producerad av USA: s armé. Ytterligare en kryptoanalys av en Playfair -chiffer finns i kapitel XXI i Helen Fouché Gaines, Cryptanalysis / en studie av chiffer och deras lösningar .

En detaljerad kryptanalys av Playfair genomförs i kapitel 28 i Dorothy L. Sayers mysterieroman Have His Carcase . I den här historien visas ett Playfair -meddelande vara kryptografiskt svagt, eftersom detektiven kan lösa hela nyckeln och gör bara några gissningar om meddelandets formatering (i det här fallet, att meddelandet börjar med namnet på en stad och sedan ett datum). Sayers bok innehåller en detaljerad beskrivning av mekaniken för Playfair-kryptering, samt en steg-för-steg-redogörelse för manuell kryptoanalys.

Den tyska armén, flygvapnet och polisen använde Double Playfair- krypteringen som en mellanstor chiffer under andra världskriget, baserat på den brittiska Playfair-chiffran som de hade brutit tidigt under WWI. De anpassade det genom att införa en andra kvadrat från vilken den andra bokstaven i varje bigram valdes, och avstod från nyckelordet och placerade bokstäverna i slumpmässig ordning. Men med den tyska förälskelsen för proforma -meddelanden, bröts de i Bletchley Park . Meddelanden föregicks av ett sekventiellt nummer och siffror stavades. Eftersom de tyska siffrorna 1 (eins) till tolv (zwölf) innehåller alla utom åtta bokstäver i Double Playfair-rutorna, var proformatrafiken relativt lätt att bryta (Smith, sidan 74-75)

Använd i moderna korsord

Avancerade tematiska kryptiska korsord som The Listener Crossword (publicerad i lördagsutgåvan av den brittiska tidningen The Times ) innehåller ibland Playfair -chiffer. Normalt måste mellan fyra och sex svar matas in i rutnätet i kod, och nyckelfrasen Playfair är tematiskt betydelsefull för den slutliga lösningen.

Chifferet lämpar sig väl för korsord, eftersom klartext hittas genom att lösa en uppsättning ledtrådar, medan chiffertexten hittas genom att lösa andra. Lösare kan sedan konstruera nyckeltabellen genom att para ihop digrammen (det är ibland möjligt att gissa sökordet, men aldrig nödvändigt).

Användning av Playfair -krypteringen förklaras i allmänhet som en del av ingressen till korsordet. Detta jämnar ut spelplanen för de lösare som inte har stött på krypteringen tidigare. Men hur krypteringen används är alltid densamma. Det 25-bokstaviga alfabetet som används innehåller alltid Q och har I och J sammanfallande. Nyckeltabellen fylls alltid rad för rad.

I populärkulturen

  • Romanen Have His Carcase av Dorothy L. Sayers ger ett slag för slag redogörelse för sprickan i en Playfair-chiffer.
  • Thrillern från andra världskriget The Trojan Horse av Hammond Innes döljer formeln för en ny höghållfast metalllegering med hjälp av Playfair-chifferet.
  • I filmen National Treasure: Book of Secrets är en skattjakt ledtråd kodad som en Playfair -chiffer.
  • I ljudboken Rogue Angel : God of Thunder används en Playfair -krypteringsled för att skicka Anja Creed till Venedig.
  • I romanen York: The Map of Stars (del tre i en trilogi för barn) av Laura Ruby krypteras en ledtråd till att lösa Morningstarr -krypteringen med hjälp av Playfair -krypteringen.
  • Playfair -krypteringen fungerar som en plot -enhet i ett avsnitt av säsong 2 av Batwoman 2019 (TV -serien) .

Se även

Anteckningar

Referenser

externa länkar