Kryptografia
Algorytmy symetryczne
dr Robert Borowiec
Politechnika Wrocławska
Instytut Telekomunikacji i Akustyki
pokój 908, C-5
tel. [phone]
Wykład VII
e-mail: [e-mail]
www: lstwww.ita.pwr.wroc.pl/~RB/
2-godziny
Duże liczby
Wiek naszej planety 230 lat = 255 s
Wiek wszechświata 234 lat = 259 s
Liczba atomów w planecie 2170 sztuk
Liczba atomów w Słońcu 2190 sztuk
Liczba atomów w galaktyce 2223 sztuk
Liczba atomów we wszechświecie
2265 sztuk
(Å‚Ä…cznie z  czarna materiÄ…
Objętość wszechświata 2280 cm3
© Robert Borowiec Kryptografia, WykÅ‚ad VII Strona2/42
Najważniejsze znane algorytmy
symetryczne
DES (ang. Data Encryption Standard)
AES (ang. Advanced Encryption
Standard)-od 2001 roku nowy standard
szyfrowania informacji poufnych
IDEA (ang. International Data Encryption
Algorithm)
© Robert Borowiec Kryptografia, WykÅ‚ad VII Strona3/42
Inne znane algorytmy symetryczne
Lucifer
RC-2
Madrygi
RC-3
NewDes
RC-5
Feal-N
SAFER
Redoc
SkipJack
Loki
Khuru i Khafre
MMB
CA-1.1
© Robert Borowiec Kryptografia, WykÅ‚ad VII Strona4/42
Algorytm DES
ang. Data Encryption Standard
W 1977 r Narodowe Biuro Normalizacji USA
przyjęło standard szyfrowania danych.
Algorytm szyfrowania informacji DES powstał
w firmie IBM i jest rozwinięciem szyfru
LUCIFER.
Algorytm ma zastosowanie do przesyłania
informacji poufnych. Szyfr Lucifer, protoplasta
szyfru DES pracował z kluczem 128 bitowym.
W standardzie DES przyjęto efektywny klucz 56
bitowy.
© Robert Borowiec Kryptografia, WykÅ‚ad VII Strona5/42
Algorytm DES
ang. Data Encryption Standard
Jest to szyfr blokowy wykonujÄ…cy operacje
podstawienia oraz permutacje na 64 bitowych blokach
danych wejściowych.
Algorytm służy do szyfrowania jak i deszyfrowania
informacji. Zmienia się tylko kolejność podkluczy.
Do szyfrowania informacji używa się 16 podkluczy 48
bitowych, które są generowane na podstawie 64
bitowego klucza wejściowego. Przy czym efektywny
klucz jest 56 bitowy, gdyż co 8 bit klucza wejściowego
jest bitem parzystości.
© Robert Borowiec Kryptografia, WykÅ‚ad VII Strona6/42
Ogólny schemat blokowy algorytmu
Te ks t ja wny
IP
Algorytm rozpoczyna siÄ™
permutacją wstępną IP.
L0 R0
K1
Ponieważ algorytm ma być
f
symetryczny, kończy się
L1=R0
R1=L0•"f(R0, K1)
permutacja odwrotnÄ….
K2
f
Taka budowa algorytmu
L2=R1
R2=L1•"f(R1, K2)
umożliwia stosowanie go
zarazem do szyfrowania i
L15=R15 R15=L14•"f(R14, K15)
K16
deszyfrowania informacji. Z
f
tym, że przy deszyfrowaniu
L16=R15 R16=L15
informacji kolejność
IP-1 podkluczy jest odwrotna.
Szyfrogram
© Robert Borowiec Kryptografia, WykÅ‚ad VII Strona7/42
Tabela permutacji poczÄ…tkowej i
końcowej
Tabela permutacji Tabela permutacji
początkowej IP końcowej IP-1
IP IP
58 50 42 34 26 18 10 2 40 8 48 16 56 24 64 32
60 52 44 36 28 20 12 4 39 7 47 15 55 23 63 31
62 54 46 38 30 22 14 6 38 6 46 14 54 22 62 30
64 56 48 40 32 24 16 8 37 5 45 13 53 21 61 29
57 49 41 33 25 17 9 1 36 4 44 12 52 20 60 28
59 51 43 35 27 19 11 3 35 3 43 11 51 19 59 27
61 53 45 37 29 21 13 5 34 2 42 10 50 18 58 26
63 55 47 39 31 23 15 7 33 1 41 9 49 17 57 25
© Robert Borowiec Kryptografia, WykÅ‚ad VII Strona8/42
Obliczanie funkcji f(Ri-1,Ki)
Ri-1 (32 bity)
E
48 bitów
Ki (48 bitów)
S1 S2 S3 S4 S5 S6 S7 S8
P
f(Ri-1,Ki)
© Robert Borowiec Kryptografia, WykÅ‚ad VII Strona9/42
S-bloki
S-bloki (ang. substitution boxes) dokonujÄ… operacji
podstawienia nieliniowego.
Na wejście wprowadzane są bloki 6 bitowe, a na
wyjściu pojawiają się bloki 4 bitowe.
S bloki nie sÄ… liniowymi funkcjami afinicznymi
swojego wejścia, tzn. nie można ułożyć układu
równań, z których można wyliczyć bity wyjściowe
na podstawie bitów wejściowych.
Zmiana jednego bitu wejściowego powoduje
zmianę co najmniej 2 bitów wyjściowych.
Minimalizowana jest różnica ilości występowania
zer i jedynek.
© Robert Borowiec Kryptografia, WykÅ‚ad VII
Strona10/42
Tablica stanów dla S-bloku nr 1
(każdy S-blok ma inaczej zdefiniowaną tablicę !!)
b2b3 b4b5
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
(0) (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) (12) (13) (14) (15)
0000 1110 0100 1101 0001 0010 1111 1011 1000 0011 1010 0110 1100 0101 1001 0000 0111
(0) (14) (4) (13) (1) (2) (15) (11) (8) (3) (10) (6) (12) (5) (9) (0) (7)
0001 0000 1111 0111 0100 1110 0010 1101 0001 1010 0110 1100 1011 1001 0101 0011 1000
(1) (0) (15) (7) (4) (14) (2) (13) (1) (10) (6) (12) (11) (9) (5) (3) (8)
0010 0100 0001 1110 1000 1101 0110 0010 1011 1111 1100 1001 0111 0011 1010 0101 0000
(2) (4) (1) (14) (8) (13) (6) (2) (11) (15) (12) (9) (7) (3) (10) (5) (0)
0011 1111 1100 1000 0010 0100 1001 0001 0111 0101 1011 0011 1110 1010 0000 0110 1101
(3) (15) (12) (8) (2) (4) (9) (1) (7) (5) (11) (3) (14) (10) (0) (6) (13)
© Robert Borowiec Kryptografia, WykÅ‚ad VII
Strona11/42
Tablica wyboru E i permutacji P
Tablica E wyboru bitów Tablica permutacji P
32 1 2 3 4 5 16 7 20 21
4 5 6 7 8 9 29 12 28 17
1 15 23 26
8 9 10 11 12 13
5 18 31 10
12 13 14 15 16 17
2 8 24 14
16 17 18 19 20 21
32 27 3 9
20 21 22 23 23 25
19 13 30 6
24 25 26 27 28 29
22 11 4 25
28 29 30 31 32 1
© Robert Borowiec Kryptografia, WykÅ‚ad VII
Strona12/42
b b

1
6
Tworzenie kluczy
K
1. PoczÄ…tkowo klucz jest
PC -1
redukowany z 64 bitów
do 56 poprzez
C0 D0
odrzucenie bitów
LS1 LS
1
parzystości i .
C1 D1
2. Z klucza 56 bitowego
K1
PC -2
LS1 LS tworzone jest 16
1
różnych kluczy 48
C2 D2
K1
PC -2 bitowych, które są
LS1 LS
1
używane w kolejnych
cyklach szyfrowania.
C16 D16
K16
PC -2
© Robert Borowiec Kryptografia, WykÅ‚ad VII
Strona13/42
Tworzenie kluczy
Tablica permutacji Tablica permutacji
klucza PC-1 klucza PC-2
57 49 41 33 25 17 9 14 17 11 24 1 5
1 58 50 42 34 26 18 3 28 15 6 21 10
10 2 59 51 43 35 27 23 19 12 4 26 8
19 11 3 60 52 44 36 16 7 27 20 13 2
63 55 47 39 31 23 15 41 52 31 37 47 55
7 62 54 46 38 30 22 30 40 51 45 33 48
14 6 61 53 45 37 29 44 49 39 56 34 53
21 13 5 28 20 12 4 46 42 50 36 29 32
Ilość przesunięć połówek klucza C i D
I 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
LS 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1
© Robert Borowiec Kryptografia, WykÅ‚ad VII
Strona14/42
Klucze słabe w DES
Z powodu sposobu generowania podkluczy w
systemie DES, istniejÄ…:
4-klucze słabe
12-kluczy półsłabych
Klucze słabe -podklucze generowane w kolejnych
cyklach z kluczy słabych są identyczne.
Klucze półsłabe-generują tylko dwa różne
podklucze zamist 16 różnych. Tak więc każdy
podklucz jest używany w algorytmie 8 razy.
© Robert Borowiec Kryptografia, WykÅ‚ad VII
Strona15/42
Wydajność
Algorytm DES został zaimplementowany w
postaci programowej oraz sprzętowej
Prędkość szyfrowania za pomocą układów
sprzętowych wynosi 1 GBit/s (dane z 1985 r).
Najszybsze implementacje programowe
osiągnęły prędkość 14 MBit/s. (dane z 2000
roku)
© Robert Borowiec Kryptografia, WykÅ‚ad VII
Strona16/42
Opublikowane metody
łamania szyfrów
1. Metoda siłowa -(ang. brutal force)
przeszukiwanie całej przestrzeni klucza
2. Kryptoanaliza różnicowa
3. Kryptoanaliza metodÄ… kluczy
powiÄ…zanych
4. Kryptoanaliza liniowa
© Robert Borowiec Kryptografia, WykÅ‚ad VII
Strona17/42
Wyniki kryptoanalizy DES
Analizow
Rodzaj Wybrane Znane teksty ane Złożoność
kryptoanalizy teksty jawne jawne teksty obliczeniowa
jawne
Brutalna 1 (8 Bajtów)
1 1 256
Różnicowa
247 255 (262144 TB) 236 237
Kluczy
233*(64 MB)
217* b.d. b.d.
powiÄ…zanych
Liniowa 247 (1024 TB)
b.d. b.d. b.d.
* znana jest różnica pomiędzy dwoma kluczami
© Robert Borowiec Kryptografia, WykÅ‚ad VII
Strona18/42
Kryptoanaliza algorytmu DES
Według opinii kryptoanalityków z roku 1985 klucz 56
bitowy był za krótki. Nie zapewniał on bowiem
odpowiedniego poziomu bezpieczeństwa.
Szyfr DES można bowiem złamać przy ataku
brutalnym (przeszukanie całej przestrzeni klucza) z
tekstem jawnym w ciÄ…gu jednego dnia przy
zastosowaniu maszyny złożonej z 1miliona procesorów i
sprawdzajÄ…cej jeden klucz w ciÄ…gu 1 µs.
W końcu lat 90 złamano metodą brutalną szyfr DES z
kluczem 56 bitowym w ciÄ…gu 3 dni na specjalizowanej
maszynie liczÄ…cej, po przeszukaniu 1/3 kluczy.Wynika z
tego, że każdy szyfrogram DES na tej maszynie można
złamać w ciągu 9 dni.
© Robert Borowiec Kryptografia, WykÅ‚ad VII
Strona19/42
Podwójny DES
SZYFROWANIE
DES DES
Tekst
Szyfro
jawny K1 K2
-gram
DES-1 DES-1
DESZYFROWANIE
© Robert Borowiec Kryptografia, WykÅ‚ad VII
Strona20/42
Potrójny DES
SZYFROWANIE
DES DES-1 DES
Tekst
Szyfro
jawny
K1 K2 K1
-gram
DES-1 DES DES-1
DESZYFROWANIE
© Robert Borowiec Kryptografia, WykÅ‚ad VII
Strona21/42
Narodziny standardu AES
We wrześniu 1997 roku NIST (ang. National
Institute of Standards and Technology) ogłosił
konkurs na nowy system szyfrujący, który ma
spełniać określone założenia.
W listopadzie 2001 roku NIST (ang. National
Institute of Standards and Technology) przyjÄ…Å‚ nowy
standard szyfrowania danych AES.
Do szyfrowania w nowym standardzie został
wybrany algorytm Rijndael (autorstwa Joan Daemen
i Vincent Rijmen)
© Robert Borowiec Kryptografia, WykÅ‚ad VII
Strona22/42
Wymagania postawione algorytmowi
dla standardu AES
AES musi być algorytmem symetrycznym
Przetwarzać 128 bitowe bloki informacji
Pracować z kluczami 128, 192, 256 bitowymi
Odporny na znane metody kryptoanalityczne
Programowa i sprzętowa łatwość implementacji
Odporny na ataki metodÄ… czasowa i poboru mocy
(w przypadku kart chipowych)
Powinien być szybki zarówno w implementacjach
programowych oraz sprzętowy
Małe potrzeby jeśli chodzi o zasoby systemowe
Wolny od opłat patentowych
© Robert Borowiec Kryptografia, WykÅ‚ad VII
Strona23/42
Specyfikacja algorytmu AES
Algorytm AES może pracować z kluczami
o różnej długości tj.: 128, 192 i 256 bitów
Przetwarza informacjÄ™ binarna w blokach o
długości 128 bitów.
Algorytm AES jest szybszy od 3DES około
4 razy. Przy programowej aplikacji AES
osiąga prędkość szyfrowania 50 Mbps (dla
klucza 256), podczas gdy 3DES 14 Mbps
© Robert Borowiec Kryptografia, WykÅ‚ad VII
Strona24/42
Opis algorytmu AES dla
klucza i danych o dł. 128-bitów
Tajny klucz 128 bitowy 1 6 b a j t ó w t e k s t u
1 a w k
6 j s
Klucz rundy 1 Runda 1
t t t
b ó e u
Klucz rundy 2 Runda 2
$ k n c
# * ! k
s ; . d
Klucz rundy 10 Runda 10 { a , ?
$ k n c # * ! k s ; . d { a , ?
© Robert Borowiec Kryptografia, WykÅ‚ad VII
Strona25/42
Właściwości algorytmu AES
Jest odporny na znane metody
kryptoanalityczne
Jest to algorytm symetryczny. Do
deszyfrowania trzeba jednak używać
innego algorytmu i innych tabel
© Robert Borowiec Kryptografia, WykÅ‚ad VII
Strona26/42
ALGORYTM IDEA
W 1990 roku Algorytm Xuejia Lai i James
Masseya zaproponowali nowy algorytm
szyfrowania -PES (ang. Proposed Encryption
Standard).
Pod aktualną nazwą algorytm IDEA zaistniał
1992r po wzmocnieniu go przeciw
kryptoanalizie różnicowej.
Obecnie jest to najlepszy algorytm dostępny
publicznie (do zastosowań niekomercyjnych
jest wolny od opłat).
Stosowany jest między innymi w PGP (ang.
Pretty Good Privacy)
© Robert Borowiec Kryptografia, WykÅ‚ad VII
Strona27/42
ALGORYTM IDEA
Algorytm przetwarza 64 bitowe bloki informacji
i pracuje z kluczem 128 bitowym. Bazuje na :
mieszaniu
rozpraszaniu
W tym celu stosowane sÄ… operacje:
poelementowe dodawanie modulo 2
Dodawanie modulo 216 (dodawanie z
pominięciem przepełnienia)
Mnożenie modulo 216+1 (mnożenie z
pominięciem przepełnienia)
© Robert Borowiec Kryptografia, WykÅ‚ad VII
Strona28/42
Schemat algorytmu IDEA
K4(1) K4(9)
X4
Y4
X3 Y3
K6(1)
K3(1) K3(9)
Siedem
pozostałych
cykli
K2(9)
K2(1)
K5(1)
X2 Y2
X1 Y1
K1(9)
K1(1)
© Robert Borowiec Kryptografia, WykÅ‚ad VII
Strona29/42
Kryptoanaliza algorytmu IDEA
Algorytm IDEA jest odporny na analizę różnicową
Atak brutalny wymaga sprawdzenia 2128 kluczy
Maszyna złożona z miliarda układów scalonych, z
który każdy testowałby miliard kluczy na sekundę
złamała by szyfrogram w ciągu 243 lat, czyli w
czasie dłuższym niż czas istnienia wszechświata
© Robert Borowiec Kryptografia, WykÅ‚ad VII
Strona30/42
Tryby pracy szyfrów
blokowych
ECB -Electronic CodeBook -
elektroniczna książka kodowa
CBC -Cipher Block Chaining - wiÄ…zanie
bloków szyfrogramu
CFB -Cipher FeedBack - sprzężenie
zwrotne szyfrogramu
OFB -Output Feedback - wyjściowe
sprzężenie zwrotne
© Robert Borowiec Kryptografia, WykÅ‚ad VII
Strona31/42
Elektroniczna książka kodowa (ECB)
Proces szyfrowania
M1 M2 MN
Szyfrator Szyfrator Szyfrator
K K K
C1 C2 CN
Proces des zyfrowania
C1 C2 CN
Deszyfrator
Deszyfrator Deszyfrator
K K K
M1 M2 MN
© Robert Borowiec Kryptografia, WykÅ‚ad VII
Strona32/42
Wiązanie bloków szyfrogramu (CBC)
Proces szyfrowania
Wektor M1 M2 MN
Inic.
K Szyfrator K Szyfrator K Szyfrator
C1 C2 CN
© Robert Borowiec Kryptografia, WykÅ‚ad VII
Strona33/42
Wiązanie bloków szyfrogramu (CBC)
Proces deszyfrowania
C1 C2 CN
K Deszyfrator K Deszyfrator K Deszyfrator
Wektor
Inic.
M1 M2 MN
© Robert Borowiec Kryptografia, WykÅ‚ad VII
Strona34/42
Sprężenie zwrotne szyfrogramu
Cipher FeedBack
Rejestr przesuwajÄ…cy Rejestr przesuwajÄ…cy
Szyfrator Szyfrator
Klucz K Klucz K
Lewy s krajny Lewy skrajny
ci-1 ci-1
bajt bajt
mi ci
ci m
i
Wyjście Wejście
Bajt wejściowy
Des zyfrowanie
Szyfrowanie
© Robert Borowiec Kryptografia, WykÅ‚ad VII
Strona35/42
Wyjściowe sprężenie zwrotne
Output FeedBack
Rejestr przesuwajÄ…cy Rejestr przesuwajÄ…cy
Szyfrator Szyfrator
Klucz K Klucz K
Lewy skrajny Lewy skrajny
ci-1 ci-1
bajt bajt
mi ci
ci mi
Wyjście Wejście
Bajt wejściowy
Szyfrowanie Des zyfrowanie
© Robert Borowiec Kryptografia, WykÅ‚ad VII
Strona36/42
Wyjściowe sprężenie zwrotne
Output FeedBack
Rejestr przesuwajÄ…cy Rejestr przesuwajÄ…cy
Szyfrator Szyfrator
Klucz K Klucz K
Lewy skrajny Lewy skrajny
ci-1 ci-1
bajt bajt
mi ci
ci mi
Wyjście Wejście
Bajt wejściowy
Szyfrowanie Des zyfrowanie
© Robert Borowiec Kryptografia, WykÅ‚ad VII
Strona37/42
Szyfry strumieniowe
Szyfry strumieniowe przekształcają tekst
jawny bit po bicie.
Najprostsza implementacja polega na
sumowaniu XOR bitów informacji jawnej z
bitami klucza.
Deszyfrowanie odbywa siÄ™ w identyczny
sposób.
Szyfry strumieniowe stosuje się w kanałach
telekomunikacyjnych o dużej przepustowości
© Robert Borowiec Kryptografia, WykÅ‚ad VII
Strona38/42
Szyfry strumieniowe
Generator
Generator
=
ciÄ…gu klucza w
ciÄ…gu klucza
nadajniku
w odbiorniku
CiÄ…g klucza Ki CiÄ…g klucza Ki
y
ródło Odbiorca
informacji Kanał telekomunikacyjny informacji
Pi Pi
Szyfrogram Ci
Ci=Pi•"Ki Pi=Ci•"Ki
© Robert Borowiec Kryptografia, WykÅ‚ad VII
Strona39/42
Szyfry strumieniowe
Generator Generator
Tajny
ciÄ…gu klucza w ciÄ…gu klucza
klucz
nadajniku w odbiorniku
K
CiÄ…g klucza Ki CiÄ…g klucza Ki
y
ródło Odbiorca
Kanał telekomunikacyjny
informacji informacji
Pi Pi
Ci=Pi•"Ki Szyfrogram Ci Pi=Ci•"Ki
© Robert Borowiec Kryptografia, WykÅ‚ad VII
Strona40/42
KONIEC
Dziękuję za uwagę
© Robert Borowiec Kryptografia, WykÅ‚ad VII
Strona41/42