<jupyter_start><jupyter_text>Algoritmos de Euclides Antes de empezar necesitaremos un sistema para cálculo del máximo común divisor (mcd en castellano, gcd en inglés) de dos números, y el inverso de un número en un anillo cíclico. Ambas cosas se conocen desde hace tiempo: son dos "algoritmos de Euclides" Algoritmo de Euclides para determinar el máximo común divisor (gcd) de dos enteros a yb<jupyter_code>def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

print('gcd(2, 3) = ', gcd(2, 3))
print('gcd(20, 30) = ', gcd(20, 30))
print('gcd(50720, 48184) = ', gcd(50720, 48184))<jupyter_output><empty_output><jupyter_text>Algoritmo generalizado de Euclides para encontrar el inverso multiplicativos de un número en un anillo cíclico $\mathbb{Z}_{\phi}$<jupyter_code>def multiplicative_inverse(e, phi):
    d = 0
    x1 = 0
    x2 = 1
    y1 = 1
    temp_phi = phi
    
    while e > 0:
        temp1 = temp_phi // e
        temp2 = temp_phi - temp1 * e
        temp_phi = e
        e = temp2
        
        x = x2 - temp1 * x1
        y = d - temp1 * y1
        
        x2 = x1
        x1 = x
        d = y1
        y1 = y

    if temp_phi == 1:
        return d + phi
    # no inverse: return None
    return None

print('3^{-1} mod 10 = ', multiplicative_inverse(3, 10))
print('2^{-1} mod 10 = ', multiplicative_inverse(2, 10))
print('25^{-1} mod 119 = ', multiplicative_inverse(25, 119))
def is_prime(num):
    if num == 2:
        return True
    if num < 2 or num % 2 == 0:
        return False
    for n in range(3, int(num**0.5)+2, 2):
        if num % n == 0:
            return False
    return True

for i in [2, 5, 19, 25, 222, 314, 317]:
    print(f'{i}: ', is_prime(i))<jupyter_output><empty_output><jupyter_text>RSARSA son unas pocas funciones sencillas:- Generación de claves- Cifrado y descifrado son iguales (y simplemente es una potencia)<jupyter_code>def generate_keypair(p, q):
    if not (is_prime(p) and is_prime(q)):
        raise ValueError('Both numbers must be prime.')
    elif p == q:
        raise ValueError('p and q cannot be equal')
    #n = pq
    n = p * q

    #Phi is the totient of n
    phi = (p - 1) * (q - 1)

    # Choose an integer e such that e and phi(n) are coprime
    e = random.randrange(1, phi)

    # Use Euclid's Algorithm to verify that e and phi(n) are coprime
    g = gcd(e, phi)
    while g != 1:
        e = random.randrange(1, phi)
        g = gcd(e, phi)

    #Use Extended Euclid's Algorithm to generate the private key
    d = multiplicative_inverse(e, phi)
    
    #Return public and private keypair
    #Public key is (e, n) and private key is (d, n)
    return ((e, n), (d, n))

def encrypt(pk, number):
    # Unpack the key into it's components
    key, n = pk
    return (number ** key) % n

decrypt = encrypt
pk, sk = generate_keypair(17, 23)
print(f'Publickey (e, n): {pk} Private-key (d, n): {sk}')<jupyter_output><empty_output><jupyter_text>Fíjate: si generamos otro par de claves, aunque usemos los mismos primos, obtendremos unas claves diferentes. Eso es porque el parámetro $e$ se escoge al azar<jupyter_code>pk, sk = generate_keypair(17, 23)
print(f'Publickey: {pk} Private-key: {sk}')<jupyter_output><empty_output><jupyter_text>Vamos a intentar cifrar un texto sencillo:<jupyter_code>print(encrypt(pk, 'hola'))<jupyter_output><empty_output><jupyter_text>No podemos: RSA solo puede cifrar enteros. Una posibilidad es codificar el mensaje como un conjunto de enteros<jupyter_code>print([encrypt(pk, ord(c)) for c in 'hola'])<jupyter_output><empty_output><jupyter_text>¿Qué pasa si intentamos cifrar varias veces lo mismo?<jupyter_code>print([encrypt(pk, ord(c)) for c in 'aaaa'])<jupyter_output><empty_output><jupyter_text>Pocas veces querremos eso. RSA debe usarse siguiendo recomendaciones como PKCS1  (semi) HomorfismoRSA es semihomomórfico con la multiplicación: se pueden hacer cálculos con los números cifrados, aunque no sepas lo que son ni qué resultado tienes. Al descifrar, el resultado es correcto.Por ejemplo, vamos a multiplicar los mensajes cifrados c1 y c2, que son los cifrados de 5 y 2 respectivamente<jupyter_code>m1 = 5
c1 = encrypt(pk, m1)
print(f'encrypt(pk, {m1}) = {c1}')
print(f'decrypt(sk, {c1}) = {decrypt(sk, c1)}')

