Algoritmul criptografic Solitaire este un cifr de flux cu feedback de ieșire care a fost dezvoltat de Bruce Schneier la cererea scriitorului Neil Stevenson .
Stevenson avea nevoie de un algoritm de criptare care să permită agenților din cartea sa Cryptonomicon să facă schimb de informații secrete fără a trezi suspiciuni. Solitaire era ideal pentru aceste cerințe, deoarece le permitea agenților să cripteze mesajele fără a utiliza electronice sau orice dispozitiv compromițător. În carte, algoritmul a fost numit „Pontifex” pentru a ascunde faptul că cardurile erau folosite pentru criptare.
„Solitaire” și-a moștenit fiabilitatea din caracterul aleatoriu inerent al poziției cărților la amestecarea pachetului. Prin manipularea unui pachet simplu de cărți, persoana care criptează mesajul poate crea o secvență aleatorie de caractere care sunt ulterior combinate cu mesajul. Acest algoritm poate părea destul de nesigur, dar potrivit lui Schneier însuși, Solitaire poate rezista chiar și atacului celor mai puternici oponenți militari cu finanțare uriașă, computere puternice și criptoanalisti excelenți și este cel mai bun algoritm criptografic din lume implementat folosind „creion și hârtie”. [unu]
Ideea principală a acestui algoritm este că generează așa-numita „gamma” de numere de la 1 la 26. Pentru criptare, este necesar să se genereze un număr de „gamma” egal cu numărul de litere din text. Apoi adăugați-le modulo 26 la fiecare dintre literele textului. De exemplu, luați în considerare procesul de criptare a primului mesaj din cartea „Cryptonomicon” „NU UTILIZAȚI PC”:
1) Împărțim mesajele în grupuri de cinci caractere (acest lucru nu are nimic de-a face cu criptarea, este doar acceptat), pentru a completa ultimul grup, dacă este necesar, folosiți X. În cazul nostru, obținem:
2) Folosiți Solitaire pentru a genera zece scale (detalii mai jos), să presupunem că acestea sunt:
3) Traducem literele din mesaj în cifre: A=1, B=2 etc., obținem:
4) În același mod, traducem „scălele”:
5) Adăugați mesajul și „gamma” modulo 26:
6) Traducem suma primită înapoi în litere:
Dacă aveți suficientă practică, puteți încerca să „adăugați” imediat litere, ceea ce va accelera semnificativ procesul de criptare.
Ideea principală a decriptării este că destinatarul generează aceeași „gamă” și le scade din textul cifrat.
1) Împărțim textul cifrat în grupuri de cinci caractere:
2) Folosim un pachet de cărți pentru a genera „gama”. Dacă destinatarul folosește aceeași cheie ca și adresatorul, atunci „gama” va fi aceeași:
3) Traducem textul cifrat din litere în cifre:
4) Facem același lucru cu „sânare”:
5) Scădeți gamma din textul cifrat modulo 26:
6) Traducem suma primită înapoi în litere:
După cum puteți vedea, procesul de decriptare este absolut similar cu procesul de criptare. Acest exemplu este destul de simplu, dar atunci când convertiți mesaje de dimensiuni mai mari, trebuie mai întâi să scăpați de semnele de punctuație.
Să trecem la generația „gamma”. Aceasta este cea mai importantă parte a algoritmului, toate cele de mai sus sunt valabile pentru orice cifru de flux cu feedback de ieșire . Aceeași parte se aplică direct doar pentru Solitaire.
Solitaire generează „gamas” folosind un pachet de cărți. Un pachet de cărți este format din 54 de cărți, ceea ce ne oferă numărul de permutări egal cu 54!, care este aproximativ egal cu 2,3·10 71 . Și mai bine, în afară de glumeți, sunt 52 de cărți în pachet și 26 de litere în alfabet. Pentru a cripta, ai nevoie de un pachet cu 54 de cărți, iar glumeții trebuie să difere cumva unul de celălalt. Să desemnăm condiționat unul dintre jokeri A și celălalt B. Pentru a „inițializa” pachetul, trebuie să aranjați cărțile într-o anumită ordine, aceasta va fi cheia. Apoi trebuie să luați cărțile cu fața în jos, acum puteți genera „gama”.
1) Găsiți jokerul A, mutați-l cu o carte în jos, adică schimbați locurile cu cartea de sub ea.
2) Găsiți jokerul B, mutați-l cu două cărți în jos. Astfel, dacă cărțile au fost plasate în această ordine înainte de primul pas:
apoi după al doilea pas:
Dacă avem mai întâi, de exemplu,
apoi la final ajungem
3) Efectuăm o „triple cut”, adică schimbăm cărțile de deasupra primului joker cu cărțile de sub al doilea joker. Adică, dacă pachetul arată astfel:
apoi, după acest pas, va merge la:
După cum puteți vedea, aici „primul” și „al doilea” se referă la ordinea în care jokerii apar în pachet. Principalul lucru de reținut este că glumeții înșiși și cărțile dintre ei nu se mișcă sau se schimbă în niciun fel în timpul acestui pas. Și dacă pachetul arată așa înainte de acest pas:
A ... B,apoi după pasul 3 nu se va schimba nimic.
4) Ne uităm la cartea de jos din pachet, o punem în linie cu un număr de la 1 la 53.
Facem acest lucru în felul următor: dacă culoarea cărții este crose, atunci această valoare corespunde cu cea afișată pe carte; dacă acestea sunt diamante, atunci valoarea este plus 13; dacă inimi, atunci valoarea este plus 26; pică - valoare plus 39. Orice joker - 53. Acum numărăm același număr de cărți, începând de la prima, și le punem între cartea de jos și restul pachetului.
Dacă inițial pachetul arăta astfel:
apoi, după acest pas, va merge la:
Motivul pentru care ultimul card rămâne pe loc este pentru a face acest pas reversibil. Dacă partea de jos a pachetului a fost un joker, atunci rămâne neschimbată după acest pas.
5) Găsim o hartă cu care va fi creată „gama”. Pentru a face acest lucru, comparăm cardul de sus cu un număr de la 1 la 53, ca în pasul al patrulea. Numărăm acest număr de cărți. Notăm cartea care se află sub cea la care am numărat pe hârtie, lăsând-o în pachet (dacă lovim jokerul, atunci începem din nou de la primul pas). Aceasta este harta care ne interesează. Rețineți că acest pas nu schimbă ordinea cărților din pachet.
6) Traducem cardul de la pasul al cincilea într-un număr. Acest lucru se face în același mod ca în pasul al patrulea, cu o singură excepție. Deoarece există 26 de litere în alfabet, numărăm cluburile și inimile de la 1 la 13, iar pică și diamantele de la 14 la 26. Apoi trecem la litere.
Astfel de pași trebuie să fie efectuati pentru a cripta un caracter. Repetând aceiași șase pași pentru fiecare caracter necriptat, criptăm întregul text simplu.
În general, nu este necesar să respectați regulile de numerotare a cardurilor prezentate aici, principalul lucru este ca ambele persoane să adere la aceeași schemă.
Înainte de a începe criptarea, trebuie să pregătiți un pachet. Aceasta este poate cea mai importantă parte, deoarece cel mai simplu mod de a sparge Solitaire este să aflați ce cheie este folosită. Pentru ca cheia să fie cu adevărat de încredere, ar trebui să respectați următoarele metode:
Cu toate acestea, nu trebuie uitat că în engleză există doar 1,4 biți de aleatorie pe caracter, așa că autorul algoritmului sfătuiește să criptezi fraze de cel puțin 80 de caractere pentru a pregăti un pachet.
Deși lucrarea originală a autorului algoritmului afirmă că este reversibil, situația în care jokerul ajunge în partea de jos a pachetului și apoi se deplasează în partea de sus când pachetul este inițiat face procesul ireversibil. Este demn de remarcat aici că generatoarele de numere pseudoaleatoare ireversibile au perioade mai scurte și tind să se repete. Într-adevăr, atunci când se utilizează algoritmul Solitaire, este posibil să se genereze un număr de la 1 la 26, adică fiecare dintre ele ar trebui să iasă cu o probabilitate de 1/26, dar în realitate această probabilitate este mai mare - 1/22,5. [2]
De asemenea, puteți veni cu o versiune rusă a acestui cifr, de exemplu, eliminând litera „e” din alfabet, obținem 32 de caractere plus 2 cărți ale analogului de joker, în total - 34, adică, o punte obișnuită fără, să zicem, o pereche de șase. Un minus imens al unei astfel de utilizări este o scădere a puterii cheii. Această opțiune este probabil optimă, deoarece în cazul lăsării a 52 de carduri și efectuării unor calcule similare cu calculele din versiunea originală, dar modulo 32, obținem posibilitatea analizei frecvenței. O altă opțiune este de a veni cu o transformare a textului original scris folosind toate cele 33 de litere ale alfabetului rus într-un text care conține doar aproximativ 26 de litere. [3]
Un dezavantaj este că criptarea și decriptarea durează mult timp. Dar în comparație cu alte cifruri similare, această dată este acceptabilă. De exemplu, cifrul real folosit de spionii sovietici, descris de David Kann , are nevoie de aceeași perioadă de timp pentru a cripta un mesaj suficient de mare ca și Solitaire: aproximativ o seară.
În plus, ar trebui să respectați următoarele reguli: