Introducción a la Criptografía de Curvas Elípticas

(Curvas Elípticas aplicadas a la criptografía asimétrica o de clave pública)

Carlos A. Escobar González
[email protected]
Nro. Carnet: 07-85718

Resumen

El uso de técnicas criptográficas tiene como propósito prevenir algunas fallas de seguridad en un
sistema automatizado. La seguridad en general debe ser considerada como un aspecto de gran
importancia en cualquier corporación que trabaje con sistemas computarizados. El hecho que gran
parte de actividades humanas sea cada vez más dependiente de los sistemas computarizados hace que la
seguridad juegue un papel importante, al punto en que se han creado políticas de aseguramiento de la
información tanto a nivel físico, en donde el acceso a los equipamientos computacionales es
resguardado, como a nivel lógico donde entra en juego el ámbito de la criptografía. Dentro de los
métodos criptográficos de cifrado encontramos los sistemas simétricos y los sistemas asimétricos, los
cuales difieren en el manejo de las claves que hacen posible sus respectivos procesos de cifrado y
descifrado. Ambos tipos criptográficos logran satisfacer algunos de los principios básicos de la
seguridad informática como la confidencialidad e integridad, sin embargo, para el caso de los sistemas
asimétricos también se logra satisfacer el principio básico de la irrefutabilidad o no repudio de la
información. Los métodos de clave pública más utilizados son el RSA, para encriptado y firma digital, el
Dffie-Hellman para acuerdo de claves y el DSA para firmas digitales. Sin embargo, con el incremento
de la capacidad de cómputo actual existen algoritmos matemáticos que resuelven estos métodos y por
lo tanto es necesario aumentar el tamaño de las claves, lo que implica un mayor costo de
procesamiento. En 1985, Neil Koblitz y Victor Miller, de forma independiente, propusieron el
criptosistema de curva elíptica (ECC: Elliptic Curve Cryptosystem), cuya seguridad computacional se
basa en el Problema del Logaritmo Discreto, lo cual permite utilizar claves de tamaño más pequeñas
que otros algoritmos de clave pública, permitiendo su implementación en aplicaciones donde los
recursos de computación son limitados tales como smart cards y teléfonos celulares.
En este trabajo conoceremos qué son las curvas elípticas y como pueden ser usadas para construir
criptosistemas de clave pública. Primero se presenta un marco teórico donde se detallan las nociones
matemáticas que dan origen a las curvas elípticas y el problema del Logaritmo Discreto y su análogo
sobre curvas elípticas. A continuación se describen la teoría de criptografía de clave pública, se detalla la
criptografía ECC y se realiza una comparación con el sistema de clave pública RSA. Luego se
especifican los estándares de los criptosistemas ECC incluidos en NIST y ANSI, incuyendo el IEEE
P1363. Posteriormente se realiza una descripción de algunos algoritmos basados en ECC como
ElGamal y un ejemplo de esquema de firma digital. El uso de las curvas elípticas actualmente está
adquiriendo una gran difusión de su uso, es por ello que describiremos las ventajas y desventajas de su
implementación tanto en la parte de seguridad como en el campo económico. A continuación se
describen algunas implementaciones de ECC en la industria del hardware y del software que dan una
visión de su importancia y posteriormente se habla de la empresas públicas y privadas que actualmente
desarrollan productos con ECC, en el caso de empresas privadas Certicom y a nivel de gobiernos la
NSA de EEUU con su Suite B que es un estándar federal para la seguridad en las comunicaciones
clasificadas y no clasificadas basada en ECC. Para finalizar se presentan algunos desafíos resueltos y
otros por resolver relacionados con la criptografía de curvas elípticas.

1
Introducción

La criptografía de clave pública se ideo con el objetivo de solucionar dos de los grandes problemas
asociados a la criptografía pública: La distribución y gestión de claves y la firma digital [1].
El primer sistema de clave pública fue el Diffie Hellman, publicado en mayo de 1976 [2], basado en el
problema de logaritmo discreto (DLP) y el objetivo es el acuerdo de clave entre dos usuarios. En 1978
aparece el RSA, creado por Rivest, Shamir y Adleman y utiliza el problema de la factorización de
enteros (IFP) como la base matemática [3].
Como una opción, en 1985, Neil Koblitz y Victor Miller (independientemente) propusieron el Elliptic
Curve Cryptosystem (ECC)[4], o Criptosistema de Curva Elíptica, cuya seguridad descansa en el mismo
problema que los métodos de Diffie-Hellman y DSA la base matemática del problema del logaritmo
discreto adaptado a las curvas elípticas llamado ECDLP, pero en vez de usar números enteros como los
símbolos del alfabeto del mensaje a encriptar (o firmar), usa puntos en un objeto matemático llamado
Curva Elíptica. ECC puede ser usado tanto para encriptar como para firmar digitalmente.
La criptografía de curvas elípticas (ECC) son los criptosistemas más recientes dentro del campo de los
sistemas de clave pública y representan sólo otra forma de implementar métodos de logaritmo discreto.
Las curvas elípticas en criptografía son básicamente un conjunto de puntos que cumplen la y2 = x3 + ax
+ b siempre que sean considerados en un cuerpo finito de característica p (con p > 3). Para
características del cuerpo p = 2 y p = 3 se requiere una ecuación ligeramente diferente.

Los puntos de una curva elíptica forman una estructura llamada grupo (concretamente son un grupo
abeliano). Esto significa que podemos realizar las operaciones aritméticas de suma y resta con ellos del
mismo modo que lo hacemos con los enteros.

Además de presentar algunas ventajas teóricas son muy prácticas. No existe ningún algoritmo rápido de
cálculo de un logaritmo, lo cual supone que el tamaño de la clave, así como las firmas digitales y
mensajes cifrados obtenidos son pequeños. De hecho, los criptosistemas basados en curvas elípticas
proporcionan la misma seguridad que los basados en factorización o logaritmo discreto reduciendo
considerablemente el número de dígitos.

Las curvas elípticas pueden ser implementadas con gran eficiencia en hardware y software, y son
capaces de competir en velocidad con sistemas como RSA y DSS. En general se cree que son bastante
seguros, pero no ha sido demostrado. Sí se sabe que existe un tipo de curvas que recientemente se ha
revelado extremadamente vulnerable, por lo que éstas no deben usarse en criptografía. Y de entre los
demás tipos de curvas se deberá examinar cuidadosamente antes de elegir uno concreto para
comprobar su idoneidad como base para un código de cifrado de datos.

Marco Teórico
Una curva elíptica es una ecuación de la forma

donde x e y son las indeterminadas y a1, a2, a3, …, a5, son elementos constantes de un campo.

Aunque esta ecuación puede ser estudiada sobre varias estructuras algebraicas, como un anillo o campo;
para nuestros propósitos, consideraremos solamente las curvas elípticas sobre un campo. En este caso,
los coeficientes ai son elementos del campo, y nuestra tarea es encontrar pares (x; y) con x e y en el
campo, que satisfagan la ecuación.

Para entender de que estamos hablando, consideremos el campo de los números reales R. Podemos
obtener un gráfico de la curva elíptica fiando un x y resolviendo la ecuación cuadrática en y. Veamos
como quedará el gráfico de la siguiente curva:

2
donde a1= a2 = a3 = 0, a4=-4 y a5=0,67
En la Figura 1 se muestra el gráfico resultante

Figura 1. Gráfico de una Curva Elíptica[8]

El grafico consiste de dos partes separadas, aunque podrán estar pegadas por un solo punto, o bien
consistir solamente de una parte, en forma de “campana”. Veremos que el conjunto de soluciones de
una curva elíptica tiene propiedades interesantes. En particular, se puede hacer del conjunto un grupo,
es decir proveer al conjunto de una operación binaria y un elemento identidad, lo cual nos habilita para
hacer criptografía.
Yendo al caso de los números reales, se podrá probar que si x3 +ax+b no tiene factores repetidos, o
equivalentemente 4a3 +27b2 6 ≠ 0, entonces las curvas elípticas de la forma y2 = x3 + ax + b forman un
grupo.

Entonces, pasemos a definir la operación, siguiendo la Figura 2. Tome dos puntos P y Q de la curva, y
trace la línea que pasa por ambos puntos. En el caso general esta línea siempre tiene un punto de
intersección con la curva. Ahora tome este tercer punto en la intersección de la línea con la curva y
trace una línea vertical. El otro punto R de intersección con la curva de esta línea vertical se define
como la suma de P y Q, en símbolos, R = P + Q.
La Figura 2 también nos muestra como definimos el elemento opuesto -R a un punto R de la curva:
simplemente, el punto opuesto a R = (x; y) es el punto -R = (x;-y)
Si P1 = P2, es decir que queremos obtener R = P + P (vea Figura 3), entonces la línea a ser construida
en el primer paso es la tangente a la curva, el cual otra vez tiene otro punto de intersección con la curva.
Note que el grupo es conmutativo.

Figura 2. Suma de P y Q [8], Figura 3. Suma del mismo punto P. [8]

3
Una parte compleja es definir el elemento identidad del grupo. La pregunta a responder es: ¿Qué punto
de la curva sumado a un punto P cualquiera resulta en el punto P? Solamente podemos encontrar una
respuesta a esta pregunta si un punto extra es agregado a la curva. Este punto extra se llama punto en el
infinito, y se lo designa con O.

El punto O está en un lugar infinitamente lejos sobre el eje vertical, y es la identidad del grupo de la
curva elíptica. Por ejemplo, observe el punto P en Figura 4. Dada la definición del elemento identidad
(o elemento nulo), P + (-P) = O. Observe también (ver Figura 5) el caso especial en el que queremos
obtener el punto P +P = 2P, donde la recta tangente a la curva en el punto P es la recta vertical (lo cual
sucede solo cuando P = (x; y) con y = 0); en este caso también obtenemos 2P = O.

Figura 4. Suma del punto P con su opuesto Figura 5. Suma del punto P=(x,y) con si
mismo, y = 0

Puede demostrarse que la operación de suma es una operación binaria de grupo bien definida, aunque
algunos de los requerimientos (por ejemplo asociatividad) no son nada fáciles de probar. Aunque
anteriormente dimos una definición general de las curvas elípticas, no se considera práctico utilizarlas
en forma general, ni tampoco utilizarla en el campo de los R, debido a los errores de redondeo y
truncamiento de los valores. Por eso, aquí se consideran las curvas elípticas definidas sobre Zp donde p
es un número primo impar y sobre los campos finitos de la forma F2m; m≥1, ya que estos conjuntos
producen las implementaciones más eficientes de la aritmética de curva elíptica [9].

Curvas Elípticas sobre Zp. Una curva elíptica E sobre Zp, denotada E(Zp) es definida por la ecuación de
la forma
y2 ≡ x3 + ax + b (mod p)

donde a; b Zp, y 4a3 + 27b2 0 (mod p), junto con el punto en el infinito O. El conjunto E(Zp) consiste
de todos los puntos (x; y); x Zp; y Zp, los cuales satisfacen la Ecuación.
Veamos un ejemplo: Si p = 23, y consideramos la curva elíptica E : y2 = x3 + x + 1 definida sobre Z23
donde las constantes usadas fueron a = b = 1. Note que 4a3 + 27b2 = 4 + 4 = 8 ≠ 0 (mod 23), de
manera que en realidad es una curva elíptica.

Curvas Elípticas sobre F2m. Los campos finitos de la forma F2m con m≥1 son convenientes de usar,
puesto que sus elementos encajan a la perfección en una palabra de datos de longitud m bits. Esto es
porque los elementos de F2m son representados por el conjunto de polinomios binarios de grado ≤ m-1:

4
donde estos polinomios se representan en la computadora por la palabra de datos de m bits (am-1 am-2 am-
3 … a1 a0).

Parámetros del Dominio de Curvas Elípticas.

Los parámetros del dominio de las curvas elípticas son los valores básicos necesarios para definir el
campo finito a usar, los valores a y b que definen la curva, etc. Aunque pueden ser generados por
cualquier entidad, en Internet seguramente los generará una Autoridad Certificadora (AC). Debe
notarse que estos parámetros deben ser compartidos por las partes que quieren comunicarse, de manera
que en general se trata de utilizar siempre los mismos parámetros recomendados por las organizaciones
productoras de estándares

Parámetros de dominio para curvas sobre Fp. Los parámetros que definen el dominio de las curvas elípticas
sobre Fp son una séxtupla:

T = (p; a; b; G; n; h)

consistiendo de un número entero primo p que especifica el campo finito Fp, dos elementos a; b  Fp
especificando una curva elíptica E(Fp) definida por la ecuación

E : y2 ≡ x3 + ax + b (mod p);

un punto base G = (xG; yG) E(Fp), un número primo n el cual es el orden de G, y un número entero h
que es el cofactor h = #E(Fp)/n. La función que cumplen p; a; b son las constantes que definen el
tamaño en bits de los puntos y la forma de la curva.
El punto base G es un punto de referencia que se proporciona para poder hacer criptografía. Es el
análogo del generador en el DLP. El número n es el orden de G, o sea n es tal que nG = O. Note que
n es un número primo grande. Algo muy importante que no siempre se dice es que el orden de G debe
ser lo suficientemente grande como para que sea impráctico buscar todos los múltiplos G; 2G;… ; (n-1)
G de G. De hecho, el GDLP depende, además de otros factores, de que el orden n de G sea grande (en
el DLP,el orden del elemento generador queda implícitamente definido por el tamaño de p.)

Dependiendo del nivel de seguridad que se intenta conseguir, el número primo p de Zp se suele elegir
de manera que:

log    {112; 128; 160; 192; 224; 256; 384; 521}

Esto representa el tamaño en bits de p. Note la aparición del número 521, en vez de 512; esto es un
requerimiento que aparece en parámetros estándares de seguridad del gobierno de U.S.

Las Primitivas Diffie-Hellman de Curvas Elípticas son la base para operación del ECAES (Elliptic
Curve Augmented Encryption Scheme), y el Esquema Diffie-Hellman de curvas elípticas. Se
especifican dos primitivas: la primitiva Diffie-Hellman de curva elíptica y la primitiva Diffie-Hellman de
cofactor de curva elíptica. La idea básica de ambos esquemas es la misma -generar un valor secreto
compartido a partir de una clave privada adueñada por una entidad U y una clave pública adueñada por
otra entidad V de manera que si ambas entidades ejecutan la primitiva simultáneamente con las claves
correspondientes, podrán recuperar el mismo valor secreto compartido. Sin embargo, las dos primitivas
son sutilmente diferentes: la primitiva Diffie-Hellman de curva elíptica es el análogo directo del bien
conocido protocolo de acuerdo de claves Dffie-Hellman, mientras que la primitiva Diffie-Hellman de
cofactor de curva elíptica incorpora el cofactor h en el cálculo del valor secreto compartido para
proveer una resistencia eficiente contra ataques de subgrupo pequeño. A partir de estas definiciones,
podemos ver que la construcción de un protocolo de acuerdo de claves Diffie-Hellman basado en ECC
es directa.

5
Esquemas de Firma Digital.
Dada la aceptación de los sistemas basados en curvas elípticas, recientemente el gobierno de U.S., bajo
recomendaciones del NIST (National Institute of Standards and Technology) estandarizó la segunda
versión de su estándar de DSS (Digital Signature Standard) [10], que describe ahora tanto el algoritmo
de firma digital DSA como también el ECDSA. El algoritmo DSA es una variante del esquema de
firmas de ElGamal. Este explota pequeños subgrupos en Z*p de manera de reducir el tamaño de las
firmas producidas.

Elliptic Curve DSA (ECDSA). ECDSA es el análogo sobre curvas elípticas al DSA. Esto es, en vez de
trabajar sobre el subgrupo de orden q en Z*p, se trabaja en un grupo de curva elíptica E(Zp). Como
dijimos anteriormente, el ECDSA fue estandarizado por el NIST, pero también estén en este proceso
los comités de estándares ANSI X9F1 e IEEE P1363. En concreto, el ECDSA es un esquema de firma
con apéndice basado en ECC. Está diseñado para ser existencialmente infalsificable, aún ante la
presencia de un adversario capaz de lanzar ataques de mensajes elegidos por él.

Ataques conocidos al ECDLP.

No se conocen algoritmos sub-exponenciales generales (es decir, que no exploten ninguna propiedad
de las puntos sobre curvas elípticas) para resolver el ECDLP. Más específicamente, no se conoce un
algoritmo index-calculus para el ECDLP, puesto que no se conoce el concepto de smoothness de un
punto sobre una curva elíptica . Por esta razón, se cree que el ECDLP es mucho más difícil de resolver
que el IFP o el DLP, en el sentido que no se conocen algoritmos de propósito general y tiempo sub-
exponencial para resolverlo. Los mejores algoritmos generales conocidos a la fecha están basados en el
Pollard-ρ y el Pollard-λ. El Pollard-ρ toma alrededor de /2  pasos (cada paso representa la suma de
dos puntos en una curva elíptica), y el Pollard-λ toma alrededor de 2√   pasos. Ambos métodos
pueden ser paralelizados.

Recientemente se mostró que el método Pollard-ρ puede ser acelerado por un factor de √2 . Entonces
el tiempo esperado de ejecución del método Pollard-ρ conesta mejora es de /4 pasos [6].

Comparación de las Curvas Elípticas con otros sistemas.

Compararemos como impactan los tipos de ataques conocidos en la seguridad y eficiencia de los
métodos basados en el IFP, DLP y ECDLP.
Seguridad. El primer paso en el proceso de generación de los parámetros de un esquema de ECC es
determinar el nivel de seguridad que se intenta alcanzar. Varios factores podrán influenciar esta
determinación, como el valor de la información, el tiempo que debe ser protegida, el tamaño de los
parámetros que serán usados, el nivel de seguridad provisto por el esquema, etc. Sin embargo, varias
reglas prácticas podrán ser utilizadas. Por ejemplo, se sabe que el esquema RSA con modulo de 512 bits
provee seguridad solo a corto plazo, 1024 bits de modulo es generalmente adecuada para uso general, y
2048 bits de módulo provee buena seguridad a mediano y largo plazo.
Debido a que el mejor algoritmo, actualmente conocido, para la resolución del problema en el que basa
su seguridad ECC es de orden completamente exponencial, a diferencia de los métodos usados para
romper criptosistemas como RSA cuyo orden es sub-exponencial, se puede lograr el mismo nivel de
seguridad que otros métodos con longitudes de claves menores. Ejemplo de esto es mostrado en la
Tabla 1 [7] donde vemos una comparación del tamaño necesario de los parámetros de varios esquemas
para alcanzar un nivel comparable de seguridad. En la primera columna se presenta el tamaño de un
parámetro en bits. La segunda columna lista los tamaños de claves en un esquema simétrico, luego los
tamaños de un esquema basado en ECC, y después para los esquemas RSA y DSA (utilizan el IFP y
DLP respectivamente.) Cada fila representa un nivel de seguridad comparable entre los distintos

6
método os. La concluusión que sacaamos de esta tabla es que para sistemas de clave púública, esquem mas
basadoos en ECC briindan la mismma seguridad queq los ya traddicionales, perro con un costo más reduciido
en su empleo,
e debidoo al tamaño reeducido de loss parámetros que
q utiliza.

Tabla 1.
1 Tamaños dee claves comp
parables en bits.

Eficienccia. Cuando se habla sobre eficiencia

e de un criptosistem
ma de clave púública, hay quee tener en cuen
nta
tres facctores:
Sobrecarga en cálculos: Cuanta
C compuutación se requuiere para ejecutar las transsformaciones de
clave privad
da y clave públlica.
Tamaño de clave: Cuanto os bits se reqquieren para almacenar
a p de claves y algunos otrros
el par
parámetros del sistema.
Ancho de banda: Cuantos bits deben ser s comunicaddos para transferir un menssaje encriptado oo
una firma.
A conttinuación, en lal Tabla 2, se comparan
c los métodos cripptográficos de RSA y curvass elípticas a nivvel
de seguuridad y eficienncia:

Tab
bla 2. Relación
n entre RSA y ECC.

Los criiptosistemas ded curvas elíppticas son máás eficiente co

omputacionalm
mente que los sistemas dee la
primeraa generación de clave púública RSA y Diffie-Helm man. La Tablla 3 [13] quee se muestraa a
continuuación, indicaa la rata de có
ómputo de los sistemas Diiffie-Helman versus
v los sisttemas de curvvas
elípticaas.

7
 Nivel de Seguridad Relación de Costos
(Bits) Diffie-Helman Vs Cirvas Elípticas
80 3:1
112 6:1
128 10:1
192 32:1
256 64:1
Tabla 3. Costos relativos al computo de Diffie-Helman vs Curvas Elípticas

Legislación
En cuanto a la regulación que permite el uso adecuado y optimo de los ECC se encuentran varios
estándares creados por los diferentes organismos:
La National Institute of Standards and Technology (NIST) usa los estándares que indicant cuales
algoritmos de criptografia pueden usar las agencias Federal de Gobierno tales como:
Federal Information Processing Standards (FIPS) 186-2: El estándar de firmas digitales (DSS).
Estandariza el algoritmo de firmas digitales con curvas elípticas (ECDSA) y recomienda 15
conjuntos de parámetros para los dominios de curvas elípticas.
Publicación Especial 800-56: Recomienda sobre esquemas de establecimiento de claves las
cuales incluyen ECC, ECDH
Publicación Especial 800-57: Guia para la administración de claves . Guia para el manejo
simétrico de claves,con claves públicas tales como claves ECC. Menciona los tamaños optimos
de claves para ECC.

Institute of Electrical and Electronics Engineers:

IEEE P1363. Estándar de especificaciones para criptografía de clave pública

American National Standards Institute:

ANSI X9.62. especifica ECDSA
ANSI X9.63,
ANSI TG-17
ANSI X12

La Suite B: es el nuevo conjunto de algoritmos criptográficos aprobados por la NSA como parte de su
Programa de Modernización Criptográfica. El continuo incremento de la potencia de cálculo de los
computadores amenaza las bases de los sistemas criptográficos actuales. La NIST recomienda
abandonar la criptografía de 80 bits para este año y la de 112 bits para el 2030. La progresión de uso de
los algoritmos de RSA con claves cada vez mayores, no parece sostenible. El tiempo y potencia de
cálculo requeridos a medida que crecen la longitud de las claves crece vertiginosamente. El tiempo
requerido para firmar es proporcional a la longitud de la clave elevada al cubo. Se han definido 3 curvas
y tamaños de claves: P-256, P-384 y P-521 con longitudes de claves de 256, 384 y 521 bits
respectivamente. Estas curvas equivalen a claves AES de 256, 192 y 512 respectivamente. Muchos de
los sistemas operativos actuales y restante software comercial ya incorporan estos algoritmos. Parece
probable que asistiremos en los próximos 2 o 3 años a una rápida migración de los algoritmos RSA a
esta nueva Suite-B, que realizarán operaciones criptográficas más robustas en un menor espacio de
tiempo.
International Standards Organization:
UN/EDIFACT
ISO/IEC 14888
ISO/IEC 9796-4
ISO/IEC 14946

8
Otros:
ATM Forum
WAP
El NESSIE Europeo.
El CryptRec de Japón.

Relacionado con todo lo referido a comercio electrónico, transacciones e Internet están:

FSTC ( Financial Services Technology Consortion )
OTP 0.9 (Open Trading Protocol)
SET (Secure Electronic Transactions)
IETF (The Internet Engineering Task Force)
IPSec (Internet Protocol Security Protocol)

Ventajas Económicas usando Curvas Elípticas.

Dispositivos móviles
Los dispositivos móviles son aquellos equipos diseñados específicamente para realizar funciones
específicas y de forma portable, como por ejemplo, teléfonos celulares, PDAs, palms, entre otros. El
uso de este tipo de tecnologías va creciendo día a día convirtiéndose en herramientas fundamentales
para las personas y su relación con empresas u organizaciones de diferentes tamaños. Hoy en día se
puede revisar el correo electrónico y calendario personal fuera de la oficina en un pequeño teléfono
inteligente o salir de viaje de negocios con un dispositivo pocket PC inalámbrico con capacidad GPS
que ayude a orientarse en ubicaciones poco conocidas.
Sea cual sea la utilización que se le otorgue a estos dispositivos, cada uno de ellos posee características
en relación a la cantidad de memoria que usan o la capacidad de procesamiento de información que
aplican para su funcionamiento. Si hablamos de la implementación de procesos de cifrado para
potenciar la seguridad que brindan, se puede entrar en un conflicto de valoración de un producto móvil,
debido a que aplicar un proceso de cifrado implica una mayor carga de transacciones y por ende se
requiere mayor poder de procesamiento por parte del equipo móvil, esto traducido a términos
económicos significa dispositivos móviles con memorias y procesadores evidentemente más caros.

Para muchos dispositivos móviles que requieren de algún nivel de seguridad, la implementación de un
proceso de cifrado usando RSA se hace casi impracticable, la cantidad de memoria adicional que se
requiere y los tiempos de cpu que se deben dedicar al proceso son altísimos. Si se implementa un
sistema como este, el valor del dispositivo subiría considerablemente simplemente por el hecho de
poseer un procesador más potente y memoria dedicada para este proceso para no interferir con la que
memoria que usa para desarrollar su propio desempeño funcional. Cabe recordar que la aplicación de
un proceso de cifrado de información dentro de un dispositivo móvil es una función de soporte la cual
no debe interferir con las funciones principales de cada dispositivo, no se puede pensar que el proceso
de cifrado use una mayor porción de procesamiento de datos que la función primaria de un dispositivo.

Usando curvas elípticas significa que un dispositivo embebido puede:

Usar un procesador más barato y pequeño o aplicar mayor procesamiento a las funciones
primarias del dispositivo; en casos donde las operaciones de seguridad son integradas a un
chipset, usando curvas elípticas significará chips menos costosos.
Aplicar menos ciclos de procesador porque el dispositivo está creando menos calor, por ende
menos escape energético, dando como resultado alargar la vida útil de sus baterías.
Requerir menos ancho de banda para sus transacciones debido a que protocolos mas eficientes.
Costos asociados de diseño para sistemas embebidos
En esta sección se examinan los factores asociados a los costos que los desarrolladores, fabricantes y
vendedores deberían considerar cuando implementan seguridad en sus diseños embebidos.
Poder de procesamiento

9
En la determinación de las operaciones potenciales de cualquier dispositivo, la selección de chips es una
de las consideraciones más importantes: un procesador más caro permite a un dispositivo hacer más,
además al usar métodos eficientes se le permite a un procesador más barato realizar las mismas
funciones que uno más caro. Es aquí donde las características de la criptografía de curvas elípticas se
presentan como un método de eficiencia que permite el ahorro de dinero ante el uso de RSA.
Por ejemplo, una smart card para una transacción financiera se debe autenticar a un lector. Realizando
esta transacción usando curvas elípticas requerirá menos procesamiento e incluirá dos posibles
beneficios:
La transacción ocurrirá más rápido significando que el sistema puede procesar mayor cantidad
de transacciones y generar mayores ingresos.

Un procesador más barato (y más lento) puede ser usado en la smart card para realizar la
misma transacción en el mismo tiempo que lo haría un procesador más rápido implementando
AES o RSA por ejemplo.

Otros dispositivos móviles como PDAs o smartphones muestran resultados similares. Un procesador
típico para este tipo de dispositivos es el ARM SA1110, 206MHZ. Al mismo nivel de seguridad de 128
bit de AES, ECC-256 provee de excelentes tiempos de respuesta, RSA-3072 ofrece buena respuesta
solamente en verificaciones de firmas; los tiempos para generar claves y firmas que presenta son
inaceptables.
Como conclusión se puede afirmar que para obtener un buen resultado usando RSA se requiere del uso
de un procesador más caro que el usado por curvas elípticas para obtener resultados similares.

Compuertas lógicas
Como ya ha sido dicho, la criptografía de curvas elípticas ofrece mejoras en software, sin embargo,
también puede ser muy eficiente en hardware. Los beneficios de curvas elípticas pueden incrementar
dramáticamente su eficiencia en comparación a RSA en ambientes basados en hardware. Los diseños
optimizados basados en chips han demostrado que pueden ser hasta treinta y siete veces más rápidos
que el mismo diseño implementado en software.
Esta ventaja se ve reflejada en la cantidad de compuertas lógicas usadas en un diseño electrónico (lo que
indica el espacio usado en un chip) y en performance en relación a RSA. Como todo diseñador
electrónico sabe, más compuertas lógicas dentro del diseño electrónico significan más dinero.
Por estas razones, la criptografía de curvas elípticas es una opción clara y obvia al momento de
implementar este tipo de seguridad en hardware. Cualquier dispositivo que use RSA requerirá de mayor
poder de procesamiento para un microprocesador del que debería usar.

Desgaste de baterías
Como consecuencia de una implementación eficiente de seguridad en hardware según lo planteado en
el uso de compuertas lógicas, se requiere de menos ciclos de procesamiento y menos trabajo por parte
de los microprocesadores, lo que finalmente se traduce en el uso de menos energía y en una disipación
de calor menor. Esto es un punto crítico dentro de los dispositivos móviles, donde el factor limitante
para el uso en muchos casos es la duración de la batería.
Como el uso de ECC reduce los factores mencionados, se dice que el uso de ECC es parte de la
solución para aumentar la vida de los dispositivos móviles.

Ancho de banda y protocolos

Usando menos ancho de banda puede afectar a los tiempos y capacidad de las transacciones,
significando que puede se puede transferir más datos en el mismo tiempo.

Reducción de gastos
Existen costos que se pueden reducir en diferentes etapas del desarrollo de las nuevas tecnologías, la
aplicación de hardware específico optimizado para utilizar la menor cantidad de compuertas lógicas o la

10
implementación de los algoritmos de cifrado por medio de software entre otras opciones. En ambas se
ha demostrado que el uso de la criptografía de curvas elípticas presenta los mejores resultados.

Un ejemplo donde la criptografía de curvas elípticas ofrecen beneficios claros es en la utilización de las
smart cards. Una de las principales funciones del uso de las smart cards es la criptografía. Son
generalmente usadas porque pueden ser usadas para accesos seguros, transacciones financieras,
identificación y todas aquellas actividades donde se requiera de seguridad.

Como en RSA los largos de claves se mueven después de los 1024 bits, es requerido un coprocesador
matemático para lograr una performance aceptable, lo que trae consigo una mayor complejidad y por
ende un valor comercial más elevado. Usando curvas elípticas por otro lado, no se requiere de un
coprocesador, a lo más un pequeño set de hardware reducido, pero aún así las transacciones con smart
cards se realizan mucho más rápido.

El sistema de criptografia de Curvas Elípticas roto por medio de fuerza bruta

Los retos o desafíos se denotan por ECCp-d o ECC2-d o ECC2k-d.
ECCp-d: Curva elíptica definida sobre con un subgrupo cíclico de orden d bits.
ECC2-d: Curva elíptica definida sobre . con un subgrupo cíclico de orden d bits.
ECC2k-d: Curva elíptica de Koblitz con un subgrupo cíclico de orden d bits.

Los retos resueltos:

ECCp-97: Resuelto en 1997 con 740 máquinas 16000 años en MIPS.

ECC2k-108: Resuelto en el 2000 con 9500 máquinas y 400000 años en MIPS.
ECCp-109: Resuelto en 2002 por un grupo académico que empleo un sistema de red de más de 10.000
computadores, que durante las 24 horas del día durante más 549 días fueron capaces de obtener la clave
de cifrado, empleando la fuerza bruta. El premio por vencer el reto que planteaba ECCp-109 fue de
10.000 dólares.
ECC2k-109: En el 2004, tardaron 17 meses con 2600 computadores.

Desafios propuestos por CERTICOM

Actualmente Certicom, ofrece la cantidad de 20000 dólares por el reto de la clave de 131 bits que es
más fuerte que su sistema de ECCp-109. El reto es ECCp-131.
Existen otros retos propuestos, aún sin resolver:
ECCp-163.
ECCp-191.
ECCp-239.
ECC2k-130.
ECC2-131.
ECC2-163

Trabajos Relacionados.

En el campo de la investigación en claves públicas se encontraron diferentes trabajos que focalizan sus
puntos de vistas en una introducción a los sistemas de criptografía elíptica ECC, uno de ellos es Gabriel
Belingueres[11] donde define las curvas elípticas y como pueden ser usadas para construir
criptosistemas de clave pública. Se detallan nociones matemáticas, el problema del Logaritmo Discreto

11
sobre curvas elípticas, pero no detalla la legislación que sustenta esta teoría y es muy débil en cuanto a
las ataques a la ECC. Por otra parte Gomez, Carlos & Izava, Gustavo [12] explican algunos
fundamentos matemáticos de la criptografía de las curvas elípticas y describe las aplicaciones y su uso
en las tecnologías y arquitecturas de seguridad, sin embargo a pesar de su excelente descripción de las
aplicaciones de ECC no detalla los problemas que pueden surgir producto de los ataques en cada
implementación. También Annop MS [15] en su trabajo realiza una introducción teórica de la ECC y
como esta es usada en la implementación de las ECDSA, discute implementaciones de ECC en campos
finitos: campos de números primos y campos binarios, es una excelente guía para la definición teórica
de las ECC pero carece de las bases legales y las debilidades que se han conseguido de la ECC en la
actualidad producto de los grandes sistemas de cómputos y los programas paralelizables.

Conclusiones.

Una integral elíptica o curva elíptica es una función que expresa la longitud del arco de la elipse y que da
lugar a una función semi-cúbica. A pesar de que RSA sigue siendo el criptosistema público más
utilizado, los algoritmos de curvas elípticas están empezando a tener gran impacto en las tecnologías de
firmas digitales y transacciones Web seguras. Debido a que el mejor algoritmo actualmente conocido,
para la resolución del problema en el que basa su seguridad ECC es de orden completamente
exponencial, a diferencia de los métodos usados para romper criptosistemas como RSA cuyo orden es
subexponencial, se puede lograr el mismo nivel de seguridad que otros métodos con longitudes de
claves menores; esta disminución en la longitud de la clave que se gana al usar ECC produce como
resultado que los algoritmos de encriptamiento y desencriptamiento sean más rápidos, pero a costa de
una menor protección contra ataques de fuerza bruta.

Como con todos los criptosistemas, y especialmente con criptosistemas de clave pública, toma años de
evaluación pública antes de que un razonable nivel de confianza en un nuevo sistema sea establecido.
ECC parece haber alcanzado ese nivel ahora, y en los últimos años, las primeras implementaciones
comerciales fueron apareciendo, como bibliotecas de funciones, pero también en aplicaciones reales,
como seguridad en e-mail, smart cards, etc. Un factor que aún queda grandemente incierto es su
seguridad: como con todos los criptosistemas de clave pública usados en la práctica, su seguridad no ha
sido probada, sino que está basada en la incapacidad de encontrar ataques. Si existen ataques sobre
alguno de esos sistemas, podrán ser descubiertos tarde o temprano. En tal caso, se deberá cambiar a
alguna otra alternativa, como los ya tradicionales criptosistemas usados en la práctica basados en el IFP
y el DLP. No obstante, los ECC pueden ser implementados eficientemente, y tienen un número de
ventajas que pueden hacerlo la mejor elección en un rango de aplicaciones, como aquellas en las que los
recursos disponibles (memoria, procesamiento, energía, ancho de banda, etc.) son reducidos. Además,
con un número de estándares estando en preparación, la interoperabilidad entre los diferentes
productos será mucho más fácil de obtener.

Constantemente se ha estado trabajando en dispositivos que aceleren algunas operaciones básicas de

cifrado, mediante la implementación de algunos algoritmos específicos, pero la diferencia no es tan
significativa. Otra manera es balancear la carga de cifrado y descifrado, es decir, usar claves públicas
más grandes, lo que significaría claves privadas mas pequeñas. El problema de esto es estarían
transfiriendo la carga de procesamiento a los usuarios del sistema, que en muchas ocasiones poseen
computadores de bajo nivel de procesamiento. Si bien, el sistema en sí tendría menos carga de trabajo,
las transacciones al final serían más lentas, debido a lo que se demoraría el computador del usuario en
cifrar la información, por lo que la calidad de servicio disminuiría notablemente, y esto puede que cause
pérdidas mayores al gasto de máquinas que soporten más procesamiento o bien al proceso de
migración de tecnología.

12
Lo cierto es que la nueva tendencia es la utilización de dispositivos cada vez más pequeños para realizar
tareas que faciliten la vida laboral y cotidiana. Esto quiere decir que el acceso a Internet está
aumentando de manera exponencial, por lo que garantizar un servicio de calidad y seguro se convirtió
en una necesidad clara, y las empresas fabricantes de los dispositivos móviles se encuentra hoy en día
constantemente estudiando como mejorar el servicio debido a la gran competencia que existe. Nos
referimos a empresas como IBM, Sun Microsystems, Microsoft, Hewlett-Packard o Motorota entre
otras.
El cambio de sistema criptográfico es inminente, y si bien tomará algunos años en incorporarse de lleno
en el mercado, ya se logró un gran paso, que es la aprobación de la NSA para su uso en procesos
gubernamentales. Se espera que pronto, otras entidades empiecen a usar la nueva generación de
criptografía.

Referencias.

[1] S. Singh, “Los códigos secretos”, Debate, Madrid , 2000

[2] W. Diffie , M Hellman, “New directions in criptography”, IEEE Transactions on information Theory,
1976.
[3] R, Rivest, A Shamir, L Adleman. “A method for obtaining digital signatures and public key cryptosystems”.
Comunicactions of the ACM, 1978.
[4] N. Koblitz, “Elliptic curve criptosystems”, Mathematics of computation, 1987.
[5] CADENA, Miguel y MARTÍNEZ, Carlos. Firmas digitales utilizando curvas elípticas. Laboratorio
de cómputo especializado. Universidad Autónoma de Bucaramanga, Colombia. 2002
[6] A. E. Escott, J. C. Sager, A. P. L. Selkirk, and D. Tsapakidis, Attacking elliptic curve cryptosystems using the
parallel pollard rho method, CryptoBytes (1999).
[7] Certicom Research, Sec 1: Elliptic curve cryptography, Working Draft 0.5, Standards for Eficient
Cryptography, http://www.secg.org, September 1999
[8] Certicom, Certicom ecc tutorials, http://www.certicom.com/ecc/enter/index.htm.
[9] A. Jurisic and A. J. Menezes, “Elliptic curves and cryptography”, Whitepaper, Certicom Corp.,
http://www.certicom.com, 1997
[10] NIST, Digital signature standard, FIPS PUB 186-2, NIST, http://csrc.ncsl.nist.gov/fips/, 2010
[11] Belingueres Gabriel, Introducción a los Critosistemas de Curvas Elípticas URL:
http://www.geocities.com/belingueres, Argentina, 2000,
[12] Gómez, Carlos Barco e Isaza Echeverry, Gustavo A. Bases matemáticas y aplicaciones de la
criptografía de curvas elípticas. Revista Vector, Volumen 1. 2006.
[13] National Security Agency / Central Security Services. “The Case for Elliptic Curve Cryptography”.
http://www.nsa.gov/business/programs/elliptic_curve.shtml. Febrero 2010.
[14] Certicom. The Basics of ECC. http://www.certicom.com/index.php/the-basics-of-ecc, Febrero,
2010.
[15] Anoop MS. “Elliptic Curve Cryptography, An Implementation Guide” , 2001

13