Zamieszanie i dyfuzja - Confusion and diffusion

W kryptografii , zamieszanie i dyfuzja są dwie właściwości funkcjonowania bezpiecznym szyfrem zidentyfikowane przez Claude Shannon w swoim raporcie 1945 niejawnych matematycznej teorii kryptografii . Te właściwości, jeśli są obecne, uniemożliwiają zastosowanie statystyk i innych metod kryptoanalizy .

Te koncepcje są również ważne w projektowaniu niezawodnych funkcji mieszających i generatorów liczb pseudolosowych, w których dekorelacja generowanych wartości ma ogromne znaczenie.

Definicja

Dezorientacja

Zamieszanie oznacza, że ​​każda cyfra binarna (bit) zaszyfrowanego tekstu powinna zależeć od kilku części klucza, zasłaniając połączenia między nimi.

Właściwość pomyłki ukrywa związek między tekstem zaszyfrowanym a kluczem.

Ta właściwość utrudnia znalezienie klucza w zaszyfrowanym tekście, a zmiana pojedynczego bitu w kluczu wpłynie na obliczanie większości lub wszystkich bitów w zaszyfrowanym tekście.

Zamieszanie zwiększa niejednoznaczność zaszyfrowanego tekstu i jest używane zarówno przez szyfry blokowe, jak i strumieniowe.

W sieciach substytucyjno-permutacyjnych zamieszanie zapewniają pola substytucyjne .

Dyfuzja

Dyfuzja oznacza, że ​​jeśli zmienimy jeden bit tekstu jawnego, to około połowa bitów tekstu zaszyfrowanego powinna się zmienić i podobnie, jeśli zmienimy jeden bit tekstu jawnego, to powinna zmienić się około połowa bitów tekstu jawnego. Jest to równoznaczne z oczekiwaniem, że schematy szyfrowania wywołują efekt lawinowy .

Celem dyfuzji jest ukrycie statystycznego związku między tekstem zaszyfrowanym a tekstem jawnym. Na przykład dyfuzja zapewnia, że ​​wszelkie wzorce w tekście jawnym, takie jak nadmiarowe bity, nie będą widoczne w tekście zaszyfrowanym. Szyfry blokowe osiągają to poprzez „rozproszenie” informacji o strukturze tekstu jawnego w wierszach i kolumnach szyfru.

W sieciach substytucyjno-permutacyjnych dyfuzję zapewniają skrzynki permutacyjne .

Teoria

W oryginalnych definicjach Shannona zamieszanie odnosi się do uczynienia relacji między szyfrogramem a kluczem symetrycznym tak złożonym i zaangażowanym, jak to tylko możliwe; dyfuzja odnosi się do rozproszenia struktury statystycznej tekstu jawnego w większości tekstu zaszyfrowanego . Ta złożoność jest na ogół realizowana poprzez dobrze zdefiniowane i powtarzalne serie podstawień i permutacji . Substytucja odnosi się do zastąpienia pewnych komponentów (zwykle bitów) innymi komponentami, zgodnie z pewnymi zasadami. Permutacja odnosi się do manipulacji kolejnością bitów zgodnie z jakimś algorytmem. Aby była skuteczna, każda niejednorodność bitów tekstu jawnego musi zostać rozłożona na znacznie większe struktury w tekście zaszyfrowanym, co znacznie utrudnia wykrycie tej niejednorodności.

W szczególności, dla losowo wybranego wejścia, jeśli odwrócimy i- ty bit, prawdopodobieństwo, że j- ty bit wyjścia ulegnie zmianie, powinno wynosić połowę, dla dowolnego i oraz j — jest to określane jako ścisłe kryterium lawinowe . Bardziej ogólnie, można wymagać, aby odwrócenie ustalonego zestawu bitów zmieniało każdy bit wyjściowy z prawdopodobieństwem równym połowie.

Jednym z celów pomyłki jest utrudnienie znalezienia klucza, nawet jeśli ma się dużą liczbę par tekst jawny-tekst zaszyfrowany utworzonych przy użyciu tego samego klucza. Dlatego każdy bit zaszyfrowanego tekstu powinien zależeć od całego klucza i w różny sposób od różnych bitów klucza. W szczególności zmiana jednego bitu klucza powinna całkowicie zmienić zaszyfrowany tekst. Najprostszym sposobem osiągnięcia zarówno dyfuzji, jak i zamieszania jest użycie sieci substytucyjno-permutacyjnej . W tych systemach tekst jawny i klucz często odgrywają bardzo podobną rolę w tworzeniu danych wyjściowych, stąd ten sam mechanizm zapewnia zarówno dyfuzję, jak i zamieszanie.

Zastosowano do szyfrowania

Projektując metodę szyfrowania wykorzystuje się zarówno zasady pomyłki, jak i dyfuzji. Zamieszanie oznacza, że ​​proces drastycznie zmienia dane z danych wejściowych na dane wyjściowe, na przykład poprzez tłumaczenie danych przez nieliniową tabelę utworzoną z klucza. Istnieje wiele sposobów odwrócenia obliczeń liniowych, więc im bardziej są one nieliniowe, tym więcej narzędzi analitycznych się psuje.

Dyfuzja oznacza, że ​​zmiana pojedynczego znaku wejścia spowoduje zmianę wielu znaków wyjścia. Zrobione dobrze, każda część danych wejściowych wpływa na każdą część danych wyjściowych, co znacznie utrudnia analizę. Żaden proces dyfuzji nie jest doskonały: zawsze przepuszcza pewne wzory. Dobra dyfuzja powoduje szerokie rozproszenie tych wzorów na wyjściu, a jeśli jest kilka wzorów, które się przez nie przebijają, mieszają się one ze sobą. To sprawia, że ​​wzorce są znacznie trudniejsze do wykrycia i znacznie zwiększa ilość danych do przeanalizowania w celu złamania szyfru.

Analiza AES

Advanced Encryption Standard (AES) posiada zarówno doskonałą zamieszanie i dyfuzji. Tabele przeglądowe zamieszania są bardzo nieliniowe i dobrze niszczą wzory. Jego stopień dyfuzji rozkłada każdą część wejścia na każdą część wyjścia: zmiana jednego bitu wejścia zmienia średnio połowę bitów wyjścia. Zarówno zamieszanie, jak i rozproszenie są powtarzane wielokrotnie dla każdego wejścia, aby zwiększyć ilość szyfrowania. Tajny klucz jest mieszany na każdym etapie, aby atakujący nie mógł z góry obliczyć, co robi szyfr.

Nic z tego nie dzieje się, gdy proste jednoetapowe mieszanie opiera się na kluczu. Wzorce wejściowe przepłyną prosto do wyjścia. Na pierwszy rzut oka może się to wydawać przypadkowe, ale analiza znajdzie oczywiste wzorce i szyfr może zostać złamany.

Zobacz też

Bibliografia

Prace cytowane