Image
11.9.2017 0 Comments

Praktická kryptológia 7. časť: AES

Týmto článkom sa vrátime k teórii, a to konkrétne k opisu algoritmu (šifry) Rijndael, ktorý sa stal víťazom súťaže vyhlásenej organizáciou NIST. Algoritmus bol prijatý v roku 2001 vo forme nového štandardu AES (Advanced Encryption Standard), ktorý je podrobne opísaný v publikácii FIPS PUB 197. Tá obsahuje úplnú charakteristiku šifry – použité matematické operácie, dôvody výberu jednotlivých parametrov a takisto možné spôsoby optimalizácie na 8 a 32-bitových platformách. V našich článkoch postupne predstavíme tzv. Galoisovo teleso, základné matematické operácie, ktoré sú v ňom definované, a štruktúru iteračnej blokovej šifry Rijndael vrátane jej operácií. Teóriu následne aplikujeme v praxi vo forme praktickej ukážky šifrovania/dešifrovania údajov pomocou AES.

Galoisovo teleso (Galois Field)

Galoisovo teleso je konečné (finite) teleso – množina 256 prvkov, ktorú označujeme ako GF(28), resp. GF(256). V tomto telese rozoznávame 256 rôznych 8-bitových (1-bajtových) čísel. Každé z nich je na bitovej úrovni zložené z kombinácie ôsmich číslic 0, resp. 1. Osem bitov reprezentuje bajt = jeden konkrétny prvok z GF(256). Prvok telesa zapisujeme pomocou polynómu s koeficientmi: a(x) = a7x7 + a6x6 + a5x5 + a4x4 + a3x3 + a2x2 + a1x1 + a0. Koeficienty môžu nadobúdať hodnoty z telesa GF(2), to znamená čísla 0 alebo 1, alebo z telesa GF(28), teda čísla 0x00 – 0xFF (v hexadecimálnom tvare), resp. 00000000 – 11111111 (v binárnom tvare).

V GF(28) definujeme matematické operácie – pre koeficienty z telesa GF(2) = (0, 1):

1.

Sčítanie

Bitový súčet koeficientov modulo 2 = XOR koeficientov,

pričom pre XOR platí: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 0

Napríklad pre:

a = (01010111), b = (10000011), c = a XOR b = (11010100)

(x6 + x4 + x2 + x + 1) + (x7 + x + 1) = x7 + x6 + x4 + x2

2.

Násobenie

Násobenie polynómov modulo nezmenšiteľný (irreducible) polynóm 8. stupňa:

m(x) = x8 + x4 + x3 + x + 1 = 0x11B = 100011011

c(x) = ( a(x) . b(x) ) modulo m(x)

Nezmenšiteľný (neredukovateľný) polynóm je taký polynóm, ktorý je deliteľný iba 1 alebo samým sebou. Je teda nedeliteľný (nefaktorizovateľný) dvoma existujúcimi polynómami. Redukcia pomocou m(x) zabezpečí, že výsledok násobenia dvoch polynómov bude takisto patriť do GF(28).

Pretože algoritmus Rijndael používa najmä násobenie dvoch prvkov, z ktorých prvý je konštantný a má malú hodnotu, možno zaviesť a využívať tzv. funkciu xtime(): b(x) = xtime( a(x) )

Napríklad pre násobenie číslom 2:

b(x) = ( 0x02 . a(x) ) = x . b(x) modulo m(x) = LeftShift( b(x) ) s podmienkou pretečenia cez 255, v takom prípade sa na výsledok aplikuje XOR 0x1B

Na násobenie rádovo väčšími číslami (higher powers) 0x04, 0x08, 0x10… sa na predošlý výsledok opakovane aplikuje funkcia xtime()

V GF(28) definujeme matematické operácie – pre koeficienty z telesa GF(28) = (0, 255):

1.

Sčítanie

Bitový súčet korešpondujúcich koeficientov modulo 2 = XOR koeficientov

2.

Násobenie

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

c0 = a0 . b0

c1 = a1 . b0 XOR a0 . b1

c2 = a2 . b0 XOR a1 . b1 XOR a0 . b2

c3 = a3 . b0 XOR a2 . b1 XOR a1 . b2 XOR a0 . b3

c4 = a3 . b1 XOR a2 . b2 XOR a1 . b3

c5 = a3 . b2 XOR a2 . b3

c6 = a3 . b3

Pretože výsledok c(x) nemožno reprezentovať pomocou 4 B = 32 bitov, výsledok sa redukuje pomocou polynómu 4. stupňa: m(x) = x4 + 1:

xj modulo (x4 + 1) = xj modulo 4

d(x) = ( a(x) . b(x) ) modulo m(x) = d3x3 + d2x2 + d1x + d0

d0 = a0 . b0 XOR a3 . b1 XOR a2 . b2 XOR a1 . b3

d1 = a1 . b0 XOR a0 . b1 XOR a3 . b2 XOR a2 . b3

d2 = a2 . b0 XOR a1 . b1 XOR a0 . b2 XOR a3 . b3

d3 = a3 . b0 XOR a2 . b1 XOR a1 . b2 XOR a0 . b3

resp. v maticovom zápise:

d0

=

a0

a3

a2

a1

 

b0

d1

a1

a0

a3

a2

b1

d2

a2

a1

a0

a3

b2

d3

a3

a2

a1

a0

b3

Podobne ako v prípade funkcie xtime() možno b(x) násobiť číslom, resp. násobkami čísla 2, čo predstavuje cyklický posun bajtov vektora:

c(x) = ( x . b(x) ) modulo m(x) = b2x3 + b1x2 + b0x + b3

resp. v maticovom zápise:

c0

=

00

00

00

01

 

b0

c1

01

00

00

00

b1

c2

00

01

00

00

b2

c3

00

00

01

00

b3


Rijndael substitution box (S-Box) v GF (28)

Štruktúra šifry Rijndael

Substitučný box šifry Rijndael je založený na opísanom GF(28). Dôvodom použitia neredukovateľného polynómu je dosiahnutie príslušného rozptylu (diffusion) nelineárnej permutačnej (substitučnej) funkcie. Programové generovanie S-Boxu využíva operácie LeftShift,  XOR a násobenie matíc (matrix multiplication).

Rijndael podobne ako DES používa Nr opakovaní (iterácií = rúnd) s variabilnou veľkosťou bloku zodpovedajúcemu prírastku základného bloku dĺžky 128 bitov o voliteľný násobok 32 bitov (to znamená 128, 160, 192, 224, 256). Štandard AES na rozdiel od Rijndael podporuje jedinú striktnú dĺžku bloku, a to 128 bitov.

Počet rúnd Nr je závislý od dĺžky bloku Nb a dĺžky kľúča Nk a vychádza z nasledujúcej tabuľky:

Nr = počet opakovaní

Nb = 4B (128b)

Nb = 6B (192b)

Nb = 8B (256b)

Nk = 4B (128b)

10

12

14

Nk = 6B (192b)

12

12

14

Nk = 8B (256b)

14

14

14

Jednotlivé medzivýsledky algoritmu sa nazývajú stavy (states) a sú reprezentované maticou so štyrmi riadkami a Nb (dĺžka bloku v bitoch/32) stĺpcami:

a00

a01

a02

...

a0Nb-1

a10

a11

a12

...

a1Nb-1

a20

a21

a22

...

a2Nb-1

a30

a31

a32

...

a3Nb-1

Šifrovacie kľúče sú veľmi podobne reprezentované maticou so štyrmi riadkami a Nk (dĺžka kľúča v bitoch/32) stĺpcami:

k00

k01

k02

...

k0Nk-1

k10

k11

k12

...

k1Nk-1

k20

k21

k22

...

k2Nk-1

k30

k31

k32

...

k3Nk-1

Pri šifrovaní sa zo vstupného Nk bitového kľúča (Key) vypočítajú kľúče patriace jednotlivým iteráciám (RoundKeys). Hovoríme o tzv. expanzii kľúča (Key Expansion), resp. o kľúčovom pláne (Key Schedule). Expanzia pracuje s tzv. slovami (words) s dĺžkou 4 bajty = 32 bitov. Prvých Nb rundových 4B kľúčov (slov) sa vypočíta z otvoreného textu pomocou funkcie XOR a uloží sa do príslušného stavu (matice).


Výpočet RoundKeys pre Nk = 128b

Stav sa spracuje Nr-1 krát, pričom výpočet sa realizuje pomocou nasledujúceho pseudokódu:

Iterácia(stav,RoundKey) {
  ByteSub(stav);
  ShiftRow(stav);
  MixColumn(stav);
  AddRoundKey(stav, RoundKey);
}

Nasleduje záverečná (final) iterácia:

FnálnaIterácia(stav,RoundKey) {
  ByteSub(stav);
  ShiftRow(stav);
  AddRoundKey(stav, RoundKey);
}

Pokračovanie nabudúce…

 

 

Zobrazit Galériu
Autor: Marek Sopko

Mohlo by Vás zaujímať

Bezpečnosť

5 tipov ako vybrať správny firemný firewall

19.09.2019 00:15

Kybernetickú bezpečnosť dnes čoraz viac firiem berie ako prioritu najvyššieho manažmentu. Napriek tomu mnoho organizácií stále nevie, ako správne budovať bezpečnostnú architektúru. Kľúčom k maximálne ...

Bezpečnosť

Google Nest Hub Max s Face Match vás sleduje naozaj stále

18.09.2019 00:10

Google Nest Hub Max sa javí ako pomerne inteligentné zariadenie. Má niekoľko zaujímavých funkcií, okrem iného dokáže zobraziť kalendár alebo obsah prispôsobený osobe, ktorá sa naň pozerá. To všetko b ...

Bezpečnosť

6 najväčších podnikových e-mailových hrozieb

17.09.2019 00:05

V roku 2019 je podľa niektorých odhadov poslaných a prijatých okolo 300 miliárd obchodných a osobných e-mailov každý deň a toto číslo do budúcnosti porastie, hlavne vo firemnej sfére. Rastúca e-mailo ...

q

Žiadne komentáre

Vyhľadávanie

AMCHAM 2019

Najnovšie videá

elearn

IT GALA stvorec 2019