crypto_c_17

riptografie si Securitate

- Prelegerea 17 -Prezumptii criptografice dificile

Adela Georgescu, Ruxandra F. Olimid

Facultatea de Matematica si InformaticaUniversitatea din Bucuresti

Cuprins

1. Numere prime si factorizare

2. Problema logaritmului discret

Criptografie si Securitate 2/29 ,

Prezumptii criptografice dificile Criptografia moderna se bazeaza pe prezumptia ca anumite

probleme nu pot fi rezolvate n timp polinomial;

Pana acum am vazut ca schemele de criptare si deautentificare se bazeaza pe prezumptia existentei permutarilorpseudoaleatoare;

Dar aceasta prezumptie e nenaturala si foarte puternica;

In practica, PRF si PRP pot fi instantiate cu cifruri bloc;

Insa metode pentru a demonstra pseudoaleatorismulconstructiilor practice relativ la alte prezumptii mairezonabile nu se cunosc;

Dar e posibil a demonstra existenta permutarilorpseudoaleatoare pe baza unei prezumptii mult mai slabe, ceaa existentei functiilor one-way;


Prezumptii criptografice dificile

In continuare vom introduce cateva probleme consideratedificile si vom prezenta functii conjecturate ca fiind one-waybazate pe aceste probleme;

Tot materialul ce urmeaza se bazeaza pe notiuni de teorianumerelor;

La criptografia simetrica (cu cheie secreta) am vazut primitvecriptografice (i.e. functii hash, PRG, PRF, PRP) care pot ficonstruite eficient fara a implica teoria numerelor;

La criptografia asimetrica (cu cheie publica) constructiilecunoscute se bazeaza pe probleme matematice dificile dinteoria numerelor;


Primalitate si factorizare

O prima problema conjecturata ca fiind dificila este problemafactorizarii numerelor ntregi sau mai simplu problemafactorizarii;

Fiind dat un numar compus N, problema cere sa se gaseascadoua numere prime x1 si x2 pe n biti asa ncat N = x1 x2;

Cele mai greu de factorizat sunt numerele cele care au factoriprimi foarte mari.


Primalitate si factorizare

The problem of distinguishing prime numbers from composite numbers

and of resolving the latter into their prime factors is known to be one of

the most important and useful in arithmetic. It has engaged the industry

and wisdom of ancient and modern geometers to such an extent that it

would be superfluous to discuss the problem at length... The dignity of

the science itself seems to require that every possible means be explored

for the solution of a problem so elegant and so celebrated.

(C.F.Gauss 1777 1855)


Generarea numerelor prime

Pentru a putea folosi problema n criptografie, trebuie sageneram numere prime aleatoare n mod eficient;

Putem genera un numar prim aleator pe n biti prin alegerearepetata de numere aleatoare pe n biti pana cand gasim unulprim;

Pentru eficienta, ne intereseaza doua aspecte:

1. probabilitatea ca un numar aleator de n biti sa fie prim;

2. cum testam eficient ca un numar dat p este prim.


Generarea numerelor prime

Pentru distributia numerelor prime, se cunoaste urmatorulrezultat matematic:

Teorema

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

Rezulta imediat ca probabilitatea ca un numar ales aleator pen biti sa fie prim este cel putin c/n;

Iar daca testam t = n2/c numere, probabilitatea ca un numarprim sa nu fie ales este (1 c/n)t , adica cel mult en, decineglijabila.


Testarea primalitatii

Cei mai eficienti algoritmi sunt probabilisti:

Daca numarul p dat este prim atunci algoritmul ntotdeaunantoarce rezultatul prim;

Daca p este compus, atunci cu probabilitate mare algoritmulva ntoarce compus;

Concluzie: daca outputul este compus, atunci p sigur estecompus, daca outputul este prim, atunci cu probabilitate marep este prim dar este posibil si sa se fi produs o eroare;

Un algoritm determinist polinomial a fost propus n 2002, dareste mai lent decat algoritmii probabilisti;

Prezentam un algoritm probabilist foarte raspandit:Miller-Rabin.


Testarea primalitatii

Algorithm 1 Algoritmul Miller-Rabin

Input: N , tOutput: o decizie daca N este compus sau nu1: if N este par sau N = N1

2 then

2: return compus3: end if

4: compute r 1 si u impar a.. N 1 = 2ru5: for j = 1 to t do6: a {1, ...,N 1}7: if (gcd(a,N) 6= 1) or (au 6= 1 mod N and a2iu 6= 1 mod

N, pentru orice i {1, ..., r 1}) then8: return compus9: end if

10: end for

11: return prim


Algoritmul Miller-Rabin

Accepta la intrare un numar N si un parametru t caredetermina probabilitatea de eroare;

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

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


Algoritmul Miller-Rabin

Ne ntoarcem la problema generarii eficiente a numerelorprime;

Folosim algoritmul Miller-Rabin pentru a descrie un algoritmpolinomial de generare a numerelor prime;

Pentru o intrare n, ntoarce un numar aleator pe n biti careeste prim cu exceptia unei probabilitati neglijabile n n.


Algoritmul de generare a numerelor prime

Algorithm 2 Algoritmul de generare a numerelor prime

Input: nOutput: Un numar aleator prim pe n biti1: for i = 1 to n2/c do2: p {0, 1}n13: p = 1||p4: executa testul Miller-Rabin pentru p cu parametrul n5: if output = prim then6: return p7: end if

8: end for

9: return esec


Algoritmi de factorizare

Deocamdata nu se cunosc algoritmi polinomiali pentruproblema factorizarii;

Dar exista algoritmi mult mai buni decat forta bruta;

Prezentam n continuare cativa algoritmi de factorizare.



Reamintim: Fiind dat un numar compus N, problemafactorizarii cere sa se gaseasca 2 numere prime p si q a..N = pq;

Consideram |p| = |q| = n si deci n = O(logN); Metoda cea mai simpla este mpartirea numarului N prin toate

numerele p impare din intervalul p = 3, ...,

N.

Complexitatea timp este O(N (logN)c) unde c este o

constanta;

Pentru N < 1012 metoda este destul de eficienta.



Exista nsa algoritmi mai sofisticati, cu timp de executie maibun, ntre care:

Metoda Pollard p 1: functioneaza atunci cand p 1 arefactori primi mici;

Metoda Pollard rho: timpul de executie esteO(N1/4 (logN)c);

Algoritmul sitei patratice - ruleaza n timp sub-exponentialn lungimea lui N.

Deocamdata, cel mai rapid algoritm de factorizare este ombunatatire a sitei patratice care factorizeaza un numar N delungime O(n) n timp 2O(n

1/3(log n)2/3).


Algoritmul sitei patratice

Un element y Zp este rest patratic modulo p daca x Zpa..

x2 = y mod p

x se numeste radacina patratica a lui y;

Algoritmul se bazeaza pe doua observatii simple:

1. Daca N = pq cu p, q prime distincte, atunci fiecare restpatratic modulo N are exact 4 radacini patratice diferite;

2. Daca se pot afla x , y cu x2 = y2 mod N si x 6= y mod N,atunci gcd(x y ,N) este un factor prim al lui N calculabil ntimp polinomial;



Algoritmul ncearca sa genereze o pereche de valori x , y a..x2 = y2 mod N, n speranta ca x 6= y mod N cuprobabilitate constanta; cautarea se desfasoara astfel:

Se fixeaza o baza B = {p1, ..., pk} de numere prime mici; Se cauta l > k numere distincte x1, ..., xl ZN pentru care

qi = [x2i mod N] este mic asa ncat toti factorii primi ai lui

qi se gasesc n B ;

Vor rezulta relatii de forma

x2j = pej,11 p

ej,22 p

ej,kk mod N

unde 1 j k .



Pentru fiecare j se considera vectorul:ej = (ej ,1 mod 2, ..., ej ,k mod 2)

Daca se poate determina o submultime formata din astfel devectori, a caror suma modulo 2 sa fie (0,0,...,0), atuncipatratul produsului elementelor xj corespunzatoare va avea nB toti divizorii reprezentati de un numar par de ori.

Se poate arata ca algoritmul optimizat ruleaza n timp2O(

nlogn) pentru factorizarea unui numar N de lungime

O(n), deci sub-exponential n lungimea lui N.


Exemplu

Fie N = 377753. Se stie ca 6647 = [6202 mod N] si putemfactoriza

6647 = 172 23 Deci:

6202 = 172 23 mod N Similar:

6212 = 24 17 29 mod N6452 = 27 13 23 mod N

6552 = 23 13 27 29 mod N Baza de numere prime mici este:

B = {2, 13, 17, 23, 29}


Exemplu

Obtinem:

6202 6212 6452 6552 = 214 132 174 232 292 mod N[620 621 645 655 mod N]2 = [27 13 172 23 29 mod N]2 mod N

Toti exponentii sunt pari!

Dupa efectuarea calculelor:

1271942 = 453352 mod N Cum 127194 6= 45335 mod N, se calculeaza un factor prim al

lui N:gcd(127194 45335, 377753) = 751


RSA Challenge

In 1991, Laboratoarele RSA lanseaza RSA Challenge;

Aceasta presupune factorizarea unor numere N, undeN = p q, cu p, q 2 numere prime mari;

Au fost lansate mai multe provocari, cate 1 pentru fiecaredimensiune (n biti) a lui N:

Exemple includ: RSA-576, RSA-640, RSA-768, ,RSA-1024, RSA-1536, RSA-2048;

Provocarea s-a ncheiat oficial n 2007;

Multe provocari au fost sparte n cursul anilor (chiar si ulteriornchiderii oficiale), nsa exista numere nca nefactorizate:


RSA Challenge

RSA-1024

135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563

[http://www.emc.com/emc-plus/rsa-labs/historical/

the-rsa-challenge-numbers.htm]


RSA Challenge

RSA-2048

25195908475657893494027183240048398571429282126204032027777137836043662020707595556264018525880784406918290641249515082189298559149176184502808489120072844992687392807287776735971418347270261896375014971824691165077613379859095700097330459748808428401797429100642458691817195118746121515172654632282216869987549182422433637259085141865462043576798423387184774447920739934236584823824281198163815010674810451660377306056201619676256133844143603833904414952634432190114657544454178424020924616515723350778707749817125772467962926386356373289912154831438167899885040445364023527381951378636564391212010397122822120720357

[http://www.emc.com/emc-plus/rsa-labs/historical/

the-rsa-challenge-numbers.htm]


Prezumptia logaritmului discret

O alta prezumtie dificila este DLP (Discrete LogarithmProblem) (sau PLD (Problema Logaritmului Discret));

Consideram G un grup ciclic de ordin q;

Exista un generator g G a.. G = {g0, g1, ..., gq1}; Echivalent, pentru fiecare h G exista un unic x Zq a..

g x = h;

x se numeste logaritmul discret al lui h n raport cu g si senoteaza

x = logg h


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.

2. Alege h R G. (se poate alege x 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 dacapentru orice algoritm PPT A exista o functie neglijabila negl asancat

Pr [DLogA(n) = 1] negl(n)


Grupuri ciclice de ordin prim

Exista cateva clase de grupuri ciclice pentru care DLP esteconsiderata dificila;

Una dintre ele este clasa grupurilor ciclice de ordin prim (naceste grupuri, problema este cea mai dificila);

DLP nu poate fi rezolvata n timp polinomial n grupurile carenu sunt de ordin prim, ci doar este mai usoara;

In aceste grupuri cautarea unui generator si verificarea ca unnumar dat este generator sunt triviale.


Lucrul n Zp 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 luiZp;

Reamintim: Un element y Zp este rest patratic modulo pdaca x Zp a.. x2 = y mod p;

Multimea resturilor patratice modulo p formeaza un subgrupal 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 esteciclic si toate elementele sunt generatori.


Important de retinut!

Cel mai rapid algoritm de factorizare necesita timpsub-exponential;

Problema logaritmului discret este dificila.


Date post:	08-Nov-2015
Category:	Documents
Upload:	cristi
View:	3 times
Download:	1 times

crypto_c_17

Documents