«Las curvas elípticas de coeficientes racionales … son modulares».
Sección 3.5 Más allá de lo no resuelto
Si el contenido teórico de todo lo anterior le parece unos galimatías inentendibles, entonces además del teorema Mordell-Weil, asuma como cierta la conjetura de Shimura y Taniyama (1955) —ahora: Teorema de la Modularidad— la cual está fuera de las posibilidades del autor para explicarla; en otros términos. Considérela como cierta, ya que los matemáticos Andrew Wiles y Richard Taylor probaron un caso especial de dicha conjetura (para las curvas elípticas semiestables definidas sobre los racionales). Avance considerable, y suficiente para que A. Wiley en 1995 demuestre (por reducción al absurdo) la veracidad de la conjetura mediante el conocido «último teorema de Fermat»; tres siglos y medio después que fuera garabateado por Fermat en el margen de una copia de la Aritmética de Diofanto 1 ; finalmente teorema (ya no más conjetura).
Subsección 3.5.1 La conjetura de Taniyama-Shimura-Weill
La conjetura origina de Taniyama-Shimura; extendida por Wiles 2 , es ahora conocida como «teorema de la modularidad»; luego que fuera demostrada en 2001 (para todas las curvas elípticas definidas sobre los racionales) por los matemáticos Christophe Breuil, Brian Conrad, Fred Diamond y Richard Taylor.
Teorema 3.5.1. de la Modularidad.
Para toda curva elíptica \(E\) con coeficientes racionales, existe una forma modular \(f\) (de peso 2) tal que la serie \(L\) asociada a \(E\) y la serie \(L\) asociada a \(f\) coinciden [23]. Esto equivale a que los coeficientes \(a_{p}\) asociados a la curva \(E\) (que se obtiene a partir del número de puntos de la curva módulo \(p\text{,}\) para \(p\) primo de buena reducción de \(E\)) coinciden con los coeficientes de Fourrier en el infinito de \(f\text{.}\)
Subsección 3.5.2 El Logaritmo Discreto
El logaritmo discreto implica encontrar el exponente al cual se ha elevado un número para obtener otro número en un conjunto finito; operación conocida por ser difícil de resolver eficientemente, especialmente cuando se trabaja con números grandes y primos. Básicamente es la operación inversa de la exponenciación discreta que eleva un número a una potencia en un conjunto finito.
Las curvas elípticas definidas sobre cuerpos finitos \(\mathbb{F}_q\) siendo \(q
= p^m\) y \(p\) un número primo, proporcionan grupos finitos de gran interés criptográfico debido a la dificultad que tiene el problema del logaritmo discreto planteado sobre ellos (DLP: Discrete Logarithm Problem). Se considera el cuerpo base de \(\mathbb{F}_q\) como grande, si \(p\) es mayor o igual a \(2^{160}\) bits.
Dado una curva elíptica sobre \(\mathbb{F}_q\text{,}\) un generador \(P\) de un subgrupo cíclico \(G\) y un punto \(Q \in G\text{,}\) el problema consiste en encontrar el entero \(d\) tal que \(Q=d.P\text{;}\) por definición, \(d\) es el logaritmo discreto de \(Q\) en base \(P\text{;}\) que pudiera escribirse como \(d =
\log_PQ\text{.}\)
Como sabemos, los puntos de una curva elíptica forman un grupo respecto de la suma, y en concordancia, dado un punto generador \(P\) de un subgrupo cíclico \(G\) de una curva elíptica \(E\) definida sobre \(\mathbb{F}_q\text{,}\) podemos calcular la “multiplicación escalar”: \(P = eG\text{,}\) con \(e \in
\mathbb{Z}\text{,}\) y \(P\) vuelve a ser un punto de la curva \(E\text{.}\)
La multiplicación escalar y el logaritmo discreto son operaciones inversas entre sí en el contexto de curvas elípticas, y ambas tienen aplicaciones importantes en criptografía.
Factorización imposible.
Se puede calcular \(Q = d.P\) de forma eficiente; conocido \(P\) y \(d\text{.}\) Pero es absolutamente imposible (en términos prácticos), hallar \(d\) a partir de valores conocidos de \(P\) y \(Q\text{;}\) básicamente debido a que no se cuentan con algoritmos rápidos y eficientes para factorizar grandes números.
Lo que resulta esencialmente útil para la seguridad criptográfica es la imposibilidad práctica (y teórica) del procedimiento inverso al considerar la forma exponencial discreta: \(q=p^m\text{;}\) con \(p\) primo y \(m \in \mathbb{N}\) para \(Q \in G\) de orden \(n\) (normalmente un primo 3 ). Para grandes números como los \(p^m\) seleccionados para operar en criptografía, no sabemos cómo resolver lo que en esencia es un problema logarítmico.
Las curvas elípticas ofrecen una forma eficaz de implementar algoritmos de firma digital y sistemas criptográficos de clave pública. La dificultad del problema del logaritmo discreto en curvas elípticas proporciona una capa adicional de seguridad, lo que significa que es computacionalmente costoso invertir la función utilizada para generar claves; permiten el uso de claves más cortas en comparación con otros sistemas criptográficos, para lograr el mismo nivel de seguridad. Esto es crucial en el contexto de las criptomonedas, ya que reduce la cantidad de datos que deben transmitirse y almacenarse, mejorando la eficiencia de la red. Por estas y otras razones, aunque la computación cuántica podría representar una amenaza para algunos algoritmos criptográficos, las curvas elípticas son una opción resistente a los ataques cuánticos; proporcionan una capa adicional de seguridad en un entorno de computación cuántica.
La complejidad computacional que implica invertir las operaciones matemáticas utilizadas en estos algoritmos que usan curvas elípticas (ECDLP), incluso con una computadora cuántica, sigue siendo un desafío significativo debido a las propiedades matemáticas de ellas.
La complejidad específica varía según el algoritmo utilizado. Para los tamaños de clave típicos utilizados en la práctica \(\geq 2^{160}\) (frecuentemente: 256 bits o 521 bits), resolver el logaritmo discreto en una computadora clásica puede ser extremadamente difícil y llevaría un tiempo significativo, incluso con los mejores algoritmos actuales [Figura 4.6].
El algoritmo de Shor 4 es exponencialmente más eficiente que los mejores algoritmos clásicos conocidos. En una computadora cuántica, los algoritmos clásicos eficientes para resolver problemas ECDLP tienen complejidad exponencial. En contraste, el algoritmo de Shor que puede resolver el logaritmo discreto en un tiempo polinómico (la complejidad temporal del algoritmo está descrita por una función polinómica en términos del tamaño de la entrada). Aunque se avanza significativamente en el campo de la computación cuántica, aún no se alcanza un nivel que comprometa la criptografía basada en curvas elípticas de manera eficiente (con utilidad práctica).
Nota 3.5.2.
En la práctica el algoritmo de Shor, ha sido probado experimentalmente: el número \(15\) se factorizó correctamente desde el 2001; usando siete qubits, en 2007 con cuatro qubits de fotones, en 2012 con 3 qubits de estado sólido y en 2016 con cinco qubits de iones. El número \(21\) se factorizó en 2012 usando un fotón qubit y un qutrit (un sistema de tres niveles). Todas esas demostraciones experimentales del algoritmo de Shor; se basaron en el conocimiento previo de los resultados precompilados. En general, para cualquier entero \(N\text{,}\) se requieren \(2 + \frac{3}{2} \log_2N \) qubits para factorizarlo [8].
El tiempo estimado para resolver el problema del logaritmo discreto en una computadora cuántica dependerá del tamaño del grupo cíclico y de la capacidad cuántica de la computadora.
