Criptografía de curva elíptica
De Wikipedia, la enciclopedia libre
La Criptografía de Curva Elíptica (CCE) es una variante de la criptografía asimétrica o de clave pública basada en las matemáticas de las curvas elípticas. Sus autores argumentan que la CCE puede ser más rápida y usar claves más cortas que los métodos antiguos — como RSA — al tiempo que proporcionan un nivel de seguridad equivalente. La utilización de curvas elípticas en criptografía fue propuesta de forma independiente por Neal Koblitz y Victor Miller en 1985.
La criptografía asimétrica o de clave pública utiliza dos claves distintas: una de ellas puede ser pública, la otra es privada. La posesión de la clave publica no proporciona suficiente información para determinar cuál es la clave privada.
Existen varias versiones de criptografía de curva elíptica con pequeñas variaciones, todas ellas basadas en la creencia ampliamente extendida de la dificultad de resolver el problema de un logaritmo discreto para el grupo de una curva elíptica sobre algunos grupos finitos. Los grupos finitos más usados para ello son los enteros módulo un número primo (véase aritmética modular), o un grupo de Galois de tamaño potencia de dos. También se han propuesto grupos de Galois de tamaño de la potencia de algún otro primo, pero son considerados dudosos entre los criptoanalistas.
Dada una curva elíptica E, y un grupo GF(q), consideramos el grupo abeliano de puntos racionales E(q) de la forma (x, y), donde x e y pertenecen a GF(q), y donde el grupo operación "+" se define en esta curva cómo se describe en el artículo curva elíptica. Definimos entonces una segunda operación "*" | Z×E(q) → E(q): si P es algún punto en E(q), entonces definimos 2*P = P + P, 3*P = 2*P + P = P + P + P, y así en adelante. Nótese que dados los enteros j y k, j*(k*P) = (j*k)*P = k*(j*P). El problema del logaritmo discreto de una curva elíptica (PLDCE) es pues determinar el entero k, dados los puntos P y Q, cuando k*P = Q.
Se cree que el típico problema del logaritmo discreto sobre el grupo multiplicativo (PLD) y el PLDCE no son problemas equivalentes, y que el PLDCE es significativamente más difícil que el PLD.
En el uso criptográfico, se elige un punto base G específico y publicado para utilizar con la curva E(q). Se escoge un número entero aleatorio k como clave privada, y entonces el valor P = k*G se dá a conocer como clave pública (nótese que la supuesta dificultad del PLDCE implica que k es difícil de deducir a partir de P). Si María y Pedro tienen las claves privadas kA y kB, y las claves públicas PA y PB, entonces María podría calcular kA*PB = (kA*kB)*G; y Pedro puede obtener el mismo valor dado que kB*PA = (kB*kA)*G.
Esto permite establecer un valor "secreto" que tanto María como Pedro pueden calcular fácilmente, pero que es muy complicado de derivar para una tercera persona. Además, Pedro no consigue averiguar nada nuevo sobre kA durante ésta transacción, de forma que la clave de María sigue siendo privada.
Los métodos utilizados en la práctica para cifrar mensajes basándose en este valor secreto consisten en adaptaciones de antiguos criptosistemas de logaritmos discretos originalmente diseñados para ser usados en otros grupos. Entre ellos se podrían incluir Diffie-Hellman, ElGamal y DSA.
La realización de las operaciones necesarias para ejecutar este sistema es más lenta que para un sistema de factorización o de logaritmo discreto módulo entero del mismo tamaño. De todas maneras, los autores de sistemas de CCE creen que el PLDCE es significativamente más complicado que los problemas de factorización o del PLD, y así se puede obtener la misma seguridad mediante longitudes de clave mucho más cortas utilizando CCE, hasta el punto de que puede resultar más rápido que, por ejemplo, RSA. Los resultados publicados hasta la fecha tienden a confirmar esto, aunque algunos expertos se mantienen escépticos.
La CCE ha sido ampliamente reconocida como el algoritmo más fuerte para una determinada longitud de clave, por lo que podría resultar útil sobre enlaces que tengan requisitos muy limitados de ancho de banda.
NIST y ANSI X9 han establecido unos requisitos mínimos de tamaño de clave de 1024 bits para RSA y DSA y de 160 bits para ECC, correspondientes a un bloque simétrico de clave de 80 bits. NIST ha publicado una lista de curvas elípticas recomendadas de 5 tamaños distintos de claves (80, 112, 128, 192, 256). En general, la CCE sobre un grupo binario requiere una clave asimétrica del doble de tamaño que el correspondiente a una clave simétrica.
Certicom es la principal empresa comercial de CCE, esta organización posee 130 patentes, y ha otorgado licencias sobre tecnología a la National Security Agency (NSA) por 25 millones de dólares. Certicom también ha patrocinado varios desafíos al algoritmo CCE. El más complejo resuelto hasta ahora, es una clave de 109 bits, que fue roto por un equipo de investigadores a principios de 2003. El equipo que rompió la clave utilizó un ataque masivo en paralelo basado en el 'birthday attack', mediante más de 10000 PC's de tipo Pentium funcionando continuamente durante 540 días. Se estima que la longitud de clave mínima recomendada para CCE (163 bits) requeriría 108 veces los recursos utilizados para resolver el problema con 109 bits.
[editar] Referencias
- Neal Koblitz, "Elliptic curve cryptosystems", Mathematics of Computation 48, 1987, pp203–209.
- V. Miller, "Use of elliptic curves in cryptography", CRYPTO 85, 1985.
- Blake, Seroussi, Smart, "Elliptic Curves in Cryptography", Cambridge University Press, 1999
- Hankerson, Menezes, Vanstone: "Guide to Elliptic Curve Cryptography", Springer-Verlag, 2004
[editar] Enlaces externos
- Recommended Elliptic Curves for Government Use, NIST document (PDF file)
- Certicom press release regarding 109 bit ECC challenge
- Certicom Online ECC Tutorial
- Digital Signature Standard; includes info on ECDSA
- libecc: Open source ECC library
- Demo of elliptic curve point counting and domain parameter generation
- eccGnuPG: Parche experimental para el GnuPG
