RSA
Sistemi di crittografia
Prof.ssa Lilli Fragneto
Prof.ssa Maria Elena Zecchinato
Boniolo Luca
Breveglieri Francesca
Caneve Piero
Cantisani Giorgia
Fessler Stefano
Ghiro Lorenzo
Mautone Luca
Remondini Gianluca
Silvestri Mattia
Crittografia
Κρυπτός + γραϕία: (kryptòs + grafìa): scrittura segreta
La necessità di comunicare in modo sicuro è antichissima
I primi sistemi crittografici risalgono all’antica Grecia e ai
Romani
Evoluzione di questi sistemi  fine ‘800 prima grande
rivoluzione: non è più segreto l’algoritmo ma sono nascoste le
sue chiavi di cifratura e decifratura.
Sistema simmetrico
Utilizza la stessa chiave per cifrare
e decifrare un messaggio
1918: viene elaborato un sistema inattaccabile, caduto
in velocemente in disuso, poiché le chiavi utilizzate
erano lunghe come il messaggio e potevano essere
utilizzate un’unica volta.
Sistema asimmetrico
Le chiavi sono dipendenti tra
loro, ma non è possibile
risalire dall’una all’altra.
Ideato nel 1976
Utilizza due chiavi distinte: una per la
cifratura e l’altra per la decifratura.
RSA (1978)
Rivest – Shamir - Adleman
Numeri primi  aritmetica modulare
PROTOCOLLO
Aritmetica modulare
Aritmetica utilizzata nel sistema crittografico RSA
Si ha un n  si lavora nell’insieme
0123456789
0123401234
Operazioni con l’aritmetica modulare
n=5
n=6
∙
0
1
2
3
4
∙
0
1
2
3
4
5
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
2
3
4
5
2
0
2
4
0
2
4
3
0
3
0
3
0
3
1
0
1
2
3
4
2
0
2
4
1
3
3
0
3
1
4
2
4
0
4
2
0
4
2
4
0
4
3
2
1
5
0
5
4
3
2
1
Sistema
1) Generazione delle chiavi
p e q  numeri primi (
300 cifre decimali)
n = p ∙ q  n è pubblico, ma non si conoscono q e p che l’hanno generata
 fattorizzazione difficile
Cardinalità di

Così sono state generate:
 Chiave pubblica (n,e)
 Chiave segreta (n,d)
2) Criptazione
“Formattare” il testo
Dividere m in:
Due interlocutori scelgono la
medesima n che è pubblica e
fornita dalla Certification
Authority
 Deve avere lo stesso numero di
cifre di n e deve essere minore di n
Esempio:n=271
237 54 263
237 054 263
3) Decriptazione
Teorema di Eulero
Attacchi
1. Attacchi fisici
2. Attacchi al sistema  cercano di risolvere il problema della
fattorizzazione di n
• Forza bruta (intelligenza 0)
• Forza bruta (intelligenza parziale)
• Curve ellittiche
• Metodi probabilistici
3. Attacchi alla chiave “Aggirano il problema della fattorizzazione,
individuando le debolezze del sistema”
Common Modulus Attack
Dati: