Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# jeffnuss/prime-factorization-example.py

Last active Jan 4, 2016
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)
to join this conversation on GitHub. Already have an account? Sign in to comment