Playfair-chiffer

Playfair-chifferet er en manuell symmetrisk krypteringsteknikk, og var det første chiffer som brukte digraferstatning. Systemet ble oppfunnet i 1854 av Charles Wheatstone, men har sitt navn fra Lord Playfair, som fremmet bruken av chifferet.

Teknikken går på å kryptere bokstavpar (digrafer), i stedet for enkeltbokstaver. Playfair er derfor vanskeligere å knekke, siden frekvensanalysen som brukes ved vanlige erstatningschiffer har færre kombinasjoner, 26 enkeltbokstaver kontra 600 mulige digrafer, da ingen duplikate bokstaver er tillatt, og en bokstav er utelatt (Q) eller kombinert (I/J), slik at det blir 25x24 = 600 mulige kombinasjoner.

Historie

Chifferet ble avvist av det britiske utenriksdepartementet i sin tid, da de mente at det var for komplisert. Når Wheatstone tilbød seg å demonstrere hvor enkelt det var, ved å påstå at tre av fire gutter fra hvilken som helst nærliggende skole kunne lære seg systemet på et kvarter, så svarte undersekretæren hos utenriksdepartementet: "Ja, det er godt mulig, men du klarer ikke å lære det bort til attachéer."

Chifferet ble brukt for taktiske formål av de britiske styrker under andre boerkrig og under første verdenskrig, og for de samme formål av australske og tyske styrker under andre verdenskrig. Grunnen til dette var at Playfair var relativt raskt å bruke, og krevde inget spesielt utstyr. En typisk bruksområde var å beskytte ikke-kritiske, men allikevel viktige hemmeligheter under selve kamphandlingen. Når fiendens kryptoanalytikere dekodet meldingen, var som regel informasjonen utdatert og ikke lenger av verdi for dem.

Playfair er ikke lenger i bruk av militære styrker, da digitale krypteringsenheter har kommet for å bli. Playfair er nå regnet som usikker for alle formål, da moderne håndholdte datamaskiner lett kan knekke chifferet i løpet av få sekunder.

Den første publiserte løsningen på Playfair-chifferet ble beskrevet, i en 19-siders folder, av løytnant Joseph Mauborgne, utgitt i 1914.

 Hvordan bruke Playfair 

Playfair-chifferet bruker en 5 x 5 tabell som inneholder et nøkkelord eller frase. Å memorere nøkkelordet og fire enkle regler er alt som skal til for å lage tabellen og bruke chifferet.

For å lage tabellen, fyll først inn nøkkelordet i tabellen, men dropp eventuelle mellomrom og duplikate bokstaver. Fyll så resten av tabellen med resten av alfabetet (basert på det 26-tegn lange engelske alfabetet), men hopp over bokstavene som allerede er i bruk i nøkkelordet. Noen versjoner bruker "I" og "J" på samme plass, andre dropper bokstaven "Q", men man kan ta bort hvilken som helst bokstav som brukes få ganger. Nøkkelen kan skrives i topp-raden på tabellen, fra venstre til høyre, eller i andre mønstre, i en spiral som starter i øverste venstre hjørne, eller hvilken som helst annen måte, så lenge avsender og mottaker av den krypterte meldingen er enige og innforstått med metoden som er brukt. Nøkkelordet pluss metoden for å fylle ut resten av tabellen er så krypteringsnøkkelen i chifferet.

For å kryptere en melding, bryt opp meldingen i digrafer (2 og 2 bokstaver), slik at eksempelvis "HelloWorld" blir "HE LL OW OR LD"

 Om en digraf (2-bokstavsgruppe) er to like bokstaver, sett inn en "X" etter den første bokstaven, og forskyv så resten av bokstavene. Om den siste digrafen består av bare en bokstav, legg på en "X"

"HelloWorld" vil etter dette bli: "HE LX LO WO RL DX"

Om man så finner de to bokstavene i en digraf i tabellen, så vil de forme hjørnene i ett rektangel inne i tabellen. Merk deg den relative posisjonen for rektangelet, og bruk så de følgende reglene i rekkefølge for hvert par klartekst:

