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.
Este tipo de sistemas se basa 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
, 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 la exponenciación binaria.
Una curva elíptica es una curva plana definida por una ecuación de la forma 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 cuerpo 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 cuerpos finitos (PLD).
, donde y Finalmente, definimos Con esto se puede mostrar que E es un grupo abeliano con elemento identidad
donde el problema del logaritmo discreto sea intratable.
, debido a que la operación del grupo es aditiva).
Se calculan los puntos sobre E verificando los posibles valores de
, sigue que es cíclico e isomorfo a
En criptografía, 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).
Esto permite establecer un valor «secreto» que tanto Alicia como Bernardo pueden calcular fácilmente, pero que es muy complicado de derivar para una tercera persona.
Además, Bernardo no consigue averiguar nada nuevo sobre kA durante esta transacción, de forma que la clave de Alicia 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.
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 Agencia de Seguridad Nacional (NSA) por 25 millones de dólares.
Certicom también ha patrocinado varios desafíos al algoritmo CCE.
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.
Cuando el ECC es utilizado en máquinas virtuales, un atacante puede usar una curva inválida para obtener por completo una clave privada de tipo PDH.