Original Writeup on seall.dev

This challenge involves the Chinese Remainder Theorem, and with some help with my teammate we solved this one. I’m not particularly well experienced with any form of cryptography, so I was easily intimidated.

The first portion is the following:

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.

My teammate created some Java code to find the number at the time:

public class Main {
    public static int gimmeHowMany() {
        for (int i = 1000; i <= 1100; i++) {
            if (i % 3 == 2 && i % 5 == 4 && i % 7 == 5) {
                return i;
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        int result = gimmeHowMany();
        if (result != 0) {
            System.out.println("The number is: " + result);
        } else {
            System.out.println("No number found that satisfies the conditions.");
        }
    }
}

Here is a quick Python script I wrote to do the same:

for i in range(1000,1101):
  if (i%3==2 and i%5==4 and i%7==5):
    print(i)

The result for the first section was: 1034.

The second section caused more issues that the first.

The technique Han Xin used is known to us today as the Chinese Remainder Theorem. In the language of modern algebra, we can write the problem as the system of equations.

$ x \equiv 2 \pmod{3} $

$ x \equiv 4 \pmod{5} $

$ x \equiv 5 \pmod{7} $

The notation $ x \equiv y \pmod{n} $ means “the remainder of $ x $ divided by $ n $ is equal to $ y $”. This idea of working with “remainders after division” underpins many of our building blocks for modern cryptography. One of these building blocks is the RSA cryptosystem. Broadly speaking, the RSA cryptosystem takes a secret number $ m $ and turns it into an encrypted number $ c $ by calculating the value

$ c \equiv m^e \pmod{n}. $

Given only the values of $ e $, $ c $ and $ n $, it should be impossible for an attacker to recover the secret message. However something strange happens when $ e $ is small and the same message is sent multiple times using different $ n $. Can you recover the hidden message from the three transmissions below?

$ c_1 \equiv m^e \pmod{n_1} $

$ c_2 \equiv m^e \pmod{n_2} $

$ c_3 \equiv m^e \pmod{n_3} $

where

e = 3

c_1 = 105001824161664003599422656864176455171381720653815905925856548632486703162518989165039084097502312226864233302621924809266126953771761669365659646250634187967109683742983039295269237675751525196938138071285014551966913785883051544245059293702943821571213612968127810604163575545004589035344590577094378024637

c_2 = 31631442837619174301627703920800905351561747632091670091370206898569727230073839052473051336225502632628636256671728802750596833679629890303700500900722642779064628589492559614751281751964622696427520120657753178654351971238020964729065716984136077048928869596095134253387969208375978930557763221971977878737

c_3 = 64864977037231624991423831965394304787965838591735479931470076118956460041888044329021534008265748308238833071879576193558419510910272917201870797698253331425756509041685848066195410586013190421426307862029999566951239891512032198024716311786896333047799598891440799810584167402219122283692655717691362258659

n_1 = 147896270072551360195753454363282299426062485174745759351211846489928910241753224819735285744845837638083944350358908785909584262132415921461693027899236186075383010852224067091477810924118719861660629389172820727449033189259975221664580227157731435894163917841980802021068840549853299166437257181072372761693

n_2 = 95979365485314068430194308015982074476106529222534317931594712046922760584774363858267995698339417335986543347292707495833182921439398983540425004105990583813113065124836795470760324876649225576921655233346630422669551713602423987793822459296761403456611062240111812805323779302474406733327110287422659815403

n_3 = 95649308318281674792416471616635514342255502211688462925255401503618542159533496090638947784818456347896833168508179425853277740290242297445486511810651365722908240687732315319340403048931123530435501371881740859335793804194315675972192649001074378934213623075830325229416830786633930007188095897620439987817

Now, we need to find $ m $, which is the hidden message. Due to the small public expontent $ e $ we can crack the message, also utilising CRT:

from sympy.ntheory.modular import crt
from gmpy2 import iroot

def find_m(c1, c2, c3, n1, n2, n3, e):
    # crt
    x, N = crt([n1, n2, n3], [c1, c2, c3])

    m, exact = iroot(x, e)
    
    if exact:
        return int(m)
    else:
        return None

e = 3
c1 = 105001824161664003599422656864176455171381720653815905925856548632486703162518989165039084097502312226864233302621924809266126953771761669365659646250634187967109683742983039295269237675751525196938138071285014551966913785883051544245059293702943821571213612968127810604163575545004589035344590577094378024637
c2 = 31631442837619174301627703920800905351561747632091670091370206898569727230073839052473051336225502632628636256671728802750596833679629890303700500900722642779064628589492559614751281751964622696427520120657753178654351971238020964729065716984136077048928869596095134253387969208375978930557763221971977878737
c3 = 64864977037231624991423831965394304787965838591735479931470076118956460041888044329021534008265748308238833071879576193558419510910272917201870797698253331425756509041685848066195410586013190421426307862029999566951239891512032198024716311786896333047799598891440799810584167402219122283692655717691362258659
n1 = 147896270072551360195753454363282299426062485174745759351211846489928910241753224819735285744845837638083944350358908785909584262132415921461693027899236186075383010852224067091477810924118719861660629389172820727449033189259975221664580227157731435894163917841980802021068840549853299166437257181072372761693
n2 = 95979365485314068430194308015982074476106529222534317931594712046922760584774363858267995698339417335986543347292707495833182921439398983540425004105990583813113065124836795470760324876649225576921655233346630422669551713602423987793822459296761403456611062240111812805323779302474406733327110287422659815403
n3 = 95649308318281674792416471616635514342255502211688462925255401503618542159533496090638947784818456347896833168508179425853277740290242297445486511810651365722908240687732315319340403048931123530435501371881740859335793804194315675972192649001074378934213623075830325229416830786633930007188095897620439987817

print(find_m(c1, c2, c3, n1, n2, n3, e))

This returns: 11564025922867522871782912815123211630478650327759091593792994457296772521676766420142199669845768991886967888274582504750347133.

Flag: DUCTF{btw_y0u_c4n_als0_us3_CRT_f0r_p4rt14l_fr4ct10ns}