Integral

El sistema de clave pública más usado es el RSA [13] que está basado en la dificultad Computacional de factorizar un número n, suficientemente grande, en sus factores primos. En el RSA se elige n = pq siendo p y q primos muy grandes. Un primer ataque al RSA consiste en factorizar el entero n. Los algoritmos de factorización de enteros y los tests de primalidad (basados en teoría de números, engeometría algebraica,...) son, y han sido, aplicaciones de resultados matemáticos teóricos. Desde el punto de vista de la implementación, los algoritmos más eficientes de factorización son la criba cuadrática, las cribas de cuerpos de números (basado en cálculos en anillos de enteros algebraicos) y el algoritmo basado en curvas elípticas introducido por Lenstra. El último entero factorizado usado enRSA es de 576 bits. Este es el motivo de que en la actualidad se recomiende usar p y q de tamaño de 576 bits y n de 1024 bits como módulo, (incluso algunas agencias estatales proponen que n tenga 2048 bits). Desde el punto de vista teórico, cabe resaltar, el algoritmo AKS que permite saber si un entero es primo usando un algoritmo de complejidad polinomial. Sin embargo, por lo general, losataques que más exitosos se deben al mal uso de los parámetros del RSA [8]. Para su implementación
práctica matemáticos e ingenieros deben trabajar juntos en resolver el problema de encontrar la relación entre efectividad y seguridad pública es el problema del logaritmo discreto. En general, si (G, ·) es un grupo cíclico finito de orden n generado por a, i.e. G = {a, a2, . . . , an−1, an = 1}, y dado x∈ G el problema consiste en encontrar k tal que x = ak. Para que un grupo (G, ·) se pueda usar en criptografía debe verificar las siguientes propiedades: i) los elementos del grupo deben ser expresados de un modo compacto, ii) la operación del grupo debe ser computada eficientemente, iii) el problema de logaritmo discreto debe ser intratable en G. En el año 1976, Diffie-Helmman establecieron unprotocolo de intercambio de claves basado en el problema del logaritmo discreto sobre el grupo de unidades del cuerpo finito Fp. En la actualidad y conociendo los resultados matemáticos actuales, los grupos que se usan en la práctica son los siguientes:
1) (G, ·) = (F∗q , ·), donde F∗q es el grupo de unidades del cuerpo finito Fq con q = p con p
Primo o q = 2n.
2) (G, ·) = (E(Fq),+), dondeE(Fq) es el conjunto de puntos racionales de una curva elíptica
Sobre el cuerpo finito Fq, con q = p con p primo o q = 2n.
El algoritmo más eficiente para resolver el problema del logaritmo discreto en los grupos
De tipo 1) es el algoritmo del cálculo del índice, que es sub-exponencial. En general para los de tipo 2) no existen tales algoritmos y la complejidad de los algoritmos conocidos esexponencial.
Esto hace que los sistemas basados en curvas elípticas proporcionen la misma seguridad con tamaños de clave mucho menores, por ejemplo una clave de curva elíptica de 163 bits proporciona la misma seguridad que otra de 1024 bits de RSA o de tipo 1). Tamaños de clave menores implican menor tiempo de proceso y menor espacio de almacenamiento, factores fundamentales para la aplicaciónpráctica de la criptografía (por ejemplo en wireless, tarjetas electrónicas, ...),
[7].

En el año 1994 Shor [14] encontró un algoritmo de factorización que en un “ordenador cuántico" tiene complejidad polinomial. Por tanto, si se llega a construir un ordenador cuántico de tamaño industrial todos los criptosistemas y protocolos basados en el problema de la factorización o en el problema logaritmodiscreto serían inseguros. En la actualidad no se sabe si se llegará a construir un ordenador cuántico y cuando,
pero dado el interés del tema hay muchos grupos de investigación que incluyen matemáticos trabajando en ello. Hay que decir a este respecto, que ya se usa criptografía basada en fenómenos cuánticos, incluso a nivel comercial, para la transmisión de información aunque no existan todavía...