sisteme de criptare

8/7/2019 sisteme de criptare

1/20

Sisteme de criptare cu cheie publica Sistemul RSA Sistemul El-Gamal Exercitii propuse

Sisteme de criptare cu cheie publica

Luciana Morogan

Facultatea de Matematica-InformaticaUniversitatea Spiru Haret

Laborator


2/20


Outline

1 Sisteme de criptare cu cheie publica

Generalitati

Securitatea

2 Sistemul RSA

RSA

3 Sistemul El-Gamal

El-Gamal

4 Exercitii propuse

Exercitii propuse


3/20


Generalitati

Idei de baza

Regula de criptare ek poate fi pulicata intr-un registru public.

Alice (sau orice alta persoana) poate trimite lui Bob un mesaj

criptat cu ek, fara a intra in prealabil in contact, iar Bob este

singurul capabil sa descifreze textul, utilizand cheia sa secreta

de decriptare dk.


4/20


Generalitati

Cele mai cunoscute sisteme cu cheie publica

Sistemul RSA - bazat pe dificultatea descompunerii infactori primi a numerelor mari (de sute de cifre); cel mai

larg utilizat in acest moment

Sistemul El-Gamal - bazat pe dificultatea calculului

logarimului discret intr-un corp finitSistemul Merkle-Hellman - primul sistem definit cu cheie

publica, bazat pe problema {0, 1} a rucsacului (problemaNP-completa1)

Sistemul McEliece - bazat pe teoria algebrica a codurilor

(decodificarea unui cod linear este o problemaNP-completa)

Curbe eliptice - sistem ce isi desfasoara calculele pe

multimea punctelor unei curbe eliptice1

Daca problema se reduce la o problema nepolinomiala elementara(NP-tare). De exemplu: 2n, en, aa

n

s.a.


5/20


Generalitati

Functii neinversabile (1)

ExempleStrazile cu sens unic dintr-un oras

A B

B A imposibil

desi este usor sa parcurgi drumul A B, este imposibil sa te intorci

B A (decriptarea)

Cartea de telefon a unui oras mare

Este usor de gasit numarul de telefon al unei persoane si foarte greu

(imposibil) de aflat persoana care are un anumit numar de telefon.

Criptarea. Pentru fiecare litera a textului clar se alege un nume care

incepe cu acelasi caracter, iar numarul de telefon al persoanei

reprezinta criptarea (doua aparitii ale aceleiasi litere pot fi codificate

diferit)

Decriptarea. Bob detine cartea de teleon scrisa in ordine

crescatoare/descrescatoare a numerelor de telefon

S S S S G


6/20


Generalitati

Functii neinversabile (2)

O functie neinversabila trebuie sa verifice conditiile:

fiind dat x, f(x) este usor de calculat

calculul lui x din f(x) este imposibil

D. p. d. v. matematic nu se cunosc astfel de functii si deci o

problema este:

usoara - daca se poate rezolva cu un algoritm polinomial

cel mult linear

grea - daca se poate rezolva cu un algoritm polinomialnelinear

imposibila - daca este NP-completa

Si t d i t h i bli Si t l RSA Si t l El G l E itii


7/20


Generalitati

Trapa secreta

Bob trebuie sa dispuna de un procedeu care sa-i permita sa

transforme o problema NP-completa in una usoara.

procedeu numit trapa secreta

Exemplu

In exemplul cu cartea de telefon, trapa secreta este

reprezentata de cartea de telefon ordonata dupa numere si nu

dupa abonati.

Sisteme de criptare cu cheie publica Sistemul RSA Sistemul El Gamal Exercitii propuse


8/20


Generalitati

Principii generale de constructie a unui sistem de criptare cu cheie

publica

Se incepe cu o problema P dificila a carei rezolvare, in

termeni de complexitate, este imposibila (nu exista nici un

algoritm de complitate polinomiala care sa rezolve P)

Se alege P1 o subproblema a lui P rezolvabila in timp

polinomial (preferabil linear)

Lui P1 i se aplica o transformare si se obtine P2 care sa nu

semene cu P1, dar sa fie apropiata P

Se face publica P2 si se descrie algoritmul de criptare

bazat pe aceasta. Trapa secreta: modul in care se obtineP1 din P2Se construiesc detaliile de criptare a.i. destinatarul sa

poata folosi trapa secreta si sa rezolve P1, iar criptanalistul

sa trebuiasca sa rezolve P2, imposibila datorita asemanarii

acesteia cu P



9/20


Securitatea

Atacuri (1)

Daca criptanalistul Oscar dispune de un text criptat y,atunci el poate cauta un text clar x a.i. ek(x) = y

Raspundeti la intrebarea ce modalitate de aparare

considerati a fi posibila in acest caz?



10/20


Securitatea

Atacuri (1) - raspuns

Raspuns: gradul de complexitate al sistemului



11/20


Securitatea

Atacuri (2)

Meet - in - the middle

Presupunem ipoteza in care Alice si Bob vor sa stabileasca

intre ei o legatura (un contact)

cei doi vor face publice cheile lor de criptare eA si eB

daca contactul este nepersonalizat, aunci Oscar poatecontrola mesajele schimbate intre cei doi:

Oscar opacizaza cele doua chei de criptare si trimite luiAlice ceia e1B ca venind dpartea lui Bob. La fel procedeazade cealalta parte substituind eA cu e

1A

daca consideram m mesajul pe care Alice doreste sa-ltrimita lui Bob, atunci aceasta codifica pe m si trimitey1 = e

1B(m)

Oscar intercepteaza mesajul si afla m = d1B(y1)Oscar recripteaza y = eB(m) si trmite y lui Bob (Oscarpoate intarzia sau modifica mesajul)

CE CONCLUZII TRAGETI DE AICI?



12/20


Securitatea

Atacuri (2) - raspuns

Apare necesitatea:

autentificarii mesajului sau expeditorului - autentificarea::

procesul princare un calculator (program sau alt uilizator)

incearca sa confirme destinatarului ca mesajul primit deacesta provine sau nu din partea sa

confidentialtatea:: asigura accesul la informatie doar

partilor autorizate

integritatea:: siguranta ca datele la care se refera unutilizator pot fi accesate si modificate doar de catre cei

autorizati



13/20

p p p p

RSA

Algoritm

RSA:: Rivest-Shamir-Adleman

p, q numere prime impare, p= q si n= pq

(n) = (p 1)(q 1) indicatorul lui Eulerfie P= C =Zn, definimK= {(n, p, q, a, b)|n = pq, ab 1(mod(n))}

pentru k = (n, p, q, a, b),x, y Zn avem

ek(x) = xb(mod n)

dk(y) = ya(mod n)

valorile n, b sunt publice; p, q, asunt secrete



14/20

p p p p

RSA

Securitatea si trapa secreta

Securitatea

Se bazeaza pe ipoteza ca ek(x) = xb (mod n) este

neinversabila d.p.d.v al complexitatii.

Pentru ca sistemul sa fie sigur, trebuie ca n sa fie suficient

de mare pentru ca factorizarea acestuia sa fie imposibila( (n) imposibil a imposibil)

Trapa secreta

Descompunerea lui n= pqse calculeaza (n) = (p 1)(q 1)

se determina exponentul de decriptare afolosind

algoritmul lui Euclid extins (pentru aflarea cmmdc-ului si a

inversului intr-un inel Zn

)



15/20

RSA

Implementarea

Decriptare

Bob trebuie sa urmareasca pasii:

genereaza numerele prime mari p si q

calculeaza n = pq si (n) = (p 1)(q 1)

alege aleator un b, 1 < b < (n) a.i. (b, (n)) = 1

calculeaza a= b1(mod(n)) folosind algoritmul lui Euclid

face publice n si b



16/20

El-Gamal

Problema logaritmului discret

p - prim, , Zp, = 0

a=?, a Zp1 a.i. a (mod p)

a, dc exista, este unic si a= log

Obs! Pentru problema logaritmilor discreti nu este obligatoriu ca p sa fie

numar prim, important este ca sa fie radacina primitiva de ordinul p 1 a

unitatii (i, 0 < i< p 1, i 1 (mod p))

Teorma lui Fermat. p1 1 (mod p)

Obs! Cum logritmul discret este dificil de calculat iar operatia inversa

(exponentierea) este simpla, trebuie utilizata problema logaritmului discret

dificila in Zp:

p - minim 512 biti (1024 pt securitate pe termen lung)

p 1 - are cel putin un divizor prim mare

Pentru alegerea convenabila a lui p, problema este NP-completa.



17/20

El-Gamal

El-Gamal

Algoritmp - prim a.i. problema logaritmilor discreti sa fie dificila in

Zp si Z

p primitiv

P= Zp, C= Z

p Z

p

K= {(p, , a, )| a

(modp)}valorile p, , - publice, iar a- secreta

pt K = (p, , a, ) si k Zp1 aleator(secret) definim:eK(x, k) = (y1, y2) unde

y1 = k(mod p)

y2 = x k(mod p)

pt y1, y2 Z

p definim dK(y1, y2) = y2 (ya1 )1 (mod p)

Sistemul este nedeterminist: criptarea depinde de x si o

variabila aleatoare k aleasa de Alice exista mai multe texte

criptate corespunzatoare unui anumit text clar.



18/20

El-Gamal

Observatii

Dezavantaj: dublarea lungimii textului criptat comparativ cu

lungimea textului clar

Daca (y1, y2), (z1, z2) sunt textele criptare ale mesajelorm1, respectiv m2, atunci se deduce textul criptat pentrum1m2 ca fiind (y1z1, y2z2)

criptarea pentru 2m1 (respectiv 2m2) conduce la concluziaca sistemul El-Gamal este sensibil la atacul cu text clar ales

ESENTIAL: doua texte diferite ce vor fi criptate trebuie safoloseasca valori diferite pentru k



19/20

Exercitii propuse

Sistemul RSA

Ex. 1

Fie d exponentul de decriptare al

sistemului de criptare RSA construit

cu numerele prime p = 3,q = 5. Dacaexponentul de criptare este e = 7,determinati d.

Ex. 2

Fie d = 11 exponentul de decriptare alsistemului de criptare RSA construit

cu numerele prime p = 7, q = 11.Determinati exponentul de criptare e.

Ex. 3

Consideram sistemul de criptare RSA

construit cu numerele prime

p = 3, q = 5. Daca exponentul decriptare este e = 4 si se dorestecodificarea textului clar m = 11,determinati textul criptat c.

Ex. 4

Un utilizator al sistemului de criptare

RSA are ca cheie publica

(n, e) = (35, 5) si cheia secreta d = 5.Daca primeste textul criptat c = 3,atunci textul clar decodificat de

utilizator este ...



20/20

Exercitii propuse

Sistemul El-Gamal

Ex. 1

Fie cifrul El-Gamal asociat numarului prim p = 7 si radaciniiprimitive = 5. Cheia secreta a lui Alice este 3, iar cea a lui

Bob este 4. Daca Bob codifica textul clar x = 11 si il transmitelui Alice, atunci aceasta primeste codificarea...

Ex. 2

Fie cifrul El-Gamal asociat numarului prim p = 11 si radaciniiprimitive = 5. Cheia secreta a lui Alice este 4, iar cea a luiBob este 7. Alice primeste de la Bob textul criptat (3,7) pe care

il decodifica si gaseste mesajul clar ...

sisteme de criptare

Documents

Transcript of sisteme de criptare