kryptoanaliza.pdf

(266 KB) Pobierz
58396164 UNPDF
BSK 2003
C OPYRIGHT BY K ATARZYNA T RYBICKA -F RANCIK
K. T RYBICKA -F RANCIK
KRYPTOANALIZA
Opracowanie wewnętrzne Instytutu Informatyki
Gliwice, 1999
Kryptoanaliza
Kryptoanaliza jest dziedziną wiedzy i badań zajmującą się metodami przełamywania szyfrów.
Szyfr jest przełamywalny, jeśli istnieje możliwość odtworzenia tekstu jawnego bądź klucza na
postawie tekstu zaszyfrowanego albo określenie klucza na podstawie tekstu jawnego i
zaszyfrowanego. Wyróżnia się trzy podstawowe rodzaje przełamywania szyfru:
1. Atak bez tekstu jawnego. Kryptoanalityk musi określić klucz znając tekst
zaszyfrowany. Mogą być też znane: metoda szyfrowania, język tekstu jawnego,
tematyka badanego tekstu oraz słowa charakterystyczne dla tej tematyki z określonym
prawdopodobieństwem wystąpienia.
2. Atak z tekstem jawnym. Kryptoanalityk zna pary tekstów jawnego i zaszyfrowanego.
3. Atak z wybranym tekstem jawnym. Kryptoanalityk może zdobyć tekst zaszyfrowany
odpowiadający wybranemu fragmentowi tekstu zaszyfrowanego.
1
BSK 2003
C OPYRIGHT BY K ATARZYNA T RYBICKA -F RANCIK
1.1 Kryptoanaliza metodą anagramową
Metoda ta jest szczególnie przydatna w przełamywaniu szyfrów przestawieniowych
(permutacyjnych). Kryptoanalitycy mogą łatwo poznać, czy zastosowany szyfr jest szyfrem
przestawieniowym, gdyż częstość wystąpień liter tekstu szyfrowanego jest taka sama jak
częstość występowania liter w tekście zaszyfrowanym.
Metoda anagramowa polega na odtworzeniu właściwej kolejności przemieszanych znaków z
wykorzystaniem tablic częstości występowania digramów (kombinacji 2-literowych) i
trigramów (kombinacji 3-literowych).
1.2 Analiza częstości występowania liter 1
Metoda ta jest efektywna, gdy mamy do czynienia z prostymi szyframi podstawieniowymi.
Atak polega na porównaniu częstości występowania liter w kryptogramie z częstościami
oczekiwanymi. Metoda ta pozwala z dużym prawdopodobieństwem dopasować litery
kryptogramu do liter tekstu jawnego. Wielce pomocną w pracy kryptoanalityka jest
znajomość częstości występowania digramów i trigramów.
1.3 Brutalna metoda przełamywania algorytmów kryptograficznych
Brutalna metoda przełamywania algorytmów kryptograficznych polega na przeszukaniu całej
przestrzeni klucza. I tak, gdy mamy do czynienia z szyfrem podstawieniowym typu szyfr
Cezara to przestrzeń klucza ogranicza się do 25 kombinacji dla alfabetu angielskiego (kolejno
sprawdzamy podstawienia dla alfabetu szyfrującego przesuniętego o 1, 2, 3,…, 25 pozycje w
prawo w stosunku do alfabetu tekstu szyfrowanego). Złożoność obliczeniowa rośnie, gdy atak
przeprowadzamy na szyfr podstawieniowy z alfabetem szyfrującym będącym dowolną
kombinacją odwzorowań znak alfabetu jawnego- znak alfabetu szyfrującego. W tym
przypadku mamy do sprawdzenia 26! kombinacji, czyli 403291461126605635584000000
przypadków. Współczesne algorytmy szyfrujące opierają się wprawdzie na alfabecie
dwuznakowym (0, 1) ale ilość kombinacji dla klucza 56-bitowego jest równa 256. Zakładając,
że superkomputer może sprawdzić milion kluczy na sekundę, znalezienie właściwego klucza
zajmie mu ok. 2000 lat.
1 Por. Załącznik D
2
BSK 2003
C OPYRIGHT BY K ATARZYNA T RYBICKA -F RANCIK
1.4 Kryptoanaliza różnicowa
Kryptoanaliza różnicowa została opracowana przez E. Bihama i A. Shamira dla algorytmu
DES. Później została zaadoptowana do różnych innych szyfrów iteracyjnych. Metoda ta
polega na szyfrowaniu par tekstów jawnych różniących się w określony sposób (stąd nazwa
metody) i analizie uzyskanych szyfrogramów. W niniejszy rozdziale zostanie opisana
merytoryczna strona kryptoanalizy różnicowej algorytmu DES
W algorytmie DES zastosowano skrzynki o sześciu bitach wejściowych i czterech wyjścia.
Wynika stąd, iż każda skrzynka ma 64*64 możliwe wartości par wejściowych (zakładając, że
istotna jest kolejność w parze). Dla każdej pary określić można różnicę jej wartości poprzez
wyliczenie ich bitowej sumy modulo 2 (czyli poprzez wykonanie operacji XOR na
odpowiadających sobie bitach; rezultat takiej operacji nazywany jest różnicą wartości,
ponieważ na pozycjach, na których bity się różnią, w wyniku otrzymujemy jedynki – rezultat
niejako informuje nas na jakich pozycjach są różne wartości). Podobnie wartości XOR’rów
można wyliczyć dla par na wyjściu skrzynki.
Ponieważ wejście skrzynki jest sześciobitowe, natomiast wyjście – czterobitowe, mamy
64*16 możliwych par: XOR wejściowy – XOR wyjściowy. Wynika stąd, że na każdą parę
XOR wejściowy – XOR wyjściowy przypadają średnio cztery pary wartości wejściowych.
Jednak nie wszystkie kombinacje XOR wejściowy – XOR wyjściowy są możliwe, a te
możliwe mają nierównomierny rozkład. Tablicę ilustrującą rozkład XOR’ów wejściowych i
wyjściowych wszystkich możliwych par wejściowych skrzynki nazywamy tablicą rozkładu
XOR’ów par . Określony element takiej tablicy jest liczbą mówiącą ile jest par wejściowych o
XOR’ze określonym przez numer wiersza tego elementu, które dają na wyjściu XOR
wyjściowy określony przez numer kolumny. Przykład fragmentu takiej tablicy – dla skrzynki
S1 algorytmu DES – przedstawiony jest na rysunku 1.
Przykład 1. Weźmy XOR wejściowy 34 (stosujemy zapis szesnastkowy). Z tablicy z rysunku
1 wynika, że dla takiego XOR’u wejściowego możliwymi wartościami XOR’u na wyjściu są:
1, 2, 3, 4, 7, 8, D i F. XOR wyjściowy równy 1 jest uzyskiwany dla 8 par, 2 – dla 16 par, 3 –
dla sześciu, itd..
Definicja 1. Niech dX oznacza sześciobitowy XOR wejściowy, zaś dY czterobitowy XOR
wyjściowy skrzynki S. Mówimy, że dX może spowodować dY dla skrzynki s, jeżeli istnieje co
najmniej jedna para wejściowa o XOR’ze równym dX , dla którego XOR wyjściowy skrzynki
S jest równy dY . Fakt, że dX może spowodować dY oznaczamy: dX->dY .
3
BSK 2003
C OPYRIGHT BY K ATARZYNA T RYBICKA -F RANCIK
Przykład 2. Z tablicy z rysunku 1 wynika, że dla skrzynki S1, XOR wejściowy 34 może
spowodować XOR wyjściowy 2 z prawdopodobieństwem ¼ - ponieważ sytuacja taka jest dla
16 spośród 64 możliwych par wejściowych o XOR’ze równym 34.
XOR wyjściowy
XOR wejściowy 0
1
2
3
4
5
6
7
8
9
A B C D E F
0
64 0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
6
0
2
4
4
0 10 12 4 10 6
2
4
2
0
0
0
8
0
4
4
4
0
6
8
6 12 6
4
2
3
14 4
2
2 10 6
4
2
6
4
4
0
2
2
2
0
4
0
0
0
6
0 10 10 6
0
4
6
4
2
8
6
2
5
4
8
6
2
2
4
4
2
0
4
4
0 12 2
4
6
…
30
0
4
6
0 12 6
2
2
8
2
4
4
6
2
2
4
31
4
8
2 10 2
2
2
2
6
0
0
2
2
4 10 8
32
4
2
6
4
4
2
2
4
6
6
4
8
2
2
8
0
33
4
4
6
2 10 8
4
2
4
0
2
2
4
6
2
4
34
0
8 16 6
2
0
0 12 6
0
0
0
0
8
0
8
35
2
2
4
0
8
0
0
0 14 4
6
8
0
2 14 0
…
Rysunek 1. Tablica rozkładu XOR’rów par dla skrzynki S1 algorytmu DES (fragment).
Dla skrzynek DES około 20% elementów tablic rozkładu XOR’ów par to zera.
Tablica rozkładu XOR’ów par daje nam informacje dla ilu par wejściowych o zadanym
XOR’ze możliwe jest uzyskanie określonego XOR’u wyjściowego. Kolejną informacją jaka
będzie nam potrzebna jest informacja jakie pary dają określoną kombinację XOR wejściowy
– XOR wyjściowy.
Przykład 3. Rozważmy element 34->4 (tzn. element z wiersza 34, kolumny 4) tablicy z
rysunku 1. Ponieważ jest on równy 2, to znaczy, że istnieją dwie pary o XOR’ze 34 które na
wyjściu skrzynki S1 dają XOR równy 4. Są to pary (13, 27) oraz (27, 13) (jeśli jakaś para jest
rozważanym zestawie par to oczywiście zawsze jest w nim też para o elementach w
odwróconej kolejności). Tablica wszystkich par wejściowych dla wiersza 34 pogrupowanych
wg XOR’ów wyjściowych przedstawiona jest na rysunku 2.
Jak znaleźć bity klucza iteracyjnego (klucza jednej iteracji algorytmu) wykorzystując
znajomość par wejściowych i XOR’u wyjściowego funkcji F algorytmu DES. Funkcja F
4
58396164.002.png
BSK 2003
C OPYRIGHT BY K ATARZYNA T RYBICKA -F RANCIK
przedstawiona jest na rysunku 3. W dalszych rozważaniach wykorzystywane będą
przedstawione na tym rysunku oznaczenia.
XOR wyjściowy
XOR wejściowy
1
2
3
4
03, 0F, 1E, 1F, 2A, 2B, 37, 3B
04, 05, 0E, 11, 12, 14, 1A, 1A, 20, 25, 26, 2E, 2F, 30, 31, 3A
01, 02, 15, 21, 35, 36
13, 27
00, 08, 0D, 17, 18, 1D, 23, 29, 2C, 34, 39, 3C
7
8
D
F
09, 0C, 19, 2D, 38, 3D
06, 10, 16, 1C, 22, 24, 28, 32
07, 0A, 0B, 33, 3E, 3F
Rysunek 2. Tablica par wejściowych o XOR’ze równym 34 pogrupowanych wg XOR’ów wyjściowych
dla skrzynki S1
wejście
klucz iteracyjny
S1 K S2 K
S3 K
S4 K
S5 K
S6 K
S7 K
S8 K
E
S1 E S2 E
S3 E
S4 E
S5 E
S6 E
S7 E
S8 E
S1 I
S2 I
S8 I
S1
S2
…
S8
S1 0
S2 0
S8 0
P
Rysunek 3. Funkcja F algorytmu DES.
Poniższy przykład obrazuje jak znaleźć sześć skrajnie lewych bitów klucza iteracyjnego, tzn.
6 bitów znajdujących się na pozycjach odpowiadających skrzynce S1. Zajmować się więc
będziemy sześciobitowymi słowami S1 E , S1 K , S1 I , S1 0 – patrz rysunek 3.
5
58396164.003.png 58396164.004.png 58396164.005.png 58396164.001.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin