TecNoticias, tu portal de información

Obtenga información sobre ECC o criptografía de curva elíptica, incluidas sus aplicaciones y beneficios.

Mi último artículo discutió el ingenio del intercambio de claves Diffie-Hellman. Este artículo presenta las curvas elípticas utilizadas en un intercambio más avanzado. (Si desea un poco más de contexto, consulte mi introducción a la criptografía para obtener información básica).

La razón por la que utilizamos curvas elípticas para el intercambio de claves es porque permiten generar claves más largas con menos bits de datos intercambiados entre las computadoras. Este método de criptografía fue descubierto independientemente por Neal Koblitz y Victor S. Miller.

Los investigadores de seguridad siempre sabían que era posible "romper" una clave de 512 bits a través de la fuerza bruta, las tablas del arco iris o algún otro ingenio. Simplemente se pensó que tomaba demasiadas computadoras y demasiado tiempo.

En los años transcurridos desde que se implementó por primera vez el intercambio Diffie-Hellman original, los microprocesadores se han vuelto más rápidos, más pequeños y más asequibles. Un mal actor de hoy puede crear un clúster de computadora Raspberry Pi de 50 nodos y 400 nodos por aproximadamente el mismo costo que una computadora con base en 8051 desde hace 30 años. Eso significa que los investigadores de seguridad y los "buenos" necesitan aumentar constantemente la longitud de la clave para evitar que los malos descubran sus secretos.

Uno de los esquemas utilizados hoy en día es el intercambio Diffie-Hellman de curva elíptica.

¿Qué es una curva elíptica?

Las curvas elípticas son una clase de curvas que satisfacen ciertos criterios matemáticos. Específicamente, una curva plana es elíptica si es suave y toma la "forma de Weierstrass" comúnmente utilizada de

$$ y ^ {2} = x ^ {3} + Ax + B $$

dónde

$$ 4A ^ {3} + 27B ^ {2} ≠ 0 $$

A menudo verá estas curvas representadas como cortes planos de lo que de otra manera podría ser una gráfica 3D.

A la izquierda, en rojo transparente, está el gráfico de contorno tridimensional de y2 = x3-3x + z. El plano naranja que intersecta la gráfica de contorno 3D se muestra a la derecha. La curva es "elíptica" en todas partes, excepto en el punto de silla de montar, donde la curva pasa de una curva cerrada a una curva abierta.

Es posible que note que las "curvas elípticas" no parecen elipses geométricas. Esto se debe a que las "curvas elípticas" toman su nombre de una clase más grande de ecuaciones que describen estas curvas y las elipses que conoció en la escuela.

$$ ay ^ 2 + by = cx ^ 3 + dx ^ 2 + ex + f quad {a, b, c, d, e, f } in rm I ! R $$

La forma general de la ecuación de curva elíptica.

Operaciones de adición de curva elíptica

Las curvas elípticas tienen algunas peculiaridades necesarias cuando se trata de la suma. Dos puntos en la curva (P, Q) interceptarán la curva en un tercer punto de la curva. Cuando ese punto se refleja en el eje horizontal, se convierte en el punto (R). Entonces P ⊕ Q = R.

*Nota: El carácter ⊕ se utiliza como un operador matemático de suma de puntos, no el binario XOR operador.

En el gráfico de la izquierda, el punto P (-2.1, 0.2) más el punto Q (0, -1.7) produce el punto R (2.9, 4.4). En la gráfica de la derecha, el punto P (-2.1, 0.2) + el punto R (2.9, 4.4) produce el punto S (-0.1, -1.8)

La línea que conecta P y Q intersecta la curva en un tercer punto, y cuando ese punto se refleja en el eje horizontal, se convierte en el punto R.

Esta reflexión es necesaria para los tiempos en que P y Q están en el mismo punto de la curva (P = Q). En esos casos, la línea generada es tangente a la curva por definición. Sin la reflexión, no sería posible agregar P a sí mismo varias veces, ya que P⊕P (2P) generaría el mismo punto que P⊕P⊕P (3P, 4P, nP), etc.

Izquierda: Un punto que se agrega a sí mismo (2P) genera una línea tangente que intercepta la curva en un nuevo punto que cuando se refleja en el acceso horizontal se convierte en el punto R. Derecha: Dos puntos (P, Q) que se encuentran en la curva interceptarán la curva en un tercer punto, que cuando se refleja a través del acceso horizontal se convierte en el punto R.

Esto, por supuesto, no sería una condición matemática ideal. Al reflejar debajo de la línea, P⊕P = R, y el punto P⊕R = P⊕P⊕P = 3P termina generando un nuevo punto (-S) en otra parte de la curva. Ese nuevo punto, cuando se agrega a P, genera un nuevo punto, y así sucesivamente. Sin la reflexión, nada de esto sucedería.

El siguiente gráfico muestra el resultado de la adición sucesiva de P a sí mismo (P⊕P, P⊕2P, P⊕3P, P⊕4P, etc.).

Esta animación muestra los resultados de P⊕P⊕P⊕P⊕P – Cada fotograma muestra los resultados de P⊕Q = R (hasta que la animación completa el ciclo), siendo el primer fotograma P⊕P, y cada fotograma sucesivo usando el resultados del último fotograma R para generar el nuevo punto Q que se agrega al punto estacionario P. Cada punto "Q" comienza el fotograma donde "R" finalizó el fotograma anterior (hasta que se recicla a 2P).

La idea detrás de todo esto es que un punto en la curva agregado a sí mismo varias veces generará otros puntos en la curva. Cualquiera de los dos puntos puede usarse para identificar un tercer punto en la curva. Se proporciona una excepción para cuando P (x, y = 0), y la línea tangente va al infinito.

Encontrar puntos enteros en la curva

Para usar estas curvas en criptografía, tenemos que limitar su rango; después de todo, simplemente no es práctico tener números cercanos al infinito en un microcontrolador de 16/32/64 bits. Por lo tanto, el rango vertical y horizontal está limitado a un número primo muy grande, p. El operador de módulo se utiliza para mantener los resultados dentro de ese rango. Luego, se encuentran todas las soluciones enteras de la ecuación que describe la curva.

En este ejemplo, usaré el número primo 281 y la ecuación

$$ y ^ 2 = x ^ 3-3x + 3 $$

Reorganizar e introducir el operador de módulo deja la siguiente ecuación:

$$ (y ^ 2-x ^ 3 + 3x-3) (mod ; 281) = 0 $$

En esta ecuación, x e y son números enteros con valores entre 0 y 281. Cuando se calcula el lado izquierdo de la ecuación, dividido por 281, y no hay resto, el punto se agrega a la lista a continuación.

Entonces es una cuestión de sustituir todos los valores enteros de x e y entre 0 y 281 en la ecuación y ver si la ecuación es verdadera o no. Si bien la ecuación se puede evaluar a mano, el proceso se adapta mejor a un programa de computadora.

Los puntos que satisfacen la ecuación mostrada anteriormente están codificados por colores para su uso en un diagrama que se muestra a continuación. Los colores se basan en su valor de y distancia desde 281/2, que es la mitad del módulo. Tenga en cuenta que cada valor de x solo tiene dos valores de y, y los valores de y son equidistantes del punto medio del módulo. Los colores se introducen simplemente para ayudar en el reconocimiento de patrones en diagramas posteriores

Cuando estos puntos se trazan en coordenadas cartesianas, ciertas simetrías se hacen evidentes.

La gráfica de arriba traza los puntos previamente determinados. Tenga en cuenta que cada valor x tiene dos valores y que están separados por igual del centro vertical.

Pero una gráfica plana no es realmente la mejor manera de visualizar los números. Cuando usamos el operador de módulo, el gráfico se envuelve alrededor de sí mismo en las direcciones x e y una vez que alcanza 281; 281 es equivalente a 0, 282 es equivalente a 1, 290 es equivalente a 9, etc. Si la gráfica se envolviera en una sola dirección, podríamos representarla como un cilindro. Pero se envuelve en ambos y los matemáticos tienden a imaginar esas situaciones con un toro.

Los puntos de datos asignados a la superficie del toro se muestran en la siguiente imagen, con líneas de colores provistas para ayudar a determinar la orientación.

El toro se crea de tal manera que el punto medio vertical de la gráfica corresponde al radio exterior del toro, y la parte superior e inferior de la gráfica corresponden al radio interno del toro. En este gráfico, la codificación de colores debe permitirle ver cómo se mapean los puntos en el toro. Por ejemplo, el grupo de puntos cerca (50,150) es visible en el lado cercano del toro a la izquierda del espectador. Se agregan líneas de puntos para ayudar a los espectadores a determinar la orientación.

A continuación se muestra una línea de pendiente constante que recorre la superficie del toro. Esta línea pasa a través de dos puntos de datos seleccionados al azar.

Para agregar dos puntos en el gráfico, dibuje una línea desde el primer punto seleccionado PAG = (187, 89) al segundo punto seleccionado Q = (235, 204), y extiende la línea hasta que se cruce con otro punto en el gráfico -R = (272, 215), extendiéndolo a través de los límites de la trama si es necesario.

Una vez que intercepte un punto de datos, refleje el punto verticalmente en la mitad del gráfico (una línea de puntos naranja que representa y = 281/2) para encontrar el nuevo punto en el gráfico (272, 66). Por lo tanto (187, 89) ⊕ (235, 204) = (272, 66)

Esto es equivalente a lo que hicimos antes. Se seleccionan dos puntos y se dibuja una línea entre ellos hasta que intercepta el tercer punto. Como calculamos los puntos, sabemos que todos se encuentran en el gráfico y satisfacen la ecuación.

$$ (y ^ 2-x ^ 3 + 3x-3) (mod ; 281) = 0 $$

Poniéndolo todo junto: el intercambio de claves de curva elíptica de Diffie-Hellman

El intercambio Diffie-Hellman descrito en el último artículo mostraba cómo dos usuarios podían llegar a un secreto compartido con aritmética modular. Con la criptografía de curva elíptica, Alice y Bob pueden llegar a un secreto compartido moviéndose alrededor de una curva elíptica.

Alice y Bob primero aceptan usar la misma curva y algunos otros parámetros, y luego escogen un punto aleatorio G en la curva.

Tanto Alice como Bob eligen números secretos (α, β). Alice multiplica el punto G por sí mismo α veces, y Bob multiplica el punto G por sí mismo β veces.

En este ejemplo, Alice escogió α = 7 y Bob escogió β = 5 como sus números secretos.

Cada uno llega a los nuevos puntos A = αG y B = βG que intercambian los puntos entre sí.

Comenzando en los nuevos puntos, Alice y Bob nuevamente multiplican su nuevo punto por su propio número secreto.

Bob y Alice multiplican su número secreto por el punto que reciben para generar el secreto S. Esto funciona porque, matemáticamente, S = α (βG) = β (αG).

Una vez que Alice y Bob intercambian sus números públicos A y B, repiten el cálculo de puntos (αβ) que realizaron antes con su hasta que determinan su secreto compartido S

Al final del intercambio, Bob y Alice eligieron un punto secreto S en el gráfico que Eve no puede determinar fácilmente.

Recuerde que utilizamos números pequeños para facilitar la comprensión del proceso. DHEC utiliza una ecuación conocida públicamente con grandes coeficientes y módulos, por ejemplo, curve1559, que podría estar protegiendo su navegador en este momento.

max: 115792089210356248762697446949407573530086143415290314195533631308867097853951
curva: y² = x³ + ax + b
a = 115792089210356248762697446949407573530086143415290314195533631308867097853948
b = 41058363725152142129326129780047268409114441015993725554835256314039467401291

Resumen

Gran parte de la criptografía moderna se basa en el intercambio Diffie-Hellman, que requiere que dos partes combinen sus mensajes con un secreto compartido que es difícil de deducir para un mal actor.

La curva elíptica Diffie-Hellman permite a los microprocesadores determinar de forma segura una clave secreta compartida, lo que dificulta que un mal actor determine la misma clave compartida. Los siguientes artículos mostrarán cómo implementar comunicaciones seguras en un proyecto de microcontrolador.

Recurso adicional