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 Dr. Ashish Choudhury Department of Computer Science International Institute of Information Technology – Bangalore Collezione – 47 Hybrid Public Key Cryptosystem Welcome to this lecture. Il piano per questa lezione è il seguente. (Riferimento Slide Time: 00.36) In questa lezione introdurremo lo schema di crittografia - chiave Hybrid e introdurremo il paradigma KEM/DEM, e vedremo una instanziazione di KEM basato su CDH nel modello di oracolo di Random e la creazione di DDH di KEM nel modello standard. (Riferimento Slide Time: 00 :49) Quindi, lasciate che i signori inizi con la motivazione di Hybrid Public - Key Ciphers e prima di farlo, confrontiamo lo schema di crittografia a chiave pubblica con uno schema di crittografia a chiave segreta. Immaginate, ci viene dato uno schema di crittografia a chiave pubblica, Π pub, e ci viene dato uno schema di crittografia simmetrica, Π priv, poi se consideriamo lo schema di crittografia a chiave pubblica, l'accordo chiave non è affatto una sfida. Ecco qual è l'intera motivazione per la nascita del processo di crittografia pubblica. Se sono un ricevitore è sufficiente per me solo annunciare la mia chiave pubblica nel dominio pubblico. Chi vuole criptare un messaggio e inviarlo a me, può scegliere la mia chiave pubblica, crittografare il messaggio e inviarlo a me. D'altra parte avevamo visto che l'accordo chiave è la più grande sfida nel dominio delle chiavi simmetriche. Fino a quando e a meno che non si stabilisse la chiave comune tra il mittente e il destinatario, non possiamo utilizzare nessuno dei primitivi della chiave simmetrica. Se consideriamo lo schema di crittografia a chiave pubblica, il lato negativo c'è lo spazio dei messaggi deve essere un gruppo finito o una struttura algebrica finita, che la maggior parte dei casi è il gruppo, che è una sorta di restrizione perché, in pratica, lo spazio dei messaggi dovrebbe essere una stringa di bit. D'altra parte, lo spazio dei messaggi nella parola chiave simmetrica sono stringhe binarie. Non richiediamo alcuna sofisticata struttura algebrica dallo spazio di messaggio sottostante per la sicurezza complessiva dei miei schemi di crittografia dei tasti simmetrici. Se consideriamo schemi di crittografia a chiave pubblica, sono computazionalmente molto pesanti perché dobbiamo eseguire ampliamenti modulari per l'istanza nella funzione RSA e nello schema di codifica El Gamal. L'esecuzione di exponentiations modulare è molto computazionalmente costosa e pesante rispetto al processo di codifica, processo di decodifica che utilizziamo in schema di codifica a chiave simmetrica, che sono superveloci ed eseguono operazioni che sono di operazioni XOR. Allo stesso modo, lo schema di crittografia a chiave pubblica, l'espansione del testo di cifratura è enorme, per esempio, se si vede lo schema di crittografia El Gamal, il testo di pianura che si desidera crittografare è un elemento di gruppo unico, ma il testo di cifratura è composto da due elementi di gruppi e paggiunta RSA, la quantità di messaggio, che si finisce per crittografare è molto breve rispetto alla quantità di casualità che si sta effettivamente imbottendo. D'altra parte, nel mondo della chiave simmetrica, l'espansione del testo di cifratura può essere il più possibile minimale utilizzando una qualsiasi delle così chiamate modalità sicure di funzionamento dei cifrari di blocco. Quindi, ora possiamo vedere avere entrambi i pro come i contro dello schema di crittografia a chiave pubblica, schemi di crittografia simmetrica e quello che possiamo fare è, possiamo pensare di combinare in qualche modo questi due processi in una moda generica e ottenere un tipo di codifica ibrida dove nel processo di codifica ibrida, che chiamiamo EncHyb. Il mittente sceglie una chiave casuale per lo schema di crittografia dei tasti simmetrici e la codifica utilizzando il processo di crittografia a chiave pubblica, ovvero codifica il tasto casuale k, che ha selezionato e crittografa utilizzando la chiave pubblica del destinatario e una volta che il testo in pianura è disponibile con il mittente, la crittografia effettiva del testo di pianura avviene utilizzando un processo di codifica a chiave simmetrica che utilizza la chiave casuale, scelta dal mittente. Se lo facciamo, quello che sta accadendo qui è sostanzialmente l'intera efficienza del processo di codifica ibrida diventa quasi quello del processo di codifica della chiave simmetrica perché il messaggio reale che stiamo crittografando viene crittografato utilizzando un processo di codifica a chiave simmetrica. Il carico extra pay che stiamo pagando qui è quello di crittografare la chiave simmetrica che viene utilizzata per cifrare il testo di pianura reale utilizzando un processo di crittografia a chiave pubblica. Tuttavia in linea di principio sintatticamente questo intero processo ibrido sarà ancora considerato come un'istanza di processo di codifica di chiave pubblica perché la chiave per la crittografia della chiave simmetrica che il mittente sta utilizzando viene crittografata da un processo di crittografia a chiave pubblica. Ecco, ecco qual è la motivazione complessiva per progettare Hybrid Public - Key Ciphers. (Riferimento Slide Time: 5.01) Per rendere più chiaro il mio punto, consideriamo un'istanza di Hybrid El Gamal - key Cipher. Allora, fatemi ricordare la sintassi di Hybrid El Gamal public-key cipher, diciamo Seetha vuole dire di impostare per il suo parametro pubblico, la sua chiave pubblica e la chiave segreta, così la descrizione pubblica, a disposizione di tutti è la descrizione del gruppo ciclico, del generatore e delle dimensioni del gruppo. Per fare il setup della chiave, quello che Seetha fa è, immaginate di fare la sua parte di protocollo di scambio chiave Diffie Hellman una volta per tutte per ogni potenziale Ram. Per ogni potenziale mittente che vuole criptare un messaggio e inviare a Seetha. Così, lei picchia il suo casuale α dal set Zq ovvero da 0 a q-1, e cioè una chiave segreta e una chiave pubblica, che è g α che è disponibile in ambito pubblico, e questo se si può immaginare come Seetha il contributo per la chiave generale Diffie - Hellman, che vuole stabilire con ogni potenziale mittente in questo mondo. Ora immagina che ci sia un mittente, che ha un testo semplice m, che vuole criptare e ora questo testo di pianura è un po' stringa, non serve essere un elemento di gruppo. Quindi, a differenza del processo di crittografia di El Gamal dove il testo di pianura reale, che il mittente potrebbe criptare e inviare a Seetha dovrebbe essere un elemento di gruppo, ora il testo pianeggiante è un po' string. Ora, per criptare questo testo di pianura m, quello che fa il mittente, picchia un elemento casuale del gruppo che vengono notati da e codifica questo messaggio utilizzando il processo di codifica di El Gamal. Così, calcola il testo di cifratura c1, c2 dove c1 può essere interpretato come mittente del mittente il contributo per il protocollo di scambio chiavi Diffie - Hellman, ovvero g β, dove β è una codifica casuale di questo casuale utilizzando il comune Diffie - Hellman key g α β Ora, non è la crittografia del messaggio, quindi fino ad ora quello che mittente ha fatto in sostanza il c1, c2, quel mittente ha inviato a Seetha è una crittografia del casuale, ma l'obiettivo del mittente è quello di criptare il testo di pianura m, quindi quello che facciamo qui è ipotizziamo che a parte la descrizione del gruppo ciclico, del generatore, dell'ordine di gruppo e così via, supponiamo di avere una descrizione di una funzione di derivazione chiave H pubblicamente disponibile e supponiamo che la funzione di derivazione chiave associa gli elementi dal gruppo g allo spazio chiave dello schema di crittografia dei tasti simmetrici, che il mittente stia ora utilizzando. Quindi ora, quello che il mittente sta per fare, il mittente sa che inviando c1, c2, a Seetha. Sender sa che Seetha finirà anche per ottenere il tasto comune g α β e assumendo l'assunzione di DDH è vero nel gruppo sottostante, questo tasto g α β sarà un elemento casuale dal gruppo dal punto di vista di un avversario computazionato. Quindi ciò che il mittente può ora fare è, può derivare un bit di stringa di bit per il processo di crittografia simmetrica applicando una funzione di derivazione chiave a questo elemento casuale e tale tasto viene utilizzato per ora crittografare il testo di pianura m, che è una stringa di bit e che è una codifica effettiva del testo di pianura m, che il mittente vuole criptare. La decodifica a Seetha s fine avviene come segue. Quindi per la decodifica, Seetha ha anche bisogno di recuperare lo stesso, che il mittente ha usato per ricavare la chiave simmetrica k e può essere ottenuto decodificando c1, c2 come per la sintassi dello schema di crittografia El Gamal e una volta recuperato da Seetha, ciò che Seetha può fare, può anche applicare la stessa funzione di derivazione chiave pubblicamente disponibile su e una volta recuperata, può decodificare la componente c del testo di cifratura come per l'algoritmo di decodifica del processo di codifica della chiave simmetrica e recuperare m. Ecco, ecco come si può interpretare una versione ibrida di El Gamal public-key cipher. Così pittoricamente quello che sta accadendo è qui che come ho detto prima c1, c2 è la crittografia a chiave pubblica della chiave simmetrica, mentre il componente c qui è la crittografia a chiave privata effettiva del testo di pianura. Tuttavia, se si mette in pausa qui per un attimo, l'idea di criptare l'elemento del gruppo casuale per mittente e derivare una chiave da esso è un overkill. Quindi, quello che sta accadendo qui è che il mittente sta usando un elemento di gruppo casuale, crittografandolo nel suo insieme utilizzando il processo di crittografia El Gamal, e poi derivando che una chiave simmetrica. Ecco quindi un overkill qui. Una stretta osservazione ti dice che è sufficiente che il mittente solo invii g β Non deve essere necessario inviare c2. È sufficiente per il mittente solo inviare g β. Perché il mittente sa che se invia g β che può essere revisionati come se mittente stia inviando la sua parte del messaggio di protocollo di scambio chiave Diffie - Hellman, allora sa che inviando g β, sia Seetha che Ram finiranno per concordare su g α e supponendo che l'assunzione di DDH sia vera nel gruppo sottostante, sappiamo che g α β sarà casuale nel punto di vista dell'avversario.Da qui la chiave k può derivare dal g α β invece di derivare la chiave dall'elemento casuale, perché se facciamo questo invece di usare l'approccio che abbiamo visto fino ad ora, facciamo un risparmio qui. Non dobbiamo scegliere l'elemento casuale e non abbiamo bisogno di criptare, di qui non abbiamo bisogno di inviare c2, e la dimensione complessiva del testo di cifratura si ridurrà in modo significativo e che porterà anche a risparmiare anche nella larghezza di banda, perché se non avremo bisogno di inviare il c2 significa non dover inviare un elemento extra di gruppo per crittografare il messaggio. (Riferirsi Slide Time: 11.22) Anche se abbiamo visto una instantificazione di Hybrid El Gamal cifrata qui, si scopre che questo approccio è un overkill. Quindi quello che faremo ora, dato che ora siamo motivati dalla discussione qui che, basti pensare al mittente qui per inviare solo g β e ricavare una chiave da g β, quello che faremo è ora ricavare un nuovo primitivo, che chiamiamo come Key - Encapsulation mechanism o KEM e poi vedremo che come possiamo ottenere una crittografia Hybrid più efficiente usando questo KEM. Quindi, per rendere il mio punto chiaro il via libera di Hybrid encryption che abbiamo visto ora è solo nel contesto di Hybrid El Gamal è il seguente. Così, alla fine della crittografia quello che stavamo facendo è il mittente stava raccogliendo un tasto casuale per la chiave simmetrica ed è stato codificato dalla chiave pubblica del ricevitore per ricavare il testo di cifratura c, che può essere considerato come una crittografia della chiave simmetrica. E la crittografia effettiva del messaggio è stata fatta usando la chiave k e questo è stato tipo un approccio di due stadi, dove prima sceglievamo la nostra chiave simmetrica casuale e poi la utilizzavamo per il processo di crittografia a chiave pubblica. Un approccio più efficiente sarà fatto usando un primitivo, che definiremo presto che chiamiamo meccanismo di incapsulamento chiave in cui entrambe queste due cose vengono fatte in un solo colpo in una sola tappa. E il vantaggio qui è che non solo è concettualmente più semplice, ma in molti casi è più efficiente e capire che esattamente come KEM sarà efficiente rispetto a questo approccio di due stadi, si può vedere quello che abbiamo visto proprio ora nel contesto di Hybrid El Gamal. Il modo na ï vela di implementare El Gamal il mittente stava raccogliendo un casuale derivando la chiave ed è stato interamente crittografato utilizzando il processo di codifica di El Gamal. Ma poi abbiamo sostenuto che il mittente non ha bisogno di farlo. Può realizzare Hybrid Encryption anche solo inviando g β al destinatario. Ora, è sufficiente che la funzione di derivazione chiave sottostante sia un tipo di funzione speciale, che distribuisce l'elemento di gruppo quasi uniformemente tra gli elementi dello spazio chiave del processo di codifica della chiave simmetrica. Quello che intendo dire con questo è, se considero questo il mio gruppo g, e se questo è il mio set K, e il numero di elementi, che si associano a un elemento candidato da questo spazio chiave, il numero di elementi di gruppo che si associano a questo elemento candidato da questo spazio chiave dovrebbe quasi essere lo stesso. Non ci dovrebbero essere bias nella distribuzione o nella mappatura mediante la quale questa funzione H sta mappando gli elementi del gruppo agli elementi dello spazio chiave del mio processo di codifica della chiave simmetrica. Se presumo che la mia funzione di derivazione chiave sottostante abbia quel tipo di effetto livellante, allora è sufficiente per me rimanere solo nel modello standard e rivendicare la sicurezza di questo meccanismo di incapsulamento chiave, proprio partendo dall'assunzione di DDH. Ora, si può vedere l'importanza delle ipotesi che stiamo facendo durante tutto questo corso. La stessa costruzione qui può essere dimostrata sicura in con ipotesi di durezza più deboli, ovvero l'assunzione di CDH. Ma con proprietà più potenti dalla funzione hash sottostante, cioè supponendo che si stia comportando come un Random - oracolo mentre se non si desidera modellare la propria funzione hash sottostante come un Random - oracolo, si desidera modellarlo come un tipo speciale di funzione di distribuzione liscia, allora è necessario avere un presupposto di durezza più forte nel gruppo sottostante, ovvero è necessario avere il problema del DDH difficile da risolvere nel gruppo sottostante. Quindi, questo mi porta alla fine di questa lezione. Tanto per riassumere in questa lezione abbiamo introdotto il processo di codifica Hybrid e abbiamo discusso della CPA - security of Hybrid encryption process. Abbiamo anche visto una generica costruzione di come combinare un meccanismo di incapsulamento chiavi CPA sicuro o COA insieme a qualsiasi tasto simmetrico sicuro COA