Ir al contenido principal

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.

Comentarios

  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

Publicar un comentario

Entradas populares de este blog

Creando firmas de virus para ClamAV

ClamAv es un antivirus opensource y multiplataforma creado por Tomasz Kojm muy utilizado en los servidores de correo Linux. Este antivirus es desarrollado por la comunidad, y su utilidad práctica depende de que su base de datos de firmas sea lo suficientemente grande y actualizado. Para ello es necesario que voluntarios contribuyan activamente aportando firmas. El presente artículo pretende describir de manera sencilla cómo crear firmas de virus para ClamAV y contribuir con ellas a la comunidad.

Manejo de grafos con NetworkX en Python

El aprendizaje computacional es un área de investigación que en los últimos años ha tenido un auge importante, sobre todo gracias al aprendizaje profundo (Deep Learning). Pero no todo son redes neuronales. Paralelamente a estas técnicas, más bien basadas en el aprendizaje de patrones, también hay un auge de otras técnicas, digamos, más basadas en el aprendizaje simbólico. Si echamos la vista algunos años atrás, podemos considerar que quizá, la promesa de la web semántica como gran base de conocimiento ha fracasado, pero no es tan así. Ha ido transmutándose y evolucionando hacia bases de conocimiento basadas en ontologías a partir de las cuales es posible obtener nuevo conocimiento. Es lo que llamamos razonamiento automático y empresas como Google ya lo utilizan para ofrecerte información adicional sobre tus búsquedas. Ellos lo llaman Grafos de Conocimiento o Knowledge Graphs . Gracias a estos grafos de conocimiento, Google puede ofrecerte información adicional sobre tu búsqueda, ad...

Scripts en NMAP

Cuando pensamos en NMAP, pensamos en el escaneo de puertos de un host objetivo al que estamos relizando una prueba de intrusión, pero gracias a las posibilidades que nos ofrecen su Scripting Engine , NMAP es mucho más que eso. Antes de continuar, un aviso: algunas de posibilidades que nos ofrecen los scripts de NMAP son bastante intrusivas, por lo que recomiendo hacerlas contra hosts propios, máquinas virtuales como las de Metasploitable, o contrato de pentesting mediante. Para este artículo voy a usar las máquinas de Metasploitable3 . No voy a entrar en los detalles sobre el uso básico de NMAP, ya que hay miles de tutoriales en Internet que hablan sobre ello. Lo cierto es que NMAP tiene algunas opciones que permiten obtener información extra, además de qué puertos están abiertos y cuales no. Por ejemplo, la opción -sV trata de obtener el servicio concreto, e incluso la versión del servicio que está corriendo en cada puerto. Otro ejemplo es la opción -O, que intenta averiguar el ...