Zobrazenie zdroja stránky Substitučná šifra

V [[Kryptografia|kryptografii]] je '''substitučná šifra''' spôsob [[Šifrovanie|šifrovania]], pri ktorom sú jednotky [[Otvorený text|otvoreného textu]] nahradené [[Zašifrovaný text|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 [[Transpozícia (kryptológia)|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 ==
[[Súbor:ROT13.png|náhľad|[[ROT13]] je [[Cézarova šifra|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ézarova šifra|Cézarovej]] a [[Atbaš|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:
{| class="wikitable"
!Abeceda [[Otvorený text|otvoreného textu]]
!ABCDEFGHIJKLMNOPQRSTUVWXYZ
|-
|'''Abeceda''' [[Zašifrovaný text|zašifrovaného textu]]
|ZEBRASCDFGHIJKLMNOPQTUVWXY
|}
Správu

<code>ihneď utečte. boli sme objavení!</code>

zašifrujeme ako

<code>FDKAR TQABQA. ELHF PJA LEGZUAKF!</code>

Š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ý text|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 [[Telegraf|telegrafom]] :

<code>FDKAR TQABQ ELHFP JALEG ZUAKF</code>

Ak sa stane, že dĺžka správy nie je deliteľná piatimi, môže byť na konci doplnená „ [[Nulová postava|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 [[Pigpen šifra|šifre prasiatka]], šifrový text pozostáva zo súboru symbolov odvodených z mriežky. Napríklad:

[[Súbor:A-pigpen-message.svg|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:
{| class="wikitable"
|+
!Čísla [[Otvorený text|otvoreného textu]]
!123456789
|-
|'''Abeceda''' [[Zašifrovaný text|zašifrovaného textu]]
|MAKEAPROFIT&nbsp;<ref>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."</ref>
|}
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 <sup>88,4</sup> alebo asi [[Veľkosť kľúča|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 [[Kryptoanalýza|kryptoanalytik]] odvodiť pravdepodobný význam najbežnejších symbolov analýzou [[Rozdelenie frekvencií|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é [[Angličtina|anglické]] slová so vzorom ''ABBCADB''. Mnoho ľudí rieši takéto šifry rekreačne, ako napríklad [[Kryptogram|kryptogramové]] hádanky v novinách.

Podľa [[Unicitná vzdialenosť|unicitnej vzdialenosti]] [[Angličtina|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 ==
[[Súbor:Babington postscript.jpg|náhľad|Falošná nomenklačná správa použitá v [[Babingtonský pozemok|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ód (kryptografia)|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é slovo|kódové slová]]'' v modernom jazyku) a písmená (v modernom jazyku ''šifra'' ) neboli v zašifrovanom texte rozlíšené. Jednou z nich bola [[Rossignols|Rossignolova]] [[veľká šifra]], ktorú používal [[Ľudovít XIV.|Ľudovít XIV]].

Nomenklátory boli štandardnou súčasťou [[Diplomacia|diplomatickej]] korešpondencie, [[Špionáž|špionáže]] a pokročilého politického [[sprisahanie (politické)|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 [[kryptoanalytik|kryptoanalytici]] [[vláda|vládnych]] [[Spravodajská služba|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ýza|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 [[Dejiny|historického výskumu]].

== Homofónna substitúcia ==
[[Súbor:Nomenclator-French 17th cent.jpg|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ónia (písanie)|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ácia nezávislosti Spojených štátov|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 <ref>Stahl, Fred A., ''On Computational Security'', University of Illinois, 1974</ref> <ref>Stahl, Fred A. "[http://www.computer.org/plugins/dl/pdf/proceedings/afips/1973/5081/00/50810565.pdf?template=1&loginState=1&userData=anonymous-IP%3A%3AAddress%3A+67.188.203.8%2C+%5B172.16.161.5%2C+67.188.203.8%2C+127.0.0.1%5D%20 A homophonic cipher for computational cryptography] {{Webarchive|url=https://web.archive.org/web/20160409131649/https://www.computer.org/plugins/dl/pdf/proceedings/afips/1973/5081/00/50810565.pdf?template=1&loginState=1&userData=anonymous-IP::Address:+67.188.203.8,+%5B172.16.161.5,+67.188.203.8,+127.0.0.1%5D%20 |date=2016-04-09 }}", afips, pp. 565, 1973 Proceedings of the National Computer Conference, 1973</ref> 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|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. <ref>David Salomon. [https://books.google.com/books?id=A88kvYwIVu0C&pg=PA224&lpg=PA224&dq=homophonic+cipher+mantua+1400s&source=bl&ots=yFuWwRbqiG&sig=SUYa0tmxxaeZhkBMkk84p1Nb4m8&hl=en&sa=X&ved=0ahUKEwiokPLgyvTKAhULCywKHegKDYEQ6AEIGjAA#v=onepage&q=homophonic%20cipher%20mantua%201400s&f=false Coding for Data and Computer Communications]. Springer, 2005.</ref> <ref>Fred A. Stahl. "[http://www.computer.org/csdl/proceedings/afips/1973/5081/00/50810565.pdf A homophonic cipher for computational cryptography]" Proceedings of the national computer conference and exposition (AFIPS '73), pp. 123–126, New York, USA, 1973.</ref>

== Polyalfabetická substitúcia ==
Dielo [[Al-Qalqashandi|Al-Qalqashandiho]] (1355-1418), založené na skoršom diele [[Ibn al-Durayhim|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.<ref>{{cite book|last1=Lennon|first1=Brian|title=Passwords: Philology, Security, Authentication|date=2018|publisher=[[Harvard University Press]]|isbn=9780674985377|page=26|url=https://books.google.com/books?id=jbpTDwAAQBAJ&pg=PT26}}</ref>. Polyalfabetické substitučné šifry neskôr opísal v roku 1467 [[Leon Battista Alberti|Leone Battista Alberti]] vo forme diskov. [[Johannes Trithemius]] vo svojej knihe ''Steganographia'' ([[Starogréčtina|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 [[Giambattista della Porta|Giovanni Battista della Porta]] vo svojej knihe ''[[De Furtivis Literarum Notis]]'' (v [[Latinčina|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ľka|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 [[Blaise de Vigenère|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úzština|francúzsky]] „nerozlúštiteľná šifra“).

Vo [[Vigenèrova šifra|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, [[Modulárna aritmetika|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 [[Krymská vojna|vojnou]] [[Charles Babbage|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<ref>{{Cite journal|last=Toemeh|first=Ragheb|year=2014|title=Certain investigations in Cryptanalysis of classical ciphers Using genetic algorithm|journal=Shodhganga|hdl=10603/26543}}</ref>. 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:

* Gronsfeldova šifra. Identická Vigenèrovej okrem toho, že sa používa iba 10 abecied, takže „kľúčové slovo“ je číselné.
* [[Beaufortova šifra]] . Prakticky to isté ako Vigenère, ibaže ''tabula recta'' je nahradená spätným, matematicky ekvivalentným šifrovým textom = kľúč - otvorený text. Táto operácia je ''samoinverzná'', pričom rovnaká tabuľka sa používa na šifrovanie aj dešifrovanie.
* [[Autokey šifra|Šifra automatického]] kľúča, ktorá kombinuje čistý text s kľúčom, aby sa zabránilo [[Periodická funkcia|periodicite]] .
* [[Spustená kľúčová šifra|Šifra bežiaceho kľúča]], kde je kľúč vytvorený veľmi dlhým použitím pasáže z knihy alebo podobného textu.

Moderné [[Prúdová šifra|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 ( <math>26^2</math> ). 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 [[Glyf (znak)|glyfmi]]. Systém bol však nepraktický a pravdepodobne sa nikdy nepoužil.

Najstaršia praktická '''digrafická šifra''' (párová substitúcia) bola takzvaná [[Playfair šifra|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 [[Druhá búrska vojna|búrskej vojny]] cez [[Druhá svetová vojna|druhú svetovú vojnu]].

Niekoľko ďalších praktických polygrafií zaviedol v roku 1901 [[Felix Delastelle]], vrátane [[Bifid šifra|bifidovej]] a štvorštvorcovej [[Štvorcová šifra|šifry]] (obe digrafické) a trifidovej [[Trifid šifra|š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árna algebra|lineárnej algebry]]. Každé písmeno sa považuje za číslicu v [[Číselná sústava|základe 26]] : A = 0, B = 1 atď. (Vo variácii sú pridané 3 extra symboly, aby bola  [[Báza (vektorový priestor)|vektorová báza]] [[Prvočíslo|prvočíslom]].) Blok n písmen sa potom považuje za n-rozmerný [[Vektorový priestor|vektor]] a vynásobí sa [[Matica (matematika)|maticou]] n x n, [[Modulárna aritmetika|modulo]] 26. Komponenty matice sú kľúčové a mali by byť [[Náhoda|náhodné]] za predpokladu, že matica je invertovateľná nad <math>\mathbb{Z}_{26}^n</math> (aby sa zabezpečilo možné dešifrovanie). Mechanická verzia Hillovej 6-rozmernej šifry bola patentovaná v roku 1929<ref>{{cite web|title=Message Protector patent US1845947|date=February 14, 1929|url=https://www.google.com/patents/US1845947|access-date=November 9, 2013}}</ref>.

Hillova šifra je zraniteľná voči útokom so [[Útok so známym otvoreným textom|známym otvoreným textom]], pretože je úplne [[Lineárne|lineárna]], takže na znemožnenie tohto útoku ju treba skombinovať s nejakým [[Nelineárne|nelineárnym]] krokom. Kombinácia širších a širších slabých, lineárnych [[Difúzia|rozptylových]] krokov, ako je Hillova šifra, s nelineárnymi substitučnými krokmi, v konečnom dôsledku vedie k [[Substitučná-permutačná sieť|substitučno-permutačnej sieti]] (napr. [[Feistelova šifra]] ), takže je možné – z tejto extrémnej perspektívy – uvažovať moderné [[Bloková šifra|blokové šifry]] ako typ polygrafickej substitúcie.

== Mechanické substitučné šifry ==
[[Súbor:HGM Enigma.jpg|náhľad|[[Enigma (šifrovací stroj)|Šifrovací stroj Enigma]], ktorý používala nemecká armáda v druhej svetovej vojne]]
Medzi [[Prvá svetová vojna|prvou svetovou vojnou]] a rozšírenou dostupnosťou [[Počítač|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 (šifrovací stroj)|Enigma]], najmä vo verziách používaných [[Wehrmacht|nemeckou armádou]] približne od roku 1930. [[Spojenci (druhá svetová vojna)|Spojenci]] tiež vyvinuli a používali rotorové stroje (napr. [[SIGABA]] a [[Typex]] ).

Všetky boli podobné v tom, že nahradené písmeno bolo vybrané [[Elektrina|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 [[Hebernov rotorový stroj|Hebernovom rotorovom stroji]] a [[Alfred Dillwyn Knox|Dillwyn Knox]] z GC&CS vyriešil verzie stroja Enigma (tie bez „zásuvného panela“) ešte pred začiatkom [[Druhá svetová vojna|druhej svetovej vojny]] . Prenos dát, ktorý chránili v podstate všetky nemecké vojenské Enigmy, prerušili spojeneckí kryptoanalytici, najmä tí v [[Bletchley Park|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 [[Marian Rejewski|Mariana Rejewského]] v [[Poľsko|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 [[Jozef Mauborgne|Joseph Mauborgne]] v USA. [[Claude Elwood Shannon|Claude Shannon]] matematicky dokázal, že je neprelomiteľný, pravdepodobne počas [[Druhá svetová vojna|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. [[Vylučujúce alebo|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áhoda|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á. [[Sovietsky zväz|Sovietske]] jednorazové blokové správy odoslané z USA na krátky čas počas druhej svetovej vojny používali [[Náhoda|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úca linka Moskva-Washington|horúcej linke]]'' [[Moskva]] - [[Washington, D. C.|Washington]] zriadenej po [[Kubánska raketová kríza|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á šifra|blokové šifry]] (napr. [[Data Encryption Standard|DES]] alebo [[Pokročilý štandard šifrovania|AES]] ) možno pozerať ako na substitučné šifry na enormne veľkej [[Dvojková číselná sústava|binárnej]] abecede. Okrem toho blokové šifry často obsahujú menšie substitučné tabuľky nazývané [[S-box|S-boxy]].

== Substitučné šifry v popkultúre ==

* [[Sherlock Holmes]] prelomil substitučnú šifru v knihe "[[Dobrodružstvo tancujúcich mužov]]". Tam zostala šifra nerozlúštená roky, ak nie desaťročia; nie pre jej náročnosť, ale preto, že [[Steganografia|nikto netušil, že ide o kód]], namiesto toho to považoval za detinské čmáranie.
* Jazyk [[Al Bhed]] vo ''[[Final Fantasy X]]'' je vlastne substitučná šifra, aj keď sa vyslovuje foneticky (t. j. „vy“ v angličtine sa prekladá na „oui“ v Al Bhed, ale vyslovuje sa rovnakým spôsobom ako „oui“ vo [[Francúzština|francúzštine]] ).
* [[Minbarijci|Minbarijská]] abeceda zo série ''[[Babylon 5]]'' je substitučná šifra z angličtiny.
* Jazyk v ''[[Dobrodružstvá Starfox|Starfox Adventures]] : Dinosaur Planet'', ktorým hovoria domorodí Sauriani a [[Zoznam postáv zo série Star Fox|Krystal]], je tiež substitučnou šifrou [[anglická abeceda|anglickej abecedy]] .
* Televízny program ''[[Futurama]]'' obsahoval substitučnú šifru, v ktorej bolo všetkých 26 písmen nahradených symbolmi a táto šifra bola nazvaná [http://www.gotfuturama.com/Interactive/AlienCodec/ „Alien Language“] {{Webarchive|url=https://web.archive.org/web/20221225115942/https://www.gotfuturama.com/Interactive/AlienCodec/ |date=2022-12-25 }} . Zarytí diváci to pomerne rýchlo rozlúštili zobrazením reklamy „Slurm“ so slovom „Drink“ v jednoduchej angličtine aj v jazyku mimozemšťanov, čím poskytli kľúč. Neskôr producenti vytvorili druhý cudzí jazyk, ktorý používal kombináciu substitučných a matematických šifier. Po rozlúštení anglického písmena cudzieho jazyka sa číselná hodnota tohto písmena (0 pre „A“ až po 25 pre „Z“) pripočíta (modulo 26) k hodnote predchádzajúceho písmena zobrazujúceho skutočný zamýšľaný list. Tieto správy možno vidieť v každej epizóde seriálu a nasledujúcich filmoch.
* Na konci každej epizódy prvej sezóny kresleného seriálu ''[[Gravity Falls]]'' je počas záverečných titulkov jedna z troch jednoduchých substitučných šifier: A -3 [[Cézarova šifra|Caesarova šifra]] (naznačená „3 písmenami späť“ na konci úvodnej sekvencie), [[Atbaš|Atbashova šifra]] alebo jednoduchá substitučná šifra z písmena na číslo. Finále 1. sezóny zakóduje posolstvo so všetkými tromi. V druhej sezóne sa používajú Vigenèrove [[Vigenèrova šifra|šifry]] namiesto rôznych monoalfabetických šifier, pričom každá používa kľúč skrytý vo svojej epizóde.
* V [[Artemis Fowl (knihy)|sérii Artemis Fowl]] od [[Eoin Colfer|Eoina Colfera]] sú tri substitučné šifry; Gnommish, Centaurean a Eternean, ktoré prebiehajú pozdĺž spodnej časti stránok alebo sú niekde inde v rámci kníh.
* V ''Bitterblue'', treťom románe [[Kristin Cashorová|Kristin Cashore]], slúžia substitučné šifry ako dôležitá forma kódovanej komunikácie.
* Vo videohre ''[[BioShock Infinite]]'' z roku 2013 sú v celej hre skryté substitučné šifry, v ktorých musí hráč nájsť kódové knihy, ktoré im pomôžu rozlúštiť ich a získať prístup k množstvu zásob.
* V anime adaptácii ''[[Diabol je brigádnik!|The Devil Is a Part-Timer!]]'', jazyk Ente Isla, nazývaný Entean, používa substitučnú šifru s abecedou šifrového textu, pričom na pôvodných pozíciách ponechajú iba A, E, I, O, U, L, N a Q.

== Referencie ==
<references />

== Externé odkazy ==

* [http://www.quipqiup.com/ quipqiup] Automatizovaný nástroj na riešenie jednoduchých substitučných šifier so známymi hranicami slov aj bez nich.
* [http://www.cryptool.org/ CrypTool] Vyčerpávajúci bezplatný a open source e-learningový nástroj na vykonávanie a prelomenie substitučných šifier a mnoho ďalších.
* Aplikácia [http://sourceforge.net/projects/substcipher Substitution Cipher Toolkit], ktorá dokáže – okrem iného – ''automaticky'' dešifrovať texty zašifrované substitučnou šifrou
* [http://www.secretcodebreaker.com/scbsolvr.html SCB Cipher Solver] Monoalfabetický lúštič šifier.
* [http://www.shubhsblog.com/c-language/mono-alphabetic-cipher-implementation-in-c-language-for-encrypting-file/ Implementácia monoalfabetickej šifry na šifrovanie súboru] {{Webarchive|url=https://archive.is/20140819191247/http://www.shubhsblog.com/c-language/mono-alphabetic-cipher-implementation-in-c-language-for-encrypting-file/ |date=2014-08-19 }} (jazyk C).
* [http://spwebgames.com/crypto/ Implementácia substitučnej šifry so šiframi Caesar a Atbash] (Java)
* [https://web.archive.org/web/20060413125614/http://blogger-bee.com/virtualsoil/CGI/anycode.html Online implementácia jednoduchej substitúcie] (Flash)
* [http://www.makeprofit.de/?code=1234567890 Online jednoduchá substitučná implementácia kódu MAKEPROFIT] {{Webarchive|url=https://web.archive.org/web/20110930195439/http://www.makeprofit.de/?code=1234567890 |date=2011-09-30 }} (CGI skript: Nastaviť vstup v URL, prečítať výstup na webovej stránke)
* [http://math.ucsd.edu/~crypto/java/EARLYCIPHERS/Monoalphabetic.html Monoalfabetická substitúcia] prelomila monoalfabetický šifrovací systém pomocou známeho útoku s otvoreným textom
* http://cryptoclub.math.uic.edu/substitutioncipher/sub2.htm {{Webarchive|url=https://web.archive.org/web/20081223103658/http://www.cryptoclub.math.uic.edu/substitutioncipher/sub2.htm |date=2008-12-23 }}
* [https://cryptoquipsanswer.com/how-to-solve-cryptoquip-puzzles/ Denná odpoveď na šifru Cryptoquip (Substitution).]
* [https://cryptoquip.net/ Denné hádanky Cryptoquip]

[[Kategória:Šifrovacie algoritmy]]