¿Qué es la criptografía de curva elíptica?

octubre 2, 2007 § Deja un comentario

En general, los sistemas de criptografía de clave pública están basados en problemas matemáticos de muy difícil resolución. El sistema RSA, que ya examinamos en el Boletín ENIGMA nº 46, debía su fortaleza al hecho de que factorizar números grandes es una tarea computacionalmente compleja, tanto más cuanto mayor sea el número utilizado. En el sistema RA, sin embargo, las claves han de ser mucho más grandes que en el caso de los algoritmos simétricos para otorgar una seguridad parecida. Se conoce desde hace tiempo un tipo de criptografía de clave pública que requiere claves más pequeñas. Conocida bajo el nombre de Criptografía de Curva Elíptica (ECC), ha sido apenas usada hasta ahora, pero el hecho de que requiere claves más pequeñas que otros sistemas de clave pública lo hacen un buen candidato para aplicaciones donde los requisitos de tamaño de memoria son más exigentes, como por ejemplo en sistemas de identificación mediante tarjetas.

Como contrapartida, son sistemas más engorrosos de entender
desde el punto de vista matemático. Pero para eso estamos aquí. Vamos
a intentar descifrar el funcionamiento de los sistemas ECC. Les
advierto que va a ser algo pesado, pero como de costumbre pondré las
neuronas a funcionar con el objeto de simplificar en lo posible la
explicación. El lector juzgará hasta qué punto he tenido éxito.

Vamos a comenzar a cocinar. Para este plato necesitaremos
logaritmos, grupos, puntos y operaciones. Si en el caso del
algoritmo RSA, el problema consistía en factorizar números, en la ECC se
trata de obtener logaritmos. Por si alguien no tiene fresco el
concepto, recordemos. Supongamos que tenemos una expresión del tipo
a^x=b, donde el signo ^ quiere decir “elevado a”. Para “despejar” x,
utilizamos la operación inversa a la potenciación, y eso es el
logaritmo. Esto es, si a^x=b, entonces x=Log(a)b, lo que se lee “x es
el logaritmo en base a de b” Si a=10, hablamos de logaritmos decimales,
y si a es el número e (=2.71828…), tenemos logaritmos naturales o
neperianos.

Bueno, en principio hallar un logaritmo no comporta mayor
problema que hallar una potencia. Así que vamos a complicar las cosas
en seguida. En primer lugar, necesitaremos un grupo. No se trata de
una agrupación de personas. En álgebra, un grupo es un conjunto de
elementos unidos a una operación matemática. Dicha operación matemática
(llamémosla *) debe cumplir las siguientes propiedades:
– Si a,b son elementos del grupo, su combinación a*b también es
un elemento del grupo
– La operación cumple la propiedad asociativa: a*(b*c)=(a*b)*c
– Existe el elemento neutro 1, tal que 1*a=a*1 para cualquier a
– Existe el elemento opuesto, y, tal que x*y=y*x=1.

Por ejemplo, el conjunto de números enteros con la operación
suma (y el cero como elemento neutro) formaría un grupo.

Existen muchos tipos de grupos. Los que nos interesan se
denominan “grupos cíclicos”. Un grupo cíclico se caracteriza porque
todos sus elementos se pueden obtener mediante un sólo elemento, llamado
generador. Si la operación es la multiplicación, se denomina grupo
cíclico multiplicativo. Como ejemplo, podemos tomar el grupo formado
por las cuatro raíces cuartas de 1: +1,-1,+i,-i (i es la raíz cuadrada
de uno). El número i puede servir de multiplicador. En efecto:

i*(+1) = i
i*(+i) = -1
i*(-1) = -i
i*(-i) = 1

El concepto de grupo multiplicativo nos permite complicar la
obtención de logaritmos. Supongamos un grupo G con n elementos, y sea b
un generador. Eso significa que podemos obtener todos los elementos del
grupo como {1, b, b^2, b^3 … b^(n-1)}. Es decir, habrá un número
entero k de forma que podamos escribir g=b^k para cualquier número g del
grupo. En realidad, existen muchos números enteros k que cumplan esta
propiedad. Por ejemplo, el número k’=k+n también nos vale, puesto que
b^(k+n)=(b^k)*(b^n),y b^n=1. Esto nos dice que cualesquiera dos enteros
k,k´ capaces de representar el elemento g son congruentes módulo n (o
dicho de otra forma: nos dan el mismo resto al dividirlos por n).

Me huelo la cara que estará poniendo. Así que, antes de que
pierda usted el apetito, vamos a aderezar el guiso con el elemento
filipino: los logaritmos discretos. ¿Recuerda? Bien, se trataba de que
si a^x=b, entonces x=Log(a)b. Aquí tenemos algo muy similar. La
diferencia es que, en lugar de movernos por todo el campo de los números
reales, nos restringiremos al grupo cíclico G. El LOGARITMO DISCRETO de
g en base b es la operación inversa a la potenciación: si g=b^k,
entonces k=Log(b)g.

En el caso de nuestro grupo, tendríamos b=i, k=0,1,2,3:
b^k=g k=Log(b)g.
i*1 = i 1 = Log(i)i
i*2 = -1 2 = Log(i)(-1)
i*3 = -i 3 = Log(i)(-i)
i*4 = 1 4 = Log(i)(1)

