Polyalfabetická šifra (polyalfabetická šifra) je soubor jednoduchých substitučních šifer , které se používají k zašifrování dalšího znaku otevřeného textu podle nějakého pravidla.
Podstatou polyalfabetické šifry je cyklická aplikace několika monoalfabetických šifer na určitý počet písmen zašifrovaného textu. Předpokládejme, že existuje nějaká zpráva x 1 , x 2 , x 3 , …, x n , …, x 2n , … , kterou je třeba zašifrovat, a pro použití polyalfabetické šifry bylo použito n monoalfabetických šifer. V tomto případě se první monoalfabetická šifra aplikuje na první písmeno, druhá na druhé písmeno, třetí na třetí, ..., n-té na n-té písmeno a první na (n + 1)-th znovu a tak dále, dokud není celá zpráva zašifrována. Získá se tak poměrně složitá sekvence, jejíž otevření je obtížnější než u monoalfabetické šifry. Důležitým efektem dosaženým při použití polyalfabetické šifry je maskování četností výskytu určitých písmen v textu, které jednoduché substituční šifry postrádají.
Historie kryptoanalýzy pochází z monoalfabetických šifer. Tato šifra poskytovala potřebné utajení přenášených zpráv, dokud rozvoj frekvenční kryptoanalýzy nezničil její sílu. První slabinu těchto šifer pro frekvenční kryptoanalýzu ukázal již v 9. století arabský filozof a matematik Al-Kindi ve své práci „ Rukopis o dešifrování kryptografických zpráv “ [1] . V Evropě byly monoalfabetické šifry velmi populární až do 15. století . Nápadným příkladem nespolehlivosti této šifry byla poprava Marie Stuartovny v roce 1587 . Důkazem spiknutí proti anglické královně Alžbětě byl dopis rozluštěný Thomasem Phelippesem od Marie Stuartovny Anthonymu Babingtonovi [1] .
Bylo tedy potřeba vytvořit dokonalejší způsob ochrany informací a monoalfabetické šifry byly nahrazeny polyalfabetickými. V šedesátých letech XV století italský vědec a architekt Leon Battista Alberti ( italsky Leone Battista Alberti ), který se pokoušel získat šifru odolnou vůči frekvenční kryptoanalýze, byl jedním z prvních, kdo použil dvě nebo více namísto jedné tajné abecedy, přecházení z jednoho do druhého podle určitého pravidla [ 2] . Bylo však na jeho následovnících, aby tento systém dovedli k plnohodnotnému [3] .
Významného výsledku dosáhl německý mnich Johann Trithemius ( lat. Iohannes Trithemius ). Podle jeho metody je následující písmeno nahrazeno znakem z vlastní šifrové abecedy a každá následující abeceda se z předchozí získá posunutím o jedno písmeno. Souhrn těchto šifer posunu, zapsaných pod sebou v pořadí, se nazývá tritémská tabulka [4] .
V roce 1553 navrhl Ital Giovan Battista Bellaso ( italsky Giovan Battista Bellaso ) v brožuře „Šifra Signora Giovanniho Bellaso“ ( italsky „La cifra del. Sig. Giovan Battista Belaso“ ) tuto metodu vylepšit zavedením klíčového slova. Písmena tohoto slova jsou postupně přepisována přes zašifrovaný text, takže každé písmeno klíče ukazuje na konkrétní šifrovou abecedu z Trithemiovy tabulky [5] .
Italský lékař a vědec Giambattista della Porta ( italsky Giambattista della Porta ) přitom zpochybnil spolehlivost polyalfabetických šifer. Při analýze šifrovacích metod navržených Trithemiem a Bellasem identifikoval některé vzory, s jejichž pomocí vyvinul metody pro otevírání těchto šifer. Porta však nebyl schopen rozšířit svá pozorování na polyalfabetické šifry obecně, a proto byl tento typ šifrování nadále považován za spolehlivý po dalších tři sta let [5] .
Dalším významným představitelem historie vývoje popsaných šifer je francouzský kryptograf Blaise de Vigenère ( francouzsky Blaise de Vigenère ). Na základě prací svých předchůdců vyvinul metodu šifrování podobnou té, kterou dříve navrhl Giovanni Bellaso. Hlavním rozdílem bylo, jak se volí šifrová abeceda pro další písmeno. Vigenère navrhl použít jako klíč nějaký jiný prostý text. Tuto šifrovací metodu, dnes známou jako Vigenèrova šifra , citoval ve své práci „Pojednání o šifrách“ ( fr. „Traicté des Chiffres“ ) v roce 1585 [4] .
Navzdory tehdejší odolnosti vůči kryptoanalýze nebyly polyalfabetické šifry dlouho široce používány kvůli složitosti jejich použití. Pro každodenní účely běžného člověka postačovalo používání monoalfabetických šifer a pro vojenské a diplomatické účely stát věnoval velkou pozornost rychlosti a jednoduchosti šifrování. K tomu sloužily některé intermediální šifry, jejichž otevření vyžadovalo ve srovnání s monoalfabetickými šiframi více úsilí, ale jejich použití bylo jednodušší než u polyalfabetických [3] .
S rozvojem „černých kabinetů“ v evropských zemích v 18. století ztratily všechny monoalfabetické substituční šifry veškerou spolehlivost. Tato skutečnost přispěla k nucenému přechodu na používání polyalfabetických šifer. Dalším důvodem pro popularizaci složitějšího typu šifrování byl rozvoj telegrafu a potřeba chránit zprávy před zachycením. [3]
V roce 1863 našel Friedrich Kasiski ( německy Friedrich Wilhelm Kasiski ) způsob, jak prolomit Vigenèrovu šifru pomocí krátkého kódového slova, jehož použití bylo nejčastější. V případě, že bylo šifrování provedeno pomocí klíče úměrného otevřenému textu, lze zvolit přístupovou frázi za předpokladu, že se skládá ze smysluplných slov. Pokusy vymyslet novou šifru odolnou proti prolomení dlouho nevedly k úspěchu, proto kryptografové přicházeli s takovými implementacemi existujících polyalfabetických šifer, aby se vyhnuli jejich otevírání pomocí Kasiskiho metody a metody výběru kódového slova [3] [4 ] . Například major US Army Joseph Mauborgne vynalezl jednorázovou šifrovací podložku na konci první světové války . Na každé stránce sešitu byla napsána sekvence stovek náhodných písmen, která byla použita jako jednorázový klíč k zašifrované zprávě. Vznikl také identický poznámkový blok, s jehož pomocí byla zpráva příjemcem dešifrována . Po použití byla odpovídající stránka každého notebooku zničena. Řada implementací však není široce používána kvůli složitosti jejich použití [6] .
Na přelomu 19. a 19. století se Thomas Jefferson pokusil zmechanizovat proces šifrování a vytvořil jeden z prvních rotačních strojů (také známý jako Jeffersonův válec ), který usnadnil používání polyalfabetických substitučních šifer. Rotační stroje se nejvíce používaly ve 20. století [4] [7] . Takové stroje poskytovaly zvýšený stupeň šifrovací síly a zvýšenou rychlost šifrování, což bylo zvláště důležité během vojenských operací. Mezi nejznámější rotační systémy lze jmenovat německý stroj Enigma , americký přístroj Sigaba a také stroj Tyrex, který pochází z Velké Británie . S nástupem počítačů ve 40. letech 20. století. bylo možné otevřít rotační kryptosystémy. Postupem času polyalfabetické šifry ustoupily do pozadí a byly nahrazeny novými, spolehlivějšími šifrovacími metodami [2] .
Prolomení polyalfabetické šifry v roce 1863 popsal ve své knize Die Geheimschriften und die Dechiffrirkunst ve své knize Die Geheimschriften und die Dechiffrirkunst bývalý důstojník pruské armády Friedrich Kasiski ( německy Friedrich Kasiski ) . Tato metoda je použitelná pro šifry s krátkým klíčovým slovem, protože je založena na hledání opakovaných sekvencí znaků v šifrovém textu. Délka klíče určuje počet možností, které lze použít k zašifrování stejné sekvence v otevřeném textu. Lze tedy předpokládat, že počet písmen mezi opakovanými sekvencemi v šifrovém textu je násobkem délky kódového slova. Dále kryptoanalytik určí pravděpodobný počet znaků v kódovém slově výběrem společných dělitelů pro všechny intervaly mezi opakováními. V konečné fázi je výchozí šifrový text považován za několik monoalfabetických šifer , na které je aplikována frekvenční kryptoanalýza [3] [8] .
Tuto metodu prolomení polyalfabetické šifry vyvinul již v roce 1854 Charles Babbage . Vzhledem k tomu, že výsledky své práce nepublikoval, vešlo o tom ve známost až ve 20. století . Proto je tento způsob dešifrování spojen se jménem Friedricha Kasisky a nazývá se také metoda Kasiska [3 ] .
V roce 1920 vyšla vynikající monografie s názvem Index náhody a její aplikace v kryptografii [ 9 ] . Jeho autorem je známý kryptoanalytik té doby William Friedman . Začal se zajímat o nalezení způsobu, jak prolomit Vigenèrovu šifru náhodným dlouhým klíčem [10] . Ve své analýze se nejprve obrátil ke statistickým metodám a považoval text za jediný objekt se vzájemně souvisejícími prvky. Díky práci Friedmana se objevil koncept „ indexu shody “ a kryptoanalýza byla obohacena o nástroje z kategorie statistického výzkumu [9] .
Jako příklad zašifrujme frázi „ odklon vojsk na východní hřeben “ pomocí Vigenèrovy šifry pomocí klíčového slova „ WHITE “. Zpočátku jsou písmena kódového slova psána jedno po druhém přes prostý text. Klíčové slovo se opakuje, dokud každé písmeno zašifrované zprávy neodpovídá určitému písmenu použitého klíče. Dále, abychom získali šifrový text, použijeme Vigenèrův čtverec . Každé písmeno klíčového slova se shoduje s řetězcem začínajícím stejným písmenem. Tato metoda určuje šifrovací abecedu, pomocí které bude každé písmeno otevřeného textu zašifrováno . To znamená , že 23. řádek Vigenèrova čtverce se používá k zašifrování prvního znaku " d " . Dalším krokem je najít písmeno, které stojí na průsečíku sloupce začínajícího na „ d “ a odpovídajícího řetězce šifrové abecedy. V tomto případě se jedná o písmeno " Z ", které je prvním znakem šifrového textu. Totéž uděláme s každým písmenem původní fráze [3] .
Pro dešifrování přijaté zprávy je třeba provést stejné kroky jako při šifrování, jen s jedním rozdílem: nyní je známo písmeno, které je na průsečíku řádku šifrové abecedy a sloupce začínajícího požadovaným písmenem v otevřeném textu [3] .