Lord Riot's Blog
0%

摸鱼Writeup-2

发表于 更新于 分类于
Ant x D3CTF

Ant x D3CTF

BabyLattice

考虑r很小，有\(b m + r= c + k n\)，故构造格

\[\begin{bmatrix} n & 0 & 0 \\ b & 1 & 0 \\ c & 0 & X\end{bmatrix}\]

X为放缩因子，目标向量为\((k, m, 1)\)时，通过格映射为向量\((r, m, X)\)，调整X大小为\(2^{300}\)，可成功规约出目标向量，exp如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from hashlib import sha256

n = 69804507328197961654128697510310109608046244030437362639637009184945533884294737870524186521509776189989451383438084507903660182212556466321058025788319193059894825570785105388123718921480698851551024108844782091117408753782599961943040695892323702361910107399806150571836786642746371968124465646209366215361
b = 65473938578022920848984901484624361251869406821863616908777213906525858437236185832214198627510663632409869363143982594947164139220013904654196960829350642413348771918422220404777505345053202159200378935309593802916875681436442734667249049535670986673774487031873808527230023029662915806344014429627710399196
c = 64666354938466194052720591810783769030566504653409465121173331362654665231573809234913985758725048071311571549777481776826624728742086174609897160897118750243192791021577348181130302572185911750797457793921069473730039225991755755340927506766395262125949939309337338656431876690470938261261164556850871338570

X = 2**300
M = Matrix(ZZ, [[n, 0, 0], [b, 1, 0], [c, 0, X]])

ML = M.LLL()

r = int(ML[0][0])
m = int(abs(ML[0][1]))
assert (b * m + r) % n == c

print('d3ctf{%s}' % sha256(int(m).to_bytes(50, 'big')).hexdigest())
SimpleGroup

需要用到第一题中有关n，b的关系式，

\(b * a11 - a12 \equiv 0 \mod p\)

\(b * a21 - a22 \equiv 0 \mod q\)

考虑到a11，a12，a21，a22都很小，可以使用格基规约，但p，q未知（这里我一开始想直接二元Copper，但发现好像bound不太够，懒得想复杂的多项式构造了），考虑将两个式子相乘，展开得到

\[a11 * a21 * b^2 -(a11*a22 + a21*a12) *b + a12 * a22 = k * n\]

构造格如下：

\[\begin{bmatrix} n & 0 & 0 \\ b & 1 & 0 \\ b^2 & 0 & 1\end{bmatrix}\]

这里由于a11，a12，a21，a22都非常小，不需要平衡因子，目标向量\((k, a11*a22 + a21*a12, -a11 * a21)\)，通过格映射，得到向量\((a12 * a22, a11*a22 + a21*a12, -a12 * a22)\)，之后联立方程，即可解除a11，a12，a21，a22，然后即可分解n。

又考虑到$e = e_1 * e_2, e_1 = 36493 ,e_2= 52859 $

对于\(m_i\)， 有\(c_i \equiv y^{m_i} r_i^{e} \mod n,\quad m \equiv m_1 \mod e_1, \quad m \equiv m_2 \mod e_2\)

\(\Rightarrow c_1 \equiv y^{m_1} (y^{k_1} r^{e_2})^{e_1} \mod n, \quad c_2 \equiv y^{m_1} (y^{k_2} r^{e_1})^{e_2} \mod n\)

可以看到由于y已知，\(e_1, e_2\) 位数均很小，可以通过分别爆破\(m_1, m_2\)（利用\(c_1 y^{-m_1}, c_2 y^{-m_2}\) 在\(GF(n)\) 上是否是\(e_1, e_2\) 次数剩余来判断），之后CRT即可恢复\(m_i\)，完整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
from Crypto.Util.number import *
from tqdm import tqdm


def check(s, t, _phi):
    if _phi % t != 0:
        return False
    return pow(s, _phi//t, n) == 1


n = 69804507328197961654128697510310109608046244030437362639637009184945533884294737870524186521509776189989451383438084507903660182212556466321058025788319193059894825570785105388123718921480698851551024108844782091117408753782599961943040695892323702361910107399806150571836786642746371968124465646209366215361
b = 65473938578022920848984901484624361251869406821863616908777213906525858437236185832214198627510663632409869363143982594947164139220013904654196960829350642413348771918422220404777505345053202159200378935309593802916875681436442734667249049535670986673774487031873808527230023029662915806344014429627710399196
y = 12064801545723347322936991186738560311049061235541031580807549422258814170771738262264930441670708308259694588963224372530498305648578520552038029773849342206125074212912788823834152785756697757209804475031974445963691941515756901268376267360542656449669715367587909233618109269372332127072063171947435639328
e = 1928983487
C = [63173987757788284988620600191109581820396865828379773315280703314093571300861961873159324234626635582246705378908610341772657840682572386153960342976445563045427986000105931341168525422286612417662391801508953619857648844420751306271090777865836201978470895906780036112804110135446130976275516908136806153488, 9763526786754236516067080717710975805995955013877681492195771779269768465872108434027813610978940562101906769209984501196515248675767910499405415921162131390513502065270491854965819776080041506584540996447044249409209699608342257964093713589580983775580171905489797513718769578177025063630080394722500351718, 37602000735227732258462226884765737048138920479521815995321941033382094711120810035265327876995207117707635304728511052367297062940325564085193593024741832905771507189762521426736369667607865137900432117426385504101413622851293642219573920971637080154905579082646915297543490131171875075081464735374022745371, 1072671768043618032698040622345664216689606325179075270470875647188092538287671951027561894188700732117175202207361845034630743422559130952899064461493359903596018309221581071025635286144053941851624510600383725195476917014535032481197737938329722082022363122585603600777143850326268988298415885565240343957, 27796821408982345007197248748277202310092789604135169328103109167649193262824176309353412519763498156841477483757818317945381469765077400076181689745139555466187324921460327576193198145058918081061285618767976454153221256648341316332169223400180283361166887912012807743326710962143011946929516083281306203120, 27578857139265869760149251280906035333246393024444009493717159606257881466594628022512140403127178174789296810502616834123420723261733024810610501421455454191654733275226507268803879479462533730695515454997186867769363797096196096976825300792616487723840475500246639213793315097434400920355043141319680299224, 29771574667682104634602808909981269404867338382394257360936831559517858873826664867201410081659799334286847985842898792091629138292008512383903137248343194156307703071975381090326280520578349920827357328925184297610245746674712939135025013001878893129144027068837197196517160934998930493581708256039240833145, 33576194603243117173665354646070700520263517823066685882273435337247665798346350495639466826097821472152582124503891668755684596123245873216775681469053052037610568862670212856073776960384038120245095140019195900547005026888186973915360493993404372991791346105083429461661784366706770467146420310246467262823, 5843375768465467361166168452576092245582688894123491517095586796557653258335684018047406320846455642101431751502161722135934408574660609773328141061123577914919960794180555848119813522996120885320995386856042271846703291295871836092712205058173403525430851695443361660808933971009396237274706384697230238104, 61258574367240969784057122450219123953816453759807167817741267194076389100252707986788076240792732730306129067314036402554937862139293741371969020708475839483175856346263848768229357814022084723576192520349994310793246498385086373753553311071932502861084141758640546428958475211765697766922596613007928849964, 13558124437758868592198924133563305430225927636261069774349770018130041045454468021737709434182703704611453555980636131119350668691330635012675418568518296882257236341035371057355328669188453984172750580977924222375208440790994249194313841200024395796760938258751149376135149958855550611392962977597279393428]

e1 = 36493
e2 = e//e1

X = 1
M = Matrix(ZZ, [[n, 0, 0], [b, X, 0], [b ^ 2, 0, X]])
ML = M.LLL()

# a = a11 * a21, b = a11*a22 + a21*a12, c = a12 * a22
'''
a = 211380743487233628797755584958526337321408979158793229985661
b = 1382843159437215516163973075066558157591473749635266665605630
c = 1173142580751247504024100371706709782500216511824162516724129

a11, a21, a12, a22 = var('a11, a21, a12, a22')
solve([a == a11 * a21, b == a11*a22 + a21*a12, c == a12 * a22], a11, a21, a12, a22)
'''


a11 = 1018979931854255696816714991181
a12 = 1017199123798810531137951821909

p = gcd(b * a11 - a12, n)
q = n//p
assert n == p * q

M = []
phi = (p-1)*(q-1)
for i in tqdm(range(len(C))):
    for m in range(1, e1+1):
        tmp = (C[i] * inverse(int(pow(y, m, n)), n)) % n
        if check(tmp, e1, phi):
            m1 = m
            break
    for m in range(1, e2+1):
        tmp = (C[i] * inverse(int(pow(y, m, n)), n)) % n
        if check(tmp, e2, phi):
            m2 = m
            break
    tmp_m = CRT([m1, m2], [e1, e2])
    M.append(tmp_m)

print('M:', M)
flag = 0
for i in range(len(M)):
    flag += M[i] * (e**i)

print(long_to_bytes(flag))
EasyCurve

这一题有个很大的非预期，就是由于x，y坐标给的较小，可以完全通过hackergame2020中OT的方法来获得完整的一对\(x, y\)，由于p-1非常光滑，可以直接在其曲线上使用Pohlig Hellman算法来得到e，从而得到flag。

这里谈下预期解法，是通过一个映射来讲曲线的点映射到GF上，然后构造OT，再在GF上使用Pohlig Hellman求解的，具体得到这个映射的方法很多，我这里讲一种比较简单的求通项得到的方法。

稍作分析可以发现题给曲线其实是一个\(GF(p)\) 上的pell方程，即\(x^2 \equiv Dy^2 + u^2\)，而pell方程的解可以通过以下方法得到（这里的\(x_n\) 即对应\((nG)x\)，即n倍点的坐标）

对矩阵\(\begin{bmatrix} x_1 & Dy_1 \\ y_1 & x_1\end{bmatrix}\)，进行对角化，可以得到其特征值为$ D y + x, -D y + x$，之后求得 \[ x_n = \frac{(y_1\sqrt D + x_1)^n + (-y_1\sqrt D + x_1)^n}{2 u^{n-1}} \]

\[ y_n = \frac{(y_1\sqrt D + x_1)^n - (-y_1\sqrt D + x_1)^n}{2 \sqrt Du^{n-1}} \]

容易得到 \[ \frac{x_n - \sqrt D y_n}{ u} = (\frac{x1 - \sqrt D y1}{u}) ^ n \]

\[ \frac{x_n + \sqrt D y_n}{ u} = (\frac{x1 + \sqrt D y1}{u}) ^ n \]

即找到了两个将曲线上点映射到GF的映射 \[ f: f(x, y) = \frac{x - \sqrt D y}{ u} \]

\[ g: g(x, y) = \frac{x + \sqrt D y}{ u} \]

此时，利用hackergame2020的OT中的技巧，且D已知，对于每一个点，可以得到\(x - \sqrt D y\)，得到两组数据后相除，即可得到 \[ \frac{x_{1n} + \sqrt D y_{1n}}{ x_{2n} + \sqrt D y_{2n}} = (\frac{x1 + \sqrt D y1}{x_1 + \sqrt D y_2}) ^ n \] 对这两个数通过Pohlig Hellman算法求DLP，即可得到e，从而得到flag，完整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
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
from winpwn import *
from Crypto.Util.number import *
from math import sqrt, ceil
from factordb.factordb import FactorDB
from gmpy2 import jacobi
from sympy import nthroot_mod
from hashlib import sha256
from string import digits, ascii_letters
import os

charset = digits + ascii_letters
p = 9688074905643914060390149833064012354277254244638141162997888145741631958242340092013958501673928921327767591959476890238698855704376126231923819603296257


def get_factor_list(n):
    factor = FactorDB(n)
    factor.connect()
    return list(factor.get_factor_list())


def get_factor_list_with_exponent(n, factor_list=None):
    if not factor_list:
        factor = FactorDB(n)
        factor.connect()
        factor_list = list(factor.get_factor_list())
    factor_list_with_exponent = {}
    for factor in factor_list:
        if factor not in factor_list_with_exponent.keys():
            factor_list_with_exponent[factor] = 1
        else:
            factor_list_with_exponent[factor] += 1
    return factor_list_with_exponent


def bsgs(g, y, p, upper_bound=None):
    res = []
    if not upper_bound:
        upper_bound = p - 1
    m = int(ceil(sqrt(upper_bound)))
    S = {pow(g, j, p): j for j in range(m+1)}
    gs = pow(g, (-m) % (p-1), p)
    for i in range(m+1):
        if y in S:
            return i * m + S[y]
        y = (y * gs) % p
    return None


def GCRT(mi, ai):
    assert (isinstance(mi, list) and isinstance(ai, list))
    curm, cura = mi[0], ai[0]
    for (m, a) in zip(mi[1:], ai[1:]):
        d = int(GCD(curm, m))
        c = a - cura
        assert (c % d == 0)
        K = c // d * inverse(curm // d, m // d)
        cura += curm * K
        curm = curm * m // d
        cura %= curm
    return cura % curm, curm


def get_n_order(g, p, phi=None, factor_list=None):
    if not phi:
        phi = p-1
    if not factor_list:
        factor_list = get_factor_list(phi)
    ord = phi
    new_factor_list = factor_list
    for factor in factor_list:
        if pow(g, ord//factor, p) == 1:
            ord //= factor
            new_factor_list.remove(factor)
    return ord, get_factor_list_with_exponent(p, new_factor_list)


def pohlig_hellman(g, y, p, ord=None, factor_list=None):
    if not ord:
        ord, factor_list = get_n_order(g, p, factor_list=factor_list)
    else:
        factor_list = get_factor_list_with_exponent(ord)
    prime_order_mod = [0] * len(factor_list)
    for i, factor in enumerate(factor_list.keys()):
        tmp_g = pow(g, ord//factor, p)
        for j in range(factor_list[factor]):
            tmp_y = (y * inverse(pow(g, prime_order_mod[i], p), p)) % p
            tmp_y = pow(tmp_y, ord//(factor**(j+1)), p)
            pmod = bsgs(tmp_g, tmp_y, p, factor**(j+1))
            prime_order_mod[i] += pmod * (factor**j)
    return GCRT([factor**factor_list[factor] for factor in factor_list.keys()], prime_order_mod)[0]


def proof_of_work(end, judge):
    for a in tqdm(charset):
        for b in charset:
            for c in charset:
                for d in charset:
                    tmp = a + b + c + d
                    if sha256((tmp + end).encode()).hexdigest() == judge:
                        return tmp


def get_x_y(s):
    io.recvuntil('n = ')
    n = int(io.recvuntil('\n').strip())
    io.recvuntil('e = ')
    e = int(io.recvuntil('\n').strip())
    io.recvuntil('x0 = ')
    x0 = int(io.recvuntil('\n').strip())
    io.recvuntil('x1 = ')
    x1 = int(io.recvuntil('\n').strip())
    io.recvuntil('v = ')

    v = pow(-s, e, n) * x1 - x0
    v = (v * inverse(pow(-s, e, n) - 1, n)) % n
    io.sendline(str(v))

    io.recvuntil('m0_ = ')
    m0 = int(io.recvuntil('\n').strip())
    io.recvuntil('m1_ = ')
    m1 = int(io.recvuntil('\n').strip())

    return (m0 + m1 * s) % n


while True:
    # io = remote('47.100.50.252', 10000)
    io = remote('127.0.0.1', 10015)
    '''io.recvuntil('sha256(XXXX+')
    have = io.recv(16)
    io.recvuntil('== ')
    ans = io.recv(64)
    io.recvuntil('Give me XXXX:')
    io.sendline(proof_of_work(have, ans))'''

    io.recvuntil('D = ')
    D = int(io.recvuntil('\n').strip())
    if jacobi(D, p) == 1:
        break
    io.close()
a = nthroot_mod(D, 2, p)

Gx = []
kGx = []
for i in range(2):
    Gx.append(get_x_y(a))
    kGx.append(get_x_y(a))
    io.recvuntil('do you know my e?')
    io.sendline(str(0))
    print(io.recvuntil('\n'))

get_x_y(0)
get_x_y(0)
io.recvuntil('do you know my e?')

g = (Gx[0] * inverse(Gx[1], p)) % p
y = (kGx[0] * inverse(kGx[1], p)) % p
print('g =', g)
print('y =', y)

guess = pohlig_hellman(g, y, p)
assert pow(g, guess, p) == y

print('guess =', guess)
io.sendline(str(guess))
print(io.recvuntil('\n'))
io.interactive()