Modulo n
φ(n) (p − 1)(q − 1)
Chiave pubblica (e, n)
Chiave privata d e · d mod φ(n) = 1

Le chiavi

    Come si trova d: l'algoritmo di Euclide esteso

    Ogni riga divide le due righe sopra di essa. Nella riga con resto 1, l'ultima colonna è d (aggiungi φ(n) se è negativo).

    QuozienteRestoCoefficiente di e

    Il messaggio

    Carattere Codice m Risultato

    Inviato in rete

    BitQuadratoMoltiplica per m

    Violare la chiave

    Operazione

    Maggiori informazioni su RSA

    Demo della cifratura RSA

    RSA permette a chiunque di chiudere un messaggio con la tua chiave pubblica, mentre solo tu puoi aprirlo con la tua chiave privata. Dietro ci sono poche righe di aritmetica scolastica: due numeri primi, una moltiplicazione, un resto e un inverso ingegnoso. Costruisci una coppia di chiavi con primi scelti da te, cifra e decifra un messaggio carattere per carattere, firmalo perché chiunque possa verificare che viene da te, e poi mettiti nei panni dell'attaccante e fattorizza n per capire perché le chiavi vere hanno bisogno di centinaia di cifre. Scegli due numeri primi p e q, oppure premi Nuovi numeri primi. L'app costruisce la chiave pubblica (e, n) e la chiave privata d, e mostra come l'algoritmo di Euclide esteso trova d. Scrivi un messaggio: ogni carattere viene cifrato con la chiave pubblica e decifrato con la chiave privata. Clicca su una riga per vedere la potenza calcolata con i quadrati ripetuti. Passa a Firma per firmare invece con la chiave privata, e premi Fattorizza n per vedere quanto in fretta cedono le chiavi piccole.

    Come funziona

    1. Inserisci due numeri primi p e q, oppure scegli una dimensione e premi Nuovi numeri primi; l'app calcola n, φ(n), e e d, e mostra come si trova d.
    2. Scrivi un messaggio e scegli Cifra o Firma. Ogni carattere viene trasformato in un numero ed elevato a una potenza mod n; clicca su una riga per vedere i quadrati ripetuti.
    3. Premi Fattorizza n per lasciare che Eve scomponga n nei suoi due primi e recuperi la chiave privata.

    Come funzionano le chiavi

    Moltiplica due numeri primi: n = p × q. Con p = 61 e q = 53, n = 3233. Il numero φ(n) = (p − 1)(q − 1) = 3120 conta i numeri minori di n che non hanno fattori comuni con esso, e può calcolarlo solo chi conosce p e q. Scegli e = 17, che non ha fattori comuni con 3120, e trova d tale che e × d superi di 1 un multiplo di φ(n): qui d = 2753, perché 17 × 2753 = 46801 = 15 × 3120 + 1. Pubblica (e, n) e tieni d. Un messaggio m diventa c = mᵉ mod n, e il teorema di Euler garantisce che cᵈ mod n restituisca m.

    Perché è difficile da violare

    Tutto ciò che serve a un attaccante è nascosto nei fattori di n. Con n = 3233 non c'è alcuna protezione: provando i divisori dispari si trova 53 dopo circa due dozzine di tentativi. Ma lo sforzo cresce con la radice quadrata di n. Un modulo di 2048 bit ha circa 617 cifre, e nessun metodo noto, su nessun computer oggi esistente, è in grado di fattorizzarlo in un tempo utile. La firma fa funzionare RSA al contrario: s = mᵈ mod n si può produrre solo con la chiave privata, e chiunque può verificare che sᵉ mod n restituisca m.

    Domande frequenti

    Perché nessuno può calcolare d dalla chiave pubblica?

    Per trovare d serve φ(n) = (p − 1)(q − 1), e per ottenere φ(n) servono p e q. Ricavarli da n significa fattorizzarlo, e per numeri con centinaia di cifre non si conosce alcun metodo veloce. La demo ti permette di fattorizzare chiavi giocattolo in una frazione di secondo, il che mostra esattamente perché le chiavi vere sono così grandi.

    Perché il messaggio viene cifrato un carattere alla volta?

    Perché le chiavi giocattolo sono piccole: RSA può cifrare solo un numero minore di n. Con n = 3233 ogni codice di carattere ci sta, ma un'intera frase no. Il vero RSA usa un modulo di 2048 bit o più, completa il messaggio con byte casuali in modo che lo stesso messaggio non venga mai cifrato due volte allo stesso modo e, nella pratica, cifra solo una chiave corta per un cifrario più veloce come AES.

    A che cosa servono i quadrati ripetuti?

    Calcolano potenze enormi come m²⁷⁵³ mod n senza mai scrivere il numero gigantesco. Scrivi l'esponente in binario, poi scorri i suoi bit: eleva al quadrato il risultato parziale per ogni bit e moltiplicalo per m per ogni 1, prendendo ogni volta il resto mod n. Un esponente di 2048 bit richiede solo circa 2048 elevamenti al quadrato.

    Qual è la differenza tra cifrare e firmare?

    Per cifrare si usa la chiave pubblica del destinatario, così che solo la chiave privata del destinatario possa annullare l'operazione. Per firmare si usa la chiave privata del mittente, così che chiunque possa verificare la firma con la chiave pubblica del mittente e sapere che il messaggio viene dal titolare di quella chiave e non è stato modificato.

    Il mio messaggio viene inviato da qualche parte?

    No. Tutto viene calcolato nel tuo browser, e i tuoi numeri primi e il tuo messaggio restano nella memoria locale di questo browser.

    Pronto a provarlo?

    Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.

    Vai all'editor