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.
prime1= 512927357
prime2= 674506081
Next, compute the product. Easy peazy lemon squeezy.
N = prime1*prime2
Note that N has approximately twice as many digits!
N
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.
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.
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.
find_a_factor(859093)
(859093, 'Prime!')
find_a_factor(2814841)
(2814841, 'Prime!')
find_a_factor(15485863)
(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.
N and d.
Take their message, which is a number, and take it to the dth power modulo N. Make sure you know this easy.
Take their message to the f'th power to get it back to their message. Again, super easy.
Phi_N = (prime1 - 1)* (prime2-1)
print Phi_N
print N
345972620220324480 345972621407757917
Choose a d and make sure it's prime to Φ(N).
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
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.
f = 3 * 20351330601195557 + 2
test = f*d
print test
1037917860660973441
We just want to make sure test has remainder 1 when it's divided by Phi_N:
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"
secret = 805121215
Let's do something random to get the 17th power of "secret":
s2 = (secret**2)%N
print s2
302247549435318308
s4 = (s2*s2)%N
s8 = (s4*s4)%N
s16=(s8*s8)%N
encrypted_message = (secret*s16)%N
encrypted_message
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:
f
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.
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.
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"!
prod = 1
for p in powers_list:
prod = prod*encrypted_dict[p]%N
prod
805121215L
Holy shit it worked.