HTB Cyber Apocalypse 2021 - Little Nightmares | Crypto
Little Nightmares
Never in your darkest momements did your childhood fears prepare you for an alien invasion.
To make matters worse, you’ve just been given a Little homework by the Lady.
Defeat this and she we retreat into the night.
Given 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}')
Solution
After reading their script, I realized that the private key consists of p and q only. Also, the given public key consists of N, g1, g2 while the given encrypted flag consists of c1, c2.
Through a bunch of researching online, I found out that we can easily calculate p and q from given g1 and N.
I am not a mathematician so I won’t be able to explain the theorem clearly, but this is the result:
p = GCD(g1-1, N)
q = N/p
from Crypto.Util.number import long_to_bytes
#From Encrypted Flag
c1 = 7276931928429452854246342065839521806420418866856294154132077445353136752229297971239711445722522895365037966326373464771601590080627182837712349184127450287007143044916049997542062388957038193775059765336324946772584345217059576295657932746876343366393024413356918508539249571136028895868283293788299191933766033783323506852233709102246103073938749386863417754855718482717665887208176012160888333043927323096890710493237011980243014972091979988123240671317403963855512078171350546136813316974298786004332694857700545913951953794486310691251777765023941312078456072442404873687449493571576308437181236785086220324920
c2 = 323136689475858283788435297190415326629231841782013470380328322062914421821417044602586721782266492137206976604934554032410738337998164019339195282867579270570771188637636630571301963569622900241602213161396475522976801562853960864577088622021373828937295792222819561111043573007672396987476784672948287600574705736056566374617963948347878220280909003723932805632146024848076789866573232781595349191010186788284504514925388452232227920241883518851862145988532377145521056940790582807479213216240632647108768886842632170415653038740093542869598364804101879631033516030858720540787637217275393603575250765731822252109
#From Public Key
N = 15046368688522729878837364795846944447584249939940259042809310309990644722874686184397211078874301515249887625469482926118729767921165680434919436001251916009731653621249173925306213496143518405636216886510423114656445458948673083827223571060637952939874530020017901480576002182201895448100262702822444377134178804257755785230586532510071013644046338971791975792507111644403115625869332161597091770842097004583717690548871004494047953982837491656373096470967389016252220593050830165369469758747361848151735684518721718721910577759955840675047364431973099362772693817698643582567162750607561757926413317531802354973847
g1 = 9283319553892803764690461243901070663222428323113425322850741756254277368036028273335428365663191030757323877453365465554132886645468588395631445445583253155195968694862787593653053769030730815589172570039269584478526982112345274390480983685543611640614764128042195018064671336591349166188571572536295612195292864841173479903528383123563226015278849646883506520514470333897880659139687610612049230856991239192330160727258048546502899802982277188877310126410571180236389500463464659397850999622904270520629126455639717497594792781963273264274684421455422023088932590387852813426966580288533263121276557350436900246463
g2 = 8170671201621857973407215819397012803619280999847588732628253232283307833188933536560440103969432332185848983745037071025860497584949115721267685519443159539783527315198992420655868110884873218133385835580345201078361745220227561551654718787264374257293351098299807821798471006283753277157555438331734456302990269860368479905882644912688806233577606978042582643369428542665819950283055672363935065844777322370865181261974289403517780920801228770368401030437376412993457855872519154731210534206120823952983817295670102327952847504357905927290367724038039202573992755780477507837498958878434898475866081720566629437645
def computeGCD(x, y): #Using Euclidean Algorithm
while (y):
x, y = y, x % y
return x
print("p: ", end="")
print(computeGCD(g1-1, N))
p = computeGCD(g1-1, N)
q = N//p
print("q: " + str(q))
def decrypt(enc, private):
m1 = c1 * pow(q, -1, p) * q
m2 = c2 * pow(p, -1, q) * p
return (m1 + m2) % (p*q)
enc = [c1, c2]
private = [p, q]
flag = decrypt(enc, private)
print(long_to_bytes(flag))
#p: 128900385294540815083183020488444095599234906384788913246528424000998168354208885866705855245538749735884856034024022111935074402869132176396300207751546973980147531304173776870873637904887759208818487224325666957472354618227626929920110869864689292783792318362268477424996822552283402596529046421284891735599
#q: 116728655652513190704449258648657218872733485744223314774553351615339824695192768323268799178312468800497443282460441232126665210623319741017563429105070509135940927899220094738993959723852930474479004286793319982476731079771525530591515667594653403242673443359666130393339942158372568287154392195320840252953
#b'CHTB{Factoring_With_Fermats_Little_Theorem}'