DES (ang. Data Encryption Standard)

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

Zastosowanie

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.

Algorytm

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.

Klucze słabe w DES

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)

Klucze półsłabe w DES

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 w DES

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.

Siła szyfru DES

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 256 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 243 bloków tekstu jawnego, a ich złożoność obliczeniowa wynosi około 239 do 243.

Schemat Blokowy Algorytmu DES

Schemat blokowy algorytmu DES

Schemat Blokowy funkcji Feistela

Schemat blokowy funkcji Feistela

Schemat Blokowy generowania bitów klucza w DES

Schemat blokowy generowania bitów klucza

Matematyka:

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

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

Tabela permutacji początkowej
585042342618102
605244362820124
625446383022146
645648403224168
57494133251791
595143352719113
615345372921135
635547393123157
Schemat permutacji początkowej
Schemat permutacji początkowej

Permutacja Klucza PC-1

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

Tabela Permutacji PC-1
Lewa część
5749413325179
1585042342618
1025951433527
1911360524436
Prawa część
63554739312315
7625446383022
1466153453729
211352820124
Schemat Permutacji PC-1
Schemat Permutacji PC-1

Permutacja Rozszerzająca

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.

Tabela Permutacji Rozszerzającej
321234545
6789891011
1213121314151617
1617181920212021
2223242524252627
282928293031321
Schemat Permutacji Rozszerzającej
Schemat Permutacji Rozszerzającej

Przesunięcie Bitów Klucza

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

Tabela Przesunięcia Bitów Klucza
Numer cykluIlość bitów
10 
11 
12 
13 
14 
15 
16 

Permutacja Klucza PC-2

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

Tabela Permutacji PC-2
1417112415328
15621102319124
2681672720132
4152313747553040
5145334844493956
3453464250362932
Schemat Permutacji PC-2
Schemat Permutacji PC-2

S-Bloki

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

S1
x0000x
x0001x
x0010x
x0011x
x0100x
x0101x
x0110x
x0111x
x1000x
x1001x
x1010x
x1011x
x1100x
x1101x
x1110x
x1111x
0yyyy01441312151183106125907
0yyyy10157414213110612119538
1yyyy04114813621115129731050
1yyyy11512824917511314100613
S2
x0000x
x0001x
x0010x
x0011x
x0100x
x0101x
x0110x
x0111x
x1000x
x1001x
x1010x
x1011x
x1100x
x1101x
x1110x
x1111x
0yyyy01518146113497213120510
0yyyy13134715281412011069115
1yyyy00147111041315812693215
1yyyy11381013154211671205149
S3
x0000x
x0001x
x0010x
x0011x
x0100x
x0101x
x0110x
x0111x
x1000x
x1001x
x1010x
x1011x
x1100x
x1101x
x1110x
x1111x
0yyyy01009146315511312711428
0yyyy11370934610285141211151
1yyyy0136498153011212510147
1yyyy11101306987415143115212
S4
x0000x
x0001x
x0010x
x0011x
x0100x
x0101x
x0110x
x0111x
x1000x
x1001x
x1010x
x1011x
x1100x
x1101x
x1110x
x1111x
0yyyy07131430691012851112415
0yyyy11381156150347212110149
1yyyy01069012117131513145284
1yyyy13150610113894511127214
S5
x0000x
x0001x
x0010x
x0011x
x0100x
x0101x
x0110x
x0111x
x1000x
x1001x
x1010x
x1011x
x1100x
x1101x
x1110x
x1111x
0yyyy02124171011685315130149
0yyyy11411212471315015103986
1yyyy04211110137815912563014
1yyyy11181271142136150910453
S6
x0000x
x0001x
x0010x
x0011x
x0100x
x0101x
x0110x
x0111x
x1000x
x1001x
x1010x
x1011x
x1100x
x1101x
x1110x
x1111x
0yyyy01211015926801334147511
0yyyy11015427129561131401138
1yyyy09141552812370410113116
1yyyy14321295151011141760813
S7
x0000x
x0001x
x0010x
x0011x
x0100x
x0101x
x0110x
x0111x
x1000x
x1001x
x1010x
x1011x
x1100x
x1101x
x1110x
x1111x
0yyyy04112141508133129751061
0yyyy11301174911014351221586
1yyyy01411131237141015680592
1yyyy16111381410795015142312
S8
x0000x
x0001x
x0010x
x0011x
x0100x
x0101x
x0110x
x0111x
x1000x
x1001x
x1010x
x1011x
x1100x
x1101x
x1110x
x1111x
0yyyy01328461511110931450127
0yyyy11151381037412561101492
1yyyy07114191214206101315358
1yyyy12114741081315129035611

Permutacja w P-Bloku

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

Tabela Permutacji w P-Bloku
167202129122817
11523265183110
282414322739
19133062211425
Schemat Permutacji w P-Bloku
Schemat Permutacji w P-Bloku

Permutacja Końcowa

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

Tabela Permutacji Końcowej
408481656246432
397471555236331
386461454226230
375451353216129
364441252206028
353431151195927
342421050185826
33141949175725
Schemat Permutacji Końcowej
Schemat Permutacji Końcowej