TellezGonzalezJorgeLuis_ElGamal

Vista previa del material en texto

Universidad Nacional Autónoma de México
Facultad de Ingeniería
Criptografía
Grupo: 02 - Semestre: 2023-2
Tarea:
Lectura ElGamal.
Fecha de entrega: 27/03/2023
Profesora:
Dra. Rocío Alejandra Aldeco Pérez
Alumno:
Téllez González Jorge Luis
Facultad de Ingeniería Criptografía______________________________________________________________________________________________________________
Introducción
El algoritmo ElGamal es un algoritmo de cifrado de clave pública que se basa en la
di�cultad del problema del logaritmo discreto. Fue propuesto por Taher ElGamal en 1985 y
es similar en muchos aspectos al esquema de Di�e-Hellman.
El algoritmo ElGamal se utiliza para cifrar y descifrar mensajes y también puede ser
utilizado para �rmar digitalmente mensajes. Consiste en generar una clave pública y una
clave privada. La clave pública se comparte con otros para que puedan cifrar los mensajes y
la clave privada se mantiene en secreto para descifrar los mensajes. El proceso de cifrado en
ElGamal implica la elección de un número aleatorio y el cálculo de una serie de operaciones
matemáticas. El proceso de descifrado utiliza la clave privada y las mismas operaciones
matemáticas para obtener el mensaje original.
En el artículo se presenta el sistema de �rma y cifrado ElGamal basado en logaritmos
discretos sobre campos �nitos. Este sistema se implementa utilizando el esquema de
distribución de clave de Di�e-Hellman, donde la seguridad de ambos sistemas depende de
la di�cultad de calcular logaritmos discretos. El texto también menciona algunos intentos
previos de crear sistemas de clave pública basados en otros problemas matemáticos, como el
sistema RSA basado en la factorización de enteros grandes. A continuación, se presenta un
documento del texto.
Desarrollo
El sistema de clave pública
El texto describe el sistema de clave pública basado en el algoritmo de distribución de claves
Di�e-Hellman. En este sistema, A y B comparten una clave secreta mediante el uso de un
número primo grande p y un elemento primitivo a. También se describe cómo se puede
utilizar este sistema para cifrar y descifrar mensajes.
Así mismo, el tamaño del texto cifrado es el doble del tamaño del mensaje original y
no se recomienda utilizar el mismo valor para cifrar más de un bloque del mensaje. El texto
concluye que romper este sistema es equivalente a romper el esquema de distribución
de claves Di�e-Hellman y que la elección de p es importante para garantizar la seguridad
del sistema.
2
Facultad de Ingeniería Criptografía______________________________________________________________________________________________________________
Un esquema de �rma digital
Para �rmar un documento m, un usuario A debe poder usar la clave secreta xA para
encontrar una �rma para m de tal manera que todos los usuarios puedan veri�car la
autenticidad de la �rma usando la clave pública yA (junto con a y p), y nadie pueda falsi�car
una �rma sin conocer el secreto xA.
La �rma para m es el par (r, s), donde 0 ≤ r, s ≤ p - 1, elegido de tal manera que la
ecuación a^m = y^r * t^s mod p se satisfaga.
El procedimiento de �rma consiste en 3 pasos:
1. Elegir un número aleatorio k uniformemente entre 0 y p - 1, tal que gcd (k, p - 1) =
1.
2. Calcular r= a^k mod p.
3. Calcular s resolviendo la ecuaciónm = xr + ks mod (p-1).
El procedimiento de veri�cación es simplemente comprobar que ambas partes de la
ecuación anterior son iguales. Cabe señalar que nunca se debe usar el mismo valor de kmás
de una vez.
Ataques en el esquema de �rmado digital
Algunos de estos ataques se demuestran fácilmente como equivalentes al cálculo de
logaritmos discretos sobre GF(p). Aún no se ha demostrado que romper el esquema de
�rma sea equivalente a calcular logaritmos discretos o equivalente a romper el esquema de
distribución. Sin embargo, ninguno de los ataques presentados en esta sección parece
romper el sistema.
Los ataques se dividirán en dos grupos. El primer grupo incluye algunos ataques
para recuperar la clave secreta x, y en el segundo grupo se muestran algunos ataques para
falsi�car �rmas sin recuperar x.
Ataques para recuperar x
Uno de estos ataques consiste en tratar de resolver un sistema de ecuaciones con l
ecuaciones, utilizando I documentos y sus correspondientes �rmas. Debido a que hay I + 1
incógnitas (ya que cada �rma utiliza un k diferente), el sistema es indeterminado y él
3
Facultad de Ingeniería Criptografía______________________________________________________________________________________________________________
número de soluciones es grande. Cada valor de k genera una solución diferente y dado que
p - 1 tiene al menos un factor primo grande q, recuperar x mod q requeriría un número
exponencial de pares mensaje-�rma.
Ataques para falsi�car �rmas
Un forjador puede intentar encontrar r y s que satisfagan a^m = y^r r^s mod p para un
documento m. Si r = a^j mod p está �jo para algún j elegido al azar, entonces calcular s es
equivalente a resolver un problema de logaritmo discreto sobreGF(p).
Si el forjador tiene s primero, entonces r podría ser calculado a partir de la ecuación y^r *
r^s = A mod p. Resolver la ecuación para r aún no se ha demostrado que sea tan difícil
como calcular logaritmos discretos, pero se cree que no es factible resolver (7) en tiempo
polinómico.
El esquema de �rma permite un ataque en el que el intruso, conociendo una �rma
legítima para un mensaje, puede generar otras �rmas y mensajes legítimos. Esta propiedad
existe en todos los esquemas de �rma digital existentes y se puede evitar requiriendo quem
tenga una cierta estructura, o aplicando una función unidireccional al mensaje m antes de
�rmarlo.
Propiedades del sistema y comparaciones con otros esquemas
El tamaño de los números utilizados en el sistema propuesto debe ser similar al tamaño de
los números utilizados en otros sistemas de clave pública, como el sistema RSA, para
obtener el mismo nivel de seguridad. Sin embargo, esto implica que el tamaño del archivo
público es más grande que el del sistema RSA, ya que cada usuario tiene una entrada n en su
clave pública y la clave de cifrado en el archivo público.
Además, se menciona que el algoritmo conocido más efectivo para resolver tanto el
problema del logaritmo discreto como el problema de factorización de enteros tiene una
complejidad de O(exp sqrt(cm ln m)), donde c es aproximadamente 0.89 para ambos
problemas.
4
Facultad de Ingeniería Criptografía______________________________________________________________________________________________________________
Propiedades del sistema de clave pública
Debido a la aleatorización en la operación de cifrado presentada, el texto cifrado para un
mensaje dado no se repite y no hay relación obvia entre el cifrado de diferentes mensajes.
Además, se requieren dos exponenciaciones para cifrar y solo una exponenciación para
descifrar. El tamaño del texto cifrado es el doble del tamaño del texto cifrado RSA
correspondiente.
Propiedades del esquema de cifrado
En este esquema y RSA, el tamaño de la �rma es el doble del tamaño del documento.
Entonces, el tamaño de la �rma es el mismo con respecto con respecto a RSA, y la mitad del
tamaño de la �rma para el nuevo esquema de �rma que depende de LAS formas cuadráticas
publicadas por Ong y Schnorr, y también deOng, Schnorr y Shamir (ya que ambos sistemas
se basan en el problema de factorización entera). Dado que el sistemaOng-Schnorr-Shamir
ha sido comprometido, no está claro si un sistema seguro basado en ecuaciones modulares
se puede encontrar.
Cada documento tiene muchas �rmas, pero cualquier �rma solo �rma un
documento. Para el procedimiento de �rma, se necesita una exponenciación (más algunas
multiplicaciones). Para veri�car una �rma, se necesitan tres exponenciaciones, pero se puede
reducir a 1.675 exponenciaciones mediante una representación binaria de los exponentes.
Se espera que se necesite una multiplicación el 87.5% del tiempo.
Conclusiones
ElGamal emplea la di�cultad del problema del logaritmo discreto parasu esquema, lo que
lo hace resistente a los ataques de criptoanálisis. Adicionalmente, su sistema de �rma digital
es seguro y efectivo en la autenticación de documentos.
Sin embargo, debido al tamaño de los textos cifrados y �rmas digitales, el sistema
puede ser menos e�ciente en términos de velocidad de procesamiento y almacenamiento de
datos en comparación con otros sistemas criptográ�cos. En general, ElGamal sigue siendo
una opción viable para la seguridad de la información en la comunicación moderna,
especialmente cuando se trata de la privacidad de las comunicaciones en línea y la
autenticación de remitentes sobre la red.
5
Facultad de Ingeniería Criptografía______________________________________________________________________________________________________________
Referencias
ElGamal, T. (1985). A Public Key Cryptosystem and a Signature Scheme based on Discrete
Logarithms. https://ieeexplore.ieee.org/document/1057074
6