Skip to content

Instantly share code, notes, and snippets.

Last active July 14, 2023 17:35
Show Gist options
  • Save juanplopes/6908681 to your computer and use it in GitHub Desktop.
Save juanplopes/6908681 to your computer and use it in GitHub Desktop.
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
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.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment