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

1.7. Transpozicijske šifre

Svi kriptosustavi koje smo do sada promatrali su uključivali supstituciju: elementi otvorenog teksta zamjenjivani su različitim elementima šifrata. Ideja transpozicijske šifre je da se elementi otvorenog teksta ostave nepromijenjeni, ali da se promjeni njihov međusobni položaj. Spomenimo da je podjelu šifri na supstitucijske i transpozicijske uveo u 16. stoljeću Giovanni Porta. Formalna definicija transpozicijske šifre je sljedeća:

Neka je m fiksan prirodan broj. Neka je P = C = (Z26)m, te neka se K sastoji od svih permutacija skupa {1, 2, ... , m}. Za π ∈ K definiramo

eπ (x1, ... , xm) = (xπ(1), ... , xπ(m)),
dπ(y1, ... , ym) = (yπ-1(1), ... , yπ-1(m)).

Postavlja se ponovo pitanje praktične realizacije ove opće ideje. U praksi najupotrebljavanija transpozicijska šifra bila je stupčana transpozicija. Kod nje se otvoreni tekst upisuje u pravokutnik po redcima, a zatim se poruka čita po stupcima, ali s promijenjenim poretkom stupaca. Ako se posljednji redak ne ispuni do kraja, onda se prazna mjesta popune proizvoljnim slovima (nulama) koja ne mijenjaju sadržaj poruke. (Koristili su se i nepotpuni pravokutnici, no mi ih ovdje nećemo analizirati.)

Primjer 1.12: Šifrirati otvoreni tekst   KRIPTOGRAFIJA I KRIPTOANALIZA   stupčanom transpozicijom s ključem   4 3 1 2 5 7 6.

Rješenje.

 
     ključ         4  3  1  2  5  7  6


                   K  R  I  P  T  O  G

                   R  A  F  I  J  A  I 
otvoreni tekst
                   K  R  I  P  T  O  A 

                   N  A  L  I  Z  A  X



    šifrat         IFILPIPIRARAKRKNTJTZGIAXOAOA

Prepoznavanje da se radi o transpozicijskoj šifri je vrlo jednostavno jer kod nje slova imaju iste frekvencije kao u otvorenom tekstu. U kriptoanalizi stupčane transpozicije, prvi korak je određivanje dimenzije pravokutnika. To se radi tako da se broj slova u šifratu faktorizira. Ukoliko time dobijemo više mogućnosti, upišemo slova šifrata po stupcima u pravokutnike pretpostavljenih dimenzija, te promatramo odnos samoglasnika i suglasnika u svakom retku. Ukoliko je pretpostavka o dimenziji točna, taj odnos ne bi smio puno odstupati od njihovog odnosa u jeziku otvorenog teksta (u hrvatskom 43% : 57%). Nakon što odredimo dimenzije, moramo još odrediti poredak stupaca. Ako je broj stupaca relativno mali, to će nam obično poći za rukom običnim anagramiranjem. Izrežemo vrpce koje sadrže stupce pravokutnika i premještamo ih dok ne dobijemo smisleni sadržaj u redcima. Dodatnu pomoć nam mogu dati podatci o frekvencijama bigrama.

Primjer 1.13: Dekriptirati šifrat

      AAOSA JRTIE EAAAU SCEAE IANPI
      JAJJN FVSOI RZVPH NIONA RNZIJ
      INUSS NTRZU TIC
dobiven stupčanom transpozicijom

Rješenje. U šifratu imamo 63 slova, pa nam se kao najvjerojatnije nameću dimenzije 7 × 9 i 9 × 7 (razumno je pretpostaviti da ni broj stupaca ni broj redaka nisu jako mali - u prvom slučaju bi anagramiranje bilo trivijalno za obaviti, a u drugom duljina ključa ne bi bila bitno kraća od duljine otvorenog teksta). Upišemo li šifrat u pravokutnike tih dimenzija, dobivamo:


A E A J Z I S   3:4              A T U A J R O J T   4:5
A E E J V N N   3:4              A I S N N Z N I R   3:6
O A I N P Z T   3:4              O E C P F V A N Z   3:6
S A A F H I R   3:4              S E E I V P I U U   5:4
A A N V N J Z   2:5              A A A J S H N S T   3:6
J U P S I I U   3:4              J A E A O N Z S I   5:4
R S I O O N T   3:4              R A I J I I I N C   5:4
T C J I N U I   3:4
I E A R A S C   4:3
Odnos samoglasnika i suglasnika sugerira da je prvi izbor dimenzija vjerojatniji. Sada ovih 7 stupaca možemo pokušati "anagramirati" tako da dobijemo smisleni tekst. Tu nam (barem na početku) može pomoći frekvencija bigrama. Bigrami koji u hrvatskom jeziku imaju frekvenciju veću od 0.8% su (abecednim redom):

AK, AN, AS, AT, AV, CI, DA, ED, EN, IC, IJ, IN, 
IS, JA, JE, KA, KO, LI, NA, NE, NI, NO, OD, OJ,
OS, OV, PO, PR, RA, RE, RI, ST, TA, TI, VA, ZA. 
Za svaki od parova redaka, pogledajmo koliko se od tako dobivenih 9 bigrama nalazi među ovih 36 najfrekventnijih. Tako se dobije sljedeća tablica:
      |  1   2   3   4   5   6   7
  ----------------------------------
   1  |      0   2   2   2   2   4
      |
   2  |  1       1   3   1   1   4
      | 
   3  |  2   2       1   0   3   2
      |
   4  |  5   6   5       2   0   0   
      |
   5  |  4   2   1   2       1   1 
      |
   6  |  5   4   2   2   1       0
      |
   7  |  3   5   4   0   1   1
Uočavamo da je broj 6 najveći od svih brojeva u tablici. Stoga krenimo od pretpostavke da stupci 4 2 dolaze jedan do drugoga (u tom poretku). Vjerojatno je već ovo dovoljno da pogodimo rješenje, ali možemo još iskoristiti tablicu. Eliminirajmo sve parove s frekvencijama bigrama 0 ili 1, te one koji su u kontradikciji s izborom 4 2, tj. par 2 4 i parove kojima je 4 na prvom ili 2 na drugom mjestu. Uočavamo kao vjerojatne parove (najbolji u retku i stupcu) 7 3 i 6 1. Također je vrlo vjerojatan par 2 7 (najbolji u retku). Čini se da bi 4 2 7 3 mogao biti dio ključa. Iz preostalih vrijednosti u tablici, kao najvjerojatniji ključevi se nameću

4 2 7 3 6 1 5,       5 1 6 4 2 7 3,       6 1 5 4 2 7 3.

Sada se lako provjeri da jedino drugi izbor daje suvisli tekst:
ZA RJEŠAVANJE NEPOZNATIH ŠIFARA NAJVAŽNIJI 
SU UPORNOST, INTUICIJA I SREĆA. 

             (Parker Hitt: Udžbenik za rješavanje vojnih šifara)

Napomenimo da se sigurnost transpozicijskih šifara može znatno povećati korištenjem više koraka transpozicije. Većina njemačkih šifri tijekom prvog svjetskog rata su bile dvostruke transpozicijske šifre. Ove šifre su vrlo sigurne, ali njihovo dekriptiranje postaje relativno jednostavno ako kriptoanalitičar raspolaže s nekoliko jednako dugih šifrata šifriranih istim ključem. Tada se dva šifrata ispišu jedan ispod drugog na dugim trakama papira, pa se trake okomito razrežu tako da po dva slova (jedno iz svakog šifrata) dođu na isti papirić. Ti se papirići sada slažu jedan uz drugog, sve dok se gore i dolje ne pojavi nešto nalik na otvoreni tekst.


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