Criptografía de clave asimétrica

En esta lección veremos la criptografía de clave asimétrica, que constituye la base de muchas interacciones de red seguras en la actualidad.

Al finalizar la lección habremos cubierto:

Qué es la criptografía de clave asimétrica
Usos de la criptografía de clave asimétrica, incluyendo el intercambio de claves y las firmas digitales
Seguridad de la criptografía de clave asimétrica en general
Más detalles sobre los algoritmos RSA, DSA y de curvas elípticas, y su seguridad
Algunos ejemplos de código Python que muestran cómo funcionan los algoritmos en la práctica
Amenazas a estos algoritmos provenientes tanto de computadoras clásicas como cuánticas

Introducción a la criptografía de clave asimétrica

Como aprendimos en la lección anterior, la criptografía de clave simétrica es muy rápida y eficiente para proteger información, pero tiene algunas limitaciones:

A medida que aumenta el número de partes que desean intercambiar información de forma segura, la cantidad de claves necesarias crece de manera combinatoria. No ofrece ningún mecanismo para distribuir esas claves de forma segura entre emisores y receptores.
No contempla la no-repudiación. Cualquier parte puede descifrar o cifrar mensajes sin que haya forma de garantizar que un mensaje fue recibido ni de dónde proviene.

La solución a ambos problemas la ofrece la criptografía de clave asimétrica (AKC, por sus siglas en inglés), también conocida como criptografía de clave pública (PKC), que por ello constituye un pilar fundamental de la seguridad digital moderna.

La criptografía de clave asimétrica (AKC) implica el uso de un par de claves: una pública y una privada. Las claves pública y privada están vinculadas criptográficamente y generalmente se generan al mismo tiempo como un par de claves mediante un algoritmo matemático especializado. La clave pública, como su nombre indica, está destinada a distribuirse libremente, mientras que la clave privada la mantiene en secreto la parte que generó el par. La seguridad de las comunicaciones que emplean pares de claves asimétricas está garantizada siempre que la clave privada permanezca confidencial.

Figura 1. Cifrado de clave asimétrica

Figura 1. Cifrado de clave asimétrica

La AKC ofrece varias funciones útiles, como:

Cifrado y descifrado para garantizar la confidencialidad de las comunicaciones.
Firmas digitales para asegurar la autenticidad, la integridad y la no-repudiación.
Intercambio seguro de claves para facilitar el uso posterior de criptosistemas simétricos.

En las aplicaciones modernas, la AKC se utiliza principalmente para firmas digitales e intercambio seguro de claves. En esta lección presentamos estas dos funciones clave y luego analizamos diversas variantes de protocolos criptográficos para estas funciones.

Intercambio de claves con criptografía de clave asimétrica

Uno de los problemas fundamentales en criptografía es el intercambio de claves de forma segura. Por ejemplo, si dos partes quieren usar cifrado simétrico, ambas necesitan la misma clave para cifrar y descifrar mensajes. ¿Pero cómo intercambian esa clave de forma segura? La criptografía de clave asimétrica aborda esto mediante mecanismos de intercambio de claves interactivos y no interactivos.

Intercambio de claves interactivo

Un protocolo de intercambio de claves interactivo es un método en el que dos partes colaboran para crear una clave secreta compartida a través de un canal de comunicación inseguro. Esta clave secreta compartida puede usarse después para tareas de cifrado y descifrado simétrico.

El más conocido de estos protocolos es el algoritmo Diffie-Hellman (DH), diseñado específicamente para facilitar el intercambio de claves. En este protocolo, cada parte genera un par de claves (pública y privada) y difunde su clave pública. Luego, cada parte usa su propia clave privada y la clave pública de la otra parte para generar una clave secreta compartida. DH emplea los principios de la aritmética modular para asegurar que ambas partes obtengan el mismo secreto compartido, aunque cada parte solo tenga acceso a la clave pública de la otra.

Los criptosistemas modernos basados en criptografía de curva elíptica (ECC) amplían este concepto con el intercambio de claves Diffie-Hellman de curva elíptica (ECDH). ECDH funciona de manera similar a DH pero aprovecha las propiedades de las curvas elípticas, lo que resulta en un sistema más seguro y eficiente.

Figura 2. Protocolo de intercambio de claves

Figura 2. Protocolo de intercambio de claves

Intercambio de claves no interactivo

A diferencia de los protocolos de intercambio de claves como DH y ECDH, que son interactivos y requieren comunicación de ida y vuelta para acordar la clave simétrica, la AKC también ofrece formas no interactivas de establecer una clave secreta compartida. En estos esquemas, una parte genera un par de claves (pública y privada) y comparte la clave pública con la otra parte. Esta segunda parte genera entonces una clave simétrica aleatoria, la cifra con la clave pública recibida y se la envía a la primera parte. La primera parte usa su clave privada para descifrar el mensaje recibido y así obtiene la clave simétrica compartida. Este esquema es no interactivo en el sentido de que la clave simétrica la determina una parte y simplemente se comunica de forma segura a la otra en forma cifrada.

Una consideración importante en el intercambio de claves no interactivo tiene que ver con la diferencia en bits entre la clave simétrica que las partes desean intercambiar y los tamaños de mensaje recomendados en AKC. Típicamente, las claves simétricas modernas tienen entre 128 y 256 bits de longitud, mientras que los criptosistemas de clave asimétrica como RSA trabajan con tamaños de mensaje de alrededor de 1024 a 4096 bits. Por lo tanto, al usar AKC para transmitir una clave simétrica, por seguridad esta debe codificarse en un mensaje más largo de 1024 a 4096 bits. Esto puede lograrse mediante dos enfoques:

Intercambio de claves basado en relleno: En este enfoque, primero se genera la clave simétrica más corta (128-256 bits) y luego se usa un esquema de relleno reversible acordado, como OAEP, para insertarla en un mensaje más largo (1024-4096 bits). Este mensaje más largo se cifra con AKC y se difunde como texto cifrado. El destinatario primero descifra el texto cifrado y luego elimina el relleno para extraer la clave simétrica más corta.
Mecanismos de encapsulación de claves (KEM): Con el intercambio de claves basado en KEM, primero se genera un mensaje de texto plano largo y aleatorio (1024-4096 bits), del cual se puede extraer una clave simétrica más corta (128-256 bits) mediante una función de derivación de claves (KDF) acordada. El texto plano más largo se cifra con AKC y se difunde al destinatario como texto cifrado. El destinatario decodifica el texto cifrado usando su clave privada y luego utiliza la KDF para extraer la clave simétrica más corta (128-256 bits). Criptosistemas populares como RSA, con su capacidad para cifrar datos directamente, pueden usarse para implementar KEMs.

Figura 3. Mecanismo de encapsulación de claves

Figura 3. Mecanismo de encapsulación de claves

Firmas digitales con criptografía de clave asimétrica

Las firmas digitales son otra poderosa aplicación de la criptografía de clave asimétrica. Proporcionan autenticación, integridad y no-repudiación, posibles gracias al hecho de que en AKC cada entidad posee claves privadas únicas. La idea básica que subyace a los protocolos de firma es que los emisores de mensajes seguros firmarán digitalmente los mensajes con su clave privada única. El receptor verificará entonces la firma digital usando la clave pública del emisor. En AKC, las firmas digitales pueden implementarse usando algoritmos diseñados específicamente para ese propósito o mediante criptosistemas genéricos.

Figura 4. Firmas digitales con criptografía de clave asimétrica

Figura 4. Firmas digitales con criptografía de clave asimétrica

Algoritmos dedicados de firma digital

Actualmente, el estándar estadounidense de procesamiento de información federal (FIPS) para firmas digitales es un esquema dedicado titulado simplemente Algoritmo de firma digital (DSA). De manera algo similar al protocolo Diffie-Hellman, el DSA utiliza las propiedades algebraicas de la exponenciación modular y los inversos multiplicativos para la generación y verificación de firmas.

El algoritmo de firma digital de curva elíptica (ECDSA) es una variante del DSA basada en ECC que ofrece la misma funcionalidad pero con claves significativamente más cortas. Esto resulta en una mayor eficiencia, lo que lo convierte en una opción popular para sistemas con restricciones de recursos.

Tanto DSA como ECDSA se ilustrarán con más detalle más adelante.

Esquemas de firma digital con criptosistemas genéricos

Además de los algoritmos dedicados, las firmas digitales también pueden generarse usando criptosistemas asimétricos genéricos, como RSA.

RSA, que se analizará en detalle en una sección posterior, también explota los inversos multiplicativos modulares y la exponenciación modular como operaciones fundamentales, pero las combina en una secuencia diferente a la de DSA. En RSA, el firmante normalmente crea un hash del mensaje y luego cifra ese hash con su clave privada, creando así la firma digital. Cualquier parte puede verificar esta firma descifrándola con la clave pública del firmante y comparándola con el mensaje hasheado.

Aplicaciones de la criptografía de clave asimétrica

La criptografía de clave asimétrica es ubicua en las aplicaciones de tecnología digital modernas. Las funcionalidades básicas de la AKC descritas anteriormente son los bloques de construcción de muchos protocolos de aplicación de alto nivel, entre ellos:

Comunicación por internet: La comunicación segura por internet, como HTTPS, depende en gran medida de la criptografía de clave asimétrica. La seguridad de la capa de transporte (TLS) y su predecesora, la capa de sockets seguros (SSL), utilizan criptografía de clave asimétrica durante el proceso de negociación inicial para establecer una clave simétrica, que luego se usa durante el resto de la sesión de comunicación.
Autenticación: La criptografía de clave asimétrica se usa para crear firmas digitales, lo que permite a una entidad autenticar un documento o mensaje digital como proveniente de un emisor específico. Esto se utiliza en muchos escenarios, desde la verificación de actualizaciones de software hasta contratos digitales con validez legal.
Cifrado de correo electrónico: Los protocolos de cifrado de correo electrónico como PGP (Pretty Good Privacy) y su alternativa de código abierto GPG (GNU Privacy Guard) utilizan criptografía de clave asimétrica para garantizar que solo el destinatario previsto pueda leer el contenido del correo.
Shell seguro (SSH): SSH es un protocolo para el inicio de sesión remoto seguro y otros servicios de red seguros sobre una red insegura. Utiliza criptografía de clave asimétrica para autenticar el servidor ante el cliente y, opcionalmente, el cliente ante el servidor.
VPN (red privada virtual): El cifrado de clave asimétrica se usa para establecer conexiones seguras en las VPN, garantizando una comunicación segura a través de redes públicas.
Blockchain y criptomonedas: Las tecnologías blockchain, incluyendo Bitcoin y Ethereum, usan criptografía de clave asimétrica. Por ejemplo, la propiedad de Bitcoin se establece mediante firmas digitales que emplean criptografía de clave asimétrica.
Autoridades de certificación: La criptografía de clave asimétrica es utilizada por las autoridades de certificación (CA) para emitir y firmar certificados digitales, que se usan en comunicaciones TLS, firma de código, cifrado de correo electrónico y más. Un certificado digital vincula una clave pública a una entidad específica (por ejemplo, una persona o un servidor).

Figura 5. Emisión y firma de certificados digitales mediante criptografía de clave asimétrica

Figura 5. Emisión y firma de certificados digitales mediante criptografía de clave asimétrica

Seguridad de la criptografía de clave asimétrica

Varios conceptos criptográficos se combinan para hacer posible la criptografía de clave asimétrica segura, entre ellos:

Secreto de la clave privada: El requisito de seguridad más básico de la AKC es que la clave privada permanezca secreta. Sin embargo, dado que la clave privada debe estar matemáticamente vinculada a la clave pública, el secreto de la clave privada también requiere que sea computacionalmente inviable derivar la clave privada a partir del conocimiento de la clave pública. Los esquemas de generación de claves en AKC se apoyan en problemas matemáticos computacionalmente difíciles para satisfacer este requisito.

Funcionalidad de trampilla: En AKC, las operaciones de cifrado y descifrado involucran claves complementarias diferentes de un mismo par de claves. El texto cifrado generado mediante el cifrado con una de las claves (por ejemplo, la clave pública) debe ser incomprensible para terceros, aunque fácilmente descifrable por el titular de la clave complementaria (en este caso, la clave privada). En otras palabras, el cifrado debe parecerse a una función unidireccional con trampilla de manera que terceros no puedan invertir la operación y recuperar el texto plano, pero la clave privada proporcione una trampilla secreta que permita invertirla fácilmente. Los algoritmos AKC populares utilizan la exponenciación modular para crear este comportamiento de función unidireccional con trampilla.

Aleatoriedad: El proceso de generación de claves también debe explotar la aleatoriedad para garantizar que las claves sean impredecibles, ya que cualquier patrón o predictibilidad en la generación de claves podría ser explotado por un atacante. La aleatoriedad también se usa para el relleno durante el cifrado, con el fin de generar textos cifrados semánticamente seguros, y dentro de los esquemas de firma digital para producir firmas únicas incluso cuando el mismo mensaje se firma múltiples veces. Por esta razón, el uso de generadores de números aleatorios robustos es una parte importante de la AKC.

Tamaño de clave grande: Al igual que en el caso de la criptografía de clave simétrica (SKC), los tamaños de clave grandes aseguran protección contra ataques de fuerza bruta. Sin embargo, dado que los tamaños de clave grandes también aumentan el costo computacional del proceso de cifrado y descifrado, una solución óptima debe equilibrar las consideraciones de seguridad y eficiencia. La siguiente tabla muestra los tamaños de clave típicos para varios protocolos y aplicaciones de criptografía de clave asimétrica:

Protocolo	Tamaños de clave típicos (en bits)	Aplicación
RSA	1024 (obsoleto), 2048, 3072, 4096	Cifrado, firmas digitales
DSA	1024 (obsoleto), 2048, 3072	Firmas digitales
DH	2048, 3072, 4096	Intercambio de claves
ECDH	224, 256, 384, 521	Intercambio de claves
ECDSA	224, 256, 384, 521	Firmas digitales

Infraestructura de clave pública: En AKC, las claves privadas deben mantenerse en secreto por sus propietarios mientras que las claves públicas se comparten. Es necesario contar con un mecanismo seguro para gestionar y distribuir estas claves públicas entre usuarios. La infraestructura de clave pública (PKI) ofrece una forma de hacerlo mediante certificados digitales. Un certificado digital proporciona prueba de identidad del propietario de la clave pública y es emitido por una autoridad de confianza como una autoridad de certificación (que forma parte de una PKI). Por ello, la PKI desempeña un papel integral en la seguridad de las aplicaciones modernas que utilizan AKC, al habilitar la gestión de claves a gran escala (mediante la creación, gestión, distribución y revocación de certificados digitales).

Riesgos de seguridad para la criptografía de clave asimétrica

Como se indica en la tabla anterior, los algoritmos de clave asimétrica modernos como RSA suelen emplear tamaños de clave mucho más grandes que las contrapartes de clave simétrica de uso común, como AES-128. Incluso los protocolos basados en ECC (ECDH y ECDSA), que tienen claves más pequeñas, emplean un mínimo de al menos 224 bits para las claves. Esto implica a su vez que un ataque de fuerza bruta que involucre una búsqueda exhaustiva del espacio de claves privadas para identificar la clave correcta es computacionalmente inmanejable en el futuro previsible. Esto sigue siendo cierto incluso si se desplegaran computadoras cuánticas para esta tarea. Por ello, los ataques contra la AKC suelen centrarse en explotar otras debilidades potenciales de criptosistemas específicos. Algunos modos de ataque bien documentados apuntan a:

Debilidad algorítmica mediante el uso de medios matemáticos y computacionales sofisticados para socavar los supuestos de dificultad que fundamentan los algoritmos de clave asimétrica. Por ejemplo, la seguridad de RSA está basada en la dificultad de factorizar grandes números primos, y avances computacionales recientes han permitido factorizar con éxito claves RSA de 829 bits. Por ello, RSA de 1024 bits está actualmente obsoleto. Como se analizará más adelante, el principal riesgo que representan las computadoras cuánticas para la AKC también cae en esta categoría.
Aleatoriedad imperfecta, que puede generar debilidades en el proceso de generación de claves. Por ejemplo, si el generador de números aleatorios usado para crear las claves es defectuoso y genera claves que no son verdaderamente aleatorias, un atacante podría ser capaz de predecir las claves.
Fallos de implementación, como errores en la implementación de algoritmos criptográficos que revelan inadvertidamente información sobre las claves. Por ejemplo, un relleno incorrecto puede revelar detalles sobre las claves.
Canales laterales que se refieren a fugas de información del sistema físico que realiza la criptografía. Estas fugas pueden presentarse como información de temporización, consumo de energía o incluso sonido, los cuales pueden ser explotados en un llamado ataque de canal lateral. Por ejemplo, analizar cuánto tiempo tardan en ejecutarse las operaciones criptográficas podría revelar el número de «1» en una clave binaria. Esta fuga aparentemente inocente reduce significativamente el espacio de búsqueda, descubriendo posibles soluciones a problemas que inicialmente parecían insuperables.
Intercambio de claves mediante la interceptación de claves mientras se están intercambiando, como en un ataque de intermediario (MITM). El protocolo DH es susceptible a ataques MITM si no se incorporan pasos de autenticación adicionales.
Almacenamiento de claves apuntando a robar claves de almacenamientos con seguridad deficiente. Esto incluye ataques físicos como la manipulación o el robo de dispositivos de almacenamiento.

Asegurar los criptosistemas de clave asimétrica contra la variedad de ataques posibles es, por tanto, una tarea significativa que involucra consideraciones matemáticas, de hardware, de software, logísticas y legales.

RSA

El algoritmo RSA (Rivest-Shamir-Adleman) es uno de los primeros criptosistemas de clave pública y se utiliza ampliamente para la transmisión segura de datos. Es un criptosistema versátil en el sentido de que proporciona las operaciones necesarias para habilitar el cifrado, el descifrado, las firmas digitales y el intercambio de claves dentro de un marco común.

En esta sección ilustraremos la criptografía de clave asimétrica (AKC) usando RSA a través de ejemplos sencillos.

Usaremos el escenario estándar de dos partes, Alice y Bob, que desean comunicarse de forma segura usando AKC.

El algoritmo RSA

El algoritmo RSA básico involucra cuatro operaciones: generación de claves, distribución de claves, cifrado y descifrado:

Generación de claves:

Las claves pública y privada se generan basándose en principios matemáticos sobre números primos, donde calcularlos es fácil, pero el proceso inverso es difícil.

Nos referiremos a ellas como:
- Clave pública: $(e, n)$
- Clave privada: $(d, n)$
Observa que $n$ es común tanto a la clave pública como a la clave privada, y se conoce como el módulo. Lo necesitaremos más adelante.

Detalle matemático

Elige dos números primos distintos, $p$ $p$ y $q$ $q$ .
- Elegidos al azar (por seguridad).
- Deben ser de magnitud similar, pero diferir en longitud por unos pocos dígitos, para dificultar la factorización.
- Los números primos pueden elegirse eficientemente usando una prueba de primalidad.
Calcula $n = p*q$ $n = p * q$ .
- $n$ es el módulo tanto para la clave pública como para la privada.
Calcula el totiente $φ$ $(n) = (p-1)*(q-1)$ $(n) = (p - 1) * (q - 1)$ .
- El totiente debe mantenerse en secreto y típicamente se descarta tras la generación de claves.
Elige un entero $e$ $e$ tal que $1 < e <$ $1 < e <$ $φ$ $(n)$ $(n)$ y $gcd$ $(e,$ $(e,$ $φ$ $(n)) = 1$ $(n)) = 1$ .
- Es decir, $e$ y $φ$ $(n)$ deben ser coprimos.
- Este número $e$ forma el exponente de la clave pública y normalmente se elige como un número pequeño por eficiencia computacional.
- El número primo $65537 = 2^{16} + 1$ se usa con frecuencia.
- Calcula $d$ $d$ para satisfacer la relación de congruencia $d*e ≡ 1 ($ $d * e \equiv 1 ($ $mod$ $φ$ $(n))$ $(n))$ .
  - Es decir, $d$ es el inverso multiplicativo de $e$ módulo $φ$ $(n)$ .
  - Esto se calcula de forma más eficiente usando el algoritmo euclidiano extendido.
  - Este número $d$ es el exponente de la clave privada.
La clave pública consiste en $(e, n)$ , y la clave privada es $(d, n)$ .

Distribución de claves:
- La clave pública $(e, n)$ se hace pública para quienes deseen enviar un mensaje.
- La clave privada $(d, n)$ se mantiene en secreto.
Cifrado:
- Alice desea enviar un mensaje $M$ a Bob. En este caso, un simple entero.
- Alice usa la clave pública de Bob $(e, n)$ para cifrar el mensaje y obtener el texto cifrado $C$ .
Detalle matemático
- $M$ es un entero $0 ≤ M < n$ .
- $C ≡ M^e (mod n)$ , donde $C$ es el texto cifrado.
Descifrado:
- Bob recibe el texto cifrado $C$ .
- Bob usa su clave privada $(d, n)$ para descifrar el mensaje y recuperar el mensaje original $M$ .
Detalle matemático
- $M ≡ C^d (mod n)$ .

Este es el esquema básico de RSA. En la práctica, se aplican al texto plano $M$ esquemas de relleno más sofisticados antes del cifrado para garantizar que textos planos iguales produzcan textos cifrados distintos. Esto previene una variedad de posibles ataques contra implementaciones ingenuas de RSA y habilita la seguridad semántica.

Ilustración de RSA en Python

En los siguientes bloques de código, ilustramos un ejemplo sencillo del algoritmo RSA usando enteros pequeños y, a continuación, demostramos aplicaciones prácticas de distribución de claves y firmas digitales usando bibliotecas de Python que implementan RSA.

nota

Nota: En esta sección mostraremos los cálculos matemáticos en detalle como parte del código Python.

Generación de claves RSA

Repasemos paso a paso una instancia sencilla del algoritmo RSA con números primos pequeños.

Necesitaremos poder calcular el máximo común divisor de dos enteros, ya que será necesario para comprobar si dos enteros son coprimos.

Explicaremos una forma sencilla de calcularlo, aunque para enteros más grandes es mucho más eficiente usar la función math.gcd de Python.

# Added by doQumentation — required packages for this notebook
!pip install -q cryptography

import math

# Example function to compute the gcd (greatest common divisor)
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

# let's calculate some examples using algorithm
n1 = gcd(50, 10)
n2 = gcd(99, 33)
n3 = gcd(59, 9)

# do the same with the python library call

m1 = math.gcd(50, 10)
m2 = math.gcd(99, 33)
m3 = math.gcd(59, 9)

# Confirm they are the same
assert n1 == m1
assert n2 == m2
assert n3 == m3

# They are - print out the values for explanation
print("gcd(50,10) =", m1)
print("gcd(99,33) =", m2)
print("gcd(59,9) =", m3)

La primera fase del flujo de trabajo de RSA es la generación de claves. Esta comienza eligiendo dos números primos, que deben mantenerse en secreto por la entidad que genera las claves.

# Choosing two prime numbers and keep them secret
p = 13
q = 19
print("The secret prime numbers p and q are:", p, q)

A continuación, se calcula el módulo $n$ , que es simplemente el producto de los dos primos elegidos. Este módulo se publicará como parte de la clave pública.

# Calculate n which is the modulus for both the public and private keys
n = p * q
print("modulus n (p*q)=", n)

A continuación se calcula la función totiente de Euler $\varphi(n)$ , ya que se necesita para la operación de inverso multiplicativo modular utilizada para determinar las claves en RSA. $phi$ también se mantiene en secreto y normalmente se descarta tras la generación de claves.

# Compute Euler's totient function, φ(n) and keep it secret
phi = (p - 1) * (q - 1)
print("The secret Euler's function (totient) [phi(n)]:", phi)

Ahora estamos listos para calcular las claves pública y privada. En RSA, cada una de ellas se especifica mediante una tupla de dos enteros. El primer elemento de cada tupla es un entero distinto, y el segundo es el módulo $n$ que es común a ambas claves.

El primer elemento de la clave pública puede ser cualquier entero mayor que 1 que sea coprimo con $phi$ . Dos enteros son coprimos si su máximo común divisor es 1. Por lo tanto, usamos la función math.gcd para encontrar un entero $e$ coprimo con $phi$ .

# Choose an integer e such that e and φ(n) are coprime
e = 2
while e < phi:
    if math.gcd(e, phi) == 1:
        break
    else:
        e += 1
print("Public Key (e):", e)

La clave privada requiere un entero $d$ , que es el inverso multiplicativo de $e$ módulo $phi$ ; es decir, satisface la relación de congruencia $d*e\equiv 1 \pmod{\varphi(n)}$ . Para esta ilustración sencilla con enteros pequeños, podemos simplemente recorrer los enteros positivos para localizar un $d$ adecuado. En escenarios reales, se usa el computacionalmente eficiente algoritmo euclidiano extendido para este propósito.

# Compute a value for d such that (d * e) % φ(n) = 1
d = 1
while True:
    if (d * e) % phi == 1:
        break
    else:
        d += 1
print("Private Key (d):", d)

Ahora formamos las tuplas $(e, n), (d, n)$ , que constituyen las claves pública y privada respectivamente. La clave pública se publica, mientras que la clave privada se mantiene en secreto.

# Public and Private Key pair
public = (e, n)
private = (d, n)

print(f"The Public key is {public} and Private Key is {private}")

El cifrado y el descifrado en RSA usan la operación de exponenciación modular. Además, las claves pública y privada son complementarias, en el sentido de que cualquiera de ellas puede usarse para cifrar un mensaje que la otra puede descifrar.

Aquí ilustramos el caso en que la clave pública $(e,n)$ se usa para cifrar y la clave privada $(d, n)$ se usa para descifrar, definiendo una función de Python para cada operación.

Luego ciframos y desciframos un mensaje entero $msg$ .

# Encryption function
def encrypt(plain_text):
    return (plain_text**e) % n

# Decryption function
def decrypt(cipher_text):
    return (cipher_text**d) % n

# Simple message to encode
msg = 9

# encrypt then decrypt
enc_msg = encrypt(msg)
dec_msg = decrypt(enc_msg)

print("Original Message:", msg)
print("Encrypted Message:", enc_msg)
print("Decrypted Message:", dec_msg)

Si bien los enteros pequeños usados anteriormente son útiles para esbozar fácilmente las ideas centrales del algoritmo RSA, en aplicaciones reales RSA requiere el uso de enteros muy grandes. Por ejemplo, RSA de 2048 bits implica el uso de un módulo $n$ de 2048 bits de longitud, cuyos equivalentes en enteros decimales rondan los 10 $^{616}$ . Estos números enormes son necesarios para la seguridad práctica de RSA.

Intercambio de clave simétrica con RSA

Como se menciónó anteriormente, la AKC permite a dos partes que deseen comunicarse establecer de forma segura un secreto compartido, que puede usarse, por ejemplo, como clave secreta para el cifrado simétrico posterior de texto plano en volumen.

Consideremos el siguiente escenario. Alice y Bob quieren usar la SKC para cifrar y descifrar mensajes. Sin embargo, antes de que este proceso pueda iniciarse, necesitan acordar una clave secreta común. Una opción es que una de las partes —digamos, Alice— genere una clave secreta y luego la transmita de forma segura a Bob. Para lograr esta transferencia segura, Alice decide usar RSA como mecanismo de encapsulación de claves (KEM, por sus siglas en inglés).

Esto implica los siguientes pasos:

Primero, Alice genera una clave simétrica aleatoria que tiene intención de compartir con Bob.
Luego, Bob genera un par de claves asimétricas y hace pública su clave pública en un canal adecuado.
A continuación, Alice usa la clave pública de Bob para cifrar la clave simétrica, encapsulándola en un texto cifrado.
Después, Alice transmite el texto cifrado por un canal fiable pero no necesariamente seguro.
Finalmente, Bob recibe el texto cifrado y lo descifra usando su clave privada. Ahora tiene acceso a la clave simétrica generada por Alice.

Figura 1. Intercambio de clave simétrica con RSA

Figura 1. Intercambio de clave simétrica con RSA

Ejemplo de intercambio de claves basado en relleno en Python

A continuación se ilustra un flujo de trabajo práctico que utiliza RSA para el intercambio de claves no interactivo basado en relleno, usando la biblioteca cryptography de Python.

Importa los módulos necesarios de la biblioteca cryptography de Python. Si es necesario, esta biblioteca puede instalarse con el comando pip install cryptography.

Alice genera entonces una clave secreta aleatoria que tiene intención de transmitir a Bob.

# pip install cryptography
from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.fernet import Fernet
from cryptography.hazmat.primitives import hashes

symmetric_key = Fernet.generate_key()
print(f"\nSymmetric key generated by Alice: {symmetric_key}")

Usando el módulo rsa de la biblioteca cryptography, Bob genera un par de claves y luego difunde su clave pública. Cualquiera puede interceptar la clave pública y leer los números públicos $(e,n)$ que forman la clave.

# Bob generates a 2048-bit RSA key pair
bob_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
bob_public_key = bob_private_key.public_key()
print(f"Public key broadcast by Bob: {bob_public_key}")
print(f"\nPublic numbers in Bobs' public key: {bob_public_key.public_numbers()}")

En este punto, asumimos que Alice ha recibido la clave pública difundida por Bob. La symmetric_key de Alice puede ahora cifrarse usando la clave pública de Bob para producir el texto cifrado. En un escenario realista, Alice también usará métodos de relleno adicionales como OAEP para garantizar la seguridad semántica en sus comunicaciones con Bob.

