Summary
RSA, but done 1024 times in a loop! This challenge requires understanding how the primes were generated in the main challenge script to create an efficient solution for factoring down all 1024 public keys, then decrypting, until we get back to the original flag.
Initial Analysis
from secrets import FLAG
from Crypto.Util.number import bytes_to_long, getPrime
from sympy import nextprime
E = 65537
LOOPS = 1024
keysize = 512
pt = bytes_to_long(FLAG)
for i in range(0,LOOPS):
#print(f"pt {i}: {pt}")
p = getPrime(keysize)
q = nextprime(p)
n = p*q
print(f"n {i}: {n}")
ct = pow(pt, E, n)
pt = ct
keysize+=1
if i == LOOPS - 1:
print(f"ct {i}: {ct}")
Reviewing the challenge code we see that an initial flag is turned into a number, p is generated as a 512 bit prime, and then q is chosen to be the next prime after p. These are used to encrypt pt with an e of 65537 (this is standard). After doing that once, the ciphertext is then encrypted again, but with a 513 bit p, and so on, until 1024 iterations are completed. The program outputs each of the public keys in this series, but only gives us the final ciphertext, meaning we have to factor and decrypt every layer of the encryption.
Reviewing output.txt, we see that we’re given the output of a run of the program, as expected, with only the final ct present.
...
n 1022: 132076419000769603717784893450626000723259992349469677525717795995528508967273773642449176589937365413512656856073213660192756074689786067404838814495509486076315127815330366309495452505865074285741159741995256967035753306638986968387990147136876800879157927968775010341256695572612266437833733774801800768061757011891239953328003395686745635920447495124936492139347174646992806299003375722372109734699440167581640770963740105110670455733626391802222159440122808944866307651231731572709341871237797285403682992573808669562487019112231888793779799456547365583799669025172332042942591826147598625412552302981218851015710200643064221379077826848585814544144977960003327346978914196710646654337762676940119558349849816496600019792755203494446509457480886261109238951113871313857818740591401357520994857355223967680857497170536721444096629305782933685186042564326599072832429623437868576922057084666009811618096112414995265451469
n 1023: 1267919874988366294824754036502102253839007260324431994159563506150527737933721534242973396801528291782062435156001060576106259511187851542673154260334449420573811437511601222626257814850849868036401038254780655406667342662783075675279348081527412407589891876965829954443294919002205278574238340766902606903158754281519494495397829601214540036573007092747269897782321207910274243316347055831965232371918023374086760818426747875311906362251077679481154945695895158664896692153216729025599558239510433848932913871051008234150319960025234545082490863672396770851851918839344920597177301535559330640371198784781384359811154106580798863751965711939656904877044064901234472152935884199640782746451197646516806025000456914468223373262814803272461933323590514938198921544799815384261380125390232828732845529684619654493045148743805154302299521722285312469243036133945037149086165761003738705967996780136020932374602666380997736858769
ct 1023: 1250021393696525786335144361256414392593842741899479026585356065981817277181288068914492467448549175876062630331679179355487465372606959563984767504620720255739774332272265642671917705941701114225469036166567594052827968764499243560382703470425820431311019975034026645239723973080187014930125726065276819489811844274205868050933689117304876596915537920549094830768541674984384367985548037483091618223908344579452561631433297832894343244227860114298682044575901262345754528530201542566101805629757559712992093692264025791932530650085361520370720560897345946878375718294804530566609217693927191949845442274139788083823261127745109253437341146676011790218622001363252912102009978815070618838677527704373445935401007981220691357785265074004747715150454051491489944469565489921680045495525795924651018931270447789984693706499550173787891272109393797400115911729509755305600161994934603465525212582074265397044150982115224461467939
Prime Selection Weakness
Because we need to factor 1024 semi-primes, with bit-lengths up to 1536, we need an efficient way to factor this generation algorithm. Thankfully, instead of picking two secure or at least random primes for p and q, p and q are related so that q is the next prime after p. This effectively means that p will be the first prime before the square root of n, and q will be the first prime after the square root of n. This gives us an extremely efficient factorization method we can use:
def factor_n(n):
sqrt_n = isqrt(n)
q = nextprime(sqrt_n)
if n % q == 0:
p = n // q
if isprime(p):
if isprime(q):
return p, q
raise ValueError("Failed to factor n")
Looping Solution
With factorization complete, all that’s left is to read the values into a solve script, and loop the decryption backwards from the final ct – n pair, feeding the pt into the prior public key to continue the decryption loop.
from Crypto.Util.number import long_to_bytes
from sympy import isprime, nextprime
from math import isqrt
def read_output_file(file_path):
with open(file_path, 'r') as file:
data = file.read()
return data
def extract_values(data):
n_values = []
ct_value = None
for line in data.splitlines():
if line.startswith('n '):
n_values.append(int(line.split(': ')[1]))
elif line.startswith('ct '):
ct_value = int(line.split(': ')[1])
return n_values, ct_value
def factor_n(n):
sqrt_n = isqrt(n)
q = nextprime(sqrt_n)
if n % q == 0:
p = n // q
if isprime(p):
if isprime(q):
return p, q
raise ValueError("Failed to factor n")
def decrypt(ct, p, q, e=65537):
from Crypto.Util.number import inverse
n = p * q
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
pt = pow(ct, d, n)
return(pt)
def main():
data = read_output_file('output.txt')
n_values, ct_value = extract_values(data)
for n in reversed(n_values):
print(f"decrypting ct {ct_value} with n {n}")
p, q = factor_n(n)
pt = decrypt(ct_value, p, q)
#print(f"Decrypted message: {pt}")
ct_value = pt # Use the decrypted message as the new ciphertext for the next iteration
print(long_to_bytes(pt))
if __name__ == "__main__":
main()
Running the solution gives us the flag!
...
decrypting ct 340634711211243138433805580617347894095865165430674334413626074027556804221183006816828654255867623604787345483479892929805924063831838506949958802541984205970677463387071104721856773661344795329551283820408890318206198995615068385607634859111321801911320028153753834682864346617047095353372373698749901666604 with n 1559230717146436704258126658878594303835854678919760985172436714506910746263901891106710743493961990464628191090502846776956568264866565700228335235919370966430208637927737297040638052365863727774078564524547976902060128879221804567894768562590230275602281461418831077416735526836794895469692918002247920633673
decrypting ct 253253539302891215810266167225267394303424306965068593473421758678485872399935017872998778767804441774325520684867947077287062621101778539733577852908255738587490681598318097170680881362729996393744636912644522034899176149779375758346381803575071579492461334545276902896519586743912055514994318443054733966207 with n 420074976683378657854469830084952452166331743473055570014564677217278678109354411673745923344406469209476033895602263472721449067395081686757235932197766820144127698660254630004481280733415500804393235136927892534076667879707641538667404654805572048375580943632117170785312674084495314753014227063390393253971
decrypting ct 14074926983573487397213869369194024763563205366479274620231056693662965728624340517439249530599306310741608544050713120492806626504004805406153906592593934111037539180059514886668736478556630674313433032766472850388516457369887080817248906755989660032714667461880616863156235935710696807899434658983991998604 with n 58925408247237150718853020288660614964885937087443374494748117153321454897494106350365153437207431995046188449566482398926564680325766021705291969671142407537893105626964976326911173444535099436796060713319386867699316931662339127118126085249539191718287895359339838418358971997170530525806189319780925594989
b'MetaCTF{g0t_d0wn_7o_7h3_root_0f_th3_lo0py_pr1mes}'
Flag
MetaCTF{g0t_d0wn_7o_7h3_root_0f_th3_lo0py_pr1mes}