ROZDZIAŁ 3

SZYFRY BLOKOWE

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

1. TRYBY PRACY

Szyfry blokowe możemy wykorzystywać w różnych trybach pracy.

1. Elektroniczna książka kodowa (Electronic Code Book - ECB)

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
.

2. Wiązanie bloków zaszyfrowanych (Cipher Block Chaining - CBC)

Każdy blok tekstu jawnego jest przed szyfrowaniem sumowany z poprzednim blokiem szyfrogramu:

.

Deszyfrowanie:

.

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

3. Sprzężenie zwrotne wyjścia (Output Feedback - OFB)

Na podstawie klucza K i wartości początkowej V₀ =IV generowany jest pseudolosowy ciąg bitowy:

.

sumowany z blokami tekstu jawnego:

.

Deszyfrowanie:

.

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
.

4. Sprzężenie zwrotne szyfrogramu (Cipher Feedback -CFB)

Podobnie jak w trybie OFB, ale ciąg bitowy zależy tutaj od szyfrogramu:

.

Deszyfrowanie:

.

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).

1. STANDARD SZYFROWANIA DANYCH DES

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.

1. Ogólny opis algorytmu

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 2⁵⁶ 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 L₀, a prawa R₀. 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.

1. 
   Przekształcenia klucza

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, C₀ i D₀. 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 K_i powstaje wg wzoru







Rys. 5.9. Schemat funkcji szyfrującej f algorytmu DES.

2. Funkcja szyfrująca f

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ą.

Wynikiem fazy podstawień jest 32 bitowy blok powstały z konkatenacji ośmiu 4 bitowych bloków. Jest on następnie permutowany przy pomocy permutacji P. Permutacja P odwzorowuje każdy bit wejściowy w jeden bit wyjściowy. Żaden bit nie jest pomijany ani nie jest używany dwukrotnie (jest to bijekcja). Tabela 3.6 pokazuje tą permutację.

Tablica 3.6. Permutacja P.

16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10

2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25

Wynik permutacji P jest blokiem wyjściowym funkcji f.

1. Deszyfrowanie DES

Deszyfrowanie DES odbywa się przy wykorzystaniu tego samego algorytmu co szyfrowanie. Jedyna różnica polega na kolejności użycia podkluczy. Są one pobierane w odwrotnej kolejności. Oznacza to, że jeśli kluczami szyfrującymi dla poszczególnych cykli są K₁, K₂,...K₁₆ to kluczami deszyfrującymi są K_16, K₁₅, ...K₁.

2. Tryby pracy DES

DES posiada wyspecyfikowane 4 tryby pracy (na podstawie FIPS PUB 81), które zostały już omówione wyżej. Są to:

1. ECB;

2. CBC;

3. OFB;

4. CFB.

3. Bezpieczeństwo DES

Od chwili stworzenia w 1977 r. DES podlegał intensywnej analizie. Istniało wiele spekulacji dotyczących długości klucza, liczby cykli i projektu skrzynek. Szczególnie tajemnicze były skrzynki. Nikomu nie znane były zasady ich stworzenia. Istniało podejrzenie istnienia tzw. zapadni, dzięki czemu NSA miałoby możliwość łatwego łamania DES.

Przez ponad 20 lat badań nie znaleziono jednak praktycznych metod szybkiego łamania DES. Dostępne implementacje programowe umożliwiają na komputerze z zegarem 33 MHz przeszyfrowanie 40 600 bloków na sekundę. Bezpieczeństwo DES polega na tym, że najlepszym sposobem złamania tego szyfru jest tzw. atak brutalny, czyli przejrzenie całej przestrzeni klucza. Mając blok wejściowy i jego zaszyfrowany odpowiednik, czyli stosując tzw. atak ze znanym tekstem jawnym, aby znaleźć klucz tego szyfrowania należy sprawdzić wszystkie 2⁵⁶ klucze. Jest to więc 7*10¹⁶ szyfrowań co przy szybkości 40 600 bloków/s zajęłoby aż 56 tys. lat. Ale stosując szybsze komputery i wykorzystując obliczenia równoległe można to zrobić o wiele szybciej. W 1993 roku Michael Wiener stwierdził, że komputer, który złamałby DES, czyli przejrzał całą przestrzeń klucza w 3,5 godziny kosztowałby 1 milion USD. Takie urządzenie zostało zbudowane w roku 1997 w ramach programu EFF (Electronic Frontier Foundation). Właśnie dlatego uważa się, że DES nie jest już szyfrem bezpiecznym i nie został zatwierdzony ponownie jako standard.

Alternatywą dla DES są szyfry blokowe o dłuższym kluczu. Jednym z nich jest potrójny DES. Jego działanie polega na trzykrotnym użyciu szyfru DES z dwoma różnymi kluczami. Daje to dużo lepsze efekty niż DES tradycyjny.

4. Klucze słabe

W algorytmie DES istnieją klucze słabe (ang. weak keys). Wybór jednego z tych kluczy spowoduje, że podklucze używane w poszczególnych cyklach będą takie same. Zjawisko to wystąpi, jeżeli wszystkie bity w każdej z połówek są 0 lub 1.

Tablica 3.7. Klucze słabe DES

Pierwotny ciąg słabego klucza				Faktyczny ciąg klucza
0101	0101	0101	0101	00000000	00000000
FEFE	FEFE	FEFE	FEFE	FFFFFFFF	FFFFFFFF
1F1F	1F1F	0E0E	0E0E	00000000	FFFFFFFF
E0E0	E0E0	F1F1	F1F1	FFFFFFFF	00000000

Istnieją również klucze półsłabe (ang. semi-weak keys), które szyfrują różne teksty jawne do jednakowych tekstów tajnych. W wyniku generowania podkluczy zamiast 16 różnych podkluczy powstaną tylko 2, z których każdy zostanie wykorzystany 8 razy.

Tablica 3.8. Klucze półsłabe DES

01FE 01FE 01FE 01FE

1FE0 1FE0 0FE1 0FE1

01E0 01E0 01F1 01F1

1FFE 1FFE 0EFE 0EFE

011F 011F 010E 010E

E0FE E0FE F1FE F1FE

Można znaleźć również 48 kluczy, które w rezultacie dają 4 różne podklucze, każdy wykorzystywany 4 razy. W rezultacie na 2⁵⁶ istnieją tylko 64 klucze słabe. Prawdopodobieństwo trafienia takiego klucza jest pomijalnie małe.

5. Długość klucza

Prototyp DES, czyli LUCIFER posiadał klucz 128 bitowy. Klucz DES został ograniczony do 56 bitów. Wielu kryptologów opowiadało się za dłuższym kluczem, ze względu na atak brutalny, który dla 56 bitów był bardzo kosztowny, ale nie niemożliwy.

6. Liczba iteracji

DES wykorzystuje 16 iteracji. Wybór takiej liczby powtórzeń został wybrany ze względu na odporność przeciwko kryptoanalizie różnicowej. Biham i Shamir udowodnili, że DES ograniczony do liczby cykli mniejszej niż 16 może być złamany z wybranym tekstem jawnym efektywniej niż atak brutalny.

7. Budowa skrzynek

Przez wiele lat nieznane były zasady budowy skrzynek. Oto niektóre kryteria projektowe:

• Żadna ze skrzynek nie jest liniową funkcją afiniczną swojego wejścia.

• Zmiana wartości 1 bitu na wejściu skrzynki spowoduje zmianę wartości co najmniej 2 bitów na wyjściu. Skrzynki maksymalizują stopień rozproszenia.

• Skrzynki mają minimalizować różnicę między liczbą 0 i 1, gdy wartość jednego bitu wejściowego jest utrzymana na stałym poziomie.

• Wydaje się, że zasadniczym kryterium była odporność na kryptoanalizę różnicową.

1. Modyfikacje DES




Rys. 3.10. Trzykrotny algorytm DES.

Istnieje wiele różnych modyfikacji DES. Najbardziej znanym jest DES trzykrotny. Ponieważ DES nie tworzy grupy, zatem tekst tajny jest znacznie trudniej złamać metodą brutalnego ataku. Rozmiar przestrzeni klucza wynosi 2¹¹² zamiast 2⁵⁶. Tekst jawny jest najpierw szyfrowany z kluczem K₁, następnie jest deszyfrowany z kluczem K₂ i ponownie szyfrowany z kluczem K₁. Deszyfrowanie polega na zamianie procesu szyfrowania na deszyfrowanie z tym samym kluczem. Patrz rysunek 3.10.

Inną modyfikacją jest użycie DES z niezależnymi podkluczami. Zamiast generowania podkluczy 48 bitowych z 56 bitów używa się klucza o długości 768 bitów (16 cykli razy 48 bitów podklucza). Przestrzeń klucza wynosi 2⁷⁶⁸ co jest wielkością trudną do porównania z czymkolwiek (liczba atomów we Wszechświecie wraz z czarną materią szacowana jest na 2²⁶⁵). Wariant ten znacznie zwiększa złożoność DES. Biham i Shamir pokazali jednak, że tak zmodyfikowany szyfr może być złamany przy użyciu 2⁶¹ wybranych tekstów jawnych. Występują ponadto warianty DES ze zmienioną kolejnością skrzynek i ich wartościami, które są zależne od klucza np. CRYPT(3).

1. MIĘDZYNARODOWY ALGORYTM SZYFROWANIA DANYCH

IDEA

Najpoważniejszym konkurentem DES przed ogłoszeniem konkursu AES był algorytm IDEA.

1. Historia

Wiele prób podejmowanych było nad zaprojektowaniem algorytmu, który zastąpiłby DES. Jedną z przyczyn było przekonanie, że wielkość kluczy DES jest za mała. Inną ważną przyczyną były regulacje prawne w USA uznające DES za produkt o znaczeniu militarnym i używanie go poza granicami USA bez stosownych licencji było używane za czyn przestępczy. Ponieważ utrudnia to stosowanie kryptografii w kontaktach z partnerami z USA i spoza USA, istniała potrzeba znalezienia algorytmu, którego stosowanie nie prowadziłoby do konfliktów z amerykańskimi organami bezpieczeństwa. Cele te przyświecały powstaniu IDEA. Szyfr został stworzony przez Xuejia Lai i Jamesa Masseya ze Szwajcarskiego Federalnego Instytutu Technologii we współpracy z firmą Asccom Systec. Pierwotna wersja zwana PES (ang. Proposed Encryption Standard) została opublikowana w materiałach z konferencji Eurocrypt '90. Wersja poprawiona, odporna na atak kryptoanalizą różnicową, została przedstawiona rok później. IDEA jest używana w wielu aplikacjach m.in., w TFT (ang. Trusted File Transfer) oraz PGP (ang. Pretty Good Privacy).

2. Ogólny opis algorytmu

IDEA jest szyfrem blokowym, iteracyjnym. Ogólny schemat szyfrowania jest przedstawiony na rys. 3.11. Algorytm operuje na 64 bitowych blokach danych i 128 bitowym kluczu. Szyfrowanie składa się z 8 cykli, po których następuje przekształcenie końcowe. Algorytm wykorzystuje, podobnie jak DES, mieszanie i rozpraszanie. Realizowane jest to przez następujące operacje trzech grup algebraicznych:

- poelementowe dodawanie modulo 2,

- dodawanie modulo 2¹⁶ ,

- mnożenie modulo 2¹⁶+1.

W przeciwieństwie do DES nie występują permutacje, a dzięki zastosowaniu 16 bitowych podbloków algorytm działa efektywnie na procesorach 16 bitowych.




Rys. 3.11. Ogólny schemat algorytmu IDEA.

64 bitowy blok tekstu jawnego dzielony jest na cztery 16 bitowe podbloki X₁, X₂, X₃, X₄. Stanowią one wejście do pierwszego cyklu algorytmu. Opis pojedynczej iteracji został przedstawiony na rys. 3.12. Dodatkowymi danymi jest sześć 16 bitowych podkluczy Z₁,..,Z₆ powstałych z 128 bitowego klucza w trakcie operacji generowania kluczy. Iteracja rozpoczyna się przekształceniem, które tworzy kombinację czterech wejściowych podbloków z czterema podkluczami przy użyciu operacji dodawania i mnożenia. Cztery bloki przy użyciu operacji XOR łączone są w dwa 16 bitowe bloki, które stanowią wejście do struktury realizującej rozpraszanie, zwanej MA (patrz rys. 3.12, szary prostokąt). Struktura ta używa dwóch podkluczy i tworzy dwa bloki 16 bitowe.




Rys. 3.12. Opis pojedynczej iteracji algorytmu IDEA.

Następnie z 4 bloków wejściowych i dwóch utworzonych w MA tworzy się przy użyciu funkcji XOR cztery bloki, będące wynikiem iteracji. Dodatkowo zmieniana jest kolejność bloków drugiego i trzeciego. Powoduje to dodatkowe wymieszanie bitów, co jeszcze bardziej uodparnia IDEA przeciw kryptoanalizie różnicowej. Na koniec, w etapie przekształcenia (rys.3.13) wyniku, następuje niwelowanie wymiany, która nastąpiła w ósmym cyklu. Wymagane jest to ze względu na używanie tego samego algorytmu do szyfrowania i deszyfrowania. Etap ten wymaga tylko 4 podkluczy.




Rys. 3.13. Etap przekształcenia wyników algorytmu IDEA.

3. Generowanie podkluczy

Szyfrowanie przy pomocy algorytmu IDEA wymaga 52 podkluczy 16-bitowych. Podklucze są generowane w następujący sposób:

128 bitów klucza jest dzielone na bloki 16-bitowe. Daje to pierwszych 8 podkluczy (6 podkluczy dla pierwszego cyklu, 2 dla drugiego cyklu). Na kluczu wykonuje się przesunięcie cykliczne o 25 bitów w lewo i na nowo dzielony jest on na bloki długości 16. Daje to, następne 8 podkluczy (4 brakujące podklucze dla drugiego cyklu, 4 dla trzeciego cyklu).

Powyższe operacje powtarzamy aż wygenerujemy wszystkie podklucze.

Jest to skuteczna metoda generowania podkluczy. Na uwagę zasługuje fakt, że pierwsze podklucze w każdej iteracji korzystają z innego zestawu bitów klucza. Jeśli cały klucz jest oznaczony Z[1..128] to kluczom Z₁, Z₇, Z₁₃, Z₁₉, Z₂₅, Z₃₁, Z₃₇, Z₄₃ zostaną przypisane następujące bity:

Z₁ = Z[1..16] Z₂₅ = Z[76..91]

Z₇ = Z[97..112] Z₃₁ = Z[44..59]

Z₁₃ = Z[90..105] Z₂₅ = Z[37..52]

Z₁₉ = Z[83..98] Z₄₃ = Z[30..45]

4. Deszyfrowanie

Deszyfrowanie przebiega tak samo jak szyfrowanie. Odbywa się przy wykorzystaniu tej samej ogólnej struktury algorytmu IDEA. Lecz przy użyciu innego zestawu podkluczy. Podbloki klucza są addytywną i multiplikatywną odwrotnością podkluczy użytych do szyfrowania. Tworzy się je według zasady: pierwsze cztery podklucze iteracji deszyfrowania i tworzone są na podstawie czterech pierwszych podkluczy iteracji szyfrowania
, gdzie etap przekształcenia liczy się jako dziewiąta iteracja. Pierwszy i czwarty podklucz stanowią odwrotność modulo
pierwszego i czwartego podklucza szyfrowania. W iteracjach 1 i 9 drugi i trzeci podklucz deszyfrowania jest odwrotnością względem dodawania modulo
drugiego i trzeciego podklucza szyfrowania. W iteracjach od 2 do 8 drugi i trzeci podklucz deszyfrowania jest odwrotnością względem dodawania modulo
trzeciego i drugiego podklucza szyfrowania. W pierwszych ośmiu iteracjach ostatnie dwa podklucze iteracji deszyfrowania i równe są ostatnim dwu podkluczom iteracji szyfrowania
.

5. Tryby pracy IDEA

IDEA, podobnie jak DES, może pracować w każdym z trybów pracy szyfrów blokowych, omawianych wyżej:

ECB,

CBC,

OFB,

CFB.

6. Bezpieczeństwo IDEA

Algorytm IDEA może być z powodzeniem implementowany na procesorach 16 bitowych. Jego programowa implementacja jest szybsza od programowej implementacji DES i znacznie szybsza od potrójnego DES. Na komputerze z zegarem 33 MHz IDEA szyfruje dane z szybkością 880 Kbit/s, a na komputerze VAX 9000 cztery razy szybciej. Sprzętowa implementacja algorytmu, układ scalony o powierzchni 108,7 mm² zawierający 251 000 tranzystorów, osiąga szybkość 177 Mbit/s, przy częstotliwości taktowania 25 MHz. Zakładając, że atak brutalny jest najbardziej efektywny, znalezienie klucza wymagałoby 2¹²⁸ (10³⁸) szyfrowań. Gdybyśmy zaprojektowali układ scalony, który testowałby miliard kluczy w ciągu sekundy i gdybyśmy użyli miliarda takich układów, to znalezienie klucza zajęłoby 10¹³ lat - czas dłuższy niż czas życia Wszechświata. Sieć 10²⁴ takich układów znalazłaby klucz w ciągu jednego dnia, lecz w całym Wszechświecie nie ma tylu atomów krzemu, aby można było zbudować taką maszynę.

Mimo, że IDEA jest algorytmem znanym już ponad dekadę jak na razie nie są znane lepsze sposoby ataku niż atak brutalny. Nie poddał się on (w przeciwieństwie do DES) popularniej obecnie kryptoanalizie różnicowej. Dlatego jest on jednym z najlepszych szyfrów blokowych, ale trwają ciągłe prace nad jego złamaniem. Podobnie jak DES również algorytm IDEA podlega intensywnym badaniom. Do tej pory, mimo intensywnych badań kilku ośrodków cywilnych i wojskowych, nie udało się znaleźć metody, która byłaby efektywniejsza od ataku brutalnego.

Dodatkowa trudność związana jest z wytwarzaniem podkluczy deszyfrujących. Wytwarzanie podkluczy szyfrujących jest dużo szybsze niż deszyfrujących. W związku z tym, przy dużych ilościach kluczy, znalezienie wszystkich odwrotności multiplikatywnych powoduje dwu - lub trzykrotne zwiększenie czasu wymaganego do przeprowadzenia ataku brutalnego (w porównaniu z czasem potrzebnym do wytworzenia kluczy szyfrujących). IDEA została uodporniona na atak kryptoanalizą różnicową. Poprzednia wersja, PES poddawała się temu atakowi. Niewielkie zmiany w tym algorytmie spowodowały, że został on wzmocniony.

7. Klasa kluczy słabych

Podobnie jak DES również IDEA posiada klucze słabe. Wybór takich kluczy nie spowoduje wygenerowania identycznych podkluczy dla wszystkich cykli. Są one słabe w tym sensie, że użycie takiego klucza może być łatwo odkryte przy ataku z wybranym tekstem jawnym. Przykładem takiego klucza jest (szesnastkowo)

0000 0000 0F00 0000 0000 000F FFFF F000

gdzie F oznacza dowolną liczbę z zakresu 0 do 15.

8. Modyfikacje IDEA

IDEA podobnie jak DES może zostać wykorzystana do dwukrotnego szyfrowania (podatna jest wtedy na atak metodą spotkania w środku), do trzykrotnego szyfrowania (jest odporna na atak wymieniony wyżej). Można zastosować modyfikację z niezależnymi kluczami. Algorytm wymaga wtedy 52 kluczy 16 bitowych. Nie udowodniono, że modyfikacja ta mogłaby osłabić algorytm.

2. KONKURS AES

Konkurs AES (ang. Advanced Encryption Standard) czyli zaawansowany standard szyfrowania zrodził się z potrzeby zastąpienia wprowadzonego w latach 70-tych standardu szyfrowania danych DES. Algorytm ten był krytykowany już od dawna jako nie dający wystarczającego zabezpieczenia w stosunku do obecnych możliwości kryptoanalizy. Chodzi tu przede wszystkim o zbyt małą długość klucza w stosunku do współczesnych możliwości ataku brutalnego. Koszt i czas przeszukania przestrzeni klucza DES są zbyt małe aby mógł on dalej być bezpiecznym standardem szyfrowania. Prześledźmy pokrótce postęp w tej dziedzinie. W 1979 roku Diffie i Hellman przewidywali teoretycznie możliwość złamania DES atakiem brutalnym w ciągu 24 godzin przy kosztach wynoszących 20 - 50 mln USD. W 1987 doszło do pierwszych kłopotów z zatwierdzeniem DES na standard, ze względu na sprzeciw amerykańskiej agencji bezpieczeństwa NSA (ang. National Security Agency). W roku 1992 jeszcze raz zatwierdzono ten algorytm na standard. W 1993 M.J. Wiener zasugerował sposób znalezienia klucza DES w ciągu 3,5 godziny przez maszynę wartą 1 mln USD. W 1997 roku w Electronic Frontier Foundation zbudowano maszynę łamiącą DES w trzy dni. Jej całkowity koszt wraz z projektem wyniósł 210 tys. USD. Tak więc przy obecnej technologii DES nie jest algorytmem bezpiecznym. Wprowadzane modyfikacje DES, np. potrójny DES także nie spełniają współczesnych wymogów bezpieczeństwa. Dlatego zdecydowano o wprowadzeniu nowego algorytmu szyfrowania. Został on wyłoniony w drodze ogólnodostępnego konkursu AES.

1. Założenia konkursu AES

AES ma być algorytmem, który przetrwa jako standard przynajmniej równie długo co DES, czyli algorytmem XXI wieku. Wyborem algorytmu i przebiegiem konkursu kieruje amerykański instytut standaryzacji NIST (ang. National Institute of Standards and Technology). W przyjętych założeniach AES ma być:

• bardzo silnym, symetrycznym szyfrem blokowym do nieklasyfikowanych zastosowań rządowych i zastosowań komercyjnych w przyszłym wieku;

• bardziej efektywny i bardziej bezpieczny niż potrójny DES;

• o następujących parametrach (w bitach):

• długości klucza: 128, 192, 256;

• długość bloku 128 (64, 80, 128 lub inna opcjonalnie);

• publicznie przedstawiony (jawny) i oceniony;

• nie wymagający opłacania praw autorskich na całym świecie.

AES ma być wybrany w całkowicie otwartym procesie, tzn. każdy miał prawo zgłosić swojego kandydata, wszystkie algorytmy mogą być publicznie komentowane i oceniane. Ostatecznie wybrany algorytm zostanie przedstawiony ministrowi handlu (ang. Secretary of Commerce).

1. Kryteria oceny

Wszystkie zgłoszone algorytmy oceniane będą w następujących kategoriach:

• Bezpieczeństwo:

• aktualne bezpieczeństwo;

• losowe własności permutacji;

• podstawy matematyczne;

• inne zaproponowane czynniki bezpieczeństwa.

• Koszty:

• efektywność (szybkość działania);

• wymagania pamięciowe (sprzętowe i programowe).

• Algorytm i implementacja:

• elastyczność;

• sprzętowa i programowa realizowalność;

• prostota projektu.

• Inne aspekty:

• efektywność i zgodność implementacji;

• przedstawienie i obrona algorytmu;

• wymagania licencyjne.

Podsumowując każdy mógł zgłosić kandydata, każdy może testować zgłoszone algorytmy i każdy może oceniać kandydatów.

1. Propozycje algorytmów blokowych zgłoszonych do AES

W sierpniu 1998 roku odbyła się pierwsza konferencja AES, na której przedstawiono 15 algorytmów zgłoszonych jako kandydaci. Listę wszystkich tych algorytmów wraz z autorami przedstawia poniższa tabela.

Lp.	Nazwa algorytmu	Zgłoszony przez	Autorzy
1.	CAST-256	Entrust Technologies, Inc.	Carlise M. Adams Stafford E. Tavares Michael J. Wiener Howard M. Heys
2.	CRYPTON	Chae Hoon Lim & Future Systems, Inc.	Chae Hoon Lim
3.	DEAL	Richard Outerbridge	Lars R. Knudsen
4.	DFC	Centre National pour la Recherche Scientifique (CNRS)	Serge Vaudenay
5.	E2	Nippon Telegraph and Telephone Corporation (NTT)	NTT
6.	FROG	TecApro	Dianelos Geroges Georgoudis Damian Leroux Billy Simon Chaves
7.	HPC	Rich Schroeppel	Rich Schroeppel
8.	LOKI97	Dr Lawrie Brown	Lawrie Brown Josef Pieprzyk Jennifer Sebbery
9.	MAGENTA	Deutsche Telokom AG	Klaus Huber Stefan Wolter
10.	MARS	IBM	Don Coppersmith and others
11.	RC6	RSA Laboratories	Ronald L. Rivest Matthew L. B. Robshaw Ray Sidney Yiqun Lisa Yin
12.	Rijndael	Joan Deamen	Joan Deamen Vincent Rijmen
13.	SAFER+	Cylink Corporation	James L. Massey Gurgen H. Khachatrian Melsik K. Kuregian
14.	SERPENT	Ross J. Anderson	Ross J. Anderson Eli Biham Lars R. Knudsen
15.	TWOFISH	Bruce Schneier	Bruce Schneier and others

Tabela 3.1.

W marcu 1999 roku odbyła się druga konferencja AES, na której ustalono nieoficjalny ranking kandydatów. W rankingu tym bardzo wysoko znalazły się algorytmy: RC6 i Rijndael, które omówimy tu szerzej.

1. RC6

Szyfr blokowy RC6 został zaprojektowany w Laboratoriach RSA. Jego autorami są: Ronald L.Rivest, Matthew J.B. Robshaw, Ray Sidney, Yiqun Lisa Yin. Został on zgłoszony jako kandydat na nowy standard szyfrowania danych do konkursu AES. Bazą do skonstruowania tego algorytmu był szyfr RC5, który zmodyfikowano do wymogów konkursu (zmiana długości bloku i długości klucza), a także wprowadzono zmiany podnoszące bezpieczeństwo i poprawiające wydajność (szybkość działania).

1. Wprowadzenie

Zaproponowany w 1995 roku szyfr RC5 był celowo zaprojektowany bardzo prosto. Bezpieczeństwo opierało się na zależnych od danych rotacjach (przesunięciach cyklicznych). Mimo prób nie znaleziono żadnego praktycznego ataku na ten szyfr, a tylko ataki teoretyczne oparte głównie na tym, że ilość rotacji w RC5 nie zależała od wszystkich bitów rejestru danych. W RC6 poprawiono tę wadę. Zgodnie z wymogami konkursu AES długość klucza ma wynosić 128, 192 i 256 bitów, a długość bloku danych 128 bitów. Dlatego też zastosowano podział na cztery 32-bitowe rejestry, wykorzystując 32-bitową architekturę większości aktualnych procesorów. W RC6, jak i w RC5, zastosowano tylko operacje efektywnie zaimplementowane na współczesnych procesorach (rozkazy asemblera, np. rotacja). Jako efektywną funkcję „mieszającą” zastosowano mnożenie całkowitoliczbowe.

Algorytm RC6 może działać z blokami i kluczami różnej długości, dlatego różne jego wersje można w sposób parametryczny zapisać jako RC6-w/r/b, gdzie

w - rozmiar słowa w bitach,

r - liczba rund,

b - długość klucza w bajtach.

Dla AES parametry te wynoszą
(32 bity × 4 słowa = 128 bitów),
,
, 24, 32 (b × 8 = 128, 192, 256 bitów).

RC6-w/r/b operuje na 4 w-bitowych słowach wykorzystując sześć prostych operacji:

a + b dodawanie całkowitoliczbowe modulo 2^w,

a - b odejmowanie całkowitoliczbowe modulo 2^w,

a ⊕ b binarna różnica symetryczna słów w-bitowych,

a × b mnożenie całkowitoliczbowe modulo 2^w,

a <<< b rotacja (przesunięcie cykliczne) w-bitowego słowa a w lewo o wartość wyznaczoną przez log₂w najmniej znaczących bitów słowa b,

a >>> b rotacja (przesunięcie cykliczne) w-bitowego słowa a w prawo o wartość wyznaczoną przez log₂w najmniej znaczących bitów słowa b.

2. Szyfrowanie i deszyfrowanie

Cztery w-bitowe rejestry wykorzystywane przez RC6-w/r/b oznaczane są jako A, B, C, D. Pierwszy bajt tekstu jawnego umieszczany jest w najmniej znaczącym bajcie rejestru A, a ostatni bajt tekstu jawnego w najbardziej znaczącym bajcie rejestru D. Po operacji szyfrowania w rejestrach A, B, C, D znajduje się tak samo ułożony szyfrogram. Szyfrowanie przedstawiono poniżej za pomocą pseudokodu. Zapis „(A,B,C,D) = (B,C,D,A)” oznacza przestawienie (permutację) rejestrów (A=B,B=C itd.), a „lg w” logarytm o podstawie 2 z w. W opisie rundy RC6 można dostrzec pewną analogię do DES, a mianowicie połowa bloku danych jest modyfikowana przy pomocy drugiej połowy, a później obie są zamieniane miejscami.

Szyfrowanie RC6-w/r/b

Wejście: Tekst jawny umieszczony w czterech w-bitowych rejestrach A, B, C, D,

2r + 4 w-bitowych kluczy S[0,...,2r +3].

Wyjście: Szyfrogram umieszczony w rejestrach A, B, C, D.

Szyfrowanie: B = B + S[0]

D = D +S[1]

for i = 1 to r do

{

t = (B × (2B + 1) <<< lg w

u = (D × (2D + 1) <<< lg w

A = ((A ⊕ t) >>> u) + S[2i]

C = ((C ⊕ u) >>> t) + S[2i+1]

(A,B,C,D) = (B,C,D,A)

}

A= A + S[2r + 2]

C = C + S[2r + 3]

Deszyfrowanie RC6-w/r/b

Wejście: Szyfrogram umieszczony w czterech w-bitowych rejestrach A, B, C, D,

2r + 4 w-bitowych kluczy S[0,...,2r + 3].

Wyjście: Tekst jawny umieszczony w rejestrach A, B, C, D.

Deszyfrowanie: C = C + S[2r + 3]

A = A + S[2r + 2]

for i = 1 to r do

{

(A,B,C,D) = (D,A,B,C)

t = (D × (2D + 1) <<< lg w

u = (B × (2B + 1) <<< lg w

A = ((C - S[2i +1 ]) >>> t) ⊕ u

A = ((A - S[2i]) >>> u) ⊕ t

}

D = D + S[1]

B = B + S[0]

Schemat jednej rundy przedstawia rysunek 3.14, gdzie funkcja f jest dana wzorem:

f(x) = x × (2x + 1).




Rys. 3.14. Schemat jednej rundy RC6.




Rys. 3.15. Schemat blokowy RC6.

3. Generowanie podkluczy

Szyfr RC6-w/r/b wymaga
podkluczy, należy je wygenerować z
b-bajtowego klucza głównego dostarczonego przez użytkownika. Używa się w tym celu podany niżej algorytm. Algorytm ten wykorzystuje dwie „magiczne stałe”:

P₃₂ = B7E15163 i Q₃₂ = 9E377989.

Zostały one uzyskane z dwóch znanych matematycznych stałych. P₃₂ jest zapisem szesnastkowym ułamkowej części podstawy logarytmu naturalnego e, Q₃₂ jest natomiast szesnastkowym zapisem ułamkowej części złotego podziału φ.

Generowanie podkluczy (key schedule) RC6-w/r/b

Wejście: b-bajtowy klucz użytkownika umieszczony w tablicy L[0,...,c-1] o długości c słów.

Wyjście: w-bitowe podklucze S[0, ..., 2r+3].

Działanie: S[0] = P_w

for i = 1 to 2r+3 do

S[i] = S[i-1] + Q_w

A = B = i = j = 0

v = 3 × max{c,2r + 4}

for s = 1 to v do

{

A = S[i] = (S[i] + A + B) <<< 3

B = L[j] = (L[j] + A + B) <<< (A + B)

i = (i + 1) mod (2r + 4)

j = (j + 1) mod c

}

4. Założenia projektowe

Projektowanie RC6 polegało na kolejnym ulepszeniu algorytmu RC5. W kilku krokach prześledzimy etapy dochodzenia od RC5 do RC6.

1. Podstawowa runda RC5 wyglądała następująco:

for i = 1 to r do

{

A = ((A ⊕ B)) <<< B) + S[i]

(A, B) = (B, A)

}

2. Po rozszerzeniu danych do czterech rejestrów wykonujemy rundę RC5 dwukrotnie:

for i = 1 to r do

{

A = ((A ⊕ B)) <<< B) + S[2i]

C = ((C ⊕ D)) <<< D) + S[2i + 1]

(A, B) = (B, A)

(C, D) = (D, C)

}

3. Przestawienia rejestrów można dokonać w jednej operacji, wiążąc (mieszając) równocześnie rejestry AB z CD:

for i = 1 to r do

{

A = ((A ⊕ B)) <<< B) + S[2i]

C = ((C ⊕ D)) <<< D) + S[2i + 1]

(A, B, C, D) = (B, C, D, A)

}

4. Dalsze związanie (wymieszanie) rejestrów poprzez zamianę parametrów rotacji:

for i = 1 to r do

{

A = ((A ⊕ B)) <<< D) + S[2i]

C = ((C ⊕ D)) <<< B) + S[2i + 1]

(A, B, C, D) = (B, C, D, A)

}

5. Aby uzależnić rotację od wszystkich bitów rejestru danych wykorzystano przekształcenie

f(x) = x(2x + 1) (mod 2^w)

wraz z rotacją w lewo o 5 pozycji. Przekształcenie to spełnia wymogi bezpieczeństwa żądane przez projektantów i posiada tę przewagę nad innymi przekształceniami, że jest efektywnie implementowane na większości współczesnych procesorów. Jest ono przekształceniem jeden w jeden modulo 2^w, a najbardziej znaczące bity f(x) wyznaczające ilość wykonywanych rotacji silnie zależą od wszystkich bitów x. Otrzymano:

for i = 1 to r do

{

t = (B × (2B + 1) <<< 5

u = (D × (2D + 1) <<< 5

A = ((A ⊕ t)) <<< u) + S[2i]

C = ((C ⊕ u)) <<< t) + S[2i + 1]

(A, B, C, D) = (B, C, D, A)

}

6. Aby tekst jawny nie ujawniał części wejścia do pierwszej rundy, a szyfrogram nie ujawniał części wyjścia z ostatniej, dołożono proste operacje początkowe i końcowe zależne od klucza.

W ten sposób otrzymano ostateczną wersję RC6:

B = B + S[0]

D = D + S[1]

for i = 1 to r do

{

t = (B × (2B + 1) <<< 5

u = (D × (2D + 1) <<< 5

A = ((A ⊕ t)) <<< u) + S[2i]

C = ((C ⊕ u)) <<< t) + S[2i + 1]

(A, B, C, D) = (B, C, D, A)

}

A = A + S[2r + 2]

C = C + S[2r + 3]

W rzeczywistości proces projektowania nie przebiegał tak prosto. Przeanalizowano dziesiątki alternatywnych rozwiązań, kierując się trzema celami: bezpieczeństwem, prostotą i efektywnością działania.

1. Bezpieczeństwo

Wykazano teoretycznie, że znalezienie klucza pełnego, 20 rundowego szyfru RC6 jest możliwe tylko poprzez brutalne przeszukanie. Znane obecnie bardziej wyrafinowane ataki są praktycznie niewykonalne, co obrazują poniższe wartości.

Odporność na atak metodą kryptoanalizy:

• różnicowej - wymaga zgromadzenia 2²³⁸ par tekst jawny - tekst zaszyfrowany,

• liniowej - potrzebnych jest 2¹⁵⁵ par.

Tak więc liczba danych wymagana do przeprowadzenia tych ataków przekracza liczbę wszystkich dostępnych (możliwych) danych. Nie znaleziono także przykładów kluczy, które można by nazwać „słabymi”.

1. Szybkość implementacji

Od kandydatów zgłoszonych do konkursu AES wymagano implementacji w języku C i Java. Poniżej prezentujemy szybkości działania algorytmu RC6 w zależności od implementacji.

	Java	Borland C	Asembler
Szyfrowanie	0,197 MB/s (1,57 Mb/s)	5,19 MB/s (41,5 Mb/s)	12,6 MB/s (100,8 Mb/s)
Deszyfrowanie	0,194 MB/s (1,55 Mb/s)	5,65 MB/s (45,2 Mb/s)	12,6 MB/s (100,8 Mb/s)

Tabela 3.2. Szybkość przy szyfrowaniu i deszyfrowaniu (procesor 200MHz)

	Java	Borland C	Asembler
Tworzenie podkluczy (RC6-32/20/32)	1820	86956	180500
Szyfrowanie	12300	325000	787000
Deszyfrowanie	12100	353000	788000

Tabela 3.3. Ilość operacji na sekundę (procesor 200MHz)

	Java	Borland C	Asembler
Tworzenie podkluczy (RC6-32/20/32)	110000	2300	1108
Szyfrowanie	16200	616	254
Deszyfrowanie	16500	566	254

Tabela 3.4. Ilość cykli procesora na operację (procesor 200MHz)

Dla porównania prezentujemy zestawienie szybkości działania wszystkich zgłoszonych do AES algorytmów.

Nazwa algorytmu	Tworzenie podkluczy w C	Szyfrowanie w C na Pentium Pro	Szyfrowanie w asemblerze na Pentium Pro	Szyfrowanie w asemblerze na Pentium
CAST-256	4300	660	600	600
Crypton	955	476	345	390
DEAL	4000	2600	2200	2200
DFC	7200	1700	750	?
E2	2100	720	410	410
Frog	1386000	2600	?	?
HPC	120000	1600	?	?
Loki97	7500	2150	?	?
Magenta	50	6600	?	?
Mars	4400	390	320	550
RC6	1700	260	250	550
Rijndael	850	440	291	320
SAFER+	4000	1400	800	1100
Serpent	2500	1030	900	1100
Twofish	8600	400	258	290

Tabela 3.5. Ilość cykli procesora na operację

Jak widać w tym zestawieniu algorytm RC6 wypada bardzo korzystnie.




1. BEZPIECZEŃSTWO SZYFRÓW BLOKOWYCH

Uniwersalną i często jedyną praktyczną metodą ataku na szyfry blokowe jest atak brutalny, czyli pełne przeszukiwanie przestrzeni klucza. Długość klucza wyznacza rozmiar przestrzeni kluczy, które należy przeszukać, prezentuje to poniższa tabela.

Długość klucza w bitach	Liczba możliwych kluczy
40	2^40 = 10^12
56	2^56 = 10^16
64	2^64 = 10^19
80	2^80 = 10^24
112	2^112 = 10^33
128	2^128 = 10^38
256	2^156 = 10^77

Tabela 3.6.

Przewidywane czasy „złamania” za pomocą ataku brutalnego szyfrów blokowych z różnymi długościami kluczy przedstawiają poniższe tabele.

Czas trwania sprzętowego łamania brutalnego (koszt 1 mln USD)

	Długość klucza w bitach
Rok	40	56	64	80	112	128
1995	0,2 s	3,6 godz	38 dni	7 000 lat	10^13 lat	10^18 lat
2000	0,02 s	21 min	4 dni	700 lat	10^12 lat	10^17 lat
2005	2 ms	2 min	9 godz	70 lat	10^11 lat	10^16 lat
2010	0,2 ms	13 s	1 godz	7 lat	10^10 lat	10^15 lat
2015	0,02 ms	1 s	5,5 min	251 dni	10^9 lat	10^14 lat
2020	2 μs	0,1 s	31 min	25 dni	10^8 lat	10^13 lat
2025	0,2 μs	0,01 s	3 s	2,5 dnia	10^7 lat	10^12 lat
2030	0,02 μs	1 ms	0,3 s	6 godz	10^6 lat	10^11 lat

Czas trwania programowego łamania brutalnego (koszt 1 mln USD)

	Długość klucza w bitach
Rok	40	56	64	80	112	128
1995	33 min	3 lata	1000 lat	10^7 lat	10^17 lat	10^22 lat
2000	3,3 min	115 dni	100 lat	10^6 lat	10^16 lat	10^21 lat
2005	20 s	15 dni	10 lat	700 000 lat	10^15 lat	10^20 lat
2010	2 s	1,5 dnia	1 rok	70 000 lat	10^14 lat	10^19 lat
2015	0,2 s	3,6 godz	38 dni	7 000 lat	10^13 lat	10^18 lat
2020	0,02 s	21 min	4 dni	700 lat	10^12 lat	10^17 lat
2025	2 ms	2 min	9 godz	70 lat	10^11 lat	10^16 lat
2030	0,2 ms	13 s	1 godz	7 lat	10^10 lat	10^15 lat

*
i
są łączone i permutowane zgodnie z permutacją końcową IP^-1, będącą odwrotnością permutacji IP. Wynikiem działania IP^-1 jest blok 64 bitowy zwany tekstem tajnym T.


J. Szmidt, M. Misztal - Wstęp do kryptologii

J. Szmidt, M. Misztal - Wstęp do kryptologii

106

105

107

SZYFR BLOKOWY




E

E

E










E

E

E




*

*

Wejście

2 pierwsze podklucze

Operacje początkowe

(xor B i D z podkluczami)




Runda podstawowa




Operacje końcowe

(xor A i C z podkluczami)

Wyjście










E



















Blok szyfrogramu (n bitów)

Blok klucza

(k bitów)

Blok tekstu jawnego (n bitów)

E

E




IV

IV

IV


































+




+

Rys. 3.7. Schemat blokowy algorytmu DES.







+




























2 ostatnie podklucze

2r (40) podkluczy

r (20) rund













E

E

E

---