Teoria criptarii

Modulul 3 Bazele matematice ale criptrii

45

BAZELE MATEMATICE ALE CRIPTRII

3.1. Aritmetica pe clase de resturi modulo specificat Se prezint pentru nceput tabelele pentru operaiile de adunare, nmulire i ridicare la putere pe mulimea claselor de resturi modulo 7.

+ | 0 1 2 3 4 5 6 * | 0 1 2 3 4 5 6

^ | 0 1 2 3 4 5 6 0 | 0 1 2 3 4 5 6 0 | 0 0 0 0 0 0 0 1 | 1 2 3 4 5 6 0 1 | 0 1 2 3 4 5 6 1 | 1 1 1 1 1 1 1 2 | 2 3 4 5 6 0 1 2 | 0 2 4 6 1 3 5 2 | 1 2 4 1 2 4 1 3 | 3 4 5 6 0 1 2 3 | 0 3 6 2 5 1 4 3 | 1 3 2 6 4 5 1 4 | 4 5 6 0 1 2 3 4 | 0 4 1 5 2 6 3 4 | 1 4 2 1 4 2 1 5 | 5 6 0 1 2 3 4 5 | 0 5 3 1 6 4 2 5 | 1 5 4 6 2 3 1 6 | 6 0 1 2 3 4 5 6 | 0 6 5 4 3 2 1 6 | 1 6 1 6 1 6 1

Analiznd tabelul din stnga se constat c 1 i 6, 2 i 5 i 3 i 4 sunt inverse n raport cu adunarea. S lum prima pereche i s considerm c se dorete transmiterea mesajului 3. n loc de 3 se va emite 4 (trei plus unu). La recepia se va aduna modulo 7 inversul lui 1, adic 6 i se va obine 10 modulo 7, adic 3, adic mesajul care trebuia transmis. Poate c metoda descris anterior este cea mai simpl schem de criptare bazat pe aritmetica claselor de resturi. Dac se ndeprteaz din tabelul de nmulire linia i coloana care conin doar elemente nule atunci cele ase numere care rmn n fiecare linie i n fiecare coloan sunt diferite ntre ele. Se constat c n fiecare linie respectiv coloan pe o anumit poziie exist un 1. De aceea se poate afirma c pentru fiecare numr cuprins ntre 1 i 6 exist un alt numr cuprins ntre 1 i 6 astfel nct produsul acestor dou numere, modulo 7, s fie egal cu 1. Cu alte cuvinte, dac se elimin elementul 0, pe clasa de resturi modulo 7 (fr 0) operaia de nmulire este inversabil. De exemplu inversul lui 2, n raport cu nmulirea

Subiecte 3.1. Aritmetica pe clase de resturi modulo specificat 3.2. Numere prime 3.3. Mica teorem a lui Fermat 3.4. Cmpuri Galois 3.5. Matrici MDS 3.6. Transformri Pseudo-Hadamard 3.7. Funcii hash 3.7.1 Descrierea algoritmului MD5

Evaluare: 1. Rspunsuri la ntrebrile i problemele finale 2. Discuie pe tema: Bazele matematice ale criptrii


46

modulo 7 este 4. Aceast proprietate nu este adevrat pentru orice valoare a modulului. Ea este adevrat n cazul exemplului nostru deoarece modulul utilizat, 7, este un numr prim. 3.2. Numere prime

Se numete funcie indicator, totient, a lui Euler i se noteaz cu funcia care asociaz lui N numrul de numere ntregi i pozitive mai mici dect N, relativ prime cu N. E clar c dac N este prim atunci (N)=N-1. n cazul din exemplul anterior (7)=6. Deci dac modulul N este numr prim, atunci numrul de elemente inversabile la nmulirea modulo N este (N). Mai interesant este tabelul de ridicare la putere prezentat n paragraful anterior. Analiznd acest tabel se constat c orice numr cuprins ntre 1 i 6, ridicat la puterea 6 este egal cu 1. Mai mult, pe baza tabelului de ridicare la putere se constat c aceast operaie este periodic. Valorile obinute prin ridicarea la puterea 0 sunt identice cu valorile obinute prin ridicarea la puterea a 6-a. n consecin doar pentru 6 valori distincte ale exponenilor (1, 2, 3, 4, 5 i 6) se obin valori diferite prin ridicarea la putere modulo 7. innd seama de definiia anterioar a funciei totient a lui Euler, se poate afirma, pe baza acestui exemplu, c numrul de exponeni pentru care se obin valori distincte prin ridicarea la putere modulo N este egal cu (N). Cu alte cuvinte perioada de repetiie ntr-un tabel de ridicare la putere modulo N este egal cu (N). Din acest punct de vedere se poate afirma c la ridicarea la putere modulo 7, (N), exponentul poate fi privit ca fiind un element al clasei de resturi modulo 6 (modulo (N)). Aceast proprietate este valabil, n general, pentru orice clas de returi modulo un numr prim. n continuare se analizeaz cazul n care baza nu este numr prim. Dac se cunoate restul mpririi unui anumit numr cu 5 i apoi cu 7, se poate determina (deoarece 5 i 7 sunt numere prime ntre ele (nu au factori comuni)) restul mpririi acelui numr la 35. De fapt cele dou resturi sunt egale. De aceea se poate spune c proprietile aritmeticii modulo 35 sunt o combinaie a proprietilor aritmeticilor modulo 5 i modulo 7. De aceea, referindu-ne acum la operaia de ridicare la putere i innd seama de proprietatea amintit anterior, nu este nevoie ca pentru ridicarea la putere modulo 35 (care conform proprietii anterioare ar pretinde exponeni modulo 34) s se foloseasc exponeni modulo 34, fiind suficient s se utilizeze exponeni modulo 24 (pentru ridicarea la puterea a 5-a sunt suficieni, conform proprietii anterioare, coeficieni modulo 4, iar pentru ridicarea la puterea a aptea, exponeni modulo 6 i produsul dintre 4 i 6 este 24). Raionamentul

Ce numere din tabel sunt inverse in raport cu adunarea ? Care care este inversul lui 3, n raport cu nmulirea modulo 7 ? Precizai dac operaia de nmulire este inversabil pentru orice

valoare a modulului.


47

fcut explic rolul numrului (p-1)(q-1) folosit n metoda de criptare cu cheie public RSA. Aceast metod presupune criptarea unui mesaj M, prin ridicarea sa la o putere e modulo N. Perechea (N,e) reprezint cheia de criptare. Se obine textul criptat C. Decriptarea se realizeaz prin ridicarea lui C la o putere d, inversa lui e n raport cu operaia de nmulire modulo N. Cheia de decriptare este perechea (N,d). Pentru a aplica aceast metod de criptare trebuie calculat puterea d. n continuare se prezint tabelul 3.1 corespunztor operaiei de ridicare la putere modulo 55. Factorii lui 55 sunt 5 i 11, numere prime ntre ele i prime n general. Conform observaiei anterioare ar trebui s fie folosii coeficieni modulo 40, deoarece tabelul ar trebui s se repete cu perioada 40. Observaia anterioar este justificat de urmtoarea propoziie:

Dac p i q sunt dou numere relativ prime i dac N =p q

atunci (N)=(p1)(q1). ntr-adevr, n exemplul prezentat mai sus, valoarea lui N este

55, valoarea lui p este 5 iar valoarea lui q este 11. Numerele relativ prime cu 55, mai mici dect 55 sunt: 1, 2, 3, 4, 6, 7, 8, 9, 12, 13, 14, 16, 17, 18, 19, 21, 23, 24, 26, 27, 28, 29, 31, 32, 34, 36, 37, 38, 39, 41, 42, 43, 46, 47, 48, 49, 51, 52, 53, 54. De aceea (55)=40. Pe baza analizei acestui tabel se pot face cteva observaii.

Dei coloana a 20-a nu conine doar elemente egale cu 1,

coloana a 21-a este identic cu coloana 1-a, ambele coninnd n ordine numerele cuprinse ntre 1 i 45. Asta nseamn c tabelul se repet cu perioada 20 n loc de 40. Evident c i 40 este o valoare bun pentru perioad (orice multiplu al perioadei prinicpale reprezint o perioad). Aceast comportare are loc ntotdeauna cnd cel mai mare divizor comun al numerelor p-1 i q-1 este 2. Cu alte cuvinte perioada de repetiie n tabelul de ridicare la putere modulo N (dat de produsul dintre p i q) este egal cu (p-1)(q-1)/2, dac factorii p i q sunt numere prime. De aceea exponenii de la ridicarea la putere modulo N, trebuie privii ca i elemente ale clasei de resturi modulo (p-1)(q-1)/2. De aceea se lucreaz cu acest modul n metoda RSA pentru determinarea puterii d. Deoarece 55 nu este numr prim e logic ca prin nmulirea repetat a numerelor divizibile cu 5 i cu 11 s nu se poat obine numere nedivizibile cu 5 sau cu 11 cum ar fi de exemplu 1. Doar dac valoarea produsului este 1 se poate vorbi despre inversare. De aceea numai numere prime cu (p-1)(q-1) pot fi utilizate ca i exponeni pentru cifrarea respectiv descifrarea bazate pe metoda de criptare RSA. De aceea pentru cazul analizat trebuiesc excluse toate numerele divizibile cu 2 i 5.


48

Tabel 3.1. Ridicarea la putere modulo 55.

^ | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

