Szyfr Solitaire

Solitaire Cipher

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

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.

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.)