Zup folks, for the picoCTF we (dtm, pysec, kowalski and me), had to solve several crypto challenges.
RSA being the most common subject.
So here I thought it’s time to share what I know about RSA, because it’s one of the most common algorithms seen in public key crypto.
First let’s start with a little story:
Suppose you work for the CIA or NSA. The year is 1800 and computers weren’t yet invented. Some journalist is being threatened by Erdogan, but he has valuable info and you want to make sure he can send it to your office, without having to worry about some KGB trained Putin getting his hands on it. You could send a safe with a padlock and a key, but what if someone intercepts the key and makes a copy of it?, that’d be terrible.
Luckily you meet 3 guys called Ron Rivest, Adi Shamir, and Leonard Adleman. They have an awesome invention. They have invented a padlock that uses two keys: one for unlocking and one for locking. Genius right?
So now you send the unbreakable safe with this unbreakable padlock and the key for locking to this journalist and he can write his message (‘Send Nudes’) on a paper, put it in the box, lock the box with the padlock using the special key for locking and put it somewhere on a Ali Express delivery camel. Mission Succeeded!
The two key system is what make public key crypto so succesful, we would refer to the key for locking as the
public key and the key for unlocking as the
Here the idea is that we use a mathematical system / formula that is easy to calculate one way, but very hard to reverse. RSA uses such a formula, the idea is as follows:
Multiplying two very big numbers is easy, finding the original two big number with just the product of it is VERY hard (tedious).
Before we continue we have to cover some mathematics, it’s probably very unlike anything you’ve ever seen in school, but it’s not that hard.
So let’s start off with looking at a very simple python program:
import sys a = int(sys.argv) b = int(sys.argv) n = int(sys.argv) c = (a * b) % n
That’s it, this the mathematics behind RSA, it’s called
In RSA you’ll usually work with really big numbers of several hundred digits
Something you might see is the following calculation:
61447^28918293809555798793287493827982374 mod 9830849029834038402948
(note that mod is the same as
% earlier in the python program).
Square and multiply
So how could the computer calculate such large number?
A cool trick for this is called
square and multiply
2^684343 mod 102
This would be a way too big number if you’d try to calculate
2^684343 first and then do mod 102.
Luckily there are a few cool tricks in modular multiplication:
a^b mod c is the same as
(a mod c)^b mod c in MM (modular multiplication)
So for example 103^999999999999999 mod 102
is the same as (103 mod 102)^9999999999999999 mod 102 which is the same as:
1^99999999999999999 mod 102 which is just 1.
So how does this property help us solve
2^684343 mod 102?
2^684343 mod 102 == 2 * 2^684342 mod 102 == 2 * (2^2)^342171 mod 102 == 2 * 4^342171 mod 102 == 2 * 4 * 4^342170 mod 102 == 2 * 4 * (4^2)^171085 mod 102 == 2 * 4 * 16^171085 mod 102 == 2 * 4 * 16 * 16^171084 mod 102 == 2 * 4 * 16 * (16^2)^85542 mod 102 == 2 * 4 * 16 * 256^85542 mod 102 == 2 * 4 * 16 * (256 mod 102)^85542 mod 102 == 2 * 4 * 16 * 52^85542 mod 102 == 2 * 4 * 16 * (52^2)^42771 mod 102 == 2 * 4 * 16 * 2704^42771 mod 102 == 2 * 4 * 16 * (2704 mod 102)^42771 mod 102 == 2 * 4 * 16 * 52^42771 mod 102 == 2 * 4 * 16 * 52 * 52^42770 mod 102 == 2 * 4 * 16 * 52 * (52^2)^21385 mod 102 == 2 * 4 * 16 * 52 * 2704^21385 mod 102 == 2 * 4 * 16 * 52 * (2704 mod 102)^21385 mod 102 == 2 * 4 * 16 * 52 * 52^21385 mod 102 == 2 * 4 * 16 * 52^2 * 52^21384 mod 102 == etc etc
So this would be an approach to solving such big calculations, I hope you understood the method.
Now let’s have a look at
Groups are a mathematical term for a set of elements with an operation defined for them.
This may sound rather vague, but you already know some groups
For example, the real numbers with addition (R+) is a group.
here the operation is ‘+’ as you know it and the numbers are the numbers as you know them. (1, 5, sqrt(5), pi etc).
These are a group because the following properties hold:
ais in R+ and
bis in R+, then so is
a + b.
- there is an element
0in R+, such that for all
x + 0 = x(well obviously) This is the
- for every
ain R+, there is
inv(a)in R+ (-a in this case) such that
a + inv(a) = 0(a + -a = 0)
- for every
(a + b) + c=
a + (b + c)
If this doesn’t make any sense, don’t worry, it just means that adding two numbers will result in a new number and that that number exists in the numbers.
Also it means that for every number, there is a unique number, such that adding that number to the number does nothing to the number (for 4 + 0 = 4).
And lastly it means that the order doesn’t matter:
(2 + 4) + 4 is the same as
2 + (4 + 4)
We will now look at the group
This may sound weird, but don’t mind the notation.
Here Z mean the whole numbers (3, 5, -2, 2323232 etc)
and * means multiplication.
The n here stands for the modulo.
That means if n is 15 for example you’d have the group:
Z15* (Just notation).
So now rather than R+ with addition we have Zn with multiplication (Zn*).
The following things now hold for Zn*
- If a and b are Zn* then so is a * b
- There is an element e in Zn* such that a * e = a (here it’s 1)
- For every a in Zn* there is an a^-1 such that a * a^-1 = e
Considering these criteria let’s look at Z8* (meaning n = 8 (Zn*) ).
So what elements would be in Z8*?
0 is not in it.
After all according to rule 3 there must be an element in Z8* such that 0 * x = 1.
This is never gonna be true so 0 can’t be in it.
1 is in it.
2 is not in it.
if 2 is in Z8* then so is 22 according to rule 1. But then so is 222 = 8 mod 8 = 0, but we already found 0 is not in it.
Another way to approach the question wether 2 is in it, is by looking at rule 3. There must be some x in Z8 such that
2 * x mod 8 = 1.
But since both 2 and 8 are even numbers, this is never gonna work out.
Then with the same logic we know that 4, 6 and 8 are not in Z8*.
After fiddling around a bit we will find that only 1,3,5 and 7 are in Z8*.
That means that there are 4 numbers in Z8*.
And that if you multiple any of these numbers the result will be one of these four numbers
The order of groups
As we found earlier there are 4 elements in Z8*. We then say that the order of Z8* is 4.
#Z8* = 4 or
|Z8*| = 4. Normally the order of a group Zn* can be tedious to find, but there are a few special cases:
- n is prime
- n is the product of two or more prime numbers who are all different from each other.
In this case we can use Eulers Totient Function. the notation for this is called phi(n)
So let’s look at the different cases discussed earlier
- If n is prime, then phi(n) is simply n-1
- If n is the product of say p,q,r (n = pqr) then phi(n) is (p-1) * (q-1) * (r-1),
If p,q,r,d… then just (p-1)(q-1)(r-1)(d-1)…
Now why would we even care about Eulers Totient Equation?
As it turns out, if n is the product of two prime numbers or n is prime the following holds:
Let x be an element of Zn*, then x^phi(n) mod n = 1.
Back to RSA
RSA works on this principle:
Find two very large prime numbers
q, where p != q.
n by multiplying p and q.
phi(n) by doing
(p-1)*(q-1) (Eulers function).
Now pick a nice public key
e such that
e is prime and
e is rather small (like 62219).
Now calculate the inverse of
Muh math again
Woops how do we calculate the inverse?
Ez, use python, but since that’s trivial let’s do it by hand using a more simple example.
Suppose you have p = 13 and q is 17.
Then n = 13 * 17 = 170 + 21 + 30 = 221.
Then phi(n) = 12 * 16 = 160 + 32 = 192.
Now suppose you’ve chosen e = 7.
So now you want to calculate inv(e) mod phi(n).
There is a neat little trick for this.
It goes as following:
0 * 7 = 192 mod 192 (since 192 mod 192 = 0) 1 * 7 = 7 mod 192 -27 * 7 = 3 mod 192 (0*7 - 27 * 1*7 -> 192 - 189 = 2) 55 * 7 = 1 mod 192 (1*7 -2(-27 * 7) -> 7 - 2*3 = 1)
So this means 55 is the inverse of 7 mod 192.
Don’t worry if you don’t really understand this technique, it takes some brainfarts until you get it, but it’s not that important considering we have a computer who is perfectly capable of doing all this work for is. check out python’s gmpy2 module.
Back to RSA
So now that we know how to calculate the inverse let’s look at that RSA example once again.
e = 62219 we use the computer to calculate inv(e) and find
So now we have n,e and d. This is all you need to the RSA to work.
Suppose you have a message
m that you want to encrypt.
The procedure is as follows the server gives you (n,e), it’s public key.
You then calculate
c = m^e mod n.
You then send this to the server.
The server receives c and calculates m by doing c^d mod n = m.
So why does this work?
Well remember that c = m^e.
And that d = e^-1 mod phi(n)
(m^e)^(e^-1 mod phi(n) ) ==
m^(e * e^-1 mod phi(n) ) ==
m^(1 mod phi(n)) ==
m^phi(n) * m^1 ==
1 * m^1 ==
Let’s look at our previous example again where we had p = 13, q = 17, e = 7 and d = 55 n = 221.
Suppose we want to encrypt the message
_ (a single spacebar) then in ascii that is 0x20, meaning 32 in decimals, so m = 32.
Then we calculate 32^7 mod 221 = 59
we send 59 to the server and the server then calculates
59^55 mod 221 = 32, yay success!
This was probably a bit messy, so please give me loads of feedback and I will keep improving this article.