Metody różnicowej i liniowej kryptoanalizy szyfrów blokowych

Metody różnicowej i liniowej kryptoanalizy szyfrów blokowych

1 opinia

Format:

ibuk

WYBIERZ RODZAJ DOSTĘPU

 

Dostęp online przez myIBUK

WYBIERZ DŁUGOŚĆ DOSTĘPU

6,15

Wypożycz na 24h i opłać sms-em

17,50

cena zawiera podatek VAT

ZAPŁAĆ SMS-EM

TA KSIĄŻKA JEST W ABONAMENCIE

Już od 19,90 zł miesięcznie za 5 ebooków!

WYBIERZ SWÓJ ABONAMENT

Symetryczne szyfry blokowe należą do podstawowych narzędzi nowoczesnej kryptografii. Ponieważ nie są znane konstrukcje, których bezpieczeństwo można udowodnić, ocena tych szyfrów jest heurystyczna. Brane są pod uwagę tylko dotychczas znane ataki kryptograficzne. Do najważniejszych rozważanych ataków należą kryptoanaliza różnicowa i kryptoanaliza liniowa. W odróżnieniu od kryptoanalizy różnicowej, która jest w zasadzie metodą ataku kryptograficznego z wybranym tekstem jawnym, kryptoanaliza liniowa jest zasadniczo metodą ataku kryptograficznego ze znanym tekstem jawnym, a ponadto w pewnych okolicznościach może być wykorzystana do ataku na tekst zaszyfrowany. Podstawowa idea kryptoanalizy liniowej polega na opisaniu danego algorytmu szyfrowania za pomocą przybliżonego równania, tak zwanej aproksymacji liniowej. Przybliżone równanie opisujące wpływ szczególnych różnic w parach tekstów jawnych na różnice w odpowiadających im parach tekstów zaszyfrowanych nazywane jest aproksymacją różnicową. Dla dowolnej funkcji f o n binarnych wejściach i m binarnych wyjściach zbiór wszystkich aproksymacji różnicowych lub liniowych może być reprezentowany w postaci tablicy aproksymacji o rozmiarze O(2n+m). Algorytmy oparte na definicji aproksymacji różnicowej lub liniowej obliczają pojedynczą wartość tablicy aproksymacji w czasie wykładniczym. Ogranicza to zastosowanie tych podstawowych algorytmów do funkcji składowych szyfru o niewielkiej liczbie binarnych wejść i wyjść. Przedstawione w rozprawie szybkie algorytmy obliczają najlepszą niezerową aproksymację różnicową i liniową w co najwyżej liniowym czasie O(n+m) dla pojedynczego elementu bez angażowania pamięci potrzebnej do przechowania całych tablic. Pożądana jest konstrukcja specjalizowanych algorytmów dla pewnych klas funkcji składowych szyfrów blokowych. Dla struktur z selektorami sformułowano algorytm obliczania pojedynczego elementu tablicy liniowych aproksymacji struktury w czasie O(k ⋅ 2k), jak również algorytm obliczania całej tablicy aproksymacji struktury w czasie O(k) dla pojedynczego elementu, gdzie k oznacza liczbę bitów adresowych selektora. Oba algorytmy są oparte na ogólnym wyniku, który pozwala obliczyć wartości tablicy aproksymacji struktury na podstawie wstępnie obliczonych tablic aproksymacji jej funkcji składowych. Dla losowo wybranych n-bitowych permutacji i dowolnych funkcji rozważono dwuwymiarowe (tj. różnicowo-liniowe) rozkłady najlepszych aproksymacji niezerowych. Dla obu klas funkcji rozkłady te są podobne. Uzyskane wyniki świadczą o tym, że począwszy od pewnej wartości n, liniowa aproksymacja funkcji S-bloków staje się bardziej efektywna od aproksymacji różnicowej. Ta przewaga efektywności aproksymacji liniowej rośnie wraz ze wzrostem n, a przy rozmiarach S-bloków algorytmu DES nie jest jeszcze zauważalna. Wykazano, że wśród trzech losowo wybranych S-bloków dwa z nich nie są gorsze od najlepszego S-bloku algorytmu DES. W rozkładach jednowymiarowych porównano następujące warianty najlepszej aproksymacji liniowej: aproksymację z sumą modulo 2 bitów wyjściowych, aproksymację z dowolnym bitem wyjściowym i aproksymację z pojedynczym bitem wyjściowym. Do często stosowanych elementów składowych szyfrów blokowych należą funkcje sumy i różnicy arytmetycznej. Dla tych funkcji sformułowano wielomianowe w czasie algorytmy obliczania wartości tablic aproksymacji i rozkładów wartości w tych tablicach, jak również algorytm generowania listy efektywnych aproksymacji, uporządkowanej malejąco według miary efektywności. Zastosowana metoda umożliwia rozwiązanie wielu innych problemów generacji, typowych dla obliczeń wielorundowych charakterystyk szyfrów blokowych. Algorytmy służące do obliczania w czasie O(n) pojedynczej wartości tablicy różnicowych lub liniowych aproksymacji funkcji n-bitowej sumy lub różnicy arytmetycznej są przykładami algorytmów specjalizowanych. Ocenę szyfrów blokowych ograniczono do przypadku kryptoanalizy liniowej. Jako kryterium jakości przyjęto efektywność najlepszej aproksymacji niezerowej. Jakość szyfru porównywana jest z jakością algorytmu porównawczego o tej samej długości bloku. Wyróżnia się trzy metody oceny szyfru blokowego: zgrubną, pośrednią i dokładną. Metoda zgrubna jest oparta na założeniu, że najlepsza niezerowa aproksymacja szyfru jest złożeniem najlepszej niezerowej aproksymacji pojedynczej iteracji. Metodę tę zastosowano do szyfru typu DES i szyfru PP-1, który jest skalowalną siecią podstawieniowo-permutacyjną (SPN). W metodzie pośredniej dla szyfru konstruowany jest graf G aproksymacji zerowo- niezerowych. Algorytm SP oblicza najkrótszą ścieżkę o określonej długości w grafie G. Ta ścieżka określa najlepszą zerowo-niezerową aproksymację szyfru spełniającą warunki aproksymacji. Efektywność tej aproksymacji stanowi podstawę oceny szyfru. Wykazano, że efektywność odpowiednia dla 64-bitowego szyfru blokowego uzyskiwana jest przez 48-rundowy wariant algorytmu DES z poprawionymi S-blokami. Metoda dokładna polega na wyznaczeniu najlepszej niezerowej aproksymacji szyfru. Obliczenie najbardziej efektywnej aproksymacji przeprowadzane jest typowo w dwóch krokach. Najpierw, w wyniku kompozycji aproksymacji funkcji składowych, obliczane są efektywne aproksymacje pojedynczej iteracji. Następnie, w rezultacie kompozycji aproksymacji kolejnych iteracji, uzyskiwana jest aproksymacja całego szyfru. Metoda dokładna powinna być stosowana w odniesieniu do istniejących szyfrów. Pozostałe dwie metody, w których pomijane są szczegóły konstrukcji szyfru, są przydatne na etapie jego konstruowania. Rozważono różnicową i liniową kryptoanalizę algorytmów DES o zredukowanej liczbie rund. Wiele uwagi poświęcono wyznaczaniu charakterystyk aproksymacji. W szczególności przedstawiono optymalne różnicowe i liniowe charakterystyki r-rundowego algorytmu DES, gdzie r jest ograniczone, odpowiednio, przez 6 i 7, jak również optymalne cykliczne liniowe charakterystyki o długości cyklu od 2 do 5, które umożliwiają identyfikację klucza w przypadku większej liczby rund. Dla tych charakterystyk są formułowane warunki aproksymacji, uzyskiwane przez rozwiązanie właściwego dla algorytmu zbioru równań. Ten sam zbiór równań jest używany do wyznaczenia ogólnej postaci aproksymacji. Najlepsze charakterystyki odpowiadają najbardziej efektywnym aproksymacjom wykorzystywanym w różnych typach ataków kryptograficznych.


Liczba stron214
WydawcaWydawnictwo Politechniki Poznańskiej
ISBN-13978-83-7143-906-3
Język publikacjipolski
Informacja o sprzedawcyRavelo Sp. z o.o.

Ciekawe propozycje

Spis treści

  Streszczenie    5
  Oznaczenia    9
  
  1. WSTĘP    13
  1.1. Wprowadzenie    13
  1.2. Prace autora rozprawy    16
  1.3. Cel i układ rozprawy    19
  
  2. APROKSYMACJA SZYFRÓW BLOKOWYCH    23
  2.1. Ogólna struktura szyfru blokowego    23
  2.2. Szyfr DES    25
  2.3. Szyfr PP-1    27
  2.4. Różnicowa i liniowa aproksymacja funkcji    32
  2.5. Tablice aproksymacji    35
  2.6. Składanie aproksymacji    36
  2.7. Podsumowanie    39
  
  3. ALGORYTMY OBLICZANIA TABLIC APROKSYMACJI    41
  3.1. Algorytmy podstawowe    41
  3.2. Twierdzenie o obliczaniu tablicy TAf    42
  3.3. Szybkie algorytmy    44
  3.4. Algorytmy obliczania maxTD i maxTA    48
  3.5. Obliczanie tablicy TAf dla struktur z selektorami    51
  3.6. Podsumowanie    56
  
  4. APROKSYMACJA LOSOWYCH S-BLOKÓW    59
  4.1. S-bloki o równej liczbie wejść i wyjść    59
  4.2. Rozmiar S-bloków algorytmu DES    65
  4.3. Warianty liniowej aproksymacji S-bloków    66
  4.4. Podsumowanie    74
  
  5. APROKSYMACJA ARYTMETYCZNEJ SUMY I RÓŻNICY    77
  5.1. Różnicowa i liniowa aproksymacja sumy arytmetycznej    77
  5.2. Szybkie algorytmy dotyczące różnicowej aproksymacji sumy    81
  5.3. Szybkie algorytmy dotyczące liniowej aproksymacji sumy    89
  5.4. Różnicowa i liniowa aproksymacja różnicy arytmetycznej    95
  5.5. Szybkie algorytmy dotyczące różnicowej aproksymacji różnicy    98
  5.6. Szybkie algorytmy dotyczące liniowej aproksymacji różnicy    100
  5.7. Podsumowanie    101
  
  6. OCENA JAKOŚCI SZYFRU BLOKOWEGO    105
  6.1. Metoda oceny    105
  6.2. Klasa jakości S-bloków    106
  6.3. Algorytm porównawczy    108
  6.4. Własności aproksymacji szyfru blokowego    109
  6.5. Zgrubna ocena szyfru blokowego    112
  6.6. Zgrubna ocena algorytmu typu DES    114
  6.7. Rozszerzona zgrubna ocena algorytmu typu DES    117
  6.8. Rozszerzona zgrubna ocena algorytmu DES    120
  6.9. Zgrubna ocena szyfru PP-1    121
  6.10. Podsumowanie    123
  
  7. POŚREDNIA OCENA JAKOŚCI ALGORYTMU TYPU DES    125
  7.1. Warunki aproksymacji    125
  7.2. Aproksymacje zerowo-niezerowe    127
  7.3. Graf aproksymacji zerowo-niezerowych    131
  7.4. Algorytm SP    132
  7.5. Ocena dla funkcji f właściwie skonstruowanej    138
  7.6. Pośrednia ocena algorytmu DES    140
  7.7. Ocena dla dowolnej funkcji f    142
  7.8. Podsumowanie    145
  
  8. KRYPTOANALIZA RÓŻNICOWA ALGORYTMU DES    147
  8.1. Różnicowa aproksymacja funkcji f    147
  8.2. Różnicowa aproksymacja algorytmu DES    149
  8.3. Identyfikacja klucza algorytmu DES    155
  8.4. Indywidualna identyfikacja fragmentów klucza    161
  8.5. Wyniki eksperymentów identyfikacji    167
  8.6. Podsumowanie    168
  
  9. KRYPTOANALIZA LINIOWA ALGORYTMU DES    169
  9.1. Liniowa aproksymacja funkcji f    169
  9.2. Liniowa aproksymacja algorytmu DES    171
  9.3. Aproksymacje cykliczne algorytmu DES    177
  9.4. Identyfikacja klucza algorytmu DES    181
  9.5. Wyniki eksperymentów identyfikacji    186
  9.6. Podsumowanie    187
  
  10. PODSUMOWANIE    189
  
  Literatura    193
  Summary    211
RozwińZwiń
W celu zapewnienia wysokiej jakości świadczonych przez nas usług, nasz portal internetowy wykorzystuje informacje przechowywane w przeglądarce internetowej w formie tzw. „cookies”. Poruszając się po naszej stronie internetowej wyrażasz zgodę na wykorzystywanie przez nas „cookies”. Informacje o przechowywaniu „cookies”, warunkach ich przechowywania i uzyskiwania dostępu do nich znajdują się w Regulaminie.

Nie pokazuj więcej tego powiadomienia