Exposicion Algoritmo El Gamal

• Fue descrito por Taher Elgamal en 1984 • Se usa en software GNU Privacy Guard, versiones recientes de PGP
•No esta bajo ninguna patente o sea de uso libre

• El procedimiento se refiere a unesquema de cifrado basado en problemas matemáticos de logaritmos discretos • Criptografía asimétrica basada en la idea de Diffie-Hellman • Puede ser utilizado para generar firmas digitales

•Seguridad: función de un sólo sentido y la dificultad de calcular un logaritmo discreto
• El procedimiento de des/cifrado esta basado en cálculos sobre un grupo cíclico

• Consta de tres componentes:generador de claves, algoritmos de des/cifrado

• Generación de llaves: p = num_primo * a = clv_priv A = clv_pub ::: ::: ::: g = generador * a Є {0, …, p-1} A = gᵅ (mod p)
*aleatorios

•Convertir el texto plano a un elemento de G, obteniendo m • Luego se escoge b(*) tal que b Є {0, …, p-1}, para calcular y₁ = gᵇ(mod p) ::: y₂ = Aᵇ m(mod p)

El mensaje cifrado corresponde a: Cb(m, b)=(y₁,y₂)
*aleatorio

• Se comienza con el siguiente calculo: m = yˣ₁. y₂(mod p);

x = p-1-a

y ₁ᴾ ¯¹¯ᵃ .y ₂ = gᵇ⁽ᴾ ¯¹¯ᵃ⁾. Aᵇ m = g⁽ᴾ ¯ ¹⁾ᵇ.g⁽ᵃ⁾¯ᵇ. Aᵇ m = A¯ᵇ. Aᵇ m ≡ m(mod p) NOTA: También existela solución de esta manera dk (y₁, y₂) = y₂(y₁¯ᵃ)(mod p)= m(mod p)

• Generación de llaves: p = 17 a=6 A = gᵅ (mod p) ::: ::: ::: g=3 a Є {0, …, p-1} A = 3⁶ (mod 17) = 15

Llave publica = (17, 3,15) Llave privada = (6)

•Dado un texto plano m=9
y₁ = 3⁵(mod 17) = 5 y₂ = 15 ⁵.9(mod 17) = 1 Mns_cfr:

:::

b = 5(*)

Cb(9, 5)=(5, 1) [tupla]
*aleatorio

Mns_cfr: Cb(9, 5)=(5, 1)[tupla] Llave publica = (17, 3, 15); Llave privada = (6) (1) m = y ₁ᴾ ¯¹¯ᵃ .y ₂ (mod p) = 5¹ᴼ.1(mod 17) = 9 (2) m = y₂(y₁¯a)(mod p) = 5¯⁶.1(mod 17) = 9

• Efectividad: el algoritmo de computación delogaritmos discretos es subexponencial con una complejidad de λ = 1/3 , la misma que la de factorizar dos números primos • Maleabilidad: debido a la función modulo un ataque especifico a las operaciones...