Vi racconterò una storia matematica che mostra la grande unità della disciplina, inziando come fa da problemi elementari e finendo nella ricerca e nelle sue applicazioni. La storia La storia di due triangoli: i triangoli di Erone e le curve elli3che Osservare: quali legami? 4 5 Area con la formula di Erone Perimetro = 12 3 156 35 101 21 41/15 Porre un problema: argomentare I due triangoli hanno stessa area E stesso perimetro. Come trovare altri (tuJ i) triangoli che hanno stessa area E stesso perimetro? 4 5 3 156 35 101 21 41/15 Osservare e argomentare: a, b, c α, β, γ Argomentare e calcolare A = area r = raggio s = semiper. γ β α A = rs Calcolare z z x γ α/2 β y y x = r tan(α /2) A = area r = raggio s = semiper. x y = r tan(β /2) z = r tan(γ/2) Argomentare e calcolare γ β α A = rs Calcolare γ β α A = rs x > 0, y> 0, xy > 1 Osservare, Argomentare, Calcolare e Dimostrare 2 xy + 2 xy – kxy + k = 0 x > 0, y> 0, xy > 1 , k = 2 s /A >0 9 Guardando in avanP 2 xy + 2 xy – kxy + k = 0 È una curva elliJca Forma normale di Weierstrass: y2 = f(x) = x3 + ax2 + bx + c Se le radici (ev. complesse) sono distinte si chiama curva ellittica. Cubiche singolari y2 = x2(x + 1) y2 = x3 13 Guardando in avanP • Curve elliJche e punP razionali: uno sguardo dall’alto al nostro problema • Curve elliJche e dimostrazione Teor. di Fermat • Curve, integrali, funzioni elliJci • Curve elliJche e criVografia 1. Un problema di triangoli 3. Cri5ografia elli7ca Pun6 razionali sulle coniche Sullla circonferenza x2+y2 = 1 Se x e y sono razionali anche t lo è. Consideriamo una curva ellittica del tipo y² = x³ + ax + b con i numeri a e b razionali. Intersechiamola con una retta di equazione y = mx + k (m, k razionali). Otteniamo l’equazione di terzo grado x³ – m²x² + (a – 2mk)x + b – k² = 0 Chiamiamo x₁ , x₂ e x₃ le soluzioni reali. Otteniamo la seguente fattorizzazione: x³ – m²x² + (a – 2mk)x + b – k² = (x – x₁)(x – x₂)(x – x₃) Svolgiamo il prodotto (x – x₁)(x – x₂)(x – x₃) = = x³ – (x₁ + x₂ + x₃)x² + (x₁x₂ +x₂x₃ +x₁x₃)x – x₁x₂x₃ Quindi se x₁ e x₂ sono razionali , anche x₃ sarà razionale. I punti possono essere strutturati come un gruppo additivo. 14 Formula algebrica per la SOMMA di PUNTI Lavoriamo sulla curva ellittica y² = x³ + 2x +1. Dati A(x₁, y₁), B(x₂, y₂) sulla curva, la retta per A, B in generale incontra la curva in un terzo punto C (x₃ ; y₃) di coordinate x₃ = (y2-y1/x2-x1 )² - x₁ - x₂ y₃ = (y2-y1 /x2-x1) (x₃ – x₁) + y₁ Ora sappiamo calcolare/disegnare A+B Formula per A+A Se abbiamo due punti coincidenti è come se avessimo un solo punto: basta considerare la tangente. Formule per avere le coordinate di 2A che chiamiamo x₃ ; y₃ conoscendo le coordinate x₁ , y₁ di A (m è il coeff. ang. della tg. a C in A): m = (3x₁² + a) / (2y₁) x₃ = m² – 2x₁ y₃ = -y₁ – m(x₃ - x₁) Si trova quindi 2A, 3A,…nA,… 31 A, 2A, 3A,…nA…? Si prosegue indefinitamente oppure ci si ferma perché si torna su se stessi (nel qual caso si dice che A è di ordine finito)? Un teorema (Nagell-Lutz) dice che in una cubica non singolare a coefficienti interi (razionali) se un punto P(x,y) a coordinate razionali è di ordine finito allora x, y sono interi, e: y=0 (ordine 2) oppure y divide il discriminante di f(x) dove y²= f(x) è l’equazione della curva. Discriminante D: Se f(x) = (x- x₁) (x - x₂) (x- x₃) è D = (x₁- x₂)² (x₁- x₃)² (x₂- x₃)² Discrimina se f(x) ha o meno radici coincidenti. NB. Il teorema di Nagell-Lutz non esprime una condizione necessaria e sufficiente: esistono punti a coordinata intera con y che divide D, che però non sono di ordine finito. Zero P+H = O A+O=O+A=A O+O=O O Zero O punto all’infinito della curva = sua intersezione con la retta all’infinito (x3 = 0) Multipli di un punto e agenzie di viaggio Per arrivare a K = 16P: - 15 salti: P + P = 2P ; 2P + P = 3P ecc. - 4 salti: P + P = 2P; 2P + 2P = 4P; 4P + 4P = 8P; 8P + 8P =16P. y2 = x3 – 9x +9 P(-‐8/9;109/27) (-‐0.88..;4.03..) Q=(1491/361;-‐44601/6859) = (4.13..;-‐6.50..) pari 1 Multipli di un punto e agenzie di viaggio (2) Dopo un viaggio lunghissimo (n molto grande) siamo arrivati a K = nP. Dopo qualche tempo vogliamo tornare indietro ma non ricordiamo n e ci rivolgiamo a un’agenzia di viaggi ellittici. Scopriamo che nessuna agenzia può darci la risposta: occorrerebbe un tempo enorme per calcolarla (problema del log discreto). 325 2 = ? (mod 7) 5 2 2 = 4 = 2 2 4 6 325 = 5 · 13 2 =22 =1 325 2 =2 5·5·13 2 5 13 5 5 13 5 13 = ((2 ) ) = ((4) ) 5 2 13 2 2 13 = ((2 ) ) = ((2 ) ) = ((2 ) ) = 4 13 (2 ) 13 = (2) = (2) (6+6+1) 6 6 = 2 ·2 ·2 = 2 Problemi vari su curve ell. in FNW (y2 = f(x) = x3 + ax2 + bx + c) del tipo y^2 = x^3 +bx + c; b, c interi, e punti P razionali. a) Se prendo una curva ellittica qualunque C, un punto P razionale qualunque appartenente alla curva e mi metto a viaggiare verso 2P , 3P , 4P ecc… , arriverò allo zero o vagherò nei secoli dei secoli ? E’ un problema che i matematici non hanno ancora risolto: trovare per quali curve ellittiche e per quali punti si arrivi o no allo 0 Problemi vari su curve ell. in FNW…(2) b) E se da un punto P si arriva allo zero, con quanti passi? c) Se parto da un singolo punto P razionale, si può arrivare a un qualunque altro punto razionale della curva? No, però vale il teor. di Mordell: il gruppo C (Q) (punti razionali di C) è finitamente generato. Quindi c’è in numero finito di punti raz.li P₁, P₂,…. Pk partendo dai quali si può raggiungere un qualunque altro punto raz.le della curva. Le curve ellittiche sono un campo aperto della ricerca matematica. Teorema di Mordell. (1923) Se una cubica non singolare nel piano ha un punto razionale, allora il gruppo dei punti razionali è finitamente generato. Congettura di Mordell. Sia C una curva razionale piana liscia di grado > 3. Allora l’insieme C(Q) dei punti razionali di C è finito. Dimostrata da Faltings nel 1983. Cubiche modulo p (in campi finiti Fp) y2 = x3 + ax2 + bx +c Tutti i calcoli sono fatti modulo p Tutti i punti sono razionali. 2 y = 3 x +x+4 1. Un problema di triangoli 2. Pun< razionali sulle curve elli7che Whi`ield Diffie e MarPn Hellman (1976) ()ﻃﺎﻫﺮ اﳉﻤﻞ ElGamal signature scheme à Digital Signature Algorithm (DSA) (1985) Neal Koblitz Victor S. Miller NK e VM indipendentemente suggerirono l’uso delle curve ellittiche in crittografia nel 1985 . Esse sono usate in larga scala dal 2004/5. Situazione tipo Alice: vuole mandare il testo in chiaro; lo cripta (testo cifrato) in modo che Eva non lo possa leggere. A. usa la chiave di criptazione. Bob usa la chiave di decrittazione per potere leggere il testo criptato. La chiave deve essere tenuta segreta per Eve. Il modello di Diffie-‐Hellman per lo scambio delle chiavi in cri5ografia elli7ca Le operazioni in verde si possono svolgere anche aVraverso un canale insicuro. Le operazioni in rosso sono segrete. La preparazione Alice e Bob si accordano su: -‐ un numero primo p -‐ una curva elliJca E: y2=x3+rx+s su Zp -‐ un punto P di E. Generazione delle chiavi pubbliche e private Alice genera un numero segreto a (chiave privata) e determina il punto A=aP (chiave pubblica) Bob genera un numero segreto b (chiave privata) e determina il punto B=bP (chiave pubblica) Scambio delle chiavi pubbliche Alice invia A a Bob Bob invia B ad Alice Costruzione parallela di una coppia di lucche7 iden<ci Alice determina il punto Q=aB Bob determina il punto QQ=bA Risulta Q=abP=baP=QQ Alice Bob La comunicazione segreta Bob cifra il messaggio M facendo la somma C=M+Q Bob invia C ad Alice Alice decifra il messaggio soCraendo a C il punto segreto Q: C-‐Q=M+Q-‐Q=M ESEMPIO Si lavora in Zp con p = 109+7 Sulla curva: y2=x3+17x+42 Modp Si sceglie un punto P sulla curva Alice e Bob scelgono le chiavi private a, b Bob cifra il messaggio “Si” (corto perché p è piccolo) Pari 2 ECDHE indicano uno scambio di chiavi con lo schema di Diffie-‐ Hellman (DHE) in un sistema di criVografia elliJca (EC). In un documento del NIST (NaPonal InsPtute of Standards and Technology) dal Ptolo Recommended EllipPc Curves for Federal Government Use sono elencaP i parametri che devono soddisfare le curve elliJche (in parPcolare se uPlizzate dal governo federale degli StaP UniP) e vengono suggerite delle curve. Aprendo una pagina google, il server scambia con il computer dell’utente una coppia di chiavi esaVamente come avviene tra Alice e Bob. La curva elliJca G uPlizzata da google (definita su Zp): p = 11579208921035624876269744694940757353008614341529 0314195533631308867097853951; r = Mod(1157920892103562487626974469494075735300861434 15290314195533631308867097853948,p); s = Mod(4105836372515214212932612978004726840911444101 5993725554835256314039467401291,p); G=ellinit([0,0,0,r,s]); y2 = x3 + rx +s Mod p Come mai si usano le curve ellittiche? Le CE forniscono cifrature di sicurezza equivalenti ai sistemi classici, ma usano meno bit. ECC Vs/ RSA L’idea di Sicurezza Globale di A.K. Lenstra Rompere una chiave a 228-bit RSA richiede l’energia necessaria per bollire un cucchiaino d’acqua. Arjen K. Lenstra Rompere una chiave a 228-bit EC richiede l’energia necessaria per bollire tutta l’acqua della Terra. Per ottenere questo livello di sicurezza con RSA occorrerebbero 2380-bit. Usi della ECC: - il governo USA per msg interni - il meccanismo di certificazione di possesso dei bitcoins - firme certificate nel servizio iMessage di Apple - navigazione sicura su Transport Layer Security (TLS) protocol e su Secure Sockets Layer (SSL) protocol - criptazione del DNS - CloudFlare garantisce la segretezza dell’invio di msg ECC come sistema di codifica sicuro? (5-09-2013) Dual EllipPc Curve DeterminisPc Random Bit GeneraPon Algorithm, approvato dal NIST nel 2006 La storia descritta mostra la notevole unità della matematica, a cominciare da argomenti semplici per finire in problemi di ricerca. Lungo la strada abbiamo incontrato un'idea fondamentale nella matematica moderna: l'idea di risolvere un problema riguardante un particolare tipo di oggetto (i triangoli con area 6 e perim. 12, per esempio) situando l'oggetto in uno spazio più generale (lo spazio di tutti i triangoli) e trovando il modo più conveniente per parametrizzarlo. Questo lavoro di modellizzazione ci ha permesso di entrare in un campo ricco di teorie e problemi matematici, che hanno anche importanti ricadute nelle applicazioni. Bibliografia Blake, I., Seroussi, G. and Smart, N., editors, (2005). Advances in Elliptic Curve Cryptography, London Mathematical Society 317, Cambridge University Press. Husemöller, D. (2004). Elliptic Curves. Second Edition. Springer: New York. Rosemberg, S., Spillane, M., & Wulf, D.B. (2008). Heron Triangles and Moduli Spaces, Mathematics Teacher, 1 (9). 656-663. Silverman, J.H., and Tate J. (1992). Rational Points on Elliptic Curves. Springer: New York. Washington, L. (2003). Elliptic Curves: Number Theory and Cryptography, Chapman & Hall / CRC. PariGP hVp://pari.math.u-‐bordeaux.fr/download.html Per mac: hVp://pari.math.u-‐bordeaux.fr/~pascal/ Esiste anche la versione Android, PariDroid: hVp://code.google.com/p/paridroid/wiki/ BuildingPariForAndroid Koblitz suggerisce di molPplicare c per 100 e sommare al prodoVo 100·∙c un numero casuale r di 2 cifre ripetendo il procedimento fino a trovare l’ascissa di un punto di E.