0x41414141 CTF: Crypto: factorize (400)

This is from the 0x41414141 CTF by Soul.

For this challenge, we are provided with a c value, n value, and a python script.

c: 17830167351685057470426148820703481112309475954806278304600862043185650439097181747043204885329525211579732614665322698426329449125482709124139851522121862053345527979419420678255168453521857375994190985370640433256068675028575470040533677286141917358212661540266638008376296359267047685745805295747215450691069703625474047825597597912415099008745060616375313170031232301933185011013735135370715444443319033139774851324477224585336813629117088332254309481591751292335835747491446904471032096338134760865724230819823010046719914443703839473237372520085899409816981311851296947867647723573368447922606495085341947385255

n: 23135514747783882716888676812295359006102435689848260501709475114767217528965364658403027664227615593085036290166289063788272776788638764660757735264077730982726873368488789034079040049824603517615442321955626164064763328102556475952363475005967968681746619179641519183612638784244197749344305359692751832455587854243160406582696594311842565272623730709252650625846680194953309748453515876633303858147298846454105907265186127420148343526253775550105897136275826705375222242565865228645214598819541187583028360400160631947584202826991980657718853446368090891391744347723951620641492388205471242788631833531394634945663
import binascii
import random
from Crypto.Util.number import isPrime

flag = open("flag.txt", "rb").read().strip()
m = int(binascii.hexlify(flag), 16)

def genPrimes(size):
    base = random.getrandbits(size // 2) << size // 2
    base = base | (1 << 1023) | (1 << 1022) | 1
    while True:
        temp = base | random.getrandbits(size // 2)
        if isPrime(temp):
            p = temp
            break
    while True:
        temp = base | random.getrandbits(size // 2)
        if isPrime(temp):
            q = temp
            break
    return (p, q)

p, q = genPrimes(1024)
n = p * q
e = 0x10001

print("c:", pow(m, e, n))

Based on the provided values and script, this appears to be an RSA type challenge.

I got to https://www.alpertron.com.ar/ECM.HTM to get the possible primes for the provided n value. There are only two:

1521152103631606164757991388657189704366976433537820099034648874538500153362765519668135545276650144504533686483692163171569868971464706026329525740394016509185464641520736454955410019736330026303289754303711165526821866422766844554206047678337249535003432035470125187072461808523973483360158652600992259609986591
and
152103631606164757991388657189704366976433537820099034648874538500153362765519668135545276650144504533686483692163171569868971464706026329525740394016509191077550351496973264159350455849525747355370985161471258126994336297660442739951587911017897809328177973473427538782352524239389465259173507406981248869793

I iterate these in a script to calculate phi:

primes = [152103631606164757991388657189704366976433537820099034648874538500153362765519668135545276650144504533686483692163171569868971464706026329525740394016509185464641520736454955410019736330026303289754303711165526821866422766844554206047678337249535003432035470125187072461808523973483360158652600992259609986591, 152103631606164757991388657189704366976433537820099034648874538500153362765519668135545276650144504533686483692163171569868971464706026329525740394016509191077550351496973264159350455849525747355370985161471258126994336297660442739951587911017897809328177973473427538782352524239389465259173507406981248869793]

phi = 1
for p in primes:
  phi *= (int(p) - 1)

Based on the e value (e = 0x10001 = 65537) from the provided python script, I calculate d:

e = 65537
d = inverse(e,phi)

I then use the power function with the calculated d value and provided c and n values to get the plaintext value (which gets converted from long to bytes):

plaintext = pow(c,d,n)
print(long_to_bytes(plaintext))

This chunks out our flag:

The full python script:

from Crypto.Util.number import inverse, long_to_bytes

primes = [152103631606164757991388657189704366976433537820099034648874538500153362765519668135545276650144504533686483692163171569868971464706026329525740394016509185464641520736454955410019736330026303289754303711165526821866422766844554206047678337249535003432035470125187072461808523973483360158652600992259609986591, 152103631606164757991388657189704366976433537820099034648874538500153362765519668135545276650144504533686483692163171569868971464706026329525740394016509191077550351496973264159350455849525747355370985161471258126994336297660442739951587911017897809328177973473427538782352524239389465259173507406981248869793]

e = 65537

c = 17830167351685057470426148820703481112309475954806278304600862043185650439097181747043204885329525211579732614665322698426329449125482709124139851522121862053345527979419420678255168453521857375994190985370640433256068675028575470040533677286141917358212661540266638008376296359267047685745805295747215450691069703625474047825597597912415099008745060616375313170031232301933185011013735135370715444443319033139774851324477224585336813629117088332254309481591751292335835747491446904471032096338134760865724230819823010046719914443703839473237372520085899409816981311851296947867647723573368447922606495085341947385255

n = 23135514747783882716888676812295359006102435689848260501709475114767217528965364658403027664227615593085036290166289063788272776788638764660757735264077730982726873368488789034079040049824603517615442321955626164064763328102556475952363475005967968681746619179641519183612638784244197749344305359692751832455587854243160406582696594311842565272623730709252650625846680194953309748453515876633303858147298846454105907265186127420148343526253775550105897136275826705375222242565865228645214598819541187583028360400160631947584202826991980657718853446368090891391744347723951620641492388205471242788631833531394634945663

phi = 1

for p in primes:
  phi *= (int(p) - 1)
d = inverse(e,phi)

plaintext = pow(c,d,n)

print(long_to_bytes(plaintext))

Thank you for the challenge!

Shadow CTF: Misc: Tesseract (350)

This is from the Shadow CTF.

Disclaimer: I did this challenge quick and dirty in order to get first blood.

For this challenge, we are told that there is a program that can decrypt the flag for us using the right password. The password is a number between 16000 and 20000. We are provided a zip file containing an ELF binary (numgen)and another zip file that contains a bunch of small images. These images are named 0.png … 39.png. They are pictures of random letters, numbers, and characters.

Running the executable I am told it wants a number argument.

I provide a number (1600) and get a series of numbers as a response.

Looking at the image file names with relation to the numbers in the response, I see it translates to gibberish. I can make an educated guess that the flag should end with a “}”, which is 39.png and the the first character should be an “S” (7.png) or an “F” (32.png) based on the CTF flag format.

Using this method, I can write a script to try all possibilities from 16000 to 20000 (4000 possibilities).

#!/bin/bash
for i in {16000..20000}
do
  ./numgen $i
done

I can run the script and output the results to a file. Yes, a more elegant solution could be crafted that would grep for the right results, but it is only a 24-hour CTF.

/runnum.sh > numgenout.txt

The output file contains 8,000 lines (the resulting numbers and the “Randomizing names of images …” string.

7 5 8 39 11 33 33 33 23 6 8 21 38 36 38 14 9 20 24 
Randomizing names of images ... 
5 8 39 11 33 33 33 23 6 17 8 38 36 38 14 9 20 24 18 
Randomizing names of images ... 
8 39 11 33 33 33 23 6 17 21 8 36 38 14 9 20 24 18 27 
Randomizing names of images ... 
39 11 33 33 33 23 6 17 21 38 8 38 14 9 20 24 18 27 17 
Randomizing names of images ... 
11 33 33 33 23 6 17 21 38 36 8 ................................

Quick and dirty I copy the lines into excel (yeah, I know) and drop all cells containing the “Randomizing names of images …” string.

I create a quick formula to get the 1 or two digit number before the first space in the cell and then throw it in the “B” column.

=LEFT(A1,(FIND(" ",A1,1)-1))

A quick filter to only show the cells that start with 7 or 32 (S or F), and I get 189 cells.

I then do a quick filter using “ends with” and use 18 (“}”) as the criteria.

That narrows it down to 9 possible cells.

I now look for the second letter based on my assumption that the first word is “shadow” or “flag”. The numbers should be either 6, 4, or 31 (there are two “L” images).I do this with another filter.

It gives me only one result:

A quick and dirty translation using the images gives me the flag:

SHADOWCTF{W3LLD0N3}

After submitting the flag for first blood, I make an HTML file to make the flag look pretty:

<html>
<head><title>Gimmie The Flag</title></head>
<body>
<center>
<p>7 6 22 13 34 8 17 0 32 39 8 19 4 31 30 25 2 14 18</p>
<p><img src="7.png"><img src="6.png"><img src="22.png"><img src="13.png"><img src="34.png"><img src="8.png"><img src="17.png"><img src="0.png"><img src="32.png"><img src="39.png"><img src="8.png"><img src="19.png"><img src="4.png"><img src="31.png"><img src="30.png"><img src="25.png"><img src="2.png"><img src="14.png"><img src="18.png"></p>
</center>
</body>
</html>