estudiante

ElGamal

Esquema de firma digital basado en la
complejidad del cálculo del logaritmo
discreto

Algoritmo asimétrico ElGamal
Taher ElGamal propone en 1985 un algoritmo que hace uso delproblema del logaritmo discreto PLD.
Este algoritmo fue diseñado específicamente para firma digital

Algoritmo asimétrico El Gamal
Se elige un grupo multiplicativo Zp*, donde p es un primo grande
Delgrupo p se elige una raíz α, generador del grupo
Cada usuario elige un número aleatorio λ dentro de p
El valor λ será la clave privada
Cada usuario calcula αλ mod p
Los valores (αλ mod p) y pserán la clave pública
Seguridad del sistema
Para descubrir la clave privada, el atacante deberá enfrentarse
al problema del logaritmo discreto para p grandehttp://web.usna.navy.mil/~wdj/book/node48.html

ë

Operación de cifra con ElGamal
Operación Cifrado: A cifra un número N que envía a B
El usuario B ha elegido su clave privada b dentro del
cuerpo del número primo p que es público.El usuario B ha hecho pública su clave αb mod p.
El emisor A genera un número aleatorio ν de sesión y
calcula αν mod p.
Con la clave pública de B (αb) el emisor A calcula:
(αb)ν mod p
A envía a Bel par:

y

N∗(αb)ν mod p
C = [αν mod p, N∗(αb)ν mod p]

Operación de descifrado con ElGamal
Operación Descifrado: B descifra el criptograma C que envía A
El usuario B recibe C = [αν mod p,N∗(αb)ν mod p].
B toma el valor αν mod p y calcula (αν)b mod p.
B descifra el criptograma C haciendo la siguiente división:
[N∗(αb)ν mod p ] / [(αν)b mod p] ... porque (αb)ν = (αν)b
El pasoanterior es posible hacerlo porque existirá el
inverso de (αν)b en el grupo p al ser p un primo. Luego:
[N∗(αb)ν ∗ {inv (αν)b, p}] mod p = N

Ejemplo de cifrado con ElGamal
Adela (A) enviará a Benito(B) el número N = 10 cifrado
dentro del cuerpo p = 13 que usa Benito.
CIFRADO
Claves públicas de Benito: p = 13, α = 6, (αb) mod p = 2
Adela (A) elige por ejemplo ν = 4 y calcula:
(αν) mod p =...