Criptografía (CCLXXXI): Intercambio de clave de Diffie-Hellman 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  implementar el intercambio de clave de Diffie-Hellman.

Antes de poner el script, recordar que en este post decía que este protocolo criptográfico se utiliza para el intercambio seguro de una clave entre dos interlocutores a través de un canal inseguro, como puede ser Internet, sin poner en peligro el secreto de ésta si las comunicaciones entre ambos son interceptadas por un tercero.

El script simula el intercambio de clave, por ejemplo: una clave de sesión para ser utilizada en el cifrado y descifrado de mensajes mediante AES, entre Alicia (A) y Bernardo (B), de la siguiente manera:

1.- A genera un número primo aleatorio 'p' de 2.048 bits y se lo envía a B junto con el número 5, que le propone utilizar como número 'g' para este intercambio de clave.

2.- A introduce una frase de contraseña de la que se calcula el hash SHA-256 para obtener su número 'a', que será secreto (sólo ella debe conocerlo), y envía a B el resultado de la operación g^a mod p.

3.- B introduce su frase de contraseña de la que se calcula el hash SHA-256 para obtener su número 'b', que será secreto (sólo él debe conocerlo), y envía a A el resultado de la operación g^b mod p.

4.-  A y B calculan, cada uno de forma separa del otro, la clave de sesión ('k') que van a compartir en el cifrado y descifrado de mensajes mediante AES:

4.1.- A calcula: k = (g^b mod p)^a mod p.

4.2.- B clacula: k = (g^a mod p)^b mod p.

5.- Se comprueba que la clave de sesión calculada por ambos de forma independiente es la misma y, por tanto, se concluye si el intercambio se ha realizado con éxito o no.

Para que el script funcione se necesita importar los dos siguientes módulos en el programa principal, que se encargarán, respectivamente, de la generación del número primo 'p' de 2.048 bits y de realizar las operaciones 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 el intercambio de clave de Diffie-Hellman:

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

# INTERCAMBIO DE CLAVE DE DIFFIE-HELLMAN:
#
# Protocolo Diffie-Hellman para el intercambio seguro de una clave de sesión a través de un canal inseguro.
#
# http://mikelgarcialarragan.blogspot.com/

import hashlib
import primo_aleatorio
from exponenciacion_modular_rapida import exp_modular_rapida

def main():
# MENÚ:
# Se presenta el menú para que se seleccione una opción.
    salir = False
    while not salir:
        print ("")
        print ("*** MENÚ *****************************************")
        print ("1. Intercambio de clave de sesión entre A y B.")
        print ("2. Salir.")
        print ("")
        opcion = input("Por favor, seleccione una opción: ")
        if opcion == "1":
            print ("")
            print ("--- INTERCAMBIAR CLAVE DE SESIÓN ENTRE A Y B:")
            print ("*** A genera un número primo aleatorio 'p' de 2.048 bits y escoge 'g' = 5")
            p = primo_aleatorio.generar_primo_aleatorio(2048,5)
            g = 5
            print ("[+] Número primo aleatorio 'p' generado:", p)
            print ("[+] Número 'g' escogido:", g)
            print ("*** A envía a B el número primo aleatorio 'p' y 'g'")
            print ("*** A introduce una frase de contraseña de la que se calcula el hash SHA-256 para obtener su número secreto 'a'")
            frase_password = ""
            while frase_password == "":
                frase_password = input('Por favor, introduzca su frase de contraseña: ')
                if frase_password != "":
                    a = (hashlib.sha256(frase_password.encode()).digest()).hex()
                    print ("[+] Número secreto de A (hexadecimal), 'a':", a)
                    print ("*** A envía a B el resultado de g^a mod p")
                    print ("*** B introduce una frase de contraseña de la que se calcula el hash SHA-256 para obtener su número secreto 'b'")
                    frase_password = ""
                    while frase_password == "":
                        frase_password = input('Por favor, introduzca su frase de contraseña: ')
                        if frase_password != "":
                            b = (hashlib.sha256(frase_password.encode()).digest()).hex()
                            print ("[+] Número secreto de B (hexadecimal), 'b':", b)
                            print ("*** B envía a A el resultado de g^b mod p")
                            print ("*** A calcula la clave de sesión que va a compartir con B, k = (g^b mod p)^a mod p")
                            ka = exp_modular_rapida(exp_modular_rapida(g, int(b,16), p), int(a,16), p)
                            print ("[+] Clave de sesión compartida ('k') calculada por A:", ka)
                            print ("*** B calcula la clave de sesión que va a compartir con A, k = (g^a mod p)^b mod p")
                            kb = exp_modular_rapida(exp_modular_rapida(g, int(a,16), p), int(b,16), p)
                            print ("[+] Clave de sesión compartida ('k') calculada por B:", kb)
                            if ka == kb:
                               print ("[+] Las claves de sesión calculadas por A y B de forma independiente son iguales. INTERCAMBIO DE CLAVE CORRECTO.")
                            else:
                               print ("[+] Las claves de sesión calculadas por A y B de forma independiente son diferentes. INTERCAMBIO DE CLAVE INCORRECTO.")
                        else:
                            print ("*** ERROR: Por favor, introduzca su frase de contraseña.")
                else:
                    print ("*** ERROR: Por favor, introduzca su frase de contraseña.")
        elif opcion == "2":
            print ("*** FIN ******************************************")
            salir = True
        else:
            print ("*** ERROR: Opción no válida.")

if __name__ == '__main__':
    main()

Lo ejecuto:

Quizás también te interese: