Criptografia RSA

[Adriel Filipe]

Boa noite à todos do fórum. Criei um programa em python que segue a lógica do RSA (gera dois primos grandes, n=multiplicação desses primos, pego um ''e'' tal que mdc(e,phi(n))=1, etc...) .

Quando escolho números pequenos (coloquei n=21,p=3,q=7,phi(n)=12,e=5,d=5 por exemplo) eles pegam normalmente... Contudo, quando começo a gerar os números, não consigo descriptografar! Alguém poderia por favor me ajudar?

segue o código:

import random
from random import getrandbits
def criptografa(m,u,n):
    m1=pow(m,u,n)
    return m1
def euclides_extendido(a, b):
    lastremainder, remainder = abs(a), abs(b)
    x, lastx, y, lasty = 0, 1, 1, 0
    while remainder:
        lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder)
        x, lastx = lastx - quotient * x, x
        y, lasty = lasty - quotient * y, y
    return lastremainder, lastx * (-1 if a < 0 else 1), lasty * (-1 if b < 0 else 1)

def modinv(a, m):
    g, x, y = euclides_extendido(a, m)
    if g != 1:
        raise ValueError
    return x % m
def phi(p,q):
    aux = (p - 1) * (q - 1)
    return aux
def mdc(num1, num2):
    resto = None
    while resto is not 0:
        resto = num1 % num2
        num1  = num2
        num2  = resto

    return num1
small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]

def miller_rabbin(n, k):
    if n < 2: return False
    for p in small_primes:
        if n < p * p: return True
        if n % p == 0: return False
    r, s = 0, n - 1
    while s % 2 == 0:
        r += 1
        s //= 2
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, s, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

p = getrandbits ( 512 )
q = getrandbits ( 512 )
while not (miller_rabbin(p,100)==True or miller_rabbin(q,100)==True):
    p = getrandbits(512)
    q = getrandbits(512)
phi_n=phi(p,q)
n=p*q
e=2
while not (mdc(e,phi_n)==1):
    e = random.randint(2, phi_n)
d=modinv(e,phi_n)
m=55
print(m)
m1=criptografa(m,e,n)
m=criptografa(m1,d,n)
print(e)
print((d*e)%phi_n)
print(d)
print(n)
print(m1)
print(m)

Desde já, grato.