Elementi di crittografia

(1)

RETI DI CALCOLATORI II

Prof. PIER LUCA MONTESSORO Facoltà di Ingegneria Università degli Studi di Udine

© 2010 Pier Luca Montessoro (si veda la nota a pagina 2) 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 devono mai essere rimossi e devono essere riportati anche in utilizzi parziali.

Nota di Copyright

Elementi di crittografia

Crittografia

Permette di ottenere:

Autenticazione Segretezza

Integrità del messaggio

Definizioni

ABCD

testo in chiaro

algoritmo di cifratura

#^$&

testo cifrato

Definizioni

algoritmo di

cifratura ^ABCD

#^$&

(2)

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

Algoritmo segreto Esempio:

void crypto (char s[]) {

int i, m = strlen (s);

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

char t; int j;

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

t = s[i];

s[i] = s[j];

s[j] = t;

} return;

} Cifratura

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;

} return;

} Decifratura

Esempio:

"Cara Alice, credo che Trudy ci stia spiando"

"arT sausA eie aioCnodcrda y cc,e trlidchip"

NO: è necessario permettere lo sviluppo del software

necessario

Algoritmo segreto per Internet?

algoritmi pubblici + CHIAVI

Definizioni

ABCD

algoritmo di cifratura

#^$&

testo cifrato chiave

K_A Alice

(3)

Definizioni

algoritmo di

decifratura ^ABCD

%&*#

testo cifrato chiave

K_B Bob

Definizioni

KH#4

testo incomprensibile algoritmo di

decifratura

%&*#

?

Trudy

Chiavi simmetriche

Stessa chiave per crittografia e decrittografia

Come scambiarsi le chiavi?

Problema:

Chiavi simmetriche

len (chiave) > len (messaggio) chiavi sempre diverse Massima sicurezza:

Algoritmi per chiavi simmetriche

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

Cifrature monoalfabetiche (cifrario di Cesare)

Î Forzatura tramite analisi statistica delle ricorrenze

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” “erfv”

Esempio: cifrario di Cesare

(4)

n cifrari di Cesare usati ciclicamente Cifrature polialfabetiche

(cifrari di Vigenere)

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

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”

Esempio: cifrario di Vigenere

“ciao” “mmyy”

Tipologie di attacco

Î Forza bruta(tutte le possibili chiavi) Î Analisi statistica(ricorrenze delle

lettere, delle sillabe, ecc.)

Î Analisi con testo in chiaro scelto Î Analisi del crittogramma di cui è

nota una parte del testo (es. intestazione standard)

Î Chiave a 56 bit

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

DES: Data Encryption Standard

Î Due fasi di permutazione

Forzato nel 1997

Evoluzione: DES triplo (3DES)

Chiavi pubbliche

Due chiavi Chiave pubblica Chiave privata (segreta)

(5)

d_B(e_B (m)) = m = e_B (d_B(m)) Chiavi pubbliche

Chiavi e algoritmo di cifratura devono soddisfare la proprietà:

Chiavi pubbliche

Dove:

d_Bchiave privata di Bob, tipicamente usata per la

decifratura

e_Bchiave pubblica di Bob, tipicamente usata per la

cifratura

m messaggio

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

Crittografia a chiave pubblica

%&*#

e_B(m) chiave

pubblica di Bob

eB Alice ABCD

algoritmo di cifratura

Crittografia a chiave pubblica

%&*# testo cifrato eB(m) chiave

privata di Bob

d_B Bob

ABCD testo in chiaro

dB(eB(m))=m algoritmo di

decifratura

Î 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)

V. descrizione dell’algoritmo sul libro di testo

Algoritmo RSA per

cifratura a chiave pubblica

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”

(6)

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

Î Calcolare d < z tale che de mod z = 1

RSA esempio

RSA:

chiavi e cifratura Î 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)

richiede calcolo di elevamento a potenza con numeri molto grandi

Lungo tempo di elaborazione Problema:

scambio di chiavi simmetriche di sessione

RSA → chiavi di sessione

DES → contenuto dei messaggi Possibile impiego: