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)Così 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) Quindi 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 configurazione sicura CCA di cifratura di El Gamal, quindi quello che faremo è invece di vedere una versione sicura CCA di cifratura di El Gamal, stiamo andando a vedere una variante sicura del cifrario di El Gamal e per questo che cosa faremo è, instanziamo un CCA sicuro KEM basato su problemi Diffie - Hellman. Quindi, ricordiamo il meccanismo di incapsulamento della chiave 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 ciò che l'avversario può ora fare è, può scegliere arbitrariamente qualche elemento c dal gruppo e dire che è qualche g βnando 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 casualmente scelto zdi per ottenere la chiave k. Ora che l'avversario è autorizzato ad avere il servizio di oracolo di decapsulamento, può chiedere la decapsulazione di c. Dal momento che c è 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 α β , perché se c è g β , quindi per decapsulare c, lo sfidante sta andando in primo compimento g α e poi mappa quell' elemento g α β ad un elemento dello spazio chiave eseguendo, calcolando l'output della derivazione chiave funzione. 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, computing il k corrispondente a scegliere z e chiedendo il servizio di decapsulamento del componente c e ora una volta che è polinomicamente addestrato, può presentare la sua risposta, sia generato come per il metodo b uguale 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, z) è una tripletta DDH o meno. Più precisamente, se la risposta del servizio di decapsulamento per c restituisce il tasto k, che è diverso dal k, che l'avversario ha calcolato, poi l'avversario sa che sicuramente (u, c, 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 km è uguale a k, ovvero la risposta che viene fuori come la risposta dal servizio di oracolo di decapsulamento corrispondente alla query degli avversari è lo stesso della k, che ha calcolato, quindi con altissima probabilità, la tripletta (u, c, zmt) costituisce una tripletta DDH. Questo perché se (u, c, z) non è una tripletta DDH, questo significa, questo zm è diverso da g α β , allora è molto improbabile che la funzione di derivazione chiave su due diversi input sia g αaccedi e alcuni g γ, dove γ 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. (Riferirsi 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 richiediamo 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. (Riferirsi 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. (Riferirsi Slide Time: 21.54) Quindi questo significa che ora abbiamo un'istanziazione di meccanismo di incapsulamento sicuro CCA, quindi quello che stiamo per fare è, lo useremo 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
 
 
Fondamenti di crittografia Dr. Ashish Choudhury Department of Computer Science Indian Institute of Science - Bangalore Lecture - 50 CCA Secure Public Key Ciphers Based on RSA Presupposto (Riferimento Slide Time: 00.30) Ciao a tutti. Benvenuti a questa lezione. Tanto per ricapitolarci, nell'ultima lezione avevamo discusso di CCA le instantiazioni sicure di cifrature a chiave pubblica basate sui problemi di Diffie - Hellman. In questa lezione il nostro obiettivo è vedere le instantiazioni sicure di CCA di crittografi a chiave pubblica in base alle ipotesi RSA, nello specifico la roadmap per questa lezione è la seguente: vedremo la malleabilità della pianura RSA, che dimostrerà che la pianura RSA non è sicura del CCA. E valuteremo la versione imbottita di RSA e dimostreremo la sua insicurezza CCA, ovvero vedremo un attacco molto interessante, che chiamiamo come attacco di Bleichenbacher e poi vedremo un candidato CCA sicuro instanziamento di crittografia a chiave pubblica basato sull'assunzione di RSA, ovvero RSA OAEP. (Riferimento Slide Time: 01.12)Così ricordiamo la costruzione di plain RSA public key cipher from RSA one-way trapdoor permutation. Quindi si ha lo schema di permutazione di RSA trapdoor, che ha il suo algoritmo di generazione chiavi. In sostanza, l'algoritmo di generazione della chiave sceglie uniformemente numeri di n - bit casuali, p e q e calcola il modulo N, che è il prodotto di p e q. Poi, dato p e q, calcola il valore di (), ovvero | Zoes |. Poi, picchi e > 1, tale che gcd (e, ()) = 1 e poi dato che gcd (e, ()) = 1, possiamo calcolare l'inverso moltiplicativo di e denota come d,. Poi, infine, abbiamo fissato (N, e) a essere la chiave pubblica e (N, d) a essere la chiave segreta. La funzione RSA è una mappatura da ZERO ⇒ Zetteria e per calcolare il valore della funzione RSA su alcuni input x, praticamente compaiamo xe modulo N. D'altra parte, se si desidera calcolare la funzione inversa RSA, allora si tratta di una mappatura da Zaia ⇒ Zacchini operato con la chiave segreta (N, d). Per calcolare il valore della funzione inversa su qualche input y, yd modulo N. Poi, in base a ciò avevamo visto una instantizzazione dello schema di crittografia a chiave pubblica, che chiamiamo come semplice codifica RSA, dove l'algoritmo di generazione chiavi della pianura RSA è sostanzialmente quello di eseguire l'algoritmo di generazione chiavi del sistema di permutazione intrappolato RSA. E impostare (N, e) alla chiave di codifica e (N, d) ad essere la chiave di decodifica. Se c'è un mittente, che vuole criptare un testo di pianura semplice, allora usando la chiave pubblica (N, e), può produrre testo di codifica RSA, che sono io modulo n e il destinatario che ottiene il testo di cifratura c su possessione della chiave segreta (N, d) può decodificare un testo di cifratura mediante calcolo yd modulo N. (Fare Slide Time: 03.17) Ora quello che vedremo è la malleabilità del cifrario in chiave pubblica RSA. Allora, ricordate quando abbiamo introdotto una RSA di pianura, abbiamo visto che la crittografia RSA sicuramente non fornisce sicurezza CPA, perché non è casuale. Se si codifica lo stesso testo semplice più volte utilizzando la stessa chiave pubblica, si otterrà lo stesso testo di codifica. Non solo, non possiamo ridurre la sicurezza della crittografia RSA direttamente alla durezza del problema RSA perché il problema RSA richiede che il sottostante m debba essere un elemento casuale da Z, ma quando si instaura cifratura RSA, il sottostante testo di pianura, che mittente è crittografato potrebbe non essere un elemento casuale da Zaia. E non solo, abbiamo anche discusso che anche se non puntiamo sulla sicurezza semantica, cioè per noi è sufficiente se l'avversario non impara l'intero testo di pianura sottostante nella sua interezza e ne siamo contenti. Poi, anche in quel caso, ci sono diversi possibili attacchi, che possono essere persi sulla pianura chiave pubblica RSA. Quindi, quello di cui ora discuteremo è, andiamo a considerare lo stesso requisito cioè dire, siamo contenti di tutto o di niente di sicuro. Non puntiamo sulla sicurezza semantica a base di indistinguibilità.