sábado, 27 de diciembre de 2014

¿Qué son las curvas elípticas?

La última charla del primer día a la que asistí resultó ser una introducción muy asequible de cómo funcionan las curvas elípticas para cifrar. Particularmente interesante es el formato de presentación de doble página que facilitaba mucho seguir las explicaciones, aunque os enlazo a la normal que es más fácil de seguir y tiene menso páginas.
Voy a intentar hacer un resumen, explicando los conceptos básicos, aunque para los detalles recomiendo leerse la charla que tiene todo el codigo en python de ejemplo además de las ecuaciones.
El cálculo básico que han enseñado es un cálculo irreversible que permite ser usado en cifrados asimétricos como los que se usan para firmas de clave pública o protocolos para intercambio secreto de claves. Aunque también pueden ser usados para cifrados de clave secreta, simétricos, en la charla no se explicó cómo hacerlo.
Para entender los cálculos, se comienza mostrando el cálculo sobre un círculo en lugar de una curva elíptica. Un cifrado de clave asimétrica en un círculo consiste en multiplicar por un escalar el ángulo de un punto del círculo, haciéndolo además con una aritmética con un módulo primo grande.
Lo primero que mostraron es cómo es la suma (de ángulos) de dos puntos del círculo. Aunque requiere trigonometría, la suma de dos puntos (x1,y1) y (x2,y2) es una fórmula sencilla en el círculo: (x1*y2+x2*y1, y1*y2-x1*x2). Una vez se tiene explicada la suma, el multiplicar por un escalar --n*(x,y), representado como n(x,y)-- es simplemente sumar repetidamente un número consigo mismo.
En este sistema de cifrado, son conocidos por todos el punto inicial, (x,y) y el módulo p en el que se realizan los cálculos, y la clave pública para por ejemplo un intercambio de Diffie Hellman serían a(x,y) y b(x,y) que permiten calcular el secreto común a(b(x,y)) = b(a(x,y)), y los secretos son a y b, ya que es muy difícil calcular a partiendo de a(x,y) ya que el cálculo módulo p y el hecho de que al multiplicar el punto da muchas vueltas al círculo lo hacen muy difícil de adivinar.
De hecho, la principal ventaja de las curvas elípticas es que la mejora de los métodos para factorizar números que afectan al RSA no debilitan nada el algoritmo.
Para realmente usar curvas elípticas, en lugar de un círculo x^2+y^2=1, se usa una curva elíptica, en la que por ejemplo:
  • x^2+y^2=1+dx^2y^2 (curvas de Edward)
  • y^2=x^3+ax+b (curvas de Weierstrass)
  • Ay^2=x^3+Bx^2+x (curvas de Montgomery)
Por terminar el ejemplo de las curvas de Edward, la fórmula de la suma de dos puntos, pasa a ser muy parecido, añadiendo un factor divisor a los términos: ((x1*y2+x2*y1)/(1+d*x1*x2*y1*y2), y1*y2-x1*x2/(1-d*x1*x2*y1*y2)), a los factores conocidos anteriormente es necesario añadir el factor d de la curva.
En la charla se han mencionado además varios criterios que son necesarios para usar adecuadamente las curvas:
  • Escoger un d que sea seguro y no produzca excepciones (si d es un cuadrado, los denominadores de las divisiones anteriores pueden ser cero).
  • Escoger un primo p que sea seguro. 
  • Tener cuidado con los ataques de temporización o escuchas (puede deducirse n del tiempo de computación o las frecuencias emitidas por la CPU)

No hay comentarios:

Publicar un comentario en la entrada