AMIGOS PARA SIEMPRE: Criptografía

Algoritmos criptográficos

En criptografía, LSA (acrónimo de Light Summary Algorithm , Algoritmo Ligero de Resumen) es un algoritmo de reducción criptográfico de 64 bits.

Codificación

La codificación del LSA de 64 bits es representada típicamente como un número de 16 dígitos hexadecimal. El siguiente código de 28 bytes ASCII será tratado con LSA y veremos su correspondiente hash de salida:

   LSA("Esto si es una prueba de LSA") = cfa26da3a8c76ca3

Un simple cambio en el mensaje nos da un cambio total en la codificación hash, en este caso cambiamos dos letras, el «si» por un «no».

   LSA("Esto no es una prueba de LSA") = d607d93d2556c3b5

Otro ejemplo sería la codificación de un campo vacío:

   LSA("") = bb52e9b27ef418a3

Algoritmo

El algoritmo LSA se basa en el reordenamiento de una tabla de valores, en base al mensaje a codificar. A partir de este punto, se hacen uso de funciones lógicas para determinar el valor de salida.

Implementación en C#:

    /// 
    /// LSA(Light Summary Algorithm) Algoritmo de reducción criptográfico de 64 bits.
    /// Copyright(C) Ronald Anderson 2007-2008
    ///

