Algorytm DES został opracowany przez
firmę IBM w latach 70-tych na bazie algorytmu Lucifer Horsta Feistela.
W roku 1977 Narodowe Biuro Standardów USA zaakceptowało ten algorytm jako
standard szyfrowania danych nie utajnionych przez agencje rządowe. Obecnie
DES jest jednym z najbardziej rozpowszechnionych algorytmów szyfrujących.
W algorytmie szyfrowane są 64-bitowe bloki danych 56-bitowym kluczem.
Algorytm przedstawiono na Rys.1. Blok
wejściowy M jest najpierw przekształcany w permutacji początkowej IP dając
M0 = IP(M). Następnie M0 jest podawane na wejście pierwszej spośród
16 iteracji specjalnej funkcji F. Rezultat 16 iteracji funkcji F jest poddawany
permutacji IP-1 (jest to permutacja odwrotna do IP). Permutacje IP i IP-1
są przedstawione na rys.2. (Tablice permutacji należy czytać począwszy
od pierwszej kolumny i pierwszego rzędu, od lewej do prawej, od góry do
dołu; na przykład w IP pierwszy bit wejścia jest przesuwany na pozycję
58 na wyjściu, drugi bit na pozycję 51, itd.) Pomiędzy permutacjami
IP i IP-1 w algorytmie wykonywane jest 16 iteracji funkcji F łączącej podstawienia
i permutacje. Niech Xi oznacza rezultat i-tej iteracji, a Li i Ri odpowiednio
jego lewą i prawą połowę, czyli Xi = LiRi, gdzie:
Li = t1, ..., t32
Ri = t33, ..., t64.
Rys.1.Alogorymt DES
..: Powiększ :..
Zachodzi:
Li = Ri-1
Ri = Li-1 ? F(Ri-1,Ki),
gdzie Ki jest 48-bitowym kluczem
iteracyjnym opisanym dalej. Zauważmy, że po ostatniej iteracji lewa i prawa
połowa są zamieniane, a otrzymany blok R16L16 jest wejściem dla permutacji
IP-1. Jest to konieczne, aby algorytm mógł być użyty zarówno do szyfrowania,
jak i deszyfrowania.
Rys.2.Permutacje IP i IP-1.
..: Powiększ :..
Rys.3.Funkcja F DES.
..: Powiększ :..
Na Rys.3 przedstawiono funkcję F.
Najpierw Ri-1 jest rozszerzane do 48-bitowego bloku E(Ri-1)
przy użyciu tablicy wyboru bitów E, przedstawionej na Rys.4. Tablica ta
jest używana w ten sam sposób, co tablice permutacji, z wyjątkiem tego,
że kilka bitów Ri-1 jest wybranych więcej niż raz; tak więc
dla Ri-1 = r1, r2, ..., r32, E(Ri-1) = r32, r1, r2, ..., r32, r1.
Rys.4.Rozszerzenie E.
..: Powiększ :..
Każdy 6-bitowy blok Bj, i=1,2,...,8,
jest następnie używany jako wejście do skrzynki
podstawieniowej Sj, która na wyjściu
daje 4-bitowy blok Sj(Bj). Bloki te są łączone razem i
otrzymany 32-bitowy blok wynikowy
jest przetwarzany w permutacji P opisanej na Rys.5.
Rys.5.Permutacja P.
..: Powiększ :..
S1
|
Rząd
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
|
0
|
14
|
4
|
13
|
1
|
2
|
15
|
11
|
8
|
3
|
10
|
6
|
12
|
5
|
9
|
0
|
7
|
|
1
|
0
|
15
|
7
|
4
|
14
|
2
|
13
|
1
|
10
|
6
|
12
|
11
|
9
|
5
|
3
|
8
|
|
2
|
4
|
1
|
14
|
8
|
13
|
6
|
2
|
11
|
15
|
12
|
9
|
7
|
3
|
10
|
5
|
0
|
|
3
|
15
|
12
|
8
|
2
|
4
|
9
|
1
|
7
|
5
|
11
|
3
|
14
|
10
|
0
|
6
|
13
|
S2
|
Rząd
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
|
0
|
15
|
1
|
8
|
14
|
6
|
11
|
3
|
4
|
9
|
7
|
2
|
13
|
12
|
0
|
5
|
10
|
|
1
|
3
|
13
|
4
|
7
|
15
|
2
|
8
|
14
|
12
|
0
|
1
|
10
|
6
|
9
|
11
|
5
|
|
2
|
0
|
14
|
7
|
11
|
10
|
4
|
13
|
1
|
5
|
8
|
12
|
6
|
9
|
3
|
2
|
15
|
|
3
|
13
|
8
|
10
|
1
|
3
|
15
|
4
|
2
|
11
|
6
|
7
|
12
|
0
|
5
|
14
|
9
|
S3
|
Rząd
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
|
0
|
10
|
0
|
9
|
14
|
6
|
3
|
15
|
5
|
1
|
13
|
12
|
7
|
11
|
4
|
2
|
8
|
|
1
|
13
|
7
|
0
|
9
|
3
|
4
|
6
|
10
|
2
|
8
|
5
|
14
|
12
|
11
|
15
|
1
|
|
2
|
13
|
6
|
4
|
9
|
8
|
15
|
3
|
0
|
11
|
1
|
2
|
12
|
5
|
10
|
14
|
7
|
|
3
|
1
|
10
|
13
|
0
|
6
|
9
|
8
|
7
|
4
|
15
|
14
|
3
|
11
|
5
|
2
|
12
|
S4
|
Rząd
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
|
0
|
7
|
13
|
14
|
3
|
0
|
6
|
9
|
10
|
1
|
2
|
8
|
5
|
11
|
12
|
4
|
15
|
|
1
|
13
|
8
|
11
|
5
|
6
|
15
|
0
|
3
|
4
|
7
|
2
|
12
|
1
|
10
|
14
|
9
|
|
2
|
10
|
6
|
9
|
0
|
12
|
11
|
7
|
13
|
15
|
1
|
3
|
14
|
5
|
2
|
8
|
4
|
|
3
|
3
|
15
|
0
|
6
|
10
|
1
|
13
|
8
|
9
|
4
|
5
|
11
|
12
|
7
|
2
|
14
|
S5
|
Rząd
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
|
0
|
2
|
12
|
4
|
1
|
7
|
10
|
11
|
6
|
8
|
5
|
3
|
15
|
13
|
0
|
14
|
9
|
|
1
|
14
|
11
|
2
|
12
|
4
|
7
|
13
|
1
|
5
|
0
|
15
|
10
|
3
|
9
|
8
|
6
|
|
2
|
4
|
2
|
1
|
11
|
10
|
13
|
7
|
8
|
15
|
9
|
12
|
5
|
6
|
3
|
0
|
14
|
|
3
|
11
|
8
|
12
|
7
|
1
|
14
|
2
|
13
|
6
|
15
|
0
|
9
|
10
|
4
|
5
|
3
|
S6
|
Rząd
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
|
0
|
12
|
1
|
10
|
15
|
9
|
2
|
6
|
8
|
0
|
13
|
3
|
4
|
14
|
7
|
5
|
11
|
|
1
|
10
|
15
|
4
|
2
|
7
|
12
|
9
|
5
|
6
|
1
|
13
|
14
|
0
|
11
|
3
|
8
|
|
2
|
9
|
14
|
15
|
5
|
2
|
8
|
12
|
3
|
7
|
0
|
4
|
10
|
1
|
13
|
11
|
6
|
|
3
|
4
|
3
|
2
|
12
|
9
|
5
|
15
|
10
|
11
|
14
|
1
|
7
|
6
|
0
|
8
|
13
|
S7
|
Rząd
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
|
0
|
4
|
11
|
2
|
14
|
15
|
0
|
8
|
13
|
3
|
12
|
9
|
7
|
5
|
10
|
6
|
1
|
|
1
|
13
|
0
|
11
|
7
|
4
|
9
|
1
|
10
|
14
|
3
|
5
|
12
|
2
|
15
|
8
|
6
|
|
2
|
1
|
4
|
11
|
13
|
12
|
3
|
7
|
14
|
10
|
15
|
6
|
8
|
0
|
5
|
9
|
2
|
|
3
|
6
|
11
|
13
|
8
|
1
|
4
|
10
|
7
|
9
|
5
|
0
|
15
|
14
|
2
|
3
|
12
|
S8
|
Rząd
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
|
0
|
13
|
2
|
8
|
4
|
6
|
15
|
11
|
1
|
10
|
9
|
3
|
14
|
5
|
0
|
12
|
7
|
|
1
|
1
|
15
|
13
|
8
|
10
|
3
|
7
|
4
|
12
|
5
|
6
|
11
|
0
|
14
|
9
|
2
|
|
2
|
7
|
11
|
4
|
1
|
9
|
12
|
14
|
2
|
0
|
6
|
10
|
13
|
15
|
3
|
5
|
8
|
|
3
|
2
|
1
|
14
|
7
|
4
|
10
|
8
|
13
|
15
|
12
|
9
|
0
|
3
|
5
|
6
|
11
|
Każda skrzynka podstawieniowa Sj
przekształca
6-bitowy blok
Bj = b1, b2, b3, b4, b5, b6 w blok 4-bitowy zgodnie
z tablicami podstawień przedstawionymi na Rys.6. Wykonywane jest to następująco:
liczba całkowita utworzona z dwóch skrajnych bitów słowa Bi czyli
b1, b6 wybiera rząd w tabeli, podczas gdy liczba utworzona ze środkowych
bitów Bi b2, b3, b4, b5 wybiera kolumnę. Wartość Sj(Bj)
jest wtedy 4-bitową reprezentacją liczby całkowitej w tym rzędzie i kolumnie.
Jeżeli na przykład B1 = 011100,
to S1 zwraca wartość z rzędu 0, kolumny 14; jest to 0, które będzie
przedstawione jako 0000.
W i-tej iteracji algorytmu DES używany
jest 48-bitowy klucz Ki, wyprowadzony z 56-bitowego klucza głównego
w algorytmie generowania kluczy iteracyjnych. Na Rys.15 przedstawiono sposób,
w jaki jest to realizowane. Wejściem jest 64-bitowy klucz główny K (bity
8,16,24,32,40,48,56,64 to bity parzystości; są one odrzucane, a wykorzystywanych
jest pozostałych 56 bitów). Permutacja PC1 odrzuca bity parzystości i przenosi
pozostałe bity tak, jak Rys.15. jest to pokazane na Rys.16.
Rys.15
..: Powiększ :..
Rezultat PC1(K) jest następnie
dzielony na połówki używane do generowania kluczy Ki. Oznaczmy
przez Ci i Di odpowiednio lewą i prawą połówkę używaną
do generowania klucza i-tej iteracji Ki. Zachodzi:
Ci = LSi(Ci-1),
Di = LSi(Di-1),
i=1,2,...,16
gdzie RLi jest rotacją w lewo
(cyklicznym przesunięciem w lewo) o liczbę pozycji zgodnie z tabelą na
Rys.17, a C0 i D0 wartościami na wyjściu permutacji PC1. Klucz
Ki jest dany przez
Ki = PC2(Ci, Di)
gdzie PC-2 jest permutacją przedstawioną na Rys.18.
Rys.16.Permutacja klucza PC1.
..: Powiększ :..
Rys.17.Rozkład klucza lewych zmian LS.
..: Powiększ :..
Rys.18.Permutacja klucza PC-2.
..: Powiększ :..
Deszyfrowanie jest realizowane przy pomocy
tego samego algorytmu, z tą różnicą, że klucze iteracyjne są używane w
odwrotnej kolejności, tzn. K16 zostaje użyty w pierwszej iteracji, K15
w drugiej, itd.. Istotne, że zmieniana jest tylko kolejność kluczy, podczas
gdy algorytm pozostaje ten sam.
Źródło:
http://www.bezpieczenstwoit.pl/Artykuly/ Kryptografia/Redakcja,Algorytm_DES/index.html
|
