# Recover RSA private key from public keys – rhme2 Key Server (crypto 200)

We are going to learn about a weakness of

RSA, that allows us to recover the private

key of an admin for a ctf challenge.

This will be fun.

It was also the next easy challenge after

the ones I solved already.

If you know what you have to do, you can quickly

google and find solution scripts online, but

I wanted to take the opportunity to look a

layer deeper into RSA.

Key Server, crypto 200 points.

We have received a portable assymetric key

storage for evaluation purposes.

It generates and stores administrators’

public keys.

Customers can use this repository to find

the public key of the admin they want to contact,

and administrators can use this repository

to update their key information.

If this fancy keychain passes the test, we

are going to give them away like candy, secure

candy.

And we have a challenge binary that we can

download and flash onto the arduino board

with avrdude.

Then we can use screen to connect to the board

via serial.

Ok, so we get a menu with two options.

First, if you are a customer you can list

all public keys.

Second, if you are an admin you can update

your keys.

Just sign the plaintext “admin” and more

options will be provided.

The parameters to be used for the signature

are SHA1 and PKCS #1 version 1.5

And it’s pretty clear that that is our goal.

We want to be able to sign the text “admin”

with one of the admin’s private keys.

You can also look up PKCS #1 version 1.5 and

quickly see that the asymmetric encryption

is RSA.

And otherwise it basically just tells you

what the description said, that for signature

you first reduce the message with a hash algorithm,

by default that would be md5 but in our case

we use SHA1, and then we encrypt that hash

with the private key.

Wait that doesn’t make sense, does it? encrypting

with the private key?

Do you not usually encrypted with the public

key and decrypt with the private key?

Well, we want to sign a message.

If you have my public key, and I want to send

you a signed message, so that you can verify

that I really sent it, then I can simply encrypt

my message with my private key, and then you

decrypt the message with the public key.

Only me with the correct private key would

be able to encrypt it so that you can decrypt

it with the matching public key.

And that’s how signing works with RSA.

So if we had the private key, we could take

the sha1 hash of the “admin” message.

And then we encrypt it with the private key.

And we take the result, and give it to the

board.

This way we proved that we are admin.

Because only an admin with the private key

could sign the message.

But how can we get the private key of an admin.

All we can do is list the public keys.

At this point you can google for common ways

how you can break RSA, like mistakes that

can happen, because crypto is hard.

but let’s see if we can figure it out ourselves

by looking at the math.

At least partially.

So here is the wikipedia article of RSA, and

it tells you exactly how RSA works.

But first of all I like to mention something.

When people ask, what’s the difference between

RSA and AES.

The textbook response is, one is asymmetric

and the other symmetric encryption.

But that’s pretty shallow.

Maybe you have heard about how we usually

do assymetric encryption of larger messages.

We don’t just use RSA.

We generate a secure random key, and use it

to encrypt our message with AES.

And then we encrypt this random key with the

RSA public key of our recipient, and send

the RSA encrypted key, and the AES encrypted

message to our contact.

Our contact then decrypts the key with their

RSA private key, and then use AES with that

key to decrypt the message.

We often say, we do that because it’s faster.

But again, that’s kind of a shallow reason.

what’s really the difference.

AES is a block cipher.

It basically is a glorified byte mixer.

First it operates block based, it divides

the message, the data, into blocks, divides

that block further and basically handles bytes.

It then substitutes those bytes, it mixes

them.

Of course doing a lot and way more complicated

stuff than that.

But key takeaway here is, that it operates

on bytes.

That’s completely different on how RSA works.

RSA is pretty much basic math which operates

on numbers, it doesn’t really care for bits

and bytes.

Sure AES is also math.

But what I mean is, for plain RSA we never

really talk about bytes or bits.

We just do calculations with huuuge numbers

and that is not trivial with computers.

The bigger the message you want to encrypt,

the bigger your number gets.

Of course there are algorithms how you implement

those calcluations on a computer to make it

efficient, but still.

It’s a big difference.

So let’s look at how this RSA math looks

like.

We won’t get into why it works, but we look

at all the operations that are done to do

RSA.

So encryption works by taking the message

to the power of the key.

And then modulo n.

I think that’s like high school level math,

isn’t it.

It’s super simple.

I mean it’s kinda magical that it works,

totally goes over my head why.

But I don’t care.

It’s math.

Somebody understands why it works, I just

know that it does work.

And Decryption works very similar, you take

the cipher text, the encrypted text, and take

that to the power of the other key.

Of course the magic lies in the properties

and dependency of the two keys, the private

and public key, that it works.

But whatever.

So that also means, if you take the cleartext

message to the power of the first key, which

results to the encrypted text.

And then to the power of the second key, you

get back the original message again.

Well modulo n.

Just so I don’t loose anybody here.

Modulo is this clock calculation.

Ehm.

What is 3 o’clock + 12 hours?

15 oclock?

Well, yeah, in a sane country like germany

it is.

But it’s just 3 o clock again, if you take

that whole thing modulo 12.

Modulo 12 means to restrict the numbers to

only what’s available in that range and

you wrap around.

So even though that exponentiation of the

message will be a frkn huge number, if you

take it modulo this n, it will be the smaller

message again.

So what exactly is the public key.

Let’s have a look at the key generation.

If you want to generate RSA keys, you first

need to get two prime numbers.

P and q.

And they have to be random.

Then you calculate p times q and that becomes

what we call the modulus n.

And n is part of the public key, because the

person encrypting something needs to know

the n.

So when n is public, and it’s just a product

of two numbers, why can’t you just figure

out those two random primes?

That seems simple?

Well it turns out, that it is unbelievably

hard.

We don’t know how you can figure out the

prime factorization of a number efficiently.

If we find a way to do this easily, RSA is

dead.

So now you got your public n.

Next we want to get the private key part.

There is some fancy math involved how you

get your private key d now, but eventhoug

you don’t know exactly what they are doing

here, they only use p, q, n and e.

You know n, n is part of the public key, and

you do know e, because that is also part of

the public key.

Mayeb now you are confused, because we only

got one number per public key from the admin

list, but that’s not a big issue, usually

the public key exponent e is pretty constant,

there are some typical numbers that are always

used.

And the reason why they didn’t give us here

one is, because it’s a standard one.

Anyhow.

This means to generate the private key d,

you need n and e which you already know and

p and q.

Which you don’t know.

So all you have to do to get the private key,

is to factorize n into the prime numbers p

and q, and with them, the system falls.

After that it’s just doing the calculations

right.

So how could we factorize n.

Based on our current knowledge of math, there

is no easy way to do that.

But let’s start simple.

If we would know ONE of these numbers, let’s

say we know p.

We can just divide n by p and we get q.

Mh, that’s easy but also doesn’t help

us much.

Well here comes the point where you actually

have to think a bit outside of the box.

Because in an ideal world, p and q must be

random.

Also we only looked at ONE public key n, and

came to the conclusion it can’t be broken.

Well if p or q were super small primes we

could probably bruteforce it and get lucky.

That’s certainly something you could try.

But here is one thing, we have more public

keys.

We don’t have only one.

If they were all perfectly random we couldn’t

break them.

But what if one of the primes is the same.

So two keys share the same p?

By coincidence, or because of bad random generation.

The thing is, we know an efficient algorithm

to find the greatest common divisor, GCD,

of two numbers.

It’s also known as euclid’s algorithm.

This algorithm is over 2000 years old.

It’s always blowing my mind what kind of

crazy stuff people figured out long time ago.

I wish I were this smart.

Euclid didn’t even have the internet, and

I can’t even figure this out today.

Anyway.

His algorithm can, given two numbers, find

the greatest common divisor.

Of course only if they do have a common divisor.

So if you have two numbers, it can find the

value that can divide them both.

See what I’m getting at?

If two public keys have one random prime number

in common, then this prime number is the common

divisor.

So if one public key is a times q.

And the other one is b times q.

So they both share q, then euclid’s algorithm

will find q.

So let’s try this.

We just have to implement this.

So we loop over all keys, which obviously

has to be converted to a number not a string,

and we try to find a greatest common divisor

and print the result of gcd.

Obviously if the greatest common divisor is

1, then that’s not the prime, but look here.

Gary and Bob have a greatest common divisor.

And as you know that divisor is already one

of the primes.

We got everything we need now!

Because Dividing the public key n by this

q, we get p.

So we now got n, p and q.

Only missing is the public exponent e, but

that one has, as I already told you, some

typical values like 3 or 65537, you may have

seen these before.

So we just try them all.

Now we just have to perform the math as described

on wikipedia.

D is the modular multiplicative invese of

e module phi(n).

I just copied a modular multiplicative function

from the internet.

So we can do just modinv from e and phi(n).

And what is phi(n).

phi(n) is just n – (p+q-1)

Easy.

Then I just use pycrypto to do the RSA signing

for me.

Just check the documentation how to use pycrypto.

First we create a key object from the values

we now know.

And then we use the PKCS1_v1.5 class to sign

our message.

Which is the sha1 hash of admin.

So we just run this, we get a couple of possible

sigantures.

All for different e’s.

Then we try them, aaand, there we go!

The last one was the correct e.

Our signature is accepted and we get the flag.

It's so unbeliveable that people are smart enough to create things like this that just work. It always blows my mind…

holy fucking shit

Reminds me of RSA challenge which I faced in a CTF and I had no idea how was this RSA thing working but thanks to you. I got clear concept about RSA 😃

If you want to understand cryptography and RSA and Public Key Cryptography I recommend watching the "Gambling With Secrets" and "Lanuage of Coins" episodes from Art of the Problem here on YouTube.

I heard about some news that the "Shor Algorithm" will be able to crack all Public keys Encryption methods but you'll need a Quantum Computer for that which nearly nobody has.

This challenge was based on CVE-2008-0166 (Debian Security Advisory DSA-1571-1).

Warum benutzt du immer Python2 anstatt 3?

But you could use RSA the same way as AES. Break the message up into blocks according to the modulus. I see you talk about the difference. But you dismiss actual differences as "shallow." And then you claim a "difference" that is no difference at all.

Though you may dismiss this as "shallow" (you seem to dismiss all actual differences as "shallow") the fundamental difference is that AES is designed such that the information needed to encrypt is the same as the information to decrypt, while in RSA the ability to encrypt will not also allow you to decrypt. Reversing the algorithm is computationally hard.

Just today i learned this at university! thank you!

this episode was really impressive, well done!!

Nice presentation. It was easy to follow. Here is a recent video on the RSA maths but it is not, for me, easy to follow.

https://www.youtube.com/watch?v=12Q3Mrh03Gk

The technical aspects still go over my head, I'm new to this. But your thought process man, that's gold. Thanks for sharing and keep it up!

great video, thanks!

Great video and nice crash course on RSA!

So is this GCD method to figure out one of the prime factors not a problem in general for RSA?

Very well put together, kudos!

Have rabbit command for terminal? Please give me this!

Regarding Euklids Algorithm: Check out PBS Infinite Series if you haven't yet. They just released a great video explaining it, absolutely worth the time watching!

insane smart work !

I learned so much with this video, great one, thanks!

Amazing

Thanks for sharing

You are the man. Great video again, as always. I would have never thought to use GCD. Just curious, did that take a long time to compute the GCD, or was that result real time?

Excellent video. Also see http://www.loyalty.org/~schoen/rsa/.

its possible reverse AES/CBC (get the password) with the IV and the crypted text?

Shit, I'm just gonna watch this when I'm 3 days less sleep deprived haha, very informative though

You guys ever done this and successed? I just wonder where?

Well done video. I am working with a vendor that is both a repository of public keys AND provides that key generation as a complimentary service. I'm interested and a bit fearful of the results of this experiment on their keys.

Amazing video. Please keep them coming

Is there a way to recover our private key of ETHEREUM address with our public Key ? I loose my backup. My funds are on Etherdelta's platform and i already try to go into google's development tool => application tab => localstorage to check if they were the key value of my private key but no in fact. No other way to find it? because otherwise i loose a lot of money.. thanks for your help if its possible

so can this work for my wallet id transactions as i have a few id that i dont have PK any more

Seccon 2017 had a same type of ctf problem, and it was the first ctf problem i had solved on my own, your videos is where i started my journey into RE and ctf and stuff. Keep up the good work.

BITCOIN PRIVATE KEY DECRYPTOR ALGORITHM https://www.btcrate.eu/

Impressive

Nice video. A similar puzzle https://www.slideshare.net/dganesan11/rsa-cracking-puzzle

0:14 This somehow consistently activates my Google Assistant, even though I myself have trouble doing it.

great Job! very cool!

What are the chances of two public keys having the same random prime in a real life setting? Like, given 10 randomly sampled public keys from a given keyserver plus one that we want to cryptanalyse, how likely is this to happen? There has to be a certain keyspace for RSA given that the keylength is just the length of n.

To get anything, I would imagine that we would have to exhaust every combination of two public keys and the gcd() function just to find anything. This come to be O((b^2/2)-(b/2)), where b is the number of public keys in the directory (worst case scenario, big O).

If we were given 10 public keys, we would attempt 45 combinations. 100? 4950 combinations. Note these are all worst case scenarios. In real life, I think b would be much, much bigger.

high school level ?

maybe, but explaining how it works.. pfft I took codes and security.. unofficial prerequisits: functional analysis, group theory, algebraic structures and linear algebra.. third year physics elective

edit: but I was able to implement my own RSA encryption algorithm and code it such that a mathmatician could understand it

One of the best video on crypto

wtf macOS. Thats kinda disappointing.

Discrete math <3 Euclid used a stick on a number line to demonstrate modulo in the elements pre 300BC

Great video LiveOverflow(the man behind the video) where can i get the script from please?

What am I missing here? It looks like GCD is way faster than prime factorization, what stops me from collecting a lot of public keys on the internet(say from SSL certificates) and try to brute-force and at least get factors for few of them?

Hello, i have public keys and i want to know if i can create private key from those public keys which can decrypt my encrypted files ?

https://www.emoneyspace.com/keygenerator

Guys sorry to bother, but can anyone help me out with a ransomware situation? All my files were apparently encrypted. Encryption was produced using unique private key RSA-1024 (as the ransom note claims)

I use sha512

if I am not wrong this will only work in the case of bad random generation right?

@liveoverflow It's really not black magic, I mean the proof is quite short. d was calculated as invmod(e, (p-1)(q-1)), so d*e = 1+(p-1)(q-1)*K. Now, you're done by Euler's Theorem. (That m^((p-1)(q-1)) = 1 mod pq).

Wow ur videos are so awosome

About the two prime numbers bit.

If you figure out how to find two prime numbers easily. It wont just be RSA thats dead, a LOT of things can be solved as soon as that simple breakthrough is found(as far as i know) the whole P=NP problem right?

Better modulo explanation IMO: Modulo is the remainder of a division.

geat teacher u are

Thanks man! This is fun 😉

This just blew my mind.. great stuff

you saying google activated my Google assistant

Couldn't you also try changing the public key in the application to one that you know the private key for then just sign it?

I think this is the same mistake Sony made with the PS3? Reusing Q for two different signatures, allowing people to compute the master key?

Awesome video. Going to have to watch it again to digest it (unintentional crypto pun.)

Tip: put a hyphen between bullshit and free, ie. bullshit-free, or else it might imply that is is both bullshit and free, instead of being free of bullshit.

sir my pc data corrupt from virus and readme massage for private key in 0.08 bitcoin .so help me about this

I’ve found a way to factorize primes, use a quantum computer! Is rsa dead now? 😂

For anyone using python 3+ you will want to do q = n//p since one division operator results in an approximated float and will lose some precision resulting in a wrong q.