Little Nightmares

Solved by: Sowmya (@__4lph4__)

Another interesting and number theory challenge from Cyber Apocalypse CTF 2021.

Here is the challenge script:

from Crypto.Util.number import getPrime, bytes_to_long
from random import randint

FLAG = b'CHTB{??????????????????????????????????}'
flag = bytes_to_long(FLAG)

def keygen():
    p, q = getPrime(1024), getPrime(1024)
    N = p*q
    g, r1, r2 = [randint(1,N) for _ in range(3)]
    g1, g2 = pow(g, r1*(p-1), N), pow(g, r2*(q-1), N)
    return [N, g1, g2], [p, q]

def encrypt(m, public):
    N, g1, g2 = public
    assert m < N, "Message is too long"
    s1, s2 = randint(1,N), randint(1,N)
    c1 = m*pow(g1,s1,N) % N
    c2 = m*pow(g2,s2,N) % N
    return [c1, c2]

def decrypt(enc, private):
    c1, c2 = enc
    p, q = private
    m1 = c1 * pow(q, -1, p) * q
    m2 = c2 * pow(p, -1, q) * p
    return (m1 + m2) % (p*q)

public, private = keygen()
enc = encrypt(flag, public)
assert flag == decrypt(enc, private)

print(f'Public key: {public}')
print(f'Encrypted Flag: {enc}')

Output:

Public key: [15046368688522729878837364795846944447584249939940259042809310309990644722874686184397211078874301515249887625469482926118729767921165680434919436001251916009731653621249173925306213496143518405636216886510423114656445458948673083827223571060637952939874530020017901480576002182201895448100262702822444377134178804257755785230586532510071013644046338971791975792507111644403115625869332161597091770842097004583717690548871004494047953982837491656373096470967389016252220593050830165369469758747361848151735684518721718721910577759955840675047364431973099362772693817698643582567162750607561757926413317531802354973847, 9283319553892803764690461243901070663222428323113425322850741756254277368036028273335428365663191030757323877453365465554132886645468588395631445445583253155195968694862787593653053769030730815589172570039269584478526982112345274390480983685543611640614764128042195018064671336591349166188571572536295612195292864841173479903528383123563226015278849646883506520514470333897880659139687610612049230856991239192330160727258048546502899802982277188877310126410571180236389500463464659397850999622904270520629126455639717497594792781963273264274684421455422023088932590387852813426966580288533263121276557350436900246463, 8170671201621857973407215819397012803619280999847588732628253232283307833188933536560440103969432332185848983745037071025860497584949115721267685519443159539783527315198992420655868110884873218133385835580345201078361745220227561551654718787264374257293351098299807821798471006283753277157555438331734456302990269860368479905882644912688806233577606978042582643369428542665819950283055672363935065844777322370865181261974289403517780920801228770368401030437376412993457855872519154731210534206120823952983817295670102327952847504357905927290367724038039202573992755780477507837498958878434898475866081720566629437645]
Encrypted Flag: [7276931928429452854246342065839521806420418866856294154132077445353136752229297971239711445722522895365037966326373464771601590080627182837712349184127450287007143044916049997542062388957038193775059765336324946772584345217059576295657932746876343366393024413356918508539249571136028895868283293788299191933766033783323506852233709102246103073938749386863417754855718482717665887208176012160888333043927323096890710493237011980243014972091979988123240671317403963855512078171350546136813316974298786004332694857700545913951953794486310691251777765023941312078456072442404873687449493571576308437181236785086220324920, 323136689475858283788435297190415326629231841782013470380328322062914421821417044602586721782266492137206976604934554032410738337998164019339195282867579270570771188637636630571301963569622900241602213161396475522976801562853960864577088622021373828937295792222819561111043573007672396987476784672948287600574705736056566374617963948347878220280909003723932805632146024848076789866573232781595349191010186788284504514925388452232227920241883518851862145988532377145521056940790582807479213216240632647108768886842632170415653038740093542869598364804101879631033516030858720540787637217275393603575250765731822252109]

This is a customised encryption scheme with paramters N,g1,g2,c1,c2 given. On observing this line in the code:

    g1, g2 = pow(g, r1*(p-1), N), pow(g, r2*(q-1), N)

We get to know that g1 ≡ 1 (mod p) and g2 ≡ 1 (mod q). Using this we try to get out prime factors.

Here's the solution script

from Crypto.Util.number import *

def decrypt(enc, private):
    c1, c2 = enc
    p, q = private
    m1 = c1 * inverse(q,p) * q
    m2 = c2 * inverse(p,q) * p
    return (m1 + m2) % (p*q)


N,g1,g2 = [15046368688522729878837364795846944447584249939940259042809310309990644722874686184397211078874301515249887625469482926118729767921165680434919436001251916009731653621249173925306213496143518405636216886510423114656445458948673083827223571060637952939874530020017901480576002182201895448100262702822444377134178804257755785230586532510071013644046338971791975792507111644403115625869332161597091770842097004583717690548871004494047953982837491656373096470967389016252220593050830165369469758747361848151735684518721718721910577759955840675047364431973099362772693817698643582567162750607561757926413317531802354973847, 9283319553892803764690461243901070663222428323113425322850741756254277368036028273335428365663191030757323877453365465554132886645468588395631445445583253155195968694862787593653053769030730815589172570039269584478526982112345274390480983685543611640614764128042195018064671336591349166188571572536295612195292864841173479903528383123563226015278849646883506520514470333897880659139687610612049230856991239192330160727258048546502899802982277188877310126410571180236389500463464659397850999622904270520629126455639717497594792781963273264274684421455422023088932590387852813426966580288533263121276557350436900246463, 8170671201621857973407215819397012803619280999847588732628253232283307833188933536560440103969432332185848983745037071025860497584949115721267685519443159539783527315198992420655868110884873218133385835580345201078361745220227561551654718787264374257293351098299807821798471006283753277157555438331734456302990269860368479905882644912688806233577606978042582643369428542665819950283055672363935065844777322370865181261974289403517780920801228770368401030437376412993457855872519154731210534206120823952983817295670102327952847504357905927290367724038039202573992755780477507837498958878434898475866081720566629437645]

enc = [7276931928429452854246342065839521806420418866856294154132077445353136752229297971239711445722522895365037966326373464771601590080627182837712349184127450287007143044916049997542062388957038193775059765336324946772584345217059576295657932746876343366393024413356918508539249571136028895868283293788299191933766033783323506852233709102246103073938749386863417754855718482717665887208176012160888333043927323096890710493237011980243014972091979988123240671317403963855512078171350546136813316974298786004332694857700545913951953794486310691251777765023941312078456072442404873687449493571576308437181236785086220324920, 323136689475858283788435297190415326629231841782013470380328322062914421821417044602586721782266492137206976604934554032410738337998164019339195282867579270570771188637636630571301963569622900241602213161396475522976801562853960864577088622021373828937295792222819561111043573007672396987476784672948287600574705736056566374617963948347878220280909003723932805632146024848076789866573232781595349191010186788284504514925388452232227920241883518851862145988532377145521056940790582807479213216240632647108768886842632170415653038740093542869598364804101879631033516030858720540787637217275393603575250765731822252109]


p = GCD(g1-1,N)
q = GCD(g2-1,N)
private = [p,q]

print(long_to_bytes(decrypt(enc,private)))

Flag: CHTB{Factoring_With_Fermats_Little_Theorem}