[Prethodno poglavlje]   [Sljedeće poglavlje]   [Sadržaj]

1.4. Playfairova šifra

Jedna ideja za poboljšanje supstitucijskih šifara je uvođenje polialfabetskih šifara. Jednu takvu šifru smo vidjeli u prethodnom poglavlju. Druga ideja je uporaba blokova slova kao osnovnih elemenata otvorenog teksta. No, veliki je problem kako spretno realizirati tu ideju, jer već za blokove od dva slova treba opisati (zapamtiti, sigurno prenijeti) šifrate od 262 = 676 elemenata otvorenog teksta. Prikazat ćemo najpoznatiju takvu šifru, tzv. Playfairovu šifru. Ovu šifru je izumio britanski znanstvenik Charles Wheatstone 1854. godine, a ime je dobila po njegovom prijatelju barunu Playfairu od St. Andrewsa koji ju je popularizirao.

To je bigramska šifra, u smislu da se šifriraju parovi slova i to tako da rezultat ovisi i o jednom i o drugom slovu. Algoritam za šifriranje se bazira na 5 × 5 matrici slova, koja se konstruira koristeći ključnu riječ. Na primjer, ako je ključna riječ   PLAYFAIR, onda matrica izgleda ovako: 


              P   L   A   Y   F  

              IJ  R   B   C   D  

              E   G   H   K   M  

              N   O   Q   S   T  

              U   V   W   X   Z
Budući da imamo 25 slova, dogovor je da se slova I i J poistovjete. U slučaju da je otvoreni tekst na hrvatskom jeziku, mi ćemo poistovjećivati V i W da bismo izbjegli moguće nesporazume kod dešifriranja.

Šifriranje se sada vrši na sljedeći način. Najprije podijelimo otvoreni tekst na blokove od po dva slova. Pritom pazimo da se niti jedan blok ne sastoji od dva jednaka slova, te da je duljina teksta parna. I jedno i drugo postižemo umetanjem npr. slova X ukoliko je to potrebno.

Kod šifriranja bloka od dva slova, mogu nastupiti tri slučaja, ovisno o položaju slova u matrici:

  1. Slova se nalaze u istom retku. Tada ih zamijenimo sa slovima koja se nalaze za jedno mjesto udesno (ciklički, tj. iza najdesnijeg slova dolazi najljevije slovo iz istog retka). Npr. EH ↦ GK, ST ↦ TN, FP ↦ PL.
  2. Slova se nalaze u istom stupcu. Tada ih zamijenimo sa slovima koja se nalaze za jedno mjesto ispod (ciklički, tj. iza najdonjeg slova dolazi najgornje slovo iz istog stupca). Npr. OV ↦ VL, KY ↦ SC, PI ↦ IE.
  3. U protivnom, pogledamo pravokutnik koji određuju ta dva slova, te ih zamijenimo s preostala dva vrha tog pravokutnika. Redoslijed je određen tako da najprije dođe ono slovo koje se nalazi u istom retku kao prvo slovo u polaznom bloku. Npr. OC ↦ SR, RK ↦ CG, PD ↦ FI.

Primjer 1.8: Šifrirajmo otvoreni tekst   CRYPTOGRAPHY pomoću Playfairove šifre s ključem   PLAYFAIR.

Rješenje.   CR YP TO GR AP HY   ↦   DB FL NQ OG YL KA

Playfairova šifra ima nekoliko značajnih prednosti pred supstitucijskom šifrom. Budući da je šifra bigramska, gube se u šifratu jednoslovne riječi (npr. "a") koje dosta utječu na frekvencije. Nadalje, bigramsko šifriranje smanjuje na polovicu broj elemenata dostupnih analizi frekvencije. S druge strane, broj bigrama je puno veći od broja individualnih slova (26 slova - 676 bigrama), dok su frekvencije najfrekventnijih bigrama puno ujednačenije od frekvencija najfrekventnijih slova.

Iz ovih razloga, Playfairova šifra je dugo vremena smatrana sigurnom. Tako je bila standardna šifra u britanskoj vojsci za vrijeme 1. svjetskog rata, a čak je korištena (za šifriranje poruka manje važnosti) i u američkoj vojsci u 2. svjetskom ratu.

Ipak, kod dugih tekstova ova šifra postaje nesigurna jer se može iskoristiti analiza frekvencija bigrama. Poznato je da i kod ove šifre dio strukture jezika ostaje sačuvan. Naime, slova u šifratu nisu jednoliko raspoređena. Dok u otvorenom tekstu na engleskom jeziku najfrekventnije slovo ima relativnu frekvenciju ≈ 13%, u šifratu dobivenom Playfairovom šifrom to iznosi ≈ 7%, dok recimo kod Vigenereove šifre imamo ≈ 6%. Takvi podatci mogu nam pomoći i kod određivanja vrste šifre.

Primjer 1.9: Dekriptirati šifrat 

       CK FL ET IJ KS VI XG IE QO SA
       GA PL TE AU KH CA ET AF CK TO
       IV OV OI AD BS HM HA OJ AF VU
       OL HN TY LS AB PJ OL PJ AI LO
       AJ HT CS VI OJ VC UI VI XG IE
       ZC AI BS HM IE AJ SJ NT SJ AF
       OJ VC ZA PJ JT HT ET OJ FJ
dobiven Playfairovom šifrom (V = W). Otvoreni tekst je na hrvatskom jeziku.

Rješenje. Ovaj šifrat je prekratak da bi ga dekriptirali samo analizom frekvencija bigrama. Zato ćemo uvesti dodatnu pretpostavku da nam je poznata jedna riječ koja se pojavljuje u otvorenom tekstu. Dakle, koristit ćemo metodu "vjerojatne riječi". Metoda se sastoji u tome da se napravi lista riječi ili fraza za koje pretpostavljamo da ih otvoreni tekst sadrži, te da u šifratu pronađemo segment čija se struktura podudara sa strukturom vjerojatne riječi. Recimo da je vjerojatna riječ (fraza) "MATEMATIKA I MATEMATIČARI". Kod rastavljanja na blokove po dva slova, imamo dvije mogućnosti (u ovisnosti o tome gdje se ovaj tekst nalazi unutar poruke): 

       MA  TE  MA  TI  KA  IM  AT  EM  AT  IČ  AR  I* 

       *M  AT  EM  AT  IK  AI  MA  TE  MA  TI  ČA  RI
Sada bismo u šifratu potražili segment koji ima neku od ove dvije strukture (po dva ponavljanja s istim ovakvim razmacima). Ovakav napad je često vrlo efikasan. U praksi se on sprječava tako da se vjerojatne riječi najprije "kodiraju" (npr. MATEMATIKA = ABC, MATEMATIČARI = ADE), a tek potom šifriraju. Budući da nam je poznat šifrat, to znači da smo već poduzeli (uspješnu) akciju presretanja poruke, pa nije nerealno pretpostaviti da naslućujemo barem nešto o njenom mogućem sadržaju. Također, često su poznate neke informacije o strukturi poruke (zaglavlje, datum, kome je naslovljena, od koga potpisana, i sl.).

No, za potrebe našeg primjera, mi ćemo pretpostaviti da otvoreni tekst sadrži riječ MINISTARSTVO (u nekom padežu). Pogledajmo strukturu ove riječi: 

       MI   NI   ST   AR   ST   VO
Identičnu strukturu uočavamo u 4. retku šifrata i krećemo s pretpostavkom da je LS AB PJ OL PJ šifrat of MI NI ST AR ST. To je u skladu s analizom frekvencija bigrama:

OJ (4), PJ, AF, IE, ET, VI (3),

jer visoko frekventni bigram u hrvatskom jeziku ST, odgovara visoko frekventnom bigramu PJ u šifratu. Dakle, imamo:

LS ↦ MI, AB ↦ NI, PJ ↦ ST, OL ↦ AR.

Pokušajmo krenuti u popunjavanje kvadrata za šifriranje. Krenimo s prvom, trećom i četvrtom supstitucijom. Uz pretpostavku da se slova u tim supstitucijama ne nalaze u istom retku ili stupcu, dobivamo (do na permutaciju redaka ili stupaca, ili njihovo spajanje) konfiguraciju 
                   A       O  

                   L   M   R  
       
               T       J

               P   I   S
Za očekivati je da OJ odgovara nekom visoko frekventnom bigramu (osim ST i RA), a to su JE, NA i AN. Ako JE ↦ OJ, onda su E, J, O susjedna slova u istom retku ili istom stupcu, pa taj slučaj možemo barem privremeno odbaciti. To znači da O, J, N, A ili čine pravokutnik ili se nalaze u istom retku ili stupcu. Jedina je mogućnost da retke s A i O, te T i J spojimo, pa tom retku još pridodamo N. Taj redak izgleda

_ A J _ N O _       ili       _ N J _ A O _

s tim da još treba na neko prazno mjesto ubaciti slovo T. No, ovih 5 slova je toliko "porazbacano" u abecedi da je jasno da je ovaj redak dio ključa. Zaključujemo da je taj redak TAJNO, te da je to prvi redak. Također je vrlo vjerojatno da je segment PIS dio ključa, pa ga pomaknimo u drugi redak. Tako dobivamo: 
              T   A   J   N   O

              P   I   S 

                  L   M       R
Odavde se vrlo vjerojatnom čini pretpostavka da je ključna riječ TAJNOPIS. Popunimo kvadrat i provjerimo pretpostavku: 
              T   A   J   N   O

              P   I   S   B   C
  
              D   E   F   G   H

              K   L   M   Q   R

              U   V   X   Y   Z
Dešifriranjem dobivamo: 
PR EM DA SA MP LA YF AI R nije nikad tvrdio
da je pronalazač te šifre, ona je u žargonu
Ministarstva rata dobila naziv Playfairova
šifra i taj x joj x je naziv ostao do danas x.

[Prethodno poglavlje]   [Sljedeće poglavlje]   [Sadržaj]
Web stranica kolegija Kriptografija Andrej Dujella - osobna stranica