Writeups

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!