Loading
Note di Apprendimento
Study Reminders
Support
Text Version

Gruppi ciclici a base di curve Ellittiche

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 – 41 Candidati Ciclici per Finalità Crittografiche Parte II (Riferirsi Slide Time: 00.44) Ciao a tutti, benvenuti a questa lezione in questa lezione continueremo la nostra discussione sui candidati gruppi ciclici per scopi crittografici e in questa lezione introdurremo specificatamente i gruppi ciclici basati su curve ellittiche. Iniziamo quindi con la discussione sulle curve ellittiche a base di gruppi ciclici. Allora ricordate nell'ultima lezione che avevamo visto che se p e q sono primes dove p è della forma r i tempi q + 1 e se prendiamo tutti i residui di r modulo p allora il set di resultanza che denottiamo come G costituisce un sottogruppo di Zp * e possiamo dimostrare che questo set G insieme all'operazione di moltiplicazione modulo p costituisce un gruppo ciclico. Tuttavia, si scopre che per la sicurezza pratica dobbiamo operare o selezionare valori molto grandi di questo primo p e cioè dobbiamo fare in modo che la p sia almeno 2048 bit numeri primi che in realtà finiscono per garantire che il tempo risultante del mittente e del destinatario sia anche molto lento. Quindi quello che stiamo per fare è in questa lezione che vedremo gruppi ciclici basati sui punti sulle curve ellittiche e questi sono fondamentalmente gruppi ciclici alternativi dove il problema del DLog problema e i problemi del DDH sono effettivamente ritenuti impegnativi. Più precisamente se le dimensioni di prime che stiamo per operare sono di dimensioni n bit, allora il più noto DLog solver che conosciamo per questi gruppi è di ordine 2 n / 2 e che significa la sua sufficiente per operare con un numero primo che è un numero primo di 256 bit per la maggior parte pratica e che ci fornisce instanziamenti altamente efficienti di DLog, CDH e DDH based sistemi crittografici rispetto alle instanziazioni in base ai sottogruppi di prim'ordine di Zp * a destra. Quindi questo è più punto di questo gruppo rispetto alle instanziazioni in base ai sottogruppi di primo ordine di Zp *. Un'altra proprietà interessante dei gruppi ciclici basati sulle curve ellittiche è che ci fornisce strutture aggiuntive quelle che chiamiamo pairings che non discuteremo in questo corso. Poiché questi sono concetti avanzati ma solo per le tue informazioni questa struttura aggiuntiva che chiamiamo pairing può essere utilizzata per costruire primitivi crittografici altamente avanzati come le firme aggregate, la crittografia broadcast, la crittografia funzionale e così via. (Riferimento Slide Time: 02.59) Così prima di entrare nell'esatto gruppo ciclico basato su ellittico che utilizzeremo per lo scopo crittografico lasciateci fare un warmup e vedere come sono esattamente le curve ellittiche sopra i numeri reali. Quindi lascia che R sia il set di numeri reali e let a e b be 2 numeri reali o costanti pubblicamente noti come questo rapporto tutto compreso 4a3 + 27b2 non è motivo 0.The per questa costante sarà chiaro e b consideriamo questa equazione in x e y, y2 = x3 + ax + b poi se trento i punti su questa equazione o se prendi tutte quelle x, y coppie che sono numeri reali che soddisfano questa equazione e insieme a questo se prendo un punto speciale che non ho fatto come O poi il resultante impostato come E. Così per esempio se prendo la curva o l'equazione y2 = x3 - x e trama tutto il vero x, y soddisfacendo questa equazione poi ho ottenuto questa curva nello stesso modo se prendo la curva y2 = x3 - x + 1 e trama tutto il vero x, y soddisfacendo questa equazione poi ottengo questa curva. Quindi quello che E è praticamente una volta che abbiamo aggiustato l'equazione prendiamo tutti i numeri x, y veri che soddisfa questa equazione e insieme a quello un punto speciale che denoti come O e questo speciale punto O è chiamato come il punto all'infinito che è una specie di punto immaginario che si può immaginare seduto in cima all'asse y e sdraiato su ogni linea verticale. Così potete immaginare che ogni linea verticale alla fine si incontrerà ad un orizzonte in un unico punto e quel punto in cui tutte le linee verticali si incontreranno è considerata come il punto all'infinito che sarebbe denota da questa speciale notazione O. Così è così che costruiamo il set E ora l'insieme di punti E che abbiamo definito sopra è definito una curva ellittica non singolare sul set di numeri reali e perché si chiama non singolare, è perché abbiamo assicurato la condizione 4a3 + 27b2 ≠ 0 che è una condizione necessaria e sufficiente per garantire che la curva risultante che abbiamo definito qui ovvero y2 = x3 + ax + b ha 3 radici distinte perché è un'equazione di grado 3 in x. Tuttavia, se non garantiamo questa condizione cioè 4a3 + 27b2 ≠ 0 se lasciamo che sia 0 allora la curva corrispondente o la serie di punti che otteniamo è chiamata curva ellittica singolare non avrà 3 radici distinte. (Riferimento Slide Time: 05 :55) Così è la definizione delle curve ellittiche. Ora quello che faremo qui è trovare un modo molto sofisticamente di fare esercizio di esecuzione: operazione di aggiunta sui punti su questa curva ellittica. Immaginate quindi di avere una curva ellittica non singolare rispetto ai numeri reali e definiamo l'operazione aggiuntiva su questi punti tale che il modo in cui stiamo andando a definire l'operazione di aggiunta che soddisfa tutti i nostri assiomi di gruppo e cioè che soddisfarà la proprietà di chiusura, la proprietà associatività, sarà garantito abbiamo un elemento identitario e un inverso additivo per ogni punto della curva e che garantisce che il set E insieme al funzionamento plus che definiremo ora costituisca un gruppo additivo. Così l'operazione plus è definita come segue quindi definiamo il punto all'infinito per essere l'elemento identit che è la nostra definizione. Così definiamo che se abbiamo definito un'operazione + su qualsiasi punto p su questa curva ellittica e un punto all'infinito per dare il risultato come p. Quindi se si prende qualsiasi punto p che potrebbe essere il punto all'infinito e a quel punto se si aggiunge il punto all'infinito il risultato è definito il punto p stesso. Ecco quindi una prima proprietà dell'operazione di aggiunta che abbiamo definito qui. D'altra parte, se ci si dà 2 punti P e Q sdraiati sulla curva E e diciamo le coordinate del punto P sono (x1, y1) e le coordinate del punto Q sono (x2, y2) e né P né Q è il punto all'infinito poi il modo in cui definiremo il funzionamento plus su questi 2 punti P e Q è il seguente. Così possiamo avere il 3 dei casi possibili a seconda del rapporto che intrattiene tra le coordinate di P e Q. Così il primo caso è quando x1 ≠ x2 in questo caso il modo in cui definiamo il risultato di P + Q è il seguente. Così definiamo L di x essere la linea che passa attraverso i punti P e Q. Così la sua linea retta che passa attraverso il P e Q così si ha la rappresentazione pittorica qui e let let R è il terzo punto distinto che si trova sia sulla retta che sulla curva ellittica. Quindi sto denotando le coordinate x e y del terzo punto ad essere x3, -y3 e io chiamo quel punto per essere R. Così pittorico si dice questa curva la retta passa attraverso P e Q e interseca la curva ellittica al terzo punto dice a R le cui coordinate lo denotano come x3 e -y3. Così in questo particolare esempio nella rappresentazione pittorica la coordinata y di R è in realtà positiva ma che non è sempre necessario. Ecco perché lo sto solo rappresentando come -y3 perché se per esempio se il tuo Q sarebbe stato qui allora di passaggio della retta o attraverso P e Q si sarebbe incontrato da qualche parte qui, e la coordinata y di R sarebbe stata una coordinata negativa. Quindi indipendentemente da cosa sia esattamente il caso. È solo un problema notazionale il terzo punto distinto in cui la linea intercetta la curva ellittica è densata come R e la sua coordinata x è x3 e la coordinata y è -y3. Ora quello che facciamo qui è solo riflettere il punto R lungo l'asse x e se riflettiamo il punto R lungo l'asse x la coordinata x rimarrà la stessa, ma la y coordinata il suo segno verrà modificata. Se fosse – y3 diventerà + y3 mentre se saremmo stati più plus, allora diventa meno. E il risultato dell'aggiunta di P e Q è definito come quello riflesso. Ecco quindi che il modo in cui definiamo l'operazione plus sui punti P e Q sia né P che Q sono infinity point e x1 ≠ x2. Quindi ora se vogliamo matematicamente calcolare il valore esatto di x3 e y3 ecco come possiamo compattare: si scopre che x3 e y3 sono correlati alle coordinate x1, x2, y1, y2 da questa relazione 3 = 2 − 1 − 3 − 3 − 1 e qui λ è sostanzialmente la pendenza della retta che passa ai punti P e Q arriva attraverso questa formula 2 − 1 2 − 1 e dato che siamo nel caso in cui x1 ≠ x2 che significa che il denominatore non è 0 e da qui il λ è ben definito. Ecco quindi che il funzionamento dell'operazione di aggiunta (plus) sui punti P e Q è definito per questo caso per il caso in cui x1 ≠ x2 ora ci facciamo prendere il secondo caso in cui x1 = x2 ma le coordinate y di P e Q sono esattamente opposte tra loro. Quindi in questo caso quello che facciamo qui è la linea che facciamo passare per P e Q in sostanza finisce per convergere al punto all'infinito giusto. Quindi l'idea qui è anche la stessa che in realtà passiamo una linea passa nei punti P e Q e vediamo dove esattamente incontra la curva ellittica. Ma in questo caso dato che le coordinate x di P e Q sono uguali ma solo le loro coordinate y sono diverse nel segno la retta che passa per P e Q sostanzialmente soddisfa il punto all'infinito, converge al punto all'infinito ed è per questo che definiamo l'operazione P + Q in questo caso per dare il risultato al punto all'infinito che significa possiamo interpretare 2 punti x1, y1 e x2, -y1 dove x1 e x2 sono uguali per essere l'inversa additiva tra di loro. Giusto mentre per il terzo caso in cui x1 = x2 e y1 = y2 abbiamo 2 sub - casi se y1 = 0 allora possiamo interpretare y2 da essere = -y1 perché 0 e + 0 e - 0 altrettanto giusto? quindi se y1 = 0 allora possiamo interpretare y2 per essere = - y1 e poi praticamente arriviamo al caso precedente dove x1 = x2 e y1 è - y2. In quel caso il modo in cui abbiamo definito l'operazione plus otteniamo che la sommatoria di P con lo stesso punto che in sostanza è 2P ti dà il punto all'infinito. D'altra parte se y1 non è 0 che significa dire che abbiamo un punto come questo P e vogliamo aggiungere P a se stesso allora la linea che passa per questo punto è definita in modo diverso: la linea qui è sostanzialmente la tangente a questa curva E che passa per il punto P e vediamo dove esattamente la tangente tocca la curva che chiamiamo punto R e diciamo che le coordinate di R sono x3 e -y3 che è il terzo punto, 2 dei punti sono P e il terzo punto sdraiato sulla curva è R e quello che ora facciamo è semplicemente riflettere il punto R lungo l'asse x e questo è il risultato dell'aggiunta P a se stessa. Quindi il risultato P + P, che è 2P in questo caso sarà x3, y3 e matematicamente di nuovo x3 e y3 sono esattamente gli stessi definiti per il caso in cui x1 non era uguale a x2 l'unica differenza ora è che qui la pendenza della linea è diversa rispetto al primo caso. Perché nel primo caso i punti P e Q sono punti distinti ma qui i punti P e Q sono gli stessi punti ed è per questo che la linea è la tangente e la pendenza della tangente è calcolata con questa formula 31221 + .. E dato che y1 non è 0 a destra siamo nel caso in cui y1 non è 0 il denominatore 2 volte y1 è non 0 ed è per questo che la pendenza è ben definita. (Riferirsi Slide Time: 13.55) Così è il modo in cui eseguiamo l'operazione di aggiunta per le curve ellittiche definite sopra la serie di numeri reali ma come ho detto prima per i primitivi di crittografia vogliamo operare su un set che ha una dimensione finita che è per questo che ora stiamo andando a compere operazioni su curve ellittiche modulo numero primo che non avranno gradevoli rappresentazioni geometriche come abbiamo avuto per le curve ellittiche sui numeri reali ma di proprietà possiamo estendere la definizione dell'operazione plus come abbiamo fatto per il caso di numeri reali anche qui. Ecco come definiamo le curve ellittiche modulo un primo: così lasciamo che E sia un ellittico non singolare sul set Zp praticamente quello che significa è che formiamo un'equazione di curva ellittica qui cioè l'equazione è y2 = x3 + ax + b modulo p e ci prendiamo tutti x, y elements o x, y coppie dal set Zp x Zp e prendiamo tutti gli elementi della forma x, y dove x è nella gamma da 0 a p - 1 e y è anche nella gamma da 0 a p-1 che soddisfa questa equazione e insieme a quelle x, y coppie prendiamo il punto immaginario speciale cioè il punto all'infinito.Così come è stato il caso per le curve ellittiche definite sopra l'insieme dei numeri reali il punto all'infinito serve come elemento di identità e cioè definiamo che qualsiasi non punto P appartenente allo stato E se eseguiamo l'operazione plus rispetto al punto all'infinito poi torniamo allo stesso punto P mentre se abbiamo 2 punti P e Q appartenenti al set E che non sono i punti all'infinito e diciamo che le coordinate di P sono x1, y1 e x2, y2 dove x1, y1, x2, y2 sono tutti elementi dello stato Zp poi l'operazione plus è definita come segue. Per il caso in cui x1 = x2 e y1 = - y2 definiamo P + Q per essere infinito, questo è esattamente il caso in cui questo è lo stesso del caso 2 per le curve ellittiche sui numeri reali. Mentre se diversamente se x1 ≠ x2 o y1 ≠ y2 allora definiamo P + Q da essere (x3, y3) dove x3 e y3 sono elementi di Zp e dove x3 sarà questo valore cioè sarà &ldash; 2 – x2 di corso tutto modulo p e y3 sarà λ tempi (x1 – x3) – y1 modulo p destra e &ldambda; sarà calcolato in modo diverso per 2 sub - casi: se P = Q poi λ è definito in questo modo cioè (3x12 + a) * (2 y1-1) e questo sostanzialmente corrisponde a questo caso che è come abbiamo definito x3, y3 per il caso numero reale e se P ≠ Q poi la λ è sostanzialmente la pendenza della linea che passa attraverso i punti P e Q che sostanzialmente è simile al primo caso per le curve ellittiche sul numero reale. E si scopre che tutte le operazioni plus e tutte le operazioni di moltiplicazione che stiamo eseguendo qui sono modulo p quando in realtà stiamo eseguendo operazioni sulle curve ellittiche modulo p e se vedete qui il modo in cui abbiamo definito λ questo è l'elemento 2 volte y1-1 non è 2 /y1. Non è così. Questo deve essere interpretato come l'elemento 2 volte y1 &ld'inverso moltiplicativo che esiste perché stiamo eseguendo operazione modulo prime p e allo stesso modo per il secondo caso in cui &ldambda; è di questo modulo 2 − 1 2 − 1, questo (x2 - x1) -1 è l'inverso moltiplicativo dell'elemento (x2 - x1) modulo p che è garantito anche perché x2 - x1 sarà un valore non 0. Così è così che si estendono naturalmente la definizione dell'operazione plus per le curve ellittiche definite sopra modulo primo. (Riferimento Slide Time: 18 :18) E per un'illustrazione facciamo fare questo esempio diciamo che eseguo tutte le mie operazioni su Z11. Prendo la mia curva per essere equazione x3 + x + 6 modulo 11 e prendo il mio set E per essere il set di tutti x, y appartenente al set Z11 x Z11 soddisfa questa equazione insieme al punto all'infinito. Quindi se prendete tutte x, y appartenente al set Z11 x Z11 e vedere quale di loro soddisfa questa equazione allora otteniamo il set E per consistere in questi valori tutte le coppie soddisfano questa equazione modulo 11 e insieme a quella abbiamo un punto all'infinito. Dato che la dimensione di questo E è un numero primo cioè abbiamo 13 entità in questo set E ne consegue da un fatto basilare dalla teoria dei numeri che il set E insieme al funzionamento plus che abbiamo definito costituisce un gruppo ciclico additivo e dato che l'ordine di questo gruppo è un numero primo ogni elemento di questo gruppo eccetto l'elemento identit che è il punto all'infinito può essere trattato come il generatore per questo gruppo. Così per esempio possiamo prendere l'elemento (2, 7) appartenente al set E che è un elemento non identit e si può verificare che effettivamente costituisca un generatore e cioè poteri diversi di questo elemento (2, 7) vi darà tutti gli elementi dello stato E. Così 0 volte g come per la definizione ti dà l'elemento d'identità cioè il punto all'infinito e se eseguiamo l'operazione 1 volte g, 2 volte g, 3 volte g poi il modo in cui abbiamo definito l'operazione di gruppo additiva ci riprenderemo ognuno degli elementi dallo stato E cioè gli elementi non identici del set E una volta, questo significa che l'elemento 2,7 effettivamente costituisce un generatore del set E. (Fare Slide Time: 20.12) Ora abbiamo un altro gruppo candidato ovvero i gruppi ciclici a base ellittica e vediamo come esattamente il problema di DLog, problema CDH e problema DDH sembrerà su questi gruppi perché nella descrizione del problema DLog, DDH e CDH che avevamo visto nell'ultima lezione abbiamo ipotizzato che l'operazione di gruppo di sottolineatura sia l'operazione moltiplicativa ma ora vogliamo solo ripartire quelle definizioni nei gruppi ciclici a curva ellittica. Ecco quindi la descrizione fornita di un gruppo ciclico basato sui punti sulla curva ellittica modulo primo e dire la dimensione del gruppo è un numero primo q e ti viene dato un generatore che significa diversi poteri di g e cioè fino a q – 1 ° potere di g ti avrebbe dato il tutto il set E. Poi il problema DLog è come segue lo sfidante qui picchia un indice casuale dal set 0 a q – 1. E dà g α tempi g che non è altro, ma l'elemento g aggiunto a se stesso (α – 1) e la sfida per l'avversario è scoprire l'indice α C'è un problema CDH è lo sfidante ha scelto 2 punti casuali dalla curva ellittica raccogliendo gli indici α e β e computing α times g e β times g e l'obiettivo dell'informativa è quello di calcolare la funzione Diffie Hellman senza conoscere α .E il problema DDH è lo sfidante in cui i primi 2 componenti sono punti casuali dalla curva ellittica e il terzo componente è l'uscita della funzione DH la funzione Diffie Hellman rispetto ai primi 2 componenti o un punto casuale dalla curva e l'obiettivo dell'avversario è trovare fuori se sta vedendo un tripletto di Diffie Hellman o un tripletto non Diffie Hellman (Fare Slide Time: 22.06) Così ora abbiamo visto la definizione di curve ellittiche per applicazioni crittografiche così la prossima domanda che vorremmo rispondere è: è il caso che tutte le curve ellittiche modulo siano adatte per applicazioni crittografiche? Così prima di rispondere che vediamo un risultato interessante per la curva ellittica in base alla curva ellittica modulo primo. Quindi facciamo che p sia un primo e diciamo E sia una curva ellittica arbitraria definita su Zp che potrebbe essere una curva singolare, curva non singolare cioè dire E è la raccolta di tutte le x, y coppie che soddisfano questa equazione insieme al punto all'infinito poi un legato molto ben noto che viene chiamato come Hasse bound ti dà un limite inferiore oltre che superiore sul numero di punti che abbiamo su questa curva ellittica. Quindi questo è il legato più basso (e questo è il tuo legato superiore (ed è interessante che abbiamo algoritmi di tempo polati polinomiali nel numero di bit che abbiamo bisogno di rappresentare un primo p che può darti la cardinalità della curva ellittica, abbiamo anche algoritmi di tempo polati per scegliere punti casuali dalla curva, abbiamo anche algoritmi a tempo di polpa per l'aggiunta di 2 punti e sappiamo anche come generare una curva ellittica dove la dimensione della curva ellittica è un numero primo. Quindi la prossima domanda che vorremmo rispondere è che sono i DLog, CDH e DDHproblem computazionalmente difficili da risolvere in ogni gruppo ciclico basato su curva ellittica e la risposta non è davvero. Ci sono quindi alcune curve che dovremmo assolutamente evitare per instantificare primitivi crittografici. Quindi non possiamo prendere le curve definite sopra Zp dove le dimensioni della curva o il numero di punti sulla curva sono esattamente p che perché esistono algoritmi ben noti per risolvere i problemi DLog in quei gruppi, quindi queste curve sono chiamate curve anomale. Allo stesso modo dovremmo evitare curve dove le dimensioni della curva p + 1 che si chiamano curve super singolari e dovremmo anche evitare curve dove le dimensioni della curva sono pk - 1 per un piccolo gruppo. Tutte queste curve sono curve crittograficamente deboli perché come dicevo prima le istanze di problema DLog sono molto facili da risolvere in questo gruppo. Questo significa che se domani si propone una nuova curva ellittica basata su modulo modulo prima dobbiamo analizzare rigorosamente la proprietà di sicurezza di quelle curve ellittiche prima di prendere quelle curve ellittiche ed eseguire operazioni su quelle curve per istanziare qualsiasi tipo di crittografia primitiva ad esempio un protocollo di scambio chiave Diffie Hellman e si scopre che analizzare qualsiasi ellittico appena proposto è un compito molto impegnativo. Quindi un'alternativa che si può fare è che è possibile fidarsi e utilizzare qualsiasi delle curve consigliate NIST se ad esempio curva P256, curva 25519 che sono state rigorosamente analizzate da NIST e sostengono di non aver riscontrato alcuna debolezza in quelle curve in termini di risoluzione del problema DLog che significa che non esiste algoritmi in politempo per risolvere il problema di DLog per il calcolo del Dlog di qualsiasi punto dati casualmente su quelle curve. Ma dovreste fidarvi della rivendicazione di NIST a vostro rischio ed è per questo che quando un governo di qualsiasi paese cerca di adottare qualsiasi primitivo crittografico dove il gruppo ciclico sottostante si basa su curve ellittiche allora diventano molto scettici di usare o fidarsi delle curve che sono consigliate da NIST perché ritengono che ci potrebbero essere delle scappatoie che solo NIST conosce, ma non è conosciuta nel dominio pubblico ed è per questo che il governo per tali applicazioni critiche si spinge ad arrivare a nuove curve e a cercare di analizzare quelle curve e utilizzare quelle curve per istanziare i primitivi di crittografia. Ma si scopre che per molti scopi pratici queste curve sono molto popolate per istanziare la curva ellittica e i gruppi ciclici per istanziare i primitivi di crittografia. Così questo mi porta alla fine di questa lezione solo per riassumere in questa lezione abbiamo introdotto la seconda classe di gruppi ciclici in cui crediamo che il problema DLog, CDH e DDH sia difficile cioè i gruppi ciclici basati su curve ellittiche modulo primo. Il vantaggio di questi gruppi rispetto ai gruppi ciclici Zp * moltiplicativo modulo p è che qui i migliori algoritmi conosciuti per risolvere il problema DLog sono dell'ordine 2n/2. Quindi non dobbiamo operare con modulistica molto grande ovvero 2048 bit modulo che era il caso per i sottogruppi ciclici di Zp * il suo bastimento per impostare il modello come dimensioni a 256 e otteniamo lo stesso livello di sicurezza che ci si potrebbe aspettare da AES 128 e non solo che i gruppi ciclici basati su curve ellittiche ti danno un'altra struttura aggiuntiva che chiamiamo pairings che