2014-03-18
Agenda
" Charakterystyka
Bezpieczeństwo
" Sieci Fiestela
i ochrona danych
" DES
" IDEA
Algorytmy blokowe " AES
Algorytmy symetryczne Algorytmy blokowe
" Klucz szyfrujÄ…cy i deszyfrujÄ…cy jest taki sam
" Szyfry blokowe dzielą tekst jawny na bloki o stałej
długości i wynikowy kryptogram ma taką samą długość
" Dwie klasy kryptosystemów: blokowe i strumieniowe
Algrorytm Strumieniowy Algorytm Blokowy
" Blokowe algorytmy szyfrujÄ… pojedyncze bloki tekstu
100110110100010111010010 100110110100010111010010
jawnego wykorzystując skomplikowane przekształcenia
1 & & 1 & & 0 & & 0 & & 0 100110 110100 010111 010010
szyfrujÄ…ce
&
& & " Przykład:
&
E E E E E E E E E
 DES: blok 64 bit
 AES: blok 128 bit
1& & ...1& & ..1& & .0& & .1 110010 011101 010010 001001
" Algorytmy blokowe mogą pracować w różnych trybach
110010011101010010001001
110010011101010010001001
(tryby pracy algorytmu)
Algorytmy blokowe
Algorytmy blokowe
" Algorytmy blokowe są współczesną wersją
" Algorytmy blokowe propagujÄ… w pewnym ograniczonym
książek kodowych
zakresie błędy, lecz ze względu na swoją elastyczność i
możliwość pracy w różnych trybach są najczęściej
wykorzystywane do ochrony różnych atrybutów danych
" W rzeczywistości, algorytm blokowy jest
zestawem wielu książek kodowych
" Własności algorytmu szyfrowania są zależne również od
(liczba i typ książki zależy od klucza)
trybu pracy algorytmu i sposobu jego wykorzystania.
" Wspólny klucz wymusza użycie jednej książki
" Dla różnych trybów pracy, ten sam algorytm może
przejawiać różne własności.
" Zmiana klucza powoduje wybór innej książki
1
2014-03-18
Algorytmy blokowe C. Shannon
" Jak szyfrować tekst o długości przekraczającej " W roku 1949 Shannon wprowadził koncepcję sieci
długość bloku? podstawieniowo-przestawieniowyhc
(ang. substitution-permutation (S-P) networks)
" Nowy klucz dla każdego kolejnego bloku?
" Podstawa dla współczesnych algorytmów
 Problem taki sam jak w przypadku one-time pad
blokowych
" Szyfrować każdy blok niezależnie?
" Sieci S-P opierają się na dwóch podstawowych
" Szyfrować kolejne bloki zależnie od bloków
operacjach kryptograficznych:
wcześniejszych?
 Podstawieniu (S-box)
" Jak szyfrować bloki niekompletne?
 Przestawieniu (P-box) (transposition)
Mieszanie i plÄ…tanie Sieci Feistela
Shannon, twórca teorii informacji przedstawił w 1949 roku
" Horst Feistel opracował tzw. Szyfrator
dwie główne zasady szyfrowania:
feistela (feistel cipher)
" Mieszanie (Konfuzja) oznacza rozmycie zależności
 Implementacja koncepcji Shannona dotyczÄ…cej
pomiędzy tekstami jawnymi a ich zaszyfrowanymi
podstawień i przestawień
wersjami
 Blok wejściowy dzielony jest na dwie części
" Rozpraszanie (Dyfuzja)oznacza rozłożenie zawartych w
 Przetwarzane wielokrotnie w procesie tzw. Algorytmu
tekście jawnym informacji w całym tekście
rundy
zaszyfrowanym
 Wykonują podstawienie na lewej części danych
 Prawa część poddawana jest przestawieniom
 Części są zamieniane ze sobą po kolejnej rundzie
Szyfr Feistel Szyfr Feistel
" Deszyfracja:
" Feistel cipher odnosi się do klasy algorytmów i nie jest
 Kryptogram= (Ln,Rn)
jednym konkretnym algorytmem
 Dla każdej rundy i=n,n-ð1,& ,1, oblicz
" Dwie części tekstu jawnego = (L0,R0)
Ri-ð1 = Li
" Dla każdej rundy i=1,2,...,n, oblicz
Li= Ri-ð1 Li-ð1 = Ri Åð F(Ri-ð1,Ki)
Ri= Li-ð1 Åð F(Ri-ð1,Ki)
gdzie F jest funkcjÄ… rundy i Ki jest
gdzie F jest funkcją rundy (nie musi być odwracalna) i
podkluczem
Ki jest podkluczem (kluczem rundy)
 Tekst jawny = (L0,R0)
" Kryptogram= (Ln,Rn)
 Możliwe różne wersje funkcji F
 Lecz bezpieczne jedynie dla pewnych F
2
2014-03-18
Sieci Feistela Sieci Feistela
" Szyfrowanie
" Własności:
Li+1 = Ri Ri+1 = Li XOR fS,i(Ri)
 Rozmiar bloku
" Właściwość " Zwiększenie długości bloku zwiększa bezpieczeństwo, lecz spowalnia
szyfrowanie
Li = (Li XOR fS,i(Ri)) XOR fS,i(Ri) = Ri+1 XOR fS,i(Ri)
 Rozmiar klucza
" Deszyfrowanie
" Zwiększenie długości klucza zwiększa bezpieczeństwo (utrudnia
Rn-1 = Ln Ln-1 = Rn XOR fS,n-1(Rn-1) przeszukiwanie kompletne), lecz może spowalniać algorytm
. . .  Liczba rund
" Zwiększa bezpieczeństwo lecz spowalnia działanie
R0 = L1 L0 = R1 XOR fS,0(R0)
 Sposób generowania kluczy rund
L R
i i
" Większa złożoność utrudnia analizę lecz spowalnia szyfrowanie
 Funkcja rundy
" Większa złożoność utrudnia analizę lecz spowalnia szyfrowanie
f Klucz rundy
 Szybkość szyfrowania/deszyfrowania
" UÅ‚atwia stosowanie i testowanie
XOR
L R
i+1 i+1
Efekt lawinowy Algorytm DES - historia
" 1971  pierwszy patent dotyczÄ…cy algorytmu Lucifer
" Efektem lawinowym określamy intensywniejszy niż dla
opracowanego przez Horsta Fiestela i jego kolegów w
rozpraszania  rozmazanie tekstu jawnego w tekście
IBM (64-bit blok,128-bit)
zaszyfrowanym
" 1973  NBS (National Bureau of Standards) ogłasza
" Jest spotykany dla szyfrowania blokowego
konkursu na algorytm szyfrujÄ…cy
" Każdy bit zaszyfrowanego tekstu zależy od wszystkich
bitów tekstu jawnego w danym bloku " 1977  FIPS (wcześniej NBS) publikuje algorytm DES
(ang. Data Encryption Standard) oparty na Lucifer jako
" Dla zmiany pojedynczego bitu tekstu jawnego lub klucza,
każdy bit tekstu zaszyfrowanego powinien zmienić swoją standard FIPS 46
wartość z prawdopodobieństwem
" 1999  DES potwierdzony po raz 4 przez NIST w wersji
równym dokładnie 50%
Triple DES jako FIPS 46-3
" Kryptoanaliza różnicowa wykorzystuje nawet niewielkie
" 2001  publikacja AES (Advanced Encryption Standard)
odstępstwo od tej zasady
jako FIPS 197
" 2005  NIST wycofuje DES (FIPS 46-3)
DES w pigułce DES - kontrowersje
" Dane sÄ… szyfrowane w 64-bitowych blokach
" Kontrowersje budził fakt oparcia
" Klucz ma długość 56 bitów
konstrukcji algorytmu o klucz 56 bitowy, w
" Algorytm produktowy  stosuje transpozycje w kolejnych
kontekście 128 bitowego klucza alg.
etapach (iteracjach)
Lucifer będącego pierwowzorem DES
" Szyfrowanie polega na serii etapów przetwarzających
64-bitowe dane wejściowe na 64-bitowy wynik
" DeszyfrujÄ…c wykonuje siÄ™ te same etapy i ten sam klucz,
" Podejrzewany o istnienie  tylnych drzwi
ale w odwrotnej kolejności
" Najważniejszym elementem algorytmu są S-bloki (ang.
S-box)
" Lata użytkowania i analizy nie
potwierdziły wątpliwości
3
2014-03-18
Permutacja wstępna
Ogólny schemat DES
64-bitowy tekst jawny 56-bitowy klucz
" Permutację wstępną IP i jej odwrotność IP-1 definiuje poniższa
Permutacja Permutowany
tabela
wstępna wybór 1
" Obie funkcje są odwrotne względem siebie
K1 Permutowany Cykliczne przesu-
Iteracja 1
" Jeżeli szyfrujemy blok M to tekst po permutacji wygląda
nięcie w lewo
wybór 2
następująco X=IP(M)
K2 Permutowany Cykliczne przesu-
Iteracja 2
nięcie w lewo
wybór 2 " Po permutacji odwrotnej otrzymujemy
Y= IP-1(X)=IP-1(IP(M))=M
Bit wyjściowy 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
K16 Permutowany Cykliczne przesu-
Iteracja 16
Z bitu wejściowego 58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4
nięcie w lewo
wybór 2
Bit wyjściowy 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
Zamiana bloków
Z bitu wejściowego 62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8
32-bitowych
Bit wyjściowy 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
Odwrotność per-
Z bitu wejściowego 57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3
mutacji wstępnej
Bit wyjściowy 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
64-bitowy tekst zaszyfrowany Z bitu wejściowego 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7
Iteracja algorytmu DES Permutacja rozszerzajÄ…ca
32 bity 32 bity 28 bity 28 bity
" Permutacja rozszerzajÄ…ca powoduje wygenerowanie z 32
Li-1 Ri-1 Ci-1 Di-1
bitów wejściowych 48 bitów wyjściowych według
Rozszerzenie/ Przesunięcie(a) Przesunięcie(a)
podanej tabeli
permutacja (tablica E) w lewo w lewo
48
Bit wyjściowy 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
48 Permutacja/skrócenie
Z bitu wejściowego 32 1 2 3 4 5 4 5 6 7 8 9 8 9 10 11
XOR (permutowany wybór)
Bit wyjściowy 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
48
Z bitu wejściowego 12 13 12 13 14 15 16 17 16 17 18 19 20 21 20 21
Podstawienie/wybór
(S-blok)
Bit wyjściowy 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
32
Z bitu wejściowego 22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 1
Permutacja P
32
XOR
32
Li Ri Ci Di
S-blok S-blok
32 bity
" Pierwszy i ostatni bit wejścia S-bloku wskazuje odpowiedni wiersz
R
tabeli S-bloku
" Środkowe 4 bity określają kolumnę
Rozszerzenie/
permutacja (tablica E) " Na przykład
48
wejście: 011011
48
Klucz wiersz 01 (1)
XOR
kolumna 1101 (13)
48
wyjście: 5 (0101)
S S S S S S S S
1 2 3 4 5 6 7 8
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
32 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
Permutacja P
3 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13
4
2014-03-18
Algorytm IDEA
" International Data Encryption Algorithm (IDEA) to
algorytm szyfrowania blokowego opublikowany przez
Xueji Lai i James Massey (ETH Zurich) w 1991 roku
" IDEA to szyfr blokowy  bloki majÄ… po 64 bity
Algorytm IDEA
" Stosowany jest 128 bitowy klucz
Założenia projektowe
Skuteczność kryptograficzna IDEA
algorytmu IDEA
" Zastosowanie 16-bitowych podbloków " Długość bloków powinna być duża, by utrudnić
kryptoanalizÄ™
" Zastosowanie prostych operacji arytmetycznych
" Długość klucza powinna uniemożliwić atak siłowy.
" Podobieństwo między szyfrowaniem i deszyfrowaniem
" Mieszanie (konfuzja) - zależność tekstu zaszyfrowanego
" Regularna struktura ułatwiająca realizację w technice
od tekstu jawnego i klucza powinna być skomplikowana,
VLSI
aby utrudnić kryptoanalizę
" Rozpraszanie (dyfuzja)- każdy bit wejścia powinien
wpływać na każdy bit tekstu zaszyfrowanego
Mieszanie w algorytmie IDEA Rozpraszanie w algorytmie IDEA
F F
1 2
" Rozpraszanie jest osiÄ…gane za pomocÄ…
W IDEA mieszanie uzyskuje siÄ™ za pomocÄ… trzech operacji
podstawowej jednostki algorytmu
wykonywanych na dwóch wejściowych 16-bitowych
nazywanej strukturÄ…
Z
5
blokach:
mnożenia/dodawania MA (ang.
multiplication/addition)
" XOR logiczny oznaczany znakiem Åð
" Dodawanie liczb całkowitych modulo 216 (65536)
" Struktura ta produkuje dwa 16-bitowe
oznaczane jako . Dane wejściowe to nieujemne liczby
wyniki (G1,G2) z dwóch 16-bitowych
16-bitowe
wartości wejściowych tekstu jawnego
(F1,F2) i dwóch 16-bitowych podkluczy
" Mnożenie liczb całkowitych modulo 216+1 (65537)
Z
wyprowadzanych z klucza (Z1,Z2) 6
oznaczane jako znak
G G
1 2
5
2014-03-18
Szyfrowanie za pomocÄ… IDEA
X X X X
1 2 3 4
64-bitowy tekst jawny X
128-bitowy klucz Z
X1 X2 X3 X4
Z Z
1 3
. Z1 Generator
.
Iteracja 1 Z Z
2
. 4
Z6 podkluczy
W11 W12 W13 W14 . . .
. Z7 Z1 Z52
.
Iteracja 2
.
Z12
W21 W22 W23 W24
Z
5
W71 W72 W73 W74
. Z43
.
Iteracja 8
. Z
6
Z48
W81 W82 W83 W84
. Z49
Przekształcenie
.
.
wyniku
Z52
Y1 Y2 Y3 Y4
64-bitowy tekst zaszyfrowany Y
W W W W
11 12 13 14
Etap przekształcania wyników
Generowanie podkluczy w
algorytmu IDEA algorytmie IDEA
W W W W
81 82 83 84 " Wszystkie 52 podklucze o długości 16 bitów są
generowane na podstawie głównego 128 bitowego
klucza
" Pierwsze 8 podkluczy Z1 - Z8 generowane sÄ…
bezpośrednio z klucza
Z Z
49 51
" Następnie cyklicznie przesuwamy klucz w lewo o 25
bitów i generujemy kolejne 8 podkluczy
Z Z
50 52
" ProcedurÄ™ powtarzamy do wygenerowanie 52
podkluczy
Y Y Y Y
1 2 3 4 128 bitowy klucz
Z15 Z16 Z2 Z9 Z3 Z10 Z4Z17 1 Z5 Z6 Z7 Z14 Z8
Z1 Z1 Z18Z12 Z19Z13 Z20 Z15
Konkurs AES
" W 1997 roku agencja NIST (ang. National Institute of
Standards and Technology) rozpisała konkurs na nowy
standard szyfrowania, który miał otrzymać nazwę AES
(ang. Advanced Encryption Standard)
Algorytm AES
" Wybrany algorytm, Rijndael opracowany został przez
naukowców belgijskich dr Joan Daemen oraz dr Vincent
Rijmen
" Rijndael jest blokowym algorytmem szyfrowania z
kluczem symetrycznym pozwalajÄ…cym na wykorzystanie
klucza szyfrującego o długości 128, 192 i 256 bitów
6
2014-03-18
Kalendarium konkursu AES
Kalendarium konkursu AES
" 02.01.1997 Ogłoszenie konkursu.
" 15.04.1999 Koniec publicznego badania kandydatów.
Zgłoszenie kandydatów do 12.09.1997
Pięć algorytmów wybrano do finału według
" 15.04.1997 Dokładne sformułowanie kryteriów dla
następującego głosowania
nowego algorytmu
 Rijndael: 86 positive, 10 negative
