PROGETTO LAUREE SCIENTIFICHE
ITGS PASCAL-UNIV. PARMA
(è stato usato vario materiale di Alessandro Zaccagnini, Alessandro Languasco)
Docenti: BAROZZI -SIMEONE
CORSO DI CRITTOGRAFIA
Terzo incontro
CRITTOGRAFIA ASIMMETRICA
Uno dei DOGMI indiscussi della crittografia
classica è:
LE CHIAVI DI CIFRATURA E DECIFRATURA
DEVONO ESSERE TENUTE SEGRETE
cioè devono essere note solo alle persone
che comunicano tra loro.
CRITTOGRAFIA ASIMMETRICA
Con l’avvento di Internet, del commercio elettronico,
della home banking etc… si pongono nuovi problemi:



Com’è possibile che due persone che non si conoscono
e non si fidano una dell’altra si mettano d’accordo
sulla chiave di un sistema simmetrico utilizzando
Internet?
Com’è possibile dialogare in modo sicuro su Internet?
Com’è possibile certificare l’identità?
PROTOCOLLO DEL DOPPIO LUCCHETTO
Diffie ed Hellman 1975
A mette il suo messaggio
per B in una scatola che
chiude con un lucchetto e
invia a B.
B mette il suo lucchetto
alla scatola e la
rispedisce ad A.
A toglie il suo lucchetto e
rispedisce la scatola a B.
B toglie il suo lucchetto e
legge il messaggio.
PROTOCOLLO DEL DOPPIO LUCCHETTO
Si noti che:
 la scatola non viaggia mai senza
lucchetto
 né A né B ha dovuto inviare all’altro la
chiave del proprio lucchetto.
COME REALIZZARE IL PROTOCOLLO DEL
DOPPIO LUCCHETTO?
PRIMA IDEA:



Dividere il messaggio in blocchi di lunghezza fissata (k) e trasformarli in un numero intero, usando
per esempio il codice ASCII
Prendere un numero primo p>nk, ove n è il numero dei caratteri distinti del nostro alfabeto (26
lettere + 10 cifre numeriche + spazio + punteggiatura….), se usiamo il codice ASCII n=256
A prende ogni singolo blocco MZp, sceglie un altro elemento aZp-{0} (il suo lucchetto) e calcola
M1=a*M (mod p)

B sceglie un elemento bZp-{0} (il suo lucchetto), calcola M2=b*M1 (mod p) e trasmette M2 ad A

A toglie il suo lucchetto moltiplicando M2 per a-1, ovvero calcola M3=a-1*M2 (mod p)

B toglie il suo lucchetto moltiplicando M3 per b-1 e riottiene M
QUESTO METODO NON E’ SICURO INFATTI SE UN INTRUSO RIESCE A LEGGERE I TRE MESSAGGI M 1,
M2, M3 OTTIENE FACILMENTE M=(M1*M3)*M2-1 (mod p).
Infatti: (M1*M3)*M2-1=(a*M*a-1*M2) *M2-1=M*M2*M2-1=M
COME REALIZZARE IL PROTOCOLLO DEL
DOPPIO LUCCHETTO?
UN PROTOCOLLO FUNZIONANTE (MASSEY-OMURA):



Tutti gli utenti scelgono di comune accordo un numero primo grande p (CHIAVE
PUBBLICA).
Ciascun utente sceglie due interi d,eZp-1 con la proprietà che d*e=1 (mod p-1).
Chiameremo d(A), e(A) i numeri d ed e scelti da A e d(B), e(B) i numeri d ed e scelti da
B.
A prende il messaggio (o una sua parte) MZp, e calcola M1=Md(A) (mod p) (applica il
suo lucchetto)

B calcola M2=M1d(B) (mod p) e trasmette M2 ad A (applica il suo lucchetto)

A toglie il suo lucchetto calcolando M3=M2e(A) (mod p)

B toglie il suo lucchetto calcolando M=M4=M3e(B) (mod p)
PUO’ SEMBRARE MIRACOLOSO CHE L’OPERAZIONE DI RIMOZIONE DEL LUCCHETTO
COINCIDA CON QUELLA DI CHIUSURA DEL LUCCHETTO STESSO, CIOE’ SIA IL CALCOLO
DI UNA POTENZA: I MATEMATICI CHIAMANO QUESTI MIRACOLI COL NOME DI TEOREMI
FERMAT: IL PRINCIPE DEI DILETTANTI
Pierre de Fermat nacque a Beaumont-de-Lomagne, vicino a Tolosa.
Figlio di un mercante, studiò legge e divenne avvocato al Parlamento di
Tolosa, dove si trasferì nel 1631. Nello stesso anno sposò la cugina
materna Luisa de Long, dalla quale ebbe cinque figli.
Lavorava duramente e scrupolosamente, ma nonostante ciò nel tempo
libero si occupava di letteratura e, soprattutto, di matematica. Per
questo è chiamato "il principe dei dilettanti", poiché, pur dedicandosi
alla matematica solo nel tempo libero, la sua influenza sulla storia della
disciplina fu notevolissima.
Pubblicava le sue idee molto raramente e per lo più sappiamo delle sue
scoperte grazie alla corrispondenza scambiata con altri matematici,
come Mersenne o Pascal. La conoscenza di altre sue intuizioni, ci viene
da suoi commenti in margine a libri che stava leggendo. Per questo
motivo spesso il suo lavoro fu imputato ad altri. Morì all'età di 63 anni a
Castres.
Da Wikipedia
IL PICCOLO TEOREMA DI FERMAT
PROBLEMA: trovare l’inverso di un numero in Zp.
TEOREMA: Sia p un numero primo qualsiasi ed a un intero, non
divisibile per p, allora ap-1=1 (mod p)
CONSEGUENZA: ap-2 è l’inverso di a.
DIMOSTRAZIONE: Dimostreremo una proposizione equivalente,
ovvero che
QUALUNQUE SIA L’INTERO a, SE p E’ UN NUMERO PRIMO,
ALLORA ap=a (mod p) OVVERO
p DIVIDE ap-a
IL PICCOLO TEOREMA DI FERMAT
Dimostrazione
nel caso di p=3 e a=4.
Consideriamo tutte le
possibili collane che si
possono costruire con 3
(p) perline di 4 (a) colori
diversi. Queste sono 43,
ovvero nel caso
generico ap.
A sinistra abbiamo le 4 collane monocrome con 3 perline, a destra le 43-4 collane
policrome, suddivise in classi di collane equivalenti per rotazione. Ogni classe
contiene esattamente 3 collane e quindi 3 deve dividete 43-4.
Cioè p deve dividere ap-a.
OSSEY-OMURA FUNZIONA
Dimostriamo ora che effettivamente M4=M.
M4=Md(A)e(A)d(B)e(B) (mod p)=M(1+k(p-1))(1+h(p-1)) (mod p) =
M(1+t(p-1)) (mod p)=M*(Mp-1)t (mod p)=M*1 (mod p)=
M (mod p)
IL SISTEMA RSA (Rivest-Shamir-Adleman)
Un protocollo che si utilizza molto in internet
attualmente è il protocollo RSA che è stato ideato nel
1978 da Rivest, Shamir, Adleman.
IDEA: diversa complessità computazionale
PRIMALITA’
FATTORIZZAZIONE
PRIMALITA’
VS
FATTORIZZAZIONE
Il numero RSA-129 è un numero di 129 cifre decimali,
fattorizzato nel 1994, creato secondo i criteri proposti da RivestShamir-Adleman, richiede con un computer domestico parecchio
tempo per essere fattorizzato (giorni), mentre in pochi secondi un
qualunque PC riesce a dire che non è primo.
RSA129=1143816257578888676692357799761466120102
18296721242362562561842935706935245733897830597
123563958705058989075147599290026879543541
IL SISTEMA RSA





Ogni utente sceglie in modo casuale due numeri primi p e q
distinti ed estremamente grandi (diciamo di circa 300 cifre
decimali ciascuno) e pone n=pq
Calcola (n)=(p-1)(q-1)
Sceglie in modo casuale un intero e tale che 1<e<(n) e
MCD(e,(n))=1
Calcola d=e-1 (mod (n))
Ogni utente quindi ha una chiave pubblica: i due valori n ed e;
una chiave privata: d
IL SISTEMA RSA
MESSAGGIO=M
ANNA


BRUNO
Anna calcola M1=Me(B) (mod n(B))
Bruno riceve M1 e calcola M=M1d(B), così Bruno può
leggere il messaggio mandatogli da Anna.