riptografie si Securitate

- Prelegerea 12 -Scheme de criptare CCA sigure

Adela Georgescu, Ruxandra F. Olimid

Facultatea de Matematica si InformaticaUniversitatea din Bucuresti

Cuprins

1. Schema de criptare CCA sigura - constructie

2. Schema de criptare CCA sigura - demonstratie

Criptografie si Securitate 2/10 ,

Securitate CCA

I In cursul precedent am introdus notiunile de securitate CPA sisecuritate CCA;

I Multe dintre schemele prezentate pana acum sunt CPA sigure(sistemele bloc ımpreuna cu modurile de utilizare CBC, OFBsi CTR);

I Insa nici una din schemele prezentate nu este CCA sigura;

I In acest curs vom folosi MAC-uri ımpreuna cu scheme CPAsigure pentru a construi scheme CCA sigure;

I Incepem prin a reaminti notiunea de schema CCA sigura;

Criptografie si Securitate 3/10 ,

Securitate CCA

I In cursul precedent am introdus notiunile de securitate CPA sisecuritate CCA;

I Multe dintre schemele prezentate pana acum sunt CPA sigure(sistemele bloc ımpreuna cu modurile de utilizare CBC, OFBsi CTR);

I Insa nici una din schemele prezentate nu este CCA sigura;

I In acest curs vom folosi MAC-uri ımpreuna cu scheme CPAsigure pentru a construi scheme CCA sigure;

I Incepem prin a reaminti notiunea de schema CCA sigura;

Criptografie si Securitate 3/10 ,

Securitate CCA

I In cursul precedent am introdus notiunile de securitate CPA sisecuritate CCA;

I Multe dintre schemele prezentate pana acum sunt CPA sigure(sistemele bloc ımpreuna cu modurile de utilizare CBC, OFBsi CTR);

I Insa nici una din schemele prezentate nu este CCA sigura;

I In acest curs vom folosi MAC-uri ımpreuna cu scheme CPAsigure pentru a construi scheme CCA sigure;

I Incepem prin a reaminti notiunea de schema CCA sigura;

Criptografie si Securitate 3/10 ,

Securitate CCA

I In cursul precedent am introdus notiunile de securitate CPA sisecuritate CCA;

I Multe dintre schemele prezentate pana acum sunt CPA sigure(sistemele bloc ımpreuna cu modurile de utilizare CBC, OFBsi CTR);

I Insa nici una din schemele prezentate nu este CCA sigura;

I In acest curs vom folosi MAC-uri ımpreuna cu scheme CPAsigure pentru a construi scheme CCA sigure;

I Incepem prin a reaminti notiunea de schema CCA sigura;

Criptografie si Securitate 3/10 ,

Securitate CCA

I In cursul precedent am introdus notiunile de securitate CPA sisecuritate CCA;

I Multe dintre schemele prezentate pana acum sunt CPA sigure(sistemele bloc ımpreuna cu modurile de utilizare CBC, OFBsi CTR);

I Insa nici una din schemele prezentate nu este CCA sigura;

I In acest curs vom folosi MAC-uri ımpreuna cu scheme CPAsigure pentru a construi scheme CCA sigure;

I Incepem prin a reaminti notiunea de schema CCA sigura;

Criptografie si Securitate 3/10 ,

Experimentul Priv ccaA,π(n)

I Pe toata durata experimentului, A are acces la oracolul decriptare Enck(·) si la oracolul de decriptare Deck(·) curestrictia ca nu poate decripta c!

Criptografie si Securitate 4/10 ,

Experimentul Priv ccaA,π(n)

Definitie

O schema de criptare π = (Enc ,Dec) este CCA-sigura daca pentruorice adversar PPT A exista o functie neglijabila negl asa ıncat

Pr[Priv ccaA,π(n) = 1] ≤ 1

2 + negl(n).

Criptografie si Securitate 5/10 ,

Schema de criptare CCA sigura

I Cele doua parti comunicante partajeaza doua chei secrete,una pentru schema de criptare CPA sigura si ınca una pentruun cod de autentificare a mesajelor (MAC).

I Pentru criptarea unui mesaj m, Alice procedeaza astfel:

I cripteaza m folosind schema CPA sigura, rezultand textulcriptat c

I calculeaza un tag MAC t pe textul criptat cI rezultatul final al criptarii este 〈c , t〉

I Pentru un text criptat 〈c , t〉, Bob verifica validitatea tag-uluiınainte de a decripta;

I Un text criptat 〈c, t〉 este valid daca t este un tag validpentru c .

Criptografie si Securitate 6/10 ,

Schema de criptare CCA sigura

I Cele doua parti comunicante partajeaza doua chei secrete,una pentru schema de criptare CPA sigura si ınca una pentruun cod de autentificare a mesajelor (MAC).

I Pentru criptarea unui mesaj m, Alice procedeaza astfel:

I cripteaza m folosind schema CPA sigura, rezultand textulcriptat c

I calculeaza un tag MAC t pe textul criptat cI rezultatul final al criptarii este 〈c , t〉

I Pentru un text criptat 〈c , t〉, Bob verifica validitatea tag-uluiınainte de a decripta;

I Un text criptat 〈c, t〉 este valid daca t este un tag validpentru c .

Criptografie si Securitate 6/10 ,

Schema de criptare CCA sigura

I Cele doua parti comunicante partajeaza doua chei secrete,una pentru schema de criptare CPA sigura si ınca una pentruun cod de autentificare a mesajelor (MAC).

I Pentru criptarea unui mesaj m, Alice procedeaza astfel:

I cripteaza m folosind schema CPA sigura, rezultand textulcriptat c

I calculeaza un tag MAC t pe textul criptat cI rezultatul final al criptarii este 〈c , t〉

I Pentru un text criptat 〈c , t〉, Bob verifica validitatea tag-uluiınainte de a decripta;

I Un text criptat 〈c, t〉 este valid daca t este un tag validpentru c .

Criptografie si Securitate 6/10 ,

Schema de criptare CCA sigura

I Cele doua parti comunicante partajeaza doua chei secrete,una pentru schema de criptare CPA sigura si ınca una pentruun cod de autentificare a mesajelor (MAC).

I Pentru criptarea unui mesaj m, Alice procedeaza astfel:

I cripteaza m folosind schema CPA sigura, rezultand textulcriptat c

I calculeaza un tag MAC t pe textul criptat c

I rezultatul final al criptarii este 〈c , t〉

I Pentru un text criptat 〈c , t〉, Bob verifica validitatea tag-uluiınainte de a decripta;

I Un text criptat 〈c, t〉 este valid daca t este un tag validpentru c .

Criptografie si Securitate 6/10 ,

Schema de criptare CCA sigura

I Cele doua parti comunicante partajeaza doua chei secrete,una pentru schema de criptare CPA sigura si ınca una pentruun cod de autentificare a mesajelor (MAC).

I Pentru criptarea unui mesaj m, Alice procedeaza astfel:

I cripteaza m folosind schema CPA sigura, rezultand textulcriptat c

I calculeaza un tag MAC t pe textul criptat cI rezultatul final al criptarii este 〈c , t〉

I Pentru un text criptat 〈c , t〉, Bob verifica validitatea tag-uluiınainte de a decripta;

I Un text criptat 〈c, t〉 este valid daca t este un tag validpentru c .

Criptografie si Securitate 6/10 ,

Schema de criptare CCA sigura

I Cele doua parti comunicante partajeaza doua chei secrete,una pentru schema de criptare CPA sigura si ınca una pentruun cod de autentificare a mesajelor (MAC).

I Pentru criptarea unui mesaj m, Alice procedeaza astfel:

I cripteaza m folosind schema CPA sigura, rezultand textulcriptat c

I calculeaza un tag MAC t pe textul criptat cI rezultatul final al criptarii este 〈c , t〉

I Pentru un text criptat 〈c , t〉, Bob verifica validitatea tag-uluiınainte de a decripta;

I Un text criptat 〈c, t〉 este valid daca t este un tag validpentru c .

Criptografie si Securitate 6/10 ,

Schema de criptare CCA sigura

I Cele doua parti comunicante partajeaza doua chei secrete,una pentru schema de criptare CPA sigura si ınca una pentruun cod de autentificare a mesajelor (MAC).

I Pentru criptarea unui mesaj m, Alice procedeaza astfel:

I cripteaza m folosind schema CPA sigura, rezultand textulcriptat c

I calculeaza un tag MAC t pe textul criptat cI rezultatul final al criptarii este 〈c , t〉

I Pentru un text criptat 〈c , t〉, Bob verifica validitatea tag-uluiınainte de a decripta;

I Un text criptat 〈c, t〉 este valid daca t este un tag validpentru c .

Criptografie si Securitate 6/10 ,

O schema de criptare CCA sigura

Constructie

Fie ΠE = (Enc,Dec) o schema de criptare cu cheie secreta siΠM = (Mac,Vrfy) un cod de autentificare a mesajelor.Definim schema de criptare (Enc′,Dec′) astfel:

I Enc: pentru o cheie (k1, k2) si un mesaj m, calculeazac = Enck1(m) si t = Mack2(c) si ıntoarce textul criptat 〈c , t〉;

I Dec: pentru o cheie (k1, k2) si un text criptat 〈c , t〉, verificadaca Vrfyk2

(c , t) = 1. In caz afirmativ, ıntoarce Deck1(c),altfel ıntoarce ⊥.

I Simbolul ⊥ indica esec;

I Corectitudinea schemei cere ca Deck1,k2(Enck1,k2(m)) 6=⊥.

I Spunem ca (Mac,Vrfy) are tag-uri unice daca ∀m ∀k ∃ ununic tag t a.ı. Vrfyk(m, t) = 1.

Criptografie si Securitate 7/10 ,

O schema de criptare CCA sigura

Teorema

Daca schema de criptare ΠE este CPA-sigura si ΠM este un MACsigur cu tag-uri unice, atunci constructia precedenta reprezinta oschema de criptare CCA-sigura.

Criptografie si Securitate 8/10 ,

Demonstratie intuitiva

I Un text criptat 〈c, t〉 este valid (ın raport cu o cheie (k1, k2))daca Vrfyk2

(c , t) = 1;

I Mesajele pe care adversarul A le trimite catre oracolul dedecriptare sunt de 2 feluri:

I texte criptate pe care A le-a primit de la oracolul de criptare(stie deja textul clar, deci nu ıi sunt de folos);

I texte criptate pe care nu le-a primit de la oracolul de criptare;

I Insa, cum ΠM este un MAC sigur, cu probabilitate foarte maretextele criptate care nu au fost obtinute de la oracolul decriptare sunt invalide, iar oracolul de decriptare va ıntoarce ⊥ın acest caz;

I Cum oracolul de decriptare este inutil, securitatea schemei(Enc′,Dec′) se reduce la securitatea CPA a schemei ΠE .

Criptografie si Securitate 9/10 ,

Demonstratie intuitiva

I Un text criptat 〈c, t〉 este valid (ın raport cu o cheie (k1, k2))daca Vrfyk2

(c , t) = 1;

I Mesajele pe care adversarul A le trimite catre oracolul dedecriptare sunt de 2 feluri:

I texte criptate pe care A le-a primit de la oracolul de criptare(stie deja textul clar, deci nu ıi sunt de folos);

I texte criptate pe care nu le-a primit de la oracolul de criptare;

I Insa, cum ΠM este un MAC sigur, cu probabilitate foarte maretextele criptate care nu au fost obtinute de la oracolul decriptare sunt invalide, iar oracolul de decriptare va ıntoarce ⊥ın acest caz;

I Cum oracolul de decriptare este inutil, securitatea schemei(Enc′,Dec′) se reduce la securitatea CPA a schemei ΠE .

Criptografie si Securitate 9/10 ,

Demonstratie intuitiva

I Un text criptat 〈c, t〉 este valid (ın raport cu o cheie (k1, k2))daca Vrfyk2

(c , t) = 1;

I Mesajele pe care adversarul A le trimite catre oracolul dedecriptare sunt de 2 feluri:

I texte criptate pe care A le-a primit de la oracolul de criptare(stie deja textul clar, deci nu ıi sunt de folos);

I texte criptate pe care nu le-a primit de la oracolul de criptare;

I Insa, cum ΠM este un MAC sigur, cu probabilitate foarte maretextele criptate care nu au fost obtinute de la oracolul decriptare sunt invalide, iar oracolul de decriptare va ıntoarce ⊥ın acest caz;

I Cum oracolul de decriptare este inutil, securitatea schemei(Enc′,Dec′) se reduce la securitatea CPA a schemei ΠE .

Criptografie si Securitate 9/10 ,

Demonstratie intuitiva

I Un text criptat 〈c, t〉 este valid (ın raport cu o cheie (k1, k2))daca Vrfyk2

(c , t) = 1;

I Mesajele pe care adversarul A le trimite catre oracolul dedecriptare sunt de 2 feluri:

I texte criptate pe care A le-a primit de la oracolul de criptare(stie deja textul clar, deci nu ıi sunt de folos);

I texte criptate pe care nu le-a primit de la oracolul de criptare;

I Insa, cum ΠM este un MAC sigur, cu probabilitate foarte maretextele criptate care nu au fost obtinute de la oracolul decriptare sunt invalide, iar oracolul de decriptare va ıntoarce ⊥ın acest caz;

I Cum oracolul de decriptare este inutil, securitatea schemei(Enc′,Dec′) se reduce la securitatea CPA a schemei ΠE .

Criptografie si Securitate 9/10 ,

Demonstratie intuitiva

I Un text criptat 〈c, t〉 este valid (ın raport cu o cheie (k1, k2))daca Vrfyk2

(c , t) = 1;

I Mesajele pe care adversarul A le trimite catre oracolul dedecriptare sunt de 2 feluri:

I texte criptate pe care A le-a primit de la oracolul de criptare(stie deja textul clar, deci nu ıi sunt de folos);

I texte criptate pe care nu le-a primit de la oracolul de criptare;

I Insa, cum ΠM este un MAC sigur, cu probabilitate foarte maretextele criptate care nu au fost obtinute de la oracolul decriptare sunt invalide, iar oracolul de decriptare va ıntoarce ⊥ın acest caz;

I Cum oracolul de decriptare este inutil, securitatea schemei(Enc′,Dec′) se reduce la securitatea CPA a schemei ΠE .

Criptografie si Securitate 9/10 ,

Demonstratie intuitiva

I Un text criptat 〈c, t〉 este valid (ın raport cu o cheie (k1, k2))daca Vrfyk2

(c , t) = 1;

I Mesajele pe care adversarul A le trimite catre oracolul dedecriptare sunt de 2 feluri:

I texte criptate pe care A le-a primit de la oracolul de criptare(stie deja textul clar, deci nu ıi sunt de folos);

I texte criptate pe care nu le-a primit de la oracolul de criptare;

I Insa, cum ΠM este un MAC sigur, cu probabilitate foarte maretextele criptate care nu au fost obtinute de la oracolul decriptare sunt invalide, iar oracolul de decriptare va ıntoarce ⊥ın acest caz;

I Cum oracolul de decriptare este inutil, securitatea schemei(Enc′,Dec′) se reduce la securitatea CPA a schemei ΠE .

Criptografie si Securitate 9/10 ,

Important de retinut!

I Schema de criptare CPA-sigura + MAC sigur = schema decriptare CCA sigura

Criptografie si Securitate 10/10 ,