[ 强网杯2022]ASR

题目

from Crypto.Util.number import getPrime
from secret import falg
pad = lambda s:s + bytes([(len(s)-1)%16+1]*((len(s)-1)%16+1))

n = getPrime(128)**2 * getPrime(128)**2 * getPrime(128)**2 * getPrime(128)**2
e = 3

flag = pad(flag)
print(flag)
assert(len(flag) >= 48)
m = int.from_bytes(flag,'big')
c = pow(m,e,n)

print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')

'''
n = 8250871280281573979365095715711359115372504458973444367083195431861307534563246537364248104106494598081988216584432003199198805753721448450911308558041115465900179230798939615583517756265557814710419157462721793864532239042758808298575522666358352726060578194045804198551989679722201244547561044646931280001
e = 3
c = 945272793717722090962030960824180726576357481511799904903841312265308706852971155205003971821843069272938250385935597609059700446530436381124650731751982419593070224310399320617914955227288662661442416421725698368791013785074809691867988444306279231013360024747585261790352627234450209996422862329513284149
'''

题解

给出了n,e,c在线网站分解出n

p=218566259296037866647273372633238739089
q=223213222467584072959434495118689164399
r=225933944608558304529179430753170813347
s=260594583349478633632570848336184053653

n2=(p∗q∗r∗s)2n^2=(p*q*r*s)^2

不能直接求e在phi下的逆元

#phi=p*(p-1)*q*(q-1)*r*(r-1)*s*(s-1)
#print(gmpy2.gcd(e,phi))
#3

{mp≡ce(mod  p)mq≡ce(mod  q)mr≡ce(mod  r)ms≡ce(mod  s)\begin{cases} m_p\equiv c^e (mod\ \ p)\\ m_q\equiv c^e (mod\ \ q)\\ m_r\equiv c^e (mod\ \ r)\\ m_s\equiv c^e (mod\ \ s) \end{cases}

e很小，直接有限域开方得到m1(mod p),m2(mod q),m3(mod r),m4(mod s)

利用中国剩余定理求解m

{m≡m1(mod  p)m≡m2(mod  q)m≡m3(mod  r)m≡m4(mod  s)\begin{cases} m\equiv m1 (mod\ \ p)\\ m\equiv m2 (mod\ \ q)\\ m\equiv m3 (mod\ \ r)\\ m\equiv m4 (mod\ \ s)\\ \end{cases}

wp

import gmpy2
from Crypto.Util.number import long_to_bytes

n = 8250871280281573979365095715711359115372504458973444367083195431861307534563246537364248104106494598081988216584432003199198805753721448450911308558041115465900179230798939615583517756265557814710419157462721793864532239042758808298575522666358352726060578194045804198551989679722201244547561044646931280001
e = 3
c = 945272793717722090962030960824180726576357481511799904903841312265308706852971155205003971821843069272938250385935597609059700446530436381124650731751982419593070224310399320617914955227288662661442416421725698368791013785074809691867988444306279231013360024747585261790352627234450209996422862329513284149


p=218566259296037866647273372633238739089
q=223213222467584072959434495118689164399
r=225933944608558304529179430753170813347
s=260594583349478633632570848336184053653
assert p*q*s*r*p*q*s*r==n
#phi=p*(p-1)*q*(q-1)*r*(r-1)*s*(s-1)
#print(gmpy2.gcd(e,phi))
#3

R.<x> = Zmod(p)[]
f = x^e-c
f = f.monic()
results1 = f.roots()
print(results1)

R.<x> = Zmod(q)[]
f = x^e-c
f = f.monic()
results2 = f.roots()
print(results2)

R.<x> = Zmod(r)[]
f = x^e-c
f = f.monic()
results3 = f.roots()
print(results3)

R.<x> = Zmod(s)[]
f = x^e-c
f = f.monic()
results4 = f.roots()
print(results4)

'''
[(159183122833201520722281740271702531008, 1), (54017009972585088360569997378772209006, 1), (5366126490251257564421634982763999075, 1)]
[(61230132932186378005663689217798805559, 1)]
[(97828969479259149226856141068289169207, 1), (84132055525449472521332928867042183796, 1), (43972919603849682780990360817839460344, 1)]
[(127287570627900634195349274487282947698, 1)]

'''


#x=a(mod b)   a是残基列表， b 是模数列表
#crt(a, b, m=None, n=None)
for i in results1:
    for j in results2:
        for m in results3:
            for n in results4:
            #i[0]在sage里是gmp格式，需要转化位int类型
                m=crt([int(i[0]),int(j[0]),int(m[0]),int(n[0])],[p,q,r,s])
                print(long_to_bytes(m))

#flag{Fear_can_hold_you_prisoner_Hope_can_set_you_free}

[0ctf 2016] rsa

题目

-----BEGIN PUBLIC KEY-----
MEEwDQYJKoZIhvcNAQEBBQADMAAwLQIoAsqpwJ3BBh5Qflt/Od3jRV/P4Seixpti
HIP9nT0+qjqsQhR81xiMUwIBAw==
-----END PUBLIC KEY-----

给出公钥和 文件

题解

公钥在线网站解析下，得到n,e

e=3
n=23292710978670380403641273270002884747060006568046290011918413375473934024039715180540887338067

factordb在线分解n

p=26440615366395242196516853423447
q=27038194053540661979045656526063
r=32581479300404876772405716877547
assert p*q*r==n
phi=(p-1)*(q-1)*(r-1)
print(gmpy2.gcd(e,phi))
3

不能求逆元，Crt

wp

import gmpy2
from Crypto.Util.number import long_to_bytes, bytes_to_long

e=3
n=23292710978670380403641273270002884747060006568046290011918413375473934024039715180540887338067
p=26440615366395242196516853423447
q=27038194053540661979045656526063
r=32581479300404876772405716877547
assert p*q*r==n
#phi=(p-1)*(q-1)*(r-1)
#print(gmpy2.gcd(e,phi))
#3

with open("D:\\浏览器下载\\flag\\flag.enc",'rb')as f:
    c=bytes_to_long(f.read())
print(c)
R.<x> = Zmod(p)[]
f = x^e-c
f = f.monic()
results1 = f.roots()
print(results1)

R.<x> = Zmod(q)[]
f = x^e-c
f = f.monic()
results2 = f.roots()
print(results2)

R.<x> = Zmod(r)[]
f = x^e-c
f = f.monic()
results3 = f.roots()
print(results3)



for i in results1:
    for j in results2:
        for m in results3:
            m=crt([int(i[0]),int(j[0]),int(m[0])],[p,q,r])
            m=long_to_bytes(m)
            if b'0ctf{'in m:
                print(m)
                break

#b'\x02\xd1^\xcb\x84\x84RC\xf3J\x000ctf{HahA!Thi5_1s_n0T_rSa~}\n'

[NepCTF 2022] 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 = 0x10001
    #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
"""

题解

yafu分解n

image-20230714164516814

这里需要注意p和q的取值

p = 141264221379693044160345378758459195879285464451894666001807667429134348549398732060237738374405784248735752195059908618618110595213605790125890251970818437656069617772772793421437649079362238861287098916200835889507111259332056471215428085418047179545017193159169629731673653136069647622114441162534727202901
q = 141264221379693044160345378758459195879285464451894666001807667429134348549398732060237738374405784248735752195059908618618110595213605790125890251970818437656069617772772793421437649079362238861287098916200835889507111259332056471215428085418047179545017193159169629731673653136069647622114441162534727202891
assert n==p*q
#  q = p + 1
if q<p:
    t=q
    q=p
    p=t

p,q取反会影响后面的crt结果

phi=(p-1)*(q-1)
gg=gcd(e,phi)
print(gg)
#1

可以求出d，但是缺少c

{cp≡c(mod  p)cq≡c(mod  q)\begin{cases} c_p\equiv c (mod\ \ p)\\ c_q\equiv c (mod\ \ q)\\ \end{cases}

利用crt求解出c

wp

import gmpy2
from Crypto.Util.number import long_to_bytes

n = 19955580242010925349026385826277356862322608500430230515928936214328341334162349408990409245298441768036250429913772953915537485025323789254947881868366911379717813713406996010824562645958646441589124825897348626601466594149743648589703323284919806371555688798726766034226044561171215392728880842964598154362131942585577722616354074267803330013886538511795383890371097812191816934883393255463554256887559394146851379087386846398690114807642170885445050850978579391063585254346364297374019309370189128443081285875218288166996242359495992824824109894071316525623741755423467173894812627595135675814789191820979950786791
e = 65537
c_mod_p = 32087476819370469840242617415402189007173583393431940289526096277088796498999849060235750455260897143027010566292541554247738211165214410052782944239055659645055068913404216441100218886028415095562520911677409842046139862877354601487378542714918065194110094824176055917454013488494374453496445104680546085816
c_mod_q = 59525076096565721328350936302014853798695106815890830036017737946936659488345231377005951566231961079087016626410792549096788255680730275579842963019533111895111371299157077454009624496993522735647049730706272867590368692485377454608513865895352910757518148630781337674813729235453169946609851250274688614922



p = 141264221379693044160345378758459195879285464451894666001807667429134348549398732060237738374405784248735752195059908618618110595213605790125890251970818437656069617772772793421437649079362238861287098916200835889507111259332056471215428085418047179545017193159169629731673653136069647622114441162534727202901
q = 141264221379693044160345378758459195879285464451894666001807667429134348549398732060237738374405784248735752195059908618618110595213605790125890251970818437656069617772772793421437649079362238861287098916200835889507111259332056471215428085418047179545017193159169629731673653136069647622114441162534727202891
assert n==p*q
#  q = p + 1
if q<p:
    t=q
    q=p
    p=t
phi=(p-1)*(q-1)
gg=gcd(e,phi)
print(gg)
#1
d=inverse_mod(e,phi)
#1252990107815050396131095071106875863839625463162341861437776714252424196867083751438050781152678454544290561348477588314424473974689219719915628330383292496262245806653795391680166551537602119522395725446199697857165189662727850129646294082998077471030893379415607095699225984851603694723276083262879311002929800558428024700747018831268269585502183294987547669372754175415834581968714034535861714455512875208618004858007748676310828573704007774858023825900743373244384093983022857223181677619286464710238287796148593564498619278346936626883260434122906742989245858429095035901635408963549294384055658232382801968473d

c=crt([c_mod_q,c_mod_p],[q,p])
#8369827206646471725648221280443642913388486837857749422377443709344056256739630346534533146105632597070721439934856655940395342623231741478262231476476895787866760088192669327162635088142879029056171991584770144825818324801483521699151523102578319030073063876821271650020632690304932408057713155174759408880939994952627594837104668073211723138636793527906462930731423037213763838952491695586071368029327643093468179086573397581451391513348430378745870919639874205430206113452479543035880405912439274954646894037894109316588387682278704190062477033823342378579047291423599761218381843437513666136897007886110262414183

print(c)
m=int(pow(c,d,n))
print(long_to_bytes(m))

#NepCTF{ju5t_d0_f4ct_4nd_crt_th3n_d3crypt}'

中国剩余定理

构造mp,mq,求解出q

image-20230718124254862