Šifra transpozicije

Šifra transpozicije ili šifra pomeranja je metod šifrovanja u kriptografiji kojim se elementi otvorenog teksta (koji su obično karakteri ili grupe karaktera) ostave nepromenjeni ali se promeni njihov međusobni položaj tako da šifrat predstavlja permutaciju otvorenog teksta, čime se redosled jedinica menja (otvoreni tekst se preraspoređuje). Matematički bijektivna funkcija se koristi na pozicijama karaktera za šifrovanje, a inverzna funkcija za dešifrovanje.

Sledi nekoliko implementacija.

Šifra šina-ograda

Šifra šina-ograda je šifra transpozicije koja je dobila svoje ime na osnovu načina kodiranja.U ovoj šifri, otvoreni tekst je napisan prema dole na uzastopnim "šinama" neke imaginarne ograde, a zatim se kreće gore kada dođemo do dna. Poruka se potom čita u redovima. Na primer, koristeći tri "šine" i poruku “OTKRIVENI SMO. POBEGNITE ODMAH” se šifrovano piše:

O...I...I...P...G...E...A.

.T.R.V.N.S.O.O.E.N.T.O.M.H

..K...E...M...B...I...D...

Čita se:

OIIPG EATRV NSOOE NTOMH KEMBID

(Šifra je slomljena na pet blokova da bi se izbegle greške. Ovo je uobičajena tehnika koja se koristi da bi šifra bila čitljivija. Razmak u šifri se ne odnosi na razmak u otvorenom tekstu i tako da nema nikakvu informaciju o otvorenom tekstu.)

Skitala

Šifru šine-ograde su koristili drevni Grci u skitali, mehanički sistem za transpoziciju šifre. Sistem se sastojao od cilindra i trake koja je obmotana oko cilindra. Poruka koja je kodirana je namotana na traku. Pisma originalne poruke se promene kada se traka odmota. Međutim, poruku je lako dešifrovati kada se traka strgne sa cilindra istog prečnika kao i kodirani cilindar

Šifra rute

U šifri rute, otvoreni tekst je pisan u obliku mreže datih dimenzija, zatim se očitava u obrascu datom u ključu. Na primer, koristeći otvoreni tekst : “OTKRIVENI SMO.POBEGNITE”.

O R E S P E I

T I N M O G T

K V I O B N E

Ključ se može odrediti "spiralno ka unutra,u smeru kazaljke na satu, počevši od gornjeg desnog ugla". To bi dalo šifru:

ITEN BOIV KTOR ESPE GOMNI

Ove šifre imaju mnogo više ključeva od šifre šina-ograda. U stvari, za poruke razumne dužine, broj mogućih ključeva je preveliki da se prebroji čak i na modernim mašinama. Međutim, nisu svi ključevi jednako dobri. Loše odabrane rute će ostaviti mnogo delova otvorenog teksta ili će tekst jednostavno obrnuti, i to će dati kriptoanalitičaru trag ka ruti.

Varijacija na šifre ruta je “Unija šifri ruta”, korišćena od strane “snage Unije” tokom Američkog građanskog rata. Ovo je ličilo na običane šifre ruta, ali zamenjene su cele reči umesto pojedinačnih slova. Jer bi to ostavilo neke veoma osetljive reči izložene, te reči se prvo sakriju kodom (kriptografskim). Službenik za šifre može takođe dodati null reči, koje se često biraju da bi šifrat postao duhovit.

Transpozicija kolona

U transpoziciji kolona, poruka je ispisana u redovima fiksne dužine, a zatim se pročita ponovo kolonu po kolonu, a kolone su izabrane u nekom permutovanom redosledu. Ključna reč obično definiše širinu redova i permutaciju po kolonama. Na primer, reč KENGUR je dužine 6 (tako da su redovi dužine 6), a permutacija je definisana azbučnim redosledom slova ključne reči. U ovom slučaju, redosled bi bio "3 2 4 1 6 5".

U pravilnoj transpoziciji kolona, bilo koji rezervni prostori su null; u nepravilnim transpozicijama kolona, prostori se ostavljaju prazni. Na kraju, poruka se čita po kolonama, u redosledu koji je određen ključnom rečju. Na primer, pretpostavimo da koristimo ključnu reč KENGUR i poruku OTKRIVENI SMO. POBEGNITE ODMAH. U redovnoj transpoziciji kolona, pišemo na sledeći način:

3 2 4 1 6 5

O T K R I V

E N I S M O

P O B E G N

I T E O D M

A H Dž Z Lj P

Poslednja 4 slova su upravo null(DžZLjP). Šifrat se potom čita kao:

RSEO3 TNOTH OEPIA KIBEDž VOMNŽ IMGDLj.

U nepravilnom slučaju, kolone nisu završene sa null:

3 2 4 1 6 5

O T K R I V

E N I S M O

P O B E G N

I T E O D M

A H

Šifrat je:

RSEOT NOTHO EPIAK IBEVO NMIMGD

Da se dešifruje, primalac mora da radi po dužinama kolona tako što dužinu poruke deli dužinom ključne reči. Tada može ponovo da napiše poruku po kolonama, a zatim preraspodeli kolone tako što će ponovo formirati ključnu reč.

U slučaju da je poruka blokirana u segmente čija je dužina ključne reči velika na svakom segmentu se primenjuje ista permutacija (dodeljena od strane ključa). Ovo je ekvivalentno transpoziciji kolona gde je čitanje po redovima umesto po kolonama.

Transpozicija kolona se koristi za ozbiljnije svrhe, kao sastavni deo složenijih šifara još od 1950-ih godina.

Dvostruka transpozicija

Transpozicije sa jednom kolonom mogu biti napadnute pogađanjem moguće dužine kolone, ispisivanjem poruka u svoje kolone (ali u pogrešnom redosledu, kako ključ još uvek nije poznat), a zatim traženjem mogućih anagrama. S obzirom da je jača, dvostruka transpozicija često je korišćena. Ovo je jednostavno transpozicija kolona primenjena dvaput. Isti ključ može biti korišćen za obe transpozicije, ili dva različita.

Kao primer možemo uzeti rezultat nepravilne transpozicije kolona u prethodnom delu, i izvršiti drugu enkripciju sa različitomm ključnom rečju, LUSTER, proizvodi permutaciju "2 6 4 5 1 3".

2 6 4 5 1 3

R S E O T N

O T H O E P

I A K I B E

V O N M I M

G D

Kao i ranije, ovo se čita po kolonama da bi se dobio šifrat.

TEBIR OIVGN PEMEDž KNOOI MSTAOD

Ako je više poruka, potpuno iste dužine, šifrovano koristeći iste ključeve, od njih mogu istovremeno da se naprave anagrami. Ovo može dovesti kako do razbijanja poruke,tako i do razbijanja ključeva (tako da svaka druga poruka poslata sa tim ključevima može biti pročitana).

Tokom Prvog svetskog rata, Nemačka vojska je koristila šifru dvostruke transpozicije kolona, retko menjajući ključeve. Sistem je regularno rešen od strane Francuza, zvanog Ubhi, koji je mogao da pronađe ključeve jednom kada je prekinut broj poruka iste dužine, što je obično trajalo nekoliko dana. Međutim, uspeh Francuza je postao široko poznat, nakon objavljivanja u Matinu, i Nemci su promenili sistem 18. novembra 1914. godine. Tokom Drugog svetskog rata, dvostruku transpoziciju šifre koristile su Holandske grupe otpora, francuski Maki i britanska Uprava za specijalne operacije, koja je bila zadužena za upravljanje podzemnim aktivnostima u Evropi.Takođe je korišćena od strane agenata američke Kancelarije za strateške usluge i u hitnim slučajevima kao šifra za nemačku vojsku i mornaricu.

Sve do pronalaska VIK šifra, dvostruka transpozicija je generalno smatrana za najkomplikovaniju šifru tako da je agent mogao pouzdano da radi pri teškim uslovima na terenu.

Mizkovski transpozicija

Jedna od varijanti oblika transpozicije kolona, koju je predložio Emil Viktor Teodor Mizkovski 1902. godine, zahteva ključnu reč sa ponovljenim slovima. U uobičajenoj praksi, kasnija pojavljivanja slova ključne reči se tretiraju kao da su naredna slova po azbučnom redu, na primer, ključna reč LISICA daje numerički ključni niz " 4 2 5 3 6 1 ". U transpoziciji Mizkovski, slova koja se ponavljaju u ključnoj reči su numerisana isto, LISICA, daje ključni niz " 3 2 4 2 5 1".

3 2 4 2 5 1

O T K R I V

E N I S M O

P O B E G N

I T E O D M

A H

Otvoren tekst u kolonoma sa jedinstvenim brojevima se prepisuje odozgo naniže, a u kolonama gde se brojevi ponavljaju sleva nadesno:

VONMT RNCOE TOHOE PIAKI BEIMGD

Prekinuta transpozicija

U prekinutoj transpoziciji, određene pozicije u mreži su blokirane, i ne popunjavaju se prilikom unosa teksta. Ovo prekida redovne modele i čini kriptoanalitičarev posao još težim.

Rešetke

Transpozicija zamene koja koristi rešetke ili fizičke maske sa isečcima. Ovo može da proizvede veoma nepravilnu transpoziciju u periodu određenom veličinom rešetke, ali zahteva da dopisnici čuvaju tajnu o fizičkom ključu. Rešetke su prvi put predložene 1550. godine, i bile su korišćene u vojne svrhe prvih nekoliko meseci Prvog svetskog rata.

Transpozicija i kriptoanaliza

S obzirom da transpozicija ne utiče na učestalost pojedinačnih simbola, jednostavna transpozicija lako može biti detektovana kriptoanalizom, određivanjem stepena učestalosti. Ukoliko u šifrovanom tekstu postoji frekventna distribucija koja je slična otvorenom teksu, verovatno se radi o transpoziciji. Ovo može biti rešeno anagramiranjem - premeštanje delova šifrata, zatim potragom za delovima koji liče na anagrame Srpskih reči, i na kraju rešavanje anagrama.

Jednom kada su anagrami pronađeni, oni će nam otkriti informacije o šablonima transpozicije, i oni stoga mogu biti dalje istraženi.

Kod jednostavnijih transpozicija takođe može da postoji problem zbog činjenice da će ključ koji je veoma blizu pravoga ključa otkriti dugačke sekvence legitimnog teksta koje će biti praćene umetnutim besmislenim tekstom. Shodno tome, takve šifre mogu biti ranjive na optimalne algoritme traženja kao što je genetski algoritam.

Detaljan opis kriptoanalize nemačkog transpozicionog šifarnika može se naći u sedmom poglavlju Herbert Jardlijeve knjige "Američki crni kabinet".

Kombinacije

Transpozicija se često kombinuje sa drugim tehnikama kao što su evaluacione metode.

Na primer, jednostavnim kombinovanjem substitucionog šifrovanja sa transpozicijom kolona, izbegavamo slabosti obe metode. Zamenom visokofrekventnih simbola u šifrovanom tekstu sa velikom količinom slova otvorenog teksta, ne otkrivamo delove teksta usled transpozicije. Anagramiranje transpozicija neće biti od koristi zbog substitucije. Tehnika kombinovanja je posebno moćna kada se upotrebi u kombinaciji sa frakcionisanjem. Mane su to što su ovakve šifre znatno teže i podložnije greškama od jednostavnih šifri.

Frakcionisanje

Transpozicija je posebno efektna kada se primeni u kombinaciji sa frakcionisanjem - koja je preliminarna faza koja deli svaki simbol ootvorenog teksta na nekoliko šifrovanih simbola. Na primer, alfabet otvorenog teksta može biti ispisan u obliku koordinatne mreže, i zatim svako slovo u poruci može biti zamenjeno sa njegovim koordinatama. Druga metoda frakcionisanja je jednostavno prevođenje poruke u Morzeovu abuku, sa uključenim simbolima za razmake kao i za tačke i zareze.

Kada se ovakva frakcionisana poruka transpozicionira, komponente pojedinih slova postaju široko razdvojene u poruci, na taj način postižući Klod Elvud Šenunovu difuziju. Primeri šifara koji kombinuju frakcionisanje i transpoziciju uključuju: bifidska šifra, trifidska šifra, ADFGVX šifra i VIK šifra.

Još jedan način bio bi da se svako slovo zameni sa svojom binarnom reprezentacijom, ovo se transpozicionira, i onda se novi binarni niz pretvori u odgovarajuće ASKI karaktere.

Ponavljanje procesa transpozicije na binarnom nizu više puta pre nego što ga promenimo u ASKI karaktere bi verovatno učinilo ovaj kod težim za dekodiranje. Veliki broj modernih blok šifara koristi kompleksnije forme transpozicije koje su bazirane na ovoj prostoj ideji.

Literatura

• Kahn, David (1996). The Codebreakers: The Story of Secret Writing. Scribner. 
• Yardley, Herbert (1931). The American Black Chamber. Bobbs-Merrill.