Vale, ya está. La salsa está lista. Ahora, la pregunta del
millón es ¿y esto qué complicación tiene? Nos hemos aburrido como locos
con todo ese rollo de los grupos multiplicativos, total, para terminar
haciendo un logaritmo. El problema está cuando el grupo es muy grande.
En nuestro caso, el número n es pequeño, de forma que he podido generar
los elementos g como b^k (k=1,2,3,4). Si quiero saber cuál es el
logaritmo discreto de -i no tengo más que mirar en la tabla y leer
“i^3=-i”, de forma que la respuesta que busco es k=3.

Pero, ¿y si el número n es muy grande? ¿Y si es enorme? ¿Y si n
es 2^100? !Ah! Entonces tengo un problema gordo. !A ver quién se dedica
a calcular g, g^2, g^3 … hasta g^(2^100)! Calcularlos todos requiere
un tiempo de ejecución polinómico, lo que nos deja en la cuneta cuando n
alcanza valores grandes. Es decir, podemos hacer operaciones del tipo
g=b^k fácilmente, pero su inversa k=Log(b) ya es mucho más difícil. Nos
recuerda el caso del algoritmo RSA: es fácil multiplicar dos números
primos grandes, pero resulta mucho más difícil factorizar el producto.

¿Y dónde entran las curvas elípticas? Básicamente, y
simplificando mucho, nos permiten crear el grupo G. Según sea el grupo,
así de complicado será el problema y, por tanto, así de seguro será el
esquema a efectos de montar sistemas de cifrado. Por ejemplo, el
algoritmo de cifrado Diffle-Hellman (bueno, en realidad es de
intercambio de claves, pero viene a ser lo mismo) usa un grupo que se
denota como Zn* y que se lee “”grupo multiplicativo de enteros módulo
n”. No es necesario aquí saber qué significa, así que sean buenos y no
me obliguen a explicárselo.

Volvamos a las curvas elípticas. ¿Recuerdan sus tiempos de
instituto?. La ecuación y=ax+b nos daba una recta, x^2+y^2=r^2
representaba una circunferencia … y la curva del tipo y^2=x^3+ax+b nos
da nuestra curva elíptica. Para cada pareja de valores (a,b), la curva
nos da un montón de puntos (x,y). Añadiremos el “punto en el infinito” a
efectos de complitud. Ese montón de puntos forma un grupo.

Es importante distinguir entre dos conceptos: los números x,y
son reales y forman un campo finito (otro bicho matemático como el
grupo, pero con propiedades distintas), pero los puntos (x,y) forman un
grupo. Es como una coordenada en un plano. Si decimos “longitud 4.3,
latiud 45.8″, los números 4.3 y 45.8 son una cosa, pero el lugar
geográfico que representan es otra. Por eso suele hablarse de “grupos
multiplicativos de campos finitos”. Puede parecer complicado, pero por
lo que parece el problema de logaritmos discretos en los grupos
generados mediante curvas elípticas es más complejo que el
correspondiente al grupo de elementos muitlplicativos no nulos
subyacentes al campo en sí (y si no lo han entendido, lo tachan y ya
está).

El esquema sería algo así:

a) Escogemos una curva elíptica
b) La curva elíptica tiene un conjunto de soluciones (x,y).
c) Si los valores x,y pertenecen a un campo finito, entonces los
puntos (x,y) de la curva forman un grupo
d) Tomamos un elemento del grupo, y hallamos su logaritmo
discreto para una base dada. Eso nos servirá de base para establecer
algoritmos criptográficos de intercambio de claves y de firma digital.

Mis disculpas por lo engorroso del tema, y coincido con ustedes
en que quienes inventaron todo ese galimatías debería ser puesto en
busca y captura. Los “sospechosos habituales” son Victor Millery Neil
Koblitz, quienes descubrieron la ECC en 1985 como mecanismo alternativo
para distribución de claves.

En cualquier caso, el hecho es que la ECC es mucho más compleja que el sistema RSA, tiene más incertidumbres y puede que nos de más de una sorpresa. También es bastante lento, al menos en su implementacióninicial. En el apartado positivo, requiere claves de longitud menor que
las RSA, aunque todavía mayores que las de los algoritmos simétricos.

Según el NIST (el instituto de estándares de EEUU), el algoritmo simétrico AES con clave de 128 bits proporciona una seguridad aproximadamente igual a la de ECC con clave de 256 bits … o a la del algoritmo asimétrico RSA con clave de 3072 bits. Quizá el mayor inconveniente del esquema ECC sea legal: según la NSA norteamericana, la empresa Certicom tiene más de 130 patentes en ese campo, lo que seguramente desanima a más de uno. Claro que la propia NSA tiene un acuerdo de licencia con Certicom, y acepta dos algoritmos basados en ECC dentro de su “Suite B” de algoritmos de cifrado y firma. Así que algo debe tener.

El boletín ENIGMA es una publicación gratuita del Taller de Criptografía, y se rige por las normas de la licencia de Creative Commons “Reconocimiento-NoComercial-CompartirIgual”. Se permite su libre copia, distribución y comunicación para fines no lucrativos, citando nombre y referencia.

Fuente: Boletín Enigma

Anuncios

Responder

Por favor, inicia sesión con uno de estos métodos para publicar tu comentario:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

¿Qué es esto?

Actualmente estás leyendo ¿Qué es la criptografía de curva elíptica? en Seguridad Informática.

Meta

A %d blogueros les gusta esto: