Objetivos de Aprendizaje

• Comprender los fundamentos teóricos del algoritmo cuántico de Shor
• Implementar una simulación simplificada del algoritmo
• Analizar cómo este algoritmo compromete la seguridad de RSA
• Evaluar las implicaciones para la criptografía actual

Requisitos Previos

• Conocimientos básicos de criptografía de clave pública (RSA)
• Familiaridad con conceptos matemáticos: teoría de números, aritmética modular
• Python 3.8 o superior instalado
• Bibliotecas requeridas: numpy, matplotlib, qiskit (opcional para la parte avanzada)

Introducción Teórica

El algoritmo de Shor, desarrollado por Peter Shor en 1994, es un algoritmo cuántico que puede factorizar números enteros en tiempo polinómico. Su importancia radica en que puede romper eficientemente el cifrado RSA, que basa su seguridad en la dificultad de factorizar números grandes.

El algoritmo consta de dos partes principales:

1. Reducción del problema de factorización a encontrar el período de una función: Transformar el problema de factorizar N en encontrar el período de la función f(x) = a^x mod N, donde a es un número coprimo con N.
2. Encontrar el período utilizando la transformada cuántica de Fourier: Utilizar un algoritmo cuántico para encontrar el período de la función anterior de manera eficiente.

Una vez encontrado el período r, podemos calcular factores de N con alta probabilidad utilizando el máximo común divisor (MCD) de N y a^(r/2) ± 1.

Parte 1: Implementación Clásica Simplificada

1.1 Configuración del Entorno

Crea un nuevo archivo Python llamado shor_simulation.py e importa las bibliotecas necesarias:

import numpy as np
import math
import random
import matplotlib.pyplot as plt
from fractions import Fraction

1.2 Implementación de Funciones Auxiliares

Primero, implementaremos algunas funciones auxiliares necesarias:

# Calcular el máximo común divisor (MCD)
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

# Exponenciación modular rápida
def mod_exp(base, exponent, modulus):
    if modulus == 1:
        return 0
    result = 1
    base = base % modulus
    while exponent > 0:
        if exponent % 2 == 1:
            result = (result * base) % modulus
        exponent = exponent >> 1
        base = (base * base) % modulus
    return result

# Encontrar un número aleatorio coprimo con n
def find_coprime(n):
    a = random.randint(2, n-1)
    while gcd(a, n) != 1:
        a = random.randint(2, n-1)
    return a

# Expansión de fracción continua para aproximar fracciones
def continued_fraction_expansion(x, y, max_denominator):
    fractions = []
    a = Fraction(x, y).limit_denominator(max_denominator)
    fractions.append(a)
    
    # Generar convergentes intermedios
    n, d = a.numerator, a.denominator
    for i in range(1, d):
        if i * a.denominator <= max_denominator:
            fractions.append(Fraction(round(i * a.numerator / a.denominator), i))
    
    return fractions

1.3 Implementación del Algoritmo de Shor Clásico

Ahora implementaremos una versión simplificada del algoritmo de Shor:

def find_period_classically(a, N):
    """
    Encuentra el período de f(x) = a^x mod N de manera clásica (ineficiente).
    En un ordenador cuántico real, esta parte sería mucho más eficiente.
    """
    x = 1
    for r in range(1, N):
        x = (x * a) % N
        if x == 1:
            return r
    return None

def shor_algorithm_classical(N, max_attempts=5):
    """
    Implementación clásica simplificada del algoritmo de Shor
    """
    if N % 2 == 0:
        return 2, N // 2
    
    for _ in range(max_attempts):
        # Paso 1: Elegir un número aleatorio a < N
        a = find_coprime(N)
        print(f"Intentando con a = {a}")
        
        # Paso 2: Encontrar el período r (en un ordenador cuántico, esto sería mucho más rápido)
        r = find_period_classically(a, N)
        
        if r is None:
            print("No se encontró período. Intentando con otro valor de a.")
            continue
            
        print(f"Período encontrado: r = {r}")
        
        # Paso 3: Verificar condiciones
        if r % 2 != 0:
            print("El período es impar. Intentando con otro valor de a.")
            continue
            
        x = mod_exp(a, r // 2, N)
        if x == N - 1:
            print("a^(r/2) ≡ -1 (mod N). Intentando con otro valor de a.")
            continue
        
        # Paso 4: Calcular factores
        factor1 = gcd(x - 1, N)
        factor2 = gcd(x + 1, N)
        
        if factor1 > 1 and factor1 < N:
            return factor1, N // factor1
        if factor2 > 1 and factor2 < N:
            return factor2, N // factor2
    
    return None, None

1.4 Función Principal y Visualización

Finalmente, implementaremos la función principal y algunas visualizaciones:

def main():
    # Número a factorizar (pequeño para esta simulación)
    N = 15  # = 3 × 5
    
    print(f"Intentando factorizar N = {N} usando el algoritmo de Shor (simulación clásica)")
    
    # Ejecutar el algoritmo
    factor1, factor2 = shor_algorithm_classical(N)
    
    if factor1 is not None:
        print(f"¡Factorización exitosa! {N} = {factor1} × {factor2}")
        
        # Visualización
        plt.figure(figsize=(10, 6))
        
        # Gráfico de la función f(x) = a^x mod N
        a = find_coprime(N)
        x_values = list(range(20))
        y_values = [mod_exp(a, x, N) for x in x_values]
        
        plt.subplot(1, 2, 1)
        plt.plot(x_values, y_values, 'o-')
        plt.title(f"Función f(x) = {a}^x mod {N}")
        plt.xlabel("x")
        plt.ylabel(f"{a}^x mod {N}")
        plt.grid(True)
        
        # Histograma de valores
        plt.subplot(1, 2, 2)
        plt.hist(y_values, bins=range(min(y_values), max(y_values) + 2), alpha=0.7)
        plt.title(f"Distribución de valores de {a}^x mod {N}")
        plt.xlabel("Valor")
        plt.ylabel("Frecuencia")
        plt.grid(True)
        
        plt.tight_layout()
        plt.savefig('shor_visualization.png')
        plt.show()
    else:
        print("No se pudo factorizar N con los intentos realizados.")

if __name__ == "__main__":
    main()

Parte 2: Análisis de Seguridad de RSA

2.1 Implementación Simplificada de RSA

Ahora implementaremos una versión simplificada de RSA para demostrar su vulnerabilidad:

# Crear un nuevo archivo rsa_simulation.py
import random
from math import gcd

def is_prime(n, k=5):
    """Test de primalidad de Miller-Rabin simplificado"""
    if n <= 1 or n == 4:
        return False
    if n <= 3:
        return True
    
    # Implementación simplificada para números pequeños
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

def generate_prime(bits):
    """Genera un número primo de aproximadamente 'bits' bits"""
    # Para esta simulación, usamos primos pequeños
    primes = [p for p in range(10, 100) if is_prime(p)]
    return random.choice(primes)

def mod_inverse(e, phi):
    """Calcula el inverso modular de e módulo phi"""
    def extended_gcd(a, b):
        if a == 0:
            return b, 0, 1
        else:
            gcd, x, y = extended_gcd(b % a, a)
            return gcd, y - (b // a) * x, x
    
    g, x, y = extended_gcd(e, phi)
    if g != 1:
        raise Exception('El inverso modular no existe')
    else:
        return x % phi

def generate_rsa_keys():
    """Genera un par de claves RSA (simplificado)"""
    # Generar dos primos distintos
    p = generate_prime(8)
    q = generate_prime(8)
    while p == q:
        q = generate_prime(8)
    
    n = p * q
    phi = (p - 1) * (q - 1)
    
    # Elegir e coprimo con phi
    e = random.randint(3, phi - 1)
    while gcd(e, phi) != 1:
        e = random.randint(3, phi - 1)
    
    # Calcular d (inverso modular de e módulo phi)
    d = mod_inverse(e, phi)
    
    return (e, n), (d, n), p, q

def rsa_encrypt(message, public_key):
    """Cifra un mensaje usando RSA"""
    e, n = public_key
    return pow(message, e, n)

def rsa_decrypt(ciphertext, private_key):
    """Descifra un mensaje usando RSA"""
    d, n = private_key
    return pow(ciphertext, d, n)

def main_rsa():
    # Generar claves
    public_key, private_key, p, q = generate_rsa_keys()
    e, n = public_key
    d, _ = private_key
    
    print(f"Generadas claves RSA con n = {n} = {p} × {q}")
    print(f"Clave pública: (e={e}, n={n})")
    print(f"Clave privada: (d={d}, n={n})")
    
    # Cifrar y descifrar un mensaje
    message = random.randint(2, n-1)
    print(f"Mensaje original: {message}")
    
    ciphertext = rsa_encrypt(message, public_key)
    print(f"Mensaje cifrado: {ciphertext}")
    
    decrypted = rsa_decrypt(ciphertext, private_key)
    print(f"Mensaje descifrado: {decrypted}")
    
    # Intentar romper RSA usando el algoritmo de Shor
    print("\nIntentando romper RSA usando el algoritmo de Shor...")
    from shor_simulation import shor_algorithm_classical
    
    factor1, factor2 = shor_algorithm_classical(n)
    
    if factor1 is not None:
        print(f"¡RSA comprometido! Se han encontrado los factores: {factor1} y {factor2}")
        
        # Reconstruir la clave privada
        phi_recovered = (factor1 - 1) * (factor2 - 1)
        d_recovered = mod_inverse(e, phi_recovered)
        print(f"Clave privada recuperada: (d={d_recovered}, n={n})")
        
        # Verificar descifrando el mensaje
        decrypted_recovered = pow(ciphertext, d_recovered, n)
        print(f"Mensaje descifrado con la clave recuperada: {decrypted_recovered}")
        print(f"¿Coincide con el mensaje original? {'Sí' if decrypted_recovered == message else 'No'}")
    else:
        print("No se pudo factorizar n con los intentos realizados.")

if __name__ == "__main__":
    main_rsa()

Parte 3: Ejercicios y Preguntas de Reflexión

3.1 Ejercicios

1. Modifica el código para factorizar otros números compuestos pequeños (por ejemplo, 21, 33, 35).
2. Implementa una función que calcule el tiempo que tardaría un ordenador clásico en factorizar números de diferentes tamaños usando el algoritmo de fuerza bruta.
3. Compara la complejidad teórica del algoritmo de Shor (O(log³ N)) con la del mejor algoritmo clásico conocido (aproximadamente O(e^(log N)^(1/3) * (log log N)^(2/3))).
4. Modifica el código RSA para usar números primos más grandes (dentro de lo razonable para una simulación) y analiza cómo afecta esto al tiempo de ejecución del algoritmo de Shor clásico.

3.2 Preguntas de Reflexión

1. ¿Por qué el algoritmo de Shor representa una amenaza tan significativa para RSA?
2. ¿Qué tamaño de clave RSA se considera seguro actualmente contra ordenadores clásicos? ¿Y contra ordenadores cuánticos potenciales?
3. ¿Qué otros algoritmos criptográficos, además de RSA, son vulnerables al algoritmo de Shor?
4. ¿Cuáles son las limitaciones actuales para implementar el algoritmo de Shor en ordenadores cuánticos reales?
5. ¿Qué estrategias de migración recomendarías a una organización que actualmente utiliza RSA para proteger información sensible a largo plazo?

Parte 4: Extensión (Opcional) - Simulación Cuántica

Si tienes experiencia con bibliotecas de computación cuántica como Qiskit, puedes intentar implementar una simulación más realista del algoritmo de Shor:

# Requiere: pip install qiskit
from qiskit import QuantumCircuit, Aer, execute
from qiskit.visualization import plot_histogram
import numpy as np
import matplotlib.pyplot as plt

# Esta es una implementación muy simplificada y parcial
# Para una implementación completa, consulta la documentación de Qiskit

def qft_rotations(circuit, n):
    """Rotaciones QFT sin swaps"""
    if n == 0:
        return circuit
    n -= 1
    circuit.h(n)
    for qubit in range(n):
        circuit.cp(np.pi/2**(n-qubit), qubit, n)
    qft_rotations(circuit, n)

def qft(circuit, n):
    """Transformada cuántica de Fourier"""
    qft_rotations(circuit, n)
    # Swaps
    for qubit in range(n//2):
        circuit.swap(qubit, n-qubit-1)
    return circuit

def inverse_qft(circuit, n):
    """QFT inversa"""
    # Swaps
    for qubit in range(n//2):
        circuit.swap(qubit, n-qubit-1)
    # Rotaciones inversas
    for j in range(n):
        for m in range(j):
            circuit.cp(-np.pi/2**(j-m), m, j)
        circuit.h(j)
    return circuit

def shor_period_finding_circuit(a, N, n_count, n_target):
    """Circuito para encontrar el período en el algoritmo de Shor"""
    # Crear circuito
    circuit = QuantumCircuit(n_count + n_target, n_count)
    
    # Inicializar registros
    for q in range(n_count):
        circuit.h(q)
    circuit.x(n_count)
    
    # Aplicar operaciones U controladas
    # (Esta es una simplificación extrema)
    for q in range(n_count):
        # Aplicar a^(2^q) mod N controlado por q
        # En una implementación real, esto sería mucho más complejo
        circuit.cp(2*np.pi*a**(2**q) % N / N, q, n_count)
    
    # Aplicar QFT inversa
    inverse_qft(circuit, n_count)
    
    # Medir
    circuit.measure(range(n_count), range(n_count))
    
    return circuit

def simulate_shor_quantum(a, N):
    """Simula la parte cuántica del algoritmo de Shor"""
    # Parámetros
    n_count = 8  # Número de qubits para el registro de conteo
    n_target = 4  # Número de qubits para el registro objetivo
    
    # Crear circuito
    circuit = shor_period_finding_circuit(a, N, n_count, n_target)
    
    # Simular
    simulator = Aer.get_backend('qasm_simulator')
    result = execute(circuit, simulator, shots=1024).result()
    counts = result.get_counts()
    
    # Visualizar
    plot_histogram(counts)
    plt.title(f"Distribución de mediciones para a={a}, N={N}")
    plt.savefig('shor_quantum_simulation.png')
    plt.show()
    
    return counts

# Ejemplo de uso
# simulate_shor_quantum(7, 15)

Esta implementación es muy simplificada y no funcionará correctamente para el algoritmo de Shor completo, pero proporciona una idea de cómo se podría abordar usando Qiskit.

Entregables

Al finalizar esta práctica, deberás entregar:

1. Código fuente de las implementaciones (shor_simulation.py y rsa_simulation.py)
2. Capturas de pantalla o gráficos generados durante la ejecución
3. Un informe breve (máximo 2 páginas) que incluya:
   • Resultados obtenidos en las factorizaciones
   • Respuestas a las preguntas de reflexión
   • Análisis de la vulnerabilidad de RSA frente al algoritmo de Shor
   • Conclusiones sobre las implicaciones para la seguridad criptográfica actual

Recursos Adicionales

• Artículo original de Peter Shor
• Tutorial de Qiskit sobre el algoritmo de Shor
• Wikipedia: RSA Cryptosystem
• Wikipedia: Algoritmo de Shor