HSCTF - RSA Cryptography (Reverse Search Algorithm)

Key Takeaways

[Music] what's going on everybody my name is John Hammond welcome back to the YouTube video we're looking at the cryptography section of HS CTF 2019 this challenge which was the first in the category is called reverse search algorithm to point value got knocked down pretty low so it's not a difficult challenge in fact you can probably already guess by the challenge title it's a reference to RSA so we have these variables that are given to us an e and c we can assume that this is our ciphertext and our public key and as our modulus and E as the exponent so let's go ahead and create a file for this I'll just call it like RSA prompt text and I'm gonna throw these in here because I will use them later in the video and then I'll go ahead and create a new file that will just be subl RSA or api whatever we want yeah let's just do RSA not pi that's fine and we'll have our shebang line because it's going to be a Python script to solve this and we'll paste those numbers in there and then we'll start to work so with RSA I've covered this in way too many videos already we need to factor n so I want to show you a couple ways to do this right normally you do this just by factor DB factor DB calm you can face it in here and you have number 29 looks like that is one of our peas and our other factor Q is gonna be this other value so we can copy that guy in here and then we would be able to calculate fee and then we can calculate D and then we can calculate the MA message the plaintext and that works just fine for us let's go ahead and do that just whip it out real quick so from crypto dot util dot number we can import inverse and I also want to import long two bytes because I was remembered thank you to that fellow viewer and thankful and very grateful for you and sharing that long two bytes can totally be able to print out an integer representation and straight to ASCII and give us the flag so let's calculate fee right fees inverse e and fee I'm sorry that's D but we need to actually calculate fee so given that these are both prime we can calculate that totient euler's totient by P minus 1 times Q - one and then D will be the modular inverse and M can equal the power of C raised to D all mod n so we have M calculated just fine here and then we can go ahead and display it as long - bytes which will simply give us the flag right that's easy RSA decryption H s CTF yes or si is solved that's it I want to sprinkle in some other cool niceties here I'd like to show you the prime factor a in Python in fact this is a fork of the library that originally has prime fact itself that will go ahead and attempt to factor integers and offer other cool mathematics and stuff that's built off of GM py or Gympie I don't know however you'd like to say that or pronounce it but gimpy - this fork actually adds support if it's not able to determine a factor by its mathematical means it will just go ahead and ask factor DB and try and pull it off from the internet so that's that's an option here you can install it using the github repository so pip install gets and then lists location you could just tack on a get plus if you're using the URL and I know that works just fine for me I have had to stumble a little bit because I got it working in Python 3 but I needed to install a couple other modules here because it needs Gympie what I needed to do when pip was trying to install was actually install this library Lib MPC dev so I wanted to make that noted for you if you needed to install that you can and then you should be able to suit up a pip install can't be - again I was I had the most success with Python 3 you saw a lot of red because I was in pip - right if I specify pip 3 I've got 2 installed and it work just fine note you don't need to sudo if you set up a virtual environment and that is a recommended way to do it again or just kind of blazing through stuff because this is the CTF realm right we just kind of want to roll through the answer be very very careful if you pseudo install pip packages because maybe if it's maybe it could be malicious right you want to create a virtual environment now we have Gympie installed we can go ahead and actually grab at this URL from the git repository and then we can just use git plus and then plop in that URL that should go ahead and install it for us now in my code I can import Prime FAQ we have P and Q that no longer be no longer have to be manually inserted but Prime type will be able to print it out for us remember if I try and run this sublime is kind of tuned to use Python 2 right now and I don't have installed for Python 2 you've got to be cognizant of what Python version you're using so in my command line I can totally use Python 3 and P is not defined anymore so let's just exit but now you know okay there aren't any errors it would pop up because we were able to import prime factor just fine sublime text is the one that's in the wrong right now because it's using Python 2 because I have primetime installed for Python 3 where I okay okay so now prime FAQ has this nice handy handy function called factor int and you just pass in the number or variable in this case that you want to factor so let's display those and we'll print it out here 29 is one factor and this other value is another factors and that's the number of occurrences that is in the prime factorization so we can pull these out right we can say items or I'm sorry it is key doesn't it ticked yes ticked keys so then we can say P and Q will equal those that are not printed I'll actually just print out P and Q to make sure we got these a okay and we do so now we don't need to like hard code those values in prime faculty calculate them and figure them out for us and fee we'll be able to calculate this D will calculate M we'll calculate it all works perfectly fine now now we have a bytes representation of the flag so yes we have solved our essay awesome so that's it I want to showcase one last thing because I want to show off katana katana will be able to do this and just crank it out so let's get into get up Ratana I will activate the virtual environment as said again that's the better practice let's remove results let's run katana will use all here and then we'll offer so tack a for Auto not all right it'll use all units that it can find applicable HS is now our essay prompt text and our flag format is HS c TF curly braces paste that in here and it should crank through it because all that prompt has are any and see those values including in there it's found those and detected okay that's gonna be likely RSA factored it with that prime factor like just told you about knew how to calculate fee and know how to calculate d and spat it out for us so all you need to do is give it the prompt and katana will solve it cool alrighty thank you guys for watching I hope you enjoyed this if you did like this video I know I've done RSA like way too many times but in the nature of a CTF write-up I wanted to give it to you and I wanted to sprinkle in those other niceties between prime fact pulling down at github library and pip and showcasing how katana can just rip through this so soon we'll be in the hands of you the people alrighty if you liked this video please do like comment and subscribe love to see you in the discord server link in the description join the party I'd love to see you on patreon let me see you on PayPal thank you for your support and whatever you're going to help the channel see you the next video [Music]