Transpoziční šifra

Transpoziční šifra je základní kryptografická operace, její princip je v záměně pořadí písmen otevřeného textu. Tato operace musí být vykonána podle určitých pravidel, aby bylo možné text zpětně dešifrovat. Mezi jednoduché transpoziční šifry patří například psaní textu opačně.

Rail Fence šifra

Rail Fence šifra je forma transpoziční šifry, která dostala svoje jméno podle způsobu, kterým je kódovaná. V Rail Fence šifře se původní text (plaintext) píše sestupně na "koleje" jdoucí za sebou. Když se dostaneme na poslední "kolej" imaginárního plotu, pokračujeme dále směrem nahoru. Zpráva se potom čte v řádcích. Například použijeme tři "koleje" a zprávu "BYLI JSTE ODHALENI. HNED UTECTE", šifra se zapíše takto:

B . . . J . . . O . . . L . . . H . . . U . . . T .
. Y . I . S . E . D . A . E . I . N . D . T . C . E
. . L . . . T . . . H . . . N . . . E . . . E . . .

Potom se to čte takto:

BJOLH UTYIS EDAEI NDTCE LTHNE E

(Rozložíme potom tento zašifrovaný text do bloků po 5 písmen abychom předešli chybám.)

Route šifra

V route šifře se nejdříve původní text (plaintext) zapíše do mřížky daných rozměrů, potom se čte podle vzoru uvedeného v klíči. Na ukázku použijeme stejný text, který jsme použili při rail fence šifře.

BITDLIETT
YJEHEHDEE
LSOANNUC

Za klíč můžeme zvolit „pravotočivou spirálu dovnitř, začínající z pravého horního rohu“. Dostaneme takto zašifrovaný text:

TECUNNAOSLYBITDLIETEDHEHEJ

Sloupcová transpozice

V sloupcové transpozici je zpráva psaná v řádcích přesně určené délky a následně je čtená sloupec po sloupci a řádky jsou vybírané v zakódovaném pořadí. Šířka řádků a uspořádání sloupců jsou obvykle definované klíčem. Pro příklad použijeme jako klíčové slovo "STOLEK", jeho délka je 6 (tedy délka řádků je 6) a uspořádání je definované abecedním pořadím písmen v klíči. V tomto případe to bude uspořádání "5 6 4 3 1 2". V souměrné sloupcové transpoziční šifře jsou zbývající místa vyplněna nulami (náhodnými písmeny), v nesouměrné sloupcové transpoziční šifře jsou zbývající místa ponechána prázdná. Nakonec zprávu čteme po sloupcích v pořadí, které je dané klíčem. Pro příklad použijeme jako klíč slovo "STOLEK" a zprávu "BYLI JSTE ODHALENI. HNED UTECTE". V souměrné sloupcové transpozici to zapíšeme takto:

5 6 4 3 1 2
B Y L I J S
T E O D H A
L E N I H N
E D U T E C
T E Q K J E

Na konci jsme přidali 4 náhodné písmena (QKJE). Zašifrovaný text potom čteme takto: JHHEJ SANCE IDITK LONUQ BTLET YEEDE V nesouměrné sloupcové transpozici sloupec nedoplníme, bude to vypadat takto:

5 6 4 3 1 2
B Y L I J S
T E O D H A
L E N I H N
E D U T E C
T E

Následná šifra bude vypadat takto:

JHHES ANCID ITLON UBTLE TYEED E

Na dešifrování musí příjemce vypočítat délku sloupce dělením délky zprávy délkou klíče. Následně může napsat zprávu do sloupce, potom přeuspořádat sloupce podle klíče. Taková sloupcová transpozice se běžně používala jako část komplexnějších šifer v 50. letech.

Dvojitá transpozice

Jednoduchá sloupcová transpozice může být napadena hádáním možné délky sloupce. Napíšeme zprávu v uspořádaných sloupcích (ale v nesprávném pořadí, protože neznáme klíč) a potom hledáme vhodný anagram. Proto vytvořili silnější dvojitou transpozici, která byla často používaná. Je to jednoduché sloupcová transpozice aplikovaná dvakrát. Stejný klíč můžeme použit pro obě transpozice, nebo můžeme použit dva odlišné klíče. Jako příklad můžeme vzít výsledek nesouměrné sloupcové transpozice z předcházejícího výsledku a realizovat druhé zašifrování s jiným klíčem, např. "JABLKO", který dává uspořádání "3 1 2 5 4 6":

3 1 2 5 4 6
J H H E S A
N C I D I T
L O N U B T
L E T Y E E
D E

Šifra bude vypadat takto:

HCOEE HINTJ NLLDS IBEED UYATT E

V době první světové války používala dvojitou sloupcovou transpoziční šifru německá armáda. Šifrovací systém vymyslel Francouz Übchi, avšak francouzský úspěch se stal obecně známým. Po jeho publikaci v Le Matin Němci 18. listopadu 1914 přešli na nový systém. Během druhé světové války byla dvojitá transpoziční šifra používaná skupinami holandských gard, francouzských makistů, britských SOE, kteří měli na starosti řízení tajných operací v Evropě. Byla též využívaná agenty amerických OSS a jako nouzová šifra pro německou armádu a námořnictvo. Až do objevení VIC šifry byla dvojitá transpozice všeobecně považovaná za nejsložitější šifrování, které agent může spolehlivě používat v těžkých podmínkách.

Myszkowskiho transpozice

Je to varianta sloupcové transpozice, kterou navrhl Émile Victor Théodore Myszkowski roku 1902 a požaduje klíčové slovo se střídavými písmeny. Jak se opakují písmena klíčového slova, tak se zapisují následující znaky v abecedním pořadí. Jako příklad si zvolíme za klíčové slovo "FLASKA", tedy permutace bude "3 5 1 6 4 2". V Myszkowskiho transpozici opakující se písmena klíčového slova jsou číslované stejně. Pro klíčové slovo "FLASKA" to bude zapsané takto "2 4 1 5 3 1" .

2 4 1 5 3 1
B Y L I J S
T E O D H A
L E N I H N
E D U T E C
T E

Text v sloupcích s různými čísly je přepisovaný směrem dolů, ale s opakujícími se písmeny je přepisovaný zleva doprava, tedy šifra bude vypadat následovně:

LSOAN NUCBT LETJH HEYEE DEIDI T

Narušená transpozice

V narušené transpozici jsou jisté pozice v mřížce zakryté a nepoužité, když se vyplní nešifrovaný text. Toto přerušení se pravidelně formátuje a činí dešifrování složitější.

Mřížky

Jinou formu transpoziční šifry používá mřížka, tedy kartička s otvory spíš než matematický algoritmus. Na délce určené velikostí mřížky je takto vytvořená transpozice velice nepravidelná, je ovšem nutné udržet utajení fyzického klíče. Mřížky byly navrženy roku 1550 a byly používány ještě i v prvních měsících první světové války.

Detekce a dešifrování

Pokud transpozici nepostihla frekvence individuálních symbolů, jednoduchá transpozice byla lehko odkrytá dešifrováním pomocí počítání frekvence. Jak šifrovaný text ukazuje frekvenční rozdělení velmi podobné nešifrovanému textu, je to pravděpodobně transpozice. Toto potom může být často napadené anagramem – posouváním částí šifrovaného textu dokola, potom hledáním sekcí, které vypadají jako anagram nějakých slov a řeší anagramy. Od té doby, co byly objeveny anagramy, odhalily informaci o transpozičním formátovaní a mohly být následně rozšířené. Jednodušší transpozice též často trpí tím, že klíče velmi blízké správným klíčům odhalí dlouhé sekce zřetelného nešifrovaného roztroušeného textu. V důsledku toho šifry můžu být zranitelné algoritmy s postupným přibližováním se k optimu jako např. genetické algoritmy. Detailní opis dešifrované německé transpoziční šifry můžete nalézt v kapitole 7 z Herbert Yardley's "The American Black Chamber".

Kombinace

Transpozice je často kombinována s jinými technikami. Například jednoduchá substituční šifra kombinovaná se sloupcovou transpozicí se vyhne slabosti obou transpozicí. Nahrazením vysoko frekventovaných symbolů vysoko frekventovaným nešifrovaným textem znaků neodhalí kus nešifrovaného textu z důvodu transpozice. Anagram transpozice nepracuje z důvodu substituce. Technika je obzvlášť silná, když se kombinuje s frakcionací (viz níže). Nevýhoda je, že takovéto šifry jsou o mnohem více pracné a více náchylné na chyby jako jednoduché šifry.

Frakcionace

Transpozice je obzvlášť efektivní, když je použitá s frakcionací – to jest, předběžný stupeň, který dělí každý nešifrovaný text na několik šifrovaných symbolů. Například, abeceda nešifrovaného textu může být napsaná do mřížky a potom každý znak ve zprávě nahrazený jeho souřadnicemi. Jiná metoda frakcionace je jednoduše konvertovat zprávu do Morseovy abecedy se symbolem pro mezery stejným jako tečky a čárky. Když je taková rozdělená zpráva převedená, komponenty individuálních znaků se ve zprávě stanou široko rozdělené. Takto dosahují difúzi Clauda E. Shannona. Příklady šifer, které kombinují frakcionaci a transpozici, obsahuje bifid šifra, trifid šifra, ADFGVX šifra a VIC šifra. Jiná volba může být nahrazení každého znaku s jeho binárním vyjádřením, transpozicí tohoto a potom konvertováním nového binárního řetězce do příslušného ASCII znaku. Slučování zakódovaného procesu na binární řetězec víckrát před změnou na ASCII znaky může pravděpodobně způsobit, že to bude těžší na rozluštění. Mnoho moderních blokových šifer používá častěji komplexní formy transpozice týkající se tohoto jednoduchého nápadu.

Reference

V tomto článku byl použit překlad textu z článku Transpozícia (kryptológia) na slovenské Wikipedii.