" 20.08.1998 Pierwsza konferencja AES.
 Serpent: 59 positive, 7 negative
NIST ogłasza dopuszczenie 15 algorytmów do konkursu.
 Twofish: 31 positive, 21 negative
Rozpoczyna siÄ™ ich publiczna analiza
 RC6: 23 positive, 37 negative
" Marzec 1999 Druga konferencja AES.
Dyskusja dotychczasowych rezultatów
 MARS: 13 positive, 83 negative
" 15.04.1999 Koniec publicznego badania kandydatów.
Pięć algorytmów wybrano do finału (MARS, RC6,
Rijndael, Sperpent, Twofish)
Kalendarium konkursu AES Dlaczego wygrał Rijndeal
" 13/14.04.2000 Trzecia konferencja AES. " Znakomita kombinacja gwarantowanego poziomu
Omawiane są analizy 5 finalistów bezpieczeństwa, wydajności, efektywności i łatwości
implementacji
" 15.05.2000 Zakończenie otwartych dyskusji
" Rijndael charakteryzuje się bardzo dobrą wydajnością
" 02.10.2000 Ogłoszenie zwycięzcy  algorytmu Rijndael.
zarówno przy implementacji sprzętowej, jak i
" Listopad 2000 Udostępnienie standardu FIPS-197
programowej uwzględniającej różne środowiska i
Można zgłaszać komentarze i uwagi
systemy operacyjne
" Luty 2001 Koniec publicznej dyskusji nt. standardu
" Testy wykazały, że nie wymaga dużo pamięci
" Kwiecień-Czerwiec 2001 Zatwierdzenie standardu FIPS
operacyjnej, co sprawia, że można go stosować w wielu
niedostępnych dla innych algorytmów miejscach
Rijndael Rijndael
" Algorytm blokowy (128, 192 lub 256 bitowe bloki " Został zatwierdzony jako następca algorytmu DES
danych)
" Szyfrowanie jest symetryczne, zatwierdzono klucze o " Rijndael nie jest chroniony żadnymi zastrzeżeniami
długościach 128, 192 i 256 bitów patentowymi, więc nie wymaga opłat licencyjnych
" Proces szyfrowania podlega iteracjom, przy czym
rozróżnia się:
" Spełnia 3 główne założenia postawione przez twórców
 rundę wstępną,
algorytmu:
 pewną ilość rund standardowych, z których każda posiada 4
 odporność na wszystkie znane ataki,
transformacje,
 szybkość pracy i zwartość kodu na różnych platformach,
(ilość rund zależy od długości klucza i wynosi odpowiednio 10, 12
 łatwość implementacji
lub 14)
 rundę końcową
7
2014-03-18
Rijndael w pigułce Szczegóły algorytmu Rijndael
" Aktualny stan wiedzy w zakresie kryptoanalizy nie
" Podstawowe pojęcia służące do opisu algorytmu to "Stan"
pozwala na skuteczny atak na wiadomości szyfrowane
i "runda"
tym algorytmem
" Runda (ang. round) to odpowiednik standardowego
etapu obliczeń mającym jako parametr tzw. Klucz Rundy
" Atak brutalny, czyli sprawdzenie wszystkich możliwych
(ang. Round Key)
kluczy szyfrujÄ…cych jest praktycznie niewykonalny ze
względu na długość klucza " Z reguły runda jest superpozycją, co najmniej 2 bijekcji
tzw. podstawienia i permutacji, w Rijndaelu tych
" Jest łatwy do implementacji sprzętowej (większość przekształceń jest więcej
rodzajów procesorów, smartcard) i programowej
(wiele popularnych języków programowania)
Szczegóły algorytmu Rijndael
Szczegóły algorytmu Rijndael
" Klucz szyfrujący jest również reprezentowany jako macierz o 4
" Przekształcenia składające się na każdą rundę operują na
wierszach
pewnej macierzy prostokÄ…tnej stanowiÄ…cej wynik
" LiczbÄ™ kolumn tego klucza oznaczamy przez Nk
pośredni kolejnych obliczeń podczas realizacji algorytmu
" Liczba Nk jest równa długości klucza podzielonej przez 32; Nk=4,
i nazywanej Stanem (ang. State)
6 lub 8
" Długość klucza i bloku, czyli Nk i Nb możemy zmieniać niezależnie
" Jest to macierz o współczynnikach w ciele GF(28) lub
" Liczba rund Nr stosowana w algorytmie zależy od Nb i Nk
inaczej w zbiorze {0,1}8 czyli macierz, której
współczynniki to bajty
Nb Nk Nr Nb Nk Nr Nb Nk Nr
" Macierz bajtowa Stanu ma 4 wiersze i Nb kolumn (Nb to
4 4 10 4 6 12 4 8 14
długość bloku podzieloną przez 32), Nb=4, 6 lub 8
6 4 12 6 6 12 6 8 14
8 4 14 8 6 14 8 8 14
128-bitowy tekst jawny
T e k s t j a w n y w 1 2
T t w w
Ogólny opis algorytmu
Macierz e n
Stanu k j y 1
s a 2
//State  macierz stanu, CipherKey  klucz
Klucz
Runda 1
128-bitowy klucz
Rijndael(State,CipherKey)
rundy 1
ByteSub
{
Generator
ShiftRow
Klucz kluczy rund
KeyExpansion(CipherKey,ExpandedKey) ;
Runda 2
rundy 2
MixColumn
AddRoundKey(State,ExpandedKey);
AddRoundKey
for i=1 to (Nr-1)
{
Klucz
Runda 10
rundy 10 Round(State,ExpandedKey+Nb*i);
}
$ * a x
- \ & ^
FinalRound(State,ExpandedKey+Nb*Nr);
{ : C g
u S . !
}
$ * a x - \ & ^ { : C g u S . !
128-bitowy tekst zaszyfrowany
8
2014-03-18
Opis jednej rundy algorytmu Przekształcenie ByteSub
" Przekształcenie rundy jest bijekcją będąca superpozycją " Przy transformacji ByteSub operuje się na
4 bijekcji składowych poszczególnych elementach macierzy Stanu, które są
pojedynczymi bajtami
" Runda składa się z następujących czterech przekształceń
operujących na macierzy Stanu " Każdy bajt przechodzi transformację, którą ze względów
historycznych nazwano S-Boxem i jest wpisywany w to
 przekształcenia ByteSub
samo miejsce
 przekształcenia ShiftRow
" W fazie tej wykonuje siÄ™ jedynie operacje na bajtach, a
 przekształcenia MixColumn
zatem jest to Å‚atwe nawet w procesorach 8-bitowych
 dodawania klucza rundy
S-Box
a a a a b b b b
0,0 0,1 0,2 0,3 0,0 0,1 0,2 0,3
" Ostatnia runda nie zawiera przekształcenia MixColumn
a a a a b b b b
ai,j bi,j
1,0 1,1 1,2 1,3 1,0 1,1 1,2 1,3
a a a a b b b b
2,0 2,1 2,2 2,3 2,0 2,1 2,2 2,3
a a a a b b b b
3,0 3,1 3,2 3,3 3,0 3,1 3,2 3,3
Przekształcenie ShiftRow Przekształcenie MixColumn
" Ta transformacja przesuwa cyklicznie kolejne wiersze
" Transformacja MixColumn miesza wartości zawarte w
macierzy o odpowiedniÄ… liczbÄ™ pozycji
jednej kolumnie w dość skomplikowany sposób,
" Wartości przesunięcia zależą od wielkości bloku i klucza
zmieniając jednocześnie ich wartości
- dla naszych danych pierwszego wiersza siÄ™ nie
przesuwa, drugi przesuwa siÄ™ o 1 kolumnÄ™, trzeci o 2
" Dzięki zastosowaniu specjalnych struktur algebraicznych
kolumny, a czwarty o 3 kolumny
taka operacja może zostać wykonana dość sprawnie na
" Ponieważ takie przesunięcie sprowadza się jedynie do
8-bitowym procesorze lub wykorzystując pełną moc
zmiany uporządkowania danych w pamięci, nie
procesora 32-bitowego
przedstawia ono problemu dla żadnych procesorów.
a oc(x) b
a0,0 a0,j a0,2 a0,3 b0,0 b0,j b0,2 b0,3
0,1 0,1
a b c d brak przesunięcia a b c d a1,0 a1,j a1,2 a1,3 b1,0 b1,j b1,2 b1,3
a b
1,1 1,1
e f g h przesunięcie o 1 bajt f g h e a2,0 a2,j a2,2 a2,3 b2,0 b2,j b2,2 b2,3
2,1
a b2,1
i j k l przesunięcie o 2 bajty k l i j
a3,0 a3,1 a3,2 a3,3 b3,0 b3,j b3,2 b3,3
3,1
a b
3,j
m n o p p m n o
przesunięcie o 3 bajty
Przekształcenie MixColumn Dodawanie klucza rundy
" Kolumny Stanu są traktowane jako wielomiany w GF(28) i " Dla każdej rundy generowany jest z klucza pierwotnego
są mnożone przez c(x) specjalny klucz rundy, który zostaje w tej transformacji
połączony z macierzą danych za pomocą operacji XOR
" Można to zapisać jako mnożenie macierzy, gdzie
b(x)=c(x)Äða(x). " Poszczególne komórki (bajty) klucza sÄ… XORowane z
odpowiednimi komórkami (bajtami) macierzy Stanu
b0 02 03 01 01 a0
éð Å‚ð éð Å‚ð éð Å‚ð
Ä™ðb Å›ð Ä™ð01 02 03 01Å›ð Ä™ða Å›ð
1 1
Ä™ð Å›ð Ä™ð Å›ð Ä™ð Å›ð
=ð ×ð
Ä™ðb2 Å›ð Ä™ð Å›ð Ä™ða2Å›ð
01 01 02 03
Ä™ð Å›ð Ä™ð Å›ð Ä™ð Å›ð
3 3
ëðb ûð ëð03 01 01 02ûð ëða ûð
9
2014-03-18
Bezpieczeństwo algorytmu
Rozszerzanie klucza
Rijndael
" Operacje MixColumn i ShiftRow zapewniajÄ… silne
//RotByte(W) zwraca słowo w którym bajty są permutacją
//(wejściowe (a,b,c,d) daje na wyjściu (b,c,d,a) rozpraszanie(zamiana jednego bitu stanu wpływa na
//Rcon  tablica zawierająca stałe
wszystkie bity stanu w małej liczbie rund)
KeyExpansion(byte Key[4*Nk], word W[Nb*(Nr+1)])
" Operacje ByteSub i dodawanie klucza rundy zapewniajÄ…
{
silne mieszanie (zgubienie zależności  na podstawie
for i=0 to (Nk-1)
rezultatu jednej rundy nie można wywnioskować
W[i]=(Key[4*i],Key[4*i+1],Key[4*i+2],Key[4*i+3]);
macierzy stanu na poczÄ…tku rundy)
for i=Nk to ((Nb*(Nr+1))-1)
" Aby przeprowadzić kryptoanalizę różnicową, między
{
poszczególnymi rundami muszą istnieć przewidywalne
temp=W[i-1];
różnice. Udowodniono, że odpowiednie
if ((i mod Nk)==0)
prawdopodobieństwa wykorzystywane przy
temp=SubByte(RotByte(temp)) XOR Rcon[i/Nk];
kryptoanalizie DES-a w przypadku Rijndaela nie sÄ…
W[i]=W[i-Nk] XOR temp;
wystarczajÄ…ce do przeprowadzenia skutecznego ataku
}
}
Bezpieczeństwo algorytmu
Rijndael
" Udowodniono, że zależności danych pomiędzy rundami
dla Rijndaela są tak małe, iż kryptoanaliza liniowa jest
całkowicie nieskuteczna
" Istnieją ataki (np. Square, XSL), które są zdolne do
złamania algorytmu Rijndaela ale dla liczby rund
Dziękuję za uwagę
znacznie mniejsze niż określone w standardzie
10