Criptografía (CCLXXVII): Generación de claves RSA 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 RSA.

Antes de poner el script, recordar que en este post expliqué cómo se generaban ambas claves en este criptosistema, posiblemente el algoritmo de cifrado asimétrico más utilizado actualmente y que debe su nombre a las iniciales de los apellidos de sus tres inventores: Ronald Rivest, Adi Shamir y Leonard Adleman, que lo desarrollaron en 1977.

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

1.-Se eligen aleatoriamente dos numero primos grandes (p y q), actualmente de un tamaño mínimo de 1.024 bits cada uno de ellos, y se calcula el producto (n) de ambos. Es decir, n = pq.

2.- Se calcula la función de Euler del módulo (n), que para dos números primos es: j(n) = (p - 1)(q - 1).

3.- Se escoge un número e (de 'encrypt'), en el intervalo 1 < e < j(n), que sea coprimo o primo relativo con j(n), es decir, de forma que el máximo común divisor de e y j(n) sea 1 (mcd(e, j(n))= 1). La clave pública será (e, n).

Como valor estándar de e se utiliza el número 4 de Fermat: 65.537 (un número primo de 17 bits).

4.- Se calcula, mediante el algoritmo de Euclides extendido el inverso mutiplicativo d (de 'decrypt') de e módulo j(n), es decir, que satisfaga: de º 1 mod (j(n)). La clave privada será (d, n).

Para que el script para la generación del par de claves funcione se necesita importar el siguiente módulo en el programa principal, que se encargará de generar los dos números primos aleatorios, p y q.

#!/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

El script es el siguiente:

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

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

# RSA:
#
# Generación de las claves, pública (e, n) y privada (d,n), para un usuario.
#
# http://mikelgarcialarragan.blogspot.com/

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

def pempubl(n, e):
    template = '-----BEGIN RSA PUBLIC KEY-----\n{}-----END RSA PUBLIC KEY-----\n'
    seq = pyasn1.type.univ.Sequence()
    for i,x in enumerate((n, e)):
        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(n, e, d, p, q):
    template = '-----BEGIN RSA PRIVATE KEY-----\n{}-----END RSA PRIVATE KEY-----\n'
    seq = pyasn1.type.univ.Sequence()
    dP = d%(p-1)
    dQ = d%(q-1)
    qInv = pow(q, -1, p)
    for i,x in enumerate((0, n, e, d, p, q, dP, dQ, qInv)):
        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 introduce el tamaño mínimo, número de bits, que tendrán los números primos aleatorios p y q a generar
            b = "*"
            while not b.isnumeric() or int(b) < 1024:
                b = input("Introduzca el número de bits, sin punto decimal y mayor o igual que 1024, que tendrán los números primos aleatorios 'p' y 'q' a generar: ")
                if b.isnumeric() and int(b) >= 1024:
                    inicio_generacion_par_claves = inicio_generacion_primo = time()
                    print("[+] Generando número primo aleatorio 'p'...")
                    p = q = 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)
                    inicio_generacion_primo = time()
                    print("[+] Generando número primo aleatorio 'q'...")
                    while p == q:
                        q = primo_aleatorio.generar_primo_aleatorio(b,5)
                    print("[+] Número primo aleatorio 'q' generado:", q)
                    print("[+] Tiempo de ejecucion de la generación del número primo aleatorio 'q':", time() - inicio_generacion_primo)
                    n = p * q
                    print("[+] Módulo 'n':", n)
                    phi = (p-1) * (q-1)
                    print("[+] 'phi':", phi)
                    e = 65537
                    print("[+] Clave pública (e, n): (",e, ",", n,")")
                    d = pow(e, -1, phi)
                    print("[+] Clave privada (d, n): (",d, ",", n,")")
                    print("[+] Tiempo de ejecucion de la generación del par de claves, pública y privada:", time() - inicio_generacion_par_claves)
                    publpem = pempubl(n, e)
                    print("[+] Clave pública en formato PEM:")
                    print(publpem)
                    with open("public.pem", "w") as f:
                        f.write(publpem)
                    privpem = pempriv(n, e, d, p, q)
                    print("[+] Clave privada en formato PEM:")
                    print(privpem)
                    with open("private.pem", "w") as f:
                        f.write(privpem)
                else:
                    print ("*** ERROR: Número de bits incorrecto. Debe ser un número natural, sin punto decimal, mayor o igual que 1024.")
        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 (e, n) y la clave privada (d , n) 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: