Criptografía (CCLXXXV): Generación de claves ElGamal en python

Continúo poniendo scripts de programación en python para automatizar tareas que tengan relación con la criptografía.

En este post incluyo un script en python para la generación del par de claves de un usuario, pública y privada, en ElGamal.

Antes de poner el script, recordar que en este post expliqué cómo se generaban ambas claves en este criptosistema, que debe su nombre al criptógrafo egipcio Taher Elgamal que lo describió en 1984.

Conforme a lo que indiqué en el citado post, la generación del par de claves para un usuario consiste en:

1.- Se elige un número primo 'p' muy grande y un generador 'g' o raíz primitiva módulo 'p'. Al igual que en el intercambio de clave de Diffie-Hellman y por el mismo motivo, se puede obviar que 'g' sea un generador 'g' o raíz primitiva módulo 'p', aunque es recomendable que sí lo sea.

2.- Se escoge aleatoriamente un número 'a' mayor que cero y menor que 'p'.

3.- Se calcula k = g^a mod p.

4.- La clave pública será (p, g, k).

5.- La clave privada será (a).

Para que el script para la generación del par de claves funcione se necesita importar los dos siguientes módulos en el programa principal, que se encargarán, respectivamente, de la generación de un número primo aleatorio 'p' (mínimo de 2.048 bits) y de realizar la operación de exponenciación modular de forma eficiente.

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# GENERACIÓN DE UN NÚMERO PRIMO ALEATORIO:
#
# Generación de un número primo aleatorio a partir de un número de b bits.
#
# http://mikelgarcialarragan.blogspot.com/

from sympy import primerange, prime 
from random import randint, getrandbits

def test_miller_rabin(n,k):
# n = número natural mayor que 1 e impar del que queremos conocer si es primo.
# k = número de veces o rondas a ejecutar el test.
# t = indicador de que n es primo con un cierto nivel de confianza (0: primo; 1: compuesto).
# s = número de veces que 2 divide a n - 1.
    t = 0
    s = 0
    r = n - 1

    while r%2 == 0:
        s+=1
        r = r//2

    i=0 
    while i in range(0, k) and t != 1:
        a = randint(2, n - 1)
        j = 0
        y = pow(a, r, n)
        if y != 1 and y != n - 1:
            j = 1
            while y != n - 1 and t != 1 and j <= s - 1:
                y = pow(y, 2, n)
                if y == 1:
                    t = 1
                else:
                    j = j + 1
            if y != n -1:
                t = 1
        i = i + 1

    if t == 0:
        return True
    else:
        return False

def generar_primo_aleatorio(b,k):
# b = número de bits que tendrá como mínimo el número primo aleatorio.
# k = número de veces o rondas a ejecutar el test de primalidad.
# Se genera un número aleatorio impar (p) de b bits.
    p = getrandbits(int(b))
    if p%2 == 0:
        p+=1

# Se crea una lista con los primeros 2048 números primos, para descartar rápidamente aquellos
# candidatos no primos, es decir, aquellos que son divisibles por alguno de los números primos
# integrantes de esta lista.
    primeros_2048_primos = list(primerange(prime(2048 + 1)))

# Se realizan las comprobaciones tendentes a verificar si el candidato es primo con un cierto
# nivel de confianza.
    puede_ser_primo = False
    while not puede_ser_primo:
        puede_ser_primo = True
        for primo in primeros_2048_primos:
            if p%primo == 0:
                puede_ser_primo = False
                break
        # Si el candidato supera la primera criba, es decir no es divisible entre ninguno de los primeros
        # 2048 números primos, entonces se le somete al test de primalidad de Miller-Rabin.
        if puede_ser_primo:
            if not test_miller_rabin(p,int(k)):
                puede_ser_primo = False
        # Si el candidato no supera la primera criba, es decir es divisible entre alguno de los primeros
        # 2048 números primos o no supera el test de primalidad de Miller-Rabin, entonces se incrementa
        # al candidato en dos unidades y se vuelve a comprobar si el nuevo candidato puede ser primo.
        if not puede_ser_primo:
                p+=2

    return p

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# ALGORITMO DE EXPONENCIACIÓN MODULAR RÁPIDA:
#
# Algoritmo utilizado en operaciones de exponenciación modular
# con números muy grandes con objeto de hacerlas de forma
# más eficiente.
#
# http://mikelgarcialarragan.blogspot.com/

def exp_modular_rapida(b, e, m):
    c = 1
    e = bin(e)[2:]

    for i in range(0, len(e)):
        c = pow(c, 2, m)
        if e[i]=="1":
            c = c*b%m

    return c

El script es el siguiente:

- Script python para la generación del par de claves ElGamal, pública y privada, de un usuario:

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# ElGamal:
#
# Generación de las claves, pública (p, g, k) y privada (a), para un usuario.
#
# http://mikelgarcialarragan.blogspot.com/

import primo_aleatorio
import random
import pyasn1.type.univ
import pyasn1.codec.der.encoder
import base64
from time import time
from exponenciacion_modular_rapida import exp_modular_rapida

def pempubl(p, g, k):
    template = '-----BEGIN ELGAMAL PUBLIC KEY-----\n{}-----END ELGAMAL PUBLIC KEY-----\n'
    seq = pyasn1.type.univ.Sequence()
    for i,x in enumerate((p, g, k)):
        seq.setComponentByPosition(i, pyasn1.type.univ.Integer(x))
    der = pyasn1.codec.der.encoder.encode(seq)
    return template.format(base64.encodebytes(der).decode('ascii'))

def pempriv(p, g, k, a):
    template = '-----BEGIN ELGAMAL PRIVATE KEY-----\n{}-----END ELGAMAL PRIVATE KEY-----\n'
    seq = pyasn1.type.univ.Sequence()
    for i,x in enumerate((p, g, k, a)):
        seq.setComponentByPosition(i, pyasn1.type.univ.Integer(x))
    der = pyasn1.codec.der.encoder.encode(seq)
    return template.format(base64.encodebytes(der).decode('ascii'))

def main():
# MENÚ:
# Se presenta el menú para que se seleccione una opción.
    salir = False
    while not salir:
        print ("")
        print ("*** MENÚ *****************************************")
        print ("1. Generar par de claves.")
        print ("2. Salir.")
        print ("")
        opcion = input("Por favor, seleccione una opción: ")
        if opcion == "1":
            print ("")
            print ("--- GENERACIÓN DE LA CLAVE PÚBLICA Y PRIVADA PARA UN USUARIO:")
            # Se introducen el tamaño mínimo, número de bits, que tendrá el número primo aleatorio 'p' a generar y el generador 'g' o
            # raíz primitiva módulo 'p'.
            b = g = "*"
            while not b.isnumeric() or int(b) < 2048:
                b = input("Introduzca el número de bits, sin punto decimal y mayor o igual que 2048, que tendrá el número primo aleatorio 'p': ")
                if b.isnumeric() and int(b) >= 2048:
                    inicio_generacion_par_claves = inicio_generacion_primo = time()
                    print("[+] Generando número primo aleatorio 'p'...")
                    p = primo_aleatorio.generar_primo_aleatorio(b,5)
                    print("[+] Número primo aleatorio 'p' generado:", p)
                    print("[+] Tiempo de ejecucion de la generación del número primo aleatorio 'p':", time() - inicio_generacion_primo)
                    while not g.isnumeric() or int(g) < 1 or int(g) > p -1:
                        g = input("Introduzca el generador 'g' o raíz primitiva módulo 'p': ")
                        if g.isnumeric() and int(g) > 0 and int(g) < p:
                            a = random.randint(1, p-1)
                            k = exp_modular_rapida(int(g), a, p)
                            print("[+] Clave pública (p, g, k): (", p, ",", g, ",", k, ")")
                            print("[+] Clave privada (a): (", a)
                            print("[+] Tiempo de ejecucion de la generación del par de claves, pública y privada:", time() - inicio_generacion_par_claves)
                            publpem = pempubl(p, g, k)
                            print("[+] Clave pública en formato PEM:")
                            print(publpem)
                            with open("public.pem", "w") as f:
                                f.write(publpem)
                            privpem = pempriv(p, g, k, a)
                            print("[+] Clave privada en formato PEM:")
                            print(privpem)
                            with open("private.pem", "w") as f:
                                f.write(privpem)
                        else:
                            print ("*** ERROR: Generador 'g' o raíz primitiva módulo 'p' incorrecto. Debe ser un número natural, sin punto decimal, mayor que 0 y menor que 'p'.")
                else:
                    print ("*** ERROR: Número de bits incorrecto. Debe ser un número natural, sin punto decimal, mayor o igual que 2048.")
        elif opcion == "2":
            print ("*** FIN ******************************************")
            salir = True
        else:
            print ("*** ERROR: Opción no válida.")
	
if __name__ == '__main__':
    main()

Lo ejecuto:

El script muestra la clave pública (p, g, k) y la clave privada (a) generadas y guarda ambas en sendos archivos .PEM, para que puedan ser utilizadas en el cifrado (otro usuario con la clave pública del usuario para el que se ha generado este par de claves), descifrado y firma digital (el usuario para el que se ha generado este par de claves con la clave privada).

Quizás también te interese: