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 crittografiaDr. Ashish ChoudhuryDipartimento di Computer ScienceInternational Institute of Information Technology – BangaloreLezione – 45RSA AssunzioneCiao a tutti, benvenuto a questa lezione.(Fare Slide Time: 00.42)Così giusto per recap nell'ultima lezione, abbiamo visto Candidate Public Encryption Schema, CPA secure Public Encryption Scheme, principalmente lo schema di crittografia El Gamal. In questa lezione e la lezione successiva, parleremo di un altro Candidato Public Encryption Schema basato sul diverso problema hard, che chiamiamo assunzione RSA, che ci condurrà in un altro schema di crittografia pubblica ovvero il RSA Public Encryption Schema.(Rinvio Slide Time: 00.58)Quindi per capire l'ipotesi RSA, cerchiamo prima di capire il set ZN*. Così ZN*fondamentalmente è 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 a il modulo N. Namely, il loro GCD è 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 - prime al modulus 10, ed è facile da vedere che se il modulus N è primo, allora il set ZN* consisteva sostanzialmente di tutti gli elementi da 1 a N-1.Così, un fatto ben noto dalla teoria dei numeri la cui prova I am skipping è che il set ZN*costituisca un gruppo e soddisfa tutti gli assiomi del gruppo.Così, ad esempio, ho disegnato la matrice per gli elementi in Z10 *, ovvero 1, 3, 7 e 9, e il risultato dell'esecuzione la moltiplicazione dell'operazione modulo 10 per qualsiasi elemento di coppia da il set e ora potete vedere che tutti gli assiomi dei gruppi sono soddisfatti ed è per questo che questo è un gruppo. Del resto, un fatto ben noto dalla teoria dei numeri è che abbiamo algoritmi in politempo per il calcolo dell'inverso moltiplicativo, che denota da, a-1, per qualsiasi elemento a nel set ZN*. E c'è un algoritmo ben noto per quello, che chiamiamo come Extended Euclide ' s GCD algoritmo, che discuteremo in una delle nostre successive lezioni, e il tempo di esecuzione di che algoritmo è polinomiale nel numero di bit che dobbiamo rappresentare il modulus N.(Fare Slide Time: 02.47)Così, facciamo discutere a fianco di Euler Tv Totient Function, 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 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, ci sono questi molti 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. Così 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 4 non è altro che p-1, ovvero 2 - 1 moltiplicato per q-1, che è 5-1, e infine un'altra proprietà interessante che utilizzeremo da Numero Teoria è che, per qualsiasi elemento a nello ZN*, un φ (N) modulo N è 1. Questo significa, se N è un primo p, allora questo φ (N) è niente ma p-1, quindi otteniamo ap-1 modulo p to be 1.Questa proprietà o questo risultato è chiamato anche come Fermat s Little Theorem, e ci troviamo 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 dell'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'axcome 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 completo un φ (N) modulo N, stai andando per darti la risposta 1. Quindi, tutti questi lotti vi daranno la risposta 1, 1, 1, 1 e 1 moltiplicato per 1 vi darà 1. Quindi, siete finalmente rimasti con l'ultimo lotto, che ha ax modulo φ (N). Così, ecco come otteniamo questo corollario.(Vedi Slide Time: 06.03)Così, con tutta questa matematica in atto, ora cerchiamo di capire la permutazione RSA. Quindi questa permutazione RSA è una mappatura dal set ZN* a ZN*, così il modo in cui questa permutazione è definito come segue. Immagina, ti viene dato un esponente e, che è maggiore di 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 un e b, tale che GCD di un 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. Così, il mio modulus in questo caso è φ (N), perché e è co - prime a φ (N), e se e è co prime a φ (N), utilizzando l'algoritmo Euclide esteso, posso trovare d dove e e d costituisce i loro reciproci ingreti moltiplicativi.Che significa, e tempi d modulo φ (N) e d tempi e modulo φ (N) è 1. Ora, la permutazione RSA è definita come segue. Per andare nella direzione in avanti, la funzione è fe, e a calcola il valore di fe (x) dove x è membro di ZN*, praticamente compaiamo xee 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.dichiaro qui che la funzione fd è l'inverso della funzione fe e viceversa. Così, per quel considerare qualsiasi arbitrario x qui, appartenente a ZN*, e dire che la mappa a y, come per la funzione fe,così la mia y non è altro che xe, e ora lascia che i signori ci vedano ciò che 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 xevolte d modulo N, e utilizzando il corollario che abbiamo indicato nell'ultima slide, modulo fisso N nell'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 all'altro.Così, nell'esponente, è e tempi d modulo φ (N) si riduce a 1, quindi ho ottenuto che questo fissomodulo N non è altro che x modulo N, e dato che ho scelto la mia x per appartenere al set ZN*.Che significa x è comunque inferiore a N, e se x è inferiore a N, poi x modulo N ti dà x tale che l'effetto della mod non capita affatto. Così questo dimostra che la tua funzione fd e fesono reciprocamente inversate l'una dall'altra.Provo anche qui ora 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 dicono 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 x1ed il modulo N è uguale al x2modulo N.Questo praticamente significa che x1 è uguale a x2, perché x1ed il modulo N, non è altro che x1 e x2edmodulo N non è altro che x2. Quindi questo significa, se prendo una mappatura arbitraria x1, x2 alla stessa y, allora fondamentalmente finendo per dimostrare che x1 è uguale a x2, e da qui ho capito complessivamente che la mia funzione fe è una permutazione qui.(Fare Slide Time: 10.32)Ora, discutiamone supplienza, che sarà correlata all'assunzione di RSA, che discuteremo finalmente. Questo si chiama Factoring Presupposto, e l'intuizione dietro questo presupposto è che, se si è dato il prodotto di due grandi numeri primi arbitrari, si gira per 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 la fatturazione di un prodotto di due numeri primi arbitrari, se quei numeri primi vengono scelti arbitrariamente. Quindi, questa intuizione o la durezza di questo problema sarà formalizzata da un esperimento, e per questo esperimento , cerchiamo prima di tutto di definire un algoritmo, che chiamiamo algoritmo di GenModulus. Esso praticamente picchia due numeri primi di n bit casuali, diciamo p e q, e ci sono ben ben noti algoritmi per scegliere numeri primi casuali.Non sto entrando nei dettagli esatti su come si scelgono esattamente quei due numeri casuali di primo , in polenta (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 come Fattore 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 è a inventarsi con la sua prima fattorizzazione, ovvero p e q. Così, sottopone un paio di numeri, p e q. e diciamo che l'output dell'esperimento è di 1, cioè l'avversario ha vinto l'esperimento se effettivamente, la coppia p pi, 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 up con correttezza corretta 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 fatturazione 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 una candidata One-Way Function, questo significa che se ti do il prodotto di due numeri primi arbitrari numeri primi 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 . Così, questo problema RSA è descritto rispetto ad un altro parametro di generazione generazione, che chiamiamo GenRSA.Quindi, cosa fa l'algoritmo di GenRSA, esegue per la prima volta l'algoritmo GenModulus e pick up primes p e q di dimensione n - bit ciascuno, e li ha multipli 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 Extended Euclide s s, si può calcolare l'inversore moltiplicativo di e modulo φ (N). Complessivamente, questo algoritmo GenRSA ora outmette N, p, q, e e d. Intuitivamente, il problema RSA è, se ci si dà solo un pubblico modulus 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 effettivo di d o senza conoscere la prima fattorizzazione di N.sottolineo che la sfida è quella di calcolare la radice modulo N perché se ti sfido a calcola la radice senza modulo N, è molto facile farlo. La sfida qui è a calcola il valore di eth radice del casuale y modulo N, che viene formalizzato 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 casualmente dal set ZN*. Ancora, se siete chiedenete che come raccogliere un elemento casuale dal set ZN* sia possibile in polpa (n) tempo, beh è possibile, potete vedere il libro di riferimento di Katz e Lindell dove si dà l'algoritmo di come scegliere elementi casuali.Ora la sfida per l'avversario è scoprire la radice di questa casuale y appena basata su la 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 l'output dell'esperimento è 1, se e solo se, x è effettivamente la radice di random y modulo N, ovvero se xemodulo 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 up con la radice corretta di una y è superiore a qualche probabilità trascurabile.(Fare Slide Time: 16.23)Ora, lasciate che i signori tentino di confrontare l'assunzione RSA e il Factoring Presupposto, perché su un livello alto potrebbero sembrare simili a voi. Quindi, sul tuo lato sinistro hai il factoring esperimento dove la sfida per l'avversario è quella di arrivare con i primi fattori del modulo pubblico N. Sul lato destro, hai l'esperimento di modellazione del problema RSA dove l'avversario è ora dato qualche informazione in più come parte della sua sfida, ovvero, è dato il pubblico esponente e il suo obiettivo è quello di arrivare con la radice di y modulo N.Si scopre che possiamo dimostrare che se la supposizione RSA, poi Factoring Presupposto anche detiene e questo può essere dimostrato da controfigura, ovvero, se si ipotizza che il factoring sia computazionalmente facile, questo significa che è possibile che un avversario politempo possa arrivare con una prime fattorizzazione p, q di un modulus N. Poi, una volta factorizzare il tuo modulus N nella sua prime fattorizzazione di p e q, allora puoi facilmente calcolare φ (N) perché φ (N) non è altro che ) p-1.E se φ (N) è computabile in politempo e comunque è dato a te, quindi eseguendo l'algoritmo Extended Euclide, si può calcolare autonomamente l'inverso moltiplicativo di e, ovvero d, e una volta computi d, la radice di y non è altro che yd modulo N. Che significa, questa implicazione è effettivamente vera. D'altra parte, lasciamo che i signori si sforzino di considerare il rapporto tra il Factoring Assunzione e 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 noi non possiamo dimostrare che se l'assunzione di RSA non regge e il Factoring Presupposto non hold. Si tratta di un grande problema aperto perché potrebbe esserci un modo per risolvere in modo efficiente il problema RSA senza realmente fattorizzare il proprio modulo. Perché uno dei modi per risolvere il problema RSA potrebbe essere quello di sfaccorizzare il tuo N e poi una volta che la fattorizzazione è nota, inventarsi con il valore d e così via, ma non serve essere il solo per risolvere il problema RSA. Ci potrebbero essere altri modi per compattarsi per risolvere il problema RSA in quantità polinomiale di tempo senza sfatare in realtà il tuo modulus, e in quel senso, rendendo l'assunzione di RSA è un presupposto molto forte rispetto a rendere il factoring presupposto perché difficoltà saggia, il problema del factoring sembra un problema più impugnabile, problema più difficile che risolvere il problema RSA.(Fare Slide Time: 19.05)Così, finalmente lasciaci discutere di come esattamente puoi utilizzare la tua RSA Permutazione come Trapdoor Permutazione perché nella nostra prossima lezione andremo a trattare la nostra Permutazione RSA come una permutazione diTrapdoor e vedremo che come possiamo formulare un'istanza di sistema di crittografia pubblica da questa Permutazione RSA. Quindi, per quel richiamo la definizione di One-Way Trapdoor Permutation.Quindi, è una funzione dal set x al set x, facile da calcolare per qualsiasi input dal dominio , ma il difficile da invertire da qualsiasi input casuale dal co - dominio, fino a e a meno che non venga fornito con speciali informazioni trapporta. Quindi, questo è formalizzato dicendo che più formalmente abbiamo uno schema di permutazione trapporta sul set x, che consiste in un algoritmo di Generazione di chiave , una funzione trapdoor f, e il suo inverso in cui l'algoritmo del parametro Generation esporrà un parametro pubblico e un parametro segreto, la funzione f è fondamentalmente, una funzione keyed, keyed by the public key pk e ti dà valore dal set x e ti dà un output dal set x ed è un algoritmo Deterministico e l'algoritmo corrispondente è operato da una chiave segreta, quindi la tua chiave segreta si comporta fondamentalmente come una trapdoor informazioni qui e utilizzando queste informazioni trapporta, è possibile invertito correttamente qualsiasi y dal codominio , ovvero il set x. La proprietà di correttezza che richiediamo dallo schema di permutazione di trapdoor è che per ogni coppia di parametro generata dall'algoritmo di Generazione, per ogni x dal tuo dominio, se si calcola il valore di fpk (x), e diciamo di ottenere l'output y, e ora se si inverte quella y con il tasto segreto sk, è necessario ripartire la x, e un secondo requisito è l'unico requisito di wayness, che in sostanza afferma che la tua funzione f dovrebbe comportarsi come una funzione unidirezionalità, anche se un avversario conosce il valore del parametro pk.(Fare Slide Time: 21.09)Così, vediamo come possiamo visualizzare la permutazione RSA dal set ZN* a ZN* come un'istanziazione della Permutazione di Trapdoor. Quindi, sostanzialmente RSA Trapdoor Permutation è composta dadi tre algoritmi, l'algoritmo di Generazione dei parametri non è altro che algoritmo di GenRSA, ovvero, picchi uniformemente casuali n - bit di n °, p e q, calcola il modulo N, e compone quindi le dimensioni di ZN*, ovvero φ (N).Si picchia l'esponente pubblico e, tale che e è co - prime a φ (N). Dato che e è co - prime a φ (N), eseguendo l'algoritmo Extended Euclide, l'inverso moltiplicativo di e modulo φ (N) è calcolato e i parametri pubblici sono N, e e i parametri segreti sono N, d. La funzione di direzione in avanti, ovvero la funzione fRSA, e operata con la chiave pubblica N, è come segue. Per calcolare il valore di questa funzione fRSA su un input x praticamente si è appena uscita xe modulo N, e xe modulo N può essere calcolato in polpa (n) tempo. Vedremo in seguito come esattamente questo esponente del gruppo possa essere calcolato in polinomio in n quantità di tempo. D'altra parte, se hai una trapporta cioè un parametro segreto n, d e se vuoi invertire qualsiasi dato y dal set ZN*. In sostanza devi calcolare yd modulo N. Quindi, lascia vedere se questo RSA Trapdoor Permutazione soddisfa effettivamente il requisito di un generico Sistema di Permutazione di Trapdoor. Così il requisito di correttezza afferma che, dovrebbe trattarsi di xeseguito sollevandolo a d modulo N, dovrebbe darmi la mia x e abbiamo già dimostrato che è il caso in cui abbiamo dimostrato che la funzione f e la funzione inversa RSA sono inverse tra di loro.D'altra parte, la proprietà One - Wayness da questa permutazione RSA, richiede che chiunque conosca solo il parametro pubblico, ovvero N, e, ma non conosca le informazioni del trapporta , diciamo d, senza la conoscenza delle informazioni trapporta, è difficile calcolare la radice di qualsiasi casuale y, e il suo si scopre che effettivamente è il caso se l'assunzione di RSA mantiene rispetto al tuo algoritmo di Generazione dei parametri che significa.Se effettivamente il problema RSA è difficile da risolvere rispetto a questo algoritmo RSA Generation, allora questa così chiamata permutazione RSA può essere visualizzata come un'istanziazione della tua Permutazione di Trapdoor. Così, ricordando che in una delle nostre precedenti lezioni avevamo visto che quanto genericamente riusciamo a convertire Trapdoor Permutation Scheme in un accordo chiave protocollo con debole concetto di segretezza.E ora se instanziate Trapdoor Permutation by an RSA Trapdoor Permutation, poi da utilizzando la Permutazione RSA Trapdoor, in realtà otteniamo un protocollo di scambio chiavi RSA, che ti dà una debole nozione di segretezza, ovvero il tasto resultante sarà noto al mittente e al destinatario, e l'avversario non conoscerà la chiave completa nella sua interezza. Sull' altra mano, la funzione di registrazione discreta che avevamo discusso in precedenza, non può essere visualizzata come un'istanziazione della Permutazione di Trapdoor. Perché conosciamo la funzione di forward direction, ovvero dire gxpuò essere trattata come la tua funzione di direzione di inoltro , ma non sappiamo quali debbano essere le corrispondenti informazioni trapdoor utilizzando le quali possiamo utilizzare e invertire questa funzione. Questo è un tipo di grande problema impugnabile che c'è. D'altra parte, nel contesto della permutazione RSA, abbiamo la corrispondente trapporta associata cioè l'esponente d, ovvero l'inverso moltiplicativo di e, modulo φ (N). Così questo mi porta alla fine di questa lezione. In questa lezione abbiamo introdotto l'assunzione di RSA e abbiamo visto il rapporto tra il problema RSA e il problema del factoring . Grazie.