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.
