1
Carlo Strapparava - Informatica
Analisi di programmi: Crittografia
Come caso concreto di sistema, proviamo adabbozzare e a vedere una primaimplementazione di un sistema di crittografiaa chiave pubblica
La crittografia studia le tecniche pernascondere l’informazione
Tecniche di crittografia sono molto usate perla sicurezza di transazioni bancarie,e-commerce, firme digitali
Carlo Strapparava - Informatica
Crittografia
Un sistema crittografico si compone di due parti: unacodifica (o cifratura) e una decodifica (o decifratura)
Messaggio “in chiaro” Cifratura
Chiave
Messaggio criptato
Messaggio criptato Decifratura Messaggio “in chiaro”
Chiave
2
Carlo Strapparava - Informatica
Crittografia simmetrica
Quando si usa un'unica chiave sia perproteggere il messaggio che per renderlonuovamente leggibile, si parla di crittografiasimmetrica
Fino a pochi anni fa l'unico metodocrittografico esistente era quello dellacrittografia simmetrica
Il problema è portare in giro la chiave senzache venga scoperta
Carlo Strapparava - Informatica
Crittografia
Macchina per crittografia“Enigma”, usata dai militaritedeschi nella secondaguerra mondiale
Gli alleati, in particolare gliInglesi, studiarono a lungoil modo di “crackare” ilcodice dei Tedeschi … e ciriuscirono
3
Carlo Strapparava - Informatica
Crittografia a chiave pubblica
Il problema della crittografia simmetrica stanella gestione delle chiavi: Come faccio a trasmettere la chiave in maniera
sicura ?
Sarebbe bello avere un sistema che permette la codifica dei messaggi con una chiave e la decodifica con una chiave completamente
diversa
Carlo Strapparava - Informatica
Crittografia a chiave pubblica
Nel 1978, Ronald Rivest, Adi Shamir, and LenAdleman inventarono la crittografia RSA
La crittografia RSA ha una coppia di chiavi: unachiave pubblica e una privata
A e B vogliono comunicare segretamente A genera la coppia di chiavi, tiene per sè quella
privata e manda a B quella pubblica B critta il messaggio con la chiave pubblica e lo
manda a A. La chiave non importa che sia pubblica:serve solo a crittografare i messaggi
A è in grado di decodificare il messaggio con la suachiave privata
4
Carlo Strapparava - Informatica
RSA: la teoria RSA è basato sulla fattorizzazione in numeri primi si scelgono a caso due numeri primi, p e q, l'uno
indipendentemente dall'altro, abbastanza grandi dagarantire la sicurezza dell'algoritmo
si calcola il loro prodotto n = pq , chiamato modulo (datoche tutta l'aritmetica seguente è modulo n)
si calcola poi m = (p - 1) (q - 1) Si seleziona anche un numero e tale che MCD(e,m)=1 La chiave pubblica è la coppia di numeri (n,e) Chiunque voglia mandarci un messaggio s, lo crittograferà
utilizzando la seguente trasformazione S = (se) modulo n
Carlo Strapparava - Informatica
RSA: la teoria
Vediamo la parte della chiave privata Se ricevo un messaggio S, lo decodificherò usando la
seguente trasformazione RSA, usando la coppia dinumeri (n,d)
s′ = (Sd) modulo n Il numero d viene scelto in modo che s’ = s s = (se)d modulo n E si può verificare avviene se de = 1 modulo m (n, d) è la chiave privata
5
Carlo Strapparava - Informatica
RSA: la teoria
Quindi una volta che ho calcolato questi numeri, lacoppia (n, e) sarà la chiave pubblica, mentre (n, d)sarà la chiave privata
La sicurezza del metodo RSA si basa sul fatto cheanche se uno conosce la chiave pubblica (n, e), ilmetodo per ottenere d, è quello di fattorizzare n pertrovare i numeri p e q e trovare così gli altri numeri
Quindi “crackare” un codice RSA è difficile almenoquanto fattorizzare n nei sui primi p e q
Quando p e q sono numeri di 300 cifre, questorichiede un secolo di tempo macchina del più velocesupercomputer
Carlo Strapparava - Informatica
RSA: implementazione
Il cuore del metodo è il calcolo (se) modulo n
Data abstraction per il tipo di dato “chiave”
(define (expmod b e m) ;; simile all’esponenziazione vista (cond ((zero? e) 1) ;; a lezione ma consiederando il modulo ((even? e) (modulo (square (expmod b (/ e 2) m)) m)) (else (modulo (* b (expmod b (- e 1) m)) m))))
(define make-key cons) ;; il costruttore(define key-modulus car) ;; i selettori(define key-exponent cdr)
(define (RSA-transform number key) ;; il cuore del metodo RSA (expmod number (key-exponent key) (key-modulus key)))
6
Carlo Strapparava - Informatica
RSA: implementazione
Una coppia di chiavi RSA, consiste in unachiave pubblica ed una privata
(define make-key-pair cons) ;; il costruttore(define key-pair-public car) ;; i selettori(define key-pair-private cdr)
(define (generate-RSA-key-pair) ;; implementazione della generazione della coppia di chiavi …
)
Carlo Strapparava - Informatica
RSA: implementazione
Il metodo RSA è pensato per trasformare numeri Noi abbiamo bisogno di spedire messaggi di testo Possiamo pensare si usare come predefinite due
funzioni string->intlist e intlist->stringche trasformano rispettivamente stringhe di testo inliste di numeri e liste di numeri in stringhe
(string->intlist "questo e' un messaggio")⇒ (242842353 212350964 232607783 242841248 217706739 67647465)(intlist->string '(242842353 212350964 232607783 242841248 217706739 67647465))⇒ "questo e' un messaggio ”
7
Carlo Strapparava - Informatica
RSA: implementazione Una volta cha abbiamo questa lista di numeri, li
codifichiamo / decodifichiamo con la trasformazione RSARSA-transform
Nei metodi reali si sceglie di codificare il primo numerodella lista, sommarlo al secondo, codificare la somma,sommare il risultato al terzo numero ecc…
(define (RSA-convert-list intlist key) …)(define (RSA-unconvert-list intlist key) …)
Carlo Strapparava - Informatica
RSA: implementazione
Vediamo le funzioni generali per usare la crittografiaRSA
Notiamo che tutto il metodo trasforma numeri,mentre noi dobbiamo trattare messaggi di testo
(define (RSA-encrypt string key1) (RSA-convert-list (string->intlist string) key1))
(define (RSA-decrypt intlist key2) (intlist->string (RSA-unconvert-list intlist key2)))
8
Carlo Strapparava - Informatica
RSA: test Proviamo ad usare il sistema Es. Sarkozy spedisce messaggi a Carla, con la chiave pubblica di Carla
(define sarkozy-rsa-key (generate-RSA-key-pair))(define carla-rsa-key (generate-RSA-key-pair))(define cecilia-rsa-key (generate-RSA-key-pair))(key-pair-public sarkozy-rsa-key)⇒ (478995823 . 37981609)(key-pair-private sarkozy-rsa-key)⇒ (478995823 . 213019289)(key-pair-public carla-rsa-key)⇒ (530019449 . 364979005)(key-pair-private carla-rsa-key)⇒ (530019449 . 421224373)(RSA-encrypt "Amo Carla Bruni" (key-pair-public carla-rsa-key))⇒ (28522895 337295473 59556703 410503941)(RSA-decrypt '(28522895 337295473 59556703 410503941) (key-pair-private carla-rsa-key))⇒ "Amo Carla Bruni ”(crack-rsa (key-pair-public carla-rsa-key)) ;; Cecilia cracka la chiave di Carla⇒ (530019449 . 421224373)