L3Hctf2025crypto方向个人wp

ECDSA

import hashlib
import random
from ecdsa import NIST256p, SigningKey

class FlawedNonceGenerator:
    def __init__(self, n):
        self.n = n
        self.a = random.randrange(1, n)
        self.b = random.randrange(1, n)
        self.c = random.randrange(1, n)
        self.last_k = random.randrange(1, n)

    def generate_nonce(self):
        current_k = self.last_k
        next_k = (self.a * current_k**2 + self.b * current_k + self.c) % self.n
        self.last_k = next_k
        
        return current_k


curve = NIST256p
n = curve.order
private_key = SigningKey.from_secret_exponent(random.randrange(1, n), curve=curve)
d = private_key.privkey.secret_multiplier
public_key = private_key.get_verifying_key()

messages = [
    b"Hello player, welcome to L3HCTF 2025!",
    b"This is a crypto challenge, as you can probably tell.",
    b"It's about ECDSA, a very... robust algorithm.",
    b"I'm sure there are no implementation flaws whatsoever.",
    b"Anyway, here are your signatures. Good luck!",
    f"Oh, and the flag is L3HCTF{{{d}}}. Don't tell anyone!".encode(),
]
nonce_generator = FlawedNonceGenerator(n)
f = open('signatures.txt', 'w')

for i in range(6):
    k = nonce_generator.generate_nonce()
    message = messages[i]
    h = int.from_bytes(hashlib.sha256(message).digest(), 'big')
    R = k * curve.generator
    r = R.x() % n
    s_inv = pow(k, -1, n)
    s = (s_inv * (h + d * r)) % n
    f.write(f"h: {h}, r: {r}, s: {s}\n")

基础的ECDSA加密签名，并且输出了6个k和s

关键攻击在于

def generate_nonce(self):
        current_k = self.last_k
        next_k = (self.a * current_k**2 + self.b * current_k + self.c) % self.n
        self.last_k = next_k
        return current_k

这里的是一个可预测的递推公式 k_i + 1 = a ⋅ k_i² + b ⋅ k_i + c (mod  n) 这里我用的是Groebner 基进行解决的这个问题

from sage.all import *

# NIST256p curve order
n = 0xFFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551

# 6组签名数据： (h, r, s)
signatures = [
    (5832921593739954772384341732387581797486339670895875430934592373351528180781, 
     78576287416983546819312440403592484606132915965726128924031253623117138586396, 
     108582979377193966287732302562639670357586761346333866965382465209612237330851),
    
    (85517239535736342992982496475440962888226294744294285419613128065975843025446, 
     60425040031360920373082268221766168683222476464343035165195057634060216692194, 
     27924509924269609509672965613674355269361001011362007412205784446375567959036),
    
    (90905761421138489726836357279787648991884324454425734512085180879013704399530, 
     75779605492148881737630918749717271960050893072832415117470852442721700807111, 
     72740499400319841565890543635298470075267336863033867770902108413176557795256),
    
    (103266614372002123398101167242562044737358751274736728792365384600377408313142, 
     89519601474973769723244654516140957004170211982048028366151899055366457476708, 
     23639647021855356876198750083669161995553646511611903128486429649329358343588),
    
    (9903460667647154866199928325987868915846235162578615698288214703794150057571, 
     17829304522948160053211214227664982869100868125268116260967204562276608388692, 
     74400189461172040580877095515356365992183768921088660926738652857846750009205),
    
    (54539896686295066164943194401294833445622227965487949234393615233511802974126, 
     66428683990399093855578572760918582937085121375887639383221629490465838706027, 
     25418035697368269779911580792368595733749376383350120613502399678197333473802),
]

# 构造变量环
R = PolynomialRing(Zmod(n), names=('a', 'b', 'c', 'd'))
a, b, c, d = R.gens()

# 构造每个 k_i 表达式：k_i = (h_i + r_i*d) * s_i^{-1}
k_list = []
for h, r, s in signatures:
    s_inv = inverse_mod(s, n)
    k_expr = (h + r * d) * s_inv
    k_list.append(k_expr)

# 构造递推等式: k_{i+1} = a * k_i^2 + b * k_i + c
eqs = []
for i in range(5):  # 共5个等式
    f = a * k_list[i]**2 + b * k_list[i] + c - k_list[i+1]
    eqs.append(f)

# 构造理想并求 Groebner 基
I = R.ideal(eqs)
G = I.groebner_basis()

# 从 Groebner 基中提取含 d 的多项式并求根
found = False
for g in G:
    if g.degree(d) > 0:
        poly = g.univariate_polynomial()
        roots = poly.roots()
        for root, _ in roots:
            d_val = int(root)
            print(f"[+] Found private key d = {d_val}")
            print(f"L3HCTF{{{d_val}}}")
            found = True
if not found:
    print("[-] Failed to recover private key. Try different subsets or check equations.")
#[+] Found private key d = 46003571009791459373376302598944888076887350506059398976372956237301255231719
#L3HCTF{46003571009791459373376302598944888076887350506059398976372956237301255231719}

math_problem

import gmpy2
from gmpy2 import *
from Crypto.Util.number import *
from random import randint
from gmpy2 import invert
from scret import flag

def myfunction(num):
    output = 0
    output=num**3
    return output

if __name__ == '__main__':
    flag_len = len(flag)
    p, q = getPrime(512), getPrime(512)

    while True:
        r = getPrime(512)
        R = bytes_to_long(str(r).encode())
        if isPrime(R):
            break

    n = p * q * r
    hint1 = R * r
    mod = myfunction(n)
    hint2 = pow(3*n+1, p % (2 ** 400), mod)
    m = bytes_to_long(flag)
    c = pow(m, 65537, n)

    print('All data:')
    print(f'n = {n}')
    print(f'c = {c}')
    print(f'hint1 = {hint1}')
    print(f'hint2 = {hint2}')


'''
All data:
n = 1031361339208727791691298627543660626410606240120564103678654539403400080866317968868129842196968695881908504164493307869679126969820723174066217814377008485456923379924853652121682069359767219423414060835725846413022799109637665041081215491777412523849107017649039242068964400703052356256244423474207673552341406331476528847104738461329766566162770505123490007005634713729116037657261941371410447717090137275138353217951485412890440960756321099770208574858093921
c = 102236458296005878146044806702966879940747405722298512433320216536239393890381990624291341014929382445849345903174490221598574856359809965659167404530660264493014761156245994411400111564065685663103513911577275735398329066710295262831185375333970116921093419001584290401132157702732101670324984662104398372071827999099732380917953008348751083912048254277463410132465011554297806390512318512896160903564287060978724650580695287391837481366347198300815022619675984
hint1 = 41699797470148528118065605288197366862071963783170462567646805693192170424753713903885385414542846725515351517470807154959539734665451498128021839987009088359453952505767502787767811244460427708303466073939179073677508236152266192609771866449943129677399293427414429298810647511172104050713783858789512441818844085646242722591714271359623474775510189704720357600842458800685062043578453094042903696357669390327924676743287819794284636630926065882392099206000580093201362555407712118431477329843371699667742798025599077898845333
hint2 = 10565371682545827068628214330168936678432017129758459192768614958768416450293677581352009816968059122180962364167183380897064080110800683719854438826424680653506645748730410281261164772551926020079613841220031841169753076600288062149920421974462095373140575810644453412962829711044354434460214948130078789634468559296648856777594230611436313326135647906667484971720387096683685835063221395189609633921668472719627163647225857737284122295085955645299384331967103814148801560724293703790396208078532008033853743619829338796313296528242521122038216263850878753284443416054923259279068894310509509537975210875344702115518307484576582043341455081343814378133782821979252975223992920160189207341869819491668768770230707076868854748648405256689895041414944466320313193195829115278252603228975429163616907186455903997049788262936239949070310119041141829846270634673190618136793047062531806082102640644325030011059428082270352824026797462398349982925951981419189268790800571889709446027925165953065407940787203142846496246938799390975110032101769845148364390897424165932568423505644878118670783346937251004620653142783361686327652304482423795489977844150385264586056799848907
'''

直接找到关键的加密位置

n = p * q * r
hint1 = R * r
mod = myfunction(n)
hint2 = pow(3*n+1, p % (2 ** 400), mod)
m = bytes_to_long(flag)
c = pow(m, 65537, n)

这里n和hint用了一个gcd就得到了r的值，进而得到了p*q的取值

