Solitaires kryptografiska algoritm är ett strömchiffer med utdatafeedback som utvecklades av Bruce Schneier på begäran av författaren Neil Stevenson .
Stevenson behövde en krypteringsalgoritm som skulle tillåta agenterna i hans bok Cryptonomicon att utbyta hemlig information utan att väcka misstankar. Solitaire var idealisk för dessa krav, eftersom det gjorde det möjligt för agenter att kryptera meddelanden utan att använda elektronik eller några kompromissande enheter. I boken kallades algoritmen "Pontifex" för att dölja det faktum att kort användes för kryptering.
"Solitaire" ärvde sin tillförlitlighet från den inneboende slumpmässigheten i kortens position när de blandade leken. Genom att manipulera en enkel kortlek kan personen som krypterar meddelandet skapa en slumpmässig sekvens av tecken som sedan kombineras med meddelandet. Denna algoritm kan tyckas ganska opålitlig, men enligt Schneier själv kan Solitaire motstå till och med de mäktigaste militära motståndarnas attack med enorm finansiering, kraftfulla datorer och utmärkta kryptoanalytiker och är världens bästa kryptografiska algoritm implementerad med hjälp av "penna och papper". [ett]
Huvudidén med denna algoritm är att den genererar den så kallade "gamma" av siffror från 1 till 26. För kryptering är det nödvändigt att generera antalet "gamma" lika med antalet bokstäver i texten. Lägg sedan till dem modulo 26 till var och en av bokstäverna i texten. Tänk till exempel på processen att kryptera det första meddelandet från boken "Cryptonomicon" "ANVÄND INTE PC":
1) Vi delar in meddelanden i grupper om fem tecken (detta har inget att göra med kryptering, det är bara accepterat), för att komplettera den sista gruppen, om nödvändigt, använd X. I vårt fall får vi:
2) Använd Solitaire för att generera tio skalor (detaljer nedan), låt oss säga att de är:
3) Vi översätter bokstäverna från meddelandet till siffror: A=1, B=2, etc., vi får:
4) På samma sätt översätter vi "vågen":
5) Lägg till meddelandet och "gamma" modulo 26:
6) Vi översätter det mottagna beloppet tillbaka till bokstäver:
Om du har tillräckligt med övning kan du försöka att omedelbart "lägga till" bokstäver, vilket avsevärt kommer att påskynda krypteringsprocessen.
Huvudidén med dekryptering är att mottagaren genererar samma "gamma" och subtraherar dem från chiffertexten.
1) Vi delar upp chiffertexten i grupper om fem tecken:
2) Vi använder en kortlek för att skapa "gamma". Om mottagaren använder samma nyckel som adresseren kommer "gamma" att vara detsamma:
3) Vi översätter chiffertexten från bokstäver till siffror:
4) Vi gör samma sak med "vågar":
5) Subtrahera gamma från chiffertexten modulo 26:
6) Vi översätter det mottagna beloppet tillbaka till bokstäver:
Som du kan se är dekrypteringsprocessen absolut lik krypteringsprocessen. Det här exemplet är ganska enkelt, men när du konverterar meddelanden av större storlek måste du först bli av med skiljetecken.
Låt oss gå vidare till generationen av "gamma". Detta är den viktigaste delen av algoritmen, allt ovanstående är sant för alla strömchiffer med utmatning . Samma del gäller direkt endast för Solitaire.
Solitaire genererar "gammas" med hjälp av en kortlek. En kortlek består av 54 kort, vilket ger oss antalet permutationer lika med 54!, vilket är ungefär lika med 2,3·10 71 . Ännu bättre, förutom jokarna, finns det 52 kort i leken och 26 bokstäver i alfabetet. För att kryptera behöver du en kortlek med 54 kort, och jokrarna måste på något sätt skilja sig från varandra. Låt oss villkorligt utse en av jokarna A och den andra B. För att "initiera" kortleken måste du ordna korten i en viss ordning, detta kommer att vara nyckeln. Sedan måste du ta korten med framsidan nedåt, nu kan du generera "gamma".
1) Hitta jokern A, flytta den ett kort nedåt, det vill säga byt plats med kortet under.
2) Hitta jokern B, flytta den två kort ner. Således, om korten placerades i denna ordning före det första steget:
sedan efter det andra steget:
Om vi först har t.ex.
sen får vi i slutet
3) Vi utför ett "trippelsnitt", det vill säga vi byter korten ovanför den första jokern med korten under den andra jokern. Det vill säga om kortleken ser ut så här:
sedan efter detta steg kommer det att gå till:
Som du kan se hänvisar "första" och "andra" här till den ordning i vilken jokarna dyker upp i kortleken. Det viktigaste att komma ihåg är att jokarna själva och korten mellan dem inte rör sig eller förändras på något sätt under detta steg. Och om kortleken ser ut så här före detta steg:
A ... B,sedan efter det 3:e steget kommer ingenting att förändras.
4) Vi tittar på det nedersta kortet i leken, sätter det i linje med ett nummer från 1 till 53.
Vi gör detta enligt följande: om färgen på kortet är klöver, så motsvarar detta värde det som visas på kortet; om dessa är diamanter är värdet plus 13; om hjärtan är värdet plus 26; spader - värde plus 39. Vilken som helst joker - 53. Nu räknar vi samma antal kort, med början från det första, och lägger dem mellan det nedersta kortet och resten av kortleken.
Om kortleken ursprungligen såg ut så här:
sedan efter detta steg kommer det att gå till:
Anledningen till att det sista kortet förblir på plats är att göra detta steg reversibelt. Om botten av kortleken var en joker, förblir den oförändrad efter detta steg.
5) Vi hittar en karta med vilken "gamma" kommer att skapas. För att göra detta jämför vi det översta kortet med ett nummer från 1 till 53, som i det fjärde steget. Vi räknar detta antal kort. Vi skriver ner kortet som ligger under det som vi räknade till på papper och lämnar det i kortleken (om vi slår jokern, börjar vi om från första steget). Det här är kartan vi är intresserade av. Observera att detta steg inte ändrar ordningen på korten i kortleken.
6) Vi översätter kortet från det femte steget till ett nummer. Detta görs på samma sätt som i det fjärde steget med ett undantag. Eftersom det finns 26 bokstäver i alfabetet numrerar vi klöver och hjärta från 1 till 13, och spader och ruter från 14 till 26. Sedan går vi vidare till bokstäver.
Sådana steg måste göras för att kryptera ett tecken. Genom att upprepa samma sex steg för varje okrypterat tecken krypterar vi hela klartexten.
I allmänhet är det inte nödvändigt att följa kortnumreringsreglerna som anges här, det viktigaste är att båda personerna följer samma system.
Innan du börjar kryptering måste du förbereda en kortlek. Detta är kanske den viktigaste delen, eftersom det enklaste sättet att knäcka Solitaire är att ta reda på vilken nyckel som används. För att nyckeln ska vara riktigt tillförlitlig bör du följa följande metoder:
Med allt detta bör man inte glömma att på engelska finns det bara 1,4 bitar av slumpmässighet per tecken, så författaren till algoritmen rekommenderar att kryptera fraser som är minst 80 tecken långa för att förbereda en kortlek.
Även om algoritmens ursprungliga författares papper säger att den är reversibel, gör situationen där jokern hamnar längst ner på kortleken och sedan flyttar till toppen när kortleken initieras processen oåterkallelig. Det är värt att notera här att icke-reversibla pseudoslumptalsgeneratorer har kortare perioder och tenderar att upprepas. När du använder Solitaire-algoritmen är det faktiskt möjligt att generera ett tal från 1 till 26, det vill säga att var och en av dem ska komma ut med en sannolikhet på 1/26, men i verkligheten är denna sannolikhet större - 1/22,5. [2]
Du kan också komma med en rysk version av detta chiffer, till exempel genom att släppa bokstaven "e" från alfabetet får vi 32 tecken plus 2 kort av analogen av jokrar, totalt - 34, det vill säga, en vanlig kortlek utan säg ett par sexor. Ett stort minus med sådan användning är en minskning av nyckelns styrka. Det här alternativet är förmodligen optimalt, eftersom i fallet med att lämna 52 kort och utföra beräkningar som liknar beräkningarna i originalversionen, men modulo 32, får vi möjlighet till frekvensanalys. Ett annat alternativ är att göra en omvandling av originaltexten skriven med alla 33 bokstäverna i det ryska alfabetet till en text som bara innehåller cirka 26 bokstäver. [3]
En nackdel är att kryptering och dekryptering tar lång tid. Men i jämförelse med andra liknande chiffer är denna tid acceptabel. Till exempel tar det riktiga chiffer som används av sovjetiska spioner, beskrivet av David Kann , lika lång tid att kryptera ett tillräckligt stort meddelande som Solitaire: ungefär en kväll.
Dessutom bör du följa följande regler: