Loading
Study Reminders
Support
Text Version

Set your study reminders

We will email you at these times to remind you to study.
  • Monday

    -

    7am

    +

    Tuesday

    -

    7am

    +

    Wednesday

    -

    7am

    +

    Thursday

    -

    7am

    +

    Friday

    -

    7am

    +

    Saturday

    -

    7am

    +

    Sunday

    -

    7am

    +

Fondamenti di Cryptography Prof. Ashish Choudhury Department of Computer Science International Institute of Information Technology - Bangalore Lecture - 49 CCA Secure Public Key Ciphers Based on Diffie - Hellman Problems (Riferirsi Slide Time: 00.33) Ciao a tutti. Benvenuti a questa lezione. Il piano per questa lezione è il seguente: Così in questa lezione vedremo l'insicurezza del CCA di El Gamal public key cryptosystem, che avevamo dimostrato prima di essere CPA sicuro. Poi, vedremo un'istanziazione di CCA protetto chiave di incapsulamento basato su ipotesi di gap - CDH. Quindi introdurremo formalmente ciò che esattamente è gap - assunzione CDH. E in base a ciò, vedremo un CCA garantito instanziamento del meccanismo di incapsulamento delle chiavi e dato che nell'ultima lezione avevamo visto che, se ci si dà un KEM protetto da CCA, poi combinandolo con qualsiasi cifratura simmetrica protetta da CCA, possiamo ottenere un sistema di codifica a chiave pubblica ibrida protetta da CCA. Così facendo, otterremo una versione sicura di CCA di instanziamento di crittosistema di chiavi pubbliche ibrida basato su problemi di Diffie - Hellman e le due varianti di tale instanziamento, ovvero DHIES ed ECIES, ne discuteremo. (Riferimento Slide Time: 01 :26) Quindi iniziamo con la malleabilità di El Gamal Cipher. Tanto per ricordare, questa è una descrizione del processo di crittografia di El Gamal. L'algoritmo di generazione chiavi in chiave outmette un tasto pubblico e segreto, dove la chiave pubblica è qualche g α dove α viene scelto casualmente da Zq e una chiave segreta. Per cifrare un testo semplice, sender prime calcola g β, dove β viene scelto casualmente da Zq. E poi il messaggio viene moltiplicato per chiave pubblica (pk) β e (pk) β non è altro che un tasto Diffie - Hellman g α β Quindi per semplicità, presumo che il mio gruppo sottostante sia un gruppo moltiplicativo ed è per questo che il mio c2 è il prodotto di m e il componente (pk) β. Per decodificare, il ricevitore calcola per la prima volta una chiave comune Diffie - Hellman alzando la parte c1 del testo di cifratura alla chiave segreta e prendendo il suo inverso moltiplicativo e moltiplicare che con la componente c2 del testo di cifratura. Così che l'effetto di g α   annulla. E avevamo dimostrato che se l'assunzione di DDH detiene, allora questo è CPA sicuro. Quindi ricordati che, abbiamo discusso anche in una delle nostre precedenti lezioni la proprietà homomorfe dei cifrari El Gamal. Quindi El Gamal ciphers, quindi che cosa intendiamo esattamente che, supponiamo di ricevere la crittografia cm di qualche messaggio sconosciuto m, allora come per la sintassi del cifrario El Gamal cm consisterà in due elementi di gruppo. Il primo elemento di gruppo sarà di alcuni g β (uknonwn β) e il secondo componente sarà il testo di pianura sconosciuto m moltiplicato per g α β Ora se prendiamo il testo di cifratura e prendiamo il secondo componente del testo di cifratura e lo moltiplichiamo per qualsiasi valore c dal gruppo. Poi quello che otteniamo è in sostanza un nuovo testo di cifratura composto da due elementi di gruppo, che possono essere considerati come crittografia valida El Gamal del messaggio c volte m. Questo significa che il mio processo di crittografia El Gamal è malleabile, perché solo prendendo un testo di cifratura di un messaggio sconosciuto m, posso produrre un testo di cifratura di un messaggio correlato cioè i tempi c m dove c mi è noto, ma il m non mi è noto, semplicemente eseguendo alcune operazioni locali e si scopre che, se il mio processo di codifica è malleabile, allora non possiamo mai sperare che possa essere il CCA sicuro e lo dimostrerò con un esempio qui. (Riferirsi Slide Time: 04.05) Immaginate, c'è un politempo avversario arbitrario, che partecipa ad un'istanza di gioco CCA contro il cifrario El Gamal. Così come per le regole del gioco, lo sfidante lancerà la chiave pubblica all'avversario, dove il tasto pubblico u è g α dove α non è noto. Quello che fa l'avversario, ci vuole una coppia arbitraria di testo semplice del gruppo. La sfida è preparata dallo sfidante raccogliendo m0 o m1 per la crittografia. E sottopone un testo di impugnatura di sfida c * all'avversario e quello che ora fa l'avversario è, sa che il testo della sfida cifrata, che consiste in due elementi di gruppo ha questa struttura: 1 ← e 2 ←. , dove β non vi è nota, l'effettivo mb non è noto ad esso e g α β non è noto, ma ciò che l'avversario può fare è, può scegliere qualche arbitrario x dal gruppo e può sfruttare la proprietà di malleabilità del testo di cifratura di El Gamal. E può ora produrre qualche testo di codifica modificato come c, che ora è una crittografia del messaggio x volte il messaggio sconosciuto mb e ciò che l'avversario ora fa è, chiede il servizio di oracolo di decodifica per questo testo di codifica modificato c, consentito come per le regole del gioco CCA. Ora lo sfidante deve decodificare questo testo di cifratura modificato c e su decriptarlo, si butta indietro x * mb all'avversario. Ora che l'avversario conosce il valore di x e x appartiene al gruppo, può calcolare l'inverso moltiplicativo del valore x e a moltiplicarlo con m, può identificare completamente ciò che mb e da qui può presentare il giusto b e come potete vedere che la probabilità che questa strategia avversaria vinca il gioco, il gioco CCA è esattamente 1. Questo significa che il mio cifrario El Gamal non è sicuro del CCA. È solo CPA sicuro. Appena criptiamo qualche messaggio usando la cifratura di El Gamal e se siamo nel modello adversariale malevolo usando l'ausilio del servizio di oracolo di decodifica, l'avversario può assolutamente scoprire cosa esattamente è crittografato. (Riferirsi Slide Time: 06.20) Quindi questo significa, ora dobbiamo pensare che come possiamo progettare una CCA sicura instantificazione di El Gamal cipher, quindi quello che faremo è invece di vedere una versione sicura del codice di El Gamal, stiamo andando a vedere una variante sicura del cifrario di El Gamal e per questo ci instaura un CCA sicuro KEM sicuro basato su problemi di Diffie - Hellman. Quindi ricordati il meccanismo di incapsulamento della chiave sicura CPA basato sull'assunzione di CDH nel modello di oracolo casuale, che avevamo discusso in una delle lezioni precedenti. Quindi immagina Sita voglia di impostare la chiave per il suo meccanismo di incapsulamento chiave. Quindi quello che fa è, fa la sua parte del protocollo di scambio delle chiavi Diffie - Hellman una volta per tutti scegliendo un α casuale, che è impostato come sua chiave segreta e facendo g α come sua chiave pubblica. Questo può essere considerato, questo messaggio g α può essere considerato un messaggio una volta per tutti per ogni potenziale mittente che vuole comunicare a lei e ora se c'è una Ram che vuole incapsulare la chiave, allora l'algoritmo di incapsulamento per Ram sarà il seguente. Ram farà la sua parte del protocollo di scambio delle chiavi Diffie - Hellman scegliendo un β casuale e il computing g β questo è l'incapsulamento. E la chiave, che Ram ottiene o che è considerata incapsulata in questo incapsulamento c è sostanzialmente l'output di (pk) β valutato sotto la funzione di derivazione chiave, disponibile pubblicamente, dove la sottostante funzione di derivazione chiave deriva dal gruppo ciclico g, allo spazio chiave di qualche schema di codifica di chiave simmetrica sottostante. Per decapsulare c, quello che Sita deve fare è, deve fare la sua parte del protocollo di scambio delle chiavi Diffie - Hellman per ottenere il tasto comune g α β e ottenere l'output della funzione di derivazione chiave su quella g α β e poi potrà ottenere indietro la stessa chiave k. Avevamo dimostrato che nel modello di oracolo casuale, se supponiamo che il problema CDH sia difficile da risolvere nel gruppo sottostante, allora il meccanismo di incapsulamento di cui sopra è CPA garantite. Ma si scopre che lo stesso meccanismo di incapsulamento chiave non è il CCA sicuro, anche se siamo nel modello di oracolo casuale. Questo perché se supponiamo che ci sia un avversario politempo, che partecipa ad un'istanza di gioco CCA contro il meccanismo di incapsulamento di cui sopra, allora il gioco cercherà qualcosa come segue. Lo sfidante genererà la chiave segreta e una chiave pubblica e utilizzando la chiave pubblica, eseguirà un incapsulamento per ottenere l'incapsulamento c e la chiave incapsulata k. E preparerà la sfida lanciando, lanciando una moneta equa e la sfida per l'avversario sarà u, c, e e l'obiettivo dell'avversario è quello di identificare se viene generato come per il metodo b pari a 0 o come per il metodo b pari a 1. Ma visto che siamo nel mondo CCA, l'avversario è ora autorizzato ad avere accesso al servizio di oracolo di decapsulamento. Ovvero può presentare qualsiasi incapsulamento c, che sia diverso da c e c la decapsulazione del resultante c. Quindi quello che ora l'avversario può fare è, può scegliere arbitrariamente qualche elemento c del gruppo e dire che è un po' di g β e insieme a quello, picchia qualche elemento casuale z dal gruppo e non solo, calcola anche l'output della funzione di derivazione chiave su quell' elemento scelto casualmente z per ottenere la chiave k. Ora da quando l'avversario è autorizzato ad avere il servizio di oracolo di decapsulamento, può chiedere la decapsulazione di c. Dal momento che c 'viene scelto casualmente dal gruppo, molto probabilmente c' sarà diverso da c. Anche se non è diverso da c, ciò che gli avversari possono fare è, può continuare a scegliere casualmente c e molto probabilmente c) sarà diverso da c non appena ottiene il c. diverso da c, chiede la decapsulazione di c. E in risposta lo sfidante uscirà questo k, e se si vede la sintassi dell'algoritmo di decapsulamento, questo valore k non è altro che l'output della funzione di derivazione chiave sull'input g α β stesso, perché se c) è g β corta, poi per decapsulare c., lo sfidante sta andando in primo compimento g α stesso e poi mappa quell' elemento g α β stesso ad un elemento dello spazio chiave eseguendo, calcolando l'output della funzione di derivazione chiave. Ora ciò che l'avversario può ora fare è, può chiedere il servizio di oracolo di decapsulamento per molti simili c, ovvero può eseguire lo stesso calcolo che ha fatto qui, polinomiale numero di tempo, raccogliendo alcuni casuali c, random z., calcolando il k che corrisponde a scegliere z e chiedendo il servizio di decapsulamento della componente c. e ora una volta che è polinomicamente addestrato, può presentare la sua risposta, sia generata come per il metodo b pari a 0 o come per il metodo b pari a 1. Ora forse vi starete chiedendo che quale extra vantaggio l'avversario qui sta ottenendo vedendo la risposta del servizio di oracolo di decapsulamento. Se vedete da vicino qui, vedendo la risposta del servizio di oracolo di decapsulamento, l'avversario arriva a imparare se la tripletta (u, c, c, z) è una tripletta DDH o meno. Più precisamente, se la risposta del servizio di decapsulamento per c bis restituisce la chiave k, che è diversa dal k del k, che l'avversario ha calcolato, allora avversario sa che sicuramente (u, c, z, z) non costituisce una tripletta DDH. Perché contrapposto, se effettivamente (u, c., z.) è una tripletta DDH, poi sostanzialmente k sarebbe stato uguale a k. D'altra parte, l'avversario sa anche che se k è uguale a k, ovvero la risposta che viene fuori come la risposta dal servizio di oracolo di decapsulamento corrispondente alla query degli avversari è uguale al k, che ha calcolato, poi con altissima probabilità, la tripletta (u, c., z.) costituisce una tripletta DDH. Questo perché se (u, c si, z) non è una tripletta DDH, questo significa, questo z è diverso da g α β stesso, poi è molto improbabile che la funzione di derivazione chiave su due diversi input sia g α β stesso e qualche g γ in cui γ times β ti dà la stessa uscita e questo vale, perché siamo nel modello casuale oracolo, dove la funzione di derivazione chiave si sta comportando come una funzione davvero casuale. Quindi questo significa, quello che possiamo ora vedere qui è che il modo avversario sta raccogliendo il suo servizio di oracolo di decapsulamento e facendo qualche calcolo locale poi confrontando la risposta dal servizio di oracolo di decapsulamento, sostanzialmente l'avversario ha ottenuto un accesso al solutore DDH, che gli dice se una tripletta presentata costituisca o meno una tripletta DDH. Il che significa, proprio in base all'assunzione del CDH e del modello di oracolo casuale, non possiamo dimostrare che questa costruzione di meccanismo di incapsulamento chiave sia il CCA sicuro. Perché attraverso il servizio di oracolo di decapsulamento, l'avversario sta ora ottenendo l'accesso al solutore DDH e che ci spinge ad ora definire una nuova supposizione. (Riferimento Slide Time: 14 :47) O un nuovo problema hard, che chiamiamo come gap computazionale Diffie-Hellmen problem o gap computazionale Diffie - Hellman presupposto e intuito sottostante a questo presupposto è che ci chiediamo che il problema CDH sia difficile da risolvere nel mio gruppo sottostante, anche se un avversario ha avuto l'accesso oracolo ad un solutore DDH. Sottolineo qui che ha ottenuto solo un accesso oracolo al solutore DDH; non ha un politempo; non conosceva i passi esatto di quel solutore DDH. Così il modo in cui lo modelliamo qui è il seguente: chiamiamo questo esperimento come gap - CDH e sostanzialmente lo sfidante prepara un'istanza di problema CDH raccogliendo un random g α e g β in cui α e β casualmente scelte dal set 0 a q – 1 e la sfida per l'avversario è quella di calcolare la funzione Diffie - Hellman di questa u, v pair, ovvero deve compere g α β Ma ora per modellare il fatto che l'avversario ha avuto l'accesso oracolo ad un solutore DDH, consentiamo all'avversario di presentare il numero polinomiale di query della forma (v, w) e in risposta lo sfidante outmette 1, se e solo se lo sfidante trova che questo wcomponente è effettivamente questo v α ovvero questa coppia (v, w) costituisce una tripletta DDH rispetto all'u, che l'avversario ha gettato come una sfida. E l'avversario è ora permesso di fare il numero polinomiale di tali query qui e una volta che ha fatto il numero polinomiale di query, l'obiettivo dell'avversario è quello di calcolare la funzionaria CDH della sfida u, v, che viene lanciata all'avversario, e cioè outmette un elemento di gruppo e la definizione dell'esperimento è dire che l'avversario ha vinto l'esperimento, che noi denunziamo dicendo che la produzione dell'esperimento è di 1, se e solo se l'avversario è correttamente in grado di risolvere il problema CDH, ovvero è effettivamente uguale a g α β Diciamo che il gap di assunzione di CDH detiene nel mio gruppo sottostante g rispetto al quale si gioca questo gioco è per ogni avversario politempo che partecipa a questo esperimento, la probabilità che vinca l'esperimento è delimitata da qualche funzione trascurabile. Vi starete chiedendo che cosa esattamente il gap di prefisso ci indica qui. Ebbene, il gap ci indica qui che vogliamo che un problema CDH sia difficile anche se il problema del DDH è computazionalmente facile da risolvere in quel gruppo. Il che significa, vogliamo catturare l'essenza che c'è un divario tra la difficoltà del problema CDH e il problema del DDH qui e si scopre che ci sono diversi gruppi candidati, dove crediamo che il gap di assunzione di CDH, ovvero il problema del CDH gap effettivamente sia difficile da risolvere. Per esempio, il gruppo basato sui punti sulle curve ellittiche modulo primo è uno di tali candidati. Puoi anche prendere il sottogruppo di primo ordine del gruppo moltiplicativo Zp *. In entrambi questi gruppi candidati crediamo che il presupposto gap - CDH sia in possesso di valori sufficientemente ampi del parametro di sicurezza. (Riferimento Slide Time: 18 :04) Così ora, vediamo come possiamo instanziare meccanismo di incapsulamento chiave sotto il presupposto gap - CDH e si scopre che la costruzione non è una nuova costruzione. La costruzione è esattamente la stessa costruzione, che avevamo visto, quando abbiamo discusso di una CPA sicura di un meccanismo di incapsulamento chiave sotto l'assunzione di CDH e assunzione di DDH. L'unica differenza ora è dato che ora stiamo cercando di modellare un avversario attivo, ogni qualvolta il ricevitore riceve incapsulamento c prima di incapsularlo, basta verificare se l'incapsulamento c è l'elemento di gruppo o meno. Perché idealmente, se effettivamente l'incapsulamento c viene da un party onesto o un mittente onesto, allora come per i passi dell'algoritmo di incapsulamento, il componente c dell'incapsulamento dovrebbe essere un elemento di gruppo. D'altra parte, se c è in realtà in arrivo come interrogazione oracolo di decapsulamento, allora quello che un avversario potrebbe provare a fare è, può chiedere la decapsulazione di un elemento, che non è un elemento del gruppo e se il ricevitore non effettua il controllo della sanita ' e proceda alla cieca per decapsularlo e rimandare l'uscita, allora potrebbe portare a una breccia di sicurezza qui. Ecco quindi l'unico controllo aggiuntivo che stiamo facendo qui. Il resto dei passi per l'algoritmo di generazione della chiave, l'algoritmo di incapsulamento e l'algoritmo di decapsulamento sono esattamente gli stessi, come c'era prima. Ora quello che possiamo provare qui, se il gap di assunzione di CDH detiene nel mio gruppo sottostante, allora questa istanziazione del meccanismo di incapsulamento chiave è il CCA sicuro nel modello di oracolo casuale. E vediamo una panoramica molto alta della prova. Non entreremmo nei dettagli formali. Se siete interessati, potete vedere il libro di Katz & Lindell per i dettagli formali. Quindi se pensiamo ad ogni avversario, un avversario politempo che partecipa al gioco CCA contro questo meccanismo di incapsulamento, allora la mia affermazione è che la decapsulazione, le query di decapsulamento oracolo, sostanzialmente dà l'accesso avversario al solutore DDH e questo avevamo visto prima, giusto. Ma se il mio gap - assunzione di CDH detiene nel gruppo sottostante, giusto, allora vuol dire che anche se l'avversario ottiene l'accesso al solutore DDH implicito, il problema del CDH rimane ancora difficile per l'avversario da risolvere. Questo significa, l'oracolo di decapsulamento, le query di decapsulamento non sono affatto d'uso all'avversario. Non lo aiuterebbe a risolvere il problema del CDH e ora quello che in sostanza stiamo facendo qui è sostanzialmente dato che le query di decapsulamento non sono di aiuto per l'avversario, allora sappiamo già che in assenza di query di decapsulamento un'istanza di gioco CCA contro il meccanismo di incapsulamento chiave è esattamente la stessa di una ricorrenza del gioco CPA contro lo stesso meccanismo di incapsulamento chiave, che avevamo già dimostrato essere CPA sicuri sotto l'assunzione di CDH nel modello casuale oracolo. Il che significa, non dobbiamo aggiungere passi sofisticati in questo meccanismo di incapsulamento chiave esistente per renderlo sicuro CCA. Quello che dobbiamo solo garantire è che, instanziamo i passi dell'algoritmo di incapsulamento e di decapsulamento in un gruppo in cui il gap di assunzione di CDH e nell'assunzione di gap ci tiene, siamo al sicuro perché il servizio di oracolo di decapsulamento è completamente inutile per l'avversario e non ottiene alcun vantaggio aggiuntivo rispetto a un avversario CPA. (Riferimento Slide Time: 21.54) Quindi questo significa che ora abbiamo un'istanziazione di meccanismo di incapsulamento sicuro di CCA, quindi quello che faremo è utilizzarlo per arrivare con CCA versioni ibride sicure di cifrature di chiave pubblica basate su problemi Diffie - Hellman e ci sono due instantiazioni ben note di questo quadro, una si chiama DHIES ed ECIES e l'idea qui è sostanzialmente quella di utilizzare il framework generico che avevamo discusso nell'ultima lezione. Dove abbiamo visto che se ci viene dato un meccanismo di incapsulamento sicuro CCA e se ci viene dato un processo di codifica simmetrico sicuro CCA, allora il processo di codifica ibrida che ne deriva è protetto da CCA. Quello che dobbiamo praticamente ora fare è, dobbiamo inventarci con CCA la instantizzazione sicura del meccanismo di incapsulamento chiave. Quindi quello che possiamo fare è, possiamo usare il meccanismo di incapsulamento chiave, che è il CCA sicuro in base all'assunzione di gap - CDH, che avevamo appena visto ora. E per istanziare la crittografia della chiave simmetrica sicura CCA, quello che possiamo fare è, possiamo utilizzare qualsiasi schema di crittografia autenticato, che avevamo visto durante la nostra discussione sul processo di codifica della chiave simmetrica, ovvero possiamo utilizzare la costruzione generica basata sulla crittografia poi autentica, che ci dà sempre la garanzia che lo schema risultante sia uno schema di crittografia autenticato. Ricordate quindi nella cripta quindi l'approccio autenticato, prendiamo un processo di crittografia sicuro CPA, un processo di codifica della chiave simmetrica e un codice di autenticazione dei messaggi sicuro e li combiniamo utilizzando questa codifica quindi autenticata, dove codifichiamo per la prima volta il messaggio utilizzando la crittografia chiave simmetrica CPA sicura e il testo di codifica di codifica risultante viene autenticato come per il codice di autenticazione del messaggio per ottenere il tag. E (testo di cifratura, tag) è considerato il testo di cifratura complessivo e avevamo rigorosamente dimostrato che questo approccio generico ci regala sempre un processo di crittografia simmetrico di crittografia autenticato e sappiamo che nel mondo chiave simmetrico, la crittografia autenticata implica la sicurezza della CCA, perché una delle condizioni per lo schema di crittografia autenticata per essere soddisfatte è che, dovrebbe avere la nozione di sicurezza CCA. Per istanziare questa crittografia chiave simmetrica protetta da CCA, possiamo utilizzare qualsiasi schema di crittografia autenticato. Così ora, abbiamo istanziato entrambi i gadget di cui abbiamo bisogno nel nostro schema di crittografia ibrida. Se usiamo queste due istanziazioni, otteniamo quello che chiamiamo schema di codifica integrato Diffie - Hellman o DHIES in breve e quando instanziamo questo DHIES dove il gruppo sottostante si basa sui punti sulla curva ellittica, allora l'istanziazione del DHIES risultante è chiamata ECIES, ovvero schema di codifica integrato ellittico. Si tratta di due standard ben noti, che vengono utilizzati in pratica per instanziare, i cifrati chiave pubblici ibridi basati su problemi di Diffie - Hellman. Così questo mi porta alla fine di questa lezione. Tanto per riepilogare, in questa lezione, abbiamo assistito a instanziamenti di meccanismo di incapsulamento sicuro di CCA. Per questo abbiamo introdotto una nozione di gap - CDH e gap - ipotesi CDH e avevamo visto che se combinassimo un KEM sicuro di CCA basato sull'assunzione di gap - CDH insieme a qualsiasi schema di crittografia autenticato nel mondo della chiave simmetrica, che è la chiave simmetrica, allora la costruzione risultante ci dà il processo di crittografia sicuro del CCA, che chiamiamo come