Cifratura chiave pubblica 2008 - Link.it · Sicurezza nelle reti di TLC - Prof. Marco Listanti -...

Sicurezza nelle reti di TLC - Prof. Marco Listanti - A.A. 2008/2009INFOCOM Dept

Cifratura a chiave pubblica


Crittografia a chiave privata

Chiave singolaCrittografia simmetrica

La stessa chiave è utilizzata sia per la cifratura che per la decifratura dei messaggi

La chiave rappresenta il segreto condiviso tra sender e receiver

La rivelazione della chiave compromette la riservatezza delle comunicazioni

Un sistema crittografico simmetrico non protegge il sender dal fatto che il receiver possa assemblare un messaggio e sostenere che questo sia stato emesso dal sender


Crittografia a chiave pubblica (1)

L’ideazione risale alla metà degli anni ’70 (Diffie, Helmann 1976)Ha rappresentato una vera rivoluzione nella storia dei sistemi crittografici

Crittografia asimmetricaOgni utente possiede due chiavi

Chiave privata segreta (non condivisa)Chiave pubblica (nota a chiunque)

Se si effettua la codifica con una chiave (privata/pubblica), la decodifica può essere effettuata solo con l’altra chiave (pubblica/privata)

Complementa l’uso della crittografia simmetrica e consente la realizzazione di diversi servizi

ConfidenzialitàAutenticazioneFirma Digitale



Le due chiavi (pubblica e privata) sono correlate tra loro

La chiave pubblica di un utente può essere conosciuta da chiunque e può essere usata per

Cifrare i messaggi (confidenzialità)

Verificare la firma digitale (autenticazione)

La chiave privata di un utente deve essere mantenuta segreta e può essere usata per

Decifrare i messaggi (confidenzialità)

Creare la firma digitale (autenticazione)

Il sistema è asimmetricoL’entità che cifra i messaggi o verifica le firme non può decrittare i messaggi o creare le firme



I sistemi a chiave pubblica sono stati ideati per risolvere due problemi

Distribuzione delle chiaviAvere un canale sicuro per la distribuzione delle chiavi senza avere una relazione sicura con un Centro di Distribuzione Chiavi (CDC)

Firme digitaliAvere un meccanismo sicuro per verificare che un messaggio non abbia subito manipolazioni rispetto a quello che viene indicato dal sender

RequisitiDeve essere computazionalmente infattibile individuare la chiave usata per la decifrazione (pubblica o privata) conoscendo solo un messaggio cifrato e la chiave di cifratura (privata o pubblica)

Deve essere computazionalmente semplice cifrare e/o decifrare i messaggi se è conosciuta la chiave di cifratura e/o decifratura


Confidenzialità (1)

Schema generale

Bob Alice



Servizio di confidenzialità della comunicazione da A a B

A legge la chiave pubblica di B da una directory pubblica accessibile a tutti

A codifica il messaggio con la chiave pubblica di B

Il messaggio può essere decifrato solo mediante la chiave segreta di B

B decifra il messaggio con la sua chiave segreta

Algoritmodi

decifratura

Chiavepubblica

di B

Chiavesegreta

di B

Algoritmodi

cifratura

MittenteA

DestinatarioB

Testo inchiaro

Testo inchiaro

Testocifrato

Testocifrato

Testo inchiaro

Testo inchiaro



Servizio di confidenzialità della comunicazione da A a B

Testo cifrato: Y = EKPb (X)

Testo decifrato: X = DKSb(Y)

Originalemessaggio Algoritmo

di cifraturaDestinazioneAlgoritmo

di decifratura

Analistacrittografico

X

KPb

Y X

KSb^

X̂

Originalechiavi

KSb

Origine A Destinazione B


Autenticazione (1)

Schema generale

Bob Alice


Autenticazione (2)

Servizio di autenticazione di un messaggio emesso da A verso B

A codifica il messaggio utilizzando la propria chiave segreta

Il messaggio può essere decifrato solo mediante la chiave pubblica di A

Tutti possono decifrare il messaggio, quindi anche B

Il fatto che sia possibile decifrare il messaggio con la chiave pubblica di A dimostra che A è effettivamente il mittente del messaggio

Algoritmodi

decifratura

Testo inchiaro

Testo inchiaro

Chiaveprivata

di A

Chiavepubblica

di A

Testocifrato

Testocifrato

Algoritmodi

cifratura

TestoAutenticato

TestoAutenticato

MittenteA

DestinatarioB


Autenticazione (3)

Servizio di autenticazione della comunicazione da A a B

Testo cifrato: Y = EKSa (X)

Testo decifrato: X = DKPa(Y)



di decifratura

Analistacrittografico

X

KPa

Y X

KSa^

Originalechiavi

KSa



Confidenzialità e Autenticazione

Servizi di Confidenzialità e Autenticazione da A a BTesto cifrato: Z = EKPb (EKSa(X))

Testo decifrato: X = EKPa (EKSb(Z))

KPa

Originalechiavi

KSa




di decifraturaAlgoritmodi cifratura

Algoritmodi decifratura

KPb Originalechiavi

KSb

X Y XZ Y


Confronto Crittografia Simmetrica e Asimmetrica

Crittografia Simmetrica (Chiave Privata) Crittografia Asimmetrica (Chiave pubblica)Requisiti di Funzionamento

Requisiti per la Sicurezza

Stesso algoritmo e unica chiave per la cifratura e decifratura

Stesso algoritmo per la cifratura e decifratura, ma uso di una coppia di chiavi (una per la codifica e una per la decodifica)

Mittente e destinatario devono condividere la stessa chiave

Mittente e destinatario devono utilizzare una coppia di chiavi correlate, ma distinte

Chiave deve essere mantenuta segreta Una delle chiavi deve essere mantenuta segreta, l’altra è pubblica

Deve essere impossibile decodificare il messaggio senza disporre di altre informazioni

Deve essere impossibile decodificare il messaggio senza disporre di altre informazioni

La conoscenza dell’algoritmo e di campioni di testo cifrato non deve essere sufficiente a determinare la chiave

La conoscenza dell’algoritmo, di una chiave e di campioni di testo cifrato non deve essere sufficiente a determinare l’altra chiave


Requisiti crittografia a chiave pubblica (1)

Generazione chiavi semplicePer un utente A deve essere computazionalmente facile generare una coppia di chiavi (KSA e KPA)

Cifratura testo in chiaro semplice

Deve essere computazionalmente facile per un sender A, conoscendo la chiave pubblica del receiver B, generare il testo cifrato

C = EKPb(M)

Decrittazione testo cifrato semplice (nota chiave segreta) Deve essere computazionalmente facile per un receiver B, ottenere il testo in chiaro decrittando il testo cifrato

M = DKSb(C) = DKSb[EKPb(M)]



Individuazione chiave privata impossibileDeve essere computazionalmente impossibile per un attaccante, conoscendo la chiave pubblica di un utente (KPA), ricavare la sua chiave privata (KSA)

Decrittazione testo cifrato semplice (ignota chiave segreta)

Deve essere computazionalmente impossibile per un attaccante, conoscendo la chiave pubblica di un utente (KPA) ed il testo cifrato C, risalire al testo in chiaro M

C = EKPb(M)



Ad oggi sono noti solo due algoritmi che soddisfano ai requisiti ora illustrati

RSA

Curva ellittica

La sicurezza di questi algoritmi dipende dalla lunghezza delle chiavi e dalla difficoltà di effettuare particolari operazioni matematiche

Nella crittografia a chiave pubblica si usano chiavi di lunghezza molto elevata (≥512 bit)

Le operazioni di cifratura e decifratura sono più complesse rispetto a quelle della crittografia simmetrica

L’uso della crittografia a chiave pubblica è utilizzato essenzialmente per le funzioni di gestione delle chiavi e per la firma digitale


Elementi di Teoria dei Numeri


Numeri primi (1)

Un numero intero è un numero primo se ha per divisori solo 1 e se stessoUn numero primo non può essere fattorizzato, ovvero espresso come prodotto di altri numeri

Una fattorizzazione di un numero n corrisponde ad una sua espressione tramite prodotto di altri numeri

Esempio: n = a. b. cSi noti che trovare una qualsiasi fattorizzazione di un numero è un’operazione molto più complessa che ottenere il numero noti i fattori

Una fattorizzazione in numeri primi di un numero n si ottiene esprimendo n come prodotto esclusivamente di numeri primi

Detta p1, p2,…, pk la sequenza dei primi k numeri primi, si ha

La fattorizzazione di n in numeri primi è unica

pk a

Ppak

aa pnpppn∈Π=→= L21

21


Numeri primi (2)

Considerando l’espressione

Il valore di n può essere specificato semplicemente indicando gli esponenti ai (i=1,2,..,k) diversi da zero

Esempio: 12 = 22.3 e quindi può rappresentato da {a2=2,a3=1}

Il prodotto tra due numeri è uguale alla somma degliesponenti corrispondenti

Esempio:

12 → {a2=2,a3=1}; 18 → {a2=1,a3=2} da cui 12x18=216 → {a2=3,a3=3};

pa

Pppn

∈Π=


Numeri relativamente primi

Due numeri a e b sono detti primi relativi se non hanno divisori comuni eccetto 1

Esempio: 8 e 15 sono primi relativi tra loroDivisori di 8 : 1, 2, 4, 8; Divisori di 15 : 1, 3, 5, 15

Si definisce Massimo Comune Divisore [MCD(a,b)] di due numeri a e b il loro divisore comune di valore più grande

Esempio: MCD(18,300) = 6

Se a e b sono primi relativi si ha MCD(a,b)=1

In generale detti a → {a1,a2,a3,.. ap} e b → {b1,b2,b3,.. bp}

MCD(a,b) → {k1,k2,k3,.. kp} dove ki = min(ai,bi) (i=1,2,…,p)


Teorema di Fermat

Dati due numeri a e p, dovep è un numero primo

MCD(a,p) = 1, ovvero a e p sono primi relativi

si ha

Esempio: a=3, p=5

ap-1 mod_5 = 34 mod_5 = 81 mod_5 = 1

1mod1 =− pa p


Funzione Toziente di Eulero

Dato un intero n, si definisce funzione toziente di Eulero di n [φ(n)] il numero di interi positivi minori di n e primi relativi di n

Esempio: φ(10) = 4i numeri positivi minori di 10 sono 1, 2, 3, 4, 5, 6, 7, 8, 9tra questi i numeri primi relativi di 10 sono 1, 3, 7, 9, quindi φ(10) = 4

Se n è un numero primo si ha φ(n)=n-1Dati due numeri primi p e q e un numero n=p.q si ha:

φ(n) = φ(pq) = φ(p).φ(q) = (p-1).(q-1)

Esempio: p=5, q=7 → φ(5)=4, φ(7)=6, p.q=35 → φ(35)=24non sono primi relativi di 35: 1) i multipli di 5 (5,10,15,20,25,30);2) i multipli di 7 (7,14,21,28); quindi φ(35)=34-10=24,


Teorema di Eulero

E’ una generalizzazione del teorema di FermatDati due numeri a e N primi relativi, ovvero per cui MCD(a,N)=1, si ha

Esempio: a=3, N=10 si ha φ(10) = 4, quindi: 34 mod_10 = 1Se N è un numero primo si ottiene il teorema di Fermat poichéφ(N)=N-1

Corollario del teorema di Eulero

1mod)( =Na Nφ

aNa N =+ mod1)(φ


Radici primitive (1)

Si consideri l’espressione, in cui a e n sono primi relativiam mod_n = 1

In base al teorema di Eulero questa equazione ammette almeno la soluzione m=φ(n), ma ci possono essere anche altre soluzioni

Esempio: per a=7, n=19 si ha l’equazione 7m mod_19 = 1Le soluzioni sono m=3, 6, 9, 12, 15, 18 [φ(n)], 21, …

Il più piccolo valore di m (mmin) che soddisfa l’equazione è detto lunghezza del periodo generato da a (mod n)

Esempio: per a=7, n=19 il periodo generato da a=7 è mmin=3, infatti71 mod_19 = 7; 72 mod_19 = 11; 73 mod_19 = 1;74 mod_19 = 7; 75 mod_19 = 11; 76 mod_19 = 1;……

Sostituendo nella funzione [am mod_n] tutti i valori interi si ottiene una sequenza periodica di periodo mmin=3, ogni periodo si chiude con il valore di m che soddisfa l’equazione


Radici primitive (2)

Se n è primo e il valore minimo di che soddisfa l’equazione [ammod_n=1] è uguale a φ(n), la lunghezza del periodo generato da a (mod n) è uguale a n-1

In questo caso l’intero base a genera, tramite le potenze da 1 a φ(n) e attraverso l’operazione mod_n, tutti gli interi diversi da 0 minori di n

Se la condizione precedente è vera a è detta radice primitiva di n

Se a è una radice primitiva di n (primo) si ha che i numeri

a1 mod_n; a2 mod_n; a3 mod_n; ……; ap-1 mod_n

sono numeri distinti che vanno da 1 a n-1


Esempio di Radici primitive (3)

Esempio: le radici primitive di n=19 [φ(n)=18] sono 2, 3, 10, 13, 14, 15


Logaritmi discreti

Dato un intero b e una radice primitiva a di un numero primo n, si definisce logaritmo discreto di b per la base a mod_n, l’esponente i tale che

b = ai mod_n 0 ≤ i ≤ n-1; 1 ≤ b ≤ n-1

Il logaritmo discreto si indica con l’espressione

i = inda,n(b)

Esempio: n=19, b=3

)(19,3 bindb


Complessità calcolo logaritmi discreti

Data l’espressione di un logaritmo discreto

b = ai mod_pin cui a è una base primitiva del numero primo n

E’ immediato calcolare b noti, a, p, i

E’ molto complesso calcolare i (logaritmo discreto) noti b, a, p

E’ noto un solo algoritmo di complessità

Ad oggi è praticamente impossibile calcolare un logaritmo discreto per numeri primi di grandi dimensioni

( ) ( )( )3/23/1 lnlnln ppe


Algoritmo RSA (1)

Algoritmo ideato da Rivest, Shamir & Adleman nel 1977Cifratura a blocchi in cui il testo in chiaro ed il testo cifrato sono interi compresi tra 0 e n-1

Normalmente n ha dimensione uguale a 1024 bit (lunghezza blocco) (equivalente ad un numero intero di circa 309 cifre)

La crittografia di un testo in chiaro M e la decrittografia di un testo cifrato C hanno la forma

C = Me mod_nM = Cd mod_n = (Me)d mod_n = Med mod_n

Il sender S conosce {e,n} → Chiave pubblica di R Kp(R)={e,n}Il receiver R conosce {d,n} → Chiave privata di R Ks(R)={d,n}

S RC


Algoritmo RSA (2)

Requisiti base dell’algoritmo RSADeve essere possibile trovare i valori di e, d, n tali che M=Medmod_n per qualsiasi valore di M < n

Deve essere semplice calcolare Me e Cd per tutti i valori M < n

Deve essere computazionalmente impossibile determinare “d” conoscendo “e” e “n”


Algoritmo RSA (3)

La generazione delle chiavi (pubblica e privata) da parte di una entità A si articola nei seguenti passi

A sceglie due numeri primi p, q (valori che devono essere mantenuti segreti)A calcola n=p.q (valore che può essere pubblico)A sceglie il valore di e tale che MCD(e, φ(n))=1 con 1 < e < φ(n) (valore pubblico)

I valori di e e φ(n) sono primi relativi

A calcola d = e-1 mod_φ(n) (valore segreto)Chiave privata di A → Ks(A) = {d,n} (valore segreto)Chiave pubblica di A → Kp(A) = {e,n} (valore pubblico)

Nel caso un utente A abbia pubblicato la sua chiave pubblica {e,n} e un altro utente B debba inviare ad A il messaggio M, la crittografia C del testo in chiaro M è data da

C = Me mod_nLa decrittografia M del testo cifrato C è data da

M = Cd mod_n

B AC


Algoritmo RSA (4)

Giustificazione procedura generazione chiaviI valori di e,d sono scelti in modo tale che → d = e-1 mod_φ(n)

Quindi → d.e mod_φ(n) = 1

Il prodotto d.e ha la forma k.φ(n) + 1

Poiché n=p.q con p e q primi, per le proprietà della funzione toziente di Eulero → φ(n)=(p-1)(q-1)

Per il teorema di Eulero → Mkφ(n)+1 = Mk(p-1)(q-1)+1 = M mod_n

Quindi → Med = M mod_n


Esempio generazione chiavi

Scegliamo p = 17, q =11

Calcoliamo n =pq =17 x 11 =187

Calcoliamo φ(n) = (p-1)(q-1) = 16 x 10 = 160

Scegliamo e in modo che sia primo relativo di φ(n)=160, ad esempio e=7

Determiniamo d, tale che e.d mod_160=1 e d<160, si ha d=23

Chiave pubblica Kp = {7,187}

Chiave privata Ks = {23,187}


Sicurezza RSA

Tre possibili attacchiForza bruta

Sono necessarie chiavi di grandi dimensioni

MatematicoCerca di scomporre il numero n nei fattori p e q


Gestione delle chiavi nella crittografia pubblica


Gestione delle chiavi

La crittografia a chiave pubblica permette di risolveredella gestione delle chiavi in un sistema crittograficopoichè

Permette la distribuzione delle chiavi pubbliche

Permette l’uso delle cifratura mediante chiavi pubbliche per distribuire eventuali chiavi segrete

Le chiavi pubbliche possono essere rese note medianteAnnuncio publico (Public announcement)

Elenco pubblico (Publicly available directory)

Autorità di distribuzione delel chiavi (Public-key authority)

Certificati (Public-key certificates)


Annuncio pubblico

Gli utenti distribuiscono direttamente le propriechiavi pubbliche agli altri utenti o effettuano un annuncio broadcast

Questo schema non protegge da eventualicontraffazioni

Chiunque può assumere un’identità falsa, creare unachiave e diffonderla

E’ possibile un attacco per mascheramento


Elenco pubblico

Le chiavi pubbliche possono essereregistrate in un leneco pubblico (directory)La directory deve essere gestito da un entità fidata

contiene l’associazione {nome, chiave pubblica} di ciascun utenteGli utenti devono accedere alla directory in modo sicuroGli utenti devono poter sostituire la chiave in qualsiasi momentoLa directory deve essere aggiornataperiodicamenteL’accesso alla directory deve essereelettronico

L’elenco pubblico è vulnerabile da attacchi ditampering (individuazione della chiaveprivata dell’autorità) e di distribuzione dichiavi pubbliche contraffatte


Autorità di gestione delle chiavi pubbliche (1)

Migliora la sicurezza della soluzione precedenteeffettuando un controllo più stretto sulla distribuzionedelle chiavi

Le modalità sono identiche a quelle dell’elenco pubblico, ma è basato sull’uso della chiave pubblica dell’autorità digestione

Gli utenti accedono alla directory per ottenere qualsiasichiave pubblica in modo sicuro

E’ necessario l’accesso real time alla diretory per averela chaive pubblica dell’entità corrispondente


Autorità di gestione delle chiavi pubbliche (2)

1. A invia un messaggio all’autorità per richiedere la chiave pubblica di B

2. L’autorità risponde inviando la chiave pubblica di B con un messaggio crittografato con la propria chiave privata (autenticazione)

3. A usa la chiave pubblica di B per inviare a B il proprio identificatore (IDA) e un nonce(N1)

4. B invia all’autorità la richiesta della chiave pubblica di A (analogo passo 1)

5. L’autorità risponde inviando la chiave pubblica di A con un messaggio crittografato con la propria chiave privata (autenticazione) (analogo passo 2)

6. B invia a A un messaggio cifrato con la chiave pubblica di A contenente il nonce N1 e un nuovo nonce generato da B (N2)

7. A risponde a B con un messaggio crittigrafato con la chiave pubblica di B contenente il nonce di B (N2)


Certificati a chiave pubblica (1)

I certificati permettono lo scambio delle chiavi senza la necessità di accedere all’autorità di gestione delle chiavi

Un certificato associa l’identità dell’utente alla propriachiave pubblica

Un cerificato contiene anche informazioni accessoria come tempo di validità, diritto d’uso, ecc.

Un certificato è firmato da una Certification Authority (CA) mediante la propria chiave privata

Un certificato può essere verificato attraverso la chiavepubblica della CA


Certificati a chiave pubblica (2)

A e B chiedono alla CA di emettere un certificato che indica e autentica la rispettiva identità e chiave pubblica

A invia a B il proprio certificato CA contenente la propria chiave pubblica

B effettua la stessa operazione verso A inviando il proprio certificato CB


Distribuzione delle chiavi segrete

Una volta ottenute le chiavi pubbliche, questepossono essere utilizzate per la distribuzionedelle chiavi segrete di un sistema crittograficosimmetrico

La crittografia simmetrica è computazionalmente piùsemplice rispetto a quella a chiave pubblica

Mediante le chiavi pubbliche è possibilerealizzare la segretezza e l’autenticazione delloscambio delle chiavi segrete di sessione


Protocollo di Merkle

Fasi del protocolloA genera una coppia temporanea di chiavi pubblica/privataA invia a B la chiave pubblica e la sua identitàB genera una chiave di sessione K e la invia ad A crittografandola con la chiavepubblica inviata da AA decifra la chiave di sessione

Questo protocollo è vulnerabile ad un attacco attivo (man-in-the-middle) in cui un attacante

Intercetta le comunicazioni di A e di BImpersona l’identità di A verso B e viceversa


Protocollo di Merkle protetto

Una che A han ottenuto la chiave pubblica di B e viceversaA utilizza la chiave di B per crittografare un messaggio contenente un nonceN1 e l’identificatore di A (IDA)B risponde con un messaggio crittigrafato con la chiave pubblica di A contenente N1 e un nuovo nonce N2A risponde a B inviando N2 crittografato con la chiave pubblica di BA invia a B la chiave di sessione Ks crittografata con la chiave privata di A e con la chiave pubblica di B

La crittografia con la chiave privata di A assicura B che la chiave viene sicuramente da A


Protocollo di Diffie-Hellman (1)

Protocollo pratico usato in numerose applicazioni per lo scambio di una chiave segreta tra due entitàTutti gli utenti concordano su un insieme di parametri globali

Un numero primo di grandi dimensioni qUna radice primitiva α di q

Un utente (es.A) genera la propria chiaveSceglie la propria chiave privata xA (un numero xA < q)Calcola la propria chiave pubblica yA (yA=α

xAmod_q )Rende pubblica la propria chiave pubblica yA

Al termine di questa proceduraA conosce yBB conosce yA



La chiave segreta condivisa tra A e B è KAB, calcolatasecondo la seguente proceduraKAB = α xA.xB mod q

= yAxB mod q (which B can compute)

= yBxA mod q (which A can compute)

KAB è usata come chiave segreta di sessione tra A e B

La sicurezza del protocollo si basa sulla difficoltà dicalcolo dei logaritmi discreti

xA = indα,q(yA); xB = indα,q(yB)



AA BB

1

2

L’utente A

Genera un numero casuale XA

Calcola il valore YA= αXA mod_q

Emette verso B il numero YA



AA BB

1

2L’utente B

Genera un numero casuale XB

Calcola il valore YB= αXB mod_q

Emette verso A il numero YB

Calcola la chiave segreta K= (YA) XB mod_q



AA BB

1

2

L’utente ACalcola la chiave segreta K= (YB) XA mod_q


Esempio protocollo Diffie-Hellman

Alice (A) e Bob (B) concordano i seguenti valoriq=353 ; α=3

Scegliono in modo casuale la propria chiave segretaA sceglie xA=97, B sceglie xB=233

A e B calcolano le rispettive chaivi pubblicheyA=397

mod 353 = 40 (A)yB=3233

mod 353 = 248 (B)

A e B calcolano la chiave di sessioneKAB= yB

xA mod 353 = 24897= 160 (Alice)

KAB= yAxB mod 353 = 40233

= 160 (Bob)

Cifratura chiave pubblica 2008 - Link.it · Sicurezza nelle reti di TLC - Prof. Marco Listanti -...

Documents

Transcript of Cifratura chiave pubblica 2008 - Link.it · Sicurezza nelle reti di TLC - Prof. Marco Listanti -...