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.