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ť

PR: Staňte sa špecialistom na alarmy. Certifikované školenie aj vo vašom meste!

31.08.2018 08:01

Láka vás začať montovať alarmy prestížnej značky Jablotron? Chcete sa stať certifikovaným odborníkom v tejto oblasti? Tak si do svojho diára poznačte termíny najbližších školení:  18 a 19. 9. 2018  v  ...

Bezpečnosť

Startup učí autonómne vozidlá rozpoznávať zámery chodcov, či vstúpia na cestu alebo počkajú

22.08.2018 00:10

Chodci predstavujú jednu z najväčších výziev pre autonómne vozidlá - nakoľko ostatné autá sa pohybujú viac-menej predvídateľným spôsobom, no pohyb chodcov je nepravidelný a ťažko sa dá vopred odhadnúť ...

Bezpečnosť

Hackeri by mohli zneužiť faxy v multifunkčných zariadeniach na ovládnutie celej firemnej siete

20.08.2018 00:05

Vo veku okamžitých správ cez internet sa fax považuje za archaický kus technológie. No výskumní pracovníci zo spoločnosti Check Point varujú, že kybernetickí kriminálnici môžu využívať zraniteľnosti, ...

q

Žiadne komentáre

Vyhľadávanie

e-learnmedia_2018

Najnovšie videá



PC forum button