riptografie si Securitate

- Prelegerea 16 -Criptografia asimetrica

Adela Georgescu, Ruxandra F. Olimid

Facultatea de Matematica si InformaticaUniversitatea din Bucuresti

Cuprins

1. Limitarile criptografiei simetrice

2. Criptografia asimetrica

Criptografie si Securitate 2/20 ,

Limitarile criptografiei simetrice

I Am studiat pana acum criptografia simetrica;

I Aceasta asigura confidentialitatea si integritatea mesajelortransmise pe canale nesecurizate;

I Insa raman multe probleme nerezolvate...

Criptografie si Securitate 3/20 ,

Limitarile criptografiei simetrice

I Am studiat pana acum criptografia simetrica;

I Aceasta asigura confidentialitatea si integritatea mesajelortransmise pe canale nesecurizate;

I Insa raman multe probleme nerezolvate...

Criptografie si Securitate 3/20 ,

Limitarile criptografiei simetrice

I Am studiat pana acum criptografia simetrica;

I Aceasta asigura confidentialitatea si integritatea mesajelortransmise pe canale nesecurizate;

I Insa raman multe probleme nerezolvate...

Criptografie si Securitate 3/20 ,

Problema 1 - Distribuirea cheilor

I Criptarea simetrica necesita o cheie secreta comuna partilorcomunicante;

I Intrebare: Cum se obtin si se distribuie aceste chei?

I Varianta 1. Se transmit printr-un canal de comunicatienesecurizat;

I NU! Un adversar pasiv le poate intercepta si utiliza ulteriorpentru decriptarea comunicatiei.

Criptografie si Securitate 4/20 ,

Problema 1 - Distribuirea cheilor

I Criptarea simetrica necesita o cheie secreta comuna partilorcomunicante;

I Intrebare: Cum se obtin si se distribuie aceste chei?

I Varianta 1. Se transmit printr-un canal de comunicatienesecurizat;

I NU! Un adversar pasiv le poate intercepta si utiliza ulteriorpentru decriptarea comunicatiei.

Criptografie si Securitate 4/20 ,

Problema 1 - Distribuirea cheilor

I Criptarea simetrica necesita o cheie secreta comuna partilorcomunicante;

I Intrebare: Cum se obtin si se distribuie aceste chei?

I Varianta 1. Se transmit printr-un canal de comunicatienesecurizat;

I NU! Un adversar pasiv le poate intercepta si utiliza ulteriorpentru decriptarea comunicatiei.

Criptografie si Securitate 4/20 ,

Problema 1 - Distribuirea cheilor

I Criptarea simetrica necesita o cheie secreta comuna partilorcomunicante;

I Intrebare: Cum se obtin si se distribuie aceste chei?

I Varianta 1. Se transmit printr-un canal de comunicatienesecurizat;

I NU! Un adversar pasiv le poate intercepta si utiliza ulteriorpentru decriptarea comunicatiei.

Criptografie si Securitate 4/20 ,

Problema 1 - Distribuirea cheilor

I Varianta 2. Se transmit printr-un canal de comunicatie sigurcare presupune un serviciu de mesagerie de ıncredere;

I Optiunea poate fi posibila la nivel guvernamental sau militar;

I Dar nu va fi niciodata posibila ın cazul organizatiilornumeroase;

I Presupunem doar cazul ın care fiecare manager trebuie sapartajeze o cheie secreta cu fiecare subordonat;

I Problemele care apar sunt multiple: pentru fiecare nouangajat este necesara stabilirea cheilor, organizatia are sedii ınmai multe tari, ...

Criptografie si Securitate 5/20 ,

Problema 1 - Distribuirea cheilor

I Varianta 2. Se transmit printr-un canal de comunicatie sigurcare presupune un serviciu de mesagerie de ıncredere;

I Optiunea poate fi posibila la nivel guvernamental sau militar;

I Dar nu va fi niciodata posibila ın cazul organizatiilornumeroase;

I Presupunem doar cazul ın care fiecare manager trebuie sapartajeze o cheie secreta cu fiecare subordonat;

I Problemele care apar sunt multiple: pentru fiecare nouangajat este necesara stabilirea cheilor, organizatia are sedii ınmai multe tari, ...

Criptografie si Securitate 5/20 ,

Problema 1 - Distribuirea cheilor

I Varianta 2. Se transmit printr-un canal de comunicatie sigurcare presupune un serviciu de mesagerie de ıncredere;

I Optiunea poate fi posibila la nivel guvernamental sau militar;

I Dar nu va fi niciodata posibila ın cazul organizatiilornumeroase;

I Presupunem doar cazul ın care fiecare manager trebuie sapartajeze o cheie secreta cu fiecare subordonat;

I Problemele care apar sunt multiple: pentru fiecare nouangajat este necesara stabilirea cheilor, organizatia are sedii ınmai multe tari, ...

Criptografie si Securitate 5/20 ,

Problema 1 - Distribuirea cheilor

I Varianta 2. Se transmit printr-un canal de comunicatie sigurcare presupune un serviciu de mesagerie de ıncredere;

I Optiunea poate fi posibila la nivel guvernamental sau militar;

I Dar nu va fi niciodata posibila ın cazul organizatiilornumeroase;

I Presupunem doar cazul ın care fiecare manager trebuie sapartajeze o cheie secreta cu fiecare subordonat;

I Problemele care apar sunt multiple: pentru fiecare nouangajat este necesara stabilirea cheilor, organizatia are sedii ınmai multe tari, ...

Criptografie si Securitate 5/20 ,

Problema 1 - Distribuirea cheilor

I Varianta 2. Se transmit printr-un canal de comunicatie sigurcare presupune un serviciu de mesagerie de ıncredere;

I Optiunea poate fi posibila la nivel guvernamental sau militar;

I Dar nu va fi niciodata posibila ın cazul organizatiilornumeroase;

I Presupunem doar cazul ın care fiecare manager trebuie sapartajeze o cheie secreta cu fiecare subordonat;

I Problemele care apar sunt multiple: pentru fiecare nouangajat este necesara stabilirea cheilor, organizatia are sedii ınmai multe tari, ...

Criptografie si Securitate 5/20 ,

Problema 2 - Stocarea secreta a cheilor

I Ramanem la exemplul anterior al unei organizatii numeroasecu N angajati;

I Intrebare: Cate chei sunt necesare pentru ca fiecare 2 angajatisa poata comunica criptat?

I Raspuns:C 2N = N(N − 1)/2;

I La acestea se adauga cheile necesare pentru accesul la resurse(servere, imprimante, baze de date ...);

I Apare o problema de logistica: foarte multe chei sunt dificilde mentinut si utilizat;

I Si apare o problema de securitate: cu cat sunt mai multechei, cu atat sunt mai dificil de stocat ın mod sigur, deci crescsansele de a fi furate de adversari;

Criptografie si Securitate 6/20 ,

Problema 2 - Stocarea secreta a cheilor

I Ramanem la exemplul anterior al unei organizatii numeroasecu N angajati;

I Intrebare: Cate chei sunt necesare pentru ca fiecare 2 angajatisa poata comunica criptat?

I Raspuns:C 2N = N(N − 1)/2;

I La acestea se adauga cheile necesare pentru accesul la resurse(servere, imprimante, baze de date ...);

I Apare o problema de logistica: foarte multe chei sunt dificilde mentinut si utilizat;

I Si apare o problema de securitate: cu cat sunt mai multechei, cu atat sunt mai dificil de stocat ın mod sigur, deci crescsansele de a fi furate de adversari;

Criptografie si Securitate 6/20 ,

Problema 2 - Stocarea secreta a cheilor

I Ramanem la exemplul anterior al unei organizatii numeroasecu N angajati;

I Intrebare: Cate chei sunt necesare pentru ca fiecare 2 angajatisa poata comunica criptat?

I Raspuns:C 2N = N(N − 1)/2;

I La acestea se adauga cheile necesare pentru accesul la resurse(servere, imprimante, baze de date ...);

I Apare o problema de logistica: foarte multe chei sunt dificilde mentinut si utilizat;

I Si apare o problema de securitate: cu cat sunt mai multechei, cu atat sunt mai dificil de stocat ın mod sigur, deci crescsansele de a fi furate de adversari;

Criptografie si Securitate 6/20 ,

Problema 2 - Stocarea secreta a cheilor

I Ramanem la exemplul anterior al unei organizatii numeroasecu N angajati;

I Intrebare: Cate chei sunt necesare pentru ca fiecare 2 angajatisa poata comunica criptat?

I Raspuns:C 2N = N(N − 1)/2;

I La acestea se adauga cheile necesare pentru accesul la resurse(servere, imprimante, baze de date ...);

I Apare o problema de logistica: foarte multe chei sunt dificilde mentinut si utilizat;

I Si apare o problema de securitate: cu cat sunt mai multechei, cu atat sunt mai dificil de stocat ın mod sigur, deci crescsansele de a fi furate de adversari;

Criptografie si Securitate 6/20 ,

Problema 2 - Stocarea secreta a cheilor

I Ramanem la exemplul anterior al unei organizatii numeroasecu N angajati;

I Intrebare: Cate chei sunt necesare pentru ca fiecare 2 angajatisa poata comunica criptat?

I Raspuns:C 2N = N(N − 1)/2;

I La acestea se adauga cheile necesare pentru accesul la resurse(servere, imprimante, baze de date ...);

I Apare o problema de logistica: foarte multe chei sunt dificilde mentinut si utilizat;

I Si apare o problema de securitate: cu cat sunt mai multechei, cu atat sunt mai dificil de stocat ın mod sigur, deci crescsansele de a fi furate de adversari;

Criptografie si Securitate 6/20 ,

Problema 2 - Stocarea secreta a cheilor

I Ramanem la exemplul anterior al unei organizatii numeroasecu N angajati;

I Intrebare: Cate chei sunt necesare pentru ca fiecare 2 angajatisa poata comunica criptat?

I Raspuns:C 2N = N(N − 1)/2;

I La acestea se adauga cheile necesare pentru accesul la resurse(servere, imprimante, baze de date ...);

I Apare o problema de logistica: foarte multe chei sunt dificilde mentinut si utilizat;

I Si apare o problema de securitate: cu cat sunt mai multechei, cu atat sunt mai dificil de stocat ın mod sigur, deci crescsansele de a fi furate de adversari;

Criptografie si Securitate 6/20 ,

Problema 2 - Stocarea secreta a cheilor

I Sistemele informatice sunt deseori infectate de programemalitioase care fura cheile secrete si le transmit prin internetcatre atacator;

I Totusi daca numarul de chei este mic, exista solutii de stocarecu securitate crescuta;

I Un exemplu ıl reprezinta dispozitivele de tip smartcard ;

I Acestea realizeaza calculele criptografice folosind cheiastocata, asigurand faptul ca niciodata cheia secreta nu ajungeın calculator;

I Capacitatea de stocare a unui smartcard este ınsa limitata,neputand memora, de exemplu mii de chei criptografice.

Criptografie si Securitate 7/20 ,

Problema 2 - Stocarea secreta a cheilor

I Sistemele informatice sunt deseori infectate de programemalitioase care fura cheile secrete si le transmit prin internetcatre atacator;

I Totusi daca numarul de chei este mic, exista solutii de stocarecu securitate crescuta;

I Un exemplu ıl reprezinta dispozitivele de tip smartcard ;

I Acestea realizeaza calculele criptografice folosind cheiastocata, asigurand faptul ca niciodata cheia secreta nu ajungeın calculator;

I Capacitatea de stocare a unui smartcard este ınsa limitata,neputand memora, de exemplu mii de chei criptografice.

Criptografie si Securitate 7/20 ,

Problema 2 - Stocarea secreta a cheilor

I Sistemele informatice sunt deseori infectate de programemalitioase care fura cheile secrete si le transmit prin internetcatre atacator;

I Totusi daca numarul de chei este mic, exista solutii de stocarecu securitate crescuta;

I Un exemplu ıl reprezinta dispozitivele de tip smartcard ;

I Acestea realizeaza calculele criptografice folosind cheiastocata, asigurand faptul ca niciodata cheia secreta nu ajungeın calculator;

I Capacitatea de stocare a unui smartcard este ınsa limitata,neputand memora, de exemplu mii de chei criptografice.

Criptografie si Securitate 7/20 ,

Problema 2 - Stocarea secreta a cheilor

I Sistemele informatice sunt deseori infectate de programemalitioase care fura cheile secrete si le transmit prin internetcatre atacator;

I Totusi daca numarul de chei este mic, exista solutii de stocarecu securitate crescuta;

I Un exemplu ıl reprezinta dispozitivele de tip smartcard ;

I Acestea realizeaza calculele criptografice folosind cheiastocata, asigurand faptul ca niciodata cheia secreta nu ajungeın calculator;

I Capacitatea de stocare a unui smartcard este ınsa limitata,neputand memora, de exemplu mii de chei criptografice.

Criptografie si Securitate 7/20 ,

Problema 2 - Stocarea secreta a cheilor

I Sistemele informatice sunt deseori infectate de programemalitioase care fura cheile secrete si le transmit prin internetcatre atacator;

I Totusi daca numarul de chei este mic, exista solutii de stocarecu securitate crescuta;

I Un exemplu ıl reprezinta dispozitivele de tip smartcard ;

I Acestea realizeaza calculele criptografice folosind cheiastocata, asigurand faptul ca niciodata cheia secreta nu ajungeın calculator;

I Capacitatea de stocare a unui smartcard este ınsa limitata,neputand memora, de exemplu mii de chei criptografice.

Criptografie si Securitate 7/20 ,

Problema 3 - Medii de comunicare deschise

I Desi dificil de stocat sau utilizat, criptografia simetrica arputea (cel putin ın teorie) sa rezolve aceste probleme;

I Dar este insuficienta ın medii deschise, ın care participantii nuse ıntalnesc niciodata;

I Astfel de exemple includ: o tranzatie prin internet sau une-mail transmis unei persoane necunoscute;

”Solutions that are based on private-key cryptography are not

sufficient to deal with the problem of secure communication in open

systems where parties connot phisically meet, or where parties have

transient interactions.”

(J.Katz, Y.Lindell: Introduction to Modern Cryptography)

Criptografie si Securitate 8/20 ,

Problema 3 - Medii de comunicare deschise

I Desi dificil de stocat sau utilizat, criptografia simetrica arputea (cel putin ın teorie) sa rezolve aceste probleme;

I Dar este insuficienta ın medii deschise, ın care participantii nuse ıntalnesc niciodata;

I Astfel de exemple includ: o tranzatie prin internet sau une-mail transmis unei persoane necunoscute;

”Solutions that are based on private-key cryptography are not

sufficient to deal with the problem of secure communication in open

systems where parties connot phisically meet, or where parties have

transient interactions.”

(J.Katz, Y.Lindell: Introduction to Modern Cryptography)

Criptografie si Securitate 8/20 ,

Problema 3 - Medii de comunicare deschise

I Desi dificil de stocat sau utilizat, criptografia simetrica arputea (cel putin ın teorie) sa rezolve aceste probleme;

I Dar este insuficienta ın medii deschise, ın care participantii nuse ıntalnesc niciodata;

I Astfel de exemple includ: o tranzatie prin internet sau une-mail transmis unei persoane necunoscute;

”Solutions that are based on private-key cryptography are not

sufficient to deal with the problem of secure communication in open

systems where parties connot phisically meet, or where parties have

transient interactions.”

(J.Katz, Y.Lindell: Introduction to Modern Cryptography)

Criptografie si Securitate 8/20 ,

Problema 4 - Imposibilitatea non-repudierii

I O cheie simetrica este detinuta de cel putin 2 parti;

I Este imposibil de demonstrat de exemplu ca un MAC a fostprodus de una dintre cele 2 parti comunicante;

I De aceea nu se poate utiliza autentificarea simetrica pentru aatesta sursa unui mesaj sau document.

Criptografie si Securitate 9/20 ,

Problema 4 - Imposibilitatea non-repudierii

I O cheie simetrica este detinuta de cel putin 2 parti;

I Este imposibil de demonstrat de exemplu ca un MAC a fostprodus de una dintre cele 2 parti comunicante;

I De aceea nu se poate utiliza autentificarea simetrica pentru aatesta sursa unui mesaj sau document.

Criptografie si Securitate 9/20 ,

Problema 4 - Imposibilitatea non-repudierii

I O cheie simetrica este detinuta de cel putin 2 parti;

I Este imposibil de demonstrat de exemplu ca un MAC a fostprodus de una dintre cele 2 parti comunicante;

I De aceea nu se poate utiliza autentificarea simetrica pentru aatesta sursa unui mesaj sau document.

Criptografie si Securitate 9/20 ,

Criptografia asimetrica

I Criptografia cu cheie publica este introdusa de W.Diffie siM.Hellman in 1976 ca o solutie la problemele enumerateanterior:

”Two kinds of contemporary developments in cryptography are

examined. Widening applications of teleprocessing have given rise

to a need for new types of cryptographic systems, which minimize

the need for secure key distribution channels and supply the

equivalent of written signature. This paper suggests ways to solve

these currently open problems.”

(W.Diffie, M.Hellman: New Directions in Cryptography - abstract)

Criptografie si Securitate 10/20 ,

Criptografia asimetrica

[http://cisac.stanford.

edu/people/whitfield_

diffie/]

[http://www-ee.

stanford.edu/~hellman/]

Criptografie si Securitate 11/20 ,

Criptografia asimetrica

[https://www.acm.org/awards/2015-turing]

Criptografie si Securitate 12/20 ,

Sisteme de criptare asimetrice

I Am studiat sisteme de criptare care folosesc aceeasi cheiepentru criptare si decriptare - sisteme de criptare simetrice;

I Vom studia sisteme de criptare care folosesc chei diferitepentru criptare si decriptare - sisteme de criptare asimetrice;

Criptografie si Securitate 13/20 ,

Sisteme de criptare asimetrice

I Am studiat sisteme de criptare care folosesc aceeasi cheiepentru criptare si decriptare - sisteme de criptare simetrice;

I Vom studia sisteme de criptare care folosesc chei diferitepentru criptare si decriptare - sisteme de criptare asimetrice;

Criptografie si Securitate 13/20 ,

Sisteme de criptare asimetrice

I Am studiat sisteme de criptare care folosesc aceeasi cheiepentru criptare si decriptare - sisteme de criptare simetrice;

I Vom studia sisteme de criptare care folosesc chei diferitepentru criptare si decriptare - sisteme de criptare asimetrice;

Criptografie si Securitate 13/20 ,

Criptarea asimetrica (cu cheie publica)

Criptografie si Securitate 14/20 ,

Criptarea asimetrica (cu cheie publica)

Criptografie si Securitate 15/20 ,

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 publica si sk este cheia secreta

I M = spatiul textelor clare (mesaje)

I C = spatiul textelor criptate

este un dublet (Enc,Dec), unde:

1. Enc : Kpk ×M→ C2. Dec : Ksk × C →M

a.ı. ∀m ∈M, (pk, sk) ∈ K : Decsk(Encpk(m)) = m.

Criptografie si Securitate 16/20 ,

Terminologie

I Spre deosebire de criptarea simetrica, criptarea asimetricafoloseste o pereche de chei:

I Cheia publica pk este folosita pentru criptare;

I Cheia secreta sk este folosita pentru decriptare;

I Cheia publica este larg raspandita pentru a asiguraposibilitatea de criptare oricui doreste sa transmita un mesajcatre entitatea careia ıi corespunde;

I Cheia secreta este privata si nu se cunoaste decat de entitateacareia ıi corespunde;

I Consideram (pentru simplitate) ca ambele chei au lungime celputin n biti.

Criptografie si Securitate 17/20 ,

Terminologie

I Spre deosebire de criptarea simetrica, criptarea asimetricafoloseste o pereche de chei:

I Cheia publica pk este folosita pentru criptare;

I Cheia secreta sk este folosita pentru decriptare;

I Cheia publica este larg raspandita pentru a asiguraposibilitatea de criptare oricui doreste sa transmita un mesajcatre entitatea careia ıi corespunde;

I Cheia secreta este privata si nu se cunoaste decat de entitateacareia ıi corespunde;

I Consideram (pentru simplitate) ca ambele chei au lungime celputin n biti.

Criptografie si Securitate 17/20 ,

Terminologie

I Spre deosebire de criptarea simetrica, criptarea asimetricafoloseste o pereche de chei:

I Cheia publica pk este folosita pentru criptare;

I Cheia secreta sk este folosita pentru decriptare;

I Cheia publica este larg raspandita pentru a asiguraposibilitatea de criptare oricui doreste sa transmita un mesajcatre entitatea careia ıi corespunde;

I Cheia secreta este privata si nu se cunoaste decat de entitateacareia ıi corespunde;

I Consideram (pentru simplitate) ca ambele chei au lungime celputin n biti.

Criptografie si Securitate 17/20 ,

Terminologie

I Spre deosebire de criptarea simetrica, criptarea asimetricafoloseste o pereche de chei:

I Cheia publica pk este folosita pentru criptare;

I Cheia secreta sk este folosita pentru decriptare;

I Cheia publica este larg raspandita pentru a asiguraposibilitatea de criptare oricui doreste sa transmita un mesajcatre entitatea careia ıi corespunde;

I Cheia secreta este privata si nu se cunoaste decat de entitateacareia ıi corespunde;

I Consideram (pentru simplitate) ca ambele chei au lungime celputin n biti.

Criptografie si Securitate 17/20 ,

Terminologie

I Spre deosebire de criptarea simetrica, criptarea asimetricafoloseste o pereche de chei:

I Cheia publica pk este folosita pentru criptare;

I Cheia secreta sk este folosita pentru decriptare;

I Cheia publica este larg raspandita pentru a asiguraposibilitatea de criptare oricui doreste sa transmita un mesajcatre entitatea careia ıi corespunde;

I Cheia secreta este privata si nu se cunoaste decat de entitateacareia ıi corespunde;

I Consideram (pentru simplitate) ca ambele chei au lungime celputin n biti.

Criptografie si Securitate 17/20 ,

Terminologie

I Spre deosebire de criptarea simetrica, criptarea asimetricafoloseste o pereche de chei:

I Cheia publica pk este folosita pentru criptare;

I Cheia secreta sk este folosita pentru decriptare;

I Cheia publica este larg raspandita pentru a asiguraposibilitatea de criptare oricui doreste sa transmita un mesajcatre entitatea careia ıi corespunde;

I Cheia secreta este privata si nu se cunoaste decat de entitateacareia ıi corespunde;

I Consideram (pentru simplitate) ca ambele chei au lungime celputin n biti.

Criptografie si Securitate 17/20 ,

Criptografia asimetrica vs. Criptografia simetrica

Criptografia simetrica

I necesita secretizarea ıntregiichei

I foloseste aceeasi cheiepentru criptare si decriptare

I rolurile emitatorului si alereceptorului pot fischimbate

I pentru ca un utilizator saprimeasca mesaje criptatede la mai multi emitatori,trebuie sa partajeze cufiecare cate o cheie

Criptografia asimetrica

I necesita secretizarea uneijumatati din cheie

I foloseste chei distinctepentru criptare si decriptare

I rolurile emitatorului si alereceptorului nu pot fischimbate

I o pereche de cheiasimetrice permite oricui satransmita informatiecriptata catre entitateacareia ıi corespunde

Criptografie si Securitate 18/20 ,

Criptografia asimetrica

Avantaje

I numar mai mic de chei

I simplifica problemadistribuirii cheilor

I fiecare participant trebuiesa stocheze o singura cheiesecreta de lunga durata

I permite comunicarea sigurape canale publice

I rezolva problema mediilorde comunicare deschise

Dezavantaje

I criptarea asimetrica estemult mai lenta decatcriptarea simetrica

I compromiterea cheii privateconduce la compromitereatuturor mesajelor criptateprimite, indiferent de sursa

I necesita verificareaautenticitatii cheii publice(PKI rezolva aceastaproblema)

Criptografie si Securitate 19/20 ,

Important de retinut!

I Criptografia simetrica NU rezolva toate problemelecriptografiei

I Criptografia asimetrica apare ın completarea criptografieisimetrice

Criptografie si Securitate 20/20 ,