Solitaires kryptografiske algoritme er en stream-chiffer med output-feedback, der blev udviklet af Bruce Schneier på anmodning af forfatteren Neil Stevenson .
Stevenson havde brug for en krypteringsalgoritme, der ville tillade agenterne i hans bog Cryptonomicon at udveksle hemmelige oplysninger uden at vække mistanke. Solitaire var ideel til disse krav, da det tillod agenter at kryptere beskeder uden brug af elektronik eller kompromitterende enheder. I bogen blev algoritmen kaldt "Pontifex" for at skjule, at kort blev brugt til kryptering.
"Solitaire" arvede sin pålidelighed fra den iboende tilfældighed af kortenes placering, når de blandede bunken. Ved at manipulere et simpelt spil kort kan den person, der krypterer beskeden, skabe en tilfældig sekvens af tegn, som efterfølgende kombineres med beskeden. Denne algoritme kan virke ret upålidelig, men ifølge Schneier selv kan Solitaire modstå selv de mest magtfulde militære modstanders angreb med enorme midler, kraftfulde computere og fremragende kryptoanalytikere og er verdens bedste kryptografiske algoritme implementeret ved hjælp af "blyant og papir". [en]
Hovedideen med denne algoritme er, at den genererer det såkaldte "gamma" af tal fra 1 til 26. For kryptering er det nødvendigt at generere antallet af "gamma" svarende til antallet af bogstaver i teksten. Tilføj dem derefter modulo 26 til hvert af bogstaverne i teksten. Overvej for eksempel processen med at kryptere den første besked fra bogen "Cryptonomicon" "BRUG IKKE PC":
1) Vi opdeler beskeder i grupper på fem tegn (dette har intet at gøre med kryptering, det er bare accepteret), for at supplere den sidste gruppe, hvis det er nødvendigt, brug X. I vores tilfælde får vi:
2) Brug Solitaire til at generere ti skalaer (detaljer nedenfor), lad os sige, at de er:
3) Vi oversætter bogstaverne fra beskeden til tal: A=1, B=2 osv., vi får:
4) På samme måde oversætter vi "skalaerne":
5) Tilføj meddelelsen og "gamma" modulo 26:
6) Vi oversætter det modtagne beløb tilbage til bogstaver:
Hvis du har nok øvelse, kan du prøve at "tilføje" bogstaver med det samme, hvilket vil fremskynde krypteringsprocessen betydeligt.
Hovedideen med dekryptering er, at modtageren genererer den samme "gamma" og trækker dem fra chifferteksten.
1) Vi opdeler chifferteksten i grupper på fem tegn:
2) Vi bruger et sæt kort til at generere "gamma". Hvis modtageren bruger den samme nøgle som adresseren, vil "gamma" være den samme:
3) Vi oversætter chifferteksten fra bogstaver til tal:
4) Vi gør det samme med "skalaer":
5) Træk gamma fra chifferteksten modulo 26:
6) Vi oversætter det modtagne beløb tilbage til bogstaver:
Som du kan se, ligner dekrypteringsprocessen absolut krypteringsprocessen. Dette eksempel er ret simpelt, men når du konverterer beskeder af en større størrelse, skal du først slippe af med tegnsætningstegn.
Lad os gå videre til generationen af "gamma". Dette er den vigtigste del af algoritmen, alt ovenstående er sandt for enhver stream -chiffer med output-feedback . Den samme del gælder kun direkte for Solitaire.
Solitaire genererer "gammaer" ved hjælp af et sæt kort. Et sæt kort består af 54 kort, hvilket giver os antallet af permutationer svarende til 54!, hvilket er omtrent lig med 2,3·10 71 . Endnu bedre, bortset fra jokerne, er der 52 kort i bunken og 26 bogstaver i alfabetet. For at kryptere skal du bruge et kortspil med 54 kort, og jokerne skal på en eller anden måde adskille sig fra hinanden. Lad os betinget udpege en af jokerne A, og den anden B. For at "initialisere" bunken, skal du arrangere kortene i en bestemt rækkefølge, dette vil være nøglen. Så skal du tage kortene med billedsiden nedad, nu kan du generere "gamma".
1) Find jokeren A, flyt den et kort ned, det vil sige byt plads med kortet under den.
2) Find jokeren B, flyt den to kort ned. Således, hvis kortene blev placeret i denne rækkefølge før det første trin:
derefter efter det andet trin:
Hvis vi først har f.eks.
så får vi til sidst
3) Vi udfører et "triple cut", det vil sige at vi skifter kortene over den første joker med kortene under den anden joker. Det vil sige, hvis dækket ser sådan ud:
så efter dette trin vil det gå til:
Som du kan se, refererer "først" og "anden" her til den rækkefølge, som jokerne optræder i bunken. Det vigtigste at huske er, at jokerne selv og kortene mellem dem ikke bevæger sig eller ændres på nogen måde under dette trin. Og hvis dækket ser sådan ud før dette trin:
A ... B,så efter 3. trin vil intet ændre sig.
4) Vi ser på det nederste kort i bunken, sætter det på linje med et tal fra 1 til 53.
Vi gør dette på følgende måde: hvis farven på kortet er køller, svarer denne værdi til den, der vises på kortet; hvis disse er diamanter, så er værdien plus 13; hvis hjerter, så er værdien plus 26; spar - værdi plus 39. Enhver joker - 53. Nu tæller vi det samme antal kort, startende fra det første, og placerer dem mellem det nederste kort og resten af bunken.
Hvis dækket oprindeligt så sådan ud:
så efter dette trin vil det gå til:
Grunden til at det sidste kort forbliver på plads er at gøre dette trin reversibelt. Hvis bunden af bunken var en joker, forbliver den uændret efter dette trin.
5) Vi finder et kort, som "gamma" vil blive oprettet med. For at gøre dette sammenligner vi det øverste kort med et tal fra 1 til 53, som i det fjerde trin. Vi tæller dette antal kort. Vi skriver kortet ned, der ligger under det, vi talte til på papir, og efterlader det i bunken (hvis vi rammer jokeren, så starter vi igen fra det første trin). Dette er kortet, vi er interesserede i. Bemærk, at dette trin ikke ændrer rækkefølgen af kortene i bunken.
6) Vi oversætter kortet fra det femte trin til et tal. Dette gøres på samme måde som i fjerde trin med én undtagelse. Da der er 26 bogstaver i alfabetet, nummererer vi kløver og hjerter fra 1 til 13, og spar og ruder fra 14 til 26. Så går vi videre til bogstaver.
Sådanne trin skal udføres for at kryptere ét tegn. Ved at gentage de samme seks trin for hvert ukrypteret tegn krypterer vi hele klarteksten.
Generelt er det ikke nødvendigt at overholde kortnummereringsreglerne, der er givet her, det vigtigste er, at begge personer overholder den samme ordning.
Før du starter kryptering, skal du forberede et kortspil. Dette er måske den vigtigste del, for den nemmeste måde at knække Solitaire på er at finde ud af, hvilken nøgle der bruges. For at nøglen virkelig er pålidelig, bør du følge følgende metoder:
Med alt dette bør man ikke glemme, at der på engelsk kun er 1,4 bits tilfældighed pr. tegn, så forfatteren af algoritmen råder til at kryptere sætninger på mindst 80 tegn for at forberede et kortspil.
Selvom algoritmens oprindelige forfatters papir siger, at den er reversibel, gør situationen, hvor jokeren ender i bunden af bunken og derefter bevæger sig til toppen, når bunken påbegyndes, processen irreversibel. Det er værd at bemærke her, at ikke-reversible pseudo-tilfældige talgeneratorer har kortere perioder og har en tendens til at gentage. Faktisk, når du bruger Solitaire-algoritmen, er det muligt at generere et tal fra 1 til 26, det vil sige, at hver af dem skal komme ud med en sandsynlighed på 1/26, men i virkeligheden er denne sandsynlighed større - 1/22,5. [2]
Du kan også komme med en russisk version af denne chiffer, for eksempel ved at droppe bogstavet "e" fra alfabetet, får vi 32 tegn plus 2 kort af analogen af jokere, i alt - 34, det vil sige, et almindeligt dæk uden for eksempel et par seksere. Et stort minus ved sådan brug er et fald i nøglens styrke. Denne mulighed er formentlig optimal, for i tilfælde af at efterlade 52 kort og udføre beregninger svarende til beregningerne i den originale version, men modulo 32, får vi mulighed for frekvensanalyse. En anden mulighed er at lave en transformation af den originale tekst, der er skrevet med alle 33 bogstaver i det russiske alfabet, til en tekst, der kun indeholder omkring 26 bogstaver. [3]
En ulempe er, at kryptering og dekryptering tager lang tid. Men i sammenligning med andre lignende cifre er denne gang acceptabel. For eksempel tager den rigtige chiffer, der bruges af sovjetiske spioner, beskrevet af David Kann , lige så lang tid at kryptere en tilstrækkelig stor besked som Solitaire: cirka en aften.
Derudover skal du overholde følgende regler: