Rivest Shamir Adleman, aka “The (in)Solitude of Prime Numbers”

During the last weekend I’ve got back to the good old times, with the Zeromutarts CTF, a challenge organised by the Technische Universität of Braunschweig, Germany.

I’ve found tho choice of the challenges very well made: some of them were easy, some others a little more tricky.
It has been a lot of fun, anyway, going through all of them.

wWat I’m sharing, here, is the solution of one of these challenges, called “rivest-shamir-adleman” – obviously concerning RSA encryption – which helped me to revise some interesting notions about maths applied in cryptography, (numbers are sexy!).

The challenge

The challenge was about decrypting this message, and catching the flag contained on it. of course, the encryption is made with a low exponent, and this makes possible to attack it easily.

In the python script attached to this challenge, the guys provide us with the elements we know

`N = 80646413 e = 5`

while d is unknown; this means – to summarize – that we only have a part of the public key, and we need to find the private one.
The python code attached, conveniently completed, will find the solution.

Let’s take a look to the arithmetic functions which are hiding behind that

solution 1

Finding private exponent by using Euler’s totient and Extended Euclidean algorithm.
We know that the modulus N is given by

`N = p*q` (where p and q are two prime numbers)

so

`N = p*q = 80646413`

let’s compute now the Euler’s totient of N, which is

`φ(80646413) = 80628348`

e is known being 5, the algorithm of RSA tells that d is e-times the modular multiplicative inverse of N

`d = e (mod φ(N))`

which is

`d = 5 (mod φ(80646413)) = 5 (mod 80628348)`

we can calculate the modular multiplicative inverse with the Extended Euclidean algorithm, (which, for instance, you can even find in the python code)

`d = 290262053`

the public key is: `N = 80628348, e = 5`
the private key is: `N = 80628348, d = 290262053`

It’s good to remark that e and d are both prime numbers and in the meantime both co-primes of φ(N): in fact, if they weren’t, the decryption would not have been unique.

solution 2

Finding private exponent starting from p and q primes
as we have e and N, let’s find their Greatest Common Divisors

`5: 1, 5`

`80646413: 1, 8059, 10007, 80646413`

the Euler’s totient we talked before, in RSA is also known as r

`r = φ(80646413) = (8059-1)*(10007-1) = 8058*10006 = 80628348`

following the RSA theory, we need now to find a list of candidates integers K which equal 1 mod r. this means that

`K = (e*d) = 1 mod r = 1 mod (80628348)`

Here’s a list of candidates integers K

`80628349 161256697 241885045 322513393 403141741`
`483770089 564398437 645026785 725655133 806283481`
`886911829 967540177 1048168525 1128796873 1209425221`
`1290053569 1370681917 1451310265 1531938613 1612566961`
`1693195309 1773823657 1854452005 1935080353 2015708701` `2096337049 2176965397 2257593745 2338222093 2418850441`

By factorizing each of these candidates, we’ll need to find all of those which accept 5, (e), as divisor: one of the good ones, divided by 5, will give you the value of d.

`K = 1451310265 has these prime factors: 5*307*945479 = 5*290262053`

`d = 290262053`

catch the flag :>

Now that we know even the private exponent of the encryption, we can use any RSA calculator online, (like this one by the Drexel University), and we can easily decrypt the message. the flag needed to solve the challenge was

`flag{rivest_and_the_cool_gang_would_be_proud}`