Strona główna

1. rijndael podstawy matematyczne


Pobieranie 111.11 Kb.
Data19.06.2016
Rozmiar111.11 Kb.

1.RIJNDAEL




    1. Podstawy matematyczne


Będziemy rozpatrywali bajty

b = b7b6b5b4b3b2b1b0, bi  { 0, 1}


jako reprezentacje elementów ciała skończonego GF (28).

Reprezentacja elementów ciała w bazie wielomianowej :

b7x7 + b6x6 + b5x5 + b4x4 + b3x3 + b2x2 + b1x1 + b0

daje wzajemnie jednoznaczną odpowiedniość między elementami tego ciała a bajtami. Struktura algebraiczna ciała GF(28) określa działania na bajtach.



Dodawanie jest binarnym dodawaniem (wielomianów) bajtów – jest to bitowa operacja EXOR oznaczana .

Mnożenie w GF(28) jest zdefiniowane jako mnożenie binarnych wielomianów modulo określony nierozkładalny binarny wielomian stopnia 8. Dla Rijndaela wielomianem tym jest:

m(x) = x8 + x4 + x3 + x + 1.



Przykład


(x6 + x4 + x2 + x + 1) (x7 + x + 1) = (x13 + x11 + x9 + x8 + x6 + x5 + x4 + x3 + 1) mod m(x) = x7 + x6 + x4 + x3 + 1.

Operacja modulo polega na braniu reszty z dzielenia przez wielomian m(x). Powyższa operacja mnożenia w GF(28) określa operację mnożenia bajtów oznaczaną . Dla niezerowego wielomianu b(x)  GF(28) określony jest element odwrotny b-1(x) wzorem:

b(x)  b-1(x) = 1 mod m(x).

Określa to z kolei dla niezerowego bajtu b bajt odwrotny b-1 taki, że

b b-1 = 00000001.

Jeśli pomnożymy wielomian b(x) przez x to wynik x  b(x) otrzymujemy redukując wielomian

b7x8 + b6x7 + b5x6 + b4x5 + b3x4 + b2x3 + b1x2 + b0x

modulo m(x). Jeśli b7 = 0 to redukcja jest operacją identycznościową. Jeśli b7 = 1 to musimy odjąć (to samo co dodać) m(x); tzn. wykonać operację EXOR. Na poziomie bajtów mnożenie przez x (w zapisie szesnastkowym ‘02’ = 0000010) może być zaimplementowane jako lewe przesunięcie, a następnie jako warunkowa operacja EXOR z bajtem ‘1B’ reprezentującym wielomian m(x) bez wyrazu x8. Powyższa operacja oznaczona jest przez

a = xtime (b).

Mnożenie przez wyższe potęgi x może być zaimplementowane jako wielokrotne wykonanie operacji xtime. Dołączenie operacji dodawania daje nam implementacje mnożenia przez dowolny wielomian.



Wielomiany o współczynnikach z ciała GF(28).

4-bajtowy wektor odpowiada wielomianowi o współczynnikach z GF(28) stopnia mniejszego niż 4. Wielomiany o współczynnikach z GF(28) dodajemy wykonując operację EXOR na bajtach reprezentujących te współczynniki. Operacja mnożenia wielomianów jest bardziej skomplikowana. Niech

a(x) = a3x3 + a2x2 + a1x + a0,

b(x) = b3x3 + b2x2 + b1x + b0

będą wielomianami o współczynnikach z ciała GF(28).

Wtedy iloczyn

c(x) = a(x) b(x)

jest równy

c(x) = c6x6 + c5x5 + c4x4 + c3x3 + c2x2 + c1x1 + c0

gdzie:


c0 = a0  b0 c4 = a3  b1  a2  b2  a1  b3

c1 = a1  b0  a0  b1 c5 = a3  b2  a2  b3

c2 = a2  b0  a1  b1  a0  b2 c6 = a3  b3

c3 = a3  b0  a2  b1  a1  b2  a0  b3

Redukując wielomian c(x) modulo wybrany wielomian stopnia 4 otrzymujemy wielomian stopnia mniejszego niż 4. Dla Rijndaela tym wybranym wielomianem jest:

M(x) = x4 + 1.

Jest to wielomian rozkładalny ponieważ

x4 +1 = (x2 +1)2 nad ciałem GF(28).

Wykorzystując równość

xi mod (x4 +1) = xi mod 4,

iloczyn modularny wielomianów a(x) i b(x), który oznaczamy

d(x) = a(x) b(x),

dany jest wzorami

d(x) = d3x3 + d2x2 + d1x + d0,

gdzie

d0 = a0  b0  a3  b1  a2  b2  a1  b3



d1 = a1  b0  a0  b1  a3  b2  a2  b3

d2 = a2  b0  a1  b1  a0  b2  a3  b3

d3 = a3  b0  a2  b1  a1  b2  a0  b3.

O
perację mnożenia modularnego można zapisać w postaci macierzowej


Jeśli wielomian b(x) pomnożymy przez x to otrzymujemy

b3x4 + b2x3 + b1x2 + b0x.

Redukując modulo x4 + 1 otrzymujemy wielomian

b2x3 + b1x2 + b0x1 + b3.

Modularne mnożenie przez x

c(x) = x  b(x)

m
ożemy zapisać w następującej postaci macierzowej

Zatem modularnemu mnożeniu przez x, lub przez potęgi x, odpowiada cykliczne przesunięcie bajtów wewnątrz wektora.



    1. Założenia projektowe


W projekcie Rijndaela przyjęto następujące ogólne założenia.

  • Odporność przeciw znanym atakom kryptograficznym.

  • Szybkość i spójność implementacji na różnych platformach sprzętowych.

  • Prostota projektu.

Rijndael składa się z kolejno wykonywanych kilkunastu rund. Transformacje wykonywane w kolejnych rundach nie mają struktury sieci Feistela jak jest w tradycyjnych algorytmach blokowych, np. w DES-ie. Każda runda składa się z trzech różnych, odwracalnych, jednorodnych transformacji zwanych warstwami (ang. layers). Przez „jednorodność” rozumiemy, że każdy bit przekształconego stanu traktowany jest w jednakowy sposób. W poszczególnych rundach Rijndaela występują następujące warstwy.

  • Warstwa nieliniowa: równoległe zastosowanie S- skrzynek o wysokim stopniu nieliniowości.

  • Warstwa liniowa mieszająca: zapewnia dużą dyfuzję przez wiele rund.

  • Warstwa dodawania klucza: EXOR podklucza danej rundy z danym stanem.

Przed wykonaniem pierwszej rundy stosowana jest pojedyncza warstwa dodawania klucza. W celu nadania szyfrowi i jego odwrotności podobnej struktury, warstwa liniowa mieszająca w ostatniej rundzie jest różna od takiej warstwy w pozostałych rundach. Jest to odpowiednikiem braku przestawienia lewej i prawej połowy stanu w algorytmie DES.



    1. Specyfikacja algorytmu


W Rijndaelu długość bloków szyfrowanych i długość klucza może wynosić odpowiednio 128, 192 i 256 bitów. Przedstawimy wersję algorytmu gdy długość bloków szyfrowanych wynosi 128 oraz długość stosowanego klucza także wynosi 128 bitów. Poszczególne postaci tekstu jawnego po zastosowaniu kolejnych transformacji algorytmu będziemy nazywali stanami.

Stan będzie reprezentowany jako następująca tablica, której elementami są bajty




a00

a01

a02

a03

a10

a11

a12

a13

a20

a21

a22

a23

a30

a31

a32

a33

Dany blok teksu jawnego o długości 128 bitów przekształcany jest na taką samą tablicę numerując poszczególne bajty kolumnami w następujący sposób

a00, a10, a20, a30, a01, ..., a03 , a13, a23, a33.

Stan wyjściowy szyfru dany w postaci tablicy przekształcany jest w blok o długości 128 bitów grupując poszczególne bajty kolumnami. Podobnie 128 bitowy klucz szyfru reprezentowany jest jako tablica o bajtowych elementach




k00

k01

k02

k03

k10

k11

k12

k13

k20

k21

k22

k23

k30

k31

k32

k33

Dla przyjętej wyżej długości bloków tekstu i długości klucza w Rijdaelu ustalono, że



liczba rund algorytmu równa jest 10.

Dla dłuższych bloków tekstu lub dla dłuższego klucza liczba rund algorytmu jest odpowiednio większa.

Podstawową rundę algorytmu przedstawiamy w następujący sposób

Wejście



Warstwa nieliniowa






Warstwa liniowa mieszająca



Warstwa dodawania klucza



Podklucz kolejnej rundy





Wyjście


W postaci pseudo-kodu podstawową rundę algorytmu zapisujemy jak następuje
Round (State, Roundkey)

{

ByteSub (State);

ShiftRow (State);

MixColumn(State);

AddRoundKey (State,RoundKey);

}

Przekształcenia ShiftRow (przesunięcie wierszy) i MixColumn (mieszanie kolumn) stanowią warstwę liniową mieszającą.

W ostatniej rundzie Rijdaela warstwa liniowa mieszająca nie zawiera transformacji MixColumn.

FinalRound (State, RoundKey)

{

ByteSub (State);

ShiftRow (State);

AddRoundKey (State,RoundKey);

}

Opiszemy teraz poszczególne transformacje.


Transformacja ByteSub


Jest to jedyna nieliniowa transformacja stosowana w algorytmie. Działa ona niezależnie na każdy bajt stanu i ma postać skrzynki podstawieniowo –przestawieniowej o wymiarach 8  8. Każda skrzynka jest odwracalnym przekształceniem i jest złożeniem następujących dwóch operacji.

  • Branie elementu odwrotnego w GF(28), które działa na bajtach w opisany wyżej sposób.

  • Z
    astosowanie przekształcenia afinicznego danego w postaci macierzowej następującym wzorem

Zastosowanie opisanych wyżej S-skrzynek do danego stanu zapisujemy symbolicznie



ByteSub (State).

Poniższy rysunek ilustruje to graficznie





S-skrzynka
a0,0

a0,1

a0,2

a0,3




b0,0

b0,1

b0,2

b0,3


ai,j

bi,j
a1,0

a1




a1,3




b1,0




b1,2

b1,3

a2,0

a2




a2,3




b2,0




b2,2

b2,3

a3,0

a3,1

a3,2

a3,3




b3,0

b3,1

b3,2

b3,3


Transformacja ShiftRow

Stan reprezentowany jest, jak wyżej, jako bajtowa tablica o wymiarach 4  4.Transformacja ShiftRow działa na wierszach tej tablicy przesuwając cyklicznie każdy wiersz o określoną liczbę bajtów daną przez tabelę




Wiersz numer

0

1

2

3

Liczba przesunięć

0

1

2

3

Transformację ShiftRow ilustrujemy graficznie




m

n

o

p

nie ma przesunięcia



m

n

o

p

j

k

l

...

cykliczne przesunięcie o 1 bajt






j

k

l

d

e

f

...

cyklicznie przesunięcie o 2 bajty









d

e

w

x

y

z

cyklicznie przesunięcie o3 bajty











w

Dla wersji algorytmu z długością bloków szyfrowanych równą 192 i 256 bitów liczby przesunięć trzech ostatnich wierszy stanu są inne



Transformacja MixColumn


W transformacji tej kolumny danego stanu rozpatrywane są jako wielomiany nad GF(28) stopnia mniejszego od 4 (elementy kolumny są współczynnikami wielomianu) i mnożone są modulo x4 + 1 przez ustalony wielomian

c(x) = ‘03’ x3 + ‘01’ x2 +‘01’ x +‘02’ ,

gdzie współczynniki wielomianu zapisane są w reprezantacji szesnastkowej. Operację tę zapisujemy symbolicznie

b(x) = c(x)  a(x),

l
ub w postaci macierzowej
Jako element pseudo-kodu transformację tę zapisujemy

MixColumn (State)

co możemy zilustrować graficznie




a0,j

a1,j

a2,j

a3,j

a0,j




b0,j

b1,j

b2,j

b3,j

a0,j







 c(x)
a0,0

a0,1




a0,3




b0,0

b0,1




b0,3

a1,0

a1,1




a1,3




b1,0

b1,1




b1,3

a2,0

a2,1




a2,3




b2,0

b2,1




b2,3

a3,0

a3,1




a3,3




b3,0

b3,1




b3,3



Transformacja dodawania klucza


Dla każdej kolejnej rundy generowany jest podklucz o tej długości co długość przekształcanych stanów. Na koniec każdej rundy podklucz ten jest dodawany (operacja EXOR) do stanu wyjściowego z uprzednio wykonanej transformacji. Operację tę zapisujemy w pseudo-kodzie jako

AddRoundKey(State, RoundKey)

lub w postaci macierzowej




a0,0

a0,1

a0,2

a0,3




k0,0

k0,1

k0,2

k0,3




b0,0

b0,1

b0,2

b0,3

a1,0

a1,1

a1,2

a1,3



k1,0

k1,1

k1,2

k1,3


=

b1,0

b1,1

b1,2

b1,3

a2,0

a2,1

a2,2

a2,3

k2,0

k2,1

k2,2

k2,3

b2,0

b2,1

b2,2

b2,3

a3,0

a3,1

a3,2

a3,3




k3,0

k3,1

k3,2

k3,3




b3,0

b3,1

b3,2

b3,3

Przypomnijmy, że przed wykonaniem pierwszej, podstawowej rundy algorytmu wykonujemy operację dodania klucza do bloku wejściowego, będziemy to nazywali rundą zerową algorytmu. W ten sposób algorytm Rijndael składa się z 11 rund numerowanych od 0 do 10; rundy od 1 do 9 są identyczne. Natomiast runda 10 nie zawiera transformacji MixColumn. Do każdej rundy potrzebny jest 128 bitowy podklucz. Zatem do wykonania algorytmu, w prezentowanej tutaj wersji, potrzebne jest 11  128 = 1408 bitów materiału wszystkich podkluczy, które generowane są przy pomocy oddzielnego algorytmu (ang. key schedule) na podstawie 128-bitowego klucza głównego stosowanego w algorytmie.



Algorytm generowania podkluczy


Algorytm ten składa się z dwóch etapów.


  • Klucz główny szyfru jest przekształcany do tzw. klucza rozszerzonego (ang. expanded key) składającego się z 11 słów 32 bitowych co stanowi 1408 bitów.

  • Podklucze kolejnych rund są brane z klucza rozszerzonego w następujący sposób: podklucz do rundy nr.0 stanowią pierwsze 4 słowa klucza rozszerzonego, następny podklucz stanowią kolejne 4 słowa i tak dalej.

Klucz rozszerzony jest jednowymiarową tablicą o 4-bajtowych elementach składająca się z 44 słów o długości 32 bitów. Pierwsze 4 słowa stanowią klucz główny szyfru, następne słowa zdefiniowane są rekurencyjnie przy pomocy słów wcześniejszych. Klucz rozszerzony składa się ze słów

W[0], W[1], ..., W[43].

Przedstawiamy algorytm generowania klucza rozszerzonego w postaci pseudo-kodu


KeyExpansion(CipherKey, W)

{

for (i=0; i<4; i++) W[i] = CipherKey[i];

for (j=4; j<44; j+=4)

{

W[j] = W[j-4] ^ SubByte (Rot1(W[j-1])) ^ Rcon[j/4];

for (i=1; i<4 && i+j<44; i++)

W[i+j] = W[i+j-4] ^ W[i+j-1];

}

}
W powyższym kodzie Rot1 oznacza cykliczne przesunięcie bajtów w słowie, Rcon[i] jest stałą i-tej rundy określoną jak następuje

Rcon[i] = (RC[i], ‘00’, ‘00’, ‘00’, ‘00’),

gdzie


RC[0] = ‘01’,

Rc[i] = xtime (Rcon[i-1]).

Operacja SubByte zastosowana jest do 4-bajtowego słowa. Jak powiedzieliśmy wcześniej pierwsze cztery słowa klucza rozszerzonego pokrywają się z kluczem szyfru. Każde następne słowo W[i], jeśłi i nie jest wielokrotnością 4, równe jest EXOR słowa poprzedniego W[i-1] i słowa cztery pozycje wcześniejszego, tzn. W[i-4]. Słowa W[4i] na pozycjach będących wielokrotnością 4 są równe EXOR słowa W[4i-4] i wyniku operacji SubByte zastosowanej do Rot1(W[4j-1]) i EXOR ze stałą Rcon[i]. Kolejne 128 bitowe podklucze składają się z następujących 4 słów klucza rozszerzonego.

Podsumowując powyższy opis Rijndael jako algorytm szyfrujący składa się z:


  • rundy wstępnej polegającej na wykonaniu EXOR z podkluczem o indeksie 0,

  • dziewięciu rund podstawowych,

  • rundy końcowej.

W postaci pseudo-kodu algorytm Rijndael zapsiujemy:


Rijndael (State, CipherKey);

{

KeyExpansion (CipherKey, ExpandedKey);

for (i=1; i<10; i+1)

Round (State, ExpandedKey +4i);

FinalRound (State, ExpandedKey + 40);

}

W określonych implementacjach możemy wydzielić algorytm generowania podkluczy.



Szyfr odwrotny


W algorytmie odwrotnym poszczególne przekształcenia są transformacjami odwrotnymi do tych występujących w algorytmie szyfrującym, natomiast typ transformacji pozostaje bez zmian. W szyfrze odwrotnym należy dokonać zmian w algorytmie generowania podkluczy. Opiszemy teraz odwrotności poszczególnych transformacji Rijndaela.

Odwrotnością transformacji MixColumn jest cyklicznie przesunięcie wierszy stanu w następujący sposób




Wiersz numer

0

1

2

3

Liczba przesunięć

0

3

2

1

Odwrotnością transformacji MixColumn jest taka transformacja określona przez wielomian d(x) odwrotny modulo x4 + 1 do podanego wyżej wielomianu

c(x) = ‘03’ x3 + ‘01’ x2 + ‘01’ x + ’02’,

c(x)  d(x) =’01’.

Obliczamy, że

d(x) = ‘08’ x3 + ‘0D’ x2 + ‘09’ x +’0E’.

Transformacja AddRoundKey równa jest swojej odwrotności.

W postaci pseudo-kodu odwrotność warstwy podstawowej Rijndaela zapisujemy następująco



InvRound (State, RoundKey)

{

AddRoundKey (State, RoundKey);

InvMixColumn (State);

InvShift (State);

InvByteSub (State);

}

Dla odwrotności ostatniej warstwy odpowiednio mamy



InvFinalRound (State, RoundKey)

{

AddRoundKey (State, RoundKey);

InvShift (State);

InvByteSub (State);

}

Odwrotność całego szyfru zapisana w postaci powyższego pseudo-kodu składa się z następujących warstw



Wejście



Odwrotność warstwy końcowej




Odwrotność warstwy podstawowej






9 warstw


Odwrotność warstwy podstawowej




Runda dodawania klucza


Wyjście

Podany niżej równoważny opis szyfru odwrotnego wykorzystując następujące własności algebraiczne transformacji występujących w Rijndaelu.

Kolejność wykonania transformacji ShiftRow i ByteSub jest dowolna. Operacja ShiftRow dokonuje permutacji bajtów i nie zmienia wartości tych bajtów, natomiast operacja ByteSub działa na pojedynczych bajtach niezależnie od ich położenia. Ciąg transformacji



AddRoundKey (State, RoundKey);

InvMixColumn (State);

możemy zastąpić przez transformacje równoważne



InvMixColumn (State);

AddRoundKey (State, InvRoundKey);

gdzie klucz InvRoundKey otrzymujemy przez zastosowanie transformacji InvMixColumn do klucza RoundKey.

Zdefiniujemy teraz warstwę podstawową szyfru odwrotnego

I_Round (State, I_RoundKey)

{

InvByteSub(State);

InvShiftRow(State);

InvMixColumn (State);

}
I_FinalRound (State, I_RoundKey)

{

InvByteSub (State);

InvShiftRow (State);

AddRoundKey (State, RoundKey0);

}

Szyfr odwrotny możemy teraz przedstawić jak następuje


I_Rijndael (State, CipherKey)

{

I_KeyExpansion (CipherKey, I_ExpandedKey);

AddRoundKey (State, I_ExpandedKey + 40);

for (i =1; i < 10; i++)

Round (State, I_ExpandedKey + 4i);

I_FinalRound (State, I_ExpandedKey);

}
Klucz rozszerzony dla szyfru odwrotnego określamy na podstawie klucza podstawowego szyfru w następujący sposób

  • stosujemy operację rozszerzenie klucza,

  • stosujemy operację ...


©snauka.pl 2016
wyślij wiadomość