One-Time Pad (OTP)

Szyfr strumieniowy z kluczem symetrycznym
  • Długość klucza = długość wiadomości

Opracowany w roku 1917 przez Gilberta Vernama, pracownika amerykańskiej firmy AT&T w USA.

Zastosowanie

Poprawnie stosowany szyfr OTP zapewnia całkowite bezpieczeństwo (ang. perfect secrecy) i umożliwia bardzo szybkie szyfrowanie i deszyfrowanie przesyłanej wiadomości. Wadą tego algorytmu jest długość klucza, która nie może być mniejsza od długości nadawanej wiadomości, co czyni go niewygodnym przy próbach zastosowania do przesyłu większej ilości danych.

Algorytm

Szyfrowanie i deszyfrowanie danych w OTP przebiega w taki sam sposób. Dysponując wiadomością do zaszyfrowania lub odszyfrowania oraz sekretnym kluczem, należy dodawać za pomocą operacji XOR kolejne bajty wiadomości i klucza.

Odpowiadające sobie bajty wiadomości i sekretnego klucza dodawane są jeden po drugim. Każda taka operacja produkuje jeden bajt wyjściowy:

   mi XOR ki = ci
   ci XOR ki = mi

Wielokrotne użycie klucza

Każda część klucza szyfrującego może być użyta tylko jeden raz, do zaszyfrowania tylko jednego fragmentu wiadomości (oczywiście, o takiej samej długości). Użycie tych samych bajtów klucza więcej niż jeden raz, umożliwia napastnikowi uzyskanie dwóch oryginalnych wiadomości zsumowanych XOR:

   M1 XOR K = C1
   M2 XOR K = C2
   C1 XOR C2 = M1 XOR K XOR M2 XOR K = M1 XOR M2

Na tak otrzymaną kombinację oryginalnych wiadomości, można przeprowadzać ataki bazujące na cechach kodowania znaków i cechach językowych.

Brak integralności

Szyfr OTP nie zapewnia integralności danych. Oznacza to, że możliwe jest zmodyfikowanie zaszyfrowanego tekstu, bez pozostawienia śladu po tej operacji. Dodatkowo, wynik takiej zmiany będzie miał przewidywalny wpływ na odszyfrowany potem przez odbiorcę tekst jawny.

   m -> enc(m, k) -> m XOR k
   (m XOR k) XOR p = m XOR k XOR p
   m XOR k XOR p -> dec(m XOR p, k) -> m XOR p

   gdzie p jest zmianą wprowadzoną przez napastnika.

Dzielenie Sekretu

OTP pozwala na współdzielenie sekretnego klucza przez pewną liczbę osób. W takim przypadku szyfrogram może być odkodowany tylko wtedy, jeśli wszystkie współdzielące go strony użyją swoich części klucza. Każda taka osoba będzie znała tylko swój podklucz.

Aby zaszyfrować tekst o długości n znaków przy użyciu sekretnego klucza współdzielonego przez m osób, należy przygotować m*n znaków klucza. Dzięki temu, każdy podklucz będzie składał się z n znaków i pozwoli zaszyfrować tekst o długości maksymalnie n znaków.

Przykładowo, jeśli sekretny klucz jest współdzielony pomiędzy trzema stronami, to wszystkie trzy podklucze będą musiały być dodane XOR do szyfrogramu w celu otrzymania oryginalnej wiadomości.

   K = K1 XOR K2 XOR K3
   C = M XOR K1 XOR K2 XOR K3
   M = C XOR K1 XOR K2 XOR K3

Schemat Blokowy Algorytmu OTP

Schemat algorytmu OTP

Matematyka:

XOR

Jedyną operacją wykonywaną podczas szyfrowania i deszyfrowania w OTP jest sumowanie bitów modulo 2 (XOR). Wszystkie bajty danych są sumowane XOR po kolei z odpowiadającymi im bajtami klucza.

Sumowanie XOR bajtów polega na dodawaniu XOR odpowiadających sobie kolejnych bitów w każdym bajcie.

Tablica prawdy dla dodawania XOR
b1b2b1 XOR b2
0 0 0   
0 1 1   
1 0 1   
1 1 0   

Implementacja

Szyfrowanie OTP zaimplementowane w C++:

string otp(const string & tekst_jawny, const string & klucz) {
    size_t dlug = tekst_jawny.size() < klucz.size() ?
                  tekst_jawny.size() : klucz.size();

    string szyfrogram;
    szyfrogram.resize(dlug);

    for (size_t i = 0; i < dlug; ++i) {
        szyfrogram[i] = ((short int)tekst_jawny[i]) ^
                        ((short int)klucz[i]);
    }

    return szyfrogram;
}
Data: 2020-03-09