m2 = 2
c2 = encrypt(pk, m2)
print(f'encrypt(pk, {m2}) = {c2}')
print(f'decrypt(sk, {c2}) = {decrypt(sk, c2)}')
cm = c1 * c2
print(f"c1 = {c1}; c2 = {c2}; cm = {cm}")<jupyter_output><empty_output><jupyter_text>Un atacante no sabe cuánto vale c1 ni c2, ni sabe qué valor tiene cm, pero sabe que, sea lo que sea, ha multiplicado c1 y c2 y cuando se descifre el resultado va a ser correcto<jupyter_code>print(f'decrypt(sk, c1 * c2) = m1 * m2 = {m1} * {m2} = {decrypt(sk, cm)}')<jupyter_output><empty_output><jupyter_text>Según la utilidad, el semihomorfismo puede ser útil o no:- Sistemas PET (private enhanced technologies) necesitas calcular sin descifrar. Por ejemplo, voto electrónico- Pero en general no querremos que un atacante pueda multiplicar una orden de pago por otro número y que el resultado sea válido: recomendaciones PKCS1  PyCryptoDomeLa función de arriba solo sirve para ver cómo funciona RSA a alto nivel. Veamos ahora cómo de grandes son los números involucrados en estos cifrados. Ojo: ¡mide cuánto tiempo necesitamos para generar las claves!<jupyter_code># Clave de 2048 bits
from Crypto.PublicKey import RSA
key2048 = RSA.generate(2048)
key2048
key4096 = RSA.generate(4096)
key4096<jupyter_output><empty_output><jupyter_text>EjerciciosHemos visto cómo crear claves con PyCryptoDrome, pero no cómo usarlo para cifrar o descifrar.Recuerda de las transparencias que no es recomendable utilizar RSA "de forma pura", es decir, sin tener en cuenta muchas consideraciones sobre padding, conversiones, longitudes... que se recogen en [PKCS1](https://en.wikipedia.org/wiki/PKCS_1). De hecho, PyCryptoDome no nos va a dejar utilizar el cifrado y descifrado directamente.Observa que la línea siguiente da un error, avisando que uses el módulo  `Crypto.Cipher.PKCS1_OAEP`<jupyter_code>key2048.encrypt(b'hola', None)<jupyter_output><empty_output><jupyter_text>**Aunque no se debe**, vamos a utilizar la función `_encrypt()`, que no está documentada pero la puedes encontrar en el código: https://github.com/Legrandin/pycryptodome/blob/master/lib/Crypto/PublicKey/RSA.pyL147<jupyter_code>c = key2048._encrypt(15)
d = key2048._decrypt(c)
print(f"Cifrado: {c}")
print(f"Descifrado: {d}")<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.106656346749226, 'fraction_numerical': 0.03173374613003096, 'mean_word_length': 4.059514487079092, 'pattern_counts': {'":': 0, '<': 50, '<?xml version=': 0, '>': 50, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '12', 'dir': 'jupyter-structured-clean-dedup', 'id': '158139', 'license': 'CC0-1.0', 'n_tokens_mistral': 2558, 'n_tokens_neox': 2414, 'n_words': 775, 'path': 'ejercicios/05/.ipynb_checkpoints/RSA-checkpoint.ipynb', 'repo_name': 'Juanvvc/crypto', 'size': '6460'}