Loading
Note di Apprendimento
Study Reminders
Support
Text Version

Gruppi ciclici candidati

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 ScienceIndian Institute of Science – BangaloreCollezione - 40Candidati Ciclici per Scopi Crittografici parte I(Riferimento Slide Time: 00.27)Ciao a tutti. Benvenuti a questa lezione. Così il piano per questa lezione è il seguente. Noi introdurremo alcuni gruppi ciclici candidati in cui crediamo che il problema del DDH, il problema CDH e i problemi discreti siano effettivamente difficili da risolvere. Ovvero, introdurremo i gruppi ciclici ordine di primo ordine . (Riferimento Slide Time: 00.46)Così iniziamo la nostra discussione con l'importanza di buoni gruppi ciclici. Ricordate quindi che in l'ultima lezione abbiamo visto la definizione dell'assunzione DLog, assunzione di CDH e assunzione di DDH. Quindi se stiamo progettando qualsiasi primitivo crittografico la cui sicurezza è basata sulla durezza di questi problemi, allora dobbiamo scegliere opportunamente i gruppi ciclici sottostanti.Perché se i gruppi ciclici sottostanti che usiamo per istanziare la primitiva crittografica, se in quei gruppi questi problemi sono più facili da risolvere, allora il primitivo crittografico non sarà più sicuro. Quindi ora la domanda interessante è per quali gruppi ciclici o per i quali candidati ciclabili effettivamente questi problemi, ovvero il problema DLog, il problema CDH e il problema del DDH sono difficili da risolvere. Quindi ricordati nell'ultima lezione i passi concreti del protocollo Diffie – Hellman Key Exchangeipotizziamo che stiamo operando su un gruppo in cui il problema DLog, CDH e DDH sono effettivamente difficili. Ma ora la nostra domanda è come esattamente troviamo quei gruppi. Così ci sono 2 scelte popolari di gruppi ciclici o gruppi ciclici candidati, dove crediamo che questi problemi siano effettivamente difficili da risolvere. La prima scelta sono i gruppi di ordine di primo ordine, ovvero i gruppi in cui il numero di elementi è qualche numero primo. Tuttavia, si scopre che non tutti i gruppi ciclici di primo ordine sono appropriati per applicazioni crittografiche. Infatti, vedremo qualche candidato candidato primo ordine gruppi ciclici dove problema DLog, problema CDH, problema DDH è davvero molto facile da risolvere.Ma si scopre che abbiamo altri tipi di gruppi ciclici di primo ordine, dove fortemente crediamo che DLog, CDH, problema DDH siano effettivamente difficili da risolvere. La seconda scelta di picking i gruppi ciclici candidati, è il gruppo basato su punti sulle curve ellittiche. Così in questa lezione valuteremo i gruppi di primo ordine basati su determinate proprietà. Nella lezione successiva vedremo i gruppi ciclici in base ai punti sulle curve ellittiche e poi noi confronteremo questi 2 tipi di gruppi, che uno è meglio per instanziare i primitivi crittografici, la cui sicurezza si basa sulla durezza dei problemi DLog, CDH e DDH. (Riferirsi Slide Time: 03.07)Così prima di procedere oltre, vediamo i gruppi ciclici inappropriati per applicazioni crittografiche , ovvero quali gruppi ciclici dovremmo evitare per instantificare i primitivi crittografici , la cui sicurezza è basata su DLog, CDH e DDH supposto. Quindi iniziamo con il gruppo moltiplicativo , ovvero il set Zaia?, dove Zaia? è costituito dagli elementi 1 a? − 1 e la mia operazione sottostante è modulo di moltiplicazione?. Quindi ricordati la moltiplicazione modulo? è definito come segue. Se vuoi eseguire il modulo di moltiplicazione modulo? di 2 numeri? e? dal set Zecco?, poi si esegue la moltiplicazione intero?? e prendere il resto, facendo una mod? funzionamento, che garantisce che il restante risultato residuo sia nel set 0 a? − 1. Si scopre che questo set Zecca?, insieme a questo modulo di moltiplicazione ? funzionamento, costituisce un gruppo ciclico di ordine? − 1.Perché di ordine? − 1? Perché gli elementi in questo set Zaia? sono gli elementi da 1 a? − 1, quindi ha ? − 1 numero di elementi. E da allora? è primo,? − 1 non può essere primo, ecco perché l'ordine di questo gruppo è un numero non primo. E possiamo dimostrare che questo gruppo è un gruppo ciclico. E abbiamo algoritmi efficienti per scegliere un generatore per questo gruppo data la fattorizzazione di ? − 1. Quindi ricordati i passi del protocollo di scambio di chiavi Diffie – Hellman che avevamo visto nell'ultima lezione , il pubblico allestito che ci serve c'è la descrizione del gruppo, dove come parte della descrizione del gruppo, anche i dettagli del generatore dovrebbero essere conosciuti pubblicamente. Quindi abbiamo bisogno di algoritmo in politempo per scegliere il generatore e quando dico algoritmo in politempo, io intendo polinomiale nel numero di bit che dobbiamo rappresentare l'elemento del set Zafferano?. Quindi abbiamo algoritmi in politempo, algoritmo efficiente per i generatori di picking per questo gruppo, dato a cui si dà la fattorizzazione? − 1.Così che è anche un positivo di questo gruppo. Inoltre si ritiene che il problema DLog sia effettivamente difficile da risolvere in questo gruppo, fornito? è sufficientemente grande. Ecco quindi una buona notizia rispetto a questo gruppo. Ma il problema qui è che il problema del DDH non è duro in generale in questo gruppo e questo significa che non possiamo usare questo gruppo per istanziare il protocollo di scambio Diffie – Hellman Key . Perché ricordate per la sicurezza del protocollo Diffie – Hellman Key - Exchange, ovvero per la forte - privacy del protocollo Diffie – Hellman Key - Exchange, noi abbiamo bisogno che il problema del DDH sia difficile da risolvere nel gruppo sottostante. Quindi se uso Zaffi?,insieme all'operazione di moltiplicazione modulo? come il mio gruppo ciclico sottostante ed eseguire le operazioni come per i passi del protocollo Diffie – Hellman Key - Exchange, allora non è garantito che il protocollo di scambio chiave risultante soddisfi la nozione di forte - privacy. Perché non è garantire che il problema del DDH in questo specifico gruppo sia duro. Quindi questo significa questo gruppo è adatto solo a istanziare quelle applicazioni o quelle primitive crittografiche, la cui sicurezza è solo basata sull'assunzione di DLog e non sull'assunzione di DDH, che non è il caso per il protocollo di scambio Diffie – Hellman.Così questa è la brutta notizia rispetto a questo gruppo. Quindi questo significa che potete vedere ora il gruppo Zaia?con operazione di moltiplicazione modulo? non può essere un gruppo adatto per istanziare il protocollo di scambio Diffie –Hellman, è un gruppo ciclico inappropriato. Ora consideriamo il gruppo additivo. Quindi il gruppo precedente Zaia? con la moltiplicazione operazione modulo? era un gruppo moltiplicativo. Ora consideriamo un gruppo additivo, dove il mio set è Z?,costituito dagli elementi 0 a? − 1 e la mia operazione è aggiunta modulo?, dove aggiunta modulo? sugli elementi? e? è definito come segue: si esegue l'aggiunta intera di? e ? e prendere il promemoria rispetto al modulo?. Questo è il modo in cui definiamo l'aggiunta di?e? modulo?. Quindi rispetto a questo gruppo sono noti i seguenti fatti. Prima di tutto questo gruppo è noto per essere un gruppo ciclico e che troppo di primo ordine. Perché gli elementi nel set Z? sono 0 a? − 1, ovvero ha? numero di elementi, dove? è un primo ed è noto essere un gruppo ciclico. Ecco quindi una buona notizia. E un'altra proprietà interessante di questo gruppo di prime ordine, è che ogni elemento, tranne l'elemento di identità è un generatore e questo non è solo specifico per questo gruppo. Questa proprietà detiene rispetto a qualsiasi gruppo che abbia un ordine di primo ordine. Il fatto fondamentale che deriva dall'algebra astratta è che se si dispone di un gruppo il cui ordine è primo, ovvero è costituito da numero primo di elementi, allora qualsiasi elemento da quel gruppo eccetto l'elemento di identità di quel gruppo è un generatore. Quindi il generatore di picking non è affatto andando ad essere un compito sofistito. Se operiamo o se effettuiamo operazioni in questo gruppo, voi potete scegliere qualsiasi elemento eccetto il 0, che è destinato ad essere un generatore. Tuttavia, la parte più sfortunata o il fatto più sfortunato rispetto a questo gruppo è che il problema DLog è molto, molto facile da risolvere in questo gruppo. In polenta quantità di tempo è possibile calcolare il DLog di qualsiasi elemento scelto casualmente da questo set con probabilità 1. Quindi cosa esattamente sarà un'istanza del problema DLog in questo gruppo? Quindi scegli un indice casuale?nel set 0 a? − 1, perché il tuo gruppo è di dimensioni?. E tu compatte??, dove? è il generatore conosciuto pubblicamente. E dire l'output risultante è? e la sfida per voi è quella di compimento di questo sconosciuto?, tale?? modulo? ti avrebbe dato?. Allora quali sono le cose note a te, lo sai? qui, lo stai sapendo? qui e sai che tutto è relativo modulo? qui e il tuo obiettivo è scoprilo? qui. Si scopre che possiamo facilmente calcolare? qui, moltiplicando sia il lato con l'inverso moltiplicativo di?. E inverso moltiplicativo di? modulo? può essere calcolato in quantità di tempo polinomiale. E se si moltiplicano entrambi i lati con inverni moltiplicativi di ?, poi l'effetto di? cancelli, e quello che ti resta, è?. E da qui si è ottenendo il valore di?, ovvero il registro discreto di? alla base? in quantità polinomiale di volta. Così non sto dando i dettagli completi del solutore di log discreto per questo gruppo, ma questa è l'idea globale . Quindi anche se questo gruppo specifico ha delle belle proprietà, ovvero è un ordine di primo ordine gruppo ciclico, il generatore di picking non è un compito difficile, la parte più sfortunata qui è che il problema DLog è molto, molto facile da risolvere e che implica automaticamente che il problema CDH sia facile da risolvere. E che implica automaticamente che il problema del DDH sia più facile da risolvere in questo gruppo. Quindi questo significa che questo gruppo non può essere utilizzato a tutti per istanziare qualsiasi tipo di crittografia primitivo, la cui sicurezza si basa sulla durezza del problema DLog, problema CDH, problema DDH . (Riferirsi Slide Time: 10.24)Così ora vediamo un altro gruppo, abbastanza appropriato per instanziare i primitivi crittografici basati, sulla difficoltà di DLog e CDH e problemi DDH. E questo gruppo è fondamentalmente un sottogruppo ciclico di primo ordine del gruppo Zaia?, con la moltiplicazione del funzionamento modulo?. Quindi let? e? essere primati, conosciuti pubblicamente, tale che? è correlato? in questa forma, ovvero? =?? + 1, dove? è anche pubblicamente conosciuto.E poi mi lasci definire un set? di essere il set di tutti gli elementi del modulo h? modulo?, dove happartiene al set Zaia?. Quindi pittoricamente quello che sto facendo qui è, immaginate gli elementi in questo cerchio più grande come gli elementi di Zaia? e Zaia? ha? − 1 numero di elementi, perché la mia operazione sottostante è modulo di moltiplicazione modulo?. Quello che sto facendo qui è nel set?, sono solo che raccoglie un sottoinsieme più piccolo di elementi da Zaia?. Namely sto raccogliendo tutti i residui? ?hdei residui modulo?. Perché? ?hresidui? Perché sto prendendo h da Zaia? e crescerlo al potere? e prendere modulo?. Ed è per questo che il risultato può essere visualizzato come? ?hresiduo modulo?. Per esempio, se? = 2, poi in sostanza? è costituito da tutti gli elementi , che sono quadrati perfetti modulo?, perché raccoglierò elementi del modulo h2 mod?, dove h appartiene a Zaia?.considerando se? sarebbero stati 3, allora? sostanzialmente è costituito da tutti gli elementi che sono perfetti cubo modulo? e così via. Quindi in generale se? è qualche h?, poi? è il set di tutti? ?hresidui modulo?. Quindi è così che sto elaborando questo set? qui. E un risultato molto interessante dalla teoria del numero , che non proverò qui, afferma esplicitamente che la raccolta? o il sottoinsieme ?, ovvero un sottoinsieme di Zaffio?, insieme all'operazione di moltiplicazione modulo?, costituisce un gruppo di ordine?.Namely il set? avrà? numero di elementi. E da quando ho scelto? essere un primo, questo significa l'ordine di? è un primo. E possiamo dimostrare che se si esegue l'operazione moltiplicazione modulo? sugli elementi che abbiamo selezionato nel set?, quindi soddisfa gli assiomi di gruppo . E cioè possiamo dimostrare che gli elementi in? può essere espresso come i poteri di un generatore, dove gli indici dei poteri saranno nell'intervallo 0 a? − 1, per qualche generatore ?, appartenente al set?. E d'altronde l'importante proprietà interessante che otteniamo qui è che dal mio set? o di gruppo? ha ordine di primo ordine, ogni elemento in questo set?, tranne l'elemento identità , sarà un generatore per il sottogruppo che ho scelto. Perché lo chiamosottogruppo? Perché gli elementi nel set? è un sottoinsieme degli elementi in Zaia?. Ma l'operazione in questo set?, ovvero la moltiplicazione modulo?, è la stessa dell'operazione nel gruppo più grande ovvero Zaia?. Per questo lo chiamo come sottogruppo. Così, dato che l'ordine di questo sottogruppo è prime, ogni elemento di questo sottogruppo sarà un generatore, tranne l'elemento di identità. Inoltre, per il sottogruppo che ho scelto qui, abbiamo algoritmi efficienti per picking elementi casuali oltre che per l'espettazione di gruppo. Quindi se si richiamano i passi del protocollo di scambio Diffie – Hellman, il loro destinatario e il ricevitore devono scegliere elementi casuali dal gruppo sottostante su cui sono che eseguono le operazioni. Per questo dobbiamo avere un algoritmo efficiente, algoritmi in politempo, per scegliere elementi casuali dal gruppo. E si scopre che se ho impostato il mio gruppo per essere il set di tutti? ?hresidui modulo?, poi ho un algoritmo efficiente per scegliere elementi casuali da questo gruppo e per l'esplazione di gruppo. E si scopre che DLog, CDH, DDH, tutti questi problemi sono ritenuti molto, molto duri per valori sufficientemente grandi? e ?, se scelgo il mio sottogruppo? essere il set di tutti? ?hresidui modulo?. (Riferimento Slide Time: 14.58)Così vediamo un'illustrazione di un sottogruppo ciclico di primo ordine di Z? si scrive. Quindi immaginate? = 11, dove ? = 11 è un numero primo. Così posso esprimere 11 nel modulo 2 × 5 + 1 e Z11praticamente consiste in degli elementi da 1 a 10. Quindi se prendo la mia? ad essere 5, allora? e? sono correlati come 2 volte 5 + 1. Quindi posso prendere la mia? ad essere 2 e quello che posso fare è, posso impostare il mio set? per essere tutta la piazza perfetta modulo 11. Ovvero I prendere tutti gli elementi h dal set Z11elettricoelevarlo alla potenza 2 e fare modulo 11. E l'output risultante è la mia collezione?. Quindi quello che ho fatto in questo tavolo, è che ho preso tutti gli elementi dal set Z11Z11 e le piazze resultanti e se prendo le piazze resultanti I ottengo il mio set?. Ovvero il mio set? è costituito dagli elementi 1,3, 4, 5, 9 e potete vedere nella tabella , che sotto le piazze, gli elementi 1,3, 4, 5, 9 sono ripetuti due volte.Così 12 mi dà 1, e così fa 102. 22mi dà 4, così fa 92. 32mi dà 9 e 82dà me 9 e così via. Questo perché qualsiasi quadrato perfetto, ovvero un elemento nel set? avrà 2 radici quadrate, perché è un residuo quadrato. Quindi avrà 2 radice quadrata modulo?. E se una delle radici quadrate è? allora l'altra radice quadrata sarà −?. E −? qui non c'è niente ma? −?.Quindi per esempio se prendo l'elemento 9, che è un elemento di?, poi ha 2 radici quadrate perché è il risultato di 32, quindi è per questo che il 3 è una delle radici quadrate. E analogamente il 9 è il risultato di 82modulo 11 ed è per questo che il 8 è anche una delle radici quadrate del 9. Ed è facile da vedere che il sottoinsieme 1, 3, 4, 5, 9 insieme alla moltiplicazione operazione modulo 11 costituisce un gruppo di ordine 5.Si può verificare che nello stesso modo, per lo stesso esempio dove? = 11, posso prendere la mia? a essere 2 e di conseguenza? sarà di 5. E ora se mi focalizzo sui quinto residui modulo 11, ovvero la raccolta di tutto il modulo h5modulo 11, dove h appartiene a Z11Già, poi ottengo il sottoinsieme 1, 10 e questo sottoinsieme 1,10, possiamo vedere che costituisce effettivamente un gruppo ciclico di ordine 2. Perché ha 2 elementi e ha l'elemento di identità e 10 è il generatore. Ecco quindi un'illustrazione qui. Ma non ho dimostrato i risultati generici. E cioè se prendo? e? per essere sul modulo ? =? ×? + 1, poi il set di tutti? ?hresidui ti dà un gruppo ciclico. Non sto dimostrando che, è possibile vedere uno qualsiasi dei riferimenti standard per la teoria dei numeri per la prova di quel fatto.(Fare Slide Time: 18.11)Così ora la domanda è, abbiamo visto che possiamo formare un sottogruppo ciclico di primo ordine di Z?, ovveroe DLog, CDH, problemi di DDH sono ritenuti molto difficili in quei sottogruppi ciclici. Le domande si scopre che quale dovrebbe essere la grandezza del risultato? e? per garantire che effettivamente i problemi DLog, CDH e DDH siano difficili nei sottogruppi che ne derivano. Quindi il problema che vogliamo affrontare qui è dato? e? che sono primes, dove ? è della forma?? + 1. E abbiamo trovato una serie di residui? ?h, che conosciamo è un gruppo ciclico , che ha un generatore? e dire il numero di bit che dobbiamo rappresentare? è l e il numero di bit che dobbiamo rappresentare? è?. Ora i migliori algoritmi conosciuti per risolvere il problema di log discreto nel sottogruppo che abbiamo formato qui, scende sotto le 2 categorie.Abbiamo l'algoritmo di Classe I che conosciamo per risolvere il problema del log discreto. Il loro tempo di esecuzione è di ordine √?. E ora da allora? è di magnitudo 2?, questo significa √? sarà del ?magnitudo 22. Quindi anche se questo è tempo esponenziale nel parametro di sicurezza sottostante, dobbiamo decidere con molta magistratura il valore di?, quando stiamo instanziando questo sottogruppo per instanziando una primitiva crittografica la cui sicurezza si basa sull'assunzione di DLog.Si scopre che se si imposta? = 256, ovvero se selezioniamo? che è un 256 bit prime e di conseguenza impostare un primo? dove? e? sono correlati dal rapporto che? è?? + 1, poi solo impostando? = 256, realizziamo un livello di sicurezza paragonabile a AES-128. Quindi ricordati quando abbiamo visto l'istanziazione pratica di cifratura di blocco, come AES, DES, dove noi puntiamo alla sicurezza pratica e per sicurezza pratica di AES-128, intendo dire che il miglior attacco possibile che un avversario possa lanciare per recuperare una chiave AES, dove l'avversario ha diverse (?,?) coppie, dove? è l'input AES e? è il corrispondente output AES, sotto una chiave sconosciuta, allora la complessità del miglior attacco conosciuto dovrebbe essere di ordine 2128. Quindi si gira che se instanziamo qualsiasi primitivo crittografico basato sulla durezza di DLog problema selezionando un sottogruppo ciclico di Zanzare? per impostazione? = 256, poi il miglior algoritmo conosciuto per 256risolvere il problema DLog da questa classe di algoritmo richiederà tempo all'incirca all'ordine 2 2, che sarà di ordine 2128. Il che significa che otteniamo lo stesso livello di sicurezza, visto che il tuo AES-128 avrebbe fornito .considerando che gli algoritmi di Classe 2 per risolvere il problema DLog in questo sottogruppo ciclico, il suo tempo di esecuzione è di ordine 2 all'ordine di potenza logaritmico nel numero di bit che noi dobbiamo rappresentare?. Così a partire da 2016, questo algoritmo di classe 2 può essere utilizzato per risolvere istanze di Dlog problema e per qualsiasi istanziazione del sottogruppo ciclico dove l è 768. Ed è suggerito che per avere una nozione significativa di sicurezza dovremmo operare impostando l to be 2048.Significa che se riassumiamo, per affrontare gli algoritmi di classe 1 e gli algoritmi di classe 2 che noi abbiamo per risolvere i problemi DLog in questo sottogruppo ciclico, per garantire che abbiamo ragionevole quantità di sicurezza o il tempo di esecuzione dell'avversario per risolvere il problema del log discreto è di ordine sufficientemente grande, dobbiamo eseguire calcoli modulo 2048 bit numero primo. Che significa per esempio se usiamo il protocollo di scambio Diffie – Hellman Key e se noi instanziamo i passi del protocollo di scambio Diffie – Hellman Key impostando il mio set? essere set di tutti? ?hresidui modulo?, poi devo garantire che il mio? dovrebbe essere un numero primo di 2048 bit grande. Questo significa che sia il mittente che il destinatario devono eseguire elaborazioni modulo questo grande numero primo, che effettivamente riduce il tempo di esecuzione sia del mittente che del destinatario .Così anche se ora abbiamo un sottogruppo ciclico candidato che ora possiamo utilizzare per instanziare qualsiasi primitivo crittografico, la cui sicurezza è basata sulla durezza delle ipotesi DLog, CDH e DDH , si scopre che anche il tempo di esecuzione del mittente, del destinatario o di tutte le parti coinvolte riduce. Perché stiamo per eseguire operazioni modulo un numero primo molto grande.Così una domanda interessante sarà, possiamo avere altri tipi di gruppi ciclici candidati, dove non dobbiamo eseguire operazioni modulo un numero primo così enorme, ma ancora il problema CDH , il problema del DDH e i problemi DLog sono difficili da risolvere in quei gruppi alternativi. Snd nella lezione successiva, vedremo uno di tali candidati. Così questo mi porta alla fine di questa lezione. In questa lezione abbiamo introdotto un gruppo ciclico candidato, ovvero il sottogruppo ciclico di Zaia? rispetto all'operazione di moltiplicazione modulo?, e crediamo che il problema CDH , il problema DLog e il problema DDH siano effettivamente difficili da risolvere in questo gruppo. Tuttavia per ottenere un livello pratico di sicurezza dobbiamo impostare il valore del modulistica? essere un numero molto grande, per garantire che il mittente e il destinatario ottenino una ragionevole quantità di sicurezza, che in realtà finisce per rendere lento anche il tempo di esecuzione del mittente e del destinatario. Grazie tu.