Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# juanplopes/rsa.py

Last active Oct 19, 2019
RSA by example
 from random import randint #----Step 1 # First, choose two random primes. # In real world, they should be really big primes (hundreds of digits). p, q = 41, 47 #----Step 2 # From them we have n=p*q and phi(n)=(p-1)*(q-1). # # phi(n) is Euler's totient function. It counts how many numbers <= n that have # no common factors with n (coprimes). For prime numbers, phi(p) = p-1. n = p*q phi = (p-1)*(q-1) #----Step 3 # Choose some random number "e" between 1 and phi(n) exclusive. # "e" must be coprime with phi(n). # # You can check if e and phi(n) are coprimes using GCD(e, phi(n)) == 1. def gcd(a, b): return gcd(b, a%b) if b else a e = 42 while gcd(e, phi) != 1: e = randint(2, phi-1) #----Step 4 # Find d, such that (d*e)%phi == 1. That is, d*e - k*phi == 1. # You can solve this equation by using Euclid's algorithm. # # euclid(a, b) finds smallest positive y such that a*x + b*y == 1 def euclid(a,b): return (1-a*euclid(b, a%b))/b%a if b else 0 d = euclid(phi, e) #----Step 5 # Having the public (n,e) and private (n,d) keys, you can define: # encrypt(x) = x**e % n # decrypt(x) = x**d % n print 'Public key:', (n,e) print 'Private key:', (n,d) message = 'some secret message' plain = [ord(x) for x in message] encrypted = [pow(x, e, n) for x in plain] plain_again = [pow(x, d, n) for x in encrypted] print 'Plain:', plain print 'Encrypted:', encrypted print 'Plain:', plain_again """ Epilogue RSA is based on the fact that multiplying p by q is easy, but factoring n is hard. The relation between the public (e) and the private (d) exponents is given by phi(n) that can only be calculated if you know p and q. The correctness of the algorithm can be proven by Fermat's little theorem. It states, among other things, that if e*d % phi(n) == 1 then a**(e*d) % n == a What we do in RSA is exactly this: a**e%n to encrypt and a**d%n to decrypt. Plain RSA as explained here is not actually secure. It should be combined with some padding scheme to be made useful in real software. """
to join this conversation on GitHub. Already have an account? Sign in to comment