Parliamo un po' più a fondo di endomorfismi, vediamo da dove nascono i valori beta di cui ho parlato un paio di post sopra e cerchiamo così di entrare più a fondo nel mondo delle curve ellittiche (sempre privilegiando la nostra curva secp256k1).
ENDOMORFISMIUna mappa f: E -> E si dice un ENDOMORFISMO (endomorfismo di E sul campo Fp) se
1) manda il punto all'infinito di E nel punto all'infinito di E
2) f(P) = (g(P),h(P)) per tutti i punti P di E, dove g e h sono funzioni razionali (rapporto tra 2 polinomi) i cui coefficienti sono nel campo Fp.
In pratica facendo una serie di operazioni - g - sul punto P (cioè sulla sua x e sulla sua y) si ottiene la x di un nuovo punto, il punto f(P), analogamente facendo un'altra serie di operazioni - h - sulle coordinate x e y di P si ottiene la y di f(P).
Questa mappa quindi consente di passare da un punto P della curva a un punto f(P) sempre della curva, facendo alcune operazioni particolari sulle x e y di P.
Un esempio semplice di mappa che soddisfa il requisito 2) ma non 1) è la mappa che prende P qualsiasi e aggiunge a P sempre lo stesso punto, chiamiamolo G.
f : P --> P+G per ogni P di E
Questa mappa (una sorta di traslazione) è quella che viene usata in programmi tipo vanitygen per generare nella maniera più veloce possibile le chiavi pubbliche (tenendo traccia delle chiavi private, che vengono incrementate di 1 ad ogni iterazione).
Nell'ipotesi che P sia diverso da G e da O (punto all'infinito), questa mappa si compone delle seguenti due parti:
a) la x di f(P) = g(P) = ((yG - yP) / (xG -xP))^2 -xP -xG
b) la y di f(P) = h(P) = ((yG - yP) / (xG -xP)) * (xP - g(P)) - yP
ovvero la solita
formule di addizione.
Però questa mappa manda O in O+G = G, e quindi non rispetta il primo criterio e non è un endomorfismo. Vedremo invece che la mappa:
f : P --> k*P
che associa a ogni punto il suo prodotto per uno scalare k fissato è un endomorfismo.
Nel termine ENDOMORFISMO il prefisso ENDO significa INTERNO, il termine MORFISMO vuol dire che questa mappa rispetta la "forma" (struttura) algebrica di E, nel senso che sommare prima due punti in E e poi applicare la mappa f produce lo stesso risultato che applicare prima f ai due punti separatamente e poi sommare i risultati:
f(P1 + P2) = f(P1) + f(P2) per ogni P1, P2 in E.
Per fare un parallelo con un esempio più noto, la mappa
f : R -> R, f(x) = ln(x)
si chiama OMOMORFISMO nel senso che traduce la struttura algebrica (operazione) della moltiplicazione in una struttura algebrica analoga, dello stesso tipo, cioè nella addizione:
ln(a*b) = ln(a) + ln(b)
In R se vogliamo costruire un ENDOMORFISMO che rispetti l'operazione di addizione possiamo farlo così:
f : R -> R f(x) = k*x
k*(a+b) = k*a + k*b
(si noti il parallelismo con k*P delle curve ellittiche, dove k*(P1 + P2) = k*P1 + k*P2)
Nota: possono sembrare cose molto astratte, ma quanti sbagliano trattando la funzione x^2 o la funzione radice come fossero endomorfismi rispetto all'operazione di addizione!
(a + b)^2 = a^2 + b^2radice (a + b) = radice(a) + radice(b)mentre ovviamente x^2 e radice(x) sono endomorfismi solo rispetto all'operazione di moltiplicazione.
Torniamo alle curve ellittiche.Un endomorfismo f è una mappa da E a E che soddisfa certi requisiti, ovvero che manda punti di E in punti di E con l'unica avvertenza che il punto O va mandato nel punto O.
Si può verificare che un endomorfismo da E in E è sempre un omomorfismo di gruppo, ovvero che:
f(P1 + P2) = f(P1) + f(P2)
Esempi di endomorfismi da E in E1) la moltiplicazione per uno scalare k fissato
la mappa f: P --> k*P è endomorfismo di E, è immediato verificare infatti che k*(P1 + P2) = k*P1 + k*P2
casi particolari della mappa appena vista si hanno per k = 1 (identità) e k = -1 (la mappa negazione, quella che associa ad ogni punto P il suo opposto -P, nel qual caso f è definita come (x,y) --> (x,-y) ).
2) la mappa f: (x,y) --> (beta*x, y) dove beta è un elemento di ordine 3 di Fp (è una radice cubica di 1, questo si ha solo se p = 1 mod 3)
in quest'ultimo caso si ha quindi la possibilità di calcolare le coordinate di un nuovo punto in modo rapidissimo, con una sola moltiplicazione nel campo Fp. Se si applica 3 volte di seguito la mappa f appena descritta
P --> f(P) = P1 --> f(P1) = P2 --> f(P2) = P
(x,y) --> (beta*x, y) --> (beta^2*x, y) --> (beta^3*x,y) = (x,y)
si vede che si torna sempre al punto dal quale si era partiti. Quindi, ragionando senza le coordinate, si ha
P -> lambda * P -> lambda^2 * P -> lambda^3 * P = P dove lambda è uno scalare di Zn
ovvero che lambda è un elemento di ordine 3 di Fn. Sottolineiamo che, quando si passa da un elemento P a un elemento P1 = f(P), si può sempre scrivere P1 come k*P, poichè ogni punto P diverso dal punto all'infinito genera ogni altro elemento di E, ovvero ogni punto P1 è multiplo di ogni altro punto P, per un opportuno fattore k.
Quindi di fatto la mappa 2) è un caso particolare della mappa 1), dove m = lambda e i calcoli sulle coordinate risultano particolarmente semplici (g(P) = beta*x, h(P) = y)
Piccola osservazione: sia p - 1 che n - 1 sono multipli di 3:
p - 1 = 115792 089237 316195 423570 985008 687907 853269 984665 640564 039457 584007 908834 671662 (78 digits) = 2 × 3 × 7 × 13441 × 205115 282021 455665 897114 700593 932402 728804 164701 536103 180137 503955 397371 (72 digits)
n - 1 = 115792 089237 316195 423570 985008 687907 852837 564279 074904 382605 163141 518161 494336 (78 digits) = 26 × 3 × 149 × 631 × 107361 793816 595537 × 174 723607 534414 371449 × 341 948486 974166 000522 343609 283189 (33 digits)
Come si fanno a calcolare gli elementi beta e lambda (rispettivamente elementi di ordine 3 di Zp e di Zn)?
Basta prendere un elemento a caso di Zp (Zn) ed elevarlo alla (p-1)/3 ((n-1/3)), si otterrà sicuramente un elemento di ordine 3, se non è uguale a 1 otterremo una delle due radici non banali dell'unità che stiamo cercando:
>>> hex(pow(19,(p-1)/3,p)) #proviamo prima con 19^((p-1)/3)
'0x1L' #otteniamo 1, non va bene
>>> hex(pow(20,(p-1)/3,p)) #proviamo allora con 20^((p-1)/3)
'0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501eeL' --> ok, questo è beta
>>> hex(pow(24,(p-1)/3,p)) #facendo altri tentativi, alla fine otteniamo con 24^((p-1)/3)
'0x851695d49a83f8ef919bb86153cbcb16630fb68aed0a766a3ec693d68e6afa40L' --> questo lo chiamiamo beta2, poichè è = beta^2
>>> hex(pow(48,(n-1)/3,n))
'0x1L'
>>> hex(pow(49,(n-1)/3,n)) -->
'0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72L' --> abbiamo trovato lambda
>>> hex(pow(50,(n-1)/3,n))
'0xac9c52b33fa3cf1f5ad9e3fd77ed9ba4a880b9fc8ec739c2e0cfc810b51283ceL' --> abbiamo trovato lambda2 = lambda^2
Facciamo un rapido controllo che la seguente mappa :
f: P --> lambda*P
(x,y) --> (beta*x, y)
sia verificata per P = G:
from micro_ecdsa import mul
>>> Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
>>> Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
>>> lamb = 0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72
>>> (Rx,Ry) = mul(lamb,Gx,Gy) --> R = lambda * G
>>> hex(Rx)
'0xbcace2e99da01887ab0102b696902325872844067f15e98da7bba04400b88fcbL'
>>> hex(Ry)
'0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8L' --> da notare che Ry = Gy !!!
>>> beta = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee
>>> hex((beta*Gx) % p)
'0xbcace2e99da01887ab0102b696902325872844067f15e98da7bba04400b88fcbL' --> beta * Gx = Rx !!!
