Elementi di crittografia Elementi di Elementi di

(1)

RETI DI CALCOLATORI II

Prof. PIER LUCA MONTESSORO Facoltà di Ingegneria

Università degli Studi di Udine

(2)

Questo insieme di trasparenze (detto nel seguito slide) è protetto dalle leggi sul copyright e dalle disposizioni dei trattati internazionali. Il titolo ed i copyright relativi alle slides (ivi inclusi, ma non limitatamente, ogni immagine, fotografia, animazione, video, audio, musica e testo) sono di proprietà degli autori prof. Pier Luca Montessoro e ing. Davide Pierattoni, Università degli Studi di Udine.

Le slide possono essere riprodotte ed utilizzate liberamente dagli istituti di ricerca, scolastici ed universitari afferenti al Ministero della Pubblica Istruzione e al Ministero dell’Università e Ricerca Scientifica e Tecnologica, per scopi istituzionali, non a fine di lucro. In tal caso non è richiesta alcuna autorizzazione.

Ogni altro utilizzo o riproduzione (ivi incluse, ma non limitatamente, le riproduzioni su supporti magnetici, su reti di calcolatori e stampe) in toto o in parte è vietata, se non esplicitamente autorizzata per iscritto, a priori, da parte degli autori.

L’informazione contenuta in queste slide è ritenuta essere accurata alla data della pubblicazione. Essa è fornita per scopi meramente didattici e non per essere utilizzata in progetti di impianti, prodotti, reti, ecc. In ogni caso essa è soggetta a cambiamenti senza preavviso. L’autore non assume alcuna responsabilità per il contenuto di queste slide (ivi incluse, ma non limitatamente, la correttezza, completezza, applicabilità, aggiornamento dell’informazione).

In ogni caso non può essere dichiarata conformità all’informazione contenuta in queste slide.

In ogni caso questa nota di copyright e il suo richiamo in calce ad ogni slide non

Nota di Copyright

(3)

Elementi di crittografia Elementi di Elementi di

crittografia

(4)

Crittografia Crittografia

Permette di ottenere:

Autenticazione Autenticazione Autenticazione

Segretezza Segretezza Segretezza

Integrità del messaggio Integrit

Integritàà del messaggiodel messaggio

(5)

Definizioni Definizioni

ABCD

testo in chiaro testo in

chiaro

algoritmo di cifratura

#^$&

testo cifratotesto cifrato

(6)

algoritmo di cifratura

algoritmo di

cifratura ^ABCD

chiaro

#^$&

(7)

“Scambia ogni lettera in posizione i con quella in posizione (i³+3) mod m”

Algoritmo segreto Algoritmo segreto

Esempio:

(8)

void crypto (char s[]) void crypto (char s[]) {{

intint i, m = i, m = strlenstrlen (s);(s);

for (i = 0; i < m; i++) for (i = 0; i < m; i++) {{

char t;

char t; intint j;j;

j = (i*i*i + 3) % m;

t = s[i];

s[i] = s[j];

s[j] = t;

}}

return;

Cifratura Cifratura

(9)

void decrypto (char s[]) {

int i, m = strlen (s);

for (i = m-1; i >= 0; i--) {

char t; int j;

j = (i*i*i + 3) % m;

t = s[i];

s[i] = s[j];

s[j] = t;

}

Decifratura Decifratura

(10)

Esempio:

"Cara Alice, credo

"Cara Alice, credo cheche Trudy Trudy cici stiastia spiando"spiando"

"

"arTarT sausAsausA eieeie aioCnodcrdaaioCnodcrda y cc,e y cc,e trlidchiptrlidchip""

(11)

NO: è necessario permettere lo sviluppo del software

necessario

NO: è necessario permettere lo sviluppo del software

necessario

Algoritmo segreto per Internet?

algoritmi pubblici + CHIAVI

algoritmi pubblici

+ CHIAVI

(12)

ABCD

chiaro

algoritmo di cifraturaalgoritmo di cifratura

#^$&

testo cifratotesto cifrato chiave

K_A chiave

K_A

Alice Alice

(13)

algoritmo di decifratura algoritmo di

decifratura ^ABCD

chiaro

%&*#

testo cifratotesto cifrato chiave

K_B chiave

K_B

BobBob

(14)

KH#4

testo

incomprensibiletesto incomprensibile algoritmo di

decifratura algoritmo di

decifratura

%&*#

?

? ?

Trudy Trudy

(15)

Chiavi simmetriche Chiavi simmetriche

Stessa chiave per crittografia e decrittografia

(16)

Come scambiarsi le chiavi?

Problema:

Chiavi simmetriche Chiavi simmetriche

len (chiave) > len (messaggio) chiavi sempre diverse

Massima sicurezza:

(17)

Algoritmi per chiavi simmetriche

Î Schema di sostituzione fissa di ogni lettera con un’altra

Î Schema di sostituzione fissa di ogni lettera con un’altra

Cifrature monoalfabetiche (cifrario di Cesare)

Î Forzatura tramite analisi statistica delle ricorrenze Î Forzatura tramite analisi

statistica delle ricorrenze

(18)

a b c d e f g h i j k l m n o ...

f g e s j y z k r q p i t a v ...

“ciao”

“ciao” “erfv”“erfv”

Esempio: cifrario di Cesare Esempio: cifrario di Cesare

(19)

n cifrari di Cesare usati ciclicamente

n cifrari di Cesare usati ciclicamente

Cifrature polialfabetiche (cifrari di Vigenere)

(20)

k l m n o p q r s t u v w x y ...

e f g h i j k l m n o p q r s ...

y z a b c d e f g h i j k l m ...

k l m n o p q r s t u v w x y ...

e f g ...

...

k l m n o p q r s t u v w x y ...

e f g h i j k l m n o p q r s ...

y z a b c d e f g h i j k l m ...

k l m n o p q r s t u v w x y ...

e f g ...

... chiave: “key”chiave: “key”

Esempio: cifrario di Vigenere Esempio: cifrario di Vigenere

“ciao”

“ciao” “mmyy”“mmyy”

(21)

Tipologie di attacco Tipologie di attacco

Î Forza bruta (tutte le possibili chiavi)

Î Forza bruta (tutte le possibili chiavi)

Î Analisi statistica (ricorrenze delle lettere, delle sillabe, ecc.)

Î Analisi statistica (ricorrenze delle lettere, delle sillabe, ecc.)

Î Analisi con testo in chiaro scelto Î Analisi con testo in chiaro scelto

Î Analisi del crittogramma di cui è nota una parte del testo

(es. intestazione standard)

Î Analisi del crittogramma di cui è nota una parte del testo

(es. intestazione standard)

(22)

Î Chiave a 56 bit Î Chiave a 56 bit

Î 16 fasi di manipolazione ed EXOR con i bit della chiave

Î 16 fasi di manipolazione ed EXOR con i bit della chiave

DES: Data Encryption Standard DES: Data Encryption Standard

Î Due fasi di permutazione Î Due fasi di permutazione

(23)

Forzato nel 1997 Forzato nel 1997

Evoluzione: DES triplo (3DES) Evoluzione: DES triplo (3DES)

(24)

Chiavi pubbliche Chiavi pubbliche

Due chiavi Due chiavi

Chiave pubblica Chiave pubblica

Chiave privata (segreta) Chiave privata (segreta)

(25)

d_B (e_B (m)) = m = e_B (d_B (m)) d_B (e_B (m)) = m = e_B (d_B (m))

Chiavi e algoritmo di cifratura devono soddisfare la proprietà:Chiavi e algoritmo di cifratura devono soddisfare la proprietà:

(26)

Dove:

d_B chiave privata di Bob, tipicamente usata per la

decifratura

d_B chiave privata di Bob, tipicamente usata per la

decifratura

e_B chiave pubblica di Bob, tipicamente usata per la

cifratura

e_B chiave pubblica di Bob, tipicamente usata per la

cifratura

d_B (e_B (m)) = m = e_B (d_B (m)) d_B (e_B (m)) = m = e_B (d_B (m))

(27)

Crittografia a chiave pubblica Crittografia a chiave pubblica

%&*#

testo cifrato

e_B(m) testo cifrato

e_B(m) chiave

pubblica di Bob

e_B chiave pubblica

di Bob e_B

ABCD

chiaro

algoritmo di cifraturaalgoritmo di cifratura

(28)

Crittografia a chiave pubblica Crittografia a chiave pubblica

%&*# testo cifrato e_B(m)

testo cifrato e_B(m)

chiave privata

di Bob d

chiave privata

di Bob

Bob d

Bob

ABCD

testo in chiaro d_B(e_B(m))=m testo in chiaro

d_B(e_B(m))=m algoritmo di

decifratura algoritmo di

decifratura

(29)

Î RSA (Ron Rivest, Adi Shamir, Leonard Adleman)

Î RSA (Ron Rivest, Adi Shamir, Leonard Adleman)

Î Chiavi generate a partire da due

numeri primi p e q molto grandi:

p, q dell’ordine di 1024 bit

(difficile scomposizione in fattori)

Î Chiavi generate a partire da due

numeri primi p e q molto grandi:

p, q dell’ordine di 1024 bit

(difficile scomposizione in fattori)

V. descrizione dell’algoritmo V. descrizione dell’algoritmo

Algoritmo RSA per

cifratura a chiave pubblica Algoritmo RSA per

cifratura a chiave pubblica

(30)

Diffie and Hellman:

crittografia a chiave asimmetrica

Tre proprietà:

Î D(E(P)) = P

Î estremamente difficile dedurre D da E Î E non può essere forzato con attacco

di tipo “testo in chiaro a scelta”

(31)

Rivest, Shamir and Adleman:

RSA

Î Scegliere p e q (da 1024 bit) Î Calcolare

n = p x q

z = (p - 1) x (q - 1)

Î Scegliere e tale che:

1 < e < z

MCD (z, e) = 1

(32)

esempioRSA

(33)

chiavi e cifraturaRSA:

Î Chiave pubblica: { e , n } Î Chiave privata: { d, n }

Î Cifratura del testo in chiaro M < n

C = M^e (mod n)

Î Decifratura del testo cifrato C

M = C^d (mod n)

(34)

richiede calcolo di elevamento a potenza con numeri molto grandi richiede calcolo di elevamento a potenza con numeri molto grandi

Lungo tempo di elaborazione Lungo tempo di elaborazione

Problema:

(35)

scambio di chiavi simmetriche di sessione

RSA → chiavi di sessione

DES → contenuto dei messaggi RSA → chiavi di sessione

DES → contenuto dei messaggi

Possibile impiego:

(36)