Kody korekcyjne i kryptografia
1
Kryptografia
Algorytmy symetryczne
dr Robert Borowiec
Politechnika Wrocławska
Instytut Telekomunikacji i Akustyki
pokój 908, C-5
tel. 3203083
e-mail: robert.borowiec@ita.pwr.wroc.pl
www: lstwww.ita.pwr.wroc.pl/
~
RB/
Wykład VII
2-godziny
© Robert Borowiec
Kryptografia, Wykład VII Strona2/42
Duże liczby
2
190
sztuk
Liczba atomów w Słońcu
2
223
sztuk
Liczba atomów w galaktyce
2
265
sztuk
Liczba atomów we wszechświecie
(łącznie z „czarna materią”
2
280
cm
3
Objętość wszechświata
2
170
sztuk
Liczba atomów w planecie
2
34
lat = 2
59
s
Wiek wszechświata
2
30
lat = 2
55
s
Wiek naszej planety
Kody korekcyjne i kryptografia
2
© Robert Borowiec
Kryptografia, Wykład VII Strona3/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 Strona4/42
Inne znane algorytmy symetryczne
¾
Lucifer
¾
Madrygi
¾
NewDes
¾
Feal-N
¾
Redoc
¾
Loki
¾
Khuru i Khafre
¾
MMB
¾
CA-1.1
¾
RC-2
¾
RC-3
¾
RC-5
¾
SAFER
¾
SkipJack
Kody korekcyjne i kryptografia
3
© Robert Borowiec
Kryptografia, Wykład VII Strona5/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 Strona6/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.
Kody korekcyjne i kryptografia
4
© Robert Borowiec
Kryptografia, Wykład VII Strona7/42
Ogólny schemat blokowy algorytmu
Algorytm rozpoczyna się
permutacją wstępną IP.
Ponieważ algorytm ma być
symetryczny, kończy się
permutacja odwrotną.
Taka budowa algorytmu
umożliwia stosowanie go
zarazem do szyfrowania i
deszyfrowania informacji. Z
tym, że przy deszyfrowaniu
informacji kolejność
podkluczy jest odwrotna.
R
2
=L
1
⊕f(R
1
, K
2
)
L
0
R
0
IP
L
15
=R
15
R
15
=L
14
⊕f(R
14
, K
15
)
f
L
2
=R
1
f
L
1
=R
0
R
1
=L
0
⊕f(R
0
, K
1
)
f
L
16
=R
15
R
16
=L
15
Te ks t ja wny
IP
-1
Szyfrogra m
K
1
K
2
K
16
© Robert Borowiec
Kryptografia, Wykład VII Strona8/42
Tabela permutacji początkowej i
końcowej
7
15
23
31
39
47
55
63
5
13
21
29
37
45
53
61
3
11
19
27
35
43
51
59
1
9
17
25
33
41
49
57
8
16
24
32
40
48
56
64
6
14
22
30
38
46
54
62
4
12
20
28
36
44
52
60
2
10
18
26
34
42
50
58
IP
Tabela permutacji
początkowej IP
25
57
17
49
9
41
1
33
26
58
18
50
10
42
2
34
27
59
19
51
11
43
3
35
28
60
20
52
12
44
4
36
29
61
21
53
13
45
5
37
30
62
22
54
14
46
6
38
31
63
23
55
15
47
7
39
32
64
24
56
16
48
8
40
IP
Tabela permutacji
końcowej IP
-1
Kody korekcyjne i kryptografia
5
© Robert Borowiec
Kryptografia, Wykład VII Strona9/42
Obliczanie funkcji f(R
i-1
,K
i
)
E
S
1
S
2
S
3
S
4
S
5
S
6
S
7
S
8
P
f(R
i-1
,K
i
)
K
i
(48 bitów)
R
i-1
(32 bity)
48 bitów
© Robert Borowiec
Kryptografia, Wykład VII
Strona10/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.
Kody korekcyjne i kryptografia
6
© Robert Borowiec
Kryptografia, Wykład VII
Strona11/42
Tablica stanów dla S-bloku nr 1
(każdy S-blok ma inaczej zdefiniowaną tablicę !!)
b
1
b
6
→
b
2
b
3
b
4
b
5
→
1101
(13)
0110
(6)
0000
(0)
1010
(10)
1110
(14)
0011
(3)
1011
(11)
0101
(5)
0111
(7)
0001
(1)
1001
(9)
0100
(4)
0010
(2)
1000
(8)
1100
(12)
1111
(15)
0011
(3)
0000
(0)
0101
(5)
1010
(10)
0011
(3)
0111
(7)
1001
(9)
1100
(12)
1111
(15)
1011
(11)
0010
(2)
0110
(6)
1101
(13)
1000
(8)
1110
(14)
0001
(1)
0100
(4)
0010
(2)
1000
(8)
0011
(3)
0101
(5)
1001
(9)
1011
(11)
1100
(12)
0110
(6)
1010
(10)
0001
(1)
1101
(13)
0010
(2)
1110
(14)
0100
(4)
0111
(7)
1111
(15)
0000
(0)
0001
(1)
0111
(7)
0000
(0)
1001
(9)
0101
(5)
1100
(12)
0110
(6)
1010
(10)
0011
(3)
1000
(8)
1011
(11)
1111
(15)
0010
(2)
0001
(1)
1101
(13)
0100
(4)
1110
(14)
0000
(0)
1111
(15)
1110
(14)
1101
(13)
1100
(12)
1011
(11)
1010
(10)
1001
(9)
1000
(8)
0111
(7)
0110
(6)
0101
(5)
0100
(4)
0011
(3)
0010
(2)
0001
(1)
0000
(0)
© Robert Borowiec
Kryptografia, Wykład VII
Strona12/42
Tablica wyboru E i permutacji P
1
32
31
30
29
28
29
28
27
26
25
24
25
23
23
22
21
20
21
20
19
18
17
16
17
16
15
14
13
12
13
12
11
10
9
8
9
8
7
6
5
4
5
4
3
2
1
32
Tablica E wyboru bitów
Tablica permutacji P
25
4
11
22
6
30
13
19
9
3
27
32
14
24
8
2
10
31
18
5
26
23
15
1
17
28
12
29
21
20
7
16
Kody korekcyjne i kryptografia
7
© Robert Borowiec
Kryptografia, Wykład VII
Strona13/42
Tworzenie kluczy
K
D
0
C
0
LS
1
D
1
LS
1
C
1
PC -1
LS
1
D
2
LS
1
C
2
PC -2
K
1
LS
1
D
16
LS
1
C
16
PC -2
K
1
PC -2
K
16
1. Początkowo klucz jest
redukowany z 64 bitów
do 56 poprzez
odrzucenie bitów
parzystości i .
2. Z klucza 56 bitowego
tworzone jest 16
różnych kluczy 48
bitowych, które są
używane w kolejnych
cyklach szyfrowania.
© Robert Borowiec
Kryptografia, Wykład VII
Strona14/42
Tworzenie kluczy
32
53
48
55
2
8
10
5
29
36
50
42
46
34
56
39
49
44
33
45
51
40
30
47
37
31
52
41
13
20
27
7
16
26
4
12
19
23
21
6
15
28
3
1
24
11
17
14
12
37
30
23
44
35
26
17
4
20
28
5
13
21
29
45
53
61
6
14
22
38
46
54
62
7
15
31
39
47
55
63
36
52
60
3
11
19
27
43
51
59
2
10
18
34
42
50
58
1
9
25
33
41
49
57
Tablica permutacji
klucza PC-1
Tablica permutacji
klucza PC-2
Ilość przesunięć połówek klucza C i D
2
15
1
2
2
2
2
2
1
2
2
2
2
2
2
1
1
LS
16
14
13
12
11
10
9
8
7
6
5
4
3
2
1
I
Kody korekcyjne i kryptografia
8
© Robert Borowiec
Kryptografia, Wykład VII
Strona15/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
Strona16/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)
Kody korekcyjne i kryptografia
9
© Robert Borowiec
Kryptografia, Wykład VII
Strona17/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
Strona18/42
Wyniki kryptoanalizy DES
2
37
2
36
2
55
(262144 TB)
2
47
Różnicowa
b.d.
b.d.
2
47
(1024 TB)
b.d.
Liniowa
b.d.
b.d.
2
33*
(64 MB)
2
17*
Kluczy
powiązanych
2
56
1
1 (8 Bajtów)
1
Brutalna
Złożoność
obliczeniowa
Analizow
ane
teksty
jawne
Znane teksty
jawne
Wybrane
teksty jawne
Rodzaj
kryptoanalizy
* znana jest różnica pomiędzy dwoma kluczami
Kody korekcyjne i kryptografia
10
© Robert Borowiec
Kryptografia, Wykład VII
Strona19/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
Strona20/42
Podwójny DES
SZYFROWANIE
DES
DES
DESZYFROWANIE
DES
-1
DES
-1
Szyfro
-gram
Teks t
jawny K
1
K
2
Kody korekcyjne i kryptografia
11
© Robert Borowiec
Kryptografia, Wykład VII
Strona21/42
Potrójny DES
SZYFROWANIE
DES
DES
-1
DES
DESZYFROWANIE
DES
-1
DES
DES
-1
Szyfro
-gram
Teks t
jawny
K
1
K
2
K
1
© Robert Borowiec
Kryptografia, Wykład VII
Strona22/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)
Kody korekcyjne i kryptografia
12
© Robert Borowiec
Kryptografia, Wykład VII
Strona23/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
Strona24/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
Kody korekcyjne i kryptografia
13
© Robert Borowiec
Kryptografia, Wykład VII
Strona25/42
Opis algorytmu AES dla
klucza i danych o dł. 128-bitów
Klucz rundy 1
t
e k s
u
t
w
ó
t
j
a
b
6
1
u
e
ó
b
t
t
t
s
j
6
k
w
a
1
Runda 1
Runda 2
Runda 10
?
,
a
{
d
.
;
s
k
!
*
#
c
n
k
$
,
d { a
?
.
;
s
k
!
*
#
c
n
k
$
Klucz rundy 2
Klucz rundy 10
Tajny klucz 128 bitowy
© Robert Borowiec
Kryptografia, Wykład VII
Strona26/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
Kody korekcyjne i kryptografia
14
© Robert Borowiec
Kryptografia, Wykład VII
Strona27/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
Strona28/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 2
16
(dodawanie z
pominięciem przepełnienia)
Ö Mnożenie modulo 2
16
+1 (mnożenie z
pominięciem przepełnienia)
Kody korekcyjne i kryptografia
15
© Robert Borowiec
Kryptografia, Wykład VII
Strona29/42
Schemat algorytmu IDEA
X
4
X
3
X
2
X
1
Y
4
Y
3
Y
2
Y
1
K
4
(1)
K
3
(1)
K
2
(1)
K
1
(1)
K
4
(9)
K
3
(9)
K
2
(9)
K
1
(9)
Siedem
pozostałych
cykli
K
5
(1)
K
6
(1)
© Robert Borowiec
Kryptografia, Wykład VII
Strona30/42
Kryptoanaliza algorytmu IDEA
¾
Algorytm IDEA jest odporny na analizę różnicową
¾
Atak brutalny wymaga sprawdzenia 2
128
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 2
43
lat, czyli w
czasie dłuższym niż czas istnienia wszechświata
Kody korekcyjne i kryptografia
16
© Robert Borowiec
Kryptografia, Wykład VII
Strona31/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
Strona32/42
Elektroniczna książka kodowa (ECB)
Szyfrator
Szyfrator
Szyfrator
K K
K
C
1
C
2
C
N
M
1
M
2
M
N
Proces s zyfrowania
Proces des zyfrowania
Deszyfra tor
Deszyfra tor
Deszyfra tor
K K
K
M
1
M
2
M
N
C
1
C
2
C
N
Kody korekcyjne i kryptografia
17
© Robert Borowiec
Kryptografia, Wykład VII
Strona33/42
Wiązanie bloków szyfrogramu (CBC)
Proces szyfrowania
Szyfrator
Szyfrator
S zyfrator
K K
K
C
1
C
2
C
N
M
1
M
2
M
N
Wektor
Inic.
© Robert Borowiec
Kryptografia, Wykład VII
Strona34/42
Wiązanie bloków szyfrogramu (CBC)
Proces deszyfrowania
Deszyfrator
Deszyfrator
Deszyfrator
K K
K
C
1
C
2
C
N
M
1
M
2
M
N
Wektor
Inic.
Kody korekcyjne i kryptografia
18
© Robert Borowiec
Kryptografia, Wykład VII
Strona35/42
Sprężenie zwrotne szyfrogramu
Cipher FeedBack
Rejestr przesuwający
c
i-1
c
i
m
i
Wyjście
Bajt wejściowy
Lewy s krajny
bajt
S zyfrowanie
S zyfrator
Klucz K
Szyfrator
Klucz K
Rejestr przesuwający
c
i-1
m
i
c
i
Lewy skrajny
bajt
Des zyfrowanie
Wejście
© Robert Borowiec
Kryptografia, Wykład VII
Strona36/42
Wyjściowe sprężenie zwrotne
Output FeedBack
Szyfrator
Klucz K
Rejestr przesuwający
c
i-1
c
i
m
i
Wyjście
Bajt wejściowy
Lewy skrajny
bajt
S zyfrowanie
Szyfrator
Klucz K
Rejestr przesuwający
c
i-1
m
i
c
i
Lewy skrajny
bajt
Des zyfrowanie
Wejście
Kody korekcyjne i kryptografia
19
© Robert Borowiec
Kryptografia, Wykład VII
Strona37/42
Wyjściowe sprężenie zwrotne
Output FeedBack
Szyfrator
Klucz K
Rejestr przesuwający
c
i-1
c
i
m
i
Wyjście
Bajt wejściowy
Lewy skrajny
bajt
S zyfrowanie
Szyfrator
Klucz K
Rejestr przesuwający
c
i-1
m
i
c
i
Lewy skrajny
bajt
Des zyfrowanie
Wejście
© Robert Borowiec
Kryptografia, Wykład VII
Strona38/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
Kody korekcyjne i kryptografia
20
© Robert Borowiec
Kryptografia, Wykład VII
Strona39/42
Szyfry strumieniowe
Generator
ciągu klucza w
nadajniku
Generator
ciągu klucza
w odbiorniku
Ciąg klucza K
i
Ciąg klucza K
i
Kanał telekomunikacyjny
Szyfrogram C
i
Źródło
informacji
P
i
Odbiorca
informacji
P
i
=
C
i
=P
i
⊕K
i
P
i
=C
i
⊕K
i
© Robert Borowiec
Kryptografia, Wykład VII
Strona40/42
Szyfry strumieniowe
Generator
ciągu klucza w
nadajniku
Generator
ciągu klucza
w odbiorniku
Ciąg klucza K
i
Ciąg klucza K
i
Kanał telekomunikacyjny
Szyfrogram C
i
Źródło
informacji
P
i
Odbiorca
informacji
P
i
C
i
=P
i
⊕K
i
P
i
=C
i
⊕K
i
Tajny
klucz
K
Kody korekcyjne i kryptografia
21
© Robert Borowiec
Kryptografia, Wykład VII
Strona41/42
KONIEC
Dziękuję za uwagę