# Encryption
ciphertext = bob_public_key.encrypt(
    symmetric_key,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Ciphertext:", ciphertext)

Alice transmite entonces el texto cifrado por un canal abierto, confiada en que solo Bob, con la clave privada correspondiente, podrá descifrarlo. Asumimos que Bob ha recibido el texto cifrado y ahora puede descifrarlo usando su clave privada confidencial.

# Bob decrypts ciphertext to access the symmetric key
decrypted_symmetric_key = bob_private_key.decrypt(
    ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Decrypted key:", decrypted_symmetric_key)
assert decrypted_symmetric_key == symmetric_key

En este punto, tanto Alice como Bob tienen acceso a la clave simétrica secreta, que pueden usar para aplicaciones de SKC.

Simulación de un mecanismo de encapsulación de claves con RSA en Python

En el siguiente flujo de trabajo, ilustramos el uso de RSA para simular un mecanismo de encapsulación de claves (KEM) mediante el cual un mensaje secreto aleatorio suficientemente largo se intercambia de forma segura y se convierte posteriormente en un secreto compartido de la longitud adecuada usando una KDF.

De nuevo, Alice y Bob quieren establecer un secreto compartido de forma no interactiva, y Alice es la parte que decide qué secreto usar.

Comenzamos importando algunas bibliotecas de Python necesarias.

Bob genera entonces su par de claves RSA y difunde su clave pública.

from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from cryptography.hazmat.primitives import hashes
from os import urandom

# Bob's RSA key pair
private_key_Bob = rsa.generate_private_key(public_exponent=65537, key_size=2048)
public_key_Bob = private_key_Bob.public_key()

print("Bob's private and public keys created")

Alice genera primero un secreto aleatorio largo del que se derivará finalmente el secreto compartido. En un KEM puro, el secreto largo sería un elemento aleatorio de la estructura algebraica subyacente al criptosistema. En el caso de RSA de 2048 bits, sería un entero aleatorio módulo el módulo RSA de 2048 bits. Dado que un KEM puro no requiere relleno adicional, pero en este ejemplo solo estamos simulando un KEM usando RSA y la biblioteca cryptography requiere el uso de relleno al cifrar con RSA, usaremos un secreto largo algo más corto, aunque significativamente más largo que una clave AES estándar de 256 bits.

Alice_long_secret = urandom(160)  # A 160 byte or 1280 bit random message
print("Alice's secret created")

A continuación, Alice cifra el secreto largo usando la clave pública de Bob y el secreto cifrado se comunica a Bob.

Alice_encrypted_secret = public_key_Bob.encrypt(
    Alice_long_secret,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)
print("Alice's secret encrypted")

Bob descifra el secreto cifrado recibido de Alice usando su clave privada.

Bob_decrypted_secret = private_key_Bob.decrypt(
    Alice_encrypted_secret,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

assert Alice_long_secret == Bob_decrypted_secret, "Secrets do not match!"

# if we get here they match
print("Secrets match")

Finalmente, tanto Alice como Bob aplican por separado una función de derivación de clave (KDF) acordada sobre el secreto largo para derivar la clave simétrica.

Ten en cuenta que el proceso implica un protocolo de hash y el uso de una sal aleatoria, lo que garantiza la unicidad e imprevisibilidad de la clave simétrica compartida en caso de que el secreto largo se reutilice alguna vez (no se recomienda). Sin embargo, la sal en sí no tiene por qué ser secreta y, una vez que se genera aleatoriamente, por ejemplo por Alice en este ejemplo, puede difundirse a Bob junto con el secreto largo cifrado.

Asumiremos, por lo tanto, que tanto Alice como Bob tienen acceso a la misma sal aleatoria.

def key_derivation_function(secret, salt):
    hkdf = HKDF(
        algorithm=hashes.SHA256(),
        length=32,  # Desired key length
        salt=salt,
        info=None,
        backend=None,
    )
    return hkdf.derive(secret)

common_salt = urandom(16)  # Random salt accessible to both Alice and Bob

symmetric_key_Alice = key_derivation_function(Alice_long_secret, common_salt)
symmetric_key_Bob = key_derivation_function(Bob_decrypted_secret, common_salt)

assert symmetric_key_Alice == symmetric_key_Bob, "Derived keys do not match!"
print(
    f"A symmetric key of length {len(symmetric_key_Alice)*8} bits was successfully derived by both Alice and Bob!"
)

Firmas digitales con RSA

Ahora ampliaremos el escenario de comunicación confidencial entre Alice y Bob para incluir también validación con la ayuda de una firma digital.

Como antes, Alice enviará confidencialmente a Bob un mensaje que encapsula una clave simétrica, pero también firmará digitalmente el mensaje para que Bob, al recibirlo, pueda verificar que fue Alice quien lo originó y que el contenido del mensaje no fue manipulado durante la transmisión.

En términos más generales, es deseable permitir la validación sin comprometer la confidencialidad, de modo que cualquier parte interesada pueda verificar la integridad, la autenticidad y establecer el no repudio respecto a una comunicación dada, incluso si esa parte no tiene acceso al texto plano real.

Consideraremos este contexto general, que implica los siguientes pasos:

Primero, tanto Bob como Alice hacen públicas sus claves públicas a través de un canal abierto.
Luego, Alice cifra el texto plano usando la clave pública de Bob, creando un texto cifrado.
A continuación, Alice crea un hash del texto cifrado con una función hash y además cifra el hash resultante usando su clave privada. Este hash cifrado es la firma.
Después, Alice transmite tanto el texto cifrado como la firma por un canal abierto.
Luego, Bob usa la clave pública de Alice para descifrar la firma, revelando el hash del texto cifrado.
A continuación, como Bob también tiene acceso al propio texto cifrado, usa la misma función hash que Alice para recrear una segunda instancia del hash del texto cifrado. Si esta coincide con la obtenida al descifrar la firma de Alice, entonces el mensaje queda validado, aunque el texto cifrado en sí aún no haya sido descifrado.
Finalmente, Bob, habiendo validado el mensaje, descifra el texto cifrado usando su propia clave privada.

Figura 2. Firmas digitales con RSA

Figura 2. Firmas digitales con RSA

Este flujo de trabajo para una firma digital se ilustra a continuación.

De nuevo importamos algunos módulos útiles de la biblioteca cryptography. Como antes, Alice tiene intención de enviar de forma segura una clave simétrica a Bob, pero también desea firmarla digitalmente. En este caso, necesitamos claves públicas tanto para Alice como para Bob. Por lo tanto, el primer paso es que tanto Alice como Bob creen su propio par de claves usando RSA y difundan su propia clave pública al mundo.

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import padding, rsa
from cryptography.hazmat.primitives.asymmetric.utils import Prehashed

# Generate keys for Bob
bob_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
bob_public_key = bob_private_key.public_key()

# Generate keys for Alice
alice_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
alice_public_key = alice_private_key.public_key()

print("Private and Public keys generated for Bob and Alice.")

En el siguiente paso, como antes, Alice usa la clave pública de Bob para cifrar la clave simétrica y prepara el texto cifrado.

# Alice encrypts the message using Bob's public key
ciphertext = bob_public_key.encrypt(
    symmetric_key,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("ciphertext of symmetric key: ", ciphertext)

En esta etapa, en lugar de simplemente difundir el texto cifrado, Alice tiene intención de adjuntarle una firma digital para poder demostrar a Bob que ella fue la remitente del mensaje. Esto se hace en dos pasos:

Crear un hash del texto cifrado usando un algoritmo de hash.
Cifrar el hash usando la clave privada de Alice, lo que equivale a una firma.

# Alice signs the ciphertext using her private key
digest = hashes.Hash(hashes.SHA256())
digest.update(ciphertext)
hash_to_sign = digest.finalize()

signature = alice_private_key.sign(
    hash_to_sign,
    padding.PSS(mgf=padding.MGF1(hashes.SHA256()), salt_length=padding.PSS.MAX_LENGTH),
    Prehashed(hashes.SHA256()),
)

print("signature: ", signature)

Alice transmite entonces el texto cifrado y la firma por una red para que Bob pueda interceptar ambos.

# Bob receives the ciphertext and signature
received_ciphertext = ciphertext
received_signature = signature

# Send signature and ciphertext here
print("Sending ciphertext and signature.....")

Del lado de Bob, la primera tarea es verificar la integridad y la autenticidad del texto cifrado. Para ello, Bob crea un hash del texto cifrado recibido usando el mismo algoritmo de hash que usó Alice.

# Bob creates a hash of the ciphertext using the same algorithm used by Alice
digest = hashes.Hash(hashes.SHA256())
digest.update(received_ciphertext)
hash_to_verify = digest.finalize()

print("hash to verify: ", hash_to_verify)

Luego, Bob descifra la firma recibida usando la clave pública de Alice. Como Alice usó su clave privada para crear la firma, Bob puede descifrarla usando la clave pública de Alice. La firma descifrada no es más que un hash del texto cifrado creado por Alice. Si el hash creado por Bob coincide con la firma descifrada, Bob ha verificado que el texto cifrado que recibió no fue manipulado y que fue Alice quien firmó el texto cifrado.

En el código Python a continuación, estas operaciones se combinan en una función utilitaria llamada verify, proporcionada por un objeto asociado a la clave pública de Alice.

from cryptography.exceptions import InvalidSignature

def is_signature_valid(public_key, signature, data_hash):
    try:
        public_key.verify(
            signature,
            data_hash,
            padding.PSS(
                mgf=padding.MGF1(hashes.SHA256()), salt_length=padding.PSS.MAX_LENGTH
            ),
            Prehashed(hashes.SHA256()),
        )
        return True
    except InvalidSignature:
        return False

if is_signature_valid(alice_public_key, received_signature, hash_to_verify):
    print("The signature is valid.")
else:
    print("The signature is not valid.")

Habiendo verificado la integridad y la autenticidad del texto cifrado recibido, Bob puede entonces descifrarlo usando su clave privada, ya que Alice creó el texto cifrado usando la clave pública de Bob.

# Bob decrypts the message using his private key
decrypted_message = bob_private_key.decrypt(
    received_ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Decrypted message:", decrypted_message.decode())

En el escenario de firma digital anterior, cualquier parte —no solo Bob— puede verificar que Alice es la remitente del texto cifrado, porque todos pueden acceder a la clave pública de Alice, al texto cifrado y a la firma digital. Además, tras enviar el texto cifrado y la firma, Alice no puede negar posteriormente haberlo hecho, ya que la firma puede descifrarse hasta obtener un hash significativo usando únicamente su clave pública. Esto establece el no repudio.

Al habilitar la distribución segura de claves y dar soporte al no repudio, la criptografía de clave pública establece una base sólida para la comunicación digital segura.

Rompiendo RSA

La utilidad y seguridad del algoritmo RSA descrito anteriormente se basan en dos supuestos matemáticos:

Encontrar el inverso multiplicativo modular $d$ teniendo acceso únicamente a $(e, n)$ es computacionalmente inviable.
En el contexto de RSA, la operación de exponenciación modular se comporta como una función trampa unidireccional. Cuando se utiliza para cifrar, produce un texto cifrado incomprensible y, sin acceso a la clave privada, invertir la operación para recuperar el texto plano a partir del texto cifrado no es factible. Sin embargo, con acceso a la clave privada, que actúa como trampa, el texto cifrado puede descifrarse fácilmente.

El ataque más destacado contra el algoritmo RSA tiene como objetivo socavar el supuesto 1 recuperando eficientemente el número de clave privada $d$ mediante la factorización del módulo $n$ . Como se ilustrará a continuación, es fácil recuperar $d$ si se tiene acceso a los factores primos $p$ y $q$ de $n$ , o al totiente $φ$ $(n)$ . Recuerda que $p$ , $q$ y $φ$ $(n)$ se mantienen secretos durante la generación de claves y se descartan después. Un tercero que recupere esta información mediante un ordenador clásico o cuántico básicamente descubre la clave privada, rompiendo RSA. Por lo tanto, la factorización de números primos es la primitiva computacional clave necesaria para romper RSA.

Computación clásica y RSA

Se sabe que la factorización de números enteros grandes presenta un escalado superpolinomial o subexponencial en los ordenadores clásicos. El mejor algoritmo clásico conocido para factorizar enteros mayores de $10^{100}$ es el tamiz de cuerpos de números generales (GNFS)

Detalle matemático

$L_n[\frac{1}{3}, (\frac{64}{9})^{(\frac{1}{3})}] = e^{[((\frac{64}{9})^{(\frac{1}{3})} + o(1)) (log(n))^{\frac{1}{3}}(log(log(n))^{\frac{2}{3}})]}$

como función del entero $n$ a factorizar.

Este escalado es superpolinomial en el número de bits necesarios para representar $n$ .

Por lo tanto, la factorización de números primos se considera ineficiente en los ordenadores clásicos.

En la actualidad, los enteros más grandes factorizados en hardware clásico se sitúan en torno a 829 bits o 250 dígitos decimales. Dado el crecimiento exponencial en la potencia de la computación clásica que se ha observado en las últimas décadas, RSA de 1024 bits ya no se considera seguro a corto plazo y está actualmente en desuso. Sin embargo, en el futuro previsible, factorizar enteros de 2048 bits cuya magnitud se sitúa en el rango de $10^{617}$ se considera actualmente inviable en sistemas clásicos, lo que sugiere una viabilidad continuada. Sin embargo, la llegada de los ordenadores cuánticos invalida esta evaluación.

El algoritmo cuántico de Shor y RSA

Probablemente el algoritmo cuántico más conocido hoy en día es el algoritmo de Shor para encontrar los factores primos de enteros. Cuando Peter Shor lo presentó en 1994, fue reconocido como el primer algoritmo cuántico que ofrecía una aceleración superpolinomial respecto a los algoritmos clásicos en un problema de gran importancia práctica, concretamente la factorización de números primos.

El algoritmo de Shor puede factorizar primos con $O(n^2)$ donde $n$ es el número de bits.

Explicación matemática del algoritmo de Shor

En el contexto de RSA, el algoritmo de Shor funciona explotando la periodicidad de la función exponencial modular $f(x) = a^x (mod~n)$ y proporciona una primitiva cuántica de búsqueda de período que permite la factorización prima eficiente del módulo $n$ .

A continuación se presenta un esquema simplificado y de alto nivel del procedimiento general de Shor para romper RSA:

Dado el módulo $n$ , que se publica como parte de la clave pública, elige un número $a$ coprimo con $n$ , es decir, $gcd(a,n) = 1$ . Dado que sabemos que $n = p*q$ tiene exactamente dos factores primos $(p, q)$ , casi cualquier número menor que $n$ que elijamos al azar probablemente será coprimo con $n$ .
Habiendo elegido $a$ , encuentra el exponente $r$ tal que $a^r \equiv 1 (mod~n)$ . Esto implica $a^r - 1 \equiv 0 (mod~n)$ . La existencia de un exponente $r$ tal que la congruencia anterior se cumple está garantizada por la propiedad de periodicidad de la exponenciación modular.
Si $r$ es par, $a^r - 1 \equiv 0 (mod~n) \implies (a^{r/2} - 1) (a^{r/2} + 1) = \gamma*n$ para algún entero $\gamma$ . El lado izquierdo de esta última igualdad debe contener $p$ y $q$ como dos de sus factores primos, ya que el lado derecho también los contiene. Si $r$ es impar, vuelve al paso 1 y prueba con otra elección de $a$ .
Utiliza el algoritmo de Euclides extendido para encontrar $gcd((a^{r/2} - 1), n)$ o $gcd((a^{r/2} + 1), n)$ . El MCD calculado muy probablemente identificará uno de los factores primos $p$ o $q$ . Divide $n$ entre ese factor primo para recuperar el otro.
Una vez conocidos $p, q$ , utiliza los pasos del algoritmo RSA original para reconstruir el totiente $\phi(n)$ y generar el número de clave privada $d$ como el inverso modular del número de clave pública conocido $e$ .

En agosto de 2023, Oded Regev publicó una mejora del original de Shor mediante un enfoque multidimensional que da como resultado $O(n^{1.5})$ . Continúa habiendo investigación adicional, incluyendo la de Ragavan y Vaikuntanathan en esta área, que podría mejorar el tiempo, el coste o el número de cúbits necesarios. Aunque no podemos decir cuándo ejecutar tales algoritmos contra el cifrado RSA del mundo real se vuelve verdaderamente viable, cada vez está más cerca.

Ejemplo en Python que demuestra cómo romper el cifrado RSA

En las siguientes celdas de código, ilustramos un ejemplo de cómo encontrar una clave privada teniendo solo acceso a la clave pública. Se usará computación clásica por fuerza bruta, pero muestra cómo podría utilizarse el algoritmo de Shor, incluso con claves grandes.

nota

En esta sección mostraremos los cálculos matemáticos en detalle como parte del código Python

En el ejemplo, tenemos una clave pública $(5, 247)$ y recuperaremos la clave privada.

Paso 1: El primer paso es elegir un número coprimo con 247. Casi cualquier número que elijamos servirá. Elijamos 6.

n = 247  # the modulus
e = 5  # public key number
a = 6  # an integer coprime to n
assert gcd(a, n) == 1
print(f"Checked {n} and {a} are coprime")

Paso 2: A continuación necesitamos encontrar el período $r$ tal que $6^r \equiv 1 (mod~247)$ . En este ejemplo, calculamos $r$ clásicamente mediante fuerza bruta, pero también podríamos usar el algoritmo de Shor en un ordenador cuántico usando Qiskit.

r = 0
rem = 100
while rem != 1:
    r += 1
    rem = (a**r) % n

print(f"period r is: {r}")
assert a**r % n == 1

print(f"Checked {a}^{r} mod {n} is 1")

Paso 3: Dado que el período $r = 36$ es par, podemos calcular $f1 = (a^{r/2}-1), f2=(a^{r/2}+1)$ .

# explicitly use as integer
f1 = int(a ** (r / 2) - 1)
f2 = int(a ** (r / 2) + 1)

print(f"f1 = {f1}")
print(f"f2 = {f2}")

Paso 4: Encuentra el MCD de cualquiera de esos factores con $n$ . Simplemente divide $n$ entre el factor primo ya encontrado para obtener el segundo factor primo.

q_found = gcd(f1, n)
print(f"One possible prime factor of n ({n}) is: {q_found}")

# explicit int (to avoid floating point)
p_found = int(n / q_found)
print(f"The second prime factor of n ({n}) is: {p_found}")

assert n == p_found * q_found

Paso 5: Habiendo recuperado los factores primos de $n = 247$ como $p_{found}=13$ y $q_{found}=19$ , calculamos el totiente $\phi_{found} = (p_{found}-1)*(q_{found}-1)$ .

La clave privada es el inverso modular del número de clave pública $e=5$ .

# Compute the totient
phi_found = (p_found - 1) * (q_found - 1)
print(f"The totient is: {phi_found}")

# Recover the private key number d_found by satisfying (d_found * e) % phi_found = 1
d_found = 1
while True:
    if (d_found * e) % phi_found == 1:
        break
    else:
        d_found += 1
print("Private Key number:", d_found)

En el esquema anterior, el paso 2 es la operación crucial de búsqueda de período para la cual el algoritmo de Shor emplea dos primitivas cuánticas fundamentales, concretamente la transformada cuántica de Fourier y la estimación cuántica de fase. Para una explicación detallada de los aspectos cuánticos del algoritmo de Shor, consulta la lección sobre estimación de fase y factorización en Fundamentos de Algoritmos Cuánticos. Los pasos 1 y 3 al 5 implican operaciones relativamente económicas que pueden llevarse a cabo fácilmente en ordenadores clásicos.

Opcionalmente, aquí tienes un recorrido visual detallado sobre la implementación del algoritmo de Shor.

En ordenadores cuánticos, el algoritmo de Shor puede exhibir un escalado poliogarítmico tan favorable como $O((log~n)^2 (log~log~n))$ en términos del módulo $n$ , o un escalado polinomial en términos del número de bits necesarios para representar $n$ . Esto supone una aceleración superpolinomial en comparación con el algoritmo GNFS clásico.

Las estimaciones de recursos recientes indican que, basándose en ciertos supuestos sobre la configuración del hardware, serán necesarios entre unas decenas de miles y varios millones de cúbits para romper RSA de 2048 bits usando el algoritmo de Shor. No es inconcebible que los ordenadores cuánticos con varias decenas de miles de cúbits estén disponibles en los próximos años, haciendo accesible el extremo inferior de la estimación de recursos.

Intercambio de claves Diffie-Hellman y el Algoritmo de Firma Digital

En la sección anterior, discutimos el criptosistema RSA, cuya seguridad se basa en la dificultad computacional de la factorización prima. Aquí, discutiremos dos populares protocolos criptográficos de clave asimétrica, el intercambio de claves Diffie-Hellman (DH) y el Algoritmo de Firma Digital (DSA), ambos basados en un problema matemático diferente, concretamente el problema del logaritmo discreto (DLP).

El problema del logaritmo discreto

En la siguiente ecuación necesitamos encontrar $a$ conociendo solo $e$ , $M$ , $c$

$a^e$ $mod$ $M = c$

Se cree que esto es difícil con los ordenadores clásicos debido al uso de la aritmética modular, y por lo tanto es una buena base matemática para un algoritmo de cifrado.

Esto se conoce como el problema del logaritmo discreto (DLP).

Detalles matemáticos del problema del logaritmo discreto

El DLP se enmarca típicamente en el contexto de los grupos cíclicos y se enuncia de la siguiente manera.

Considera un grupo cíclico $G$ generado por un elemento de grupo $g \in G$ y, dado un elemento arbitrario $h \in G$ , encuentra un entero $k$ tal que $h = g^{k}$ .

Aquí el entero $k \equiv log_{g}h$ es el logaritmo discreto. La propiedad cíclica de $G$ garantiza que para todo $h$ existe un entero válido $k$ .

Para la criptografía, resulta útil el DLP en el grupo multiplicativo de enteros módulo un número primo $p$ , denotado $(\mathbb{Z}_p)^{\times}$ . Los elementos de $(\mathbb{Z}_p)^{\times}$ son clases de congruencia etiquetadas por enteros módulo $p$ que son coprimos con $p$ .

Por ejemplo:

$(\mathbb{Z}_5)^{\times} = \{[1],[2],[3],[4]\}~\mathrm{y}~(\mathbb{Z}_7)^{\times} = \{[1],[2],[3],[4],[5],[6]\}$

La operación de multiplicación $(\times)$ en estos grupos es simplemente la multiplicación ordinaria de enteros seguida de reducción módulo $p$ , y la exponenciación por un entero $k$ es simplemente la multiplicación repetida $k$ veces y reducción módulo $p$ .

Ilustremos una instancia del DLP en $(\mathbb{Z}_7)^{\times}$ .

Este grupo multiplicativo tiene dos generadores $\{[3],[5]\}$ , también conocidos como raíces primitivas. Usaremos $[5]$ como generador; es decir, generaremos cada elemento de $(\mathbb{Z}_7)^{\times}$ usando potencias enteras sucesivas de 5.

#Generate elements of (Z_7)^{x} using generator [5].
g = 5
p = 7
print(f"Using generator {g}")
for k in range(3*p):
    print(f"{g}**{k} mod {p} ≡ {(g**k)%7}")

Vemos que en aritmética módulo 7, elevar 5 a potencias enteras sucesivas produce cada elemento de $(\mathbb{Z}_7)^{\times}$ exactamente una vez antes de que el ciclo se repita indefinidamente con un período $p-1 =6$ .

Por lo tanto, el DLP en $(\mathbb{Z}_7)^{\times}$ con generador [5] es:

$\mathrm{Dado}~h \in (\mathbb{Z}_7)^{\times} \mathrm{, encontrar~} k \mathrm{~tal~que~} 5^{k} \equiv h~(mod~7)$ .

A partir de la salida de la celda Python anterior vemos que:

$h = 2 \implies k=4 \mathrm{~o~} 4 = log_5(2) (mod~7)$

$h = 6 \implies k=3 \mathrm{~o~} 3 = log_5(6) (mod~7)$

En la aritmética de números reales ordinaria, la exponenciación es una función monótona y encontrar el logaritmo de cualquier número en cualquier base es computacionalmente fácil. En contraste, como es evidente en el simple ejemplo de $(\mathbb{Z}_7)^{\times}$ anterior, la exponenciación modular no es monótona y, aunque es periódica con período $p-1$ , es por lo demás sumamente no trivial. Por lo tanto, calcular su inversa, el logaritmo discreto, resulta ineficiente para $p$ grande en los ordenadores clásicos.

Esta observación sustenta tanto el intercambio de claves Diffie-Hellman (DH) como el Algoritmo de Firma Digital (DSA), que se discuten en la siguiente sección.

El DLP puede extenderse a subgrupos cíclicos de la siguiente manera:

Considera $(\mathbb{Z}_p)^{\times}$ definido anteriormente y un elemento $g \in (\mathbb{Z}_p)^{\times}$ de orden primo $r$ , es decir, $g^r \equiv 1 (~mod~p)$ .
El conjunto de potencias enteras de $g$ : $\{g^k~(mod~p) | 1 \le k \le r\} = \langle g \rangle$ es un subgrupo cíclico de $(\mathbb{Z}_p)^{\times}$ con orden de grupo $r$ .
Un DLP puede especificarse en $\langle g \rangle$ eligiendo $h \in \\langle g \rangle$ y buscando $1 \le a \le r$ tal que $g^a~(mod~p) = h$

Intercambio de claves Diffie-Hellman

En 1976, Whitfield Diffie y Martin Hellman propusieron un protocolo de intercambio de claves para permitir la creación de una clave secreta compartida sobre canales de comunicación inseguros. La clave secreta podría entonces ser usada por las partes que la comparten para el cifrado simétrico. El algoritmo se basa en el DLP.

Figure 1. Diffie-Hellman key exchange

Figura 1. Intercambio de claves Diffie-Hellman

Detalles matemáticos del intercambio de claves Diffie-Hellman

Con Alice y Bob como las dos partes que se comunican, el protocolo funciona de la siguiente manera:

Primero, Alice y Bob acuerdan un número primo grande $p$ y una raíz primitiva o generador $a$ .
Luego, Alice elige un exponente secreto $k_A$ aleatoriamente con $1 \le k_A \le p-2$ y calcula $h_A = a^{k_A}~(mod~p)$ . $k_A, h_A$ son las claves privada y pública de Alice, respectivamente.
A continuación, Bob elige un exponente secreto $k_B$ aleatoriamente con $1 \le k_B \le p-2$ y calcula $h_B = a^{k_B}~(mod~p)$ . $k_B, h_B$ son las claves privada y pública de Bob, respectivamente.
Luego, Alice envía a Bob $h_A$ y Bob envía a Alice $h_B$ a través de un canal fiable pero no necesariamente seguro.
A continuación, Alice usa el $h_B$ que recibió para calcular la clave secreta compartida $\kappa = h_B^{k_A}~(mod~p)$ .
Finalmente, Bob mientras tanto usa el $h_A$ que recibió para calcular la clave secreta compartida $\kappa = h_A^{k_B}~(mod~p)$ .

Con este protocolo,

Alice y Bob tienen garantizado acabar con la misma clave secreta $\kappa$ porque $h_B^{k_A}~(mod~p) = (a^{k_B})^{k_A}~(mod~p) = a^{k_A k_B}~(mod~p) = (a^{k_A})^{k_B}~(mod~p) = h_A^{k_B}~(mod~p)$ .
Un tercero que intercepte $h_A$ o $h_B$ no puede construir la clave secreta $\kappa$ porque no tiene acceso a $k_B$ o $k_A$ respectivamente.
Extraer $k_A$ o $k_B$ usando la información pública $a$ , $p$ , $h_A$ y $h_B$ es computacionalmente difícil ya que equivale a resolver el DLP en $(\mathbb{Z}_p)^{\times}$ .

Ilustración del protocolo Diffie-Hellman en Python

Veamos un ejemplo sencillo del protocolo DH en Python usando números primos pequeños:

nota

En esta sección mostraremos los cálculos matemáticos en detalle como parte del código Python

Paso 1: Alice y Bob acuerdan un primo $p$ y una raíz primitiva $a$ . Elijamos $p=11, a=7$ .

# Step 1: Choose a prime `p` and a primitive root `a`
p = 11
a = 7

print(f"prime: {p}")
print(f"primitive root: {a}")

Pasos 2, 3: Alice elige un exponente secreto $k_A$ y calcula $h_A = a^{k_A}~(mod~p)$ . De manera similar, Bob elige un exponente secreto $k_B$ y calcula $h_B = a^{k_B}~(mod~p)$ .

k_A = 4  # Alice's private key
h_A = (a ** (k_A)) % p  # Alice's public key

print(f"Alice's private key is {k_A} and public key is {h_A}")

k_B = 8  # Bob's private key
h_B = (a ** (k_B)) % p  # Bob's public key

print(f"Bob's private key is {k_B} and public key is {h_B}")

Paso 4: Las dos partes difunden sus claves públicas $h_A$ y $h_B$ .

Pasos 5, 6: Cada parte combina su clave privada con la clave pública de la otra parte para crear la clave secreta compartida.

secret_key_alice = h_B**k_A % p
secret_key_bob = h_A**k_B % p
assert secret_key_alice == secret_key_bob
print(f"The shared secret key is: {secret_key_bob}")

Alice y Bob ya pueden usar la clave secreta compartida para el cifrado simétrico.

Seguridad del intercambio de claves Diffie-Hellman

Como se señaló anteriormente, la seguridad de DH se basa en la dificultad computacional de resolver el DLP con grandes primos $p$ . En aplicaciones típicas, NIST recomienda enteros primos de 2048 o 3072 bits para el intercambio de claves DH, lo cual se considera suficientemente seguro frente a los intentos de resolver el DLP usando ordenadores clásicos.

Ataques de hombre en el medio (MITM): El hecho de que DH sea un esquema interactivo donde el secreto compartido depende de combinar la clave privada de una parte con la clave pública de la otra lo hace vulnerable a un llamado ataque de hombre en el medio (MITM).

Detalles matemáticos de la seguridad de DH y los ataques MITM

En este escenario, un tercero —digamos, Eva— intercepta las claves públicas $h_A, h_B$ durante la transmisión y sustituye su propia clave pública $h_E$ por cada una de $h_A$ y $h_B$ antes de reenviarlas a Bob y Alice, respectivamente.

Entonces, en lugar de usar $h_B$ para crear su secreto compartido, Alice usará $h_E$ mientras cree que está usando la clave pública de Bob. De manera similar, en lugar de usar $h_A$ para crear su secreto compartido, Bob usará $h_E$ mientras cree que está usando la clave pública de Alice.

Dado que $h_E$ se usó para crear el secreto compartido de Alice (Bob), el texto plano cifrado por Alice (Bob) puede ser descifrado por Eva.

Por lo tanto, el intercambio de claves DH se usa típicamente junto con un algoritmo de firma digital para garantizar que cada parte use una clave pública autenticada para crear su secreto compartido.

El Algoritmo de Firma Digital (DSA)

Aunque los criptosistemas genéricos como RSA proporcionan funcionalidad de firma digital, en 1994 NIST adoptó un esquema de firma especializado basado en la exponenciación modular y el problema del logaritmo discreto como estándar federal para las firmas digitales. Este esquema, que llegó a conocerse simplemente como el Algoritmo de Firma Digital (DSA), involucra cuatro fases distintas:

Generación de claves:

Las claves DSA se generan a partir de:
- 2 primos que cumplen ciertas reglas
  - $p$ - típicamente 256 bits (llamaremos a esta longitud $N$ )
  - $q$ - típicamente 3072 bits (llamaremos a esta longitud $L$ )
- Una función hash criptográfica que convertirá cadenas de longitud $L$ a $N$
- Un parámetro adicional $g$ (ver detalles a continuación)
A partir de esto, elegimos un número aleatorio $x$ como clave privada y podemos calcular una clave pública $y$
Detalles matemáticos de la generación de claves
- Generación de parámetros: Matemáticamente, DSA involucra un subgrupo cíclico de $(\mathbb{Z}_p)^{\times}$ generado por un elemento $g$ de orden primo q < p. El primer paso en el DSA es por tanto seleccionar dos primos p, q para establecer las estructuras matemáticas necesarias.
  
  Elige un primo $q$ de $N$ bits.
  
  Elige un primo $p$ de $L$ bits tal que $p-1$ sea un múltiplo de $q$ . La elección de $p$ especifica el grupo $(\mathbb{Z}_p)^{\times}$
  
  Elige un entero $1 < h < p-1$ al azar y calcula $g = h^{(p-1)/q}~mod~p$ . Si $g=1$ , lo que ocurre raramente, prueba con otro h.
  
  Verifica que $g^q~mod~p = 1$ . g es por tanto un generador de un subgrupo cíclico $\langle g \rangle$ de $(\mathbb{Z}_p)^{\times}$ de orden primo q.
  
  Los parámetros $(q, p, g)$ especifican una instancia del algoritmo y son información pública. Típicamente, $N \sim 256$ y $L \sim 3072$ en aplicaciones reales.
  
  El protocolo también requiere una función hash criptográfica $H : \{0,1\}^L \rightarrow \{0, 1\}^N$ que mapea cadenas binarias de $L$ bits a cadenas de $N$ bits, por ejemplo SHA-256.
- Generación del par de claves: El firmante necesita generar un par de claves en su extremo.
  
  Elige un entero secreto aleatorio $x \in \{1,2...q-1\}$ . $x$ es la clave privada.
  
  Genera $y = g^{x}~mod~p$ . $y$ es la clave pública del firmante.
Distribución de claves:

La siguiente información se comparte con cualquiera que desee validar una firma
- Los parámetros utilizados $(p,q,g)$ que describen el algoritmo
- La función hash $H$
- La clave pública $y$
Firma:
- El firmante puede ahora firmar un mensaje $m$ . La firma resultante es $(r,s)$
- El mensaje y la firma se envían al destinatario
Detalles matemáticos de la firma de un mensaje
El firmante firma un mensaje $m$ de la siguiente manera:
- Elige un entero secreto k al azar de $\{1,2...q-1\}$
- Calcula $r = (g^k~mod~p)~mod~q$ . En el raro caso en que $r=0$ , prueba con otro k aleatorio.
- Calcula $s = (k^{-1} (H(m) + xr))~mod~q$ . En raros casos, si $s=0$ , prueba con otro k aleatorio.
- La firma es la tupla $(r, s)$ .
- El firmante transmite el mensaje $m$ así como la firma $(r,s)$ al verificador.
Dado que tanto $r$ como $s$ son enteros, módulo $q$ el tamaño de la firma es del orden de $N$ bits y no de los más largos $L$ bits.
Verificación:

El destinatario ahora desea verificar la autenticidad del remitente. Tiene acceso a la información pública $(q, p, g, H, y, (r,s), m)$ Puede ejecutar un cálculo que demuestre que el remitente tenía acceso a la clave privada $x$

y busca comprobar que el firmante es alguien con acceso a la clave privada $x$ .
Detalles matemáticos del esquema de verificación DSA
- Verifica que $0 \lt r \lt q$ y $0 \lt s \lt q$ , es decir, que $r, s$ son enteros válidos módulo~q.
- Calcula $w = s^{-1}~mod~q$ .
- Calcula $u_1 = H(m)w~mod~q$ .
- Calcula $u_2 = rw~mod~q$ .
- Calcula $v = (g^{u_1}y^{u_2}~mod~p)~mod~q$ .
- La firma se verifica si $v = r$ .
Para firmas legítimas, la corrección del algoritmo DSA se demuestra fácilmente de la siguiente manera:
- En el extremo del firmante: $s = (k^{-1} (H(m) + xr))~mod~q \implies k = ((H(m) + xr)s^{-1})~mod~q$
- Considerando el lado derecho de esta última igualdad, un verificador puede calcular $s^{-1}, H(m)$ porque $s, q, m, H$ son información pública.
- Así, el verificador calcula $w = s^{-1}~mod~q$ y $u_1 = H(m)w~mod~q = H(m)s^{-1}~mod~q$ .
- El verificador también calcula $u_2 = rw~mod~q = rs^{-1}~mod~q$ ya que $r$ también es público.
- Nótese que $k = (u_1 + xu_2)~mod~q$ .
- Sin embargo, un verificador no tiene acceso a $x$ ya que es la clave privada del firmante, por lo que $k$ en sí mismo no puede calcularse directamente. El esquema se basa en cambio en el hecho de que aunque el verificador no puede calcular $k$ , con un firmante legítimo, el verificador debería poder recalcular $(g^k~mod~p)~mod~q = r$ con la ayuda de la clave pública del firmante $y = g^{x}~mod~p$ .
- Así, el verificador calcula $v = (g^{u_1}y^{u_2}~mod~p)~mod~q = (g^{u_1}g^{xu_2}~mod~p)mod~q = (g^{u_1+xu_2}~mod~p)mod~q = (g^k~mod~p)mod~q$ .
- La última igualdad se sigue porque $g$ tiene orden $q$ y establece $v = r$ para firmas válidas.

Ilustración del DSA en Python

En este ejemplo, usaremos primos pequeños para ilustrar el proceso DSA en un escenario donde Alice envía un mensaje firmado a Bob. Usaremos enteros pequeños en este ejemplo. Un escenario real emplearía primos mucho más grandes del orden de 2048-3072 bits.

nota

Puedes intentar volver a ejecutar este ejemplo con diferentes valores para ver cómo se comporta el algoritmo, pero asegúrate de empezar a ejecutar desde la primera celda de esta sección.

Comenzamos importando las bibliotecas necesarias y eligiendo nuestros parámetros. Los parámetros enteros $p$ , $q$ , $g$ son información pública y satisfacen las siguientes reglas:

$p$ , $q$ son ambos primos
$(p-1) \mod\ q = 0$
$g \ge 2$
$g \le (p-2)$
$g^{(p-1)/q} \mod\ p \neq 1$

from random import randint

# parameter generation: select the primes q, p and generator g:
# EXPERIMENT with the values, they must meet certain rules
# this example code does not verify p,q are prime

q = 11
p = 23
g = 4

assert (p - 1) % q == 0
assert g >= 2
assert g <= (p - 2)
assert (pow(g, (p - 1) / q) % p) != 1

print(f"Public information is good: q={p}, p={q}, g={g}")

A continuación, el firmante, Alice, genera su clave privada.

La clave privada, k (alice-private-key en el código Python) debe satisfacer:

$k \ge 2$
$k \le (q-1)$

# Alice chooses an integer randomly from {2..q-1}
# EXPERIMENT with the values

alice_private_key = randint(2, q - 1)
# alice_private_key =

assert alice_private_key >= 2
assert alice_private_key <= (q - 1)

print(f"Alice's private key is {alice_private_key}")

Alice mantiene su clave privada en secreto.

A continuación, Alice calcula su clave pública usando la exponenciación modular. Invertir este paso para recuperar la clave privada es una instancia del DLP, por lo tanto difícil de calcular en ordenadores clásicos cuando se usan primos grandes.

A partir de la explicación matemática anterior, sabemos que esto puede calcularse usando la fórmula:

$y = g^{x} \mod\ p$

alice_public_key = pow(g, alice_private_key, p)
# Alternatively can use (g ** alice_private_key) % p

print(f"Alice's public key is {alice_public_key}")

Como de costumbre, Alice hace pública su clave pública a través de un canal no necesariamente secreto.

Ahora Alice puede firmar un mensaje.

Para el esquema de firma digital, necesitamos generar un hash $H(m)$ del mensaje $m$ a firmar.

Supongamos que Alice y Bob acuerdan usar un algoritmo de hashing particular con longitud de hash $N$ igual al número de bits de $q$ . En este ejemplo simple, acotaremos las salidas de nuestra función hash simulada por $q$ . La función hash aquí es trivial: simplemente genera un entero aleatorio.

hash_dict = {}

def mock_hash_func(input_message):
    print(input_message)
    if input_message not in hash_dict:
        hash_dict[input_message] = randint(1, q)
    return hash_dict[input_message]

alice_message = "Inspection tomorrow!"
alice_hash = mock_hash_func(alice_message)  # In reality, you'd use a hash function
print(f"Alice's message hash is: {alice_hash}")

A continuación, Alice necesita generar un número secreto aleatorio por mensaje $k$ , así como su inverso multiplicativo módulo $q$ , para calcular la firma.

Se puede usar un algoritmo sencillo de fuerza bruta para calcular el inverso modular. Sin embargo, es mejor usar una de las funciones integradas de Python pow como se muestra a continuación.

# brute-force implementation to find modular inverse
def modular_inverse(k, q):
    for i in range(0, q):
        if (k * i) % q == 1:
            return i
    print(f"error! no inverse found! for {k},{q}")
    return 0

# Let's compare this algorithm with the standard python 'pow' function

n1 = modular_inverse(3, 7)
n2 = modular_inverse(4, 11)
n3 = modular_inverse(7, 5)
m1 = pow(3, -1, 7)
m2 = pow(4, -1, 11)
m3 = pow(7, -1, 5)

assert n1 == m1
assert n2 == m2
# assert(n3==m3)

print(f"modular_inverse(3,7) = {m1}")
print(f"modular_inverse(4,11) = {m2}")
print(f"modular_inverse(7,5) = {m3}")

# Some numbers don't have modular inverses - our function throws an error
n4 = modular_inverse(2, 6)

# The python library will throw an exception, which must be caught
if math.gcd(2, 6) == 1:
    m4 = pow(2, -1, 6)
else:
    print("Exception from pow() - no modular inverse found!")

Alice ya puede calcular la firma.

$r = (g^{k} \mod p) \mod\ q$
$s = (k^{-1} (H(m) + xr)) \mod q$

Nótese que hay ciertas condiciones particulares que nos obligarán a elegir un valor diferente para $k$ en el caso en que $r$ o $s$ den como resultado $0$ . En este caso generaremos un nuevo valor y repetiremos.

# Start an infinite loop; we will 'break' out of it once a valid signature is found.
while True:
    k = randint(1, q - 1)  # Should be different for every message
    print("Using random k =", k)

    r = pow(g, k, p) % q
    # If r is 0, the value is invalid. Try again with a new k.
    if r == 0:
        print(f"{k} is not a good random value to use to calculate r. Trying another k")
        continue

    s = (pow(k, -1, q) * (alice_hash + alice_private_key * r)) % q
    # If s is 0, the value is also invalid. Try again with a new k.
    if s == 0:
        print(f"{k} is not a good random value to use to calculate s. Trying another k")
        continue

    # If we've reached this point, both r and s are valid. Break the loop.
    signature = (r, s)
    print(f"Alice's signature is : {(r,s)}")
    break

# After the loop, the valid r and s values can be used here.
# print(f"Generated Signature -> r: {r}, s: {s}")

Alice difunde el mensaje y su firma al receptor o verificador, Bob.

Bob ha obtenido previamente la clave pública de Alice y ahora puede verificar la firma para autenticar su mensaje.

Para hacerlo, realiza algunas comprobaciones, y luego vuelve a generar un hash del mensaje difundido por Alice y calcula las cantidades auxiliares $w, u_1, u_2$ y $v$ .

$0 < r < q$
$0 < s < q$
$w = s^{-1} \mod\ q$
$u_{1} = H(m) . w \mod\ q$
$u_{2} = r . w \mod\ q$
$v = (g^{u1}y^{u2} \mod\ p) \mod\ q$

Finalmente, Bob comprueba si $v$ es igual a $r$ . Si son iguales, la firma queda verificada.

# Bob re-generates message hash using Alice's broadcast message
bob_hash = mock_hash_func(alice_message)

# Bob computes auxiliary quantities w (using modular inverse), u1, u2 and v
w = (pow(s, -1, q)) % q
u1 = (bob_hash * w) % q
u2 = (r * w) % q
v = ((g**u1 * alice_public_key**u2) % p) % q

if v == r:
    print("Signature is valid!")
else:
    print("Signature is invalid!")

Seguridad del DSA

Con la computación clásica, la seguridad del DSA puede verse influida por varios factores:

Tamaño de clave: Como siempre, el tamaño de clave proporciona protección básica contra los ataques de fuerza bruta. Las aplicaciones modernas que usan DSA emplean tamaños de clave de al menos 2048 bits.
Calidad de $k$ : En DSA, cada firma necesita un valor $k$ único, aleatorio y secreto (véase más arriba). La unicidad, la entropía y el secreto de $k$ son críticos, y la debilidad en cualquiera de estos aspectos podría llevar a que la clave privada $x$ se vea comprometida. Los generadores de números aleatorios usados para generar $k$ necesitan ser seguros por sí mismos.
Fortaleza de la función hash: Dado que DSA utiliza una función hash como parte del proceso de generación y verificación de firmas, una función hash débil podría comprometer la seguridad de la firma digital. Por ejemplo, el uso de SHA-1 con DSA está en desuso y se recomienda SHA-2 o superior.

Además de estos, una implementación robusta de DSA también debe protegerse contra otros tipos de ataques que tienen como objetivo la criptografía de clave asimétrica, tal como se describió anteriormente.

Intercambio de claves autenticado con Diffie-Hellman y DSA

Los protocolos modernos de seguridad de red, como Transport Layer Security (TLS) y muchos otros, implican combinar las funcionalidades de intercambio de claves y autenticación. En el contexto de Diffie-Hellman, se necesita autenticación para protegerse contra los ataques MITM. En las siguientes celdas de código, ilustramos un ejemplo donde Alice y Bob realizan un intercambio de claves autenticado combinando los protocolos Diffie-Hellman y DSA. Para ello, usaremos la biblioteca Python cryptography.

Figure 2. Authenticated key exchange with Diffie-Hellman and DSA

Figura 2. Intercambio de claves autenticado con Diffie-Hellman y DSA

Primero, Alice y Bob acuerdan un conjunto de parámetros DH y generan un conjunto de pares de claves públicas y privadas DH.

# import necessary library modules
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import dh, dsa

# Generate DH parameters
parameters = dh.generate_parameters(generator=2, key_size=2048)

# Generate Alice's DH private key and public key
alice_dh_private_key = parameters.generate_private_key()
alice_dh_public_key = alice_dh_private_key.public_key()

# Generate Bob's DH private key and public key
bob_dh_private_key = parameters.generate_private_key()
bob_dh_public_key = bob_dh_private_key.public_key()

print("Public and private keys generated for Bob and Alice")

Las claves públicas DH se difunden. A continuación, tanto Alice como Bob generan por separado un par de claves para usar con DSA. Estas claves se usarán a su vez para firmar las claves públicas DH que se van a intercambiar.

# Generate DSA keys for Alice and Bob
alice_dsa_private_key = dsa.generate_private_key(key_size=2048)
alice_dsa_public_key = alice_dsa_private_key.public_key()
bob_dsa_private_key = dsa.generate_private_key(key_size=2048)
bob_dsa_public_key = bob_dsa_private_key.public_key()

print("Additional key pair generated for signing")

Alice firma su clave pública DH usando su clave privada DSA.

# Alice signs
alice_public_bytes = alice_dh_public_key.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo,
)
alice_signature = alice_dsa_private_key.sign(alice_public_bytes, hashes.SHA256())

print("Alice signed public key")

De manera similar, Bob firma su clave pública DH usando su clave privada DSA.

bob_public_bytes = bob_dh_public_key.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo,
)
bob_signature = bob_dsa_private_key.sign(bob_public_bytes, hashes.SHA256())

print("Bob signed public key")

Las claves públicas DH y las firmas correspondientes son ahora difundidas por Alice y Bob. Habiendo recibido la clave pública y la firma de su contraparte, cada parte verifica entonces que la firma es válida. De esta manera, se puede prevenir un ataque MITM, ya que Alice, por ejemplo, sabe que la clave pública DH de Bob fue efectivamente firmada por Bob y viceversa.

# Alice and Bob verify each other's DH public keys using DSA public keys
# An InvalidSignature exception will occur if they are not valid
alice_dsa_public_key.verify(alice_signature, alice_public_bytes, hashes.SHA256())
bob_dsa_public_key.verify(bob_signature, bob_public_bytes, hashes.SHA256())

print("Signatures are valid")

Tras la verificación de la firma, Alice y Bob generan el secreto compartido, lo que completa el intercambio de claves.

# Perform key exchange
alice_shared_key = alice_dh_private_key.exchange(bob_dh_public_key)
bob_shared_key = bob_dh_private_key.exchange(alice_dh_public_key)

print("Shared secrets generated")

Opcionalmente, para mayor seguridad, Alice y Bob pueden usar una función de derivación de claves especializada como HKDF para generar una clave simétrica más segura a partir de su secreto compartido mediante técnicas de estiramiento de claves.

# Derive a shared symmetric key using key-stretching
def derive_key(shared_key):
    return HKDF(
        algorithm=hashes.SHA256(),
        length=32,
        salt=None,
        info=None,
    ).derive(shared_key)

alice_symmetric_key = derive_key(alice_shared_key)
bob_symmetric_key = derive_key(bob_shared_key)

assert alice_symmetric_key == bob_symmetric_key
print("Keys checked to be the same")

Rompiendo Diffie-Hellman y DSA

Tanto los protocolos Diffie-Hellman (DH) como DSA implican la generación de claves públicas de la forma $y = g^{x}~mod~p$ , donde la clave privada $x$ es el logaritmo discreto.

Un atacante que pueda resolver una instancia del DLP puede exponer la clave privada de una de las dos partes y, combinándola con la clave pública de la segunda parte, obtener acceso al secreto compartido. En el caso de DSA, un atacante que pueda resolver el DLP puede recuperar la clave privada del firmante, anulando la premisa básica de una firma digital.

En los sistemas de computación clásica, se cree que el DLP no tiene solución en tiempo polinomial. Pero como demostró Peter Shor en su artículo original de 1994, el algoritmo de Shor también resuelve el DLP en tiempo polinomial en computadoras cuánticas.

El algoritmo de Shor y el problema del logaritmo discreto

El algoritmo de Shor es capaz de resolver el problema del logaritmo discreto en tiempo polinomial. Logra principalmente su eficiencia mediante el uso de algoritmos cuánticos que pueden encontrar el período de una función que depende de la entrada del problema, la cual se combina luego con operaciones más convencionales.

Detalles matemáticos del algoritmo de Shor

El algoritmo de Shor proporciona una solución eficiente al DLP mapeándolo a un problema más general de teoría de grupos conocido como el problema del subgrupo oculto (HSP, por sus siglas en inglés).

En el HSP, se tiene un grupo algebraico $G$ y una función $f: G \rightarrow X$ de $G$ a algún conjunto $X$ tal que $f$ es constante en cada coclase de algún subgrupo $H$ de $G$ (y distinta en coclases diferentes). La tarea consiste entonces en determinar $H$ . Se sabe que las computadoras cuánticas pueden resolver el HSP en grupos abelianos finitos en tiempo polinomial en $log~|G|$ , donde $|G|$ es el orden del grupo.

En el caso del DLP entero discutido en esta lección, el mapeo al HSP es el siguiente:

Sea $p$ un número primo y considera el DLP dado por $y = g^r~mod~p$ donde $g$ es un generador de $(\mathbb{Z}_p)^{\times}$ . Como $g^{p-1} \equiv 1~mod~p$ , $g$ tiene orden $p-1$ .
Elige $G = \mathbb{Z}_{p-1} \times \mathbb{Z}_{p-1}$ donde $\mathbb{Z}_{p-1}$ es el grupo de enteros módulo $(p-1)$ .
Elige $f : G \rightarrow (\mathbb{Z}_p)^{\times}$ definida como $f(a, b) = g^a y^{-b}~mod~p \equiv g^{a-rb}~mod~p$ .
El núcleo de $f$ es entonces el subgrupo $H_0 = \langle (r, 1) \rangle = \{(a,b) \in G | f(a,b) \equiv 1~mod~p\} = \{ (a, b) \in G | a - rb \equiv 0~mod~(p-1)\}$ .
$f$ es constante en las coclases $(\delta, 0) + H_0$ y "oculta" el subgrupo $H_0$ , planteando un HSP.

Con lo anterior, el algoritmo cuántico de Shor para el DLP entero utiliza un oráculo cuántico para evaluar la función $f$ en un estado que representa una superposición uniforme sobre $G$ , y luego emplea la transformada cuántica de Fourier y mediciones con estimación de fase para producir estados cuánticos que permiten identificar el generador $(r, 1)$ de $H_0$ . A partir de esto, se puede extraer $r$ , el logaritmo discreto de interés.

El artículo original de Shor contiene una descripción detallada del algoritmo.

Criptografía de curva elíptica

La criptografía de curva elíptica (ECC), basada en las matemáticas de las curvas elípticas, ofrece un enfoque poderoso para la criptografía de clave asimétrica. Se sabe que ECC proporciona un nivel de seguridad similar al de métodos como RSA, pero con claves más cortas, lo que la hace más eficiente y especialmente adecuada para sistemas con recursos limitados, como sistemas embebidos y dispositivos móviles, donde el ahorro de almacenamiento y computación que ofrecen los tamaños de clave más pequeños es muy deseable.

Principios básicos de la criptografía de curva elíptica

Una curva elíptica tiene típicamente la forma $y^2 = x^3 + ax + b$ y posee algunas propiedades interesantes.

Es simétricamente horizontal. Así, para cualquier punto $(x,y)$ en la curva, su reflejo $(x,-y)$ también está en la curva.
Cualquier línea recta no vertical intersecará la curva en un máximo de tres puntos.

Figure 1. Operations of addition and point doubling on an elliptic curve. Facet 1 defines P + Q = -R. Facet 2 illustrates point doubling 2Q = -P. Facet 3 defines the additive inverse of a point as its reflection about the x-axis i.e, P = -Q

Figura 1. Operaciones de adición y doblado de punto en una curva elíptica. La faceta 1 define P + Q = -R. La faceta 2 ilustra el doblado de punto 2Q = -P. La faceta 3 define el inverso aditivo de un punto como su reflejo respecto al eje x, es decir, P = -Q

La criptografía de curva elíptica hace uso de una serie de operaciones aritméticas aplicadas a puntos de la curva. Cada una navega efectivamente hacia un nuevo punto en la curva. Este es un proceso sencillo de seguir en una dirección y, con tamaños de clave más cortos, resulta más eficiente que otros algoritmos como RSA; sin embargo, invertirlo es muy difícil, de ahí su aplicación a la criptografía.

Principios matemáticos de la criptografía de curva elíptica

Una curva elíptica sobre un campo algebraico $K$ está definida por una ecuación matemática, típicamente de la forma $y^2 = x^3 + ax + b$ con los coeficientes $a, b \in K$ , y describe puntos $(x, y) \in K \otimes K$ con el requisito adicional de que la curva no tenga codos ni autointersecciones.

Las propiedades de las curvas elípticas permiten definir operaciones de "adición" y "multiplicación escalar" que involucran puntos de la curva.

Adición: Si $P$ y $Q$ son dos puntos en una curva elíptica, entonces $P + Q$ describe un tercer punto único identificado de la siguiente manera: traza la línea que intersecta $P$ y $Q$ y encuentra el tercer punto, $R$ , donde esa línea vuelve a intersectar la curva. Entonces definimos $P + Q = −R$ , el punto opuesto a $R$ reflejado a través del eje $x$ (ver figura a continuación). Cuando la línea que pasa por $P, Q$ no intersecta la curva en ningún punto finito $(x, y)$ , decimos que intersecta la curva en el punto del infinito $\mathbf{O}$ .

La adición en curvas elípticas satisface las propiedades algebraicas de grupo, con el punto del infinito como identidad aditiva.

Doblado y multiplicación escalar: La operación de doblado de punto, que corresponde a la multiplicación escalar por $2$ , se obtiene fijando $P = Q$ en la operación de adición e involucra gráficamente la línea tangente en $P$ . La multiplicación escalar general por un entero $n$ , definida como $nP = P + P + ...~n$ veces, se obtiene mediante doblados y adiciones repetidas.

Problema del logaritmo discreto en curva elíptica

El problema del logaritmo discreto en curva elíptica (ECDLP) tiene muchas similitudes con el problema del logaritmo discreto discutido anteriormente, ya que se basa en la dificultad de encontrar factores.

La operación de multiplicación escalar en curvas elípticas permite definir el problema del logaritmo discreto en curva elíptica:

Dados los puntos $P, Q$ en una curva elíptica tales que $Q = nP$ , determinar $n$ .

Se sabe que este problema es intratable en computadoras clásicas para valores grandes de $n$ y constituye la base de la seguridad criptográfica.

Descripción matemática del ECDLP

La criptografía de curva elíptica se basa principalmente en el ECDLP formulado sobre ciertos campos finitos algebraicos. En 1999, el NIST recomendó diez campos finitos para su uso en ECC. Estos son:

Cinco campos primos $\mathbb {F} _{p}$ para primos $p$ de tamaño $\{192, 224, 256, 384, 521\}$ bits.
Cinco campos binarios $\mathbb {F} _{2^{n}}$ para $n \in \{163, 233, 283, 409, 571\}$ .

Con la configuración anterior, un criptosistema de clave asimétrica basado en ECC para el caso de campos primos puede especificarse de la siguiente manera:

Elige un $p$ de la lista de valores recomendados por el NIST para especificar $\mathbb {F} _{p}$ .
Selecciona los parámetros $a, b$ de la curva elíptica.
Elige un punto base $G$ que "genera" un subgrupo cíclico en la curva con orden $n$ ; es decir, el entero más pequeño tal que $nG = \mathbf{O}$ .
Calcula el cofactor $h = |E(\mathbb {F} _{p})|/n$ donde $|E(\mathbb {F} _{p})|$ es el número de puntos en la curva. $h$ es típicamente un entero pequeño.
Los parámetros de dominio $(p, a, b, G, n, h)$ permiten especificar claves asimétricas de la siguiente manera:
- La clave privada es un entero elegido aleatoriamente $d$ con tantos bits como el primo $p$ . Debe mantenerse en secreto.
- La clave pública es el resultado de "multiplicar" el punto base $G$ por la clave privada $d$ . Esto se denota típicamente como $Q = dG$ .

Recuperar $d$ es equivalente a resolver el ECDLP, que se supone intratable para valores grandes de $d$ . El ECDLP constituye así la base para los esquemas de intercambio de claves y firmas digitales, en analogía directa con los esquemas Diffie-Hellman y DSA definidos sobre $(\mathbb{Z}_p)^{\times}$ discutidos anteriormente.

Intercambio de claves con ECC

Uno de los principales usos de ECC es en el protocolo de intercambio de claves conocido como Diffie-Hellman en curva elíptica (ECDH). En ECDH, cada parte genera un par de claves privada-pública y luego intercambia las claves públicas. Cada parte utiliza entonces su propia clave privada y la clave pública de la otra parte para calcular un secreto compartido, que puede usarse como clave para el cifrado simétrico.

Si bien es relativamente fácil realizar la adición de puntos en una curva elíptica y derivar una clave pública a partir de una clave privada, es computacionalmente inviable revertir el proceso y derivar una clave privada a partir de una clave pública. Este comportamiento "unidireccional" proporciona la seguridad del intercambio de claves ECDH.

A continuación se ilustra un ejemplo de cómo se podría realizar un intercambio de claves ECDH usando Python y la biblioteca cryptography.

from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives import hashes

# Each party generates a private key
private_key1 = ec.generate_private_key(ec.SECP384R1())
private_key2 = ec.generate_private_key(ec.SECP384R1())

# They exchange public keys
public_key1 = private_key1.public_key()
public_key2 = private_key2.public_key()

# Each party uses their own private key and the other party's public key
# to derive the shared secret
shared_key1 = private_key1.exchange(ec.ECDH(), public_key2)
shared_key2 = private_key2.exchange(ec.ECDH(), public_key1)

# The shared secrets are the same
assert shared_key1 == shared_key2
print("Keys checked to be the same")

Firmas digitales con ECC

ECC también puede usarse para generar firmas digitales mediante el Algoritmo de Firma Digital en Curva Elíptica (ECDSA). En ECDSA, el firmante crea una firma usando su clave privada, y otras partes pueden verificar la firma usando la clave pública del firmante. Al igual que con ECDH, la seguridad de ECDSA se basa en el ECDLP. Es computacionalmente inviable que alguien falsifique una firma sin acceso a la clave privada del firmante.

El siguiente es un ejemplo de una transacción simple de firma y verificación usando ECDSA con Python y cryptography.

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import ec

# Generate a private key for use in the signature
private_key = ec.generate_private_key(ec.SECP384R1())

message = b"A message to be signed"

# Sign the message
signature = private_key.sign(message, ec.ECDSA(hashes.SHA256()))

# Anyone can verify the signature with the public key
public_key = private_key.public_key()

def check_ecdsa_signature(public_key, signature, message):
    try:
        public_key.verify(signature, message, ec.ECDSA(hashes.SHA256()))
        return True
    except InvalidSignature:
        return False

if check_ecdsa_signature(public_key, signature, message):
    print("The signature is valid.")
else:
    print("The signature is invalid.")

En el código anterior, si se modifica el mensaje después de haber sido firmado, la verificación fallará, lo que proporciona una garantía de autenticidad e integridad del mensaje.

Rompiendo ECDH y ECDSA

De manera análoga al problema del logaritmo discreto entero, el ECDLP resulta difícil en computadoras clásicas, pero tiene una solución eficiente en computadoras cuánticas, una vez más mediante el algoritmo de Shor. Te remitimos a la literatura reciente para una discusión relacionada con la generalización del algoritmo de Shor al caso del ECDLP.

Resumen

En esta lección, comenzamos analizando las principales características de la criptografía de clave asimétrica (AKC) y discutimos las consideraciones básicas de seguridad que sustentan los criptosistemas asimétricos. En particular, introdujimos las dos aplicaciones principales de la AKC — a saber, el intercambio de claves y las firmas digitales — ambas componentes esenciales de la comunicación moderna basada en internet.

Luego estudiamos el criptosistema RSA, que desde la década de 1970 ha demostrado ser de enorme valor para asegurar las comunicaciones digitales modernas, al permitir el intercambio de claves y las firmas digitales dentro de un marco simple y versátil. La seguridad criptográfica de RSA respecto a la computación clásica se basa en la dificultad de factorizar números enteros grandes y requiere tamaños de clave en el rango de 2048 bits para garantizar que los enteros utilizados en aplicaciones prácticas sean lo suficientemente grandes como para resistir la factorización.

Luego estudiamos el intercambio de claves Diffie-Hellman (DH) y el Algoritmo de Firma Digital (DSA). La seguridad de estos esquemas se basa en el problema del logaritmo discreto entero (DLP), cuya clave privada es computacionalmente difícil de extraer a partir de la clave pública, sin solución en tiempo polinomial en computadoras clásicas. El uso de claves aleatorias y únicas proporciona seguridad adicional frente a ataques. Tanto las variantes de campo finito entero como las de curva elíptica de los protocolos DH y DSA tienen actualmente un uso generalizado en muchos protocolos de comunicación digital modernos, como TLS, SSH, entre otros.

Finalmente, estudiamos la criptografía de curva elíptica. Con su eficiente tamaño de clave y sus sólidas propiedades de seguridad, actualmente representa una excelente opción para muchas aplicaciones criptográficas, desde el intercambio de claves hasta las firmas digitales.

Todos estos algoritmos están expuestos a ataques de algoritmos cuánticos, dado que se pueden desarrollar soluciones para resolver los problemas matemáticos que sirvieron de base en su diseño. Un ejemplo de ello es el algoritmo de Shor. Por lo tanto, deberán ser reemplazados por criptosistemas asimétricos cuántico-seguros que sean más resilientes a los ataques cuánticos y que, al mismo tiempo, mantengan su seguridad frente a algoritmos clásicos. Los problemas matemáticos en los que se basan pueden resolverse eficientemente mediante computadoras cuánticas, lo que hace necesario el desarrollo de criptosistemas asimétricos cuántico-seguros que puedan resistir ataques cuánticos sin comprometer la seguridad clásica.

Introducción a la criptografía de clave asimétrica​

Intercambio de claves con criptografía de clave asimétrica​

Intercambio de claves interactivo​

Intercambio de claves no interactivo​

Firmas digitales con criptografía de clave asimétrica​

Algoritmos dedicados de firma digital​

Esquemas de firma digital con criptosistemas genéricos​

Aplicaciones de la criptografía de clave asimétrica​

Seguridad de la criptografía de clave asimétrica​

Riesgos de seguridad para la criptografía de clave asimétrica​

RSA​

El algoritmo RSA​

Ilustración de RSA en Python​

Generación de claves RSA​

Intercambio de clave simétrica con RSA​

Ejemplo de intercambio de claves basado en relleno en Python​

Simulación de un mecanismo de encapsulación de claves con RSA en Python​

Firmas digitales con RSA​

Rompiendo RSA​

Computación clásica y RSA​

El algoritmo cuántico de Shor y RSA​

Ejemplo en Python que demuestra cómo romper el cifrado RSA​

Intercambio de claves Diffie-Hellman y el Algoritmo de Firma Digital​

El problema del logaritmo discreto​

Detalles matemáticos del problema del logaritmo discreto​

Intercambio de claves Diffie-Hellman​

Ilustración del protocolo Diffie-Hellman en Python​

Seguridad del intercambio de claves Diffie-Hellman​

El Algoritmo de Firma Digital (DSA)​

Ilustración del DSA en Python​

Seguridad del DSA​

Intercambio de claves autenticado con Diffie-Hellman y DSA​

Rompiendo Diffie-Hellman y DSA​

El algoritmo de Shor y el problema del logaritmo discreto​

Criptografía de curva elíptica​

Principios básicos de la criptografía de curva elíptica​

Problema del logaritmo discreto en curva elíptica​

Intercambio de claves con ECC​

Firmas digitales con ECC​

Rompiendo ECDH y ECDSA​

Resumen​

Introducción a la criptografía de clave asimétrica

Intercambio de claves con criptografía de clave asimétrica

Intercambio de claves interactivo

Intercambio de claves no interactivo

Firmas digitales con criptografía de clave asimétrica

Algoritmos dedicados de firma digital

Esquemas de firma digital con criptosistemas genéricos

Aplicaciones de la criptografía de clave asimétrica

Seguridad de la criptografía de clave asimétrica

Riesgos de seguridad para la criptografía de clave asimétrica

RSA

El algoritmo RSA

Ilustración de RSA en Python

Generación de claves RSA

Intercambio de clave simétrica con RSA

Ejemplo de intercambio de claves basado en relleno en Python

Simulación de un mecanismo de encapsulación de claves con RSA en Python

Firmas digitales con RSA

Rompiendo RSA

Computación clásica y RSA

El algoritmo cuántico de Shor y RSA

Ejemplo en Python que demuestra cómo romper el cifrado RSA

Intercambio de claves Diffie-Hellman y el Algoritmo de Firma Digital

El problema del logaritmo discreto

Detalles matemáticos del problema del logaritmo discreto

Intercambio de claves Diffie-Hellman

Ilustración del protocolo Diffie-Hellman en Python

Seguridad del intercambio de claves Diffie-Hellman

El Algoritmo de Firma Digital (DSA)

Ilustración del DSA en Python

Seguridad del DSA

Intercambio de claves autenticado con Diffie-Hellman y DSA

Rompiendo Diffie-Hellman y DSA

El algoritmo de Shor y el problema del logaritmo discreto

Criptografía de curva elíptica

Principios básicos de la criptografía de curva elíptica

Problema del logaritmo discreto en curva elíptica

Intercambio de claves con ECC

Firmas digitales con ECC

Rompiendo ECDH y ECDSA

Resumen