strona główna     -     okładka numeru     -     spis treści     -     archiwum fahrenheita     -     napisz do nas
 
Adam Cebula Para, nauka i obok
<<<strona 21>>>

 

Wokół szyfrów i takich innych

 

 

Jeszcze całkiem niedawno szyfrowanie wiadomości było rzeczą wyjątkową, domeną szpiegów, dyplomatów, przestępców. Normalny człowiek nawet bał się, że cokolwiek może wyglądać na zaszyfrowaną wiadomość. Dziś, w epoce komputerów, posługiwanie się narzędziami szyfrującymi i hasłami to niemal codzienność. Ludzie, którzy używają do przesyłania wiadomości jawnego tekstu nierzadko narażają nie tylko siebie, ale i innych. Na własnej skórze kiedyś się przekonałem, że szyfrowanie stało się obowiązkiem, gdy pani administratorka sieci komputerowych wyłączyła mi ftp i nakazała się posługiwać sftp. Dziś już lekko nie ma, na każdym zakręcie kabla czyhają crakerzy, włamywacze i inne złe stwory.

Wokół szyfrowania narosło wiele mitów i nieporozumień. Może warto zacząć od tego, że algorytmy szyfrujące nie są diabelnie zawiłe. W książkach o programowaniu zazwyczaj poświęca się im jakiś rozdział, przy czym bynajmniej niewiele miejsca na wyjaśnienie, jak to działa, sporo za to, jak napisać.

Przejdźmy do konkretu. Najstarszym praktycznie stosowanym systemem szyfrowania wiadomości był zapewne szyfr Juliusza Cezara. Był to zmodyfikowany prosty kod podstawieniowy. Coś takiego (nie kod Cezara) samemu można wydumać w pięć minut i będzie to dość skuteczne. Zwyczajnie zastępujemy jedną literę inną. W tym wykonaniu klucz będzie miał postać tablicy, w której zapisaliśmy, w jaki sposób znaki pisarskie zostały pozamieniane. Metoda świetna, ale mało dowcipna. Poza tym, gdy wróg wyśle na przykład szpiega za naszym dyplomatą, który ma wysyłać tajne informacje, może ukraść tablicę podstawień.

Można prosto wymyślić metodę tworzenia takiej tablicy. Zapisujemy litery w kółeczko a następnie nowe litery także w kółeczko, ale przesunięte, na przykład, o trzy. Tak więc, gdy pominiemy ogonki, "a" odpowiada "d", "b" to "e" i tak dalej. Ostatnie trzy litery alfabetu zostaną zastąpione przez "a", "b", "c". Nasz dyplomata musi więc umieć tylko abecadło i zapamiętać jedną liczbę: przesunięcie. Tak właśnie ma wyglądać dobra metoda szyfrowania. Powinna być prosta, szybka i nie wymagać skomplikowanych kluczy, które można by ukraść. Wymyślił to podobno sam Juliusz Cezar

Niestety, metoda ta ma zasadniczą wadę, która ją dyskwalifikuje w dzisiejszych czasach. Bardzo łatwo ją złamać metodą analizy statystycznej częstości występowania liter.

Zasadniczą sprawą dla łamacza szyfru jest bowiem mieć jakieś pojęcie o systemie, z którym toczy bój. Tych zaś ostatnio namnożyło tak wiele, że naprawdę przejęcie przekazu to może być dopiero początek zabawy.

Tak czy owak, w dłuższym tekście pisanym po polsku, bez trudu wyłapiemy literkę "p", co pozwoli nam na określenie przesunięcia i system zawali się bez oporu. Akurat w tym przypadku nie potrzeba zresztą analizy, mamy tylko tyle możliwości, ile jest znaków do zakodowania, czyli kilkadziesiąt (łącznie z "małpami" i gwiazdkami).

Rozwinięciem takiego systemu kodowania są tak zwane przekształcenia afiniczne. Do przesuwania o stałą wartość dodajemy operację mnożenia. Literkę o numerze P zastępujemy literką o numerze C w sposób następujący:

 

C=P*a+b (mod N).

 

Zapis robi się skomplikowany. Chodzi o to, że mnożymy literę P przez pewną liczbę a, dodajemy do wyniku b, następnie dzielimy z resztą wynik przez N (czyli liczbę znaków) i zapisujemy resztę, czyli C. Liczba a nie może być byle jak wybrana, bo inaczej nie da się odwrócić operacji i w jednoznaczny sposób odkodować wiadomości. Liczby a i N nie mogą mieć wspólnych podzielników większych niż 1.

Trzeba odrobinę więcej czasu poświęcić na jeden szczegół. Da się zdefiniować dodawanie, odejmowanie i szereg innych operacji, tak zwanych "modulo". Grają one zasadniczą rolę w wielu metodach szyfrowania i są znakomitym przedmiotem do dywagacji dla matematyków. Operacje modulo można sobie trochę przybliżyć, wyobrażając je sobie jako owijanie linijki nitką, przy czym chodzi o owijanie wzdłuż skali , a nie prostopadle do niej, bo to ostatnie nie miałoby sensu. Jeśli weźmiemy nitkę, której długość jest wynikiem pomnożenia dwu liczb, to mnożenie modulo względem trzeciej liczby znajdziemy, owijając nitką linijkę (bardzo cienką) o długości tej trzeciej liczby (linijka ma długość modulo), koniec nitki wskaże wynik operacji. Zasadniczą różnicą arytmetyki modulo w stosunku do normalnej jest to, że wyniki mieszczą się na skończonym kawałku osi liczbowej, ograniczonej właśnie liczbą, względem której obliczamy wyniki. Inaczej mówiąc, są to operacje "z resztą", przy czym wynikiem jest reszta.

Wiedząc tyle, możemy ruszyć dalej. Odkodowanie informacji jest nieco bardziej skomplikowane. Nie zaprzątając sobie głowy (na razie) podzielnikami, można stworzyć po prostu tablicę liter jawnych i "tajnych", które odpowiadają sobie po przekształceniu . 

Dzięki jednak owej operacji modulo, złamanie kodu z przekształceniem afinicznym nie jest proste. Rzecz możemy przedstawić za pomocą równania:

C=P*x +y (mod N)

 

Jest to banalne, jeśli ktoś miał w szkole, równanie z dwoma niewiadomymi. Szukane niewiadome są właśnie składnikami klucza. Aby się brać za jego rozwiązanie, trzeba co najmniej dwu literek podejrzanych o to, czym są naprawdę. System afiniczny nie jest już "trywialny", czyli mówiąc po ludzku, dramatycznie prosty (zerowotrudny? – przełożenie tego, co matematycy i fizycy pod słówkiem "trywialne" rozumieją, nie jest chyba ... trywialne). Kombinacji liczb będących kluczami jest tu całe mrowie. Jednak uczciwie mówiąc, w dzisiejszych czasach do niczego się nie nadaje, zwłaszcza w codziennej komunikacji ludzi.

Ponieważ jednak nie chcę mówić tylko o komputerowych protokołach, takich, które rozmnożone w milionach jednakowych egzemplarzy, muszą się sprawdzić, pozwolę sobie na wlezienie w maliny. Przyda się wiedza, o której próżno czytać w uczonych rozprawach. Albowiem, o czym dziennikarze nader często zapominają, kryptolodzy zajmują się systemami szyfrowania, które są poddane bardzo ostrym kryteriom. Jeśli te kryteria rozluźnimy, to przekonamy się, że właściwie "jest inaczej". Jest bardzo łatwo wymyślić system, może nie tyle nie do złamania, ale taki, z którym będą zasadnicze kłopoty.

Podstawową wadą afinicznej metody kodowania jest nieodporność na atak sprawdzający statystyczną zawartość liter. W dobie komputerowych programów możemy sobie pozwolić na dramatyczne skomplikowanie algorytmu, zwłaszcza jeśli chcemy używać go bardzo rzadko. Zazwyczaj naprawdę tajnych informacji jest niewiele i nie ma chyba potrzeby przesyłania zakodowanej wielotomowej encyklopedii. Być może taki problem będą mieli niebawem producenci filmów, żeby obronić się przed piratami, ale to osobna sprawa.

Zmodyfikujmy nieco naszą metodę, nie wymyśloną przez Cezara, lecz jeszcze prostszą z tablicą liter odpowiadających sobie, którą nieszczęsny dyplomata musi dobrze chować przed szpiegami. Pomyślmy, co się stanie, gdy powiedzmy feralnej literce "p" w polskim języku i "e" w angielskim przypiszemy wiele znaków, najlepiej liczb. Całkiem eleganckim wyborem może być zestaw dwubajtowy od 0 do 65535. Nie ma to nic wspólnego z kodowaniem UTF8, chodzi tylko o to, że dwa bajty to oszczędny sposób gospodarowania komórkami pamięci. Oczywiście, mając na przykład 512 MB RAM nie musimy się tym martwić, ale powiedzmy, że się martwimy. Każdej literze możemy przypisać co najmniej 2520 kodujących ją liczb. Może to wyglądać tak:

 

a – (12312, 621, 32666, ..., 23, 54321)

b – (202, 32002, 12092, ..., 405, 14013)

c – (128, 10278, 901, ..., 8079, 47331)

(...)

k – (5, 40563, 55771, 13, ..., 889, 2788)

l – (60111, 2, 67, 8776 , ..., 45176, 46771)

m – (52709, 50802, 1001, ..., 50101, 13188)

(...)

o – (87, 507, 37809, ..., 3, 60781, 44).

(...)

t – (307, 50403, 6083, ..., 25, 20701, 151)

(...)

 

Tablicę tę układałem "z ręki", więc może ona wykazywać "ludzkie" cechy, w szczególności może się coś powtórzyć.

Wynik kodowania "Ala ma kota" to na przykład taki ciąg: 12312, 60111, 621, 52709, 32666, 5, 87, 307, 23. Jak widać, literce "a" odpowiadają całkowicie różne liczby w kolejnych miejscach jej wystąpienia.

Co ze statystyczną metodą łamania kodów? Otóż, jeśli nie byliśmy głupi i zbudowaliśmy naszą tablicę z pomocą prawdziwego, czy sztucznego, ale dobrej jakości chaosu, to znaczy na przykład rzucając kostką albo uruchamiając porządny generator liczb pseudolosowych, to dopóki nie zaczną się powtarzać liczby kodujące litery, nie ma co marzyć o jakimkolwiek łamaniu kodu.

Może to, co powiem, jest nieco zawiłe, ale jeśli zaczniemy tak losowy wybrany szereg liczb analizować statystycznie, to nic nam nie wyjdzie. Do momentu, do którego wielokrotnie nie zaczną się powtarzać litery, we wszelkich testach otrzymamy tylko i wyłącznie losowe rozkłady odwzorowujące dokładnie rozkład, który dało nam to coś, za pomocą czego wygenerowaliśmy liczby. Oczywiście jeśli, tak jak w tym przykładzie, wsadziliśmy wszystkie liczby z pewnego zakresu, musi to być rozkład płaski. Możemy się jeszcze zastanowić, jak bardzo nasz system kodowania ewentualnemu deszyfrantowi utrudni życie. Na oko potrzebuje on około 2500 razy więcej tekstu do statystycznej analizy niż w przypadku prostego szyfru podstawieniowego. Wszelako, wychodzimy z milczącego założenia, że wie, co się stało. Co jednak, jeśli szyfr został skonstruowany nieco inaczej, niż na początku założyliśmy, jeśli na przykład literom przypisano niejednakową ilość liczb? Jak widać, dość prawdopodobne, że będzie musiał zaczynać pracę całkowicie po omacku. Tak czy owak, do roboty będzie się mógł zabrać, gdy ilość przechwyconych informacji będzie odpowiadać co najmniej 60 – 90 stron maszynopisu znormalizowanego (na stronie mamy około 1800 znaków). Prawdopodobnie potrzebować będzie więcej. Pojęcia nie mam, jak wielką korespondencję prowadzą różne tajne organizacje, ale wydaje mi się, że jest jej bardzo wiele, jak na trefne wiadomości.

Oczywiście, system jest wyjątkowo nieoszczędny. Aby klucz przekazać, trzeba się wymienić dyskietką, na której zajmie on prawie 1/10 miejsca, pewnie ciut ponad 128 kB. Wsypa pewnie zdarzyłaby się, gdyby ponumerować litery "za koleją" albo w jakiś inny regularny sposób, jeśli jednak będzie to ciąg czy losowy, czy pseudolosowy, to jak się mówi: "zdechł pies". Jedna mała uwaga, możemy także nie podawać sposobu wyboru kolejnych liczb kodujących tę samą literę w wiadomości. Możemy to robić systemowo, ale można przy tak małej bazie danych kazać komputerowi, który odcyfrowuje u adresata wiadomość, przepatrywać całą tablicę.

Lepiej jest to robić systemowo (czyli wg jakiegoś porządku), ale znaczenie z punktu widzenia bezpieczeństwa kodu uzyska to wówczas, gdy tablica liczb zastępujących litery będzie wielokrotnie większa niż nasze przykładowe 65536, gdy w grę zacznie wchodzić czas pracy komputera.

Nim przejdziemy do następnego punktu, jeszcze jedna uwaga: podana metoda jest wyjątkowo głupia, ale jednocześnie prosta i raczej skuteczna. Każdy początkujący programista może zacząć swe ćwiczenia od napisania podobnego programu.

Dość oczywistym pomysłem jest podwójne zakodowanie informacji, w nadziei, że to znacznie utrudni złamanie szyfru. Zobaczmy, co się stanie, gdy złożyć dwie głupie metody do kupy, na przykład przekształcenia afiniczne z metodą podstawieniową.

Jeśli nasza tablica będzie wyglądała jak w przykładzie powyżej, gdzie mamy wiersze zapełnione liczbami odpowiadającymi literom, to jak będzie wyglądała, i czy w ogóle da się skonstruować tablica, która zrealizuje złożenie kodowania przez podstawianie i przekształcenie afiniczne? Sprawę dość łatwo rozwikłać, bowiem wynikiem zastosowania kodu Cezara jest zamiana liter miejscami może więc to wyglądać tak

 

z=a – (12312, 621, 32666, ..., 23, 54321)

a=b – (202, 32002, 12092, ..., 405, 14013)

b=c – (128, 10278, 901, ..., 8079, 47331)

(...)

j=k – (5, 40563, 55771, 13, ..., 889, 2788)

k=l – (60111, 2, 67, 8776 , ..., 45176, 46771)

l=m – (52709, 50802, 1001, ..., 50101, 13188)

(...)

n=o – ( 87, 507, 37809, ..., 3, 60781, 44).

(...)

s=t – (307, 50403, 6083, ..., 25, 20701, 151)

(...)

 

Dość istotne jest spostrzeżenie, że nowa tablica, która zrealizuje od razu przekształcenie afiniczne i podstawienie, będzie się różniła od starej tylko kolejnością wierszy. Wystarczy przesunąć wiersz odpowiadający "a" na koniec, wiersz "b" na miejsce wiersza "a" itd.

Osoba deszfrująca informacje może w ogóle nie wiedzieć o dodatkowej operacji, odtworzy od razu tablicę odpowiadającą złożeniu przekształceń, a my się tylko niepotrzebnie napracujemy. Trzeba więc uważać! Jednak możemy bardzo łatwo łamaczom kodu utrudnić życie. Wystarczy, by przekształcenie afiniczne miało klucz zależny od dnia tygodnia, wówczas tablicy z wtorku będzie odpowiadała prawie taka sama tablica piątkowa, ale z poprzestawianymi wierszami.

Jak wyczytałem w książce Neal’a Kobnitz’a "Wykład z Teorii Liczb i Kryptografii", tak zwane trigramy już praktycznie nie wykazują statystycznych zależności. Digramy jeszcze można tą metodą złamać, lecz trigramów już nie. O co chodzi? Metoda jest o wiele inteligentniejsza od zaproponowanej poprzednio. Kodujemy bowiem nie pojedyncze litery, lecz ich grupy. Digramy czyli grupy dwu liter, trigramy to grupy trzech liter. Możemy im w prosty i oszczędny sposób przypisać liczby. Jeśli mamy w alfabecie 26 liter to mamy 26*26= 676 kombinacji. Numerujemy je, wzorując się na układzie pozycyjnym pisania liczb. Na przykład tak (nie uwzględniając 0) ab =26+2=28, ba=2*26+1=53, cd=3*26+4=82. Tak to będzie wyglądać dla digramów. Dla trigramów na przykład abc=676+(2*26)+3=731. Podobnie jak dla prostego przedstawienia liter alfabetu jako 26 liczb, tu także możemy zastosować przekształcenie afiniczne. Operacja modulo zamienia jedne trigramy na inne i tak bez piętrowych operacji, elegencką metodą kodujemy tekst i pozbywamy się kłopotów z deszyfrowaniem metodami statystycznymi i nie musimy wozić fatalnej tablicy szyfrów, bo znowu wystarczy zapamiętać tylko dwie liczby.

Pewną odmianą wyżej opisanych metod jest zapis macierzowy. Łatwiej to sobie wyobrazić jako geometryczne przekształcenia położenia punktów na płaszczyźnie. Dwójkę liter zastępujemy odpowiadającymi im numerami. Te numery traktujemy jako współrzędne punktu. Następnie, gdy stosujemy prosty szyfr Cezara, przesuwamy go o pewien wektor, który jest naszym kluczem. Wynik przesunięcia traktujemy operacją modulo z liczby liter. Otrzymujemy nowy punkt, który odpowiada nowej parze liczb i równoważnych im liter. Tak mniej więcej wyglądał szyfr Vigenere’a. Dla trigramów możemy się posłużyć przekształceniami w przestrzeni trójwymiarowej.

Wbrew być może skomplikowanemu opisowi, te systemy kodowania ze względu na stosunkowo krótki klucz są łatwe do złamania. Można jednak za ich pomocą wyjaśnić przyczynę zainteresowania liczbami pierwszymi. Jak już wspomniałem, składniki klucza przekształcenia afinicznego nie mogą być byle jakie, bo inaczej może się okazać, że po zakodowaniu jedna litera może być odczytana na kilka sposobów. Liczby pierwsze mają tę cudowną własność, że odpowiednio zastosowane wykluczają takie przypadki. W chwili obecnej przyczyna ich stosowania jest nieco inna, lecz zawsze jej podstawą jest fakt, że potrzebny jest taki składnik kodu, który nie da się porozkładać na iloczyn mniejszych liczb. Taka operacja pozwala operować jakby na kawałku kodu i z reguły dramatycznie upraszcza złamanie systemu.

