Firmas digitales utilizando curvas elípticas

Miguel Cadena Carter
Juan Carlos Martínez Quintero
Laboratorio de computo especializado
Universidad Autónoma de Bucaramanga
Bucaramanga, Colombia

Resumen
En el presente articulo se describen los conceptos importantes para el desarrollo de una aplicación en lenguaje C++ para realizar firmas digitales utilizando curvas elípticas. El procedimiento de firmas utiliza los siguientes algoritmos:  la función SHA1 doble barra para asegurar la integridad del archivo  y el esquema de firma Nyber-Rueppel para asegurar autenticidad. También se utilizaron otras herramientas como algoritmos de compresión de datos. La fortaleza de las firmas digitales utilizando curvas  elípticas se basa en el problema del logaritmo discreto. Los mejores algoritmos conocidos para solucionar este problema corren en tiempo exponencial.

Palabras clave: Firmas digitales, Curvas elípticas, Autenticidad, Integridad, Secreto 

Abstract

In this work it is described important concepts needd for develop an  application in C++ language to sign and check digital signatures using elliptic curves, In the signature procedure the following algorithms were used:  the function SHA-1 double barrel to assure the file integrity and the signature algorithm Nyberg-Rueppel to assure authenticity. Other tools were also used like compression of data algorithms. The strength of digital signatures using elliptic curves is based in the discreet algorithm problem. The best known algorithms to solve this problem runs in exponential time.

Key Words:  Digital sign, elliptic curve,  integrity, authenticity, secret
 
1.0 Introducción
Las facilidades de comunicación de información que suministra una red LAN pueden ser usadas, en el entorno de cualquier organización, para disminuir en forma significativa, el consumo de papel y la mensajería tradicional interna, con las consiguientes ventajas de oportunidad y precisión de la información, pero se presenta la dificultad de asociar en forma efectiva la identidad del usuario al mensaje. Este inconveniente se soluciona a través de la introducción de las firmas digitales. El presente trabajo tiene como objetivo construir una aplicación que permita la firma y verificación de cualquier archivo de datos que se pueda ubicar dentro del ambiente de trabajo de un computador que tenga instalado el sistema operacional Windows 95/98.  

Para lograr el objetivo propuesto se utilizará tecnología basada en curvas elípticas, la cual tiene como ventaja el que se encuentra libre de patentes y se ha considerado como la tecnología del futuro para desarrollos de sistemas criptográficos.

El  propósito de una firma es la de asociar la identidad del firmante con la información registrada en el documento (autenticidad), las firmas manuscritas permiten realizar esta función pero si el documento es alterado el firmante seguirá avalando la información registrada en el documento. Las firmas digitales por el contrario  permiten asociar la identidad del firmante con el documento firmado y detectar modificaciones del mismo (Integridad).

Las firmas digitales se construyen utilizando criptografía de clave publica, la cual utiliza dos claves, privada y publica. La clave privada se mantiene en secreto y la clave publica se divulga libremente. Para firmar se utiliza la clave privada y para verificar la firma se utiliza la clave publica.  Las firmas digitales permiten garantizar los servicios de Integridad y  Autenticidad al tiempo.

Existen diferentes tecnologías para realizar firmas digitales, la mas usada en la actualidad es RSA la cual  utiliza el problema de la factorización  de un entero  considerado computacionalmente infactible para tamaños del modulo  mayores de 1024.  Existen otros esquemas de firma digital que se apoyan sobre otros problemas como el problema del logaritmo discreto (DSS).

Las curvas elípticas se pueden utilizar par formular el problema del logaritmo discreto, una vez formulado este problema es posible construir un esquema de firma digital como el DSS o el esquema Nyberg-Rueppel.

Este trabajo esta organizado como sigue: en la primera sección se presenta una breve introducción sobre el tema de las curvas elípticas; este es un tema del cual se ha escrito en forma muy extensa  durante los últimos ciento cincuenta años y abarca áreas que no son de interés de la criptografía, como un ejemplo de ello se tiene su reciente participación como pilar fundamental en la demostración del ultimo teorema de Fermat.   

La segunda sección trata sobre la criptografía de clave publica[DIFFIE], la cual es una forma de criptografía de reciente desarrollo, cuya definición y fortaleza radican en la dificultad para solucionar cierto tipo de problemas denominados “duros” ya que requieren de ingentes recursos de computo a medida que aumenta el tamaño del problema[ELIPCUR]. El tercer capítulo trata sobre las aplicaciones  desarrolladas

2.0 Cuerpos [MENEZES2, pagina 76]
Un cuerpo F es un conjunto diferente de vacío dotado de dos operaciones, usualmente denominadas adición y multiplicación. El conjunto F junto con la operación de adición forman un grupo abeliano de igual forma  los elementos de F   {0} , junto con la operación de multiplicación también forman un grupo abeliano. Adicionalmente la multiplicación es distributiva con respecto a la suma..

Por ejemplo, Los números racionales , los números reales   y los números complejos   forman cuerpos con las operaciones de suma y multiplicación.

El conjunto de los enteros  con las operaciones usuales de suma y multiplicación  no forma un cuerpo, ya que los únicos elementos  con inverso multiplicativo son el  1  y el  -1. Un cuerpo es finito si consta de un numero finito de elementos.

Por definición la característica de un campo es cero  si la suma de uno m veces  (1+1+1...  +1m)  nunca es igual a cero,  para cualquier m  1. Por otro lado, la característica de un cuerpo es el menor entero positivo m  tal que:

El conjunto p (Enteros módulo p, p primo) tiene característica p. 

El cuerpo F2m es un cuerpo finito compuesto por  2m  sartas de unos y ceros de longitud m, al cual también se le denomina cuerpo de Galois. Estas estructuras son  particularmente propicias para  su utilización en  aplicaciones computacionales ya que corresponden muy bien con la representación interna que los computadores hacen de los números. 

2.1 Curvas elípticas
Una curva elíptica E es el conjunto de todas las soluciones  a una ecuación de la forma:

En donde los coeficientes   pertenecen a un cuerpo como  p  ,, , ,  F2m, mas un punto especial 0  denominado punto en el infinito.

Como un requisito indispensable para que estas curvas sean criptograficamente fuertes [KOBLITZ1, pag 168]   se requiere que  la curva cumpla la siguiente condición.

El conjunto conformado por las soluciones a a la ecuación (2.1) , mas el  punto 0, permite la definición de una operación  de adición [KOBLITZ1, pagina 169] que gráficamente puede presentarse de la siguiente manera. Dados dos puntos P, Q sobre la curva, se traza una línea que pase por los dos puntos P y Q, esta línea corta la curva en otro punto R, la suma de P+Q, es la reflexión de R sobre el eje x. 

Figura #1.
Algebraicamente esto puede representarse de la siguiente forma. Dados dos puntos  P =(x1,y1) y Q=(x2,y2) sobre una curva elíptica, se puede encontrar un punto  Q =(x3,y3) =  P+Q  donde:

El conjunto conformado por las soluciones a la curva y la operación de adición definida según las ecuaciones (2,3) a  (2,5) conforman un grupo aditivo [MENEZES1, pagina 17].

2.2 Problema del Logaritmo discreto en curvas elípticas.
Utilizando la operación de suma definida sobre el conjunto de puntos conformado  por una curva elíptica definida sobre un  cuerpo, es posible plantear el problema del logaritmo discreto. El cual consiste en que dada una curva elíptica E definida sobre F2m, un punto P  E(F2m) de orden n, y un punto Q que pertenece a E(F2m), determinar el entero K,  0  K  n - 1, tal que  Q = KP, suponiendo que tal entero existe.

Ejemplo.
Tomando la curva elíptica: y2 = x3 + 9x + 17  definida en el cuerpo F23  cual es el logaritmo discreto   k  de  Q = (4,5)  en la base P  = (16,5).

Una forma de solucionar este problema es realizando una aproximación por fuerza bruta, es decir probar todos los posibles K . 

K=1 	P = (16,5)
K=2  	2P = (20,20)
K=3	3P = (14,14)
K=4	4P = (19,20)
K=5	5P = (13,10)
K=6	6P = (7,3) 
K=7	7P = (8,7) 
K=8	8P = (12,17) 
K=9	9P = (4,5);   Se ha encontrado el valor de Q, por lo tanto k = 9 es logaritmo discreto  de  Q (4,5)  en base  P(16,5).

Los mejores algoritmos para solucionar este problema corren en tiempo exponencial [ELIPCUR, pagina 8] en función del tamaño del cuerpo, por tal motivo este problema al igual que otros, con las mismas características, se denominan problemas “duros”.

2.3 Funciones Hash.
Las funciones Hash permiten realizar un resumen de longitud fija de cualquier mensaje   h= H(m). Son funciones que se comportan como funciones de una vía por lo cual deben cumplir las siguientes propiedades. [WSTALL, pagina 175]

•	Dado un mensaje m   es fácil calcular    h=  H(m);
•	Dado  h, es computacionalmente difícil encontrar  M , tal que H(M) = h;
•	Dado M, es computacionalmente difícil encontrar  M´, tal que H(M)=H(M´).

También se requiere de una condición adicional, la cual se denomina resistencia a las colisiones y consiste en que  es difícil encontrar dos mensajes aleatorios  M  y M´  tales que  H(M)  = H(M´) 
Para  el desarrollo de este trabajo se utilizo la función  hash  SHA-1 con doble barra, la cual genera un resumen de  260 bits de cualquier mensaje.

3.0 Criptografía de Clave pública
La criptografia de clave publica fue creada por los señores  Martin E. Hellman,  Ralph C. Merkle y Whitfield Diffie en 1976, básicamente postularon la necesidad de contar  con dos claves (privada y publica) para cada participante, de tal manera que la clave publica se podría repartir libremente y la clave privada se debía mantener en secreto.  Para genera la  clave privada y la clave publica se debería utilizar un procedimiento que se pudiese ejecutar en tiempo polinomial, pero  el conocimiento de la clave publica  y de las características del algoritmo de generación de  las claves debía ser insuficiente para determinar la clave privada. El trabajo solo proponía las especificaciones  de lo que debería cumplir un sistema de criptografía de clave publica, en 1977 los señores Rivest, Shamir y Addleman postularon el criptosistema RSA, el cual cumplia con todas las especificaciones y es la base de la mayoría de aplicaciones de comercio electrónico modernas.

3.1. Protocolo Diffie-Hellman.
Este protocolo fue desarrollado por los señores  Whitfield Diffie y  Martín Hellman en 1976 y tiene como propósito realizar el intercambio de una clave de sesión. El protocolo se apoya en el problema del logaritmo discreto definido en el cuerpo Zp.  Para que dos  entidades puedan intercambiar información en forma segura en un medio inseguro, cada uno de ellos debe contar con una pareja de claves (privada y publica), e intercambian sus claves publicas y con estas se realizan operaciones aritméticas que conducen a la generación de un entero (igual para ambos) que puede utilizarse para encriptar información utilizando criptografía convencional ( una sola clave).

3.2 Firmas Digitales.
Una firma digital  de un documento es un segmento de información (un grupo de bits) basada en:  el documento a firmar, en la clave privada del usuario que firma  el documento y en una función o esquema de firma. El objetivo de una firma digital, al igual que las firmas manuscritas, es el de ligar en forma indiscutible la identidad del usuario al documento firmado  (Autenticidad de entidad).

3.3 Protocolo de firma
La figura 2. muestra un esquema general de firma[WSTALL],  el emisor toma el mensaje  M y le aplica una función Hash, esta función genera un resumen  e del archivo, el cual el emisor encripta o transforma con su clave privada.  Este proceso produce un conjunto de bits que el emisor concatena con el mensaje y envía al receptor.  El receptor recibe el paquete y procede a separar el mensaje de su firma, luego aplica una función hash al mensaje y calcula un resumen  e’ .  El siguiente paso que debe ejecutar el receptor es decriptar o realizar una transformación inversa sobre  los bits de la firma utilizando la clave pública del  emisor, una vez ejecutado este paso el emisor cuenta con  el resumen e original del mensaje enviado por el emisor. En este momento el emisor puede comparar  e  y e´.  Si las dos sartas de bits son iguales el receptor puede concluir que el mensaje fue enviado por  A y que el mismo  no ha sido alterado. 

Figura #2.

Para realizar la firma del documento se utilizo el esquema Nyberg-Rueppel. [MICHAELR]  El cual funciona de la siguiente manera:

Sea  e el valor  hash del documento m , sea E  la curva  que satisface las ecuaciones  2.1 y 2.2, sea P  un punto sobre la curva  con un orden primo grande denotado por   n , sea s  la clave privada del usuario.

La clave publica  Q  del usuario se construye de la siguiente manera.

Q = sP				(3.1)

Para realizar la firma se debe escoger una secuencia aleatoria de bits   k  y calcular

			R = kP				(3.2)

Ya que R es otro punto de la curva, se toma su componente  x  para calcular

			c  =  x+e mod n			(3.3)

			d =  k – sc mod n 		(3.4)

La pareja  (c,d)  es la firma digital del documento m  representado por su valor hash  e .

La firma digital se concatena con el mensaje, se comprime  y se envía como un mensaje de correo electrónico. El destinatario recibe el mensaje, descomprime el archivo y separa sus componentes: la firma y  el mensaje original. Con los bits de la firma realiza los siguientes cálculos:

			R´ =  dP + cQ			(3.5)

Usando la componente  x de R´  se calcula.

			e´ = c – x´ mod n		(3.6)

Como paso final el destinatario calcula el valor hash e=Hash(M) del mensaje recibido y lo compara con e´  .  Si los valores son iguales la firma es correcta. Si los valores son diferentes, entonces el mensaje fue alterado y la firma debe ser rechazada.

4.0 Descripción de las aplicaciones realizadas.
Se  desarrollaron dos aplicaciones  en visual C++ versión 6  en las cuales se utilizaron  rutinas de dominio publico para realizar operaciones en cuerpos de Galois de tal manera que  fuese posible definir una curva elíptica.  Para ello  era necesario que el software permitiera la realización  de las operaciones de Suma y Multiplicación entre los elementos del cuerpo F2m,  una vez definidas las curvas elípticas  se pudo implementar la operación de suma de puntos de una curva , con la operación  de suma se pueden crear claves privadas y publicas  que pueden ser utilizadas para realizar firmas digitales.  

Las aplicación principal permite generar una parejas de claves y almacenar la clave publica  en un servidor Oracle, junto con los datos de identificación del usuario. Una vez realizado esto  se puede:
a.	Elegir un archivo dentro del entorno de Windows 95/98 y firmarlo. Este proceso produce un archivo comprimido con extensión  .fdi  el cual puede ser enviado por correo utilizando un navegador o cualquier otra herramienta.
b.	Elegir un archivo firmado, descomprimirlo y verificar la firma anexa.

También se ha desarrollado una aplicación que permite implementar el protocolo Diffie- Hellman para intercambio de una clave de sesión para realizar criptografia convencional,  para ello la  aplicación consulta la base de datos donde se almacenan las claves publicas y toma la clave publica de cada participante y con ella se genera información compartida entre dos entidades que se puede utilizar para  realizar encriptamiento convencional. 

5.0 Conclusiones
La teoría referente a la  utilización  de curvas  elípticas para aplicaciones criptográficas y los desarrollos de software de dominio publico, permiten la construcción de aplicaciones para ofrecer los servicios de autenticidad e integridad en una red LAN con un buen nivel de seguridad.  Con la conveniencia de que las tecnologías utilizadas están libres de patentes.  También se puede implementar los servicios de secreto  para la transmisión segura de información en medios inseguros.   Esto abre  las puertas al desarrollo de productos comerciales que puedan ofrecer buenos servicios de seguridad para transmisión de información entre usuarios de una red LAN y  en otros tipos de aplicaciones como productos de workflow etc.

El trabajo desarrollado  requiere avances en otras áreas como  métodos para generar curvas criptográficamente fuertes (finitas, con un  gran numero de puntos y que cumplan la condición 2.2)  para que los productos puedan ser configurados por los usuarios. También se requiere del desarrollo de técnicas de programación segura, que no permitan los ataques del tipo desbordamiento de pila o que expongan información critica en memoria.