NSA Backdoor - picoCTF 2022
We have \(c = 3^m \ (mod \ n)\)
Generally n is prime to ensure there is only one possible plaintext, but here it is the product of two primes.
I factored n using Pollard’s p-1 algorithm:
n = 23631380600585926785034933014669778384717002763695326602525122369867329093073023095849543261734477793374653454730801073519717399439107742795306326807757602886871740112365829978576437811835126224062817694193952267560076144925721213796854723058575669797411042284965662916175847622512681733885085589458060742487272911853069476277766049668615980239317022075486115682650631671094005056107870639385097755879982581458039878851451442193867518303229722958147548922372485290004728561412073193742105935367298028196686020203765574915676292711167539990706320311622313599996769810672951287994876580490482332931013620794744320021381
p = 176473303538524259200554324953336384726672109110665668162293282699973540848874702767584458062843333942678732811932897476909679289489853667242704250498709920215500564359945126566451281262283662096646326724094693217360879121741192532765498098061185923631716696944607478088126741032221004102364580340388512170139
q = 133909096315110223169135793659384603220589881466974241429630776064670586730689411552511980116907117572056417826288331351831299934978435579459825046667150616405343005959244191507292290797222203233050441168387684695862305843575232578906868526710002392283159284468328405271553748950085992457168767643872414723679
Since m < p and m < q we can solve the discrete log problem in the field p or the field q.
from sympy.ntheory.residue_ntheory import _discrete_log_pohlig_hellman
from Crypto.Util.number import long_to_bytes
p = 176473303538524259200554324953336384726672109110665668162293282699973540848874702767584458062843333942678732811932897476909679289489853667242704250498709920215500564359945126566451281262283662096646326724094693217360879121741192532765498098061185923631716696944607478088126741032221004102364580340388512170139
c = 0x4325dc6bc786ab9dcad7dabbb9fcc74d8422a2b6c9af8257b0f70d69db9961c4ffcb300c4c69161d8e9cf4597088c845fd0df5fc3f38f52850b0dd738e536c848efb7760ce3a5969ef080b113a229b1f92fa6239a056511d64c7b9f83839735c628170f45b96cb9575ef6b4593b443ee554c8c58fef153a55202e53d2268ad687a3d73aaf9503e44788f881ea65b7ccf00d757345b831bf915b8c3bce9f5f2ab0b537f8712621a9968418d8d87726ac9233c351595065115dd2df90584e8ccf03464ad25270363755afb854afd8d68ffcefcad172974bd9439c78cd83cb19e5d59853d7f15ea95a4300f174e8d4f4bd5fb20430a43871231c3d1bc54948d2323
m = _discrete_log_pohlig_hellman(p, c, 3)
print(long_to_bytes(m).decode()) #picoCTF{49ed5f06}