W chwili obecnej praktycznie nie używa się nie tylko opisanych wyżej, ale w ogóle systemów kodowania symetrycznych. We wszystkich opisanych wyżej systemach do zakodowania i odkodowania potrzebny jest ten sam klucz. Aby zacząć tajną korespondencję, trzeba go najpierw wymienić. To nie zawsze jest możliwe, a zawsze kłopotliwe. Współczesne metody, w tym metoda RSA, najbardziej znana, opiera się o przekształcenia, w których operacja odkodowania wymaga więcej wiadomości niż zakodowanie. To pozwala stosować tak zwane klucze publiczne. Jeśli chcę, by korespondowano ze mną, publikuję (np. umieszczam na stronie www) klucz publiczny. Osoba, która chce wysłać do mnie zaszyfrowaną wiadomość, używa go i oczywiście algorytmu, który jest powszechnie znany (albo udostępniony na stronie). Jednak ten algorytm plus klucz nie wystarczą do odszyfrowania wiadomości. Tak więc możemy zacząć tajną korespondencję, w ogóle się nie spotykając. Oczywiście osoba, która chce, abym ja jej odpowiadał w tajny sposób, może umieścić swój klucz w dostępnym miejscu i w ten sposób obustronna wymiana informacji będzie zaszyfrowana mimo, że korespondenci nigdy się nie spotkali.

Niestety, nie mam dobrego pomysłu na wytłumaczenie, jak to działa. Można zerknąć do wymienionej już kryptografii. Jednak ciekawe są pewne techniczne szczegóły. Aby wygenerować klucz, zaczynamy od dwu liczb pierwszych odpowiednio dużych, powiedzmy a i b. Następnie obliczamy ich iloczyn c=a*b, a potem d=(a-1)*(b-1)=c+1-a–b. Ta procedura pozwoli nam wybrać losowo pewną liczbę e zawartą pomiędzy 1 (zapewne znacznie większą od 1) i d, która nie ma z nią wspólnych podzielników. W kolejnym kroku znajduje się liczbę f, która jest odwrotnością do e modulo d. Jak – to osobna sprawa. Umiemy znajdować odwrotność liczby w arytmetyce modulo. Szyfrowanie polega na tym, że bierzemy blok literowy i zamieniamy na liczbę, tak jak w trigramach,czy digramach, otrzymamy jakąś liczbę "jawną " J. Podnosimy J do potęgi e modulo c. Otrzymujemy tajny wynik T. Żeby otrzymać jawny, podnosimy T do potęgi f modulo c. Klucz publiczny to liczby c i e. Liczbę f zachowujemy w tajemnicy.

Nie należy tego traktować jak wytłumaczenia działania szyfru RSA, natomiast możemy zwrócić uwagę, na czym polega siła szyfru. Mianowicie, do publicznej wiadomości zostaje podana wskazówka, jak powstaje liczba f stosowana do rozszyfrowania, to liczba c, iloczyn dwu liczb pierwszych, z których wystartowaliśmy. Jednak, jeśli jest on dostatecznie duży, operacja znalezienia tych liczb, a i b, jest bardzo czasochłonna, jeśli tylko liczby są dość duże.

Tak działa współczesna kryptografia: owszem, złamanie szyfru jest możliwe, lecz dobieramy parametry tak, by trwało to dostatecznie długo, by wynik ewentualnemu przeciwnikowi do niczego się nie przydał. Sednem są tu operacje, które okazują się niesymetryczne, w jedną stronę idzie gładko (stosunkowo łatwo mnoży się nawet bardzo długie liczby), w drugą bardzo trudno.

Znajdowanie takich niesymetrycznych procedur nie jest łatwe i zazwyczaj gdy się pojawia nowa, jest to swego rodzaju sensacja. Przykładem kolejnej niesymetrycznej operacji jest podnoszenie do potęgi modulo i znajdowanie logarytmu modulo. W normalnej arytmetyce oczywiście także łatwiej jest wymnożyć liczbę przez siebie, niż znaleźć potęgę, do której trzeba podnieść podstawę logarytmu, by otrzymać logarytmowaną liczbę. Jednak dramatyczna różnica wystąpi wówczas, gdy "popsujemy" definicję logarytmu.

Jak widać, kryptografia jest po trosze dziedziną matematyczną czerpiącą z najbardziej szlachetnej, tworzonej dla samego poznania teorii liczb, po trosze dziedziną inżynierską. Gdy po raz pierwszy w starym Fahrenheicie pisałem o szyfrowaniu, procesory miały za jakiś czas osiągnąć 1 GHz prędkości. Dziś niebawem sięgną 10 GHz. To, co do niedawna było nie do złamania, niebawem okaże się za słabym szyfrem.

Jednak natura zapewniła szyfrującym olbrzymią przewagę nad łamiącymi kody. Łatwo pokazać to na przykładzie "durnych", prostych szyfrów. Jeszcze w czasach PRL w "Młody Techniku" były w ramach kursu programowania prezentowane proste programy szyfrujące. Wbrew pozorom temu, że miały charakter szkoleniowy, bynajmniej nie były one łatwe do złamania, w każdym razie wielokrotnie trudniejsze od kodu Cezara. Działanie takich maszynek opiera się o tak zwane generatory liczb pseudolosowych. Mamy pewne doskonałe procedury, które z jednej strony potrafią znakomicie naśladować całkowicie przypadkową naturę, z drugiej są doskonale uporządkowane. Jedną z najładniej dostosowanych do techniki jest tak zwany generator szumu z rejestrem przesuwnym. Inny algorytm zawiera dzielenie modulo z zastosowaniem "magicznych" liczb. Dokładniejsze przepisy można znaleźć w starych numerach F. Obrazowym przykładem jest chyba ów generator z rejestrem przesuwnym. Działa to tak: Mamy szereg pojemników na "0" i "1" ustawionych w długi wąż. Jakiś mechanizm przekłada liczby z pojemnika o numerze mniejszym do tego o większym na komendę zegara. Na pstryk wszystkie liczby przesuwają się o pojemnik dalej. Na końcu i w pewnym magicznym miejscu węża zapinamy jedno z wejść dwuwejściowej bramki realizującej mnożenie xor. Co to jest, za chwilę. Z wyjścia tej bramki wpuszczamy liczby na początek węża.

Xor działa według tabelki:

0*0=0,

1*1=0,

1*0=1 , 

0*1=1.

Jeśli na początek wpuścimy w wąż same zera, nic z tego nie wyjdzie, będą krążyły same zera. Jeśli jednak wpuścimy trochę jedynek, to dokładnie trudno powiedzieć, co będzie. I o to chodzi. Aby przewidzieć stan węża za ileś taktów zegara, trzeba po prostu wykonać całą operację. Prościej się nie da. Otóż nie działa to dla dowolnej długości węża, dla dowolnego miejsca zapięcia bramki xor. Dowcip jednak w tym, że istnieją (powszechnie dostępne) dane na temat takich węży o długości do ponad 100 tysięcy pojemników. Nie trudno sobie wyobrazić, że wąż o tej samej długości i tym samym miejscu zapięcia bramki (bo jedno z wejść musi być na końcu), do którego wpuścimy w ustalonej kolejności zera i jedynki (zainicjujemy stan rejestru, mówiąc inżyniersko), wygeneruje zawsze ten sam ciąg. Wystarczy teraz wykonywać kolejne tyknięcia zegara i obserwować na przykład wyjście bramki xor, zapisując jej kolejne stany.

Jeśli niczego nie popsujemy, otrzymany szereg będzie miał wszelkie własności ciągu losowego. W szczególności osoba, która nie zna startowej konfiguracji zer i jedynek, nic będzie mogła wydedukować na temat tego, co kolejno się pojawi.

Wystarczy zamienić informację na bity, a kodowanie okaże się banalnie proste. Wykonujemy operację xor (znowu xor!) pomiędzy bitami informacji i ciągu losowego. I otrzymamy kompletną kaszkę, idealny prawie szum losowy. Odbiorca musi znać stan początkowy generatora (znowu mamy system symetryczny, ten sam klucz koduje i odkodowuje). Uruchamia generator, wykonuje xor z bitami zakodowanej informacji i dostaje jawną treść.

