Szyfrowanie z jednorazowym kluczem: Jedyny dowcipnie niezłamalny szyfr

Jak Pracuje Zaszyfrowanie XOR z Losowym Kluczem

Zaszyfrujesz dane za pomocą jednorazowego klucza, kombinując każdy element wiadomości o odpowiednim elemencie tajnego klucza przy użyciu operacji, która może być doskonale odwrotnie wykonana używając tego samego klucza. Dla danych binarnych ta operacja to wykluczające lub (XOR), które odwraca każdy bit wiadomości tam, gdzie bit odpowiadającego klucza jest jedynką, a pozostawia go niezmienionym tam, gdzie bit klucza jest zerem. Dla systemów opartych na tekście, takich jak historyczne zaszyfrowane dokumenty używane przez spioników i dyplomatach, równoważna operacja to dodawanie modularne: każda litera wiadomości przesuwa się w kierunku przodu alfabetu o ilość wyznaczoną przez odpowiadającą jej literę klucza, zwracając się do początku alfabetu po Z. Oba operacje są matematycznie równoważne i mieszają wiadomość i klucz tak, że wynik wygląda na bezsensowny szum. Odszyfrowanie polega tylko na odwrotnym procesie: stosowanie tej samej operacji XOR lub odejmowanie tego samego wartości klucza powraca do oryginalnej wiadomości dokładnie. Cała bezpieczeństwo systemu opiera się na jednym obiekcie, strumieniu klucza, który musi być generowany niezależnie od wiadomości i mieć dokładnie tą samą długość co wiadomość. Jeśli klucz jest nawet o jeden znak krótszy i powtarza się lub jest uzupełniany w sposób przewidziany, gwarancje opisane dalej już nie są prawdziwe, a szyfrogram staje się znacznie słabszy niż sugeruje jego reputacja.

Dowód Shannona na Pełną Sigmatycznosc

W 1949 roku Claude Shannon opublikował pracę Communication Theory of Secrecy Systems, w której formalnie zdefiniował to, co oznacza niezbrojne szyfrowanie, i udowodnił, że jednorazowy klucz osiąga to. Koncept Shannona, nazywany pełną sigmatycznością, stwierdza, że rozkład prawdopodobieństwa możliwych tekstów zaszyfrowanych, podanej cyfry szyfrującej, musi być identyczny z rozkładem prawdopodobieństwa tekstów przed tym, jak została widziana cyfra szyfrująca. W prostej mowie, odbieranie cyfry szyfrującej nie naucza atakującego niczego o wiadomości, nawet najmniejszej wskazówki ograniczającej możliwe opcje. Intuicyjna przyczyna, dla której to działa dla jednorazowego klucza, polega na tym, że dla każdego zaszyfrowanego tekstu, który atakujący odbierze, istnieje pewien możliwy klucz, który umożliwi dekodowanie go do dowolnego tekstu tej samej długości, który atakujący mógłby przypuszczać. Bez wiedzy na temat klucza, każdy równorzędny tekst pozostaje równie prawdopodobnym, czy mówi o bezpiecznej listce zakupów, czy o krytycznym rozkazie wojskowym. To jest podstawowo różne od każdego innego szyfrowania w obecności, które może odpierać atak tylko dlatego, że nikt jeszcze nie znalazł skrótu lub ponieważ komputery nie są wystarczająco szybkie. Bezpieczeństwo jednorazowego klucza pozostaje takie samo niezależnie od mocy obliczeniowej, ciekawości algorytmicznej czy przyszłych rozwiązań matematycznych, co jest powodem dla opisania go jako niewzględnie lub teoretycznie sigmatycznego, a nie tylko obliczeniowo sigmatycznego.

Stronneżne wymagania dla gwarancji bezpieczeństwa

Dowód Shannona zawiera warunki, które są niezwykle żądane w praktyce. Pierwsze to klucz musi być prawdziwie losowy, wygenerowany przez fizyczny proces, tak jak rozpad radioaktywny, szum atmosferyczny lub rzut kostką, a nie za pomocą generatora pseudolosowego czy algorytmu, ponieważ każdy deterministyczny proces generujący klucz wprowadza wzorce, które atakujacy mógłby w teorii wykorzystać do zniszczenia pełnej uniformności, na jaką opiera się dowód. Drugie to klucz musi być używany dokładnie raz i nigdy nie ponownie dla innych wiadomości; nawet reużycie fragmentu materiału klucza wobec drugiej wiadomości otwiera drzwi do ataków statystycznych. Trzecie to klucz musi pozostawać całkowicie tajemniczy, znany tylko wysyłającemu i odbiorcy, a musi być wymieniany poprzez bezpieczny kanał, przesyłany zaufanym kurierem, zapamiętany lub ustalony w zaawansowanej fazie. Czwarte to klucz musi być co najmniej taki sam długości jak tekst zaszyfrowany, ponieważ każda niedostateczność wymusza ponowne użycie materiału klucza do pokrycia pozostającej części wiadomości. Każdy z tych warunków jest praktycznym obciążeniem, a nie matematycznie eleganckim szczegółem. Przestąpienie dowolnego jednego z nich, czyli używanie zepsutego generatora liczb losowych, reużycie strony z papierowego klucza lub pozwolenie na ujawnienie klucza, może znacząco obniżyć bezpieczeństwo szyfru w praktyce, często do tego stopnia, że stanie się niemalże łatwe do złamania.

Venona: Katastrofa Wirtualna Ze Znówu Korzystania z Klucza

Najjasniejszym historycznym przykładem tego, co się stanie, gdy przepis o jednorazowej poduszce kluczowej zostanie naruszone, jest projekt Venona. W latach 40. Sowieckie agencje inteligencji zaszyfrowały dyplomatyczne i szpiegowskie komunikaty za pomocą podużek kluczowych, które powinny być używane tylko raz na jednym arkuszu klucza. W wyniku nacisku wojennego however, personel kryptograficzny Sowietów ponownie wykorzystywał części materiału kluczowego w wielu komunikatach, tworząc tzw. głębokość dwie lub więcej szyfrogramów zaszyfrowanych za pomocą klucza pokrywającego się. W latach 1943-1980, wojskowi i późniejsze wspólne grupy dekodera amerykańsko-brytyjskie, pracując przez ponad trzydzieści lat, odkryli to znów i wykorzystali je. Porównując szyfrogramy zawierające wspólny materiał kluczowy, analiści mogli zrzucić wiele rzeczywistej przypadkowości, odtworzyć fragmenty podstawowego klucza i powoli odzyskać części oryginalnego rosyjskiego tekstu poprzez starannie przeprowadzone statystyczne i językowe analizy. Wyniki były zaskakujące: Venona odsłoniła istniejącą w Stanach Sowiecką sieć szpiegowską, obejmującą źródła związane z Projektem Manhattan. Uczy to jasno. Doskonała tajność poduszki kluczowej nie jest właściwością samego algorytmu; zależy ona całkowicie od doskonałej dyscypliny operacyjnej. Jedna sytuacja znów użycia klucza, nawet w nacisku wojennym i nawet przez zaawansowaną służbę szpiegowską, była wystarczająca, aby zamienić niezsolvable szyfr na rozwiązywalny problem.

Dlaczego jest niepraktyczne mimo że teoretycznie idealne

Jeśli jednorazowy klucz (one-time pad) jest naprawdę niezbrojny, dlaczego wszyscy używają go zamiast AES lub innych współczesnych szyfrów? Odpowiedzią jest problem rozdzielania klucza, który jest taki poważny, że jednorazowy klucz prawie nie ma codziennej aplikacji. Ponieważ klucz musi być tak długi jak wiadomość i nigdy nie może zostać ponownie wykorzystany, dwie strony, które chcą wymieniać nieskończoną ilość tajnego komunikatu w ciągu czasu, muszą na podstawę przeprowadzić przedmiotowe, bezpieczne i wstępne przechowywanie nieograniczonej ilości prawdziwie losowych materiałów kluczowych, bez kopiowania żadnej z nich, utraty ani compromitowania. Dla pojedynczej krótkiej telegrafii to managowalne; dla kontynuowanej współczesnej komunikacji obejmującej gigabajty lub terabajty danych, generowanie, rozprowadzanie i bezpieczne przechowywanie odpowiedniej ilości prawdziwej losowości jest niepraktycznie niewygodne. Każdy bezpieczny kanał potrzebny do rozdzielania klucza mógłby często być używany do przesyłania samej wiadomości, co stanowi centralny paradoks tego schematu. Współczesna kryptografia polega na szyfrach zabezpieczonych obliczeniowo, które uzywają krótkich kluczy łatwo rozprowadzanych, często wymieniających się za pomocą ciekawych protokołów matematycznych, takich jak Diffie-Hellman, wraz z algorytmami uważanymi za niewykonalne do złamania przy dowolnej rzeczywistej ilości obliczeniowej mocy. To oznacza odgadnięcie gwarancji absolutnie matematycznej Shannona na ogromną praktyczną wygodę. Jednorazowy klucz przetrwał do dziś głównie w nischen, mało intensywnych, bardzo wysokostawkowych ustawach, takich jak pewne komunikacje dyplomatyczne lub inteligencji, gdzie koszt przedmiotowego rozdzielania materiałów kluczowych jest zasługujący na zapewnienie, które żaden inny szyfr nie może zastąpić.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz The One-Time Pad: The Only Provably Unbreakable Cipher i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.