L3HCTF-2025

EzECDSA

题面：

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)
        print(f'a,b,c = {self.a,self.b,self.c}')

    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
print(f'd = {d}')
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")

分析：

用NIST256p这个曲线进行的ECDSA签名，其中由于这个曲线是已知的，所以n = curve.order，n是已知的，也就是我们有6组签名，而且每个k之间都有联系：

$s_1=k_1^{-1}(h_1+xr_1)\\s_2=k_2^{-1}(h_2+xr_2)\\\vdots\\s_6=k_6^{-1}(h_6+xr_6)$

$都做一下转换即可得到6个多项式：$

$h_1+xr_1-s_1k_1=0\\h_2+xr_2-s_2k_2=0\\\vdots\\ h_6+xr_6-s_6k_6=0$

由于$k_i$之间存在线性关系，所以最终都可以表示为$k_1$的多项式，这里直接求这些多项式理想的grobner基即可得到多项式方程的解

[x + 69788518200564789389321144350462685453109604718076361366049302823767256812650, k + 20259192668456929166524619606713276345602588639715480059091270804733464402770, a + 5429358627696695589699281230327408089193738662340759874540258774415727222303, b + 44568864543157323131751489652584342118296318663514348237122188472367311256223, c + 43731216038486108514267049101526725549282472663927075875243047123834915417678]

题解：

from ecdsa import NIST256p, SigningKey
from Crypto.Util.number import *

sig = [(5832921593739954772384341732387581797486339670895875430934592373351528180781, 78576287416983546819312440403592484606132915965726128924031253623117138586396, 108582979377193966287732302562639670357586761346333866965382465209612237330851),
(85517239535736342992982496475440962888226294744294285419613128065975843025446, 60425040031360920373082268221766168683222476464343035165195057634060216692194, 27924509924269609509672965613674355269361001011362007412205784446375567959036),
(90905761421138489726836357279787648991884324454425734512085180879013704399530, 75779605492148881737630918749717271960050893072832415117470852442721700807111, 72740499400319841565890543635298470075267336863033867770902108413176557795256),
(103266614372002123398101167242562044737358751274736728792365384600377408313142, 89519601474973769723244654516140957004170211982048028366151899055366457476708, 23639647021855356876198750083669161995553646511611903128486429649329358343588),
(9903460667647154866199928325987868915846235162578615698288214703794150057571, 17829304522948160053211214227664982869100868125268116260967204562276608388692, 74400189461172040580877095515356365992183768921088660926738652857846750009205),
(54539896686295066164943194401294833445622227965487949234393615233511802974126, 66428683990399093855578572760918582937085121375887639383221629490465838706027, 25418035697368269779911580792368595733749376383350120613502399678197333473802)
]

h = [sig[i][0] for i in range(len(sig))]
r = [sig[i][1] for i in range(len(sig))]
s = [sig[i][2] for i in range(len(sig))]

curve = NIST256p
print(curve)
n = curve.order
g = curve.generator
print(f'n = {n}')

PR.<x,k,a,b,c> = PolynomialRing(Zmod(n))

eqs = []
for i in range(6):
    eq = ((h[i] + x * r[i])) - s[i]*k
    k = (a * k**2 + b * k + c)
    eqs.append(eq)
    
I = PR.ideal(eqs)
G = I.groebner_basis()
print(G)

x = -int(G[0].coefficients()[1])%n
print(f"L3HCTF{{{x}}}")

math_problem

题面：

import gmpy2
from gmpy2 import *
from Crypto.Util.number import *
from random import randint
from gmpy2 import invert
from scret import flag
0
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
'''

分析：

题目里给定了

$hint_1=R*r\\$

$hint_2=(3n+1)^{p_l}\ \ mod\ \ n^3\\$

$n=p*q*r$

所以可以通过求最大公因数的方式得到r

$r=GCD(hint_1,n)$

然后对于hint2，进一步二项展开：

$hint_2=(3n+1)^{p_l}\ \ mod\ \ n^3=C_{p_l}^2(3n)^2+C_{p_l}^1(3n)+1\\$

$p_l=(hint_2-1)//(3n)\%n$

然后coppersmith得到p

题解：

from Crypto.Util.number import *

n = 1031361339208727791691298627543660626410606240120564103678654539403400080866317968868129842196968695881908504164493307869679126969820723174066217814377008485456923379924853652121682069359767219423414060835725846413022799109637665041081215491777412523849107017649039242068964400703052356256244423474207673552341406331476528847104738461329766566162770505123490007005634713729116037657261941371410447717090137275138353217951485412890440960756321099770208574858093921
c = 102236458296005878146044806702966879940747405722298512433320216536239393890381990624291341014929382445849345903174490221598574856359809965659167404530660264493014761156245994411400111564065685663103513911577275735398329066710295262831185375333970116921093419001584290401132157702732101670324984662104398372071827999099732380917953008348751083912048254277463410132465011554297806390512318512896160903564287060978724650580695287391837481366347198300815022619675984
hint1 = 41699797470148528118065605288197366862071963783170462567646805693192170424753713903885385414542846725515351517470807154959539734665451498128021839987009088359453952505767502787767811244460427708303466073939179073677508236152266192609771866449943129677399293427414429298810647511172104050713783858789512441818844085646242722591714271359623474775510189704720357600842458800685062043578453094042903696357669390327924676743287819794284636630926065882392099206000580093201362555407712118431477329843371699667742798025599077898845333
hint2 = 10565371682545827068628214330168936678432017129758459192768614958768416450293677581352009816968059122180962364167183380897064080110800683719854438826424680653506645748730410281261164772551926020079613841220031841169753076600288062149920421974462095373140575810644453412962829711044354434460214948130078789634468559296648856777594230611436313326135647906667484971720387096683685835063221395189609633921668472719627163647225857737284122295085955645299384331967103814148801560724293703790396208078532008033853743619829338796313296528242521122038216263850878753284443416054923259279068894310509509537975210875344702115518307484576582043341455081343814378133782821979252975223992920160189207341869819491668768770230707076868854748648405256689895041414944466320313193195829115278252603228975429163616907186455903997049788262936239949070310119041141829846270634673190618136793047062531806082102640644325030011059428082270352824026797462398349982925951981419189268790800571889709446027925165953065407940787203142846496246938799390975110032101769845148364390897424165932568423505644878118670783346937251004620653142783361686327652304482423795489977844150385264586056799848907

e = 65537
'''
p = getPrime(5)
print(p)
PR.<n> = PolynomialRing(ZZ)
f = (3*n+1)**p % n**3
print(f)
# 4185*n^2 + 93*n + 1
'''

r = GCD(n,hint1)
pl = (hint2-1)//(3*n)%n
print(pl.bit_length())
# 400

n = n//r
PR.<x> = PolynomialRing(Zmod(n))
f = x*2**400 + pl
ph = f.monic().small_roots(X=2^114,beta=0.49)

p = int(ph[0])*2**400 + pl
print(isPrime(p))
# True

q = n//p
phi = (p-1)*(q-1)*(r-1)
d = inverse(e,phi)
m = pow(c,d,p*q*r)
print(long_to_bytes(m))

# b'L3HCTF{1s_4h1s_r3a11y_m4th?}'

RRRSSSAAA

题面：

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

分析：

对于给定的

$phi=(p^4-1)(q^4-1)\approx N^4$

则

$ed=e(\phi-d_{small})=1\ \ mod\ \ \phi\\ ed_{small}=-1\ \ mod\ \ \phi\\ ed_{small}+1=k\phi$

然后检查一下是否满足Legendre's theorem

$|\frac{e}{N^4}-\frac{k}{d_{small}}|=|\frac{k\phi-ed_{small}-kN^4+kN^4}{N^4d_{small}}|\approx|\frac{k(\phi-N^4)}{N^4d_{small}}|$

其中

$|\phi-N^4|=|(p^4-1)(q^4-1)-p^4q^4|\leq p^4+q^4\approx 2*(2^{512})^4=2^{2049}\\ k\approx \frac{ed_{small}}{N^4}\approx 2^{1021}$

则有

$|\frac{e}{N^4}-\frac{k}{d_{small}}|\leq \frac{2^{1021}*2^{2049}}{N^4d_{small}}\approx \frac{2^{3070}}{2^{4096} * 2^{1020}}=2^{-2046}<\frac{1}{2d_{small}^2}\approx 2^{-2043}$

说明满足Legendre's theorem，所以可以通过连分数展开得到$d_{small}$

然后来看加密部分：

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()

• R = Integers(N)：定义模N的整数环$\Z /N\Z$

• P = PolynomialRing(R, 't')：在环R上构造多项式环($\Z/N\Z$)[t]

• Q = P.quotient(t**n - r)：构造商环$Q=\frac{(\Z/N\Z)[t]}{(t^4-2)}$

  • 在Q中满足 $t^4=2$ (因为模掉了理想 $⟨t^4−2⟩$)

• m_poly = Q([m, 0, 0, 0])：将m嵌入商环Q中的元素：

  $m_{poly}=m+0*t+0*t^2+0*t^3$

  • 这本质上是常数多项式（仅常数项非零）

• c_poly = m_poly ** e：

  • 在商环Q中进行指数运算，但由于$m_{poly}$是常数多项式，运算简化为$c_{poly}=m^e（在商环Q中）$
  • 所以等价于RSA的$c=m^e\ \ mod\ \ n$

此处$ed_{small}=-1\ \ mod\ \ \phi$，所以解密时$m=c^{-d_{small}}\ \ mod\ \ n$

题解：

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


N = 99697845285265879829811232968100099666254250525000506525475952592468738395250956460890611762459685140661035795964867321445992110528627232335703962897072608767840783176553829502743629914407970206513639916759403399986924602596286330464348286080258986075962271511105387188070309852907253486162504945490429185609
e = 74900336437853271512557457581304251523854378376434438153117909482138661618901386551154807447783262736408028580620771857416463085746907317126876189023636958838207330193074215769008709076254356539808209005917645822989554532710565445155350102802675594603406077862472881027575871589046600011223990947361848608637247276816477996863812313225929441545045479384803449990623969591150979899801722841101938868710054151839628803383603849632857020369527380816687165487370957857737696187061619496102857237814447790678611448197153594917852504509869007597997670022501500067854210261136878917620198551551460145853528269270832725348151160651020188255399136483482428499340574623409209151124687319668989144444549871527949104436734300277004316939985015286758651969045396343970037328043635061226100170529991733947365830164811844853806681198818875837903563263114249814483901121700854712406832325690101810786429930813776784979083590353027191492894890551838308899148551566437532914838098811643805243593419063566975400775134981190248113477610235165151367913498299241375039256652674679958159505112725441797566678743542054295794919839551675786573113798857814005058856054462008797386322048089657472710775620574463924678367455233801970310210504653908307254926827
c = 98460941530646528059934657633016619266170844887697553075379408285596784682803952762901219607460711533547279478564732097775812539176991062440097573591978613933775149262760936643842229597070673855940231912579258721734434631479496590694499265794576610924303262676255858387586947276246725949970866534023718638879

cf = continued_fraction(e/N^4)
convs = cf.convergents()

for conv in convs:
    d = conv.denominator()
    if d.bit_length() == 1021:
        print(f'd = {d}')
        m = pow(c,-d,N)
        print(long_to_bytes(m))