Om bokstavene ligger på samme rad i tabellen, erstatt dem med bokstaven rett til høyre for den enkelte bokstaven (slå rundt til venstre side av tabellen om den opprinnelige bokstaven er helt til høyre på raden).
 Om bokstavene ligger på samme kolonne i tabellen, erstatt dem med bokstaven rett under den enkelte bokstaven (slå rundt til toppen av tabellen om den opprinnelige bokstaven er helt i bunnen av kolonnen).
Om bkostavene ikke er på samme rad eller kolonne, erstatt dem med bokstaven som er på samme rad, i det andre "hjørnet" av rektangelet. 

Rekkefølgen er viktig, erstatt alltid den første bokstaven først, så den andre.

For å dekryptere, bruk de samme reglene, men baklengs (dropp ekstra "X"er som ikke gir noen mening i den resulterende klarteksten).

Se nedestående eksempel for en detaljert gjennomgang av en kryptering med Playfair-chifferet.

 Eksempel 

Ved å bruke "manchester" som nøkkel, så blir tabellen som følger:

 M  A  N  C  H
 E  S  T  R  B
 D  F  G I/J K
 L  O  P  Q  U
 V  W  X  Y  Z

Legg merke til at I og J deler plass.

Vi må først forberede klarteksten for kryptering. For å kryptere meldingen "THIS SECRET MESSAGE IS ENCRYPTED", grupperer vi først bokstavene to og to (digrafer). Om bokstavene i en gruppe er like, sett inn en X mellom dem. Om den siste gruppen bare har én bokstav, legg til en X:

 TH IS SE CR ET ME SX SA GE IS EN CR YP TE DX

Så skal vi starte krypteringen av hver digraf. Lokaliser bokstavene T og H i tabellen, og finn bokstavene som finnes i de motsatte "hjørnene" i rektangelet som formes:

 .  .  N  .  H
 .  .  T  .  B
 .  .  .  .  .
 .  .  .  .  .
 .  .  .  .  .

Om man så erstatter digrafen man kryptere med disse to bokastvene, så blir den resulterende digrafen BN, da man starter med bokstaven på samme rad som første bokstaven i den opprinnelige digrafen. Bruk samme logikk på neste digraf, IS → FR.

 TH IS SE CR ET ME SX SA GE IS EN CR YP TE DX
 BN FR

Videre, S og E ligger i samme rad:

 .  .  .  .  .
 E  S  T  .  .
 .  .  .  .  .
 .  .  .  .  .
 .  .  .  .  .

I dette tilfellet så bruker vi bokstaven rett til høyre for den opprinnelige, slik at SE blir til TS.

 TH IS SE CR ET ME SX SA GE IS EN CR YP TE DX
 BN FR TS

Neste bokstavgruppe, CR ligger i samme kolonne:

 .  .  .  C  .
 .  .  .  R  .
 .  .  . I/J .
 .  .  .  .  .
 .  .  .  .  .

Bruk da bokstaven rett under den opprinenlige, slik at CR → RI. Fortsett å kryptere hver digraf på samme måte:

 TH IS SE CR ET ME SX SA GE IS EN CR YP TE DX
 BN FR TS RI SR ED TW FS DT FR TM RI XQ RS GV

I de tilfeller hvor det ikke er noen bokstav til høyre for, eller rett under, "gå rundt" tabellen, og bruk bokstaven på motsatt side.

Slå så sammen digrafene av den resulterende chifferteksten, og du har så kryptert meldingen "THIS SECRET MESSAGE IS ENCRYPTED" til "BNFRTSRISREDTWFSDTFRTMRIXQRSGV". 

For å dekryptere, gjør motsatt av fremgangsmåten overfor, og husk at nøkkelen er "MANCHESTER".

 Playfair kryptoanalyse 

På lik linje med de fleste post-moderne chiffre eller kryptogrammer, så kan Playfai-chifferet enkelt knekkes om det finnes nok tekst. Å finne krypteringsnøkkelen er relativt enkelt om både klartekst og chiffertekst er kjent. Når kun chifferteksten er kjent, så brukes "rå kraft" (brute-force) kryptoanalyse. Dette gjøres ved å søke gjennom nøkkelrommet for samsvarheter mellom hyppigheten av digrafer og den kjente hyppigheten av digrafer i det språk man antar meldingens klartekst er skrevet i.

