Szyfr z kluczem jednorazowym

Szyfr z kluczem jednorazowym (ang. one-time pad) – szyfr zaproponowany w 1917 roku przez Gilberta Vernama, którego, przy poprawnym wykorzystaniu, nie można złamać. Szyfr z kluczem jednorazowym jest dużym zbiorem o niepowtarzalnych i przypadkowych sekwencjach znaków. W pierwotnej postaci była to jednorazowa taśma perforowana do dalekopisu. Nadawca używa każdej litery z tego zbioru do zaszyfrowania jednego znaku tekstu jawnego. Szyfrowanie to dodanie modulo 26 jednego znaku tekstu jawnego i znaku jednorazowego klucza.

Metoda Vernama zapewniała prawie doskonałe zabezpieczenie treści przekazu, ale wymagała użycia dalekopisu lub maszyny szyfrującej. Trzej kryptolodzy pracujący dla niemieckiego Ministerstwa Spraw Zagranicznych – Werner Kuntze, Rudolf Schauffler i Erich Langlotz – przekształcili metodę Vernama do postaci praktyczniejszych w użyciu tzw. jednorazowych bloczków szyfrowych. Były to łączone w 50-stronicowe bloki tablice, z których każda zawierała po 48 pięciocyfrowych grup. Cyfry we wszystkich grupach na jednej stronie były zapisane w sposób zupełnie przypadkowy, bez powtórzenia żadnej z grup. Podobnie żadna strona nie była duplikatem innej. Po przekształceniu tekstu jawnego depeszy w ciąg cyfr szyfrant według ustalonego systemu wybierał określoną stronę z bloku i wykorzystywał grupy cyfr jako klucz do zaszyfrowania depeszy dodając (modulo 10) cyfry klucza i te powstałe z przekształcenia tekstu jawnego. Odbiorca, dysponując identycznym blokiem odwracał proces szyfrowania. W latach 1921–1923 takie bloki wprowadzono do użytku w niemieckiej korespondencji dyplomatycznej. Potem metoda ta stała się najpowszechniej stosowanym sposobem szyfrowania w sytuacjach, kiedy nie było możliwości użycia maszyn szyfrujących.

Istniała również wersja jednorazowych bloczków szyfrowych, w której losowe grupy składały się z liter. Używanie tej wersji było bardziej skomplikowane: trzeba było (według ustalonej reguły) zamienić litery tekstu jawnego i litery jednorazowego klucza na dwucyfrowe liczby, a następnie dodać je do siebie (modulo 26). Otrzymane liczby z powrotem przekształcano w litery^[1].

Oryginalny szyfr Vernama

W 1917 Vernam skonstruował urządzenie do łączności telegraficznej korzystającej z 32-znakowego kodu Baudota. Każdy znak kodu jest kombinacją pięciu sygnałów lub ich braku, co odpowiada bitom 1 i 0 w komputerach. Niepowtarzalny, losowy ciąg znaków klucza jest wyperforowany na taśmie papierowej i każdy bit tekstu jawnego jest dodawany modulo 2 do kolejnego bitu klucza.

Polega na tym, że każdy bit wiadomości $M=m_{1},m_{2},m_{3},\dots ,m_{n}$ dodajemy modulo 2 (funkcja XOR) z bitem pochodzącym z idealnego generatora losowego $K=k_{1},k_{2},k_{3},\dots ,k_{n}.$ Taki generator można traktować jako ciąg losowy $n$ doświadczeń Bernoulliego z prawdopodobieństwem ${\frac {1}{2}}$ (np. rzut symetryczną monetą). Szyfrogram $C=c_{1},c_{2},c_{3},\dots ,c_{n}$ odczytujemy w analogiczny sposób, wykorzystując ciąg bitów wygenerowany przy szyfrowaniu:

c_{i}=m_{i}{\dot {\lor }}k_{i}

m_{i}=c_{i}{\dot {\lor }}k_{i}

i\in \left\{1,2,3,\dots ,n\right\}.

Na podstawie twierdzenia: jeżeli dwie zmienne losowe $X_{1}$ i $X_{2}$ są niezależne i $X_{2}$ ma rozkład jednostajny nad $\{0,1\},$ to $Y=X_{1}{\dot {\lor }}X_{2}$ ma rozkład jednostajny nad $\{0,1\}$ otrzymujemy wiadomość zaszyfrowaną. Idealność szyfru polega na tym, że wnioskowanie o następnym bicie szyfrogramu możliwe jest jedynie z prawdopodobieństwem równym ${\frac {1}{2}}.$ Innymi słowy nie ma żadnej metody, która pozwoliłaby powiększyć szansę zgadnięcia następnego bitu szyfrogramu nad ślepy traf.

Przykład

Załóżmy, że:

Ciąg bitów tekstu jawnego: $M=m_{1}m_{2}\dots$
Ciąg bitów klucza: $K=k_{1}k_{2}\dots$

Wtedy szyfr Vernama generuje ciąg bitów kryptogramu $C=EK(M)=c_{1}c_{2}\dots ,$ gdzie $c_{i}=(m_{i}+k_{i})\mod {2}$ dla $i=1,2,3\dots$

Litera tekstu jawnego A (11000 w kodzie Baudota)
Litera klucza D (10010 w kodzie Baudota)

Szyfrowanie polega na dodaniu litery tekstu jawnego do litery klucza

{\begin{aligned}M&=11000\\K&=10010\\EK(M)&=01010\end{aligned}}

Stosowanie

Każdy klucz używany jest tylko raz, do zaszyfrowania tylko jednej wiadomości. Klucz tworzony jest w sposób losowy, przeciwnik nie ma informacji, która może ułatwić złamanie szyfru. Po zaszyfrowaniu wiadomości nadawca niszczy strony lub taśmę perforowaną z wykorzystanym zbiorem znaków. Odbiorca dysponuje identycznym zbiorem i używa tych samych znaków zbioru do odszyfrowania każdego znaku szyfrogramu. Podobnie jak nadawca po odszyfrowaniu wiadomości niszczy zbiór znaków stanowiących klucz. Przy nadawaniu nowej wiadomości trzeba zastosować nowy zbiór znaków i nowe znaki klucza.

Szyfrowanie z kluczem jednorazowym może być rozszerzone na dane binarne. Zamiast zestawu znaków są stosowane klucze binarne.

Metoda generacji i użycia klucza kryptograficznego wymaga by:

Klucz użyty do szyfrowania wiadomości był dłuższy lub równy szyfrowanej wiadomości.
Klucz musi być wygenerowany w sposób całkowicie losowy (nie może istnieć sposób na odtworzenie klucza na podstawie znajomości działania generatorów liczb pseudolosowych).
Klucz nie może być użyty do zaszyfrowania więcej niż jednej wiadomości.

Zalety

Wykorzystanie tej metody np. w szyfrowaniu XOR, bądź w szyfrze polialfabetycznym zapewnia całkowite bezpieczeństwo wiadomości, ponieważ dla każdej pary M i C (wiadomość i tekst zaszyfrowany) istnieje pasujący do nich K (klucz), czyli znając jedynie C, możemy dopasować do niego dowolną M o tej samej długości i na ich podstawie wyliczyć pasujący K. Dzięki temu złamanie szyfru (o niezakodowanym tekście jawnym) nie jest możliwe nawet poprzez testowanie wszystkich możliwych kluczy (atak brute force).

Problem złamania OTP jest podobny do problemu związanego z rozwiązaniem równania: M + K = C w którym znane jest jedynie C. Zakładając, że przeciwnik nie ma dostępu do jednorazowego zestawu znaków stosowanego do szyfrowania wiadomości, można powiedzieć, że jest to idealnie bezpieczny algorytm utajniania. Dowolny szyfrogram może być szyfrogramem dowolnego tekstu jawnego o tej samej długości.

Wady

Praktyczną wadą algorytmu jest długość klucza, która nie może być mniejsza od długości wiadomości, jaką nadawca zamierza przesłać. Rutynowe stosowanie szyfrów z kluczem jednorazowym wymagałoby od nadawcy i odbiorcy wcześniejszego uzgodnienia ogromnego klucza (bądź ogromnego zbioru kluczy). Problem stanowi zarówno całkowicie losowe wygenerowanie klucza, jak i jego bezpieczne przekazanie drugiej stronie.

Z tego powodu algorytm z kluczem jednorazowym znajduje zastosowanie przede wszystkim w szyfrowaniu wyjątkowo tajnych informacji w kanałach o małej przepustowości. Gorąca linia między prezydentami Rosji i Stanów Zjednoczonych jest zabezpieczona właśnie za pomocą takiego szyfru^[2].

Przypisy

↑ Leo Marks: Between Silk and Cyanide: a Codemaker’s Story, 1941-1945. HarperCollins, 1998. ISBN 0-684-86780-X.
↑ Simon Singh, Księga szyfrów, Wydawnictwo Albatros, Warszawa 2001.

Bibliografia

David Kahn: Łamacze kodów. Warszawa: Wydawnictwa Naukowo-Techniczne, 2004. ISBN 83-204-2746-0.
Bruce Schneier, Kryptografia dla praktyków, WNT, Warszawa, 2002.

[1] Leo Marks: Between Silk and Cyanide: a Codemaker’s Story, 1941-1945. HarperCollins, 1998. ISBN 0-684-86780-X.

[2] Simon Singh, Księga szyfrów, Wydawnictwo Albatros, Warszawa 2001.

[1]

[2]