TJCTF2025 writeup (crypto)


## bacon-bits (300 solves / 180 points)

follow the trail of bacon bits...  
flag is all lowercase, with the format of tjctf{...}

```python:enc.py
with open('flag.txt') as f: flag = f.read().strip()
with open('text.txt') as t: text = t.read().strip()

baconian = {
'a': '00000',	'b': '00001',
'c': '00010',	'd': '00011',
'e': '00100',	'f': '00101',
'g': '00110',	'h': '00111',
'i': '01000',    'j': '01000',
'k': '01001',    'l': '01010',
'm': '01011',    'n': '01100',
'o': '01101',    'p': '01110',
'q': '01111',    'r': '10000',
's': '10001',    't': '10010',
'u': '10011',    'v': '10011',
'w': '10100',	'x': '10101',
'y': '10110',	'z': '10111'}

text = [*text]
ciphertext = ""
for i,l in enumerate(flag):
    if not l.isalpha(): continue
    change = baconian[l]
    ciphertext += "".join([ts for ix, lt in enumerate(text[i*5:(i+1)*5]) if int(change[ix]) and (ts:=lt.upper()) or (ts:=lt.lower())]) #python lazy boolean evaluation + walrus operator

with open('out.txt', 'w') as e:
    e.write(''.join([chr(ord(i)-13) for i in ciphertext]))
```
```out.txt
BaV8hcBaTg\`XG[8eXJTfT7h7hCBa4g<`Xg[8EXjTFTWHW8Ba6XHCbATG\`Xg;8eXj4fT7h78bAV8HcBa4G\@XG[XeXJ4fTWHWXBa68hCbA4g<`8G[8e8JTFT7hWXbA6XhcBaTG
```

5桁の二進数に変換する [ベーコン暗号](https://en.wikipedia.org/wiki/Bacon%27s_cipher) を利用した問題。
`out.txt`のASCIIがencodeの際に13ひかれているので戻してあげると

```
OncEupOnatimeThEreWasaDuDuPOnAtImethERewaSadUdEOnCeUPoNaTimetHErewAsaDuDEoNcEUpOnATiMeThereWAsadUdeOnCEuPoNAtImEThErEWaSaDudeoNCeupOnaT
```

ベーコン暗号のdecodeを行う ([tool](https://www.dcode.fr/bacon-cipher)) と

```
tictfoinkooinkoooinkooooink
```

この問題で使用するベーコン暗号はi/j, u/vが同じで記号は無視されるので、フラグ形式を考えて

```
tjctf{oinkooinkoooinkooooink}
```

## alchemist-recipe (300 solves / 180 points)

an alchemist claims to have a recipe to transform lead into gold. however, he accidentally encrypted it with a peculiar process of his own. he left behind his notes on the encryption method and an encrypted sample. unfortunately, he spilled some magic ink on the notes, making them weirdly formatted. the notes include comments showing how he encrypted his recipe. can you find his "golden" secret?

```python:chall.py
import hashlib

SNEEZE_FORK = "AurumPotabileEtChymicumSecretum"
WUMBLE_BAG = 8 

def glorbulate_sprockets_for_bamboozle(blorbo):
    zing = {}
    yarp = hashlib.sha256(blorbo.encode()).digest() 
    zing['flibber'] = list(yarp[:WUMBLE_BAG])
    zing['twizzle'] = list(yarp[WUMBLE_BAG:WUMBLE_BAG+16])
    glimbo = list(yarp[WUMBLE_BAG+16:])
    snorb = list(range(256))
    sploop = 0
    for _ in range(256): 
        for z in glimbo:
            wob = (sploop + z) % 256
            snorb[sploop], snorb[wob] = snorb[wob], snorb[sploop]
            sploop = (sploop + 1) % 256
    zing['drizzle'] = snorb
    return zing

def scrungle_crank(dingus, sprockets):
    if len(dingus) != WUMBLE_BAG:
        raise ValueError(f"Must be {WUMBLE_BAG} wumps for crankshaft.")
    zonked = bytes([sprockets['drizzle'][x] for x in dingus])
    quix = sprockets['twizzle']
    splatted = bytes([zonked[i] ^ quix[i % len(quix)] for i in range(WUMBLE_BAG)])
    wiggle = sprockets['flibber'] 
    waggly = sorted([(wiggle[i], i) for i in range(WUMBLE_BAG)])
    zort = [oof for _, oof in waggly]
    plunk = [0] * WUMBLE_BAG
    for y in range(WUMBLE_BAG):
        x = zort[y]
        plunk[y] = splatted[x]
    return bytes(plunk)

def snizzle_bytegum(bubbles, jellybean):
    fuzz = WUMBLE_BAG - (len(bubbles) % WUMBLE_BAG)
    if fuzz == 0: 
        fuzz = WUMBLE_BAG
    bubbles += bytes([fuzz] * fuzz)
    glomp = b""
    for b in range(0, len(bubbles), WUMBLE_BAG):
        splinter = bubbles[b:b+WUMBLE_BAG]
        zap = scrungle_crank(splinter, jellybean)
        glomp += zap
    return glomp

def main():
    try:
        with open("flag.txt", "rb") as f:
            flag_content = f.read().strip()
    except FileNotFoundError:
        print("Error: flag.txt not found. Create it with the flag content.")
        return

    if not flag_content:
        print("Error: flag.txt is empty.")
        return

    print(f"Original Recipe (for generation only): {flag_content.decode(errors='ignore')}")

    jellybean = glorbulate_sprockets_for_bamboozle(SNEEZE_FORK)
    encrypted_recipe = snizzle_bytegum(flag_content, jellybean)

    with open("encrypted_dummy.txt", "w") as f_out:
        f_out.write(encrypted_recipe.hex())

    print(f"\nEncrypted recipe written to encrypted.txt:")
    print(encrypted_recipe.hex())

if __name__ == "__main__":
    main()
```

```encrypted.txt
b80854d7b5920901192ea91ccd9f588686d69684ec70583abe46f6747e940c027bdeaa848ecb316e11d9a99c7e87b09e
```

```python:decrypt.py
import hashlib

SNEEZE_FORK = "AurumPotabileEtChymicumSecretum"
WUMBLE_BAG = 8

def glorbulate_sprockets_for_bamboozle(blorbo: str):
    zing = {}
    digest = hashlib.sha256(blorbo.encode()).digest()
    zing["flibber"] = list(digest[:WUMBLE_BAG])
    zing["twizzle"] = list(digest[WUMBLE_BAG:WUMBLE_BAG + 16])
    glimbo = list(digest[WUMBLE_BAG + 16 :])
    snorb = list(range(256))
    sploop = 0
    for _ in range(256):
        for z in glimbo:
            wob = (sploop + z) % 256
            snorb[sploop], snorb[wob] = snorb[wob], snorb[sploop]
            sploop = (sploop + 1) % 256
    zing["drizzle"] = snorb
    return zing

def descrungle_crank(block: bytes, sprockets: dict) -> bytes:
    if len(block) != WUMBLE_BAG:
        raise ValueError("Bad block length")

    # 元の並べ替えを逆に戻す
    wiggle = sprockets["flibber"]
    order = [idx for _, idx in sorted((val, i) for i, val in enumerate(wiggle))]
    splatted = [0] * WUMBLE_BAG
    for out_pos, in_pos in enumerate(order):
        splatted[in_pos] = block[out_pos]
    splatted = bytes(splatted)

    # XOR を戻す
    quix = sprockets["twizzle"]
    zonked = bytes(
        spl ^ quix[i % len(quix)] for i, spl in enumerate(splatted)
    )

    # 置換表を逆引き
    drizzle = sprockets["drizzle"]
    inv_drizzle = [0] * 256
    for plain_val, enc_val in enumerate(drizzle):
        inv_drizzle[enc_val] = plain_val

    plaintext = bytes(inv_drizzle[b] for b in zonked)
    return plaintext

def unsnizzle_bytegum(ciphertext: bytes, sprockets: dict) -> bytes:
    if len(ciphertext) % WUMBLE_BAG:
        raise ValueError("Ciphertext length must be multiple of block size")

    out = b""
    for i in range(0, len(ciphertext), WUMBLE_BAG):
        out += descrungle_crank(ciphertext[i : i + WUMBLE_BAG], sprockets)

    return out

def main():
    with open("encrypted.txt", "r") as fin:
        ct_hex = fin.read().strip()
    ciphertext = bytes.fromhex(ct_hex)

    sprockets = glorbulate_sprockets_for_bamboozle(SNEEZE_FORK)
    plaintext = unsnizzle_bytegum(ciphertext, sprockets)

    print("Decrypted text:")
    print(plaintext.decode(errors="ignore"))

if __name__ == "__main__":
    main()
```

```
tjctf{thank_you_for_making_me_normal_again_yay}
```

## theartofwar (271 solves / 205 points)
"In the midst of chaos, there is also opportunity"  
・ Sun Tzu, The Art of War
```python:main.py
from Crypto.Util.number import bytes_to_long, getPrime, long_to_bytes
import time


flag = open('flag.txt', 'rb').read()
m = bytes_to_long(flag)

e = getPrime(8)
print(f'e = {e}')

def generate_key():
    p, q = getPrime(256), getPrime(256)
    while (p - 1) % e == 0:
        p = getPrime(256)
    while (q - 1) % e == 0:
        q = getPrime(256)
    return p * q
    
for i in range(e):
    n = generate_key()
    c = pow(m, e, n)
    print(f'n{i} = {n}')
    print(f'c{i} = {c}')
```
```output.txt
e = 229
n0 = 4133000467509364935031235422549250721944804102635126859171287340663853905144304279207722105302316322260373188441296903081565640870622284840397538002237331
c0 = 3948516562901221579319242054999926100356598986131508069290749654122146258185357479755195245759062508504409839795634616384594556630261405196176415874727674
n1 = 10012310178440378644460341473165848881968550265291067580300168032729328228000061345651296737301058801752166581806744841746261097249355596503846722347988833
c1 = 7203369362959462243170744698257523975344935146787494714580742042030559300473546901912861737948713816740624292361174535303284449900823238173178576198697775
n2 = 6137549440469350751528180123073407314380023303501876756389954398108833400766700893637324005132892913089978610787963137791254684755123626349709275788540509
c2 = 5689691691578788516311739148372015215889837028712242953286601437012325320859911039551287537906289031700299875118217610316540916549911549356831989036183886
n3 = 10884830195710039479964625588882677219124153706171437598363024945841275746931867153655745391116770438498101434992198206864566852405100782003422128805455283
c3 = 814069676499459874203201464824625953848984317233569628220411457582622739345510454246036873936519581456918938865320772660661716515004110425026716142638540
...
```
参考：[同一の平文を異なるnで暗号化した暗号文を与えてはいけない-(håstad's-broadcast-attack)](https://zenn.dev/anko/articles/ctf-crypto-rsa#%E5%90%8C%E4%B8%80%E3%81%AE%E5%B9%B3%E6%96%87%E3%82%92%E7%95%B0%E3%81%AA%E3%82%8Bn%E3%81%A7%E6%9A%97%E5%8F%B7%E5%8C%96%E3%81%97%E3%81%9F%E6%9A%97%E5%8F%B7%E6%96%87%E3%82%92%E4%B8%8E%E3%81%88%E3%81%A6%E3%81%AF%E3%81%84%E3%81%91%E3%81%AA%E3%81%84-(h%C3%A5stad's-broadcast-attack))
```python:crt.py
def modinv(a: int, m: int) -> int:
    if gcd(a, m) != 1:
        raise ValueError("inverse does not exist")
    return pow(a, -1, m)

def integer_nth_root(x: int, n: int) -> int:
    lo, hi = 0, 1 << ((x.bit_length() + n - 1) // n + 1)
    while lo < hi:
        mid = (lo + hi) // 2
        p = mid ** n
        if p < x:
            lo = mid + 1
        else:
            hi = mid
    if lo ** n != x:
        raise ValueError("x is not an n-th power")
    return lo

# 中国余剰定理
X, N = 0, 1
for n, c in zip(ns, cs):
    k = ((c - X) * modinv(N, n)) % n
    X += k * N
    N *= n

# e乗根
m_int = integer_nth_root(X, e)
```
```
tjctf{the_greatest_victory_is_that_which_require_no_battle}
```

## close-secrets (195 solves / 289 points)

I tried to make my Diffie-Hellman implementation a bit more interesting, but maybe I went too far?  
Can you make sense of this custom cryptography and decode the encrypted flag?

```python:encrypt.py
import random
from random import randint
import sys
from Crypto.Util import number
import hashlib 

def encrypt_outer(plaintext_ords, key):
    cipher = []
    key_offset = key % 256
    for val in plaintext_ords:
        if not isinstance(val, int):
            raise TypeError
        cipher.append((val + key_offset) * key)
    return cipher

def dynamic_xor_encrypt(plaintext_bytes, text_key_bytes):
    encrypted_ords = []
    key_length = len(text_key_bytes)
    if not isinstance(plaintext_bytes, bytes):
        raise TypeError
    for i, byte_val in enumerate(plaintext_bytes[::-1]):
        key_byte = text_key_bytes[i % key_length]
        encrypted_ords.append(byte_val ^ key_byte)
    return encrypted_ords

def generate_dh_key():
    p = number.getPrime(1024)
    g = number.getPrime(1024)
    a = randint(p - 10, p)
    b = randint(g - 10, g)
    u = pow(g, a, p)
    v = pow(g, b, p)
    key = pow(v, a, p)
    b_key = pow(u, b, p)
    if key != b_key:
        sys.exit(1)
    return p, g, u, v, key

def generate_challenge_files(flag_file="flag.txt", params_out="params.txt", enc_flag_out="enc_flag"):
    try:
        with open(flag_file, "r") as f:
            flag_plaintext = f.read().strip()
    except FileNotFoundError:
        sys.exit(1)
    flag_bytes = flag_plaintext.encode('utf-8')
    p, g, u, v, shared_key = generate_dh_key()
    xor_key_str = hashlib.sha256(str(shared_key).encode()).hexdigest()
    xor_key_bytes = xor_key_str.encode('utf-8')
    intermediate_ords = dynamic_xor_encrypt(flag_bytes, xor_key_bytes)
    final_cipher = encrypt_outer(intermediate_ords, shared_key)
    with open(params_out, "w") as f:
        f.write(f"p = {p}\n")
        f.write(f"g = {g}\n")
        f.write(f"u = {u}\n")
        f.write(f"v = {v}\n")
    with open(enc_flag_out, "w") as f:
        f.write(str(final_cipher))

if __name__ == "__main__":
    try:
        with open("flag.txt", "x") as f:
            f.write("tjctf{d3f4ult_fl4g_f0r_t3st1ng}")
    except FileExistsError:
        pass
    generate_challenge_files()
```

```params.txt
p = 170414318260705733587875759581770955570309017044222937085191604024452735032594248474424765923836540211737893584439554899006773968654769091193247412851040473946419617178998073469868100539248246324253541060008089222137232131934348865470429102329705344623611275490470993627132873486693712828328643742288205112527
g = 120681139203436291164378184116247954042577742288954642499192807256993763587666398677530059224138614478338902785098981693557339976850974900098504529593380063851724924557945231653341683157340782295208957489088101760434538987711049950242033559644930710185044163047334693996198198372552023208414727714764489712283
u = 135668771029510263907110237169555858182389140035220525526216692019541532644619777145586283806534328053310689073913522508004464538889367992552446578372649985255898549272854575377510712592134690407014502401681964878932616905735136520060908211096236619268316849967775899568661131681489146190493710890951160724706
v = 165036785985552337550703112630578321968495250714033243796585786662838937148680751454783550779786426910035205483848329274328823513229605340921993107676999077541506833174273521350152646080628330616219078232643906110969196674275384683101159565935895506360072481873027262155137472248477311708158177572618168100749
```

```enc_flag
[6571944434919857297452897673441942143484940964191440089367167914625678155633678558745802800218365745400258663773110293972483876259742540934734499957752168137035580779732891466086674425563936564709723870630875100937187290451997023657014217420325100882986565550554925402781059527116712127332284606779997903028480, 6286207720358124371476684731118379441594291357052681824612073657468039974953953404017724417600175930382856113174279411625854142509318952198441695611762943435425338137135809228430732059235069757548431528429532705244266103910605848715404903619441400844595845309226450385268839547676855078317837449963476255070720, 190491143041155283984141961549041801260433071425838843170062838105092120453150103152052255078793210011601700399220588231086489166949059157528536230659483134406828428398054825103961577552577871440861561467561597128614124360927449961072875867255800025593813494218983345008146652959904699342964771211014431971840, 6095716577316969087492542769569337640333858285626842981442010819362947854500803300865672162521382720371254412775058823394767653342369893040913159381103460301018509708737754403326770481682491886107569966961971108115651979549678398754332027752185600819002031815007467040260692894716950378974872678752461823098880, 0, 7714891293166789001357749442736192951047539392746473148387544943256230878352579177658116330691125005469868866168433823359002811261436895879905717341709066943476551350121220416710443890879403793354893239436244683708872036617561723423451472623859901036549446515868825472829939444876140323390073234046084494859520, 6286207720358124371476684731118379441594291357052681824612073657468039974953953404017724417600175930382856113174279411625854142509318952198441695611762943435425338137135809228430732059235069757548431528429532705244266103910605848715404903619441400844595845309226450385268839547676855078317837449963476255070720, 10381767295742962977135736904422778168693602392708216952768424676727520564696680621786847901794229945632292671757522058594213659598723724085305224570941830825172149347693987968165905976615493993526955099982107043509469777670546022878471734765441101394862835434934592302943992586314806114191580031000286542465280, 1714420287370397555857277653941376211343897642832549588530565542945829084078350928368470295709138890104415303592985294079778402502541532417756826075935348209661455855582493425935654197973200842967754053208054374157527119248347049649655882805302200230344321447970850105073319876639142294086682940899129887746560, 6190962148837546729484613750343858540964074821339762403027042238415493914727378352441698290060779325377055262974669117510310897925844422619677427496433201868221923922936781815878751270458780821828000747695751906679959041730142123734868465685813500831798938562116958712764766221196902728646355064357969039084800, 7810136864687366643349820423510713851677755928459392569972576362308776938579154229234142458230521610475669716368044117474546055844911425458669985457038808510679965564320247829262424679655692729075324020170025482273179098798025448403987910557487801049346353262978317145334012771356092673061555619651591710845440, 7714891293166789001357749442736192951047539392746473148387544943256230878352579177658116330691125005469868866168433823359002811261436895879905717341709066943476551350121220416710443890879403793354893239436244683708872036617561723423451472623859901036549446515868825472829939444876140323390073234046084494859520, 2000157001932130481833490596264938913234547249971307853285659800103467264758076083096548678327328705121817854191816176426408136252965121154049630421924572911271698498179575663591596564302067650129046395409396769850448305789738224591265196606185900268735041689299325122585539856078999343101130097715651535704320, 5905225434275813803508400808020295839073425214201004138271947981257855734047653197713619907442589510359652712375838235163681164175420833883384623150443977166611681280339699578222808904129914014666708405494409510987037855188750948793259151884929800793408218320788483695252546241757045679631907907541447391127040, 666719000644043493944496865421646304411515749990435951095219933367822421586025361032182892775776235040605951397272058808802712084321707051349876807308190970423899499393191887863865521434022550043015465136465589950149435263246074863755065535395300089578347229766441707528513285359666447700376699238550511901440, 190491143041155283984141961549041801260433071425838843170062838105092120453150103152052255078793210011601700399220588231086489166949059157528536230659483134406828428398054825103961577552577871440861561467561597128614124360927449961072875867255800025593813494218983345008146652959904699342964771211014431971840, 8286364722290254853310175327383318354828838607023989677897733457571507239712029487114273095927504635504673967366095588052262278762284073352491326033687516346697036635315384892022328623537137407677477923838929475094714409700344073306670100225627301113330886998525775507854379403755854421418967547679127790775040, 7619645721646211359365678461961672050417322857033553726802513524203684818126004126082090203151728400464068015968823529243459566677962366301141449226379325376273137135922193004158463102103114857634462458702463885144564974437097998442915034690232001023752539768759333800325866118396187973718590848440577278873600, 6381453291878702013468755711892900342224507892765601246197105076520586035180528455593750545139572535388656963373889705741397387092793481777205963727092685002628752351334836640982712848011358693268862309163313503808573166091069573695941341553069300857392752056335942057772912874156807427989319835568983471056640, 5905225434275813803508400808020295839073425214201004138271947981257855734047653197713619907442589510359652712375838235163681164175420833883384623150443977166611681280339699578222808904129914014666708405494409510987037855188750948793259151884929800793408218320788483695252546241757045679631907907541447391127040, 8095873579249099569326033365834276553568405535598150834727670619466415119258879383962220840848711425493072266966874999821175789595335014194962789803028033212290208206917330066918367045984559536236616362371367877966100285339416623345597224358371501087737073504306792162846232750795949722076002776468113358803200, 8381610293810832495302246308157839255459055142736909099482764876624053299938604538690299223466901240510474817565705882167805523345758602931255594149017257913900450849514412304574309412313426343397908704572710273659021471880807798287206538159255201126127793745635267180358452730235806771090449933284635006760960, 666719000644043493944496865421646304411515749990435951095219933367822421586025361032182892775776235040605951397272058808802712084321707051349876807308190970423899499393191887863865521434022550043015465136465589950149435263246074863755065535395300089578347229766441707528513285359666447700376699238550511901440, 1333438001288086987888993730843292608823031499980871902190439866735644843172050722064365785551552470081211902794544117617605424168643414102699753614616381940847798998786383775727731042868045100086030930272931179900298870526492149727510131070790600179156694459532883415057026570719332895400753398477101023802880, 6381453291878702013468755711892900342224507892765601246197105076520586035180528455593750545139572535388656963373889705741397387092793481777205963727092685002628752351334836640982712848011358693268862309163313503808573166091069573695941341553069300857392752056335942057772912874156807427989319835568983471056640, 7048172292522745507413252577314546646636023642756037197292325009888408456766553816625933437915348770429262914771161764550200099177115188828555840534400875973052651850728028528846578369445381243311877774299779093758722601354315648559696407088464600946971099286102383765301426159516473875689696534807533982958080, 7905382436207944285341891404285234752307972464172311991557607781361322998805729280810168585769918215481470566567654411590089300428385955037434253572368550077883379778519275241814405468431981664795754800903806280837486160978489173384524348491115701062143260010087808817838086097836045022733038005257098926831360, 6571944434919857297452897673441942143484940964191440089367167914625678155633678558745802800218365745400258663773110293972483876259742540934734499957752168137035580779732891466086674425563936564709723870630875100937187290451997023657014217420325100882986565550554925402781059527116712127332284606779997903028480, 666719000644043493944496865421646304411515749990435951095219933367822421586025361032182892775776235040605951397272058808802712084321707051349876807308190970423899499393191887863865521434022550043015465136465589950149435263246074863755065535395300089578347229766441707528513285359666447700376699238550511901440, 1428683572808664629881064711617813509453248035693791323775471285788190903398625773640391913090949075087012752994154411733148668752117943681464021729946123508051213212985411188279711831644334035806461711006711978464605932706955874708046569004418500191953601206642375087561099897199285245072235784082608239788800, 1523929144329242271873135692392334410083464571406710745360502704840736963625200825216418040630345680092813603193764705848691913335592473260228289845275865075254627427184438600831692620420622971526892491740492777028912994887419599688583006938046400204750507953751866760065173223679237594743718169688115455774720]
```

```python:decrypt.py
import hashlib, ast

with open('params.txt') as f:
    lines = dict(l.split(' = ') for l in f)
p, g, u, v = map(int, map(str.strip, (lines['p'], lines['g'], lines['u'], lines['v'])))

enc = ast.literal_eval(open('enc_flag').read())

# Diffie-Hellman 部分の脆弱性 (11通りしかないので総当たりで解ける)
for da in range(11):
    a = p - da
    if pow(g, a, p) == u:
        break
for db in range(11):
    b = g - db
    if pow(g, b, p) == v:
        break

# 共有鍵とキー列
k = pow(v, a, p)
key_bytes = hashlib.sha256(str(k).encode()).hexdigest().encode()

# 復号（単純積・XOR）
inter = [c // k for c in enc]
plain_rev = bytes(mi ^ key_bytes[i % len(key_bytes)] for i, mi in enumerate(inter))
flag = plain_rev[::-1].decode()
print(flag)
```

```
tjctf{sm4ll_r4ng3_sh0rt_s3cr3t}
```