hint1=41699797470148528118065605288197366862071963783170462567646805693192170424753713903885385414542846725515351517470807154959539734665451498128021839987009088359453952505767502787767811244460427708303466073939179073677508236152266192609771866449943129677399293427414429298810647511172104050713783858789512441818844085646242722591714271359623474775510189704720357600842458800685062043578453094042903696357669390327924676743287819794284636630926065882392099206000580093201362555407712118431477329843371699667742798025599077898845333
n=1031361339208727791691298627543660626410606240120564103678654539403400080866317968868129842196968695881908504164493307869679126969820723174066217814377008485456923379924853652121682069359767219423414060835725846413022799109637665041081215491777412523849107017649039242068964400703052356256244423474207673552341406331476528847104738461329766566162770505123490007005634713729116037657261941371410447717090137275138353217951485412890440960756321099770208574858093921
hint2 = 10565371682545827068628214330168936678432017129758459192768614958768416450293677581352009816968059122180962364167183380897064080110800683719854438826424680653506645748730410281261164772551926020079613841220031841169753076600288062149920421974462095373140575810644453412962829711044354434460214948130078789634468559296648856777594230611436313326135647906667484971720387096683685835063221395189609633921668472719627163647225857737284122295085955645299384331967103814148801560724293703790396208078532008033853743619829338796313296528242521122038216263850878753284443416054923259279068894310509509537975210875344702115518307484576582043341455081343814378133782821979252975223992920160189207341869819491668768770230707076868854748648405256689895041414944466320313193195829115278252603228975429163616907186455903997049788262936239949070310119041141829846270634673190618136793047062531806082102640644325030011059428082270352824026797462398349982925951981419189268790800571889709446027925165953065407940787203142846496246938799390975110032101769845148364390897424165932568423505644878118670783346937251004620653142783361686327652304482423795489977844150385264586056799848907
from Crypto.Util.number import *
x=GCD(n, hint1)
print(f'GCD(n, hint1) = {x}')  
pq=n//x
print(f'pq = {pq}')
#pq=89976238182539956361646502174582239233867602786630733592087980565136028257351416845669763032829951111889837196225697003100579641554184101899334531827940735063578835944600821891388396352487725296846958330005131539072371256697512444779913966988812704198431594797297087795356209894849648037186106182879820249927

hint2用了一个推导

k = (hint2 - 1) // n
inv = invert(3, n)
p_low = (k * inv) % n
print(f'p_low = {p_low}')

然后我们就得到了p的低400位

最后就是一个p的已知低位攻击打一元copper

#sage
plow = 1485680028344144006765555653772516703832059493333760848397113959350969611961772611966978839643079277183666542572626814999
pq = 89976238182539956361646502174582239233867602786630733592087980565136028257351416845669763032829951111889837196225697003100579641554184101899334531827940735063578835944600821891388396352487725296846958330005131539072371256697512444779913966988812704198431594797297087795356209894849648037186106182879820249927
plow_bits=400
pbits = 512
kbits = pbits - plow_bits  
R = 2^plow_bits
P.<x> = PolynomialRing(Zmod(pq))
f = x * R + plow
f_monic = f.monic()  
roots = f_monic.small_roots(X=2^kbits, beta=0.4)

if roots:
    x0 = int(roots[0])
    p = x0 * R + plow
    q = pq // p
    print(f'[+] 找到 p = {p}')
    print(f'[+] 找到 q = {q}')

p = 10131840248837038199009829519775750424799329778826965567641085303764923942459699675684256950985404319256009819736357506324552460305994284453952660375382039
q = 8880542524628503503088519580251341265303330988486163026964989899094554424819704451400137548766462436771110504734327527344318689549280294343934878659187793
r = 11462596792681484119885867626229848343628572981903327079472959385609791492187597506621130701780561699379556165436984737148828369344212127061312661920652823
n = p * q * r
e = 65537  
c = 102236458296005878146044806702966879940747405722298512433320216536239393890381990624291341014929382445849345903174490221598574856359809965659167404530660264493014761156245994411400111564065685663103513911577275735398329066710295262831185375333970116921093419001584290401132157702732101670324984662104398372071827999099732380917953008348751083912048254277463410132465011554297806390512318512896160903564287060978724650580695287391837481366347198300815022619675984
phi = (p - 1) * (q - 1) * (r - 1)
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))
#b'L3HCTF{1s_4h1s_r3a11y_m4th?}'

RSSSSSSA

from sage.all import *

from secret import flag

def generate_vulnerable_key(bits=1024):
    p_bits = bits // 2
    q_bits = bits - p_bits

    while True:
        p = random_prime(2**(p_bits), lbound=2**(p_bits-1))
        q = random_prime(2**(q_bits), lbound=2**(q_bits-1))
        if p != q and p > q and p < 2*q:
            break
            
    N = p * q
    phi = (p**4 - 1) * (q**4 - 1)

    d_bits = 1024
    d_bound = 2**d_bits

    while True:
        d_small = randint(2, d_bound)
        d = phi - d_small
        if gcd(d, phi) == 1:
            if d_small.bit_length() == 1021:
                break

    e = inverse_mod(d, phi)
    
    return N, e

def encrypt(m, N, e):
    n = 4
    r = 2
    R = Integers(N)
    P = PolynomialRing(R, 't')
    t = P.gen()
    Q = P.quotient(t**n - r)

    m_poly = Q([m, 0, 0, 0])

    c_poly = m_poly ** e

    return c_poly.lift()

if __name__ == "__main__":
    N, e = generate_vulnerable_key()
    m = int.from_bytes(flag, 'big')
    c = encrypt(m, N, e)

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

# N = 99697845285265879829811232968100099666254250525000506525475952592468738395250956460890611762459685140661035795964867321445992110528627232335703962897072608767840783176553829502743629914407970206513639916759403399986924602596286330464348286080258986075962271511105387188070309852907253486162504945490429185609
# e = 74900336437853271512557457581304251523854378376434438153117909482138661618901386551154807447783262736408028580620771857416463085746907317126876189023636958838207330193074215769008709076254356539808209005917645822989554532710565445155350102802675594603406077862472881027575871589046600011223990947361848608637247276816477996863812313225929441545045479384803449990623969591150979899801722841101938868710054151839628803383603849632857020369527380816687165487370957857737696187061619496102857237814447790678611448197153594917852504509869007597997670022501500067854210261136878917620198551551460145853528269270832725348151160651020188255399136483482428499340574623409209151124687319668989144444549871527949104436734300277004316939985015286758651969045396343970037328043635061226100170529991733947365830164811844853806681198818875837903563263114249814483901121700854712406832325690101810786429930813776784979083590353027191492894890551838308899148551566437532914838098811643805243593419063566975400775134981190248113477610235165151367913498299241375039256652674679958159505112725441797566678743542054295794919839551675786573113798857814005058856054462008797386322048089657472710775620574463924678367455233801970310210504653908307254926827
# c = 98460941530646528059934657633016619266170844887697553075379408285596784682803952762901219607460711533547279478564732097775812539176991062440097573591978613933775149262760936643842229597070673855940231912579258721734434631479496590694499265794576610924303262676255858387586947276246725949970866534023718638879

关键在于

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

d_bits = 1024
d_bound = 2**d_bits

while True:
    d_small = randint(2, d_bound)
    d = phi - d_small
    if gcd(d, phi) == 1:
        if d_small.bit_length() == 1021:
            break

这里生成的d位数很小，并且φ = (p⁴ - 1)(q⁴ - 1) ≈ N⁴，猜测是运用连分数的思想去规约

在这里我们有φ = (p⁴ - 1)(q⁴ - 1) ≈ N⁴；

所以：

换句话说：

然后就是用连分数的方法去解决这个问题了

from sage.all import *

N = 99697845285265879829811232968100099666254250525000506525475952592468738395250956460890611762459685140661035795964867321445992110528627232335703962897072608767840783176553829502743629914407970206513639916759403399986924602596286330464348286080258986075962271511105387188070309852907253486162504945490429185609
e = 74900336437853271512557457581304251523854378376434438153117909482138661618901386551154807447783262736408028580620771857416463085746907317126876189023636958838207330193074215769008709076254356539808209005917645822989554532710565445155350102802675594603406077862472881027575871589046600011223990947361848608637247276816477996863812313225929441545045479384803449990623969591150979899801722841101938868710054151839628803383603849632857020369527380816687165487370957857737696187061619496102857237814447790678611448197153594917852504509869007597997670022501500067854210261136878917620198551551460145853528269270832725348151160651020188255399136483482428499340574623409209151124687319668989144444549871527949104436734300277004316939985015286758651969045396343970037328043635061226100170529991733947365830164811844853806681198818875837903563263114249814483901121700854712406832325690101810786429930813776784979083590353027191492894890551838308899148551566437532914838098811643805243593419063566975400775134981190248113477610235165151367913498299241375039256652674679958159505112725441797566678743542054295794919839551675786573113798857814005058856054462008797386322048089657472710775620574463924678367455233801970310210504653908307254926827
c = 98460941530646528059934657633016619266170844887697553075379408285596784682803952762901219607460711533547279478564732097775812539176991062440097573591978613933775149262760936643842229597070673855940231912579258721734434631479496590694499265794576610924303262676255858387586947276246725949970866534023718638879

alpha = QQ(e) / (N ^ 4)
for conv in continued_fraction(alpha).convergents():
    k, d_small = conv.numerator(), conv.denominator()
    
    if not (2**1020 <= d_small < 2**1021):
        continue

    try:
        
        m = pow(inverse_mod(c, N), d_small, N)
        m_bytes = m.to_bytes((m.bit_length() + 7) // 8, 'big')

        if b"L3H" in m_bytes:
            print("Flag found:", m_bytes.decode(errors='ignore'))
            break
    except:
        continue
#Flag found: L3HCTF{d2f790fb12af914d7a34055d73f3c1bdc484cfcd75c4d4a493e31af5791ff309}