Skip to content

Instantly share code, notes, and snippets.

@jeffnuss
Last active January 4, 2016 21:39
Show Gist options
  • Save jeffnuss/8682623 to your computer and use it in GitHub Desktop.
Save jeffnuss/8682623 to your computer and use it in GitHub Desktop.
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