Cryptonomicon

Dodatek Algorytm szyfrowania Solitaire

W powieści Neala Stephensona „Cryptonomicon”, bohater Enoch Root opisuje drugiemu z bohaterów — Randy'emu Waterhouse'owi system szyfrowania o kryptonimie „Pontifex”, a później ujawnia, że kroki tego algorytmu są przystosowane do wykonywania za pomocą talii kart. Ci dwaj bohaterowie wymieniają między sobą kilka zaszyfrowanych w ten sposób wiadomości. System ów nazywa się Solitaire (w powieści zaś nosi kryptonim „Pontifex”, aby przedwcześnie nie zdradzić, że używa się do niego kart do gry); zaprojektowałem go, żeby rozsiani po świecie agenci mogli się bezpiecznie komunikować, nie zdając się przy tym na elektronikę i nie nosząc przy sobie podejrzanych instrumentów. Agent może zostać pozbawiony dostępu do komputera bądź aresztowany w razie znalezienia przy nim jakichś przyrządów do szyfrowania. Ale talia kart — cóż w niej złego?

Solitaire opiera swe bezpieczeństwo na losowości zawartej w przetasowanej talii kart. Manipulując tą talią, nadawca może wygenerować ciąg „losowych” liter, który następnie zsumuje ze swoją wiadomością. Można to oczywiście zaimplementować na komputerze, ale algorytm został zaprojektowany specjalnie do szyfrowania „na piechotę”.

Może ta technologia nie wydaje się zbyt zaawansowana i nowoczesna, jednakże jest z pewnością aktualna pod względem bezpieczeństwa. Zaprojektowałem Solitaire'a tak, by oparł się nawet atakom zasobnych wojskowych przeciwników, wyposażonych w największe komputery i najlepszych kryptoanalityków. Oczywiście nie gwarantuję, że ktoś nie znajdzie sprytnego sposobu na złamanie Solitaire'a (sprawdzajcie więc aktualności na mojej stronie WWW), z pewnością jednak jest on lepszy od wszystkich algorytmów szyfrowania za pomocą papieru i ołówka, jakie kiedykolwiek spotkałem.

Jednak nie jest szybki. Szyfrowanie lub deszyfrowanie dość długiego komunikatu może nam zabrać nawet cały wieczór. David Kahn w swej książce „Kahn on Codes” opisuje prawdziwy „papierowy” szyfr używany przez sowieckiego szpiega. Ów algorytm jest mniej więcej tak samo czasochłonny jak Solitaire.

Solitaire to szyfr ciągowy ze sprzężeniem zwrotnym na wyjściu. Czasem nazywa się to także generatorem kluczy (key generator, KG). Idea polega na generowaniu ciągu, zwanego ciągiem kluczowym, złożonego z liczb pomiędzy 1 i 26. Aby zaszyfrować wiadomość, generujemy tyle znaków ciągu kluczowego, ile liczy otwarty tekst. Następnie kolejne liczby ciągu dodajemy modulo 26 do kolejnych liter tekstu otwartego, tworząc tekst zaszyfrowany. Aby go odszyfrować, od każdej litery tekstu należy odjąć modulo 26 literę ciągu kluczowego.

Przykładowo: zaszyfrujemy pierwszą wiadomość w Solitaire wspomnianą w powieści Stephensona: DO NOT USE PC. (NIE UŻYWAJ KOMPUTERA)

1. Dzielimy tekst otwarty na grupy po pięć znaków (nic w tym magicznego ani szczególnego; to po prostu tradycja). Ostatnią piątkę dopełniamy znakiem X. Tekst otwarty wygląda więc tak: DONOT USEPC

2. Za pomocą Solitaire'a generujemy dziesięć znaków ciągu kluczowego (szczegóły poniżej).

Załóżmy, że są to: KDWUP ONOWT

3. Zamieniamy litery tekstu otwartego na cyfry: A = 1, B = 2 itd. 4151415 20 2119 51613

4. To samo czynimy z ciągiem kluczowym: 11 4 23 2116 15 14 15 23 20

5. Dodajemy kolejno liczby ciągu kluczowego do liczb tekstu otwartego, modulo 26 (modulo znaczy, że jeśli suma wynosi więcej niż 26, odejmujemy od niej 26). Na przykład: 1 + 1 = 2,26 + 1 = 26 i 27 — 26 = 1, a więc 26 + 1 = 1.

151911101010 7 2013 23

6. Zamieniamy liczby z powrotem na litery OSKJJJGTMV

Jeśli jesteś dobry w te klocki, możesz nauczyć się dodawać litery w pamięci i po prostu zsumować litery z punktów 1 i 2. Wymaga to tylko nieco ćwiczeń. Łatwo zapamiętać, że A + A = B. Trochę trudniej, że T + Q = K.

Zgodnie z koncepcją odbiorca wiadomości ma wygenerować identyczny ciąg kluczowy, a następnie odjąć litery ciągu kluczowego od liter tekstu zaszyfrowanego.

1. Bierzemy tekst zaszyfrowany i wypisujemy go w grupach po pięć znaków. (Powinien już być w tej formie): OSKJJJGTMV

2. Przy użyciu Solitaire'a generujemy dziesięć znaków ciągu kluczowego. Jeśli klucz odbiorcy jest taki sam jak nadawcy, obaj powinni otrzymać takie same: KDWUP ONOWT

3. Zamieniamy tekst zaszyfrowany na liczby: 151911101010 7 2013 23

4. Podobnie — ciąg kluczowy: 114 23 2116151415 23 20

5. Modulo 26 odejmujemy liczby ciągu kluczowego od liczb zaszyfrowanego tekstu. Na przykład: 22 — 1 = 20, 1 — 22 = 5. (To łatwe. Jeśli pierwsza liczba jest mniejsza od drugiej, przed odejmowaniem dodajemy do niej 26, np.: 1 — 22 =? staje się 27 — 22 = 5)

4 15 14 15 20 2119 5 16 13

6. Zamieniamy liczby z powrotem na litery: DONOT USEPC

Deszyfrowanie przebiega tak samo jak szyfrowanie, tyle że ciąg kluczowy odejmujemy od wiadomości.

Oto istota Solitaire'a. Powyższe opisy szyfrowania i deszyfrowania dotyczą wszystkich szyfrów ciągowych ze sprzężeniem zwrotnym na wyjściu. Ten rozdział wyjaśni, jak działa Solitaire.

Solitaire generuje ciąg kluczowy za pomocą talii kart. O 54-kartowej talii (z dżokerami) możemy myśleć jak o 54-elementowej permutacji. Możliwych ustawień takiej talii jest 54! (54 silnia) czyli 2,31 x 10⁷¹. Co więcej, talia zawiera 52 karty (pomijając dżokery), a alfabet angielski ma 26 liter. Ten zbieg okoliczności jest zbyt ładny, by go nie wykorzystać.

Talia do Solitaire'a musi mieć 52 karty i dwa dżokery. Dżokery muszą się w jakiś sposób różnić. (To często się zdarza: w talii, którą mam przed sobą, dżokery mają gwiazdki, jeden dużą, drugi mniejszą). Nazywamy jednego z dżokerów A, drugiego B. Na ogół dżokery mają taki sam element graficzny, na jednym większy, na drugim mniejszy. Oznaczmy literą B dżokera „bardziej dużego”. Jeśli to ułatwi sprawę, możesz na dżoke-rach napisać A i B, ale pamiętaj, że jeśli zostaniesz złapany, będziesz się musiał tajnej policji z tego wytłumaczyć.

Aby rozpocząć, weź folię w rękę, koszulkami do dołu. Potem ustaw ją w porządku startowym, zwanym kluczem (klucz omówię nieco później, ale to co innego niż ciąg kluczowy). Teraz możesz wygenerować ciąg kluczowy złożony z liter.

Oto sedno Solitaire'a:

1. Znajdź dżokera A. Przesuń go o jedną kartę w dół (zamień miejscami z kartą bezpośrednio pod nim). Jeśli jest ostatnią kartą w talii, wsuń go tuż pod pierwszą kartę z góry.

2. Znajdź dżokera B. Przesuń go o dwie karty w dół. Jeśli jest ostatnią kartą w talii, wsuń go tuż pod drugą kartę z góry. (Po prostu zauważ, że talia jest zapętlona… teraz już rozumiesz?).

Istotne jest wykonanie tych kroków właśnie w takiej kolejności. Jest pokusa, aby trochę ułatwić sobie zadanie i przesuwać dżokery zaraz, kiedy je znajdziesz. Nie ma sprawy, chyba że znajdą się one bardzo blisko siebie.

Jeżeli zatem talia przed pierwszym krokiem wygląda tak: 3AB89

po drugim kroku powinna wyglądać następująco: 3A8B9

Jeśli masz jakieś wątpliwości, pamiętaj, aby najpierw przestawiać dżokera A, a potem B. I uważaj, kiedy któryś z nich znajdzie się na końcu talii.

3. Wykonaj podwójne przełożenie. To znaczy, zamień karty powyżej pierwszego dżokera z kartami poniżej drugiego. Jeśli przedtem talia wyglądała tak: 246B4871A39

po tej czynności powinna wyglądać tak: 39B4871A246

Określenia „pierwszy” i „drugi” odnoszą się do dowolnego z dżokerów, najbliższego początku i końca talii. W tym kroku nie zwracamy uwagi na oznaczenia „A” i „B”.

Pamiętaj, że dżokery i karty pomiędzy nimi nie ruszają się: to pozostałe części talii poruszają się wokół nich. Łatwo to zrobić rękoma. Jeśli w którejś z części talii nie ma żadnych kart (tzn. dżokery przylegają do siebie, bądź też jeden z nich znajduje się na początku lub na końcu), po prostu traktujemy tę część jako pustą i przekładamy „w myślach”.

4. Przełóż talię w odliczonym miejscu. Popatrz na ostatnią kartę. Zamień ją na liczbę od 1 do 53. (Stosujemy tutaj brydżową kolejność kolorów: trefle, kara, kiery, piki. Jeśli karta jest treflem, ma taką wartość, na jaką wskazuje, jeśli karem — wartość plus 13, jeśli kierem — wartość plus 26, a jeśli pikiem, wartość plus 39. Oba dżokery są warte 53). Odlicz taką ilość kart od góry talii. (Ja na ogół liczę do 13 i potem jeszcze raz, i jeszcze raz, jeśli trzeba; to łatwiejsze niż liczenie dalej). Przełóż po karcie, do której odliczyłeś, zostawiając ostatnią kartę na końcu talii. Jeśli przedtem talia wyglądała tak:

7…karty… 4 5… karty… 8 9

a dziewiąta karta to 4, po przełożeniu powinieneś otrzymać: 5…karty… 8 7… karty… 4 9

Ostatnia karta zostaje na swoim miejscu, aby ten krok był odwracalny. Jest to istotne przy matematycznej analizie bezpieczeństwa szyfru.

5. Znajdź kartę wyjściową. Popatrz na wierzchnią kartę. Zamień ją na liczbę od 1 do 53, w ten sam sposób jak wyżej. Odlicz tyleż kart (traktując wierzchnią jako numer 1). Zapisz na kartce kartę następną po ostatniej odliczonej (a jeśli trafiłeś na dżokera, niczego nie zapisuj i wróć do kroku 1). Jest to pierwsza karta wyjściowa. Zauważ, że ta operacja w żaden sposób nie modyfikuje talii.

6. Zamień ją na liczbę, korzystając z brydżowej kolejności kolorów. Od najmniejszego do największego mamy trefle, kara, kiery, piki. A zatem: A* do K* to 1 do 13, Ał do K* to 14 do 26, A¥ do K¥ to 1 do 13, a AA do K* to 14 do 26.

Oto i Solitaire. Możesz w ten sposób wytworzyć dowolnej długości ciąg kluczowy.

Zdaję sobie sprawę, że w różnych regionach świata używa się różnych talii kart. W zasadzie nie ma znaczenia, jakiego porządku kolorów używamy ani w jaki sposób zamieniamy karty na liczby. Ma znaczenie jedynie, aby nadawca i odbiorca wiadomości uzgodnili ze sobą te reguły. Jeśli tego nie zrobią, nie będą mogli się porozumieć.

Solitaire jest bezpieczny tylko na tyle, na ile bezpieczny jest jego klucz. To znaczy, najłatwiejszym sposobem złamania szyfru jest ustalenie, jakiego klucza używają porozumiewający się. Oto pewne propozycje sposobów wymiany kluczy.

1. Przetasuj talię. Losowy klucz jest najlepszy. Jedna ze stron może potasować talię i potem stworzyć drugą, identyczną. Jedna wędruje do nadawcy, druga do odbiorcy. Większość ludzi nie umie dobrze tasować, dlatego należy powtórzyć tasowanie przynajmniej dziesięć razy i starać się korzystać z używanej talii, a nie nowej, wprost z pudełka. Pamiętajmy, aby mieć zapasową talię ułożoną w klucz, w przeciwnym razie, jeśli pomylimy się, nigdy nie zdołamy odszyfrować wiadomości. Miejmy także na uwadze, że klucz, dopóki istnieje, stanowi zagrożenie — tajna policja może znaleźć talię i spisać sobie jej kolejność.

2. Skorzystaj z zapisu brydżowego. Opis rąk poszczególnych graczy, spotykany w gazecie lub książce o brydżu, stanowi klucz mniej więcej 95-bitowy. Jeśli strony mogą uzgodnić sposób zamiany takiego opisu w porządek talii oraz sposób ustawienia w niej dżokerów (na przykład po dwóch pierwszych kartach wspomnianych w opisie partii), to może zadziałać. Ale uwaga: tajna policja może znaleźć twoją kolumnę brydżową i skopiować porządek kart. Możesz ustalić jakąś stałą konwencję wybierania kolumny brydżowej, na przykład „używamy kolumny brydżowej z twojej lokalnej gazety, z dnia, w którym szyfrujesz wiadomość” albo coś w tym stylu. Albo listę słów kluczowych, za pomocą których przeszukujesz witrynę internetową „New York Timesa”, a potem korzystasz z kolumny brydżowej z dnia, w którym ukazał się pierwszy ze znalezionych artykułów. Jeśli te słowa kluczowe zostaną przechwycone lub znalezione przez policję, będą wyglądały jak hasło. Wymyśl swoją własną konwencję; pamiętaj, że tajna policja również czyta książki Neala Stephensona.

3. Uporządkuj talię na podstawie hasła. Ta metoda korzysta z algorytmu Solitaire'a do początkowego uporządkowania talii. Nadawca i odbiorca uzgadniają hasto (na przykład: „TAJNY KLUCZ”). Zaczynamy od talii ułożonej w stały sposób, kolorami jak w brydżu, a w obrębie koloru od najmniejszej do największej karty. Wykonujemy operację Solitaire^ jak wyżej, ale zamiast kroku nr 5 kolejny przekładamy w odliczonym miejscu, na podstawie pierwszego znaku hasła (w tym przypadku T, czyli 20). Pamiętajmy, żeby — tak jak przedtem — odliczone karty włożyć tuż nad ostatnią kartę w talii. Powtarzamy operację dla kolejnego znaku. Dwa ostatnie znaki hasła ustalają położenie dżokerów. Należy jednak pamiętać, że w zwykłym angielskim na jeden znak przypada tylko około 1,4 bita losowości. Aby taki algorytm był bezpieczny, hasto musi mieć przynajmniej 80 znaków. Zalecałbym co najmniej 120. Przykro mi, ale krótszy klucz po prostu nie gwarantuje bezpieczeństwa.

Oto przykładowe dane, na których możesz poćwiczyć Solitaire'a.

Przykład 1: Zaczynamy od talii nieustawionej w klucz, czyli: A* do K*, Afdo K›, AV do KV, AAdo KA, dżoker A, dżoker B. Można to przedstawić jako 1-52, A,B. Pierwszych dziesięć liczb to: 4 49 10 (53) 24 8 51 44 6 33

53 oczywiście pomijamy. Zamieściłem je na liście w celu ilustracji. Jeśli otwarty tekst to: AAAAAAAAAA

to zaszyfrowany wygląda tak:EXKYIZSGEH

Przykład 2: Korzystając z trzeciej metody ustawiania talii w klucz, przy kluczu „FOO”, pierwszych piętnaście liczb ciągu kluczowego to: 8 19 7 25 20 (53) 9 8 22 32 43 5 26 17 (53) 38 48 Jeśli tekst otwarty to same A, zaszyfrowany brzmi: ITHZU JIWGR FARMW

Przykład 3: Korzystając z trzeciej metody i klucza „CRYPTONOMICON”, tekst „SOLITAIRE” szyfruje się na: KIRAKSFJAN

Oczywiście można użyć dłuższego klucza. Te przykłady służą wyłącznie celom testowym. Na mojej stronie internetowej znajdziesz więcej przykładów, możesz też stworzyć własne przy użyciu zamieszczonego w powieści skryptu w języku Perl.

Solitaire jest zaprojektowany tak, żeby zapewniał bezpieczeństwo, nawet jeśli wróg zna zasadę działania algorytmu. Zakładam, że „Cryptonomicon” będzie bestsellerem — do kupienia wszędzie. Zakładam, że Agencja Bezpieczeństwa Narodowego i wszyscy inni zbadają algorytm i będą o nim pamiętać. Zakładam, że jedyną tajemnicą jest klucz.

Dlatego właśnie zachowanie tej tajemnicy jest tak istotne. Jeśli trzymasz w bezpiecznym miejscu talię kart, przyjmij, że wrogowi spodoba się pomysł, iż używasz Solitaire'a. Jeśli w sejfie masz wycinek z kolumny brydżowej, parę osób pewnie uniesie brwi. A jeśli którakolwiek z inwigilowanych grup rzeczywiście używa Solitaire'a, spodziewaj się, że tajna policja może mieć bazę danych z wszystkimi kolumnami brydżowymi, której używa przy próbach łamania szyfru. Solitaire zachowuje siłę, nawet jeśli wróg wie, że go używasz; talia zwykłych kart i tak jest mniej podejrzana niż program do szyfrowania na twoim komputerze, ale sam algorytm nie zastąpi odrobiny cwaniactwa.

Pierwszą zasadą użycia dowolnego szyfru ciągowego ze sprzężeniem na wyjściu, jest: nigdy nie należy używać tego samego klucza do szyfrowania dwóch różnych wiadomości. Powtórz za mną: NIGDY NIE NALEŻY UŻYWAĆ TEGO SAMEGO KLUCZA DO SZYFROWANIA DWÓCH RÓŻNYCH WIADOMOŚCI. Jeśli popełnisz ten błąd, całkiem niweczysz bezpieczeństwo systemu. Oto dlaczego: jeśli masz dwa różne teksty zaszyfrowane, A + K oraz B + K i odejmiesz jeden z nich od drugiego, otrzymasz: (A + K)-(B + K) = A + K-B-K-A-B czyli dwa skombinowane ze sobą otwarte teksty. Bardzo łatwo to złamać. Zaufaj mi: ty być może nie umiałbyś ustalić A i B, mając A — B, ale zawodowy kryptoanalityk to potrafi. Jest to kluczowa kwestia: nigdy nie szyfrować dwóch wiadomości tym samym kluczem.

Staraj się, by wiadomości były krótkie. Algorytm jest przystosowany do niedługich tekstów, tak do kilku tysięcy znaków. Jeżeli musisz zaszyfrować powieść o 100 tysiącach słów, skorzystaj z jakiegoś programu komputerowego. Używaj skrótów i wyrażeń slangowych. Nie rozgaduj się.

Dla maksymalnego bezpieczeństwa naucz się wykonywać wszystkie działania w pamięci. Gdy załomocze do twoich drzwi tajna policja, po prostu spokojnie przetasuj karty (ale nie rzucaj ich w powietrze; zdziwiłbyś się, widząc, jak wiele z uporządkowania talii pozostaje po rozrzuceniu kart do gry w świnkę). Pamiętaj, aby roztasować talię zapasową, jeżeli taką masz.

Jest ich mnóstwo, ale są o wiele za skomplikowane, by je tutaj przytaczać. Patrz: http: //www.counterpane.com lub napisz do firmy Counterpane Systems, 1711 North Ave. #16, Oak Park, Illinois 60302.

Na dobry początek polecam własną książkę „Applied Cryptography”, wyd. John Wi-ley Sons, 1996. Potem — „The Codebreakers” Davida Kahna (wyd. Scribner, 1996). Poza tym istnieje sporo książek na temat kryptografii komputerowej i jeszcze kilka na temat „ręcznej”. Możesz także zaprenumerować mój darmowy biuletyn e-mailowy, pod adresem http://www.counterpane.com/cryptogram.html lub wysyłając pustą wiadomość na adres crypto-gram-subscriber@chaparraltree.com. Ta dziedzina jest bardzo ciekawa. Powodzenia!

Serdecznie dziękuję wszystkim osobom, które wspomogły mnie w trakcie pracy nad przekładem, w szczególności zaś subskrybentom grupy dyskusyjne pl.hum.tlumaczenia oraz Alexowi.

Wojciech M. Próchniewicz

[*]

[†] .

[‡]

[§]

[**]

[††]

[‡‡]

[§§]

[***]

[†††]

[‡‡‡]

[§§§]

[****]

[††††]

[‡‡‡‡]

[§§§§]

[*****]

[†††††]

[‡‡‡‡‡]

[§§§§§]

[******]

[††††††]

[‡‡‡‡‡‡]

[§§§§§§]

[*******]

[†††††††]

[‡‡‡‡‡‡‡]

[§§§§§§§]

[********]

[††††††††]

[‡‡‡‡‡‡‡‡]

[§§§§§§§§]

[*********]

[†††††††††]

[‡‡‡‡‡‡‡‡‡]

[§§§§§§§§§]

[**********]

[††††††††††]

[‡‡‡‡‡‡‡‡‡‡]

[§§§§§§§§§§]

[***********]

[†††††††††††]

[‡‡‡‡‡‡‡‡‡‡‡]

[§§§§§§§§§§§]

[************]

[††††††††††††]

[‡‡‡‡‡‡‡‡‡‡‡‡]

[§§§§§§§§§§§§]

[*************]

[†††††††††††††]

[‡‡‡‡‡‡‡‡‡‡‡‡‡] .

[§§§§§§§§§§§§§]

[**************]