Published on

BlueHensCTF 2023 - RSA School 6th Grade

Authors

RSA School 6th Grade

Table of Contents

  1. Source
  2. Solution

Source

Sixth_Grade.py file content :

from Crypto.Util.number import *
msg=b'UDCTF{REDACTED}'
pt=bytes_to_long(msg)
p1=getPrime(512)
q1=getPrime(512)
N1=p1*q1
e=3
ct1=pow(pt,e,N1)
p2=getPrime(512)
q2=getPrime(512)
N2=p2*q2
ct2=pow(pt,e,N2)
p3=getPrime(512)
q3=getPrime(512)
N3=p3*q3
ct3=pow(pt,e,N3)

print(N1)
print(N2)
print(N3)
print(e)
print(ct1)
print(ct2)
print(ct3)

output.txt file content :

101940404683148314092182537619741343820471969843093690407029610257328675616822058283838769182645366824344399515353353819793130816183060658423485619280610405015820030833852427722839904501250467628712096873390329778269768535928267751268139550847537802558918336829638018104196299204412108446654522040961058235837
74679681433630870500800762600180557065015193875421351446542706780716176492497162177418083881145442405798180136972926938569891311549925115691841878743075457971612412284596645067679716265041006557964732304139958791707676819596277816749996790403481863920999497042537177685582328973044036057708799002206799632839
100573737146541590945636341222262486942630621101299107026796895085532038383427686351121611043174306351150423506465657822449930435454418298186213727217811586553728175753616475183671899770943244241792060489168334224998929407994655190387844505675391919259886074847030882822522665949478946576261271617560351054403
3
97537343779229625148677027056474609247558991142314164186990731381686200271313205873978331513371958006472814729940790278407051941118054050488898727496970346225390695886636503944561906013129123265026309468439899500515120214095795129355317613702699593668666568316953844138511954955909885841485099479889646390930
24576278220067271066994467924629810459250013881000033163294269449098813322523936249035902376053018982711870235427255440433329932427389544039567565669233834485029769359372962513511622515998222609323796238896382805118053092524445414371375283464954274992561033256478865903093200523624090555295195503883373690124
43498624182782877233366661188600199251806006111187593264150806660094635602066978958889784097119800185861182106644332729447880775766543596889805536568073520124279816397528293711624036420976245584445797246515447058638137236091247562611424573156889579663131251891077714114495493898633857254453469780722026012280

Solution 

import gmpy2
from Crypto.Util.number import long_to_bytes

# Given data

N1 = 101940404683148314092182537619741343820471969843093690407029610257328675616822058283838769182645366824344399515353353819793130816183060658423485619280610405015820030833852427722839904501250467628712096873390329778269768535928267751268139550847537802558918336829638018104196299204412108446654522040961058235837
N2 = 74679681433630870500800762600180557065015193875421351446542706780716176492497162177418083881145442405798180136972926938569891311549925115691841878743075457971612412284596645067679716265041006557964732304139958791707676819596277816749996790403481863920999497042537177685582328973044036057708799002206799632839
N3 = 100573737146541590945636341222262486942630621101299107026796895085532038383427686351121611043174306351150423506465657822449930435454418298186213727217811586553728175753616475183671899770943244241792060489168334224998929407994655190387844505675391919259886074847030882822522665949478946576261271617560351054403
e = 3
ct1 = 97537343779229625148677027056474609247558991142314164186990731381686200271313205873978331513371958006472814729940790278407051941118054050488898727496970346225390695886636503944561906013129123265026309468439899500515120214095795129355317613702699593668666568316953844138511954955909885841485099479889646390930
ct2 = 24576278220067271066994467924629810459250013881000033163294269449098813322523936249035902376053018982711870235427255440433329932427389544039567565669233834485029769359372962513511622515998222609323796238896382805118053092524445414371375283464954274992561033256478865903093200523624090555295195503883373690124
ct3 = 43498624182782877233366661188600199251806006111187593264150806660094635602066978958889784097119800185861182106644332729447880775766543596889805536568073520124279816397528293711624036420976245584445797246515447058638137236091247562611424573156889579663131251891077714114495493898633857254453469780722026012280

# Apply the Chinese Remainder Theorem to obtain a ciphertext under a combined moduli

N = N1 * N2 * N3
C = (ct1 * (N // N1) * pow(N // N1, -1, N1) +
     ct2 * (N // N2) * pow(N // N2, -1, N2) +
     ct3 * (N // N3) * pow(N // N3, -1, N3)) % N

# Get cube root of combined ciphertext

m_cube, exact = gmpy2.iroot(C, e)
if not exact:
    print("Exact cube root not found, attack failed !")
else:
    message = long_to_bytes(int(m_cube))
    print(message)

Flag : UDCTF{ch1n3se_r3m4ind3r_th30r3m_f0r_th4_w1n!}