Kryptoanalyse av Playfair er ganske lik fire-kvadrat og to-kvadrat-chiffer, selv om den relative enkeltheten i Playfair-chifferet gjør det enklere å identifisere kandidater til klartekst-strenger. Det som er viktig å legge merke til, er at en digraf i Playfair og den motsatte digrafen (f.eks. AB og BA) bli dekryptert til det samme tegnmønsteret i klarteksten (f.eks. RE og ER). På engelsk finnes det mange ord som inneholder reverserte digrafer, slik som REceivER og DEpartED. Ved å identifisere reverserte digrafer i chifferteksten, og sammenligne mønsteret med en liste kjente klartekstord med samme mønster, så har man en enkel måte å generere mulige klartekststrenger, som kan brukes for å konstruere nøkkelen som ble benyttet.

En annen innfallsvinkel for å takle et Playfair-chiffer er å bruke fjellklatrermetoden. Denne starter ved å velge ut en tilfeldig tabell. Deretter endrer man litt etter litt, ved å bytte bokstaver, rader eller bruke speilbilde av hele tabellen for å se om mulige klartekster ligner mer på standard klartekster enn før endringen (kanskje ved å sammenligne digrafene med et kjent frekvenskart). Om den nye tabellen viser seg å være en forbedring, så brukes denne som utgangspunkt, og man fortsetter på samme måte med denne, for å finne en ennå bedre egnet kandidat for krypteringsnøkkelen. Til slutt vil klarteksten eller noe som ligner veldig på denne bli funnet for å få en maksimum uttelling på den graderingsmetoden man har valgt. Denne metoden er iøynefallende nok veldig trettende og langdryg for mennesker å utføre, men datamaskiner kan bruke denne algoritmen for å knekke Playfair-chiffer med relativt lite tekst som utgangspunkt.

Et annet aspekt som skiller Playfair fra fire-kvadrat og to-kvadrat-chiffere, er det faktum at chifferteksten aldri vil inneholde en dobbelt-bokstavs digraf, f.eks. EE. Om det ikke er noen doble bokstaver i chifferteksten, og lengden på teksten er lang nok til å gjøre dette statistisk signifikant, så er det veldig sannsnlig at krypteringsmetoden er Playfair.

En grei instruksjon på hvordan rekonstruere krypteringsnøkkelen i et Playfair-chiffer kan finnes i kapittel 7 i "Solution to Polygraphic Substitution Systems," i Field Manual 34-40-2, utgitt av United States Army.

En detaljert kryptoanalyse av Playfair blir gjennomgått i kapittel 28 av Dorothy L. Sayers' kriminalnovelle Have His Carcase. I denne historien blir et melding kryptert med Playfair demonstrert som kryptografisk svak, da detektiven klarer å finne hele krypteringsnøkkelen ved å bare gjøre noen få antagelser om meldingens format (i dette tilfellet så starter meldingen med et stedsnavn og en dato). Boken inneholder en detaljert beskrivelse av mekanismen i Playfair, samtidig som den gir en steg-for-steg beskrivelse av manuell kryptoanalyse.

Den tyske hæren, flyvåpenet og politiet brukte Dobbel Playfair som et middels sikkert chiffer under den andre verdenskrig. I og med at de hadde knekt chifferet tidlig i første verdenskrig, så hadde de tilpasset den ved å introdusere en sekundært tabell, hvorfra bokstav nummer to i hver digraf ble hentet, og sendt med nøkkelordet, slik at bokstavene ble satt i en tilfeldig rekkefølge. Men, med den tyske forkjærligheten for "pro forma" eller formelle meldinger, så ble de rask løst av Bletchley Park. Meldinger ble innledet med et skevensielt nummer, og tallene ble stavet. Siden de tyske tallene 1 (eins) til 12 (zwölf) inneholder alle tyske bokstaver bortsett fra åtte i de doble Playfair-tabellene, så ble pro forma trafikk en enkel sak å knekke.

Noter

 Eksterne lenker 
 Online kryptering og dekryptering av Playfair i JavaScript
  Extract from some lecture notes on ciphers – Digraphic Ciphers: Playfair

Kategori:Kryptografi
Kategori:Kryptografiske algoritmer
Kategori:Matematikkens historie