1 | 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 | 2 4 8 16 32 9 18 36 17 34 13 26 52 49 43 31 7 14 28 1 2 3 | 3 9 27 26 23 14 42 16 48 34 47 31 38 4 12 36 53 49 37 1 3 4 | 4 16 9 36 34 26 49 31 14 1 4 16 9 36 34 26 49 31 14 1 4 5 | 5 25 15 20 45 5 25 15 20 45 5 25 15 20 45 5 25 15 20 45 5 6 | 6 36 51 31 21 16 41 26 46 1 6 36 51 31 21 16 41 26 46 1 6 7 | 7 49 13 36 32 4 28 31 52 34 18 16 2 14 43 26 17 9 8 1 7 8 | 8 9 17 26 43 14 2 16 18 34 52 31 28 4 32 36 13 49 7 1 8 9 | 9 26 14 16 34 31 4 36 49 1 9 26 14 16 34 31 4 36 49 1 9 10 |10 45 10 45 10 45 10 45 10 45 10 45 10 45 10 45 10 45 10 45 10 11 |11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 12 |12 34 23 1 12 34 23 1 12 34 23 1 12 34 23 1 12 34 23 1 12 13 |13 4 52 16 43 9 7 36 28 34 2 26 8 49 32 31 18 14 17 1 13 14 |14 31 49 26 34 36 9 16 4 1 14 31 49 26 34 36 9 16 4 1 14 15 |15 5 20 25 45 15 5 20 25 45 15 5 20 25 45 15 5 20 25 45 15 16 |16 36 26 31 1 16 36 26 31 1 16 36 26 31 1 16 36 26 31 1 16 17 |17 14 18 31 32 49 8 26 2 34 28 36 7 9 43 16 52 4 1 31 17 18 |18 49 2 36 43 4 17 31 8 34 7 16 13 14 32 26 28 9 52 1 18 19 |19 31 39 26 54 36 24 16 29 1 19 31 39 26 54 36 24 16 29 1 19 20 |20 15 25 5 45 20 15 25 5 45 20 15 25 5 45 20 15 25 5 45 20 21 |21 1 21 1 21 1 21 1 21 1 21 1 21 1 21 1 21 1 21 1 21 22 |22 44 33 11 22 44 33 11 22 44 33 11 22 44 33 11 22 44 33 11 22 23 |23 34 12 1 23 34 12 1 23 34 12 1 23 34 12 1 23 34 12 1 23 24 |24 26 19 16 54 31 29 36 39 1 24 26 19 16 54 31 29 36 39 1 24 25 |25 20 5 15 45 25 20 5 15 45 25 20 5 15 45 25 20 5 15 45 25 26 |26 16 31 36 1 26 16 31 36 1 26 16 31 36 1 26 16 31 36 1 26 27 |27 14 48 31 12 49 3 26 42 34 38 36 37 9 23 16 47 4 53 1 27 28 |28 14 7 31 43 49 52 26 13 34 17 36 18 9 32 16 8 4 2 1 28 29 |29 16 24 36 54 26 39 31 19 1 29 16 24 36 54 26 39 31 19 1 29 30 |30 20 50 15 10 25 35 5 40 45 30 20 50 15 10 25 35 5 40 45 30 31 |31 26 36 16 1 31 26 36 16 1 31 26 36 16 1 31 26 36 16 1 31 32 |32 34 43 1 32 34 43 1 32 34 43 1 32 34 43 1 32 34 43 1 32 33 |33 44 22 11 33 44 22 11 33 44 22 11 33 44 22 11 33 44 22 11 33 34 |34 1 34 1 34 1 34 1 34 1 34 1 34 1 34 1 34 1 34 1 34 35 |35 15 30 5 10 20 40 25 50 45 35 15 30 5 10 20 40 25 50 45 35 36 |36 31 16 26 1 36 31 16 26 1 36 31 16 26 1 36 31 16 26 1 36 37 |37 49 53 36 12 4 38 31 47 34 48 16 42 14 23 26 27 9 3 1 37 38 |38 14 37 31 23 49 47 26 53 34 27 36 48 9 12 16 3 4 42 1 38 39 |39 36 29 31 54 16 19 26 24 1 39 36 29 31 54 16 19 26 24 1 39 40 |40 5 35 25 10 15 50 20 30 45 40 5 35 25 10 15 50 20 30 45 40 41 |41 31 6 26 21 36 46 16 51 1 41 31 6 26 21 36 46 16 51 1 41 42 |42 4 3 16 12 9 48 36 27 34 53 26 47 49 23 31 37 14 38 1 42 43 |43 34 32 1 43 34 32 1 43 34 32 1 43 34 32 1 43 34 32 1 43 44 |44 11 44 11 44 11 44 11 44 11 44 11 44 11 44 11 44 11 44 11 44 45 |45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 46 |46 26 41 16 21 31 51 36 6 1 46 26 41 16 21 31 51 36 6 1 46 47 |47 9 38 26 12 14 53 16 37 34 3 31 27 4 23 36 42 49 48 1 47 48 |48 49 42 36 23 4 27 31 3 34 37 16 53 14 12 26 38 9 47 1 48 49 |49 36 4 31 34 16 14 26 9 1 49 36 4 31 34 16 14 26 9 1 49 50 |50 25 40 20 10 5 30 15 35 45 50 25 40 20 10 5 30 15 35 45 50 51 |51 16 46 36 21 26 6 31 41 1 51 16 46 36 21 26 6 31 41 1 51 52 |52 9 28 26 32 14 13 16 7 34 8 31 17 4 43 36 2 49 18 1 52 53 |53 4 47 16 23 9 37 36 38 34 42 26 3 49 12 31 48 14 27 1 53 54 |54 1 54 1 54 1 54 1 54 1 54 1 54 1 54 1 54 1 54 1 54

Definii funcia totient a lui Euler. Ce presupune metoda de criptare cu cheie public RSA ?


49

3.3. Mica teorem a lui Fermat

Fiind dat numrul ntreg a i numrul prim p, care nu este divizor al lui a, are loc relaia:

ap-1

= 1 (mod p). (3.1) Demonstraie: Not istoric

Ca de obicei, Fermat nu a dat o demonstraie nici pentru aceast teorem (mrginindu-se s afirme "i-a fi trimis i demonstraia dac nu m-a fi temut c este prea lung"). Primul care a publicat o demonstraie a acestei teoreme a fost Euler n anul 1736. A fost gsit ns aceeai demonstraie ntr-un manuscris al lui Leibniz, redactat nainte de 1683, rmas nepublicat.

Pentru nceput se scriu primii p-1 multipli pozitivi ai lui a:

a, 2a, 3a, ... (p -1)a (3.2)

Dac ra i sa sunt egali modulo p, atunci:

r(mod p)a(mod p) =s (mod p)(a mod p) (3.3) deoarece p este numr prim i nu-l divide pe a. Adic:

r = s (mod p) (3.4) Dar numerele r i s sunt distincte i mai mici dect p. De aceea ultima egalitate nu poate avea loc. n consecin ipoteza fcut este absurd. De aceea se poate afirma c cei p-1 multipli ai lui a introdui mai sus sunt distinci i nenuli. n consecin (fiind vorba de p-1 valori) ei trebuie s fie egali modulo p cu numerele 1, 2, 3, ..., p-1 ntr-o anumit ordine. Prin nmulirea membrilor stngi respectiv drepi ai tuturor acestor egaliti se obine egalitatea urmtoare:

a.2a

.3a

....

.(p-1)a =1

.2

.3

....

.(p-1) (mod p) (3.5)

adic:

a(p-1)

(p-1)! = (p-1)! (mod p) (3.6) mprind n ambii membri cu (p-1)! mod(p) se obine tocmai relaia din enun.

Cine a publicat pentru prima data demonstaia micii teoreme a lui Fermat ?

Enunai mica teorem a lui Fermat.


50

3.4. Cmpuri Galois Un cmp Galois este un cmp finit cu p

n elemente, unde p este

un numr prim. Mulimea elementelor nenule ale cmpului Galois este un grup ciclic n raport cu operaia de nmulire. Un element generator al acestui grup ciclic este numit element primitiv al cmpului. Cmpul Galois poate fi generat ca o mulime de polinoame cu coeficieni n Z

p

modulo un polinom ireductibil de gradul n. Valorile unui octet se reprezint n algoritmii de criptare prin concatenarea biilor individuali: {b7, b6, b5, b4, b3, b2, b1, b0}. Aceti octei sunt interpretai ca i elemente ale cmpului finit GF(2

8) cu

ajutorul unei reprezentri polinomiale:

b7 x7 + b6 x

6 + b5 x

5 + b4 x

4 +b3 x

3 + b2 x

2 + b1x + b0 =

7

k0b k

kx

= (3.7)

De exemplu octetul {01100011} se identific cu polinomul: x

6 + x

5 + x+1. Elementele cmpurilor finite pot fi adunate sau nmulite.

Exemplul 1: GF(2)

GF(2) const din elementele 0 i 1 (p=2 i n=1) i reprezint cel mai mic cmp finit. Este generat de polinoame peste Z

2 modulo

polinomul x. Polinoamele corespunztoare elementelor din GF(2) sunt: 0 i 1, deoarece x mod x=0 i x+1 mod x=1. Tabelele sale de adunare i nmulire sunt::

+ 0 1 * 0 1 0 0 1 0 0 0 1 1 0 1 0 1

Se constat c operaia de adunare este identic cu operaia logic sau-exclusiv i c nmulirea este identic cu operaia logic i. Cmpul GF(2) este utilizat frecvent la construcia de coduri deoarece el este uor reprezentat n calculatoare, fiind necesar un singur bit. Adunarea

nsumarea a dou elemente ntr-un cmp finit Galois al lui 2 la o anumit putere este realizat prin "adunarea" coeficienilor corespunztori aceleiai puteri din polinoamele corespunztoare celor dou elemente. "Adunarea" este efectuat modulo 2 (adic este vorba despre funcia logic sau exclusiv). n consecin scderea polinoamelor este identic cu adunarea lor. Alternativ adunarea a doi octei n GF(2

8),

{a7a6a5a4a3a2a1a0} i {b7b6b5b4b3b2b1b0}, se face prin adunarea modulo 2 a biilor lor corespunztori. Se obine octetul {c7c6c5c4c3c2c1c0},


51

unde: ci = ai bi , i = 1,7. De exemplu urmtoarele expresii sunt echivalente: ( ) ( )6 4 2 7 7 6 4 21 1x x x x x x x x x x+ + + + + + + = + + + (notaie polinomial)

{01010111} {10000011} = {11010100} (notaie binar) {57} {83} = {d4} (notaie hexazecimal)

(3.8)

nmulirea n reprezentare polinomial, nmulirea n cmpul lui Galois al lui 2

8, GF(2

8), notat cu , corespunde nmulirii polinoamelor

corespunztoare modulo un polinom ireductibil de gradul 8. Un astfel de polinom ireductibil este: x

8 +x

4 +x

3 +x +1 sau {1b} n notaie

hexazecimal. De exemplu:

{57} {83} = {c1} (3.9) deoarece innd seama de reprezentrile polinomiale ale lui {57} i {83}:

( ) ( )1

11246235

78911137246

++++++++

+++++=+++++

xxxxxxxxxxxxxxxxx

(3.10)

sau innd seama de modul n care a fost definit adunarea:

( ) ( )1

113456891113

7246

++++++++=

=+++++

xxxxxxxxxxxxx

(3.11)

Dar:

( )( ) ( ) ( )

13 11 9 8 6 5 4 3 8 4 3 7 61 mod 1 1

x x x x x x x x x x x x x x

P x m x R x

+ + + + + + + + + + + + = + +

(3.12) deoarece restul mpririi lui P(x) la m(x) este x

7 x

6 +1, care este egal

cu R(x), deoarece coeficienii acestor polinoame trebuie considerai din mulimea claselor de resturi modulo 2 (aa cum s-a artat deja cnd s-a vorbit despre adunare). Dar octetul corespunztor lui R(x) este{0,1,1,0,0,0,0,0,1}sau n notaie hexazecimal {c1}.

nmulirea definit astfel este asociativ, iar elementul su neutru este {01}. Pentru orice polinom binar neidentic nul, de grad inferior lui 8, b(x), exist un element invers n raport cu aceast nmulire, notat ( )1b x . Acesta poate fi calculat utiliznd algoritmul lui Euclid, i determinnd polinoamele a(x) i c(x), care au proprietatea:


52

( ) ( ) ( ) ( ) 1b x a x m x c x + = (3.13) adic:

( ) ( ) ( ){ }mod 1b x a x m x = (3.14) ceea ce nseamn c:

( ) ( ) ( ){ }1 modb x a x m x = (3.15) Mai mult, se poate demonstra c nmulirea este distributiv n raport cu adunarea pe GF(2

8), adic:

( ) ( ) ( )( ) ( ) ( ) ( ) ( )a x b x c x a x b x a x c x + = + (3.16)

Exemplul 2: GF(3)

GF(3) este constituit din elementele 0, 1, i -1. El este generat de polinoame peste Z

3 modulo polinomul x. Tabelele sale de adunare i

nmulire sunt:

+ 0 1 -1 * 0 1 -1 0 0 1 -1 0 0 0 0 1 1 -1 0 1 0 1 -1 -1 -1 0 1 -1 0 -1 1

Este utilizat la construcia codurilor ternare. Exemplul 3: GF(4)

Acest cmp Galois este generat de polinoamele peste Z2 modulo

polinomul x2 + x + 1. Elementele sale sunt (0,1,A,B). Tabelele sale de

adunare i nmulire sunt:

+ 0 1 A B * 0 1 A B 0 0 1 A B 0 0 0 0 0 1 1 0 B A 1 0 1 A B A A B 0 1 A 0 A B 1 B B A 1 0 B 0 B 1 A

Datorit tabelului de nmulire A se identific de obicei cu rdcina cubic a unitii 2/32/1 i+ . A i B sunt elemente primitive ale lui GF(4). nmulirea cu monoame pe GF(2

8)

ntr-un paragraf anterior s-a introdus nmulirea pe acest cmp


53

Galois, dar nu s-a indicat o metod numeric simpl pentru efectuarea acestei nmuliri. nmulirea cu monoame este un caz particular important (orice nmulire de polinoame se bazeaz pe cteva nmuliri cu monoame) pentru care exist metode numerice simple de implementare.

nmulirea polinomului binar b7 x7

+ b6 x6

+b5 x5

+b4 x4

+b3 x3

+b2 x2

+b1x +b0 , notat cu b(x), cu x conduce la polinomul b7 x8

+b6 x7

+b5 x6 +b4 x

5 +b3 x

4 +b2 x

3 +b1x

2 +b0 x .

Rezultatul nmulirii ( )xbx se obine reducnd modulo m(x) rezultatul obinut anterior. Dac bitul b7 are valoarea 0 atunci rezultatul este deja n form redus. Dac acest bit are valoarea 1 reducerea este realizat prin scderea (adic prin operaia logic sau-exclusiv) polinomului m(x). n consecin nmulirea pe GF(2

8) cu x, (adic {00000010}n

form binar, respectiv {02}, n form hexazecimal) poate fi implementat la nivel de octet printr-o deplasare la stnga urmat sau nu (n funcie de valoarea bitului b7) de calculul funciei sau-exclusiv dintre rezultatul (obinut n urma rotirii) i {1b}. Aceast operaie, la nivel de octet, este notat prin xtime(). nmulirea cu puteri mai mari ale lui x poate fi implementat prin aplicarea repetat a operaiei xtime(). Prin adunarea unor astfel de rezultate intermediare poate fi implementat nmulirea cu orice polinom. De exemplu:

{57} {13} = {fe} deoarece: {57} {02} = xtime({57}) = {ae} {57} {04} = xtime({ae}) = {47} {57} {08} = xtime({47}) = {8e}

{57} {10} = xtime({8e}) = {07}

(3.17)

i: {57}{13}={57}({01}{02}{10})={57}{ae}{07}={fe} (3.18)

Polinoame cu coeficieni n GF(2

8)

Pn acum coeficienii polinoamelor erau de valoare unu sau

zero, fiind deci vorba despre polinoame binare. n continuare se analizeaz cazul polinoamelor cu coeficieni octei. Polinoamele cu patru termeni, cu coeficieni n cmpul specificat, sunt de forma:

( ) 012233 axaxaxaxa +++= (3.19) i se reprezint ca i cuvinte de forma [a0 , a1 , a2 , a3]. De data aceasta ns coeficienii nu mai sunt bii ci octei. De aceea i polinomul de reducere va fi diferit, aa cum se va arta n continuare. Pentru a ilustra operaiile de adunare i de nmulire pentru polinoame cu patru termeni cu coeficieni octei fie cel de al doilea termen (sau factor) al operaiei: b(x)=b3 x

3 +b2 x

2 +b1x +b0. Adunarea este realizat prin adunarea, n

cmpul finit al coeficienilor, a coeficienilor corespunztori aceleiai


54

puteri a lui x. Adunarea n cmpul finit al coeficienilor este efectuat prin intermediul operaiei de sau-exclusiv ntre octeii corespunztori (de aceast dat este vorba despre sau-exclusiv ntre octeii complei i nu ntre biii din componena lor). n consecin:

( ) ( ) ( ) ( ) ( ) ( )0011222333 baxbaxbaxbaxbxa +++=+ (3.20)

nmulirea celor dou polinoame, numit nmulire modular, se efectueaz n doi pai. Primul pas presupune dezvoltarea algebric a produsului celor dou polinoame, ( ) ( ) ( )xbxaxc = , identificarea coeficienilor fiecrei puteri:

c(x)=c6 x6 +c5 x

5 +c4 x

4 +c3 x

3 +c2 x

2 +c1 x+c0 (3.21)

unde:

302112233

3362011022

3223510011

3122134000

babababacbacbababac

babacbabacbababacbac

===

====

(3.22)

Acest rezultat, c(x), nu este ns un polinom cu patru termeni. Cel de al doilea pas presupune reducerea lui c(x) modulo un polinom de gradul 4, obinndu-se un polinom de grad mai mic dect patru. De exemplu n cazul algoritmului de criptare simetric Rijndael, polinomul de reducere este x

4 +1, astfel nct:

( ) mod4 4 1mod ii xxx =+ (3.23)

Produsul modular al polinoamelor a(x) i b(x), notat ( ) ( )xbxa , este dat de polinomul cu patru termeni d(x), definit dup cum urmeaz:

( ) 012233 dxdxdxdxd +++= (3.24) cu:

( ) ( ) ( ) ( )( ) ( ) ( ) ( )( ) ( ) ( ) ( )( ) ( ) ( ) ( )302112033

332011022

322310011

312213000

babababadbabababadbabababadbabababad

====

(3.25)

Dac a(x) este un polinom fixat, operaiile descrise mai sus pot fi exprimate i matricial:


55

=

3

2

1

0

0123

3012

2301

1230

3

2

1

0

bbbb

aaaaaaaaaaaaaaaa

dddd

(3.26)

De aceea se poate afirma c nmulirea modular se reduce la o nmulire matricial. Deoarece x

4 +1 nu este un polinom ireductibil pe GF(2

8), nmulirea

modular a polinoamelor cu patru termeni cu coeficieni octei, definit mai sus, nu este neaprat o operaie inversabil. n algoritmul Rijndael este totui utilizat un polinom cu patru termeni cu coeficieni octei, care trebuie s aib invers n raport cu aceast operaie de nmulire:

( ) { } { } { } { }02010103 23 +++= xxxxa (3.27) Inversul su este:

( ) { } { } { } { }exxdxbxa 00900 231 +++= (3.28) Un alt polinom utilizat n programul de criptare cu cheie secret Rijndael este polinomul x

3 . Efectul nmulirii modulare cu acest

polinom este rotirea octetului cu o poziie spre stnga. Asta nseamn c [b0, b1, b2, b3] se transform n [b1, b2, b3, b0]. 3.5. Matrici MDS Un cod separat la distana maxim, maximum distance separable code (MDSC), definit peste un cmp finit, este o coresponden ntre a elemente ale acelui cmp finit i b elemente ale unui alt cmp finit, care produce un vector compus de a+b elemente, cu proprietatea c numrul minim de elemente nenule din orice vector nenul este de cel puin b + 1. Altfel spus distana dintre oricare doi vectori produi de corespondena MDS (adic numrul de elemente care difer ntre cei doi vectori) este de cel puin b + 1. Poate fi demonstrat c nu exist o alt coresponden care s aib o distan minim, ntre oricare 2 vectori produi, mai mare. De aceea se folosete denumirea de separare la distan maxim. O coresponden MDS poate fi reprezentat cu ajutorul unei matrici MDS care are ab elemente. Transformarea MDS corespunztoare, a unui

Ce este cmpul Galois? Care este cel mai mic cmp Galois finit ? Cum este efectuat "Adunarea" n cmpul Galois i ce funcie

logic reprezint ?


56

anumit octet, se realizeaz prin nmulirea acelui octet, privit ca i vector, cu matricea MDS. De exemplu codurile corectoare de erori Reed-Solomon sunt coduri de tip MDS. O condiie necesar i suficient ca o matrice s fie MDS este ca toate submatricele sale ptrate s fie nesingulare. Algoritmul de criptare simetric Twofish utilizeaz o matrice MDS peste cmpul Galois a lui 2 la puterea a 8-a. 3.6. Transformri Pseudo-Hadamard O transformare Pseudo-Hadamard este o simpl operaie de mixare care poate fi implementat numeric rapid. Fiind date 2 intrri a i b, transformarea Pseudo-Hadamard pe 32 de bii este definit prin:

32

32

mod(2 )2 mod(2 )

t

t

a a bb a b

= +

= + (3.29)

O astfel de transformare este utilizat n algoritmul Twofish, putnd fi execut n dou operaii de microprocesor. 3.7. Funcii hash

O funcie hash, notat cu H este o funcie definit pe o mulime A, care ia valori ntr-o mulime B, format cu elemente a cror exprimare n binar se face cu acelai numr de bii, n. De obicei mulimea A reprezint mulimea mesajelor. Mulimea B are 2

n

elemente. Dac n nu este suficient de mare atunci funcia nu este injectiv i deci nu este inversabil. Caracteristicile funciilor hash sunt:

- Fiind dat mesajul M, din A, este simplu de calculat h=H(M). - Fiind dat h este dificil de calculat M. - Fiind dat M este dificil s se gseasc un alt mesaj M' diferit astfel nct H(M)=H(M'). - Este greu s se gseasc dou mesaje aleatoare astfel nct H(M)=H(M'). Aceast proprietate este numit rezisten la coliziune.

Care este distana minim dintre oricare doi vectori produi de corespondena MDS ?

Dai exemple de coduri de tip MDS. Ce condiie trebuie s ndeplineasc o matrice ca s fie de tip

MDS ?

Ce repretint transformarea Pseudo-Hadamard ? n ce algoritm de criptare este utilizat transformarea Pseudo-

Hadamard ?


57

- Prin modificarea unui singur bit din M se modific muli bii din h. O funcie hash de tipul one-way este o funcie hash care este dificil

de inversat. Asta nseamn c dac H(a)=b i dac se cunoate b atunci este foarte dificil s se afle a. Uneori nu exist nici o metod mai rapid de a-l afla pe a dect cea bazat pe fora brut (care cere s fie ncercate toate elementele din A). Rezult c funciile hash de tipul one-way sunt rezistente la atacuri de tip collision.

Funciile hash de tipul one-way au numeroase aplicaii:

- autentificare; - controlul integritii mesajelor, MIC, message integrity check; - controlul autenticitii mesajelor, MAC, message authentication check; - generarea irurilor de chei (astfel de exemple vor fi date cnd se vor prezenta funciile f, din structurile Feistel folosite de diferiii algoritmi de criptare simetric); - securitatea parolelor. Cel mai des folosit funcie hash se numete MD5 (Message Digest) i a fost introdus de Rivest n 1991. Ea transform un fiier de lungime arbitrar ntr-o valoare exprimat pe 128 de bii. Aceast funcie hash se utilizeaz la generarea semnturilor digitale, caz n care rezultatul aplicrii sale unui mesaj se numete rezumatul mesajului, MD. Aceast funcie este prezentat n [3].

3.7.1 Descrierea algoritmului MD5 Se consider c mesajul de intrare (elementul cruia i se aplic funcia hash) are o lungime de b bii. Rezultatul aplicrii funciei hash va fi rezumatul mesajului considerat. Forma mesajului iniial este: m_0 m_1 ... m_{b-1}. Terminologie i notaii ^ - ridicare la putere, x^i nseamn x la puterea i.

+ - adunarea modulo 2^32 a cuvintelor.

X


58

X v Y - rezultatul aplicrii funciei sau cuvintelor X i Y obinut prin aplicarea funciei sau fiecrei perechi de bii (de aceeai semnificaie) din cele dou cuvinte. X xor Y - rezultatul aplicrii funciei sau-exclusiv cuvintelor X i Y obinut prin aplicarea funciei sau-exclusiv fiecrei perechi de bii (de aceeai semnificaie) din cele dou cuvinte. XY - rezultatul aplicrii funciei i cuvintelor X i Y obinut prin aplicarea funciei i fiecrei perechi de bii (de aceeai semnificaie) din cele dou cuvinte. Pentru determinarea rezumatului mesajului se fac urmtorii 5 pai. Pasul 1. Adugare de bii pentru egalizarea lungimii mesajului

Mesajul este extins astfel nct lungimea sa s devin egal cu 448 modulo 512. Extinderea se face ntotdeauna, chiar dac lungimea mesajului iniial este egal cu 448 modulo 512. Extinderea se face dup cum urmeaz: se adaug un singur bit cu valoarea 1 i apoi se aduag bii de valoare 0 pn cnd lungimea mesajului ajunge s fie de valoarea dorit. Numrul de bii adugai poate varia ntre 1 i 512. Pasul 2. Adugarea lungimii mesajului

O reprezentare pe 64 de bii a lungimii iniiale a mesajului, b, este adugat la rezultatul obinut n urma efecturii pasului anterior. n ipoteza, puin probabil, c valoarea lui b este mai mare dect 2 la puterea 64, se utilizeaz doar cei mai puin semnificativi 64 de bii ai reprezentrii binare a valorii b. Acest cuvnt de 64 de bii se adauag prin concatenarea a dou cuvinte de 32 de bii, primul fiind cel care conine biii mai puin semnificativi. n acest punct al algoritmului noul mesaj obinut are o lungime egal cu un multiplu de 512. Deci acest mesaj conine un numr ntreg de cuvinte de 16, respectiv 32 de bii. Fie M[0 ... N-1] reprezentarea unui cuvnt al mesajului rezultat, unde N este un multiplu de 16.

Pasul 3. Iniializarea registrului MD

Un registru de patru cuvinte (A,B,C,D) se folosete pentru calculul rezumatului mesajului. De fapt cu A, B, C, D, au fost notate patru registre de cte 32 de bii. Aceste registre sunt ncrcate iniial cu urmtoarele valori, exprimate n hexazecimal (cu biii cei mai puin semnificativi la nceput):

A 01 23 45 67 B 89 ab cd ef C fe dc ba 98 D 76 54 32 10

Pasul 4. Prelucrarea mesajului folosind blocuri de cte 16 cuvinte

Pentru nceput se definesc 4 funcii auxiliare fiecare aplicndu-se la cte 3 cuvinte de cte 32 de bii i avnd ca valoare cte un cuvnt de 32 de bii.


59

F(X,Y,Z) = XY v not(X) Z ; G(X,Y,Z) = XZ v Y not(Z) ; H(X,Y,Z) = X xor Y xor Z; I(X,Y,Z) = Y xor (X v not(Z)).

n fiecare poziie de bit funcia F acioneaz ca i o condiionare: dac X atunci Y, altfel Z. Funcia F ar fi putut fi definit i folosind operaia + n loc de v deoarece subfunciileXY i not(X)Z nu vor avea niciodat un 1 n aceeai poziie. Este interesant s se observe faptul c dac biii operanzilor X, Y, i Z (privii ca i variabile aleatoare) sunt independeni i nepolarizai, atunci fiecare bit al lui F(X,Y,Z) va fi independent i nepolarizat.

Funciile G, H, i I sunt similare cu funcia F, n sensul c i ele

acioneaz la nivel de bit n mod paralel astfel nct dac X, Y, i Z au biii independeni i nepolarizai atunci biii rezultatelor G(X,Y,Z), H(X,Y,Z) i I(X,Y,Z) vor fi independeni i nepolarizai. Se observ c folosind funcia H poate fi fcut controlul paritii variabilelor sale.

Acest pas folosete un tabel cu 64 de elemente T[1 ... 64]

construit cu ajutorul valorilor funciei sinus. Fie T[i] cel de al i-ilea element al tabelului, care este egal cu partea ntreag a produsului dintre 4294967296 i valoarea absolut a lui sin(i), unde i este exprimat n radiani. Pentru ncheierea acestui pas se efectueaz urmtoarele operaii: /* Se prelucreaz fiecare bloc de cte 16 cuvinte. */ For i = 0 to N/16-1 do /* Se copiaz cel de al i-ilea bloc n X. */ For j = 0 to 15 do Set X[j] to M[i*16+j]. end /* al buclei dup j */ /* Salveaz A ca i AA, B ca i BB, C ca i CC, i D ca i DD. */ AA = A BB = B CC = C DD = D /* Iteraia 1. */ /* Se noteaz cu [abcd k s i] operaia: a = b + ((a + F(b,c,d) +X[k] + T[i])


60

[ABCD 13 5 29] [DABC 2 9 30] [CDAB 7 14 31] [BCDA 12 20 32] /* Iteraia 3. */ /* Se noteaz cu [abcd k s t] operaia: a = b + ((a + H(b,c,d) + X[k] + T[i])


61

Rezumat La nceput se prezint tabelele pentru operaiile de adunare, nmulire i ridicare la putere pe mulimea claselor de resturi modulo 7.

Se numete funcie indicator, totient, a lui Euler i se noteaz cu funcia care asociaz lui N numrul de numere ntregi i pozitive mai mici dect N, relativ prime cu N. Dac Neste prim atunci (N)=N-1. Deci dac modulul N este numr prim, atunci numrul de elemente inversabile la nmulirea modulo N este (N).

Un cmp Galois este un cmp finit cu p

n elemente, unde p

este un numr prim. Mulimea elementelor nenule ale cmpului Galois este un grup ciclic n raport cu operaia de nmulire. Un element generator al acestui grup ciclic este numit element primitiv al cmpului. Cmpul Galois poate fi generat ca o mulime de polinoame cu coeficieni n Z

p modulo un polinom

ireductibil de gradul n. Un cod separat la distana maxim, maximum distance

separable code (MDSC), definit peste un cmp finit, este o coresponden ntre a elemente ale acelui cmp finit i belemente ale unui alt cmp finit, care produce un vector compus de a+b elemente, cu proprietatea c numrul minim de elemente nenule din orice vector nenul este de cel puin b + 1.

O funcie hash, notat cu H este o funcie definit pe o

mulime A, care ia valori ntr-o mulime B, format cu elemente a cror exprimare n binar se face cu acelai numr de bii, n. De obicei mulimea A reprezint mulimea mesajelor. Mulimea B are 2

n elemente. Dac n nu este suficient de mare atunci

funcia nu este injectiv i deci nu este inversabil.


62

NTREBRI (TEST GRIL) 1. Specificai valoarea funciei indicator a lui Euler a

numrului N=pq dac p i q sunt dou numere relativ prime. a) p(q-1), b) (p-1)q, c) (p-1)(q-1), d) (p+2)(q-1), e) 2pq.

2. Demonstraia micii teoreme a lui Fermat se bazeaz pe: a) inducie matematic, b) calcul, c) reducere la absurd,

d) marea teorem a lui Fermat, e) cunotiine de analiz matematic.

3. Calculai pe cmpul Galois a lui 2 la puterea a 8-a produsul lui 57 cu 83 tiind c aceste elemente sunt exprimate n hexagesimal.

a) c2, b) c1, c) a1, d) 53, e) ac 4. O funcie hash de tipul one-way este o funcie hash care

a) este dificil de inversat, b) este neinversabil, c) este uor de inversat, d) este neinjectiv, e) este nesurjectiv.

5. Ce se nelege prin X

Date post:	06-Oct-2015
Category:	Documents
Upload:	darius-dakidd
View:	6 times
Download:	0 times

Teoria criptarii

Documents