Szyfr Solitaire

Solitaire – szyfr stworzony przez Bruce’a Schneiera dla potrzeb osób niemających dostępu do komputera. Jest to prosty szyfr strumieniowy (jednakże autor zaleca używanie go w trybie blokowym ze względu na wygodę), w którym cyfry oznaczające litery tekstu jawnego poddawane są operacji dodawania modulo 26 ze strumieniem klucza, a następnie ponownie zamieniane na litery. Strumień klucza jest generowany przy użyciu talii kart.

Solitaire Cipher

Rodzaj algorytmu	strumieniowy, opcjonalnie blokowy
Autorzy	Bruce Schneier, Neal Stephenson
Długość klucza	54 bity
Liczba rund	1

Strumień klucza a klucz

Strumieniem klucza nazywamy ciąg wartości wygenerowany za pomocą odpowiedniego algorytmu, za pomocą którego szyfrowany jest tekst jawny, w tym przypadku będzie to algorytm przekładania kart. Kluczem nazywamy ciąg wartości, na podstawie których będziemy obliczać strumień klucza, w tym przypadku będzie to początkowe ułożenie kart.

Szyfrowanie i deszyfrowanie

Szyfrowanie

Szyfrowanie polega na dodaniu modulo 26 liczb odpowiadających literom tekstu jawnego oraz strumienia klucza, a następnie ponowną zamianę wyniku tego działania na litery. Można to zapisać jako następujące działanie matematyczne

(M + K) mod 26 = C

gdzie M to zbiór wartości liter tekstu jawnego, K to zbiór wartości strumienia klucza a C to szyfrogram. Wartości liczbowej litery odpowiada jej pozycja w alfabecie. Litera A będzie odpowiadała liczbie 1, litera B liczbie 2, C liczbie 3 i tak dalej. Autor zaleca, aby dla wygody szyfrować tekst jawny w pięcioznakowych grupach. Jeżeli długość tekstu jawnego nie jest wielokrotnością liczby 5, należy dopełnić wiadomość do takiej długości za pomocą liter „X”.

Przykład

Tekst jawny:

To jest tajna wiadomosc.

Strumień klucza:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Po zamianie na wartości liczbowe tekst jawny będzie miał postać:

20 15 10 5 19 20 20 1 10 14 1 23 9 1 4 15 13 15 19 3

Należy po kolei dodać wartości liczbowe liter tekstu jawnego i strumienia klucza modulo 26. W wyniku otrzymamy:

21 17 13 19 24 26 1 9 19 24 12 9 22 15 19 5 4 7 12 23

Po zamianie liczb na litery będzie to:

Uq mixz aisxl ivosedglw.

Deszyfrowanie

Deszyfrowanie wiadomości polega na odejmowaniu modulo wartości liter szyfrogramu i klucza.

Przykład

Mamy szyfrogram:

Uq mixz aisxl ivosedglw.

oraz strumień klucza:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Zamieniamy szyfrogram na wartość liczbową. Szyfrogram:

21 17 13 19 24 26 1 9 19 24 12 9 22 15 19 5 4 7 12 23

Następnie odejmujemy po kolei każdą wartość strumienia klucza od wartości szyfrogramu. Jeżeli wynikiem jest liczba mniejsza od 1, obliczamy 26 – wynik. Dla przykładu: po odjęciu liczb 13 i 21 uzyskamy wynik -8. Obliczamy więc 26-8=18. Jest to wartość litery tekstu jawnego. Następnie zamieniamy liczby na litery. W ten sposób otrzymamy tekst jawny:

To jest tajna wiadomosc.

Generowanie strumienia klucza

Najważniejszą częścią szyfru jest generator strumienia klucza, którego działanie polega na odpowiednim manipulowaniu talią kart. Aby właściwie wygenerować klucz, w talii muszą występować 54 karty (standardowa talia 52 kart + 2 jokery). Dodatkowo, oba jokery muszą się od siebie różnić. Przed rozpoczęciem generowania strumienia klucza należy ustalić, który z jokerów jest „ważniejszy”. W dalszej części będzie on oznaczany literą A, natomiast joker mniej ważny literą B. Należy uznać najpopularniejsze starszeństwo kart, od najsłabszych: As, 2..10, Walet, Dama, Król.

