Criptografía de curva elíptica

Criptografía de curva elíptica

Criptografía de curva elíptica

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.

Contenido

Introducción

Los sistemas de 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 pública no proporciona suficiente información para determinar cuál es la clave privada. Este tipo de sistemas se basan en la dificultad de encontrar la solución a ciertos problemas matemáticos. Uno de estos problemas es el llamado logaritmo discreto. Encontrar el valor de b dada la ecuación ab = c, cuando a y c son valores conocidos, puede ser un problema de complejidad exponencial para ciertos grupos finitos de gran tamaño; mientras el problema inverso, la exponenciación discreta puede ser evaluado eficientemente usando por ejemplo exponenciación binaria

Una curva elíptica es una curva plana definida por una ecuación de la forma

 y^2 = x^3 + ax + b\,.

Con el conjunto de puntos G que forman la curva (i.e., todas las soluciones de la ecuación más un punto O, llamado punto en el infinito) más una operación aditiva +, se forma un grupo abeliano. Si las coordenadas x e y se escogen desde un campo finito, entonces estamos en presencia de un grupo abeliano finito. El problema del logaritmo discreto sobre este conjunto de puntos (PLDCE) se cree que es más difícil de resolver que el correspondiente a los campos finitos (PLD). De esta manera, las longitudes de claves en criptografía de curva elíptica pueden ser más cortas con un nivel de seguridad comparable.

Introducción Matemática

Sea p > 3 primo. La curva elíptica E y2 = x3 + ax + b sobre \mathbb{Z}_p es el conjunto de soluciones (x, y) \in \mathbb{Z}_p \times \mathbb{Z}_p en la congruencia

y^2 = x^3 + ax + b \pmod p\,,

donde a, b \in \mathbb{Z}_p son constantes tal que 4a^3+27b^2 \neq 0 \pmod p

Se define una operación aditiva como sigue: Considerando que

P = (x1,y1)

y

Q = (x2,y2)

son puntos en E y \mathcal{O} es un punto en el infinito. Si x2 = x1 e y2 = − y1, entonces P + Q = \mathcal{O}; de lo contrario P + Q = (x3,y3), donde

x3 = λ2x1x2,
y3 = λ(x1x3) − y1,

y

\lambda = \begin{cases} \cfrac{y_2 - y_1}{x_2 - x_1}, & \mbox{si }P \neq Q \\ \cfrac{3x_1^2 + a}{2y_1}, & \mbox{si }P = Q \end{cases}.

Finalmente, definimos

 P + \mathcal{O} = \mathcal{O} + P = P \ \forall P \in E.

Con esto se puede mostrar que E es un grupo abeliano con elemento identidad \mathcal{O}. Cabe notar que la inversa de (x, y) (que se escribe como -(x, y) ya que la operación es aditiva) es (x, -y), para todo (x, y) \in E

De acuerdo al teorema de Hasse, el número de puntos #E que contiene E es cercano a p. Más precisamente se satisface la siguiente desigualdad

 p + 1 - 2 \sqrt{p} \leq \# E \leq p + 1 + 2 \sqrt{p}.

Como se sabe que cualquier grupo de orden primo es cíclico, lo que se requiere es encontrar un subgrupo de E de orden q (q primo) para tener un isomorfismo con \mathbb{Z}_q donde el problema del logaritmo discreto sea intratable. En este caso, siendo α un generador del grupo cíclico (el cual puede ser cualquier elemento del grupo distinto de \mathcal{O}, la identidad), se pueden calcular las "potencias" de α(las que se escriben como múltiplos de α, debido a que la operación del grupo es aditiva).

Ejemplo

Sea E la curva elíptica y2 = x3 + x + 6 sobre \mathbb{Z}_{11}. Se calculan los puntos sobre E verificando los posibles valores de x \in \mathbb{Z}_{11} , y luego verificando si z = x3 + x + 6(mod 11) es un residuo cuadrático. Los valores se tabulan en la siguiente Tabla,

x x3 + x + 6(mod 11) y
0 6
1 8
2 5 4, 7
3 3 5, 6
4 8
5 4 2, 9
6 8
7 4 2, 9
8 9 3, 8
9 7
10 4 2, 9

Como E tiene 13 puntos, sigue que es cíclico e isomorfo a \mathbb{Z}_{13}. Considerando el generador α = (2,7), entonces :2α = (2,7) + (2,7)

λ  = (3 \times 2^2 + 1)(2 \times 7)^{-1} \pmod{11}
 = 2 \times 3^{-1} \pmod{11}
 = 2 \times 4 \pmod{11}
= 8

Entonces tenemos

x3 = 82 − 2 − 2(mod 11) = 5

y

y3 = 8(2 − 5) − 7(mod 11) = 2

Por lo tanto 2α = (5,2)

Uso en criptografía

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 da 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 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.

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

Enlaces externos

Obtenido de "Criptograf%C3%ADa de curva el%C3%ADptica"

Wikimedia foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Mira otros diccionarios:

  • Criptografía de curva elíptica — 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… …   Enciclopedia Universal

  • Curva elíptica — Saltar a navegación, búsqueda En matemáticas, las curvas elípticas se definen mediante ecuaciones cúbicas (de tercer grado). Han sido usadas para probar el último teorema de Fermat y se emplean también en criptografía (para más detalles ver el… …   Wikipedia Español

  • Criptografía en teléfono móvil e internet — Saltar a navegación, búsqueda Criptografía en telefonía móvil e internet Contenido 1 Criptografía 2 Telefonía móvil 3 Internet 3.1 …   Wikipedia Español

  • Criptografía asimétrica — La criptografía asimétrica es el método criptográfico que usa un par de claves para el envío de mensajes. Las dos claves pertenecen a la misma persona que ha enviado el mensaje. Una clave es pública y se puede entregar a cualquier persona, la… …   Wikipedia Español

  • Criptografía — La máquina alemana de cifrado Lorenz, usada en la Segunda Guerra Mundial para el cifrado de los mensajes para los generales de muy alto rango. La criptografía (del griego κρύπτω krypto, «oculto», y γράφως graphos, «escribir», literalmente… …   Wikipedia Español

  • Complejidad y criptografía — La criptografía es la ciencia encargada del estudio y diseño de sistemas que permiten ocultar información. Desde sus inicios, esta capacidad de encubrimiento se ha basado en la dificultad que supondría a una entidad no autorizada el obtener la… …   Wikipedia Español

  • Clave (criptografía) — Para otros usos de este término, véase clave. Una clave, palabra clave o clave criptográfica es una pieza de información que controla la operación de un algoritmo de criptografía. Habitualmente, esta información es una secuencia de números o… …   Wikipedia Español

  • Algoritmo criptográfico — En computación y criptografía un algoritmo criptográfico es un algoritmo que modifica los datos de un documento con el objeto de alcanzar algunas características de seguridad como autenticación, integridad y confidencialidad. Clasificación Los… …   Wikipedia Español

  • PKCS — En criptografía, PKCS (Public Key Cryptography Standards) se refiere a un grupo de estándares de criptografía de clave pública concebidos y publicados por los laboratorios de RSA en California. A RSA Security se le asignaron los derechos de… …   Wikipedia Español

  • Java Card — es una tecnología que permite ejecutar de forma segura pequeñas aplicaciones Java (applets) en tarjetas inteligentes y similares dispositivos empotrados. Java Card da al usuario la capacidad de programar aplicaciones que se ejecutan en la tarjeta …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”