public class LSA { private static byte[] keyStream = new byte[512]; public static byte[] ComputeHash(byte[] buffer) { for (int i = 0; i < 512; i++) { keyStream[i] = (byte)i; } if (buffer.Length == 0) buffer = new byte[1]; buffer[0] = 0; while ((buffer.Length % 512) != 0) { Array.Resize<byte>(ref buffer, buffer.Length + 1); buffer[buffer.Length - 1] = 0; } int index1 = 0; int index2 = 0; byte swap = 0; for (int i = 0; i < (buffer.Length / 512); i++ ) { for (int n = 0; n < keyStream.Length; n++) { index2 = (buffer[index1] + keyStream[n] + index2) % 512; swap = keyStream[n]; keyStream[n] = keyStream[index2]; keyStream[index2] = swap; index1 = (index1 + 1) % buffer.Length; } } return Cipher(keyStream); } private static byte[] Cipher(byte[] keyStream) { byte[] result = new byte[8]; string[] keyParts = new string[128]; for (int m = 0; m < keyParts.Length; m++) { int index = m * 4; keyParts[m] = string.Concat(string.Format("{0:x2}", keyStream[index]), string.Format("{0:x2}", keyStream[index + 1]), string.Format("{0:x2}", keyStream[index + 2]), string.Format("{0:x2}", keyStream[index + 3])); } ulong xa = 0xFC, ya = 0xEF, za = 0xBA, na = 0xDC; ulong xb = 0xCD, yb = 0xAE, zb = 0xFE, nb = 0xAD; for (int j = 0; j < keyParts.Length; j++) { ulong lX = ulong.Parse(string.Concat(keyParts[j][0], keyParts[j][1]), NumberStyles.HexNumber); ulong lY = ulong.Parse(string.Concat(keyParts[j][2], keyParts[j][3]), NumberStyles.HexNumber); ulong lZ = ulong.Parse(string.Concat(keyParts[j][4], keyParts[j][5]), NumberStyles.HexNumber); ulong lN = ulong.Parse(string.Concat(keyParts[j][6], keyParts[j][7]), NumberStyles.HexNumber); xa = AA(lX, ya, za, na); ya = AA(xa, lY, za, na); za = AA(xa, ya, lZ, na); na = AA(xa, ya, za, lN); xb = BB(lX, yb, zb, nb); yb = BB(xb, lY, zb, nb); zb = BB(xb, yb, lZ, nb); nb = BB(xb, yb, zb, lN); xa = CC(lX, yb, zb, nb); ya = CC(xb, lY, zb, nb); za = CC(xb, yb, lZ, nb); na = CC(xb, yb, zb, lN); xb = AA(lX, ya, za, na); yb = AA(xa, lY, za, na); zb = AA(xa, ya, lZ, na); nb = AA(xa, ya, za, lN); xa = BB(lX, ya, za, na); ya = BB(xb, lY, zb, nb); za = BB(xa, ya, lZ, na); na = BB(xb, yb, zb, lN); xb = CC(lX, yb, zb, nb); yb = CC(xa, lY, za, na); zb = CC(xb, yb, lZ, nb); nb = CC(xa, ya, za, lN); } result[0] = (byte)xa; result[1] = (byte)ya; result[2] = (byte)za; result[3] = (byte)na; result[4] = (byte)xb; result[5] = (byte)yb; result[6] = (byte)zb; result[7] = (byte)nb; return result; } private static ulong AA(ulong x, ulong y, ulong z, ulong n) { return (x & y) | ((~n) & z); } private static ulong BB(ulong x, ulong y, ulong z, ulong n) { return (x ^ y) | (n & (~z)); } private static ulong CC(ulong x, ulong y, ulong z, ulong n) { return (x ^ y ^ z ^ n);


El procedimiento de cifrado/descifrado ElGamal se refiere a un esquema de cifrado basado en el problema matemático del logaritmo discreto. Es un algoritmo decriptografía asimétrica basado en la idea de Diffie-Hellman y que funciona de una forma parecida a este algoritmo discreto.

El algoritmo de ElGamal puede ser utilizado tanto para generar firmas digitales como para cifrar o descifrar.

Fue descrito por Taher Elgamal en 1984¹ y se usa en software GNU Privacy Guard, versiones recientes de PGP, y otros sistemas criptográficos. Este algoritmo no está bajo ninguna patente lo que lo hace de uso libre.

La seguridad del algoritmo se basa en la suposición que la función utilizada es de un sólo sentido debido a la dificultad de calcular un logaritmo discreto.

El procedimiento de cifrado (y descifrado) está basado en cálculos sobre un grupo cíclico cualquiera  $G\,$  lo que lleva a que la seguridad del mismo dependa de la dificultad de calcular logaritmos discretos en  $\,G$ .

El algoritmo original

Mostremos el criptosistema propuesto inicialmente por Tahar ElGamal en su artículo.

Generación de la clave

Para generar la clave, Alicia escoge un número primo  $p\,$  cualquiera tal que  $p - 1\,$  tenga un factor primo grande (esto se pide para que el problema del logaritmo discreto sea difícil² ). Además elige dos números aleatorios  $g\,$  (el generador) y  $a\,$  (que actuará como clave privada) tal que  $a \in \{ 0, \ldots, p-1 \}$ .

Alicia calcula el valor de  $K=\, g^a \pmod p$ . La clave pública será  $(g, p, K)$ , mientras que el valor de  $a$  lo mantendrá en secreto.

Cifrado

Supongamos que Bruno tiene un texto claro que quiere enviar cifrado a Alicia. Lo primero por hacer es convertir este texto en un entero entre 1 y  $p-1$ , obteniendo un $m\,$  (esto no es parte del cifrado, sino que es una manera de codificar estándar, conocida por todos). Luego Bruno escoge arbitrariamente un número  $b\in \{ 2, \ldots, p-1 \}$  (que mantendrá secreto) para finalmente calcular:
 $y_1 = g^b\,\pmod p$ 
 $y_2 = K^b \, m\,\pmod p$ 

El mensaje cifrado final corresponde a la tupla  $\, C_b(m, b) = (y_1, y_2)$ 

Descifrado

Para descifrar se tiene que realizar el siguiente cálculo:
 $y_1^{-a} y_2 \pmod p$ 

donde  $y_1^{-a}$  representa el inverso de  $y_1^a$  módulo  $p$  (que, utilizando el Pequeño teorema de Fermat puede calcularse como  $y_1^{p-1-a}$ ).

Veamos por qué esto da como resultado  $m$ :
 $y_1^{-a} y_2$   $\,= (g^b)^{-a}K^bm= g^{-ab}(g^a)^bm = (g^a)^{-b} (g^a)^b m$   $\,= m \pmod p$ 

Vale observar que para calcular el descifrado, es necesario conocer  $a$ , que es justamente la clave privada de Alicia.

Ejemplo numérico

Alicia elige los valores:
 $p = 17\,$  (primo elegido al azar)
 $g = 3\,$  (generador)
 $a = 6\,$  (llave privada elegida al azar)
 $K = g^a\,\pmod p = 3^6\,\pmod {17} = 15\,$  (llave pública)

La llave pública será  $\,(17,3,15)$  y la privada  $\,(6)$ .

Bruno tiene el texto claro  $\,m = 9$ . Escoge un  $\,b = 5$  aleatorio:
 $y_1 =\, g^b \pmod p =\, 3^5 \pmod {17} =\, 5$ 
 $\,y_2 =\, K^b m \pmod p =\,15^5 \cdot 9 \pmod{17}=\, 1$ .

El texto cifrado  $\,C_b(m,b)$  está compuesto por la tupla  $\,(y_1=5, y_2=1)$ .

El texto cifrado puede ser descifrado por Alicia utilizando la llave privada  $\,(a=6)$ .

Utilizando el Pequeño Teorema de Fermat:
 $m = y_1^{p-1-a} y_2 \pmod p = 5^{10} \cdot 1 \pmod {17} = 9$ .

Generalización

Lo único que se utiliza de la congruencia módulo  $p$  es que el conjunto  $(\Z/p)^\times=\{x\in\Z: 1\leq x<p\}$  forma un grupo con las operaciones módulo  $p$  y que en dicho grupo el problema del logaritmo discreto resulta difícil.

Por lo tanto, puede cambiarse en este criptosistema al grupo  $(\Z/p)^\times$  por cualquier otro grupo  $G$  en el que el logaritmo discreto sea complicado.

Por ejemplo, resulta bastante efectivo utilizar como grupo una curva elíptica sobre  $\Z/p$  (véase Criptografía de curva elíptica), ya que no se conoce un algoritmo de tiempo subexponencial capaz de resolver el problema del logaritmo discreto en curvas elípticas en general.³

Análisis

Efectividad

Hasta el momento el algoritmo ElGamal de cifrado/descifrado puede ser considerado un algoritmo efectivo.

Un adversario con la habilidad de calcular logaritmos discretos podría ser capaz de romper un cifrado ElGamal. Sin embargo, en la actualidad, el algoritmo de computación de logaritmos discretos (cuando trabajamos módulo un primo) es subexponencial con una complejidad de λ = 1/3, la misma que la de factorizar dos números primos, y por tanto, no es accesible de realizar tal tarea en números grandes en un tiempo razonable. El logaritmo discreto es aún más difícil si trabajamos en otros grupos (como por ejemplo, curvas elípticas).

Véase Récords en logaritmos discretos para una muestra de las posibilidades que da la computación actual a la hora de resolver este problema.

Maleabilidad

Sin embargo existe un caso en que este algoritmo se vuelve maleable. Esto significa que bajo un ataque específico la seguridad de ElGamal se puede quebrar. Este ataque usa el hecho de tener el texto cifrado  $C_b=(B,M)\,$  del texto claro  $m\,$  (ambos conocidos). Sabiendo esto se puede llegar a que el texto cifrado  $C_b=(B, k*M)\,$  corresponde al texto plano  $k*m \,$ . Si ahora la persona que cifró el mensaje anterior genera otro texto cifrado  $C_b=(B, M')\,$  (utilizando el mismo  $b\,$  con el que cifró anteriormente) el adversario debería ser capaz de llegar al texto plano  $m'\,$  correspondiente siguiente los siguientes pasos:
Calcular  $k= M'/M\,$ 
Buscar un  $m'\,$  tal que  $\, m' = m * k \pmod p$  tomando en cuenta que  $m'\,$  al igual que  $m\,$  cumple con estar entre  $0\,$  y  $p-1 \,$ 
Tomando el peor caso, el atacante obtendrá dos textos claros (debido a la función módulo).

Desempeño

El análisis de desempeño del algoritmo ElGamal es similar al de RSA. Concretamente tenemos el siguiente análisis
Sea  $\,n$  el módulo usado en ElGamal. Los procesos de cifrado y descifrado de ElGamal por lo tanto toman tiempos de  $\,O(\log n)$ .