Lezione su:Lezione su:Introduzione alla Introduzione alla

crittografiacrittografia

Corso di Codici LineariCorso di Codici Lineari

è oggi il modo più semplice, comodo e veloce

di inviare e trasmettere informazioni.

Un esperto informatico non ha molte difficoltà nell’intercettare, leggere e a volte

modificare dati che passano da un computer ad un altro.

Abbiamo problemi seri quando i dati intercettati

contengono informazioni riservate come

numeri di carte di credito, password

e ogni altro tipo di “messaggio segreto”!

Abbiamo problemi seri quando i dati intercettati

contengono informazioni riservate come

numeri di carte di credito, password

e ogni altro tipo di “messaggio segreto”!

INTERNET

Sono al momento immaginabili nuove tecnologie che impediscano ai “pirati

informatici ” l’intercettazione di informazioni riservate?

La risposta è NO!

CONCLUSIONE:Non possiamo difenderci usando

l’hardware.Cerchiamo di farlo usando il

software!

CONCLUSIONE:Non possiamo difenderci usando

l’hardware.Cerchiamo di farlo usando il

software!

Come si nascondono le informazioni

riservate?

Questo si può fare con le funzioni unidirezionalifunzioni unidirezionali

Questo si può fare con le funzioni unidirezionalifunzioni unidirezionali

Bisogna trasformare “facilmente” (cifrarecifrare) il messaggio originale (testo in chiarotesto in chiaro) in uno che apparentemente non abbia alcun senso

(testo cifratotesto cifrato)

Il testo cifrato deve poter essere “facilmente” ritradotto (decifratodecifrato)

nel messaggio originale solo con l’uso di una speciale informazione (chiavechiave)

Una funzione unidirezionale F è una funzione biunivoca che si calcola

“facilmente”, mentre è praticamente impossibile calcolare la sua inversa (non esistono algoritmi di tipo polinomiale).

Il calcolo dell’inversa di F è “semplice” se si conosce un’opportuna informazione: la

“chiave”.

funzioni unidirezionali

I numeri primi permettono di

definire funzioni unidirezionali

I numeri primi permettono di

definire funzioni unidirezionali

difficilefacile

Catenaccio asimmetrico

perc

hé i

prim

i

si u

sano

in

critt

ogra

f

ia?

Moltiplicare due interi è ”facile” !

Dividere un intero per un altro è ”facile” !

Fattorizzare in primi un intero è “difficile”, a volte “impossibile” !

La funzione La funzione (p,q) pq(p,q) pq

che ad ogni coppia di primi che ad ogni coppia di primi associa il loro prodotto è associa il loro prodotto è

unidirezionale. unidirezionale.

La funzione La funzione (p,q) pq(p,q) pq

che ad ogni coppia di primi che ad ogni coppia di primi associa il loro prodotto è associa il loro prodotto è

unidirezionale. unidirezionale.

cioé

?85

1

un semplice esempio di codifica

Messaggi = alcuni numeri primi

Chiavi = alcuni numeri primi

Cifrare = moltiplicare per la chiave

Decifrare = dividere per la chiave

messaggio851:37=23

messaggio23

37

AB

A

851

B

23 37=851

RSA-576 - Premio: $10,000 - Cifre decimali: 174188198812920607963838697239461650439807163563379417382700763356422988859715234665485319060606504743045317388011303396716199692321205734031879550656996221305168759307650257059

RSA-576 - Premio: $10,000 - Cifre decimali: 174188198812920607963838697239461650439807163563379417382700763356422988859715234665485319060606504743045317388011303396716199692321205734031879550656996221305168759307650257059

The RSA Challenge Numbers

http://www.rsasecurity.com/rsalabs/challenges/factoring/numbers.html

RSA-2048 - Premio: $200,000 - Cifre decimali: 617 25195908475657893494027183240048398571429282126204032027777137836043662020707595556264018525880784406918290641249515082189298559149176184502808489120072844992687392807287776735971418347270261896375014971824691165077613379859095700097330459748808428401797429100642458691817195118746121515172654632282216869987549182422433637259085141865462043576798423387184774447920739934236584823824281198163815010674810451660377306056201619676256133844143603833904414952634432190114657544454178424020924616515723350778707749817125772467962926386356373289912154831438167899885040445364023527381951378636564391212010397122822120720357

RSA-2048 - Premio: $200,000 - Cifre decimali: 617 25195908475657893494027183240048398571429282126204032027777137836043662020707595556264018525880784406918290641249515082189298559149176184502808489120072844992687392807287776735971418347270261896375014971824691165077613379859095700097330459748808428401797429100642458691817195118746121515172654632282216869987549182422433637259085141865462043576798423387184774447920739934236584823824281198163815010674810451660377306056201619676256133844143603833904414952634432190114657544454178424020924616515723350778707749817125772467962926386356373289912154831438167899885040445364023527381951378636564391212010397122822120720357

Fattotizzato il 3

dicembre 2003

E’ la sfida piu’ grande.

Ce ne sono anche altre

intermedie!

18819881292060796383869723946165043980716356337941738270076335642298885971523466548531906060650474304531738801130339671619969232120573403879550656996221305168759307650257059

398075086424064937397125500550386491199064362342526708406385189575946388957261768583317

X

472772146107435302536223071973048224632914695302097116459852171130520711256363590397527

=

RSA-576RSA-576

Il mittente (per cifrare) eil destinatario (per

decifrare)usano la stessa chiave

segreta

crittografia simmetrica o a chiave segreta

Crittosistemi Crittosistemi simmetrici simmetrici

DDMM

fm(DD)

fn(DD)

fm

fn

(D,M,K,{(D,M,K,{fm : : mK})K})

D D è l’insieme dei messaggi in chiaro

M M è l’insieme dei messaggi in codice

K K è l’insieme delle chiavi

Un crittosistema simmetrico è una quaterna

ove

fm è la funzione (unidirezionale) di codificarelativa alla chiave m

Mittente e destinatario devono scambiarsi una chiave prima dell’inizio di ogni comunicazione

La crittografia simmetrica presenta tre grossi inconvenienti:

In un sistema con molti utenti il numero di chiavi da scambiarsi a coppie è così alto che la gestione di queste operazioni diventa molto complicata

Una buona chiave è molto lunga e vi sono seri problemi di sicurezza per la trasmissione

La sicurezza di un crittosistema non dipende dalla segretezza e

dalla complessità degli algoritmi per cifrare ma

solo dalla segretezza delle chiavi

il principio di KERCKOFFS

crittografia asimmetrica o a chiave pubblica

Gli algoritmi per cifrare e decifrare sono di dominio pubblico e ogni utente A possiede una propria coppia di chiavi (Apu , Apr)

Apu serve per cifrare ed è pubblica

Apr serve per decifrare ed è segreta (può essere utilizzata solo dal suo proprietario)

Un messaggio cifrato T con la chiave Apu può essere decifrato solo e

soltanto con la chiave privata Apr : Apr (Apu(T))=T

Chi vuole inviare un messaggio all’utente A deve cifrarlo con la chiave Apu ; il messaggio così cifrato può essere decifrato solo dal A.

Non occorre far viaggiare in segreto le chiavi per cifrare, basta far conoscere ad ogni

utente le chiavi pubbliche degli altri.

crittografia asimmetrica o a chiave pubblica

La crittografia asimmetrica permette una gestione semplice e sicura delle

chiavi, in accordo col principio di Kerckoffs.

crittografia asimmetrica o a chiave pubblica

A : Apu

A Apr

Apu (T)

Un utente trasferisce ad A il testoT cifrando con la chiave pubblica Apu

Un utente trasferisce ad A il testoT cifrando con la chiave pubblica Apu

A decifra il testo Apu (T) usando la chiave privata Apr : T = Apr (Apu (T) )

A decifra il testo Apu (T) usando la chiave privata Apr : T = Apr (Apu (T) )

A

B

C

D

EApr

Epr

Bpr

Cpr

Dpr

B : Bpu

C : Cpu

D : Dpu

E : Epu

A : Apu

utenzautenza

il crittosistema RSA

Nel 1977 tre persone diedero il più spettacolare contributo alla crittografia a chiave pubblica: Ronald Rivest, Adi Shamir e Leonard Adleman … raccolsero la sfida di produrre un crittosistema a chiave pubblica completo. Il lavoro durò alcuni mesi durante i quali Rivest proponeva strade possibili. Adleman le attaccava e Shamir faceva o l’una o l’altra cosa.

Nel maggio del 1977 essi furono ricompensati dal successo … Avevano scoperto come una semplice parte della teoria classica dei numeri poteva essere usata per risolvere il problema.

[W.Diffie, The first ten years of public-key cryptography, Proceedings of IEEE 76 (5), 1988, 560-577]

algoritmo per cifrarealgoritmo per cifrareSe l'intero positivo T è un testo in chiaro, il corrispondente testo cifrato C è definito da C=TE modN .

il crittosistema RSAil crittosistema RSA

1) N=PQ, P,Q primi molto grandi. (dell’ordine di 1024 bit)2) E>1 , intero minore di N e primo con (P-1)(Q-1).

3) DE=1 mod (P-1)(Q-1).

algoritmo per decifrarealgoritmo per decifrarePer decifrare C bisogna calcolare CD modN = T .

EsempioEsempio

(a questo punto: distruggere P e Q)

generazione delle generazione delle chiavichiavi

E=17 D=2753E=17 D=2753

Apu=(3233,17) , Apr=2753

cifriamo T=123

C=123C=1231717

mod3233=855mod3233=855decifriamo C=855

T=855T=85527532753

mod3233=123mod3233=123

P=61 Q=53 P=61 Q=53 N=PQ=3233N=PQ=3233

chiavi : chiavi : Apu=(N,E) , Apr =D

Un algoritmo per risolvere un problema che dipende da un numero N è polinomiale se richiede un numero di

operazioni elementari dell’ordine di log(N)h, per qualche intero h.

Un algoritmo per risolvere un problema che dipende da un numero N è polinomiale se richiede un numero di

operazioni elementari dell’ordine di log(N)h, per qualche intero h.

Gli algoritmi “buoni” sono quelli polinomiali

Gli algoritmi “buoni” sono quelli polinomiali

Il problema Il problema dell’autenticazionedell’autenticazione

In un sistema di comunicazione un utente A riceve un messaggio da un altro B.

Come può fare A ad essere

ragionevolmente sicuro che il messaggio ricevuto è stato effettivamente inviato da

B?

Non è richiesta la segretezza del messaggio

I crittosistemi non servono soltanto a nascondere le informazioni!

Un esempio:

una soluzione del problema una soluzione del problema dell’autenticazione:dell’autenticazione:

gli schemi di autenticazionegli schemi di autenticazione

con un numero elevato di chiavi e con la proprietà che, per ogni messaggio T, esiste un unico testo in chiaro C tale che fm(C)=T, per qualche

m K (per decifrare un messaggio non è necessaria alcuna chiave!).Gli utenti A e B concordano una chiave segreta m.

Quando A riceve il messaggio T da B, non deve fare altro che controllare se T appartiene a fm(DD).

DDMM

fm(DD)

fn(DD)

fm

fn

Si considera un criptosistema

(D,M,K,{(D,M,K,{fm : : mK})K})

Il metodo funziona perché, essendoci molte possibili chiavi, se qualcuno cambia T in un altro messaggio T’, senza conoscere la chiave segreta m, ha una piccolissima probabilità che T’ appartenga a fm(DD).

Sia k il numero delle chiavi di uno schema di autenticazione (D,M,K,(D,M,K,{{fm : : mK})K}) . Allora, per ogni testo in chiaro CDD , esistono al più messaggi T MM tali che fm (C)=T,(C)=T, per qualcheper qualche mKK .

k

Teorema di Gilbert, MacWilliams, SloaneTeorema di Gilbert, MacWilliams, Sloane

un risultato un risultato importanteimportante

In altre parole, la probabilità che un attacco ad un messaggio autenticato

vada a buon fine è sempre maggiore o uguale ak1/

uno schema di autenticazione uno schema di autenticazione perfettoperfetto

DDMM

fm(DD)

fn(DD)

fm

fn Lavoriamo in un piano proiettivo finito d’ordine q. Abbiamo q2+q+1 punti, q2 +q+1 rette, ogni punto appartienea q+1 rette e ogni retta ha q+1 punti.

D = punti di una retta d (abbiamo q+1 testi in chiaro)M = rette diverse da d (abbiamo q2+q messaggi cifrati)K = punti non appartenenti alla retta d (abbiamo q2 chiavi)Se CD e mK, poniamo fm(C) = retta per C ed m .

La probabilità che una retta (d) per C passi anche per m è 1/q, ove q è la radice quadrata del numero delle chiavi.

dC

m

fm(C)

Il nostro schema è perfetto !

bibliografia

Luigia Berardi, Albrecht Beutelspacher, Crittologia, FrancoAngeli, Milano, 1996.

Albrecht Beutelspacher, Ute Rosenbaum, Projective Geometry, Cambridge Univ.Press, Cambridge 1998.

Alessandro Languasco, Alessandro Zaccagnini, Introduzione alla crittografia, Hoepli, Milano, 2004.

Dominic Welsh, Codes and Cryptography, Oxford Science Publications, Clarendon Press, Oxford, 1988.