Substitučná šifra

V kryptografii je substitučná šifra spôsob šifrovania, pri ktorom sú jednotky otvoreného textu nahradené zašifrovým textom definovaným spôsobom pomocou kľúča; "jednotky" môžu byť jednotlivé písmená (najbežnejšie), dvojice písmen, trojice písmen, zmesi vyššie uvedených písmen atď. Prijímač dešifruje text vykonaním procesu inverznej substitúcie, aby extrahoval pôvodnú správu.
Substitučné šifry možno porovnať s transpozičnými šiframi. V transpozičnej šifre sú jednotky otvoreného textu preusporiadané v inom a zvyčajne dosť zložitom poradí, ale samotné jednotky zostávajú nezmenené. V substitučnej šifre sú jednotky otvoreného textu v zašifrovanom texte zachované v rovnakom poradí, ale samotné jednotky sú pozmenené.
Existuje množstvo rôznych typov substitučných šifier. Ak šifra pracuje s jednotlivými písmenami, nazýva sa to jednoduchá substitučná šifra ; šifra, ktorá pracuje s väčšími skupinami písmen, sa nazýva polygrafická. Monoalfabetická šifra používa pevnú substitúciu v celej správe, zatiaľ čo polyalfabetická šifra používa množstvo substitúcií na rôznych pozíciách v správe, kde je jednotka z otvoreného textu mapovaná na jednu z niekoľkých možností v šifrovanom texte a naopak.
Jednoduchá substitúcia.
Samostatné nahrádzanie jednotlivých písmen – jednoduchá substitúcia – možno demonštrovať napísaním abecedy v určitom poradí, aby reprezentovalo nahradenie. Toto sa nazýva substitučná abeceda . Šifrovacia abeceda môže byť posunutá alebo obrátená (vytvorením Cézarovej a Atbashovej šifry, v tomto poradí) alebo zakódovaná zložitejším spôsobom, v takom prípade sa nazýva "zmiešaná abeceda" alebo "pomätená abeceda" . Tradične môžu byť zmiešané abecedy vytvorené tak, že najskôr napíšete kľúčové slovo, odstránite z neho opakované písmená a potom napíšete všetky zostávajúce písmená v abecede v obvyklom poradí.
Použitím tohto systému nám kľúčové slovo "zebras“ dáva tieto abecedy:
Správu
codice_1
zašifrujeme ako
codice_2
Šifrovaný text sa zvyčajne píše v blokoch určitej dĺžky, pričom sa vynecháva interpunkcia a medzery; robí sa to s cieľom zakryť konce slov otvoreného textu a zabrániť chybám pri prenose. Tieto bloky sa nazývajú „skupiny“ a niekedy sa ako dodatočná kontrola uvádza „počet skupín“. Často sa používajú päťpísmenové skupiny, ktoré pochádzajú z obdobia, keď sa správy prenášali telegrafom :
codice_3
Ak sa stane, že dĺžka správy nie je deliteľná piatimi, môže byť na konci doplnená „ nulami “. Môžu to byť akékoľvek znaky, ktoré sa dešifrujú na zjavné nezmysly, aby ich príjemca mohol ľahko rozpoznať a zahodiť.
Abeceda šifrového textu sa niekedy líši od abecedy otvoreného textu; napríklad v šifre prasiatka, šifrový text pozostáva zo súboru symbolov odvodených z mriežky. Napríklad:
Takéto vlastnosti však nerobia veľký rozdiel v bezpečnosti schémy – prinajmenšom je možné akúkoľvek skupinu zvláštnych symbolov prepísať späť do abecedy AZ a zaobchádzať s nimi ako zvyčajne.
V katalógoch pre predajcov sa niekedy používa veľmi jednoduché šifrovanie nahradením čísiel písmenami:
Príklad: MAT by sa použil na vyjadrenie 120.
Zabezpečenie pre jednoduché substitučné šifry.
Hoci tradičná metóda kľúčových slov na vytvorenie zmiešanej substitučnej abecedy je jednoduchá, vážnou nevýhodou je, že posledné písmená abecedy (ktoré sú väčšinou nízkofrekvenčné) majú tendenciu zostať na konci. Silnejším spôsobom konštrukcie zmiešanej abecedy je vygenerovať substitučnú abecedu úplne náhodne.
Hoci počet možných substitučných abecied je veľmi veľký (26! ≈ 2 88,4 alebo asi 88 bitov), táto šifra nie je príliš silná a ľahko sa prelomí. Za predpokladu, že správa má primeranú dĺžku, môže kryptoanalytik odvodiť pravdepodobný význam najbežnejších symbolov analýzou frekvenčného rozloženia šifrovaného textu. To umožňuje vytváranie čiastkových slov, ktoré je možné predbežne vyplniť, čím sa postupne rozširuje (čiastočné) riešenie. V niektorých prípadoch môžu byť základné slová určené aj zo vzoru ich písmen; napríklad "attract", "osseous" a slová s týmito dvoma koreňmi sú jediné bežné anglické slová so vzorom "ABBCADB". Mnoho ľudí rieši takéto šifry rekreačne, ako napríklad kryptogramové hádanky v novinách.
Podľa unicitnej vzdialenosti angličtiny je na prelomenie jednoduchej substitúcie zmiešanej abecedy potrebných 27,6 písmen šifrovaného textu. V praxi je zvyčajne potrebných asi 50 písmen, aj keď niektoré správy je možné rozložiť na menej, ak sa nájdu neobvyklé vzory. V iných prípadoch môže byť otvorený text vymyslený tak, že má takmer plochú distribúciu frekvencií a kryptoanalytik bude potom vyžadovať oveľa dlhší otvorený text.
Nomenklátor.
Jedným z kedysi bežných variantov substitučnej šifry je nomenklátor. Táto šifra, pomenovaná po verejnom činiteľovi, ktorý oznámoval tituly hosťujúcich hodnostárov, používa malý kódový hárok obsahujúci tabuľky na nahradenie písmen, slabík a slov, niekedy homofónne, ktoré zvyčajne premieňajú symboly na čísla. Pôvodne bola časť kódu obmedzená na mená dôležitých ľudí, odtiaľ pochádza názov šifry; v neskorších rokoch pokrýval aj mnohé bežné slová a názvy miest. Symboly pre celé slová ( "kódové slová" v modernom jazyku) a písmená (v modernom jazyku "šifra" ) neboli v zašifrovanom texte rozlíšené. Jednou z nich bola Rossignolova veľká šifra, ktorú používal Ľudovít XIV.
Nomenklátory boli štandardnou súčasťou diplomatickej korešpondencie, špionáže a pokročilého politického sprisahania od začiatku pätnásteho storočia do konca osemnásteho storočia; väčšina konšpirátorov bola a zostala menej kryptograficky sofistikovaná. Hoci kryptoanalytici vládnych spravodajských služieb v polovici šestnásteho storočia systematicky lámali nomenklátory a od roku 1467 boli k dispozícii lepšie systémy, zvyčajnou reakciou na kryptoanalýzu bolo jednoducho zväčšiť tabuľky. Koncom osemnásteho storočia, keď systém začínal vymierať, mali niektorí nomenklátori 50 000 symbolov. 
Napriek tomu neboli všetky nomenklátory porušené; v súčasnosti zostáva kryptoanalýza archivovaných šifrových textov plodnou oblasťou historického výskumu.
Homofónna substitúcia.
Prvým pokusom o zvýšenie náročnosti útokov frekvenčnej analýzy na substitučné šifry bolo zamaskovať frekvencie písmen v otvorenom texte homofóniou. V týchto šifrách sa písmená otvoreného textu mapujú na viac ako jeden symbol šifrovaného textu. Symboly otvoreného textu s najvyššou frekvenciou majú zvyčajne viac ekvivalentov ako písmená s nižšou frekvenciou. Týmto spôsobom je frekvenčné rozdelenie sploštené, čo sťažuje analýzu.
Keďže v abecede zašifrovaného textu bude potrebných viac ako 26 znakov, na vynájdenie väčších abecied sa používajú rôzne riešenia. Najjednoduchšie je použiť numerickú substitúciu abecedy (každému písmenu z pôvodnej abecedy priradíme jedno alebo viac dvociferných čísel). Ďalšia metóda pozostáva z jednoduchých variácií existujúcej abecedy; veľké, malé, hore nohami atď. Viac umelecky, aj keď nie nevyhnutne bezpečnejšie, niektoré homofónne šifry využívali úplne vymyslené abecedy fantazijných symbolov.
Knižná šifra je typom homofónnej šifry, jedným z príkladov sú Bealeove šifry. Toto je príbeh zakopaného pokladu, ktorý bol opísaný v rokoch 1819-21 pomocou zašifrovaného textu, ktorý bol kľúčom k Deklarácii nezávislosti. Každý znak šifrového textu bol reprezentovaný číslom. Číslo sa určilo tak, že sa vzal znak otvoreného textu a našlo sa slovo v Deklarácii nezávislosti, ktoré začínalo týmto znakom, a použila sa číselná pozícia tohto slova v Deklarácii nezávislosti ako zašifrovaná forma tohto listu. Keďže veľa slov v Deklarácii nezávislosti začína rovnakým písmenom, zašifrovanie tohto znaku môže byť ktorékoľvek z čísel spojených so slovami v Deklarácii nezávislosti, ktoré začínajú týmto písmenom. Dešifrovanie zašifrovaného textového znaku "X" (čo je číslo) je také jednoduché, ako vyhľadať X-té slovo Deklarácie nezávislosti a použiť prvé písmeno tohto slova ako dešifrovaný znak.
Ďalšiu homofónnu šifru opísal Stahl a bola jedným s prvých pokusov poskytnúť počítačovú bezpečnosť dátových systémov v počítačoch prostredníctvom šifrovania. Stahl skonštruoval šifru tak, že počet homofónov pre dané písmeno bol úmerný frekvencii písmen, čím sa frekvenčná analýza značne sťažila. 
Francesco I. Gonzaga, vojvoda z Mantovy, použil prvý známy príklad homofónnej substitučnej šifry v roku 1401 na korešpondenciu s jednou Simone de Crema. 
Polyalfabetická substitúcia.
Dielo Al-Qalqashandiho (1355-1418), založené na skoršom diele Ibn al-Durayhima (1312-1359), obsahovalo prvú publikovanú diskusiu o substitučných a transpozíčných šifrách, ako aj prvý opis polyalfabetickej šifry, v ktorej je každému písmenu otvoreného textu priradených viac možností nahradenia.. Polyalfabetické substitučné šifry neskôr opísal v roku 1467 Leone Battista Alberti vo forme diskov. Johannes Trithemius vo svojej knihe "Steganographia" (staroveká gréčtina pre „skryté písmo“) predstavil teraz štandardnejšiu formu "tably". Sofistikovanejšiu verziu používajúcu zmiešané abecedy opísal v roku 1563 Giovanni Battista della Porta vo svojej knihe "De Furtivis Literarum Notis" (v latinčine „O skrytých znakoch v písaní“).
V polyalfabetickej šifre sa používajú viaceré šifrovacie abecedy. Na uľahčenie šifrovania sú všetky abecedy zvyčajne napísané vo veľkej tabuľke, tradične nazývanej "tabla (tableau)" . Tabla je zvyčajne veľká 26 × 26 písmen, takže je k dispozícii 26 plných abecied zašifrového textu. Spôsob vyplnenia tably a výber abecedy, ktorá sa použije ako ďalšia, definuje konkrétnu polyalfabetickú šifru. Všetky takéto šifry sa dajú ľahšie prelomiť, ako sa kedysi myslelo, pretože substitučné abecedy sa opakujú pre dostatočne veľké otvorené texty.
Jeden z najpopulárnejších bol spôsob Blaisea de Vigenère. Prvýkrát publikovaný v roku 1585 bol považovaný za neprelomiteľný až do roku 1863 a skutočne sa bežne nazýval "le chiffre indéchiffrable" ( francúzsky „nerozlúštiteľná šifra“).
Vo Vigenèrovej šifre je prvý riadok tably vyplnený kópiou abecedy otvoreného textu a následné riadky sú jednoducho posunuté o jedno miesto doľava. (Takéto jednoduchá tabla sa nazýva "tabula recta" a matematicky zodpovedá pridaniu otvoreného textu a kľúčových písmen, modulo 26. ) Kľúčové slovo sa potom použije na výber abecedy zašifrovaného textu, ktorá sa má použiť. Postupne sa použije každé písmeno kľúčového slova a potom sa znova zopakujú od začiatku. Ak je teda kľúčové slovo „CAT“, prvé písmeno otvoreného textu sa zašifruje pod abecedou „C“, druhé pod „A“, tretie pod „T“, štvrté pod „C“ atď. V praxi boli Vigenèrove heslá frázy dlhé niekoľko slov.
V roku 1863 Friedrich Kasiski publikoval metódu (pravdepodobne tajne a nezávisle objavenú pred Krymskou vojnou Charlesom Babbageom ), ktorá umožnila vypočítať dĺžku kľúčového slova vo Vigenèrovej zašifrovanej správe. Akonáhle to bolo urobené, písmená zašifrovaného textu, ktoré boli zašifrované v rovnakej abecede, mohli byť vyberané a napadnuté oddelene ako množstvo polonezávislých jednoduchých substitúcií – komplikované skutočnosťou, že písmená v rámci jednej abecedy boli oddelené a netvorili celé slová, ale zjednodušené tým, že sa zvyčajne používala "tabula recta".
Preto by aj dnes šifra typu Vigenère mala byť teoreticky ťažko prelomiteľná, ak sa v table používajú zmiešané abecedy, ak je kľúčové slovo náhodné a ak je celková dĺžka šifrovaného textu menšia ako 27,67-násobok dĺžky kľúčového slova. Tieto požiadavky sa dajú v praxi len zriedka realizovať, a tak bezpečnosť šifrovaných správ Vigenère je zvyčajne nižšia, ako by mohla byť.
Medzi ďalšie významné polyabecedy patria:
Moderné prúdové šifry možno z dostatočne abstraktnej perspektívy považovať za formu polyalfabetickej šifry, v ktorej bolo vynaložené všetko úsilie na to, aby bol kľúčový prúd čo najdlhší a nepredvídateľný.
Polygrafická substitúcia.
V polygrafickej substitučnej šifre sa písmená otvoreného textu nahrádzajú vo väčších skupinách namiesto toho, aby sa písmená nahrádzali jednotlivo. Prvou výhodou je, že distribúcia frekvencie je oveľa plochejšia ako distribúcia jednotlivých písmen (hoci v skutočnosti nie je plochá v reálnych jazykoch; napríklad „TH“ je oveľa bežnejšie ako „XQ“ v angličtine). Po druhé, väčší počet symbolov vyžaduje zodpovedajúcim spôsobom viac šifrového textu na produktívnu analýzu frekvencie písmen.
Nahradenie "párov" písmen by si vyžadovalo substitučnú abecedu dlhú 676 znakov ( formula_1 ). Vo vyššie spomínanom diele "De Furtivis Literarum Notis" autor Giovanny della Porta v skutočnosti navrhol takýto systém s tabuľkou 20 x 20 (pre 20 písmen talianskej/latinskej abecedy, ktorú používal) vyplnenou 400 jedinečnými glyfmi. Systém bol však nepraktický a pravdepodobne sa nikdy nepoužil.
Najstaršia praktická digrafická šifra (párová substitúcia) bola takzvaná Playfairova šifra, ktorú vynašiel Sir Charles Wheatstone v roku 1854. V tejto šifre je mriežka 5 x 5 vyplnená písmenami danej abecedy (každé písmeno v nejakom políčku, ale keďže písmen anglickej abecedy je 26 a pozícií v tabuľke len 25, dve písmená, zvyčajne I a J, sa píšu na rovnakú pozíciu). Digrafická substitúcia sa potom simuluje tak, že sa dvojice písmen vezmú ako dva rohy obdĺžnika a ďalšie dva rohy sa použijú ako šifrový text (ukážku šifrovania nájdete v hlavnom článku o šifre Playfair na anglickej wikipédii ). Špeciálne pravidlá riešia dvojité písmená a páry spadajúce do rovnakého riadku alebo stĺpca. Playfair bol vo vojenskom využití od búrskej vojny cez druhú svetovú vojnu.
Niekoľko ďalších praktických polygrafií zaviedol v roku 1901 Felix Delastelle, vrátane bifidovej a štvorštvorcovej šifry (obe digrafické) a trifidovej šifry (pravdepodobne prvá praktická trigrafická).
Hillova šifra, ktorú v roku 1929 vynašiel Lester S. Hill, je polygrafická substitúcia, ktorá dokáže kombinovať oveľa väčšie skupiny písmen súčasne pomocou lineárnej algebry. Každé písmeno sa považuje za číslicu v základe 26 : A = 0, B = 1 atď. (Vo variácii sú pridané 3 extra symboly, aby bola vektorová báza prvočíslom.) Blok n písmen sa potom považuje za n-rozmerný vektor a vynásobí sa maticou n x n, modulo 26. Komponenty matice sú kľúčové a mali by byť náhodné za predpokladu, že matica je invertovateľná nad formula_2 (aby sa zabezpečilo možné dešifrovanie). Mechanická verzia Hillovej 6-rozmernej šifry bola patentovaná v roku 1929.
Hillova šifra je zraniteľná voči útokom so známym otvoreným textom, pretože je úplne lineárna, takže na znemožnenie tohto útoku ju treba skombinovať s nejakým nelineárnym krokom. Kombinácia širších a širších slabých, lineárnych rozptylových krokov, ako je Hillova šifra, s nelineárnymi substitučnými krokmi, v konečnom dôsledku vedie k substitučno-permutačnej sieti (napr. Feistelova šifra ), takže je možné – z tejto extrémnej perspektívy – uvažovať moderné blokové šifry ako typ polygrafickej substitúcie.
Mechanické substitučné šifry.
Medzi prvou svetovou vojnou a rozšírenou dostupnosťou počítačov (pre niektoré vlády to boli približne 50. alebo 60. roky 20. storočia; pre iné organizácie to bolo o desaťročie alebo viac neskôr; pre jednotlivcov to nebolo skôr ako v roku 1975) boli mechanické implementácie polyalfabetických substitučných šifier široko používané. Viacerí vynálezcovia mali podobné predstavy v rovnakom čase a rotorové šifrovacie stroje boli patentované štyrikrát v roku 1919. Najdôležitejším z výsledných strojov bola Enigma, najmä vo verziách používaných nemeckou armádou približne od roku 1930. Spojenci tiež vyvinuli a používali rotorové stroje (napr. SIGABA a Typex ).
Všetky boli podobné v tom, že nahradené písmeno bolo vybrané elektricky z obrovského množstva možných kombinácií vyplývajúcich z rotácie niekoľkých písmenových kotúčov. Keďže jeden alebo viac diskov sa mechanicky otáčali s každým zašifrovaným písmenom otvoreného textu, počet použitých abecied bol astronomický. Šifry skorých verzií týchto strojov boli napriek tomu prelomiteľné. William F. Friedman z dešifrovacej skupiny americkej armády čoskoro našiel zraniteľné miesta v Hebernovom rotorovom stroji a Dillwyn Knox z GC&amp;CS vyriešil verzie stroja Enigma (tie bez „zásuvného panela“) ešte pred začiatkom druhej svetovej vojny . Prenos dát, ktorý chránili v podstate všetky nemecké vojenské Enigmy, prerušili spojeneckí kryptoanalytici, najmä tí v Bletchley Parku, počnúc variantom nemeckej armády, ktorý sa používal na začiatku 30. rokov 20. storočia. Táto verzia bola prelomená inšpirovaným matematickým pohľadom Mariana Rejewského v Poľsku.
Pokiaľ je verejne známe, žiadne správy chránené strojmi SIGABA a Typex neboli nikdy prelomené počas alebo blízko času, keď boli tieto systémy v prevádzke.
Vernamova šifra (Jednorazový blok).
Jeden typ substitučnej šifry, šifra s jednorazovým kľúčom, je jedinečný. Vynašli ho koncom prvej svetovej vojny Gilbert Vernam a Joseph Mauborgne v USA. Claude Shannon matematicky dokázal, že je neprelomiteľný, pravdepodobne počas druhej svetovej vojny; jeho dielo bolo prvýkrát publikované koncom 40. rokov 20. storočia. Vo svojej najbežnejšej implementácii môže byť šifra s jednorazovým kľúčom nazývaná substitučnou šifrou iba z jedinečného pohľadu; zvyčajne sa písmeno otvoreného textu nejakým spôsobom kombinuje (nie je nahradené) (napr. XOR ) s tajným kľúčom na tejto pozícii.
Jednorazový kľúč je vo väčšine prípadov nepraktický, pretože vyžaduje, aby bol kľúčový materiál taký dlhý ako čistý text, v aby bol skutočne náhodný, použitý jednorázovo (raz a "len" raz) a udržiavaný v úplnom utajení pred všetkými okrem odosielateľa a príjemcu. Keď sú tieto podmienky čo i len okrajovo porušené, šifra s jednorazovým kľúčom už nie je neprelomiteľná. Sovietske jednorazové blokové správy odoslané z USA na krátky čas počas druhej svetovej vojny používali nenáhodný kľúčový materiál. Americkí kryptoanalytici, počnúc koncom 40. rokov, boli schopní, úplne alebo čiastočne, prelomiť niekoľko tisíc správ z niekoľkých stoviek tisíc.
V mechanickej implementácii, podobne ako zariadenie Rockex, sa jednorazový kľúč používal na správy odosielané na "horúcej linke" Moskva - Washington zriadenej po kubánskej raketovej kríze.
Substitúcia v modernej kryptografii.
Substitučné šifry, najmä staršie ručné šifry písane ceruzou na papier, sa už veľmi nepoužívajú. Kryptografický koncept substitúcie však pretrváva dodnes. Z dostatočne abstraktnej perspektívy sa na moderné bitovo orientované blokové šifry (napr. DES alebo AES ) možno pozerať ako na substitučné šifry na enormne veľkej binárnej abecede. Okrem toho blokové šifry často obsahujú menšie substitučné tabuľky nazývané S-boxy.