Brute#
No need fancy crypto trick just brute, and btw you have to spin up to 20 vms with multi-thread to make it fast enough.
Pada challenge ini kita diberi dua file, satu berisi cipher dan satu kode how to cipher.
from Crypto.Util.number import getStrongPrime
m = int.from_bytes("IFEST13{???}".encode())
p = getStrongPrime(1024)
q = getStrongPrime(1024)
n = p * q
print(f'{pow(m, 0x10001, n)}\n{n}\n{p >> 40}')Kodenya cukup simple, but the reversing not so easy. Hal yang jelas, kita harus recover n, p, dan q buat dapetin m. p yang kita punya bukan p asli karena p yang kita punya kehilangan 40 bit karena shift ke kanan, anggap p nya adalah p_high, maka p = p_high * 2^40 + x, di mana x adalah 40 bit yang hilang. Nah buat cari x, kita bisa pake coppersmith method pake tools dari sagemath, yaitu small_roots.
Jadi x sudah dapat, berarti p = p_high * 2^40 + x juga udah dapat, otomatis q juga dapat karena n = p * q <=> q = n / p. Assekkk dah dapat semua, kita bisa dapetin m dengan informasi tadi berdasarkan persamaan ini:
from sage.all import *
# Given values
c = 10190308328132298810370792830407498649727116694895887482897571470790876671909417379902577324803848850655954471082089060952194185721425541632970106409477409460179454591137511596832421737353754768175974443794887211632429320728354925107321000890255988379005072889707213292319847199584075893238735146835736979402380614028245390503793552296747076984394930725251632591625471426901314091323869057780461687871597918704838734422002502048443745431116004254026457663052173884656414629831184831431248595040967979335625485086150017379359647307566607127100190320972594606082853976569219798608787775461446205014804326191379628416459
n = 22052867210059985056723988324723437469643935229284382742545572507193384098102119262228001598529023654073757846310755124262636633869347982051002191511240379141051585596043583392443536537486511985566413114358501620593150325155980714427378089922768898334419054390129931556129883835862579370606862267536439488040273973837168042166190169509259514869605813849934412879327376082076832835805173922914432614662509276644729233158638994237998916272949330215708015931366306430206836771702005645140291164351968902134211930508335582704492675362575695821618037439189132191250206861088835015459823510074661891457866577589023776648751
p_high = 138398228938242977290956349154712526327465608129677172002562239407676097284597892604642541735116262199110899389173013415023231356739796256927576905061498760222434453315905920861684849512303589509164929424151033355318032546176479325956586655296074717479220347079941178337950508153135271887365359007
a = p_high * (2**40) # Reconstruct p_high << 40
R = PolynomialRing(Zmod(n), names=('x',))
x = R.gen()
f = x + a
# Find small roots using Coppersmith's method
x0 = f.small_roots(beta=0.33)
x0 = int(x0[0])
p = a + x
if n % p == 0:
q = n / p
e = 0x10001
phi = (p - 1) * (q - 1)
d = inverse_mod(e, phi)
m = pow(c, d, n)
byte_length = (m.bit_length() + 7) // 8
flag_bytes = m.to_bytes(byte_length, 'big')
try:
flag = flag_bytes.decode()
print(flag)
except UnicodeDecodeError:
print("Flag: ", flag_bytes.hex())