Descriere

RC4 este un sistem de criptare fluid pe octeti:

m {0, 1}8 , c {0, 1}8

Ramane de definit PRG...

Criptografie si Securitate

4/10

Descriere
I

2 faze:
I

Starea interna:
I
I

initializare: determina starea interna, fara sa produca chei

fluide;
generare de chei fluide: modifica starea interna si genereaza un
octet (cheia fluida) care se XOR-eaza cu m pentru a obtine c;
un tablou S de 256 octeti: S[0], . . . , S[255];
2 indici i si j;

Toate operatiile se efectueaza pe octeti (i.e. (mod 256)).

Criptografie si Securitate

5/10

Descriere
Faza 1. Initializare
I
I

n = numarul octetilor din cheie, 1 n 256

j 0
for i = 0 to 255 do
S[i] i
end for
for i = 0 to 255 do
j j + S[i] + k[i (mod n)]
swap (S[i], S[j])
end for
i 0
j 0

Criptografie si Securitate

6/10

Descriere
Faza 2. Generarea cheii fluide
I
I

cheia se obtine octet cu octet

i i +1
j j + S[i]
swap (S[i], S[j])
return S[S[i] + S[j]]

Criptografie si Securitate

7/10

Pseudoaleatorismul
I

Un sir pseudoaleator arata similar unui sir uniform aleator

din punct de vedere al oricarui algoritm polinomial;

Altfel spus: un algoritm polinomial nu poate face diferenta

ntre o secventa perfect aleatoare si una pseudoaleatore
(decat cu probabilitate neglijabila);

Sau: o distributie a secventelor de lungime l este

pseudoaleatoare daca este nedistinctibil
a de distributia
uniforma a secventelor de lungime l;

Mai exact: nici un algoritm polinomial nu poate spune daca o

secventa de lungime l este esantionarea unei distributii
pseudoaleatoare sau este o secventa total aleatoare de
lungime l.

Criptografie si Securitate

4/22

Sisteme fluide
OTP (One Time Pad)

Criptografie si Securitate

Sisteme fluide

7/22

PRG
I

Ramane sa definim notiunea de generator de numere aleatoare

sau PRG (PseudoRandom Generator);

Acesta este un algoritm determinist care primeste o

samanta relativ scurta s (seed) si genereaza o secventa
pseudoaleatoare de biti;

Notam |s| = n, |PRG (s)| = l(n)

PRG prezinta interes daca:

l(n) n
(altfel NU genereaza aleatorism)

Criptografie si Securitate

8/22

PRG
Definitie
Fie l() un polinom si G un algoritm polinomial determinist a..
n {0, 1}n , G genereaza o secventa de lungime l(n).
G se numeste generator de numere pseudoaleatoare (PRG) daca se
satisfac 2 proprietati:
1. Expansiune: n, l(n) n
2. Pseudoaleatorism: algoritm PPT D, o funtie neglijabila
negl a..:
|Pr [D(r ) = 1] Pr [D(G (s)) = 1]| negl(n)
unde r R {0, 1}l(n) , s R {0, 1}n
l(n) se numeste factorul de expansiune al lui G

Criptografie si Securitate

9/22

Notatii

D = Distringuisher

PPT = Probabilistic Polynomial Time

x R X = x este ales uniform aleator din X

negl(n) = o functie neglijabila n (parametrul de securitate) n

In plus:
I

Vom nota A un adversar (Oscar / Eve), care (n general) are

putere polinomiala de calcul

Criptografie si Securitate

10/22

Sisteme fluide
Definitie
Un sistem de criptare (Enc, Dec) definit peste (K, M, C) se
numeste sistem de criptare fluid daca:
1. Enc : K M C
c = Enck (m) = G (k) m
2. Dec : K C M
m = Deck (c) = G (k) c
unde G este un generator de numere pseudoaleatoare cu factorul
de expansiune l, k {0, 1}n , m {0, 1}l(n)

Criptografie si Securitate

11/22

Moduri de utilizare

modul sincronizat: partenerii de comunicatie folosesc pentru

criptarea mesajelor parti succesive ale secventei
pseudoaleatoare generate;

modul nesincronizat: partenerii de comunicatie folosesc pentru

criptarea mesajelor secvente pseudoaleatoare diferite.

Atentie!
PRG va necesita 2 intrari: cheia k si un vector de initializare IV .

Criptografie si Securitate

15/22

Modul sincronizat

Criptografie si Securitate

16/22

Modul nesincronizat

Criptografie si Securitate

17/22

Moduri de utilizare
Modul sincronizat
I

mesajele sunt criptate n

mod succesiv (participantii
trebuie sa stie care parti au
fost deja folosite)

necesita pastrarea starii

mesajele succesive pot fi

percepute ca un singur
mesaj clar lung, obtinut
prin concatenarea
measajelor succesive

se preteaza unei singure

sesiuni de comunicatii

Criptografie si Securitate

Modul nesincronizat
I

mesajele sunt criptate n

mod independent

NU necesita pastrarea starii

valorile IV1 , IV2 , . . . sunt

alese uniform aleator pentru
fiecare mesaj transmis

valorile IV1 , IV2 , . . . (dar si

IV n modul sincronizat)
fac parte din mesajul
criptat
(sunt necesare pentru
decriptare)

18/22

Descriere
I
I
I

WEP utilizeaza RC4;

Introduce n plus (Cyclic Redundancy Check) cu rolul de a
detecta eventuale erori de transmisiune;
IV este transmis catre destinatar, mpreuna cu c (IV ||c), fiind
necesar pentru decriptare .

Criptografie si Securitate

4/10

Descriere
Detalii de implementare:
I

|IV | = 24 (biti)

IV se utilizeaza n counter mode (0, 1, 2, . . . )

Criptografie si Securitate

5/10

Securitate - Problema 1
Problema 1: Utilizarea multipla a lui IV
I

Intrebare: Ce efect imediat are utilizarea multipla a lui IV

pentru o cheie fixata k?

Raspuns: Se obtine ntotdeauna aceeasi cheie fluida kr

IV1 = IV2 = IV kf 1 = kf 2 = PRG (IV ||k)

Intrebare: Sistemul ramane sigur n aceste conditii?

Raspuns: NU!
c1 = m1 kf 1 , c2 = m2 kf 2 c1 c2 = m1 m2
Exemplu:
I
I

daca A cunoaste m1 , atunci poate determina m2

A poate determina m1 si m2 folosind analiza statistica

Criptografie si Securitate

6/10

Securitate - Problema 1

Intrebare: Cate valori posibile poate lua IV?

Raspuns: 224

Cum un AP (Access Point) trimite aproximativ 1000

pachete/s, valoarea lui IV se repeta la cel mult la cateva ore!

Mai mult, exista echipamente care reseteaza IV la fiecare

repornire!

Criptografie si Securitate

7/10

Securitate - Problema 2
Problema 2: Liniaritatea
I
Intrebare: Facand abstractie de CRC, A poate modifica
mesajul criptat transmis dupa bunul sau plac?
I R
aspuns: DA!
(m1 m2 ) kf = (m1 kf ) m2
Exemplu:
I

A intercepteaza c1 si l transforma n c2

Criptografie si Securitate

8/10

Securitate semantica - interceptare simpla

Vom defini securitatea semantica pe baza unui experiment de

eav (n) unde = (Enc, Dec) este schema
indistinctibilitate PrivA,
de criptare iar n este parametrul de securitate al schemei

Personaje participante: adversarul A care ncearca sa sparga

schema si un provocator (challenger).

Trebuie sa definim capabilitatile adversarului: n contextul

sistemelor de criptare fluide, el poate vedea un singur text
criptat cu o anume cheie, fiind un adversar pasiv care poate
rula atacuri n timp polinomial.

Criptografie si Securitate

4/24

eav
Experimentul PrivA,
(n)

Output-ul experimentului este 1 daca b 0 = b si 0 altfel. Daca

eav (n) = 1, spunem c
PrivA,
a A a efectuat experimentul cu
succes.

Criptografie si Securitate

9/24

Securitate semantica - interceptare simpla

Definitie
O schema de criptare = (Enc, Dec) este indistinctibila n
prezenta unui atacator pasiv daca pentru orice adversar A exista o
functie neglijabila negl asa ncat
eav (n) = 1]
Pr[PrivA,

1
2

+ negl(n).

Un adversar pasiv nu poate determina care text clar a fost

criptat cu o probabilitate semnificativ mai mare decat daca ar
fi ghicit (n sens aleator, dat cu banul).

Criptografie si Securitate

10/24

mult
Experimentul PrivA,
(n)

I
I

Output-ul experimentului este 1 daca b 0 = b si 0 altfel;

Definitia de securitate este aceeasi, doar ca se refera la
experimentul de mai sus.
Securitatea pentru interceptare simpl
a nu implica securitate
pentru interceptare multipl
a!

Criptografie si Securitate

16/24

Demonstratie

I
I

Daca c1 = c2 , atunci A ntoarce 0, altfel A ntoarce 1.

Analizam probabilitatea ca A sa ghiceasca b: daca b = 0,
acelasi mesaj este criptat mereu (m01 = m02 ) iar c1 = c2 si deci
A ntoarce mereu 0;
Daca b = 1, atunci (m11 6= m12 ) iar c1 6= c2 si deci A ntoarce
mereu 1.

Criptografie si Securitate

23/24

Sisteme bloc vs. sisteme fluide

Criptografie si Securitate

4/37

Sisteme bloc vs. sisteme fluide

... d.p.d.v. al modului de criptare:

Sisteme fluide

Sisteme bloc

criptarea bitilor se
realizeaza individual

criptarea se realizeaza n
blocuri de cate n biti

criptarea unui bit din textul

clar este independenta de
orice alt bit din textul clar

criptarea unui bit din textul

clar este dependenta de
bitii din textul clar care
apartin aceluiasi bloc

Criptografie si Securitate

5/37

Sisteme bloc

Introducem notiunea de permutare pseudoaleatoare sau

PRP(PseudoRandom Permutation)

In analogie cu ce stim deja:

I

PRP sunt necesare pentru constructia sistemelor bloc

asa cum

PRG sunt necesare pentru constructia sistemelor fluide

Criptografie si Securitate

7/37

PRP

Ramane sa definim notiunea de permutare pseudoaleatoare

sau PRP (PseudoRandom Permutation);

Acesta este o functie determinist

a si bijectiv
a care pentru o
cheie fixata produce la iesire o permutare a intrarii ...

... indistinctibil
a fata de o permutare aleatoare;

In plus, atat functia cat si inversa sa sunt eficient calculabile.

Criptografie si Securitate

9/37

PRP
Definitie
O permutare pseudoaleatoare definita peste (K, X ) este o functie
bijectiva
F :X K X
care satisface urmatoarele proprietati:
1. Eficienta: k K, x X , algoritmi deterministi PPT care
calculeaza Fk (x) si Fk1 (x)
2. Pseudoaleatorism: algoritm PPT D, o functie neglijabila
negl a..:
|Pr [D(r ) = 1] Pr [D(Fk ()) = 1]| negl(n)
unde r R Perm(X ), k R K

Criptografie si Securitate

10/37

PRF
Definitie
O functie pseudoaleatoare definita peste (K, X , Y) este o functie
bijectiva
F :X K Y
care satisface urmatoarele proprietati:
1. Eficienta: k K, x X , algoritm PPT care calculeaza
Fk (x)
2. Pseudoaleatorism: algoritm PPT D, o functie neglijabila
negl a..:
|Pr [D(r ) = 1] Pr [D(Fk ()) = 1]| negl(n)
unde r R Func(X , Y ), k R K

Criptografie si Securitate

13/37

Notatii

Fk (x) = F (k, x)
o cheie este n general (aleator) aleasa si apoi fixata

Func(X , Y ) = multimea functiilor de la X la Y

X = {0, 1}n , Y = {0, 1}n

consideram n general ca PRF pastreaza lungimea

D = Distringuisher care are acces la oracolul de evaluare a

functiei

Criptografie si Securitate

14/37

Moduri de utilizare
I

Sa continuam cu ceva mai practic...

Intrebare: Ce se ntampla daca lungimea mesajului clar este

mai mic
a decat dimensiunea unui bloc?

Raspuns: Se completeaza cu biti: 1 0 . . . 0;

Intrebare: Ce se ntampla daca lungimea mesajului clar este

mai mare decat lungimea unui bloc?

Raspuns: Se utilizeaza un mod de operare (ECB, CBC,

OFB, CTR);

Notam cu Fk un sistem de criptare bloc (i.e. PRP) cu cheia k

fixata.

Criptografie si Securitate

27/37

Modul ECB (Electronic Code Book)

Criptografie si Securitate

28/37

Modul ECB (Electronic Code Book)

I

Pare modul cel mai natural de a cripta mai multe blocuri;

Pentru decriptare, Fk trebuie sa fie inversabli

a;

Este paralelizabil;

Este determinist, deci este nesigur;

Intrebare: Ce informatii poate sa ofere modul de criptare ECB

unui adversar pasiv?

Raspuns: Un adversar pasiv detecteaza repetarea unui bloc de

text clar pentru ca se repeta blocul criptat corespunzator;

Modul ECB NU trebuie utilizat n practica!

Criptografie si Securitate

29/37

Modul CBC (Cipher Block Chaining)

Criptografie si Securitate

30/37

Modul CBC (Cipher Block Chaining)

IV este o ales n mod aleator la criptare;

IV se transmite n clar pentru ca este necesar la decriptare;

Pentru decriptare, Fk trebuie sa fie inversabli

a;

Este secvential, un dezavantaj major daca se poate utiliza

procesarea paralela.

Criptografie si Securitate

31/37

Modul OFB (Output FeedBack)

Criptografie si Securitate

32/37

Modul OFB (Output FeedBack)

Genereaza o secventa pseudoaleatoare care se XOR-eaza

mesajului clar;

IV este o ales n mod aleator la criptare;

IV se transmite n clar pentru ca este necesar la decriptare;

Fk nu trebuie neaparat sa fie inversablia;

Este secvential, nsa secventa pseudoaleatoare poate fi

pre-procesata anterior decriptarii.

Criptografie si Securitate

33/37

Modul CTR (Counter)

Criptografie si Securitate

34/37

Modul CTR (Counter)

I

Genereaza o secventa pseudoaleatoare care se XOR-eaza

mesajului clar;

ctr este o ales n mod aleator la criptare;

ctr se transmite n clar pentru ca este necesar la decriptare;

Fk nu trebuie neaparat sa fie inversablia;

Este paralelizabil;

In plus, secventa pseudoaleatoare poate fi pre-procesata

anterior decriptarii.

Criptografie si Securitate

35/37

Exemple

DES (Data Encryption Standard):

I
I

propus de IBM
adoptat ca standard NIST n 1976
(lungime cheie = 64 biti, lungime bloc = 64 biti)
spart prin cautare exhaustiva n 1997

AES (Advanced Encryption Standard):

I
I

algoritmul Rijndael propus de J. Daemen si [Link]

adoptat ca standard NIST n 2001
(lungime cheie = 128, 192, 256 biti, lungime bloc = 128 biti)

Criptografie si Securitate

36/37

Sisteme bloc ca PRP

Ideal ar fi sa se utilizeze o permutare aleatoare pe n biti;

Ar fi necesari n 2n biti pentru stocare;

Pentru n = 50 este necesara o capacitate de stocare de

200TB !

Sistemele bloc au n general n 64 sau n 128 biti;

In consecinta, NU se poate utiliza o (singura) permutare

aleatoare!

Criptografie si Securitate

5/25

Retele de substitutie - permutare

I

Se construieste permutarea F , pe baza mai multor permutari

aleatoare fi de dimensiune mai mica;

Consideram F pe 128 biti si 16 permutari aleatoare f1 , . . . , f16

pe cate 8 biti;

Pentru x = x1 || . . . ||x16 , x {0, 1}128 xi {0, 1}8 :

Fk (x) = f1 (x1 )|| . . . ||f16 (x16 )

Spunem ca {fi } introduc confuzie n F .

Criptografie si Securitate

7/25

Retele de substitutie - permutare

Intrebare: Considerand capacitatea necesara de stocare, este

F fesabila?

Raspuns: DA.

Fiecare fi necesita 8 28 biti pentru stocare;

Sunt 16 functii {fi }, deci n total F necesita pentru stocare

16 8 28 32KB.

Criptografie si Securitate

8/25

Retele de substitutie - permutare

I

F se transforma n PRP n 2 pasi:

I

Pasul 1: se introduce difuzie prin amestecarea (permutarea)

bitilor de iesire;

Pasul 2: se repeta o runda (care presupune confuzie si

difuzie) de mai multe ori;

Repetarea confuziei si difuziei face ca o modificarea unui

singur bit de intrare sa fie propagata asupra tutoror bitilor de
iesire;

Un exemplu pentru 2 runde si intrarea x:

I
I
I
I

x 0 = Fk (x);
x1 se obtine prin reordonarea bitilor din x 0 ;
x10 = Fk (x1 );
x2 se obtine prin reordonarea bitilor din x10 .

Criptografie si Securitate

10/25

Retele de substitutie - permutare

I

O retea de substitutie-permutare este o implementare a

constructiei anterioare de confuzie-difuzie n care functiile {fi }
sunt fixe (i.e. nu depind de cheie);

{fi } se numesc S-boxes (Substitution-boxes);

S-box-urile raman n continuare permutari;

Cum nu mai depind de cheie, aceasta este utilizata n alt scop;

Din cheie se obtin mai multe chei de rund

a (sub-chei) n
urma unui proces de derivare a cheilor (key schedule);

Fiecare cheie de runda este XOR-ata cu valorile intermediare

din fiecare runda.

Criptografie si Securitate

11/25

Retele de substitutie - permutare

Criptografie si Securitate

12/25

Principul 1: Inversabilitatea S-box

I

O retea de substitutie-permutare trebuie sa fie inversabila;

Daca fiecare runda este inversabila, atunci reteaua este

inversabila;

Intr-o runda:
I
I

XOR este inversabil;

Permutarea finala a bitilor de iesire este inversabila;

In concluzie, daca toate S-box-urile sunt inversabile, atunci

reteaua este inversabila;

Principiul 1 - necesitate functionala (pentru decriptare).

Criptografie si Securitate

14/25

Principul 2: Efectul de avalansa

I

Un singur bit modificat la intrare trebuie sa afecteze toti bitii

din secventa de iesire;

Efectul de avalansa apare ntr-o retea de substitutie-permutare

daca:
1. S-box-urile sunt proiectate a.. un singur bit schimbat la
intrare sa schimbe cel putin 2 biti de la iesire;
2. Permutarea este proiectata a.. bitii de la iesirea unui S-box sa
fie mpartiti ntre intrarile n S-box-uri diferite la runda
urmatoare.

Principiul 2 - necesitate de securitate.

Criptografie si Securitate

15/25

Retele Feistel

Se aseamana retelelor de substitutie-permutare n sensul ca

pastreaza aceleasi elementele componente: S-box, permutare,
procesul de derivare a cheii, runde;

Se diferentiaza de retelele de substitutie-permutare prin

proiectarea de nivel nalt;

Introduc avantajul major ca S-box-urile NU trebuie sa fie

inversabile;

Permit asadar obtinerea unei structuri inversabile folosind

elemente neinversabile.

Criptografie si Securitate

17/25

Retele Feistel

Criptografie si Securitate

19/25

Descriere AES
I

AES este o retea de substitutie - permutare pe 128 biti care

poate folosi chei de 128, 192 sau 256 biti;

Lungimea cheii determina numarul de runde:

Lungime cheie (biti)
Numar runde

128
10

192
12

256
14

Foloseste o matrice de octeti 4 4 numita stare;

Starea initiala este mesajul clar (4 4 8 = 128);

Starea este modificata pe parcursul rundelor prin 4 tipuri de

operatii: AddRoundKey, SubBytes, ShiftRows, MixColumns;

Iesirea din ultima runda este textul criptat.

Criptografie si Securitate

5/10

Descriere AES
I

Sa ne reamintim exemplul de retea de substitutie - permutare

prezentat n cursurile anterioare:
1. XOR cu cheia de runda;
2. aplicarea S-box-urilor pentru a obtine confuzie;
3. amestecarea bitilor pentru a obtine difuzie.

Criptografie si Securitate

7/10

Descriere AES

AES este o retea de substitutie - permutare:

I

AddRoundKey: XOR cu cheia de runda;

SubBytes: fiecare octet este nlocuit de un alt octet conform

tabelei de substitutie S-box (unica pentru AES!);

ShiftRows si MixColumns: amestecarea bitilor presupune mai

mult decat o simpla permutare, folosind o transformare liniara
pe biti.

Criptografie si Securitate

8/10

Scenarii de atac
I

Reamintim cateva dintre scenariile de atac pe care le-am mai

ntalnit:
I

Atac cu text criptat: Atacatorul stie doar textul criptat - poate

ncerca un atac prin forta bruta prin care se parcurg toate
cheile pana se gaseste cea corecta;

Atac cu text clar: Atacatorul cunoaste una sau mai multe

perechi (text clar, text criptat);

Atac cu text clar ales: Atacatorul poate obtine criptarea unor

texte clare alese de el;

Atac cu text criptat ales: Atacatorul are posibilitatea sa obtina

decriptarea unor texte criptate alese de el.

Criptografie si Securitate

3/38

cpa
Experimentul PrivA,
(n)

Output-ul experimentului este 1 daca b 0 = b si 0 altfel. Daca

cpa
(n) = 1, spunem ca A a efectuat experimentul cu
PrivA,
succes.

Criptografie si Securitate

13/38

cpa
Experimentul PrivA,
(n)

Definitie
O schema de criptare = (Enc, Dec) este CPA-sigura daca pentru
orice adversar PPT A exista o functie neglijabila negl asa ncat
cpa
Pr[PrivA,
(n) = 1]

1
2

+ negl(n).

Un adversar nu poate determina care text clar a fost criptat

cu o probabilitate semnificativ mai mare decat daca ar fi ghicit
(n sens aleator, dat cu banul), chiar daca are acces la oracolul
de criptare.

Criptografie si Securitate

14/38

Securitate CPA

Intrebare: Un sistem de criptare CPA-sigur este ntotdeauna

semantic sigur?
eav (n) este Priv cpa (n)
Raspuns: DA! Experimentul PrivA,
n care
A,
A nu foloseste oracolul de criptare.

Intrebare: Un sistem de criptare determinist poate fi

CPA-sigur?

Raspuns: NU! Adversarul cere oracolului criptarea mesajului

m0 . Daca textul criptat este egal cu c, atunci b 0 = 0, altfel
b 0 = 1. In concluzie, A castiga cu probabilitate 1.

Criptografie si Securitate

15/38

Securitate CCA
I

Capabilitatile adversarului: el poate interactiona cu un oracol

de criptare si cu un oracol de decriptare, fiind un adversar
activ care poate rula atacuri n timp polinomial;

Adversarul poate transmite catre oracolul de criptare orice

mesaj m si primeste napoi textul criptat corespunzator sau
poate transmite catre oracolul de decriptare anumite mesaje c
si primeste napoi mesajul clar corespunzator;

Daca sistemul de criptare este nedeterminist, atunci oracolul

de criptare foloseste de fiecare data o valoare aleatoare noua
si neutilizata anterior.

Criptografie si Securitate

22/38

cca
Experimentul PrivA,
(n)

Pe toata durata experimentului, A are acces la oracolul de

criptare Enck () si la oracolul de decriptare Deck () cu
restrictia ca nu poate decripta c!

Criptografie si Securitate

28/38

cca
Experimentul PrivA,
(n)

Definitie
O schema de criptare = (Enc, Dec) este CCA-sigura daca pentru
orice adversar PPT A exista o functie neglijabila negl asa ncat
cca (n) = 1]
Pr[PrivA,

1
2

+ negl(n).

Un adversar nu poate determina care text clar a fost criptat

cu o probabilitate semnificativ mai mare decat daca ar fi ghicit
(n sens aleator, dat cu banul), chiar daca are acces la
oracolele de criptare si decriptare.

Criptografie si Securitate

30/38

Comunicare sigura si integritatea mesajelor

I

Un scop de baza al criptografiei este sa asigure comunicarea

sigura de-a lungul unui canal public de comunicare;

Am vazut cum putem obtine aceasta cu ajutorul schemelor de

criptare;

Insa, nu ne intereseaza doar ca adversarul sa nu aiba acces la

mesajele trimise, ci...

Vrem sa garantam integritatea mesajelor (sau autentificarea

mesajelor)

Aceasta nseamna ca mesajul primit de Bob este exact mesajul

trimis de Alice.

Criptografie si Securitate

3/42

Criptare vs. autentificarea mesajelor

I

Raspuns: Atacul se aplica identic pentru modurile OFB si

CTR;

Pentru modul ECB, modificarea unui bit din al i-lea bloc

criptat afecteaza numai al i-lea bloc clar, dar este foarte greu
de prezis efectul exact;

Mai mult, ordinea blocurilor la ECB poate fi schimbata;

Pentru modul CBC, schimbarea bitului j din IV va schimba

bitul j din primul bloc;

Toate celelalte blocuri de text clar raman neschimbate

(mi = Fk1 (ci ) ci1 iar blocurile ci si ci1 nu au fost
modificate).

Criptografie si Securitate

9/42

MAC - Definitie

Alice si Bob stabliesc o cheie secreta k pe care o partajeaza;

Cand Alice vrea sa i trimita un mesaj m lui Bob, calculeaza

mai ntai un tag t pe baza mesajului m si a cheii k si trimite
perechea (m, t);

Criptografie si Securitate

11/42

MAC - Definitie
Definitie
Un cod de autentificare a mesajelor (MAC) definit peste
(K, M, T ) este format dintr-o pereche de algoritmi polinomiali
(Mac, Vrfy) unde:
1. Mac : K M T este algoritmul de generare a tag-urilor
t Mack (m);
2. Vrfy : K M T {0, 1}
este algoritmul de verificare ce ntoarce un bit
b = Vrfyk (m, t) cu semnificatia ca:
I
I

b = 1 nseamna valid
b = 0 nseamna invalid

a. : m M, k K Vrfyk (m, Mack (m)) = 1.

Criptografie si Securitate

13/42

Securitate MAC - discutie

Intuitie: nici un adversar polinomial nu ar trebui sa poata

genera un tag valid pentru nici un mesaj nou care nu a fost
deja trimis (si autentificat) de partile care comunica;

Trebuie sa definim puterea adversarului si ce nseamna

spargerea sau un atac asupra securitatii;

Adversarul lucreaza n timp polinomial si are acces la mesajele

trimise ntre parti mpreuna cu tag-urile aferente.

Adversarul poate influenta continutul mesajelor (direct sau

indirect), fiind deci un adversar activ.

Criptografie si Securitate

14/42

Experimentul Macforge
A, (n)

Output-ul experimentului este 1 daca si numai daca:

(1) Vrfyk (m, t) = 1 si (2) m
/ {m1 , ..., mq };
Daca Macforge
a A a efectuat experimentul
A, (n) = 1, spunem c
cu succes.

Criptografie si Securitate

22/42

Atacuri prin replicare

I

Intrebare: De ce este necesara a doua conditie de la

securitatea MAC (un adversar nu poate ntoarce un mesaj
pentru care anterior a cerut un tag)?

Raspuns: Pentru a evita atacurile prin replicare n care un

adversar copiaza un mesaj mpreuna cu tag-ul aferent trimise
de partile comunicante;

Intrebare: Definitia MAC ofera protectie la atacurile prin

replicare efectuate chiar de partile comunicante?

Raspuns: NU! MAC-urile nu ofera nici un fel de protectie la

atacurile prin replicare efectuate de partile comunicante.

Criptografie si Securitate

24/42

Constructia MAC-urilor sigure

I

Functiile pseudoaleatoare (PRF) sunt un instrument bun

pentru a construi MAC-uri sigure;

Constructie
Fie F : {0, 1}n {0, 1}n {0, 1}n o PRF. Definim un MAC n
felul urmator:
I

Mac : pentru o cheie k {0, 1}n si un mesaj m {0, 1}n ,

calculeaza tag-ul t = Fk (m) (daca |m| =
6 |k| nu ntoarce
nimic);

Vrfy : pentru o cheie k {0, 1}n , un mesaj m {0, 1}n si un

tag t {0, 1}n , ntoarce 1 daca si numai daca t = Fk (m)
(daca |m| =
6 |k|, ntoarce 0).

Criptografie si Securitate

28/42

CBC-MAC
I

O solutie mult mai eficienta este sa folosim CBC-MAC;

CBC-MAC este o constructie similara cu modul CBC folosit

pentru criptare;

Folosind CBC-MAC, pentru un tag aferent unui mesaj de

lungime l n, se aplica sistemul bloc doar de l ori.

Criptografie si Securitate

37/42

CBC-MAC
Definitie
Fie F o functie pseudoaleatoare. Un CBC-MAC este format dintr-o
pereche de algoritmi polinomiali probabilisti (Mac, Vrfy):
1. Mac: pentru o cheie k {0, 1}n si un mesaj m de lungime l:
I
I

Sparge m in m = m1 , ..., ml , |mi | = n si noteaza t0 = 0n ;

Pentru i = 1, ..., l, calculeaza ti = Fk (ti1 mi );

Intoarce tl ca tag-ul rezultat;

2. Vrfy : pentru o cheie k {0, 1}n , un mesaj m de lungime l, si
un tag t de lungime n:
ntoarce 1 daca si numai daca t = Mack (m).
Ramane valabila conditia de corectitudine:
m M, k K, Vrfyk (m, Mack (m)) = 1.
Criptografie si Securitate

38/42

CBC-MAC pentru mesaje de lungime variabila

Putem modifica constructia anterioara n diverse moduri ca sa
obtinem o versiune de CBC-MAC pentru mesaje de lungime
variabila. Iata trei dintre ele care pot fi demonstrate ca fiind sigure:
1. Calculeaza kl = Fk (l); Apoi foloseste CBC-MAC cu cheia kl ;
aceasta asigura faptul ca sunt folosite chei diferite pentru a
autentifica mesaje de lungimi diferite;
2. Se adauga un bloc de mesaj (n fata primului bloc) care
contine |m| si se aplica CBC-MAC pe mesajul rezultat.
3. Se poate modifica schema asa ncat sa se aleaga doua chei
k1 , k2 {0, 1}n ; se autentifica mesajul m cu CBC-MAC
folosind cheia k1 si se obtine t iar tag-ul rezultat va fi
t 0 = Fk2 (t).

Criptografie si Securitate

41/42

Schema de criptare CCA sigura

I

Cele doua parti comunicante partajeaza doua chei secrete,

una pentru schema de criptare CPA sigura si nca una pentru
un cod de autentificare a mesajelor (MAC).

Pentru criptarea unui mesaj m, Alice procedeaza astfel:

I

I
I

cripteaza m folosind schema CPA sigura, rezultand textul

criptat c
calculeaza un tag MAC t pe textul criptat c
rezultatul final al criptarii este hc, ti

Pentru un text criptat hc, ti, Bob verifica validitatea tag-ului

nainte de a decripta;

Un text criptat hc, ti este valid daca t este un tag valid

pentru c.

Criptografie si Securitate

6/10

O schema de criptare CCA sigura

Constructie
Fie E = (Enc, Dec) o schema de criptare cu cheie secreta si
M = (Mac, Vrfy) un cod de autentificare a mesajelor.
Definim schema de criptare (Enc0 , Dec0 ) astfel:
I

Enc: pentru o cheie (k1 , k2 ) si un mesaj m, calculeaza

c = Enck1 (m) si t = Mack2 (c) si ntoarce textul criptat hc, ti;

Dec: pentru o cheie (k1 , k2 ) si un text criptat hc, ti, verifica

daca Vrfyk2 (c, t) = 1. In caz afirmativ, ntoarce Deck1 (c),
altfel ntoarce .

Simbolul indica esec;

Corectitudinea schemei cere ca Deck1 ,k2 (Enck1 ,k2 (m)) 6=.

Spunem ca (Mac, Vrfy) are tag-uri unice daca m k un

unic tag t a.. Vrfyk (m, t) = 1.

Criptografie si Securitate

7/10

Demonstratie intuitiva
I

Un text criptat hc, ti este valid (n raport cu o cheie (k1 , k2 ))

daca Vrfyk2 (c, t) = 1;

Mesajele pe care adversarul A le trimite catre oracolul de

decriptare sunt de 2 feluri:
I

texte criptate pe care A le-a primit de la oracolul de criptare

(stie deja textul clar, deci nu i sunt de folos);

texte criptate pe care nu le-a primit de la oracolul de criptare;

Insa, cum M este un MAC sigur, cu probabilitate foarte mare

textele criptate care nu au fost obtinute de la oracolul de
criptare sunt invalide, iar oracolul de decriptare va ntoarce
n acest caz;

Cum oracolul de decriptare este inutil, securitatea schemei

(Enc0 , Dec0 ) se reduce la securitatea CPA a schemei E .

Criptografie si Securitate

9/10

Securitatea functiilor hash

I

In practica, rezistenta la coliziuni poate fi dificil de obtinut;

Pentru anumite aplicatii sunt utile notiuni mai relaxate de

securitate;

Exista 3 nivele de securitate:

1. Rezistenta la coliziuni: este cea mai puternica notiune de
securitate si deja am definit-o formal;
2. Rezistenta la a doua preimagine: presupune ca fiind dat x este
dificil de determinat x 0 6= x a.. H(x) = H(x 0 )
3. Rezistenta la prima preimagine: presupune ca fiind dat H(x)
este imposibil de determinat x.

Criptografie si Securitate

17/32

Rezistenta la coliziuni

Provocare: Se cer 2 valori x 6= x 0 a.. H(x) = H(x 0 );

Atac: Atacul zilei de nastere necesita 2l(n)/2 evaluari

pentru H.

Criptografie si Securitate

18/32

Rezistenta la a doua preimagine

Provocare: Fiind dat x, se cere x 0 a.. H(x) = H(x 0 );

Atac: Un atac generic necesita 2n evaluari pentru H.

Criptografie si Securitate

19/32

Rezistenta la prima preimagine

Provocare: Fiind dat y = H(x), se cere x a.. H(x) = y ;

O astfel de functie se numeste si calculabila ntr-un singur

sens (one-way function);

Atac: Un atac generic necesita 2n evaluari pentru H.

Criptografie si Securitate

20/32

Securitatea functiilor hash

I

Intrebare: De ce o functie care satisface proprietatea de

rezistent
a la coliziuni satisface si proprietatea de rezistent
a
la a doua preimagine?

Raspuns: Pentru x fixat, adversarul determina x 0 6= x pentru

care H(x) = H(x 0 ), deci gaseste o coliziune;

Intrebare: De ce o functie care satisface proprietatea de

rezistent
a la a doua preimagine satisface si proprietatea de
rezistent
a la prima imagine?

Raspuns: Pentru x oarecare, adversarul calculeaza H(x), o

inverseaza si determina x 0 a.. H(x 0 ) = H(x). Cu probabilitate
mare x 0 6= x, deci gaseste o a doua preimagine.

Criptografie si Securitate

22/32

Atacul zilei de nastere

I

Generalizand, consideram o multime de dimensiune n si q

elemente uniform aleatoare din aceasta multime y1 , . . . , yq ;

Atunci pentru q 1.2 2n/2 probabilitatea sa existe i 6= j a..

yi = yj este 1/2.

Aceast rezultat conduce imediat la un atac asupra functiilor

hash cu scopul de a determina coliziuni:

Adversarul alege 2n/2 valori xi ;

Calculeaza pentru fiecare yi = H(xi );

Cauta i 6= j cu H(xi ) = H(xj );

Daca nu gaseste nici o coliziune, reia atacul.

Cum probabilitatea de succes a atacului este 1/2, atunci

numarul de ncercari este 2.

Criptografie si Securitate

24/32

Transformarea Merkle-Damg
ard
I

Scopul este sa construim o functie hash (cu intrare de lungime

variabila), pornind de la o functie de compresie (de lungime
fixa);

Pentru aceasta se aplica transformarea Merkle-Damg

ard;

Criptografie si Securitate

27/32

Transformarea Merkle-Damg
ard
I

Ramane sa prezentam o constructie pentru h;

Constructia Davies-Meyer:

Enc este un sistem bloc care cripteaza zi1 cu cheia xi :

h(zi1 ||xi ) = Encxi (zi1 ) zi1

Criptografie si Securitate

30/32

Revizuire: MAC-uri
I

In prelegerile anterioare am vazut ca putem construi MAC-uri

sigure pe baza functiilor pseudoaleatoare (PRF);

Pentru F : {0, 1}n {0, 1}n {0, 1}n o PRF, defineam un

MAC astfel

Mac(k, m) : t = Fk (m);

Vrfy(k, m, t) = 1 daca si numai daca t = Fk (m) (altfel

ntoarce 0).

Aceasta constructie este buna pentru mesaje de lungime mica,

dar avem nevoie de constructii de MAC-uri pentru mesaje
mult mai mari;

Criptografie si Securitate

3/11

Revizuire: MAC-uri

Insa pentru mesaje de lungime variabila, putem retine aceasta

constructie ca fiind sigura:

Criptografie si Securitate

5/11

HMAC
I

Incercam sa construim un MAC direct pornind de la H(),

unde H() este functia hash obtinuta cu transformarea
Merkle-Damg
ard;

Definim Mac(k, m) astfel: t = H(k||m).

Intrebare: Este acesta un MAC sigur (nu poate fi falsificat

printr-un atac cu mesaj clar ales)?

Raspuns: NU! Un advesar poate calcula un tag t 0 pentru un

mesaj nou care nu a mai fost autentificat: extinde mesajul
anterior cu nca un bloc d, si calculeaza:
H(k||m||d) = h(d||H(k||m))

Criptografie si Securitate

7/11

HMAC
I

Folosim metoda standardizata HMAC (Hash MAC):

HMAC se defineste astfel:

Mac(k, m): t = H((k opad) || H((k ipad) || m));

Vrfy(k, m, t) = 1 t = Mac(k, m).

Criptografie si Securitate

8/11

Notatii

ipad si opad sunt doua constante de lungimea unui bloc mi

ipad consta din byte-ul 0x5C repetat de atatea ori cat e

nevoie;

opad consta din byte-ul 0x36 repetat de atatea ori cat e

nevoie;

IV este o constanta fixata.

Criptografie si Securitate

9/11

Securitate HMAC
I

Definim G (k) = h(IV || (k opad)) ||h(IV || (k ipad))

Privind secventa ca G (k) = k1 ||k2 , daca G este PRG si

k R {0, 1}n , desi k1 , k2 sunt dependente, acestea par alese
n mod uniform si independent;

Daca G este PRG, atunci dam urmatorul rezultat de securitate

pentru HMAC :

Teorema
Daca G este PRG, h prezinta rezistenta la coliziuni si MAC-ul
h(k || m) contruit be baza ei este sigur (pentru mesaje de lungime
fixa), atunci HMAC este sigur (pentru mesaje de lungime
arbitrara) - nu poate fi falsificat printr-un atac cu mesaj ales.

Criptografie si Securitate

10/11

Atac de timp
Pasii atacului:
1. A trimite cerere catre server pentru m si un tag aleator
t = B1 B2 ...Bn (t este reprezentat pe octeti) si masoara
timpul pana server-ul raspunde;
2. A trimite cerere catre server pentru fiecare ti 0 = i B 02 ...B 0n
pentru i = 1, 2, 3... (B 02 , ..., B 0n sunt octeti arbitrari);
3. A se opreste cand timpul de verificare e putin mai mare decat
la pasul 1;
4. In acest caz, a gasit primul octet si continua atacul pentru
urmatorii octeti, pe rand, pana cand gaseste tag-ul valid.

Criptografie si Securitate

5/8

Criptarea asimetrica (cu cheie publica)

Definitie
Un sistem de criptare asimetric definit peste (K, M, C), cu:
I

K = Kpk Ksk = spatiul cheilor, de forma unor perechi

(pk, sk), unde pk este cheia public
a si sk este cheia secret
a

M = spatiul textelor clare (mesaje)

C = spatiul textelor criptate

este un dublet (Enc, Dec), unde:

1. Enc : Kpk M C
2. Dec : Ksk C M
a.. m M, (pk, sk) K : Decsk (Encpk (m)) = m.

Criptografie si Securitate

15/19

Generarea numerelor prime

I

Pentru distributia numerelor prime, se cunoaste urmatorul

rezultat matematic:

Teorema
Exista o constanta c asa ncat, pentru orice n > 1 numarul de
numere prime pe n biti este cel putin c 2n1 /n
I

Rezulta imediat ca probabilitatea ca un numar ales aleator pe

n biti sa fie prim este cel putin c/n;

Iar daca testam t = n2 /c numere, probabilitatea ca un numar

prim sa nu fie ales este (1 c/n)t , adica cel mult e n , deci
neglijabila.

Criptografie si Securitate

8/29

Testarea primalitatii
Algorithm 1 Algoritmul Miller-Rabin
Input: N , t
Output: o decizie daca N este compus sau nu
1: if N este par sau N = N1 2 then
2:
return compus
3: end if
4: compute r 1
si u impar a.. N 1 = 2r u
5: for j = 1 to t do
6:
a {1, ..., N 1}
i
7:
if (gcd(a, N) 6= 1) or (au 6= 1 mod N and a2 u 6= 1 mod
N, pentru orice i {1, ..., r 1}) then
8:
return compus
9:
end if
10: end for
11: return prim
Criptografie si Securitate

10/29

Algoritmul Miller-Rabin

Accepta la intrare un numar N si un parametru t care

determina probabilitatea de eroare;

Ruleaza n timp polinomial n |N| si t si satisface:

Teorema
Daca N este prim, atunci testul Miller-Rabin ntoarce mereu
prim. Daca N este compus, algoritmul ntoarce prim cu
probabilitate cel mult 2t (i.e. ntoarce rezultatul corect compus
cu probabilitate 1 2t )

Criptografie si Securitate

11/29

Experimentul logaritmului discret DLogA (n)

1. Genereaza (G, q, g ) unde G este un grup ciclic de ordin q (cu
|q| = n) iar g este generatorul lui G.
0

2. Alege h R G. (se poate alege x 0 R Zq si apoi h := g x .)

3. A primeste G, q, g , h si ntoarce x Zq ;
4. Output-ul experimentului este 1 daca g x = h si 0 altfel.

Definitie
Spunem ca problema logaritmului discret (DLP) este dificila daca
pentru orice algoritm PPT A exista o functie neglijabila negl asa
ncat
Pr [DLogA (n) = 1] negl(n)
Criptografie si Securitate

26/29

Lucrul n Zp
I

DLP este considerata dificila n grupuri ciclice de forma Zp cu

p prim;

Insa pentru p > 3 grupul Zp NU are ordin prim;

Aceasta problema se rezolva folosind un subgrup potrivit al lui

Zp ;

Reamintim: Un element y Zp este rest patratic modulo p

daca x Zp a.. x 2 = y mod p;

Multimea resturilor patratice modulo p formeaza un subgrup

al lui Zp ;

Daca p este numar prim tare (i.e. p = 2q + 1 cu q prim),

subgrupul resturilor patratice modulo p are ordin q, deci este
ciclic si toate elementele sunt generatori.

Criptografie si Securitate

28/29

Securitate perfecta
I

Incepem studiul securitatii n acelasi mod n care am nceput

la criptografia simetrica: cu securitatea perfecta;

Definitia e analoaga cu diferenta ca adversarul cunoaste, n

afara textului criptat, si cheia publica;

Definitie
O schema de criptare peste un spatiu al mesajelor M este perfect
sigura daca pentru orice probabilitate de distributie peste M,
pentru orice mesaj m M si orice text criptat c cu cheia publica
pk pentru care Pr [C = c] > 0, urmatoarea egalitate este
ndeplinita:
Pr [M = m|C = c] = Pr [M = m]

Criptografie si Securitate

3/26

eav
Experimentul PubKA,
(n)

Output-ul experimentului este 1 daca b 0 = b si 0 altfel. Daca

eav (n) = 1, spunem c
PubKA,
a A a efectuat experimentul cu
succes.

Criptografie si Securitate

11/26

Securitate pentru interceptare simpla

I

Principala diferenta fata de definitia similara studiata la

criptografia cu cheie secreta este ca A primeste cheia publica
pk;

Adica A primeste acces gratuit la un oracol de criptare, ceea

ce nseamna ca el poate calcula Encpk (m) pentru orice m;

Prin urmare, definitia este echivalenta cu cea pentru

securitate CPA (nu mai este necesar oracolul de criptare
pentru ca A isi poate cripta singur mesajele);

Reamintim ca n criptografia simetrica exista scheme sigure la

securitate semantica dar care nu sunt CPA-sigure .

Criptografie si Securitate

13/26

Securitate CCA
I

Notiunea de securitate CCA ramane identica cu cea de la

sistemele simetrice;

Capabilitatile adversarului: el poate interactiona cu un oracol

de decriptare, fiind un adversar activ care poate rula atacuri
n timp polinomial;

Adversarul poate transmite catre oracolul de decriptare

anumite mesaje c si primeste napoi mesajul clar
corespunzator;

Ca si n cazul securitatii CPA, adversarul nu mai necesita

acces la oracolul de criptare pentru ca detine cheia publica pk
si poate realiza singur criptarea oricarui mesaj m.

Criptografie si Securitate

25/26

Permutari cu trapa secreta

I

Reamintim notiunea de functie one-way;

Aceasta este o functie pentru care este usor de calculat

valoarea functiei...

... dar este dificil de calculat valoarea functiei inverse;

Am ntalnit notiunea cand am studiat functiile hash;

Daca H : {0, 1} {0, 1}n este o functie hash (rezistenta la

prima preimagine), atunci:
I

Fiind dat x, este eficient de calculat H(x);

Cunoscand H(x) este (computational) dificil de calculat x.

Criptografie si Securitate

3/15

Permutari cu trapa secreta

Definitie
O permutare cu trapa secreta sau TDP (TrapDoor Permutation)
este un triplet (Gen, F , F 1 ) unde:
1. Gen este un algoritm nedeterminist PPT care genereaza o
pereche de chei (pk, sk);
2. F (pk, ) : X X este o functie one-way;
3. F 1 (sk, ) : X X este o functie eficient calculabila;
x X , F 1 (sk, F (pk, x)) = x
I

F este sigura daca poate fi eficient evaluata, dar nu poate fi

inversata fara cunoasterea cheii secrete sk (decat cu
probabilitate neglijabila);

1
Notatii: F (pk, ) = Fpk (), F 1 (sk, ) = Fsk
().

Criptografie si Securitate

5/15

Problema rucsacului
I

Exista nsa clase usoare ale problemei rucsacului;

Una dintre acestea o reprezinta vectorii super-crescatori;

Un vector A = (a1 , a2 , . . . , an ) este super-crescator daca

satisface:
j1
X
j 2, aj >
ai
i=1

Un exemplu este vectorul:

A = {1, 3, 5, 11, 21, 44, 87}
3>1
5>1+3
11 > 1 + 3 + 5
21 > 1 + 3 + 5 + 11
44 > 1 + 3 + 5 + 11 + 21
87 > 1 + 3 + 5 + 11 + 21 + 44

Criptografie si Securitate

7/15

Problema rucsacului

Transformam o problema simpl

a a rucsacului ntr-o problema
dificil
a pe baza unei informatii secrete si obtinem astfel o
functie cu trap
a secret
a;

Fie un vector supercrescator A = (a1 , a2 , . . . , an );

Se aleg un modul m si un multiplicator t a.. gcd(c, m) = 1;

Se calculeaza B = (b1 , b2 , . . . , bn ), unde bi = ai t (mod m);

Cunoscand A problema este simpla, dar cunoscand B

problema este dificila.

Criptografie si Securitate

10/15

Constructia sistemelor de criptare asimetrice

I

Folosim TDP pentru constructia sistemelor de criptare

asimetrice;

Constructie
Fie (Gen, F , F 1 ) TDP cu F : X Y, (Enc, Dec) un sistem de
criptare simetric sigur cu autentificarea mesajelor definit peste
(X , Y) si H : X K o functie hash. Definim un sistem de criptare
asimetrica peste (K, X , Y) n felul urmator:
I

Encpk (m) = (y , c) = (Fpk (x), Enck (m)), unde k = H(x) si

x R X ;
1
Decsk (y, c) = Deck (c), unde k = H(x) si x = Fsk
(y );

Criptografie si Securitate

13/15

Problema RSA
I

Problema RSA se bazeaza pe dificultatea factorizarii

numerelor mari: N = p q, p si q prime;

Fie ZN un grup de ordin (N) = (p 1)(q 1);

Problema RSA
Fiind dat N, un ntreg e > 0 care satisface (e, (N)) = 1, si un
element y ZN , se cere sa se gaseasca x a.. x e = y mod N.
I

Daca se cunoaste factorizarea lui N, atunci (N) este usor de

calculat si problema RSA este usor de rezolvat;

Daca nu se cunoacste (N), problema RSA este dificila.

Criptografie si Securitate

6/18

Experimentul RSA RSA invA,GenRSA(n)

I

Consideram experimentul RSA pentru un algoritm A si un

parametru n.
1. Executa GenRSA si obtine (N, e, d);
2. Alege y ZN ;
3. A primeste N, e, y si ntoarce x ZN ;
4. Output-ul experimentului este 1 daca x e = y mod N si 0 altfel.

Definitie
Spunem ca problema RSA este dificila cu privire la GenRSA daca
pentru orice algoritm PPT A exista o functie neglijabila negl asa
ncat
Pr [RSA invA,GenRSA(n) = 1] negl(n)
Criptografie si Securitate

7/18

GenRSA
I

Prezumptia RSA este ca exista un algoritm GenRSA pentru

care problema RSA este dificila;

Un algoritm GenRSA poate fi construit pe baza unui numar

compus mpreuna cu factorizarea lui;

Algorithm 3 GenRSA
Input: n
Output: N, e, d
1: print N cu factorii p
si q
2: (N) = (p 1)(q 1)
3: gase
ste e a.. gcd(e, (N)) = 1
4: calculeaz
a d := e 1 mod (N)
5: return N, e, d

Criptografie si Securitate

8/18

Implementarea RSA
Algorithm 4 Exponentiere rapida
Input: N, x, c
Output: x c mod N
Pn1 i
1: descompune c n binar: c =
i=0 ci 2
2: z 1
3: for i = n 1 to 0 do
4:
z z 2 mod N
5:
if ci = 1 then
6:
z z x mod N
7:
end if
8: end for
9: return z

Criptografie si Securitate

12/18

Securitate - Problema 4
Problema 4: Utilizarea multipla a modulului
I

Cunoscand e, d, N cu (e, (N)) = 1 se poate determina

eficient factorizarea lui N;

Intrebare: Este corect sa se utilizeze mai multe perechi de chei

care folosesc acelasi modul?

Raspuns: NU! Fie 2 perechi de chei:

pk1 = (N, e1 ); sk1 = (N, d1 )
pk2 = (N, e2 ); sk2 = (N, d2 )

Posesorul perechii (pk1 , sk1 ) factorizeaza N, apoi determina

d2 = e21 mod (N).

Criptografie si Securitate

16/18

Sistemul de criptare RSA

Folosim constructia prezentata n prelegerea anterioara,

utilizand RSA ca TDP:

Constructie
Fie (Enc, Dec) un sistem de criptare simetric sigur cu autentificarea
mesajelor definit peste ZN si H : ZN K o functie hash. Definim
un sistem de criptare asimetrica peste n felul urmator:
I

Encpk (m) = (y , c) = (RSApk (x), Enck (m)), unde k = H(x) si

x R ZN ;

Decsk (y, c) = Deck (c), unde k = H(x) si x = RSAsk (y );

Criptografie si Securitate

17/18

PKCS #1 v1.5

Notam k lungimea modulului N n bytes: 28(k1) k < 28k ;

Mesajele m care se cripteaza se considera multiplii de 8 biti,

de maxim k 11 bytes;

Criptarea se realizeaza astfel:

(00000000||00000010||r ||00000000||m)e

mod N

r este ales aleator, pe k D 3 bytes nenuli, unde D este

lungimea lui m n bytes;

Criptografie si Securitate

7/13

Securitatea PKCS #1 v1.5

I

Se crede ca este CPA-sigur, dar acest lucru nu este

demonstrat;

Cu siguranta nsa nu este CCA-sigur;

In 1998, [Link] publica un atac care bazandu-se pe
faptul ca serverul web (HTTPS) ntoarce eroare daca primii 2
octeti nu sunt 02;

Scopul adversarului este sa decripteze un text c;

Adversarul transmite catre server c 0 = r e c mod N;

Raspunsul serverului indica adversarului daca c 0 este valid (i.e.

ncepe cu 02);

Adversarul foloseste raspunsul primit pentru a determina

informatii despre m;

Repeta atacul pana determina mesajul m.

Criptografie si Securitate

8/13

Metoda de calcul a indicelui

I

Pasul 1. Fie q = p 1, ordinul lui Zp si B = {p1 , ..., pk } o

baza de numere prime mici;

Se cauta l k numere distincte x1 , ..., xl Zq pentru care

gi = [g xi mod p] este mic asa ncat toti factorii primi ai lui
gi se gasesc n B;

Vor rezulta relatii de forma

e

g xi = p1i,1 p2i,2 pki,k mod p

unde 1 i k.
I

sau
xi = ei,1 logg p1 ei,2 logg p2 ei,k logg pk mod p 1

Criptografie si Securitate

8/20

Schimbul de chei Diffie-Hellman

Criptografie si Securitate

6/16

Schimbul de chei Diffie-Hellman

I

Alice si Bob doresc sa stabileasca o cheie secreta comuna;

Alice genereaza un grup ciclic G, de ordin q cu |q| = n si g un

generator al grupului;

Alice alege x R Zq si calculeaza h1 := g x ;

Alice i trimite lui Bob mesajul (G, g , q, h1 );

Bob alege y R Zq si calculeaza h2 := g y ;

Bob i trimite h2 lui Alice si ntoarce cheia kB := h1y ;

Alice primeste h2 si ntoarce cheia kA = h2x .

Criptografie si Securitate

7/16

Schimbul de chei Diffie-Hellman

Corectitudinea protocolului presupune ca kA = kB , ceea ce se

verifica usor:

Bob calculeaza cheia

kB = h1y = (g x )y = g xy

Alice calculeaza cheia

kA = h2x = (g y )x = g xy

Criptografie si Securitate

8/16

Securitate

O conditie minimal
a pentru ca protocolul sa fie sigur este ca
DLP sa fie dificila n G;

Intrebare: Cum poate un adversar pasiv sa determine cheia

comuna daca poate sparge DLP?

Raspuns: Asculta mediul de comunicatie si preia mesajele h1

si h2 . Rezolva DLP pentru h1 si determina x, apoi calculeaza
kA = kB = h2x .

Aceasta nu este nsa singura conditie necesara pentru a

proteja protocolul de un atacator pasiv!

Criptografie si Securitate

9/16

CDH (Computational Diffie-Hellman)

I

O conditie mai potrivita ar fi ca adversarul sa nu poata

determina cheia comuna kA = kB , chiar daca are acces la
ntreaga comunicatie;

Aceasta este problema de calculabilitate Diffie-Hellman

(CDH): Fiind date grupul ciclic G, un generator g al sau si 2
elemente h1 , h2 R G, sa se determine:
CDH(h1 , h2 ) = g logg h1 logg h2

Pentru schimbul de chei Diffie-Hellman, rezolvarea CDH

nseamna ca adversarul determina kA = kB = g xy cunoscand
h1 , h2 , G, g (toate disponibile pe mediul de transmisiune
nesecurizat).

Criptografie si Securitate

10/16

DDH (Decisional Diffie-Hellman)

I

Nici aceasta conditie nu este suficienta: chiar daca adversarul

nu poate determina cheia exacta, poate de exemplu sa
determine parti din ea;

O conditie si mai potrivita este ca pentru adversar, cheia

kA = kB sa fie indistinctibil
a fata de o valoare aleatoare;

Sau, altfel spus, sa satisfaca problema de decidabilitate

Diffie-Hellman (DDH):

Definitie
Spunem ca problema decizionala Diffie-Hellman (DDH) este dificila
(relativ la G), daca pentru orice algoritm PPT A exista o functie
neglijabila negl asa ncat:
|Pr [A(G, q, g , g x , g y , g z ) = 1] Pr [A(G, q, g , g x , g y , g xy ) = 1]| negl(n),

unde x, y , z R Zq
Criptografie si Securitate

11/16

Atacul Man-in-the-Middle

Criptografie si Securitate

13/16

Atacul Man-in-the-Middle
I

Alice genereaza un grup ciclic G, de ordin q cu |q| = n si g un

generator al grupului;

Alice alege x R Zq si calculeaza h1 := g x ;

Alice i trimite lui Bob mesajul (G, g , q, h1 );

Oscar intercepteaza mesajul si raspunde lui Alice n locul lui

Bob: alege a R Zq si calculeaza h02 := g a ;

Oscar si Alice detin acum cheia comuna kA = g xa ;

Oscar initiaza, n locul lui Alice, o noua sesiune cu Bob: alege

b R Zq si calculeaza h01 := g b ;

Bob alege y R Zq si calculeaza h2 := g y ;

Oscar si Bob detin acum cheia comuna kB = g yb .

Criptografie si Securitate

14/16

Sistemul de criptare ElGamal

I

Se bazeaza pe DLP ...

... sau mai exact pe dificultatea problemei DDH...

... si pe urmatoarea observatie simpla:

Observatie
Fie G un grup finit si m R G. Daca g R G, atunci g 0 = m g
ramane aleator n G:
Pr [m g = g 0 ] = 1/|G|
unde probabilitatea este data de alegerea aleatoare a lui g .

Criptografie si Securitate

4/19

Sistemul de criptare ElGamal

I

Daca emitatorul si receptorul folosesc g drept cheie secreta,

atunci un mesaj m G se cripteaza ca:
g0 = m g

Receptorul decripteaza:
m = g 0 g 1

Abordarea este asemanatoare cu OTP, unde se folosea grupul

secventelor de lungime fixata mpreuna cu operatia XOR;

O astfel de constructie este deci perfect sigura (daca g este

total aleator!).

Criptografie si Securitate

5/19

Sistemul de criptare ElGamal

In criptografia cu cheie publica, se foloseste g pseudoaleator,

deci se pierde securitatea perfecta;

Ideea de baza este alegerea lui g astfel ncat la receptie sa

poata fi calculat pe baza cheii secrete...

... dar g sa para aleator pentru un adversar;

Pentru aceasta se foloseste prezumtia DDH, constructia fiind

imediata din schimbul de chei Diffie-Hellman.

Criptografie si Securitate

6/19

Sistemul de criptare ElGamal

I

Definim sistemul de criptare ElGamal pe baza ideii prezentate

anterior;
1. Se genereaza (G, q, g ), se alege x R Zq si se calculeaza
h = gx;
I
I

Cheia public
a este: (G, q, g , h);
Cheia privat
a este (G, q, g , x);

2. Enc: data o cheie publica (G, q, g , h) si un mesaj m G,

alege y R Zq si ntoarce c = (c1 , c2 ) = (g y , m hy );
3. Dec: data o cheie secreta (G, q, g , x) si un mesaj criptat
c = (c1 , c2 ), ntoarce m = c2 c1x .

Criptografie si Securitate

7/19

Securitate - Problema 3
Problema 3: Proprietatea de homomorfism
I

Fie m1 , m2 2 texte clare si c1 = (c11 , c12 ), c2 = (c21 , c22 )

textele criptate corespunzatoare;

Atunci:
c1 c2 = (c11 c21 , c12 c22 ) = (g y1 g y2 , m1 hy1 m2 hy2 )

Intrebare: Daca un adversar cunoaste c1 si c2 criptarile lui m1 ,

respectiv m2 , ce poate spune despre c1 c2 ?

Raspuns: c1 c2 este criptarea lui m1 m2 folosind y = y1 + y2 :

c1 c2 = (g y1 +y2 , m1 m2 hy1 +y2 )

Un sistem de criptare care satisface

Decs k(c1 c2 ) = Decsk (c1 ) Decsk (c2 ) se numeste sistem de
criptare homomorfic.
(homomorfismul este deseori o proprietate utila n criptografie)

Criptografie si Securitate

10/19

Comparatie ntre ECC, criptografia simetrica si asimetrica

Chei criptografia
simetrica
80
112
128
192
256

Chei RSA

Chei ECC

1024
2048
3072
7680
15360

160
224
256
384
521

Tabel: Dimensiunile cheilor recomandate de NIST

Criptografie si Securitate

15/16