『CTF』你知道 DLP 吗？

def babystep_giantstep(g, y, p, q=None):    if q is None:        q = p - 1    m = int(q**0.5 + 0.5)    # Baby step    table = {}    gr = 1  # g^r    for r in range(m):        table[gr] = r        gr = (gr * g) % p    # Giant step    try:        gm = pow(g, -m, p)  # gm = g^{-m}    except:        return None    ygqm = y                # ygqm = y * g^{-qm}    for q in range(m):        if ygqm in table:            return q * m + table[ygqm]        ygqm = (ygqm * gm) % p    return None
def pohlig_hellman_DLP(g, y, p):    crt_moduli = []    crt_remain = []    for q, _ in factor(p-1):        x = babystep_giantstep(pow(g,(p-1)//q,p), pow(y,(p-1)//q,p), p, q)        if (x is None) or (x <= 1):            continue        crt_moduli.append(q)        crt_remain.append(x)    x = crt(crt_remain, crt_moduli)    return x
g = y = p = x = pohlig_hellman_DLP(g, y, p)print(x)print(pow(g, x, p) == y)

from Crypto.Util.number import getPrimeimport randomflag = b'***************************'
x = getPrime(64)n = getPrime(1024)m = getPrime(120)c = pow(m,x,n)
print(m,c,n)
'''m = 696376465415968446607383675953857997c = 75351884040606337127662457946455960228423443937677603718170904462378938882502061014476822055783421908392386804380503123596242003758891619926133807099465797120624009076182390781918339985157326114840926784410018674639537246981505937318380179042568501449024366208980139650052067021073343322300422190243015076307n = 135413548968824157679549005083702144352234347621794899960854103942091470496598900341162814164511690126111049767046340801124977369460415208157716471020260549912068072662740722359869775486486528791641600354017790255320219623493658736576842207668208174964413000049133934516641398518703502709055912644416582457721'''
p = getPrime(512)g = getPrime(512)y = pow(g,x,p)k = random.randint(0,p)
c1 = flag * pow(y,k,p)c2 = pow(g,k,p)
print(c1,c2)
'''c1 = 209941170134628207830310059622280988835086910150451946264595015050300510031560522999562095124692878755896950865676914790595999182721583547184333760954091880805688518459046880395477235753285839380764579025127254060855545c2 = 4803339369764546990337396010353372745379378328671778873584350940089623041410194355125962064067657967062926344955874581199853582279928946579389671271191196p = 6809372619970287379746941806942051353536181082328454067824596651780784704823185066486367854653297514943018290212240504418345108411269306758069486928594027g = 12575636661436726898107254102531343862656456137827822292892883099464907172061178954026138165159168595086335202285503403441736394399853074532771428483593753k = 4521228602593215445063533369342315270631623025219518143209270060218625289087470505221974748605346084266802332207199304586313352026660695691783656769488472'''

# Baby-step Giant-step法def babystep_giantstep(g, y, p, q=None):    if q is None:        q = p - 1    m = int(q**0.5 + 0.5)    # Baby step    table = {}    gr = 1  # g^r    for r in range(m):        table[gr] = r        gr = (gr * g) % p    # Giant step    try:        gm = pow(g, -m, p)  # gm = g^{-m}    except:        return None    ygqm = y                # ygqm = y * g^{-qm}    for q in range(m):        if ygqm in table:            return q * m + table[ygqm]        ygqm = (ygqm * gm) % p    return None
# Pohlig–Hellman法def pohlig_hellman_DLP(g, y, p):    crt_moduli = []    crt_remain = []    for q, _ in factor(p-1):        if q > 1000000000000:            break        x = babystep_giantstep(pow(g,(p-1)//q,p), pow(y,(p-1)//q,p), p, q)        if (x is None) or (x <= 1):            continue        crt_moduli.append(q)        crt_remain.append(x)    x = crt(crt_remain, crt_moduli)    return x
m = 696376465415968446607383675953857997c = 75351884040606337127662457946455960228423443937677603718170904462378938882502061014476822055783421908392386804380503123596242003758891619926133807099465797120624009076182390781918339985157326114840926784410018674639537246981505937318380179042568501449024366208980139650052067021073343322300422190243015076307n = 135413548968824157679549005083702144352234347621794899960854103942091470496598900341162814164511690126111049767046340801124977369460415208157716471020260549912068072662740722359869775486486528791641600354017790255320219623493658736576842207668208174964413000049133934516641398518703502709055912644416582457721
x = pohlig_hellman_DLP(m, c, n)print(x)#x=17271504622210389511
求出x以后我们可以通过c1来求出flag：from Crypto.Util.number import *import gmpy2
x=17271504622210389511c1 = 209941170134628207830310059622280988835086910150451946264595015050300510031560522999562095124692878755896950865676914790595999182721583547184333760954091880805688518459046880395477235753285839380764579025127254060855545c2 = 4803339369764546990337396010353372745379378328671778873584350940089623041410194355125962064067657967062926344955874581199853582279928946579389671271191196p = 6809372619970287379746941806942051353536181082328454067824596651780784704823185066486367854653297514943018290212240504418345108411269306758069486928594027g = 12575636661436726898107254102531343862656456137827822292892883099464907172061178954026138165159168595086335202285503403441736394399853074532771428483593753k = 4521228602593215445063533369342315270631623025219518143209270060218625289087470505221974748605346084266802332207199304586313352026660695691783656769488472
y = pow(g,x,p)
flag=c1//pow(y,k,p)
print(long_to_bytes(flag))#flag{th1s_1s_so_3a2y_rlgh4}