Esquema de ElGamal

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 10 de mayo de 2018; las comprobaciones requieren 43 ediciones .

El esquema de Elgamal es un criptosistema de clave pública basado en la dificultad de calcular logaritmos discretos en un campo finito . El criptosistema incluye un algoritmo de cifrado y un algoritmo de firma digital. El esquema ElGamal subyace a los antiguos estándares de firma digital en los Estados Unidos ( DSA ) y Rusia ( GOST R 34.10-94 ).

El esquema fue propuesto por Taher El-Gamal en 1985 . [1] ElGamal desarrolló una variante del algoritmo Diffie-Hellman . Mejoró el sistema Diffie-Hellman y obtuvo dos algoritmos que se utilizaron para el cifrado y la autenticación. A diferencia de RSA, el algoritmo ElGamal no estaba patentado y, por lo tanto, se convirtió en una alternativa más económica, ya que no se requerían tarifas de licencia. Se cree que el algoritmo está cubierto por la patente Diffie-Hellman.

Generación de claves

Se genera un número primo aleatorio . $pags$
Se elige un número entero , la raíz primitiva . $gramo$ $pags$
Se elige un entero aleatorio tal que . $X$ ${\ estilo de visualización (1<x<p-1)}$
Calculado . $y=g^{x}{\bmod {p}}$
La clave pública es , la clave privada es . ${\ estilo de visualización (y, g, p)}$ $X$

Trabajar en modo cifrado

El sistema de cifrado ElGamal es en realidad una de las formas de generar claves públicas Diffie-Hellman . El cifrado de ElGamal no debe confundirse con el algoritmo de firma digital de ElGamal.

Cifrado

El mensaje debe ser menor que . El mensaje se cifra de la siguiente manera: $METRO$ $pags$

Se elige la clave de sesión : un entero aleatorio coprimo con , tal que . $(pag-1)$ $k$ ${\ estilo de visualización 1<k<p-1}$
Los números y se calculan . $a=g^{k}{\bmod {p))$ $b=y^{k}M{\bmod {p}}$
Un par de números es un texto cifrado . $(a, b)$

Es fácil ver que la longitud del texto cifrado en el esquema de ElGamal es el doble de la longitud del mensaje original . $METRO$

Descifrado

Conociendo la clave privada , el mensaje original se puede calcular a partir del texto cifrado mediante la fórmula: $X$ $(a, b)$

M=b(a^{x})^{-1}{\bmod {p)).

Al mismo tiempo, es fácil comprobar que

(a^{x})^{-1}=g^{-kx}{\bmod {p))

y por lo tanto

b(a^{x})^{-1}=(y^{k}M)g^{-xk}\equiv (g^{xk}M)g^{-xk}\equiv M {\pmod {p}}

Para cálculos prácticos, la siguiente fórmula es más adecuada:

M=b(a^{x})^{-1}=ba^{(p-1-x)}{\pmod {p))

Esquema de cifrado

Ejemplo

Cifrado
1. Digamos que queremos cifrar un mensaje . ${\ estilo de visualización M = 5}$
2. Generamos las claves:
  1. deja _ Elijamos un entero aleatorio tal que . ${\ estilo de visualización p = 11, g = 2}$ ${\ estilo de visualización x = 8}$ $X$ ${\ estilo de visualización 1 <x <p}$
  2. Calculemos . $y=g^{x}{\bmod {p}}=2^{8}{\bmod {11}}=3$
  3. Entonces, la clave pública es 3 y la clave privada es el número . ${\ estilo de visualización (p, g, y) = (11,2,3)}$ ${\ estilo de visualización x = 8}$
3. Elija un número entero aleatorio tal que 1 < k < (p − 1). deja _ $k$ ${\ estilo de visualización k = 9}$
4. Calculamos el número . $a=g^{k}{\bmod {p}}=2^{9}{\bmod {11}}=512{\bmod {11}}=6$
5. Calculamos el número . $b=y^{k}M{\bmod {p}}=3^{9}5{\bmod {11}}=19683\cdot 5{\bmod {11}}=9$
6. El par resultante es el texto cifrado. ${\ estilo de visualización (a, b) = (6,9)}$
Descifrado
1. Debe recibir un mensaje utilizando un texto cifrado conocido y una clave privada . ${\ estilo de visualización M = 5}$ ${\ estilo de visualización (a, b) = (6,9)}$ ${\ estilo de visualización x = 8}$
2. Calculamos M por la fórmula: $M=b(a^{x})^{-1}{\bmod {p}}=9(6^{8})^{-1}\mod {11}=5$
3. Recibí el mensaje original . ${\ estilo de visualización M = 5}$

Dado que se introduce una variable aleatoria en el esquema de ElGamal , el cifrado de ElGamal puede denominarse cifrado de sustitución multivaluado. Debido a la aleatoriedad de la elección del número, este esquema también se denomina esquema de cifrado probabilístico. La naturaleza probabilística del cifrado es una ventaja para el esquema de ElGamal, ya que los esquemas de cifrado probabilístico muestran una mayor solidez en comparación con los esquemas con un proceso de cifrado específico. La desventaja del esquema de cifrado de ElGamal es que el texto cifrado tiene el doble de longitud que el texto sin formato. Para un esquema de cifrado probabilístico, el mensaje en sí y la clave no definen de manera única el texto cifrado. En el esquema de ElGamal, es necesario utilizar diferentes valores de una variable aleatoria para encriptar diferentes mensajes y archivos . Si usa el mismo , entonces para los textos cifrados correspondientes y la relación se cumple . A partir de esta expresión se puede calcular fácilmente , si se sabe . $k$ $k$ $METRO$ $k$ $METRO$ $METRO'$ $k$ $(a, b)$ $(a',b')$ $b(b')^{{-1}}=M(M')^{{-1}}$ $METRO'$ $METRO$

Trabajando en modo firma

La firma digital sirve para permitir identificar cambios en los datos y establecer la identidad del firmante. El destinatario de un mensaje firmado puede utilizar una firma digital para demostrar a un tercero que la firma fue realizada por el remitente. Cuando se trabaja en modo firma, se supone que existe una función hash fija , cuyos valores se encuentran en el intervalo . $h(\cdot)$ $\izquierda(1,p-1\derecha)$

Firmas de mensajes

Para firmar un mensaje , se realizan las siguientes operaciones: $METRO$

El resumen del mensaje se calcula : (La función hash puede ser cualquiera). $METRO$ ${\ estilo de visualización m = h (M).}$
Se elige y calcula un número aleatorio coprimo con ${\ estilo de visualización 1<k<p-1}$ $p-1$ $r=g^{k}\,{\bmod {\,}}p.$
El número se calcula , donde es el módulo inverso multiplicativo , que se puede encontrar, por ejemplo, usando el algoritmo de Euclides extendido . $s\,=\,(m-xr)k^{-1}{\pmod {p-1))$ $k^{{-1}}$ $k$ $p-1$
La firma del mensaje es la pareja . $METRO$ $\izquierda(r,s\derecha)$

Verificación de firma

Conociendo la clave pública , la firma del mensaje se verifica de la siguiente manera: $\izquierda(p,g,y\derecha)$ $\izquierda(r,s\derecha)$ $METRO$

Se comprueba la viabilidad de las condiciones: y . ${\ estilo de visualización 0 <r <p}$ ${\ estilo de visualización 0 <s <p-1}$
Si al menos uno de ellos falla, la firma se considera inválida.
El resumen se calcula ${\ estilo de visualización m = h (M).}$
Una firma se considera válida si se hace una comparación: $y^{r}r^{s}\equiv g^{m}{\pmod {p)).$

Comprobación de corrección

El algoritmo considerado es correcto en el sentido de que la firma calculada según las reglas anteriores será aceptada cuando sea verificada.

Transformando la definición , tenemos $s$

m\,\equiv \,xr+sk{\pmod {p-1)).

Además, del pequeño teorema de Fermat se sigue que

{\begin{alineado}g^{m}&\equiv g^{xr}g^{ks}\\&\equiv (g^{x})^{r}(g^{k}) ^{s}\\&\equiv (y)^{r}(r)^{s}{\pmod {p}}.\\\end{alineado}}

Ejemplo

Firma del mensaje.
1. Digamos que queremos firmar un mensaje . $M=baaqab$
2. Generamos las claves:
  1. Que las variables sean conocidas por alguna comunidad. ${\ estilo de visualización p = 23}$ ${\ estilo de visualización g = 5}$
  2. La clave secreta es un número entero aleatorio tal que . $x=7$ $X$ ${\ estilo de visualización 1 <x <p}$
  3. Calcular la clave pública : . $y$ $y=g^{x}{\bmod {p}}=5^{7}{\bmod {2}}3=17$
  4. Entonces la clave pública es 3 . ${\ estilo de visualización (p, g, y) = (23,5,17)}$
3. Ahora calculamos la función hash: . $h(M)=h(baaqab)=m=3$
4. Elijamos un entero aleatorio tal que se cumpla la condición . deja _ $k$ $1<k<p-1$ ${\ estilo de visualización k = 5}$
5. Calcular r = g^k mod p = 5^5 mod 23 = 20.
6. encontramos _ Tal número existe porque GCD . Se puede encontrar usando el algoritmo de Euclides extendido. Obtener $k^{-1}$ ${\ estilo de visualización (k, p-1) = 1}$ $k^{-1}=5^{-1}{\pmod {22}}=9$
7. Encontrar un número . lo conseguimos porque $s\,\equiv\,(m-xr)k^{{-1}}{\pmod {p-1}}$ ${\ estilo de visualización s = 21}$ $s=\,(3-7\cdot 20)5^{-1}{\pmod {22}}=21$
8. Entonces, firmamos el mensaje: . $<baaqab,20,21>$

Autenticación del mensaje recibido.
1. Calculamos la función hash: . $h(M)=h(baaqab)=m=3$
2. Veamos la comparación . $y^{r}\cdot r^{s}{\pmod {p}}\equiv g^{m}{\pmod {p}}$
3. Calcule el lado izquierdo módulo 23: . $17^{20}\cdot 20^{21}{\bmod {2}}3=16\cdot 15{\bmod {2}}3=10$
4. Calcular el lado derecho módulo 23: . $5^{3}{\bmod {2}}3=10$
5. Dado que las partes derecha e izquierda son iguales, esto significa que la firma es correcta.

La principal ventaja del esquema de firma digital de ElGamal es la capacidad de generar firmas digitales para una gran cantidad de mensajes usando solo una clave secreta. Para que un atacante falsifique una firma, necesita resolver problemas matemáticos complejos para encontrar el logaritmo en el campo . Se deben hacer varios comentarios:

\mathbb {Z} _{p}

El número aleatorio debe destruirse inmediatamente después de calcular la firma, porque si un atacante conoce el número aleatorio y la firma en sí, puede encontrar fácilmente la clave secreta usando la fórmula: y falsificar completamente la firma. $k$ $k$ $x=(m-ks)r^{-1}{\bmod {(}}p-1)$

El número debe ser aleatorio y no debe duplicarse para diferentes firmas obtenidas con el mismo valor de clave secreta. $k$

El uso del plegado se explica por el hecho de que protege la firma de la enumeración de mensajes según los valores de firma conocidos por el atacante. Ejemplo: si elige números aleatorios que cumplen las condiciones , mcd(j,p-1)=1 y asume que ${\ estilo de visualización m = h (M)}$ $yo, j$ $0<i<{p-1},0<j<{p-1}$ $r=g^{i}\cdot y^{-j}{\bmod {p}}$ $s=r\cdot j^{-1}{\bmod {(}}p-1)$ $m=r\cdot i\cdot j^{-1}{\bmod {(}}p-1)$

es fácil verificar que el par es la firma digital correcta para el mensaje . $(r, s)$ ${\ estilo de visualización x = M}$

La firma digital de ElGamal se ha convertido en un ejemplo de construcción de otras firmas similares en sus propiedades. Se basan en la comparación: , en la que el triple toma los valores de una de las permutaciones ±r, ±s y ±m para alguna elección de signos. Por ejemplo, el esquema original de ElGamal se obtiene con , , Los estándares de firma digital de EE. UU. y Rusia se basan en este principio de construcción de una firma. En el DSS americano (Digital Signature Standard) se utilizan los valores , , , y en el estándar ruso: , , . $y^{A}\cdot r^{B}=g^{C}(modp)$ ${\ estilo de visualización (A, B, C)}$ ${\ estilo de visualización A = r}$ ${\ estilo de visualización B = s}$ ${\ estilo de visualización C = m}$ ${\ estilo de visualización A = r}$ ${\ estilo de visualización B = -s}$ ${\ estilo de visualización C = m}$ ${\ estilo de visualización A = -x}$ $B=-m$ ${\ estilo de visualización C = s}$
Otra ventaja es la posibilidad de reducir la longitud de la firma reemplazando un par de números con un par de números , donde es un divisor simple del número . En este caso, la comparación para la verificación de la firma del módulo debe reemplazarse con un nuevo módulo de comparación : . Esto se hace en el American DSS (Digital Signature Standard). ${\ estilo de visualización (s, m)}$ $(s{\bmod {q}},m{\bmod {q}}$ $q$ $(p-1)$ $pags$ $q$ $(~y^{A}\cdot r^{B}){\bmod p}=g^{C}{\pmod {q))$

Fuerza y características criptográficas

Actualmente, los criptosistemas de clave pública se consideran los más prometedores. Estos incluyen el esquema de ElGamal, cuya fortaleza criptográfica se basa en la complejidad computacional del problema del logaritmo discreto , donde, dadas p , g e y , se requiere calcular x que satisfaga la comparación:

y\equiv g^{x}{\pmod {p)).

GOST R34.10-1994 , adoptado en 1994 en la Federación Rusa, que regulaba los procedimientos para generar y verificar una firma digital electrónica, se basó en el esquema ElGamal. Desde 2001, se utiliza el nuevo GOST R 34.10-2001 , que utiliza la aritmética de curvas elípticas definidas sobre campos de Galois simples . Hay una gran cantidad de algoritmos basados en el esquema ElGamal: estos son algoritmos DSA , ECDSA , KCDSA, esquema Schnorr .

Comparación de algunos algoritmos:

Algoritmo	Llave	Objetivo	Resistencia criptográfica, MIPS	notas
RSA	Hasta 4096 bits	Cifrado y firma	2.7•10 28 para clave de 1300 bits	Basado en la dificultad del problema de factorización de números grandes ; uno de los primeros algoritmos asimétricos. Incluido en muchos estándares
ElGamal	Hasta 4096 bits	Cifrado y firma	Para la misma longitud de clave, la fuerza criptográfica es igual a RSA, es decir 2.7•10 28 para clave de 1300 bits	Basado en el difícil problema de calcular logaritmos discretos en un campo finito; le permite generar claves rápidamente sin comprometer la seguridad. Utilizado en el algoritmo de firma digital del DSS estándar DSA
DSA	Hasta 1024 bits	Solo firma		Basado en la dificultad del problema del logaritmo discreto en un campo finito ; aceptado como estado estándar de EE. UU.; utilizado para comunicaciones secretas y no clasificadas; El desarrollador es la NSA.
ECDSA	Hasta 4096 bits	Cifrado y firma	La criptorresistencia y la velocidad de funcionamiento son superiores a las de RSA	Dirección moderna. Desarrollado por muchos matemáticos destacados

Notas

↑ Elgamal, 1985 .

Literatura

Elgamal T. Un criptosistema de clave pública y un esquema de firma basado en logaritmos discretos, un criptosistema de clave pública y un esquema de firma basado en logaritmos discretos // IEEE Trans . inf. Teoría / F. Kschischang - IEEE , 1985. - Vol. 31, edición. 4.- Pág. 469-472. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1985.1057074 ; doi:10.1007/3-540-39568-7_2
Alferov A.P., Zubov A.Yu., Kuzmin A.S., Cheremushkin A.V. Fundamentos de criptografía.[ aclarar ]
B. A. Forouzan. Esquema de firma digital El-Gamal // Gestión de claves de cifrado y seguridad de red / Per. A. N. Berlín. - Curso de lectura.
Menezes A. J. , Oorschot P. v. , Vanstone S. A. 11.5.2 El esquema de firma de ElGamal // Manual de criptografía aplicada (inglés) - CRC Press , 1996. - 816 p. - ( Matemáticas discretas y sus aplicaciones ) - ISBN 978-0-8493-8523-0

Criptosistemas de clave pública

Algoritmos

Factorización de números enteros	criptosistema Benalo Bluma - Goldwasser Cayley sobrecargo Damgorda - Eureka GMR Goldwasser-Micali Nakasha - popa paga Rabín RSA Okamoto-Uchiyama Schmidt-Samoa
logaritmo discreto	BLS Cramer - Shoup Protocolo de Diffie-Hellman DSA ECDH Curva25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Intercambio de claves cifradas Esquema de ElGamal esquema de firma MQV esquema de Schnorr HABLA PVP STS
Criptografía en celosías	NTRUEncriptar NTRUSign Intercambio de claves basado en el aprendizaje con errores Entrenamiento basado en firmas con errores en el ring FELICIDAD Nueva Esperanza
Otro	AE CEILIDH EPOC Ecuaciones de campo ocultas IES la firma de lamport McEliece Criptosistema de mochila Merkle-Hellman Criptosistema de mochila Naccache-Stern Protocolo de tres pasos XTR

Teoría

Logaritmo discreto en una curva elíptica
Criptografía elíptica
Criptografía basada en hash
Criptografía no conmutativa
problema RSA
Función unidireccional con entrada secreta

Estándares

CRYPTREC
IEEE P1363
NESSIE
Paquete B de la NSA
Criptografía post cuántica

Temas

Firma electronica
OAEP
Huella dactilar
PKI
red de confianza
Tamaño de clave
Criptografía basada en identidad
Criptografía poscuántica
Tarjeta OpenPGP

Esquema de ElGamal

Generación de claves

Trabajar en modo cifrado

Cifrado

Descifrado

Esquema de cifrado

Ejemplo

Trabajando en modo firma

Firmas de mensajes

Verificación de firma

Comprobación de corrección

Ejemplo

Fuerza y ​​características criptográficas

Notas

Literatura

Fuerza y características criptográficas