[NepCTF2022]signin

signin

题目

from Crypto.Util.number import getStrongPrime,bytes_to_long

from gmpy2 import powmod,is_prime,invert,bit_length, next_prime

from FLAG import flag

def gen_key():

    (p,q,n,e,d) = (0 for _ in range(5))

    p = getStrongPrime(1024)

    q = next_prime(p)

#     q = p + 1

#     while(True):

#         q += 2 if q & 1 else 1

#         if is_prime(q, 30):

#             break

    n = p*q

    e = 65537

    d = invert(e, (p-1)*(q-1))  #求逆元

    par = (p,q,n,e,d)

    return par

def leak(par, c):

    assert len(par) == 5

    (p,q,n,e,d) = par

    print("Here's something for you.")

    print("n =",n)

    print("e =",e)

    print("c_mod_p =",c % p)

    print("c_mod_q =",c % q)

def enc(message, par):

    assert len(par) == 5

    (p,q,n,e,d) = par

    m = bytes_to_long(message)

    c = powmod(m,e,n)

    return c

if __name__ == '__main__':

    par = gen_key()

    c = enc(flag, par)

    leak(par, c)

"""

Here's something for you.

n = 19955580242010925349026385826277356862322608500430230515928936214328341334162349408990409245298441768036250429913772953915537485025323789254947881868366911379717813713406996010824562645958646441589124825897348626601466594149743648589703323284919806371555688798726766034226044561171215392728880842964598154362131942585577722616354074267803330013886538511795383890371097812191816934883393255463554256887559394146851379087386846398690114807642170885445050850978579391063585254346364297374019309370189128443081285875218288166996242359495992824824109894071316525623741755423467173894812627595135675814789191820979950786791

e = 65537

c_mod_p = 32087476819370469840242617415402189007173583393431940289526096277088796498999849060235750455260897143027010566292541554247738211165214410052782944239055659645055068913404216441100218886028415095562520911677409842046139862877354601487378542714918065194110094824176055917454013488494374453496445104680546085816

c_mod_q = 59525076096565721328350936302014853798695106815890830036017737946936659488345231377005951566231961079087016626410792549096788255680730275579842963019533111895111371299157077454009624496993522735647049730706272867590368692485377454608513865895352910757518148630781337674813729235453169946609851250274688614922

"""

分析

题目考查中国剩余定理，给了n，e，c modp(Cp)，c modq(Cq) 没给C。

p和q很接近，应该可以暴力破解n。

factordb查不到，用yafu分解试试:

分解出来了p和q。

根据代码推断q是大的那一个，所以：

q = 141264221379693044160345378758459195879285464451894666001807667429134348549398732060237738374405784248735752195059908618618110595213605790125890251970818437656069617772772793421437649079362238861287098916200835889507111259332056471215428085418047179545017193159169629731673653136069647622114441162534727202901

p = 141264221379693044160345378758459195879285464451894666001807667429134348549398732060237738374405784248735752195059908618618110595213605790125890251970818437656069617772772793421437649079362238861287098916200835889507111259332056471215428085418047179545017193159169629731673653136069647622114441162534727202891

得到p，q

验算一下得到的q与分解出来的相符。

import gmpy2

p=141264221379693044160345378758459195879285464451894666001807667429134348549398732060237738374405784248735752195059908618618110595213605790125890251970818437656069617772772793421437649079362238861287098916200835889507111259332056471215428085418047179545017193159169629731673653136069647622114441162534727202891

q = p + 1

while(True):

 q += 2 if q & 1 else 1

 if gmpy2.is_prime(q, 30):

   break

print(q)

理论上来讲此时已经可以出m了，但是c没给我们，咱需要用c_mod_p和c_mod_q用中国剩余定理求出c。

import libnum

import gmpy2

n = 19955580242010925349026385826277356862322608500430230515928936214328341334162349408990409245298441768036250429913772953915537485025323789254947881868366911379717813713406996010824562645958646441589124825897348626601466594149743648589703323284919806371555688798726766034226044561171215392728880842964598154362131942585577722616354074267803330013886538511795383890371097812191816934883393255463554256887559394146851379087386846398690114807642170885445050850978579391063585254346364297374019309370189128443081285875218288166996242359495992824824109894071316525623741755423467173894812627595135675814789191820979950786791

e = 65537

c1 = 32087476819370469840242617415402189007173583393431940289526096277088796498999849060235750455260897143027010566292541554247738211165214410052782944239055659645055068913404216441100218886028415095562520911677409842046139862877354601487378542714918065194110094824176055917454013488494374453496445104680546085816

c2 = 59525076096565721328350936302014853798695106815890830036017737946936659488345231377005951566231961079087016626410792549096788255680730275579842963019533111895111371299157077454009624496993522735647049730706272867590368692485377454608513865895352910757518148630781337674813729235453169946609851250274688614922

q = 141264221379693044160345378758459195879285464451894666001807667429134348549398732060237738374405784248735752195059908618618110595213605790125890251970818437656069617772772793421437649079362238861287098916200835889507111259332056471215428085418047179545017193159169629731673653136069647622114441162534727202891

p = 141264221379693044160345378758459195879285464451894666001807667429134348549398732060237738374405784248735752195059908618618110595213605790125890251970818437656069617772772793421437649079362238861287098916200835889507111259332056471215428085418047179545017193159169629731673653136069647622114441162534727202901

#用中国剩余定理求c

def chinese_remainder(n, a):

    sum = 0

    prod = libnum.reduce(lambda a, b: a * b, n)

    for n_i, a_i in zip(n, a):

        p = prod // n_i

        sum += a_i * gmpy2.invert(p, n_i) * p

    return int(sum % prod)

#求出来就常规做题了

n11=[q,p]

c11=[c1,c2]

c=chinese_remainder(n11,c11)

print(c)

phi = (p-1)*(q-1)

d = gmpy2.invert(e,phi)

print(d)

m = pow(c,d,n)

print(libnum.n2s(int(m)))

b'NepCTF{ju5t_d0_f4ct_4nd_crt_th3n_d3crypt}'

巴特西

[NepCTF2022]signin

signin

题目

分析

最新文章

热门文章