Kryptografický algoritmus Solitaire je proudová šifra s výstupní zpětnou vazbou, kterou vyvinul Bruce Schneier na žádost spisovatele Neila Stevensona .
Stevenson potřeboval šifrovací algoritmus, který by agentům v jeho knize Cryptonomicon umožnil vyměňovat si tajné informace, aniž by vzbudil podezření. Solitaire byl pro tyto požadavky ideální, protože umožňoval agentům šifrovat zprávy bez použití elektroniky nebo jakýchkoliv kompromitujících zařízení. V knize byl algoritmus nazván „Pontifex“, aby skryl skutečnost, že karty byly používány pro šifrování.
"Solitaire" zdědil svou spolehlivost z přirozené náhodnosti pozice karet při míchání balíčku. Manipulací s jednoduchým balíčkem karet může osoba šifrující zprávu vytvořit náhodnou sekvenci znaků, které jsou následně kombinovány se zprávou. Tento algoritmus se může zdát poněkud nespolehlivý, ale podle samotného Schneiera dokáže Solitaire odolat i útoku nejmocnějších vojenských protivníků s obrovskými finančními prostředky, výkonnými počítači a vynikajícími kryptoanalytiky a je nejlepším světovým kryptografickým algoritmem implementovaným pomocí „tužky a papíru“. [jeden]
Hlavní myšlenkou tohoto algoritmu je, že generuje tzv. „gama“ čísel od 1 do 26. Pro šifrování je nutné vygenerovat počet „gama“ rovný počtu písmen v textu. Pak je přidejte modulo 26 ke každému písmenu textu. Zvažte například proces šifrování první zprávy z knihy „Cryptonomicon“ „NEPOUŽÍVEJTE PC“:
1) Zprávy rozdělíme do skupin po pěti znacích (to nemá nic společného se šifrováním, je to jen akceptováno), pro doplnění poslední skupiny v případě potřeby použijeme X. V našem případě dostaneme:
2) Pomocí Solitaire vygenerujte deset měřítek (podrobnosti níže), řekněme, že jsou:
3) Písmena ze zprávy přeložíme na čísla: A=1, B=2 atd., dostaneme:
4) Stejným způsobem přeložíme „váhy“:
5) Přidejte zprávu a modul „gamma“ 26:
6) Přijatou částku převedeme zpět na písmena:
Pokud máte dostatek praxe, můžete zkusit písmena okamžitě „přidat“, což výrazně urychlí proces šifrování.
Hlavní myšlenkou dešifrování je, že adresát vygeneruje stejné „gama“ a odečte je od šifrovaného textu.
1) Šifrovaný text rozdělíme do skupin po pěti znacích:
2) Ke generování „gamma“ používáme balíček karet. Pokud příjemce používá stejný klíč jako adresát, bude „gama“ stejná:
3) Přeložíme šifrový text z písmen na čísla:
4) Totéž uděláme s „vahami“:
5) Odečtěte gama od šifrového textu modulo 26:
6) Přijatou částku převedeme zpět na písmena:
Jak vidíte, proces dešifrování je naprosto podobný procesu šifrování. Tento příklad je celkem jednoduchý, ale při převodu zpráv větší velikosti se nejprve musíte zbavit interpunkčních znamének.
Přejděme ke generaci „gama“. Toto je nejdůležitější část algoritmu, vše výše uvedené platí pro jakoukoli proudovou šifru s výstupní zpětnou vazbou . Stejná část platí přímo pouze pro Solitaire.
Solitaire generuje "gammy" pomocí balíčku karet. Balíček karet se skládá z 54 karet, což nám dává počet permutací rovný 54!, což se přibližně rovná 2,3·10 71 . Ještě lepší je, že kromě žolíků je v balíčku 52 karet a 26 písmen v abecedě. K šifrování potřebujete balíček s 54 kartami a žolíky se od sebe musí nějak lišit. Podmíněně označme jednoho ze žolíků A a druhého B. Chcete-li "inicializovat" balíček, musíte karty uspořádat v určitém pořadí, to bude klíč. Pak musíte vzít karty lícem dolů, nyní můžete generovat "gama".
1) Najděte žolíka A, posuňte jej o jednu kartu dolů, to znamená, vyměňte místa s kartou pod ním.
2) Najděte žolíka B, posuňte jej o dvě karty dolů. Pokud tedy byly karty umístěny v tomto pořadí před prvním krokem:
pak po druhém kroku:
Pokud máme nejprve např.
pak na konci dostaneme
3) Provedeme „triple cut“, tedy karty nad prvním žolíkem vyměníme za karty pod druhým žolíkem. Tedy pokud balíček vypadá takto:
pak po tomto kroku přejde na:
Jak můžete vidět, zde „první“ a „druhý“ označují pořadí, ve kterém se žolíci objevují v balíčku. Hlavní je pamatovat na to, že samotní žolíci a karty mezi nimi se během tohoto kroku nijak nepohybují ani nemění. A pokud balíček před tímto krokem vypadá takto:
A ... B,pak se po 3. kroku nic nezmění.
4) Podíváme se na spodní kartu v balíčku a položíme ji do řady s číslem od 1 do 53.
Děláme to následovně: pokud jsou barvou karty kluby, pak tato hodnota odpovídá hodnotě uvedené na kartě; pokud se jedná o diamanty, pak je hodnota plus 13; pokud srdce, pak je hodnota plus 26; piky - hodnota plus 39. Libovolný žolík - 53. Nyní spočítáme stejný počet karet, počínaje první, a položíme je mezi spodní kartu a zbytek balíčku.
Pokud balíček původně vypadal takto:
pak po tomto kroku přejde na:
Důvodem, proč poslední karta zůstává na místě, je učinit tento krok vratným. Pokud byl spodek balíčku žolík, zůstane po tomto kroku nezměněn.
5) Najdeme mapu, pomocí které bude „gama“ vytvořena. K tomu porovnáme horní kartu s číslem od 1 do 53, jako ve čtvrtém kroku. Počítáme tento počet karet. Kartu, která leží pod tou, se kterou jsme počítali, si zapíšeme na papír a necháme ji v balíčku (pokud trefíme žolíka, pak začneme znovu od prvního kroku). Toto je mapa, která nás zajímá. Všimněte si, že tento krok nemění pořadí karet v balíčku.
6) Kartu z pátého kroku přeložíme na číslo. To se provádí stejným způsobem jako ve čtvrtém kroku s jednou výjimkou. Protože abeceda má 26 písmen, číslujeme palice a srdce od 1 do 13 a piky a káry od 14 do 26. Poté přejdeme k písmenům.
Takové kroky je třeba provést pro zašifrování jednoho znaku. Opakováním stejných šesti kroků pro každý nezašifrovaný znak zašifrujeme celý otevřený text.
Obecně není nutné dodržovat zde uvedená pravidla číslování karet, hlavní je, že obě osoby dodržují stejné schéma.
Před zahájením šifrování je třeba připravit balíček. To je možná nejdůležitější část, protože nejjednodušší způsob, jak prolomit Solitaire, je zjistit, který klíč se používá. Aby byl klíč skutečně spolehlivý, měli byste dodržovat následující metody:
Při tom všem bychom neměli zapomínat, že v angličtině je pouze 1,4 bitů náhodnosti na znak, takže autor algoritmu doporučuje zašifrovat fráze dlouhé alespoň 80 znaků, aby se připravil balíček.
Ačkoli původní článek autora algoritmu uvádí, že je reverzibilní, situace, kdy žolík skončí na dně balíčku a poté se přesune nahoru, když je balíček zahájen, činí proces nevratným. Zde stojí za zmínku, že nevratné generátory pseudonáhodných čísel mají kratší periody a mají tendenci se opakovat. Při použití algoritmu Solitaire je skutečně možné vygenerovat číslo od 1 do 26, to znamená, že každé z nich by mělo vyjít s pravděpodobností 1/26, ale ve skutečnosti je tato pravděpodobnost větší - 1/22,5. [2]
Můžete také přijít s ruskou verzí této šifry, například vypuštěním písmene „e“ z abecedy získáme 32 znaků plus 2 karty analogu žolíků, celkem - 34, tj. běžný balíček bez, řekněme, páru šestek. Obrovským mínusem takového použití je snížení síly klíče. Tato možnost je asi optimální, protože v případě ponechání 52 karet a provedení výpočtů podobných výpočtům v původní verzi, ale modulo 32, získáme možnost frekvenční analýzy. Další možností je vymyslet transformaci původního textu psaného pomocí všech 33 písmen ruské abecedy na text obsahující pouze nějakých 26 písmen. [3]
Jednou nevýhodou je, že šifrování a dešifrování trvá dlouho. Ale ve srovnání s jinými podobnými šiframi je tato doba přijatelná. Například skutečná šifra používaná sovětskými špiony, popsaná Davidem Kannem , trvá zašifrování dostatečně velké zprávy stejně dlouho jako Solitaire: přibližně jeden večer.
Kromě toho byste měli dodržovat následující pravidla: