A Solitaire kriptográfiai algoritmus egy kimeneti visszacsatolású adatfolyam titkosítás , amelyet Bruce Schneier fejlesztett ki Neil Stevenson író kérésére .
Stevensonnak szüksége volt egy titkosító algoritmusra, amely lehetővé teszi a Cryptonomicon című könyvében szereplő ügynökök számára, hogy gyanút keltve titkos információkat cseréljenek. A Solitaire ideális volt ezeknek a követelményeknek, mivel lehetővé tette az ügynökök számára az üzenetek titkosítását elektronika vagy bármilyen kompromittáló eszköz használata nélkül. A könyvben az algoritmust Pontifexnek hívták, hogy elrejtse azt a tényt, hogy a kártyákat titkosításra használták.
A "Solitaire" megbízhatóságát a kártyák helyzetének véletlenszerűségéből örökölte a pakli keverésekor. Egy egyszerű pakli kártya manipulálásával az üzenetet titkosító személy véletlenszerű karaktersorozatot hozhat létre, amelyet azután az üzenettel kombinál. Ez az algoritmus meglehetősen megbízhatatlannak tűnhet, de maga Schneier szerint a Solitaire a legerősebb katonai ellenfelek támadását is képes ellenállni hatalmas finanszírozás, nagy teljesítményű számítógépek és kiváló kriptoanalitikusok segítségével, és a világ legjobb "ceruzával és papírral" megvalósított kriptográfiai algoritmusa. [egy]
Ennek az algoritmusnak az a fő gondolata, hogy az 1-től 26-ig terjedő számok úgynevezett "gammáját" állítja elő. A titkosításhoz a szövegben lévő betűk számával megegyező számú "gamma" generálása szükséges. Ezután adja hozzá a modulo 26-ot a szöveg egyes betűihez. Vegyük például a „Cryptonomicon” „DO NOT USE PC” című könyv első üzenetének titkosítási folyamatát:
1) Az üzeneteket öt karakteres csoportokra osztjuk (ennek semmi köze a titkosításhoz, csak elfogadott), az utolsó csoport kiegészítésére, ha szükséges, használjunk X-et. Esetünkben a következőt kapjuk:
2) A Solitaire segítségével állítson elő tíz skálát (részletek lent), tegyük fel, hogy ezek:
3) Az üzenet betűit számokká fordítjuk: A=1, B=2 stb., így kapjuk:
4) Ugyanígy lefordítjuk a „skálát”:
5) Adja hozzá az üzenetet és a „gamma” modulo 26-ot:
6) A kapott összeget visszafordítjuk betűkre:
Ha van elég gyakorlatod, megpróbálhatod azonnal "hozzáadni" a betűket, ami jelentősen felgyorsítja a titkosítási folyamatot.
A visszafejtés fő ötlete az, hogy a címzett ugyanazt a "gammát" generálja, és kivonja őket a rejtjelezett szövegből.
1) A rejtjelezett szöveget öt karakterből álló csoportokra osztjuk:
2) Egy pakli kártya segítségével generálunk „gammákat”. Ha a címzett ugyanazt a kulcsot használja, mint a címadó, akkor a "gamma" ugyanaz lesz:
3) A titkosított szöveget betűkből számokká fordítjuk:
4) Ugyanezt tesszük a "mérlegekkel" is:
5) Vonja ki a gammát a titkosított szöveg modulo 26-ból:
6) A kapott összeget visszafordítjuk betűkre:
Amint láthatja, a visszafejtési folyamat teljesen hasonló a titkosítási folyamathoz. Ez a példa meglehetősen egyszerű, de nagyobb méretű üzenetek konvertálásakor először meg kell szabadulnia az írásjelektől.
Térjünk át a „gamma” generációjára. Ez az algoritmus legfontosabb része, a fentiek mindegyike igaz minden kimeneti visszacsatolású adatfolyam titkosításra . Ugyanez a rész közvetlenül csak a Solitaire-re vonatkozik.
A pasziánsz "gammákat" generál egy pakli kártya segítségével. Egy kártyapakli 54 lapból áll, így a permutációk száma 54!, ami megközelítőleg 2,3·10 71 . Még jobb, hogy a jokereken kívül 52 kártya van a pakliban és 26 betű az ábécében. A titkosításhoz egy 54 kártyás paklira van szükség, és a jokereknek valahogy különbözniük kell egymástól. Jelöljük feltételesen az egyik jokert A-t, a másikat B-t. A pakli "inicializálásához" bizonyos sorrendbe kell rendezni a kártyákat, ez lesz a kulcs. Ezután képpel lefelé kell venni a kártyákat, most már generálhat "gammát".
1) Keresd meg az A jokert, mozgasd egy kártyával lejjebb, azaz cserélj helyet az alatta lévő lappal.
2) Keresd meg a B jokert, mozgasd két kártyával lejjebb. Tehát, ha a kártyákat ebben a sorrendben helyezték el az első lépés előtt:
majd a második lépés után:
Ha először rendelkezünk pl.
majd a végén megkapjuk
3) Végrehajtunk egy „tripla vágást”, vagyis az első joker feletti lapokat a második joker alatti lapokkal cseréljük. Vagyis ha a pakli így néz ki:
majd e lépés után a következőre fog menni:
Amint láthatja, itt az "első" és a "második" a jokerek megjelenési sorrendjét jelenti a pakliban. A legfontosabb, hogy ne feledje, hogy maguk a jokerek és a köztük lévő kártyák nem mozognak vagy változnak semmilyen módon ebben a lépésben. És ha a pakli így néz ki e lépés előtt:
A... B,akkor a 3. lépés után semmi sem fog változni.
4) Megnézzük a pakli alsó kártyáját, és sorba tesszük egy 1-től 53-ig terjedő számmal.
Ezt a következőképpen tesszük: ha a kártya színe ütős, akkor ez az érték megegyezik a kártyán feltüntetett értékkel; ha ezek gyémántok, akkor az érték plusz 13; ha szív, akkor az érték plusz 26; pikk - érték plusz 39. Bármely joker - 53. Most megszámoljuk ugyanannyi kártyát, az elsőtől kezdve, és az alsó lap és a pakli többi része közé helyezzük.
Ha a pakli eredetileg így nézett ki:
majd e lépés után a következőre fog menni:
Az ok, amiért az utolsó kártya a helyén marad, az az, hogy ezt a lépést visszafordíthatóvá tegyük. Ha a pakli alja joker volt, akkor ez a lépés után változatlan marad.
5) Találunk egy térképet, amellyel a „gamma” létrejön. Ehhez összehasonlítjuk a felső kártyát egy 1-től 53-ig terjedő számmal, mint a negyedik lépésben. Megszámoljuk ennyi kártyát. Felírjuk a papírra azt a kártyát, amelyik alá számoltunk, a pakliban hagyva (ha eltaláltuk a jokert, akkor az első lépéstől kezdjük újra). Ez a térkép érdekel minket. Vegye figyelembe, hogy ez a lépés nem változtatja meg a kártyák sorrendjét a pakliban.
6) Lefordítjuk a kártyát az ötödik lépésből számmá. Ez egy kivétellel ugyanúgy történik, mint a negyedik lépésben. Mivel az ábécében 26 betű van, a botokat és a szíveket 1-től 13-ig számozzuk, az ásót és a gyémántot 14-től 26-ig. Ezután térünk át a betűkre.
Ilyen lépéseket kell tenni egy karakter titkosításához. Ugyanazt a hat lépést megismételve minden titkosítatlan karakterhez, a teljes szöveget titkosítjuk.
Általában nem szükséges betartani az itt megadott kártyaszámozási szabályokat, a lényeg az, hogy mindkét ember ugyanazt a sémát tartsa be.
A titkosítás megkezdése előtt el kell készítenie egy fedélzetet. Ez talán a legfontosabb rész, mert a Solitaire feltörésének legegyszerűbb módja, ha megtudja, melyik kulcsot használja. Annak érdekében, hogy a kulcs valóban megbízható legyen, kövesse az alábbi módszereket:
Mindezek mellett nem szabad elfelejteni, hogy az angolban csak 1,4 bites véletlenszerűség van karakterenként, ezért az algoritmus szerzője azt tanácsolja, hogy a pakli elkészítéséhez legalább 80 karakteres frázisokat titkosítsanak.
Bár az algoritmus eredeti szerzője azt állítja, hogy megfordítható, az a helyzet, amikor a joker a pakli aljára kerül, majd a pakli indításakor a tetejére kerül, visszafordíthatatlanná teszi a folyamatot. Itt érdemes megjegyezni, hogy a nem reverzibilis pszeudo-véletlenszám-generátorok periódusai rövidebbek, és hajlamosak az ismétlődésre. Valójában a Solitaire algoritmus használatával 1-től 26-ig lehet számot generálni, vagyis mindegyiknek 1/26 valószínűséggel kell kijönnie, de a valóságban ez a valószínűség nagyobb - 1/22,5. [2]
Kitalálhatja ennek a rejtjelnek az orosz változatát is, például az „e” betű elhagyásával az ábécéből 32 karaktert és 2 kártyát kapunk a jokerek analógjából, összesen - 34, azaz egy rendes pakli, mondjuk hatos pár nélkül. Az ilyen használat hatalmas mínusza a kulcs erősségének csökkenése. Valószínűleg ez a lehetőség optimális, mert 52 kártya elhagyása és az eredeti verzióban szereplő számításokhoz hasonló, de modulo 32 számítások elvégzése esetén lehetőség nyílik a frekvenciaelemzésre. Egy másik lehetőség az, hogy az orosz ábécé mind a 33 betűjét használva írt eredeti szöveget csak 26 betűből álló szöveggé alakítják át. [3]
Egyik hátránya, hogy a titkosítás és a visszafejtés sokáig tart. De a többi hasonló titkosításhoz képest ez az idő elfogadható. Például a szovjet kémek által használt valódi titkosítás, amelyet David Kann ír le , ugyanannyi időt vesz igénybe egy kellően nagy üzenet titkosítása, mint a Solitaire: körülbelül egy este.
Ezenkívül be kell tartania a következő szabályokat: