Konspekt:
Realizacja algorytmu DES
Autorzy: Grzegorz Dębiec, Edyta Gąsior, A
ukasz Krzanik, Maciej Tokarczyk DUMF
1
STRESZCZENIE
Konspekt powstał na podstawie wykładu (5 marca 2002) z przedmiotu  Bezpieczeństwo i
ochrona informacji , prowadzonego przez dr inż. Mirosława Hajdera.
Przedstawiona zostanie zasada działania algorytmu DES. Szyfr DES jest algorytmem syme-
trycznym, w którym do szyfrowania i deszyfracji wykorzystuje się jeden i ten sam klucz. Algo-
rytm ten funkcjonuje na ciągach bitowych, szyfruje on liczby binarne 64 bitowe z wykorzysta-
niem 56-cio bitowego klucza.
Politechnika Rzeszowska im. Ignacego A
ukasiewicza
Zakład Systemów Rozproszonych
Rzeszów 2002
2
SPIS TREŚCI
Streszczenie .................................................................................................................................. 1
1 Wprowadzenie ...................................................................................................................... 3
2 Idea algorytmu DES ............................................................................................................. 3
3 Zasada działania ................................................................................................................... 4
3.1 Procedura przygotowania kluczy.................................................................................. 5
3.2 Przygotowywanie bloku danych................................................................................... 8
Literatura .................................................................................................................................... 12
Politechnika Rzeszowska im. Ignacego A
ukasiewicza
Zakład Systemów Rozproszonych
Rzeszów 2002
3
1 WPROWADZENIE
Szyfr DES jest algorytmem symetrycznym, w którym do szyfrowania i deszyfracji wykorzy-
stuje się jeden i ten sam klucz. O zastosowaniu takiego szyfru zdecydowały następujące prze-
słanki:
" Algorytm funkcjonowania był zawsze jawny
" Do realizacji algorytmu wykorzystywane są wyłącznie operacje transpozycji i pod-
stawiania, dzięki czemu algorytm ten jest obliczeniowo prosty
" Dzięki kaskadowości szyfrowania, szyfr ten gwarantował wysoki poziom bezpie-
czeństwa.
Pomimo niewielkiej długości klucza i prostoty realizacji operacji szyfrowania szyfr DES
możemy traktować jako dobry przykład współczesnych algorytmów szyfrowania.
2 IDEA ALGORYTMU DES
Algorytm ten funkcjonuje na ciągach bitowych, szyfruje on liczby binarne 64 bitowe z wy-
korzystaniem 56-cio bitowego klucza.
Operacją szyfrowania jest operacja złożenia po modulo 2 fragmentu tekstu jawnego z frag-
mentem klucza. Operacja ta wykonywana jest na 48 bitowych blokach danych.
Blok danych w celu otrzymania 48 bitowej postaci, podlegającej dalszemu szyfrowaniu,
dzielony jest na dwie równe części po 32 bity każda. Następnie blok taki poddawany jest per-
mutacji rozszerzającej (jest to e permutacja, e wybór).
W każdym z szesnastu kroków szyfrowaniu poddawana jest połowa słowa danych, lewa i
prawa strona szyfrowane są naprzemiennie. 48 bitowy klucz szyfrowania tworzony jest na pod-
stawie przesunięć oraz permutacji zawężającej tworzącej z 56 bitowego klucza 48 bitowy pod-
klucz.
Dla każdej z iteracji szyfrowania tworzony jest oryginalny klucz na bazie przesunięcia cy-
klicznego bitów klucza podstawowego.
Po realizacji szesnastu operacji szyfrujących funkcję szyfrowania kontynuuje się w tzw. s-
boxach pozwalających zamieniać tekst o długości 48 bitów tekstem 32 bitowym.
Operację szyfrowania kończy odwrotność permutacji wstępnej wykonywanej na bloku da-
nych przed rozpoczęciem operacji szyfrowania.
Operacja deszyfracji polega na wykonaniu wszystkich omówionych wyżej operacji w od-
wrotnej kolejności.
Politechnika Rzeszowska im. Ignacego A
ukasiewicza
Zakład Systemów Rozproszonych
Rzeszów 2002
4
3 ZASADA DZIAA
ANIA
Rys. 1. Algorytm DES
Klucz do każdej następnej iteracji przygotowywany jest na podstawie cząstkowo przygoto-
wanego klucza poprzedniej iteracji. Więc chcąc uzyskać klucz drugiej iteracji, koniecznym jest
stworzenie najpierw klucza pierwszej iteracji itd.
Dla każdej operacji szyfrowania tworzony jest własny, prywatny klucz. Przy tym klucz dla i-
tej iteracji wykorzystuje dane przygotowane dla klucza w iteracji i-1. Przygotowanie klucza
oparte jest na wykorzystaniu dwóch operacji:
" transpozycji (permutacji),
" przesunięcia cyklicznego.
Politechnika Rzeszowska im. Ignacego A
ukasiewicza
Zakład Systemów Rozproszonych
Rzeszów 2002
5
Przygotowanie danych realizowane jest z wykorzystaniem operacji permutacji oraz podziału
bloku danych na dwie równe części. Na każdej z szesnastu iteracji szyfrowania odbywa się z
wykorzystaniem sumy symetrycznej.
Operacje końcowe przywracają danym podlegającym szyfrowaniu postać 64 bitową.
3.1 Procedura przygotowania kluczy
Rys. 2. Procedura przygotowania kluczy
Pierwszym krokiem tworzenia klucza jest permutowany wybór PC 1. Bardzo często zdarza
się, że zarówno blok danych jak i blok klucza jest w algorytmie DES 64-ro bitowy, co wcale
nie oznacza, że do szyfrowania korzystamy z klucza 64-ro bitowego. Korzystamy nadal z klu-
cza 56-cio bitowego, jednak co ósmy bit jest odrzucany. Bit ten w związku z tym można wyko-
rzystać w różny sposób, np. do kontroli parzystości i dzięki temu sprawdzać czy klucz został
przesłany poprawnie. Permutacja PC-1 dokonuje odrzucenia co ósmego bitu.
Kolejnym działaniem jest transpozycja w ściśle określonym porządku.
Politechnika Rzeszowska im. Ignacego A
ukasiewicza
Zakład Systemów Rozproszonych
Rzeszów 2002
6
Rys. 3. Permutowany wybór PC-1
Należy zwrócić uwagę na to, że na wejściu nie ma co ósmego bitu. Tajemnicą autorów algo-
rytmu DES pozostaje odpowiedz
na pytanie, dlaczego zastosowano właśnie taki sposób prze-
stawień i czy od niego zależy moc szyfrowania. Jednak prawdopodobnie nie ma on większego
znaczenia.
Następnym krokiem jest cykliczne przesunięcie w lewo.
Rys. 4. Rozdzielenie 56 bitowego klucza na dwie części,
cykliczne przesunięcia w lewo i odrzucenie co ósmego bitu
Klucz 56 bitowy zostaje rozdzielony na dwie części  prawą i lewą. Następnie każdą z tych
części przesuwamy o pewną liczbę bitów w lewo. W rezultacie tego przesunięcia otrzymujemy
nowe wartości prawej i lewej części klucza. Póz
niej obie części klucza zostają scalone i podda-
ne operacji permutowanego wyboru 2.
Cykliczne przesunięcie w lewo realizowane jest z pomocą specjalnej tablicy określającej o
ile bitów będzie następować przesunięcie w każdej z iteracji. Przy czym w każdej następnej ite-
racji przesunięciu zostaje poddana ta część, która została przesunięta w operacji poprzedniej.
Czyli np. w iteracji nr 3 mamy sumę przesunięć w iteracjach 1,2 i 3.
Po realizacji permutowanego wyboru 1, 56-bitowy klucz rozbijany jest na dwie równe czę-
ści, każda z nich przesuwana jest o liczbę bitów określoną w tablicy przesunięcia bitów klucza.
Kolejne działanie związane jest z realizacją permutowanego wyboru 2.
Politechnika Rzeszowska im. Ignacego A
ukasiewicza
Zakład Systemów Rozproszonych
Rzeszów 2002
7
Rys. 5. Permutowany wybór PC-2
Operacja szyfrowania w algorytmie DES realizowana jest na bazie sumy symetrycznej (czyli
sumy po modulo 2) dwóch ciągów bitowych o długości 48 bitów. Należy zwrócić uwagę na to,
że klucz początkowo miał długość 64 bity, następnie co ósmy bit został odrzucony i otrzymali-
śmy klucz 56 bitowy. Póz
niej klucz ten został podzielony na pół, co spowodowało powstanie
dwóch podkluczy 28-bitowych. Podklucze te zostały następnie cyklicznie przesunięte w lewo i
z powrotem połączone, w wyniku czego został uzyskany nowy klucz 56 bitowy. Więc zada-
niem permutacji PC-2 jest nie tylko przestawienie bitów, ale również zrobienie z 56 bitowego
klucza podstawowego, 48 bitowego klucza iteracji.
Należy zwrócić uwagę na to, że w przypadku wejścia w kilku przypadkach jest powtórzony
bit, natomiast cyfr wyjściowych jest 48. Dzięki temu na każdej iteracji powstaje oryginalny 48
bitowy klucz.
Rys. 6. Szyfrowanie połowy bloku danych - rozszerzenie
i zastosowanie sumy symetrycznej
Blok danych w algorytmie DES mający długość 64 bity jest dzielony na dwie połowy po 32
bity. W każdym kroku szyfrowania dokonywane jest wyłącznie szyfrowanie prawej części, le-
wa część jest pozostawiana bez zmian, przy czym podczas przejścia do każdego następnego
kroku lewa strona zamienia się ze stroną prawą. Znaczy to, że jeżeli w pierwszym kroku szy-
frujemy stronę prawą to w drugim szyfrujemy stronę lewą, która została przesunięta tym razem
na prawą stronę. W ten sposób w szesnastu iteracjach, osiem razy szyfrujemy stronę prawą i
osiem razy stronę lewą. Należy zwrócić uwagę, że w tym przypadku mamy podzielony już blok
na dwie części  lewą i prawą. Prawa część jest poddawana rozszerzeniu, ponieważ operacja
sumy symetrycznej jest operacją, która może być wykonywana na argumentach o tej samej
długości. Jeżeli mamy już klucz 48 bitowy, również argument podlegający szyfrowaniu (dane)
musi być rozszerzony do długości 48 bitów. W rezultacie tego otrzymywana jest suma syme-
tryczna o długości 48 bitów.
Politechnika Rzeszowska im. Ignacego A
ukasiewicza
Zakład Systemów Rozproszonych
Rzeszów 2002
8
3.2 Przygotowywanie bloku danych
Po realizacji permutacji wstępnej blok danych dzielony jest na dwie równe części, na każdej
z iteracji szyfrowaniu podlega wyłącznie prawa część bloku danych. Ponieważ jest ona równa
32 bity a długość klucza iteracji równa jest 48 bitów, część bloku danych podlega rozszerzeniu
z pomocą funkcji rozszerzającej (permutacji z rozszerzeniem).
Rys. 7. Permutacja wstępna bloku danych
Rys. 8. Permutacja rozszerzająca
Należy zwrócić uwagę na to, że wejście ma tylko 32 bity, a wyjście 48 bitów. Niektóre bity
występują dwukrotnie (np. bit 17 lub 32), rozszerzenie następuje, więc przez dwukrotne wyko-
rzystanie niektórych bitów wejściowych i umieszczenie ich na wyjściu. Po tej operacji mamy
48 bitowy blok danych i 48 bitowy klucz, w tej sytuacji wystarczy tylko przeprowadzić opera-
cję sumy symetrycznej.
Politechnika Rzeszowska im. Ignacego A
ukasiewicza
Zakład Systemów Rozproszonych
Rzeszów 2002
9
Wyniku przeprowadzenia operacji sumy symetrycznej otrzymujemy 48 bitowy blok zaszy-
frowanych danych. Następnie rozpoczyna się podstawienie w S-bloku jest to operacja polega-
jącą na tym, że wyciągamy z 32 bity z 48 bitowego bloku danych. Operacja ta musi być wyko-
nana, ponieważ należy złożyć 64 bitowy blok danych. 32 bity pochodzić będzie z bloku który
nie był szyfrowany a kolejne 32 bity należy odzyskać z 48 bitowej sumy symetrycznej. Na ko-
niec następuje permutacja P-bloku, czyli końcowe przestawienie w ramach pewnej iteracji.
Rys. 9. Schemat pojedynczego cyklu algorytmu DES
W rezultacie realizacji operacji sumy symetrycznej otrzymujemy 48 bitowy blok zaszyfro-
wanych danych, natomiast rezultatem działania algorytmu ma być 64 bitowy blok zaszyfrowa-
nych danych. Uzyskuje się to w ten sposób, że wydziela się spośród wspomnianych 48 bitów 8
bloków 6 bitowych. Bloki te noszą nazwę S-bloków. Korzystając ze specjalnej tablicy permu-
towanego wyboru S-bloków, (tablica ma 4 wiersze i 16 kolumn) z każdego S-bloku (6-
bitowego) bierzemy pierwszy i ostatni bit traktując je jako adres wiersza (czyli mamy możli-
wość podania czterech wierszy) oraz bierzemy pozostałe 4 środkowe bity celem adresowania
kolumn (16 kolumn). Mając zawarty w S-bloku konkretny adres w tablicy, znajdujemy w niej
konkretną liczbę 4 bitową. Zwróćmy więc uwagę na to, że z ośmiu bloków 6 bitowych otrzy-
mujemy 8 bloków 4 bitowych. W ten właśnie sposób zmniejszamy liczbę bitów w zaszyfrowa-
nym bloku z 48 do 32.
Politechnika Rzeszowska im. Ignacego A
ukasiewicza
Zakład Systemów Rozproszonych
Rzeszów 2002
10
Rys. 10. Odzyskanie 32-bitowej struktury połowy zaszyfrowanego bloku danych
po operacji sumy symetrycznej
Politechnika Rzeszowska im. Ignacego A
ukasiewicza
Zakład Systemów Rozproszonych
Rzeszów 2002
11
Rys. 11. Tablica permutacji S-bloku
Permutacja P-bloku  permutowany jest blok 32 bitowy.
Politechnika Rzeszowska im. Ignacego A
ukasiewicza
Zakład Systemów Rozproszonych
Rzeszów 2002
12
W ostatnim kroku tzw. odwrotności permutacji wstępnej, wykonywane jest dokładnie od-
wrotne przestawienie do wykonywanego na początku.
Rys. 12. Odwrotna permutacja wstępna bloku danych
LITERATURA
[1] William Stallings  Ochrona danych w sieci i intersieci w teorii i praktyce WNT War-
szawa, 1997,
[2] Strona WWW autorów konspektu: http://city.net.pl/editha/
Politechnika Rzeszowska im. Ignacego A
ukasiewicza
Zakład Systemów Rozproszonych
Rzeszów 2002