J. Szmidt, M. Misztal – Wstęp do kryptologii
ROZDZIAŁ 3
Szyfr blokowy jest to funkcja, która odwzorowuje n-bitowy tekst jawny w n-bitowy tekst tajny; n jest nazywane długością (wielkością) bloku. Funkcja jest parametryzowana przez k-bitowy klucz K, biorący wartości z podzbioru K (przestrzeń klucza) zbioru wszystkich k-bitowych wektorów . Najczęściej klucz jest wybierany losowo. Dla zapewnienia unikalności szyfrowania funkcja szyfrująca musi być odwracalna (1-1). Dla n-bitowego tekstu jawnego, tekstu tajnego i stałego klucza, funkcja szyfrująca jest bijekcją na zbiorze n-bitowych wektorów. Liczba kluczy wynosi , a efektywny rozmiar klucza jest równy (logarytm naturalny).
Rys. 3.1
Szyfry blokowe możemy wykorzystywać w różnych trybach pracy.
Każdy blok tekstu jawnego jest szyfrowany osobno:
.
Deszyfrowanie:
Rys. 3.2
Wadą tego trybu jest to, że jednakowe bloki szyfrogramu odpowiadają jednakowym blokom tekstu jawnego .
Każdy blok tekstu jawnego jest przed szyfrowaniem sumowany z poprzednim blokiem szyfrogramu:
Wartość początkowa IV (initial value) nie musi być tajna. Jednakowe bloki tekstu jawnego przechodzą w różne bloki szyfrogramu. Występuje mała propagacja błędów; jeśli odebrano z błędem to tylko bloki będą odszyfrowane niepoprawnie.
Rys. 3.3
Na podstawie klucza K i wartości początkowej V0 =IV generowany jest pseudolosowy ciąg bitowy:
sumowany z blokami tekstu jawnego:
Rys. 3.4
Nie występuje propagacja błędów (jeden przekłamany bit szyfrogramu przechodzi na jeden błędny bit tekstu jawnego). można wyznaczyć przed otrzymaniem lub .
Podobnie jak w trybie OFB, ale ciąg bitowy zależy tutaj od szyfrogramu:
Dwa inne tryby pracy otrzymujemy poprzez odwrócenie trybów CBC i CFB i oznaczamy CBC-1 i CFB-1.
Rys. 3.5
Inne tryby pracy to:
· wiązanie bloków tekstu jawnego (Plaintext Block Chaining – PBC);
· sprzężenie zwrotne tekstu tajnego (Plaintext Feedback - PFB);
· wiązanie bloków zaszyfrowanych różnic tekstu jawnego (Cipher Block Chaining of Plaintext Difference – CBCPD);
· sprzężenie zwrotne wyjściowe z funkcją nieliniową (Output Feedback with Non-Linear Function – OFBNLF).
DES (Data Encryption Standard), czyli Standard Szyfrowania Danych był najpopularniejszym szyfrem blokowym właśnie dlatego, że był standardem przez 24 lata. Jego historia datuje się od początku lat siedemdziesiątych. Opatentowany przez firmę IBM algorytm Lucifer został zmodyfikowany przez NSA (National Security Agency), czyli amerykańską Narodową Agencję Bezpieczeństwa. M.in. skrócono długość klucza. Powstały w ten sposób szyfr został zatwierdzony w 1977 roku przez NBS (National Bureau of Standards), czyli Narodowe Biuro Standardów i jako standard federalny otrzymał nazwę DES. Od tego czasu DES co pięć lat był ponownie zatwierdzany jako standard. Ostatni raz w roku 1992, w roku 1997 był ponownie rozważany. W roku 2000 po rozstrzygnięciu konkursu AES (Advanced Encryption Standard) został zatwierdzony, jako nowy standard algorytm RIJNDAEL.
DES jest szyfrem blokowym, który operuje na 64 bitowych blokach danych używając 56 bitowego klucza. Przeważnie jest to liczba zapisana na 64 bitach, przy czym co ósmy bit jest bitem parzystości i jest pomijany. Wśród wszystkich 256 kluczy istnieją klucze słabe, lecz mogą zostać one z łatwością pominięte. Całe bezpieczeństwo szyfru spoczywa na kluczu. Jest to szyfr symetryczny, tzn. ten sam klucz jest używany zarówno do szyfrowania jak i deszyfrowania. Na najniższym poziomie algorytm jest kombinacją dwóch podstawowych technik: mieszania i rozpraszania. Składa się on z dwóch głównych funkcji:
· permutacji klucza, która przygotowuje szesnaście 48 bitowych podkluczy. Podklucz jest wybrany z 56 bitów klucza. Służy do tego tablica permutacji podkluczy,
· funkcji szyfrującej, składającej się z 16 iteracji zwanych cyklami lub rundami. W każdym cyklu wykorzystuje się kombinację wyżej wymienionych technik z udziałem podkluczy. Algorytm wykorzystuje standardową arytmetykę i operacje logiczne (XOR, przesunięcia logiczne) na liczbach 64 bitowych. 64 bitowy tekst jawny P jest permutowany zgodnie z odwzorowaniem IP zwanym permutacją początkową (ang. Initial Permutation). Permutacja IP jest bijekcją, dokonującą transpozycji bloku wejściowego zgodnie z tablicą 3.1.
Tablica 3.1. Permutacja początkowa IP.
58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7
Tablicę należy czytać w następujący sposób: bit 58 zostaje przestawiony na bit 1, 50 na pozycję 2 itd. W podobny sposób należy czytać i inne tablice. Permutowany blok wejściowy jest następnie dzielony na 32 bitowe połowy. Lewa połowa jest zwana L0, a prawa R0. Permutacje początkowa IP i końcowa IP-1 nie zależą od danych ani od klucza. W związku z tym w żaden sposób nie wpływają na bezpieczeństwo algorytmu. Ponieważ permutacja na poziomie pojedynczych bitów jest trudna do zrealizowania programowego (chociaż jest łatwa w realizacjach sprzętowych) i jest czasochłonna, wiele aplikacji pomija permutacje IP i IP-1. Bezpieczeństwo nowego algorytmu nie jest mniejsze od bezpieczeństwa DES. Algorytm ten nie jest zgodny jednak ze standardem DES i nie powinien być nazywany DES.
Następnie wykonywane są 16 razy jednakowe operacje, zwane funkcją f, w czasie których dane łączone są z kluczem. Można je opisać następująco:
,
, (*)
gdzie 1 £ i £ 16, a f jest funkcją szyfrującą opisaną w punkcie 3.2.3. Wyrażenie (*) jest opisem jednego cyklu DES.
Rys 3.6. Pojedyncza runda algorytmu algorytmu DES.
Ponieważ funkcje szyfrujące DES używają 56 bitowego klucza, początkowy klucz 64 bitowy jest redukowany, przez usunięcie co 8 bitu. Są one wykorzystywane jako bity parzystości. Usunięcia dokonuje permutacja PC-1 zwana permutacją klucza.
Tablica 3.2. Permutacja klucza PC-1
57 49 41 33 25 17 9 1 58 50 42 34 26 18
10 2 59 51 43 35 27 19 11 3 60 52 44 36
63 55 47 39 31 23 15 7 62 54 46 38 30 22
14 6 61 53 45 37 29 21 13 5 28 20 12 4
Następnie dla każdego cyklu DES jest generowany 48 bitowy podklucz na podstawie 56 bitowego klucza K. Rysunek 3.8 przedstawia schemat generowania podkluczy dla poszczególnych cykli.
Rys. 3.8. Schemat przekształcenia klucza.
56 bitowy klucz jest dzielony na 28 bitowe połowy, C0 i D0. Następnie połowy te są przesuwane cyklicznie w lewo o jeden lub dwa bity, zależnie od numeru cyklu, zgodnie z tabelą 3.3.
Tablica 3.3. Przesunięcia klucza w zależności od numeru cyklu.
Cykl 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Liczba przesunięć 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1
Po wykonaniu przesunięcia jest wybieranych 48 z 56 bitów, wykorzystując permutację PC-2, zwaną permutacją wyboru (ang. permuted choice) lub kompresji (ang. compresion permutation).
Tablica 3.4. Permutacja wyboru PC-2.
14 17 11 24 1 5 3 28 15 6 21 10
23 19 12 4 26 8 16 7 27 20 13 2
41 52 31 37 47 55 30 40 51 45 33 48
44 49 39 56 34 53 46 42 50 36 29 32
Proces obliczania podkluczy dla cyklu i, gdzie 1£ i £ 16, przedstawiają wyrażenia:
Funkcja LS(x,i) jest przesunięciem cyklicznym x w lewo o liczbę pozycji podaną w tabeli 3.3. Podklucz Ki powstaje wg wzoru
Rys. 5.9. Schemat funkcji szyfrującej f algorytmu DES.
Funkcja szyfrująca f (przedstawiona na rysunku wyżej) tworzy 32 bitowy blok wyjściowy z 32 bitowego bloku wejściowego R i 48 bitowego podklucza K:
32 bitowy blok danych jest rozszerzany do 48 bitów za pomocą permutacji z rozszerzeniem E (ang. expansion permutation), danej tablicą 3.5. Operacja ma dwa cele: dostarczenie ciągu o tej samej długości co sumowany z nim klucz i ciągu wydłużonego, który może być poddany kompresji przy operacji podstawiania. Pozwalając jednemu bitowi wpływać na dwa podstawienia, uzyskuję się to, że zależność bitów wyjściowych od bitów wejściowych szybciej się rozprzestrzenia (tzw. efekt lawinowy).
Tablica 3.5. Permutacja rozszerzenia E
32 1 2 3 4 5 4 5 6 7 8 9
8 9 10 11 12 13 12 13 14 15 16 17
16 17 18 19 20 21 20 21 22 23 24 25
24 25 26 27 28 29 28 29 30 31 32 1
Wynik rozszerzenia, 48 bitowy blok E(R), jest sumowany modulo 2 z 48 bitowym podkluczem K, rezultatem czego jest 48 bitowy blok wejściowy poddawany operacji podstawiania. Podstawienia dokonywane są przez 8 skrzynek podstawieniowo-permutacyjnych (ang. substitution boxes), zwanych krótko S-skrzynkami lub po prostu skrzynkami (ang. S-boxes). Ciąg o długości 48 bitów jest dzielony na osiem 6 bitowych bloków. Każdy 6 bitowy blok jest przetwarzany przez oddzielną skrzynkę.
Każda skrzynka jest opisana przez tablicę złożoną z 4 wierszy i 16 kolumn, o 4 bitowych elementach. S-skrzynka odwzorowuje 6-bitowy blok wejściowy w blok 4 bitowy. Ich struktura została przedstawiona w podanej literaturze. Skrzynki są nieliniowe i są najbardziej znaczącymi elementami bezpieczeństwa szyfru.
Wartość bloku wyjściowego S-skrzynki jest opisana następującymi regułami:
· bity 0 i 5 bloku wejściowego są łączone i określają wiersz skrzynki (liczba całkowita 0,1,2 lub 3);
· środkowe 4 bity (1,2,3,4) określają kolumnę skrzynki (liczba całkowita z przedziału 0 do 15);
· 4 bitowa liczba leżąca na przecięciu wiersza i kolumny wyznaczonej w wyżej podany sposób określa wartość wyjściową.
...
i7xn1