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ť

Google Mapy vám umožnia zdieľať aj stav vašej batérie. Aby ostatní videli či ste ok, keď sa nehlásite

16.02.2018 00:05

Ak hľadáte priateľa na hromadnom podujatí alebo čakáte na niekoho, kto je na ceste k vám, zdieľanie polohy je nástroj, ktorý vám môže skvele poslúžiť. No keď sa priateľovi vybije batéria v telefóne, t ...

Bezpečnosť

Komplexné zabezpečenie od Jablotronu s videoverifikačnou kamerou

16.02.2018 00:00

Najväčšou slabinou prakticky všetkých zabezpečovacích zariadení sú falošné poplachy. Nejde len o zbytočné výjazdy k mačke, ktorá aktivovala niektorý senzor, ale hlavne o postupné otupenie pozornosti, ...

Bezpečnosť

Ako funguje zabezpečenie domácej siete od Esetu

06.02.2018 13:25

Nadväzujeme na článok o zabezpečení zariadení IoT v domácej sieti. Téma vás zaujala a dostali sme od vás niekoľko otázok, ktoré by sa podľa prvého slova dali rozdeliť do troch skupín: Prečo by niekto ...

Žiadne komentáre

Vyhľadávanie

PC forum button

Najnovšie videá