Playfair-rejtjel

A Wikipédiából, a szabad enciklopédiából

A Playfair-rejtjel vagy Playfair-négyzet egy szimmetrikus kézi kódolási módszer, amely az első szó szerinti digrafikus helyettesítő rejtjel volt. 1854-ben Charles Wheatstone találta fel, de legfőbb támogatójának, Lord Playfairnek a nevét viseli.

A módszer betűpárokat (digráfokat vagy bigrammákat) kódol, szemben az abban az időben használatos egyszerű helyettesítő rejtjelekkel és bonyolultabb Vigenère-kódokkal, amelyek a betűket helyettesítették. Tehát a Playfairt sokkal nehezebb feltörni, hiszen az egyszerű helyettesítő rejtjelek megfejtésére használt gyakoriságelemzés itt nem működik. Pontosabban fogalmazva használható, de az angol nyelvben több mint 600 betűpárra a 26 betű helyett, a magyar nyelvben 1600 betűpárra a 40 betű helyett. A betűpárok gyakoriságelemzése lehetséges, de jóval bonyolultabb, és sokkal nagyobb kódolt szövegre van szükség, hogy legyen valami haszna.

Története[szerkesztés | forrásszöveg szerkesztése]

Lord Playfair támogatta a rejtjel használatát, és ezáltal fonódott össze a neve a rendszerrel.

A Playfair-kódról az első írásos emlék 1854. március 26-áról származik, melyet bár Wheatstone írt alá, maga a rejtjel mégis Wheatstone barátjának, az azt népszerűsítő Lord Playfairnek a nevét viseli. A kidolgozásakor a brit külügyminisztérium a bonyolultságára hivatkozva elutasította. Amikor Wheatstone meg akarta nekik mutatni, hogy négy iskolás gyerekből három meg tudja tanulni használni 15 perc alatt, a külügyminisztérium államtitkára azt válaszolta, hogy "az lehet, de soha nem fogja tudni megtanítani a mi attaséinknak."

A második búr háborúban és az első világháborúban a brit hadsereg taktikai célokra használta, az ausztrálok pedig hasonló megfontolásokból a második világháború alatt. Ennek az oka az volt, hogy a Playfair meglehetősen gyorsan és bármiféle különleges felszerelés nélkül használható. A Playfair használatának egyik tipikus forgatókönyve a tényleges csata alatt fontos, de nem kritikus titkok megvédésére irányul. Mire az ellenség kriptanalitikusai feltörik a kódot, a szöveg tartalma már érvényét veszti. A digitális kódolóeszközök megjelenésével a Playfair katonai alkalmazása azonban megszűnt. A Playfairt ma már bármilyen célra megbízhatatlannak tartják – még az elavult Intel 80386-os PC is rövid idő alatt feltöri.

A Playfair-rejtjel első publikált megoldását Joseph O. Mauborgne hadnagy egy 19-oldalas füzetben írta le, 1914-ben.

A Playfair használata[szerkesztés | forrásszöveg szerkesztése]

(A Playfair-rejtjel csak az angol nyelvre működik, minthogy maga a rejtjel az angol ábécére lett tervezve, és az angol és magyar ábécékben a betűk számának jelentős eltéréséből adódóan a magyar nyelvre ezen formájában nem, legfeljebb a rendszer átalakításával lenne alkalmazható, azt pedig értelemszerűen már nem nevezhetnénk Playfair-rendszernek.)

A Playfair-rejtjel egy 5×5-ös táblát használ, amely tartalmaz egy kulcsszót vagy -kifejezést. Ennek a kulcsszónak a megjegyzése, valamint négy egyszerű szabály betartása volt minden, amit meg kellett tenni az 5x5-ös tábla elkészítéséhez és a kód használatához.

A kulcstábla elkészítéséhez először a kulcsszó betűivel kell kitölteni a mezőket (az ismétlődő betűket csak egyszer leírva), majd az üresen maradt helyeket az ábécé többi betűjével kell kitölteni (Ez általában a Q betű kihagyásával történik, hiszen a négyzet 25 mezőjébe nem fér be az angol ábécé mind a 26 betűje. Más változatok az I-t és a J-t egy betűként kezelik.) A kulcsszót írhatjuk a tábla legfelső sorába, balról jobbra, vagy valamilyen más elrendezés szerint, például a bal felső sarokból induló spirálban, amely középen végződik. A kulcsszó az 5×5-ös tábla kitöltési módjával együtt alkotja magát a kódot.

A szöveg kódolásához az eredeti szöveget két betűből álló csoportokba kell rendezni (például a "Playfair-rendszer" "PL AY FA IR RE ND SZ ER" lesz), amelyeket a kulcstáblán kell elosztani, majd egymás után alkalmazni az alábbi 4 szabályt az eredeti szöveg minden betűpárjára:

  • Ha egy pár mindkét eleme ugyanaz a betű, vagy már csak egy betű maradt az utolsó párba, akkor írjunk egy "X"-et az első betű után, és ezt az új párt kódoljuk. Néhány változat "X" helyett "Q"-t használ, de bármely ritka betű megteszi.
  • Ha egy pár mindkét betűje ugyanabban a sorban jelenik meg a kulcstáblán, akkor a tőlük közvetlenül jobbra állóval kell helyettesíteni őket (ha történetesen az egyik betű a sor jobb szélén van, akkor a sor bal szélén álló betűvel kell helyettesíteni).
  • Ha egy pár mindkét betűje ugyanabban az oszlopban jelenik meg a kulcstáblán, akkor közvetlenül az alattuk állóval kell helyettesíteni őket (ha az egyik betű az oszlop alján van, akkor az oszlop tetején álló betűvel kell helyettesíteni).
  • Ha egy pár betűi nincsenek sem egy sorban, sem egy oszlopban, akkor tekintsük azt a kulcstábla mezőiből felépülő téglalapot, amelynek a két betű a két szemközti csúcsa. A betűket a saját sorukban, a téglalap másik csúcsánál lévő betűkkel helyettesítjük.

A megfejtéshez az eljárás fordítottját kell végrehajtani (a fölösleges "X"-ek vagy "Q"-k elhagyásával a végső szövegből).

Példa[szerkesztés | forrásszöveg szerkesztése]

Mint említettük, a rendszer az angol nyelvre működik. Ha azonban az ékezetek elhagyjuk a magyar nyelvből, és a kettősbetűknek az elemeit külön-külön tekintjük, akkor a magyar nyelvre is alkalmazható. Legyen a "playfair rendszer" a kulcsszó, így a kulcstábla az alábbi módon fog kinézni:

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

Kódoljuk a "Rejtsd el az aranyat ott, a fa törzsében!" üzenetet:

RE JT SD EL AZ AR AN YA TO TX AF AT OR ZS EB EN
                            ^
  1. Az RE egy sorban van, így EN lesz belőle.
  2. A JT egy téglalapot formál, így HU lesz belőle.
  3. Az SD egy téglalapot formál, így GI lesz belőle.
  4. Az EL egy téglalapot formál, így RA lesz belőle.
  5. Az AZ egy téglalapot formál, így LB lesz belőle.
  6. Az AR egy téglalapot formál, így LE lesz belőle.
  7. Az AN egy téglalapot formál, így YE lesz belőle.
  8. Az YA egy sorban van, így FY lesz belőle.
  9. A TO egy téglalapot formál, így XH lesz belőle.
  10. A TX egy sorban van, így UT lesz belőle.
  11. Az AF egy sorban van, így YP lesz belőle.
  12. Az AT egy téglalapot formál, így PV lesz belőle.
  13. Az OR egy téglalapot formál, így DJ lesz belőle.
  14. A ZS egy sorban van, így BZ lesz belőle.
  15. Az EB egy oszlopban van, így BK lesz belőle.
  16. Az EN egy sorban van, így ND lesz belőle.
EN HU GI RA LB LE YE FY XH UT YP PV DJ BZ BK ND

Tehát a "Rejtsd el az aranyat ott, a fa törzsében!" üzenetből "ENHUGIRALBLEYEFYXHUTYPPVDJBZBKND" lesz.

Tisztázás képekkel[szerkesztés | forrásszöveg szerkesztése]

Tegyük fel, hogy valaki az AZ betűpárt akarja kódolni. Három alapvető eset lehetséges:

1)
* * * * *
* A P Z F
* * * * *
* * * * *
* * * * *

Itt AZ -> PF

2)
* * A * *
* * B * *
* * * * *
* * Z * *
* * Y * *

Itt AZ -> BY

3)
B * * A *
* * * * *
* * * * *
Z * * X *
* * * * *

Itt AZ -> BX

A Playfair kriptanalízise[szerkesztés | forrásszöveg szerkesztése]

A modern titkosírások előtti többi rejtjel rendszerhez hasonlóan, a Playfair is könnyen feltörhető, ha elegendő szöveg áll rendelkezésre. A kulcs megszerzése meglehetősen könnyű, ha ismerjük mind az eredeti, mind a kódolt szöveget. Ha csak a kódolt szöveg ismert, ún. "nyers erő" (brute force) típusú kriptanalízist kihasználva kell keressük azt, hol felel meg egymásnak a szövegben valamely betűpár gyakorisága az eredeti szöveg feltételezett nyelvében ismert gyakoriságával.

A Playfair kriptanalízise hasonlít a Két négyzet-rejtjel és a Négy négyzet-rejtjel kriptanalíziséhez, bár a Playfair viszonylagos egyszerűségéből adódóan itt könnyebb azonosítani az eredeti szöveg darabjait. A leglátványosabb jellemzője a Playfairnek hogy olyan betűpárok, amelyek egymás fordítottjai (palindrom betűpárok), azok kódolva is egymás fordítottjai lesznek. Az angol nyelvben rengeteg szóban találhatunk ilyen fordított betűpárokat, így a REceivER és DEpartED szavakban. Ha sikerül egymáshoz közül eső fordított betűpárokat felfedeznünk, akkor meg kell próbálni egy előre elkészített listáról szavakkal párosítani. Ez egy jó módszer arra, hogy valamilyen fonalon elinduljunk a kulcs felépítéséhez vezető úton.

Egy másik megközelítés a Playfairrel való megbirkózásra az ún. shotgun hillclimbing (kb. sörétespuskás hegymászás) módszer, amely egy véletlenszerűen kitöltött négyzettel indít, amelyen kisebb változtatásokat kell eszközölni (betűk, sorok felcserélése vagy az egész négyzet tükrözése), és mindig meg kell nézni, hogy az újonnan kapott feltételezett eredeti szöveg inkább hasonlít-e egy normál szöveghez, mint az előző (esetleg a betűhármasok egy ismert gyakorisági táblázattal való összehasonlításával). Ha az új négyzeten a fejlődés jelei mutatkoznak, akkor abból kiindulva végzünk további változtatásokat. Végül magát az eredeti vagy ahhoz nagyon közel eső szöveget kapunk, amely a legmagasabban áll a pontozó rendszerünk alapján, bármi is legyen az. Ez a módszer azonban nyilvánvalóan az emberi türelem határain túl van, ám számítógépek alkalmazhatják ezt az algoritmust a Playfair feltörésére, viszonylag kevés szöveg írásával.

Egy másik szempont, amiben különbözik a Playfair a két- és négy négyzet-kódtól, az az a tény, hogy a betűpárokon belül nem lehet két ugyanolyan betű, tehát ha a betűpárok között nem találunk olyat, amelyet két azonos betű építene fel, és a szöveg elég hosszú ahhoz, hogy statisztikailag szignifikáns legyen a megfigyelés, akkor nagyon valószínű, hogy a szöveg a Playfairrel lett kódolva.

A Playfair-rejtjel kulcsának újraszerkesztésére egy jó útmutató található angol nyelven a Field Manual 34-40-2 7. fejezetében, amelyet az USA hadserege készített.

A Playfair részletes kriptanalízisére Dorothy L. Sayers rejtélyes regényének, a "Have His Carcase"-nek 28. fejezetében vállalkozott. Ebben a történetben a Playfairrel kódolt üzenetet kriptográfiailag gyengének mutatja be a szerző, amelynek teljes egészét képes megfejteni a detektív mindössze néhány feltételezéssel az üzenet formázásával kapcsolatban (az üzenet egy város nevével kezdődik, majd egy évszámmal folytatódik). Sayers könyve a Playfair-kódolás mechanizmusának részletes leírását tartalmazza a kézi kriptanalízis lépéseivel egyetemben (sok online ismertető azt tanácsolja, hogy ezt a fejezetet ugorjuk át, mivel túlságosan bonyolult és technikai)

A Nemzetközösség országaiban méltán népszerű ún. rejtett keresztrejtvények (mint például a The Times (Egyesült Királyság) szombati számában megjelenő The Listener Crossword) gyakran foglalnak magukba Playfair-rejtjeleket.

Külső hivatkozások[szerkesztés | forrásszöveg szerkesztése]