Cool RSA crypto challenge in a CTF that I had a lot of fun with. I especially liked the beginner section which had a nice gradual ramp up with challenge difficulty. The final beginner challenge in each category was like a combo of what you had done until that point.
This challenge reads:
So I was trying to return the stolen archives securely, but it seems that I had
to return them one at a time, and now it seems the thieves stole them back! Can
you help recover them once and for all? It seems they had to steal them one at
a time...
Hint! Well you sure as hell ain't going to solve this one through factorization.
With the challenge we get these files:
- intercepted.txt
- returningstolenarchives.py
The intercepted.txt contains long integers that look like an RSA key and some ciphertext:
n = 54749648884874001108038301329774150258791219273879249601123423751292261798269586163458351220727718910448330440812899799
e = 65537
ct = [52052531108833646741308670070505961165002560985048445381912028939564989677616205955826911335832917245744890104862186090,24922951057478302364724559167904980705887738247412638765127966502743153757232333552037075100099370197070290632101808468,31333127727137796897042309238173536507191002247724391776525004646835609286736822503824661004274731843794662964916495223,37689731986801363765434552977964842847326744893755747412237221863834417045591676371189948428149435230583786704331100191,10128169466676555996026197991703355150176544836970137898778443834308512822737963589912865084777642915684970180060271437,31333127727137796897042309238173536507191002247724391776525004646835609286736822503824661004274731843794662964916495223,32812400903438770915197382692214538476619741855721568752778494391450400789199013823710431516615200277044713539798778715,48025916179002039543667066543229077043664743885236966440148037177519549014220494347050632249422811334833955153322952673,52052531108833646741308670070505961165002560985048445381912028939564989677616205955826911335832917245744890104862186090,32361547617137901317806379693272240413733790836009458796321421127203474492226452174262060699920809988522470389903614273,4363489969092225528080759459787310678757906094535883427177575648271159671231893743333971538008898236171319923600913595,47547012183185969621160796219188218632479553350320144243910899620916340486530260137942078177950196822162601265598970316,32361547617137901317806379693272240413733790836009458796321421127203474492226452174262060699920809988522470389903614273,33230176060697422282963041481787429356625466151312645509735017885677065049255922834285581184333929676004385794200287512,32315367490632724156951918599011490591675821430702993102310587414983799536144448443422803347161835581835150218650491476,6693321814134847191589970230119476337298868688019145564978701711983917711748098646193404262988591606678067236821423683,32710099976003111674253316918478650203401654878438242131530874012644296546811017566357720665458366371664393857312271236,49634925172985572829440801211650861229901370508351528081966542823154634901317953867012392769315424444802884795745057309,50837960186490992399835102776517955354761635070927126755411572132063618791417763562399134862015458682285563340315570436]
The python script looks to be how the encryption was performed minus some of the important bits like the primes:
p = [redacted]
q = [redacted]
e = 65537
flag = "[redacted]"
def encrypt(n, e, plaintext):
print("encrypting with " + str(n) + str(e))
encrypted = []
for char in plaintext:
cipher = (ord(char) ** int(e)) % int(n)
encrypted.append(cipher)
return(encrypted)
n = p * q
ct = encrypt(n, e, flag)
print(ct)
So I spent a while messing around and ignoring the ciphertext. The modulus (N) in the RSA key is 394 bits long. A bit too long to factor within the time we had. I tried some common attacks I’m used to seeing in CTFs but nothing worked right away.
I refocused back onto the ciphertext. There sure were a lot of them. I started wondering what kinds of attacks we can use when we’ve got a single modulus with multiple ciphertexts. This ran me around in circles for a while.
Finally I decided to re-read the clue and re-read the Python code and it became
obvious. They were actually encrypting the flag one single byte at a time. RSA
is deterministic and when I encrypt the letter r with a public key I always
get the same output.
So all I needed to do was run a brute force for each ASCII printable character that might appear in a plaintext through this public key and see if the encrypted output match the ciphertexts we have.
I reused the given code to come up with:
import string
cts = [52052531108833646741308670070505961165002560985048445381912028939564989677616205955826911335832917245744890104862186090,24922951057478302364724559167904980705887738247412638765127966502743153757232333552037075100099370197070290632101808468,31333127727137796897042309238173536507191002247724391776525004646835609286736822503824661004274731843794662964916495223,37689731986801363765434552977964842847326744893755747412237221863834417045591676371189948428149435230583786704331100191,10128169466676555996026197991703355150176544836970137898778443834308512822737963589912865084777642915684970180060271437,31333127727137796897042309238173536507191002247724391776525004646835609286736822503824661004274731843794662964916495223,32812400903438770915197382692214538476619741855721568752778494391450400789199013823710431516615200277044713539798778715,48025916179002039543667066543229077043664743885236966440148037177519549014220494347050632249422811334833955153322952673,52052531108833646741308670070505961165002560985048445381912028939564989677616205955826911335832917245744890104862186090,32361547617137901317806379693272240413733790836009458796321421127203474492226452174262060699920809988522470389903614273,4363489969092225528080759459787310678757906094535883427177575648271159671231893743333971538008898236171319923600913595,47547012183185969621160796219188218632479553350320144243910899620916340486530260137942078177950196822162601265598970316,32361547617137901317806379693272240413733790836009458796321421127203474492226452174262060699920809988522470389903614273,33230176060697422282963041481787429356625466151312645509735017885677065049255922834285581184333929676004385794200287512,32315367490632724156951918599011490591675821430702993102310587414983799536144448443422803347161835581835150218650491476,6693321814134847191589970230119476337298868688019145564978701711983917711748098646193404262988591606678067236821423683,32710099976003111674253316918478650203401654878438242131530874012644296546811017566357720665458366371664393857312271236,49634925172985572829440801211650861229901370508351528081966542823154634901317953867012392769315424444802884795745057309,50837960186490992399835102776517955354761635070927126755411572132063618791417763562399134862015458682285563340315570436]
n = 54749648884874001108038301329774150258791219273879249601123423751292261798269586163458351220727718910448330440812899799
e = 65537
def encrypt(n, e, plaintext):
encrypted = []
for char in plaintext:
cipher = pow(ord(char), e, n)
encrypted.append(cipher)
return(encrypted)
flag = ""
for c in cts:
for p in string.printable:
candidate = encrypt(n, e, p)[0]
if candidate == c:
flag += p
break
print flag
Which worked first go for the flag:
$ python returningstolenarchives.py
rtcp{cH4r_bY_Ch@R!}