2024XYCTF

发表于 2024-04-26 更新于 2024-04-28 分类于 Wp 阅读次数： Waline：本文字数： 7.5k 阅读时长 ≈ 27 分钟

记录2024XYCTF——Crypto题解

Crypto

Sign1n[签到]

task.py

from Crypto.Util.number import *
from tqdm import *
import gmpy2
flag=b'XYCTF{uuid}'
flag=bytes_to_long(flag)
leak=bin(int(flag))
while 1:
    leak += "0"
    if len(leak) == 514:
        break

def swap_bits(input_str):
    input_list = list(input_str[2:])
    length = len(input_list)

    for i in range(length // 2):
        temp = input_list[i]
        input_list[i] = input_list[length - 1 - i]
        input_list[length - 1 - i] = temp

    return ''.join(input_list)

input_str = leak
result = swap_bits(input_str)
a=result

def custom_add(input_str):
    input_list = list(input_str)
    length = len(input_list)
    
    for i in range(length):
        input_list[i] = str((int(input_list[i]) + i + 1) % 10)

    result = ''.join(input_list)
    return result


input_str = a
result = custom_add(input_str)
b=result
print(b)
#12345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567891134567789112455679912235677900123557889112356679001245568890233457780113355689901335667991134457889122355788001345578891133566790113445688902335578800124456899022346779902344567991223557880013445689911245667801134456799122355788001344578891223467799112455678912235667900123556899022346779001245578801233467789112355779912234577990233556780113

关键在于

def custom_add(input_str):
    input_list = list(input_str)
    length = len(input_list)
    
    for i in range(length):
        input_list[i] = str((int(input_list[i]) + i + 1) % 10)

    result = ''.join(input_list)
    return result

这个i+1我们能控制，只需要爆破一下input_list[i]即可，求出后把多余的0去掉即可

因为flag括号内是uuid形式，所以flag长度为43，转成int类型大概343或344bit

exp

c = "12345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567891134567789112455679912235677900123557889112356679001245568890233457780113355689901335667991134457889122355788001345578891133566790113445688902335578800124456899022346779902344567991223557880013445689911245667801134456799122355788001344578891223467799112455678912235667900123556899022346779001245578801233467789112355779912234577990233556780113"

c = list(c)

m = ""
for i in range(len(c)):
    idx = i+1
    if (idx + 0) % 10 == int(c[i]):
        m += "0"
    if (idx + 1) % 10 == int(c[i]):
        m += "1"
        
print(m)
def swap_bits(input_str):
    input_list = list(input_str[2:])
    length = len(input_list)

    for i in range(length // 2):
        temp = input_list[i]
        input_list[i] = input_list[length - 1 - i]
        input_list[length - 1 - i] = temp

    return ''.join(input_list)

mm = swap_bits(m)
# print(mm)

flag = bytes.fromhex(hex(int(mm[:343],2))[2:])
print(flag)
# XYCTF{cbd30ec3-469c-49bb-b757-354edbc1474d}

happy_to_solve1

task.py

from Crypto.Util.number import *
import sympy
from secrets import flag


def get_happy_prime():
    p = getPrime(512)
    q = sympy.nextprime(p ^ ((1 << 512) - 1))
    return p, q


m = bytes_to_long(flag)
p, q = get_happy_prime()
n = p * q
e = 65537
print(n)
print(pow(m, e, n))
# 24852206647750545040640868093921252282805229864862413863025873203291042799096787789288461426555716785288286492530194901130042940279109598071958012303179823645151637759103558737126271435636657767272703908384802528366090871653024192321398785017073393201385586868836278447340624427705360349350604325533927890879
# 14767985399473111932544176852718061186100743117407141435994374261886396781040934632110608219482140465671269958180849886097491653105939368395716596413352563005027867546585191103214650790884720729601171517615620202183534021987618146862260558624458833387692782722514796407503120297235224234298891794056695442287

q = sympy.nextprime(p ^ ((1 << 512) - 1))，说明$p+q \approx 2^{512}$

然后用费马分解法加简单爆破即可

exp

from Crypto.Util.number import *
import gmpy2

n = 24852206647750545040640868093921252282805229864862413863025873203291042799096787789288461426555716785288286492530194901130042940279109598071958012303179823645151637759103558737126271435636657767272703908384802528366090871653024192321398785017073393201385586868836278447340624427705360349350604325533927890879
c = 14767985399473111932544176852718061186100743117407141435994374261886396781040934632110608219482140465671269958180849886097491653105939368395716596413352563005027867546585191103214650790884720729601171517615620202183534021987618146862260558624458833387692782722514796407503120297235224234298891794056695442287

tmp = gmpy2.iroot((2**1024-4*n),2)[0]		# p-q
p = (tmp + 2**512) // 2						# p+q = 2**512

while 1:
    p = gmpy2.next_prime(p)
    if n % p == 0:
        q = n // p
        d = gmpy2.invert(65537,(p-1)*(q-1))
        m = pow(c,d,n)
        print(long_to_bytes(m))
        break
        # XYCTF{3f22f4efe3bbbc71bbcc999a0a622a1a23303cdc}

happy_to_solve2

task.py

import random
from Crypto.Util.number import *
from secrets import flag


def get_happy_prime():
    while 1:
        p = int("".join([random.choice("123") for _ in range(512)]))
        q = int("".join([random.choice("567") for _ in range(512)]))
        if isPrime(p) and isPrime(q):
            return (p,q)

m = bytes_to_long(flag)
p ,q= get_happy_prime()
n = p * q
e = 65537
print(n)
print(pow(m, e, n))
# 697906506747097082736076931509594586899561519277373830451275402914416296858960649459482027106166486723487162428522597262774248272216088755005277069446993003521270487750989061229071167729138628583207229945902389632065500739730301375338674342457656803764567184544685006193130563116558641331897204457729877920989968662546183628637193220770495938729301979912328865798266631957128761871326655572836258178871966196973138373358029531478246243442559418904559585334351259080578222274926069834941166567112522869638854253933559832822899069320370733424453856240903784235604251466010104012061821038897933884352804297256364409157501116832788696434711523621632436970698827611375698724661553712549209133526623456888111161142213830821361143023186927163314212097199831985368310770663850851571934739809387798422381702174820982531508641022827776262236373967579266271031713520262606203067411268482553539580686495739014567368858613520107678565628269250835478345171330669316220473129104495659093134763261751546990704365966783697780787341963138501
# 15338382608510229658123853967766869664415614805902686881375901510613913129713509783166104849307940522697222249215135610575923574950232430304703734941070902115225531542928076063911372434583653208797091845335372309055445058165793084767493022611384017236866283875644636448297709247897983820939676127932653341969905620998372184248499615002540300964465367892802586144532471541989379701587554152559013584302731232223608558157145208447726258296697270257713690438574144387052720564087444661641391723126013336422724892849257461024888113736420491400141226974046185174788335541496849927294459007162322360350169800422775333555264671556780282575579959795540922800428473974374953127083308485011357471204122489604452529259126463745279715109880260418631172459745078052014041370469737420965336996945150162758346789316041278073257508584646728913492088678995233817419320223417529965268756023259321213169345696631867084360523895872412636818528970356359147704910553852824463243486996533372269183746259112837981658272336703967402861994705714454

p由1,2,3构成，q由5,6,7构成，写个深搜就行

exp.py

from Crypto.Util.number import *
import itertools
import gmpy2

n = 697906506747097082736076931509594586899561519277373830451275402914416296858960649459482027106166486723487162428522597262774248272216088755005277069446993003521270487750989061229071167729138628583207229945902389632065500739730301375338674342457656803764567184544685006193130563116558641331897204457729877920989968662546183628637193220770495938729301979912328865798266631957128761871326655572836258178871966196973138373358029531478246243442559418904559585334351259080578222274926069834941166567112522869638854253933559832822899069320370733424453856240903784235604251466010104012061821038897933884352804297256364409157501116832788696434711523621632436970698827611375698724661553712549209133526623456888111161142213830821361143023186927163314212097199831985368310770663850851571934739809387798422381702174820982531508641022827776262236373967579266271031713520262606203067411268482553539580686495739014567368858613520107678565628269250835478345171330669316220473129104495659093134763261751546990704365966783697780787341963138501
e = 65537
c = 153383826085102296581238539677668696644156148059026868813759015106139131297135097831661048493079405226972222492151356105759235749502324303047037349410709021152255315429280760639113724345836532087970918453353723090554450581657930847674930226113840172368662838756446364482977092478979838209396761279326533419699056209983721842484996150025403009644653678928025861445324715419893797015875541525590135843027312322236085581571452084477262582966972702577136904385741443870527205640874446616413917231260133364227248928492574610248881137364204914001412269740461851747883355414968499272944590071623223603501698004227753335552646715567802825755799597955409228004284739743749531270833084850113574712041224896044525292591264637452797151098802604186311724597450780520140413704697374209653369969451501627583467893160412780732575085846467289134920886789952338174193202234175299652687560232593212131693456966318670843605238958724126368185289703563591477049105538528244632434869965333722691837462591128379816582723367039674028619947057144546


def findp(p,q):
    l = len(p)
    if l == 512 and n % int(p) == 0:
        q = n // int(p)
        print(f"p = {p}")
        print(f"q = {q}")
        d = gmpy2.invert(e,(int(p)-1)*(int(q)-1))
        m = pow(c,d,n)
        print(long_to_bytes(m))
    else:
        table1 = ["1","2","3"]
        table2 = ["5","6","7"]
        for i in table1:
            for j in table2:
                pp = int(i + p)
                qq = int(j + q)
                if pp * qq % 10**l == n % 10**l:
                    findp(i+p,j+q)

# findp('1','5')
# findp('1','7')
# findp('3','5')
findp('3','7')

素数最低位只可能是奇数，只需要考虑1,5,1,7,3,5,3,7即可

happy_to_solve3

task.py

import gmpy2
from Crypto.Util.number import *
import random
from secrets import flag

n = 1024
rho = 2
gamma = 0.352
delta = (1 - gamma) / 2


def get_happy_prime():
    p = getPrime(n // 2)
    q = getPrime(n // 2)
    N = p * q
    if 2 * q - p > gmpy2.iroot(N, 3)[0] and 2 * q - p < int(N**gamma / 16):
        d = random.randint(int(N ** (delta - 0.001)), int(N**delta))
        e = gmpy2.invert(d, (p - 1) * (q - 1))
        return N, e


N, e = get_happy_prime()
m = bytes_to_long(flag)
print(N)
print(e)
print(pow(m, e, N))
# 262520792590557046276663232446026434827811478251833823563978322470880473096166170973396967071440576532100045206129176936699321058518888771220060450723297988984995658582283884954240129867538637146924315603797818982078845855992582229939200744016516540207525916858674450616913948112117516831530578235916528257187
# 202935305174706906986376186864051444100197589482194720650385604617995167023220940138899902073948844285283834058445151666398192104922822110762965750590312021079147170573038600118139119881722125346545331027913695559130179278058419339157557267195396326664433859683010193688491694572425231599139974726246205888139
# 66173406204647583141174847814283540389326401056490970592017577810775087017197392456634167609680060931553017712058528056769618111925816921272571306246667527546366331057781905353553621522209713637253380859235235590286779517552635935384231694255450099095196595516174794966487058693308544109311774074970769293357

第一感觉是出自某论文，关键词"RSA" "d < n^0.324"，搜到名为Revisiting Wiener’s Attack – New Weak Keys in RSA的论文

228.pdf (iacr.org)，根据题目条件，定位到论文的Proposition 2，就是把$\frac{e}{n-\lceil\frac{3}{\sqrt{2}}\sqrt{n}\rceil+1}$作为$\frac{k}{d}$的收敛子

exp

from Crypto.Util.number import *
import gmpy2

n = 262520792590557046276663232446026434827811478251833823563978322470880473096166170973396967071440576532100045206129176936699321058518888771220060450723297988984995658582283884954240129867538637146924315603797818982078845855992582229939200744016516540207525916858674450616913948112117516831530578235916528257187
e = 202935305174706906986376186864051444100197589482194720650385604617995167023220940138899902073948844285283834058445151666398192104922822110762965750590312021079147170573038600118139119881722125346545331027913695559130179278058419339157557267195396326664433859683010193688491694572425231599139974726246205888139
c = 66173406204647583141174847814283540389326401056490970592017577810775087017197392456634167609680060931553017712058528056769618111925816921272571306246667527546366331057781905353553621522209713637253380859235235590286779517552635935384231694255450099095196595516174794966487058693308544109311774074970769293357

# n = 227356514376456085145407643699497785267575964192664414706015618659113920770516068763728136578026699605165351438105331282008556258187994169710089246109279146381472361264666736466411449942059568093916061632275622633234439324940363916123064654025553033995485190281219787597633737574334427577414563344330427377471759256645329
# e = 85356738187677927267094758044990579754357485762742350715347494115752841684037367619580505169859555149633498979366195155524089607956973186706608891521632808424477556097376663853312064312353402461172064273993869764933453316151177386412753448356073872108358709307048969215446586611896268736369229047317637983628682308907311
n_2 = sqrt(n)

temp = int(n_2 * 3 / sqrt(2)) + 1

phi = n - temp + 1
cf = continued_fraction(e / phi)
for i in range(1,1000):
    k = cf.numerator(i)
    d = cf.denominator(i)
    if (e*d - 1) % k == 0:
        print(d)
        m = pow(c,d,n)
        print(long_to_bytes(int(m)))
       	# XYCTF{68f1880cdafd99fbf9a156946cb39dd86477886f1d115636e149e12c16f99af0}

开根号建议用sqrt，别用gmpy2.iroot

factor1

task.py

import gmpy2
import hashlib
from Crypto.Util.number import *

p = getPrime(512)
q = getPrime(512)
d = getPrime(512)
e = gmpy2.invert(d, (p**3 - 1) * (q**3 - 1))
flag = "XYCTF{" + hashlib.md5(str(p + q).encode()).hexdigest() + "}"
print(e)
print(p * q)
# 172005065945326769176157335849432320425605083524943730546805772515111751580759726759492349719668775270727323745284785341119685198468883978645793770975366048506237371435027612758232099414404389043740306443065413069994232238075194102578269859784981454218948784071599231415554297361219709787507633404217550013282713899284609273532223781487419770338416653260109238572639243087280632577902857385265070736208291583497988891353312351322545840742380550393294960815728021248513046077985900158814037534487146730483099151396746751774427787635287611736111679074330407715700153025952858666841328055071403960165321273972935204988906850585454805923440635864200149694398767776539993952528995717480620593326867245714074205285828967234591508039849777840636255379730281105670496110061909219669860172557450779495125345533232776767292561378244884362014224844319802810586344516400297830227894063759083198761120293919537342405893653545157892446163
# 99075185389443078008327214328328747792385153883836599753096971412377366865826254033534293886034828804219037466246175526347014045811852531994537520303063113985486063022444972761276531422538694915030159420989401280012025249129111871649831185047820236417385693285461420040134313833571949090757635806658958193793

$$
\because ed \equiv 1 \mod (p^3-1)(q^3 - 1)
$$

$$
\therefore ed = k(p^3-1)(q^3-1) + 1
$$

$p^3 - 1\approx p^3$，$q^3-1\approx q^3$
$$
\therefore ed = kn^3 + 1
$$
同除$d\times n^3$有
$$
\frac{e}{n^3} = \frac{k}{d} + \frac{1}{d\times n^3}
$$
即
$$
\frac{e}{n^3} \approx \frac{k}{d}
$$
连分数展开求得$(p^3-1)(q^3-1)$

然后联立$n = p\times q$解方程即可

exp

import hashlib
from tqdm import *

n = 99075185389443078008327214328328747792385153883836599753096971412377366865826254033534293886034828804219037466246175526347014045811852531994537520303063113985486063022444972761276531422538694915030159420989401280012025249129111871649831185047820236417385693285461420040134313833571949090757635806658958193793
e = 172005065945326769176157335849432320425605083524943730546805772515111751580759726759492349719668775270727323745284785341119685198468883978645793770975366048506237371435027612758232099414404389043740306443065413069994232238075194102578269859784981454218948784071599231415554297361219709787507633404217550013282713899284609273532223781487419770338416653260109238572639243087280632577902857385265070736208291583497988891353312351322545840742380550393294960815728021248513046077985900158814037534487146730483099151396746751774427787635287611736111679074330407715700153025952858666841328055071403960165321273972935204988906850585454805923440635864200149694398767776539993952528995717480620593326867245714074205285828967234591508039849777840636255379730281105670496110061909219669860172557450779495125345533232776767292561378244884362014224844319802810586344516400297830227894063759083198761120293919537342405893653545157892446163

cf = continued_fraction(Integer(e) / Integer(n^3))

# for i in trange(2,2000):
#     k = int(cf.numerator(i))       #取连分数的分子
#     d = int(cf.denominator(i))
#     if (e*d - 1)%k == 0:
#         print(f"k = {k}")
#         print(f"d = {d}")

k = 1494016303704162064457264904035459059241052443477469129020991127731711502975536480528822831565100775167693515363479900721259984367515846296462994230670260
d = 8447122254265361577759220083550460887840558233627984117576685838469227480934556534673167325385487344741530262745308367064419215281251764917289925433582347

# phi = (e * d - 1) // k
# f1 = (p^3 - 1)*(q^3 - 1) == phi
# f2 = p*q == n
# res = solve([f1,f2],[p,q])
# print(res)

p = 9212046353930376594996890089494718736894378991991381248242532319628627449681664076081705664941905594411935750003102856235503684466394327681725704255564467
q = 10754959493573546439510276829300246769373124436128170955050379041986504869221750743052397622171703140881050431144683659643071578143360949942206693325622779
flag = "XYCTF{" + hashlib.md5(str(p + q).encode()).hexdigest() + "}"
print(flag)
# XYCTF{a83211a70e18145a59671c08ddc67ba4}

factor3

task.py

from Crypto.Util.number import *
import random

flag = b'XYCTF{*****}'
m = bytes_to_long(flag)
def gainPrime():
    while True:
        x = random.getrandbits(256)
        y = random.getrandbits(256)

        if y % 2 == 0:
            continue

        p = x ** 3 + 3 * y ** 3
        if p.bit_length() == 768 and p % 2 == 1 and isPrime(p):
            return p

p, q = gainPrime(), gainPrime()
N = p * q
phi = (p ** 2 + p + 1) * (q ** 2 + q + 1)
d = getPrime(320)
e = inverse(d, phi)
c = d**2^m

print(f"N: {N}")
print(f"e: {e}")
print(f"c: {c}")

N: 913125842482770239379848062277162627509794409924607555622246822717218133091223291889541294440266178282194506242444509803611492259403578922020590849630191477864719052980160940803309686069818208833547621252544423652489179493083138385424424384165228024273745733240109761707533778691158938848158094054261174692601673435971526522219273943464877956131040249169850420336023942653021547841666224446678539579529590840999008107782784268926145671962239929431694391039559247
e: 494518390582436635999115147756676313570637682518235195828939117782099618734167908630788943568232122157772909140885391963441876427590731524706959546524212914108888799081844320513851526790475333924396837458796755678072486028072639014677580265244176441153444956871730684233063789931539669072735599696830757690822185323538738397827461580678488181113667710378657058297572328491762536595872579603698945272140918157163640403488075948987156585480146162739943419183496337465468187233821931312507662218106713861638334075899266373256620752680354704533272722692596941861606161634082613228896420520465402725359166156632884432690715903666803067996854084671477445131853993177110154928274312496230096270510089973592664248613332000290545537840595645944390047611474888693558676781309912289044962293014118087259307560444929227407113819165713213046898243995956550944640168932947118400215917515277554126694376415569909534496134700668701465649939
c: 4450931337369461482106945992542133557585962894030505065110870389112565329875502952762182372926117037373210509516570958483606566274369840551132381128665744266165792377925899683228751870742727716

参考论文：1160.pdf (iacr.org)

攻击条件是：$ed \equiv 1 \mod (p^2+p+1)(q^2+q+1)$，$e = N^{\alpha},\frac{3}{2}<\alpha<\frac{5}{2}$，$d = N^{\delta},\delta < \frac{5}{4} -\frac{1}{2}\alpha$

本题$\alpha \approx 1.999$，$\delta = 0.208$，满足式子$\delta < \frac{5}{4}-\frac{1}{2}\alpha$

只需要把$\phi(n_0)$用论文中提到的式子代替，然后连分数展开，我们就可以得到d

exp

from Crypto.Util.number import *

n = 913125842482770239379848062277162627509794409924607555622246822717218133091223291889541294440266178282194506242444509803611492259403578922020590849630191477864719052980160940803309686069818208833547621252544423652489179493083138385424424384165228024273745733240109761707533778691158938848158094054261174692601673435971526522219273943464877956131040249169850420336023942653021547841666224446678539579529590840999008107782784268926145671962239929431694391039559247
e = 494518390582436635999115147756676313570637682518235195828939117782099618734167908630788943568232122157772909140885391963441876427590731524706959546524212914108888799081844320513851526790475333924396837458796755678072486028072639014677580265244176441153444956871730684233063789931539669072735599696830757690822185323538738397827461580678488181113667710378657058297572328491762536595872579603698945272140918157163640403488075948987156585480146162739943419183496337465468187233821931312507662218106713861638334075899266373256620752680354704533272722692596941861606161634082613228896420520465402725359166156632884432690715903666803067996854084671477445131853993177110154928274312496230096270510089973592664248613332000290545537840595645944390047611474888693558676781309912289044962293014118087259307560444929227407113819165713213046898243995956550944640168932947118400215917515277554126694376415569909534496134700668701465649939
c = 4450931337369461482106945992542133557585962894030505065110870389112565329875502952762182372926117037373210509516570958483606566274369840551132381128665744266165792377925899683228751870742727716

n_2 = sqrt(n)
temp = 0.5*(n + n_2 + 1)^2 + 0.5*(n + 0.75*sqrt(2)*n_2 + 1)^2 + 0.1875*n

cf = continued_fraction(e / temp)

for i in range(1,1000):
    k = cf.numerator(i)
    d = cf.denominator(i)
    if (e*d - 1) % k == 0 and int(d).bit_length() == 320:
        print(f"k = {k}")
        print(f"d = {d}")
        m = c ^^ d^2
        print(long_to_bytes(int(m)))
        # XYCTF{I_love_to_read_the_crypto_paper_and_try_to_ak_them}

babyRSAMAX

task.py

from Crypto.Util.number import *
from gmpy2 import *
from random import choice

flag = b'XYCTF{******}'
e = '?'
def getBabyPrime(nbits):
    while True:
        p = 1
        while p.bit_length() <= nbits:
            p *= choice(sieve_base)
        
        if isPrime(p+1):
            return p+1

p = getBabyPrime(512)
q = getBabyPrime(512)
n = p*q
gift1 = (pow(p,e,n)-pow(q,e,n)) % n
gift2 = pow(p+q,e,n)

t = 65537
x = bytes_to_long(e)
y = pow(x, t, n)

m = bytes_to_long(flag)
c = powmod(m, e, n)

print(f'n = {n}')
print(f'gift1 = {gift1}')
print(f'gift2 = {gift2}')
print(f'c = {c}')
print(f'y = {y}')

'''
n = 39332423872740210783246069030855946244104982381157166843977599780233911183158560901377359925435092326653303964261550158658551518626014048783435245471536959844874036516931542444719549997971482644905523459407775392702211086149279473784796202020281909706723380472571862792003687423791576530085747716706475220532321
gift1 = 4549402444746338327349007235818187793950285105091726167573552412678416759694660166956782755631447271662108564084382098562999950228708300902201571583419116299932264478381197034402338481872937576172197202519770782458343606060544694608852844228400457232100904217062914047342663534138668490328400022651816597367310
gift2 = 111061215998959709920736448050860427855012026815376672067601244053580566359594802604251992986382187891022583247997994146019970445247509119719411310760491983876636264003942870756402328634092146799825005835867245563420135253048223898334460067523975023732153230791136870324302259127159852763634051238811969161011462
c = 16938927825234407267026017561045490265698491840814929432152839745035946118743714566623315033802681009017695526374397370343984360997903165842591414203197184946588470355728984912522040744691974819630118163976259246941579063687857994193309554129816268931672391946592680578681270693589911021465752454315629283033043
y = 1813650001270967709841306491297716908969425248888510985109381881270362755031385564927869313112540534780853966341044526856705589020295048473305762088786992446350060024881117741041260391405962817182674421715239197211274668450947666394594121764333794138308442124114744892164155894256326961605137479286082964520217

'''

需要先求e，求e得先把n分解了
$$
\because gift_1\equiv p^e - q^e \mod n
$$

$$
gift_2 \equiv (p+q)^e \equiv p^e + q^e \mod n
$$

则有
$$
gift_1 \equiv p^e \mod q
$$

$$
\therefore gift_2 \equiv p^e \mod q
$$

则gcd(gift1 - gift2,n) = q

n分解后解出e = 4096，一眼12次Rabin，网上找个脚本套用即可

exp

from Crypto.Util.number import *
import gmpy2

n = 39332423872740210783246069030855946244104982381157166843977599780233911183158560901377359925435092326653303964261550158658551518626014048783435245471536959844874036516931542444719549997971482644905523459407775392702211086149279473784796202020281909706723380472571862792003687423791576530085747716706475220532321
gift1 = 4549402444746338327349007235818187793950285105091726167573552412678416759694660166956782755631447271662108564084382098562999950228708300902201571583419116299932264478381197034402338481872937576172197202519770782458343606060544694608852844228400457232100904217062914047342663534138668490328400022651816597367310
gift2 = 111061215998959709920736448050860427855012026815376672067601244053580566359594802604251992986382187891022583247997994146019970445247509119719411310760491983876636264003942870756402328634092146799825005835867245563420135253048223898334460067523975023732153230791136870324302259127159852763634051238811969161011462
c = 16938927825234407267026017561045490265698491840814929432152839745035946118743714566623315033802681009017695526374397370343984360997903165842591414203197184946588470355728984912522040744691974819630118163976259246941579063687857994193309554129816268931672391946592680578681270693589911021465752454315629283033043
y = 1813650001270967709841306491297716908969425248888510985109381881270362755031385564927869313112540534780853966341044526856705589020295048473305762088786992446350060024881117741041260391405962817182674421715239197211274668450947666394594121764333794138308442124114744892164155894256326961605137479286082964520217
t = 65537

q = gmpy2.gcd(gift1-gift2,n)
p = n // q

phi = (p-1)*(q-1)
d = gmpy2.invert(t,phi)
e = long_to_bytes(pow(y,d,n))
# XYCTF{e==4096}

e = 4096
# print(gmpy2.gcd(e,phi))

inv_p = gmpy2.invert(p, q)
inv_q = gmpy2.invert(q, p)
cs = [c]
for i in range(12):
    ps = []
    for c2 in cs:
        r = pow(c2, (p + 1) // 4, p)
        s = pow(c2, (q + 1) // 4, q)

        x = (r * inv_q * q + s * inv_p * p) % n
        y = (r * inv_q * q - s * inv_p * p) % n
        if x not in ps:
            ps.append(x)
        if n - x not in ps:
            ps.append(n - x)
        if y not in ps:
            ps.append(y)
        if n - y not in ps:
            ps.append(n - y)
    cs = ps

for m in cs:
    print(long_to_bytes(m))
    # XYCTF{Rabin_is_so_biggggg!}

x0y

task.py

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import os

flag = open("flag.txt", "rb").read()
key = os.urandom(16)
iv = os.urandom(16)
flag = pad(flag, 16)


def aes_encrypt(key, plaintext):
    cipher = AES.new(key, AES.MODE_ECB)
    return cipher.encrypt(plaintext)


def encrypt(key, plaintext, iv):
    ciphertext = b""
    for i in range(0, len(plaintext), AES.block_size):
        key_block = aes_encrypt(key, iv)
        ciphertext_block = bytes(
            [plaintext[i + j] ^ key_block[j] for j in range(AES.block_size)]
        )
        ciphertext += ciphertext_block
        iv = key_block
    return ciphertext


while 1:
    try:
        print("1.print\n2.input\n3.exit")
        a = input("> ")
        if a == "1":
            print((iv + encrypt(key, flag, iv)).hex())
        elif a == "2":
            ivs = bytes.fromhex(input("iv: "))
            inputs = bytes.fromhex(input("message: "))
            print(encrypt(key, inputs, ivs).hex())
        elif a == "3":
            exit(0)
        else:
            print("You need input 1,2,3")
    except:exit(0)

注意到加密的时候是把明文块中每个明文和加密后的iv进行异或

而输入1之后我们是可以得到iv和加密后的flag，输入2可以让我们输入自己的iv和想加密的信息

根据异或的特性只要把iv和密文输入，服务器就会帮我们解密出明文

exp

from pwn import *

sh = remote("xyctf.top",port)

sh.recvline()
sh.recvline()
sh.recvline()
sh.sendlineafter(b">",b"1")
msg = sh.recvline().decode().strip()

iv = msg[:32]
cipher = msg[32:]
sh.sendline(b"2")
sh.sendlineafter(b"iv:",iv.encode())
sh.sendlineafter(b"message:",cipher.encode())
m = sh.recvline().decode().strip()

flag = bytes.fromhex(m)
print(flag)
# XYCTF{eddbb551-df9c-4723-897b-101538b64ea2}

Complex_dlp

task.py

from Crypto.Util.number import *
from secrets import flag


class Complex:
    def __init__(self, re, im):
        self.re = re
        self.im = im

    def __mul__(self, c):
        re_ = self.re * c.re - self.im * c.im
        im_ = self.re * c.im + self.im * c.re
        return Complex(re_, im_)

    def __str__(self):
        if self.im == 0:
            return str(self.re)
        elif self.re == 0:
            if abs(self.im) == 1:
                return f"{'-' if self.im < 0 else ''}i"
            else:
                return f"{self.im}i"
        else:
            return f"{self.re} {'+' if self.im > 0 else '-'} {abs(self.im)}i"


def complex_pow(c, exp, n):
    result = Complex(1, 0)
    while exp > 0:
        if exp & 1:
            result = result * c
            result.re = result.re % n
            result.im = result.im % n
        c = c * c
        c.re = c.re % n
        c.im = c.im % n
        exp >>= 1
    return result


flag = flag.strip(b"XYCTF{").strip(b"}")
p = 1127236854942215744482170859284245684922507818478439319428888584898927520579579027
g = Complex(3, 7)
x = bytes_to_long(flag)
print(complex_pow(g, x, p))
# 5699996596230726507553778181714315375600519769517892864468100565238657988087817 + 198037503897625840198829901785272602849546728822078622977599179234202360717671908i

没有接触过复数域dlp，所以第一想法是想着能不能把它转换到实数域，然后用实数域求解离散对数的方法来做

注意到复数的一个性质：

对于复数$a+bi$，它的模为$|a+bi| = \sqrt{a^2+b^2}$

而$(a+bi)^2 =a^2-b^2 + 2abi$，它的模为$|(a+bi)^2| = \sqrt{a^4+b^4-2a^2b^2+4a^2b^2} = a^2+b^2$

利用次方和模长的关系，对于本题有
$$
(3+7i)^x \equiv c_{re} + c_{im}i \mod p
$$
我们可以把它转换成
$$
|3+7i|^x \equiv |c_{re}+c_{im}i| \mod p
$$
可以平方一些，即
$$
(|3+7i|^2)^x \equiv |c_{re} + c_{im}i|^2 \mod p
$$

exp

p = 1127236854942215744482170859284245684922507818478439319428888584898927520579579027

g = 3^2 + 7^2
a = 5699996596230726507553778181714315375600519769517892864468100565238657988087817 
b = 198037503897625840198829901785272602849546728822078622977599179234202360717671908
c = (a^2 + b^2) % p

x = discrete_log(mod(c,p),mod(g,p))
flag = b"XYCTF{" + bytes.fromhex(hex(int(x))[2:]) + b"}"
print(flag)
# XYCTF{___c0mp13x_d1p_15_3@5y_f0r_y0u___}

反方向的密码相思

task.py

from Crypto.Util.number import *
import hashlib
from secrets import flag


def hash(x):
    return hashlib.sha256(x.encode()).digest()


def pad(message):
    return message + hash(str(len(message)))


m = bytes_to_long(pad(flag))
p = getStrongPrime(512)
q = getStrongPrime(512)
n = p * q
e = 3
print(pow(m, e, n))
print(n)
# 120440199294949712392334113337541924034371176306546446428347114627162894108760435789068328282135879182130546564535108930827440004987170619301799710272329673259390065147556073101312748104743572369383346039000998822862286001416166288971531241789864076857299162050026949096919395896174243383291126202796610039053
# 143413213355903851638663645270518081058249439863120739973910994223793329606595495141951165221740599158773181585002460087410975579141155680671886930801733174300593785562287068287654547100320094291092508723488470015821072834947151827362715749438612812148855627557719115676595686347541785037035334177162406305243

填充的信息可以用爆破的方式，相当于m的低位泄露，我们还可以利用上flag的头，这样就是m的高位加低位泄露

exp

from Crypto.Util.number import *
import hashlib

c = 120440199294949712392334113337541924034371176306546446428347114627162894108760435789068328282135879182130546564535108930827440004987170619301799710272329673259390065147556073101312748104743572369383346039000998822862286001416166288971531241789864076857299162050026949096919395896174243383291126202796610039053
n = 143413213355903851638663645270518081058249439863120739973910994223793329606595495141951165221740599158773181585002460087410975579141155680671886930801733174300593785562287068287654547100320094291092508723488470015821072834947151827362715749438612812148855627557719115676595686347541785037035334177162406305243

def hash(x):
    return hashlib.sha256(x.encode()).digest()

for i in range(10,40):									#i代表{}中未知数的个数
    prefix = bytes_to_long(b"XYCTF{") * 256^(32 + 1 + i)
    
    pad = hash(str(i+7))
    low = bytes_to_long(b"}" + pad)
    
    R.<x> = PolynomialRing(Zmod(n))
    
    f = (prefix + x*256^33 + low)^3 - c
    f = f.monic()
    res = f.small_roots(X=256^i)
    if res != []:
        m = prefix + int(res[0])*256^33 + low
        print(long_to_bytes(int(m)))

flag的长度应该比较普通，所以可以适当缩小范围，不过还需要注意flag拼接后的值

反方向的密码情难

task.py

import hashlib
from Crypto.Util.number import *
from secrets import flag


def hash(x):
    return hashlib.sha512(x.encode()).digest() * 2


def pad(message):
    return (message[: len(message) // 2] + hash(str(len(message))) + message[len(message) // 2 :])


p = getStrongPrime(1024)
q = getStrongPrime(1024)
n = p * q
e = 2
m = bytes_to_long(pad(flag))
print(pow(m, e, n))
print(n)
# 3335299537518434350008670067273514020883265809787658909900831303201069228111667477512288715627313377374377192065531931991830331266940281529429758933125645068623703704431432931062515459304407129764836169638068667723468109909932687335727824459807903558617156661138991973933280805156893120951135488168923425258119689993859896540097318197048436676318334502053269738046279338047497258783747007084564814994803144049365117574904704816542523015746396519693505167963245600047742456478545640334467678554748227823020862550712083249012329745708139070338928730226897923885785783461594034339595106377701306570280371612953393097739
# 26278624299187148406559772770865336226934633734285979741424867540828670397865189685966828527168795621543490979182417570078991930822041468539855006585233692884235331084907340302530060261742100702658312435180527335101284800616106884692498603300926488358017928867672861988448488439356448543527810620591324774111321619391264173779312033252573140028630441135269056099074531502841259940379636699304810677716177080486265721322966814104627525953974143476452058638927511594884002185219080847495835727300670028011001853179659250270200020884333850083063514830095064730932997593930711871108436386821290545084229347398808220810263

记len(flag) = l
$$
flag = m_1\times 256^{128 + \frac{l}{2}} + hash \times 256^{\frac{l}{2}} + m_2
$$

未知数为$m_1,m_2$，可以用二元copper

exp

def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()
    R = f.base_ring()
    N = R.cardinality()
    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)
    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)
    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)
    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)
    B = B.dense_matrix().LLL()
    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)
    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots
    return []

from Crypto.Util.number import *
import hashlib
import itertools
from tqdm import *

def hash(x):
    return hashlib.sha512(x.encode()).digest() * 2

def attack(l,n,c):
    R.<m1,m2> = PolynomialRing(Zmod(n))
    pad = bytes_to_long(hash(str(l)))
    if l % 2 == 1:
        f = (m1*2^(pad.bit_length() + 8*(l // 2)+8) + pad*2^(8*(l // 2)+8) + m2)^2 - c
        res = small_roots(f,bounds=(256^(l//2),256^(l//2+1)),m = 1,d=4)
        if res != []:
            x,y = res[0]
            m = x *2^(pad.bit_length() + 8*(l // 2)+8) + pad*2^(8*(l // 2)+8) + y
            msg = long_to_bytes(int(m))
            flag = msg[:l // 2] + msg[-(l//2 + 1):]
            print(flag)
            print(f"len(flag) = {l}")
    else:
        f = (m1*2^(pad.bit_length() + 8*(l // 2)) + pad*2^(8*(l // 2)) + m2)^2 - c
        res = small_roots(f,bounds=(256^(l//2),256^(l//2)),m = 1,d=4)
        if res != []:
            x,y = res[0]
            m = x *2^(pad.bit_length() + 8*(l // 2)) + pad*2^(8*(l // 2)) + y
            msg = long_to_bytes(int(m))
            flag = msg[:l // 2] + msg[-(l//2):]
            print(flag)
            print(f"len(flag) = {l}")

for l in trange(65,77):
    c = 3335299537518434350008670067273514020883265809787658909900831303201069228111667477512288715627313377374377192065531931991830331266940281529429758933125645068623703704431432931062515459304407129764836169638068667723468109909932687335727824459807903558617156661138991973933280805156893120951135488168923425258119689993859896540097318197048436676318334502053269738046279338047497258783747007084564814994803144049365117574904704816542523015746396519693505167963245600047742456478545640334467678554748227823020862550712083249012329745708139070338928730226897923885785783461594034339595106377701306570280371612953393097739
    n = 26278624299187148406559772770865336226934633734285979741424867540828670397865189685966828527168795621543490979182417570078991930822041468539855006585233692884235331084907340302530060261742100702658312435180527335101284800616106884692498603300926488358017928867672861988448488439356448543527810620591324774111321619391264173779312033252573140028630441135269056099074531502841259940379636699304810677716177080486265721322966814104627525953974143476452058638927511594884002185219080847495835727300670028011001853179659250270200020884333850083063514830095064730932997593930711871108436386821290545084229347398808220810263
    attack(l,n,c)

经测试，在二元copper中

m=1,d=3，可以有出长度为64的flag，相当于两个界都是$2^{256}$

m=1,d=4，可以有出长度为76的flag，相当于两个界都是$2^{304}$

重生之我要当oi爷 pro

task.py

def f(a, b, p):
    t = 0
    for i in range(len(b)):
        t += pow(a, i, p) * b[i] % p
    return t % p

p = 1041231053

a = open("flag.png", "rb").read()
b = open("enc.txt", "w")
for i in range(len(a)):
    b.write(str(i) + str(f(i, a, p)) + "\n")

题目的意思就是要恢复下面这个多项式的系数
$$
y_0 \equiv x_0^0b_0 + x_0^1b_1 + … + x_0^nb_n \mod p
$$

$$
y_1 \equiv x_1^0b_0 + x_1^1b_1 + … + x_1^nb_n \mod p
$$

$$
\vdots
$$

$$
y_n \equiv x_n^0b_0 + x_n^1b_1 + … + x_n^nb_n \mod p
$$

运用到多项式快速插值的知识，可以参考：多项式的多点求值和快速插值 - Cekavis’s notes

不过这道题来自picoCTF2024的flag_printer，找遍互联网只找到了一个wpGitHub - PetePriority/picoctf-2024: picoCTF 2024 writeups

这个exp对于原题需要6-7小时，本题跑了2-3小时就出了

output

flag{1A2Q3E71528AP49Q0RT}

fakeRSA

task.py

from Crypto.Util.number import *

flag = b'XYCTF{******}'
n = ZZ(bytes_to_long(flag))
p = getPrime(int(320))
print(p)

G = Zmod(p)

def function(X, Y, Z):
    def part(a, b, c):
        return vector([9 * a - 36 * c, 6 * a - 27 * c, b])
    def parts(n):
        Gx.<a, b, c> = G[]
        if n == 0: return vector([a, b, c])
        mid = parts(n // 2)
        result = mid(*mid)
        if n % 2 == 0: return result
        else: return part(*result)
    return parts(n)(X, Y, Z)

print(function(69, 48, 52))


#1849790472911267366045392456893126092698743308291512220657006129900961168811898822553602045875909
#(1431995965813617415860695748430644570118959991271395110995534704629241309597572003500157255135707, 1011565891130611736600822618382801465506651972373410962205810570075870804325974377971089090196019, 784497518859893244278116222363814433595961164446277297084989532659832474887622082585456138030246)

代码主要实现的是矩阵快速幂，part(a,b,c)可以用矩阵相乘的形式表示：

而最后可以表示为

an,bn,cn是我们最后得到的值，而a0,b0,c0 = 69,48,52

记

所以本题问题就是：

不过这个形式不像常规离散对数的形式$c \equiv g^x \mod p$

我们需要把它往这个形式转化，注意到

我们可以在原式子上添两行，凑出

因为a0,b0,c0以及an,bn,cn已知，所以补上的两行我们是可以求的

记为$B \equiv A\times L^n \mod p$

我们只需要做一个变换即可求得$L^n \equiv B\times A^{-1}\mod p$，记为$M$，或者通过sagemath解矩阵方程(推荐这个，因为我在乘逆矩阵的时候老是出错)

这个时候我们已知$L,L^n$，就相当于求解$M \equiv L^n \mod p$，不过这个L的形式不容易求离散对数

我们可以把矩阵L转为Jordan标准型(可以参考【矩阵论】Jordan 标准型及其求解方法 - 知乎 (zhihu.com)做个了解)，相当于有个矩阵P，使得

记Jordan标准化后的矩阵为$T$，即$P^{-1}LP = T$，则$L = PTP^{-1}$

即变为求解$M \equiv (PTP^{-1})^n \equiv PT^nP^{-1} \mod p$，也就是求解$P^{-1}MP^{-1} \equiv T^n \mod p$

因为矩阵T是Jordan标准型，他有这样的形式：

简单推导可以推断出

通过这个形式，我们可以很容易计算出$n = \frac{nt^{n-1} \times t}{t^n}$，对应$n = \frac{T[0][0]\times T^n[0][1]}{T^n[0][0]}$

exp

from Crypto.Util.number import *

p = 1849790472911267366045392456893126092698743308291512220657006129900961168811898822553602045875909
L = Matrix(Zmod(p),[
    [9,6,0],
    [0,0,1],
    [-36,-27,0]
])

A0 = vector(Zmod(p),[69,48,52])
A1 = A0 * L
A2 = A1 * L
An = vector(Zmod(p),[1431995965813617415860695748430644570118959991271395110995534704629241309597572003500157255135707, 1011565891130611736600822618382801465506651972373410962205810570075870804325974377971089090196019, 784497518859893244278116222363814433595961164446277297084989532659832474887622082585456138030246])
An1 = An * L
An2 = An1 * L

A = Matrix(Zmod(p),[A0,A1,A2])
B = Matrix(Zmod(p),[An,An1,An2])
M = A.solve_right(B)                                 # L^n

L_Jor, P = L.jordan_form(transformation=True)

T = L_Jor
Tn = ~P * M * P                                      # T^n

m = T[0][0] * Tn[0][1] // Tn[0][0]
flag = long_to_bytes(int(m))
print(flag)
# XYCTF{y0u_finally_f0und_t3h_s3cr3ts!!}

random_rr

task.py

from Crypto.Util.number import *
from random import randint

flag=b'XYCTF{uuid}'
flag = bytes_to_long(flag)

n = 472993274721871037103726599805149366727531552333249750035977291933239067588481589544777397613192273114354221827196579379954069925604091911249655707080927769808587176515295614018992848517984372306879552247519117116110554431341268358177159108949791969262793325836353834899335531293329721598226413212541536002401507477776699642647348576111445702197483449777741566350285229621935507081895389023444249054515395783080003733803406382744631528246608154546123270319561514117323480441428953306734274538511770278887429407127143049023747710881993279361892937905382946820141513009017756811296722630617325141162244806884220212939955235410280899112731530527048274396186038160728562551536558223235783656985493518204710943916486379681906506757757594165379493317173050550893487151879681122510523721157284728808336110950008840684602353984682117748018347433177541603140491131603068512706893984834735290809952944273565203183330739252949245209529232254867201402656024997949207918675051941911990640248052951780195402390132237903538546705181463959793972284823588987652138458328270662652334799233015314673544813649692428544375538627858921763941533600553536579901589575693816746953261108022490849251974419402753031545629158199093099096735356165044275617408697
rr = 11898141078345200236264081467585899457224809417108457314508072413792599039332439547789237898270544336909458761754683941320649771736625000667170176071314483

def generate():
    fw = open("random", "w")
    for i in range(648):
        fw.write(str(random.getrandbits(32))+"\n")
    fw.close()

generate()
key = str(random.getrandbits(32))
key1= int(str(key)[0])

ks = [randint(0, rr**(i+key1-1)) for i in range(16)]
c1 = pow(sum(k*flag**i for i, k in enumerate(ks)), 127, n)
c2 = pow(flag, 65537, n)
ks = [pow(69, k+key, rr**(i+key1)) for i, k in enumerate(ks)]

print(f"{ks = }")
print(f"{c1 = }")
print(f"{c2 = }")

前面是一个常规的随机数预测，套用脚本就能算出key = 3168111950，则key1 = 3

from extend_mt19937_predictor import ExtendMT19937Predictor

predictor = ExtendMT19937Predictor()
f = open("random","rb").readlines()

D = []
for i in range(len(f)):
    D.append(eval(f[i]))

for _ in range(648):
    predictor.setrandbits(D[_], 32)
key = predictor.predict_getrandbits(32)
key1= int(str(key)[0])
print(key)
# 3168111950

然后就是
$$
c_1 \equiv k_0\times flag^0 + k_1\times flag^1 + … + k_n\times flag^n \mod n
$$

$$
c_2 \equiv flag^{65537} \mod n
$$

以及$ks_i \equiv 69^{k_i+key} \mod rr^{i+key1}$，$key$和$key1$都是已知的

在鸡块师傅的博客中看过类似的题，因为模数至少都是3次幂，对这种模数来说可以用p-adic的discrete_log去计算出模p^(i-1)下的值，只有一次幂下难以求解。具体原理可以看鸡块师傅的解释->2024-bi0sCTF-wp-crypto | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

求解完这个dlp问题之后就可以求得$k_i$了，然后就是两个明文做gcd，由于度比较大所以选择HGCD，同时由于两个多项式根相同，所以可以将f2先模f1后再做HGCD能更节省时间。

exp

from Crypto.Util.number import *
from random import randint
from tqdm import *

n = 
rr = 
ks = [...]
c1 = 
c2 = 
final = []

#part1 dlog by p-adic
for i in trange(16):
    R = Zp(rr, prec=i+3)
    x = (R(ks[i]).log() / R(69).log()).lift()
    final.append(x)



#part2 HGCD
def HGCD(a, b):
    if 2 * b.degree() <= a.degree() or a.degree() == 1:
        return 1, 0, 0, 1
    m = a.degree() // 2
    a_top, a_bot = a.quo_rem(x^m)
    b_top, b_bot = b.quo_rem(x^m)
    R00, R01, R10, R11 = HGCD(a_top, b_top)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    q, e = c.quo_rem(d)
    d_top, d_bot = d.quo_rem(x^(m // 2))
    e_top, e_bot = e.quo_rem(x^(m // 2))
    S00, S01, S10, S11 = HGCD(d_top, e_top)
    RET00 = S01 * R00 + (S00 - q * S01) * R10
    RET01 = S01 * R01 + (S00 - q * S01) * R11
    RET10 = S11 * R00 + (S10 - q * S11) * R10
    RET11 = S11 * R01 + (S10 - q * S11) * R11
    return RET00, RET01, RET10, RET11
    
def GCD(a, b):
    print(a.degree(), b.degree())
    q, r = a.quo_rem(b)
    if r == 0:
        return b
    R00, R01, R10, R11 = HGCD(a, b)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    if d == 0:
        return c.monic()
    q, r = c.quo_rem(d)
    if r == 0:
        return d
    return GCD(d, r)

key = 3168111950
PR.<x> = PolynomialRing(Zmod(n))
f1 = sum((k-key)*x**i for i, k in enumerate(final))^((1<<7)-1) - c1
f2 = x^((1<<16)+1) - c2
f2 = f2 % f1
res = GCD(f1,f2)

m = -res.monic().coefficients()[0]
flag = long_to_bytes(int(m))
print(flag)
# XYCTF{ba76e13f-269e-4481-baf0-4a50ad17f891}

Complex_RSA

task.py

from Crypto.Util.number import *
from secrets import flag


class Complex:
    def __init__(self, re, im):
        self.re = re
        self.im = im

    def __mul__(self, c):
        re_ = self.re * c.re - self.im * c.im
        im_ = self.re * c.im + self.im * c.re
        return Complex(re_, im_)

    def __str__(self):
        if self.im == 0:
            return str(self.re)
        elif self.re == 0:
            if abs(self.im) == 1:
                return f"{'-' if self.im < 0 else ''}i"
            else:
                return f"{self.im}i"
        else:
            return f"{self.re} {'+' if self.im > 0 else '-'} {abs(self.im)}i"


def complex_pow(c, exp, n):
    result = Complex(1, 0)
    while exp > 0:
        if exp & 1:
            result = result * c
            result.re = result.re % n
            result.im = result.im % n
        c = c * c
        c.re = c.re % n
        c.im = c.im % n
        exp >>= 1
    return result


m = bytes_to_long(flag)
key = getRandomNBitInteger(m.bit_length())
c = m ^ key
com = Complex(key, c)
p = getPrime(512)
q = getPrime(512)
e = 9
enc = complex_pow(com, e, p * q)
print(enc)
print(Complex(p, q) * Complex(p, q))
# 66350931528185981323649477263900844564494528747802437244889229343520648562164950914433406604580038018765783183569276743239888668912948977370163046257917321742455772852779551569446155827368453262479370103326286297164105599131090881306108546341785251895116423206455175290083968296281375908109039893280371271943 + 65266730684129269806656018828265187384002656633231286337130178390517924611751697965395744944541329793503617856896706439809241745206839328124348693486741656130890593895436661857688522977866438805549144904296596887218275440542852887148071837153436265722614658566275517205322945316112048487893204059562830581004i
# -28814875173103880290298835537218644402443395484370652510062722255203946330565951328874411874019897676900075613671629765922970689802650462822117767927082712245512492082864958877932682404829188622269636302484189627580600076246836248427780151681898051243380477561480415972565859837597822263289141887833338111120 + 235362412848885579543400940934854106052672292040465052424316433330114813432317923674803623227280862945857543620663672974955235166884830751834386990766053503640556408758413592161122945636548462064584183165189050320898315823173824074873376450569212651128285746330837777597290934043912373820690250920839961482862i

$$
C \equiv M^9 \mod n
$$

$\because gcd(e,phi) = e$，$gcd(e,p^2-1) = 3,gcd(e,q^2-1) = 3$

利用扩展欧几里得算法求出$e\times d_p \equiv 3 \mod p^2-1$以及$e\times d_q \equiv 3 \mod q^2-1$，这里算出来的结果一定要再模一下，血的教训

于是有$M^3p \equiv C^{d_p} \mod p$以及$M^3q \equiv C^{d_q} \mod q$

再把$M^3p$和$M^3q$展开，对于复数$z = a + bi$，展开得到$z^3 = (a^3 - 3ab^2) + (3a^2b-b^3)i$

分别解出$a_p \equiv a\mod p$，$a_q \equiv a \mod q$以及$b_p \equiv b \mod p$,$b_q \equiv b \mod q$

然后crt得到$a,b$，也就是$key$和$c$

exp

from Crypto.Util.number import *
import gmpy2

class Complex:
    def __init__(self, re, im):
        self.re = re
        self.im = im

    def __mul__(self, c):
        re_ = self.re * c.re - self.im * c.im
        im_ = self.re * c.im + self.im * c.re
        return Complex(re_, im_)

    def __str__(self):
        if self.im == 0:
            return str(self.re)
        elif self.re == 0:
            if abs(self.im) == 1:
                return f"{'-' if self.im < 0 else ''}i"
            else:
                return f"{self.im}i"
        else:
            return f"{self.re} {'+' if self.im > 0 else '-'} {abs(self.im)}i"


def complex_pow(c, exp, n):
    result = Complex(1, 0)
    while exp > 0:
        if exp & 1:
            result = result * c
            result.re = result.re % n
            result.im = result.im % n
        c = c * c
        c.re = c.re % n
        c.im = c.im % n
        exp >>= 1
    return result

# temp1 = -28814875173103880290298835537218644402443395484370652510062722255203946330565951328874411874019897676900075613671629765922970689802650462822117767927082712245512492082864958877932682404829188622269636302484189627580600076246836248427780151681898051243380477561480415972565859837597822263289141887833338111120 
# temp2 = 235362412848885579543400940934854106052672292040465052424316433330114813432317923674803623227280862945857543620663672974955235166884830751834386990766053503640556408758413592161122945636548462064584183165189050320898315823173824074873376450569212651128285746330837777597290934043912373820690250920839961482862

# var('p q')
# f1 = p^2 - q^2 == temp1
# f2 = 2*p*q == temp2
# res = solve([f1,f2],[p,q])
# print(res)
p = 10205509456040823453782883291824829705816298450992336115902525676510986341532486274067943978039013674207011185602314114359146043975207543018267242312660911
q = 11531144714660489617244423924607904114688972598683439999377362467380544567879231460623526800789918614728790840508257630983753525432337178000220918002499321
n = p * q
e = 9
phi = (p^2-1)*(q^2-1)

C = Complex(66350931528185981323649477263900844564494528747802437244889229343520648562164950914433406604580038018765783183569276743239888668912948977370163046257917321742455772852779551569446155827368453262479370103326286297164105599131090881306108546341785251895116423206455175290083968296281375908109039893280371271943,65266730684129269806656018828265187384002656633231286337130178390517924611751697965395744944541329793503617856896706439809241745206839328124348693486741656130890593895436661857688522977866438805549144904296596887218275440542852887148071837153436265722614658566275517205322945316112048487893204059562830581004)
_,dp,y1 = gmpy2.gcdext(e,p^2-1)
_,dq,y2 = gmpy2.gcdext(e,q^2-1)

dp = dp % (p^2 - 1)					
dq = dq % (q^2 - 1)

assert e * dp % (p^2-1) == 3
assert e * dq % (q^2-1) == 3
M3p = complex_pow(C,dp,p)
M3q = complex_pow(C,dq,q)

cxp = int(M3p.re)
cyp = int(M3p.im)
cxq = int(M3q.re)
cyq = int(M3q.im)

R.<a,b> = PolynomialRing(Zmod(p))

f1 = a^3 - 3*a*b^2 - cxp
f2 = 3*a^2*b - b^3 - cyp
g1 = f1.sylvester_matrix(f2,b).det().univariate_polynomial().monic()
h1 = f2.sylvester_matrix(f1,a).det().univariate_polynomial().monic()
res_ap = g1.roots()
res_bp = h1.roots()

R.<a,b> = PolynomialRing(Zmod(q))

f3 = a^3 - 3*a*b^2 - cxq
f4 = 3*a^2*b - b^3 - cyq
g2 = f3.sylvester_matrix(f4,b).det().univariate_polynomial().monic()
h2 = f4.sylvester_matrix(f3,a).det().univariate_polynomial().monic()
res_aq = g2.roots()
res_bq = h2.roots()

K = []
for i in res_ap:
    for j in res_aq:
        k = CRT_list([int(i[0]),int(j[0])],[p,q])
        if k not in K:
            K.append(k)

enc = []
for i in res_bp:
    for j in res_bq:
        c = CRT_list([int(i[0]),int(j[0])],[p,q])
        if c not in enc:
            enc.append(c)

for key in K:
    for c in enc:
        m = key ^^ c
        flag = long_to_bytes(int(m))
        if b"flag" in flag or b"XYCTF" in flag:
            print(flag)
            break
# flag{Complex_is_so_fun_and_I_think_you_know_Sylvester!}

easy_ecc

task.py

from Crypto.Util.number import *
from hashlib import sha256
from secret import flag, secret,SECRET

assert flag[6:-1] == sha256(long_to_bytes(secret)).hexdigest().encode()


class ECC_easy:
    def __init__(self):
        self.a = 1365855822212045061018261334821659180641576788523935479
        self.b = 17329427219955161804703200105884322768704934833367341
        self.p = 1365855822212045061018261334821659180641576788523935481

    def add(self, P, Q):
        mul_inv = lambda x: pow(x, -1, self.p)
        x1, y1 = P
        x2, y2 = Q
        if P!=Q:
            l=(y2-y1)*inverse(x2-x1,self.p)%self.p
        else:l=(3*x1**2+2*self.a*x1+1)*inverse(2*self.b*y1,self.p)%self.p
        temp1 = (self.b*l**2-self.a-x1-x2)%self.p
        temp2 = ((2*x1+x2+self.a)*l-self.b*l**3-y1)%self.p
        x3 = temp1
        y3 = temp2
        return x3, y3

    def mul(self, x, P):
        Q = SECRET
        x = x % self.p
        while x > 0:
            if x & 1:
                Q = self.add(Q, P)
            P = self.add(P, P)
            x >>= 1
        return Q

    def ispoint(self, x, y):
        return (self.a * x ** 2 + x ** 3+x) % self.p == (self.b * y ** 2) % self.p


ecc = ECC_easy()
LLLL = (1060114032187482137663886206406014543797784561116139791,752764811411303365258802649951280929945966659818544966)
assert ecc.ispoint(LLLL[0], LLLL[1])
END = ecc.mul(secret, LLLL)
print(END)

# (695174082657148306737473938393010922439779304870471540,414626357054958506867453055549756701310099524292082869)

题目给的是一个蒙哥马利曲线：$Kt^2 \equiv s^3 + Js^2 + s \mod p$

参考这篇文章Ed25519与Curve25519：概念与相互转换 - 知乎 (zhihu.com)，把蒙哥马利曲线映射到维尔斯特拉斯曲线，即$y^2 \equiv x^3 + 1098066776930223927329092382214459309226361965213x + 1263248714105743124314734095577181018742053879965591734 \mod p$

发现是个Singular Curve，参考Curve learning1 - hash_hash - 博客园 (cnblogs.com)

上述的曲线写为这样的形式$y^2 \equiv (x + r_1)^2(x+r_2)$

其中r1 = 544257272453066077953551360625531658485543339865638914

r2 = 277341277305912905111158613570595863670490108792657653，根据参考博客

做代换$t = x+r_1$，然后通过$y^2 \equiv t^3 + r\times t^2$，计算出$r = 1098939827064891888175868587766723385826523557450954220$

然后做代换$\phi = \frac{y+\alpha x}{y-\alpha x}$($\alpha^2 \equiv r \mod p$)，这里的$x$其实是代换后的$t$

exp

from Crypto.Util.number import *
from hashlib import sha256

K = 17329427219955161804703200105884322768704934833367341
J = 1365855822212045061018261334821659180641576788523935479
p = 1365855822212045061018261334821659180641576788523935481
G = (1060114032187482137663886206406014543797784561116139791,752764811411303365258802649951280929945966659818544966)
C = (695174082657148306737473938393010922439779304870471540,414626357054958506867453055549756701310099524292082869)

A = ((3 - J^2)*inverse(3*K^2,p)) % p
B = ((2*J^3 - 9*J)*inverse(27*K^3,p)) % p


def to_weier(x,y):
    xW = (3*x+J) * inverse_mod(3*K, p) % p
    yW = y * inverse_mod(K, p) % p
    assert yW^2 % p == (xW^3+A*xW+B) % p
    return (xW,yW)


GG = to_weier(G[0],G[1])
CC = to_weier(C[0],C[1])

r1 = 544257272453066077953551360625531658485543339865638914
r2 = 277341277305912905111158613570595863670490108792657653
tG = (GG[0] + r1) % p
tC = (CC[0] + r1) % p

r = 1098939827064891888175868587766723385826523557450954220
# R.<alpha> = PolynomialRing(Zmod(p))
# f = alpha^2 - r
# print(f.roots())
alpha = 1003930426227501665054311651540310392036896175643136673
# alpha = 361925395984543395963949683281348788604680612880798808

g = ((GG[1] + alpha*tG) * inverse((GG[1]-alpha*tG),p)) % p
y = ((CC[1] + alpha*tC) * inverse((CC[1]-alpha*tC),p)) % p

secret = discrete_log(mod(y,p),mod(g,p))
print(secret)
# 235532498456072807669363480669523682659923973393
flag = b"XYCTF{" + sha256(long_to_bytes(secret)).hexdigest().encode() + b"}"
print(flag)
# XYCTF{ec9a6e17537e81b7f593f65f7e2ca5d575e6b34c504c24e4afb40c1e9dc4be0d}

LCG_and_HNP

task.py

from Crypto.Util.number import *
import random
from secrets import flag


class LCG:
    def __init__(self, seed, a, b, p):
        self.seed = seed
        self.a = a
        self.b = b
        self.p = p

    def next(self):
        self.seed = (self.seed * self.a + self.b) % self.p
        return self.seed >> (self.p.bit_length() - 8)


m = bytes_to_long(flag)
p = getPrime(128)
a = random.randint(1, p)
b = random.randint(1, p)
seed = random.randint(1, p)
out = []
lcg = LCG(seed, a, b, p)
for i in range(30):
    out.append(lcg.next())
key = ""
while 1:
    key += str(lcg.next())
    if int(key) >= m:
        break

with open("out.txt", "w") as f:
    f.write(f"p={p}\n")
    f.write(f"a={a}\n")
    f.write(f"b={b}\n")
    f.write(f"out={out}\n")
    f.write(f"c={int(key)^m}")

已知$X_{n+1} \equiv aX_n + b \mod p$

把$X_n$拆为高位和低位之和，即$X_n = H_n+L_n$

于是有$H_{n+1}+L_{n+1} \equiv a(H_n+L_n) + b \mod p$

$\therefore L_{n+1} \equiv aL_n+(aH_n+b-H_{n+1})\mod p$

因为$L_2 \equiv aL_1 + (aH_1+b-H_2) \mod p$

$L_3 \equiv a(aL_1 + aH_1+b-H_2)+aH_2+b-H_3 \mod p$，即$L_3 \equiv a^2L_1+(aH_2+b-H_3+a^2H_1+b-H_2) \mod p$

于是能得到$L_i$与$L_1$的关系

则有$L_{i} \equiv A_iL_1 +B_i \mod p$，即$L_{i+1} = A_iL_1 + B_i + k_{i}p$

构造格

因为$L_i = 120bit$，所以最后调一个$2^{120}$

恢复出求出$L_1$之后得到$seed_1$，再恢复seed

恢复seed后，浅浅爆一下key，大概就是40次左右能出flag，运气挺好，刚好就是40

exp

#sage
import gmpy2
from Crypto.Util.number import *

m = 183640370379099520304414468793633666661
a = 36108041497607074474855679331694767924
b = 65925932211985158779695144876342622462
c = [0,34, 95, 100, 114, 16, 23, 17, 118, 115, 29, 73, 47, 12, 133, 78, 30, 30, 73, 87, 15, 85, 47, 20, 136, 6, 106, 74, 27, 116, 8]
cipher = 6003642257316152022364486167163125577018867662610595926973616937741281227891381713617380
#0是seed的高位

length = len(c)
for i in range(length):
    c[i] = c[i] << 120

A = [1]
B = [0]

for i in range(1,length-1):
    Ai = a*A[i-1] % m
    Bi = (a*B[i-1] + a*c[i]+b-c[i+1]) % m
    A.append(Ai)
    B.append(Bi)

A = A[1:]
B = B[1:]

M = Matrix(length,length)

for i in range(length-2):
    M[i,i] = m
    M[-1,i] = B[i]
    M[-2,i] = A[i]
M[-1,-1] = 2^120
M[-2,-2] = 1
inv = gmpy2.invert(a,m)
for i in M.LLL():
    if i[-1] == 2^120:
        L1 = i[-2]
        seed1 = c[1] + L1
        seed = inv * (seed1 - b) % m
        if ((a * seed + b) % m) >> 120 == c[1] >> 120:
            for _ in range(30):
                seed = (a * seed + b) % m
            key = ""
            for _ in range(40):
                seed = (a * seed % m + b) % m
                temp = seed >> 120
                key += str(temp)
                msg = cipher ^^ int(key)
                flag = long_to_bytes(int(msg))
                if b"flag" in flag or b"XYCTF" in flag:
                    print(flag)
                    break
# XYCTF{2h1_21_ZHi_5h0u_yU_zI_xI3_l@0}

new_LCG

task.py

from Crypto.Util.number import *
import random
from secrets import flag

p = getPrime(512)
q = getPrime(512)
r = getPrime(512)
n = p * q * r


class LCG1:
    def __init__(self, seed, a, b, m):
        self.seed = seed
        self.a = a
        self.b = b
        self.m = m
        self.sum = 0

    def next(self):
        old_seed = self.seed
        self.seed = (self.a * self.seed + self.b * self.sum) % self.m
        self.sum += old_seed
        return self.seed


class LCG2:
    def __init__(self, seed, q, A, B):
        self.E = EllipticCurve(GF(q), [A, B])
        self.P = self.E.lift_x(seed)
        self.b = self.E.random_point()

    def next(self):
        self.P = self.P + self.b
        return self.P[0]


a1 = random.randint(1, p)
b1 = random.randint(1, p)
seed1 = random.randint(1, p)
lcg1 = LCG1(seed1, a1, b1, p)
c1 = []
for _ in range(10):
    c1.append(lcg1.next())

a2 = random.randint(1, q)
b2 = random.randint(1, q)
seed2 = random.randint(1, q)
lcg2 = LCG2(seed2, q, a2, b2)
c2 = []
for _ in range(10):
    c2.append(lcg2.next())

c = bytes_to_long(flag)
e = 65537
print(n)
print(pow(c, e, n))
print(c1)
print(c2)
# 942554394956393500634473023924044851150783066435925660508624376974971108656861080872622432250172571195245180102507380675343264066303507696268870722959770362631674931170602993210221083436437860191861911457384526742569208842886612504579678703976889217504241741044075116270718940025586448491942058697669033418724145042156461740336592337509609124425828725269151627786668070531098444935129266626770404736852607352075247856808563388127774523912002202264558855255067503
# 91351185520045025851535940537599785616890151570421939971146348618267656786110090770321857244701820126026227283965934212135946431643320325513590505155214070540638751565105300361430272638957420276596026161454413739823593506516275224444666187442238624864548263927274591212614561916913851855552516864387460946267629794664216228596534684933791607740725160394841711539767932339281214673649553407414347293480522175832736301571839298158011533849603878482322619858083471
# [6924229081976334180193477951417117275396656434968000032228908231511246053064833236257422745299036986875244562025221130619850904830372215788197314906896784,707045810464337488125013716300756405499020414540801863434513087687914538170573314824134496890600422837133767094273649381435979038909605432188919586751472,561487665739111774897165274560908487232457333748910467998343202097778699925650682704996443560224288857862513676706660506594465853704042586896087391214886,6498834369085375452441121562339384727357898216850540864190840194924515286757125433756518026123451611578553656133012172518080309106483207567929943790044792,5508345401684913940610183958526398635406187349043368834080838153611810896629693027245511688366776749176652858929409374912959736262162942801190344337268446,7604410082265211154108357446507297790451766698177313130672954202813796888988719242951127448112228332967892794819415211618572734294964346056056171483002307,7699815879242527638422887386550759485127768822609011364311314299885418068889791030639324882736871756700299169635780542149704586720216395186814592666988591,829748131720382599696653359722612708514830904084605048590882951300049701148883021283243506081300427041733299385325284399270633917941134488957784480285437,7084115400374950827522650500486495223539292992998875483730758098005030106055310282589342193536381973309924074043955222228738842206417828828756951777504457,7482796067314266426215648326036921955183807741134787613584977300821023398375789725848056657250086288687570875979072368004217788222537115232191230702833854]
# [12573984103581521249597169818949825744876735847170990673204303602848066091917704946653820386665801380026230957120354174481948164514637637956459534723582285, 6441954407109995413858792101472089558106780628459991101662507565699664222341697230094798036088532393057448200220905589679548875702178737462785403325555226, 11684244745641367106386196774447204674089853123966422387024948921795099192025069760680924547214190425118261001002764397184950251157744938735586522727499550, 10396243416373326695473843427139385116708652845789644861965876346553795313454773668473030130335970707089781482749749170266279229263892370064669233541305377, 9090748241360606371310281608818966855338110969397659720953951845805983771894064629343960530245792700858927510839835850767728294266738917884471006979663157, 11489848045104749332790333272128633885019156159805805159750174723808043569789257625027794186359921080743368220606914862583644262009648261345452266067697628, 649349258009900424806913260265314442160901414078390702088746248078789581041616487825633046538335114117254875547413590064940767523651802950986197978665018, 6302136940345077947382276151657194124073457559487274425879887978386901058162385833414602346299055653879087077862824771863209271498552774720708307840705334, 5844526398244645236473089500608731415060125566027525405618000580381149761653744142808567706048834618328671311836990498943019718294135733114642775270792763, 4834548043993868659061606699822957422840040425976833628462093089330507589865407793951971491111695171201542345470702059513427268037868859282999222070054388]

思路比较明显，通过两个lcg求出$p,q$，再解最后的RSA

求p

self.seed = (self.a * self.seed + self.b * self.sum) % self.m根据这个式子，往下推导，再用gb基即可求出p

求q

根据题目有$P_{i+1} = P_i + B$，直接按照椭圆曲线加法展开的话，变量很多，不会处理。最后参考鸡块师傅的思路
$$
P_1 = P_2 - B
$$

$$
P_3 = P_2 + B
$$

记$B = (B_x,B_y)$，则$-B = (B_x,-B_y)$，则对于$P_1,P_3$有
$$
x_1 = (\frac{-B_y-y_2}{B_x-x_2})^2 - x_2 - B_x = (\frac{B_y+y_2}{B_x-x_2})^2 - x_2 - B_x
$$

$$
x_3 = (\frac{B_y - y_2}{B_x - x_2})^2 - x_2 - B_x
$$

相加得
$$
x_1 + x_3 = (\frac{B_y+y_2}{B_x-x_2})^2 + (\frac{B_y - y_2}{B_x - x_2})^2 - 2x_2 - 2B_x
$$
展开合并同类项得
$$
(x_1+x_3)(B_x-x_2)^2 = 2(B_y^2+y_2^2) - 2(x_2+B_x)(B_x-x_2)^2
$$
纵坐标可以用$y^2 \equiv x^3 + ax + b \mod q$来进行替换，即
$$
(x_1+x_3)(B_x-x_2)^2 = 2(B_x^3+aB_x + b+x_2^3 + ax_2 + b) - 2(x_2+B_x)(B_x-x_2)^2
$$
此时未知数只有$B_x,a,b,q$，通过gb基即可完成求解

exp

from Crypto.Util.number import *
import gmpy2

result = [6924229081976334180193477951417117275396656434968000032228908231511246053064833236257422745299036986875244562025221130619850904830372215788197314906896784,707045810464337488125013716300756405499020414540801863434513087687914538170573314824134496890600422837133767094273649381435979038909605432188919586751472,561487665739111774897165274560908487232457333748910467998343202097778699925650682704996443560224288857862513676706660506594465853704042586896087391214886,6498834369085375452441121562339384727357898216850540864190840194924515286757125433756518026123451611578553656133012172518080309106483207567929943790044792,5508345401684913940610183958526398635406187349043368834080838153611810896629693027245511688366776749176652858929409374912959736262162942801190344337268446,7604410082265211154108357446507297790451766698177313130672954202813796888988719242951127448112228332967892794819415211618572734294964346056056171483002307,7699815879242527638422887386550759485127768822609011364311314299885418068889791030639324882736871756700299169635780542149704586720216395186814592666988591,829748131720382599696653359722612708514830904084605048590882951300049701148883021283243506081300427041733299385325284399270633917941134488957784480285437,7084115400374950827522650500486495223539292992998875483730758098005030106055310282589342193536381973309924074043955222228738842206417828828756951777504457,7482796067314266426215648326036921955183807741134787613584977300821023398375789725848056657250086288687570875979072368004217788222537115232191230702833854]
n = 942554394956393500634473023924044851150783066435925660508624376974971108656861080872622432250172571195245180102507380675343264066303507696268870722959770362631674931170602993210221083436437860191861911457384526742569208842886612504579678703976889217504241741044075116270718940025586448491942058697669033418724145042156461740336592337509609124425828725269151627786668070531098444935129266626770404736852607352075247856808563388127774523912002202264558855255067503
c = 91351185520045025851535940537599785616890151570421939971146348618267656786110090770321857244701820126026227283965934212135946431643320325513590505155214070540638751565105300361430272638957420276596026161454413739823593506516275224444666187442238624864548263927274591212614561916913851855552516864387460946267629794664216228596534684933791607740725160394841711539767932339281214673649553407414347293480522175832736301571839298158011533849603878482322619858083471
c2 = [12573984103581521249597169818949825744876735847170990673204303602848066091917704946653820386665801380026230957120354174481948164514637637956459534723582285, 6441954407109995413858792101472089558106780628459991101662507565699664222341697230094798036088532393057448200220905589679548875702178737462785403325555226, 11684244745641367106386196774447204674089853123966422387024948921795099192025069760680924547214190425118261001002764397184950251157744938735586522727499550, 10396243416373326695473843427139385116708652845789644861965876346553795313454773668473030130335970707089781482749749170266279229263892370064669233541305377, 9090748241360606371310281608818966855338110969397659720953951845805983771894064629343960530245792700858927510839835850767728294266738917884471006979663157, 11489848045104749332790333272128633885019156159805805159750174723808043569789257625027794186359921080743368220606914862583644262009648261345452266067697628, 649349258009900424806913260265314442160901414078390702088746248078789581041616487825633046538335114117254875547413590064940767523651802950986197978665018, 6302136940345077947382276151657194124073457559487274425879887978386901058162385833414602346299055653879087077862824771863209271498552774720708307840705334, 5844526398244645236473089500608731415060125566027525405618000580381149761653744142808567706048834618328671311836990498943019718294135733114642775270792763, 4834548043993868659061606699822957422840040425976833628462093089330507589865407793951971491111695171201542345470702059513427268037868859282999222070054388]
e = 65537

R.<a,b,x> = PolynomialRing(ZZ)
f1 = a*x - result[0]
f2 = a^2*x + b*x - result[1]
f3 = a^3*x + 2*a*b*x + b*x - result[2]
f4 = a^4*x + 3*a^2*b*x + 2*a*b*x + b^2*x + b*x - result[3]
f5 = a^5*x + 4*a^3*b*x + 3*a^2*b*x + 3*a*b^2*x + 2*a*b*x + 2*b^2*x + b*x - result[4]
f6 = a^6*x + 5*a^4*b*x + 4*a^3*b*x + 6*a^2*b^2*x + 3*a^2*b*x + 6*a*b^2*x + b^3*x + 2*a*b*x + 3*b^2*x + b*x - result[5]

F = [f1,f2,f3,f4,f5,f6]
I = Ideal(F).groebner_basis()
p = ZZ(I[3])
print(f"p = {p}")

PR.<a,b,Bx> = PolynomialRing(ZZ)
F = []
for i in range(1,10-1):
    f = (Bx-c2[i])^2*(c2[i-1]+c2[i+1]) - 2*(Bx^3+a*Bx+b+c2[i]^3+a*c2[i]+b) + 2*(Bx+c2[i])*(Bx-c2[i])^2
    
    F.append(f)
res = Ideal(F).groebner_basis()
q = ZZ(res[3].univariate_polynomial()(0))
print(f"q = {q}")

r = n // p // q
phi = (p-1)*(q-1)*(r-1)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
print(long_to_bytes(int(m)))
# flag{71fc0bc1-167a-43f0-ab0f-e0df3bea8ed3}

铜匠

task.py

from Crypto.Util.number import *
from secrets import flag

m = bytes_to_long(flag)
m1 = getRandomRange(1, m)
m2 = getRandomRange(1, m)
m3 = m - m1 - m2


def task1():
    e = 149
    p = getPrime(512)
    q = getPrime(512)
    n = p * q
    d = inverse(e,(p-1)*(q-1))
    return (pow(m1, e, n), d >> 222 << 222, n)


def task2():
    e = 65537
    p = getPrime(1024)
    q = getPrime(1024)
    n = p * q
    return (pow(m2, e, n), (p + q) & ((1 << 624) - 1), n)


def task3():
    e = 65537
    p = getPrime(512)
    q = getPrime(512)
    n = p * q
    return (pow(m3, e, n), (p ^ q) >> 200, n)


c1, leak1, n1 = task1()
c2, leak2, n2 = task2()
c3, leak3, n3 = task3()
print(c1, leak1, n1)
print(c2, leak2, n2)
print(c3, leak3, n3)
# (89623543982221289730635223555830551523170205418976759060541832483843039074358160566735322009158596405712449020903311144480669706226166537602750967447480664875090686428406188847601970724994074417752345460791736191511081890913041143570455636020205647345764692062144226011846336769477026234106683791286490222089, 138474880017294332349992670187778287774153347391371789199005713563195654993662610111557185709277805165708109047494971468100563949333712521647405765501704478862377527360106399421209690341743821320754482338590671565510629203215009008479290995785318405211007685664887994061938667418220613430135743123498167435264, 146331610798417415036517077006943013321623040860385791423062775325646472298267580898028515394910588437521335092742913111680737790430660749825981979147191282007208147041227246620008377726207734522466015971515317594545750944838673018946440525615131606652748549901880641896940968837669894325535750125282351577689)
# (5473961166821344576614003060897848014482672788904094340704447882490091115468180944569409159343222459801235179587721232166576530621751748850763430788036935832653535110975154800191323351333883661451331971042214143454441651165718504131976920077768864850035471790911190772583977173388975105970866592974077361193822302653046511418190410043729876062517148438923211673300268277037622337403526399584759202097925983596261279676101079771530118525540842499517622478819211528345668513680064744443628779623340175578509413636950545134641050948185944279029949957748464529075830770617236599864271566534714755373562527112224962839980,62964793504732923650344975634773688108135580826064134090114181449607062497690184718845295432644650580930430061411603385577783897575232298084007041511817031640186953023971498914096209984730,20748652069632848434897928314437138341436264859802586939154590237186029244907936870477844563166827587536149170710720365760129683024401957095447466056746469055173897234659911291443605912459271248059341147358511860537769587963189092648473894868209838600346115919726589891777340166174017389513260737891557712152871714337946675533597049874155202056200170954033849176655928144354665553271709442011723088448485570394208728775665739819536229908847043007472178803394055783543378990699834066614262050119443421709878598533329555838915158259138297060574425019923291353077080236769586821808150397875920110335669136563171420068201)
# (34640310217688693418173336791306022698488916505988760907493665070072623574363578354500529023855888624978101429772253437880445815006839767802433777006836665709335479076676231470534690281412388704665083311568028710188940132495410474044569100181764053297307413009214044407982980600917158732129850605715306726034, 3763587651775261955566046684899146246387485307521708557610018711932791630073528010801142052497, 94848869174430082173244966077736519396702141299429965725051314270443078621842166791082354594193554380275167898342497998871366256044865879909218309960595691008663632410356093966762639308253848450178310347612630814852054763933063313537694449475061227647475480417779126252294793767003555255527593551612032661749)

part1

不会做

part2

由题意知$leak_2 \equiv p+q \mod 2^{624}$，除此之外还可以得到$n_{low} \equiv p\times q \mod 2^{624}$

于是有$n_{low} \equiv p(leak_2 - p) \mod 2^{624}$，解这个方程，然后得到p的低位，再用coppersmith

part3

题目给出p ^ q的高312位，参考鸡块师傅的博客：2023-鹏城杯-wp-crypto | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

剪枝的目的是为了求p的高位，再用coppersmith

exp（仅限后面两part）

import gmpy2

c1,leak1,n1 = (89623543982221289730635223555830551523170205418976759060541832483843039074358160566735322009158596405712449020903311144480669706226166537602750967447480664875090686428406188847601970724994074417752345460791736191511081890913041143570455636020205647345764692062144226011846336769477026234106683791286490222089, 138474880017294332349992670187778287774153347391371789199005713563195654993662610111557185709277805165708109047494971468100563949333712521647405765501704478862377527360106399421209690341743821320754482338590671565510629203215009008479290995785318405211007685664887994061938667418220613430135743123498167435264, 146331610798417415036517077006943013321623040860385791423062775325646472298267580898028515394910588437521335092742913111680737790430660749825981979147191282007208147041227246620008377726207734522466015971515317594545750944838673018946440525615131606652748549901880641896940968837669894325535750125282351577689)
c2,leak2,n2 = (5473961166821344576614003060897848014482672788904094340704447882490091115468180944569409159343222459801235179587721232166576530621751748850763430788036935832653535110975154800191323351333883661451331971042214143454441651165718504131976920077768864850035471790911190772583977173388975105970866592974077361193822302653046511418190410043729876062517148438923211673300268277037622337403526399584759202097925983596261279676101079771530118525540842499517622478819211528345668513680064744443628779623340175578509413636950545134641050948185944279029949957748464529075830770617236599864271566534714755373562527112224962839980,62964793504732923650344975634773688108135580826064134090114181449607062497690184718845295432644650580930430061411603385577783897575232298084007041511817031640186953023971498914096209984730,20748652069632848434897928314437138341436264859802586939154590237186029244907936870477844563166827587536149170710720365760129683024401957095447466056746469055173897234659911291443605912459271248059341147358511860537769587963189092648473894868209838600346115919726589891777340166174017389513260737891557712152871714337946675533597049874155202056200170954033849176655928144354665553271709442011723088448485570394208728775665739819536229908847043007472178803394055783543378990699834066614262050119443421709878598533329555838915158259138297060574425019923291353077080236769586821808150397875920110335669136563171420068201)
c3,leak3,n3 = (34640310217688693418173336791306022698488916505988760907493665070072623574363578354500529023855888624978101429772253437880445815006839767802433777006836665709335479076676231470534690281412388704665083311568028710188940132495410474044569100181764053297307413009214044407982980600917158732129850605715306726034, 3763587651775261955566046684899146246387485307521708557610018711932791630073528010801142052497, 94848869174430082173244966077736519396702141299429965725051314270443078621842166791082354594193554380275167898342497998871366256044865879909218309960595691008663632410356093966762639308253848450178310347612630814852054763933063313537694449475061227647475480417779126252294793767003555255527593551612032661749)
e1 = 149
e = 65537


# part2

def decrypt2(n2,c2,leak2):
    n2_low = n2 % 2^624
    var('p')
    f = p * (leak2 - p) - n2_low
    res = solve_mod(f,2^624)

    for i in res:
        plow = int(i[0])
        R.<x> = PolynomialRing(Zmod(n2))
        f2 = x * 2^624 + plow
        f2 = f2.monic()
        root = f2.small_roots(X = 2^400,beta=0.4)
        if root != []:
            p2 = int(root[0])*2^624 + plow
            q2 = n2 // p2
            d = gmpy2.invert(e,(p2-1)*(q2-1))
            m2 = pow(c2,d,n2)

            return m2
        
# m2 = decrypt2(n2,c2,leak2)
m2 = 637474741382124491125351127892971159828342019036405954553729272346832023284163998914076056292480317209934960796148267118196288511438260371617371342378683017480560448795

# part3

leak3 = leak3 << 200
leak3 = bin(leak3)[2:].zfill(512)
leakbits = 200                          # 缺失的位数

def findp(pp,qq,l):
    p_Min = int(pp + (512-l)*"0",2)
    p_Max = int(pp + (512-l)*"1",2)
    q_Min = int(qq + (512-l)*"0",2)
    q_Max = int(qq + (512-l)*"1",2)

    if(l == 512 - leakbits):
        R.<x> = PolynomialRing(Zmod(n3))
        phigh = p_Min
        f3 = phigh + x
        root = f3.small_roots(X=2^leakbits, beta=0.499)
        if root != []:
            p3 = phigh + int(root[0])
            q3 = n3 // p3
            d = gmpy2.invert(e,(p3-1)*(q3-1))
            m3 = pow(c3,d,n3)
            print(f"m3 = {m3}")
    
    if (p_Max * q_Max < n3) or (p_Min * q_Min > n3):
        return
    
    # 以下是根据异或来操作的
    if leak3[l] == '0':
        findp(pp + '1',qq + '1',l+1)
        findp(pp + '0',qq + '0',l+1)
    if leak3[l] == '1':
        findp(pp + '1',qq + '0',l+1)
        findp(pp + '0',qq + '1',l+1)

findp('1','1',1)

m3 = 334132319136130454419386550847309794306389604470819859736266178647538718607667083644497296078054806893307642673035506225568447967643224450929477875810797878149197295514

Misc

熊博士

CBXGU{ORF_BV_NVR_BLF_CRZL_QQ}

埃特巴什码 - Atbash Cipher - 在线工具网 (wtool.com.cn)

xyctf{liu_ye_mei_you_xiao_jj}

game

谷歌识图秒出

游戏名叫Papers, Please

flag:XYCTF{Papers Please}

Re

喵喵喵的flag碎了一地

Shift+F12得到第一段flag{My_fl@g_h4s_

IDA左边函数列表找到第二段br0ken_4parT_

在第二段函数处Ctrl+x即可找到什么位置指向了该函数，找到第三段Bu7_Y0u_c@n_f1x_1t!}

flag{My_fl@g_h4s_br0ken_4parT_Bu7_Y0u_c@n_f1x_1t!}

聪明的信使

Shift+F12得到密文oujp{H0d_TwXf_Lahyc0_14_e3ah_Rvy0ac@wc!}

凯撒解密，移位9解密得到明文flag{Y0u_KnOw_Crypt0_14_v3ry_Imp0rt@nt!}

-------------已经到底啦！-------------

Crypto

Sign1n[签到]

happy_to_solve1

happy_to_solve2

happy_to_solve3

factor1

factor3

babyRSAMAX

x0y

Complex_dlp

反方向的密码 相思

反方向的密码 情难

重生之我要当oi爷 pro

fakeRSA

random_rr

Complex_RSA

easy_ecc

LCG_and_HNP

new_LCG

求p

求q

铜匠

part1

part2

part3

Misc

熊博士

game

Re

喵喵喵的flag碎了一地

聪明的信使

反方向的密码相思

反方向的密码情难