riptografie si Securitate

- Prelegerea 21 -Despre problema logaritmului discret

Adela Georgescu, Ruxandra F. Olimid

Facultatea de Matematica si InformaticaUniversitatea din Bucuresti

Cuprins

1. Algoritmi pentru DLP

2. Functii hash rezistente la coliziuni bazate pe PLD

Criptografie si Securitate 2/20 ,

Algoritmi pentru calculul logaritmului discret

I Reamintim PLD:

I Fie G un grup ciclic de ordin q (cu |q| = n) iar g estegeneratorul lui G.

I Pentru fiecare h ∈ G exista un unic x ∈ Zq a.ı. g x = h.

I PLD cere gasirea lui x stiind G, q, g , h; notam x = logg h;

I Atentie! Atunci cand g x ′ = h pentru un x ′ arbitrar (deci NUneaparat x ∈ Zq), notam loggh = [x ′ mod q]

Criptografie si Securitate 3/20 ,

Algoritmi pentru calculul logaritmului discret

I Reamintim PLD:

I Fie G un grup ciclic de ordin q (cu |q| = n) iar g estegeneratorul lui G.

I Pentru fiecare h ∈ G exista un unic x ∈ Zq a.ı. g x = h.

I PLD cere gasirea lui x stiind G, q, g , h; notam x = logg h;

I Atentie! Atunci cand g x ′ = h pentru un x ′ arbitrar (deci NUneaparat x ∈ Zq), notam loggh = [x ′ mod q]

Criptografie si Securitate 3/20 ,

Algoritmi pentru calculul logaritmului discret

I Reamintim PLD:

I Fie G un grup ciclic de ordin q (cu |q| = n) iar g estegeneratorul lui G.

I Pentru fiecare h ∈ G exista un unic x ∈ Zq a.ı. g x = h.

I PLD cere gasirea lui x stiind G, q, g , h; notam x = logg h;

I Atentie! Atunci cand g x ′ = h pentru un x ′ arbitrar (deci NUneaparat x ∈ Zq), notam loggh = [x ′ mod q]

Criptografie si Securitate 3/20 ,

Algoritmi pentru calculul logaritmului discret

I Reamintim PLD:

I Fie G un grup ciclic de ordin q (cu |q| = n) iar g estegeneratorul lui G.

I Pentru fiecare h ∈ G exista un unic x ∈ Zq a.ı. g x = h.

I PLD cere gasirea lui x stiind G, q, g , h; notam x = logg h;

I Atentie! Atunci cand g x ′ = h pentru un x ′ arbitrar (deci NUneaparat x ∈ Zq), notam loggh = [x ′ mod q]

Criptografie si Securitate 3/20 ,

Algoritmi pentru calculul logaritmului discret

I Reamintim PLD:

I Fie G un grup ciclic de ordin q (cu |q| = n) iar g estegeneratorul lui G.

I Pentru fiecare h ∈ G exista un unic x ∈ Zq a.ı. g x = h.

I PLD cere gasirea lui x stiind G, q, g , h; notam x = logg h;

I Atentie! Atunci cand g x ′ = h pentru un x ′ arbitrar (deci NUneaparat x ∈ Zq), notam loggh = [x ′ mod q]

Criptografie si Securitate 3/20 ,

Algoritmi pentru calculul logaritmului discret

I Problema PLD se poate rezolva, desigur, prin forta bruta,calculand pe rand toate puterile x ale lui g pana cand segaseste una potrivita pentru care g x = h;

I Complexitatea timp este O(q) iar complexitatea spatiu esteO(1);

I Daca se precalculeaza toate valorile (x , g x), cautarea se faceın timp O(1) si spatiu O(q);

I Sunt de interes algoritmii care pot obtine un timp mai bun larulare decat forta bruta, realizand un compromis spatiu-timp.

Criptografie si Securitate 4/20 ,

Algoritmi pentru calculul logaritmului discret

I Problema PLD se poate rezolva, desigur, prin forta bruta,calculand pe rand toate puterile x ale lui g pana cand segaseste una potrivita pentru care g x = h;

I Complexitatea timp este O(q) iar complexitatea spatiu esteO(1);

I Daca se precalculeaza toate valorile (x , g x), cautarea se faceın timp O(1) si spatiu O(q);

I Sunt de interes algoritmii care pot obtine un timp mai bun larulare decat forta bruta, realizand un compromis spatiu-timp.

Criptografie si Securitate 4/20 ,

Algoritmi pentru calculul logaritmului discret

I Problema PLD se poate rezolva, desigur, prin forta bruta,calculand pe rand toate puterile x ale lui g pana cand segaseste una potrivita pentru care g x = h;

I Complexitatea timp este O(q) iar complexitatea spatiu esteO(1);

I Daca se precalculeaza toate valorile (x , g x), cautarea se faceın timp O(1) si spatiu O(q);

I Sunt de interes algoritmii care pot obtine un timp mai bun larulare decat forta bruta, realizand un compromis spatiu-timp.

Criptografie si Securitate 4/20 ,

Algoritmi pentru calculul logaritmului discret

I Problema PLD se poate rezolva, desigur, prin forta bruta,calculand pe rand toate puterile x ale lui g pana cand segaseste una potrivita pentru care g x = h;

I Complexitatea timp este O(q) iar complexitatea spatiu esteO(1);

I Daca se precalculeaza toate valorile (x , g x), cautarea se faceın timp O(1) si spatiu O(q);

I Sunt de interes algoritmii care pot obtine un timp mai bun larulare decat forta bruta, realizand un compromis spatiu-timp.

Criptografie si Securitate 4/20 ,

Algoritmi pentru calculul logaritmului discret

I Se cunosc mai multi astfel de algoritmi ımpartiti ın douacategorii:

I algoritmi generici care functioneaza ın grupuri arbitrare (i.e.orice grupuri ciclice);

I algoritmi non-generici care lucreaza ın grupuri specifice -exploateaza proprietati speciale ale anumitor grupuri

I Dintre algoritmii generici enumeram:

I Metoda Baby-step/giant-step, datorata lui Shanks,calculeaza logaritmul discret ıntr-un grup de ordin q ın timpO(√

q · (log q)c);

I Algoritmul Pohlig-Hellman poate fi folosit atunci cand secunoaste factorizarea ordinului q al grupului;

Criptografie si Securitate 5/20 ,

Algoritmi pentru calculul logaritmului discret

I Se cunosc mai multi astfel de algoritmi ımpartiti ın douacategorii:

I algoritmi generici care functioneaza ın grupuri arbitrare (i.e.orice grupuri ciclice);

I algoritmi non-generici care lucreaza ın grupuri specifice -exploateaza proprietati speciale ale anumitor grupuri

I Dintre algoritmii generici enumeram:

I Metoda Baby-step/giant-step, datorata lui Shanks,calculeaza logaritmul discret ıntr-un grup de ordin q ın timpO(√

q · (log q)c);

I Algoritmul Pohlig-Hellman poate fi folosit atunci cand secunoaste factorizarea ordinului q al grupului;

Criptografie si Securitate 5/20 ,

Algoritmi pentru calculul logaritmului discret

I Se cunosc mai multi astfel de algoritmi ımpartiti ın douacategorii:

I algoritmi generici care functioneaza ın grupuri arbitrare (i.e.orice grupuri ciclice);

I algoritmi non-generici care lucreaza ın grupuri specifice -exploateaza proprietati speciale ale anumitor grupuri

I Dintre algoritmii generici enumeram:

I Metoda Baby-step/giant-step, datorata lui Shanks,calculeaza logaritmul discret ıntr-un grup de ordin q ın timpO(√

q · (log q)c);

I Algoritmul Pohlig-Hellman poate fi folosit atunci cand secunoaste factorizarea ordinului q al grupului;

Criptografie si Securitate 5/20 ,

Algoritmi pentru calculul logaritmului discret

I Se cunosc mai multi astfel de algoritmi ımpartiti ın douacategorii:

I algoritmi generici care functioneaza ın grupuri arbitrare (i.e.orice grupuri ciclice);

I algoritmi non-generici care lucreaza ın grupuri specifice -exploateaza proprietati speciale ale anumitor grupuri

I Dintre algoritmii generici enumeram:

I Metoda Baby-step/giant-step, datorata lui Shanks,calculeaza logaritmul discret ıntr-un grup de ordin q ın timpO(√

q · (log q)c);

I Algoritmul Pohlig-Hellman poate fi folosit atunci cand secunoaste factorizarea ordinului q al grupului;

Criptografie si Securitate 5/20 ,

Algoritmi pentru calculul logaritmului discret

I Se cunosc mai multi astfel de algoritmi ımpartiti ın douacategorii:

I algoritmi generici care functioneaza ın grupuri arbitrare (i.e.orice grupuri ciclice);

I algoritmi non-generici care lucreaza ın grupuri specifice -exploateaza proprietati speciale ale anumitor grupuri

I Dintre algoritmii generici enumeram:

I Metoda Baby-step/giant-step, datorata lui Shanks,calculeaza logaritmul discret ıntr-un grup de ordin q ın timpO(√

q · (log q)c);

I Algoritmul Pohlig-Hellman poate fi folosit atunci cand secunoaste factorizarea ordinului q al grupului;

Criptografie si Securitate 5/20 ,

Algoritmi pentru calculul logaritmului discret

I Se cunosc mai multi astfel de algoritmi ımpartiti ın douacategorii:

I algoritmi generici care functioneaza ın grupuri arbitrare (i.e.orice grupuri ciclice);

I algoritmi non-generici care lucreaza ın grupuri specifice -exploateaza proprietati speciale ale anumitor grupuri

I Dintre algoritmii generici enumeram:

I Metoda Baby-step/giant-step, datorata lui Shanks,calculeaza logaritmul discret ıntr-un grup de ordin q ın timpO(√

q · (log q)c);

I Algoritmul Pohlig-Hellman poate fi folosit atunci cand secunoaste factorizarea ordinului q al grupului;

Criptografie si Securitate 5/20 ,

Algoritmi generici pentru calculul logaritmului discret

I Metoda Baby-Step/Giant-Step este optima ca timp de rulare,ınsa exista alti algoritmi mai eficienti d.p.d.v. al complexitatiispatiu;

I In cazul algoritmului Pohlig-Hellman, timpul de rulare depindefactorii primi ai lui q;

I Pentru ca algoritmul sa nu fie eficient, trebuie ca cel mai marefactor prim al lui q sa fie de ordinul 2160.

Criptografie si Securitate 6/20 ,

Algoritmi generici pentru calculul logaritmului discret

I Metoda Baby-Step/Giant-Step este optima ca timp de rulare,ınsa exista alti algoritmi mai eficienti d.p.d.v. al complexitatiispatiu;

I In cazul algoritmului Pohlig-Hellman, timpul de rulare depindefactorii primi ai lui q;

I Pentru ca algoritmul sa nu fie eficient, trebuie ca cel mai marefactor prim al lui q sa fie de ordinul 2160.

Criptografie si Securitate 6/20 ,

Algoritmi generici pentru calculul logaritmului discret

I Metoda Baby-Step/Giant-Step este optima ca timp de rulare,ınsa exista alti algoritmi mai eficienti d.p.d.v. al complexitatiispatiu;

I In cazul algoritmului Pohlig-Hellman, timpul de rulare depindefactorii primi ai lui q;

I Pentru ca algoritmul sa nu fie eficient, trebuie ca cel mai marefactor prim al lui q sa fie de ordinul 2160.

Criptografie si Securitate 6/20 ,

Algoritmi non-generici pentru calculul logaritmului discret

I Algoritmii non-generici sunt potential mai puternici decat ceigenerici;

I Cel mai cunoscut algoritm pentru PLD ın Z∗p cu p prim estealgoritmul GNFS (General Number Field Sieve) cu

complexitate timp 2O(n1/3·(log n)2/3) unde |p| = O(n);

I Exista si un alt algoritm non-generic numit metoda de calcul aindicelui care rezolva DLP ın grupuri ciclice Z∗p cu p prim ıntimp sub-expoential ın lungimea lui p.

I Aceasta metoda seamana cu algoritmul sitei patratice pentrufactorizare;

I Metoda functioneaza ın 2 etape; prima etapa este depre-procesare si necesita cunoasterea modulului p si a bazei g ;

Criptografie si Securitate 7/20 ,

Algoritmi non-generici pentru calculul logaritmului discret

I Algoritmii non-generici sunt potential mai puternici decat ceigenerici;

I Cel mai cunoscut algoritm pentru PLD ın Z∗p cu p prim estealgoritmul GNFS (General Number Field Sieve) cu

complexitate timp 2O(n1/3·(log n)2/3) unde |p| = O(n);

I Exista si un alt algoritm non-generic numit metoda de calcul aindicelui care rezolva DLP ın grupuri ciclice Z∗p cu p prim ıntimp sub-expoential ın lungimea lui p.

I Aceasta metoda seamana cu algoritmul sitei patratice pentrufactorizare;

I Metoda functioneaza ın 2 etape; prima etapa este depre-procesare si necesita cunoasterea modulului p si a bazei g ;

Criptografie si Securitate 7/20 ,

Algoritmi non-generici pentru calculul logaritmului discret

I Algoritmii non-generici sunt potential mai puternici decat ceigenerici;

I Cel mai cunoscut algoritm pentru PLD ın Z∗p cu p prim estealgoritmul GNFS (General Number Field Sieve) cu

complexitate timp 2O(n1/3·(log n)2/3) unde |p| = O(n);

I Exista si un alt algoritm non-generic numit metoda de calcul aindicelui care rezolva DLP ın grupuri ciclice Z∗p cu p prim ıntimp sub-expoential ın lungimea lui p.

I Aceasta metoda seamana cu algoritmul sitei patratice pentrufactorizare;

I Metoda functioneaza ın 2 etape; prima etapa este depre-procesare si necesita cunoasterea modulului p si a bazei g ;

Criptografie si Securitate 7/20 ,

Algoritmi non-generici pentru calculul logaritmului discret

I Algoritmii non-generici sunt potential mai puternici decat ceigenerici;

I Cel mai cunoscut algoritm pentru PLD ın Z∗p cu p prim estealgoritmul GNFS (General Number Field Sieve) cu

complexitate timp 2O(n1/3·(log n)2/3) unde |p| = O(n);

I Exista si un alt algoritm non-generic numit metoda de calcul aindicelui care rezolva DLP ın grupuri ciclice Z∗p cu p prim ıntimp sub-expoential ın lungimea lui p.

I Aceasta metoda seamana cu algoritmul sitei patratice pentrufactorizare;

I Metoda functioneaza ın 2 etape; prima etapa este depre-procesare si necesita cunoasterea modulului p si a bazei g ;

Criptografie si Securitate 7/20 ,

Algoritmi non-generici pentru calculul logaritmului discret

I Algoritmii non-generici sunt potential mai puternici decat ceigenerici;

I Cel mai cunoscut algoritm pentru PLD ın Z∗p cu p prim estealgoritmul GNFS (General Number Field Sieve) cu

complexitate timp 2O(n1/3·(log n)2/3) unde |p| = O(n);

I Exista si un alt algoritm non-generic numit metoda de calcul aindicelui care rezolva DLP ın grupuri ciclice Z∗p cu p prim ıntimp sub-expoential ın lungimea lui p.

I Aceasta metoda seamana cu algoritmul sitei patratice pentrufactorizare;

I Metoda functioneaza ın 2 etape; prima etapa este depre-procesare si necesita cunoasterea modulului p si a bazei g ;

Criptografie si Securitate 7/20 ,

Metoda de calcul a indicelui

I Pasul 1. Fie q = p − 1, ordinul lui Z∗p si B = {p1, ..., pk} obaza de numere prime mici;

I Se cauta l ≥ k numere distincte x1, ..., xl ∈ Zq pentru caregi = [g xi mod p] este ”mic” asa ıncat toti factorii primi ai luigi se gasesc ın B;

I Vor rezulta relatii de forma

g xi = pei,11 · pei,2

2 · · · · · pei,kk 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 ,

Metoda de calcul a indicelui

I Pasul 1. Fie q = p − 1, ordinul lui Z∗p si B = {p1, ..., pk} obaza de numere prime mici;

I Se cauta l ≥ k numere distincte x1, ..., xl ∈ Zq pentru caregi = [g xi mod p] este ”mic” asa ıncat toti factorii primi ai luigi se gasesc ın B;

I Vor rezulta relatii de forma

g xi = pei,11 · pei,2

2 · · · · · pei,kk 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 ,

Metoda de calcul a indicelui

I Pasul 1. Fie q = p − 1, ordinul lui Z∗p si B = {p1, ..., pk} obaza de numere prime mici;

I Se cauta l ≥ k numere distincte x1, ..., xl ∈ Zq pentru caregi = [g xi mod p] este ”mic” asa ıncat toti factorii primi ai luigi se gasesc ın B;

I Vor rezulta relatii de forma

g xi = pei,11 · pei,2

2 · · · · · pei,kk 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 ,

Metoda de calcul a indicelui

I Pasul 1. Fie q = p − 1, ordinul lui Z∗p si B = {p1, ..., pk} obaza de numere prime mici;

I Se cauta l ≥ k numere distincte x1, ..., xl ∈ Zq pentru caregi = [g xi mod p] este ”mic” asa ıncat toti factorii primi ai luigi se gasesc ın B;

I Vor rezulta relatii de forma

g xi = pei,11 · pei,2

2 · · · · · pei,kk 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 ,

Metoda de calcul a indicelui

I In ecuatiile de mai sus, necunoscutele sunt valorile {loggpi}

I Pasul 2. Se da y pentru care se cauta loggy ;

I Se gaseste o valoare s ∈ Zq pentru care g s · y mod p este”mic” si poate fi factorizat peste baza B, obtinandu-se orelatie de forma

g s · y = ps11 · p

s22 · ... · p

skk mod p

I sau

s + logg y = s1 logg p1 · s2 logg p2 · ... · sk logg pk mod p − 1

unde s si si se cunosc;

Criptografie si Securitate 9/20 ,

Metoda de calcul a indicelui

I In ecuatiile de mai sus, necunoscutele sunt valorile {loggpi}

I Pasul 2. Se da y pentru care se cauta loggy ;

I Se gaseste o valoare s ∈ Zq pentru care g s · y mod p este”mic” si poate fi factorizat peste baza B, obtinandu-se orelatie de forma

g s · y = ps11 · p

s22 · ... · p

skk mod p

I sau

s + logg y = s1 logg p1 · s2 logg p2 · ... · sk logg pk mod p − 1

unde s si si se cunosc;

Criptografie si Securitate 9/20 ,

Metoda de calcul a indicelui

I In ecuatiile de mai sus, necunoscutele sunt valorile {loggpi}

I Pasul 2. Se da y pentru care se cauta loggy ;

I Se gaseste o valoare s ∈ Zq pentru care g s · y mod p este”mic” si poate fi factorizat peste baza B, obtinandu-se orelatie de forma

g s · y = ps11 · p

s22 · ... · p

skk mod p

I sau

s + logg y = s1 logg p1 · s2 logg p2 · ... · sk logg pk mod p − 1

unde s si si se cunosc;

Criptografie si Securitate 9/20 ,

Metoda de calcul a indicelui

I In ecuatiile de mai sus, necunoscutele sunt valorile {loggpi}

I Pasul 2. Se da y pentru care se cauta loggy ;

I Se gaseste o valoare s ∈ Zq pentru care g s · y mod p este”mic” si poate fi factorizat peste baza B, obtinandu-se orelatie de forma

g s · y = ps11 · p

s22 · ... · p

skk mod p

I sau

s + logg y = s1 logg p1 · s2 logg p2 · ... · sk logg pk mod p − 1

unde s si si se cunosc;

Criptografie si Securitate 9/20 ,

Metoda de calcul a indicelui

I In combinatie cu ecuatiile din slide-ul anterior, sunt ın totall + 1 ≥ k + 1 ecuatii liniare ın k + 1 necunoscute loggpi ,pentru i = 1, ..., k si loggy .

I O varianta optimizata a acestei metode ruleaza ın timp2O(√n·log n) pentru un grup Z∗p cu p prim de lungime n.

I Algoritmul este sub-exponential ın lungimea lui p.

Criptografie si Securitate 10/20 ,

Metoda de calcul a indicelui

I In combinatie cu ecuatiile din slide-ul anterior, sunt ın totall + 1 ≥ k + 1 ecuatii liniare ın k + 1 necunoscute loggpi ,pentru i = 1, ..., k si loggy .

I O varianta optimizata a acestei metode ruleaza ın timp2O(√n·log n) pentru un grup Z∗p cu p prim de lungime n.

I Algoritmul este sub-exponential ın lungimea lui p.

Criptografie si Securitate 10/20 ,

Metoda de calcul a indicelui

I In combinatie cu ecuatiile din slide-ul anterior, sunt ın totall + 1 ≥ k + 1 ecuatii liniare ın k + 1 necunoscute loggpi ,pentru i = 1, ..., k si loggy .

I O varianta optimizata a acestei metode ruleaza ın timp2O(√n·log n) pentru un grup Z∗p cu p prim de lungime n.

I Algoritmul este sub-exponential ın lungimea lui p.

Criptografie si Securitate 10/20 ,

ExempluI Fie p = 101, g = 3 si y=87. Se stie ca

310 = 65 mod 101 si 65 = 5 · 13

La fel,312 = 24 · 5 mod 101

si314 = 13 mod 101

I Prin urmare:

10 = log35 + log313 mod 100

12 = 4 · log32 + log35 mod 100

14 = log313 mod 100

I Baza de numere prime mici este:

B = {2, 5, 13}

Criptografie si Securitate 11/20 ,

ExempluI Fie p = 101, g = 3 si y=87. Se stie ca

310 = 65 mod 101 si 65 = 5 · 13

La fel,312 = 24 · 5 mod 101

si314 = 13 mod 101

I Prin urmare:

10 = log35 + log313 mod 100

12 = 4 · log32 + log35 mod 100

14 = log313 mod 100

I Baza de numere prime mici este:

B = {2, 5, 13}

Criptografie si Securitate 11/20 ,

ExempluI Fie p = 101, g = 3 si y=87. Se stie ca

310 = 65 mod 101 si 65 = 5 · 13

La fel,312 = 24 · 5 mod 101

si314 = 13 mod 101

I Prin urmare:

10 = log35 + log313 mod 100

12 = 4 · log32 + log35 mod 100

14 = log313 mod 100

I Baza de numere prime mici este:

B = {2, 5, 13}

Criptografie si Securitate 11/20 ,

Metoda de calcul a indicelui

I De asemenea, 35 · 87 = 32 = 25 mod 101 sau

5 + log387 = 5 · log32 mod 100

I Combinand primele 3 ecuatii, rezulta ca4 · log32 = 16 mod 100;

I Aceasta relatie nu determina log32 unic dar se gasesc 4 valoriposibile: 4, 29, 54 si 79.

I Prin ıncercari, se gaseste log32 = 39, si deci log387 = 40.

Criptografie si Securitate 12/20 ,

Metoda de calcul a indicelui

I De asemenea, 35 · 87 = 32 = 25 mod 101 sau

5 + log387 = 5 · log32 mod 100

I Combinand primele 3 ecuatii, rezulta ca4 · log32 = 16 mod 100;

I Aceasta relatie nu determina log32 unic dar se gasesc 4 valoriposibile: 4, 29, 54 si 79.

I Prin ıncercari, se gaseste log32 = 39, si deci log387 = 40.

Criptografie si Securitate 12/20 ,

Metoda de calcul a indicelui

I De asemenea, 35 · 87 = 32 = 25 mod 101 sau

5 + log387 = 5 · log32 mod 100

I Combinand primele 3 ecuatii, rezulta ca4 · log32 = 16 mod 100;

I Aceasta relatie nu determina log32 unic dar se gasesc 4 valoriposibile: 4, 29, 54 si 79.

I Prin ıncercari, se gaseste log32 = 39, si deci log387 = 40.

Criptografie si Securitate 12/20 ,

Metoda de calcul a indicelui

I De asemenea, 35 · 87 = 32 = 25 mod 101 sau

5 + log387 = 5 · log32 mod 100

I Combinand primele 3 ecuatii, rezulta ca4 · log32 = 16 mod 100;

I Aceasta relatie nu determina log32 unic dar se gasesc 4 valoriposibile: 4, 29, 54 si 79.

I Prin ıncercari, se gaseste log32 = 39, si deci log387 = 40.

Criptografie si Securitate 12/20 ,

Functii hash rezistente la coliziuni

I In cadrul criptografiei simetrice, am vazut constructii euristicede functii hash rezistente la coliziuni care sunt folosite pe largın practica;

I In continuare prezentam o constructie pentru functii hashrezistente la coliziuni bazata pe PLD (prezumptia logaritmuluidiscret) ın grupuri de ordin prim;

I Cosntructia este mai putin eficienta ın practica ....

I ... ınsa arata ca e posibil a obtine rezistenta la coliziuni pebaza unor prezumptii criptografice standard si bine studiate.

Criptografie si Securitate 13/20 ,

Functii hash rezistente la coliziuni

I In cadrul criptografiei simetrice, am vazut constructii euristicede functii hash rezistente la coliziuni care sunt folosite pe largın practica;

I In continuare prezentam o constructie pentru functii hashrezistente la coliziuni bazata pe PLD (prezumptia logaritmuluidiscret) ın grupuri de ordin prim;

I Cosntructia este mai putin eficienta ın practica ....

I ... ınsa arata ca e posibil a obtine rezistenta la coliziuni pebaza unor prezumptii criptografice standard si bine studiate.

Criptografie si Securitate 13/20 ,

Functii hash rezistente la coliziuni

I In cadrul criptografiei simetrice, am vazut constructii euristicede functii hash rezistente la coliziuni care sunt folosite pe largın practica;

I In continuare prezentam o constructie pentru functii hashrezistente la coliziuni bazata pe PLD (prezumptia logaritmuluidiscret) ın grupuri de ordin prim;

I Cosntructia este mai putin eficienta ın practica ....

I ... ınsa arata ca e posibil a obtine rezistenta la coliziuni pebaza unor prezumptii criptografice standard si bine studiate.

Criptografie si Securitate 13/20 ,

Functii hash rezistente la coliziuni

I In cadrul criptografiei simetrice, am vazut constructii euristicede functii hash rezistente la coliziuni care sunt folosite pe largın practica;

I In continuare prezentam o constructie pentru functii hashrezistente la coliziuni bazata pe PLD (prezumptia logaritmuluidiscret) ın grupuri de ordin prim;

I Cosntructia este mai putin eficienta ın practica ....

I ... ınsa arata ca e posibil a obtine rezistenta la coliziuni pebaza unor prezumptii criptografice standard si bine studiate.

Criptografie si Securitate 13/20 ,

Functii hash rezistente la coliziuni

I Fie G un grup ciclic de ordin prim q (cu |q| = n) si g ungenerator al sau iar h un element aleator din G;

I Definim o functie hash H cu intrarea de lungime fixa dupacum urmeaza:

I H: pentru intrarea (x1, x2) ∈ Zq × Zq

H(x1, x2) = g x1hx2

Criptografie si Securitate 14/20 ,

Functii hash rezistente la coliziuni

I Fie G un grup ciclic de ordin prim q (cu |q| = n) si g ungenerator al sau iar h un element aleator din G;

I Definim o functie hash H cu intrarea de lungime fixa dupacum urmeaza:

I H: pentru intrarea (x1, x2) ∈ Zq × Zq

H(x1, x2) = g x1hx2

Criptografie si Securitate 14/20 ,

Functii hash rezistente la coliziuni

I Fie G un grup ciclic de ordin prim q (cu |q| = n) si g ungenerator al sau iar h un element aleator din G;

I Definim o functie hash H cu intrarea de lungime fixa dupacum urmeaza:

I H: pentru intrarea (x1, x2) ∈ Zq × Zq

H(x1, x2) = g x1hx2

Criptografie si Securitate 14/20 ,

Functii hash rezistente la coliziuni

Teorema

Daca problema logaritmului discret este dificila ın grupul G, atunciconstructia de mai sus este o functie hash de intrare fixa rezistentala coliziuni.

I Pentru demonstratie vom folosi abordarea reductionista:

I Aratam ca o constructie criptografica e sigura atata timp catproblema pe care se bazeaza e dificila, ın felul urmator:

I Prezentam o reductie explicita aratand cum putem transformaun adversar eficient A care ataca securitatea constructiei cuprobabilitate ne-neglijabila ıntr-un algoritm eficient A′ carerezolva problema dificila;

Criptografie si Securitate 15/20 ,

Functii hash rezistente la coliziuni

Teorema

Daca problema logaritmului discret este dificila ın grupul G, atunciconstructia de mai sus este o functie hash de intrare fixa rezistentala coliziuni.

I Pentru demonstratie vom folosi abordarea reductionista:

I Aratam ca o constructie criptografica e sigura atata timp catproblema pe care se bazeaza e dificila, ın felul urmator:

I Prezentam o reductie explicita aratand cum putem transformaun adversar eficient A care ataca securitatea constructiei cuprobabilitate ne-neglijabila ıntr-un algoritm eficient A′ carerezolva problema dificila;

Criptografie si Securitate 15/20 ,

Functii hash rezistente la coliziuni

Teorema

Daca problema logaritmului discret este dificila ın grupul G, atunciconstructia de mai sus este o functie hash de intrare fixa rezistentala coliziuni.

I Pentru demonstratie vom folosi abordarea reductionista:

I Aratam ca o constructie criptografica e sigura atata timp catproblema pe care se bazeaza e dificila, ın felul urmator:

I Prezentam o reductie explicita aratand cum putem transformaun adversar eficient A care ataca securitatea constructiei cuprobabilitate ne-neglijabila ıntr-un algoritm eficient A′ carerezolva problema dificila;

Criptografie si Securitate 15/20 ,

Functii hash rezistente la coliziuni

Teorema

Daca problema logaritmului discret este dificila ın grupul G, atunciconstructia de mai sus este o functie hash de intrare fixa rezistentala coliziuni.

I Pentru demonstratie vom folosi abordarea reductionista:

I Aratam ca o constructie criptografica e sigura atata timp catproblema pe care se bazeaza e dificila, ın felul urmator:

I Prezentam o reductie explicita aratand cum putem transformaun adversar eficient A care ataca securitatea constructiei cuprobabilitate ne-neglijabila ıntr-un algoritm eficient A′ carerezolva problema dificila;

Criptografie si Securitate 15/20 ,

Demonstratie

I Fie H o functie hash precum cea din constructia de mai sus siA un adversar PPT; notam cu

ε(n) = Pr [Hash − collA,H = 1]

probabilitatea ca A sa gaseasca coliziuni ın functia H;

I Aratam ca A poate fi folosit de A′ pentru a rezolva DLP cuprobabilitate de succes ε(n);

Criptografie si Securitate 16/20 ,

Demonstratie

I Fie H o functie hash precum cea din constructia de mai sus siA un adversar PPT; notam cu

ε(n) = Pr [Hash − collA,H = 1]

probabilitatea ca A sa gaseasca coliziuni ın functia H;

I Aratam ca A poate fi folosit de A′ pentru a rezolva DLP cuprobabilitate de succes ε(n);

Criptografie si Securitate 16/20 ,

Demonstratie

I Algoritmul A′ primeste la intrare s = (G, q, g , h).

1. Executa A(s) si obtine x si x ′;

2. Daca x 6= x ′ si H(x) = H(x ′) atunci

2.1 Daca h = 1 ıntoarce 0;

2.2 Altfel (h 6= 1), noteaza x = (x1, x2) si x ′ = (x ′1, x′2). Intoarce

[(x1 − x1′) · (x ′2 − x2)−1 mod q].

I Clar, A′ ruleaza ın timp polinomial;

I Verificam faptul ca daca A gaseste o coliziune, A′ ıntoarceraspunsul corect loggh:

Criptografie si Securitate 17/20 ,

Demonstratie

I Algoritmul A′ primeste la intrare s = (G, q, g , h).

1. Executa A(s) si obtine x si x ′;

2. Daca x 6= x ′ si H(x) = H(x ′) atunci

2.1 Daca h = 1 ıntoarce 0;

2.2 Altfel (h 6= 1), noteaza x = (x1, x2) si x ′ = (x ′1, x′2). Intoarce

[(x1 − x1′) · (x ′2 − x2)−1 mod q].

I Clar, A′ ruleaza ın timp polinomial;

I Verificam faptul ca daca A gaseste o coliziune, A′ ıntoarceraspunsul corect loggh:

Criptografie si Securitate 17/20 ,

Demonstratie

I Algoritmul A′ primeste la intrare s = (G, q, g , h).

1. Executa A(s) si obtine x si x ′;

2. Daca x 6= x ′ si H(x) = H(x ′) atunci

2.1 Daca h = 1 ıntoarce 0;

2.2 Altfel (h 6= 1), noteaza x = (x1, x2) si x ′ = (x ′1, x′2). Intoarce

[(x1 − x1′) · (x ′2 − x2)−1 mod q].

I Clar, A′ ruleaza ın timp polinomial;

I Verificam faptul ca daca A gaseste o coliziune, A′ ıntoarceraspunsul corect loggh:

Criptografie si Securitate 17/20 ,

Demonstratie

I Algoritmul A′ primeste la intrare s = (G, q, g , h).

1. Executa A(s) si obtine x si x ′;

2. Daca x 6= x ′ si H(x) = H(x ′) atunci

2.1 Daca h = 1 ıntoarce 0;

2.2 Altfel (h 6= 1), noteaza x = (x1, x2) si x ′ = (x ′1, x′2). Intoarce

[(x1 − x1′) · (x ′2 − x2)−1 mod q].

I Clar, A′ ruleaza ın timp polinomial;

I Verificam faptul ca daca A gaseste o coliziune, A′ ıntoarceraspunsul corect loggh:

Criptografie si Securitate 17/20 ,

Demonstratie

I Algoritmul A′ primeste la intrare s = (G, q, g , h).

1. Executa A(s) si obtine x si x ′;

2. Daca x 6= x ′ si H(x) = H(x ′) atunci

2.1 Daca h = 1 ıntoarce 0;

2.2 Altfel (h 6= 1), noteaza x = (x1, x2) si x ′ = (x ′1, x′2). Intoarce

[(x1 − x1′) · (x ′2 − x2)−1 mod q].

I Clar, A′ ruleaza ın timp polinomial;

I Verificam faptul ca daca A gaseste o coliziune, A′ ıntoarceraspunsul corect loggh:

Criptografie si Securitate 17/20 ,

Demonstratie

I Algoritmul A′ primeste la intrare s = (G, q, g , h).

1. Executa A(s) si obtine x si x ′;

2. Daca x 6= x ′ si H(x) = H(x ′) atunci

2.1 Daca h = 1 ıntoarce 0;

2.2 Altfel (h 6= 1), noteaza x = (x1, x2) si x ′ = (x ′1, x′2). Intoarce

[(x1 − x1′) · (x ′2 − x2)−1 mod q].

I Clar, A′ ruleaza ın timp polinomial;

I Verificam faptul ca daca A gaseste o coliziune, A′ ıntoarceraspunsul corect loggh:

Criptografie si Securitate 17/20 ,

Demonstratie

I Algoritmul A′ primeste la intrare s = (G, q, g , h).

1. Executa A(s) si obtine x si x ′;

2. Daca x 6= x ′ si H(x) = H(x ′) atunci

2.1 Daca h = 1 ıntoarce 0;

2.2 Altfel (h 6= 1), noteaza x = (x1, x2) si x ′ = (x ′1, x′2). Intoarce

[(x1 − x1′) · (x ′2 − x2)−1 mod q].

I Clar, A′ ruleaza ın timp polinomial;

I Verificam faptul ca daca A gaseste o coliziune, A′ ıntoarceraspunsul corect loggh:

Criptografie si Securitate 17/20 ,

Demonstratie

I Daca h = 1, atunci raspunsul lui A′ este corect pentru caloggh = 0;

I Altfel, existenta unei coliziuni implica:

H(x1, x2) = H(x ′1, x′2)⇒ g x1hx2 = g x ′1hx ′2

⇒ g x1−x ′1 = hx ′2−x2

I Notam ∆ = x ′2 − x2.

I Observam ca ∆ 6= 0 mod q. De ce?

I Pentru ca ar ınsemna ca [(x1 − x ′1) mod q] = 0 si decix = (x1, x2) = (x ′1, x

′2) = x ′, contradictie cu x 6= x ′;

Criptografie si Securitate 18/20 ,

Demonstratie

I Daca h = 1, atunci raspunsul lui A′ este corect pentru caloggh = 0;

I Altfel, existenta unei coliziuni implica:

H(x1, x2) = H(x ′1, x′2)⇒ g x1hx2 = g x ′1hx ′2

⇒ g x1−x ′1 = hx ′2−x2

I Notam ∆ = x ′2 − x2.

I Observam ca ∆ 6= 0 mod q. De ce?

I Pentru ca ar ınsemna ca [(x1 − x ′1) mod q] = 0 si decix = (x1, x2) = (x ′1, x

′2) = x ′, contradictie cu x 6= x ′;

Criptografie si Securitate 18/20 ,

Demonstratie

I Daca h = 1, atunci raspunsul lui A′ este corect pentru caloggh = 0;

I Altfel, existenta unei coliziuni implica:

H(x1, x2) = H(x ′1, x′2)⇒ g x1hx2 = g x ′1hx ′2

⇒ g x1−x ′1 = hx ′2−x2

I Notam ∆ = x ′2 − x2.

I Observam ca ∆ 6= 0 mod q. De ce?

I Pentru ca ar ınsemna ca [(x1 − x ′1) mod q] = 0 si decix = (x1, x2) = (x ′1, x

′2) = x ′, contradictie cu x 6= x ′;

Criptografie si Securitate 18/20 ,

Demonstratie

I Daca h = 1, atunci raspunsul lui A′ este corect pentru caloggh = 0;

I Altfel, existenta unei coliziuni implica:

H(x1, x2) = H(x ′1, x′2)⇒ g x1hx2 = g x ′1hx ′2

⇒ g x1−x ′1 = hx ′2−x2

I Notam ∆ = x ′2 − x2.

I Observam ca ∆ 6= 0 mod q. De ce?

I Pentru ca ar ınsemna ca [(x1 − x ′1) mod q] = 0 si decix = (x1, x2) = (x ′1, x

′2) = x ′, contradictie cu x 6= x ′;

Criptografie si Securitate 18/20 ,

Demonstratie

I Daca h = 1, atunci raspunsul lui A′ este corect pentru caloggh = 0;

I Altfel, existenta unei coliziuni implica:

H(x1, x2) = H(x ′1, x′2)⇒ g x1hx2 = g x ′1hx ′2

⇒ g x1−x ′1 = hx ′2−x2

I Notam ∆ = x ′2 − x2.

I Observam ca ∆ 6= 0 mod q. De ce?

I Pentru ca ar ınsemna ca [(x1 − x ′1) mod q] = 0 si decix = (x1, x2) = (x ′1, x

′2) = x ′, contradictie cu x 6= x ′;

Criptografie si Securitate 18/20 ,

Demonstratie

I Cum q-prim si ∆ 6= 0 mod q atunci inversul [∆−1 mod q]exista;

I Decig (x1−x ′1)·∆−1

= (hx ′2−x2)∆−1 mod q = h∆·∆−1 mod q = h

I rezulta caloggh = [(x1−x ′1)·∆−1 mod q] = [(x1−x ′1)·(x2−x ′2)−1 mod q]

I Observam ca A′ rezolva DLP corect cu probabilitate exactε(n)

I Cum DLP este dificila din ipoteza, concluzionam ca ε(n) esteneglijabila.

Criptografie si Securitate 19/20 ,

Demonstratie

I Cum q-prim si ∆ 6= 0 mod q atunci inversul [∆−1 mod q]exista;

I Decig (x1−x ′1)·∆−1

= (hx ′2−x2)∆−1 mod q = h∆·∆−1 mod q = h

I rezulta caloggh = [(x1−x ′1)·∆−1 mod q] = [(x1−x ′1)·(x2−x ′2)−1 mod q]

I Observam ca A′ rezolva DLP corect cu probabilitate exactε(n)

I Cum DLP este dificila din ipoteza, concluzionam ca ε(n) esteneglijabila.

Criptografie si Securitate 19/20 ,

Demonstratie

I Cum q-prim si ∆ 6= 0 mod q atunci inversul [∆−1 mod q]exista;

I Decig (x1−x ′1)·∆−1

= (hx ′2−x2)∆−1 mod q = h∆·∆−1 mod q = h

I rezulta caloggh = [(x1−x ′1)·∆−1 mod q] = [(x1−x ′1)·(x2−x ′2)−1 mod q]

I Observam ca A′ rezolva DLP corect cu probabilitate exactε(n)

I Cum DLP este dificila din ipoteza, concluzionam ca ε(n) esteneglijabila.

Criptografie si Securitate 19/20 ,

Demonstratie

I Cum q-prim si ∆ 6= 0 mod q atunci inversul [∆−1 mod q]exista;

I Decig (x1−x ′1)·∆−1

= (hx ′2−x2)∆−1 mod q = h∆·∆−1 mod q = h

I rezulta caloggh = [(x1−x ′1)·∆−1 mod q] = [(x1−x ′1)·(x2−x ′2)−1 mod q]

I Observam ca A′ rezolva DLP corect cu probabilitate exactε(n)

I Cum DLP este dificila din ipoteza, concluzionam ca ε(n) esteneglijabila.

Criptografie si Securitate 19/20 ,

Demonstratie

I Cum q-prim si ∆ 6= 0 mod q atunci inversul [∆−1 mod q]exista;

I Decig (x1−x ′1)·∆−1

= (hx ′2−x2)∆−1 mod q = h∆·∆−1 mod q = h

I rezulta caloggh = [(x1−x ′1)·∆−1 mod q] = [(x1−x ′1)·(x2−x ′2)−1 mod q]

I Observam ca A′ rezolva DLP corect cu probabilitate exactε(n)

I Cum DLP este dificila din ipoteza, concluzionam ca ε(n) esteneglijabila.

Criptografie si Securitate 19/20 ,

Important de retinut!

I Cel mai bun algoritm pentru DLP este sub-exponential;

I Se pot construi functii hash rezistente la coliziuni bazate pedificultatea DLP;

Criptografie si Securitate 20/20 ,