This is an example implementation of the RSA example on wikipedia: https://en.wikipedia.org/wiki/RSA_(algorithm)#A_worked_example.
# Choose two distinct prime numbers | |
p = 61 | |
q = 53 | |
# Compute n = pq | |
n = p * q | |
# Compute the totient of the product as φ(n) = (p − 1)(q − 1) | |
phi = (p - 1) * (q - 1) | |
# Choose any number 1 < e < 3120 that is coprime to 3120. Choosing a prime | |
# number for e leaves us only to check that e is not a divisor of 3120. | |
e = 17 | |
# This is the trickiest step. Compute d, the modular multiplicative inverse of e (mod φ(n)) | |
# Code from http://rosettacode.org/wiki/Modular_inverse#Python | |
def extended_gcd(aa, bb): | |
lastremainder, remainder = abs(aa), abs(bb) | |
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 aa < 0 else 1), lasty * (-1 if bb < 0 else 1) | |
def modinv(a, m): | |
g, x, y = extended_gcd(a, m) | |
if g != 1: | |
raise ValueError | |
return x % m | |
d = modinv(e, phi) | |
# The public key is (n = 3233, e = 17). Let's say we want to encrypt m. We | |
# do m^e mod n = 2790, which is c, our ciphertext | |
m = 65 | |
c = (m ** 17) % 3233 | |
# The private key is (n = 3233, d = 2753). To decrypt our ciphertext c, we | |
# do c^d mod n, which gives us back m: | |
m_decrypted = (c ** d) % n | |
print(m == m_decrypted) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment