RSA e questioni relative
Rossella Ascione
Il crittosistema RSA
•Introduzione al crittosistema RSA
•Firme digitali e RSA
•Attacchi a RSA
Il crittosistema RSA
1978 :Ron Rivest,
Adi Shamir
Leonard Adleman
Crittosistema
a
Chiave Pubblica
realizza un’intuizione
rivoluzionaria di Diffie,
Hellmann e Merkle che
nel 1976 tentarono di
inventare una tecnica
di cifratura che non
fosse a chiave
simmetrica
crittosistema a chiave pubblica
ciascun utente sceglie una funzione crittografica
Def: Una biezione f:AB viene detta
che dipende da alcuni parametri, ma rende noti
funzione unidirezionale se il calcolo di aєA
solo quelli che permettono di codificare i
è realizzabile con una complessità polinomiale
messaggi a lui diretti, mantenendo segreti
quelli
-1
per tutti gli a єA , mentre il calcolo di f (b) non
necessari alla decodifica
lo è per quasi tutti i bєB
l’inversione della funzione di cifratura fk e
computazionalmente difficile per tutti, mittente
compreso, ma non per il destinatario che possiede
l’informazione necessaria (chiave di decifratura) per il
calcolo efficiente di fk−1 .
analogia della ”scatola a due lucchetti”
Supponiamo che A desideri mandare un messaggio
segreto a B. Allora:
1) A chiude il messaggio in una scatola con un lucchetto LA,
di cui solo A ha la chiave, e invia la scatola a B.
2) Ricevuta la scatola, l’utente B aggiunge un lucchetto LB,
di cui è il solo a possedere la chiave, e rinvia il tutto ad
A.
3) Ricevuta la scatola chiusa con i due lucchetti LA e LB,
l’utente A libera la scatola dal proprio lucchetto LA e la
rinvia a B.
4) Ricevuta la scatola, l’utente B libera la scatola dal
proprio lucchetto LB e legge il messaggio di A.
Dalla precedente analogia della ”scatola
con lucchetti”…
Diffie, Hellmann e Merkle osservarono ”semplicemente”
che un lucchetto si può chiudere senza usare alcuna
chiave(!):
 1) l’utente A progetta e costruisce un lucchetto e una
chiave unica per aprirlo
 2) A rende disponibili al pubblico copie del lucchetto, ma
conserva la chiave;
 3) un qualunque altro utente B che desidera potrà
procurarsi una copia di tale lucchetto in un punto di
distribuzione;
 4) se B desidera inviare un messaggio ad A, allora
chiude tale messaggio in una scatola chiusa con il
lucchetto di A e la spedisce ad A.
Idea base di RSA
 A sceglie due primi p, q distinti e sufficientemente
grandi
 Calcola n= pq
 Calcola φ(n)=(p-1)(q-1)=n-p-q+1
 Sceglie un numero casuale e di N coprimo con φ(n)
 Calcola d di Z*n l’inverso di e modulo φ(n)
 Rende nota la coppia (n, e) come sua chiave
pubblica
 Tiene segreti la coppia (φ(n), d) come chiave privata
Se B volesse mandare un messaggio ad A…
Se un utente B desidera
Ricevuto il messaggio
mandare un messaggio
l’utente A utilizza la
segreto ad A deve calcolare
funzione di decifratura solo
La
sicurezza
del
l’equivalente numerico x di
a sistema
lui nota:
tale messaggio modulo
n e
1
d
dipende
f A (x)  y mod n
utilizzare
la
funzione
dalla
n
crittografica
di difficoltà
A che puòdi scomporre
Cioè eleva il messaggio
esere calcolatanei
da suoi
tutti gli
fattoriricevuto
primi a d modulo n..
utenti del sistema:
Infatti poichè
f A ( x)  x mod n
e
Cioè eleva x ad e modulo
n e lo invia ad A
ed  1(mod (n ))
Si ottiene
x 
e d
 x ed  x (mod n )
È possibile svelare φ(n)?
Prop: Sia n=pq con p
Dim: Se n è pari allora p=2 e
e q primi. Allora
q=n/2 e φ(n)=n/2-1
1. Noti p, q e n,
Se n è dispari
il calcolo di
Per
mantenere un corretto
φ(n)=(p-1)(q-1)=n+1-(p+q)
φ(n) ha
complessità
funzionamento
del crittosistema,
computazonale
ogni
utente deve tenere
segreto,
P+q=n+1-φ(n)
. Quindi di p e q
O(logn)
conosciamo somma e prodotto
parametri
p, quindi
q e pde qche
ha
sono soluzioni
2. oltre
Noti nai
e φ(n)
il
dell’eq:X2 –(p+q)x+n=0
calcolo
di
p
e
q
scelto, anche φ(n)
ha complessita
Per ricavare p e q abbiamo quindi
bisogno dell’estrazione della
computazionale
radice quadrata intera che ha
O(log3n)
complessita computazionale pari
a O(log3n)
Se conosco n, e e d
La conoscenza di n, e e d consente di fattorizzare
comunque efficientemente n mediante un
determinato algoritmo probabilistico che basato
sulla scelta casuale di un a
Concludendo ogni
utente deve
Si dimostra che
iterando u volte
la scelta casuale
Assolutamente
tenere
di a si ottiene un algoritmo
Segreto di
d fattorizzazione che
termina con successo con probabilità maggiore o
uguale di 1  2  u e complessità computazionale
O(u log 3 n )
Estensione al caso (x,n)>1
Teorema:
Sia nєN prodotto di primi distinti. Se m≡1 modφ(n) allora
am ≡a mod n per ogni a єZ
Si dimostra però Se
che(n,
la probabilità
di
x)≠1
trovare un tale x risulta molto bassa e
che la complessità computazionale
di osservare
In
particolare
si
può
(n,x)
potrebbe
fornire
un fattore non
(n,x)=n
tale attacco è maggiore
di
che
un quello
utente
Bdegli
potrebbe di
banale
di n consentendo
determinare
violare
algoritmi di fattorizzazione
dicompletamente
n i fattori di n il
generando
casualmente un
crittosistema
numero sufficientemente grande
di elementi x e verificando di
volta in volta se (n, x) ≠1
Una versione leggermente diversa di RSA…
( n )
Funzione
di Eulero
(n )
Funzione di
Carmichael
 A sceglie (se ci riesce) due primi p, q
distinti e sufficientemente
Vantaggiograndi)
di tale metodo:
 Calcola n= pq
 Calcola φ(n)=(p-1)(q-1)=n-p-q+1
•Calcola λ(n)=φ(n)/(p-1,q-1)
L’operazione di decifratura
risulta
•Sceglie
un numero casuale e
 Sceglie un numero casuale e di N
di N coprimo con λ(n)
coprimo con φ(n)essere più veloce
•Calcola d di Z*n l’inverso di e
 Calcola d di Z*n
l’inverso
e
che
nel dicaso
standard
modulo λ(n)
modulo φ(n)
 Rende nota la coppia (n, e) come
sua chiave pubblica
 Tiene segreti p, q e d cioè la coppia
(φ(n), d) come chiave privata
Il sistema appena presentato si è rivelato essere adatto a
soddisfare tutti i requisiti minimi di base (riservatezza,
integrità, autenticità, non-ripudiabilità) richiesti ad un
buon sistema crittografico dal punto di vista pratico.
Ciò grazie alla disponibilità di algoritmi ragionevolmente
efficienti, affidabili e rapidi per:
•generare le chiavi, private e non, degli utenti
•per testare i parametri soddisfacenti particolari
proprietà
•per calcolare i valori della funzione crittografica
•per testare il carattere unidirezionale della funzione
crittografica
Firma digitale e RSA
Problema di certificare la nostra identità con
una firma digitale
CRITTOGRAFIA A CHIAVE PUBBLICA
Schema generale di firma digitale
 A, B utenti di un sistema a chiave pubblica
 fA e fB funzioni di cifratura (pubbliche)
 fA-1 e fB-1 funzioni di decifratura (segrete)
A desidera mandare un
messaggio x a B
•A manda fB(x)
•Per certificare la propria identità
invia la quantità fB(fA-1(sA)) con
fA-1(sA) firma digitale di A e sA un
nome convenzionale di A in cui si
include un numero progressivo ,
tempo in cui è stato spedito il
messaggio, numero IP della
machina speditrice
B decifra il messaggio x…
•Utilizzando fB-1 e ottiene x
•Per controllare che il mittente sia
A applica alla funzione fB(fA-1(sA)) la
funzione a lui nota fAfB-1 e ottiene sA
Il sistema funziona bene
poiché solo A può aver
firmato il messaggio
poiché solo A conosce
fA-1
Rischi di tale sistema
1. Potrebbe esistere un utente intruso C che
renda pubblica una chiave attribuendola ad A,
divenendo automaticamente capace di
spacciarsi per A
Introduzione di un
ENTE CERTIFICATORE
Rischi di tale sistema
1. Potrebbe capitare che un intruso riesca
ad identificare fA-1(sA) utilizzando un
numero opportuno di messaggi
intercettati
Far dipendere la
Firma digitale
Dal messaggio stesso
La firma
digitale diviene
fA-1(h(M))
h(M) IMPRONTA DI M
è una sequenza di bit di lunghezza fissata detta
IMPRONTA DI M che viene ottenuta da M
mediante una opportuna funzione di hash h
Sono
funzioniviene
che hanno
Tale funzione
messalaa
caratteristica
nonutenti
consentire
di
disposizione di
degli
dall’ente
risalire
a M conoscendo
solo
certificatore,
ne viene utilizzata
h(M),e
di avere
unaglibuona
una sola
per tutti
utenti del
probabilità
di non generare
crittosistema
collisioni
Come funziona…
Per accertarsi dell’assenza di manomissioni
B dovrà
Applicare a fA-1(h(M)) la fA e otterrà h(M)
Ricalcolare l’impronta di M h(M) per
mezzo della funzione di hash
Firma digitale: certificazione dell’identità con RSA
Problema: gli spazi dei messaggi cifrati sono a priori
diversi poiché A lavora su ZnA e B lavora su ZnB in
generale diversi.
 A sceglie una firma digitale sAє ZnA che rende pubblica
 Per convincere B della propria identità , in calce al
proprio messaggio A invia una forma crittografica della
firma, e precisamente
mA=fB(fA-1(sA)) se nA<nB;
mA=fA-1(fB(sA)) se nA>nB
 Per assicurarsi dell’identità di A, B calcola
fA(fB-1 (mA)) se nA<nB;
fB-1 (fA(mA)) se nA>nB
Attacchi a RSA
 Chosen-ciphertext:
Un intruso C vuole determinare il testo in chiaro M di una
codifica C inviata ad A
C Sceglie un intero casuale R e chiede ad A la decodifica
del messaggio C1≡ReAC mod nA
In questo modo C ottiene ReAdACdA mod nA alla quale
applicando R-1 si ottiene M
mai applicare la propria funzione di
decifratura o la propria firma digitale ad
un documento casuale
Attacchi elementari:
 scelta dei possibili
messaggi in chiaro
troppo limitati
•Scelta del modulo
di n fissata per tutti
gli utenti
 Si provano a codificare tutti i
messaggi in chiaro fino a che
non viene determinato quello
la cui codifica è uguale al
messaggio intercettato
Poiché (e1, e2)=1 con
1. Se
sa che si
B calcola
ha il suo stesso
l’algoritmo
di Aeuclide
n, allora
conosce
p, q, φ(n) e
r,sєZ tali che
re1+se
2=1 e poi
calcolare d di B
Cr1 Cs2≡Mre1+se2=M mod n
2. Un intruso può ricavare da due codifiche C1 e C2
ricavate
dueutilizzata
chiavi pubbliche
) e (n,
ogni
n nonmediante
deve essere
da piu’ di(n,une1utente
e2) con (e1,e2)=1, il messaggio M stesso
Punti fissi:
I messaggi da trasmettere non devono essere dei punti
fissi della funzione di cifratura, cioè non deve accadere
f(M)≡M mod n
Messaggio cifrato
=
Messaggio in chiaro
Per non avere molti punti fissi si dimostra che e deve
essere scelto in modo tale che (e-1, p-1, q-1) sia
piccolo
Cycling attack:
Funzione di cifratura con
periodo troppo corto
Il più piccolo k tale che:
M  M mod n
ek
Sia “piccolo”
Teorema: Sia (n,e) una chiave pubblica RSA e MєZ*n. Sia r
il più grande divisore primo di p-1 e l sia il più grande
divisore primo di r-1. Allora
P(k≥l) ≥(1-l/r)(1-1/l)
Per diminuire la possibilità di cycling attack
bisogna scegliere p e q in modo tale che sia r
che l siano grandi
Attacco causato da una chiave privata troppo piccola:
d
n
1
4
Teorema(Wiener): Sia p<q<2p, n=pq,
6 . Dati
n ed e tali che ed≡1modφ(n),esiste un algoritmo
deterministico polinomiale in logn che consente di
determinare d
Due metodi per non
intercorrere in questo
tipo di attacco
1. Scegliere e>n3/2 con un
conseguente aumento
del tempo di cifratura
2. Usare il teorema
cinese del resto per
ottenere una
decifratura “veloce”
senza dover scegliere
d piccolo
Attacco a partire da una conoscenza parziale della
chiave privata(e “piccolo”)
Teorema (Boneh, Durfee e Frankel):
Sia n≡3mod4, n1/2/2<q<p<2n1/2 e sia d una chiave
privata di RSA. Siano note le [log2n]/4 cifre meno
significative di d. Sia inoltre e<2[log2n]/4-3. Allora esiste un
algoritmo che determina completamente d con
complessita polinomiale in logn
I seguenti risultati affermano che è possibile
ricostruire completamente d nel caso in cui e
sia piccolo, a partire da una conoscenza di
una frazione dei bit costituenti l’espansione
binaria di d.