2014-03-18

1

Bezpieczeństwo

i ochrona danych

Algorytmy blokowe

Agenda

• Charakterystyka
• Sieci Fiestela
• DES
• IDEA
• AES

Algorytmy symetryczne

• Klucz szyfrujący i deszyfrujący jest taki sam
• Dwie klasy kryptosystemów: blokowe i strumieniowe

1 …… 1 …… 0 ……0 ……0

E

1……...1……..1…….0…….1

100110110100010111010010

110010011101010010001001

E

E

E

E

100110110100010111010010

110010011101010010001001

100110

110100

010111

010010

E

E

E

E

110010

011101

010010

001001

…

…

…

…

Algrorytm Strumieniowy

Algorytm Blokowy

Algorytmy blokowe

• Szyfry blokowe dzielą tekst jawny na bloki o stałej

długości i wynikowy kryptogram ma taką samą długość

• Blokowe algorytmy szyfrują pojedyncze bloki tekstu

jawnego wykorzystując skomplikowane przekształcenia

szyfrujące

• Przykład:

– DES: blok 64 bit
– AES: blok 128 bit

• Algorytmy blokowe mogą pracować w różnych trybach

(tryby pracy algorytmu)

Algorytmy blokowe

• Algorytmy blokowe propagują w pewnym ograniczonym

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łasności algorytmu szyfrowania są zależne również od

trybu pracy algorytmu i sposobu jego wykorzystania.

• Dla różnych trybów pracy, ten sam algorytm może

przejawiać różne własności.

Algorytmy blokowe

• Algorytmy blokowe są współczesną wersją

książek kodowych

• W rzeczywistości, algorytm blokowy jest

zestawem wielu książek kodowych
(liczba i typ książki zależy od klucza)

• Wspólny klucz wymusza użycie jednej książki

• Zmiana klucza powoduje wybór innej książki

2014-03-18

2

Algorytmy blokowe

• Jak szyfrować tekst o długości przekraczającej

długość bloku?

• Nowy klucz dla każdego kolejnego bloku?

– Problem taki sam jak w przypadku one-time pad

• Szyfrować każdy blok niezależnie?
• Szyfrować kolejne bloki zależnie od bloków

wcześniejszych?

• Jak szyfrować bloki niekompletne?

C. Shannon

• W roku 1949 Shannon wprowadził koncepcję sieci

podstawieniowo-przestawieniowyhc
(ang. substitution-permutation (S-P) networks)

• Podstawa dla współczesnych algorytmów

blokowych

• Sieci S-P opierają się na dwóch podstawowych

operacjach kryptograficznych:

– Podstawieniu (S-box)
– Przestawieniu (P-box) (transposition)

Mieszanie i plątanie

Shannon, twórca teorii informacji przedstawił w 1949 roku

dwie główne zasady szyfrowania:

• Mieszanie (Konfuzja) oznacza rozmycie zależności

pomiędzy tekstami jawnymi a ich zaszyfrowanymi
wersjami

• Rozpraszanie (Dyfuzja)oznacza rozłożenie zawartych w

tekście jawnym informacji w całym tekście
zaszyfrowanym

Sieci Feistela

• Horst Feistel opracował tzw. Szyfrator

feistela (feistel cipher)

– Implementacja koncepcji Shannona dotyczącej

podstawień i przestawień

– Blok wejściowy dzielony jest na dwie części
– Przetwarzane wielokrotnie w procesie tzw. Algorytmu

rundy

– Wykonują podstawienie na lewej części danych
– Prawa część poddawana jest przestawieniom
– Części są zamieniane ze sobą po kolejnej rundzie

Szyfr Feistel

• Feistel cipher odnosi się do klasy algorytmów i nie jest

jednym konkretnym algorytmem

• Dwie części tekstu jawnego = (L

0

,R

0

)

• Dla każdej rundy i=1,2,...,n, oblicz

L

i

= R

i



1

R

i

= L

i



1



F(R

i



1

,K

i

)

gdzie F jest funkcją rundy (nie musi być odwracalna) i

K

i

jest podkluczem (kluczem rundy)

• Kryptogram= (L

n

,R

n

)

Szyfr Feistel

• Deszyfracja:

– Kryptogram= (L

n

,R

n

)

– Dla każdej rundy i=n,n



1,…,1, oblicz

R

i



1

= L

i

L

i



1

= R

i



F(R

i



1

,K

i

)

gdzie F jest funkcją rundy i K

i

jest

podkluczem

– Tekst jawny = (L

0

,R

0

)

– Możliwe różne wersje funkcji F
– Lecz bezpieczne jedynie dla pewnych F

2014-03-18

3

Sieci Feistela

• Szyfrowanie
L

i+1

= R

i

R

i+1

= L

i

XOR f

S,i

(R

i

)

• Właściwość
L

i

= (L

i

XOR f

S,i

(R

i

)) XOR f

S,i

(R

i

) = R

i+1

XOR f

S,i

(R

i

)

• Deszyfrowanie
R

n-1

= L

n

L

n-1

= R

n

XOR f

S,n-1

(R

n-1

)

. . .
R

0

= L

1

L

0

= R

1

XOR f

S,0

(R

0

)

L

i

R

i

f

Klucz rundy

XOR

L

i+1

R

i+1

Sieci Feistela

• Własności:

– Rozmiar bloku

• Zwiększenie długości bloku zwiększa bezpieczeństwo, lecz spowalnia

szyfrowanie

– Rozmiar klucza

• Zwiększenie długości klucza zwiększa bezpieczeństwo (utrudnia

przeszukiwanie kompletne), lecz może spowalniać algorytm

– Liczba rund

• Zwiększa bezpieczeństwo lecz spowalnia działanie

– Sposób generowania kluczy rund

• Większa złożoność utrudnia analizę lecz spowalnia szyfrowanie

– Funkcja rundy

• Większa złożoność utrudnia analizę lecz spowalnia szyfrowanie

– Szybkość szyfrowania/deszyfrowania

• Ułatwia stosowanie i testowanie

Efekt lawinowy

• Efektem lawinowym określamy intensywniejszy niż dla

rozpraszania ‘rozmazanie’ tekstu jawnego w tekście

zaszyfrowanym

• Jest spotykany dla szyfrowania blokowego
• Każdy bit zaszyfrowanego tekstu zależy od wszystkich

bitów tekstu jawnego w danym bloku

• Dla zmiany pojedynczego bitu tekstu jawnego lub klucza,

każdy bit tekstu zaszyfrowanego powinien zmienić swoją

wartość z prawdopodobieństwem

równym dokładnie 50%

• Kryptoanaliza różnicowa wykorzystuje nawet niewielkie

odstępstwo od tej zasady

Algorytm DES - historia

• 1971 – pierwszy patent dotyczący algorytmu Lucifer

opracowanego przez Horsta Fiestela i jego kolegów w
IBM (64-bit blok,128-bit)

• 1973 – NBS (National Bureau of Standards) ogłasza

konkursu na algorytm szyfrujący

• 1977 – FIPS (wcześniej NBS) publikuje algorytm DES

(ang. Data Encryption Standard) oparty na Lucifer jako
standard FIPS 46

• 1999 – DES potwierdzony po raz 4 przez NIST w wersji

Triple DES jako FIPS 46-3

• 2001 – publikacja AES (Advanced Encryption Standard)

jako FIPS 197

• 2005 – NIST wycofuje DES (FIPS 46-3)

DES w pigułce

• Dane są szyfrowane w 64-bitowych blokach
• Klucz ma długość 56 bitów
• Algorytm produktowy – stosuje transpozycje w kolejnych

etapach (iteracjach)

• 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,

ale w odwrotnej kolejności

• Najważniejszym elementem algorytmu są S-bloki (ang.

S-box)

DES - kontrowersje

• Kontrowersje budził fakt oparcia

konstrukcji algorytmu o klucz 56 bitowy, w
kontekście 128 bitowego klucza alg.
Lucifer będącego pierwowzorem DES

• Podejrzewany o istnienie ‘tylnych drzwi’

• Lata użytkowania i analizy nie

potwierdziły wątpliwości

2014-03-18

4

Ogólny schemat DES

Permutacja

wstępna

Permutowany

wybór 1

Iteracja 1

Cykliczne przesu-

nięcie w lewo

Permutowany

wybór 2

Iteracja 2

Cykliczne przesu-

nięcie w lewo

Permutowany

wybór 2

K

1

K

2

Iteracja 16

Cykliczne przesu-

nięcie w lewo

Permutowany

wybór 2

K

16

Zamiana bloków

32-bitowych

Odwrotność per-
mutacji wstępnej

64-bitowy tekst jawny

56-bitowy klucz

64-bitowy tekst zaszyfrowany

Permutacja wstępna

• Permutację wstępną IP i jej odwrotność IP

-1

definiuje poniższa

tabela

• Obie funkcje są odwrotne względem siebie
• Jeżeli szyfrujemy blok M to tekst po permutacji wygląda

następująco X=IP(M)

• 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

Z bitu wejściowego

58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4

Bit wyjściowy

17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

Z bitu wejściowego

62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8

Bit wyjściowy

33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

Z bitu wejściowego

57 49 41 33 25 17 9

1 59 51 43 35 27 19 11 3

Bit wyjściowy

49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64

Z bitu wejściowego

61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7

L

i-1

R

i-1

C

i-1

32 bity

32 bity

28 bity

D

i-1

28 bity

Rozszerzenie/

permutacja (tablica E)

XOR

Podstawienie/wybór

(S-blok)

Permutacja P

XOR

48

48

32

32

L

i

R

i

32

Przesunięcie(a)

w lewo

Przesunięcie(a)

w lewo

Permutacja/skrócenie

(permutowany wybór)

48

C

i

D

i

Iteracja algorytmu DES

Permutacja rozszerzająca

• Permutacja rozszerzająca powoduje wygenerowanie z 32

bitów wejściowych 48 bitów wyjściowych według
podanej tabeli

Bit wyjściowy

1

2

3

4

5

6

7

8

9 10 11 12 13 14 15 16

Z bitu wejściowego

32 1

2

3

4

5

4

5

6

7

8

9

8

9 10 11

Bit wyjściowy

17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

Z bitu wejściowego

12 13 12 13 14 15 16 17 16 17 18 19 20 21 20 21

Bit wyjściowy

33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

Z bitu wejściowego

22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 1

S-blok

R

32 bity

Rozszerzenie/

permutacja (tablica E)

XOR

Permutacja P

48

48

32

48

Klucz

S

2

S

3

S

4

S

5

S

6

S

7

S

1

S

8

S-blok

• Pierwszy i ostatni bit wejścia S-bloku wskazuje odpowiedni wiersz

tabeli S-bloku

• Środkowe 4 bity określają kolumnę
• Na przykład
wejście: 011011
wiersz 01 (1)
kolumna 1101 (13)
wyjście: 5 (0101)

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

2014-03-18

5

Algorytm IDEA

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
• Stosowany jest 128 bitowy klucz

Założenia projektowe
algorytmu IDEA

• Zastosowanie 16-bitowych podbloków
• Zastosowanie prostych operacji arytmetycznych
• Podobieństwo między szyfrowaniem i deszyfrowaniem
• Regularna struktura ułatwiająca realizację w technice

VLSI

Skuteczność kryptograficzna IDEA

• Długość bloków powinna być duża, by utrudnić

kryptoanalizę

• Długość klucza powinna uniemożliwić atak siłowy.
• Mieszanie (konfuzja) - zależność tekstu zaszyfrowanego

od tekstu jawnego i klucza powinna być skomplikowana,
aby utrudnić kryptoanalizę

• Rozpraszanie (dyfuzja)- każdy bit wejścia powinien

wpływać na każdy bit tekstu zaszyfrowanego

Mieszanie w algorytmie IDEA

W IDEA mieszanie uzyskuje się za pomocą trzech operacji

wykonywanych na dwóch wejściowych 16-bitowych

blokach:

• XOR logiczny oznaczany znakiem



• Dodawanie liczb całkowitych modulo 2

16

(65536)

oznaczane jako . Dane wejściowe to nieujemne liczby

16-bitowe

• Mnożenie liczb całkowitych modulo 2

16

+1 (65537)

oznaczane jako znak

Rozpraszanie w algorytmie IDEA

• Rozpraszanie jest osiągane za pomocą

podstawowej jednostki algorytmu

nazywanej strukturą

mnożenia/dodawania MA (ang.

multiplication/addition)

• Struktura ta produkuje dwa 16-bitowe

wyniki (G

1

,G

2

) z dwóch 16-bitowych

wartości wejściowych tekstu jawnego

(F

1

,F

2

) i dwóch 16-bitowych podkluczy

wyprowadzanych z klucza (Z

1

,Z

2

)

Z

5

F

1

F

2

Z

6

G

1

G

2

2014-03-18

6

Szyfrowanie za pomocą IDEA

Iteracja 1

Iteracja 2

Z

1

Iteracja 8

Przekształcenie

wyniku

64-bitowy tekst jawny X

64-bitowy tekst zaszyfrowany Y

X

1

X

2

X

3

X

4

Z

6

...

W

11

W

12

W

13

W

14

Z

7

...

Z

12

W

21

W

22

W

23

W

24

W

71

W

72

W

73

W

74

Z

43

...

Z

48

W

81

W

82

W

83

W

84

Y

1

Y

2

Y

3

Y

4

Z

49

...

Z

52

Generator

podkluczy

128-bitowy klucz Z

Z

1

Z

52

. . .

Z

5

Z

6

X

1

X

2

X

3

X

4

Z

3

Z

4

Z

1

Z

2

W

11

W

12

W

13

W

14

Etap przekształcania wyników
algorytmu IDEA

W

81

W

82

W

83

W

84

Z

51

Z

52

Z

49

Z

50

Y

1

Y

2

Y

3

Y

4

Generowanie podkluczy w
algorytmie IDEA

• 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

• Następnie cyklicznie przesuwamy klucz w lewo o 25

bitów i generujemy kolejne 8 podkluczy

• Procedurę powtarzamy do wygenerowanie 52

podkluczy

128 bitowy klucz

Z1

Z2

Z3

Z4

Z5

Z6

Z7

Z8

Z9

Z10

Z11

Z12

Z13

Z14

Z15

Z16

Z15

Z18

Z19

Z20

Z17

Algorytm AES

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)

• 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

2014-03-18

7

Kalendarium konkursu AES

• 02.01.1997 Ogłoszenie konkursu.

Zgłoszenie kandydatów do 12.09.1997

• 15.04.1997 Dokładne sformułowanie kryteriów dla

nowego algorytmu

• 20.08.1998 Pierwsza konferencja AES.

NIST ogłasza dopuszczenie 15 algorytmów do konkursu.

Rozpoczyna się ich publiczna analiza

• Marzec 1999 Druga konferencja AES.

Dyskusja dotychczasowych rezultatów

• 15.04.1999 Koniec publicznego badania kandydatów.

Pięć algorytmów wybrano do finału (MARS, RC6,

Rijndael, Sperpent, Twofish)

Kalendarium konkursu AES

• 15.04.1999 Koniec publicznego badania kandydatów.

Pięć algorytmów wybrano do finału według

następującego głosowania

– Rijndael: 86 positive, 10 negative
– Serpent: 59 positive, 7 negative
– Twofish: 31 positive, 21 negative
– RC6: 23 positive, 37 negative
– MARS: 13 positive, 83 negative

Kalendarium konkursu AES

• 13/14.04.2000 Trzecia konferencja AES.

Omawiane są analizy 5 finalistów

• 15.05.2000 Zakończenie otwartych dyskusji
• 02.10.2000 Ogłoszenie zwycięzcy – algorytmu Rijndael.
• Listopad 2000 Udostępnienie standardu FIPS-197

Można zgłaszać komentarze i uwagi

• Luty 2001 Koniec publicznej dyskusji nt. standardu
• Kwiecień-Czerwiec 2001 Zatwierdzenie standardu FIPS

Dlaczego wygrał Rijndeal

• Znakomita kombinacja gwarantowanego poziomu

bezpieczeństwa, wydajności, efektywności i łatwości
implementacji

• Rijndael charakteryzuje się bardzo dobrą wydajnością

zarówno przy implementacji sprzętowej, jak i
programowej uwzględniającej różne środowiska i
systemy operacyjne

• Testy wykazały, że nie wymaga dużo pamięci

operacyjnej, co sprawia, że można go stosować w wielu
niedostępnych dla innych algorytmów miejscach

Rijndael

• Algorytm blokowy (128, 192 lub 256 bitowe bloki

danych)

• Szyfrowanie jest symetryczne, zatwierdzono klucze o

długościach 128, 192 i 256 bitów

• Proces szyfrowania podlega iteracjom, przy czym

rozróżnia się:

– rundę wstępną,
– pewną ilość rund standardowych, z których każda posiada 4

transformacje,

(ilość rund zależy od długości klucza i wynosi odpowiednio 10, 12

lub 14)

– rundę końcową

Rijndael

• Został zatwierdzony jako następca algorytmu DES

• Rijndael nie jest chroniony żadnymi zastrzeżeniami

patentowymi, więc nie wymaga opłat licencyjnych

• Spełnia 3 główne założenia postawione przez twórców

algorytmu:

– odporność na wszystkie znane ataki,
– szybkość pracy i zwartość kodu na różnych platformach,
– łatwość implementacji

2014-03-18

8

Rijndael w pigułce

• Aktualny stan wiedzy w zakresie kryptoanalizy nie

pozwala na skuteczny atak na wiadomości szyfrowane

tym algorytmem

• Atak brutalny, czyli sprawdzenie wszystkich możliwych

kluczy szyfrujących jest praktycznie niewykonalny ze

względu na długość klucza

• Jest łatwy do implementacji sprzętowej (większość

rodzajów procesorów, smartcard) i programowej

(wiele popularnych języków programowania)

Szczegóły algorytmu Rijndael

• Podstawowe pojęcia służące do opisu algorytmu to "Stan"

i "runda"

• Runda (ang. round) to odpowiednik standardowego

etapu obliczeń mającym jako parametr tzw. Klucz Rundy
(ang. Round Key)

• Z reguły runda jest superpozycją, co najmniej 2 bijekcji

tzw. podstawienia i permutacji, w Rijndaelu tych
przekształceń jest więcej

Szczegóły algorytmu Rijndael

• Przekształcenia składające się na każdą rundę operują na

pewnej macierzy prostokątnej stanowiącej wynik

pośredni kolejnych obliczeń podczas realizacji algorytmu

i nazywanej Stanem (ang. State)

• Jest to macierz o współczynnikach w ciele GF(2

8

) lub

inaczej w zbiorze {0,1}

8

czyli macierz, której

współczynniki to bajty

• Macierz bajtowa Stanu ma 4 wiersze i Nb kolumn (Nb to

długość bloku podzieloną przez 32), Nb=4, 6 lub 8

Szczegóły algorytmu Rijndael

• Klucz szyfrujący jest również reprezentowany jako macierz o 4

wierszach

• Liczbę kolumn tego klucza oznaczamy przez Nk
• Liczba Nk jest równa długości klucza podzielonej przez 32; Nk=4,

6 lub 8

• Długość klucza i bloku, czyli Nk i Nb możemy zmieniać niezależnie
• Liczba rund Nr stosowana w algorytmie zależy od Nb i Nk

Nb

Nk

Nr

Nb

Nk

Nr

Nb

Nk

Nr

4

4

10

4

6

12

4

8

14

6

4

12

6

6

12

6

8

14

8

4

14

8

6

14

8

8

14

Runda 1

Runda 2

Runda 10

128-bitowy tekst jawny

128-bitowy tekst zaszyfrowany

Klucz

rundy 1

Generator

kluczy rund

128-bitowy klucz

T e k s t j a w n y w 1 2

T t w w
e n
k j y 1
s a 2

Klucz

rundy 2

Klucz

rundy 10

$ * a x
- \ & ^
{ : C g
u S . !

$ * a x - \ & ^ { : C g u S . !

Macierz

Stanu

ByteSub

ShiftRow

MixColumn

AddRoundKey

Ogólny opis algorytmu

//State –macierz stanu, CipherKey – klucz
Rijndael(State,CipherKey)
{
KeyExpansion(CipherKey,ExpandedKey) ;
AddRoundKey(State,ExpandedKey);
for i=1 to (Nr-1)
{
Round(State,ExpandedKey+Nb*i);
}
FinalRound(State,ExpandedKey+Nb*Nr);
}

2014-03-18

9

Opis jednej rundy algorytmu

• Przekształcenie rundy jest bijekcją będąca superpozycją

4 bijekcji składowych

• Runda składa się z następujących czterech przekształceń

operujących na macierzy Stanu

– przekształcenia ByteSub
– przekształcenia ShiftRow
– przekształcenia MixColumn
– dodawania klucza rundy

• Ostatnia runda nie zawiera przekształcenia MixColumn

Przekształcenie ByteSub

• Przy transformacji ByteSub operuje się na

poszczególnych elementach macierzy Stanu, które są
pojedynczymi bajtami

• Każdy bajt przechodzi transformację, którą ze względów

historycznych nazwano S-Boxem i jest wpisywany w to
samo miejsce

• W fazie tej wykonuje się jedynie operacje na bajtach, a

zatem jest to łatwe nawet w procesorach 8-bitowych

S-Box

b b b b
b b b b
b b b b
b b b b

0,0

0,1

0,2

0,3

1,0

1,1

1,2

1,3

2,0

2,1

2,2

2,3

3,0

3,1

3,2

3,3

a

0,0

a a a

a a a a
a a a a
a a a a

0,1

0,2

0,3

1,0

1,1

1,2

1,3

2,0

2,1

2,2

2,3

3,0

3,1

3,2

3,3

a

i,j

b

i,j

Przekształcenie ShiftRow

• Ta transformacja przesuwa cyklicznie kolejne wiersze

macierzy o odpowiednią liczbę pozycji

• Wartości przesunięcia zależą od wielkości bloku i klucza

- dla naszych danych pierwszego wiersza się nie

przesuwa, drugi przesuwa się o 1 kolumnę, trzeci o 2

kolumny, a czwarty o 3 kolumny

• Ponieważ takie przesunięcie sprowadza się jedynie do

zmiany uporządkowania danych w pamięci, nie

przedstawia ono problemu dla żadnych procesorów.

a b c d
e f g h
i j k l
m n o p

a b c d
f g h e
k l i j
p m n o

brak przesunięcia

przesunięcie o 1 bajt

przesunięcie o 2 bajty

przesunięcie o 3 bajty

Przekształcenie MixColumn

• Transformacja MixColumn miesza wartości zawarte w

jednej kolumnie w dość skomplikowany sposób,
zmieniając jednocześnie ich wartości

• Dzięki zastosowaniu specjalnych struktur algebraicznych

taka operacja może zostać wykonana dość sprawnie na
8-bitowym procesorze lub wykorzystując pełną moc
procesora 32-bitowego

c x

( )

b b b b
b b b b
b b b b
b b b b

0,0

0,1

0,2

0,3

1,0

1,1

1,2

1,3

2,0

2,1

2,2

2,3

3,0

3,1

3,2

3,3

a a a a
a a a a
a a a a
a a a a

0,0

0,1

0,2

0,3

1,0

1,1

1,2

1,3

2,0

2,1

2,2

2,3

3,0

3,1

3,2

3,3

a

0,j

a

1,j

a

2,j

a

3,j

b

0,j

b

1,j

b

2,j

b

3,j

o

Przekształcenie MixColumn

• Kolumny Stanu są traktowane jako wielomiany w GF(2

8

) i

są mnożone przez c(x)

• Można to zapisać jako mnożenie macierzy, gdzie

b(x)=c(x)



a(x).













































































3

2

1

0

3

2

1

0

02

01

01

03

03

02

01

01

01

03

02

01

01

01

03

02

a

a

a

a

b

b

b

b

Dodawanie klucza rundy

• Dla każdej rundy generowany jest z klucza pierwotnego

specjalny klucz rundy, który zostaje w tej transformacji
połączony z macierzą danych za pomocą operacji XOR

• Poszczególne komórki (bajty) klucza są XORowane z

odpowiednimi komórkami (bajtami) macierzy Stanu

2014-03-18

10

Rozszerzanie klucza

//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)
//Rcon – tablica zawierająca stałe

KeyExpansion(byte Key[4*Nk], word W[Nb*(Nr+1)])
{
for i=0 to (Nk-1)
W[i]=(Key[4*i],Key[4*i+1],Key[4*i+2],Key[4*i+3]);
for i=Nk to ((Nb*(Nr+1))-1)
{
temp=W[i-1];
if ((i mod Nk)==0)
temp=SubByte(RotByte(temp)) XOR Rcon[i/Nk];
W[i]=W[i-Nk] XOR temp;
}
}

Bezpieczeństwo algorytmu
Rijndael

• Operacje MixColumn i ShiftRow zapewniają

silne

rozpraszanie

(zamiana jednego bitu stanu wpływa na

wszystkie bity stanu w małej liczbie rund)

• Operacje ByteSub i dodawanie klucza rundy zapewniają

silne mieszanie

(zgubienie zależności – na podstawie

rezultatu jednej rundy nie można wywnioskować

macierzy stanu na początku rundy)

• Aby przeprowadzić kryptoanalizę różnicową, między

poszczególnymi rundami muszą istnieć przewidywalne

różnice. Udowodniono, że odpowiednie

prawdopodobieństwa wykorzystywane przy

kryptoanalizie DES-a w przypadku Rijndaela nie są

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
znacznie mniejsze niż określone w standardzie

Dziękuję za uwagę