miércoles, 17 de septiembre de 2014

Criptografía con curvas elípticas

Hace tiempo que le doy vueltas a la idea de hacer un post sobre criptografía basada en curvas elípticas, pero hasta ahora me he resistido porque no es un tema fácil de tratar de forma divulgativa sin meterse en berenjenales matemáticos de mucho cuidado.
Aun así, me voy a atrever por dos motivos. Porque me apetece, que para eso es mi blog, y porque personalmente creo que es un campo muy prometedor para la investigación en criptografía.
Voy a tratar de simplificar al máximo y voy a ahorrarte demostraciones matemáticas y formulitas todo lo que pueda, pero avisado quedas de que este es un artículo donde se presupone que el lector tiene cierta competencia matemática.
Sin más preámbulos, vamos al lío.


Las curvas elípticas son un campo de las Matemáticas relativamente nuevo, ya que fue en 1985 cuando se escucha hablar de estas curvas por primera vez. Lo que las hace interesante es que haciendo uso de ellas podemos implementar sistemas criptográficos más difíciles de romper con claves más pequeñas que con los criptosistemas de clave pública convencionales como RSA. Esto los hace más eficientes e interesantes para sistemas con pocos recursos, como teléfonos móviles o smartcards. Además gracias a las últimas investigaciones sobre pairings en curvas elípticas, es posible crear criptosistemas como los basados en la identidad, que son bastante interesantes.

¿Qué son las curvas elípticas?

Yendo al grano, una curva elíptica es la descrita por la ecuación siguiente.

\[Y^{2}=X^{3}+aX+b\]

Además se le debe exigir que sea no singular. Una curva no singular es la que no tiene ningún punto p singular, que son aquellos puntos en los que sus dos derivadas parciales son cero.

\[\frac{\partial f}{\partial x}(p) = 0\]
\[\frac{\partial f}{\partial y}(p) = 0\]

Si hubiera algún punto singular, la curva no nos serviría, ya que como veremos más adelante, no sería posible definir una estructura algebraíca sobre ella. Para que la curva no tenga puntos singulares, es condición necesaria y suficiente que su discriminante sea distinto de cero. Es decir:

\[(4a^{3}+27b^{2})\neq 0\]

Vamos a ver un par de curvas de ejemplo para hacernos una idea de qué pinta tienen. Por ejemplo \(y^{2}=x^{3}+2x+3\) se ve tal que así.


Y la curva \(y^{2}=x^{3}-4x+1\) tiene la siguiente forma.


Curvas elípticas como grupo algebraico

Nuestro objetivo final es poder realizar operaciones matemáticas como sumas y multiplicaciones para poder construir sobre estas curvas los algoritmos criptográficos que nos interesen. Para ello hay que definir un grupo algebraico sobre la curva elíptica.
Para construir nuestro grupo, lo primero que necesitamos es una operación binaria que, dados dos elementos (puntos de la curva) al operar con ellos obtengamos un tercer elemento que también pertenezca al grupo (es decir, otro punto que pertenezca a la curva). A esta operación la vamos a llamar suma, y para definirla nos vamos a valer de una propiedad muy curiosa de las curvas elípticas.
Si trazamos una recta que corte dos puntos P y Q, la recta cortará exactamente a un sólo tercer punto R (bueno, como veremos ahora, casi siempre).


Por definición, tomaremos como valor negativo de un punto a su simétrico respecto al eje de las abscisas.
Ya podemos definir la operación suma como el inverso del tercer punto de corte de la recta formada por P y Q. Es decir P+Q=-R.


¿Serías capaz de encontrar una recta que sólo corte dos puntos de la función? Si te empeñas seguro.


Estarás pensando que acabamos de quedarnos sin operación suma, pero no. Los puntos que definen una recta como ésta decimos que toman el valor \(O\). A este valor lo llamaremos elemento cero o neutro. En el ámbito de las curvas elíptica se le conoce como punto en el infinito. Para entender por qué se llama así tendríamos que movernos a una tercera dimensión y construir proyecciones en el plano, así que mejor te lo ahorro.

Otro caso que aun no podemos manejar es el siguiente.


En este caso, la recta sólo toca dos puntos. Se trata de la recta tangente al punto P y que toca un segundo punto en la recta (lo llamaremos R). A este caso lo llamaremos 2P (P+P) y su resultado es -R. También podemos verlo como que P=Q.

No voy a demostrar ninguna de las definiciones que acabamos de hacer, así que tendrás que hacer un acto de fe.

Recapitulando, tenemos las siguientes propiedades:

- Suma: P+Q=-R (salvo para el resultado \(O\) y para P=Q).

- Elemento cero: Lo denotaremos con el símbolo \(O\). Así P+\(O\)=P. Habitualmente, a \(O\) se le denomina punto en el infinito.

- Elemento inverso: Como hemos visto, definimos el inverso del punto R=(x,y) como -R=(x,-y).

- 2P: Definimos el producto 2P (algunos autores dicen doblar el punto P) como la recta tangente a la curva que pasa por el punto P. 2P=-R.

Estas propiedades son suficientes para definir un grupo algebraico sobre el que realizar las operaciones matemáticas necesarias para desarrollar aplicaciones criptográficas basadas en curvas elípticas.

Curvas elípticas sobre cuerpos finitos

Hemos definido las operaciones anteriores sobre una curva elíptica definida sobre \(\mathbb{R}\) (números reales). Construir algoritmos criptográficos sobre \(\mathbb{R}\) sería muy problemático, tanto por la velocidad de cálculo como por la imprecisión que conlleva trabajar en número reales. En la práctica se construyen las curvas sobre cuerpos finitos en \(\mathbb{Z}\) (también conocidos como cuerpos de Galois). Si has trabajado con aritmética modular (congruencias) este cuerpo ya te es familiar. En general, las curvas elípticas se construirán sobre \(\mathbb{Z}_{p}\) siendo p un número primo mayor que 3 (en la práctica del orden de 256 bits frente a los, al menos, 1024 bits aconsejables para RSA).
Bajo este nuevo prisma, redefiniremos la ecuación de la curva elíptica como

\[Y^{2}=X^{3}+aX+b \mod p\]

Tampoco voy a demostrarlo, pero todo lo que hemos dicho para las curvas en \(\mathbb{R}\) vale para las curvas en \(\mathbb{Z}\). Por ejemplo -P(x,y)=(x, -y mod p).

El siguiente gráfico muestra el aspecto de la curva elíptica \(y^{2}=x^{3}-4x+1\) sobre \(\mathbb{Z}_{101}\) y las rectas correspondientes a la suma P+Q.


Criptografía con curvas elípticas

Sobre el cuerpo algebraico que acabamos de definir podemos construir esquemas criptográficos de clave pública como por ejemplo ElGamal, que es el que vamos a usar como ejemplo. La fortaleza criptográfica de ElGamal se basa en la dificultad de resolver el problema del logaritmo discreto en \(\mathbb{Z}_{p}\) para un p primo grande. En otras palabras, es fácil y eficiente calcular potencias en \(\mathbb{Z}_{p}\), pero computacionalmente difícil realizar la operación inversa (encontrar el logaritmo discreto). \(\alpha ^z\equiv \beta \mod p\) es fácil de calcular pero obtener z a partir de \(\beta \mod p\) es muy difícil.

Para cifrar un mensaje usando ElGamal sobre curvas elípticas realizamos los siguientes pasos:

- Bernardo elige un punto \(\alpha\) sobre una curva E definida sobre \(\mathbb{Z}_{p}\).

- Bernardo también elige un un entero z entre 1 y el orden de E (simplificando muuuuucho, el orden de E es el número de puntos en E sobre \(\mathbb{Z}_{p}\)).

- Bernardo calcula \(\beta = z \alpha\) sobre la curva E. La clave pública de Bernardo es (\(\alpha\), \(\beta\), E) y su clave privada es z. Recuerda que el producto se puede calcular como sumas sucesivas.

- Si Alicia quiere enviar un mensaje a Bernardo elige un entero k entre 1 y el orden de la curva E. Esta será la clave privada de Alicia.

- Para cifrar el mensaje M, Alicia utiliza la clave pública de Bernardo. Para ello hace corresponder el mensaje M con un punto x de la curva y realiza el siguiente cálculo.

\[e_{k}(x,k)=(k\alpha, x+k\beta)=(y_{1}, y_{2})\]

Donde \(y=(y_{1}, y_{2})\) es el mensaje cifrado e \(y_{1}\) la clave pública de Alicia.

Si Bernardo ahora quiere descifrar el mensaje hace el siguiente cálculo (recuerda que estamos operando en una curva elíptica definida sobre \(\mathbb{Z}_{p}\)).

\[d_{z}(y_{1},y_{2})=y_{2}-zy_{1}=(x+k\beta)-z(k\alpha)=x+k(z\alpha)-z(k\alpha)=x\]

Al igual que con ElGamal, también podemos construir otros esquemas criptográficos de clave pública como, por ejemplo, las firmas digitales ECDSA (DSA sobre curvas elípticas). Además se abren nuevas posibilidades como la criptografía basada en pairings, pero eso mejor lo dejamos para otro día.

1 comentario:

  1. Hace bastante rato que busco tú blog y lo primero que encuentro es este artículo, me pareció muy interesante aunque a decir verdad, me cuesta trabajo comprender lo que posteas, sin embargo le dedicaré una leída a los conceptos que mencionas.
    Saludos.

    ResponderEliminar