Recover RSA private key from public keys - rhme2 Key Server (crypto 200)
Вставка
- Опубліковано 20 кві 2017
- Using the greatest common divisor (GCD) to factorize the public modulo into the secret primes, so we can forge a RSA signature.
Source for the rhme2 challenges: github.com/Riscure/Rhme-2016
=[ 🔴 Stuff I use ]=
→ Microphone:* geni.us/ntg3b
→ Graphics tablet:* geni.us/wacom-intuos
→ Camera#1 for streaming:* geni.us/sony-camera
→ Lens for streaming:* geni.us/sony-lense
→ Connect Camera#1 to PC:* geni.us/cam-link
→ Keyboard:* geni.us/mech-keyboard
→ Old Microphone:* geni.us/mic-at2020usb
US Store Front:* www.amazon.com/shop/liveoverflow
=[ ❤️ Support ]=
→ per Video: / liveoverflow
→ per Month: / @liveoverflow
=[ 🐕 Social ]=
→ Twitter: / liveoverflow
→ Website: liveoverflow.com/
→ Subreddit: / liveoverflow
→ Facebook: / liveoverflow
=[ 📄 P.S. ]=
All links with "*" are affiliate links.
LiveOverflow / Security Flag GmbH is part of the Amazon Affiliate Partner Programm.
#CTF #Cryptography
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.
It's so unbeliveable that people are smart enough to create things like this that just work. It always blows my mind...
LiveOverFlow is smart, but he said several times that he doesn't just write a script that works the first try, he spends at least a few hours on each video. He has a vid on making a vid, check it out
@@varkokonyi I think OP was referring to the hashes and algorithms originally, not just finding the flag
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.
this episode was really impressive, well done!!
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!
I agree
Ironic. For my job, I watched a lot of videos about why and how RSA works. Some more mathematic - some less. But the best explanation comes from a video about how to break RSA...
Thanks LiveOverflow
what is your job?
I learned so much with this video, great one, thanks!
Great video man ^^ Hope you got some more vids about cryptography like this one heheh
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 😃
+4 N it's a very typical CTF challenge :) mind blowing the first time you see it, but boring and straight forward afterwards :(
yeah. maths part is boring :(
LiveOverflow I always looked at RSA's simple one-line math and thought "how could no one break it"? As I've entered the video I thought, hmm, maybe someone did.
But no, you need extra help for doing so :(
Nevertheless, great video!
This challenge was based on CVE-2008-0166 (Debian Security Advisory DSA-1571-1).
Explains the name "Ebian Corp" ;)
@@EdwinBalani watch dogs
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?
Very well put together, kudos!
Great video and nice crash course on RSA!
Amazing video. Please keep them coming
This just blew my mind.. great stuff
Recover your lost coins with a private key inbox me
0:14 This somehow consistently activates my Google Assistant, even though I myself have trouble doing it.
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.
holy fucking shit
Just today i learned this at university! thank you!
Raúl Peñacoba Veigas what course are you doing?
I'm at Universitat Politècnica de Catalunya studying informatic engineering
Shit, I'm just gonna watch this when I'm 3 days less sleep deprived haha, very informative though
If you need a private key recovery just contact me on +1(202)7434155
Awesome Very brief explanation, great job, would you make a video on SS7
insane smart work !
One of the best video on crypto
Discrete math
Juicy work.
Yafu is a great tool for RSA key finding btw
Thanks for sharing
great Job! very cool!
Great video LiveOverflow(the man behind the video) where can i get the script from please?
Amazing
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.
Yup, on a quantum computer, shor's algorithm can do prime factorization in polynomial time
Desenter though when we'll get to quantum computing almost everything we do in cs will need to be rethinked and remodulized
1. There are lots of Quantum Computers but their computational Power is very limited. They can factorize very small numbers only. It's hard to estimate when they will be ready.
2. There are actually Asymmetric Methods that might hold against Shor's Algorithm, that you could use on a standard computer. So not all hope is lost. One method being discussed these days was invented a few decades ago and never used. Pretty impressive imho
Shor also figured out how to do logarithms on quantum computers which breaks the El gamal encryption
It's not sure quantum computers will break all public key encryption. As far as we know, only the popular methods will be broken. Candidates for post-quantum public key crypto: McEliece cryptosystem, Winternitz signatures, syncing tree parity machines for key exchange, NTRU...
Impressive
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!
I totally agree. At first they seem like one of those channels breaking down maths into such a simple ecplanation that its wrong, to make the videos more popular. But after watching I realized the maths is not only legit, they explain it in the easiest way I've seen.
Great channel
And they also explain RSA and how it could be broken with quantum computers! Definitely worth checking out.
if I am not wrong this will only work in the case of bad random generation right?
Wow ur videos are so awosome
geat teacher u are
that is cool
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?
Nope. That you solved an NP problem in polynomial time doesn't mean you can solve ALL NP problems in polynomial time. In fact, with quantum computing, there's an algorithm that solves it in polynomial time.
you need very very expansive FPGA boards to do that !
Wow
6:10 better explanation for modulo is remainder of division
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?
You guys ever done this and successed? I just wonder where?
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.
In practice, this is extremely unlikely. Assuming 2048-bit RSA (very typical), the primes will be 1024 bits long.
The probability that numbers will be prime in that range is around 1 in 709 (1/log(2^1024)), so to be conservative we can say there are 2^1014 possible primes that could be used. (divided by 1024, or 2^10)
So to try a birthday attack on this pool, the number of primes we need to collect to have a 50% chance of having a collision is approximately 2^507 primes, or 2^506 keys, which is utterly infeasible.
That assumes that all primes are selected randomly from all available primes, which isn't actually the case, but the further reduction to the prime count isn't going to make the attack useful.
Unless of course, the prime number generation routine is flawed in some significant way...
Surprisingly in certain circumstances it is rather high. There are lots of IoT devices that have bad random number generation. Also there has been a linux distro that so severely broke its random number generator for key generation that this happening was a real possibility.
its possible reverse AES/CBC (get the password) with the IV and the crypted text?
A+ for 'sane country like Germany'
i was making advanced rsa encrypter , then i saw this
So is this GCD method to figure out one of the prime factors not a problem in general for RSA?
+Phil Glaser well it is an issue for RSA in the sense that you have to be aware of this. It's a mistake you could accidentally make. It doesn't break RSA in every case, but you should be aware of in what cases crypto algorithms can be weak.
Are public keys not typically similar in length (i.e., common standards are 1024 and 2048 bit keys)? Assuming they are, wouldn't that just mean that you could apply this GCD method?
I don't know about the coding, but apllying the theory it seems very unlikely that the keys have the exact same lenght. I would guess they fill the remaining bits up with zeros.
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?
You didn’t miss anything ;) people have done that
I better get cracking 😂😂
@@LiveOverflow Are there way too many prime numbers to do that then?
I also immediately thought of this. The big companies would have a database with all prime numbers and make a public key per prime. Then compare those made up public keys with real ones they want to break.
They could even store the product in db
@@madcroc111 yeah, we're talking numbers thousands of digits long. The odds of finding such a collision in theory are comparable to the odds of winning the lottery while being hit by lightning.
But, sometimes people flub the random generation, making it a lot more likely.
Have rabbit command for terminal? Please give me this!
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?
Hello liveOverflow, greeting from Indonesia, I always like your tutorial because it's easy to understand. I tried to copy your script but I got confused in gcd script, can you please share your gcd script? Thank you in advance
I have a pdf digitally signed . Want to know if you can crack it so i could use that signature in other document and still be validated?
Idea of signature is about only you can create same signature. Then someone else can create the same signature, you can't prove that it was you. Private key should be your secret.
Nice video.
But I don’t understand one thing. There are services (like github) which have thousands and thousands RSA public keys.
Why don’t they watch this video and get all the private keys?
Maybe bruteforcing the value e is not easier than it is here? Because of ctfs these type of things are intended. I'm not sure tho
The RSA was implemented incorrectly, proper RSA can't be broken with modern tech yet.
How do you go from a hashed public key to the normal numbers public key? Is that just using SHA-1? Confused..:/
Go to fredmitnick95 oπ lnsta for a valid private key
How did you know that there was a common q in different keys? Can you find that out by debugging the code?
He was just trying out a possibility. If the number didn't have a common divisor, he'd have tried some other things.
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 ?
Nope, at least not in some very specific and generally constructed edge cases... that would break crypto
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)
If the private key has been leaked, there might be a decryption program. But if that's not available, the easiest way is to restore from backup (because you have a backup, don't you?). And take it as a lesson to backup more often. Or you could attempt to brute force it using methods such as GNFS, but you might get nowhere. And if you're patient enough, wait until quantum computers get more powerful, as RSA could be broken in a powerful enough quantum computer.
Warum benutzt du immer Python2 anstatt 3?
I'm an old person who doesn't want to change and learn anything new, so I stick to the good ol' days
what if public key pair is known? Assume a public key for RSA encryption given by the pair (143, 11). Find the private key corresponding to this pair.
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
sounds like you have no chance. sorry :(
It is too much coincidence that two public keys have one prime number in common... But I think it’s normal if you make a CTF...
is it? eprint.iacr.org/2012/064.pdf
'More worrisome is that among the 4.7 million distinct 1024-bit RSA moduli that we had originally collected, 12720 have a single large prime factor in common"
@@LiveOverflow thx 4 the info i didn't expected you respond me 😂😍🥰
so can this work for my wallet id transactions as i have a few id that i dont have PK any more
No. Bitcoin doesn't use RSA
I use sha512
This atack does not work. Number n to factorize have 256 bits. And primes have 128 bits each.
gcd(n,x) return common prime p only if x is divisible by p. But because p is so big you have not chance to chose such x. Random choise of x works only when primes p&q are small.
??? GCD on two n that share a prime factor works. As seen in this video??? What do you mean?
@@LiveOverflow "GCD on two n that share a prime factor works" but in case of PGP cryptography it is difficult to find x such that x and n share common factor. How to chose such x for given number n?. Mathematician chose random x bigger then n. If gcd(n,x)=1 they chose another x randomly. In case of random n this method works well because random n has often small factor and has many factors.
But in case of PGP cryptography n has only 2 factors which are primes!. So in this case is very difficult find such x that share common factor with n. Mo rover p and q are very big numbers.
Why choising randomly x is bad for this case?
For simplicity I take n=15 p=3,q=5. p
sir my pc data corrupt from virus and readme massage for private key in 0.08 bitcoin .so help me about this
Format the disk and restore your data from a backup.
Go to fredmitnick95 oπ lnsta for a valid private key
OpenSSL has had this patched since 2008 though!
@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).
And it's surprisingly easy to iron out the Euler part if you want a ground up understanding (not totally necessary though). By Fermat's little theorem m^(p-1) is equal to 1 mod p, and same for q. Multiplying gives m^((p-1)(q-1)) = 1 mod pq and done. An easy to understand proof of Fermat's little theorem is here: primes.utm.edu/notes/proofs/FermatsLittleTheorem.html Okay, it uses Wilson's theorem, but then look up that proof and you'll see it's also surprisingly simple (And how it all comes together is really rewarding and honestly magical in its own right)
how to convert public keys to numbers?
Hi , with this you can get RSA PRIVATE KEY?
I'm sure Fredmitnick95 oπ lnsta can get it for you
you saying google activated my Google assistant
Decipher RSA:
For example 12345 reverse it
54321, minus 54321-12345 every time take mod of result now devide by 9 repeat process until you get zero last value before zero is key to decipher this algorithm.
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.
That's clearly just an opinion of mine that I consider asymmetric vs symmetric a "shallow" difference. But I still mention it, so what's the issue? I just emphasise on what I think is a more sensible difference. The AES algorithm is fundamentally different from RSA. AES operates on bytes, s-boxes, shifting, mixing, ... blah... and sure that is also (binary logic) math. But RSA is basic numeric math. Sure you can jump through hoops and make RSA behave like a block cipher, but I think I made it clear what kind of difference I see there :)
Well, the one thing you clearly identified as a "difference" was that AES operates on blocks. You also said that implementations operate on bytes. Unfortunately, the same is true of RSA. I got the distinct sense of trying to describe a particular difference that wasn't really there.
But RSA doesn't operate on bytes. Sure it's implemented on a computer that uses bytes to represent the numbers, but RSA is essentially just mathematical exponentiation. While AES does bitwise xors, byte substitution, mixing the bytes, ...
For example bitwise xor in AES requires you to look at the data in bits. Same with the byte substitution. While you can do RSA with whatever number system you feel like.
That the difference to me.
"But RSA doesn't operate on bytes."
Any realistic implementation of it does. But you may be talking about it being easier to explain how it operates to someone.
Look at the wikipedia article of RSA - section: Operation. The whole algorithm does not involve bits or bytes. It's just dealing with numbers.
Now look at the wikipedia article of AES. In the highlevel description you can see how they talk about mixing and substituting bytes all over the place. Bit operations like XOR that only make sense on bits. It's nothing you do on regular numbers... "Substitution permutation network"...
We are attacking the math in this video - finding the prime factors of a number. Has nothing to do with bytes. You can do the calculations with your calculator.
While AES is completely different on the algorithm level. Ignore the fact that both is implemented on a finite memory deterministic machine based on bits. AES and RSA are based on fundamentally very very different things.
I’m so glad I got my account back with thê hêlp of the *lucidcracks* thanks I’m so happy guys
I’ve found a way to factorize primes, use a quantum computer! Is rsa dead now? 😂
Can you build one that can factorize numbers with 2048 bits?
Go to fredmitnick95 oπ lnsta for a valid private key
it 's 10th grade highschool math 🤣🤣
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
*DOAVERCRACKS* óñ !G🇺🇸
wtf macOS. Thats kinda disappointing.