Crypto-IT

• Długość bloku = 64 bitów
• Długość klucza = 56 bitów

DES był jednym z najpopularniejszych blokowych szyfrów symetrycznych. Wynaleziony we wczesnych latach '70 w IBM, został uznany przez NBS za standard federalny w USA w 1976 roku.

DES został uznany za standard ANSI dla sektora prywatnego w roku 1981. Znany był wtedy pod nazwą Data Encryption Algorithm.

Od pierwszych lat dwudziestego pierwszego wieku uznawany jest za szyfr, który nie jest w stanie zapewnić odpowiedniego zabezpieczenia, głównie ze względu relatywnie krótki sekretny klucz, podatny na ataki siłowe (ang. brute force attacks). W 2001 roku został zastąpiony przez AES, który otrzymał miano standardowego szyfru dla sektora prywatnego. DES jest wciąż jednym z najlepiej zbadanych i najpopularniejszych algorytmów szyfrujących.

W algorytmie DES do szyfrowania i deszyfrowania danych wykorzystywanych jest 56 bitów klucza. Klucz jest zapisywany w postaci 64 bitowego ciągu, w którym co 8 bit jest bitem kontrolnym i może służyć do kontroli parzystości.

W procesie szyfrowania dane wejściowe (tekst jawny) dzielone są na bloki 64-bitowe. Następnie dla każdego bloku wykonywane są następujące operacje:

1. Permutacja początkowa bloku przestawiająca bity w pewien z góry określony sposób. Krok ten nie zwiększa bezpieczeństwa algorytmu. Miał za zadanie ułatwić wprowadzanie danych do maszyn szyfrujących używanych w czasach powstania szyfru.
2. Podzielenie bloku wejściowego danych na dwie 32-bitowe części: lewą oraz prawą.
3. Wybranie 56 bitów z 64-bitowego sekretnego klucza (Permutacja PC-1), a następnie podzielenie tych bitów na dwie 28-bitowe części.
4. Powtórzenie 16 razy tych samych operacji, nazywanych funkcjami Feistela, przy użyciu przekazanego klucza:
   1. Bity klucza są przestawiane w połówkach w lewo o jedną lub dwie pozycje, a następnie w Permutacjach PC-2 wybieranych jest 48 z 56 bitów klucza.
   2. Prawa część danych rozszerzana jest do 48-bitów za pomocą Permutacji Rozszerzającej.
   3. Powiększona prawa połowa danych jest łączona za pomocą operacji XOR z wybranymi wcześniej 48 bitami klucza.
   4. Zsumowane dane dzielone są na osiem 6-bitowych bloków i każdy blok podawany jest na wejście jednego z S-bloków (pierwszy 6-bitowy blok na wejście pierwszego S-bloku, drugi 6-bitowy blok na wejście drugiego S-bloku, itd.). Pierwszy i ostatni bit danych określa wiersz, a pozostałe cztery bity wskazują kolumnę w tabeli S-Bloku. Po wyznaczeniu właściwej pozycji w tabeli, odczytuje się wynikową wartość i zamienia liczbę na zapis dwójkowy. Wynikiem działania każdego S-Bloku są 4 bity wyjściowe. Wszystkie wyjścia z S-Bloków tworzą 32-bitową tablicę. Każdy S-Blok ma inną strukturę.
   5. Dane wyjściowe z S-Bloków są łączone i poddawane permutacji w P-Blokach.
   6. Bity tak przekształconej prawej połowy danych dodawane są do bitów lewej połowy danych.
   7. Zmieniona lewa połowa danych staje się nową prawą połową, natomiast poprzednia prawa połowa staje się nową lewą połową.
5. Po wykonaniu wszystkich 16 powtórzeń funkcji Feistela, lewa i prawa połowa danych jest łączona za pomocą sumowania XOR.
6. Przeprowadzana jest Permutacja Końcowa.

Deszyfrowanie w DES polega na zastosowaniu tych samych operacji w odwrotnej kolejności. Jedyną różnicą jest to, że podklucze, które teraz należy wybierać od końca.

Klucz słaby w algorytmie DES to klucz, który powoduje generowanie takich samych podkluczy w kolejnych cyklach algorytmu szyfrującego. W DES znane są 4 klucze słabe. W zapisie heksadecymalnym klucze słabe są następujące:

• 0x00000000000000 (same zera)
• 0xFFFFFFFFFFFFFF (same jedynki)
• 0x0000000FFFFFFF (połowa zer i połowa jedynek)
• 0xFFFFFFF0000000 (połowa jedynek i połowa zer)

Klucz półsłaby w algorytmie DES to klucz, dla którego można znaleźć inny klucz, który z danego tekstu jawnego tworzy taki sam tekst zaszyfrowany. W DES znanych jest 12 kluczy półsłabych. Są one przedstawione heksadecymalnie poniżej, zapisane razem z bitami parzystości:

• 0x01E001E001F101F1 i 0xE001E001F101F101
• 0xFE01FE01FE01FE01 i 0x01FE01FE01FE01FE
• 0x1FE01FE00EF10EF1 i 0xE01FE01FF10EF10E
• 0xE0FEE0FEF1FEF1FE i 0xFEE0FEE0FEF1FEF1
• 0x1F011F010E010E01 i 0x011F011F010E010E
• 0xFE1FFE1FFE0EFE0E i 0x1FFE1FFE0EFE0EFE

Permutacje Początkowa i Końcowa nie mają wpływu na bezpieczeństwo. Nie bierze w nich udziału sekretny klucz, więc każdy może je przeprowadzić lub cofnąć na własną rękę. Zostały wprowadzone, aby ułatwić sprzętowe przetwarzanie 64 bitów bloków danych. W czasach kiedy powstał standard DES w użyciu były 8-bitowe szyny danych, które przekazywały dane do ośmiu rejestrów przesuwnych co było bardziej wydajne niż jeden rejestr 64-bitowy. Proces obsługi 8 rejestrów 8-bitowych w sposób naturalny odwzorowywał początkową permutację w DES.

Poniżej bardziej szczegółowy opis dla zainteresowanych.

Weźmy układ elektroniczny, którego zadaniem jest zaszyfrowanie za pomocą DES danych otrzymywanych w ośmiobitowych blokach. Oznacza to, że magistrala danych ma szerokość 8 linii (ma 8 równoległych ścieżek, po których przesyłane są dane), z których każda w każdym cyklu zegara dostarcza jeden bit danych. Zazwyczaj do odbierania danych stosuje się rejestry przesuwne: linia wejściowa jest połączona z jednobitowym rejestrem, który jest połączony do kolejnego jednobitowego rejestru i tak dalej. W każdym cyklu zegara każdy jednobitowy rejestr otrzymuje zawartość poprzedniego rejestru, a pierwszy rejestr przyjmuje nowy bit danych. Jak widać, zawartość jest więc przesuwana.

W przypadku 8-bitowej szyny danych, potrzebnych jest 8 rejestrów przesuwnych, z których każdy otrzyma po 8 bitów z bloku DES. Pierwszy rejestr otrzyma bity o numerach 1, 9, 17, 25, 33, 41, 49 i 57, drugi rejestr otrzyma bity o numerach 2, 10, 18, ... i tak dalej. Po ośmiu cyklach zegara, odebrany będzie cały 64 bitowy blok i nastąpi jego przekazanie do układu szyfrującego za pomocą algorytmu DES.

Jeśli nie byłoby Permutacji Początkowej, wtedy pierwszym krokiem pierwszego cyklu szyfrowania byłoby wydzielenie "lewej połowy" danych (32 bity), która składałaby się z 4 najbardziej lewych bitów każdego z ośmiu rejestrów przesuwnych. "Prawa połowa" również otrzymałaby bity ze wszystkich 8 rejestrów przesuwnych. Należałoby poprowadzić ścieżki łączące odpowiednie bity z rejestrów przesuwnych z elementami, które będą ich potem używać. Linie te przecinałyby się w wielu miejscach, co znacznie skomplikowałoby cały układ i podniosło koszty jego wykonania.

Z drugiej strony, jeśli bity wyjściowe z rejestrów przesuwnych podda się Permutacji Początkowej DES, okaże się, że linie łączące je z dalszymi elementami znacznie się uprościły i przestały się przecinać. Innymi słowy, bity przechowywane w wejściowych rejestrach przesuwnych są już wewnętrznie posortowane w ten sposób, że odwzorowują permutację początkową z algorytmu DES. Dzięki zdefiniowaniu permutacji początkowej, bity wejściowe w sprzętowej implementacji DES mogą być brane do szyfrowania w takiej kolejności w jakiej znajdują się już w wejściowych rejestrach przesuwnych.

Analogiczna sytuacja ma miejsce na końcu algorytmu, przy okazji przeprowadzania Permutacji Końcowej.

Trzeba pamiętać, że DES został zaprojektowany w czasach, kiedy nie były używane szyny o szerokości większej niż 8 bitów, a liczba tranzystorów rzędu tysiąca była olbrzymie drogą ilością logiki.

DES jest dobrze zaprojektowanym i efektywnym algorytmem. Już w momencie jego powstawania, wielu kryptografów twierdziło, że długość jego klucza jest za mała. Obecnie klucz o długości 56 bitów może zostać odkryty za pomocą ataku siłowego (ang. brute force) w ciągu paru dni, relatywnie niskim kosztem.

Atak na szyfr DES bardzo ułatwia znajomość fragmentu tekstu jawnego. Napastnik sprawdza wszystkie 2⁵⁶ kluczy i szuka takiego, dla którego blok znanego tekstu jawnego jest równy tekstowi otrzymanemu w danej próbie. W praktyce wystarczy znajomość zawartości dwóch lub trzech bloków tekstu jawnego, aby po odnalezieniu klucza, który przekształca znane szyfrogramy w takie same bloki tekstu jawnego, mieć pewność, że jest to poprawny sekretny klucz (ponieważ prawdopodobieństwo, że jest to niepoprawny klucz, który akurat dla tych konkretnych bloków zwraca poprawne wartości jest pomijalnie małe).

Najszybsze znane obecnie ataki na DES opierają się na kryptoanalizie liniowej. Wymagają znajomości 2⁴³ bloków tekstu jawnego, a ich złożoność obliczeniowa wynosi około 2³⁹ do 2⁴³.

Permutacje są prezentowane za pomocą tabel w celu umożliwienia łatwiejszej prezentacji przekształceń. Należy mieć na uwadze, że dane wejściowe są wektorem, nie macierzą. Kliknij aby dowiedzieć się więcej o czytaniu tabeli permutacji.

Permutacja Początkowa przeprowadzana jest na każdym bloku danych wejściowych na początku procesu szyfrowania.

Schemat permutacji początkowej

Wybranie 56 z 64 bitów klucza, a następnie podzielenie ich na dwie części w celu dokonania niezależnych cyklicznych przesunięć bitów (co ósmy bit z 64 bitów klucza nie bierze udziału w szyfrowaniu i może być używany do kontroli poprawności klucza).

Schemat Permutacji PC-1

Permutacja Rozszerzająca następuje na początku każdego cyklu funkcji Feistela i polega na rozszerzeniu prawej połowy danych z 32 bitów do 48 bitów.

Schemat Permutacji Rozszerzającej

W każdym cyklu funkcji Feistela dokonywane jest przesunięcie każdej 28-bitowej połówki klucza w lewo o jeden lub dwa bity.

Wybiera 48 z 56 bitów aktualnego klucza, otrzymanego dla każdego cyklu funkcji Feistela.

Schemat Permutacji PC-2

Podczas szyfrowania w S-Blokach ma miejsce operacja podstawiania: za każde sześć bitów wejściowych podstawia się cztery bity wyjściowe.

Jeżeli bity wejściowe oznaczy się kolejno jako a1, a2, a3, a4, a5 i a6, to bity a1 i a6 tworzą 2-bitową liczbę określającą wiersz, natomiast bity a2, a3, a4 oraz a5 tworzą liczbę 4-bitową określającą kolumnę (zarówno kolumny jak i wiersze numeruje się od zera). Na przecięciu określonego w ten sposób wiersza i kolumny znajduje się liczba wyjściowa bloku. Przykładowo, jeżeli na wejście pierwszego S-Bloku podamy następujący ciąg bitów: 101010 to liczbą wyjściową będzie 6 (czyli 0110 w zapisie bitowym).

Permutacja w P-Bloku następuje po wyjściu danych (32 bitów) z S-Bloku.

Schemat Permutacji w P-Bloku

Permutacja Końcowa przeprowadzana jest dla każdego bloku po ostatnim cyklu funkcji Feistela. Jest odwrotnością permutacji początkowej.

Schemat Permutacji Końcowej