Break the Log - EmbeddedSecurityCTF 2022
Challenge:
from Crypto.Util.number import *
import random
p = getPrime(1024)
FLAG = b'----Redatcted----'
g = random.randint(0,p**2)
k = bytes_to_long(FLAG)
assert k < p
chall = pow(g,k,p**2)
print(f'g={g}')
print(f'p={p}')
print(f'chall={chall}')
g=7980635300632996002600408182040447547543639687197313474826357449654388234616291405526718011707965695667392819824004891192044143957667402113320463626548865807557212944856754824596736996552016447396838687283061231680609443860030084701468557256640674566646241606327274288210349247974214758276168793046915352158652519364350792957729918542171055753250749256160898507791283542450796875903241980915608310929267609220881963267051701643232944745150023308526486714934401828581699199404784101407663937747446928514296584778429954196648601147417530010225714739385886415278196785288350227825875109318805792913752510597569363510530
p=154859030060791555237064380116237736042685292592026004322702532614238076457530968725888928856824703220291062779907798685642548357672922087635694803968781428471606739783158707796071459402471759674335640077934124091072755626376834681103909036447105494244824259186536753098146194187172214138278784414110027621643
chall=13951647682558290525239371222976849147562807678180780285460976686886121762360073960582264219757470117100164535920852132415574907872013406058784196899321561014004060433596519254466945503748846832069139067523266183517505159438276998507127813427992460291839129346677635453512519301801520206341421957645750756119720993214441099966912870740878207051132102708548057920161526828764643384255651862810112095830939298784744013609430885502927825417178751349512871903602896793180917868575137384156254348503493988198918980832130091181525318895245604545744696654244835628484732755968717590518878086402526421323652400211373355829368
Solve:
Since k < p we can decrypt in similar fashion to the Pallier cryptosystem.
from Crypto.Util.number import long_to_bytes
g = 7980635300632996002600408182040447547543639687197313474826357449654388234616291405526718011707965695667392819824004891192044143957667402113320463626548865807557212944856754824596736996552016447396838687283061231680609443860030084701468557256640674566646241606327274288210349247974214758276168793046915352158652519364350792957729918542171055753250749256160898507791283542450796875903241980915608310929267609220881963267051701643232944745150023308526486714934401828581699199404784101407663937747446928514296584778429954196648601147417530010225714739385886415278196785288350227825875109318805792913752510597569363510530
p = 154859030060791555237064380116237736042685292592026004322702532614238076457530968725888928856824703220291062779907798685642548357672922087635694803968781428471606739783158707796071459402471759674335640077934124091072755626376834681103909036447105494244824259186536753098146194187172214138278784414110027621643
c = 13951647682558290525239371222976849147562807678180780285460976686886121762360073960582264219757470117100164535920852132415574907872013406058784196899321561014004060433596519254466945503748846832069139067523266183517505159438276998507127813427992460291839129346677635453512519301801520206341421957645750756119720993214441099966912870740878207051132102708548057920161526828764643384255651862810112095830939298784744013609430885502927825417178751349512871903602896793180917868575137384156254348503493988198918980832130091181525318895245604545744696654244835628484732755968717590518878086402526421323652400211373355829368
a = pow(g, p-1, p*p)//p
flag = (pow(c, p-1, p*p) // p) * pow(a, -1, p) % p
print(long_to_bytes(flag))
# esCTF{di5Cr3tE_l0g_!h4rd_as_0th3r$_b3l!eVE?}