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 della crittografia Prof. Dr. Ashish Choudhury (Ex) Infosys Foundation Career Development Chair Professor International Institute of Information Technology - Bengaluru Lecture - 05 Limitazioni di Perfect Security Hello Tutti, benvenuti alla lezione 5. (Riferimento Slide Time: 00.30) Così, il piano per questa lezione è il seguente: vedremo un candidato per una crittografia perfettamente sicura, che chiamiamo come un solo time pad e vedremo i limiti imposti da qualsiasi schema di crittografia perfettamente sicuro. (Riferimento Slide Time: 00 :44) Quindi, il processo di codifica di un tempo pad, chiamato anche cifratura Vernam è molto semplice. Qui lo spazio di testo pianeggiante, lo spazio chiave e uno spazio di testo di cifratura sono tutte stringhe di bit, dove l è un qualche parametro di sistema che è pubblicamente noto al mittente, al destinatario e a chiunque utilizzi questo sistema. L'algoritmo di generazione della chiave sta andando a produrre una chiave uniformemente casuale. Così, dato che lo spazio chiave è impostato come stringhe di bit, l'algoritmo di generazione della chiave sta andando a produrre un tasto a un bit di bit uniformemente casuale. L'algoritmo di crittografia è il seguente. Quindi ci vuole un testo di pianura che sta per essere un po' stringa e la chiave k generata dall'algoritmo di generazione chiavi, che è anche una stringa di bit. E il testo cifrato è una stringa di l bit, dove il testo cifrato non è altro che lo XOR dei caratteri di testo pianeggiante e i caratteri chiave bit per bit. E come si può vedere che si tratta di un algoritmo deterministico non esiste una casualità interna come parte di questo algoritmo di codifica. Questo significa che se si codifica lo stesso messaggio m usando lo stesso tasto k si otterrà lo stesso testo cifrato. L'algoritmo di decriptazione è solo un'operazione inversa dell'algoritmo di crittografia nel senso che ci vuole un testo cifrato che sta per essere un po' stringa e la chiave k che sta anche per essere un po' stringa. E per recuperare il messaggio l'algoritmo di decodifica esegue semplicemente lo XOR del testo di cifratura con il tasto k bit per bit. Così solo per ricordare, qual è esattamente un'operazione XOR, quindi l'operazione XOR funziona con 2 a un tempo e l'output è definito come segue se entrambi i bit sono uguali, poi l'output sarà di 0. Mentre se i bit sono diversi, e l'output sarà 1, ecco qual è l'operazione XOR, giusto. (Riferimento Slide Time: 02.30) Quindi, in un certo senso, potete immaginare che questo algoritmo di crittografia faccia la mascheratura del messaggio con la chiave, a destra. Quindi l'operazione XOR ha l'effetto di mascherare il messaggio bit per bit con i bit della chiave. Mentre l'operazione di decriptazione come si può immaginare, ha il funzionamento inverso di mascherare cioè smascherare per bit l'effetto della chiave dal cifretto. Quindi, la cosa importante qui è che siccome l'operazione XOR è una sorta di reversibile qui, è possibile mascherare il messaggio usando la chiave eseguendo l'operazione XOR. E per ottenere l'effetto di non mascherare basta XOR la chiave dal cifrato per riottenere il tuo messaggio. Quindi ora proviamo a dimostrare che questo cifrario di Vernam o un solo time pad è effettivamente perfettamente sicuro. E possiamo provare la sua sicurezza perfetta come per ogni delle 3 definizioni che abbiamo visto nell'ultima lezione. Quindi proverò che Vernam cipher è effettivamente perfettamente sicuro sullo spazio dei messaggi di l bit stringhe. E per questo userò la prima definizione alternativa di perfetta segretezza che abbiamo discusso nell'ultima lezione. Ovvero, proverò che la distribuzione del testo cifrato è indipendente dal testo in chiaro sottostante in ogni ricorrenza di Vernam. Per questo consideriamo una distribuzione di probabilità arbitraria sullo spazio in chiaro, e una coppia arbitraria di messaggi m0, m1 appartenente allo spazio di testo pianeggiante come per quella distribuzione di probabilità che ha una probabilità non zero di ricorrenza. E scegliamo anche un testo cifrato arbitrario, che ha una probabilità non zero di ricorrenza. Quello che proverò è che per qualsiasi m0 e m1 che abbiamo scelto qui arbitrariamente e per qualsiasi testo di cifratura c che abbiamo scelto arbitrariamente qui, la probabilità che m0 sia criptata in c, e la probabilità che m1 in crittografato sia c, sono uguali, che dimostreranno che Vernam cifratura è perfettamente sicura. Quindi ora cerchiamo di prima provare a calcolare la probabilità condizionata che se il tuo querelante è m0, qual è la probabilità che il cifrario di Vernam produca il cifrato per essere c, giusto. Quindi la probabilità che il querelante m0 produca il testo di cifratura, c, è la stessa con la probabilità che la chiave che viene utilizzata per la crittografia sia questa stringa, ovvero la chiave è XOR di m0 e c. E qual è la probabilità che la chiave che si ottiene eseguendo l'algoritmo di generazione chiavi sia effettivamente lo XOR di m0 e c. Beh, è 1/2l. Perché, come per la sintassi del nostro algoritmo di generazione della chiave, l'algoritmo di generazione chiavi in uscita sta andando a produrre una chiave uniformemente casuale. Quindi la probabilità che una chiave uniformemente casuale che si ottiene per algoritmo di chiavi di generazione effettivamente soddisfa il valore XOR di m0 e c è 1/2l. Allo stesso modo, la probabilità che il messaggio m1 sia crittografato nel testo di cifratura, c, è uguale al valore di chiave utilizzato per la crittografia è lo XOR di m1 e c. E ancora, dal momento che il mio algoritmo di generazione chiave sta andando a emettere chiavi casuali uniformi, la probabilità che la mia chiave sia XOR di m1 e c è 1/2l. Così, dato che entrambe queste 2 probabilità sono uguali dopo aver visto un testo cifrato, che sta per essere un po' stringa, l'avversario non può evidenziare se si tratta di una crittografia di m0, o se si tratta di una crittografia di m1. E di qui l'avversario sarà completamente clueless. Ed è per questo che questa crittografia soddisfa la definizione di perfetta segretezza. Quindi ora abbiamo uno schema di crittografia dei candidati, che è perfettamente sicuro. (Riferimento Slide Time: 06 :17) Quindi ora potreste chiedervi che se abbiamo uno schema di crittografia candidati, che è perfettamente sicuro, perché non possiamo permetterci di usarlo in pratica. Quindi ora vediamo alcune delle limitazioni imposte dal regime di un time pad. La prima limitazione che si impone qui è che la chiave dovrebbe essere grande come il querelante perché la dimensione della chiave è l come pure la dimensione del querelante è anche l, giusto. Questo significa che se si vuole dire cripta 1 GB file, questo significa che se il mittente vuole cifrare un file di 1 GB, allora deve essere d'accordo su una chiave anche di dimensione 1 GB, che sembra molto poco pratica perché in pratica puntiamo ad andare per processo di codifica, dove possiamo usare un tasto di piccole dimensioni per criptare i messaggi lunghi. Ecco allora la prima restrizione che viene imposta da Vernam cifrata. La seconda limitazione che si impone qui è che non si può riutilizzare la stessa chiave per crittografare più di un messaggio. Questo significa che ogni istanza della crittografia ha bisogno di una chiave fresca. Sottolineo qui che quando dico qui che non si può riutilizzare la chiave, non intendo dire che non si può riutilizzare la chiave nella ricorrenza successiva, quello che intendo qui è che in ogni ricorrenza bisogna imbattersi nuovamente in un'istanza indipendente o una nuova istanza di algoritmo di generazione chiave. Va bene se la chiave che si sta per ottenere nel prossimo richiamo dell'algoritmo di generazione chiavi è la stessa che si è ottenuta nel precedente richiamo. Ciò che è importante qui è che entrambi i richiami della generazione chiave stanno andando in uscita in output indipendenti. Quindi dal punto di vista dell'avversario o di un aggressore che sta intercettando il testo cifrato, non starebbe sapendo che le chiavi che si sono usate se sono uguali o se sono diverse. Dal punto di vista dell'aggressore sono chiavi indipendenti. Quindi la seconda restrizione, che viene imposta qui è che non è possibile conservare la stessa chiave e continuare a crittografare più messaggi utilizzando la stessa chiave. Per esempio, immaginate uno scenario in cui il mittente utilizzerà o conservando lo stesso tasto k per criptare 2 diversi messaggi m0 e m1 in sequenza. Il che significa che ha usato un tasto k per crittografare prima un messaggio m0 comunicato il testo di cifratura. E supponga che stia nuovamente conservando lo stesso valore di chiave invece di eseguire nuovamente l'algoritmo di generazione della chiave. E riutilizza lo stesso tasto k per crittografare un prossimo messaggio m1, e ancora, il testo cifrato viene comunicato sul canale. E supponiamo che l'avversario sia consapevole di questo fatto che la stessa chiave è stata conservata e utilizzata dal mittente per criptare due messaggi m0 e m1. Quindi ora quello che un aggressore può fare è il seguente. Da quando ha intercettato il testo di cifratura c0, così come ha intercettato il testo di cifratura c1 e conosce il rapporto tra i messaggi m0 e k, m1 e k, e c0, c1. Ovvero, sa che c0 è lo XOR di m0 e k e sa che c1 è lo XOR di m1 e k. Se esegue lo XOR di c0 e c1, l'effetto di k sta per svanire, proprio perché è quello che è la proprietà dell'operazione XOR. Perché k sarà XORed con k stesso, che vi darà 0. E di conseguenza eseguendo lo XOR di c0 e c1, l'avversario otterrà lo XOR di m0 e m1. Quindi ora vi potreste chiedere quante informazioni in realtà vengono rivelate imparando lo XOR di m0 e m1. E si scopre che è una quantità significativa di informazioni. E questo significa che non possiamo rivendicare la perfetta segretezza per questo tipo di processo di crittografia dove lo stesso k è ora conservato per criptare più messaggi. (Riferirsi Slide Time: 09 :48) Quindi ecco quale vincitore del premio Turing, il leggendario scienziato informatico Michael Rabin ha da dire circa una volta pad, dice che non si dovrebbe mai riutilizzare un solo time pad, è come una carta igienica, perché se la riusa, le cose possono mettersi in gioco, giusto, quindi non si dovrebbe mai riutilizzare la chiave. Per ogni ricorrenza del mouse pad Vernam è necessario eseguire un algoritmo di generazione chiavi e ottenere un tasto fresco per crittografare i tuoi prossimi messaggi. (Riferimento Slide Time: 10.14) Quindi queste sono le 2 restrizioni imposte da Vernam cifrate. Ora, una questione naturale è se queste 2 limitazioni siano solo rispetto a un solo pad o a Vernam cifrate, o siano queste 2 limitazioni inerenti a qualsiasi cifrario perfettamente sicuro. Quello che ora dimostreremo è che queste due restrizioni sono intrinseche per qualsiasi cifratura perfettamente sicura, per qualsiasi chiave di cifratura perfettamente sicura dovrebbe essere grande quanto il testo di pianura. E dimostreremo anche che qualsiasi cifratura perfettamente sicura, ogni istanza della crittografia ha bisogno di una chiave fresca. (Riferimento Slide Time: 10.49) Quindi prima proviamo la prima limitazione qui. Così il teorema qui, immagina di ricevere un cifrario perfettamente sicuro. Potrebbe non essere una sola volta, potrebbe essere qualsiasi cifrario perfettamente sicuro. Il teorema dice che se lo schema è perfettamente sicuro, allora lo spazio chiave deve essere grande come lo spazio dei messaggi, giusto. Quindi, ecco la prova, la prova sarà per contraddizione. Così al contrario, immaginate che anche se il mio schema è perfettamente sicuro il mio spazio chiave è meno del mio spazio messaggi. Ciò significa che il numero di chiavi candidate è inferiore al numero di candidati querelanti. E per la dimostrazione qui è un esempio, presumo che il mio spazio di testo dell'impianto sia composto da 3 testo di pianura e il mio spazio chiave candidato sia costituito da 2 possibili chiavi. Quindi ora si considera la distribuzione di probabilità uniforme sullo spazio dei messaggi, questo significa considerare uno scenario in cui il mittente avrebbe potuto criptare uno qualsiasi di questi 3 possibili messaggi con uguale probabilità. E si considera un testo cifrato con la cui probabilità di ricorrenza è non zero. Quindi ora, definiamo il set M (c) che è l'insieme di tutte le decodifiche valide del testo di cifratura c, ovvero M (c) sono costituiti da tutto il testo di pianura m dallo spazio di testo pianeggiante, che posso ottenere decodificando il testo di cifratura c sotto diverse chiavi candidate dallo spazio chiave, giusto. Così, ancora in questo particolare esempio, se cerco di decriptare il testo di cifratura c, ho 2 possibili chiavi. Su decodificare cifratura da k1, otterrò un solo messaggio e su decodifica cifratura c dal secondo tasto k2 otterrò secondo messaggio che significa che la cardinalità del set M (c) è superiore delimitata dalla cardinalità dello spazio chiave perché questo è il numero massimo di decodificazioni distinte che puoi ottenere decodificando il testo cifrato c qui, e dal momento che come parte del mio presupposto, la cardinalità dello spazio dei messaggi è inferiore alla cardinalità del messaggio, ciò che ho ottenuto qui è che la cardinalità di M (c) è rigorosamente inferiore alla cardinalità dello spazio chiave inferiore alla cardinalità del messaggio spazio. Ciò che significa qui è che esiste almeno un messaggio dallo spazio dei messaggi, spazio di testo semplice, che non può mai portare al cifrato c che significa scriptare il testo del cifrario, non otterrò mai quel testo di pianura. Di nuovo in questo specifico esempio, si può vedere che la decodifica di c non può mai restituirti m3. E questa è una violazione della condizione di segretezza perfetta perché la condizione di segretezza perfetta dice che se si ha una distribuzione di probabilità uniforme sullo spazio di testo pianeggiante, poi per ogni testo di cifratura c che si verifica con probabilità non zero, dovrebbe essere una potenziale crittografia di tutti i messaggi candidati con pari probabilità o in altro senso se vedo le definizioni originali di perfetta segretezza, quello che siamo arrivati qui è il fatto che abbiamo almeno un messaggio m, dove la probabilità di ricorrenza del m è non zero, ma la probabilità condizionata che m è criptata nel cifrato c è di 0. Questo significa che queste 2 probabilità non sono uguali. E da qui si tratta di una violazione della perfetta segretezza. Quindi, questo significa che abbiamo dimostrato che in qualsiasi schema di crittografia perfettamente sicuro, lo spazio chiave deve essere grande come lo spazio dei messaggi. (Riferimento Slide Time: 14 :20) Ora, qual è l'implicazione di questo teorema. Immagina il tuo spazio chiave è il set di tutte le possibili stringhe di lunghezza x. Questo significa che il mio processo di codifica supporta la codifica di x bit stringhe. Questo significa che la cardinalità dello spazio chiave non è altro che 2x. E allo stesso modo, immaginate il mio processo di crittografia supporta lo spazio di testo semplice di stringhe di bit che significa che il testo in chiaro deve essere y bit stringato e di conseguenza, la cardinalità del mio spazio messaggi è 2y. Ora come per questo teorema è il mio schema è perfettamente sicuro ho bisogno della cardinalità dello spazio chiave per essere grande quanto la cardinalità dello spazio dei messaggi, questo significa che 2x dovrebbe essere maggiore di uguale a 2y. E come implicazione di questo, mi viene il fatto che x dovrebbe essere maggiore di uguale a y, questo significa che la lunghezza della chiave dovrebbe essere grande quanto il testo in chiaro. Questa è la prima limitazione di qualsiasi cifratura perfettamente sicura, ovvero, la chiave dovrebbe essere grande il querelante. (Riferimento Slide Time: 15 :24) Ora, proviamo la seconda limitazione di qualsiasi cifratura perfettamente sicura. E non lo dimostrerei rigorosamente e formalmente, vi darò solo un dettaglio di altissimo livello della prova qui. Così il teorema afferma che immaginate di ricevere un cifrario perfettamente sicuro sopra lo spazio di testo semplice m e lo spazio chiave k, poi ogni istanza del processo di codifica di questo cifrario dovrebbe richiedere una chiave indipendente da generare dall'algoritmo di generazione chiave. Ciò significa che non è possibile conservare la stessa chiave per crittografare più di un messaggio. Quindi ora cerchiamo di nuovo di provarlo usando una contraddizione. Immaginate quindi uno scenario in cui il mittente mantiene la stessa chiave k per criptare 2 messaggi m1 e m2 in sequenza, giusto. Quindi ha crittografato il messaggio m1 che produce cifratura c1 comunicato sul canale, e poi deve usare lo stesso tasto k per crittografare un secondo messaggio nella sequenza. E ancora il testo cifrato viene comunicato sul canale. E l'avversario ha intercettato sia il testo cifrato che l'avversario è consapevole del fatto che lo stesso k chiave sconosciuto è stato conservato e utilizzato per criptare sia i messaggi m1 che m2. Quello che proveremo è che se qualcosa di questo tipo è accaduto, allora non si potrà mai ottenere una perfetta segretezza, giusto. Quindi immaginate 2 diverse sequenze di testo semplice. La prima sequenza è quando il primo messaggio è m1 e il secondo messaggio è anche m1 e nella seconda sequenza m, le sequenze di messaggi sono m1 e m2, dove m1 e m2 sono diverse. E immaginate che l'avversario abbia intercettato un testo di cifratura composto da 2 sequenze di testo di cifratura dove il primo testo di cifratura è c1 e il secondo testo di cifratura c2, giusto. Così, come per requisito di perfetta segretezza, se l'avversario ha ottenuto una sequenza di testo cifrato essendo c1 e c2, e se l'avversario ha un'informazione preventiva che queste 2 sequenze di messaggi, che avrebbero potuto essere crittografate in c1 c2 potrebbero essere m1, m1 o m1, m2, allora il requisito di perfetta segretezza è che con uguale probabilità la sequenza cifrata c1, c2 dovrebbe essere qualsiasi crittografia di m1, m1 così come dovrebbe essere una crittografia potenziale di m1, m2 a destra. Questo significa che, se considero la probabilità lato sinistro qui allora ho introdotto qui 2 variabili casuali c1 e c2 in boldface, che denotano il valore della prima sequenza di testo di cifratura e la seconda sequenza di testo di cifratura. E allo stesso modo ho introdotto 2 variabili casuali, boldface m1 e boldface m2, per notare il candidato primo testo in chiaro e il candidato secondo querelante. Quindi la mia affermazione qui è che la probabilità che la tua probabilità lato sinistro e la tua giusta probabilità lato mano non possano mai essere uguali, ovvero una violazione di perfetta segretezza. Pittoricamente il requisito di una perfetta segretezza dovrebbe essere che non importa se la prima sequenza di messaggi m1, m1 è crittografata o se la seconda sequenza di messaggio m1, m2 è crittografata usando la chiave come per il tuo processo di codifica con uguale probabilità ti dovrebbe portare alla sequenza di testo di cifratura c1, c2, se a tutti i tuoi processi di crittografia perfettamente sicuri. Ma se questo è il caso, questo significa immaginare uno scenario dove effettivamente la sequenza di messaggi m1, m1 e una sequenza di messaggi m1, m2, entrambi portano ad una sequenza di testo di codifica c1, c2 con uguale probabilità sotto lo stesso e chiave k, poi significa un errore di decodifica. Perché questo significa che se si decodifica il testo di cifratura c2 per usare il tasto k, allora dovrebbe riportarti al testo di pianura m1 così come dovrebbe riportarti al testo di pianura m2, il che significa che c'è un errore di correttezza nel tuo processo di codifica. Il che significa che c'è un errore di decodifica nel tuo processo di codifica, che è una violazione del fatto che il tuo processo di crittografia è sicuro, perché uno dei requisiti di qualsiasi cifratura sicura è il requisito di correttezza, che esige che la tua descrizione sia univoca, ma se ci troviamo in uno scenario come questo, dove sia la sequenza di messaggi m1 m1 che la sequenza di messaggi m1 m2 portano alla stessa sequenza di testo c1, c2. Poi questo significa che se ho appena decodificato la sequenza di testo cifrato c2 potrebbe riportarmi a m1 così come potrebbe riportarmi a m2. Il che significa che c'è un'ambiguità nella decodifica del mio processo di crittografia originale stesso, che è una contraddizione, questo dimostra in modo informale il teorema che ogni istanza del processo di codifica dovrebbe funzionare di fresco di destra dell'algoritmo di generazione della chiave. Così questo mi porta a finire questa lezione. Solo per riepilogare. In questa lezione abbiamo discusso di un processo di codifica candidato, perfettamente sicuro, ovvero di un momento pad o di un cifrario di Vernam e abbiamo dimostrato la sua perfetta segretezza. Abbiamo anche visto le 2 restrizioni imposte da una sola volta. E abbiamo sostenuto che queste 2 limitazioni cioè la dimensione chiave essendo grande come messaggio e chiave fresca per ogni istanza della crittografia sono inerenti a qualsiasi processo di crittografia perfettamente sicuro. Spero che ti sia piaciuta questa lezione. Grazie.