Matematica e Segreti

Massimo GiuliettiDipartimento di Matematica e Informatica

Università degli Studi di Perugia

LE MANI IN PASTA NELLA SCIENZA

Leopardi e la Matematica...

Perciò la matematica la quale misura quando il piacer nostro non vuol misura, definisce e circoscrive quando il piacer nostro non vuol confini, analizza, quando il piacer nostro non vuole analisi nè cognizione intima ed esatta della cosa piacevole (quando anche questa cognizione non riveli nessun difetto nella cosa, anzi ce la faccia giudicare più perfetta di quello che credevamo, come accade nell'esame delle opere di genio, che scoprendo tutte le bellezze, le fa sparire), la matematica, dico, dev'esser necessariamente l'opposto del piacereopposto del piacere.

Zibaldone - 247/248

Luoghi comuni sulla matematica

1) “La Matematica non serve. E' astratta e inutile. E' come il Latino o il Greco Antico”

2) “La Matematica è immutabile. Cosa c'è da scoprire in Matematica?”

3) “La Matematica mortifica la fantasia. E' algoritmica e meccanica”

4) “Un laureato in Matematica può fare solo l'insegnante di Matematica”

Segreti

• Esigenza antica• Esplosa nella nostra epoca

– SMS, chat, e-mail– Numeri di care di credito– Diffusione wireless

Matematica

• Le informazioni digitali sono numeri• Come mascherare un numero?

Esempio..

Extant et ad Ciceronem, item ad familiares domesticis de rebus, in quibus, si qua occultius perferenda erant, per notas scripsit, id est sic structo litterarum ordine, ut nullum verbum effici posset: quae si qui investigare et persequi velit, quartam elementorum litteram, id est D pro A et perinde reliquas commutet.(Svetonio, De Vita Caesarum)

a b c d e f g h i l m n o p q r s t u v z

d e f g h i l m n o p q r s t u v z a b ca b c

reinserimento dei caratteri a,b,c in coda

traslazionea sinistradi 3 posizioni

Cifrario di Cesare

scienze--->vfnhqch

Operazione matematica??

• Corrispondenza lettere-numeri– A, B, C, D, ..., U, V, Z– 1, 2, 3, 4, ...,19, 20, 21

• Mascheramento:– X si trasforma in X+3 (mod 21)

Antico...ma non troppo!

Dai libri latini Bernardo Provenzano impara un metodo adottato da Giulio Cesare che spostava la lettera A di tre posti nell'alfabeto e così anche tutte le altre lettere: A, B, C diventavano quindi D, E, F, e così via.

(A. Camilleri, Voi non sapete, 2007)

Enigma

• Usata dalle forze armate tedesche nella II guerra mondiale

• Smascherata da Matematici

Un cifrario perfetto

TESTO C I V E D I A M O A L L E O T T O I N V I A R O M A

CHIAVE

TESTOCIFRATO

Un cifrario perfetto

TESTO C I V E D I A M O A L L E O T T O I N V I A R O M A

CHIAVE N E L M E Z Z O D E L C A M M I N D I N O S T R A V

TESTOCIFRATO

Un cifrario perfetto

TESTO C I V E D I A M O A L L E O T T O I N V I A R O M3 9 20 5 4 9 1 11 13 1 10 10 5 13 18 18 13 9 12 20 9 1 16 13 11

CHIAVE N E L M E Z Z O D E L C A M M I N D I N O S T R A12 5 10 11 5 21 21 13 4 5 10 3 1 11 11 9 12 4 9 12 13 17 18 16 1

TESTO 15 14 9 16 9 9 1 3 17 6 20 13 6 3 8 6 4 13 21 11 1 18 13 8 12CIFRATO Q P I R I I A C S F V O F C H F D O Z M A T O H N

Problema...

Prima che il messaggio sia trasmesso, mittente e destinatario devono INCONTRARSI E SCAMBIARSI LA CHIAVE segreta

•AL GIORNO D'OGGI QUESTO NON E' POSSIBILE!! AL GIORNO D'OGGI QUESTO NON E' POSSIBILE!!

COMMERCIO ONLINE COMMERCIO ONLINE TELEFONATE, CHATTELEFONATE, CHAT

Crittografia a chiave pubblica

• Metodo di cifratura: ACCESSIBILE A TUTTI

• Metodo di decifratura: NOTO SOLO AL DESTINATARIO

Facile a dirsi...

• In teoria, questo è impossibile: conoscere la strada per andare vuol dire conoscere la strada per tornare!

• In pratica, non è così– Elenco del telefono– Lucchetto– Ricetta di un dolce

= ?

=

Trappole matematiche

logAC

Trappole matematiche

• Trappola dei LOGARITMI

Dati A e B, facile calcolare AB

Dati A e AB, difficile risalire a B

Protocollo di Diffie-Hellman

• M || A, AB || B • ----------------M(AB)C, AC--------------->

• Il server ricostruisce M dato che

M=M(AB)C diviso per (AC)B

Seconda trappola matematica

Seconda trappola: MOLTIPLICARE DUE NUMERI PRIMI

• Dati p e q, facile calcolare il prodotto pq

• Dato n=pq, difficile risalire a p e a q

La lezione più corta della storia...

267-1= 193.707.721 x 761.838.257.287

• Convegno dell'American Mathematical Society del 1903

• Professor Nelson Cole (Columbia University)

.

L'enigma dei numeri primi

• I numeri primi sono gli atomi dell'aritmetica

• La sequenza dei numeri primi sembra caotica, senza regole

– 2,3,5,7,11,13,17,19,23,...,83,89,97,..10.000.019, 10.000.079,...

• Da secoli i matematici cercano regolarità nel comporamento di questi numeri

Risultati e problemi

• Teorema (Euclide): I numeri primi sono infiniti

• Teorema dei numeri primi– dato un numero N grande, i primi minori o

uguali di N sono circa N/ln(N)• Congettura di Goldbach

– ogni numero pari maggiore di due è la somma di due numeri primi

8=5+3 18=11+7 32=19+13

Risultati e problemi

• Ipotesi di Riemann

Uno dei 7 problemi del millennio, se qualcuno lo risolvesse avrebbe in premio un milione di dollari

Uno dei pochissimi problemi del secolo (23) rimasti irrisolti

La prima realizzazione pratica di un sistema La prima realizzazione pratica di un sistema crittografico basato sulla fattorizzazione si ha nel crittografico basato sulla fattorizzazione si ha nel 1977, ad opera di Ronald Rivest, Adi Shamir e 1977, ad opera di Ronald Rivest, Adi Shamir e Leonard Adleman, ricercatori al MIT Leonard Adleman, ricercatori al MIT (Massachusetts Institute of Technology) (Massachusetts Institute of Technology)

Crittosistema RSA

Il crittosistema RSA

• Basato sulla trappola della FATTORIZZAZIONE

• Chiave pubblica: N

• Chiave privata: la coppia di primi p e q con N=pq

• Problema centrale: il sistema è sicuro?il sistema è sicuro?

Crittosistema RSA

• Problema: come convincere il mondo degli affari della sicurezza del crittosistema RSA

• RSA 129: 114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541

RSA 129

• Previsione: migliaia di anni per trovare la soluzione

• Soluzione trovata nel 1994, grazie a 600 computers connessi a internet

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

Fattorizzato il 3

dicembre 2003

E’ la sfida piu’ grande.

Ce ne sono anche altre

intermedie!

18819881292060796383869723946165043980716356337941738270076335642298885971523466548531906060650474304531738801130339671619969232120573403879550656996221305168759307650257059

398075086424064937397125500550386491199064362342526708406385189575946388957261768583317

X

472772146107435302536223071973048224632914695302097116459852171130520711256363590397527

=

RSA 576

Firma digitale

• Difetti firma autografa:

Sempre la stessa, indipendentemente dal documento

Di verifica non immediata Inadatta a documenti elettronici

Firma digitale: idea

• Si applica al documento la cifratura con la chiave privata dell'utente

• Chiunque voglia verificare la firma applica la cifratura con la chiave pubblica dell'utente: se il risultato è il documento stesso, la firma è accettata.

PlayStation3

-SONY crea le proprie chiavi: pubblica e privata

-In ogni PS3 è caricata la chiave pubblica

-In ogni DVD, oltre al gioco, c'è la firma del gioco: il gioco mascerato con la chiave privata

-Ogni volta che il gioco viene caricato, la PS3 controlla l'autenticità della firma applicando alla firma la chiave pubblica, e verificando che il risultato sia ancora il gioco

La Matematica di MSN/Facebook/Skype

• MSN NON CIFRA I MESSAGGI SCAMBIATI FRA GLI UTENTI

• Tuttavia potete tutelare la vostra privacy installando semplici moduli di crittografia

• Più famosi: Pidgin, SimpLite

SimpLite

La Matematica di Facebook

-Dall'inizio del 2011 Facebook ha iniziato a introdurre supporto HTTPS

-Questo significa che le nostre comunicazioni verso i server di Facebook e verso i nostri "amici" sono protette

La Matematica di Skype

• Skype usa il crittosistema RSA a scopi di AUTENTICAZIONE

• Le telefonate vere e proprie sono crittate con un sistema simile al protocollo di Diffie-Hellman

The Skype code which tests for primality and generates key pairs appears to be implemented correctly. The code uses the odd powers variant of the standard square-and-multiply algorithm to perform modular exponentiation, and also uses smart squaring (which cuts the number of multiplication operations in half). In addition, the code implements the critical parts in assembly language where possible. This is platform-dependent. The Miller-Rabin test in the prime number generation code includes all the necessary test conditions of Miller-Rabin. The default number of iterations (25) included in the test makes the chances of misidentifying a composite number as prime extremely low (probability < 10-16). Even 5 Miller-Rabin iterations will yield a probability = 0.00063 of accepting a composite number. This is still an acceptable value and reduces the time to generate the primes on a client machine with limited processor speed The algorithm to generate the decryption exponent (private key) is a correctly implemented Montgomery method variant of modular inversion. This method, although it uses extra computations, eliminates the expensive trial divisions required by the Euclidian method, and replaces expensive normal divisions with the much cheaper divisions by two.

La Matematica di Skype

Banking Online

Banking Online

SMS, telefonate, pay-tv, dispositivi wireless...

• Differenza rispetto agli altri esempi: non sono usati computer, ma telefonini, decoder o oggetti piccolissimi

• PROBLEMA: trattamento dei numeri enormi che servono per garantire sicurezza

• SOLUZIONE: funzioni trappola più complicate

Trappole 'geometriche'

• Moltiplicare punti e non più numeri• Esempio: punti di una circonferenza

Curve di grado 3 (o ellittiche)

Grafici delle curve ellittiche sul campo Grafici delle curve ellittiche sul campo ℜℜ di di equazione (a) yequazione (a) y22=x=x33−−x, (b) yx, (b) y22=x=x33++1, (c) y1, (c) y22=x=x33−−5x5x++66

Trappola molto efficace

• Relativamente facile, dato un punto P della curva calcolare

P*P*P*P.....*P=PB

• ESTREMAMENTE DIFFICILE risalire a B partendo da PB

• Si può riproporre lo schema di Diffie-Hellman

Protocollo di Diffie-Hellman per curve ellittiche

• M || A, AB || B • --------------M(AB)C, AC------------> • Il server ricostruisce M dato che

M=M(AB)C diviso per (AC)B

Un po' di storia

• Proposto negli anni '80 da Miller e Koblitz

• Visto di cattivo occhio da RSA

• Visto di cattivo occhio dal Governo degli USA

Crittografia su curve ellittiche

• Non ancora così diffusa come per RSA

• Il più grosso vincolo all'uso massiccio è dato dalla mole di brevetti pendenti, detenuti dalla CERTICOM e acquistati parzialmente dalla NSA

• I servizi segreti tedeschi dichiarano che la vita dei loro agenti dipende dalle curve ellittiche

Applicazioni: traffico aereo

• March 26, 2002 - Certicom today announced a license agreement with the U.S. government's Federal Aviation Administration (FAA) to provide security solutions for the development of next-generation air traffic control networks

• Elliptic Curve Cryptography (ECC) has been selected due to the bandwidth advantages ECC enjoys

Applicazioni: Microsoft

• Microsoft consulted the NSA about Windows Vista and got certification for its security, so that it would be able to sell Vista systems to the U.S. Government. To do that, Microsoft of course had to meet the current cryptography standards. The old CryptoAPI didn't support elliptic curve cryptography, so Microsoft came up with a replacement, Cryptography API: Next Generation (CNG).

Applicazioni: BlackBerry

• Through an Elliptic Curve Diffie-Hellman (ECDH) key exchange, the BlackBerry Smart Card Reader is designed to enable wireless digital signing and encryption of wireless email messages.

Applicazioni: e-passport

DAL SITO DELLA POLIZIA DI STATO:

Dal 20 maggio 2010 gli attuali modelli in uso di passaporto elettronico saranno sostituiti dal nuovo libretto a 48 pagine a modello unificato.

Tutti gli Uffici emittenti in Italia e all'estero rilasceranno il passaporto di ultima generazione, che prevede foto e firma digitalizzate con impronte digitali in un nuovo tipo di libretto.

Applicazioni: e-passport

• All countries in the European Union (EU) must begin issuing second-generation e-passports by mid-2009. The new e-passports must have a higher level of security than the technology used to protect data on current e-passports.

• In Germania: "By using asymmetric cryptography based on elliptic curves, the information stored on the integrated circuit (IC) is kept secure"

• In Italia: la scelta fra RSA e Curve Ellittiche è oggetto di dibattito in questi mesi.

Crittofonini e curve ellittiche

www.antiintercettazione.it

Playstation3 e curve ellittiche

-L'algoritmo di firma visto prima utilizza proprio la trappola delle curve ellittiche

ECDSA

-Nel dicembre 2010 un gruppo di hacker è riuscito a risalire alla chiave privata di Sony

-Da allora è teoricamente possibile copiare DVD per PS3

-Non ci sarebbero mai riusciti se non avessero avuto conoscenze matematiche di livello universitario

Conclusione...

La matematica che 150 anni fa si sarebbe ritenuta fuori dal mondo, oggi vive nelle nostre tasche, nei nostri

giochi, e protegge i nostri segreti

Grazie per l'attenzione!