jueves, agosto 25, 2005

Apuntes de criptografía V: Elgamal

Retomamos nuestras clases particulares sobre criptografía. En la última entrega hablamos sobre lo que se puede considerar el padre de la criptografía asimétrica, el intercambio de Diffie-Hellman. En esta ocasión vamos hablar sobre el algoritmo de cifrado Elgamal, no tan conocido como RSA, pero sobre él versó mi proyecto de fin de carrera.

En 1985 Taher Elgamal propuso un algoritmo de cifra que hace uso del problema del cálculo de un logaritmo en campo discreto de números. Por ejemplo, Alicia tiene un número primo p y un generador g; Alicia elige un número aleatorio a y calcula A=ga. A, g y p es la clave pública de Alicia, a es su clave privada.

Benito quiere enviarle un mensaje m a Alicia para ello. Benito genera un número aleatorio k el cual es menor que p, luego Benito calcula c1 = gk mod p y c2 = Ak * m mod p y le envía a Alicia c1 y c2.

Alicia para decodificar el mensaje solo tiene que calcular c1-a * c2 mod p y obtendrá m. Esto es debido a que Alicia conoce g, p y i – su clave privada – por lo cual puede calcular c1= gk-a mod p = g-ak mod p = (ga)–k mod p = A-k mod p. Luego c1-a * c2 mod p = A-k * Ak * m = 1 * m = m

Si una persona que no conociera la clave privada – a – y quiera decodificar el mensaje tendría que despegar m de c2. Para ello debe resolver un algoritmo en campo discreto de números, lo que supone un tiempo de ejecución no polinomial.

Si lo que queremos cifrar no es número sino un mensaje deberemos transformar ese mensaje M al número m – podemos usar para ello el código ANSI. Si el texto es demasiado grande tendremos que ir rompiendo M en bloques de tamaño g-1.

Elgamal – como todos los algoritmos de clave pública – requiere mucha computación además por cada trozo de mensaje que codifiquemos deberíamos enviar c1 y c2 , con lo cual estamos duplicando la información original. Lo ideal es usar un sistema de cifrado híbrido.