HKCERT2025Quals • Misay's blog

初赛难度比较适中，质量也不错，来给进行一个复现

Bivariate copper#

那麼問題來了，什麼是copper？ So the question is, what is copper?

chall.py

from Crypto.Util.number import *
from secret import *

with open("message", "r") as f:
    message = f.read().strip().encode()

m = bytes_to_long(flag)
message = bytes_to_long(message)

p = getPrime(1024)
q = getPrime(25)
N = p * q
e = 65537

c = pow(message, e, N)
r1, r2 = getPrime(512), getPrime(512)
k = getPrime(64)

t1 = (k * inverse(m + r1, p)) % p
t2 = (k * inverse(m + r2, p)) % p

leak1 = t1 >> 244
leak2 = t2 >> 244

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

print(f'{k = }')
print(f'{r1 = }')
print(f'{r2 = }')
print(f'{leak1 = }')
print(f'{leak2 = }')

'''
e = 65537
N = 3333577291839009732612693330613476891341287017491683764014849337158389717338712200133085615150269196268856288361865352673921704626130772582853528604556994221890454520933132803888321775335519781063447756692130742361931522856942232406992357982482263472763363458621836220024977864980600979194500121897419553619426163227
c = 1277272201928931051067525742142583320131498687502905469530557519241347169899260720694873154669476372724906606385788056536109971768256973988460766527896895880291037980646963981472637862512247195798266373251524526460097881602691641026093728861572872156172787168597410496150253340538386296663073088345799201197096884740
k = 9352039867057736323
r1 = 10421792656200324147964684790160875926436411483496860422433732508593789212449544620816674407170998779863336939494663076247759140488927744939619406024905901
r2 = 8806088830734144089522276896226392806947836111998696180055727048752624989402057411311728398322297424598954586424896296000606209022432442660527640463521679
leak1 = 4266222222502644630611545246271868348722888987303187402827005454059765428769160822475080050046035916876078546634293907218937483241284454918367519709206766322037148585465519188582916280829212776096606923824120883699251868362915920299645
leak2 = 1176921186497191878459783787148403806360469809421921990427675048480656171919274113895695842508460760829511824635106692634456334400022597605585661597793889066395539405395254174368285751236344600489419240628821864912762242188289636510706
'''

前半部分可以直接爆破 $p$ 得到 $message$

from Crypto.Util.number import *
import itertools
N = 3333577291839009732612693330613476891341287017491683764014849337158389717338712200133085615150269196268856288361865352673921704626130772582853528604556994221890454520933132803888321775335519781063447756692130742361931522856942232406992357982482263472763363458621836220024977864980600979194500121897419553619426163227
e = 65537
c = 1277272201928931051067525742142583320131498687502905469530557519241347169899260720694873154669476372724906606385788056536109971768256973988460766527896895880291037980646963981472637862512247195798266373251524526460097881602691641026093728861572872156172787168597410496150253340538386296663073088345799201197096884740

# get p
for i in range(2, 2**25):
    if N % i == 0:
        q = i
        break

p = N // q

# d = inverse(e, (p-1)*(q-1))
# print(long_to_bytes(pow(c,d,N)))
# b'Hurry up and go smelt copper!'

然后分析第二部分我们定义了

t_1\equiv k\times(m+r_1)^{-1}\equiv leak_1\times2^{244}+x\mod p

t_2\equiv k\times(m+r_2)^{-1}\equiv leak_2\times2^{244}+y\mod p

我们已知 $leak_1\;\;leak_2\;\;r_1\;\;r_2\;\;p$ ， $x\;\;y$ 是244bits内的小量结合题干不难想到二元Copper 我们给 $m$ 消去不难得到

m\equiv(leak_1\times2^{244}+x)\times k^{-1} -r_1\equiv (leak_2\times2^{244}+y)\times k^{-1} -r_2\mod p

做差就可以得到一个含两个变元的小根方程

((leak_1-leak_2)\times2^{244}+x-y)\times k^{-1}-(r_1-r_2)\equiv 0\mod p

$x\;\;y$ 都是244bits以内而 $p$ 为1024bits的，存在 $244\lt\frac{1024}{4}$ ,可解

打一发二元Copper

k = 9352039867057736323
r1 = 10421792656200324147964684790160875926436411483496860422433732508593789212449544620816674407170998779863336939494663076247759140488927744939619406024905901
r2 = 8806088830734144089522276896226392806947836111998696180055727048752624989402057411311728398322297424598954586424896296000606209022432442660527640463521679
leak1 = 4266222222502644630611545246271868348722888987303187402827005454059765428769160822475080050046035916876078546634293907218937483241284454918367519709206766322037148585465519188582916280829212776096606923824120883699251868362915920299645
leak2 = 1176921186497191878459783787148403806360469809421921990427675048480656171919274113895695842508460760829511824635106692634456334400022597605585661597793889066395539405395254174368285751236344600489419240628821864912762242188289636510706





def small_roots(f, bounds, m=6, d=None):
    if not d:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality() #取得模数

    f /= f.coefficients().pop(0) #最高次项系数化为0，coefficients是多项式的降次幂排列系数
    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)
    # print(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 []


R = PolynomialRing(Zmod(p), names=('x', 'y'))
inv_k = inverse_mod(k, p)
x, y = R.gens()

f = (r2-r1)*(leak1 * 2^244 + x)*(leak2 * 2^244 + y) - k*(leak1 * 2^244 + x - leak2 * 2^244 - y)
roots = small_roots(f, bounds=(2^245,2^245))  

t1low = int(roots[0][0])

t1 = t1low + leak1 * 2^244
m = (inverse_mod(t1, p) * k - r1 )  % p
print(long_to_bytes(m))


# b'flag{H4hAHhhHh4_c0pP3r_N07_v1OI3n7_3n0uGh}'

ComCompleXX#

我最近開始迷上數學了，但這題看起來真的很複複複雜，你能幫我嗎？ I’ve recently become obsessed with math, but this problem seems really comcomplexx. Can you help me?

task.py

from Crypto.Util.number import *
import random
from secret import flag, key

p, q, e, d = key
n = p * q

assert isPrime(p) and isPrime(q) and p.bit_length() == 512 and q.bit_length() == 512
print('d_len:', d.bit_length())
# d_len: 500

class QN:
    def __init__(self, a, b, c, d, n):
        self.a = a % n
        self.b = b % n
        self.c = c % n
        self.d = d % n
        self.n = n
    def __mul__(self, other):
        if isinstance(other, QN) and self.n == other.n:
            n = self.n
            a1, b1, c1, d1 = self.a, self.b, self.c, self.d
            a2, b2, c2, d2 = other.a, other.b, other.c, other.d
            a = (a1*a2 - b1*b2 - c1*c2 - d1*d2) % n
            b = (a1*b2 + b1*a2 + c1*d2 - d1*c2) % n
            c = (a1*c2 - b1*d2 + c1*a2 + d1*b2) % n
            d = (a1*d2 + b1*c2 - c1*b2 + d1*a2) % n
            return QN(a, b, c, d, n)
        return NotImplemented
    def __pow__(self, exp):
        if exp <= 0:
            return QN(1, 0, 0, 0, self.n)
        result = QN(1, 0, 0, 0, self.n)
        base = self
        while exp > 0:
            if exp & 1:
                result = result * base
            base = base * base
            exp >>= 1
        return result
    def __repr__(self):
        return f"({self.a}, {self.b}, {self.c}, {self.d})"
    def __eq__(self, other):
        return (self.a == other.a and self.b == other.b and 
                self.c == other.c and self.d == other.d and self.n == other.n)

if __name__ == "__main__":
    m = QN(bytes_to_long(flag), random.randint(1,n-1), random.randint(1,n-1), random.randint(1,n-1), n)
    c = pow(m, e)
    assert pow(c,d) == m

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

'''
n = 85481717157593593434025329804251284752138281740610011731799389557859119300838454555657179864017815910265870318909961454026714464920305413622061116245330661303912116693461205161551044610609272231860357133575507519403908786715597649351821576114881230052647979679534076432015415470679178775688932706964062378627
e = 622349328830189017262721806176220642327451718814004869262654184548169579851269489422592218838968239824917128227573062775020729663341881800222644869706115998147909113383905386637703321110321003518025501597602036772247509043126119242571435842445265921450671551669304835480011469949693693324643919337459251944818821206437044742271947245399811180478630764346756372873090874700249814285609571282905316777766489385036566372369518133091334281269104669836052038324087775082397535339943512028851288569342237442241378961242047171826362264504999955091800815867645003788806864324904993634075730184915611726197403247247938385732000097424282851846018331719216174462481994636142469669316961566262677169345291992925101965060785779535371861314213957527417556275049382603735394888681049143483994633920712406197215676594926797093225468201559158552767178665382859062516627874818691572997614241454801824762125841557409876879638813879540588189811
c = (36509962693210047517809190780500733945629638467721636016118307831299153205787169088399018032858962653944360359037757238416729623515314461908869670066385367461579954207170900898502608201371741903312247217007567631584237670049543882850246347784852813361080564895289678219739976819925055830837232548960336550804, 14959247128290207711158598578966149380261887381574636597156641284189267790471920774170808806288580563577492441070024491886953389517733477847472737986545246252874395600374486543947605977380365673302757291495953658030048738906460472042379676160137626447499571382731894905380992263233204548600668812780247601325, 36653805985529315558503796353782648503316310086826701482263862429608379730584363732938416744191295088641419179725673205148217999183797829423539295825286947419128575063946728227807922575922697370871241826105471260524875137135999213015948866472957081351066130709476717779611974377854714476824268335455979590736, 44619982799889884704010277482810139576960205880619960462167175653326841572868809642692412859814472796539211092403704130039198480671655784971458045667408446084843398171460450068014922244839889367385992492875980531522963147513445040259751323986442839404788429909271285196520486381047903450020895598546088952188)
'''

四元数RSA问题

注意到给的 $d$ 的bits为500 而 $n$ 为1024bits $e$ 的位数为3069 非常诡异的大我们尝试打连分数但是不去分解 $n$ 能够神奇的解决

exp.sage

from Crypto.Util.number import *


class QN:
    def __init__(self, a, b, c, d, n):
        self.a = a % n
        self.b = b % n
        self.c = c % n
        self.d = d % n
        self.n = n

    def __mul__(self, other):
        a1, b1, c1, d1 = self.a, self.b, self.c, self.d
        a2, b2, c2, d2 = other.a, other.b, other.c, other.d
        n = self.n
        return QN(
            (a1 * a2 - b1 * b2 - c1 * c2 - d1 * d2) % n,
            (a1 * b2 + b1 * a2 + c1 * d2 - d1 * c2) % n,
            (a1 * c2 - b1 * d2 + c1 * a2 + d1 * b2) % n,
            (a1 * d2 + b1 * c2 - c1 * b2 + d1 * a2) % n,
            n,
        )

    def __pow__(self, exp):
        result = QN(1, 0, 0, 0, self.n)
        base = self
        while exp > 0:
            if exp & 1:
                result = result * base
            base = base * base
            exp >>= 1
        return result


n = 85481717157593593434025329804251284752138281740610011731799389557859119300838454555657179864017815910265870318909961454026714464920305413622061116245330661303912116693461205161551044610609272231860357133575507519403908786715597649351821576114881230052647979679534076432015415470679178775688932706964062378627
e = 622349328830189017262721806176220642327451718814004869262654184548169579851269489422592218838968239824917128227573062775020729663341881800222644869706115998147909113383905386637703321110321003518025501597602036772247509043126119242571435842445265921450671551669304835480011469949693693324643919337459251944818821206437044742271947245399811180478630764346756372873090874700249814285609571282905316777766489385036566372369518133091334281269104669836052038324087775082397535339943512028851288569342237442241378961242047171826362264504999955091800815867645003788806864324904993634075730184915611726197403247247938385732000097424282851846018331719216174462481994636142469669316961566262677169345291992925101965060785779535371861314213957527417556275049382603735394888681049143483994633920712406197215676594926797093225468201559158552767178665382859062516627874818691572997614241454801824762125841557409876879638813879540588189811
c = QN(
    36509962693210047517809190780500733945629638467721636016118307831299153205787169088399018032858962653944360359037757238416729623515314461908869670066385367461579954207170900898502608201371741903312247217007567631584237670049543882850246347784852813361080564895289678219739976819925055830837232548960336550804,
    14959247128290207711158598578966149380261887381574636597156641284189267790471920774170808806288580563577492441070024491886953389517733477847472737986545246252874395600374486543947605977380365673302757291495953658030048738906460472042379676160137626447499571382731894905380992263233204548600668812780247601325,
    36653805985529315558503796353782648503316310086826701482263862429608379730584363732938416744191295088641419179725673205148217999183797829423539295825286947419128575063946728227807922575922697370871241826105471260524875137135999213015948866472957081351066130709476717779611974377854714476824268335455979590736,
    44619982799889884704010277482810139576960205880619960462167175653326841572868809642692412859814472796539211092403704130039198480671655784971458045667408446084843398171460450068014922244839889367385992492875980531522963147513445040259751323986442839404788429909271285196520486381047903450020895598546088952188,
    n,
)
print(e.bit_length())

def wienerAttack(N, e, c):
    res = []
    rres = []
    cf = continued_fraction(e / N)
    convers = cf.convergents()
    for pkds in convers:
        pk, pds = pkds.as_integer_ratio()
        if pk == 0 or pds == 0:
            continue
        if (e * pds - 1) % pk != 0:
            continue
        m = c ** pds
        mes = long_to_bytes(m.a)
        if mes.endswith(b"}"):
            print(pds.bit_length())
            return mes

res = wienerAttack(n, e, c)
assert res
if res:
    print(res)
    
# 500
# b'flag{Qu4t3rNion_l5_S0_6rea7_&_Ch4rm1n9}'

验证后这个 $d$ 的确是题目给我们的但是 $k$ 并不能用来分解我们的 $n$

我们来从出题人的视角看看这些 $e\;\;d\;\;p\;\;q$ 是怎么生成的

首先随机生成两个512位的素数 $p\;\;q$

在四元数系统下一定有群的阶 $\phi$ 满足 $(p-1)(q-1)|\phi$

生成一个数 $e_0$ 计算 $d_0\equiv e_0^{-1}\mod \phi$

随后保证连分数的命中性质要有
$|\frac{e}{n}-\frac{k}{d}|\lt\lt\frac{1}{2d^2}$
整理得到
$|ed-nk|\lt\frac{n}{2d}$
本题实际做到的是
$|ed-nk|=1$
随后根据 $e=e_0+k\phi$

生成这个大的诡异的 $e$

主要是确实验证了

assert abs(e*d-k*n) == 1

事已至此就先这样吧还没看出这个题和四元数有什么关系（或许是构造了一个整除阶的群？

cruel-rsa#

task.py

from sage.all import *  
from sage.crypto.util import random_blum_prime
from Crypto.Util.number import *
from secret import flag

nbit = 512
gamma = 0.44
delta = 0.51
dm,dl = 0.103, 0.145
cpbit = ceil(nbit * gamma) 
kbit  = int(nbit * delta)
msbit = int(nbit * dm)
lsbit = int(nbit * dl)
g = random_blum_prime(2**(cpbit - 1), 2**cpbit-1)  
while 1:
    p = q = 0
    while is_prime(p) or len(bin(p)) - 2 != nbit // 2:
        a = randint(int(2 ** (nbit // 2 - 2) // g * gamma), 2 ** (nbit // 2 - 1) // g)
        p = 2 * g * a + 1 
    while is_prime(q) or len(bin(q)) - 2 != nbit // 2:
        b = randint(int(2 ** (nbit // 2 - 2) // g * gamma), 2 ** (nbit // 2 - 1) // g)
        q = 2 * g * b + 1
    L = 2 * g * a * b   
    if is_prime(L + a + b):
        n = p * q
        break

d = random_prime(2**kbit-1, lbound=2**(kbit - 1)) 
e = inverse_mod(d, L)
k = (e * d - 1) // L
dm = d // (2 ** (kbit - msbit))
dl = d % (2 ** lsbit)
m = bytes_to_long(flag)
print(dm, dl, e, n)
print(pow(m, e, n))
"""
3203202584971257 7274383203268085152331 36346110007425305872660997908648011390452485009167380402907988449045651435844811625907 8073736467273664280056643912209398524942152147328656910931152412352288220476046078152045937002526657533942284160476452038914249779936821603053211888330755
8042279705649954745962644909235780183674555369775538455015331686608683922326562829164835918982642084136603628007677118144681339970688028985720674063973679
"""

很明显的Common-prime-rsa 给出了 $d$ 的泄露

我们参考改进的pollard-rho算法可以发现N具备比较好的光滑性我们慢慢剥离大概到1609668743算法就开始吃力了

def rho(N):
    f = lambda x: (pow(x, N-1, N) + 3) % N
    while True:
        # 加快入环速度
        t = random.randint(2, N)
        h = f(t)
        step_times = 0
        step_limit = 2
        while True:
            if not step_times < step_limit:
                step_times = 0
                step_limit *= 2
                t = h
                h = f(h)
            p = gcd(abs(int(t) - int(h)), N)
            if p == N:
                break
            elif p > 1:
                return (p, N // p)
            else:
                h = f(h)
                step_times += 1

同时可以确定这里的 $n$ 确实过于光滑

然后似乎 $n-1$ 也可以被查到分解那还说啥呢

然后利用 $p\;q$ 的位数以及合数关系可以筛选出我们的 $p\;q$ 加上 $g$ 已知我们可以求出 $a\;b\;g\;p\;q$

求出 $L$ 再求出 $d$ 结果因为这里的 $d$ 是在模 $L$ 下生成但是

L=2gab\;\;;\;\;\phi(n) \not=4g^2ab

所以说你求出了 $d$ 也是没法解密的，，，

但是可以打CRT直接解方程 $m^e\equiv c\mod n$ ，毕竟有 $n$ 的分解那么我们求 $d$ 意义何在，，，

exp

from collections import Counter
from Crypto.Util.number import *
e = 36346110007425305872660997908648011390452485009167380402907988449045651435844811625907
n = 8073736467273664280056643912209398524942152147328656910931152412352288220476046078152045937002526657533942284160476452038914249779936821603053211888330755
c = 8042279705649954745962644909235780183674555369775538455015331686608683922326562829164835918982642084136603628007677118144681339970688028985720674063973679

factors = [
    3,
    3,
    5,
    11,
    13,
    241,
    19913,
    27479,
    8817293,
    1609668743,
    21744410757863,
    1791152102074579,
    2640729780285917881567,
    561544524741926577700278571,
    11606767999414698455890262045272382868998286949,
]

assert prod(factors) == n

def roots_mod_prime_power(p, k, e, c):
    mod = p ** k
    if c % mod == 0:
        t = (k + e - 1) // e
        base = p ** t
        return [base * r for r in range(p ** (k - t))]
    if k == 1:
        return [power_mod(c % p, inverse_mod(e, p - 1), p)]
    # For p odd, gcd(e, phi(p^k)) = 1 gives a unique root.
    root_p = power_mod(c % p, inverse_mod(e, p - 1), p)
    return [crt([root_p], [p], [c], [p ** k])[0] % mod]

prime_powers = Counter(factors)
mods_roots = []
for p, k in prime_powers.items():
    phi = (p - 1) * (p ** (k - 1))
    assert gcd(e, phi) == 1
    roots = roots_mod_prime_power(p, k, e, c)
    mods_roots.append((p ** k, roots))

solutions = [(0, 1)]
for mod, roots in mods_roots:
    new_solutions = []
    for a, m in solutions:
        for r in roots:
            x = crt([a, r], [m, mod])
            new_solutions.append((x, m * mod))
    solutions = new_solutions

hits = 0
for m, mod in solutions:
    if mod != n:
        continue
    pt = long_to_bytes(m)
    if pt.endswith(b"}"):
        hits += 1
        print("hit:", pt)

print("total hits:", hits)

'''
hit: b'flag{baby_so_rsa_this_is}'
total hits: 1
'''

EC-FUN#

密碼學很簡單！祝你玩得開心！ Crypto is so EC! May you have fun!

from Crypto.Cipher import AES
import random

flag = '******'.encode()
p = 1361137685787644823054950239221481267310111

have = lambda s,t:((1132105824051503958365821105743937899761226*s[0]**3 + 229031861736140864689129133477543367548885*s[0]**2*t[0] + 229031861736140864689129133477543367548885*s[0]*t[0]**2 + 1132105824051503958365821105743937899761226*t[0]**3 + 820243406944125048991336110221143271981334*s[0]**2 + 649313030456686003640437242797882952355121*s[0]*s[1] + 527983998322961064385871655992141377230770*s[1]**2 + 1081788557687039548127228258000675990657554*s[0]*t[0] + 711824655330958819414512996423598314954990*s[1]*t[0] + 820243406944125048991336110221143271981334*t[0]**2 + 711824655330958819414512996423598314954990*s[0]*t[1] + 305169689141722694283206927237198512848571*s[1]*t[1] + 649313030456686003640437242797882952355121*t[0]*t[1] + 527983998322961064385871655992141377230770*t[1]**2)*pow(229031861736140864689129133477543367548885*s[0]**2 + 903073962315363093676691972266394532212341*s[0]*t[0] + 229031861736140864689129133477543367548885*t[0]**2,-1,p)%p, (54187766978142688518903451220347809940963*s[0]**4 + 229031861736140864689129133477543367548885*s[0]**3*s[1] + 1252762151831359446017143336780785647428185*s[0]**3*t[0] + 674042100579222228987562838788851164663456*s[0]*s[1]*t[0]**2 + 108375533956285377037806902440695619881926*s[0]*t[0]**3 + 458063723472281729378258266955086735097770*s[1]*t[0]**3 + 1306949918809502134536046788001133457369148*t[0]**4 + 903073962315363093676691972266394532212341*s[0]**3*t[1] + 687095585208422594067387400432630102646655*s[0]**2*t[0]*t[1] + 1132105824051503958365821105743937899761226*t[0]**3*t[1] + 409448300551393558178072250995397507413084*s[0]**3 + 1207230666903911661795540475036106991723031*s[0]**2*s[1] + 62511624874272815774075753625715362599869*s[0]*s[1]**2 + 833153687464683758669078583229339890079341*s[1]**3 + 132792784133464148520733486235288745070859*s[0]**2*t[0] + 307814037767466322518819528370748551174160*s[0]*s[1]*t[0] + 1298626060913372007280874485595765904710242*s[1]**2*t[0] + 1228344901654180674534216752986192522239252*s[0]*t[0]**2 + 1207230666903911661795540475036106991723031*s[1]*t[0]**2 + 951689385236251264876877988226083759897027*t[0]**3 + 153907018883733161259409764185374275587080*s[0]**2*t[1] + 1236114436039099191506798731970050542110373*s[0]*s[1]*t[1] + 222814309181238370102664728754942864382199*s[1]**2*t[1] + 1053323648020178500536130710850732716135951*s[0]*t[0]*t[1] + 125023249748545631548151507251430725199738*s[1]*t[0]*t[1] + 153907018883733161259409764185374275587080*t[0]**2*t[1] + 62511624874272815774075753625715362599869*s[0]*t[1]**2 + 1138323376606406452952285510466538402927912*s[1]*t[1]**2 + 1298626060913372007280874485595765904710242*t[0]*t[1]**2 + 527983998322961064385871655992141377230770*t[1]**3)*pow(229031861736140864689129133477543367548885*s[0]**3 + 674042100579222228987562838788851164663456*s[0]**2*t[0] + 687095585208422594067387400432630102646655*s[0]*t[0]**2 + 1132105824051503958365821105743937899761226*t[0]**3,-1,p)%p)
fun = lambda t:((1355411426698193074927107560516481409632646*t[0]**4 + 1178449528330025005130887555984327255695700*t[0]**3 + 431210186226622274082401960566604243166160*t[0]**2*t[1] + 59195913557099283872495176385768072148921*t[0]*t[1]**2 + 251369299603578168918462619253512221092756*t[0]**2 + 879678478093874414429176172962662062922270*t[0]*t[1] + 281103361207015191365820977148971655332738*t[1]**2 + 362519131628697943100337725424101898137457*t[0] + 443705393890279523315779887935020111939334*t[1] + 578364425578037679604436300506704082028031)*pow(956880610267536390357724782030411500415237*t[0]**2 + 1145532592674333686013749258938179145727031*t[0]*t[1] + 650970886115272769591227531417856597580595*t[1]**2 + 233572674711604604519014902334948133513444*t[0] + 535453460641822632058096218419954325337796*t[1] + 725112018286073523450664990921518386913035,-1,p)%p, (1229680448238589741915782165367654357920185*t[0]**6 + 508331960611786860744946345382725399597519*t[0]**5 + 1343958908519289578671422203106481694277716*t[0]**4*t[1] + 177167026616744824850256300247635539724057*t[0]**3*t[1]**2 + 647526478257364195975697407176118287861906*t[0]**4 + 874634578828271234182240863130269063092359*t[0]**3*t[1] + 753721599708341578448324615735431250261044*t[0]**2*t[1]**2 + 59195913557099283872495176385768072148921*t[0]*t[1]**3 + 135184449413711070637582564227488684273926*t[1]**4 + 1184268232038119513987721523209048245879902*t[0]**3 + 588376066139055328517853740807864391561055*t[0]**2*t[1] + 975956920560485006036771022835309336072696*t[0]*t[1]**2 + 1352108846430422970045668681682022723360513*t[1]**3 + 1280832417616997174969599325837067484280181*t[0]**2 + 954546681684014316952546155309712995684234*t[0]*t[1] + 865928094420333438629116336228132264435796*t[1]**2 + 1082085886860697193173121066542089802274658*t[0] + 755869998556204076975668261501936206771336*t[1] + 657902451019006293214253561308197638483112)*pow(956880610267536390357724782030411500415237*t[0]**3 + 1037730046117678117493148768796528084935491*t[0]**2*t[1] + 591774972558173485718732355032088525431674*t[0]*t[1]**2 + 1225953236373933752417367674993992583036185*t[1]**3 + 350359012067406906778522353502422200270166*t[0]**2 + 245222696137823073119338416038381708703277*t[0]*t[1] + 1197892972677768820041026587455773400480227*t[1]**2 + 814198369070575747297044733543073893428994*t[0] + 447093761510564524382892260162823859185717*t[1] + 558976911634572335364921619094958402137856,-1,p)%p)

def have_fun(a, b):
    res = g1
    while b:
        if b&1:
            res = have(res,a)
        a = fun(a)
        b >>= 1
    return res

g1 = (1151954709424958906091046463160132564937644,709388597947225692614956015386635942863012)
g2 = (981333628607549915704008747402562350211701,1251610635487471222383956310361676241534200)

key = random.randrange(2,1<<54)
y = have_fun(g2, key)

print('y =',y)
# y = (1233646914495991358880000369082822614720033, 169216170896679696320800078452784590711491)

cipher = AES.new(str(key).encode()[:16], AES.MODE_ECB)
enc = cipher.encrypt(flag)
print('enc =', enc)
# enc = b"t\xf1x\xc2'}q\xe7i.\x0cmj\x0fkNkVJ-\xd5\xbf\xf9H_\xd1\x04hO\xcd\xe1\x95P\xad\xea\xe1\xec\x1c\xben?RCr\x932\x90t"

ECC问题给定了两个函数原型have 与fun 前者为曲线上的一种点加后者为一种倍乘（LLM直接看出来了，或者根据这里的传参个数也能大致猜测）

这里调用函数have_fun相当于计算

y=g_1+g_2\times key

所以说我们接下来分析这个椭圆曲线群的性质,尝试由已知的点加倍乘 3个曲线上的点来去恢复曲线方程

给出一种方法也就是对于这种Twisted-Curved的通用处理手法

把曲线设成

c_0y^2+c_1xy+c_2y+c_3x^3+c_4x^2+c_5x+c_6\equiv0

的广义形式（或者还可以更复杂）然后利用have和fun以及基点做出一系列点来进行插值求出系数 $c_0\sim c_6$

然后去往我们的标准形式去做变换进行简单的逆元乘法即可

y^2+a_1xy+a_3y\equiv x^3+a_2x^2+a_4x+a_6

这里因为我们直接设的就是广义形式所以说简单的代数变换就可以当然也可以考虑2024羊城杯的手法，先

x\rightarrow\frac{X}{Z}

y\rightarrow\frac{Y}{Z}

得到一个关于 $X\;Y\;Z$ 的多项式方程，再调用EllipticCurve_from_cubic方法也可以得到标准的曲线然后就是正常的曲线DLP 当然这里涉及的都是常见的Twisted-Curve 所以说我们能成功求解

exp

from Crypto.Cipher import AES

p = 1361137685787644823054950239221481267310111
F = GF(p)

g1 = (1151954709424958906091046463160132564937644,
      709388597947225692614956015386635942863012)
g2 = (981333628607549915704008747402562350211701,
      1251610635487471222383956310361676241534200)
y = (1233646914495991358880000369082822614720033,
     169216170896679696320800078452784590711491)
enc = b"t\xf1x\xc2'}q\xe7i.\x0cmj\x0fkNkVJ-\xd5\xbf\xf9H_\xd1\x04hO\xcd\xe1\x95P\xad\xea\xe1\xec\x1c\xben?RCr\x932\x90t"

have = lambda s, t:((1132105824051503958365821105743937899761226*s[0]**3 + 229031861736140864689129133477543367548885*s[0]**2*t[0] + 229031861736140864689129133477543367548885*s[0]*t[0]**2 + 1132105824051503958365821105743937899761226*t[0]**3 + 820243406944125048991336110221143271981334*s[0]**2 + 649313030456686003640437242797882952355121*s[0]*s[1] + 527983998322961064385871655992141377230770*s[1]**2 + 1081788557687039548127228258000675990657554*s[0]*t[0] + 711824655330958819414512996423598314954990*s[1]*t[0] + 820243406944125048991336110221143271981334*t[0]**2 + 711824655330958819414512996423598314954990*s[0]*t[1] + 305169689141722694283206927237198512848571*s[1]*t[1] + 649313030456686003640437242797882952355121*t[0]*t[1] + 527983998322961064385871655992141377230770*t[1]**2)*pow(229031861736140864689129133477543367548885*s[0]**2 + 903073962315363093676691972266394532212341*s[0]*t[0] + 229031861736140864689129133477543367548885*t[0]**2,-1,p)%p, (54187766978142688518903451220347809940963*s[0]**4 + 229031861736140864689129133477543367548885*s[0]**3*s[1] + 1252762151831359446017143336780785647428185*s[0]**3*t[0] + 674042100579222228987562838788851164663456*s[0]*s[1]*t[0]**2 + 108375533956285377037806902440695619881926*s[0]*t[0]**3 + 458063723472281729378258266955086735097770*s[1]*t[0]**3 + 1306949918809502134536046788001133457369148*t[0]**4 + 903073962315363093676691972266394532212341*s[0]**3*t[1] + 687095585208422594067387400432630102646655*s[0]**2*t[0]*t[1] + 1132105824051503958365821105743937899761226*t[0]**3*t[1] + 409448300551393558178072250995397507413084*s[0]**3 + 1207230666903911661795540475036106991723031*s[0]**2*s[1] + 62511624874272815774075753625715362599869*s[0]*s[1]**2 + 833153687464683758669078583229339890079341*s[1]**3 + 132792784133464148520733486235288745070859*s[0]**2*t[0] + 307814037767466322518819528370748551174160*s[0]*s[1]*t[0] + 1298626060913372007280874485595765904710242*s[1]**2*t[0] + 1228344901654180674534216752986192522239252*s[0]*t[0]**2 + 1207230666903911661795540475036106991723031*s[1]*t[0]**2 + 951689385236251264876877988226083759897027*t[0]**3 + 153907018883733161259409764185374275587080*s[0]**2*t[1] + 1236114436039099191506798731970050542110373*s[0]*s[1]*t[1] + 222814309181238370102664728754942864382199*s[1]**2*t[1] + 1053323648020178500536130710850732716135951*s[0]*t[0]*t[1] + 125023249748545631548151507251430725199738*s[1]*t[0]*t[1] + 153907018883733161259409764185374275587080*t[0]**2*t[1] + 62511624874272815774075753625715362599869*s[0]*t[1]**2 + 1138323376606406452952285510466538402927912*s[1]*t[1]**2 + 1298626060913372007280874485595765904710242*t[0]*t[1]**2 + 527983998322961064385871655992141377230770*t[1]**3)*pow(229031861736140864689129133477543367548885*s[0]**3 + 674042100579222228987562838788851164663456*s[0]**2*t[0] + 687095585208422594067387400432630102646655*s[0]*t[0]**2 + 1132105824051503958365821105743937899761226*t[0]**3,-1,p)%p)
fun = lambda t:((1355411426698193074927107560516481409632646*t[0]**4 + 1178449528330025005130887555984327255695700*t[0]**3 + 431210186226622274082401960566604243166160*t[0]**2*t[1] + 59195913557099283872495176385768072148921*t[0]*t[1]**2 + 251369299603578168918462619253512221092756*t[0]**2 + 879678478093874414429176172962662062922270*t[0]*t[1] + 281103361207015191365820977148971655332738*t[1]**2 + 362519131628697943100337725424101898137457*t[0] + 443705393890279523315779887935020111939334*t[1] + 578364425578037679604436300506704082028031)*pow(956880610267536390357724782030411500415237*t[0]**2 + 1145532592674333686013749258938179145727031*t[0]*t[1] + 650970886115272769591227531417856597580595*t[1]**2 + 233572674711604604519014902334948133513444*t[0] + 535453460641822632058096218419954325337796*t[1] + 725112018286073523450664990921518386913035,-1,p)%p, (1229680448238589741915782165367654357920185*t[0]**6 + 508331960611786860744946345382725399597519*t[0]**5 + 1343958908519289578671422203106481694277716*t[0]**4*t[1] + 177167026616744824850256300247635539724057*t[0]**3*t[1]**2 + 647526478257364195975697407176118287861906*t[0]**4 + 874634578828271234182240863130269063092359*t[0]**3*t[1] + 753721599708341578448324615735431250261044*t[0]**2*t[1]**2 + 59195913557099283872495176385768072148921*t[0]*t[1]**3 + 135184449413711070637582564227488684273926*t[1]**4 + 1184268232038119513987721523209048245879902*t[0]**3 + 588376066139055328517853740807864391561055*t[0]**2*t[1] + 975956920560485006036771022835309336072696*t[0]*t[1]**2 + 1352108846430422970045668681682022723360513*t[1]**3 + 1280832417616997174969599325837067484280181*t[0]**2 + 954546681684014316952546155309712995684234*t[0]*t[1] + 865928094420333438629116336228132264435796*t[1]**2 + 1082085886860697193173121066542089802274658*t[0] + 755869998556204076975668261501936206771336*t[1] + 657902451019006293214253561308197638483112)*pow(956880610267536390357724782030411500415237*t[0]**3 + 1037730046117678117493148768796528084935491*t[0]**2*t[1] + 591774972558173485718732355032088525431674*t[0]*t[1]**2 + 1225953236373933752417367674993992583036185*t[1]**3 + 350359012067406906778522353502422200270166*t[0]**2 + 245222696137823073119338416038381708703277*t[0]*t[1] + 1197892972677768820041026587455773400480227*t[1]**2 + 814198369070575747297044733543073893428994*t[0] + 447093761510564524382892260162823859185717*t[1] + 558976911634572335364921619094958402137856,-1,p)%p)

# ----------------- build points and interpolate -----------------
points = []
p1 = g1
p2 = g2
points.append(p1)
points.append(p2)
p3 = fun(g1)
points.append(p3)
p4 = fun(g2)
points.append(p4)
p5 = have(g1, g2)
points.append(p5)
p6 = have(p3, g2)
points.append(p6)
p7 = have(p4, g1)
points.append(p7)
p8 = fun(p5)
points.append(p8)
p9 = have(p3, p4)
points.append(p9)
points = list(set(points))

# c0*y^2 + c1*x*y + c2*y + c3*x^3 + c4*x^2 + c5*x + c6 = 0
mat_rows = []
for (x, yv) in points:
    row = [yv**2, x*yv, yv, x**3, x**2, x, 1]
    mat_rows.append(row)
M = Matrix(F, mat_rows)
K = M.right_kernel()
coeffs = K.basis()[0]
c0, c1, c2, c3, c4, c5, c6 = coeffs

# normalize so c0 == 1
c0inv = c0.inverse()
c1, c2, c3, c4, c5, c6 = [c*c0inv for c in (c1, c2, c3, c4, c5, c6)]
c0 = F(1)

# ----------------- map to Weierstrass -----------------
# y^2 + a1*x*y + a3*y = x^3 + a2*x^2 + a4*x + a6
u = -c3
a1 = c1
a2 = -c4
a3 = c2 * u
a4 = -c5 * u
a6 = -c6 * u**2

E = EllipticCurve(F, [a1, a2, a3, a4, a6])

def transform(pt):
    x, yv = F(pt[0]), F(pt[1])
    X = u * x
    Y = u * yv
    return E(X, Y)

G1 = transform(g1)
G2 = transform(g2)
Yp = transform(y)

# ----------------- DLP and decrypt -----------------
Yp = Yp - G1
key = discrete_log(Yp, G2, bounds=(0, 1 << 55), operation='+')
print("key =", key)

cipher = AES.new(str(key).encode()[:16], AES.MODE_ECB)
flag = cipher.decrypt(enc)
print(flag)

'''
key = 15946553602128288
b'flag{Tw1s7ed_5tr4nge_Curve_but_S0_3asy}\xe4\xbd\xa0\xe5\xa5\xbd\xe5\xbc\xb7'
'''

LossN#

沒有那個n，我照樣可以解出flag。 Even without that n, I can still solve the flag.

loss.py

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

m = bytes_to_long(flag)
p = getPrime(512)
q = next_prime(p)
n = p * q
e = 0x10001
d = inverse(e, (p-1) * (q-1))
c = pow(m, e, n)
print(f"c = {c}")
print(f"d = {d}")

'''
c = 30552929401084215063034197070424966877689134223841680278066312021587156531434892071537248907148790681466909308002649311844930826894649057192897551604881567331228562746768127186156752480882861591425570984214512121877203049350274961809052094232973854447555218322854092207716140975220436244578363062339274396240
d = 3888417341667647293339167810040888618410868462692524178646833996133379799018296328981354111017698785761492613305545720642074067943460789584401752506651064806409949068192314121154109956133705154002323898970515811126124590603285289442456305377146471883469053362010452897987327106754665010419125216504717347373
'''

利用式子

ed\equiv1\mod \phi

展开

ed-1=k(p-1)\times(p-1+r)

我们注意到

(p-1)(p-1+r)\approx(p-1)^2

而 $k$ 的大小不会超过 $e$ 爆搜就行

exp

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

e = 0x10001
c = 30552929401084215063034197070424966877689134223841680278066312021587156531434892071537248907148790681466909308002649311844930826894649057192897551604881567331228562746768127186156752480882861591425570984214512121877203049350274961809052094232973854447555218322854092207716140975220436244578363062339274396240
d = 3888417341667647293339167810040888618410868462692524178646833996133379799018296328981354111017698785761492613305545720642074067943460789584401752506651064806409949068192314121154109956133705154002323898970515811126124590603285289442456305377146471883469053362010452897987327106754665010419125216504717347373

ED1 = e*d - 1

for k in range(1, e):
    if ED1 % k != 0:
        continue
    T = ED1 // k
    for r in range(1, 5000):
        S = r*r + 4*T
        s = isqrt(S)
        if s*s != S:
            continue
        if (s - r) % 2 != 0:
            continue
        x = (s - r)//2
        if x <= 0:
            continue
        p = x + 1
        q = p + r
        if not isPrime(p) or not isPrime(q):
            continue
        n = p*q
        m = pow(c, d, n)
        print(long_to_bytes(m))
# b'flag{Y0u_kNow_h0w_7o_f4cTor1z3_phI}'

TryE#

from Crypto.Util.number import getPrime, bytes_to_long
from secret import flag

def get_huge_RSA():
    p = getPrime(1024)
    q = getPrime(1024)
    N = p * q
    phi = (p - 1) * (q - 1)
    while True:
        d = getPrime(256)
        e = pow(d, -1, phi)
        if e.bit_length() == N.bit_length():
            break
    return N,e

if __name__ == '__main__':
    N, e = get_huge_RSA()
    m = bytes_to_long(flag)
    c = pow(m, e, N)

    print(f'N = {hex(N)}')
    print(f'e = {hex(e)}')
    print(f'c = {hex(c)}')

'''
N = 0x662854e5ee8b1aa73eea7c897f0f1bd7cace486dea68fb4e9b1affe86ddae225221e9941b7e90b7dd87d57988fc3428f51433a5c2a6e7ef9cbe85aace0925914347ca1d403ea58e2f36435b67648f8caf0abd29c9c24d3caeadab2c41522deda75c19584ec917fa683ff16c932f334db3145a8367c3dc6bc3b918ff3f69f8bfb16c45b4caab1e8ecef24e8e923e984e921115d9fb997a638c8e25d74d592f279359e7147745a7a8443603287120d1a186f30d5a41ce26545f85844721b788564e306791ae39c3be23aeeab010e79302afab4b3e9ab18cb2769382ff8fcbc0514f51861ec6db247f0a0343b7cc6d44299878f7006c118df10de6937c11e3aed7d
e = 0x58a2680eae331e41397475dd699a75f242897e4ed4048338137eb40100cc406b651c4518f4057ad8419cd6a82605113dd5801cd9f022f8bda424b02db5feb333d96636026c3ffc4cab74f7426aa14fb1139663a4f6248dd8e5c7075fcdf3e520c425697775cfb65d33ccca5ffe08d944753b1e9da2dbf96713ece5436deb6dbc843dcd5c497eda9919e055a32c76798770535c6a91ae00b971f35be1ab9e48dd4c701026e0744826001f6fb30e4f68d6e4981aa5a5bbcc995a9e46a4d9b1658348d0fb3b1314fa091251ea1b7379a854a3860fcba2ace323dca8157008d80d6035fd6c880404495f933bf4b4ae829b35823450a921f64b9cf63ae861b3fc4ef7
c = 0x47d2e297294af43a9a02d465f7f5272cab0af2445cbc6022def1098e075dcfb3a7830f09df6112a9fa55b34ed4d0baebad54ea2cbd32e4367cbe7a138409a0ef4c36d837ea7817ec3624fca3a19c1377eaf08e4a519de73cb2c5e99ec8f3998e04d4c3bc44a6f1eb389111bf7c72c68bf1dd743e656467d1ecdd314b37313963758634b83ea96724b1872367a922788f2c8a046c76ccc57e86686bedd7ac431f92b9e2f1fae79701fa0d14d2a0119860c8908336c6caec87b9733f626166373631e1e7e9ba6be92d712e84e821e0e4dc105d460c6640498aefaeb5146d0f57b8e57c3e24bc13f3e79082172c1690428eb49bc6035f1e60f6a579129a2da00c60
'''

e這麼大…何意味？ E is so big… what does it mean?

$d$ 太小直接wiener,打连分数肯定可以但是这个bound用boner-durfee是最稳的（

依旧板子


N = int(0x662854e5ee8b1aa73eea7c897f0f1bd7cace486dea68fb4e9b1affe86ddae225221e9941b7e90b7dd87d57988fc3428f51433a5c2a6e7ef9cbe85aace0925914347ca1d403ea58e2f36435b67648f8caf0abd29c9c24d3caeadab2c41522deda75c19584ec917fa683ff16c932f334db3145a8367c3dc6bc3b918ff3f69f8bfb16c45b4caab1e8ecef24e8e923e984e921115d9fb997a638c8e25d74d592f279359e7147745a7a8443603287120d1a186f30d5a41ce26545f85844721b788564e306791ae39c3be23aeeab010e79302afab4b3e9ab18cb2769382ff8fcbc0514f51861ec6db247f0a0343b7cc6d44299878f7006c118df10de6937c11e3aed7d)
e = int(0x58a2680eae331e41397475dd699a75f242897e4ed4048338137eb40100cc406b651c4518f4057ad8419cd6a82605113dd5801cd9f022f8bda424b02db5feb333d96636026c3ffc4cab74f7426aa14fb1139663a4f6248dd8e5c7075fcdf3e520c425697775cfb65d33ccca5ffe08d944753b1e9da2dbf96713ece5436deb6dbc843dcd5c497eda9919e055a32c76798770535c6a91ae00b971f35be1ab9e48dd4c701026e0744826001f6fb30e4f68d6e4981aa5a5bbcc995a9e46a4d9b1658348d0fb3b1314fa091251ea1b7379a854a3860fcba2ace323dca8157008d80d6035fd6c880404495f933bf4b4ae829b35823450a921f64b9cf63ae861b3fc4ef7)
c = int(0x47d2e297294af43a9a02d465f7f5272cab0af2445cbc6022def1098e075dcfb3a7830f09df6112a9fa55b34ed4d0baebad54ea2cbd32e4367cbe7a138409a0ef4c36d837ea7817ec3624fca3a19c1377eaf08e4a519de73cb2c5e99ec8f3998e04d4c3bc44a6f1eb389111bf7c72c68bf1dd743e656467d1ecdd314b37313963758634b83ea96724b1872367a922788f2c8a046c76ccc57e86686bedd7ac431f92b9e2f1fae79701fa0d14d2a0119860c8908336c6caec87b9733f626166373631e1e7e9ba6be92d712e84e821e0e4dc105d460c6640498aefaeb5146d0f57b8e57c3e24bc13f3e79082172c1690428eb49bc6035f1e60f6a579129a2da00c60)

"""
Setting debug to true will display more informations
about the lattice, the bounds, the vectors...
"""
debug = False

"""
Setting strict to true will stop the algorithm (and
return (-1, -1)) if we don't have a correct
upperbound on the determinant. Note that this
doesn't necesseraly mean that no solutions
will be found since the theoretical upperbound is
usualy far away from actual results. That is why
you should probably use `strict = False`
"""
strict = False

"""
This is experimental, but has provided remarkable results
so far. It tries to reduce the lattice as much as it can
while keeping its efficiency. I see no reason not to use
this option, but if things don't work, you should try
disabling it
"""
helpful_only = True
dimension_min = 7  # stop removing if lattice reaches that dimension

############################################
# Functions
##########################################

# display stats on helpful vectors
def helpful_vectors(BB, modulus):
    nothelpful = 0
    for ii in range(BB.dimensions()[0]):
        if BB[ii, ii] >= modulus:
            nothelpful += 1

    print(nothelpful, "/", BB.dimensions()[0], " vectors are not helpful")

# display matrix picture with 0 and X
def matrix_overview(BB, bound):
    for ii in range(BB.dimensions()[0]):
        a = ('%02d ' % ii)
        for jj in range(BB.dimensions()[1]):
            a += '0' if BB[ii, jj] == 0 else 'X'
            if BB.dimensions()[0] < 60:
                a += ' '
        if BB[ii, ii] >= bound:
            a += '~'
        print(a)

# tries to remove unhelpful vectors
# we start at current = n-1 (last vector)
def remove_unhelpful(BB, monomials, bound, current):
    # end of our recursive function
    if current == -1 or BB.dimensions()[0] <= dimension_min:
        return BB

    # we start by checking from the end
    for ii in range(current, -1, -1):
        # if it is unhelpful:
        if BB[ii, ii] >= bound:
            affected_vectors = 0
            affected_vector_index = 0
            # let's check if it affects other vectors
            for jj in range(ii + 1, BB.dimensions()[0]):
                # if another vector is affected:
                # we increase the count
                if BB[jj, ii] != 0:
                    affected_vectors += 1
                    affected_vector_index = jj

            # level:0
            # if no other vectors end up affected
            # we remove it
            if affected_vectors == 0:
                # print("* removing unhelpful vector", ii)
                BB = BB.delete_columns([ii])
                BB = BB.delete_rows([ii])
                monomials.pop(ii)
                BB = remove_unhelpful(BB, monomials, bound, ii - 1)
                return BB

            # level:1
            # if just one was affected we check
            # if it is affecting someone else
            elif affected_vectors == 1:
                affected_deeper = True
                for kk in range(affected_vector_index + 1, BB.dimensions()[0]):
                    # if it is affecting even one vector
                    # we give up on this one
                    if BB[kk, affected_vector_index] != 0:
                        affected_deeper = False
                # remove both it if no other vector was affected and
                # this helpful vector is not helpful enough
                # compared to our unhelpful one
                if affected_deeper and abs(bound - BB[affected_vector_index, affected_vector_index]) < abs(
                        bound - BB[ii, ii]):
                    # print("* removing unhelpful vectors", ii, "and", affected_vector_index)
                    BB = BB.delete_columns([affected_vector_index, ii])
                    BB = BB.delete_rows([affected_vector_index, ii])
                    monomials.pop(affected_vector_index)
                    monomials.pop(ii)
                    BB = remove_unhelpful(BB, monomials, bound, ii - 1)
                    return BB
    # nothing happened
    return BB

""" 
Returns:
* 0,0   if it fails
* -1,-1 if `strict=true`, and determinant doesn't bound
* x0,y0 the solutions of `pol`
"""

def boneh_durfee(pol, modulus, mm, tt, XX, YY):
    """
    Boneh and Durfee revisited by Herrmann and May

    finds a solution if:
    * d < N^delta
    * |x| < e^delta
    * |y| < e^0.5
    whenever delta < 1 - sqrt(2)/2 ~ 0.292
    """

    # substitution (Herrman and May)
    PR.<u,x,y> = PolynomialRing(ZZ)
    Q = PR.quotient(x * y + 1 - u)  # u = xy + 1
    polZ = Q(pol).lift()

    UU = XX * YY + 1

    # x-shifts
    gg = []
    for kk in range(mm + 1):
        for ii in range(mm - kk + 1):
            xshift = x ^ ii * modulus ^ (mm - kk) * polZ(u, x, y) ^ kk
            gg.append(xshift)
    gg.sort()

    # x-shifts list of monomials
    monomials = []
    for polynomial in gg:
        for monomial in polynomial.monomials():
            if monomial not in monomials:
                monomials.append(monomial)
    monomials.sort()

    # y-shifts (selected by Herrman and May)
    for jj in range(1, tt + 1):
        for kk in range(floor(mm / tt) * jj, mm + 1):
            yshift = y ^ jj * polZ(u, x, y) ^ kk * modulus ^ (mm - kk)
            yshift = Q(yshift).lift()
            gg.append(yshift)  # substitution

    # y-shifts list of monomials
    for jj in range(1, tt + 1):
        for kk in range(floor(mm / tt) * jj, mm + 1):
            monomials.append(u ^ kk * y ^ jj)

    # construct lattice B
    nn = len(monomials)
    BB = Matrix(ZZ, nn)
    for ii in range(nn):
        BB[ii, 0] = gg[ii](0, 0, 0)
        for jj in range(1, ii + 1):
            if monomials[jj] in gg[ii].monomials():
                BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](UU, XX, YY)

    # Prototype to reduce the lattice
    if helpful_only:
        # automatically remove
        BB = remove_unhelpful(BB, monomials, modulus ^ mm, nn - 1)
        # reset dimension
        nn = BB.dimensions()[0]
        if nn == 0:
            print("failure")
            return 0, 0

    # check if vectors are helpful
    if debug:
        helpful_vectors(BB, modulus ^ mm)

    # check if determinant is correctly bounded
    det = BB.det()
    bound = modulus ^ (mm * nn)
    if det >= bound:
        # print("We do not have det < bound. Solutions might not be found.")
        # print("Try with highers m and t.")
        if debug:
            diff = (log(det) - log(bound)) / log(2)
            # print("size det(L) - size e^(m*n) = ", floor(diff))
        if strict:
            return -1, -1
    else:
        print("det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)")

    # display the lattice basis
    if debug:
        matrix_overview(BB, modulus ^ mm)

    # LLL
    if debug:
        print("optimizing basis of the lattice via LLL, this can take a long time")

    BB = BB.LLL()

    if debug:
        print("LLL is done!")

    # transform vector i & j -> polynomials 1 & 2
    if debug:
        print("looking for independent vectors in the lattice")
    found_polynomials = False

    for pol1_idx in range(nn - 1):
        for pol2_idx in range(pol1_idx + 1, nn):
            # for i and j, create the two polynomials
            PR.<w,z> = PolynomialRing(ZZ)
            pol1 = pol2 = 0
            for jj in range(nn):
                pol1 += monomials[jj](w * z + 1, w, z) * BB[pol1_idx, jj] / monomials[jj](UU, XX, YY)
                pol2 += monomials[jj](w * z + 1, w, z) * BB[pol2_idx, jj] / monomials[jj](UU, XX, YY)

            # resultant
            PR.<q> = PolynomialRing(ZZ)
            rr = pol1.resultant(pol2)

            # are these good polynomials?
            if rr.is_zero() or rr.monomials() == [1]:
                continue
            else:
                # print("found them, using vectors", pol1_idx, "and", pol2_idx)
                found_polynomials = True
                break
        if found_polynomials:
            break

    if not found_polynomials:
        # print("no independant vectors could be found. This should very rarely happen...")
        return 0, 0

    rr = rr(q, q)

    # solutions
    soly = rr.roots()

    if len(soly) == 0:
        # print("Your prediction (delta) is too small")
        return 0, 0

    soly = soly[0][0]
    ss = pol1(q, soly)
    solx = ss.roots()[0][0]

    #
    return solx, soly

delta = .271  # this means that d < N^delta
m = 8  # size of the lattice (bigger the better/slower)
t = int((1 - 2 * delta) * m)  # optimization from Herrmann and May
X = 2 * floor(N ^ delta)  # this _might_ be too much
Y = floor(N ^ (1 / 2))  # correct if p, q are ~ same size
P.<x,y> = PolynomialRing(ZZ)
A = int((N + 1) / 2)
pol = 1 + x * (A + y)

solx, soly = boneh_durfee(pol, e, m, t, X, Y)

d = int(pol(solx, soly) / e)
print(d)

m = power_mod(c, d, N)

print(bytes.fromhex(hex(m)[2:]))

'''
det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)
76516802127572529241860569119773645337201291188788443592272413818606050201799
b'flag{Y0u_kNoW_C0n7lNu3d_Fr4c71on!}'
'''

连分数也行这里做了个小优化

from Crypto.Util.number import *
from fractions import Fraction


N = int(0x662854e5ee8b1aa73eea7c897f0f1bd7cace486dea68fb4e9b1affe86ddae225221e9941b7e90b7dd87d57988fc3428f51433a5c2a6e7ef9cbe85aace0925914347ca1d403ea58e2f36435b67648f8caf0abd29c9c24d3caeadab2c41522deda75c19584ec917fa683ff16c932f334db3145a8367c3dc6bc3b918ff3f69f8bfb16c45b4caab1e8ecef24e8e923e984e921115d9fb997a638c8e25d74d592f279359e7147745a7a8443603287120d1a186f30d5a41ce26545f85844721b788564e306791ae39c3be23aeeab010e79302afab4b3e9ab18cb2769382ff8fcbc0514f51861ec6db247f0a0343b7cc6d44299878f7006c118df10de6937c11e3aed7d)
e = int(0x58a2680eae331e41397475dd699a75f242897e4ed4048338137eb40100cc406b651c4518f4057ad8419cd6a82605113dd5801cd9f022f8bda424b02db5feb333d96636026c3ffc4cab74f7426aa14fb1139663a4f6248dd8e5c7075fcdf3e520c425697775cfb65d33ccca5ffe08d944753b1e9da2dbf96713ece5436deb6dbc843dcd5c497eda9919e055a32c76798770535c6a91ae00b971f35be1ab9e48dd4c701026e0744826001f6fb30e4f68d6e4981aa5a5bbcc995a9e46a4d9b1658348d0fb3b1314fa091251ea1b7379a854a3860fcba2ace323dca8157008d80d6035fd6c880404495f933bf4b4ae829b35823450a921f64b9cf63ae861b3fc4ef7)
c = int(0x47d2e297294af43a9a02d465f7f5272cab0af2445cbc6022def1098e075dcfb3a7830f09df6112a9fa55b34ed4d0baebad54ea2cbd32e4367cbe7a138409a0ef4c36d837ea7817ec3624fca3a19c1377eaf08e4a519de73cb2c5e99ec8f3998e04d4c3bc44a6f1eb389111bf7c72c68bf1dd743e656467d1ecdd314b37313963758634b83ea96724b1872367a922788f2c8a046c76ccc57e86686bedd7ac431f92b9e2f1fae79701fa0d14d2a0119860c8908336c6caec87b9733f626166373631e1e7e9ba6be92d712e84e821e0e4dc105d460c6640498aefaeb5146d0f57b8e57c3e24bc13f3e79082172c1690428eb49bc6035f1e60f6a579129a2da00c60)


def wienerAttack(N, e, c):
    res = []
    rres = []
    cf = continued_fraction(Integer(e) / Integer(N))
    convers = cf.convergents()
    for pkds in convers:
        pk, pds = pkds.as_integer_ratio()
        if pk == 0 or pds == 0 or pds == 1:
            continue
        if (e * pds - 1) % pk != 0:
            continue
        print(pds)
        m = pow(c,pds,N)
        mes = long_to_bytes(m)
        if mes.endswith(b"}"):
            print(pds.bit_length())
            return mes, pds, pk


res = wienerAttack(N,e,c)
assert res
mes,d,k = res
print(mes)
'''
76516802127572529241860569119773645337201291188788443592272413818606050201799
256
b'flag{Y0u_kNoW_C0n7lNu3d_Fr4c71on!}'
'''

LWECC#

Easy ECC…and LWE maybe

from Crypto.Util.number import *
from Crypto.Cipher import AES
from random import choice
from hashlib import md5
from secret import flag

p = 1096126227998177188652856107362412783873814431647
E = EllipticCurve(GF(p), [0, 5])

s = [E.random_element() for _ in range(73)]
e = [E.random_element() for _ in "01"]
A = random_matrix(GF(p), 137, 73)
b = [(sum(i*j for i,j in zip(_,s)) + choice(e)).xy() for _ in A]


print("A =", A.list())
print("b =", b)
print("enc =", AES.new(key=md5(str(s).encode()).digest(), nonce=b"LWECC", mode=AES.MODE_CTR).encrypt(flag))

plaintext

给定椭圆曲线 $E$ 给随机向量 $s_{73\times1}$ ，二点分布 $e_{2\times1}$ 随机矩阵 $A_{137\times73}$

去计算

b_{137\times1}=A_{137\times73}\times s_{73\times1}+e_{137\times1}

这里给我们的椭圆曲线的阶满足

E.order()==p

所以说曲线上的阶乘可以非常轻松的通过Smart-Attack转换为点加来解决，我们重点关心这个sample-LWE问题

经过一番Osint HITCON2025BabyLWE和这个很像贴一下repo ↗

从WMCTF2025做过来我们的LWE经历了 $e$ 很小， $e$ 不小但是已知抽样来源， $e$ 不小而且不知道抽样来源

对于LWE问题

b=A\times s+e

我们知道如果 $e$ 不是很小,可以通过格基归约找到一组存在线性关系的小 $e_0$ ,即

e_0=e\times m+n

通过格子不难找到 $m\;n$

此时对方程进行一个处理得到

b\times m+n=m\cdot A\times s+e_0

也就是

B=(mA)\times s+e_0

再考虑primal-attack的优化等等

那如果我们不知道 $e$ 就没法了吗

我们看优化后的式子能得到

e_0\equiv(b\times m+n)-(mA)\times s

方便起见我们设

x\equiv-ms

得到

e_0\equiv m\cdot b+n\cdot 1+ A\times x

为了方便我们分析我们给矩阵转置

\boldsymbol{e_0^T}=\boldsymbol{x^T}\boldsymbol{A}+m\boldsymbol{b^T}+n\boldsymbol{I}+p\boldsymbol{k}

可以构造算式

\begin{pmatrix}\boldsymbol{x^T}&m&n&\boldsymbol{k}\end{pmatrix}_{1\times212}\times\begin{pmatrix}\boldsymbol{A^T}\\\boldsymbol{b^T}\\\boldsymbol{1}\\p\boldsymbol{I}\end{pmatrix}_{212\times137}=\begin{pmatrix}\boldsymbol{e_0^T}\end{pmatrix}_{1\times137}

令

\begin{pmatrix}\boldsymbol{A^T}\\\boldsymbol{b^T}\\\boldsymbol{1}\\p\boldsymbol{I}\end{pmatrix}_{212\times137}=\boldsymbol{M}

你对 $\boldsymbol{M}$ 做规约可以在前面几行找到小的向量分布那不就找出了 $\boldsymbol{e_0^T}$ 吗

但是我们还要想一个办法来还原回去这里有一个非常巧妙的手法注意我们矩阵算法本质是线性组合我们如果给 $\boldsymbol{M}$ 补充成增广矩阵也就是

\boldsymbol{L}=[c\times\boldsymbol{I}_{212\times212}\;\;|\;\;\boldsymbol{M}_{212\times137}]_{212\times349}

我们对 $L$ 进行规约可以得到

\begin{pmatrix}c\boldsymbol{x^T}&cm&cn&c\boldsymbol{k}&\boldsymbol{e_0^T}\end{pmatrix}_{1\times319}

不就直接给 $m\;n$ 做出来了吗？随后还原我们的 $\boldsymbol{e}\equiv m^{-1}(\boldsymbol{e_0}-\boldsymbol{n})$

求出 $e$ 直接得到 $As=b-e$ 解方程得到我们的 $s$ 拿下

呃呃，但是还缺一些优化而且这个实际上也就是primal-attack的思路先用鸡块师傅的板子 ↗给求下

exp

from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import md5

A = 
b = 
enc = 
p = 
E = EllipticCurve(GF(p), [0, 5])
m = 137
n = 73
nums = 137

# convert
def _find_smart_log_func(E, prec=30):
    p = E.base_ring().order()
    Q = Qp(p, prec)
    base_invs = [ZZ(x) for x in E.a_invariants()]

    for diff in [p, 2 * p, 3 * p]:
        invs = list(base_invs)
        invs[3] += diff
        try:
            Eq = EllipticCurve(Q, invs)
        except Exception:
            continue

        def log_candidate(P):
            if P == E(0):
                return 0
            x_P = ZZ(P.xy()[0])
            y_P = ZZ(P.xy()[1])
            try:
                P_lift = Eq.lift_x(x_P, all=True)[0]
            except Exception:
                return None
            if (P_lift.xy()[1] - y_P).valuation() < 1:
                P_lift = -P_lift
            R = p * P_lift
            if R == Eq(0):
                return None
            x_R, y_R = R.xy()
            val = -x_R / y_R
            v = val.valuation()
            if v < 1:
                return None
            if v >= 2:
                res = val / p**2
            else:
                res = val / p
            return GF(p)(res.residue())

        P1 = E.random_element()
        P2 = E.random_element()
        P3 = P1 + P2
        l1 = log_candidate(P1)
        l2 = log_candidate(P2)
        l3 = log_candidate(P3)
        if l1 is None or l2 is None or l3 is None:
            continue
        if l1 == 0 and l2 == 0:
            continue
        if (l1 + l2 - l3) == 0:
            return log_candidate

    raise Exception("Could not find working Smart Log map")

_SMART_LOG = _find_smart_log_func(E)

def to_scalar(P):
    if isinstance(P, (tuple, list)):
        P = E(P)
    v = _SMART_LOG(P)
    if v is None:
        raise ValueError("Smart log failed for this point")
    return int(v)

def from_scalar(k, G):
    g = to_scalar(G)
    if g == 0:
        raise ValueError("to_scalar(G)=0; choose a different generator G")
    return (k * inverse_mod(g, p)) * G


b = vector(GF(p), [to_scalar(P) for P in b])
A = matrix(GF(p), 137, 73, A)

P_tmp = E.random_element()
while P_tmp == E(0): P_tmp = E.random_element()
G = inverse_mod(to_scalar(P_tmp), p) * P_tmp


def primal_attack2(A,b,m,n,p):
    L = block_matrix(
        [
            [(matrix(Zmod(p), A).T).echelon_form().change_ring(ZZ), 0],
            [matrix.zero(m - n, n).augment(matrix.identity(m - n) * p), 0],
            [matrix(ZZ, b).stack(vector(ZZ, [1]*nums)), 1],
        ]
    )
    Q = diagonal_matrix(ZZ, [p]*m + [1]*2)
    L = L*Q
    L = flatter(L)
    L = L/Q
    L = Matrix(ZZ, L)
    res = vector(Zmod(p), L[2])
    e, k, t = res[:-2], res[-2], res[-1]
    return (e-vector(ZZ, [t]*nums))*inverse(k,p)



e2 = primal_attack2(A, b, nums, n, p)
# print(e2)
s = A[:nums].solve_right(b[:nums]-e2[:nums])
# print(s)

assert b == A*s + e2

s_points = [from_scalar(int(k), G) for k in s]
key = md5(str(s_points).encode()).digest()
plain = AES.new(key=key, nonce=b"LWECC", mode=AES.MODE_CTR).decrypt(enc)
print(plain)
# b'flag{9fa22070eb9ddfe4085c432f04019b}'

至此复现结束