How does RSA work? It comes down to understand a few things about prime numbers. So first, remind yourself when a number is prime. Namely, when nothing divides it evenly, or in other words when the remainder is not zero, except for 1 and the number itself.

Next, find some prime numbers, say here.

In [99]:
prime1= 512927357
prime2= 674506081

Next, compute the product. Easy peazy lemon squeezy.

In [100]:
N = prime1*prime2

Note that N has approximately twice as many digits!

In [101]:
N
Out[101]:
345972621407757917

Next, try to factor N, pretending you no longer know your primes.

How would you do that? Possibly: write a for loop looking for factors

First play with the "remainder" function in python.

In [102]:
print 3%12
print 12%3
print 15%4
print 4%15
3
0
3
4

Next, use that to look for factors less than n and larger than 1. This is a stupid algorithm but it works.

In [103]:
def find_a_factor(n):
    for i in range(2, n):
        if n%i == 0:
            return n, i
    return n, "Prime!"
print find_a_factor(100)
print find_a_factor(101)
(100, 2)
(101, 'Prime!')

How efficient is find_a_factor? Convince yourself it is maximally inefficient for primes, and try a few primes of increasing size.

In [104]:
find_a_factor(859093)
Out[104]:
(859093, 'Prime!')
In [105]:
find_a_factor(2814841)
Out[105]:
(2814841, 'Prime!')
In [106]:
find_a_factor(15485863)
Out[106]:
(15485863, 'Prime!')

We can estimate that it would take a seriously long time to find a factor in N. And yes, there are better ways to do it, but they are still incredibly slow. And the real RSA uses 100-digit prime numbers.

So what we have is something that's easy to do but very difficult to undo.

How do we use this to our advantage?

To explain this we need to explain a little bit about arithmetic mod N.

  1. Forms a group under addition
  2. Forms a group under multiplication if you remove stuff coprime to N.
  3. By definition you have Φ(N) elements in that group.
  4. But you secretly know that Φ(N)=(prime1 - 1) ∗ (prime2 - 1)
  5. Every element in the multiplicative group has the property that if you take it to the power Φ(N), you get 1 modulo N.
  6. If you turn a secret message into a number, and then bring that number to some power d modulo N, then you can "go the rest of the way" to get back to 1, and then go once further to get back to the coded message, but only if you know what Φ(N) is.
  7. There's actually a minor restriction on what d can be but don't worry about that because there are lots of choices for d. Namely, make sure d is coprime to Φ(N).
  8. Once you've chosen d, find also f so that f times d is 1 modulo Φ(N).
  9. Then if you first take something to the dth power, then to the fth power, you've altogether taken it to the power which is something 1 modulo Φ(N), which is the original message again, which is magic.

Here's what you make public.

N and d.

Here's what you make people do.

Take their message, which is a number, and take it to the dth power modulo N. Make sure you know this easy.

Here's what you can do after you get their encrypted message.

Take their message to the f'th power to get it back to their message. Again, super easy.

In [107]:
Phi_N = (prime1 - 1)* (prime2-1)
print Phi_N
print N
345972620220324480
345972621407757917

Choose a d and make sure it's prime to Φ(N).

In [108]:
d = 17
print Phi_N%d
11

Now find the multiplicative inverse of d modulo Φ(N). This amounts to finding an a and a b so that:

a ∗ d + b ∗ Φ(N) = 1.

First you write

Φ(N) = q1 ∗ d + r

In [109]:
q1 = Phi_N/d
r = Phi_N%d
print q1, r
20351330601195557 11

Φ(N) = 20351330601195557 ∗ 17 + 11

Next do the division algorithm on d and r and so on:

d = 17 = 1 ∗ 11 + 6

11 = 1 ∗ 6 + 5

6 = 1 ∗ 5 + 1

Now rewrite those equations slightly:

1 = 6 - 1 ∗ 5

5 = 11 - 1 ∗ 6

6 = d - 1 ∗ 11

11 = Φ(N) - 20351330601195557 ∗ d

And now go backwards from 1:

1 = 6 - (11 - 6) = 2 ∗ 6 - 11

= 2 ∗ (d - 11) - 11 = 2 ∗ d - 3 ∗ 11

= 2 ∗ d - 3 ∗ (Φ(N) - 20351330601195557 ∗ d)

= - 3 ∗ Φ(N) + (3 ∗ 20351330601195557 + 2) ∗ d

So 3 ∗ 20351330601195557 + 2 is the multiplicative inverse of d = 17. Let's check that.

In [110]:
f = 3 * 20351330601195557 + 2
In [111]:
test = f*d
print test
1037917860660973441

We just want to make sure test has remainder 1 when it's divided by Phi_N:

In [113]:
print test%Phi_N
1

OK now we're all set to try out RSA.

Should we try this? Why not?? What should our secret message be?

Let's write "hello" as 08 = "h", 05 = "e", 12 = "l", and 15 = "o"

In [114]:
secret = 805121215

Let's do something random to get the 17th power of "secret":

In [115]:
s2 = (secret**2)%N
print s2
302247549435318308
In [116]:
s4 = (s2*s2)%N
s8 = (s4*s4)%N
s16=(s8*s8)%N
encrypted_message = (secret*s16)%N
encrypted_message
Out[116]:
16899822895020834L

Now let's pretend someone handed that to us, and we want to decrypt it. That will come down to taking the fth power of that. Let's remind ourselves what f is, and that it's way bigger than d, which is 17:

In [117]:
f
Out[117]:
61053991803586673

In order to take our encrypted message to the fth power, we first write f in binary, or in other words we write f as a sum of powers of 2. I'll first write a little function that will find the biggest power of 2 smaller than f, and using that I'll form the list of exponents for f.

In [118]:
def find_leading_binary_term(f):
    exponent = 1
    while 2**exponent<f:
        exponent += 1
    return exponent - 1

powers_list = []
while f>0:
    leading_term = find_leading_binary_term(f)
    powers_list.append(leading_term)
    f = f - 2**leading_term
    
print powers_list
[55, 54, 52, 51, 47, 46, 45, 43, 38, 35, 29, 28, 26, 24, 23, 20, 17, 15, 11, 6, 5, 4, 0]

Next we need to square our encrypted_message a bunch of times to get the components we will put together for the fth power.

In [119]:
biggest_power = max(powers_list)
encrypted_dict = {}
encrypted_dict[0] = encrypted_message
for i in range(1, biggest_power+1):
    encrypted_dict[i] = (encrypted_dict[i-1]**2)%N

Now we multiply all the appropriate terms together to get the fth power of encrypted_message. "prod" is our final result, and recover our secret message "hello"!

In [120]:
prod = 1
for p in powers_list:
    prod = prod*encrypted_dict[p]%N
    
prod
Out[120]:
805121215L

Holy shit it worked.