Sun Zi's Perfect Math Class

Description

Everybody!! Sunzi's math class is about to begin!!!

Author: wednesday

#url to play
https://crypto-sunzi-perfect-math-class-6c3d583b3a73.2024.ductf.dev

Upon visting the website we get this,

Sun Zi's Perfect Math Class

In 200 BC, the Chinese general Han Xin marched into battle with 1500 soldiers. Afterwards, he could estimate that between 1000 and 1100 of them survived the battle, but needed to know exactly how many men he had.

At that moment, Han Xin's steward came up to his side and said

When the soldiers stand 3 in a row, there are 2 soldiers left over. When they line up 5 in a row, there are 4 soldiers left over. When they line up 7 in a row, there are 5 soldiers left over.

Upon hearing this, Han Xin knew immediately how many soldiers he had remaining.

How many soldiers did Han Xin have remaining?

Soln

for x in range(1000, 1101):
    if x % 3 == 2 and x % 5 == 4 and x % 7 == 5:
        print(x)
# answer - 1034

Part 2 - (rsa lol)

Soln

from sympy import mod_inverse, integer_nthroot
from Crypto.Util.number import long_to_bytes

# Given values
n1 = 147896270072551360195753454363282299426062485174745759351211846489928910241753224819735285744845837638083944350358908785909584262132415921461693027899236186075383010852224067091477810924118719861660629389172820727449033189259975221664580227157731435894163917841980802021068840549853299166437257181072372761693
n2 = 95979365485314068430194308015982074476106529222534317931594712046922760584774363858267995698339417335986543347292707495833182921439398983540425004105990583813113065124836795470760324876649225576921655233346630422669551713602423987793822459296761403456611062240111812805323779302474406733327110287422659815403
n3 = 95649308318281674792416471616635514342255502211688462925255401503618542159533496090638947784818456347896833168508179425853277740290242297445486511810651365722908240687732315319340403048931123530435501371881740859335793804194315675972192649001074378934213623075830325229416830786633930007188095897620439987817

c1 = 105001824161664003599422656864176455171381720653815905925856548632486703162518989165039084097502312226864233302621924809266126953771761669365659646250634187967109683742983039295269237675751525196938138071285014551966913785883051544245059293702943821571213612968127810604163575545004589035344590577094378024637
c2 = 31631442837619174301627703920800905351561747632091670091370206898569727230073839052473051336225502632628636256671728802750596833679629890303700500900722642779064628589492559614751281751964622696427520120657753178654351971238020964729065716984136077048928869596095134253387969208375978930557763221971977878737
c3 = 64864977037231624991423831965394304787965838591735479931470076118956460041888044329021534008265748308238833071879576193558419510910272917201870797698253331425756509041685848066195410586013190421426307862029999566951239891512032198024716311786896333047799598891440799810584167402219122283692655717691362258659

# Calculate N
N = n1 * n2 * n3

# Calculate N1, N2, N3
N1 = N // n1
N2 = N // n2
N3 = N // n3

# Calculate the modular inverses y1, y2, y3
y1 = mod_inverse(N1, n1)
y2 = mod_inverse(N2, n2)
y3 = mod_inverse(N3, n3)

# Use the Chinese Remainder Theorem to find x
x = (c1 * N1 * y1 + c2 * N2 * y2 + c3 * N3 * y3) % N

# Take the cube root of x
m, exact = integer_nthroot(x, 3)
flag = long_to_bytes(m).decode()

print(flag)

Flag

DUCTF{btw_y0u_c4n_als0_us3_CRT_f0r_p4rt14l_fr4ct10ns}