# Information:
CTF Name: PicoCTF
CTF Challenge: rsa-pop-quiz
Challenge Category: Cryptography
Challenge Points: 200
PicoCTF 2019.
# Challenge Description:
Class, take your seats! It’s PRIME-time for a quiz… nc jupiter.challenges.picoctf.org 1981
Hint: RSA info
# Writeup:
In this challenge, we are given a netcat command. It is also clear that we have to answer/solve some challenges regarding RSA.
I started by running the command nc jupiter.challenges.picoctf.org 1981 on my Linux terminal, this was the result:
First challenge:
I do not recall RSA that well so I decided to search for it. I used the link provided in the hint. After a while reading, I manage to find out that:
n = p * q
Knowing this I created a simple Python 3 script that printed to the terminal the result of p * q. The result of the product is: 4636878989. Below is the image of the interaction with the challenge:
After solving the first one a new challenge appeared:
Second challenge:
The idea is the same, the formula to use is also the same, so I went back to the Python 3 and perform the calculation, q = n // p and the result is: 93089. Below is the image of the interaction with the challenge:
The next challenge is presented in the image below:
Third challenge:
This challenge is different, in this case, it seems that it is indeed possible just not feasible. Why is that? This is the case because we have a very huge n value, in this case, it has 2049 length when converted to binary, which is very huge, and to be able to find q and p we would have to find two prime numbers that can result in this n and the truth is that no algorithm can make this happen in a reasonable amount of time. So the answer here is “No”.
Next:
Fourth challenge:
In this challenge, we are given q and p and we are asked to give the value of totient(n). This is quite simple to solve considering that after search a little bit I was able to find out that:
totient(n) = (p – 1) * (q – 1)
So, what I did was I opened my Python 3 script once again and I simply performed the calculation, and the result is: 836623060. Below you can see the interaction:
Fifth challenge:
In this challenge we have the plain-text, the 3 and the n, and it is required that we cipher text. To do all we have to do is apply the following formula:
ciphertext = (plaintext^e) mod n
Basically ciphertext equals the (plain text to the power of e) to the module of n. I, once again, created a python 3 script that made the calculations for me, the result is: 256931246631782714357241556582441991993437399854161372646318659020994329843524306570818293602492485385337029697819837182169818816821461486018802894936801257629375428544752970630870631166355711254848465862207765051226282541748174535990314552471546936536330397892907207943448897073772015986097770443616540466471245438117157152783246654401668267323136450122287983612851171545784168132230208726238881861407976917850248110805724300421712827401063963117423718797887144760360749619552577176382615108244813. See interaction below:
Sixth challenge:
In this challenge, we are given the ciphertext, the e and the n and we are asked if we can get the plaintext. Well, to be able to get the plaintext we would need to know d. Considering that it is not given, we can try to calculate it. To calculate it we would need to know q and p. We are not given q nor p, so in this case, it is not possible to solve this, the answer is “No”.
Seventh challenge:
In this challenge we are given q, p and e and we are asked for d. Well, to be able to find d, we can use the modular multiplicative inverse of the following formula:
d = inverse_mod(e, (p – 1)*(q – 1))
I decided once again to use python 3, in particular the function inverse of the Crypto.Util.number. I decided to use this function because it reverse the mod operation. The result of d is: 1405046269503207469140791548403639533127416416214210694972085079171787580463776820425965898174272870486015739516125786182821637006600742140682552321645503743280670839819078749092730110549881891271317396450158021688253989767145578723458252769465545504142139663476747479225923933192421405464414574786272963741656223941750084051228611576708609346787101088759062724389874160693008783334605903142528824559223515203978707969795087506678894006628296743079886244349469131831225757926844843554897638786146036869572653204735650843186722732736888918789379054050122205253165705085538743651258400390580971043144644984654914856729. See interaction below:
Eighth challenge:
We are now in the 8th challenge! In this one, we are given the p, ciphertext, e, and n, and we are required to give the plaintext. To tackle this exercise I decided to use the formula of the previous challenge to be able to get d. We need to find d because the formula to perform the decryption is the following:
plaintext = (ciphertext)^d mod n
And we know that:
d = inverse_mod(e, (p – 1)*(q – 1))
So what I did was first find
d which is:
22034129334251191532436631052427142022088744911087428294376533303549714947731798818325604737385904031714383011477708757017443918217594934051491731465975983129741023155187658874730504062262863677059204116473042418196655483682312571059072267891580301964167098006533984400230039789561227549336513668349914598133972091774519248676772440875769025772999278219313806132022105603602125065517276257780089695487263525233311631530270816107086663522684249560931634897706468898520986823978521565593553989544219514141658868117625286137870896148765109851519254459305427251830096270116145359667655034114642356864731801259263519426097
Knowing d it is easy to get the plaintext, I just have to use the formula described above. To do so I use Python 3 and the result is: 14311663942709674867122208214901970650496788151239520971623411712977120586163535880168563325. See interaction below:
It seems that we do not yet have the flag!! We are given the message:
If you convert the last plaintext to a hex number, then ascii, you’ll find what you need! 😉
Conversion challenge:
It seems that we have to convert the response of the previous challenge to ASCII. We first have to convert from decimal to hexadecimal and then to ASCII. For that, I opened created a simple script in python 3 once again.
And the flag is:
picoCTF{wA8_th4t$_ill3aGal..ode01e4bb}
Show flag
picoCTF{wA8_th4t$_ill3aGal..ode01e4bb}
The code can be found here.
Thank you very much for reading!
Cheers,
MRegra
Share this post:
Popular posts
Like this:
Like Loading...
I simply couldn’t leave your web site before suggesting that I actually
enjoyed the standard information an individual provide in your
guests? Is going to be back frequently to inspect new posts
Greetings! This is my first visit to your blog!
We are a collection of volunteers and starting a new project in a
community in the same niche. Your blog provided us beneficial information to
work on. You have done a extraordinary job!