Transpozícia (kryptológia)

Transpozícia alebo transpozičná šifra je zakladná kryptografická operácia, ktorej spôsob spočíva v zamiešaní poradia písmen otvoreného textu. Táto operácia musí byť vykonaná podľa určitých pravidiel, pomocou ktorých je možné text dešifrovať. Medzi jednoduché transpozičné šifry patrí napríklad písanie textu opačne.

Rail Fence šifra

Rail Fence šifra je forma transpozičnej šifry, ktorá dostala svoje meno podľa spôsobu, akým je kódovaná. V Rail Fence šifre sa pôvodný text (plaintext) píše zostupne na "koľaje" idúce za sebou. Ak sa dostaneme na poslednú "koľaj" imaginárneho plotu, pokračujeme ďalej smerom nahor. Správa sa potom číta v riadkoch. Napríklad použijeme tri "koľaje" a správu "BOLI STE ODHALENI. HNED UTECTE", šifra sa zapíše takto:

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

Potom sa to číta takto:

BSDEN TEOIT OHLNH EUETL EAIDC

(Rozložíme potom tento zašifrovaný text do blokov po 5 písmen aby sme predišli chybám.)

Route šifra

V route šifre sa najskôr pôvodný text (plaintext) zapíše do mriežky daných rozmerov, potom sa číta podľa vzoru uvedeného v kľúči. Na ukážku použijeme rovnaký text, ktorý sme použili pri rail fence šifre.

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

Za kľúč môžeme zvoliť „pravotočivú špirálu dovnútra, začínajúcu z pravého horného rohu“. Dostaneme takto zašifrovaný text:

EJXTTEILDTLOBIEHEHDECUNNAOS

Stĺpcová transpozícia

V stĺpcovej transpozícii je správa písaná v riadkoch presne určenej dĺžky a následne je čítaná stĺpec po stĺpci a riadky sú vyberané v zakódovanom poradí. Šírka riadkov a usporiadania stĺpcov sú zvyčajne definované kľúčom. Pre príklad použijeme ako kľúč slovo "STOLIK", ktorého dĺžka je 6 (teda dĺžka riadkov je 6) a usporiadanie je definované abecedným poradím písmen v kľúči. V tomto prípade to bude usporiadanie "5 6 4 3 1 2".

V súmernej stĺpcovej transpozičnej šifre sú zvyšné miesta vyplnené nulami (náhodnými písmenami), v nesúmernej stĺpcovej transpozičnej šifre sú zvyšné miesta ponechané prázdne. Nakoniec správu čítame po stĺpcoch v poradí, ktoré je dané kľúčom. Pre príklad použijeme ako kľúč slovo "STOLIK" a správu "BOLI STE ODHALENI. HNED UTECTE". V súmernej stĺpcovej transpozícii to zapíšeme takto:

5 6 4 3 1 2
B O L I 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 U

Na konci sme pridali 5 náhodných písmen (QKJEU) Zašifrovaný text potom čítame takto:

SANCE TLETU IHHEJ LDITK BEEDE OONUQ

V nesúmernej stĺpcovej transpozícii stĺpce nedopĺňame, bude to vyzerať takto:

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

Následne šifra bude vyzerať takto:

SANCT LETIH HELDI TBEED EOONU

Na dešifrovanie príjemca musí vypočítať dĺžku stĺpca delením dĺžky správy dĺžkou kľúča. Následne môže napísať správu do stĺpcov, potom preusporiadať stĺpce podľa kľúča. Takáto stĺpcova transpozícia sa zvykla používať ako časť komplexnejších šifier v 1950-tych rokoch.

Dvojitá transpozícia

Jednoduchá stĺpcová transpozícia môže byť napadnutá hádaním možnej dĺžky stĺpca. Napíšeme správu v usporiadaných stĺpcoch (ale v nesprávnom poradí, pretože nepoznáme kľúč) a potom hľadáme vhodný anagram. Teda vytvorili silnejšiu dvojitú transpozíciu, ktorá bola často používaná. Je to jednoducho stĺpcová transpozícia aplikovaná dvakrát. Rovnaký kľúč môžeme použiť pre obe transpozície, alebo môžeme použiť dva rozdielne kĺúče.

Ako príklad môžeme vziať výsledok nesúmernej stĺpcovej transpozície z predchádzajúcej sekcie a realizovať druhé zašifrovanie s iným kľúčom, napríklad "JABLKO", ktorý dáva permutáciu "3 1 2 5 4 6":

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

Šifra bude vyzerať takto:

ATDDN IIESE LEUTH BOCHT OLEEN

Počas prvej svetovej vojny používala dvojitú stĺpcovú transpozičnú šifru nemecká armáda. Šifrovací systém vynašiel francúz Übchi, ktorý bol zvyčajne schopný nájsť kľúč v priebehu niekoľkých po tom čo bol predstavený nový. Ale francúzsky úspech sa stal široko-ďaleko známy a po publikácii v Le Matin Nemci prešli na nový systém 18. novembra 1914.

Počas druhej svetovej vojny dvojitá transpozičná šifra bola používaná skupinami holandskej gardy, francúzskych makistov a britských SOE, ktorí mali na starosti riadenie tajných operácií v Európe. Bola tiež využívaná agentmi americkej OSS a ako núdzové šifry pre nemeckú armádu a námorníctvo.

Až do objavenia VIC šifry, dvojitá transpozícia bola všeobecne považovaná ako najzložitejšie šifrovanie, ktoré agent môže spoľahlivo používať v ťažkých podmienkach.

Myszkowski-ho transpozícia

Je to variant stĺpcovej transpozície, ktorú navrhol Émile Victor Théodore Myszkowski v roku 1902 a požaduje kľúčové slovo so striedavými písmenami. Ak sa opakujú písmená kľúčového slova tak sa zapisujú nasledujúce znaky v abecednom poradí. Ako príklad si zoberieme za kľúč slovo "FLASKA", teda permutácia bude "3 5 1 6 4 2". V Myszkowskiho transpozícii opakované písmená kľúčového slova sú číslované rovnako. Pre kľúčové slovo "FLASKA" to bude zapísané takto "2 4 1 5 3 1"

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

Text v stĺpcoch s rôznymi číslami je prepisovaný smerom nadol, ale s opakujúcimi sa písmenami je prepisovaný z ľava do prava, teda šifra bude vyzerať nasledovne:

LTDLI ETTBE EDESA NCOON UIHHE

Narušená transpozícia

V narušenej transpozícii sú isté pozície v mriežke zakryté a nepoužité keď sa vypĺňa nešifrovaný text. Tieto prerušenia sa pravidelne formátujú a robia dešifrovanie zložitejším.

Mriežky

Iná forma transpozičnej šifry používajúca mriežky, alebo fyzické maskovanie s prerušením presnejším ako matematický algoritmus. Toto môže produkovať vysoko nepravidelnú transpozíciu cez periódu špecifikovanú veľkosťou mriežky, ale vyžaduje vhodnosť na udržanie utajenia fyzického kľúča. Mriežky boli po prvýkrát navrhnuté v roku 1550 a boli používané ešte aj v prvých pár mesiacoch prvej svetovej vojny.

Detekcia a dešifrovanie

Pokiaľ transpozíciu nepostihla frekvencia individuálnych symbolov, jednoduchá transpozícia bola ľahko odkrytá dešifrovaním pomocou počítania frekvencie. Ak šifrovaný text ukazuje frekvenčné rozdelenie veľmi podobné nešifrovanému textu, je to pravdepodobne transpozícia. Toto potom môže byť často napadnuté anagrammingom – posúvaním častí šifrovaného textu dookola, potom hľadaním sekcií ktoré vyzerajú ako anagram nejakých slov a riešia anagramy. Odkedy boli anagramy objavené, odhalili informácie o transpozičnom formatovaní a mohli byť následne rozšírené. Jednoduchšia transpozícia tiež často trpí tým, že kľúče veľmi blízke správnym kľúčom odhalia dlhé sekcie zreteľného nešifrovaného roztrúseného textu. V dôsledku toho šifry môžu byť zraniteľné optimálnym hľadaním algoritmu tak ako “genetic algorithm”. Detailný opis dešifrovania nemeckej transpozičnej šifry môžete nájsť v kapitole 7 z Herbert Yardley's "The American Black Chamber".

Kombinácie

Transpozícia je často kombinovana s inými technikami. Napríklad jednoduchá substitučná šifra kombinovaná so stĺpcovou transpozíciou sa vyhne slabosti oboch transpozícií. Nahrádzaním vysokofrekventovaných symbolov vysokofrekventovaným nešifrovaným textom znaky neodhalia kus nešifrovaného textu z dôvodu transpozície. Anagramming transpozície nepracuje z dôvodu substitúcie. Technika je obzvlášť silná keď sa kombinuje s frakcionáciou (pozri nižšie). Nevýhoda je, že takéto šifry sú omnoho viac pracné a viac náchylné na chyby ako jednoduché šifry.

Frakcionácia

Transpozícia je obzvlášť efektívna keď je použitá s frakcionáciou – to jest, predbežný stupeň ktorý delí každý nešifrovaný text na niekoľko šifrovaných symbolov. Napríklad, abeceda nešifrovaného textu môže byť napísaná do mriežky a potom každý znak v správe nahradený jeho súradnicami. Iná metóda frakcionácie je jednoducho konvertovať správu do Morseovej abecedy so symbolom pre medzery rovnako ako bodky a čiarky. Keď je takáto rozdelená správa prevedená, komponenty individuálnych znakov sa v správe stanú široko rozdelené. Takto dosahujú difúziu Clauda E. Shannona. Príklady šifier, ktoré kombinujú frakcionáciu a transpozíciu obsahuje bifid šifra, trifid šifra, ADFGVX šifra a VIC šifra. Iná voľba môže byť nahrádzanie každého znaku s jeho binárnym vyjadrením, transpozíciou toho a potom konvertovaním nového binárneho stringu do príslušného ASCII znaku. Slučkovanie zakódovaného procesu na binárny string viackrát pred zmenou na ASCII znaky môže pravdepodobne spôsobiť, že to bude ťažšie na rozlúštenie. Veľa moderných blokových šifier používa častejšie komplexné formy transpozície týkajuce sa tohto jednoduchého nápadu.

Pozri aj

Zdroje

Ako zdroj tohto článku bol použitý článok na anglickej wikipédii.