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

    +

Fondamenta di CryptographyProf. Dr. Ashish Choudhury (Ex) Infosys Foundation Career Development Chair ProfessorIndian Institute of Technology-BengaluruLecture-04Perfect SecurityHello All, welcome to lezione 4. (Fare Slide Time: 00.28) Piano per questa lezione è il seguente: discuteremo di perfetta segretezza, che è la prima nozione formale di sicurezza, che è anche la più forte nozione di segretezza. Discuteremo anche varie definizioni equivalenti di perfetta segretezza. (Fare Slide Time: 00 :45) Quindi, la definizione di perfetta sicurezza è stata data da Claude Shannon nel suo lavoro classico nel 1948 e Shannon è spesso considerata come il padre della teoria dell'informazione e questa nozione di sicurezza è chiamata anche sicurezza incondizionata e sicurezza teoretica dell'informazione. Il modello di attacco considerato nella definizione di sicurezza perfetta è l'unico modello di attacco cifrato, in cui supponiamo di avere un mittente e un destinatario che si sono accordati su un valore chiave casuale k. supponiamo che il mittente abbia criptato un singolo messaggio m utilizzando un processo di crittografia pubblicamente noto sotto quella chiave k, e il testo cifrato sia stato intercettato dall'avversario. La parte interessante di questo modello di attacco è che ipotizziamo qui che l'avversario sia computazionalmente sconfinato. Questo significa che non facciamo alcuna supposizione sulla sua potenza di calcolo. Supponiamo che possa fare qualsiasi tipo di calcolo con forza bruta o qualsiasi altro calcolo. Ecco quindi l'aspetto interessante di questo modello di sicurezza. Informalmente, la perfetta sicurezza dice che indipendentemente da qualsiasi informazione preventiva che l'aggressore abbia sul sottostante testo di pianura, vedere il testo della cifratura non fornisce ulteriori informazioni su di lui sul sottostante testo di pianura. Il che significa vedere il cifratto è assolutamente inutile per l'aggressore. Qualunque cosa possa infastidire il messaggio dal testo cifrato, stesso avrebbe potuto già inferocere prima che qualsiasi testo cifrato sarebbe stato comunicato. Qui abbiamo 2 entità, abbiamo le informazioni precedenti e abbiamo il termine senza ulteriori informazioni. Dobbiamo ora imparare un po' di matematica per capire come formalizzare queste 2notions e cioè quella delle informazioni precedenti e che non hanno informazioni aggiuntive. (Fare Slide Time: 02 :36) Quindi, immaginiamo di ricevere un cifrario pubblicamente noto e cioè una tripletta di algoritmo di chiavi di generazione, algoritmo di crittografia e un algoritmo di decodifica. Poi qualsiasi aggressore ha le seguenti informazioni sul processo di codifica. Ovvero, conosce 3 spazi, ovvero lo spazio dei messaggi, lo spazio chiave e lo spazio di testo del cifrario, dove lo spazio dei messaggi è l'insieme di tutti i messaggi legittimi che potrebbero essere crittografati dal processo di codifica. Lo spazio chiavi denota tutte le chiavi possibili che potrebbero essere emesse dall'algoritmo di generazione chiavi. E il testo cifrato denota ogni possibile testo cifrato, che potrebbe essere generato dall'algoritmo di crittografia. Dal punto di vista dell'aggressore, qualsiasi schema di crittografia induce 3 distribuzione di probabilità, una distribuzione di probabilità sullo spazio dei messaggi, una distribuzione di probabilità sullo spazio chiave e una distribuzione di probabilità sullo spazio cifrato. Quindi ora passiamo a queste distribuzioni di probabilità uno per uno. La prima distribuzione di probabilità supera lo spazio chiave e questo è indotto dall'algoritmo di generazione della chiave. Quindi ricordate, come per il principio di Kerckhoffs, noi supponiamo che passi dell'algoritmo di generazione chiave, algoritmo di crittografia e algoritmo di decodifica siano pubblicamente noti all'aggressore. Abbiamo anche discusso che l'algoritmo generazionale chiave deve essere un algoritmo randomizzato. Il che significa, ogni volta che eseguiamo l'algoritmo di generazione della chiave sta andando a produrre una possibile chiave candidata dallo spazio chiave con certa probabilità. Ecco cosa intendiamo per la distribuzione di probabilità sullo spazio chiave indotto dall'algoritmo di generazione chiave. Inoltre, abbiamo discusso in una delle precedenti lezioni che nella maggior parte dei casi, l'algoritmo di generazione chiave sta andando a produrre una chiave uniformemente casuale dallo spazio chiave. Ovvero, se la dimensione dello spazio chiave è la cardinalità dello spazio chiave, allora qualsiasi chiave candidata potrebbe essere generata con probabilità su uno spazio chiave. Ecco quindi la distribuzione uniforme sullo spazio chiave, che l'avversario avrà già se conosce i passi dell'algoritmo di generazione chiave. Ma non è necessario che il tuo algoritmo di generazione chiavi superi sempre le chiavi uniformemente casuali dallo spazio chiave. Quindi questo sarebbe indurre un altro tipo di distribuzione di probabilità, qualunque sia il caso visto che i passi degli algoritmi di generazione chiave sono noti pubblicamente. Sappiamo che dal punto di vista dell'aggressore c'è una distribuzione di probabilità su diversi valori delle chiavi, che potrebbe verificarsi con probabilità diverse. Quella è proprio la distribuzione di probabilità sullo spazio di testo pianeggiante che l'aggressore ha. Possiamo anche matematicamente catturare cosa esattamente intendiamo per nessuna informazione aggiuntiva. Formalmente, un processo di crittografia ovvero una raccolta di algoritmi chiavi di generazione, Enc e Dec su uno spazio di testo semplice M viene definito perfettamente sicuro se per ogni distribuzione di probabilità sullo spazio di testo pianeggiante e spazio chiave, e per ogni testo di pianura m appartenente allo spazio di testo pianeggiante, secondo tale distribuzione di probabilità, e per ogni cifrario c appartenente allo spazio cifrato, Pr [ M =? | C =?] = Pr [ M =?] detiene. Quindi fatelo capire cosa significa esattamente il LHS e la RHS di questa uguaglianza. Se si considera la parte RHS di questa uguaglianza, ovvero Pr [ M =?], m potrebbe essere comunicato dal mittente. Si tratta di una precedente informazione relativa al testo di pianura sottostante prima che qualsiasi comunicazione sia avvenuta dal mittente al destinatario, prima che sia stato utilizzato qualsiasi algoritmo di generazione chiave, e il messaggio è stato crittografato. Ovvero le informazioni apriori relative al sottostante querelante. considerando che la parte LHS di questa parità Pr [ M =? | C =?] quella presunta probabilità a posteriori che il messaggio m sia crittografato in c. Questo significa, dato che l'avversario ha visto o intercettato un testo di cifratura c, qual è la probabilità che il testo di pianura m sia crittografato in questo testo cifrato c. Quindi, intuitivamente, quando diciamo che queste 2 probabilità sono uguali, significa che qualunque sia l'avversario che l'avversario sapeva del testo di pianura sottostante prima che un testo di cifratura fosse comunicato con la stessa probabilità avversaria sa che un testo di pianura potrebbe essere m e nel dato testo cifrato c. Ciò significa osservare il cifrato c non cambia aggressore le conoscenze sulla distribuzione del testo in chiaro. Qualunque sia la conoscenza dell'aggressore che si conosce prima di vedere il testo cifrato, la stessa conoscenza che ha, anche dopo aver visto il cifratto. Inoltre, trattiene anche se l'avversario è computazionalmente sconfinato. Questa è l'importanza di questa definizione. Questa definizione non pone alcun tipo di restrizione alla potenza computazionale dell'avversario. Anche se l'avversario conosce i passi dell'algoritmo, anche se sa quali potrebbero essere le chiavi candidate anche se è consentito fare la forza bruta, la sua vista o la sua conoscenza sul testo di pianura sottostante o sulla distribuzione del testo di pianura non dovrebbe cambiare prima e dopo aver visto il cifrato. Se questo vale, allora diciamo che il nostro processo di crittografia sottostante è perfettamente sicuro. Notate che in questa definizione ho evidenziato poche cose cioè, ho detto che la condizione dovrebbe tenere per ogni distribuzione di probabilità sullo spazio di testo pianeggiante. Ciò significa che non importa se la distribuzione su uno spazio di testo semplice sia una distribuzione uniforme o una distribuzione bias, la condizione dovrebbe tenere per qualsiasi possibile distribuzione di probabilità sullo spazio dei messaggi. Allo stesso modo, la condizione o l'uguaglianza dovrebbe tenere per qualsiasi tipo di distribuzione di probabilità sullo spazio chiave se si tratta di una chiave uniformemente generata, se l'output dell'algoritmo di generazione chiavi genericamente genererà chiavi casuali o chiavi bianche ancora la condizione dovrebbe hold.Inoltre, una volta fissate la distribuzione di probabilità dello spazio di testo pianeggiante e lo spazio chiave, la condizione dovrebbe tenere per ogni testo in chiaro appartenente allo spazio dei messaggi e ad ogni candidato cifrato appartenente allo spazio cifrato. (Fare Slide Time: 20 :45) Così ora, quello che faremo sarà vedere qualche equivalente alternativo definizioni per una sicurezza perfetta. Questa è la definizione originale di perfetta sicurezza come dato da Shannon e l'interpretazione della parità di queste 2 probabilità è che la probabilità di conoscere un testo in chiaro rimane la stessa prima e dopo aver visto il testo cifrato. Ecco l'interpretazione della definizione originale di perfetta sicurezza come dato da Shannon.Ora vediamo la prima definizione alternativa. La prima definizione alternativa dice che diremo un processo di crittografia o uno schema di crittografia per essere perfettamente sicuri se per ogni distribuzione di probabilità sullo spazio in chiaro e spazio chiave e per ogni coppia di messaggi m0, m1 che si verifica con probabilità non zero rispetto a quella distribuzione di probabilità e ogni testo di cifratura c la seguente uguaglianza dovrebbe tenere: Pr [ C =? | M =? 0] = Pr [ C =? | M =? 1]. L'uguaglianza dice che Pr [ C =? | M =? 0] è uguale a Pr [ C =? | M =? 1]. L'interpretazione di questa uguaglianza è che la distribuzione di probabilità del testo cifrato è indipendente da ciò che esattamente è il tuo sottostante testo di pianura. Questo significa che se l'avversario vede il cifrato c oltre il canale, allora non importa se M =? 0 o M =? 1 con uguale probabilità dal punto di vista dell'aggressore, il cifrato c dovrebbe essere una cifratura candidata di m0 oltre che una cifratura candidata di m1.Non ci dovrebbe essere alcun bias nella probabilità. Ma che si tratti di una crittografia di m0 o se si tratta di una crittografia di m1, questo significa che la distribuzione del testo cifrato dovrebbe essere indipendente dal querelante sottostante. (Fare Slide Time: 22 :32) Quindi ora quello che faremo a fianco è che dimostreremo che entrambe queste 2 definizioni sono equivalenti. Ovvero, dimostreremo che se c'è un processo di codifica che soddisfa la condizione originaria della perfetta sicurezza di Shannon, allora lo stesso processo di codifica deve soddisfare la definizione alternativa e viceversa. Proviamo prima a provare l'equivalenza della definizione ipotizzabile che abbiamo un processo di crittografia che soddisfi la condizione di definitiono.Namely, supponiamo di avere un processo di crittografia dove per ogni distribuzione di probabilità, Pr [ C =? | M =? 0] = Pr [ C =? | M =? 1] =?, diciamo delta, per tutte le coppie di messaggi m0, m1 nello spazio di testo pianeggiante e per tutti i cifrati c appartenenti allo spazio di testo di cifratura. Dato questo, dimostreremo che la condizione originale della perfetta sicurezza di Shannon è vera anche per il processo di crittografia. Pr [ M =? | C =?] = Pr [ M =?]. Quindi quello che faremo è ipotizziamo di avere un testo di pianura arbitraria e un carattere di testo arbitrario arbitrario. Ora proviamo a compaggiare Pr [ M =? | C =?]. Quindi quello che farò qui è che applicerò il teorema di Bayes qui. Applicando il teorema di Bayes, Ora proviamo a calcolare Pr [ C =?]? La probabilità che il vostro cifrario sia c sarà questa sommità. Questo stato di sommità che prendi tutti i possibili messaggi dallo spazio di testo pianeggiante e scopri qual è la probabilità che il messaggio sia quel testo di pianura candidata cioè m e dato che il messaggio è m .. qual è la probabilità che m sia crittografato in c. Questo ti darà la distribuzione di probabilità sul testo cifrato c. Perché quello che deve sostanzialmente fare è immaginare di avere lo spazio di testo pianeggiante che si prende ciascuno del candidato querelante che è proprio il primo termine in questa sommità. E una volta che hai stabilito che il candidato querelante ti trovi appena compatto qual è la probabilità che quel candidato querelante ti porti al cifrato c, cioè questo è questo secondo mandato. E se si moltiplica tutto questo, se queste 2 probabilità e prendono la sommità su tutto il testo di pianura candidata, che ti darà la distribuzione di probabilità di essere c. Ora, come per la nostra ipotesi della condizione, sappiamo che la probabilità condizionata che il cifrato è c dato che il testo di pianura è m è uguale per tutti m ovvero, Pr [ C =? | M =??) =?, perché questo è quello che è il presupposto che stiamo facendo. Stiamo facendo supporre che il nostro processo di codifica soddisfi la condizione alternativa. Quindi per ogni m .. posso sostituire il secondo mandato nella sommatoria da?. Di conseguenza, ottengo questa forma semplificata della summationatura abbiamo calcolato il valore della probabilità di C = c, cioè?. Ora, proviamo a compaggiare Pr [ C =? | M =?], cioè la parte numeratrice di questa espressione RHS. E ancora, come per la nostra ipotesi di questo teorema, o questo lemma, sappiamo già che Pr [ C =?] =?. E questo indipendentemente da quello che è mio m, potrebbe essere m0, potrebbe essere m1 potrebbe essere m2 per qualsiasi candidato m dalla base di querelle, Pr [ C =?] =?. Quindi, questo significa anche la parte numerata di questa espressione RHS?. Da qui, posso dire che il mio LHS originale ovvero, Pr [ M =? | C =?] niente ma questa uguaglianza.E nel numeratore così come in denominatore ho la? così posso annullarlo. E di qui, ottengo che questa probabilità condizionata non è altro che Pr [ M =?], che è proprio ciò che esattamente volevamo dimostrare. Questo significa che abbiamo dimostrato che se il processo di crittografia soddisfa la condizione della definizione alternativa, deve poi soddisfare anche la condizione di originale definizione di Shannon. Quindi, ora facciamo la prova in senso inverso. (Fare Slide Time: 27 :54) Ovvero, suppliamo di avere un processo di crittografia che soddisfi la condizione della definizione originale di Shannon. Quello è il Pr [ M =? | C =?] = Pr [ M =?] ∀? M,? ?. Dato questo dimostrerà che la distribuzione del testo di cifratura è indipendente dal testo in chiaro sottostante. Ovvero, non importa se il testo di pianura sia m0 o se il testo di pianura sia m1with di uguale probabilità, potrebbe portare al testo di cifratura c, e questo vale per ogni coppia di messaggi m0, m1 in dallo spazio di testo pianeggiante e ogni testo cifrato c dallo spazio di testo di cifratura. Proviamo prima a calcolare Pr [ C =? | M =? 0]. Per questo useremo il fatto che come per la condizione data, dato che lo schema di crittografia soddisfa la condizione originale di Shannon, sappiamo che Pr [ C =? | M =? 0] = Pr [ M =? 0]. Quindi ora quello che farò è espandere la mia parte LHS qui utilizzando il teorema di Bayes, dove sto solo cambiando il numeratore e il denominatore della probabilità condizionata. E applicando il teorema di Bayes, ottengo questa uguaglianza. = Pr [ M =? 0] Ora, quello che posso fare è annullare questo termine comune sia da LHS che da RHS. Da qui ho ottenuto quel Pr [ C =? | M =? 0] = Pr [ C =?]. Applicando la stessa logica, posso concludere che Pr [ C =? | M =? 1] = Pr [ C =?]. Di conseguenza, sia Pr [ C =? | M =? 0] e Pr [ C =? | M =? 1] sono uguali cioè, è Pr [ C =?]. Questo significa, abbiamo dimostrato che se la condizione originale di Shannon è soddisfatta, allora anche il processo di codifica deve soddisfare la condizione per la definizione alternativa. Il che significa, entrambe queste definizioni sono equivalenti ad ogni other.Quindi, se ci viene dato un processo di crittografia e se si chiede di provare se è perfettamente sicuro o meno, allora si può provare come per la condizione di Shannon originale oppure lo si può provare come per la prima definizione alternativa. (Fare Slide Time: 30 :30) Ora, vediamo un'altra definizione equivalente di perfetta sicurezza. Prima di entrare in questa definizione, cerchiamo innanzitutto di capire l'intuizione sottostante che vogliamo catturare attraverso questa definizione. Quindi, l'obiettivo della perfetta sicurezza è il seguente: immaginate uno scenario in cui una chiave per il processo di crittografia sia stata concordata tra il mittente e il destinatario. Supponga che l'avversario lo sappia? {?0,? 1} e anche quello con uguale probabilità.Supponiamo infatti che il mittente stia per cifrare il messaggio m0 o m1 con uguale probabilità. E codifica uno di questi messaggi usando casualmente il tasto k come per il processo di crittografia, calcola il testo di cifratura c e lo invia oltre il canale. Diciamo che l'aggressore intercetta il testo di cifratura c, e l'aggressore ha una potenza di calcolo illimitata. L'intuitivamente perfetta segretezza esige che le conoscenze degli avversari riguardo al testo di pianura sottostante debbano rimanere le stesse anche dopo aver visto il testo cifrato c. Quindi quelle che erano queste informazioni sul testo di pianura prima che un qualsiasi testo di cifratura fosse comunicata in questo caso particolare: con probabilità metà dal punto di vista dell'aggressore, il testo di pianura potrebbe essere m0, e con probabilità metà del testo pianeggiante sarebbe m1. Ora la perfetta segretezza esige che anche dopo aver visto il testo di cifratura c e anche dopo aver conosciuto i passi del processo di crittografia, e anche se l'avversario ha una potenza di calcolo illimitata, il vantaggio che l'avversità ottiene dopo aver visto il testo di cifratura e imparare il sottostante testo di pianura dovrebbe essere 0.That significa, anche dopo aver visto il testo cifrato c, la probabilità che il testo di pianura sottostante sia m0 o m1 dovrebbe essere la metà. Avversario non può fare niente di meglio che indovinare il sottostante testo di pianura. Questa è l'intuizione sottostante che ora formalizziamo. (Fare Slide Time: 32 :21) E questa intuizione è formalizzata da un gioco di risposta di sfida, che chiamiamo questo esperimento. E vedremo che nel resto di questo corso, ogni definizione di sicurezza sarà formalizzata da questo tipo di esperimento di risposta di sfida o da un gioco che modello qualcosa che vogliamo, che può accadere nella realtà. L'esperimento è il seguente: supponiamo di ricevere un cifrario conosciuto pubblicamente = (Gen, Enc, Dec), M, e il gioco è giocato tra 2entities.The prima entità qui è un avversario o un algoritmo per l'aggressore che noi denottiamo da questo algoritmo A e l'algoritmo o l'avversario è computazionalmente sconfinato. Questo modello il fatto che stiamo cercando di catturare la nozione di perfetta segretezza dove l'avversario è computazionalmente svincolato. La seconda entità qui è l'ipotetico verificatore che sta per modellare il sender.Now, la nomenclatura che seguiremo mentre nomineremo questo tipo di esperimenti è la seguente: questo particolare esperimento è denotato da? ???? (?, Π) ???. Ora cerchiamo di decodificare ognuna delle singole parti di questo nome complicato. Così, il nome PrivK denota qui che stiamo cercando di modellare un esperimento per un processo di crittografia simmetrica o un processo di crittografia dei tasti privati. Ecco perché il nome PrivK, in seguito quando cercheremo di modellare il requisito di sicurezza per i primitivi di chiave pubblica. Questa privK sarà sostituita da PubK. Il nome della stringa eav denota qui stiamo valutando un avversario dove l'avversario è consentito solo ad eavesare o semplicemente ascoltare il testo di cifratura perché siamo nel testo di cifratura solo modello di attacco. Il nome A qui denota il nome dell'algoritmo qui e la sfida denota il nome del processo di crittografia rispetto al quale si gioca questo gioco. Questa è la nomenclatura che seguiremo per denotare questo particolare esperimento. Ora, quali sono le regole di questo gioco? Questo esperimento sarà un esperimento randomizzato. Il primo passo qui è che l'avversario seleziona una coppia di messaggi dallo spazio di testo pianeggiante, diciamo m0and m1 con la restrizione che le loro dimensioni devono essere uguali. Un avversario può scegliere qualsiasi coppia di messaggi. Non c'è assolutamente alcuna restrizione che mettiamo su quale coppia di messaggi che può sottoporre al verificatore. L'unica restrizione è che la loro lunghezza deve essere uguale, quindi l'avversario può determinare deterministicamente un paio di messaggi, potrebbe scegliere casualmente una coppia di messaggi, può usare qualsiasi strategia per scegliere la coppia di messaggi che vuole inviare al verificatore. Ora, una volta che la coppia di messaggi viene comunicata al verificatore, quello che il verificatore sta andando a fare è il seguente: eseguirà l'algoritmo di generazione chiavi in uscita che avrà in uscita un tasto uniformemente casuale o una chiave come per i passi dell'algoritmo di generazione della chiave per il verificatore. E il verificatore sceglierà casualmente uno di questi due messaggi per la crittografia. L'indice del messaggio che verrà scelto per la crittografia è denotato da b, che viene prelevato uniformemente casualmente. Il che significa, con probabilità metà, potrebbe essere picking il messaggio m0 per la crittografia, o con probabilità metà potrebbe essere picking il messaggio m1 per la crittografia. Una volta che ha deciso l'indice del messaggio, crittografa quel messaggio mb utilizzando il tasto k che è noto solo al verificatore e il testo cifrato è dato all'avversario.E ora l'obiettivo dell'avversario è scoprire l'indice del messaggio che è stato crittografato in c, questo significa che l'avversario deve scoprire se la c è una crittografia di m0 o se si tratta di una crittografia di m1. Dopo aver analizzato il testo di cifratura c come per qualunque strategia avversaria voglia seguire, dà loro la previsione. Ovvero, si delinea un po', che è 0 o 1 corrispondente all'indice, che sente che quel particolare messaggio è stato crittografato nel testo di cifratura c. Questo significa b) denota l'indice, che secondo l'avversario è l'indice del messaggio cifrato nel testo cifrato c. Questo è l'esperimento. Come potete vedere, si tratta di un esperimento randomizzato, perché l'avversario potrebbe scegliere qualsiasi coppia di messaggi come per la sua casualità. Allo stesso modo il verificatore sta andando a scegliere qualsiasi messaggio casuale su questa coppia per la crittografia, e la chiave potrebbe essere qualsiasi chiave casuale come per l'algoritmo di generazione della chiave. Ora l'output dell'esperimento è deciso come segue. Diciamo che la produzione dell'esperimento è di 1 o che viene interpretata come avversario ha vinto il gioco, se ha correttamente previsto quello che è esattamente il messaggio che viene crittografato nel testo cifrato c. Il che significa che se si emette correttamente b pari a b allora diciamo che l'avversario ha vinto questo esperimento o l'avversario sessante.it s output è 1.On l'altra mano, se l'avversario identifica erroneamente ciò che è crittografato in quel testo di cifratura c che significa outputs b che è diverso da b, allora diciamo che la produzione dell'esperimento è di 0, che viene interpretata come avversario ha perso il gioco. Abbiamo visto anche la definizione di gioco - baseddefinition, che modella perfetta indistinguibilità. Spero che ti sia piaciuta questa lezione. Grazie!