Suma en curvas elípticas
Descargo de responsabilidad: esto no le hace justicia al rico tema de las curvas elípticas. Se simplifica mucho. Como las curvas elípticas recientemente recibieron mucha atención de los medios en el contexto del cifrado, quería proporcionar una pequeña idea de cómo funciona realmente el "cálculo" en una curva elíptica.
Introducción
Las curvas elípticas son conjuntos de puntos (x,y)
en el plano de la forma y^2 = x^3+Ax+B
. (Además, 4A^3+27B^2 ≠ 0
para evitar singularidades desagradables). Puede considerar estas curvas en cualquier campo. Si usa el campo de números reales, las curvas se pueden visualizar y se ven así:
Lo especial de estas curvas es que tienen una operación aritmética incorporada que es el análogo de la suma. Puede sumar y restar puntos, y esta operación es asociativa y conmutativa (un grupo abeliano).
¿Cómo funciona la suma?
Nota: la adición de puntos en curvas elípticas no es intuitiva. Este tipo de adición se define como es porque tiene ciertas propiedades agradables. Es raro, pero funciona.
Como las curvas elípticas forman un grupo, existe una identidad aditiva que es equivalente a 0. Es decir, agregar 0
a cualquier punto no cambiará el resultado. Esta identidad aditiva es el "punto" en el infinito. Todas las líneas en el plano incluyen este punto en el infinito, por lo que agregarlo no hace diferencia.
Digamos que cualquier línea dada intersecta la curva en tres puntos, que puede ser 0
, y que la suma de estos tres puntos es 0
. Teniendo eso en cuenta, mira esta imagen.
Ahora, la pregunta natural es, ¿qué es P+Q
? Bueno, si P+Q+R = 0
, entonces P+Q = -R
(alternativamente escrito como R'
). ¿Dónde está -R
? Es donde R + (-R) = 0
, que está en el otro lado del eje x de R
manera que la línea a través de ellos es vertical, de intersección solamente R
, -R
y 0
. Puedes ver esto en la primera parte de esta imagen:
Otra cosa que puede ver en estas imágenes es que la suma de un punto consigo mismo significa que la línea es tangente a la curva.
Cómo encontrar intersecciones de líneas y curvas elípticas
En el caso de dos puntos distintos
Generalmente hay exactamente una línea a través de dos puntos P=(x0,y0), Q=(x1,y1)
. Suponiendo que no es vertical y los dos puntos son distintos, podemos escribirlo como y = m*x+q
. Cuando queremos encontrar los puntos de intersección con la curva elíptica, podemos escribir
0 = x^3+Ax+B-y^2 = x^3+Ax+B-(m*x+q)^2
que es un polinomio de tercer grado. Por lo general, no son tan fáciles de resolver, pero ya conocemos dos ceros de este polinomio: ¡las dos x
coordenadas x0, x1
de los dos puntos que queremos agregar!
De esa forma, factorizamos los factores lineales (x-x0)
y nos (x-x1)
queda un tercer factor lineal cuya raíz es la x
coordenada del punto R
. ( -R
también debido a la simetría. Tenga en cuenta que si R = (x2,y2)
entonces -R = (x2,-y2)
. El -
es del grupo; no es un negativo vectorial).
En el caso de agregar un punto P
a sí mismo
En este caso tenemos que calcular la tangente de la curva en P=(x0,y0)
. Podemos escribir directamente m
y q
en términos de A,B,x0,y0
:
3*x0^2 + A
m = ------------
2*y0
-x0^3 + A*x0 + 2*B
q = --------------------
2*y0
Obtenemos la ecuación y = m*x+q
y podemos proceder de la misma manera que en el párrafo anterior.
Un árbol de casos completo
Esta es una lista completa de cómo manejar todos esos casos:
Dejar P,Q
ser puntos en la curva elíptica (incluido el punto "infinito" 0
)
- Si
P = 0
oQ = 0
, entoncesP+Q = Q
oP+Q = P
, respectivamente - De lo contrario
P ≠ 0
yQ ≠ 0
, así que dejaP = (x0,y0)
yQ = (x1,y1)
:- Si
P = -Q
(eso significax0 = x1
yy0 = -y1
) entoncesP+Q = 0
- Más
P ≠ -Q
- Si
x0 = x1
entonces tenemosP=Q
y calculamos la tangente (ver sección anterior) para obtenerR
. LuegoP+Q = P+P = 2P = -R
- De lo contrario: podemos
y = m*x+y
calcular una línea del formulario a través de esos dos puntos (ver sección anterior) para calcularR
. LuegoP+Q=-R
- Si
- Si
Campos finitos
Para este desafío solo consideraremos los campos de tamaño p
donde p
es primo (y debido a algunos detalles p ≠ 2, p ≠ 3
). Esto tiene la ventaja de que simplemente puede calcular mod p
. La aritmética en otros campos es mucho más complicada.
Esto en este ejemplo lo establecemos p = 5
y todas las igualdades aquí son congruencias mod 5
.
2+4 ≡ 6 ≡ 1
2-4 ≡ -2 ≡ 3
2*4 ≡ 8 ≡ 3
2/4 ≡ 2*4 ≡ 3 because 4*4 ≡ 16 ≡ 1, therefore 1/4 ≡ 4
Reto
Dados los parámetros A,B
de una curva elíptica, una característica de campo principal p
y dos puntos P,Q
en la curva elíptica, devuelven su suma.
- Puede suponer que los parámetros
A,B
realmente describen una curva elíptica, eso significa que4A^3+27B^2 ≠ 0
. - Puede suponer que en
P,Q
realidad son puntos en la curva elíptica o el0
punto-. - Puedes suponer que
p ≠ 2,3
es primo.
Casos de prueba
Hice una implementación (no muy elegante) en MATLAB / Octave, que puede usar para sus propios casos de prueba: ideone.com Espero que sea correcto. Al menos reproducía algunos cálculos que hice a mano.
Tenga en cuenta los casos de prueba triviales que funcionan para todas las curvas que consideramos aquí:
Agregar cero: P+0 = P
Agregar el inverso:(x,y) + (x,-y) = 0
Para p = 7, A = 0, B = 5
los dos puntos P = (3,2)
y Q = (6,2)
están en la curva elíptica. Luego se cumple lo siguiente:
2*Q = Q+Q = P
2*P = P+P = (5,2)
3*P = P+P+P = (5,2)+P = (6,5)
4*P = P+P+P+P = (5,2)+(5,2) = (6,5)+(5,2) = Q
Todos los puntos en la curva elíptica son (3,2),(5,2),(6,2),(3,5),(5,5),(6,5),0
Para p = 13, A = 3, B = 8
nosotros tenemos
(1,8)+(9,7) = (2,10)
(2,3)+(12,11) = (9,7)
2*(9,6) = (9,7)
3*(9,6) = 0
Para p = 17, A = 2, B = 2
y P=(5,1)
obtenemos
2*P = (6,3)
3*P = (10,6)
4*P = (3,1)
5*P = (9,16)
6*P = (16,13)
7*P = (0,6)
8*P = (13,7)
9*P = (7,6)
10*P = (7,11)
Si eres realmente ambicioso, toma
p = 1550031797834347859248576414813139942411
A = 1009296542191532464076260367525816293976
x0 = 1317953763239595888465524145589872695690
y0 = 434829348619031278460656303481105428081
x1 = 1247392211317907151303247721489640699240
y1 = 207534858442090452193999571026315995117
e intenta encontrar un número natural n
tal que n*(x0,y0) = (x1,y1)
. Más información aquí.
Apéndice
Antes que nada, ¡MUCHAS GRACIAS a @ El'endiaStarman por revisar y editar mi borrador!
¿Por qué curvas elípticas?
Bueno, puede parecer una especie de ecuación arbitraria, pero no lo es, es bastante general: generalmente consideramos esas "formas" geométricas en el plano proyectivo (de ahí es de donde proviene el "infinito". Allí consideramos todo homogéneo polinomios de tercer grado. (Los de grado inferior o superior serían demasiado difíciles o triviales para examinar). Después de aplicar algunas restricciones para obtener las propiedades agradables que deseamos, y después de deshomogeneizar esos polinomios (proyectar en uno de los tres planos afines ) terminamos con ecuaciones comoy^2+a*x*y+b*y = x^3+c*x^2+d*x+e
Esta es una curva elíptica en la forma larga de Weierstrass. Estas son básicamente las mismas curvas que consideramos, pero algo sesgadas. Con una transformación de coordenadas lineal, puede hacer fácilmente una ecuación de Weierstras corta a partir de eso. ejemplo , que aún contienen todas las propiedades interesantes.
¿Por qué excluimos p=2,3
?
Esto tiene que ver con el hecho de que para la forma corta de Weierstrass necesitamos la restricción 4A^3+27B^2 ≠ 0
para evitar singularidades (más sobre eso a continuación). En un campo de la característica 2 que tenemos 4 = 0
y en un campo de la característica 3 que tenemos 27 = 0
, esto hace que sea imposible tener curvas en forma de weierstrass cortas para ese tipo de campos.
¿Qué son las singularidades?
Si la ecuación se 4A^3+27B^2=0
cumple, tenemos singularidades como las siguientes: Como puede ver en esos puntos, no puede encontrar una derivada y, por lo tanto, ninguna tangente, que "mata" la operación. Puedes mirar las ecuaciones y^2 = x^3
oy^2 = x^3-3*x+2
¿Por qué se llaman curvas elípticas de todos modos?
La razón es que las ecuaciones de esta forma aparecen en integrales elípticas, por ejemplo, qué es lo que obtienes cuando quieres calcular, por ejemplo, la longitud de arco de una elipse. Una breve presentación de diapositivas sobre el origen del nombre.
¿Qué tienen que ver con la criptografía?
Hay formas de calcular de manera nP = P+P+...+P
muy eficiente. Esto se puede usar, por ejemplo, en el intercambio de claves Diffie Hellman . La aritmética modular se puede reemplazar por la adición en subgrupos de torsión, estos son solo los puntos de la curva que tienen un orden finito. (Eso significa que mP = 0
para algunos m
, que básicamente es solo calcular mod m
).
y^2 = x^3 + x
es una curva elíptica válido y(0,0) ≠ 0
es un punto de la curva!)B = 0
y me preguntaba cómo0
funcionaría ... y luego me olvidé de eso. Creo que supuseB
que no podría ser 0 en algún momento de la noche anterior. ¿Tiene alguna sugerencia sobre cómo debería ser la entrada para esto? Quizás siB = 0
, entonces definir0 = (-1, -1)
? Estoy feliz de ajustar mi código para manejarlo, solo estoy pensando que sería bueno si también está estandarizado para otras presentaciones ...[0]
(solo una coordenada) es el punto infinito, o algo similar!nP
? ¿Podría señalarme algún recurso sobre el tema para que los pensamientos fluyan? Me está costando encontrar algo buscando en Google. ¡Gracias!Python 3,
193191bytesUna solución basada en la respuesta Pyth de Rhyzomatic y su lógica Python. En particular. Me gustó cómo encontraron la tercera raíz de un polinomio cúbico monico
x^3 + bx^2 + cx + d
cuando tienes dos raícesx_1
yx_2
al notar esob == x_1 + x_2 + x_3
y restar en consecuencia. Planeo agregar una explicación, jugar golf y tal vez trasladarla a Ruby, si Ruby resulta ser más bajo.No golfista:
fuente