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 Lezione – 45 RSA Assunzione tutti, benvenuti a questa lezione. (Riferimento Slide Time: 00.42) Così giusto per recap nell'ultima lezione, abbiamo visto Candidate Public Encryption Schema, CPA secure Public Encryption Schema, principalmente lo schema di crittografia El Gamal. In questa lezione e la prossima lezione parleremo di un altro Candidato Public Encryption Schema basato sul diverso difficile problema, che chiamiamo assunzione RSA, che ci porterà ad un altro schema di crittografia pubblica ovvero il RSA Public Encryption Schema. (Riferimento Slide Time: 00 :58) Quindi per capire l'assunzione RSA, cerchiamo prima di capire il set ZN*. Così ZN* praticamente è un insieme di numeri interi modulo N, che sono co - prime al modulus N, ovvero ZN* è la raccolta di tutti gli elementi b nella gamma {1, …, N-1} tale che l'elemento b è co - prime al modulus N. Namely, il loro GCD è di 1. Ad esempio, il set Z10 * non è altro che gli elementi 1,3,7 e 9. Perché tutti questi elementi 1, 3,7 e 9, sono co - primi al modulo 10, ed è facile vedere che se il modulus N è primo, allora il set ZN* consisterà sostanzialmente in tutti gli elementi da 1 a N-1. Quindi, un fatto ben noto dalla teoria dei numeri la cui prova che sto salendo è che il set ZN* insieme all'operazione di moltiplicazione modulo N costituisce un gruppo e soddisfa tutti gli assiomi del gruppo. Così, per esempio, ho disegnato la matrice per gli elementi in Z10 *, ovvero 1, 3, 7 e 9, e il risultato di eseguire la moltiplicazione del funzionamento modulo 10 per qualsiasi elemento di coppia dal set, e ora si può vedere che tutti gli assiomi dei gruppi sono soddisfatti ed è per questo che si tratta di un gruppo. Del resto, un fatto ben noto dalla teoria dei numeri è che abbiamo algoritmi in politempo per il calcolo dell'inverso moltiplicativo, che io dengo di, a-1, per qualsiasi elemento un nella serie ZN*. E c'è un algoritmo ben noto per quello, che chiamiamo come Extended Euclide ' s GCD algoritmo, di cui discuteremo in una delle nostre successive lezioni, e il tempo di esecuzione di quell' algoritmo è polinomiale nel numero di bit che dobbiamo rappresentare il modulus N. (Fare Slide Time: 02 :47) Quindi, facciamo discutere a fianco di Euler il Totient Function, la funzione φ. Così la funzione Totient Function di Euler, che è la densata dal simbolo φ (N) è sostanzialmente la cardinalità del set ZN*, ovvero è il numero di elementi presenti nel set da 1 a N-1, che sono co - prime al tuo modulus N. Alcuni dei fatti ben noti di nuovo presi in prestito dalla teoria del Numero sono i seguenti. Se N è un primo p, allora il valore di φ (p) non è altro che p -1. Perché ci sono esattamente elementi p-1, che sono co - prime a p. D'altra parte, se n è il prodotto di 2 primes distinti, p e q, poi φ (N) non è altro che p-1 volte q-1. Questo significa che ci sono questi tanti elementi, ovvero p-1 volte q-1 elementi nella gamma {1, …, N-1}, che saranno co - prime al tuo modulus N. Per verificarlo, facciamo un esempio, diciamo N = 10, che puoi scrivere come prodotto di 2 e 5, dove 2 e 5 sono prime. Quindi il tuo p è 2 e il tuo q è 5, allora sappiamo che ci sono 4 elementi nel set Z10 *, quindi φ (10) dovrebbe essere 4, e il 4 non è altro che p-1, ovvero 2 - 1 moltiplicato per q-1, e infine un'altra proprietà interessante che utilizzeremo da Numero Teoria è che, per qualsiasi elemento a ZN*, un φ (N) modulo N è 1. Questo significa, se N è un primo p, allora questo φ (N) non è altro che p-1, quindi otteniamo ap-1 modulo p per essere 1. Questa proprietà o questo risultato è chiamato anche come Fermat s Little Theorem, e ci avamiamo anche a causa di questo fatto, il corollario che se hai un qualsiasi elemento appartenente al set ZN*, poi l'ax modulo N è esattamente lo stesso di ax modulo φ (N) modulo N. Che significa, nell'esponente è possibile ridurre l'esponente x a x modulo φ (N). Quindi il motivo di questo problema corollario è che, se la tua x è comunque inferiore a φ (N), allora sia L.H.S. che R.H.S. sono uguali, ma se la tua x è più che φ (N) allora per compatta ax modulo φ (N), ciò che puoi fare è, puoi riscrivere l'ax come diversi lotti di un φ (N) con φ (N) in esponente. a φ (N) dipende dal rapporto tra x e φ (N), e l'ultimo lotto avrà l'ax modulo φ (N), e tutto nella base modulo N. Ora, sappiamo che un φ (N) modulo N è 1, questo significa che ognuno di questi lotti, hai pieno un φ (N) modulo N, ti daranno la risposta 1. Quindi, tutti questi lotti vi daranno la risposta 1, 1, 1, 1 e 1 moltiplicato per 1 vi darà 1. Quindi, sei finalmente rimasto con l'ultimo lotto, che ha l'ax modulo φ (N). Ecco, ecco come otteniamo questo corollario. (Riferirsi Slide Time: 06.03) Così, con tutta questa matematica in atto, ora cerchiamo di capire la permutazione RSA. Così questa permutazione RSA è una mappatura dal set ZN* a ZN*, così il modo in cui questa permutazione è definita come segue. Immagina, ti viene dato un esponente e, che è superiore a 2, tale che l'esponente e sia co - prime al tuo valore φ (N). Quindi, sottolineo che è co - primato a φ (N), non a N. Ora, un fatto ben noto da Numero Teoria è che se hai un e, che è co - prime a φ (N), allora puoi scoprire l'inverso moltiplicativo di quello e modulo φ (N). In generale, se hai 2 numeri, diciamo a e b, tale che GCD di a e b è 1, cioè un e b sono co - primi l'uno all'altro, allora puoi sempre trovare l'inverso moltiplicativo di un modulo b. Quindi, il mio modulus in questo caso è φ (N), perché e è co - prime a φ (N), e se e è co prime a φ (N), utilizzando l'algoritmo di Euclide esteso, posso trovare d dove e e d costituisce il loro reciproco inversore moltiplicativo. Il che significa, e volte d modulo φ (N), e d i tempi e modulo φ (N) è 1. Ora, la permutazione RSA è definita come segue. Per andare nella direzione in avanti, la funzione è fe, e per calcolare il valore di fe (x) dove x è un membro di ZN*, praticamente compaiamo xe e facciamo mod N. D'altra parte, la funzione di reverse direction è fondamentalmente una funzione di d, ovvero, fd (y), e questa funzione è sostanzialmente se voglio compendiare fd (y), calcolerò yd, e poi eseguo mod N. I claim qui che la funzione fd è l'inverso della funzione fe e viceversa. Quindi, per questo considerare qualsiasi arbitrario x qui, appartenente a ZN*, e dire che la mappa a y, come per la funzione fe, quindi la mia y non è altro che xe, e ora lascia che i cali vedano cosa otteniamo invertendo questo valore y come per la funzione fd. Se invertito questa y come per fd, allora ottengo xe mod N, e poi intero innalzamento alla potenza d mod N. Così posso prendere il mod complessivo esterno, e ottengo che questo sia lo stesso xe volte d modulo N, e utilizzando il corollario che abbiamo dichiarato nell'ultima slide, modulo N in esponente, posso ridurre questo esponente e*d a e*d modulo φ (N). So che e*d modulo φ (N), che c'è nell'esponente, mi dà valore 1, perché ho scelto e e d tale che sono inversamente moltiplicativi l'uno dell'altro. Così, nell'esponente, è e tempi d modulo φ (N) si riduce a 1, quindi da qui ottenere che questo modulo fisso N non sia altro che x modulo N, e dato che ho scelto la mia x per appartenere al set ZN*. Il che significa x è comunque inferiore a N, e se x è inferiore a N, allora x modulo N ti dà x tale che l'effetto della mod non capita affatto. Così questo dimostra che la tua funzione fd e fe si inversano reciprocamente. Qui provate anche che la mia funzione fe (x) è una biezione, e questo significa, è uno - a - uno sulla mappatura. Per questo, consideriamo una coppia arbitraria di input x1, x2, dal set ZN*, e diciamo le immagini resultanti di x1 e x2 come per la funzione fe, sono y1 e y2. Ora, se y1 e y2 sono uguali, questo significa, x1e modulo N, è uguale a x2e modulo N, questo significa, se alzo entrambi i lati all'esponente d, ottengo x1 di modulo N è uguale al x2 ed modulo N. Questo praticamente significa che x1 è uguale a x2, perché x1 ed il modulo N, non è altro che x1 e x2 ed il modulo N non è altro che x2. Quindi questo significa, se prendo una mappatura arbitraria x1, x2 alla stessa y, poi fondamentalmente finendo per dimostrare che x1 è uguale a x2 e da qui ho capito complessivamente che la mia funzione fe è una permutazione qui. (Riferimento Slide Time: 10 :32) Ora, discutiamo di supplizio risultato, che sarà correlato all'assunzione RSA, di cui discuteremo finalmente. Questo si chiama Factoring Presupposto, e l'intuizione dietro questa assunzione è che, se si dà il prodotto di due grandi numeri primi arbitrari, si scopre che trovare i fattori primi è effettivamente un compito difficile. Si tratta di un problema molto conosciuto e ben studiato, studiato nel corso di diversi secoli. E fino ad ora non abbiamo algoritmi in politempo efficienti per sfaccettare un prodotto di due numeri primi arbitrari, se quei numeri primi vengono scelti arbitrariamente. Quindi, questa intuizione o la durezza di questo problema vanno formalizzate da un esperimento, e per quell' esperimento, cerchiamo prima di tutto di definire un algoritmo, che chiamiamo algoritmo di GenModulus. Praticamente picchia due numeri primi di n bit casuali, diciamo p e q, e ci sono algoritmi ben noti per scegliere numeri primi casuali. Non sto entrando nei dettagli esatti su come esattamente si scelgono quei due numeri casuali casuali, in polpa (n) tempo. Potete fare riferimento al libro di Katz e Lindell per l'esatto algoritmo. Ora, una volta p e q vengono scelti, si calcola il modulo, ovvero N, che è il prodotto p e q. Ora, il Factoring Presupposto, rispetto all'algoritmo di GenModulus, è modellato come un esperimento, che chiamiamo Factor Experiment, e le regole di quell' esperimento sono le seguenti. Lo sfidante esegue l'algoritmo di GenModulus, genera il parametro N, p e q e la sfida viene lanciata all'avversario, ovvero N, e la sfida per l'avversario è quella di inventarsi con la sua prima fattorizzazione, ovvero p e q. Così, sottopone un paio di numeri, p di c e q si trova, e diciamo che l'uscita dell'esperimento è del 1, cioè l'avversario ha vinto l'esperimento se effettivamente, la coppia p's, q è esattamente uguale alla prima fattorizzazione del tuo modulus N, e diciamo che il Factoring Presupposto detiene rispetto al nostro algoritmo GenModulus, se per ogni avversario politempo, la probabilità che l'avversario possa arrivare con una corretta fattorizzazione del modulo N, è in alto delimitato da qualche funzione trascurabile. Notate che, c'è sempre una strategia indovinosa da parte di un avversario, può indovinare alcuni p di p e q. e con probabilità non zero, potrebbe infatti con la corretta fattorizzazione di N. (Fare Slide Time: 13.00) Quello che vogliamo è sostanzialmente che nessun avversario politempo dovrebbe essere in grado di fare qualcosa di meglio. Questa è sostanzialmente l'intuizione di questo esperimento. Ora, finalmente vediamo l'assunzione di RSA qui. Così, si scopre che Factoring Presupposto, anche se sembra un candidato One-Way Function, questo significa che se ti do il prodotto di due numeri primi arbitrari e ti sfido a inventarti la fattorizzazione, allora che sembra un candidato One-Way Function. Ma proprio in base a questa candidata One-Way Function non possiamo ottenere direttamente un pratico crittosistema pubblico - chiave. Quindi, per aggirarlo, introduciamo un problema correlato, che chiamiamo come problema RSA, la cui difficoltà è legata alla durezza del problema del factoring. Quindi, questo problema RSA è descritto rispetto ad un altro algoritmo di generazione di parametri, che chiamiamo GenRSA. Quindi, cosa fa l'algoritmo di GenRSA, esegue per la prima volta l'algoritmo di GenModulus e raccogliendo primes casuali p e q di dimensioni n - bit ciascuno, e li multiplica per ottenere il modulo N, e ora calcola il valore φ (N) ed è computabile perché φ (N) non è altro che il prodotto di p-1 e q-1. Poi questo algoritmo di GenRSA picchia un esponente e tale che e è relativamente primo o co - prime a φ (N). E dato che e è co - prime a φ (N), eseguendo l'algoritmo di Euclide Euclide s, si può calcolare l'inverso moltiplicativo d di e modulo φ (N). Complessivamente, questo algoritmo di GenRSA ora supera N, p, q, e e d. Intuitivamente, il problema RSA è, se ci si dà solo un modulo pubblico N e l'esponente pubblico e l'elemento casuale y dal set ZN*, allora la sfida per te è quella di calcolare la radice di y modulo N senza conoscere realmente il valore reale di d o senza conoscere la prima fattorizzazione di N. Io sottolineo che la sfida è quella di calcolare la radice modulo N perché se ti sfido a calcolare la radice senza modulo N, è molto facile farlo. La sfida qui è quella di calcolare il valore di eth radice della random y modulo N, formalizzata da questo esperimento che io chiamo come esperimento RSA-inv. L'esperimento è il seguente, lo sfidante esegue l'algoritmo di GenRSA per generare i parametri N, p, q, e, d sono scelti a caso dal set ZN*. Ancora, se vi state chiedendo come sia possibile cogliere un elemento casuale dal set ZN* in poli (n) tempo, beh è possibile, potete vedere il libro di riferimento di Katz e Lindell dove si dà l'algoritmo su come scegliere elementi casuali. Ora la sfida per l'avversario è scoprire la radice di questa casuale y appena basata sulla conoscenza del modulo pubblico N e dell'esponente pubblico e. Quindi, deve produrre un elemento di gruppo diciamo x e diciamo che l'avversario ha vinto l'esperimento o la produzione dell'esperimento è di 1, se e solo se, x è effettivamente la radice di random y modulo N, ovvero se xe modulo N è y. Diciamo che l'assunzione di RSA detiene rispetto a questo algoritmo di GenRSA, se per ogni algoritmo in politempo che partecipa a questo esperimento, la probabilità che possa arrivare con la giusta radice di una y casuale è quella superiore delimitata da qualche probabilità trascurabile. (Riferimento Slide Time: 16 :23) Ora, lasciate che i signori tentino di confrontare l'assunzione RSA e il Factoring Presupposto, perché su un alto livello potrebbero sembrare simili a voi. Così, sulla tua mano sinistra hai l'esperimento di factoring in cui la sfida per l'avversario è quella di arrivare con i fattori primi del modulo pubblico N. Sulla parte destra, hai l'esperimento di modellazione del problema RSA in cui l'avversario è ora dato qualche informazione extra come parte della sua sfida, ovvero, viene dato il pubblico esponente e il suo obiettivo è arrivare con la radice di y modulo N. Si scopre che possiamo dimostrare che se la supposizione RSA, poi Factoring Presupposto trattiene e questo può essere dimostrato contrapposto, ovvero, se si ipotizza che il factoring è computazionalmente facile, questo significa che è possibile per un avversario politempo arrivare con una prima fattorizzazione p, q di un modulus N. Poi, una volta sfaccettati il tuo modulus N nella sua prima fattorizzazione di p e q, allora potrai facilmente calcolare φ (N) perché φ (N) non è altro che p-1 volte q-1. E se φ (N) è computabile in politempo e anyhow e ti viene dato, allora gestendo l'algoritmo Euclide esteso, potrai anche tu stesso calcolare l'inverso moltiplicativo di e, ovvero d, e una volta computi d, la radice di y non è altro che yd modulo N. Questo significa che questa implicazione è vera. D'altra parte, lasciamo che i signori si sforzino di considerare il rapporto tra il Factoring Presupposto e la RSA, nel senso, possiamo dire che se Factoring Assunzione detiene, allora la supposizione RSA e noi non abbiamo alcuna risposta per questo. Questo significa che non possiamo dimostrare che se l'assunzione di RSA non regge e il Factoring Presupposto non regge. Si tratta di un grande problema all'aperto perché potrebbe esserci un modo per risolvere in modo efficiente il problema RSA senza realmente fattorizzare il proprio modulistica. Ma possiamo avere qualche tipo di tradeoff e per la maggior parte delle tante istanziazioni pratiche, si tratta di un click comune, utilizzato per rendere veloce il processo di codifica. Ora, supponiamo di usare un'istanziazione di RSA, dove abbiamo fissato e di essere 3, e diciamo che siamo considerati un'applicazione dove i messaggi sottostanti m ∈ ZN*, ma la grandezza di m è rigorosamente inferiore alla radice del modulo N. E se vi state chiedendo che tipo di applicazioni incontri un tale tipo di m, se in seguito vedremo la crittografia Hybrid RSA. Poi la dimensione del modulo che tiriamo tipicamente è di dimensioni 1024, e il messaggio che vorremmo criptare alla crittografia Hybrid RSA sarà approssimativamente una stringa di bit uniformemente casuale del 300 - bit e ci imposteremo per essere 3. Se così fosse, allora il testo di cifratura sarà m3 modulo N. Ma dato che la mia grandezza di m è rigorosamente inferiore alla radice cubo di m, io o m3 modulo N sarà equivalente al cubo intero e l'effetto della mod N non avrà affatto luogo. E se l'avversario è consapevole del fatto che stiamo utilizzando un'applicazione con testo di pianura sottostante, è di magnitudo rigorosamente inferiore alla radice di cubo di modulus N, allora si renderà conto anche che il sottostante m, che è stato crittografato. Il suo cubo è effettivamente contenuto nel testo di cifratura c, ovvero il cubo intero non il cubo modulo, ed è molto facile recuperare il sottostante sconosciuto m dalla c trovando solo la radice cubo intera del testo di cifratura c, che può essere computato in poli delle dimensioni di calcolo della quantità di calcolo. Ecco quindi la nostra prima classe di attacco. (Riferimento Slide Time: 14 :14) Possiamo avere molti altri tipi di attacco possibili su Plain RSA Cipher, quindi immaginate per il momento che stiamo valutando un'applicazione in cui lo stesso messaggio deve essere crittografato e inviato a più ricevitori. Quindi, immaginate se diciamo di avere 3 ricevitori, ricevitore 1, 2 e 3 ognuno di esso ha rispettivamente il suo modulus N1, N2 e N3. Ma ognuno di loro sta usando uno stesso esponente pubblico diciamo 3, e ovviamente un diverso esponente di decodifica d1, d2 e d3 dove d1 è l'inverso moltiplicativo di 3 modulo N1, d2 è l'inverso moltiplicativo di 3 modulo N2 e così via. Quindi, la chiave pubblica, disponibile in ambito pubblico sono le rispettive chiavi pubbliche dei 3 ricevitori e immagina di avere un mittente, che ha un messaggio casuale m ∈ ZN1 *, oltre che ZN2 *, oltre che ZN3 * casualmente scelto e dire che vuole cifrare e inviare uno stesso messaggio ai 3 ricevitori. Quindi, calcola c1 che sarà il m3 modulo N1, c2 che sarà il m3 modulo N2 e così via. Ora, supponiamo che questo modulo N1, N2 e N3, siano primi a coppia. Se non supporre per esempio, il GCD di Ni e Nj non è 1, non sono co - primi l'uno all'altro. Il che significa che esiste un fattore comune di Ni e Nj, quindi usando quel fattore comune, è computazionalmente facile per sfacciarsi sia il modulo Ni che Nj e dire per esempio se Ni è factorizzabile, e dato che ei è anche noto pubblicamente e se conosciamo i fattori Ni, possiamo calcolare il valore di i). E una volta che conosciamo i) e ei, possiamo calcolare il valore di di in quantità di tempo polinomiale. Se di è computabile, allora qualsiasi codifica destinata al ricevitore ith può essere decodificata dall'avversario. Quindi, è sicuro ipotizza per il momento che coppia saggia, tutti i modulistica N1, N2 e N3, sono co - primi tra loro. Ora, fatemi definire un modulo più grande N*, che è il prodotto di tutti i tre modulistici qui, ovvero N1, N2 e N3, e dal momento che il mio sottostante testo in chiaro m, che è il mittente ha criptato ∈ ZN1 *, oltre che ZN2 *, oltre che ZN3 *. Il che significa che m è rigorosamente inferiore a N1, è rigorosamente inferiore a N2, è rigorosamente inferiore a N3. Questo significa che il numero intero m3 sarà rigorosamente inferiore al più grande modulo N* e ora quello che posso fare è dato che il mio modulo N1, N2 e N2, N3 e N1, N3 sono co - primi tra loro. Posso invocare un ottimo risultato dalla Teoria Numero, che chiamiamo il Resto Teorema cinese, che dice che se il vostro singolo modulo N1, N2 e N3 sono co prime. Poi è possibile calcolare il valore intero m3 in quantità di tempo polinomiale, polinomiale nelle dimensioni del rispettivo modulo N1, N2 e N3 tale che il m3 recuperato sostanzialmente soddisfa il sistema di seguire equazioni modulari. Quindi, ti viene dato il valore c1, che è qualche numero intero m3 modulo N1, dove m3 non è noto, e ti viene dato c2, che è lo stesso m3 modulo N2 e ti viene dato il valore di c3, che è lo stesso m3 modulo N3, e se i tuoi N1, N2 e N3, i rispettivi modulus sono co - primi tra loro. Poi quello che in sostanza il Resto Teorema cinese dice è possibile recuperare quella sconosciuta m3 in quantità polinomiale di calcolo. Poi, applicando il Chinese Restanti Teorem, un avversario che ha eavesato questi tre testi di cifratura c1, c2, c3, può applicare il Resto Teorema cinese, e recuperare lo sconosciuto m3. Una volta recuperato il numero intero sconosciuto m3, può scoprire l'esatto m. Quindi, ancora questo è un altro attacco, che è possibile sul Plain RSA Cipher anche se supponiamo che un mittente faccia il messaggio m ∈ ZN* impostato. Si scopre che potrebbero esserci diversi altri possibili attacchi, che possono essere lanciati sul processo di crittografia di Plain RSA. (Riferimento Slide Time: 18 :48) Così, questo ci porta al concetto di quello che chiamiamo crittosistema pubblico-chiave RSA e sostanzialmente l'idea generale qui è che, abbiamo visto già che il processo di crittografia di Plain RSA è un processo di codifica deterministico. Non c'è casualità interna nascosta e se non c'è casualità interna, allora non possiamo mai sperare di ottenere la sicurezza CPA. Quindi, l'idea alla base del processo di crittografia RSA imbottita è che cerchiamo di accodare alcuni bit - stringhe casuali ai bit di quercia, che vogliamo crittografare e convertire tutto in un elemento di gruppo nel set ZN*, poi applichiamo la funzione RSA per la crittografia. D'altra parte, la fine della decodifica, taglieremo le stringhe di bit casuali, che abbiamo aggiunto alle stringhe di bit plain prima della crittografia e poi quella sarà la querelle recuperata.