RSA number encryption/decryption in Python.

rsa.py

# wymagania: pprint
import random
from pprint import pprint


# algorytm euklidesa
def gcd(a, b):
    if (b == 0):
        return a
    return gcd(b, a % b)

# rozszerzony algorytm euklidesa
def xgcd(a, b):
    x, old_x = 0, 1
    y, old_y = 1, 0

    while (b != 0):
        quotient = a // b
        a, b = b, a - quotient * b
        old_x, x = x, old_x - quotient * x
        old_y, y = y, old_y - quotient * y

    return a, old_x, old_y

p, q = 7, 797

Ψ = (p - 1) * (q - 1)
n = p * q

while True:
    e = random.randrange(2, Ψ)
    if (gcd(e, Ψ) == 1):
        break

gcd, x, y = xgcd(e, Ψ)

# d musi byc > 0
d = x
if d < 0:
    d += Ψ

t = 2137

print("Liczby pierwsze wykorzystane:")
pprint((p, q))
print("Klucz publiczny:")
pprint((e, n))
print("Klucz prywatny:")
pprint((d, n))

print("Liczba do zaszyfrowania:")
print(t)

c = (t ** e) % n
print("Liczba zaszyfrowana:")
print(c)

x = (c ** d) % n
print("Liczba odszyfrowana:")
print(x)

# założenia:
assert x == t
assert t < n
assert c < n