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 náhľad|ROT13 je Ceźarova šifra, typ substitučnej šifry. V ROT13 sa abeceda otáča o 13 krokov 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: Abeceda otvoreného textuABCDEFGHIJKLMNOPQRSTUVWXYZAbeceda zašifrovaného textuZEBRASCDFGHIJKLMNOPQTUVWXY Správu
ihneď utečte. boli sme objavení!
zašifrujeme ako
FDKAR TQABQA. ELHF PJA LEGZUAKF!
Š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 :
FDKAR TQABQ ELHFP JALEG ZUAKF
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:
alt=An example pigpen message|320x320bod|Príklad správy z prasiatka
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: +Čísla otvoreného textu123456789Abeceda zašifrovaného textuMAKEAPROFIT David Crawford / Mike Esterl, At Siemens, witnesses cite pattern of bribery, The Wall Street Journal, January 31, 2007: "Back at Munich headquarters, he [Michael Kutschenreuter, a former Siemens-Manager] told prosecutors, he learned of an encryption code he alleged was widely used at Siemens to itemize bribe payments. He said it was derived from the phrase "Make Profit," with the phrase's 10 letters corresponding to the numbers 1-2-3-4-5-6-7-8-9-0. Thus, with the letter A standing for 2 and P standing for 5, a reference to "file this in the APP file" meant a bribe was authorized at 2.55 percent of sales. - A spokesman for Siemens said it has no knowledge of a "Make Profit" encryption system." 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 náhľad|Falošná nomenklačná správa použitá v Babingtonovom sprisahaní 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 náhľad|Tabuľka kódov francúzskeho nomenklátora 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 Stahl, Fred A., On Computational Security, University of Illinois, 1974 Stahl, Fred A. "A homophonic cipher for computational cryptography ", afips, pp. 565, 1973 Proceedings of the National Computer Conference, 1973 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. David Salomon. Coding for Data and Computer Communications. Springer, 2005. Fred A. Stahl. "A homophonic cipher for computational cryptography" Proceedings of the national computer conference and exposition (AFIPS '73), pp. 123–126, New York, USA, 1973.
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“).