Odległość jedności - Unicity distance

W kryptografii , odległość jedyność to długość oryginalnego szyfrogram potrzebnych do złamania szyfru poprzez ograniczenie liczby możliwych kluczy fałszywych zero w ataku brute force . Oznacza to, że po wypróbowaniu każdego możliwego klucza powinien nastąpić tylko jeden odszyfrowanie, które ma sens, tj. Spodziewana ilość tekstu zaszyfrowanego potrzebna do całkowitego określenia klucza, zakładając, że podstawowa wiadomość ma nadmiarowość.

Claude Shannon zdefiniował dystans jedyności w swoim artykule z 1949 r. „ Teoria komunikacji systemów tajemnicy ”.

Rozważmy atak na ciąg zaszyfrowanego tekstu „WNAIW” zaszyfrowany przy użyciu szyfru Vigenère z pięcioliterowym kluczem. Można sobie wyobrazić, że ten ciąg mógłby zostać rozszyfrowany na dowolny inny ciąg - RIVER i WATER są możliwościami dla niektórych kluczy. To jest ogólna zasada kryptoanalizy : bez dodatkowych informacji nie da się odszyfrować tej wiadomości.

Oczywiście nawet w tym przypadku tylko określona liczba pięcioliterowych kluczy da w wyniku angielskie słowa. Wypróbowując wszystkie możliwe klucze otrzymamy nie tylko RZEKĘ i WODĘ, ale także SXOOS i KHDOP. Liczba "działających" kluczy będzie prawdopodobnie znacznie mniejsza niż zestaw wszystkich możliwych kluczy. Problem polega na tym, aby wiedzieć, który z tych „działających” kluczy jest właściwy; reszta jest fałszywa.

Związek z rozmiarem klucza i możliwymi tekstami jawnymi

Ogólnie biorąc, biorąc pod uwagę określone założenia dotyczące rozmiaru klucza i liczby możliwych wiadomości, istnieje średnia długość tekstu zaszyfrowanego, gdy jest tylko jeden klucz (średnio), który wygeneruje czytelną wiadomość. W powyższym przykładzie widzimy tylko wielkie litery angielskie, więc jeśli przyjmiemy, że tekst jawny ma taką postać, to istnieje 26 możliwych liter na każdą pozycję w ciągu. Podobnie, jeśli przyjmiemy pięcioznakowe klawisze z wielkich liter, istnieje K = 26 5 możliwych kluczy, z których większość nie będzie „działać”.

Ogromna liczba możliwych wiadomości, N, może zostać wygenerowana przy użyciu nawet tego ograniczonego zestawu znaków: N = 26 L , gdzie L jest długością wiadomości. Jednak tylko mniejszy zestaw z nich jest czytelnym tekstem jawnym ze względu na reguły języka, być może M z nich, gdzie M prawdopodobnie będzie znacznie mniejsze niż N. Ponadto M ma relację jeden do jednego z liczbą kluczy, które działają, więc mając K możliwych kluczy, tylko K × (M / N) z nich będzie "działać". Jeden z nich to właściwy klucz, pozostałe są fałszywe.

Ponieważ M / N staje się arbitralnie małe wraz ze wzrostem długości L wiadomości, ostatecznie istnieje pewna liczba L, która jest wystarczająco duża, aby liczba fałszywych kluczy była równa zeru. Z grubsza mówiąc, jest to L, które sprawia, że ​​KM / N = 1. To L to odległość jednostkowa.

Relacja z kluczową entropią i redundancją tekstu jawnego

Jednolitość odległość można równoważnie zdefiniować jako minimalną ilość zaszyfrowanego tekstu wymaganą do umożliwienia nieograniczonemu obliczeniowo przeciwnikowi odzyskania unikalnego klucza szyfrującego.

Oczekiwaną odległość unikalności można następnie wykazać jako:

gdzie U to odległość jednostkowa, H ( k ) to entropia przestrzeni klucza (np. 128 dla 2 128 równoważnych kluczy, raczej mniej, jeśli klucz jest zapamiętaną frazą hasła). D jest definiowane jako nadmiarowość tekstu jawnego w bitach na znak.

Teraz alfabet składający się z 32 znaków może przenosić 5 bitów informacji na znak (jako 32 = 2 5 ). Ogólnie liczba bitów informacji przypadających na znak to log 2 (N) , gdzie N to liczba znaków w alfabecie, a log 2 to logarytm binarny . Tak więc w przypadku języka angielskiego każdy znak może przekazywać log 2 (26) = 4,7 bitów informacji.

Jednak średnia ilość faktycznych informacji przenoszonych na znak w zrozumiałym angielskim tekście wynosi tylko około 1,5 bitu na znak. Zatem nadmiarowość zwykłego tekstu wynosi D = 4,7 - 1,5 = 3,2.

Zasadniczo im większa odległość jednorodności, tym lepiej. Dla jednorazowego bloku czasowego o nieograniczonej wielkości, biorąc pod uwagę nieograniczoną entropię przestrzeni kluczy, mamy , co jest zgodne z tym, że jednorazowa podkładka jest niezniszczalna.

Odległość jedności szyfru podstawieniowego

W przypadku prostego szyfru podstawieniowego liczba możliwych kluczy to 26! = 4,0329 × 10 26 = 2 88,4 , czyli liczba sposobów permutacji alfabetu. Zakładając, że wszystkie klucze są równie prawdopodobne, H ( k ) = log 2 (26!) = 88,4 bitów. Dla tekstu angielskiego D = 3,2 , więc U = 88,4 / 3,2 = 28 .

Zatem biorąc pod uwagę 28 znaków zaszyfrowanego tekstu, teoretycznie powinno być możliwe opracowanie angielskiego tekstu jawnego, a tym samym klucza.

Praktyczne zastosowanie

Odległość jedności jest użyteczną miarą teoretyczną, ale nie mówi wiele o bezpieczeństwie szyfru blokowego, gdy jest atakowany przez przeciwnika z (ograniczonymi) zasobami w świecie rzeczywistym. Rozważmy szyfr blokowy z odległością jedności wynoszącą trzy bloki tekstu zaszyfrowanego. Chociaż istnieje wystarczająco dużo informacji, aby przeciwnik bez ograniczeń obliczeniowych mógł znaleźć właściwy klucz (proste, wyczerpujące wyszukiwanie), w praktyce może to być niewykonalne obliczeniowo.

Odległość unicity można zwiększyć, zmniejszając nadmiarowość tekstu jawnego. Jednym ze sposobów jest wdrożenie technik kompresji danych przed szyfrowaniem, na przykład poprzez usunięcie zbędnych samogłosek przy zachowaniu czytelności. To i tak dobry pomysł, ponieważ zmniejsza ilość danych do zaszyfrowania.

Można założyć, że szyfrogramy większe niż odległość jedności mają tylko jedno znaczące odszyfrowanie. Zaszyfrowane teksty krótsze niż odległość jednostkowa mogą mieć wiele prawdopodobnych deszyfracji. Odległość jedności nie jest miarą tego, ile tekstu zaszyfrowanego potrzeba do analizy kryptograficznej, ale ile tekstu zaszyfrowanego jest wymagane, aby istniało tylko jedno rozsądne rozwiązanie dla kryptoanalizy.

Bibliografia

Linki zewnętrzne