Misay's blog

HKCERT2025Quals

发表于 分类于
本文字数： 52k
HKCERT2025Quals-Crypto-复现

赛题Repo

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

Bivariate copper

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

chall.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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
'''

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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!'

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

我们已知，是244bits内的小量 结合题干不难想到二元Copper 我们给消去 不难得到 做差就可以得到一个含两个变元的小根方程 都是244bits以内 而为1024bits的 ，存在,可解

打一发二元Copper

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
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问题

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

exp.sage

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
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}'

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

我们来从出题人的视角看看这些是怎么生成的

首先随机生成两个512位的素数

在四元数系统下一定有群的阶满足

生成一个数 计算

随后保证连分数的命中性质 要有 整理得到 本题实际做到的是 随后根据

生成这个大的诡异的

主要是确实验证了

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

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

cruel-rsa

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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 给出了的泄露

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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

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

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

然后利用的位数以及合数关系 可以筛选出我们的加上已知 我们可以求出

求出再求出 结果因为这里的是在模下生成 但是 所以说你求出了也是没法解密的，，，

但是可以打CRT直接解方程，毕竟有的分解 那么我们求意义何在，，，

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
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!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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相当于计算 所以说我们接下来分析这个椭圆曲线群的性质,尝试由已知的点加 倍乘 3个曲线上的点来去恢复曲线方程

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

把曲线设成 的广义形式（或者还可以更复杂） 然后利用have和fun以及基点做出一系列点来 进行插值求出系数

然后去往我们的标准形式去做变换 进行简单的逆元乘法即可 这里因为我们直接设的就是广义形式 所以说简单的代数变换就可以 当然也可以考虑2024羊城杯的手法，先

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

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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
'''

利用式子 展开 我们注意到 而的大小不会超过 爆搜就行

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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?

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

依旧板子 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288

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!}'
'''

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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))

给定椭圆曲线 给随机向量，二点分布 随机矩阵

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

1
E.order()==p

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

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

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

对于LWE问题 我们知道如果不是很小,可以通过格基归约 找到一组存在线性关系的小,即 通过格子不难找到

此时对方程进行一个处理 得到 也就是 再考虑primal-attack的优化等等

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

我们看优化后的式子 能得到 方便起见 我们设 得到 为了方便我们分析我们给矩阵转置 可以构造算式 令 你对做规约 可以在前面几行找到小的向量分布 那不就找出了吗

但是我们还要想一个办法来还原回去 这里有一个非常巧妙的手法 注意我们矩阵算法本质是线性组合 我们如果给补充成增广矩阵 也就是 我们对进行规约 可以得到 不就直接给做出来了吗？随后还原我们的

求出 直接得到 解方程得到我们的 拿下

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

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
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}'

至此 复现结束