¿Cómo se ven las curvas elípticas en campos finitos?
Es fácil visualizar curvas elípticas suaves, pero ¿cómo se ven las curvas elípticas sobre un campo finito?
El siguiente es un gráfico de
Debido a que solo permitimos entradas enteras (más específicamente, elementos de campos finitos), no vamos a obtener un gráfico suave.
No todos los valores de darán como resultado un número entero para el valor de cuando resolvemos la ecuación, por lo que no habrá ningún punto presente en ese valor de . Puedes ver tales vacíos en el gráfico de arriba.
El código para generar este gráfico se proporcionará más adelante.
El número primo cambia el gráfico dramáticamente
Aquí hay algunos gráficos de realizados sobre módulo 11, 23, 31 y 41 respectivamente. Cuanto mayor es el módulo, más puntos contiene y más complejo parece ser el gráfico.
Establecimos en el artículo anterior que los puntos de la curva elíptica con la operación de “conectar y voltear” forman un grupo. Cuando hacemos esto sobre un campo finito, sigue siendo un grupo, pero se convierte en un grupo cíclico, lo cual es tremendamente útil para nuestra aplicación. Por qué es cíclico lamentablemente requerirá matemáticas muy complejas, así que por ahora solo tendrás que aceptarlo. Pero esto no debería ser demasiado sorprendente. Tenemos un número finito de puntos, por lo que generar cada punto al realizar debería parecer al menos plausible.
En la aplicación de la criptografía, necesita ser grande. En la práctica, es de más de 200 bits. Retomaremos esto en una sección posterior.
Contexto
Elemento de campo
Vamos a decir “elemento de campo” muchas veces en este artículo, y con suerte, gracias a nuestros tutoriales anteriores (especialmente sobre campos finitos) ya te sientes cómodo con ese término. Pero si no, es un número entero positivo que está dentro de una operación de módulo.
Es decir, si hacemos sumas en módulo 11, entonces los elementos del campo finito de ese conjunto son . No es correcto decir “enteros” aunque ese sea el tipo de datos que usaremos en nuestros ejemplos en Python. No se puede tener un elemento de campo negativo (aunque los enteros puedan ser negativos) al hacer sumas módulo un número primo. Un número “negativo” en un campo finito es simplemente el inverso aditivo de otro número, es decir, un número que al sumarse da como resultado cero. Por ejemplo, en un campo finito de módulo 11, el 4 puede ser considerado “-7” porque es , en un sentido comparativo a cómo 7 + (-7) es cero para los números regulares.
Sobre el campo de los números racionales, la multiplicación tiene el elemento de identidad 1, y el inverso de un número es simplemente el numerador y el denominador intercambiados. Por ejemplo, 500/303 es el inverso de 303/500 porque si los multiplicas, obtienes 1.
En un campo finito, el inverso de un elemento es el número por el que lo multiplicas para obtener el elemento de campo finito 1. Por ejemplo, en módulo 23, el 6 es el inverso del 4 porque cuando los multiplicas entre sí en módulo 23, obtienes 1. Cuando el orden del campo es primo, todos los números excepto el cero tienen un inverso.
Grupos cíclicos
Un grupo cíclico es un grupo en el que cada elemento se puede calcular comenzando con un elemento generador y aplicando repetidamente el operador binario del grupo.
Un ejemplo muy simple son los enteros módulo 11 bajo la suma. Si tu generador es 1, y sigues sumando el generador a sí mismo, puedes generar todos los elementos del grupo del 0 al 10.
Decir que los puntos de una curva elíptica forman un grupo cíclico (bajo la suma de curvas elípticas) significa que podemos representar cada número de un campo finito como un punto de la curva elíptica y sumarlos tal como lo haríamos con enteros regulares en un campo finito.
Es decir,
es homomórfico a
Donde G es el generador del grupo cíclico de la curva elíptica.
Esto solo es cierto para las curvas elípticas sobre campos finitos que tienen un número primo de puntos, que son los tipos de curvas que usamos en la práctica. Esto es algo que retomaremos más adelante.
Fórmula BN128
La curva BN128, que es utilizada por los precompilados de Ethereum para verificar pruebas ZK, se especifica de la siguiente manera:
Aquí es el módulo del campo.
El field_modulus no debe confundirse con el orden de la curva, que es el número de puntos en la curva.
Para la curva bn128, el orden de la curva es el siguiente:
from py_ecc.bn128 import curve_order
# 21888242871839275222246405745257275088548364400416034343698204186575808495617
print(curve_order)
El módulo del campo es muy grande, lo que hace que experimentar con él sea poco práctico. En la siguiente sección, desarrollaremos una intuición sobre los puntos de la curva elíptica en campos finitos usando la misma fórmula, pero con un módulo más pequeño.
Generación del grupo cíclico de la curva elíptica
Para resolver la ecuación anterior, y determinar qué puntos están en la curva, necesitaremos calcular .
Raíces cuadradas modulares
Utilizamos el Tonelli Shanks Algorithm para calcular las raíces cuadradas modulares. Puedes leer sobre cómo funciona el algoritmo si tienes curiosidad, pero por ahora puedes tratarlo como una caja negra que calcula la raíz cuadrada matemática de un elemento de campo sobre un módulo, o te informa si la raíz cuadrada no existe.
Por ejemplo, la raíz cuadrada de 5 módulo 11 es 4 , pero no hay raíz cuadrada de 6 módulo 11. (Se anima al lector a descubrir que esto es cierto mediante fuerza bruta).
Las raíces cuadradas a menudo tienen dos soluciones, una positiva y otra negativa. Aunque no tenemos números con signo negativo en un campo finito, todavía tenemos una noción de “números negativos” en el sentido de tener un inverso.
Puedes encontrar código en línea para implementar el algoritmo descrito anteriormente, pero para evitar poner grandes fragmentos de código en este tutorial, instalaremos una biblioteca de Python en su lugar.
python3 -m pip install libnum
Después de instalar libnum, podemos ejecutar el siguiente código para demostrar su uso.
from libnum import has_sqrtmod_prime_power, sqrtmod_prime_power
# the functions take arguments# has_sqrtmod_prime_power(n, field_mod, k), where n**k,
# but we aren't interested in powers in modular fields, so we set k = 1
# check if sqrt(8) mod 11 exists
print(has_sqrtmod_prime_power(8, 11, 1))
# False
# check if sqrt(5) mod 11 exists
print(has_sqrtmod_prime_power(5, 11, 1))
# True
# compute sqrt(5) mod 11
print(list(sqrtmod_prime_power(5, 11, 1)))
# [4, 7]
assert (4 ** 2) % 11 == 5
assert (7 ** 2) % 11 == 5
# we expect 4 and 7 to be additive inverses of each other, because in "regular" math, the two solutions to a square root are sqrt and -sqrt
assert (4 + 7) % 11 == 0
Ahora que sabemos cómo calcular raíces cuadradas modulares, podemos iterar a través de los valores de y calcular usando la fórmula . Despejar es solo cuestión de tomar la raíz cuadrada modular en ambos lados (si existe) y guardar los pares resultantes para poder graficarlos más tarde.
Creemos un gráfico simple de una curva elíptica
import libnum
import matplotlib.pyplot as plt
def generate_points(mod):
xs = []
ys = []
def y_squared(x):
return (x**3 + 3) % mod
for x in range(0, mod):
if libnum.has_sqrtmod_prime_power(y_squared(x), mod, 1):
square_roots = libnum.sqrtmod_prime_power(y_squared(x), mod, 1)
# we might have two solutions
for sr in square_roots:
ys.append(sr)
xs.append(x)
return xs, ys
xs, ys = generate_points(11)
fig, (ax1) = plt.subplots(1, 1);
fig.suptitle('y^2 = x^3 + 3 (mod p)');
fig.set_size_inches(6, 6);
ax1.set_xticks(range(0,11));
ax1.set_yticks(range(0,11));
plt.grid()
plt.scatter(xs, ys)
plt.plot();
El resultado del gráfico se muestra a continuación:
Algunas observaciones:
- No habrá ningún valor de x o y mayor o igual al módulo que utilicemos
- Al igual que el gráfico de valores reales, el modular “parece simétrico”
Suma de puntos en curvas elípticas
Aún más interesante, nuestra operación de “conectar los puntos y voltear” para calcular curvas elípticas ¡sigue funcionando!
Pero dado que estamos haciendo esto sobre un campo finito, no debería ser sorprendente. Nuestras fórmulas sobre números reales usan las operaciones normales de campo de suma y multiplicación. Aunque usamos raíces cuadradas para determinar si un punto está en la curva, y las raíces cuadradas no son un operador de campo válido, no usamos raíces cuadradas para calcular la suma y la duplicación de puntos.
El lector puede verificar esto eligiendo dos puntos de los gráficos anteriores, luego introduciéndolos en el código de abajo para sumar puntos y ver que siempre caen en otro punto (o en el punto en el infinito si los puntos son inversos entre sí). Estas fórmulas se extraen de la página de Wikipedia sobre la multiplicación de puntos en curvas elípticas.
def double(x, y, a, p):
lambd = (((3 * x**2 + a) % p ) * pow(2 * y, -1, p)) % p
newx = (lambd**2 - 2 * x) % p
newy = (-lambd * newx + lambd * x - y) % p
return (newx, newy)
def add_points(xq, yq, xp, yp, p, a=0):
if xq == yq == None:
return xp, yp
if xp == yp == None:
return xq, yq
assert (xq**3 + 3) % p == (yq ** 2) % p, "q not on curve"
assert (xp**3 + 3) % p == (yp ** 2) % p, "p not on curve"
if xq == xp and yq == yp:
return double(xq, yq, a, p)
elif xq == xp:
return None, None
lambd = ((yq - yp) * pow((xq - xp), -1, p) ) % p
xr = (lambd**2 - xp - xq) % p
yr = (lambd*(xp - xr) - yp) % p
return xr, yr
Aquí hay algunas visualizaciones de cómo se ve “conectar y voltear” en un campo finito:
Cada punto de la curva elíptica en un grupo cíclico tiene un “número”
Un grupo cíclico, por definición, puede generarse sumando repetidamente el generador a sí mismo.
Usemos un ejemplo real de siendo el punto generador .
Usando las funciones de Python de arriba, podemos comenzar con el punto y generar cada punto del grupo:
# for our purposes, (4, 10) is the generator point G
next_x, next_y = 4, 10
print(0, 4, 10)
points = [(next_x, next_y)]
for i in range(1, 13):
# repeatedly add G to the next point to generate all the elements
next_x, next_y = add_points(next_x, next_y, 4, 10, 11)
print(i, next_x, next_y)
points.append((next_x, next_y))
La salida será
0 4 10
1 7 7
2 1 9
3 0 6
4 8 8
5 2 0
6 8 3
7 0 5
8 1 2
9 7 4
10 4 1
11 None None
12 4 10 # note that this is the same point as the first one
Observa que . Al igual que la suma modular, cuando nos “desbordamos”, el ciclo vuelve a empezar.
Aquí, None significa el punto en el infinito, que de hecho es parte del grupo. Sumar el punto en el infinito al generador devuelve el generador, ya que así es como se supone que debe comportarse el elemento de identidad.
Podemos asignar a cada punto un “número” basado en la cantidad de veces que sumamos el generador a sí mismo para llegar a ese punto.
Podemos usar el siguiente código para graficar la curva y asignar un número junto a ella
xs11, ys11 = generate_points(11)
fig, (ax1) = plt.subplots(1, 1);
fig.suptitle('y^2 = x^3 + 3 (mod 11)');
fig.set_size_inches(13, 6);
ax1.set_title("modulo 11")
ax1.scatter(xs11, ys11, marker='o');
ax1.set_xticks(range(0,11));
ax1.set_yticks(range(0,11));
ax1.grid()
for i in range(0, 11):
plt.annotate(str(i+1), (points[i][0] + 0.1, points[i][1]), color="red");
El texto rojo se puede interpretar como comenzar con el elemento de identidad, y cuántas veces le sumamos el generador.
Los inversos de los puntos siguen siendo verticalmente simétricos
Aquí hay una observación interesante: nota que los puntos que comparten el mismo valor de x suman 12, lo que corresponde al elemento de identidad . Si sumamos el punto , que es el punto 11 en nuestro gráfico, con , obtendremos el punto en el infinito, que sería el duodécimo elemento del grupo.
El orden no es el módulo
En este ejemplo, el orden del grupo es 12 (número total de puntos de la curva elíptica en nuestro grupo), a pesar de que la fórmula para la curva elíptica es módulo 11. Esto se enfatizará varias veces, pero NO debes asumir que el módulo en la curva elíptica es el orden del grupo. Sin embargo, puedes estimar el rango del orden de la curva a partir del módulo del campo mismo usando Hasse’s Theorem.
Si el número de puntos es primo, entonces la suma de puntos se comporta como un campo finito
En el gráfico de arriba, hay 12 puntos (incluyendo el 0). La suma módulo 12 no es un campo finito porque 12 no es primo.
Sin embargo, si elegimos los parámetros de la curva cuidadosamente, podemos crear una curva elíptica donde los puntos correspondan a elementos en un campo finito. Es decir, el orden de la curva es igual al orden del campo finito.
Por ejemplo, crea una curva con 31 puntos en total, como se puede ver en el gráfico a continuación:
Cuando el orden de la curva coincide con el orden del campo finito cada operación que haces en el campo finito tiene un equivalente homomórfico en la curva elíptica.
Para ir de un campo finito a una curva elíptica, elegimos un punto (arbitrariamente) para que sea el generador, luego multiplicamos el elemento en el campo finito por el generador.
La multiplicación es en realidad una suma repetida
No existe tal cosa como la multiplicación de puntos en curvas elípticas. Cuando decimos “multiplicación escalar”, en realidad nos referimos a sumas repetidas. No puedes tomar dos puntos de una curva elíptica y multiplicarlos entre sí (bueno, en cierto modo puedes con los bilinear pairings, pero eso es algo que veremos más adelante).
Cuando usamos la biblioteca de Python para hacer multiply(G1, x), en realidad es lo mismo que G1 + G1 + … + G1 x veces. Internamente, no nos auto-sumamos tantas veces; usamos algunos atajos inteligentes con la duplicación de puntos para completar la operación en tiempo logarítmico.
Por ejemplo, si quisiéramos calcular 135G, en realidad calcularíamos eficientemente los siguientes valores usando la duplicación de puntos, los almacenaríamos en caché,
G, 2G, 4G, 8G, 16G, 32G, 64G, 128G
…y luego sumaríamos 128G + 4G + 2G + G = 135G.
Cuando decimos 5G + 6G = 11G, esencialmente solo estamos sumando G a sí mismo 11 veces. Usando el atajo ilustrado anteriormente, podemos calcular 11G con un número logarítmico de cálculos, pero al final del día, es solo una suma repetida.
Biblioteca bn128 de Python
La biblioteca que la implementación pyEVM de la EVM usa para los precompilados de curva elíptica es py_ecc, y dependeremos en gran medida de esa biblioteca. El código a continuación muestra cómo se ve el punto generador, y también muestra algo de suma y multiplicación escalar.
Así es como se ve un punto G1:
from py_ecc.bn128 import G1, multiply, add, eq, neg
print(G1)
# (1, 2)
print(add(G1, G1))
# (1368015179489954701390400359078579693043519447331113978918064868415326638035, 9918110051302171585080402603319702774565515993150576347155970296011118125764)
print(multiply(G1, 2))
#(1368015179489954701390400359078579693043519447331113978918064868415326638035, 9918110051302171585080402603319702774565515993150576347155970296011118125764)
# 10G + 11G = 21G
assert eq(add(multiply(G1, 10), multiply(G1, 11)), multiply(G1, 21))
Aunque los números son grandes y difíciles de leer, podemos ver que sumar un punto a sí mismo resulta en el mismo valor que “multiplicar” un punto por 2. Los dos puntos de arriba son claramente el mismo punto. La tupla sigue siendo un par , solo que sobre un dominio muy grande.
El número impreso arriba es enorme por una razón. No queremos que los atacantes puedan tomar un punto de una curva elíptica y calcular el elemento de campo que lo generó. Si el orden de nuestro grupo cíclico es demasiado pequeño, entonces el atacante simplemente puede forzarlo por fuerza bruta.
Aquí hay un gráfico de los primeros 1000 puntos:
Y este es el código para generar el gráfico anterior:
import matplotlib.pyplot as plt
from py_ecc.bn128 import G1, multiply, neg
import math
import numpy as np
xs = []
ys = []
for i in range(1,1000):
xs.append(i)
ys.append(int(multiply(G1, i)[1]))
xs.append(i)
ys.append(int(neg(multiply(G1, i))[1]))
plt.scatter(xs, ys, marker='.')
Esto puede parecer intimidante, pero la única diferencia con lo que hicimos en la sección anterior es que se usa un módulo mucho más grande y un punto diferente para el generador.
Suma en la biblioteca
La biblioteca py_ecc hace que la suma de puntos sea conveniente para nosotros, y la sintaxis debería explicarse por sí sola:
from py_ecc.bn128 import G1, multiply, add, eq
# 5 = 2 + 3
assert eq(multiply(G1, 5), add(multiply(G1, 2), multiply(G1, 3)));
La suma en un campo finito es homomórfica a la suma entre puntos de una curva elíptica (cuando su orden es igual). Debido al logaritmo discreto, otra parte puede sumar puntos de la curva elíptica sin saber qué elementos del campo generaron esos puntos.
Llegados a este punto, con suerte el lector tiene una buena intuición para sumar puntos de curvas elípticas, tanto teórica como prácticamente, porque los algoritmos modernos de conocimiento cero dependen enormemente de esto.
Detalle de implementación sobre el homomorfismo entre la suma modular y la suma en curvas elípticas
Necesitamos hacer una cuidadosa distinción entre terminologías aquí:
El módulo del campo es el módulo sobre el que hacemos la curva. El orden de la curva es el número de puntos en la curva.
Si comienzas con un punto y sumas el orden de la curva , obtendrás de vuelta. Si sumas el módulo del campo, obtendrás un punto diferente.
from py_ecc.bn128 import curve_order, field_modulus, G1, multiply, eq
x = 5 # chosen randomly
# This passes
assert eq(multiply(G1, x), multiply(G1, x + curve_order))
# This fails
assert eq(multiply(G1, x), multiply(G1, x + field_modulus))
La implicación de esto es que (x + y) mod curve_order == xG + yG.
x = 2 ** 300 + 21
y = 3 ** 50 + 11
# (x + y) == xG + yG
assert eq(multiply(G1, (x + y)), add(multiply(G1, x), multiply(G1, y)))
A pesar de que la operación x + y claramente se “desbordará” por encima del orden de la curva, esto no importa. Al igual que en un campo finito, este es el comportamiento que esperamos. La multiplicación en curvas elípticas ejecuta implícitamente la misma operación que tomar el módulo antes de realizar la multiplicación.
De hecho, ni siquiera necesitamos hacer el módulo si solo nos importan los números positivos, la siguiente identidad también se cumple:
x = 2 ** 300 + 21
y = 3 ** 50 + 11
assert eq(multiply(G1, (x + y) % curve_order), add(multiply(G1, x), multiply(G1, y)))
Sin embargo, si hacemos las matemáticas finitas con el módulo del número incorrecto (algún número distinto del orden de la curva), la igualdad se romperá si nos “desbordamos”
x = 2 ** 300 + 21
y = 3 ** 50 + 11 # these values are large enough to overflow:
assert eq(multiply(G1, (x + y) % (curve_order - 1)), add(multiply(G1, x), multiply(G1, y))), "this breaks"
Codificando números racionales
Cuando aplicamos el módulo, somos capaces de codificar un concepto de división.
Por ejemplo, no podemos hacer lo siguiente usando enteros regulares.
# this throws an exception
eq(add(multiply(G1, 5 / 2), multiply(G1, 1 / 2), multiply(G1, 3)
Sin embargo, en un campo finito, 1/2 se puede calcular de forma significativa como el inverso multiplicativo de 2. Por lo tanto, 5 / 2 se puede codificar como .
Así es como podemos hacerlo en Python:
five_over_two = (5 * pow(2, -1, curve_order)) % curve_order
one_half = pow(2, -1, curve_order)
# Essentially 5/2 = 2.5# 2.5 + 0.5 = 3
# but we are doing this in a finite field
assert eq(add(multiply(G1, five_over_two), multiply(G1, one_half)), multiply(G1, 3))
Asociatividad
Sabemos que los grupos son asociativos, por lo que esperamos que la siguiente identidad sea cierta en general:
x = 5
y = 10
z = 15
lhs = add(add(multiply(G1, x), multiply(G1, y)), multiply(G1, z))
rhs = add(multiply(G1, x), add(multiply(G1, y), multiply(G1, z)))
assert eq(lhs, rhs)
Se anima al lector a probar diferentes valores de x, y y z por su cuenta.
Cada elemento tiene un inverso
La biblioteca py_ecc nos proporciona la función neg que nos dará el inverso de un elemento dado volteándolo sobre el eje x (en un campo finito). La biblioteca codifica el “punto en el infinito” como un None de Python.
from py_ecc.bn128 import G1, multiply, neg, is_inf, Z1
# pick a field element
x = 12345678
# generate the point
p = multiply(G1, x)
# invert
p_inv = neg(p)
# every element added to its inverse produces the identity element assert is_inf(add(p, p_inv))
# Z1 is just None, which is the point at infinity
assert Z1 is None
# special case: the inverse of the identity is itself
assert eq(neg(Z1), Z1)
Al igual que en el caso de las curvas elípticas sobre números reales, el inverso de un punto de la curva elíptica tiene el mismo valor de x, pero el valor de y es el inverso.
from py_ecc.bn128 import G1, neg, multiply
field_modulus = 21888242871839275222246405745257275088696311157297823662689037894645226208583
for i in range(1, 4):
point = multiply(G1, i)
print(point)
print(neg(point))
print('----')
# x values are the same
assert int(point[0]) == int(neg(point)[0])
# y values are inverses of each other, we are adding y values
# not ec points
assert int(point[1]) + int(neg(point)[1]) == field_modulus
Cada elemento puede ser generado por un generador
Cuando tratamos con más de puntos, no es posible verificar esto mediante fuerza bruta. Sin embargo, considera el hecho de que eq(multiply(G1, x), multiply(G1, x + order)) es siempre cierto. Eso significa que podemos generar hasta el orden de puntos, para luego reiniciar el ciclo donde comenzó.
¿Qué pasa con optimized_bn128?
Examinando la biblioteca, verás una implementación llamada optimized_bn128. Si mides el tiempo de ejecución, notarás que esta versión se ejecuta mucho más rápido y es la implementación utilizada por pyEvm. Sin embargo, para fines educativos es preferible usar la versión no optimizada, ya que estructura los puntos de una manera más intuitiva (la tupla habitual x, y). La versión optimizada estructura los puntos de la curva elíptica como tuplas de 3 elementos, que son más difíciles de interpretar.
from py_ecc.optimized_bn128 import G1, multiply, neg, is_inf, Z1
print(G1)
# (1, 2, 1)
Pruebas de conocimiento cero básicas con curvas elípticas
Considera este ejemplo bastante trivial:
Afirmación: “Conozco dos valores e tales que ”
Prueba: Multiplico x por G1 e y por G1 y te los entrego como A y B.
Verificador: Multiplicas 15 por G1 y compruebas que A + B == 15G1.
Aquí está en Python:
from py_ecc.bn128 import G1, multiply, add
# Prover
secret_x = 5
secret_y = 10
x = multiply(G1, 5)
y = multiply(G1, 10)
proof = (x, y, 15)
# verifier
if multiply(G1, proof[2]) == add(proof[0], proof[1]):
print("statement is true")
else:
print("statement is false")
Aunque el verificador no sabe cuáles son los valores de x e y, puede verificar que x e y suman 15 en el espacio de la curva elíptica; por lo tanto, secret_x y secret_y suman 15 como elementos del campo finito.
Queda como ejercicio para el lector hacer algo más sofisticado, como demostrar el conocimiento de la solución a un sistema de ecuaciones lineales.
Como pista (muy importante), multiplicar un número por una constante es lo mismo que una suma repetida. La suma repetida es lo mismo que la multiplicación escalar en curvas elípticas. Así, si x es un punto de una curva elíptica, podemos multiplicarlo por un escalar de 9 usando multiply(x, 9). Esto es consistente con nuestra declaración de que no podemos multiplicar puntos de curvas elípticas entre sí: en realidad estamos multiplicando un punto de una curva elíptica por un escalar, no por otro punto.
¿Puedes probar que conoces tal que ? ¿Puedes generalizar esto a más variables?
Como otra pista: tú (el probador) y el verificador deben acordar la fórmula de antemano, ya que el verificador ejecutará la misma “estructura” de la fórmula original para la que afirmas conocer la solución.
Suposiciones de seguridad
Para que el esquema anterior sea seguro, asumimos que si publicamos un punto como multiply(G1, x), un atacante no puede inferir a partir del valor creado cuál fue el valor original de . Esta es la suposición del logaritmo discreto. Por eso el número primo sobre el que calculamos la fórmula debe ser grande, para que el atacante no pueda adivinarlo mediante fuerza bruta.
Existen algoritmos más sofisticados, como el algoritmo baby step giant step, que pueden superar a la fuerza bruta.
Nota: El nombre BN128 proviene de la suposición de que tiene 128 bits de seguridad. La curva elíptica se calcula en un campo finito de 254 bits, pero se cree que tiene 128 bits de seguridad ya que existen algoritmos mejores que la fuerza bruta ingenua para calcular el logaritmo discreto.
Verdadero conocimiento cero
También debemos señalar que nuestro ejemplo A + B = 15G no es de verdadero conocimiento cero. Si un atacante adivina a y b, puede verificar su suposición comparando los puntos de la curva elíptica generados con los nuestros.
La solución a este problema se abordará en un capítulo posterior.
Tratando las curvas elípticas sobre campos finitos como una caja negra mágica
Al igual que no necesitas saber cómo funciona internamente una función hash para poder usarla, tampoco necesitas conocer los detalles de implementación de la suma de puntos en curvas elípticas ni su multiplicación por un escalar.
Sin embargo, sí necesitas conocer las reglas que siguen. A riesgo de sonar como un disco rayado a estas alturas, siguen las reglas de los grupos cíclicos:
- la suma de puntos de una curva elíptica es cerrada: produce otro punto de la curva elíptica
- la suma de puntos de una curva elíptica es asociativa
- existe un elemento de identidad
- cada elemento tiene un inverso que al ser sumado, produce el elemento de identidad
Mientras comprendas esto, puedes sumar, multiplicar e invertir a tu antojo sin hacer nada inválido. Cada una de estas operaciones tiene su función correspondiente en la biblioteca py_ecc.
Esto es lo más importante que debes recordar en esta lección:
Las curvas elípticas sobre campos finitos encriptan de forma homomórfica la suma en un campo finito.
Matemáticas lunares (Moon math): ¿cómo sabemos el orden de la curva?
El lector puede estar preguntándose cómo somos capaces de determinar el orden de la curva bn128 sin contar todas las soluciones válidas de la fórmula. Hay más puntos válidos de los que cualquier computadora puede enumerar, entonces, ¿cómo llegamos al orden de la curva?
Este es un ejemplo del tipo de matemáticas que intentamos evitar, porque es bastante avanzado. Resulta que, calcular el número de puntos se puede hacer en tiempo polinomial con Schoof’s Algorithm. No se espera que entiendas cómo funciona este algoritmo, pero es suficiente saber que el algoritmo existe. Cómo llegamos al orden de la curva no es importante desde el punto de vista de la implementación, solo nos importa que los diseñadores lo hayan calculado correctamente.
Los materiales aquí en RareSkills están cuidadosamente diseñados para mantenerse alejados de estos campos minados matemáticos.
Aprende más con RareSkills
Es por esto que nuestro curso de conocimiento cero enfatiza tanto los fundamentos del álgebra abstracta. Comprender los detalles de implementación de las curvas elípticas es una pesadilla de difícil. Pero comprender el comportamiento de los grupos cíclicos, aunque inusual al principio, es totalmente comprensible para la mayoría de los programadores. Una vez que entendemos eso, el comportamiento general de sumar puntos de curvas elípticas se vuelve intuitivo, a pesar de que la operación sea difícil de visualizar.
Publicado originalmente el 19 de septiembre de 2023