Rejestry przesuwne generują skończone ciągi niepowtarzalnych sekwencji zer i jedynek. Jak długie? Znowu, jeśli nic nie jest popsute, to jest to dwa do potęgi równej ilości skrzyneczek w rejestrze. Na przykład dwa do potęgi coś około 19.000. Liczba kombinacji wyraża się w systemie dziesiętnym liczbą z 6 tysiącami cyfr. Około, liczyłem tak na oko.

Co możemy zrobić, żeby odszyfrować wiadomość? Samemu uruchomić rejestr przesuwny i prowadzić operację xor z przechwyconą informacją w nadziei, że otrzymamy coś sensownego. Jeśli mamy dostatecznie silny ośrodek obliczeniowy, może trafimy na właściwe rozwiązanie.

Choć już pisałem kilka razy, mam powody, by przypomnieć, jak wielkie liczby mają się do mocy komputerów. Doba to tylko 86400 sekund. Rok to 31536000 sekund. Zaledwie trzydzieści jeden milionów, siedem cyfr. Jeśli nawet komputer zrobi w ciągu sekundy miliard operacji, możemy założyć, że mamy komputer z 10 000 procesorów, niech będzie 10 do potęgi trzynastej operacji, to w ciągu roku będzie ich zaledwie dziesięć do około potęgi dwudziestej. Otóż standardowo stosowany obecnie klucz 128 bitów to 340282366920938463463374607431768211456 kombinacji. Liczba liczy sobie 39 cyfr.

Każde zwiększenie długości klucza, byle w nie głupim algorytmie, powoduje dwukrotne zwiększenie liczby kombinacji. Co prawda, rejestry przesuwne nie mogą mieć dowolnej długości, lecz widać chyba, że mamy dostatecznie długie, by zapomnieć o możliwości odkodowania.

Dlaczego więc jednak kryptolodzy pracują, zamiast strzelić sobie w łeb? Szukają metod bardziej subtelnych. Jeśli, na przykład, opisaną metodą statystyczną uda się ustalić jeden bit klucza, liczba kombinacji maleje dwukrotnie. Największym wrogiem szyfrujących są wszelkiego rodzaju błędy. Jeśli wysyła się jakiś stały tekst, którego można się domyślić, zazwyczaj "puszczają" wszelkie metody szyfrowania. Nawet jeśli nie wiadomo, jak tekst został zakodowany, możemy się domyślić. Zdarzają się głupie wpadki, typu szyfrowanie nagłówka firmy czy nagłówka całego dokumentu. Mądre szyfry są odporne na kombinowanie i można je złamać tylko metodą prób i błędów czyli brutal force. Prosta metoda z tablicą zamian liter (którą trzeba strzec przed szpiegami) daje piekielną liczbę możliwych kombinacji 24 litery można poprzestawiać na 6.2 * 10 do potęgi 23, lecz, niestety, wystarczy znaleźć dwie, trzy litery, a cały system zaczyna się pruć. Niestety, jesteśmy tylko ludźmi i nijak mamy się do doskonałości matematyki.

 




 
Spis treści
451 Fahrenheita
Literatura
Bookiet
Recenzje
Zatańczysz pan...?
Spam(ientnika)
Ludzie listy piszą
HOR-MONO-SKOP
Romuald Pawlak
Andrzej Pilipiuk
W. Świdziniewski
Piotr K. Schmidtke
Adam Cebula
Łukasz Małecki
Łukasz Orbitowski
Konrad Bańkowski
Paweł Laudański
Adam Cebula
T. Zbigniew Dworak
Łukasz Orbitowski
Magdalena Kozak
Krzysztof Kochański
Tomasz Duszyński
Konrad Bańkowski
Bartuss
XXX
Tomasz Pacyński
Robert J. Szmidt
Agnieszka Hałas
Jacek Piekara
Alexander Brajdak
 
< 21 >