Please enable JavaScript.
Coggle requires JavaScript to display documents.
Lezione 21: algoritmo RSA - Coggle Diagram
Lezione 21: algoritmo RSA
Usa una cifratura a blocchi in cui
testo in chiaro e cifrato sono interi
compresi tra 0 e n-1 per un dato valore di n
La cifratura è ottenuta mediante
esponenziazione
e la sicurezza dell'intero sistema sta nella difficoltà di effettuare l'operazione di fattorizzazione di grandi numeri
Ogni utente genera una coppia di chiavi casuali
Vengono scelti due numeri primi casuali
p
e
q
(privati)
Si calcola n=p*q (pubblico)
Si calcola Ø(n)=(p-1)*(q-1)
Si sceglie
e
(pubblico) tale che MCD(Ø(n),e)=1 ovvero che Ø(n) ed e sono primi tra loro con 1<e<Ø(n)
Di determina
d
dall'equazione e*d=1modØ(n)
6.Chiave pubblica (PU) costituita da {e,n}
Chiave privata (PR) costituita da {d,n}
Una volta generata il mittente le seguenti operazioni adoperando le chiavi del destinatario per cifratura e decifratura
Il mittente ottiene la chiave pubblica del destinatario
PU={e,n}
Calcola C = M^e mod n
Il destinatario utilizza la propria chiave privata PR={d,n} per decifrare il testo cifrato C
Il destinatario esegue C^d mod n = M^ed mod n = M
Questo è vero se e sole se e*d=1modØn
Generazione della chiave
Essendo p*q=n un valore pubblico bisogna scegliere p e q in un insieme di numeri primi grande, altrimenti sarà facile ricavare le chiavi con un attacco a forza bruta
Viene utilizzato l'algoritmo Miller-Rabin per determinare se un certo numero è primo
Basato su alcuni test che, eseguiti più volte in condizioni operative differenti, danno una ragionevole convinzione che il numero selezionato sia effettivamente primo
L'algoritmo di Euclide permette di calcolare il MCD di due interi (Ø(n),e) e, se MCD=1, determinare l'inverso di uno degli interi modulo dell'altro, ovvero e^-1 mod Ø(n) (che è = d)