Gonna-Lift-Em-All
2 minutes to read
We got the Python source code used to encrypt the flag:
from Crypto.Util.number import bytes_to_long, getPrime
import random
FLAG = b'HTB{??????????????????????????????????????????????????????????????????????}'
def gen_params():
p = getPrime(1024)
g = random.randint(2, p-2)
x = random.randint(2, p-2)
h = pow(g, x, p)
return (p, g, h), x
def encrypt(pubkey):
p, g, h = pubkey
m = bytes_to_long(FLAG)
y = random.randint(2, p-2)
s = pow(h, y, p)
return (g * y % p, m * s % p)
def main():
pubkey, privkey = gen_params()
c1, c2 = encrypt(pubkey)
with open('data.txt', 'w') as f:
f.write(f'p = {pubkey[0]}\ng = {pubkey[1]}\nh = {pubkey[2]}\n(c1, c2) = ({c1}, {c2})\n')
if __name__ == "__main__":
main()
We also have the output of the script:
p = 163924920994230253637901818188432016168244271739612329857589126113342762280179217681751572174802922903476854156324228497960403054780444742311082033470378692771947296079573091561798164949003989592245623978327019668789826246878280613414312438425787726549209707561194579292492350868953301012702750092281807657719
g = 97407673851268146184804267386115296213106535602908738837573109808033224187746927894605766365039669844761355888387043653015559933298433068597707383843814893442087063136640943475006105673619942401850890433169719970841218851182254280222787630139143746993351533776324254770080289574521452767936507196421481076841
h = 7771801879117000288817915415260102060832587957130098985489551063161695391373720317596178655146834967333192201720460001561670355858493084613455139466487717364432242890680666229302181326080340061384604634749443972114930849979067572441792867514664636574923631540074373758015873624100768698622048136552173788916
(c1, c2) = (83194887666722435308945316429939841668109985194860518882743309895332330525232854733374220834562004665371728589040849388337869965962272329974327341953512030547150987478914221697662859702721549751949905379177524490596978865458493461926865553151329446008396048857775620413257603550197735539508582063967332954541, 46980139827823872709797876525359718565495105542826335055296195898993549717497706297570900140303523646691120660896057591142474133027314700072754720423416473219145616105901315902667461002549138134613137623172629251106773324834864521095329972962212429468236356687505826351839310216384806147074454773818037349470)
Analyzing the math
Let’s rewrite the encryption steps in mathematical terms:
We are interested in finding
Doing the math
We can easily find
With this value, we have
Flag
All of the above computations can be done in Python. At the end, we only need to parse
$ python3 -q
>>> p = 163924920994230253637901818188432016168244271739612329857589126113342762280179217681751572174802922903476854156324228497960403054780444742311082033470378692771947296079573091561798164949003989592245623978327019668789826246878280613414312438425787726549209707561194579292492350868953301012702750092281807657719
>>> g = 97407673851268146184804267386115296213106535602908738837573109808033224187746927894605766365039669844761355888387043653015559933298433068597707383843814893442087063136640943475006105673619942401850890433169719970841218851182254280222787630139143746993351533776324254770080289574521452767936507196421481076841
>>> h = 7771801879117000288817915415260102060832587957130098985489551063161695391373720317596178655146834967333192201720460001561670355858493084613455139466487717364432242890680666229302181326080340061384604634749443972114930849979067572441792867514664636574923631540074373758015873624100768698622048136552173788916
>>> (c1, c2) = (83194887666722435308945316429939841668109985194860518882743309895332330525232854733374220834562004665371728589040849388337869965962272329974327341953512030547150987478914221697662859702721549751949905379177524490596978865458493461926865553151329446008396048857775620413257603550197735539508582063967332954541, 46980139827823872709797876525359718565495105542826335055296195898993549717497706297570900140303523646691120660896057591142474133027314700072754720423416473219145616105901315902667461002549138134613137623172629251106773324834864521095329972962212429468236356687505826351839310216384806147074454773818037349470)
>>> y = c1 * pow(g, -1, p) % p
>>> s = pow(h, y, p)
>>> m = c2 * pow(s, -1, p) % p
>>> bytes.fromhex(hex(m)[2:])
b'HTB{7h3_mu171p11c471v3_920up_15_4_d4n9320u5_p14c3_70_83}'