La multiplicació escalar de corbes el·líptiques és l'operació d'afegir successivament un punt al llarg d'una corba el·líptica a si mateix repetidament. S'utilitza en criptografia de corbes el·líptiques (ECC). La literatura presenta aquesta operació com a multiplicació escalar, escrita en forma hessiana d'una corba el·líptica. Un nom generalitzat per a aquesta operació també és multiplicació de punts de corbes el·líptiques, però això pot donar la impressió errònia de ser una multiplicació entre dos punts.
Conceptes bàsics Donada una corba, E, definida per alguna equació en un cos finit (com ara E: ), la multiplicació de punts es defineix com l'addició repetida d'un punt al llarg d'aquesta corba. Denotem com per a algun escalar (enter) n i un punt que es troba sobre la corba, E. Aquest tipus de corba es coneix com a corba de Weierstrass.miniatura|Corba cúbica de Weierstrass relacionada amb les funcions el·líptiques de Dixon. Corba cúbica de Weierstrass y2 = 4x3 – 1/27 relacionada amb les funcions el·líptiques w:Dixon. Representada amb Desmos.
La seguretat de l'ECC moderna depèn de la dificultat de determinar n a partir de
donats valors coneguts de Q i P si n és gran (conegut com el problema del logaritme discret de la corba el·líptica per analogia amb altres sistemes criptogràfics). Això es deu al fet que l'addició de dos punts en una corba el·líptica (o l'addició d'un punt a si mateix) produeix un tercer punt a la corba el·líptica la ubicació del qual no té una relació immediatament òbvia amb les ubicacions dels dos primers, i repetir això moltes vegades produeix un punt nP que pot ser essencialment a qualsevol lloc. Intuïtivament, això no és diferent del fet que si tinguéssiu un punt P en un cercle, afegir 42,57 graus al seu angle encara pot ser un punt "no massa lluny" de P, però afegir 1000 o 1001 vegades 42,57 graus produirà un punt que requereix un càlcul una mica més complex per trobar l'angle original. Invertir aquest procés, és a dir, donat Q = nP i P, i determinar n, només es pot fer provant tots els n possibles, un esforç que és computacionalment intractable si n és gran.
Operacions puntuals miniatura|600x600px|Operacions amb punts de corba el·líptica: suma (mostrada a la faceta 1), duplicació (facetes 2 i 4) i negació (faceta 3). Hi ha tres operacions definides habitualment per a punts de corbes el·líptiques: suma, duplicació i negació.
Punt a l'infinit Punt a l'O és l'element identitat de l'aritmètica de corbes el·líptiques. Si el sumem a qualsevol punt, tenim aquest altre punt, inclosa la suma d'un punt a l'infinit a si mateix. És a dir:
El punt a l'infinit també s'escriu com a .
Negació de punts La negació de punts és trobar un punt tal que, sumant-lo a si mateix, donarà com a resultat un punt a l'infinit (O)
Per a corbes el·líptiques de la forma E : , la negació és un punt amb la mateixa coordenada x però amb la coordenada y negada:
Suma de punts Amb 2 punts diferents, P i Q, l'addició es defineix com la negació del punt resultant de la intersecció de la corba E i la recta definida pels punts P i Q, donant el punt R.
Suposant que la corba el·líptica, E, ve donada per , això es pot calcular com:
Aquestes equacions són correctes quan cap dels dos punts és el punt de l'infinit, O, i si els punts tenen coordenades x diferents (no són inverses mútues). Això és important per a l'algoritme de verificació ECDSA on el valor hash podria ser zero.
Duplicació de punts On els punts P i Q coincideixen (a les mateixes coordenades), la suma és similar, excepte que no hi ha cap línia recta ben definida que passi per P, de manera que l'operació es tanca utilitzant un cas límit, la tangent a la corba, E, a P.
Això es calcula com s'ha indicat anteriorment, prenent les derivades (dE/dx)/(dE/dy):
on a prové de l'equació que defineix la corba, E, anterior.
Multiplicació de punts La manera més senzilla de calcular una multiplicació de punts és mitjançant la suma repetida. Tanmateix, hi ha mètodes més eficients per calcular la multiplicació.
Doblar i sumar El mètode més senzill és el mètode de doble suma, similar al mètode de multiplicar al quadrat en l'exponenciació modular. L'algoritme funciona de la següent manera:
Per calcular sP, comenceu amb la representació binària de s: , on
Algorisme iteratiu, índex creixent:
let bits = bit_representation(s) # the vector of bits (from LSB to MSB) representing s
let res = # point at infinity
let temp = P # track doubled P val
for bit in bits:
if bit == 1:
res = res + temp # point add
temp = temp + temp # double
return res
Iterative algorithm, index decreasing:
let bits = bit_representation(s) # the vector of bits (from LSB to MSB) representing s
let i = length(bits) - 2
let res = P
while (i >= 0): # traversing from second MSB to LSB
res = res + res # double
if bits[i] == 1:
res = res + P # add
i = i - 1
return res
Tingueu en compte que els dos mètodes iteratius anteriors són vulnerables a l'anàlisi temporal. Vegeu l'Escala de Montgomery a continuació per a un enfocament alternatiu.
Recursive algorithm: algorithm f(P, d) is
if d = 0 then
return 0 # computation complete
else
if d = 1 then
return P
else if d mod 2 = 1 then
return point_add(P, f(P, d - 1)) # addition when d is odd
else
return f(point_double(P), d / 2) # doubling when d is evenon f és la funció per multiplicar, P és la coordenada a multiplicar, d és el nombre de vegades que s'ha de sumar la coordenada a si mateixa. Exemple: 100P es pot escriure com i, per tant, requereix sis operacions de doble punt i dues operacions de suma de punts. 100P seria igual a f(P, 100).
Aquest algorisme requereix iteracions logarítmiques de logaritme 2 ( d) de duplicació i suma de punts per calcular la multiplicació completa de punts. Hi ha moltes variacions d'aquest algorisme, com ara l'ús d'una finestra, una finestra lliscant, NAF, NAF-w, cadenes vectorials i una escala de Montgomery.
Mètode de finestra En la versió amb finestra d'aquest algorisme, es selecciona una mida de finestra w i es calcula tot valors de per . L'algoritme ara utilitza la representació i esdevéQ ← 0
for i from m to 0
do Q ← point_double_repeat(Q, w)
if di > 0 then
Q ← point_add(Q, diP) # using pre-computed value of diP
return QAquest algorisme té la mateixa complexitat que l'enfocament de doble i suma amb l'avantatge d'utilitzar menys addicions de punts (que a la pràctica són més lentes que duplicar). Normalment, el valor de w es tria perquè sigui bastant petit, cosa que fa que l'etapa de precomputació sigui un component trivial de l'algorisme. Per a les corbes recomanades pel NIST, sol ser la millor selecció. La complexitat total d'un nombre de n bits es mesura com punts dobles i addicions de punts.
Mètode de finestra corredissa A la versió de finestra lliscant, busquem compensar les addicions de punts per punts dobles. Calculem una taula similar a la de la versió amb finestra, excepte que només calculem els punts per . Efectivament, només calculem els valors per als quals s'estableix el bit més significatiu de la finestra. L'algoritme utilitza llavors la representació original de suma doble de .
Q ← 0for i from m downto 0
do
if di = 0 then
Q ← point_double(Q)
else
t ← extract j (up to w − 1) additional bits from d (including di)
i ← i − j
if j < w then Perform double-and-add using t
return Q
else
Q ← point_double_repeat(Q, w)
Q ← point_add(Q, tP)
return QAquest algoritme té l'avantatge que la fase de precomputació és aproximadament la meitat de complexa que el mètode de finestra normal, alhora que intercanvia addicions de punts més lentes per duplicacions de punts. De fet, hi ha poques raons per utilitzar el mètode de finestra en lloc d'aquest enfocament, excepte que el primer es pot implementar en temps constant. L'algoritme requereix punts dobles i com a màxim addicions de punts.
Mètode de forma no adjacent w-ary (wNAF) En la forma no adjacent, pretenem aprofitar el fet que la subtracció de punts és tan fàcil com la suma de punts per realitzar menys operacions (de qualsevol dels dos) en comparació amb un mètode de finestra lliscant. La NAF del multiplicand s'ha de calcular primer amb el següent algorisme
i ← 0while (d > 0) do
if (d mod 2) = 1 then
di ← d mods 2w
d ← d − di
else
di = 0 d ← d/2 i ← i + 1
return (di−1, di-2,..., d0)
On la funció mòdul amb signe mods es defineix com
if (d mod 2w) >= 2w−1
return (d mod 2w) − 2w
else
return d mod 2wAixò produeix la NAF necessària per realitzar ara la multiplicació. Aquest algorisme requereix el càlcul previ dels punts i els seus aspectes negatius, on és el punt que s'ha de multiplicar. En les corbes típiques de Weierstrass, si llavors Així doncs, en essència, els negatius són barats de calcular. A continuació, l'algoritme següent calcula la multiplicació :
Q ← 0for j ← i − 1 downto 0
do
Q ← point_double(Q)
if (dj != 0)
Q ← point_add(Q, djP)
return QEl wNAF garanteix que, de mitjana, hi haurà una densitat de addicions de punts (lleugerament millor que la finestra sense signe). Requereix duplicar 1 punt i addicions de punts per a la precomputació. L'algoritme requereix llavors duplicacions de punts i sumes de punts per a la resta de la multiplicació.
Una propietat de la NAF és que tenim garantit que cada element diferent de zero és seguit per almenys zeros addicionals. La raó és que l'algoritme elimina els zeros inferiors trossos de amb cada subtracció de la sortida de la funció mods. Aquesta observació es pot utilitzar per a diversos propòsits. Després de cada element diferent de zero, els zeros addicionals poden estar implícits i no cal emmagatzemar-los. En segon lloc, les divisions serials múltiples per 2 es poden substituir per una divisió per després de cada valor diferent de zero element i dividir per 2 després de cada zero.
S'ha demostrat que mitjançant l'aplicació d'un atac de canal lateral FLUSH+RELOAD a OpenSSL, es pot revelar la clau privada completa després de realitzar la sincronització de la memòria cau contra tan sols 200 signatures realitzades.
Escala de Montgomery L'enfocament de l'escala de Montgomery calcula la multiplicació de punts en un nombre fix d'operacions. Això pot ser beneficiós quan el temps, el consum d'energia o les mesures de branca s'exposen a un atacant que realitza un atac de canal lateral. L'algoritme utilitza la mateixa representació que a la suma i el doble.
R0 ← 0 R1 ← Pfor i from m downto 0
do if di = 0 then
R1 ← point_add(R0, R1)
R0 ← point_double(R0)
else
R0 ← point_add(R0, R1)
R1 ← point_double(R1) // invariant property to maintain correctness
assert R1 == point_add(R0, P)
return R0Aquest algorisme té en efecte la mateixa velocitat que l'enfocament de doble i suma, excepte que calcula el mateix nombre d'addicions de punts i dobles independentment del valor del multiplicand d. Això significa que a aquest nivell l'algorisme no filtra cap informació a través de les ramificacions o el consum d'energia.
Tanmateix, s'ha demostrat que mitjançant l'aplicació d'un atac de canal lateral FLUSH+RELOAD a OpenSSL, es pot revelar la clau privada completa després de realitzar la sincronització de la memòria cau contra només una signatura a un cost molt baix.
Cadenes més llargues L'ús de cadenes de Lucas proporciona una seqüència optimitzada de duplicació i sumes en comparació amb l'escala de Montgomery, que és més ràpida en múltiples més grans (cadenes més llargues). Aquest mètode s'anomena "PRAC". Montgomery també publica PRAC, i la "implementació de referència" és GMP-ECM. HAL DJ Bernstein esmenta diversos esquemes d'aquest tipus el 2017.: § 4.8.2
Escala de Montgomery a temps constant