Cracking the RSA keys (Part 1 – getting the private exponent)

The whole idea of the RSA private key is the hardness of factorisation of two very large prime numbers.
That’s why recommended RSA keys are >2048bit long.
I won’t get into RSA details itself. If You need any info, it’s here: WIKI
For a sake of demonstration, 256bit public_key will be used. With the current hardware that we have these days, it’s very easy crackable.

Lets convert it to a more ‘mathematical’ expression:

Ok, so the public key consists of Modulus (product of two prime numbers) and a public exponent:

Let’s get rid of colons and convert all the letters to a uppercase to be prepared for a conversion:

Conversion to a decimal:

For digit factorization, I’ve used yafu (Yet Another Factoring Utility)
Ok, let’s factor the digit:

Factorisation may take a while depending on the number lenght. My case was very fast because it cached the results. The first time run this command for this digit it took around 1 minute with 4threads (You may set the thread count in yafu.ini file)
So our digit is a product of two prime numbers 299565145299812070871826362285166503457 and 267166959046601000378504971553629664723.
This is the part, that for longer keys takes forever. That’s why the >2048bit keys currently are counted as unbreakable.

Lets go on, shall we?
Private exponent is calculated with formula:

in other words, it’s a reverse public exponent by a modulus of Euler function.

Euler function may be calculated using:

p and q are the prime numbers that we’ve found.

Ok, so now only private exponent is left.
For that we need the public exponent that we saw in public key, so the whole calculation looks like this:

It would be hard to calculate these things with the simple calculator, so I’ve used the WolframAlpha for that.

That’s it. The private exponent is 42081396264635804076297698591471521526036226546344296111866129299947306543297.

Next: Cracking the RSa keys (Part 2 – generating the private key)

Leave a Reply