Introducción al algoritmo ElGamal

Método de generación de pares de claves: primero seleccione un número primo p y dos números aleatorios g y x (g, x < p), calcule y ≡ g^x (mod p), dada y, resuelva x es algo muy difícil (problema de resolución de logaritmos discretos), entonces su clave pública es y, gyp, y su clave privada es x, gyp, y puede ser compartida por un grupo de usuarios.

ElGamal se utiliza para firmas digitales. La información con signo es M, primero seleccione un número aleatorio k, k y p - 1 son primos relativos, calcule:

a ≡ g^k (mod p)

Luego use extendido Euclidiano El algoritmo resuelve b para la siguiente ecuación:

M ≡ xa + kb ( mod p - 1 )

La firma es ( a, b ). El número aleatorio k debe descartarse.

Se debe verificar la siguiente fórmula durante la verificación:

y^a * a^b ( mod p ) ≡ g^M ( mod p )

At al mismo tiempo, se debe comprobar si se cumple 1<= a < p. De lo contrario, la firma puede falsificarse fácilmente.

ElGamal se utiliza para el cifrado. La información cifrada es M, primero seleccione un número aleatorio k, k y p - 1 son primos relativos y calcule

a ≡ g^k (mod p)

b ≡ y ^k M ( mod p )

( a, b ) es el texto cifrado, que es el doble de largo que el texto sin formato. Calcular al descifrar

M ≡ b / a^x ( mod p )

La seguridad de las firmas de ElGamal se basa en el cálculo de logaritmos discretos en el grupo multiplicativo (IFp)*. El número primo p debe ser lo suficientemente grande y p-1 contiene al menos un número primo grande