Loading
Note di Apprendimento
Study Reminders
Support
Text Version

Protocolli Di Scambio Chiavi

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 Indian Institute of Science – Bangalore Collezione – 36 Key Exchange Protocolli Part 1 (Riferirsi Slide Time: 00.35) Ciao a tutti, benvenuti a questa lezione. il piano per questa lezione è il seguente, in questa lezione introdurremo la nozione di protocolli di scambio di chiavi anonimi. Vedremo le varie definizioni e vedremo le idee sottostanti coinvolte dietro il protocollo di scambio chiave seminale a causa del Diffie e dell'Hellman. (Riferimento Slide Time: 00 :47) Così giusto per recap, il quadro fino ad ora è il seguente. Fino ad ora avevamo visto diversi potenti primitivi simmetrici, sia nel mondo passivo che nel mondo attivo. Abbiamo visto varie nozioni di sicurezza, come crittografia autenticata, sicurezza CCA, sicurezza CPA; avevamo visto altri primitivi per integrità e autenticazioni come il codice di autenticazione dei messaggi. E avevamo visto costruzioni di tutte queste nozioni di sicurezza, dove le costruzioni si basano su funzioni pseudo casuali, pseudo permutazioni casuali, forti permutazioni casuali e così via. Quindi un fatto fondamentale su tutte le costruzioni che avevamo visto fino ad ora è che la sicurezza per tutti questi primitivi crittografici che abbiamo visto, detiene nell'ipotesi che una chiave comune casuale sconosciuta sia già concordata tra le parti, nello specifico il mittente e il destinatario. Quindi ora la domanda che vogliamo affrontare qui è che come una chiave casuale comune sia concordata privatamente su un canale pubblico insicuro? Quindi fino ad ora stavamo ipotizzando che in qualche modo l'accordo chiave sia già accaduto e dato che l'accordo chiave è già accaduto, abbiamo visto come progettare schemi di crittografia autenticati, schemi di crittografia sicuri CCA, schemi di crittografia sicuri CPA e così via. Ma ora vorremmo affrontare il problema principale. Vorremmo affrontare la questione che come al primo posto in sé, una chiave casuale è concordata privatamente su un canale pubblico e insicuro. E questo suona come una classica situazione catch-22 giusto? Perché se si dispone di un meccanismo in cui il mittente e il destinatario possono scambiare in modo sicuro una chiave sconosciuta che è nota solo al mittente e al destinatario su un canale insicuro pubblico, quindi utilizzando quel meccanismo, essi al primo posto stesso possono fare anche la comunicazione sicura. Quindi cosa significa esattamente 22 situazione di situazione, dove si ha uno scenario, dove si dice ad esempio che si è laureati freschi, esce dal collegio e si applica per un lavoro e quando il candidato affronta il colloquio di lavoro, affronta la domanda che si ha qualche esperienza o no? Ma al primo posto il candidato otterrà esperienza solo se il lavoro è affidato al candidato. Ecco cosa intendiamo per situazione catch-22. E ci troviamo esattamente di fronte allo stesso scenario anche qui. Sappiamo fare comunicazione sicura, assumendo che sappiamo come scambiare in modo sicuro la chiave su un canale insicuro. (Riferimento Slide Time: 03.16) Così che ci porta al problema dello scambio di chiavi anonime. Quindi definiamo qual è esattamente il problema di scambio delle chiavi anonime. Quindi l'impostazione è la seguente: abbiamo un mittente e il destinatario, e supponiamo che in qualche modo, conoscono ogni altra identità di s, ma non hanno avuto informazioni pre - condivise. Quindi vi potreste chiedere come sia possibile per un mittente e il destinatario che si incontrano per la prima volta che conoscono ogni altro soggetto di appartenenza. In seguito rimuoveremo anche questa assunzione. Ma per il momento, per rendere più semplice la descrizione del problema di scambio delle chiavi anonime, supponiamo che sia il mittente che il destinatario conoscano ogni altra entità. Quindi l'obiettivo qui è quello di progettare una coppia di protocolli, che io denota come Π per il mittente, e Π per il destinatario, che sono ormai protocolli interattivi. E lo spazio di uscita di questo protocollo sarà di alcuni e l'obiettivo è quello di progettare una tale coppia di protocolli uno per il mittente e uno per il destinatario tale che secondo i singoli protocolli mittente e destinatario comunino su un canale insicuro e alla fine dei rispettivi protocolli, mittente e ricevente uscita alcune rispettive chiavi. Quindi l'uscita del mittente io denota come e la produzione del ricevitore che denota come. E supponiamo in questa definizione di problema che abbiamo un eavesdropper, un eavesdropper delimitato computazionalmente, che sta ottenendo l'accesso all'intera comunicazione che sta accadendo tra il mittente e il destinatario. Così l'avversario è consapevole della coppia di protocolli che utilizzano il mittente e un ricevitore che interagiscono. Ovvero conosce i passi di Π e Π e ottiene anche l'accesso alle informazioni scambiate tra il mittente e il destinatario, che chiamiamo come trascrizione di protocollo, che denota come. E notate che questa trascrizione di protocollo sarà una variabile casuale, perché le informazioni che mittente e destinatario si scambieranno, dipenderanno dalla casualità interna con cui il mittente e il destinatario ricorreranno nei rispettivi protocolli Π e Π. Quindi non è il caso che mittente e destinatario si scambiano la stessa serie di valori ogni volta che richiamano questo protocollo Π, perché richiamano un protocollo randomizzato. Ora le proprietà che richiedo da questa coppia di protocolli Π e Π sono le seguenti. La prima proprietà è la proprietà di correttezza, che dice che con una probabilità molto alta, le singole uscite del mittente e del destinatario dovrebbero essere le stesse. Ovvero l'output kand output kdovrebbe essere uguale. E ora possiamo avere 2 varianti di sicurezza, che possiamo esigere da questi protocolli Π e Π. La prima definizione è una forma più debole di privacy, che io chiamo come privacy debole, che richiede che con ottime probabilità, un avversario delimitato dal punto di vista computazionale, anche dopo aver conosciuto la trascrizione del protocollo non impara nulla sull'uscita del mittente e del destinatario. Quindi qui non esigo la sicurezza nel senso indistinguibile; qui la domanda è nel senso che o l'avversario non deve imparare l'intero kand l'intero k. Va bene se l'avversario impara “ qualcosa ” su kand k. Ma il requisito qui è che come una interezza, le uscite del mittente e del destinatario non devono essere imparate dall'aggressore. Mentre possiamo andare per una nozione superiore di sicurezza, che io chiamo quella privacy più forte, che pretende che dal punto di vista di quell' avversario, anche se l'avversario ha accesso alla trascrizione del protocollo, dal punto di vista dell'avversario i rispettivi output del mittente e la rispettiva emissione del destinatario, dovrebbe essere computazionalmente distinguibile da un elemento uniformemente casuale dello spazio - chiave di uscita. Ecco allora una nozione più forte di segretezza. Perché se si va per la nozione più forte di segretezza, allora non è consentito che gli avversari imparino qualcosa sui rispettivi bit di kand k; dal punto di vista dell'avversario, i rispettivi output del mittente e del destinatario potrebbero essere qualsiasi elemento candidato dal sottostante - spazio - spazio. Così vedremo costruzione soddisfare sia la forma più debole di privacy che di costruzione che soddisfiano la forma più forte di privacy. Forse vi starete chiedendo perché esattamente ci teniamo a ottenere una forma più debole di privacy. Quindi questo sarà chiaro più avanti. Guardando avanti, vedremo costruzioni ottenendo una forma più debole di privacy, in base ai consumenti crittografici che sono lievi. Mentre se si vuole realizzare protocolli di scambio chiave che raggiungono una nozione più forte di privacy, allora dobbiamo andare per ipotesi crittografiche che sono leggermente più forti. (Riferimento Slide Time: 08 :05) Così avevamo visto intuitivamente cosa significa esattamente la privacy e la privacy. Quindi ora andiamo avanti e modelliamo questi requisiti formalmente da un gioco basato indistinguibile. E pur dando le definizioni indistinguibili, per semplicità supponiamo di considerare i protocolli di scambio chiave che hanno un errore di correttezza di 0 minuti. Il che significa con probabilità 1, la produzione del mittente e dell'output del destinatario sarà la stessa, quindi stiamo considerando quel tipo di protocolli di scambio chiave. Vediamo quindi in primo luogo come modellare la debole - privacy e ricordare il requisito dei deboli stati di privacy anche se l'avversario vede l'intero scambio di trascrizione tra il mittente e il destinatario, la chiave di uscita risultante che viene ottenuta dal mittente e il destinatario non deve essere imparata o non deve essere conosciuta a quell' avversario, nella sua interezza. E questo requisito è modellato da questo gioco. Quindi questo gioco, che chiamiamo KEweav (, qui KE stand per key - exchange e un superscript weav denota deboli eaveschi o la privacy debole, qui il gioco si gioca tra uno sfidante e un avversario in prima persona. E quello che lo sfidante o l'esperimento fa è, in sostanza, simula un'istanza casuale del protocollo di scambio chiavi Π. Quindi il protocollo Π è fondamentalmente la coppia di protocolli e, dove il protocollo verrà invocato dal mittente e il protocollo verrà richiamato dal destinatario. Ma come raccolta la chiamiamo come protocollo. Così lo sfidante sostanzialmente simula un'istanza casuale del protocollo, giocando il ruolo del mittente e di un ricevitore nella sua mente con le rispettive monete come per il protocollo e genera una trascrizione Π. Ora quello che fa è che lancia una sfida all'avversario, ovvero la trascrizione e questo modello il fatto che nel mondo reale, una seduta avversaria tra il mittente e il destinatario, avrebbe osservato una trascrizione generata dal mittente e dal destinatario eseguendo il protocollo. Ora la sfida per l'avversario è che vedendo questa trascrizione Π deve capire qual è esattamente il valore della chiave, che mittente e destinatario avrebbe ottenuto correndo dal rispetto di questa trascrizione di protocollo Π. Quindi praticamente l'avversario deve rispondere con una chiave dallo spazio chiave, che io denota come. E il modo in cui definiamo l'output dell'esperimento è il seguente. Diciamo che l'avversario ha vinto l'esperimento, che è anche denotato dicendo che la produzione dell'esperimento è di 1, se e solo se l'indovinare dell'avversario è esattamente uguale. Il che significa, l'avversario A, senza conoscere la casualità interna del mittente e la casualità interna del destinatario e osservando semplicemente la trascrizione del protocollo Π, è in grado di arrivare con la chiave esatta, che mittente e destinatario si otturino percorrendo rispetto a questa trascrizione di protocollo Π. Se questo accade allora diciamo che la produzione dell'esperimento è del 1. E la definizione di sicurezza è, diciamo che il protocollo di generazione chiavi Π ha una debole - privacy, se per qualsiasi avversario polare che partecipa a questo esperimento esiste una qualche funzione trascurabile, tale che la probabilità che l'avversario vince l'esperimento è delimitata da qualche funzione trascurabile, dove la probabilità viene presa sulle monete casuali dello sfidante. Ovvero le monete casuali, con le quali si sta simulando il ruolo del mittente e del destinatario. Così notate che qui l'avversario non deve distinguere tra qualcosa. L'obiettivo dell'avversario è quello di arrivare con la chiave che il mittente e il destinatario ottengono rispetto alla trascrizione del protocollo Π. Ecco perché la definizione di sicurezza non avrà un'espressione della forma che le probabilità avversarie di vincere l'esperimento sono delimitate da metà più qualche funzione trascurabile. L'obiettivo dell'avversario è quello di arrivare con la chiave esatta con cui mittente e destinatario si otturino eseguendo il protocollo Π e che è coerente con la trascrizione del protocollo. Sempre in questa definizione consentiamo all'avversario di vincere il gioco con qualche probabilità trascurabile perché c'è sempre un avversario indovinoso, che può solo indovinare qualche candidato dallo spazio chiave e con probabilità non zero potrebbe rivelarsi esattamente uguale. (Riferimento Slide Time: 12.31) Così ora vediamo come possiamo modellare la privacy. E ricordate l'obiettivo della forte - privacy è che un avversario che monitora la trascrizione scambiata tra il mittente e il destinatario, non dovrebbe essere in grado di distinguere la chiave risultante che il mittente e il destinatario ottengono, da qualsiasi elemento uniformemente casuale dallo spazio chiave. E ancora per modellare la forte privacy, assumiamo protocolli di cambio chiave dove c'è un errore di correttezza da 0. Questo è di nuovo senza perdita di generalità; il suo molto dritto in avanti per incorporare anche questa condizione nella definizione di sicurezza. Così ora l'esperimento si chiama KEeav (perché ora non stiamo modellando deboli - privacy. Stiamo ora modellando la forte - privacy qui e le regole del gioco sono le seguenti. L'avversario è in attesa di una sfida qui e la sfida è di nuovo generata più o meno nello stesso modo in cui è stata generata nell'esperimento per la scarsa privacy. Ovvero lo sfidante qui ricopre il ruolo di mittente e destinatario nella sua mente e richiama un'istanza del protocollo per il mittente e invoca nell'istanza del protocollo per il destinatario, con la rispettiva casualità e genera una trascrizione di protocollo Π. Quel trascrizione di protocollo è ora dato come una sfida all'avversario. Così questo modello il fatto che l'eavesdropper tra il mittente e il destinatario avrebbe eavesato e ottenuto la trascrizione del protocollo Π. E ora visto che stiamo cercando di modellare la nozione di indistinguibilità basata sulla sicurezza nel contesto del protocollo di scambio chiavi, lo sfidante lancia così una sfida come segue. Si toglie una moneta equa, con probabilità 1/2 potrebbe essere 0 o con probabilità 1/2 potrebbe essere 1. E ora a parte la trascrizione, a seconda che il gettone di moneta sia di 0 o se il gettone di moneta è di 1, lo sfidante inoltra un elemento casuale dallo spazio chiave all'avversario o alla chiave, che il mittente e il destinatario avrebbero ottenuto eseguendo l'istanza di protocollo nella mente dello sfidante. Ora l'avversario non sa, se il valore dal tasto - spazio che sta vedendo è un elemento casuale dal tasto - spazio o se si tratta di una chiave che il mittente e il destinatario avrebbero ottenuto eseguendo il protocollo Π e ottenendo la trascrizione. Quindi la sfida per l'avversario è scoprire se è nel metodo o se è nel metodo. E ne sottopone la sua risposta, ovvero un po '. E la definizione qui è, diciamo che l'avversario vince l'esperimento, che è anche denotato come l'uscita dell'esperimento è di 1, se e solo se l'avversario A potrebbe identificare correttamente se sta vedendo un elemento come per il metodo o se sta vedendo un elemento dallo spazio chiave come per il metodo. E la definizione di forte - privacy qui è, diciamo che un protocollo di scambio chiavi Π ti dà una forte - privacy, se per qualsiasi avversario polenta che partecipa a questo esperimento, c'è qualche funzione trascurabile, tale che l'avversario di probabilità vince l'esperimento è delimitato da metà più qualche funzione trascurabile. Quindi ora questo è diverso dalla definizione della debole - privacy. Perché nella debole - privacy l'obiettivo di quell' avversario era quello di arrivare con l'esatto esatto che è coerente, o che sarebbe stato ottenuto dal mittente e dal destinatario come per la trascrizione Π. Ma ora qui l'obiettivo dell'avversario è quello di distinguere il, che mittente e destinatario otterranno come per la trascrizione del protocollo Π, da un elemento uniformemente casuale dal key-space.Quindi ecco perché ora stiamo avendo una condizione simile alla definizione indistinguibile e ancora stiamo mettendo questa condizione metà più trascurabile, perché c'è sempre una strategia indovinosa da parte dell'avversario e la strategia indovinosa dell'avversario sarà solo indovinare se è nel metodo o se è nel metodo. E la probabilità di successo di quella indovinare strategia è del 1/2. A parte che siamo disposti a lasciare che l'avversario vinca questo esperimento con qualche funzione trascurabile perché siamo nel mondo computazionale. Una formulazione equivalente di questa nozione di forte - privacy è che diciamo che il protocollo Π ti dà una forte - privacy, se per qualsiasi avversario polenta che partecipa a questo esperimento, il vantaggio distintivo dell'avversario è delimitato da qualche funzione trascurabile nel parametro di sicurezza. Il che significa che non importa se lo sfidante ha generato la sfida con il metodo = 0 o se ha generato la sfida con metodo. In entrambi i casi la risposta dell'avversario dovrebbe essere quasi la stessa ′ = 1, salvo con qualche probabilità trascurabile. E possiamo dimostrare che entrambe queste condizioni sono equivalenti l'una all'altra. Ovvero se si dispone di un protocollo di scambio chiave che soddisfa la prima condizione poi implica anche che soddisfi la seconda condizione e viceversa. Quindi a seconda della nostra convenienza possiamo usare una qualsiasi di queste due condizioni. (Riferirsi Slide Time: 17.41) Così ora abbiamo le definizioni di sicurezza dei protocolli di cambio chiave e ora vi potreste chiedere se effettivamente è possibile progettare protocolli di scambio chiavi, dove mittente e destinatario, senza avere informazioni pre - condivise possono fare qualche comunicazione su un canale insicuro pubblicamente conosciuto e finisce per concordare una chiave che non è nota a terzi? Quindi a livello molto alto potrebbe sembrare un compito impossibile perché come è possibile? Ovvero un mittente sconosciuto e un destinatario che conosce appena la propria identità e non ha informazioni pre - condivise, può fare l'interazione pubblica e concordare qualcosa di noto solo a loro. Ma si scopre che abbiamo effettivamente dei protocolli di scambio così chiave. E la base di questo protocollo di scambio chiave è dovuta al lavoro pionieristico da parte dei Diffie e Hellman che sono il primo paio di crittografi che si sono presentati con il loro protocollo di scambio chiave seminale. Così in questa lezione andiamo a vedere le idee sottostanti in base alle quali è stato sviluppato il loro protocollo di scambio chiavi. Allora prima che ti racconti qualche storia affascinante su come è entrato in vigore esattamente il loro protocollo di scambio chiave. Così Whitfield Diffie era molto interessato a risolvere il problema dei cambi chiave. E ha fortemente creduto che effettivamente sia possibile per un mittente e un destinatario fare comunicazione pubblica e concordare una chiave segreta comune. E nel 1974 ha tenuto un seminario al laboratorio di IBMs Watson a un pubblico scettico, che non stava acquistando la sua idea che effettivamente lo scambio di chiavi è possibile su un canale pubblico. L'unico risultato positivo che è venuto fuori da quel seminario è che è venuto a sapere che non è solo lui, c'è un'altra persona, una professoressa di Stanford, chiamata Martin Hellman, che sta anche lavorando allo stesso problema e cerca di inventarsi dei protocolli di scambio di chiave pubblica. E non appena Diffie è venuto a conoscenza di questo, ha iniziato un viaggio stradale di 5000 chilometri per incontrarsi e fare coppia con Martin Hellman ed è così che hanno iniziato il loro lavoro per arrivare con un protocollo per risolvere il problema dello scambio chiave. E lavorano per due anni rigorosamente e finalmente sono arrivati con il loro innovativo protocollo di scambio di chiavi Diffie - Hellman. (Riferimento Slide Time: 20 :07) Quindi cerchiamo di capire l'idea sottostante che c'è nel protocollo di scambio chiave Diffe - Hellman. Quindi l'idea di base dietro il loro protocollo di scambio chiave è che ci sono diversi compiti in questo mondo, che hanno asimmetria o sono asimmetrici in natura. E asimmetria nel senso che sono molto facili da eseguire. Questo significa che quelle azioni sono molto facili da eseguire ma estremamente difficili da invertire. Quindi quello che intendo con questo è immaginare che ti do un lucchetto in uno stato aperto. E se ti chiedo di bloccarlo allora non hai bisogno di nessuna chiave. Basta premere il capo del lucchetto e dallo stato aperto è possibile portarlo facilmente allo stato bloccato. Ma ora se vi do il lucchetto nello stato bloccato e vi chiedo di riprenderlo allo stato aperto allora sarà estremamente difficile per voi se non possiate possedere la chiave per il lucchetto. Quindi in questo senso questo lei ha un'azione qui dove andare da uno stato all'altro è estremamente facile. Ma tornare indietro dallo stato ottenuto allo stato originale è estremamente difficile. Non è impossibile. Ricordate che sto dicendo il suo “ estremamente difficile ” per tornare indietro o invertire l'azione se non si conosce la chiave. Potrebbero esserci altri metodi per invertire quell' azione senza la chiave, ma quelle alternative saranno estremamente difficili. Allo stesso modo considerare questo compito che ti viene dato un colore conosciuto pubblicamente e dire se vuoi preparare una miscela segreta, allora è molto facile per te farlo prendendo quel colore pubblicamente conosciuto e aggiungendo a quel colore esistente, un colore segreto e poi ottenere la miscela. Quindi preparare la miscela è molto facile per te. Ma se qualcuno mi dà questa miscela e non mi dice qual è esattamente il colore segreto che si è aggiunto al colore pubblico per ottenere questa miscela, allora sarà molto difficile per me scoprire o separare questa miscela nei suoi costituenti, ovvero il colore conosciuto pubblicamente e il colore segreto che qui ho aggiunto. Quindi in tal senso, preparare una miscela è facile ma separare la miscela alle sue singole componenti è un compito estremamente difficile. Quindi questo nuovo requisito non c'era quando puntavamo ad ottenere il protocollo di scambio chiave Diffie Hellman con una nozione più debole di privacy. Perché lì il requisito era che l'avversario non dovesse imparare nemmeno se lo sa,. Ma ora visto che puntiamo a una più forte nozione di privacy, stiamo mettendo a punto ulteriori requisiti sulla funzione e. Ovvero, chiediamo che anche se qualcuno sa, il valore di per quell' avversario o per quella persona debba essere computazionalmente indistinguibile da qualsiasi valore casuale dal set. E se suppitiamo che effettivamente la nostra funzione e soddisfi questo requisito aggiuntivo, è facile vedere che lo stesso protocollo che avevamo appena visto darci la più debole nozione di privacy, finisce per darci una nozione di privacy più forte. Non dobbiamo aggiungere gradini aggiuntivi; dobbiamo solo fare supposizioni più forti sulle funzioni e. Così questo mi porta alla fine di questa lezione. Tanto per riassumere rapidamente, in questa lezione, abbiamo introdotto il problema di cambio chiave dove l'obiettivo del mittente e del destinatario è quello di interagire pubblicamente su un canale in - sicuro senza pre