1. Ułóż karty w pozycji startowej (jest to klucz szyfrujący).
2. Znajdź jokera A i przesuń go o jedną kartę w dół w talii.
3. Znajdź jokera B i przesuń go o dwie karty w dół.
4. Zamień miejscami karty leżące między obydwoma jokerami a końcami talii (pamiętaj, aby nie zmieniać kolejności ułożenia kart pomiędzy jokerami).
5. Sprawdź kartę znajdującą się na spodzie talii. Zamień ją na liczbę z przedziału 1 do 53 zgodnie z kolejnością kolorów: trefl, karo, kier i pik. As odpowiada liczbie 1, 2 odpowiada liczbie 2 itd. Dla karo do wartości figury dodajemy 13, dla kier 26, dla pików 39 (do treflów nie dodajemy nic). Każdy z jokerów odpowiada liczbie 53.
6. Odlicz od góry taką liczbę kart, jakiej odpowiada karta na dole talii. Następnie zamień te karty miejscami z pozostałymi kartami, nie zmieniając pozycji karty na spodzie talii. Jeżeli na spodzie talii znajduje się joker, ułożenie talii nie zmieni się.
7. Sprawdź górną kartę i oblicz jej wartość tak jak w pkt. 5. Odlicz tyle kart, ile wynosi wartość wierzchniej karty. Zapisz lub zapamiętaj jaka karta leżała za kartą na której poprzestałeś liczyć.
8. Oblicz wartość tej karty uznając, że trefle i kiery mają wartości od 1 do 13, natomiast kara i piki mają wartości od 14 do 26 (postępujemy w ten sposób dlatego, że potrzebujemy do szyfrowania wartości od 1 do 26). Jest to pierwsza wartość strumienia klucza.
9. Jeżeli chcesz wygenerować kolejną wartość strumienia klucza do zaszyfrowania kolejnej litery tekstu jawnego wróć do punktu 2 z obecnym stanem talii.

Przy punkcie 7. i 8. ułożenie talii nie zmienia się.

Przykład

Ze względów praktycznych w przykładzie użytych jest tylko 12 kart (od Asa do 10 trefl oraz 2 jokery).

1. Ułożenie początkowe to: 3, 1(As), 2, 4, A, 5, 7, 6, 8, B, 9, 10.
2. Przesunięcie jokera A o jedną kartę w dół. Talia: 3,1,2,4,5,A,7,6,8,B,9,10.
3. Przesunięcie jokera B o dwie karty w dół. Talia: 3,1,2,4,5,A,7,6,8,9,10,B.
4. Przełożenie pierwsze. Zamieniamy miejscami karty leżące między jokerami a końcami talii. Talia: A,7,6,8,9,10,B,3,1,2,4,5.
5. Sprawdzamy kartę od dołu. Jej wartość to 5 (figura daje 5, kolor daje 0).
6. Przełożenie drugie. Odliczamy od góry 5 karty i zamieniamy obie części miejscami nie zmieniając położenia spodniej karty. Talia: 10,B,3,1,2,4,A,7,6,8,9,5.
7. Wygenerowanie pierwszej wartości strumienia klucza. Wierzchnia karta to 10, 11 kartą jest 9.
8. Obliczamy wartość tej karty (pamiętaj- trefle i kiery mają wartości od 1 do 13, a kara i piki od 14 do 26). Pierwsza wartość strumienia klucza to 9.
9. Jeżeli potrzebujesz kolejnych wartości, wróć do pkt. 2 z obecnym ułożeniem talii.

Dobieranie klucza

Najtrudniejszą częścią całej operacji jest ułożenie talii w pozycji początkowej, a dokładniej ustalenie tej pozycji, czyli klucza. Można oczywiście użyć zupełnie losowego klucza i jest to wyjście najbezpieczniejsze, jednak najtrudniejsze do wykonania. Autor przedstawia metodę na ułożenie talii przy pomocy klucza. Należy ułożyć talię według starszeństwa (na końcu Joker A i B), a następnie wykonywać kolejne kroki jak przy generowaniu strumienia, z tym, że zamiast pkt. 7 wykonaj pkt. 6 biorąc jako liczbę kart do odliczenia wartości kolejnych liter hasła. Jeżeli kluczem jest słowo „Tajne”, to pkt. 6 powtórzymy dwukrotnie – raz normalnie, i drugi raz nie używając dolnej karty, a wartości 20 (litera T). Przy generowaniu kolejnej wartości strumienia użyjemy liczby 1 (litera A), kolejnym 10 (litera J) i tak dalej. Kartę na spodzie talii należy zostawić w niezmienionej pozycji.

Bezpieczeństwo

Do tej pory nie znaleziono poważnych dziur w generatorze strumienia Solitaire’a. Jednak ze względu na to, że szyfr opiera się na dodawaniu i odejmowaniu modulo, nie wolno używać tego samego klucza do szyfrowania dwóch wiadomości.

Przykładowe wyniki

Generowanie strumienia klucza

• Ustawienie początkowe: karty według starszeństwa – od najsłabszych do najsilniejszych, po kolei: trefle, kiery, karo i piki. Początkowe wyniki: 4 49 10 (53) 24 8 51 44 6 4 33. Liczby 53 nie używamy przy szyfrowaniu- jest ona tu zapisana tylko dla jasności.
• Ustawienie początkowe: karty odwrotnie niż w poprzednim przykładzie, karty od króli do asów, po kolei: piki, karo, kiery i trefle. Początkowe wyniki: 4, 2, 17, 9, 24, 19, 4, 16, 7.

Szyfrowanie

• Tekst jawny: Ala ma kota. Strumień klucza: 17 11 5 4 9 1 21 14 5. Szyfrogram: Rwf qj ljhf.
• Tekst jawny: Solitaire. Strumień klucza: 1, 1, 2, 3, 5, 8, 13, 21, 8. Szyfrogram: Tpnlyivmm.

Bibliografia

• Opis szyfru na stronie autora (ang.)
• Problemy z szyfrem Solitaire (ang.)