Matemáticas, Criptografía y otras hierbas

¿Sabías que la tecnología que hoy asegura tus mensajes de WhatsApp y transacciones bancarias fue ignorada por la industria durante casi 20 años? Esta tecnología corresponde a la criptografía con curvas elípticas (ECC).

La seguridad de la criptografía de clave pública se basa en problemas matemáticos de difícil resolución y las curvas elípticas nos ofrecen uno de ellos: el problema del logaritmo discreto.

Una clave utilizada en criptografía con curvas elípticas (ECC) de 256 bits ofrece un nivel de seguridad equivalente a una clave RSA de 3072 bits. La eficiencia es una necesidad para el internet móvil y el IoT.

Como vimos en el post anterior, las curvas elípticas, además de ser objetos geométricos, poseen una ley de suma que las convierte en un grupo abeliano. Esto quiere decir que existe una operación suma entre dos puntos de la curva que nos entrega otro punto.

En los números reales, calcular un logaritmo es un problema sencillo utilizando análisis numérico. Esto cambia al romper la continuidad y moverse al caos de los cuerpos finitos $\mathbb{F}_p.$

Calcular $Q=k\cdot P=P+P+…+P$, donde $k$ es un entero positivo y $P$ es un punto en la curva elíptica, es una operación trivial para los procesadores modernos. Gracias al algoritmo Double-and-Add ¹ podemos obtener el resultado en tiempo logarítmico respecto al tamaño de $k$. Por otro lado, hallar $k$ a partir de $Q$ y $P$, es un problema computacionalmente difícil, conocido como el Problema del Logaritmo Discreto en Curvas Elípticas (ECDLP).

Secretos compartidos: el Protocolo de Intercambio de Claves de Diffie-Hellman

En el siguiente diagrama, vemos cómo Anita y Beto pueden generar una clave secreta compartida mientras se comunican por un canal inseguro.

El protocolo funciona de la siguiente manera:

1. Selección de parámetros públicos: ambas partes acuerdan una curva elíptica $E\colon y^2=x^3+ax+b$, un número primo $p$ que determina el cuerpo finito $\mathbb{F}_p$ donde está definida la curva, y un punto base $P$ en la curva $E.$ Estos parámetros serán conocidos por todos.
2. Generación de claves secretas: Anita elige un secreto $a$ y Beto un secreto $b$, los cuales serán números positivos menores a $p$.
3. Generación de claves públicas: Anita calcula $a\cdot P$ y se lo envía a Beto. Por su parte, Beto calcula $b\cdot P$ y se lo envía a Anita. Como estos datos se envían por un canal inseguro, podrían ser leídos por un atacante.
4. Derivación del secreto compartido: Anita toma la clave pública de Beto y calcula:

Beto toma la clave pública de Anita y calcula:

La conmutatividad de la suma de puntos en la curva elíptica es crucial para que ambos lleguen al mismo resultado.

Si Óscar es un atacante que tiene acceso al canal, podrá ver partes de la información como los parámetros públicos y las claves públicas de Anita y Beto. Sin embargo, para calcular la clave secreta compartida $S$, se requiere conocer el valor de las claves secretas $a$ o $b$, lo que equivale a resolver el problema del logaritmo discreto ECDLP.

Este protocolo fue desarrollado por Whitfield Diffie y  Martin Hellman  en 1976 y es parte del artículo New Directions in Cryptography ² en donde sentaron las bases de la criptografía de clave pública. Sin embargo, su propuesta fue desarrollada en otro grupo abeliano: $(\mathbb{F}_p-\{0\},\cdot)$.³

De cuerpos finitos a curvas elípticas

La genialidad del Protocolo de Diffie y Hellman original está en que su estructura no está atada a un grupo específico, sino a la existencia de funciones one-way. En la versión de 1976 se utilizaban exponenciaciones modulares $g^a \pmod p$. Incorporar curvas elípticas consistió en sustituir ese escenario por el grupo de puntos de una curva sobre un cuerpo finito $E(\mathbb{F}_p)$.

Esta migración no fue solo por gusto matemático . Uno de los ataques más potentes al Problema del Logaritmo Discreto es el Algoritmo de cálculo de índice. En particular, para el grupo multiplicativo ($\mathbb{F}_p^*,\cdot$), la complejidad del ataque se vuelve subexponencial.

El Problema del Logaritmo Discreto en Curvas Elípticas (ECDLP) es en este sentido, más fuerte. El mejor ataque conocido para ECDLP es el Ataque Pollard-Rho, el cual tiene complejidad exponencial.

Ataques a DLP

La siguiente fórmula permite medir la complejidad⁴ de un algoritmo

donde $n$ es el tamaño del grupo a atacar, $c$ es una constante positiva y $\alpha$ es una constante que modela la complejidad. En particular, si $\alpha=1$ la complejidad es exponencial, si $\alpha=0$ la complejidad es polinomial y si $0 < \alpha < 1$ la complejidad es subexponencial.

Algoritmo del Cálculo de Índice

En este algoritmo no se intenta adivinar el número secreto $x$ de golpe. Lo que hace es , transformar un problema multiplicativo gigante (exponenciación modular) en un sistema de ecuaciones lineales más pequeño y manejable. La complejidad del algoritmo de cálculo de índice sobre $\mathbb{F}_p^*$ es $L_p[1/2, c]$ ⁵ por lo que se considera subexponencial.

General Number Field Sieve (GNFS)

En el caso de cuerpos finitos de gran tamaño, el método GNFS ⁶ es la herramienta más potente. Esta es la misma técnica que se usa para factorizar números grandes en RSA, adaptada al logaritmo discreto. Este método es más eficiente, con una complejidad de $Lp​[1/3,1.923]$.

Algoritmo Pollard-rho

Este es un algoritmo de colisión. Basados en la paradoja del cumpleaños, sabemos que si saltamos «aleatoriamente» por un grupo de tamaño $n$, encontraremos dos puntos iguales mucho antes de recorrer todo el grupo. Específicamente, se sabe que si $n$ es el tamaño del grupo $E(\mathbb{F}_p)$, su complejidad es del orden de $\sqrt{n}$, es decir, $L_n[1, c]$.⁷

Récord de cálculos

La superioridad de ECC se demuestra en los récords de estos ataques. Mientras que se ha logrado romper logaritmos discretos en cuerpos finitos de hasta 795 bits ⁸ (requiriendo 900 años-núcleo), en curvas elípticas el récord apenas alcanza los 114 bits ⁹ con un esfuerzo computacional similar. Por eso, una clave de 256 bits en ECC nos garantiza seguridad.

El inicio de ECC

La criptografía con curvas elípticas (ECC) se refiere a utilizar el grupo de puntos de una curva elíptica en reemplazo de cuerpos finitos en el protocolo de Diffie-Hellman. Esto fue propuesto de forma independiente por Neal Koblitz y Victor Miller en 1985, pero no fue hasta 2004 que se comenzó a utilizar en el mundo real.

En los 90’s, el protocolo por definición era RSA con claves de 1024 bits,las cuales podían ser procesadas en los computadores sin mayor problema. Este panorama cambió cuando en 2005 la National Security Agency (NSA). (2005) anuncia la Suite B, («Fact Sheet NSA Suite B Cryptography«,donde especificaba que para proteger información clasificada hasta el nivel de Top Secret, se debían utilizar curvas elípticas con un tamaño de clave de al menos 384 bits. Para información «Secret», bastaban con 256 bits.

Posteriormente, el NIST formaliza estas recomendaciones en un estándar donde se comparan los tamaños de claves requeridos para cada nivel de seguridad.¹⁰

Además, con el auge de los primeros smartphones (como Blackberry) y otros dispositivos IoT, el ahorro de energía y memoria se volvió vital. Una clave ECC de 256 bits consume una fracción de la batería que requeriría una clave RSA equivalente de 3072 bits.

La espera valió la pena

Parece mucho tiempo, pero esos 19 años fueron relevantes para demostrar que los ataques mencionados no serían suficientes para quebrar ECDLP y lograr la confianza de la industria en estos increíbles objetos matemáticos.

De aquí surgen varias preguntas. ¿Qué curvas elípticas seguras podemos usar? ¿Cuáles son las curvas más eficientes? ¿Qué otros problemas de seguridad podría tener el protocolo de Diffie-Hellman?

Un spoiler del siguiente post: El NIST y otras entidades han sugerido ciertas familias de curvas elípticas con propiedades especiales, que además de tener una aritmética eficiente, son seguras frente a ataques como Pollard-rho. Entre ellas están las curvas de Montgomery y las curvas de Edwards. Un problema de seguridad al que se puede enfrentar son los ataques Man-in-the-Middle, en los que un atacante podría interceptar las claves públicas y suplantar a Beto ante Anita, y viceversa. Esto se resuelve con una autenticación previa.

Ah, y otra amenaza para este protocolo: la criptografía postcuántica.

View this post on Instagram

View this post on Instagram

1. Algoritmo 3.26 en Hankerson, D., Menezes, A. J., & Vanstone, S. (2004). Guide to Elliptic Curve Cryptography. Springer Science & Business Media. ↩︎
2. Diffie, W., & Hellman, M. (1976). New directions in cryptography. IEEE Transactions on Information Theory. ↩︎
3. Si le quitamos el cero al cuerpo finito $\mathbb{F}_p$, este conjunto con la multiplicación será un grupo abeliano. ↩︎
4. La fórmula representa el tiempo esperado de ejecución del algoritmo. ↩︎
5. Ver 3.7.1 en Menezes, A. J., van Oorschot, P. C., & Vanstone, S. A. (1996). Handbook of Applied Cryptography. CRC Press. ↩︎
6. Gordon, D. M. (1993). Discrete logarithms in finite fields using the number field sieve. SIAM Journal on Discrete Mathematics. ↩︎
7. Sección 4.1.2 en Hankerson, D., Menezes, A. J., & Vanstone, S. (2004). Guide to Elliptic Curve Cryptography. Springer Science & Business Media. ↩︎
8. Boudot, F., Gaudry, P., Guillevic, A., Heninger, N., Thomé, E., & Zimmermann, P. (2020). Comparing the difficulty of factorization and discrete logarithm: A 240-digit experiment. En A. Canteaut & Y. Ishai (Eds.), Advances in Cryptology – EUROCRYPT 2020 (pp. 62–91). Springer. ↩︎
9. Gaudry, P., Kleinjung, T., Vercauteren, F., & Zimmermann, P. (2016). Discrete logarithm records. En T. Peyrin (Ed.), Fast Software Encryption – FSE 2016 (pp. 3–27). Springer. ↩︎
10. NIST Special Publication 800-57 Part 1 Rev. 5. «Recommendation for Key Management». ↩︎