Criptare Bazată pe Identitate

UNIVERSITATEA “ALEXANDRU IOAN CUZA” IAȘI

FACULTATEA DE INFORMATICĂ

LUCRARE DE LICENȚĂ

Criptare bazată pe identitate

propusă de

Murguleț Diana

Sesiunea: Iulie, 2016

Coordonator științific

Pr. Ferucio Laurențiu Țiplea

1

UNIVERSITATEA “ALEXANDRU IOAN CUZA” IAȘI

FACULTATEA DE INFORMATICĂ

Criptare bazată pe identitate

Murguleț Diana

Sesiunea: Iulie, 2012

Coordonator științific

Pr. Ferucio Laurențiu Țiplea

Murguleț Diana – Criptare bazată pe identitate

2

Declarație privind originalitate și respectarea drepturilor de autor

Prin prezenta declar că Lucrarea de licență cu titlul „Criptare bazată pe identitate” este scrisă de mine și nu a mai fost prezentată niciodată la altă facultate sau instituție de învățământ superior din țară sau străinătate. De asemenea, declar că toate sursele utilizate, inclusiv cele preluate de pe Internet, sau indicate în lucrare, cu respectarea regulilor de evitare a plagiatului:

toate fragmentele de text reproduse exact, chiar și în traducere proprie din altă limbă, sunt scrise între ghilimele și dețin referința precisă a sursei;

reformularea în cuvinte proprii a textelor scrise de către alți autori deține referința precisă;

codul sursă, imagini etc. preluate din proiecte open-source sau alte surse sunt utilizate cu respectarea drepturilor de autor și dețin referințe precise;

rezumarea ideilor altor autori precizează referința precisă la textul original.

Iași,

Absolvent: Murguleț Diana

_______________

Murguleț Diana – Criptare bazată pe identitate

3

Declarație de consimțământ

Prin prezenta declar că Lucrarea de licență cu titlul „Criptare bazată pe identitate”, codul sursă al programelor și celelalte conținuturi (grafice, multimedia, date de test etc.) care însoțesc această lucrare să fie utilizate în cadrul Facultății de Informatică. De asemenea, sunt de acord ca Facultatea de Informatică de la Universitatea Alexandru Ioan Cuza Iași să utilizeze, modifice, reproducă și să distribuie în scopuri necomerciale programele-calculator, format executabil și sursă, realizate de mine în cadrul prezentei lucrări de licență.

Iași,

Absolvent: Murguleț Diana

_______________________

Murguleț Diana – Criptare bazată pe identitate

5

Cuprins

Motivație ……………………………………………………………………………………….……………6

Introducere………………………………………………………………………………………….………7

1. Definiție și aplicații 9

1.1. Ce reprezintă criptarea bazată pe identitate 9

1.2. Aplicații ale criptării bazată pe identitate…………………………………………………………..11

1.2.1 Revocarea cheilor publice……………………………………………………………………..11

1.2.2. Delegarea cheilor de decriptare ………………………………………………..…………….12

1.3 Modelul IBE…..……………………………………………………………………………………13

1.4 Implementari IBE……………………………………………………………………………………14

2. Schema Cocks 10

Murguleț Diana – Criptare bazată pe identitate

6

Motivație

Software-ul criptografic joacă un rol esențial în sistemele computaționale. Acesta are o natură critică deoarece orice slăbiciune sau defecțiune a unui modul criptografic ar putea fi exploatată pentru a compromite siguranța întregului sistem, ceea ce ar putea duce la evenimente catastrofale din punct de vedere al securității. Sistemele ce aleg să folosească un software criptografic o fac din necesitatea de a își proteja informațiile. De la email-uri transmise între prieteni, la proiecte industriale sau secrete guvernamentale, nevoia de a ascunde informații de un adversar este reală și necesară. În societatea modernă, odată cu creșterea utilizării rețelelor de calculatoare, utilizarea criptografiei este imperativă. Atunci când este în mod corect implementată și folosită, criptografia poate proteja datele într-un mod eficient și asta nu deoarece este imposibil de atacat, ci din cauză că dobândirea neautorizată a unor informații devine computațional nerealizabilă sau mult prea costisitoare.

Criptosistemele actuale sunt împărțite în două categorii: simetrice și asimetrice. Criptosistemele simetrice, numite și criptosisteme cu chei publice, folosesc aceeași cheie (cheie secretă) pentru a cripta și a decripta un mesaj, în timp ce criptosistemele asimetrice folosesc o cheie publică pentru a cripta mesajul ce se dorește a fi transmis și o altă cheie privată pentru că respectivul mesaj să fie decriptat.

Lucrarea de față propune un studiu al unui subdomeniu al criptografiei bazată pe chei publice și anume criptografia bazată pe identitate. Pornim de la revizuirea conceptelor de bază ale sistemelor de criptare bazate pe identitate, analizând cele 3 abordări existente în prezent și îndreptându-ne atenția către schema propusă de Clifford Cocks, a cărei securitate se bazează pe utlizarea reziduurilor pătratice.

Murguleț Diana – Criptare bazată pe identitate

7

Introducere

Criptarea bazată pe chei publice (PKE – Public Key Encryption) este un model ce facilitează comunicarea printr-un canal public, cum este Internetul, folosindu-se atât de chei private, cât și de chei publice. Cheile sunt pur și simplu numere mari, fiind ascociate între ele însă nefiind identice.

Una dintre cheile din pereche este numită cheie publică și este cunoscută de toată lumea, în timp ce cealaltă cheie este ținută secretă și se numește cheie privată. În timp ce una dintre chei este folosită pentru a cripta mesajul trasnmis, cealaltă cheie va fi folosită pentru decriptarea aceluiași mesaj.

În imaginea de mai jos putem observa o schemă simplă ce ilustrează criptarea bazată pe chei publice:

Pentru ca criptarea asimetrică să ofere integritate, confidențialitate și autenticitate, utilizatorii și sistemele trebuie să fie sigure că cheia publică folosită este autentică, mai exact că aceasta aparține cu adevărat personei sau entității căreia susține că aparține și că nu a fost modificată sau înlocuită de către o a treia entitate.

Murguleț Diana – Criptare bazată pe identitate

8

Nu există o soluție privind autenticitatea cheilor publice care să funcționeze perfect, însă cea mai utilizată abordare este cea a folosirii unei infrastructuri cu chei publice ( PKI – Public Key Infrastructure). O infrastructură cu chei publice sprijină distribuția și identificarea cheilor de criptare publice, permițând atât utilizatorilor cât și calculatoarelor să transmită în mod sigur informații prin intermediul rețelelor, ca și Internetul, și să verifice identitatea celeilalte părți implicate.

Imaginea de mai jos reprezintă o schemă a infrastructurii cu chei publice, unde CA reprezintă o autoritate centrală ce eliberează sau revocă certificate.

Principala problemă a acestei abordări este faptul că criptarea mesajului se face abia după ce cheia publică și certificatul corespunzător ei au fost verificate.

Criptarea bazată pe identitate încearcă să elimine aceste probleme ce apar în criptarea asimetrică, simplificând administrarea cheilor

Murguleț Diana – Criptare bazată pe identitate

9

Definiție si aplicații

Ce reprezintă criptarea bazată pe identitate

În 1984, Adi Shamir a propus un concept de criptare bazată pe identitate. În această nouă

paradigmă a criptografiei, informațiile de identificare ale unui utilizator precum adresa de

e-mail sau adresa IP pot fi folosite ca și chei publice (în locul certificatelor digitale) pentru criptarea mesajului sau verificarea semnăturii.

Cele două imagini prezentate mai jos ne arată schemele pentru criptarea cu chei publice în care o autoritate centrală eliberează și revocă certificate corespunzătoare cheilor publice, respectiv criptarea bazată pe identitate.

pkB – Cheia publică a lui Bob

certB – Ceritficatul luiBob

AC – Autoritatea de certificare

pkCA – Parametrii publici

Murguleț Diana – Criptare bazată pe identitate

10

In cazul acestei scheme de criptare ce folosește chei publice, expeditorul, Alice, va trebui să verfice dacă destinatarul, Bob, deține o cheie publică generată de Autoritatea Centrală (AC) și se va asigura că pkB este cea mai recentă cheie publică a acestuia și abia apoi va iniția comunicarea.

CGC – Centrul de Generare a Cheilor

SP – parametrii sistemului

idB – identitatea lui Bob

skB – cheia secreta a lui Bob

Construirea unei scheme de criptare bazată pe identitate (IBE – Identity Based Encryption), a rămas pentru o lungă perioadă o problemă în criptografie, deși Shamir a construit cu ușurință o schemă de semnare bazată pe identitate ( IBS – Identity Based Signature ) folosind algoritmul deja existent RSA.

Folosind criptarea bazată pe identitate, expeditorii nu trebuie să caute cheile publice și certificatele corespunzătoare ale destinatarului, deoarece informațiile de identificare (ex: adresele de e-mail) împreună cu parametrii publici comuni sunt suficiente pentru criptarea

Murguleț Diana – Criptare bazată pe identitate

11

mesajului. Cheile private ale utilizatorilor sunt emise de către o tertă parte de încredere numită PKG – Private Key Generator (în schema de mai sus Centrul de Generare a Cheilor joacă rolul de PGK).

Într-o astfel de schemă avem patru algoritmi: setup ce generează parametrii sistemului și cheia-master, extract ce generează cheia privată corespunzătoare unui șir folosindu-se de cheia-master, encrypt ce criptează mesajul folosind cheia publică și decrypt ce decriptează mesajul folosind cheia privată corespunzătoare.

Drept rezultat, criptarea bazată pe identitate reduce semnificativ atât complexitatea sistemului, cât și costurile pentru stabilirea și gestionarea arhitecturii pentru autentificare( a infrastructurii cu chei publice).

Aplicații ale criptării bazate pe identitate

Pe lângă motivația inițială a lui Shamir de a simplifica administrarea certificatelor în sistemele de e-mail, criptarea bazată pe identitate are și alte aplicații

Revocarea cheilor publice

Este cunoscut faptul că certificatele de chei publice conțin o dată de expirare prestabilită, însă stabilirea unei date de expirare ar putea fi posibilă și într-un sistem de criptare bazat pe identitate. Alice ar putea cripta mesajul pe care îl trimite către Bob cu cheia publică „[anonimizat] || an-curent”, și astfel ea va seta dată de expirare a cheii sistemului, Bob putând să își folosească cheia privată numai în timpul anului curent. Astfel, Bob va trebui să obțină o nouă cheie privată în fiecare an, în timp ce Alice nu are nevoie să obțină un nou certificat de la Bob de fiecare data când acesta își înnoiește cheia privată.

În loc să folosească anul curent, Alice ar putea cripta mesajul și cu cheia publică „[anonimizat] || dată-curenta”, lucru care îl va obliga pe Bob să obțină o cheie privată în fiecare zi. Folosind această metodă, Alice ar putea să îi trimită și mesaje în viitor lui Bob, deoarece acesta nu va putea citi un mail decât la dată specificată de Alice. O astfel de abordare ar fi posibilă într-un mediu corporatist, unde generatorul de chei private este întreținut de corporație. În cazul în care Bob ar părăsi compania, generatorului de chei private trebuie doar să i se spună să nu mai genereze chei private pentru adresa de e-mail a lui Bob, și astfel, el nu

Murguleț Diana – Criptare bazată pe identitate

12

va mai putea sa isi citească mail-ul.

În urma acestor exemple, putem observa că criptarea bazată pe identitate este și un mecanism eficient de a implementa chei efemere.

Pe lângă folosirea datei de expirare ca făcând parte din cheia publică, am putea folosi și un câmp pentru a stabili confidențialitatea unui anumit mesaj. De exemplu, Alice ar putea folosi următoarea cheie publică pentru a îi transmite un mesaj lui Bob: „[anonimizat] || an-curent || confidentialitate=secret”, și astfel Bob va putea să citească mail-ul din data respectivă doar dacă această dată are confidențialitatea secretă. Așadar, putem observa că generatorul de chei private poate într-un mod simplu să acorde și să revoce credentialele unui utilizator.

Delegarea cheilor de decriptare

O altă aplicație a sistemelor IBE o reprezintă delegarea cheilor de decriptare. În ambele exemple ce urmează, vom considera că Bob are și rolul de PKG, el generandu-și singur parametrii sistemului, precum și cheia-master. În aceste exemple vom vedea parametrii sistemului ca fiind cheia publică a lui Bob.

Să luăm drept exemplu cazul prezentat și mai sus în care Alice criptează mesajul pe care îl transmite folosind în cheia publică data curentă. Știm că Bob are cheia-master deci va putea decripta mesajul trimis de Alice și îl va putea citi. Dar în cazul în care Bob ar fi plecat în concediu pentru o săptămâna și ar avea cheia privată pe laptop, cheia-master ar putea fi compromisă dacă cineva i-ar fura laptopul lui Bob. În acest caz, Bob ar putea pur și simplu să își instaleze cele șapte chei private corespunzătoare zilelor în care va fi plecat. Procedând astfel, dacă cineva i-ar fura laptopul, numai cele șapte chei private ar fi compromise, nu și cheia-master.

Criptarea bazată pe identitate poate să simplifice securitatea sistemelor care administrează un număr mare de chei publice. În loc să memorăm într-o bază de date cheile publice, sistemul poate fie să deriveze acest chei din numele utiliztorilor, fie doar să folosească numere întregi că și chei publice diferite. .

Să preuspunem că Alice criptează mesajul pe care i-l trimite lui Bob folosind drept cheie publică subiectul mail-ului. În cazul în care Bob ar avea mai mulți angajați responsabili fiecare de o anumită sarcină, el ar putea să îi dea fiecărui angajat o cheie privată corespunzătoare responsabilității pe care o are. Astfel, fiecare anagajat va putea citi mesajul corespunzător sarcinii sale, în timp ce Alice are nevoie doar de o singură cheie publică (cea a lui Bob).

Murguleț Diana – Criptare bazată pe identitate

13

Modelul IBE

Dan Bomeh și Mattew K. Franklin au definit un set de patru algoritmi ce alcătuiesc un sistem complet de criptare bazat pe identitate.

O schemă ɛ a criptării bazate pe identitate este speicifcată de patru algoritmi randomizați: Setup, Extract, Encrypt, Decrypt:

Setup: acest algoritm este executat de către generatorul de chei private (PKG) o

singură dată la început. Primește la intrare un parametru de securitate k și returnează parametrii sistemului, params, ce conțin o descriere a spațiului finit de mesaje M și o descriere a spațiului finit de mesaje criptate C.

Extract: acest algoritm este executat de care generatorul de chei private de fiecare dată când un utilizator solicită cheia sa privată. Primește la intrare parametrii: params, cheia-master și un ID ∈ {0,1} *,acesta reprezentând cheia publică a destinatarului, și returnează d, cheia privată corespunzătoare utlizatorului ID.

Encrypt: acest algoritm este executat de către emițător atunci când dorește să transmită un mesaj. Primește la intrare parametrii: params, ID și un mesaj m ∈ M și returnează mesajul criptat c∈C.

Decrypt: acest algoritm este executat de către destinatar pentru a putea citi mesajul. Primește la intrare params, c∈C, și cheia privată d și returnează m ∈ M.

Pentru ca intregul sistem sa functioneze, acesti algoritmi trebuie sa satisfaca constrangerea standard, si anume atunci cand algoritmul Extract folosindu-se de cheia publica ID returneaza cheia privata d, atunci:

∀ m ∈ M: Decrypt(params,c,d) = M, unde C= Encrypt(params,id,M)

Urmărind algoritmii prezentați mai jos, putem observa diferențele dintre definiția schemei de criptare bazată pe identitate prezentată de Boneh Și Franklin și schema de semnare prezentată de Shamir în 1984.

Murguleț Diana – Criptare bazată pe identitate

14

Această schemă de semnare poate fi descrisă urmărind următorii pași:

Setup: Generatorul de chei private PKG (care este în acest caz o entitate de încredere) își creează o pereche de chei dintre care una este cheia-master privată, notată cu skPKG și cealaltă este o cheie publică notată pkPKG.

Extragerea cheii private: Pentru a putea trimite un mesaj, expeditorul Alice trebuie să fie autentificat de către PKG și să obțină a cheie privată pe care o vom nota skIDAlice asociată identității sale, IDAlice.

Generarea semnăturii: Folosind cheia privată pe care a obținut- de la PKG, Alice creează o semnătură mesajului ei M.

Verificarea semnăturii: Pentru a putea decripta mesajul M trimis de Alice și având semnătura acesteia, destinatarul Bob trebuie să verifice mai întâi dacă semnătura primită de el este autentică și îi aparține cu adevărat lui Alice. El face acest lucru folosindu-se de identitatea lui Alice, IDAlice, și de cheia publică a generatorului de chei private. Dacă este într-adevăr semnătura lui Alice, el va accepta mesajul, iar în caz contrar el va refuza mesajul.

Implementări IBE

În timp ce o schemă de semnare a fost imediat prezentată încă din 1984 de către Shamir, schemele de criptare bazată pe identitate (IBE) au fost mai greu de dezvoltat și au apărut mult mai târziu.

Prima implementare a unei scheme IBE a fost propusă de către Desmedt și de către Quisquater în 1986. Din păcate, această schemă nu a putut fi pusă în practică deoarece necesita existența unui hardware inviolabil pentru a fi sigură.

O schemă de criptosistem bazat pe identitate ce putea fi cu adevărat pusă în practică a fost prezentată abia după șaptesprezece ani, prin lucrările lui Dan Boneh și Mattew Franklin, respectiv Ryuichi Skai și Masao Kasahara. Ambele variante sunt bazate pe perechile biliniare în curbele eliptice și securitatea acestor scheme este bazată pe problemă Diffie – Hellman (BDH). Aceste două scheme sunt eficiente în practică. Schema IBE propusă de Boneh și de Franklin a primit mai multă atenție dat fiind faptul că a fost prima schemă IBE a cărei securitate a fost și demonstrată.

Murguleț Diana – Criptare bazată pe identitate

15

Atât schema Boneh-Franklin, cât și schema Sakai au un algoritm de extragere a cheilor private foarte asemănător: cheia privată corespunzătoare unui id se calculează prin înmulțirea cheii-master private cu un punct de mapare pe o curbă eliptică, punct în care a fost mapat un șir corespunzător id-ului destinatarului.

Mai jos este prezentată schema Boneh – Franklin, schemă demonstrată a fi sigură împotrivă unui atac CPA (Chosen Plaintext Attack) într-un model oracle random, presupunând că BDH este dificil din punct de vedere computațional

În prima fază de Setup, PKG specifică un grup generat de și o pere- che biliniară . Specifică de asemenea și două functii hash:

unde l este lungimea textului initial. PKG alege apoi o cheie master in mod aleator și calculează o cheie

publică PKG publică decrieri ale grupului si functiile hash H1 si H2, cat și cheia publică PPKG. Pentru a decripta mesajul, Bob trebuie sa apeleze la PKG pentru a face rost de cheia sa privată unde

Alice poate acum sa cripteze mesajul M ∈ {0,1}l folosind ID-ul lui Bob si calculand U=rP

și V= , unde r este ales aleator din si QID = H1(ID)

Mesajul astfel criptat este trimis catre Bob, el decriptandu-l folosind urmatoarea formulă:

Dacă schemele prezentate până acum utilizează aplicații biliniare, Clifford Cocks vine în același an cu un model inovativ de implementare a unei scheme IBE, un model a cărui securitate se bazează pe problema reziduozitatii pătratice.

La momentul actual, exista 3 abordări ale sistemelor de criptare bazate pe identitate, acestea utilizand :

Aplicații biliniare in grupuri ale curbelor eliptice, considerată ca fiind cea mai eficientă abordare de până acum;

Reziduuri pătratice, avantajul utilizării acestora fiind faptul că operațiile de

criptare și decriptare sunt simple, însă lungimea criptotextului este una mare.

Murguleț Diana – Criptare bazată pe identitate

16

Latici, avantajul folosirii acestora fiind faptul ca nu necesită aritmetică multi-precizie, însă și această abordare are dezavantajul că lungimea criptotextului este una mare.

Murguleț Diana