Cześć. Próbuję sobie robić po kolei zadania z wielkiej listy wyzwań i mam do napisania program szyfrujący / deszyfrujący. Wybrałem sobie algorytm RSA. Kod napisałem samodzielnie, oczywiście patrząc na algorytmy w Internecie. Korzystałem z tych stron:
algorytm RSA
rozszerzony algorytm Euklidesa
Widzę, że zaszyfrowana wiadomość (encrypted_message) to w moim przypadku po prostu znaki zamienione na kody ASCII. Dlaczego szyfrowanie nie działa? Błąd może być możliwe w generate_keys(), ale co robię nie tak? A jeśli nie ta funkcja, to może w rsa_encryption()? Oto kod:
#EDIT: znalazłem jedną maleńką rzecz. Wstawiam poprawiony kod. Zdaje się, że wiadomość można zaszyfrować poprawnie. Ale wiadomość nadal się nie deszyfruje poprawnie
# ----------------------
# Copyright (c) Deloryn
# ----------------------
from math import pow
# for this task I just take two small prime numbers - p = 11 and q = 13
def generate_keys(p, q):
euler_function = (p - 1) * (q - 1)
n = p * q # n is a module
e = 1
d = 1
for i in range(2, n):
if lcd(i, euler_function) == 1 and i % 2 != 0:
e = i
break
j = 1
while True:
solution = extended_euclidean_algorithm(j,e)
if solution != "No solution":
d = solution
break
j += 1
# now (e, n) is our public key and (d, n) is our private key
return [e, n, d]
def rsa_encryption(message, e, n):
encrypted_message = ""
for letter in message:
t = ord(letter)
c = int((pow(t, e)) % n)
encrypted_message += (str(c) + " ")
return encrypted_message
def rsa_decryption(encrypted_message, d, n):
encrypted_sign = ""
decrypted_message = ""
for character in encrypted_message:
if character != " ":
encrypted_sign += character
else:
t = int((pow(int(encrypted_sign), d)) % n) # t is a decrypted sign
encrypted_sign = ""
decrypted_message += chr(t)
return decrypted_message
def lcd(a,b): # Largest Common Divisor
while b != 0:
c = a % b
a = b
b = c
return a
def extended_euclidean_algorithm(a, b):
u = 1
w = a
x = 0
z = b
while w != 0:
if w < z:
pom = u
u = x
x = pom
pom = w
w = z
z = pom
q = int(w / z)
u = u - q * x
w = w - q * z
if z != 1:
return "No solution"
if x < 0:
x += b
return x
message = "I like tea"
keys = generate_keys(11, 13)
encrypted_message = rsa_encryption(message, keys[0], keys[1])
decrypted_message = rsa_decryption(encrypted_message, keys[2], keys[1])
print("A message before RSA encryption: " + message)
print("A message after RSA encryption: " + encrypted_message)
print("A message after RSA decryption: " + decrypted_message)