Perché i numeri primi sono importanti nella crittografia?

Question

Una cosa che mi colpisce sempre come non crittografo: perché è così importante usare i numeri Prime? Cosa li rende così speciali nella crittografia?

Qualcuno ha una breve spiegazione semplice ? (Sono consapevole che ci sono molti primer e che la crittografia applicata è la Bibbia, ma come detto: non sto cercando di implementare il mio algoritmo crittografico e le cose che ho trovato mi hanno fatto esplodere il cervello - non ci sono 10 pagine di formule matematiche per favore :))

Grazie per tutte le risposte. Ho accettato quello che mi ha reso più chiaro il concetto reale.

Answer 1

Spiegazione più basilare e generale: la crittografia riguarda tutto teoria dei numeri e tutti i numeri interi ( tranne 0 e 1) sono costituiti da numeri primi, quindi ti occupi molto dei numeri primi nella teoria dei numeri.

Più specificamente, alcuni importanti algoritmi crittografici come RSA dipendono in modo critico dal fatto che scomposizione in fattori primi di grandi numeri richiede molto tempo. Fondamentalmente hai una " chiave pubblica " costituito da un prodotto di due numeri primi grandi utilizzati per crittografare un messaggio e una "chiave segreta" costituito da quei due numeri primi utilizzati per decrittografare il messaggio. Puoi rendere pubblica la chiave pubblica e tutti possono usarla per crittografare i messaggi, ma solo tu conosci i fattori primi e puoi decrittografarli. Tutti gli altri dovrebbero considerare il numero, che richiede troppo tempo per essere pratico, dato l'attuale stato dell'arte della teoria dei numeri.

Answer 2

Semplice? Yup.

Se moltiplichi due numeri primi grandi, ottieni un numero enorme non primo con solo due (primi) fattori primi.

La fattorizzazione di quel numero è un'operazione non banale e quel fatto è la fonte di molti algoritmi crittografici. Vedi funzioni a senso unico per ulteriori informazioni.

Addendum: Solo qualche spiegazione in più. Il prodotto dei due numeri primi può essere usato come chiave pubblica, mentre i numeri primi stessi come chiave privata. Qualsiasi operazione eseguita sui dati che può essere annullata solo conoscendo uno dei due fattori sarà non banale da decifrare.

Answer 3

Ecco un esempio molto semplice e comune.

algoritmo di crittografia RSA che viene comunemente utilizzato nei siti Web di commercio sicuro, è basato sul fatto che è facile prendere due numeri primi (molto grandi) e moltiplicarli, mentre è estremamente difficile fare il contrario - il che significa: prendere un numero molto grande, dato che ha solo due fattori primi, e trovare loro.

Answer 4

Non sono tanto i numeri primi stessi che sono importanti, ma gli algoritmi che funzionano con i numeri primi. In particolare, trovare i fattori di un numero (qualsiasi numero).

Come sai, qualsiasi numero ha almeno due fattori. I numeri primi hanno la proprietà unica in quanto hanno esattamente due fattori: 1 e se stessi.

La ragione per cui il factoring è così importante è che i matematici e gli informatici non sanno come fattorizzare un numero senza semplicemente provare ogni possibile combinazione. Cioè, prima prova a dividere per 2, quindi per 3, quindi per 4 e così via. Se provi a fattorizzare un numero primo - specialmente un numero molto grande - dovrai provare (essenzialmente) ogni numero possibile tra 2 e quel numero primo grande. Anche sui computer più veloci, ci vorranno anni (persino secoli) per considerare i tipi di numeri primi utilizzati nella crittografia.

È il fatto che non sappiamo come fattorizzare in modo efficiente un numero elevato che dia forza agli algoritmi crittografici. Se, un giorno, qualcuno riuscisse a capire come farlo, tutti gli algoritmi crittografici attualmente in uso diventeranno obsoleti. Questa rimane un'area di ricerca aperta.

Answer 5

Perché nessuno conosce un algoritmo veloce per fattorizzare un numero intero nei suoi fattori primi. Tuttavia, è molto facile verificare se un insieme di fattori primi si moltiplica per un certo numero intero.

Answer 6

Ci sono alcune buone risorse per accelerare la criptovaluta. Eccone uno:

• http://research.microsoft.com/en-us/ gruppi / crypto / firstcrypto.aspx

Da quella pagina:

  

Nella chiave pubblica più comunemente usata   sistema di crittografia, inventato da Ron   Rivest, Adi Shamir e Len Adleman in   1977, sia il pubblico che il privato   le chiavi sono derivate da una coppia di grandi dimensioni   numeri primi secondo a   matematica relativamente semplice   formula. In teoria, potrebbe essere   possibile derivare la chiave privata   dalla chiave pubblica lavorando il   formula al contrario. Ma solo il   prodotto dei grandi numeri primi è   numeri pubblici e di factoring   la dimensione in numeri primi è così difficile che pari   i supercomputer più potenti in   il mondo non può rompere un normale   chiave pubblica.

Il libro di Bruce Schneier Applied Cryptography è un altro. Consiglio vivamente quel libro; è divertente leggere.

Answer 7

Per essere un po 'più concreti su come RSA utilizza le proprietà dei numeri primi, l'algoritmo RSA dipende in modo critico da Teorema di Eulero , che afferma che per numeri relativamente primi "a" e " N " ;, a ^ e è congruente con 1 modulo N, dove e è il < a href = "http://en.wikipedia.org/wiki/Euler%27s_totient_function" rel = "noreferrer"> Funzione totient di Euler di N.

Da dove vengono i numeri primi? Per calcolare in modo efficiente la funzione completa di Eulero di N, è necessario conoscere la fattorizzazione primaria di N. Nel caso dell'algoritmo RSA, dove N = pq per alcuni numeri primi "p" e " q " ;, quindi e = (p - 1) (q - 1) = N - p - q + 1. Ma senza conoscere p e q, il calcolo di e è molto difficile.

Più astrattamente, molti protocolli crittografici usano varie funzioni della botola , funzioni che sono facili da calcolare ma difficile da invertire. La teoria dei numeri è una ricca fonte di tali funzioni botola (come la moltiplicazione di grandi numeri primi) e i numeri primi sono assolutamente centrali nella teoria dei numeri.

Answer 8

Suggerirei il libro A Mathematical Journey In Code . Il libro ha un bel tocco di terra, il che è sorprendente, dal momento che riguarda la crittografia. Il libro riassume il viaggio di Sarah Flannery dall'apprendimento dei puzzle da bambino alla creazione dell'algoritmo Cayley-Purser (CP) all'età di 16 anni. Fornisce una spiegazione incredibilmente dettagliata di funzioni a senso unico, teoria dei numeri e numeri primi e come si collegano alla crittografia.

Ciò che rende questo libro ancora più specifico per la tua domanda è che Sarah ha cercato di implementare un nuovo algoritmo a chiave pubblica usando quello di Matrix. È stato molto più veloce dell'uso dei numeri primi, ma è stato trovato un foro circolare che poteva sfruttarlo. Si scopre che il suo algoritmo è stato meglio utilizzato come meccanismo di crittografia privato. Il libro è una grande testimonianza dell'uso dei numeri primi per la crittografia in quanto ha superato la prova del tempo e le sfide di individui molto intelligenti.

Answer 9

Un'altra risorsa per te. Security Now! episodio 30 (~ 30 minuti di podcast, il collegamento è alla trascrizione) parla di problemi di crittografia e spiega perché i numeri primi sono importanti.

Answer 10

Non sono un matematico o un criptico, quindi ecco un'osservazione esterna in termini di profani (niente equazioni fantasiose, scusa).

Questo intero thread è pieno di spiegazioni su COME i numeri primi sono usati nella crittografia, è difficile trovare qualcuno in questo thread che spieghi in modo semplice PERCHÉ i numeri primi sono usati. .. molto probabilmente perché tutti danno questa conoscenza per scontata.

Solo guardare il problema dall'esterno può generare una reazione simile; ma se usano le somme di due numeri primi, perché non creare un elenco di tutte le somme possibili che possono generare due numeri primi?

In questo sito c'è un elenco di 455.042.511 , dove i numeri primi più alti sono 9.987.500.000 ( 10 cifre).

Il primo più grande conosciuto (al febbraio 2015) è 2 alla potenza di 257.885.161 - 1 che è 17.425.170 cifre.

Ciò significa che non ha senso mantenendo un elenco di tutti i numeri primi noti e tanto meno tutte le loro possibili somme. È più facile prendere un numero e verificare se è un numero primo.

Il calcolo dei numeri primi di per sé è un compito monumentale, quindi calcolo inverso due numeri primi che sono stati moltiplicati tra loro sia i crittografi che i matematici direbbero che è abbastanza difficile .. oggi.

Answer 11

Gli algoritmi crittografici si basano generalmente per la loro sicurezza sull'avere un "problema difficile". La maggior parte degli algoritmi moderni sembra utilizzare il factoring di numeri molto grandi come loro problema difficile - se moltiplichi due numeri grandi insieme, calcolare i loro fattori è "difficile". (cioè che richiede tempo). Se quei due numeri sono numeri primi, allora c'è solo una risposta, il che rende ancora più difficile, e garantisce anche che quando trovi la risposta, è quella giusta, non un'altra risposta che dà lo stesso risultato.

Answer 12

Penso che ciò che è importante nella crittografia non siano i numeri primi in sé, ma è la difficoltà del problema di fattorizzazione in primo piano

Supponi di avere un numero intero molto grande che è noto per essere il prodotto di due numeri primi m e n, non è facile trovare cosa sono m e n. Un algoritmo come RSA dipende da questo fatto.

A proposito, c'è un documento pubblicato sull'algoritmo che può " risolvere " questo problema di fattorizzazione primaria in tempi accettabili utilizzando il computer quantistico. Quindi i più recenti algoritmi di crittografia potrebbero non fare affidamento su questa "difficoltà". della scomposizione in fattori primi quando il computer quantistico arriva in città :)

Answer 13

Perché gli algoritmi di fattorizzazione accelerano considerevolmente con ogni fattore trovato. Rendere prime entrambe le chiavi private garantisce che anche il primo fattore trovato sia l'ultimo. Idealmente, anche entrambe le chiavi private avranno quasi lo stesso valore poiché conta solo la forza delle chiavi più deboli.

Answer 14

I numeri primi sono utilizzati principalmente nella crittografia poiché richiede molto tempo per determinare se un determinato numero è un numero primo o no. Per l'hacker se un algoritmo impiega molto tempo a decifrare il codice, diventa inutile per loro