糖醋小鸡块的blog
0%

2024-高校密码挑战赛赛题一-wp-crypto

发表于 更新于 分类于 Valine：

和@yolbby、@三顺七组队参加了这次挑战赛，最后只拿了三等奖，因为确实是完全当CTF在打——不够位数的就靠爆，没有指导老师，没有仔细考虑过时间的优化，也没有想过要搞一些创新点XD，但还是写篇博客记录一下。

第一部分——RSA特定密钥泄露攻击

1

题目数据：

1
2
3
N1=0xa4d80845630d3b332f74f667ec8a0e49aba15b6f0c4f4006161d62c91b78cf6811421cc76609d2d9dba2c43be9d8ecdc6a0dff64a8041dcde52c7f92820b0a38fc91419e8ec9a5c69d47edc6e347934b4d87f97c5759886dac6c1143ff55b8eb11acfaa6cc70956a8ec7796e1a063b123bc2e467e30937c5a69c7ab5f8ed17e1;
e1=0x3458c2e97adef45f741c7db11ece6c0814aa5b6fad9144242cdaa16a6b4f3622477935f98a41765b92892b4de22a391cf08767447df113f5151c86edd109b97f9b045fd8ad5d7a51084684d4e2353db6c0e474d5d79f399a2bf4fd867ec85b7960845ab5497f705914912f797804c06dcff57139e040596d22b141e54835e0d3;
c1=0x91b097a5b1f6b12accdbda15cd2247384e1b3ed8311085a0f3e0dbb5fffce650a355600a02674189d1b7f4075df079c70354a08646e85ecf31dd150220cd1d4ce22d55a946500f4bd8def74fb0acea3e8d2e7bb1d27ebf2ca2e80fc28c3f0d88a041d4a556a18147f66b88c65f19c99b4b94c3f78d468b8accb4da7e7ce31b29

信息：

  • d的范围在$[2^{249},2^{250}]$

显然d太小了，直接wiener或者boneh&durfee都行。

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import *

N1=0xa4d80845630d3b332f74f667ec8a0e49aba15b6f0c4f4006161d62c91b78cf6811421cc76609d2d9dba2c43be9d8ecdc6a0dff64a8041dcde52c7f92820b0a38fc91419e8ec9a5c69d47edc6e347934b4d87f97c5759886dac6c1143ff55b8eb11acfaa6cc70956a8ec7796e1a063b123bc2e467e30937c5a69c7ab5f8ed17e1
e1=0x3458c2e97adef45f741c7db11ece6c0814aa5b6fad9144242cdaa16a6b4f3622477935f98a41765b92892b4de22a391cf08767447df113f5151c86edd109b97f9b045fd8ad5d7a51084684d4e2353db6c0e474d5d79f399a2bf4fd867ec85b7960845ab5497f705914912f797804c06dcff57139e040596d22b141e54835e0d3
c1=0x91b097a5b1f6b12accdbda15cd2247384e1b3ed8311085a0f3e0dbb5fffce650a355600a02674189d1b7f4075df079c70354a08646e85ecf31dd150220cd1d4ce22d55a946500f4bd8def74fb0acea3e8d2e7bb1d27ebf2ca2e80fc28c3f0d88a041d4a556a18147f66b88c65f19c99b4b94c3f78d468b8accb4da7e7ce31b29

a = continued_fraction(e1/N1)

for i in range(len(a)):
    d,k = a.denominator(i) , a.numerator(i)
    m = pow(c1, d, N1)
    try:
        flag = long_to_bytes(m)[::-1].decode()
        print(flag)
        #print(d)
        break
    except:
        pass

#Mathematics is the queen of sciences, and arithmetic [number theory] is the queen of mathematics.



2

题目数据：

1
2
3
N2=0xd231f2c194d3971821984dec9cf1ef58d538975f189045ef8a706f6165aab4929096f61a3eb7dd8021bf3fdc41fe3b3b0e4ecc579b4b5e7e035ffcc383436c9656533949881dca67c26d0e770e4bf62a09718dbabc2b40f2938f16327e347f187485aa48b044432e82f5371c08f6e0bbde46c713859aec715e2a2ca66574f3eb;
e2=0x5b5961921a49e3089262761e89629ab6dff2da1504a0e5eba1bb7b20d63c785a013fd6d9e021c01baf1b23830954d488041b92bca2fe2c92e3373dedd7e625da11275f6f18ee4aef336d0637505545f70f805902ddbacb21bb8276d34a0f6dfe37ede87dd95bb1494dbb5763639ba3984240f1178e32aa36ee3c5fcc8115dde5;
c2=0x6a88a8fa2b8f28d96284298bab2061efeb35e3a086370e19523c15c429f5d783b9d4f32e31a402916f45ad4f2760ab30e77177335af44756bfbeef0f168b5e0dc8c3ddf75d141c358969cca0e7c2b8ab99ef8e33b031be1cbccd95b687682ac7b0dcc0d56f5651ee671d6358128d2e0801f247a6af4fe0dc5e8fb199eba0780f;

信息：

  • d的范围在$[2^{285},2^{286}]$

d虽然变大了，但还是低于boneh&durfee的理论强上界不少，所以把参数m调大到12就行。

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
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
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
from __future__ import print_function
import time
from Crypto.Util.number import long_to_bytes
from Crypto.PublicKey import RSA

############################################
# Config
##########################################

"""
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

# 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:
                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

    # 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

def example():
    ############################################
    # How To Use This Script
    ##########################################

    #
    # The problem to solve (edit the following values)
    #

    # the modulus
    N=0xd231f2c194d3971821984dec9cf1ef58d538975f189045ef8a706f6165aab4929096f61a3eb7dd8021bf3fdc41fe3b3b0e4ecc579b4b5e7e035ffcc383436c9656533949881dca67c26d0e770e4bf62a09718dbabc2b40f2938f16327e347f187485aa48b044432e82f5371c08f6e0bbde46c713859aec715e2a2ca66574f3eb;
    e=0x5b5961921a49e3089262761e89629ab6dff2da1504a0e5eba1bb7b20d63c785a013fd6d9e021c01baf1b23830954d488041b92bca2fe2c92e3373dedd7e625da11275f6f18ee4aef336d0637505545f70f805902ddbacb21bb8276d34a0f6dfe37ede87dd95bb1494dbb5763639ba3984240f1178e32aa36ee3c5fcc8115dde5;
    c=0x6a88a8fa2b8f28d96284298bab2061efeb35e3a086370e19523c15c429f5d783b9d4f32e31a402916f45ad4f2760ab30e77177335af44756bfbeef0f168b5e0dc8c3ddf75d141c358969cca0e7c2b8ab99ef8e33b031be1cbccd95b687682ac7b0dcc0d56f5651ee671d6358128d2e0801f247a6af4fe0dc5e8fb199eba0780f;

    # the hypothesis on the private exponent (the theoretical maximum is 0.292)
    delta = .278 # this means that d < N^delta

    #
    # Lattice (tweak those values)
    #

    # you should tweak this (after a first run), (e.g. increment it until a solution is found)
    m = 11 # size of the lattice (bigger the better/slower)

    # you need to be a lattice master to tweak these
    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

    #
    # Don't touch anything below
    #

    # Problem put in equation
    P.<x,y> = PolynomialRing(ZZ)
    A = int((N+1)/2)
    pol = 1 + x * (A + y)

    #
    # Find the solutions!
    #

    # Checking bounds
    if debug:
        print("=== checking values ===")
        print("* delta:", delta)
        print("* delta < 0.292", delta < 0.292)
        print("* size of e:", int(log(e)/log(2)))
        print("* size of N:", int(log(N)/log(2)))
        print("* m:", m, ", t:", t)

    # boneh_durfee
    if debug:
        print("=== running algorithm ===")
        start_time = time.time()

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

    # found a solution?
    if solx > 0:
        d = int(pol(solx, soly) / e)
        pplusq = int(soly*2)
        import gmpy2
        pminusq = gmpy2.iroot(pplusq^2-4*N,2)[0]
        p = (pplusq + pminusq) // 2
        q = N // p

        print("d =", d)
        print("p =",p)
        print("q =",q)
        assert p*q == N
        m = pow(c,d,N)
        print(long_to_bytes(int(m))[::-1])
        ##
    else:
        print("=== no solution was found ===")

    if debug:
        print(("=== %s seconds ===" % (time.time() - start_time)))

if __name__ == "__main__":
    example()


#96884485470809436429011642866838703862114673941017100586009098363273491491514356269093
#Cryptography is typically bypassed,not penetrated.



3

题目数据：

1
2
3
N3=0xf4c548636db62ffcc7ac4a0797952bea9a65bd426175af2435f72657e67ec8194667bfa94ce23c6f1e5baf3201867ab41701f6b8768e71009c41a3d5e9e7c109455341d549c7611f9f52851a2f017906aa9ccbedb95d238468e2c8577d30ecc4f158e3811fd5e2a6051443d468e3506bbc39bba710e34a604ac9e85d0feef8b3;
e3=0x16f4b438ba14e05afa944f7da9904f8c78ea52e4ca0be7fa2b5f84e22ddd7b0578a3477b19b7bb4a7f825acc45da2dd10e62dbd94a3386b97d92ee817b0c66c1507514a7860b9139bc2ac3a4e0fe304199214da00a4ca82bfcb7b18253e7e6144828e584dac2dfb9a03fabaf2376ce7c269923fbb60fc68325b9f6443e1f896f;
c3=0x26b1823cf836b226e2f5c90fdcd8420dbfcd02765b26e52ef3e5c0ab494c2f4650e475e280b0b5fff0d5016621186420b09e4706a5866e4a3319f23ef09d92c4e36acba39a0f6213fbe5ee1a736ce383e6e12351e6cbfd43f10a96b7fe34bdbaf948f2fb075d9063723c9f747fe6247ae9209e5d417faf2e37e6fee2eb863556;

信息：

  • d的范围在$[2^{299},2^{300}]$

这题d的范围增大到了boneh&durfee的理论强上界，在0.292-0.293之间，对应格的维数无穷的情况。因此在没有更优秀的shift的情况下，直接规约肯定是不可能了，因此要想办法爆破一些高位才行。

这里参考的是这篇论文爆破p高位的方法：

367.pdf (iacr.org)

经测试，m=12的情况下，有p的高19位MSB就可以稳定求解，去掉已知的最高位1的情况下还需要硬爆18位，开32进程也都还需要10天左右，太慢了。

所以就要想优化的办法，主要的思路有下面三个：

  • 参考Takayasu这篇的办法，把爆破p高位改成去爆破私钥d的MSB或者LSB：

    516.pdf (iacr.org)

    这是目前为止私钥MSB、LSB泄露的小解密指数攻击的最优结果。然而有个严峻的问题在于我的能力复现不出来这篇文章XD，感觉他的实现太复杂了。

  • 用上第二部分RNG的高位结果去得到更多p高位，这也是我们初赛的做法，速度很快。但这个方法终究是取巧，所以决赛没有再用这个。

  • 用类似剪枝的策略去把不可能存在的p高位给筛掉，这个策略也就是：

    • 如果把当前p高位后面全部填0的值记作p0，那么N除以p0得到的结果应该大于q，也就是应该大于等于512bit
    • 如果把当前p高位后面全部填1的值记作p1，那么N除以p1得到的结果应该小于q，也就是应该小于等于512bit

这个剪枝策略非常有效，可以用如下程序简单验证一下减小的复杂度：

1
2
3
4
5
6
7
8
9
10
11
12
13
N3=0xf4c548636db62ffcc7ac4a0797952bea9a65bd426175af2435f72657e67ec8194667bfa94ce23c6f1e5baf3201867ab41701f6b8768e71009c41a3d5e9e7c109455341d549c7611f9f52851a2f017906aa9ccbedb95d238468e2c8577d30ecc4f158e3811fd5e2a6051443d468e3506bbc39bba710e34a604ac9e85d0feef8b3;

possible = []
for i in range(2^18):
    t1 = (2^18 + i)*2^(512-19)
    t2 = (2^18 + i)*2^(512-19) + (2^(512-19)-1)
    if(len(bin(N3//t1)[2:]) >= 512 and len(bin(N3//t2)[2:]) <= 512):
        possible.append(i)

#ph = int("111111010000111110",2)
#print(ph in possible)
print(len(possible))
print(2^18)

输出结果是：

1
2
22998
262144

可以看出搜索空间变成了原来的十分之一不到，这样就可以在一天以内求解出来结果了。

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
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
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
import time
from subprocess import check_output
from multiprocessing import Pool

def flatter(M):
    # compile https://github.com/keeganryan/flatter and put it in $PATH
    z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
    ret = check_output(["flatter"], input=z.encode())
    from re import findall
    return matrix(M.nrows(), M.ncols(), map(int, findall(b"-?\\d+", ret)))

debug = False

strict = False


helpful_only = True
dimension_min = 7 # 如果格达到该尺寸，则停止移除

# 显示有用矢量的统计数据
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")

# 显示带有 0 和 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)

# 尝试删除无用的向量
# 从当前 = n-1（最后一个向量）开始
def remove_unhelpful(BB, monomials, bound, current):
    # 我们从当前 = n-1（最后一个向量）开始
    if current == -1 or BB.dimensions()[0] <= dimension_min:
        return BB

    # 开始从后面检查
    for ii in range(current, -1, -1):
        #  如果它没有用
        if BB[ii, ii] >= bound:
            affected_vectors = 0
            affected_vector_index = 0
             # 让我们检查它是否影响其他向量
            for jj in range(ii + 1, BB.dimensions()[0]):
                # 如果另一个向量受到影响：
                # 我们增加计数
                if BB[jj, ii] != 0:
                    affected_vectors += 1
                    affected_vector_index = jj

            # 等级：0
            # 如果没有其他载体最终受到影响
            # 我们删除它
            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

           # 等级：1
            #如果只有一个受到影响，我们会检查
            # 如果它正在影响别的向量
            elif affected_vectors == 1:
                affected_deeper = True
                for kk in range(affected_vector_index + 1, BB.dimensions()[0]):
                    # 如果它影响哪怕一个向量
                    # 我们放弃这个
                    if BB[kk, affected_vector_index] != 0:
                        affected_deeper = False
                # 如果没有其他向量受到影响，则将其删除，并且
                # 这个有用的向量不够有用
                #与我们无用的相比
                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 如果 "strict=true"，并且行列式不受约束
* x0,y0 the solutions of `pol`
"""
def boneh_durfee(pol, modulus, mm, tt, XX, YY):
    """
    Boneh and Durfee revisited by Herrmann and May
    
 在以下情况下找到解决方案：
* d < N^delta
* |x|< e^delta
* |y|< e^0.5
每当 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-移位
    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 移位列表
    monomials = []
    for polynomial in gg:
        for monomial in polynomial.monomials(): #对于多项式中的单项式。单项式（）：
            if monomial not in monomials:  # 如果单项不在单项中
                monomials.append(monomial)
    monomials.sort()
    
    # y-移位
    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 移位列表
    for jj in range(1, tt + 1):
        for kk in range(floor(mm/tt) * jj, mm + 1):
            monomials.append(u^kk * y^jj)

    # 构造格 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)

    #约化格的原型
    if helpful_only:
        #  #自动删除
        BB = remove_unhelpful(BB, monomials, modulus^mm, nn-1)
        # 重置维度
        nn = BB.dimensions()[0]
        if nn == 0:
            print ("failure")
            return 0,0

    # 检查向量是否有帮助
    if debug:
        helpful_vectors(BB, modulus^mm)
    
    # 检查行列式是否正确界定
    det = BB.det()
    bound = modulus^(mm*nn)
    if det >= bound:
        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.BKZ(block_size=25)
    BB = flatter(BB)
    
    if debug:
        print ("LLL is done!")

    # 替换向量 i 和 j ->多项式 1 和 2
    if debug:
        print ("在格中寻找线性无关向量")
    found_polynomials = False
    
    pol1_idx = 0
    pol2_idx = 1
            
    # 对于i and j, 构造两个多项式
    
    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)

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

    
    if not (rr.is_zero() or rr.monomials() == [1]):
        found_polynomials = True

    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


def example(pM):
    t1 = time.time()

    size=512     #The size of p; size=1024 in Tables 10
    length_N = 2*size
    s=19;      #s is the number of MSBs exhaustion,  which can be chosen as we need.
    nw=3     #2^nw windows
    delta = 0.292

    N = 0xf4c548636db62ffcc7ac4a0797952bea9a65bd426175af2435f72657e67ec8194667bfa94ce23c6f1e5baf3201867ab41701f6b8768e71009c41a3d5e9e7c109455341d549c7611f9f52851a2f017906aa9ccbedb95d238468e2c8577d30ecc4f158e3811fd5e2a6051443d468e3506bbc39bba710e34a604ac9e85d0feef8b3;
    e = 0x16f4b438ba14e05afa944f7da9904f8c78ea52e4ca0be7fa2b5f84e22ddd7b0578a3477b19b7bb4a7f825acc45da2dd10e62dbd94a3386b97d92ee817b0c66c1507514a7860b9139bc2ac3a4e0fe304199214da00a4ca82bfcb7b18253e7e6144828e584dac2dfb9a03fabaf2376ce7c269923fbb60fc68325b9f6443e1f896f;
    c = 0x26b1823cf836b226e2f5c90fdcd8420dbfcd02765b26e52ef3e5c0ab494c2f4650e475e280b0b5fff0d5016621186420b09e4706a5866e4a3319f23ef09d92c4e36acba39a0f6213fbe5ee1a736ce383e6e12351e6cbfd43f10a96b7fe34bdbaf948f2fb075d9063723c9f747fe6247ae9209e5d417faf2e37e6fee2eb863556;
    # The parameters (N, e) can be chosen as we need. 
    m = 12   # 格大小（越大越好/越慢）
    #guess=100
    # you need to be a lattice master to tweak these
    t = round(((1-2*delta) * m))  # 来自 Herrmann 和 May 的优化
    X = floor(N^delta)  # 
    Y = 2*floor(N^(1/2)/2^s)    # 如果 p、 q 大小相同，则正确

    p0=pM*2^(size-s)+2^(size-s-1);
    q0=N/p0;
    qM=int(q0/2^(size-s))
    A = N + 1-pM*2^(size-s)-qM*2^(size-s);
    P.<x,y> = PolynomialRing(ZZ)
    pol = 1 + x * (A + y)  #构建的方程
    if debug:
        ##print ("=== running algorithm ===")
        start_time = time.time()
            

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


    if solx > 0:
    #print ("=== solution found ===")
        if False:
            print ("x:", solx)
            print ("y:", soly)

        d_sol = int(pol(solx, soly) / e)
        #print ("私钥d:", d)
        #if(d_sol==d):
        print ("=== solution found ===")
        print ("p的高比特为：",pM)
        print ("q的高比特为：",qM)
        #print("p的真实高比特：",int(p/2^(512-s)))
        #print("q的真实高比特：",int(q/2^(512-s)))
        print ("d=",d_sol)
        
    t2 = time.time()
    print(t2-t1)


if __name__ == "__main__":
    possible = []
    for i in range(2^18):
        t1 = (2^18 + i)*2^(512-19)
        t2 = (2^18 + i)*2^(512-19) + (2^(512-19)-1)
        if(len(bin(N3//t1)[2:]) >= 512 and len(bin(N3//t2)[2:]) <= 512):
            possible.append(2^18 + i)

    with Pool(32) as pool:
        r = list(pool.imap(example, possible))



4

题目数据：

1
2
3
N4=0xd46dd141810786e451320ca452b379024fd263501ae767760f3dcf34b79806b85e36b0fee538dac61a5872c37d051a8a026384d09f12b7e1adae7eb15c4d75878007ee0043c2186cf8999c59eb66f689f55baf190bd80e70bf47b553be76bd4efffc782a51b43314d54b83fc19461e1beb6021164f64723b505e5a619cb62335；
e4=0x92fbeeef2d40eb125234cfe4c063c4607f12aec7e3014b32fb4600e58c4eac1ec485192a1b03745632f2966311ad68bd1e49dd9d08b2bff67f58e214c8d7bae0142559994c24e347ff7555c86aa30ccd03cf794e6f00eead7f15e24f33da61fae11ec81e4e09bcc76c1a0ed5ca8c2f512856cdb42470beee7111a2410188697d；
c4=0x8c5e9db89f96d769f6514836407755caf71b7bc6f5db2246200b0f824dac7ea3be5ba022c0e191d76c69b7d20c7cad5c49e381479c7cbe7ba055ce8aec2cad1a19d42aa5c4b8c07c67e22c70289891d53c3d55dff50e506ec7fb480df44f9b3219f8c73e0702d8072e9f6aabed8bb5d35f583bea30ce850b154d4fd8c39e4fb8；

信息：

  • d在$2^{399}-2^{400}$之间
  • d最高310位比特汉明重量不超过5

考虑先将d拆分为高310位dh与低90位dl，那么如下等式成立：

这里的dh直接表示一个400bit，且低90位LSB全为0的量。由题目信息得知dh汉明重量不超过5，又因为其MSB一定为1，所以等价于dh的2-310位汉明重量不超过4，因此存在汉明重量为0、1、2、3、4的几种情况，其爆破复杂度分别为：

复杂度都还可以接受，因此用爆破方式，对于每个可能的dh，利用上述等式构造出如下三元copper：

这个模多项式具有小根$(dl,k,p+q)$，其bounds可设为$(2^{90},2^{400},2^{513})$，利用defund的多元coppersmith代码先进行数据测试出m=2，d=3时，在dh正确时可以得到预期的正确小根$(dl,k,p+q)$

同时，设置上述参数可以发现在实验过程中，能够求解的dl小根上界能够达到118bit，也就是对于$(2^{118},2^{400},2^{513})$的bounds，这样的copper几乎也能达到100%的成功率。所以考虑令dl表示d的低118位，dh表示一个400bit，且低118位LSB全为0的量。此时重新估计爆破复杂度：

可以看到复杂度降低的并不算很多，但是有一点需要注意，就是如果高310位的汉明重量构成中，有至少一个1分布在90-118这个LSB区间内的话，就可以把复杂度直接降一阶。而如果把高2-310位的几个1视作完全随机散落在其中的话，那么可以简单估计一下至少有一个1落在90-118这个LSB区间内的概率为：

因此有31.7%的不算低的概率显著降低爆破复杂度，并且最终结果也证明的确有一个1分布在此区间内。

开48进程跑，最终耗时约为三小时，不过如果不满足这种情况的话会很麻烦，复杂度会增加2^6倍左右。

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 Crypto.Util.number import *
from tqdm import *
import itertools
from multiprocessing import Pool


#coppersmith
def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()
    R = f.base_ring()
    N = R.cardinality()
    f /= f.coefficients().pop(0)
    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)
    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 []

def attack(bits):
    n=0xd46dd141810786e451320ca452b379024fd263501ae767760f3dcf34b79806b85e36b0fee538dac61a5872c37d051a8a026384d09f12b7e1adae7eb15c4d75878007ee0043c2186cf8999c59eb66f689f55baf190bd80e70bf47b553be76bd4efffc782a51b43314d54b83fc19461e1beb6021164f64723b505e5a619cb62335
    e=0x92fbeeef2d40eb125234cfe4c063c4607f12aec7e3014b32fb4600e58c4eac1ec485192a1b03745632f2966311ad68bd1e49dd9d08b2bff67f58e214c8d7bae0142559994c24e347ff7555c86aa30ccd03cf794e6f00eead7f15e24f33da61fae11ec81e4e09bcc76c1a0ed5ca8c2f512856cdb42470beee7111a2410188697d
    c=0x8c5e9db89f96d769f6514836407755caf71b7bc6f5db2246200b0f824dac7ea3be5ba022c0e191d76c69b7d20c7cad5c49e381479c7cbe7ba055ce8aec2cad1a19d42aa5c4b8c07c67e22c70289891d53c3d55dff50e506ec7fb480df44f9b3219f8c73e0702d8072e9f6aabed8bb5d35f583bea30ce850b154d4fd8c39e4fb8

    dh = 1 << 399
    for j in bits:
        dh += int(1 << j)

    PR.<x,y,z> = PolynomialRing(Zmod(e*dh))
    f = e*x - 1 - y*(n+1-z)
    bounds = (2^118,2^400,2^513)

    res = small_roots(f,bounds,m=2,d=3)
    if(res != []):
        print("Found :" , bits , res)

bits_list = []
for i in range(118,399):
    for j in range(i+1,399):
        bits_list.append((i,j))

with Pool(48) as pool:
        r = list(pool.imap(attack, bits_list))


#Found : (249, 384) [(5192297506701663409346420477763893, 893384003511473915730729716053400071808197337898454780292963816952680159001572448270279758619478210599539972781994723065, 24525002309255501553376344678840111819444126206525944516411655318006503268196948978108788630740241285503306697779442437584553316771409973418709483848235094)]



5

题目数据：

1
2
3
N5=0x94eab94581f4931a5ea6aabcfe0598600fa3e0a06573887aed69e274f14484472dc3feaf50d4ef384e502f747f5605c1d2a4c8172b6ef134b7e96d6c383a9cb967ccbbd8b3647848d34928982a274999c2df00bd7dd11bf25acd61411e3395637e85dd84ecf785ff1027eed91f3976c8186e2e940edcb5fed8d759a5028b47a1;
e5=0x124c552642ef2467aaecde51b0f3e1bee2ebe87bae39a956ad56cf7eec669cdc7b9664ea435b4c3492b8e610e0a182e1a76c7af443ca2962672b4e703c4f359cf8d88a67db77be2491b74bcdae58691b69e6ea06d067815b26fc0d669d8c06f11a728154dc8cdf983a056633fecadc417df4304625c3e6f91ec3d655a91a29e9;
c5=0x63e09028c774513b5420236f8405f970c8d97c8347697c44f50b23e5cc964c921413b5e6742bb5ba7ef49f032e372f502babc0040f9c7cc2c9f4e27d18aefff0e764529ba70f6a7b22d525d0aaeb1d21432817b6b148b8143c80a6401a5c9adfecf0c033181bb076a2192a4866c5355c9e401fba78d5f22b9c1661c0065a1a28;

信息：

  • d在$2^{511}-2^{512}$之间
  • d的高256位以及低176位已知，中间80位未知

由题目已知信息，d可以写作：

那么有如下等式成立：

而由于d存在高256bit的泄露，因此对于下面的等式：

可以得到一个近似关系为：

因此可以得到一个k的近似值k’：

这样得到的k与真实k’的差值也在256bit附近，可以将差值记作x：

代入等式得到：

此时可以将该等式写成模多项式的形式如下：

该多项式有小根$(x,p+q)$，其bounds可设为$(2^{256},2^{513})$，利用defund的多元coppersmith代码进行数据测试，测试出直接令LSB泄露位数为176时，copper的效果并不是很好。而当LSB泄露位数达到181时，取m=4，d=5，在dh正确时可以在较短时间内得到预期的正确小根$(x,p+q)$，因此最终考虑爆破5位LSB，并结合copper去解如下模多项式的小根：

此时sage10.2可在2min内求解出小根，不过这是因为爆破的5位恰好全为0导致的，平均期望时间为16*2min，约为半小时。

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
from Crypto.Util.number import *
from tqdm import *
import itertools
from multiprocessing import Pool

#coppersmith
def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()
    R = f.base_ring()
    N = R.cardinality()
    f /= f.coefficients().pop(0)
    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)
    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 []


def attack(iii):
    leakh = 256
    leakl = 181
    n=0x94eab94581f4931a5ea6aabcfe0598600fa3e0a06573887aed69e274f14484472dc3feaf50d4ef384e502f747f5605c1d2a4c8172b6ef134b7e96d6c383a9cb967ccbbd8b3647848d34928982a274999c2df00bd7dd11bf25acd61411e3395637e85dd84ecf785ff1027eed91f3976c8186e2e940edcb5fed8d759a5028b47a1
    e=0x124c552642ef2467aaecde51b0f3e1bee2ebe87bae39a956ad56cf7eec669cdc7b9664ea435b4c3492b8e610e0a182e1a76c7af443ca2962672b4e703c4f359cf8d88a67db77be2491b74bcdae58691b69e6ea06d067815b26fc0d669d8c06f11a728154dc8cdf983a056633fecadc417df4304625c3e6f91ec3d655a91a29e9
    c=0x63e09028c774513b5420236f8405f970c8d97c8347697c44f50b23e5cc964c921413b5e6742bb5ba7ef49f032e372f502babc0040f9c7cc2c9f4e27d18aefff0e764529ba70f6a7b22d525d0aaeb1d21432817b6b148b8143c80a6401a5c9adfecf0c033181bb076a2192a4866c5355c9e401fba78d5f22b9c1661c0065a1a28

    dbits = 512
    dl=0x2b26d177dc20ceea15de6e3c5a03207fb326a42d53a9 + iii*2^176
    dh=0xacfad4bbb97a99b6bbc82c8b44a5260bcfe9c4a0acf437186ff4d5d1594cc5c1 * 2^256

    k_ = e*dh // n

    PR.<x,y> = PolynomialRing(Zmod(e*2^leakl))
    f = 1 + (k_ + x) * ((n+1) - y) - e*dl

    bounds = (2^(dbits - leakh),2^513)
    res = small_roots(f,bounds,m=4,d=5)
    print(res)

ilist = [i for i in range(2^5)]
for i in tqdm(ilist):
    attack(i)


#[(282010924167718115516906667153545502501458151856718764152936084250030151051, 20661478341083012421041400219228187859079281634475352660573325439758998053149827536900946611679931330854849964562295456435862096666323900861438939486653810)]



6

题目数据：

1
2
3
N6=0x94e4c83c67c6d6e33d83cc2953df899e8c4b33894f653d5bbc84d7dd9058e6949221897f6e5b7b8bd9013f495c906862e401436e77be585474066f6c220751dd9b2b8be66f07ad7f090547a6e759e482ba263b941b32c27c62c4b558d96dda168b28c52e550b7d7ff145a5996c0b398714cf5ee8f0ea1a3d5b17c592f1c15275;
e6=0x949b2e72766be1e83ee278a56bc86a2d3268b719507068ac62c6d249a810284edaac39335e8d699630887c13864f4cdf1c0c423b2f7ae88ccc60a827332e6c410800c7c7a1677918c28aa51086991d1290fc64b8e1b0f14b482f35d86139bb3491a59e2ad99dcd35bd129a44c3b8e2667e405dc2d307a5bb5a1504d7ded3bda3;
c6=0x6fd6fae8ab4e95e622e5dad2921c6f12e911df08768abf2d10d212ad9a26e4c5ec71640d7a6b3488064fd424224bc2c762b956af95a3212de37a57d74c0299936f48ae3d8b8803e644e8d1306ab735c94fd815fe8c77982b32d51e9b6f3b3d4f3753810b61fb528c3e9eb774dabd93a3c5c9919ae3fb90e8e998ed3e7f949738;

信息：

  • d在$2^{559}-2^{560}$之间
  • d的最高123位比特取值未知，但其剩余437位比特取值已知
  • d的低437位取值很小，为0x6da211f0d34b，也就是说d的中间大部分比特均为0

题目基于私钥特定低比特位的泄露，可以观察到其泄露的低位数据相当特殊，其中间位置为很多连续的0。如果将所有数据表示为：

则其所有参数完全符合给出的参考文献三的如下条件：

因此参考文献三的特殊LSB泄露情况理论上能够解决本题，构造模多项式如下：

其中：

此外采用线性化模方程处理，引入新变量$u = xy + A$，则得到方程：

然后选用如下单项式与对应多项式集合进行格构造：

最终参考实验数据，选择参数：

可以在1min左右求解。

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
from Crypto.Util.number import *

#gen params
alpha = 1
beta = 560/1024
delta = 437/1024

r = int(1024*delta)
N = 0x94e4c83c67c6d6e33d83cc2953df899e8c4b33894f653d5bbc84d7dd9058e6949221897f6e5b7b8bd9013f495c906862e401436e77be585474066f6c220751dd9b2b8be66f07ad7f090547a6e759e482ba263b941b32c27c62c4b558d96dda168b28c52e550b7d7ff145a5996c0b398714cf5ee8f0ea1a3d5b17c592f1c15275;
e = 0x949b2e72766be1e83ee278a56bc86a2d3268b719507068ac62c6d249a810284edaac39335e8d699630887c13864f4cdf1c0c423b2f7ae88ccc60a827332e6c410800c7c7a1677918c28aa51086991d1290fc64b8e1b0f14b482f35d86139bb3491a59e2ad99dcd35bd129a44c3b8e2667e405dc2d307a5bb5a1504d7ded3bda3;
c = 0x6fd6fae8ab4e95e622e5dad2921c6f12e911df08768abf2d10d212ad9a26e4c5ec71640d7a6b3488064fd424224bc2c762b956af95a3212de37a57d74c0299936f48ae3d8b8803e644e8d1306ab735c94fd815fe8c77982b32d51e9b6f3b3d4f3753810b61fb528c3e9eb774dabd93a3c5c9919ae3fb90e8e998ed3e7f949738;
d2 = dl=0x6da211f0d34b

m = 7
tau = 6
theta = ["pad"] + [2,3,4,5,6,7]


#attack
A = e*d2-1
W = e*2^r
X = int(N^(alpha+beta-1))
Y = int(3*N^0.5)
U = int(7*N^(alpha+beta-0.5))

PR.<x,y,u> = PolynomialRing(ZZ)
x,y,u = PR.gens()
f = -N*x + u
f_ = u - (x*y + A)

poly = []
monomials=set()

#G
for t in range(0,m+1):
    for j in range(0,t+1):
        G = x^(t-j) * f^j * W^(m-j)

        #deal with xy
        for mono in G.monomials():
            while(mono % (x*y) == 0):
                temp = G.monomial_coefficient(mono)
                G -= temp*mono
                mono //= (x*y)
                mono *= (u-A)
                G += temp*mono
        poly.append(G)
        for mono in G.monomials():
            monomials.add(mono)

#P
for i in range(1,tau+1):
    for j in range(theta[i],m+1):
        P = y^i * f^j * W^(m-j)

        #deal with xy
        for mono in P.monomials():
            while(mono % (x*y) == 0):
                temp = P.monomial_coefficient(mono)
                P -= temp*mono
                mono //= (x*y)
                mono *= (u-A)
                P += temp*mono
        poly.append(P)
        for mono in P.monomials():
            monomials.add(mono)

L = Matrix(ZZ,len(poly),len(monomials))

monomials = sorted(monomials)
for row,shift in enumerate(poly):
    for col,monomial in enumerate(monomials):
        L[row,col] = shift.monomial_coefficient(monomial)*monomial(X,Y,U)

print(L.dimensions())

res = L.LLL()
vec1 = res[2]
vec2 = res[1]

f1 = 0
for idx,monomial in enumerate(monomials):
	f1 += (vec1[idx] // monomial(X,Y,U)) * monomial
f1 = f1.change_ring(ZZ)
f2 = 0
for idx,monomial in enumerate(monomials):
	f2 += (vec2[idx] // monomial(X,Y,U)) * monomial
f2 = f2.change_ring(ZZ)

g1 = f_.sylvester_matrix(f1, u).det()
g2 = f_.sylvester_matrix(f2, u).det()
h = g1.sylvester_matrix(g2, x).det()
res1 = h.univariate_polynomial().monic().roots()
print(res1)


#p+q-1 is:
#[(20669116529972280868235472642422776201909637285884516155862888589837342513282316090088342096364702368094391219552254156670270390106105101130869387179628885, 1)]



7

题目数据：

1
2
3
N7=0xaeb75bb97217271bf312a7897da81a544fe469ba0f1cf75304f2a5629717e1e3d0a9a28e71135443cc19f78c60dd3f7ea4ea28ae64657d5ac3b46e9755020de73cb5c4f89a682e0193916221bc8f4abb595f2c058bbb99e199a66144a9a9b258a74db847b2460107233280c94e854394595043f62bf77cd96c9ed3eca71b726d;
e7=0x42b63e1113b4a84d0b037006a9bb729b52db495fa6b475bb64129a855a4ed6511792d0df946c5d7e22085d0db07bce5e408454a61c0cea51cf6d25e2455a2c6dc092e4b09bf4efb2157ffc1d1db3e969499479d721330ec4ac864e656318bc7bb9831a0dccf582406c87ae5d3ab9ffec351271dbb5481a0b6ed75a760b4f7e0d;
c7=0xe1f90d9f115f9ba0b65ea8826ffec785bbe1b195fbb6f93c6ea28940f0d9b571930addb3e2714999ba5a19d17af22f1bc8da49f8b515ab03b6d276140b69fedf980d1aef78d0f3c0f6effdf2e92ce9195866f85672037537021178f8c65989b57f29de2c4c9306fe3e13aef29f962f86b8d5216907e85f28260b9f41cfe2651;

信息：

  • $\phi-d$的范围在$2^{267}-2^{268}$之间

记这个小差值为t，就有：

可以看出目标是把t作为某个模多项式的小根，因此仍然利用e、d与$\phi(n)$的关系式：

移项整理一下：

这是一个等式，而由于$\phi,e$数量级是相近的，所以e-k和t数量级也只能相近，因此e-k也差不多在$2^{267}-2^{268}$这个范围，记这个值为r，那么在模e下就有：

所以有以(r,p+q)为小根的多项式：

之后用defund的copper就行。

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
import itertools
from gmpy2 import *
from Crypto.Util.number import *

def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()
 
    R = f.base_ring()
    N = R.cardinality()
 
    f /= f.coefficients().pop(0)
    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)
 
    B, monomials = G.coefficients_monomials()
    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 []

n = 0xaeb75bb97217271bf312a7897da81a544fe469ba0f1cf75304f2a5629717e1e3d0a9a28e71135443cc19f78c60dd3f7ea4ea28ae64657d5ac3b46e9755020de73cb5c4f89a682e0193916221bc8f4abb595f2c058bbb99e199a66144a9a9b258a74db847b2460107233280c94e854394595043f62bf77cd96c9ed3eca71b726d;
e = 0x42b63e1113b4a84d0b037006a9bb729b52db495fa6b475bb64129a855a4ed6511792d0df946c5d7e22085d0db07bce5e408454a61c0cea51cf6d25e2455a2c6dc092e4b09bf4efb2157ffc1d1db3e969499479d721330ec4ac864e656318bc7bb9831a0dccf582406c87ae5d3ab9ffec351271dbb5481a0b6ed75a760b4f7e0d;
c = 0xe1f90d9f115f9ba0b65ea8826ffec785bbe1b195fbb6f93c6ea28940f0d9b571930addb3e2714999ba5a19d17af22f1bc8da49f8b515ab03b6d276140b69fedf980d1aef78d0f3c0f6effdf2e92ce9195866f85672037537021178f8c65989b57f29de2c4c9306fe3e13aef29f962f86b8d5216907e85f28260b9f41cfe2651;

R.<x,y> = PolynomialRing(Zmod(e))
f = 1+x*(n+1-y)
bounds = (2^268,2^513)
res = small_roots(f,bounds,m=3,d=4)

pplusq = int(res[0][1])
pminusq = iroot(pplusq^2-4*n,2)[0]
p = (pplusq + pminusq) // 2
q = n // p

d = inverse(e,(p-1)*(q-1))

print("p =",p)
print("q =",q)
print(long_to_bytes(int(pow(c,d,n)))[::-1].decode('ISO-8859-1'))



8

题目数据：

1
2
3
N8=0xf12eac2099c4190a6f586bea0b4fc3f9dff4f23f0cb8e42cbeff950aa1df8a373c49df7974fb33b4b6619eadb2d6c01f80da1b433295b199df11b323114c439884eb31fa568bd747ae37079e885e2490c3b5a56d61b9d10533983ff78fe85e07876fe2ae07ae7ea1c71f0f9c2d6beccdcd8baf046a58549aec19d45d48d7d92d;
e8=0xb8906f5097658f27cc448d98974d9e7ccd4e8a8f25a80007826c341dcb2ac42420f899e5a89045fbefd9163bc94e6f98b4953546203be4bec249031587a27dbf;
c8=0x162a6dee8bcbe24698b9249137c2a157890910fa74a56e7d2792b5b4f29112aba03448995ff32ed24bec5118f7433212196d3f99e1c794b61395d8183e4658c9dc05953a87c069c9390773c7f885907840ebd29676afac7bf3374d54c81c4e404f09716b9885d243c41dc48db561f8291b88826cae32bfd575a472e523f455c4;

信息：

  • e仅有512bit，约为$n^{0.5}$
  • d的低900位已知，高124位未知

题目为私钥d的LSB泄露情况，并且加密指数e的比特数约为N的一半，结合此种情况找到参考文献：

27290027.pdf (iacr.org)

题目完全符合其section 6的LSB泄露情况，记数据为：

则可以写出模多项式：

此时多项式有小根：

并分别选择如下y-shift和z-shift多项式来构造格：

选取参数：

经测试可以在2min内可以求解泄露910bit的情况，而由于题目仅泄露910bit，因此考虑爆破10bit，结合多进程缩短求解时间，最终开八进程耗时约为2h。

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
from Crypto.Util.number import *
from multiprocessing import Pool
from subprocess import check_output
import time


def flatter(M):
    # compile https://github.com/keeganryan/flatter and put it in $PATH
    z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
    ret = check_output(["flatter"], input=z.encode())
    from re import findall
    return matrix(M.nrows(), M.ncols(), map(int, findall(b"-?\\d+", ret)))

ebits = 512
n=0xf12eac2099c4190a6f586bea0b4fc3f9dff4f23f0cb8e42cbeff950aa1df8a373c49df7974fb33b4b6619eadb2d6c01f80da1b433295b199df11b323114c439884eb31fa568bd747ae37079e885e2490c3b5a56d61b9d10533983ff78fe85e07876fe2ae07ae7ea1c71f0f9c2d6beccdcd8baf046a58549aec19d45d48d7d92d
e=0xb8906f5097658f27cc448d98974d9e7ccd4e8a8f25a80007826c341dcb2ac42420f899e5a89045fbefd9163bc94e6f98b4953546203be4bec249031587a27dbf
c=0x162a6dee8bcbe24698b9249137c2a157890910fa74a56e7d2792b5b4f29112aba03448995ff32ed24bec5118f7433212196d3f99e1c794b61395d8183e4658c9dc05953a87c069c9390773c7f885907840ebd29676afac7bf3374d54c81c4e404f09716b9885d243c41dc48db561f8291b88826cae32bfd575a472e523f455c4
dl=0x4cbec287edc86c5b2a9e1975d64d2a24d3930075f0d445163c7b1ceec9ee0319fe1166af348b49004d2420b83bcb82d4879e93dba01ee76c5ca1b7141490465e824bdb5e91d04016c6bbbaa41c4470747ee8163f710b2d8adb8ab2168dcc996b5ab5f85a2269dc459379fb68848cec487
leak = 910
M = 2^leak
alpha = ebits/1024
Y = int(n^alpha)
Z = int(3*n^0.5)

#attack
def attack(iii):
	t1 = time.time()
	d0 = dl + 2^900*iii

	m = 7
	t = 2

	poly = []
	monomials=set()

	PR.<y,z> = PolynomialRing(ZZ)
	y,z = PR.gens()
	f = y*(n-z) - e*d0 + 1

	for i in range(0,m+1):
		for j in range(0,i+1):
			g = y^j * (e*M)^i * f^(m-i)
			poly.append(g)
			for mono in g.monomials():
				monomials.add(mono)

	for i in range(0,m+1):
		for j in range(1,t+1):
			h = z^j * (e*M)^i * f^(m-i)
			poly.append(h)
			for mono in h.monomials():
				monomials.add(mono)


	L = Matrix(ZZ,len(poly),len(monomials))

	monomials = sorted(monomials)
	for row,shift in enumerate(poly):
		for col,monomial in enumerate(monomials):
			L[row,col] = shift.monomial_coefficient(monomial)*monomial(Y,Z)

	#print(L.dimensions())

	res = flatter(L)
	vec1 = res[0]
	vec2 = res[1]

	f1 = 0
	for idx,monomial in enumerate(monomials):
			f1 += (vec1[idx] // monomial(Y,Z)) * monomial
	f1 = f1.change_ring(ZZ)
	f2 = 0
	for idx,monomial in enumerate(monomials):
			f2 += (vec2[idx] // monomial(Y,Z)) * monomial
	f2 = f2.change_ring(ZZ)

	h = f1.sylvester_matrix(f2, y).det()
	res1 = h.univariate_polynomial().monic().roots()
	t2 = time.time()
	print(t2-t1)
	if(res1 != []):
		print(res1)


ilist = [i for i in range(2^10)]

with Pool(8) as pool:
    r = list(pool.imap(attack, ilist[::-1]))


#p+q-1 is:
#26034831836893224902673168159369440840844528954669232434446445029015830075273876167180768873144179504296085932127304140645470361784554913695920045941531153



9

题目数据：

1
2
3
e9=65537
N9=0xcc5b706f373a79c680cec9527aac573fd435129cf16c23334085bf97832e5a6c78b633c2f244b12a62f87ec5295dd89fcf3c808c39e45a9afdbda2f8d2d0b50d61b685c0fe9eb41a7018a40f98892f96d738e2a4e740d4e507bcbd07f68c1ecb2ca10bd780ce65265a7e4da00f1031a5db9d038878a29a5ffefcaf2119720005;
c9=0x20bac8a7d73a74c9913377846c13c3d2bd9f47e6df118d1486a96ed184ca9910e0f250500065cfb44105a41dff655364cabc3067ef3cd3d7d983e75c9303b786ac97507cfe803b788b12e582232028ca9772d05004aef194076ec442e3ee55e17fbb4a57f332b4393ac056c024141cc2b82f9dbc6d3c77f6eff20cd0ecc9cbab;

第九题主要有以下几个信息：

  • e=65537
  • d的低530位已知，剩余高位未知

题目基于私钥d的LSB泄露，相比于第八题，将LSB的泄露位数减少到530位，但同时将加密指数e减少到了65537。不妨将d记为：

由于公钥较小，此类情况与参考文献二的section 4.2.9完全符合。对于下式：

由于$d < \phi(n)$，因此一定有$k < e$，而由于e仅有65537，所以k可以在(0,e)这个小范围内进行爆破，而对于正确的k，下面式子成立：

上式自然在模2^530下也成立，也就有：

上式有两个变量p、q，利用n=pq这一点进行单元化，则可以化成模2^530下的单元方程：

整理一下就得到：

于是在模2^530下求解上述方程，得到的解即为可能的p低530位，而p、q本身只是512bit的素数，所以并不需要再用copper逐一求解p低位泄露，直接检查是否被n整除即可获得n的分解。sage10.2期望耗时约为半小时左右。

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
from Crypto.Util.number import *
from tqdm import *

e = 65537
n = 0xcc5b706f373a79c680cec9527aac573fd435129cf16c23334085bf97832e5a6c78b633c2f244b12a62f87ec5295dd89fcf3c808c39e45a9afdbda2f8d2d0b50d61b685c0fe9eb41a7018a40f98892f96d738e2a4e740d4e507bcbd07f68c1ecb2ca10bd780ce65265a7e4da00f1031a5db9d038878a29a5ffefcaf2119720005
c = 0x20bac8a7d73a74c9913377846c13c3d2bd9f47e6df118d1486a96ed184ca9910e0f250500065cfb44105a41dff655364cabc3067ef3cd3d7d983e75c9303b786ac97507cfe803b788b12e582232028ca9772d05004aef194076ec442e3ee55e17fbb4a57f332b4393ac056c024141cc2b82f9dbc6d3c77f6eff20cd0ecc9cbab
dl = 0x20142ae2802b877eb4dfa8a462e7d017c4d348181c367fd1a661ec9b6bbcca9dcb6601ccb6c10416b7f3c20129527346bbc136ee60f9945125cba03a9bba3720f7411

def attack(k):
    p = var('p')
    p0 = solve_mod([-k*p^2 + (k*(n+1)+1-e*dl)*p -k*n  == 0], 2^530)
    if(len(p0) != 0):
        for j in p0:
            if(n % int(j[0]) == 0):
                print("Found p:" , int(j[0]))
                return True

if(1):
    for k in trange(1,e):
        find = attack(k)
        if(find):
            break

k = 22348
p = 10846327614507406655792564994667714933899253952298425269758486277699020260863878841336945944423557227322075142932155647161674834513419649086027797728283207
q = n // p
phi = (p-1)*(q-1)
d = inverse(e,phi)

print("d =",d)
print("p =",p)
print("q =",q)
assert p*q == n
print(long_to_bytes(int(pow(c,d,n)))[::-1])

#Resolving the composite numbers into their prime factors is known to be one of the most important and useful in arithmetic.

可能是因为sage解模2^530下方程的速度并不快，所以这个方法效率真的很低，赛中听@deebato讲了一个明显更优的方式是：

  • 爆破k，由$ed \approx kn$去解d高位
  • 和d低位拼起来解c得到明文

这样就只需要几秒就行了。

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import *
from gmpy2 import powmod

e = 65537
n = 0xcc5b706f373a79c680cec9527aac573fd435129cf16c23334085bf97832e5a6c78b633c2f244b12a62f87ec5295dd89fcf3c808c39e45a9afdbda2f8d2d0b50d61b685c0fe9eb41a7018a40f98892f96d738e2a4e740d4e507bcbd07f68c1ecb2ca10bd780ce65265a7e4da00f1031a5db9d038878a29a5ffefcaf2119720005
c = 0x20bac8a7d73a74c9913377846c13c3d2bd9f47e6df118d1486a96ed184ca9910e0f250500065cfb44105a41dff655364cabc3067ef3cd3d7d983e75c9303b786ac97507cfe803b788b12e582232028ca9772d05004aef194076ec442e3ee55e17fbb4a57f332b4393ac056c024141cc2b82f9dbc6d3c77f6eff20cd0ecc9cbab
dl = 0x20142ae2802b877eb4dfa8a462e7d017c4d348181c367fd1a661ec9b6bbcca9dcb6601ccb6c10416b7f3c20129527346bbc136ee60f9945125cba03a9bba3720f7411
d = 48934776628725324382665082114299447937340082241799544768710753959849031360081579743041602050591310715229818997116081242616359194543184338502069650397869985126397078720094810145259742806152398430221459833419493737528368084683621557302194467494851616524101832395135547354509904758069472861546701396840400516113

for k in range(1,e):
    dh = k*n // e
    d = (dh >> 530 << 530) + dl
    try:
        print(long_to_bytes(powmod(c,d,n)).decode()[::-1])
        break
    except:
        pass


#Resolving the composite numbers into their prime factors is known to be one of the most important and useful in arithmetic.



10

题目数据：

1
2
3
4
5
e10=65537
N10=0x8d0df1ce526c39f9b057de462778a61ceda2049c7e32ee99d40baa4b22b7fd438e9ca1dfd7467684625add252095ee97c698199f4c5991279f6d3e74d4c14d01d137d42722df0d4565ff2a5275f9cac66dc4dfdf3304f85cbdc3d18eda1e32ac5d03675141a722ceefe0ea0533b53d7e50ed7eda1a1bbce47ed0ecb966f8678d
c10=0x3b42fa3dc9089a21e9dabfe18297df47272f7e0ff59bf9bf16bc55e7fa70504c03fed56ca5ae93ac028f60ce5da3c145c6d181c5bd3c267288ec4765a19ca6b957b4535a1a185bd1b87d2e39b30e2430ed648175c29fdc1fde3787c426783dd66ba17f98b42ba13a7b3532970d0aa31b5ffa5f3eae243337a1668bae456bfbfb
a=0x19ffe8024fcf0320b3107f380f2e7deff71d561c4266c0f439d1aca20cd43d2aa6aed8679a16b2e1d3ff4ba3fc4da69cf34e35ead6f7eb79923960b9c83d9923e591b07b65275bf67f0b3d424cd7e6e6dd88ea39a5cfa27ecee61caaacc93e751dbb2a4c196f0ce0c36d44c35d6658d71b6c48b7b29400ab9161a0000000000
b=0x19ffe8024fcf0320b3107f380f2e7deff71d561c4266c0f439d1aca20cd43d2aa6aed8679a16b2e1d3ff4ba3fc4da69cf34e35ead6f7eb79923960b9c83d9923e591b07b65275bf67f0b3d424cd7e6e6dd88ea39a5cfa27ecee61caaacc93e751dbb2a4c196f0ce0c36d44c35d6658d71b6c48b7b29400ab9161affffffffff

信息：

  • e=65537
  • d的取值范围在已知的a到b的闭区间内，范围大小约为2^40

题目等价于d的低40位未知，记这低40bit为dl，那么d可以写作：

又因为模n下有：

代入就得到：

考虑mitm，不妨把低40位再拆做两半d1和d2，就得到：

分别移到等式两侧：

之后mitm就好了。

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
from tqdm import *
from gmpy2 import *

e = 65537
n = 0x8d0df1ce526c39f9b057de462778a61ceda2049c7e32ee99d40baa4b22b7fd438e9ca1dfd7467684625add252095ee97c698199f4c5991279f6d3e74d4c14d01d137d42722df0d4565ff2a5275f9cac66dc4dfdf3304f85cbdc3d18eda1e32ac5d03675141a722ceefe0ea0533b53d7e50ed7eda1a1bbce47ed0ecb966f8678d
c = 0x3b42fa3dc9089a21e9dabfe18297df47272f7e0ff59bf9bf16bc55e7fa70504c03fed56ca5ae93ac028f60ce5da3c145c6d181c5bd3c267288ec4765a19ca6b957b4535a1a185bd1b87d2e39b30e2430ed648175c29fdc1fde3787c426783dd66ba17f98b42ba13a7b3532970d0aa31b5ffa5f3eae243337a1668bae456bfbfb
dl = 0x19ffe8024fcf0320b3107f380f2e7deff71d561c4266c0f439d1aca20cd43d2aa6aed8679a16b2e1d3ff4ba3fc4da69cf34e35ead6f7eb79923960b9c83d9923e591b07b65275bf67f0b3d424cd7e6e6dd88ea39a5cfa27ecee61caaacc93e751dbb2a4c196f0ce0c36d44c35d6658d71b6c48b7b29400ab9161a0000000000
dh = 0x19ffe8024fcf0320b3107f380f2e7deff71d561c4266c0f439d1aca20cd43d2aa6aed8679a16b2e1d3ff4ba3fc4da69cf34e35ead6f7eb79923960b9c83d9923e591b07b65275bf67f0b3d424cd7e6e6dd88ea39a5cfa27ecee61caaacc93e751dbb2a4c196f0ce0c36d44c35d6658d71b6c48b7b29400ab9161affffffffff

k = powmod(2,e,n)
k20 = powmod(k,2**20,n)
tmp = 1
l = {}
for i in trange(1,2**20):
    tmp = tmp * k20 % n
    l[tmp] = i

ki = invert(int(k),n)
tmp = 2*powmod(ki,dl,n)

for i in trange(2**20):
    tmp = tmp * ki % n
    
    if tmp in l.keys():
        print(i,l[tmp])



11

题目数据：

1
2
3
4
5
e11=65537
N11=0xcb5645c59c402b0edcf96cbd6a7308b64aac2f37a3c6f96be7c421c4b7f0a4adbdecd88cbea1128352fb21baae583fe4ceb3fc93c4905803ad3e9214ada050d5c0ff785a13a5c9157c3154ad8d7015a2d239fe13ef836d3279c5cd5dc96013ac40f372a9c9226d2f5fe73f312c56e11d9cdfbf9fb0db627ac1a752f5f0bd2b29
c11=0x84e4aa0be481e9c4bbd4c71dba5235cccd8312759de35c326c7e4cdda494196d1c0cae298240942af3082fac215965999c908a79bf07e093ee0c402e727a09a1c1f13831875d66ebbc3f89507163de90339af055bcd7d778574775214accfbd8ae20001f27bc196b974cb3ac215fea3debb7b17a21a8ebb1a9880a671539ef21
a=0x4f77b72b04e6fb2d02e5a43edef4784a2e22df0d42bfc7c9093a58ec35eb21a11962103be960b0088d0cc2e0dfb473bc2ba0a22cea1c73997442c8fab5e4bad22cd131055b0382eb9264ad40ec8257abaff11b33b173ffd0168039bf40dc203eb325d884d2845fd2b5a37f41a0f64183db0c256c244500000000000000000000
b=0x4f77b72b04e6fb2d02e5a43edef4784a2e22df0d42bfc7c9093a58ec35eb21a11962103be960b0088d0cc2e0dfb473bc2ba0a22cea1c73997442c8fab5e4bad22cd131055b0382eb9264ad40ec8257abaff11b33b173ffd0168039bf40dc203eb325d884d2845fd2b5a37f41a0f64183db0c256c2445ffffffffffffffffffff

信息：

  • e=65537
  • d的取值范围在已知的a到b的闭区间内，范围大小约为2^80

相较于第十题，本题将私钥d的未知低位提升到了80位，如果继续采用mitm的思路，则时间复杂度和建立字典的空间复杂度都过大了，因此需要转换思路。首先将d写为：

所以有：

由于d大部分高位已知，所以可以直接做整除得到k：

在有了k的准确值之后，上述式子可以看作一个模ea下的模多项式：

此时其含有小根：

将这个式子与赛题四的式子进行对比，可以发现两者区别为：

  • 本题已知k
  • 本题模多项式的模数更大
  • 本题d的LSB对应的小根更小

因此理论上来说赛题4的copper构造完全能够求解本题的情况，然而实际测试发现copper虽然能求出来根，但其根的值并不是我们需要的$(d_l,p+q-1)$，而是一个x0仅有十几bit的更小的根。

思考发现，这是因为如下形式的根均是上述方程的根：

这本质上是在说这个方程的根可以写作如下线性组合的形式：

因此copper得到的是一个相对于我们期望的$(d_l,p+q-1)$来说更小的一个根，因此得到的十几bit的小量其实是dl减去t倍的k后得到的值，对应的，得到的y0就是p+q-1+t的值。

而由于t显然不超过80bit，因此我们得到的小根中的y0与真实的p+q的误差也不会超过80bit，这就可以转化为已知p+q的高位分解n的问题。具体来说，记有误差的p+q为leak，则可以在实数域上求解下面的方程得到p的高位：

此时得到的p的高位与p的真实值的误差也在80bit左右，因此可以直接copper求解p高位泄露问题得到n的分解。此种方式自然也能解决赛题10的情形。并且耗时极短。

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 Crypto.Util.number import *
from tqdm import *
import itertools


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

    R = f.base_ring()
    N = R.cardinality()
    
    k = ZZ(f.coefficients().pop(0))
    g = gcd(k, N)
    k = R(k/g)

    f *= 1/k
    f = f.change_ring(ZZ)

    vars = f.variables()
    G = Sequence([], f.parent())
    for k in range(m):
        for i in range(m-k+1):
            for subvars in itertools.combinations_with_replacement(vars[1:], i):
                g = f**k * prod(subvars) * N**(max(d-k, 0))
                G.append(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, Integer(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 []

e = 65537
n = 0xcb5645c59c402b0edcf96cbd6a7308b64aac2f37a3c6f96be7c421c4b7f0a4adbdecd88cbea1128352fb21baae583fe4ceb3fc93c4905803ad3e9214ada050d5c0ff785a13a5c9157c3154ad8d7015a2d239fe13ef836d3279c5cd5dc96013ac40f372a9c9226d2f5fe73f312c56e11d9cdfbf9fb0db627ac1a752f5f0bd2b29
c = 0x84e4aa0be481e9c4bbd4c71dba5235cccd8312759de35c326c7e4cdda494196d1c0cae298240942af3082fac215965999c908a79bf07e093ee0c402e727a09a1c1f13831875d66ebbc3f89507163de90339af055bcd7d778574775214accfbd8ae20001f27bc196b974cb3ac215fea3debb7b17a21a8ebb1a9880a671539ef21
a = 0x4f77b72b04e6fb2d02e5a43edef4784a2e22df0d42bfc7c9093a58ec35eb21a11962103be960b0088d0cc2e0dfb473bc2ba0a22cea1c73997442c8fab5e4bad22cd131055b0382eb9264ad40ec8257abaff11b33b173ffd0168039bf40dc203eb325d884d2845fd2b5a37f41a0f64183db0c256c244500000000000000000000
k = a*e//n+1
hbits = 80

PR.<x,y> = PolynomialRing(Zmod(e*a))
f = 1 + k*(n-y) - e*x
bounds = (2^hbits,2^513)

res = small_roots(f,bounds,m=2,d=2)
print(res)

#res[0][2] is an approximate of p+q-1
#[(2540, 23935042650629633992243477175701638513817665297585812420605495051321315935163840064093820856826734951317982015362656048928090686340260908156176320805788498)]

同时，通过分析此种方法，可以知道这个方式可以拓展到私钥d未知LSB位数更多的情况，其理论求解上界就是p高位未知的求解上界，也就是p比特位数的一半。经测试，对于题目情况，理论上可以求解d低256bit未知的情况，下附测试脚本，其在d低235bit未知情况下依然快速且准确：

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
from Crypto.Util.number import *
from tqdm import *
import itertools


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

    R = f.base_ring()
    N = R.cardinality()
    
    k = ZZ(f.coefficients().pop(0))
    g = gcd(k, N)
    k = R(k/g)

    f *= 1/k
    f = f.change_ring(ZZ)

    vars = f.variables()
    G = Sequence([], f.parent())
    for k in range(m):
        for i in range(m-k+1):
            for subvars in itertools.combinations_with_replacement(vars[1:], i):
                g = f**k * prod(subvars) * N**(max(d-k, 0))
                G.append(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, Integer(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 []

e = 65537
p = getPrime(512)
q = getPrime(512)
n = p*q
phi = (p-1)*(q-1)
d = inverse(e,phi)
k = (e*d-1)//phi


hbits = 235
a = d >> hbits << hbits


PR.<x,y> = PolynomialRing(Zmod(e*a))
f = 1 + k*((n+1)-y) - e*x
bounds = (2^hbits,2^513)

res = small_roots(f,bounds,m=2,d=2)
print(res)
leak = int(res[0][1])


#part1 get leak2
PR.<x> = PolynomialRing(RealField(1000))
f = x*(leak-x) - n 
ph = int(f.roots()[0][0])


PR.<x> = PolynomialRing(Zmod(n))
f = ph + x
res = f.small_roots(X=2^(hbits+6), beta=0.499,epsilon=0.02)[0]
p = int(ph + res)
q = n // p
d = inverse(e,(p-1)*(q-1))
print("d =",d)
print("p =",p)
print("q =",q)
assert p*q == n



12

题目数据：

1
2
3
4
e12=65537
N12=0x9fac422a93f6e486e3ddae088bb5f5d06dec183ab81290042a9c98c53352961a00db3e9def7adff842381a395cedf1d06294f0b63457133e4e44cabb7633c562dcbfffdffe541d66c46ddf6a28b686c478300bcf31945f2a6495f140e64f78fa5cd47d1885233f175f28e38f1bfc422a6853ca19a7dd47a291a9e7de78a67bf1
c12=0x35476c9d0e5ad9d364ea31d8f6628b92a4f6307b1fef754e49286bc7f53ea8cd013a7ebf2a21b2327af44498d267e19526c2051a02f22cca9cab567f7ceefe5003137e396c23742370e14ec2c6a90943ca848908e87420f560d34eae4635475effa867722276710c6f4b6cb9b295777d62f3f03c57603ac815072864aadbf041
N=0x8199f8d487909988daf7d692ce8b1ffb4c37aa8010c8ca337ae4398c521383dc51007645cb6a1743c9b52ec5808e9e0e6f54d5fbb143cf81651240beab342dfb4622f073c4f8ab968dd5c8d4be3b7dd55c2cb9ef9c06294cd87e5fa29e38279c850f03687dc8c83c68104dca88e3a5c8559a01c040e7d5107e4a9f2385429f90

信息：

  • e=65537
  • 额外给出一个值N，N=kq+r，其中k的取值范围是$(2^{511},2^{512})$ ，r取值范围是$(2^{255},2^{256})$

显然是一个ACD(近似公约数)问题，然而由于只有这两个数据，所以直接造常见的格难以规约出目标向量，因此查找到文献：

ACD.dvi (iacr.org)

参照论文section5(Multivariate polynomial approach)的方式，记数据为：

可构造如下多个均以r1为根的模多项式去构造格：

其中，r1的bounds为$R = 2^{256}$，并且索引i1满足：

经测试，选取参数$t=20,k=10$，利用上述多项式去构造格，能够规约出的小根上界约为243bit，因此最终选择64进程爆破13bit并结合copper解决，耗时约3min。

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
from Crypto.Util.number import *
from tqdm import *
from itertools import *
from multiprocessing import Pool

################################################ gen data
e = 65537
N = 0x9fac422a93f6e486e3ddae088bb5f5d06dec183ab81290042a9c98c53352961a00db3e9def7adff842381a395cedf1d06294f0b63457133e4e44cabb7633c562dcbfffdffe541d66c46ddf6a28b686c478300bcf31945f2a6495f140e64f78fa5cd47d1885233f175f28e38f1bfc422a6853ca19a7dd47a291a9e7de78a67bf1
c = 0x35476c9d0e5ad9d364ea31d8f6628b92a4f6307b1fef754e49286bc7f53ea8cd013a7ebf2a21b2327af44498d267e19526c2051a02f22cca9cab567f7ceefe5003137e396c23742370e14ec2c6a90943ca848908e87420f560d34eae4635475effa867722276710c6f4b6cb9b295777d62f3f03c57603ac815072864aadbf041
m = 1
rho = 243
a = ["pad"] + [0x8199f8d487909988daf7d692ce8b1ffb4c37aa8010c8ca337ae4398c521383dc51007645cb6a1743c9b52ec5808e9e0e6f54d5fbb143cf81651240beab342dfb4622f073c4f8ab968dd5c8d4be3b7dd55c2cb9ef9c06294cd87e5fa29e38279c850f03687dc8c83c68104dca88e3a5c8559a01c040e7d5107e4a9f2385429f90]


def attack(ii):
    a = ["pad"] + [0x8199f8d487909988daf7d692ce8b1ffb4c37aa8010c8ca337ae4398c521383dc51007645cb6a1743c9b52ec5808e9e0e6f54d5fbb143cf81651240beab342dfb4622f073c4f8ab968dd5c8d4be3b7dd55c2cb9ef9c06294cd87e5fa29e38279c850f03687dc8c83c68104dca88e3a5c8559a01c040e7d5107e4a9f2385429f90 - 2^243*ii]

    ################################################ params
    t,k = 20,10
    R = 2^rho
    indices = []
    for i in product([i for i in range(t+1)] , repeat=m):
        if(sum(list(i)) <= t):
            indices.append(["pad"] + list(i))


    ################################################ attack
    PR = ZZ[tuple(f"X{i}" for i in range(m))]
    X = ["pad"] + list(PR.gens())
    poly = []
    monomials=set()
    for i in indices:
        f = 1
        for ij in range(1,len(i)):
            f *= (X[ij] - a[ij])^i[ij]
        l = max(k-sum(i[1:]),0)
        f *= N^l
        poly.append(f)
        for mono in f.monomials():
            monomials.add(mono)


    ################################################# LLL and resultant to find roots
    L = Matrix(ZZ,len(poly),len(monomials))
    monomials = sorted(monomials)
    for row,shift in enumerate(poly):
        for col,monomial in enumerate(monomials):
            L[row,col] = shift.monomial_coefficient(monomial)*monomial(*([R]*m))


    res = L.LLL()
    vec1 = res[0]

    h = 0
    for idx,monomial in enumerate(monomials):
        h += (vec1[idx] // monomial(*([R]*m))) * monomial
    h = h.change_ring(ZZ)
    res1 = h.monic().roots()

    if(res1 != []):
        print(ii,res1)

lists = [i for i in range(2^13)]
with Pool(64) as pool:
    r = list(pool.imap(attack, lists[::-1]))


#7827 [(2727306697565320519371211661141555049815806719986025448322625067833341383, 1)]



第二部分——随机数生成器分析

这个部分感觉意义不大，就看谁的脑洞更有道理了，最后知道是D.J. Bernstein的这篇论文中的周期性素数的变体：

https://eprint.iacr.org/2013/599.pdf

不太想研究这个方法具体是怎么回事，这里就讲一下我们队的脑洞吧。

首先，由于素数p内部有很明显的周期结构，所以很容易就能区分出两个素因子中哪一个是RNG生成的p，哪一个是完全随机的q，得到的所有RNG生成的p的具体数据如下：

1
2
3
4
5
6
7
8
9
10
11
12
p1 = 11731831938699772462127271873430115361544445093018344205508116263256543526314353604701640010896040499228777875913175294497034647460453248703129442880389173
p2 = 11869583389521634999588895814931899209282833085315990491955438271004312624703796644214104875335462616923607689499528893181399330078966918201596985360139071
p3 = 13330845672573024992365639486752475385999567065045919858101721586084914271256015026405358632247506825358937845584228131670535560699881432539142260730819941
p4 = 13356226842357346737299091759568737514939276729394541933682607177699916097721417538518090968081806167054821348691588113727076061555620082009933657711769897
p5 = 11797427867662564146182859301962255785374906066890850699284196012236748859126205065537843301272358073955564140004170138426605342997392924076900907292525053
p6 = 11833356611593562341229096501593508761656941850083383088968539373645279952186053495258337344120872950675089393986589783361936057299170335249974124458348637
p7 = 13204460550157942878056813628171921855910516854422240597500159684956753622537766390184760454941785574216947386843201357603678055340797551538526069521464359
p8 = 13315973629394688741750834853401728156006855695593283379566321523012211881375220806451907810948637676359456552867934749729358048834207948267102347900846147
p9 = 13230698921743059551824416344443899403552566005548844066885308262194945624798691552085027494542401017580805838924364362875395655984648652258879913619766611
p10 = 11771189496077447472415256585690278237732856915764247194903035840506904720003320569381951682128930227151469309640903353145013377646752106391473373652877601
p11 = 12625904132876024391053747255529472882205295003498735138849760876178996107401873371263341157195294988792537890500933341025075865608380995322266553378244827
p12 = 13332483168606238737181696873100104751420317885066608062141583458038224144727215840015557177200814570451949655836044414422384438369627145548625958519764109

把他们的二进制打印出来观察，可以发现以下几个显著特征：

  • 高三位都是111
  • 中间位有明显周期结构，但是有部分比特翻转
  • 最后一些比特比较杂乱

那么接下来就逐个分析这些特点。

1.周期结构

观察所有数字的中间位，可以看出很明显的分成了三类：

  • 循环节全是0的，这一部分包含素数为p1
  • 最小循环节长9的，这一部分包含素数有p2,p5,p7,p8,p9,p10
  • 最小循环节长11的，这一部分包含素数有p3,p4,p6,p11,p12

而”循环节“这个说法并不是说他们真的完全在以这个长度循环，而是一个能看出节长的最小单位，真正存在的周期其实是由多个循环节一起构成的，我们称为类周期，举两个例子如下：

长9的循环节的类周期：

image-20240826154329895

长11的循环节的类周期：

image-20240826154345916

对于以p2为例的节长为9的素数，将其第一个节称为a，第四个节称为b，很显然它呈现一个的规律：3a-4b-3a-4b-…

而对于以p3为代表的节长为11的素数，我们的实现思路是将第一个节的前7bit与后4bit拆分开来，令它们为t1和t2，将第一个节往左循环移位两位后的前7bit与后4bit拆分开来，令它们为t3和t4，此时所有的节都可以使用以下几个式子来进行表示，并且仍然是有周期性的：

这里的加号是比特串的连接的意思

记9和11的比特串构造式分别为C9和C11，就可以把两种类周期分别通过统一的表达式表示出来：

1
2
3
4
5
6
7
C9 = '111' + 8(3a+4b) + '00000'

C11 =  '111'
     + 2[2(t1+t2) + (t1+t4) + 2(t3+t4) + (t3+t2)]
     + 2[2(t1+t2) + 3(t3+t4) + (t1+t2)]
     + 3[(t1+t2) + (t1+t4) + 2(t3+t4) + (t3+t2) + (t1+t2)]
     +  [(t1+t2) + (t1+t4) + 2(t3+t4)]

以此为类周期构造，就可以恢复素数p的雏形。


2.比特翻转

刚刚的周期结构恢复的只是雏形，可以发现利用这个周期结构去构造素数的话，有很少量的比特是对不上的，这就是比特翻转。

而处理这个比特翻转的依据主要有以下两个：

  • p1代表的素数完全没有比特翻转(虽然他在2^16的位置存在一个1，这个的用处马上讲)
  • 剩余的一共有11组数据，而种子明确告诉我们是在0-2048，也就是11bit

很容易确定的一个事实是：p1对应的种子肯定是0。而p1没有比特翻转，说明比特翻转很可能是关于种子11个bit位的线性关系式

而刚刚提出的第二点正好可以佐证整个想法的，由于剩余的刚刚好是11组数据，因此对于11bit的种子来说，恰好能够求出这个线性关系的唯一解。

此时还面临着两个问题：

  • 每个素数的哪些比特位才是这个线性关系作用的结果？
  • 每个素数究竟对应哪个11bit的种子？

对于第一个问题，由刚才的分析可以知道，高三位既然都是111，所以是不参与线性方程中的，因此线性关系的求解应该从第4位开始。

那么到哪里结束呢？p1在2^16的位置存在一个1，这就显然是一个重要提示了。由于p1种子为全0，所以参与线性方程的部分理应也是全0，那么这个1就是一个信号，这个1左边的部分才参与线性方程，而右边的部分只用于nextprime。所以参与线性方程的比特范围就确定下来了。

接下来是第二个问题——每个素数究竟对应什么种子，循环节长度为11的倒还好，关键是循环节长为9的，究竟是去除了哪两个bit，这很值得商榷。

然而有个很重要的信息是：既然两种循环节以不同的长度循环着，那么它们对应的种子一定有一个可以区分的特征，这才使得循环长度不同。那么既然我们拥有循环节长度为11的几个素数p3,p4,p6,p11,p12的种子，那么我们不妨观察一下他们种子比特串的共同特征：

1
2
3
4
5
11110100001
11111000000
00001111100
10001000100
11110100011

可以看出一个相当明显的共同特征是：这些种子的2-4bit是三个完全相同的值，那么我们将长为9的循环节填至11的原则也就确定了：在2、3bit插入数据，让他们不符合这个特征即可。


3.完整步骤

此时得到了全部的种子，也就可以解线性关系式了，最终生成素数的全步骤为：

  • 初始化一个512bit的全0串
  • 最高三位填1
  • 检查种子2-4bit，如果完全相同则保留整个种子，否则删去2bit
  • 根据上一步处理得到的长度，分别应用长9和长11的构造式C9、C11得到素数雏形
  • 在[4,-16]的比特范围应用线性关系，产生比特翻转应用于当前的素数雏形上，再将倒数第十六位比特翻转
  • 取nextprime得到最终素数

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
168
from tqdm import *

p1 = 11731831938699772462127271873430115361544445093018344205508116263256543526314353604701640010896040499228777875913175294497034647460453248703129442880389173
p2 = 11869583389521634999588895814931899209282833085315990491955438271004312624703796644214104875335462616923607689499528893181399330078966918201596985360139071
p3 = 13330845672573024992365639486752475385999567065045919858101721586084914271256015026405358632247506825358937845584228131670535560699881432539142260730819941
p4 = 13356226842357346737299091759568737514939276729394541933682607177699916097721417538518090968081806167054821348691588113727076061555620082009933657711769897
p5 = 11797427867662564146182859301962255785374906066890850699284196012236748859126205065537843301272358073955564140004170138426605342997392924076900907292525053
p6 = 11833356611593562341229096501593508761656941850083383088968539373645279952186053495258337344120872950675089393986589783361936057299170335249974124458348637
p7 = 13204460550157942878056813628171921855910516854422240597500159684956753622537766390184760454941785574216947386843201357603678055340797551538526069521464359
p8 = 13315973629394688741750834853401728156006855695593283379566321523012211881375220806451907810948637676359456552867934749729358048834207948267102347900846147
p9 = 13230698921743059551824416344443899403552566005548844066885308262194945624798691552085027494542401017580805838924364362875395655984648652258879913619766611
p10 = 11771189496077447472415256585690278237732856915764247194903035840506904720003320569381951682128930227151469309640903353145013377646752106391473373652877601
p11 = 12625904132876024391053747255529472882205295003498735138849760876178996107401873371263341157195294988792537890500933341025075865608380995322266553378244827
p12 = 13332483168606238737181696873100104751420317885066608062141583458038224144727215840015557177200814570451949655836044414422384438369627145548625958519764109

f1 = [1,2,5,7,8,9,10]
f2 = [3,4,6,11,12]

PD = []
def Possible_Construction_1(t):
    '''
    t : p头部111后的前9个bit
    '''
    tt = '111'+8*(3*t+4*(t[-1]+t[:-1]))+'00000'
    
    return tt

def Possible_Construction_2(p1,p2):
    '''
    p1: p循环节前11个bit中的前7bit
    p2: p循环节前11个bit中的后4bit
    '''
    phead = p1[:2]
    p3,p4 = p1[2:]+p2[:2],p2[2:]+p1[:2]
    tt = '111'+2*(2*(p1+p2)+(p1+p4)+2*(p3+p4)+(p3+p2))+2*(2*(p1+p2)+3*(p3+p4)+(p1+p2))+3*((p1+p2)+(p1+p4)+2*(p3+p4)+(p3+p2)+(p1+p2))+(p1+p2)+(p1+p4)+2*(p3+p4)+'000'
    return tt

Lst = []
Lf2st = []


'''
给出初始化的种子列表Lst,初始化的噪音列表PD
'''
for k in range(1,12):
    if k+1 in f1:
        p = eval(f'p{k+1}')
        pp = bin(p)[2:]
        p0 = pp[3:12]
        tt = Possible_Construction_1(p0)

        pd = []
        for i in range(502):
            if pp[i] != tt[i]:
                pd.append(i)
        Lst.append([int(i) for i in p0])
    else:
        p = eval(f'p{k+1}')
        pp = bin(p)[2:]
        p_1,p_2 = pp[3:10],pp[10:14]
        tt = Possible_Construction_2(p_1,p_2)
        print(int(tt,2),k+1,p_1,p_2)

        pd = []
        for i in range(502):
            if pp[i] != tt[i]:
                pd.append(i)
        Lst.append([int(i) for i in p_1+p_2])
        Lf2st.append([int(i) for i in p_1+p_2])
    PD.append(pd)


'''
对9bit区的种子矩阵进行修正，爆破11×11的完整种子矩阵
'''
def Get_4ll_Construction(Lst,seq):
    LLst = []
    t = 0
    
    for i in range(1,12):
        if i+1 in f1:
            LLst.append([Lst[i-1][0]]+seq[t*2:t*2+2]+Lst[i-1][1:])
            t += 1
        else:
            LLst.append(Lst[i-1])

    return LLst


'''
解线性关系
'''
bl = 509
P = matrix(11,bl+1)
index = 0
for i in range(11):
    for j in range(bl):
        if j in PD[i]:
            P[i,j] = 1
        else:
            P[i,j] = 0

PC = []
for i in P.columns():
    if i:
        PC.append(list(i))
PC = matrix(PC)

P[4,-8] = 1
P[4,-7] = 1
P[4,-6] = 1
P[6,-8] = 1


for _ in trange(2^12):
    ctrl = [0,0,1,1,1,0]
    seq = [int(i) for i in bin(_)[2:].zfill(12)]
    flag = 0
    for i in range(6):
        if 1-ctrl[i] not in seq[2*i:2*i+2]:
            flag = 1
    if flag == 1:
        continue

    LLst = Get_4ll_Construction(Lst,seq)

    LLst = matrix(GF(2),LLst).T

    try:
        LLst.solve_left(PC)        
    except:
        continue
    LLst = LLst.T
    print(P.nrows(),P.ncols(),LLst.nrows(),[int(i) for i in bin(_)[2:].zfill(12)])
    C = LLst.solve_right(P)
    print(LLst)
    #C:解矩阵，用种子向量与之相乘就能够得到噪音向量

    '''
    for i,j in zip(Lst,LLst.T):
        print(j,'1' if len(i) == 9 else '2')
        print(i)
    '''
        
    for i in range(11):
        a = (matrix(LLst[i])*C)[0]
        a = ''.join([str(i) for i in list(a)])
        t = []
        for j in range(502):
            if a[j] == '1':
                t.append(j)
        #print(t)
        #print(PD[i])
        seed = ''.join([str(j) for j in list(LLst[i])])
        if seed[1:4] not in ['111' , '000']:
            p = Possible_Construction_1(seed[0:1]+seed[3:11])
        else:
            p = Possible_Construction_2(seed[0:7],seed[7:11])
            #print(seed[0:7],seed[7:11])

        p = int(p,2)
        p ^^= int(a.ljust(512,'0'),2)
        #print((seed[1:4] not in ['111' , '000']) , (i+2 in f1),seed,i+2,seed[1:4])
        #print(p)
        #print(eval(f'p{i+2}'))
        print(eval(f'p{i+2}')-p,next_prime(p) == eval(f'p{i+2}'))
    print(ans)
    break

4.缺陷

但是这个RNG显然并不成熟，比较大的两个缺陷是：

  • 在由长9的循环节反推种子这一步，显然有多种插入数据都会符合2-4bit不完全相同的要求，我们的做法是随便取其中一组，这显然不够有说服力
  • 最后的线性关系虽然可以唯一求解，但是将这个线性关系应用于其他种子的素数生成的话，有个明显的弊端：他们的比特翻转数量无法控制



第三部分——游记

这个总结并不是对整个wp的总结，而是总结一下这次比赛经过。这次参赛体验真的一点都不好，体现在很多方面：

第一点就是，主办方不报销路费以及住宿费，我们三个是跨校组队，指导老师也是随便挂个名，所以也没法找自己学校报销，就只能自费了，而路费、酒店费很容易就上千，真的肉疼。同时比赛的奖金虽然不能说低，但肯定也不高。除去我们肯定拿不到的特等奖以外，一等奖一万一个队伍，二等奖五千一个队伍，三等奖一千一个队伍。并且事先就知道百分之六七十的队伍都是拿三等奖的，就算是拿了二等奖，都还补不够路费、住宿费的开销。所以等于是完全亏钱来找罪受了，因此开始真的很纠结。

唯一包的吃还是山大食堂的餐券XD，虽然说味道确实还可以

这个时候才体会到，一个线下赛如果要自己掏钱参加的话，真的会很打击比赛的热情。


第二点，对于住宿的酒店，本来主办方是安排住在青岛美爵酒店的。这个酒店相当好，主办方也和酒店谈了房间协议价的，应该是三百多。

然而，然而，主办方最后没有谈到足够所有参赛队伍入住的协议价房间，所以剩下的没抢到房间的队伍只能预订开在旁边的一家海悦度假公寓——这个度假公寓是新开的，性质更类似于业主自己营业的民宿。

住进去的感觉真的很差：空调效果不好、热水也不好、地板很脏、虫子也多，并且肯定没有仔细打理过，因为每个柜子里面都是一些放了很久的杂物，甚至卫生间的纸都长霉了。而最重要的一点是，入住价格居然和美爵酒店花的差不多，真的很无语。

早饭也很一般，住在美爵的师傅们早上应该可以酒店餐厅里吃自助，而我们说是会送饭到每个人的房间，结果第二天一早让我们自己去另外一层楼的房间拿早饭。早饭也很简陋——杯装的粥、鸡蛋和油条，都已经有一点点冷了，而且最重要的是压根没有地方让我们坐下来吃，我们只能直接提走到楼下再想办法。

此外就是酒店位置实在太偏太偏，我还记得第一天下午到酒店的时候问了问@Lvsun去哪吃饭，他告诉我点个最近的外卖都要一个多小时的心情。为了吃顿晚饭，需要自己先走二十多分钟去博览中心地铁站，然后坐地铁去山大外面的街上觅食，一趟来回两三个小时就没了。

可以说，这次青岛之行，关于比赛的几乎所有部分体验感都很差很差，如果让我回头选一次的话，是肯定不会来了。


但是反过来想，如果去除掉比赛、去除掉花钱这部分，这次青岛之行还是挺不错的。首先就是头一次在线下见到了@deebato、@hash_hash、@Shin这几个师傅，也认识了自己素未谋面的队友@yolbby和@三顺七，算是社恐飞跃般迈出的重大一步。然后就是第二天比赛完，晚上和yolbby去山大外面吃了顿海鲜烧烤，分量真的很足，我们边吃边聊从八点多吃到快十一点，听yolbby讲了很久他精彩又离奇的大学生活(相比起来我大学过的也太平淡了)。


此外就是答辩完的当天下午，为了给这次比赛留下点旅游的记忆，我坐地铁去了五四广场。

以下图都是手机随手拍的，不好看轻喷，我对摄影本来也一窍不通(⌒ω⌒)

三点多出发，到的时候五点多了，但是人还是不少：

img

走几步路之后右转就能看见五四广场的标志性雕塑”五月的风”了，凑近拍了一张：

img

再走几步路就到了海边了，海上有很多渡轮和帆船，在四川是从来见不到的：

img

img

下一个想去的地方是八大关，那里离这里还有好几公里，我就一直沿着海边这条路向那边慢慢走。这个时候太阳已经退下去了很多，时不时有傍晚的海风吹在脸上，突然就有不少因素触动心弦——没来过的城市、独自旅行、最近几个月经历的很多烦心事，再加上近在咫尺的望不到尽头的海，我不知道怎么就想到了一些很多年没有见到过的人，这种感受很微妙。

八大关的方向是一直向西边走，所以不刺眼的夕阳一直在我的前面勾勒着高楼的轮廓，更加深了这种复杂的感觉：

img

走了一会儿之后发现前面围了很多人，细看发现是包围圈的中间是一些大叔大爷在排队跳海，虽然之前看过天津某个桥上大爷排队跳水的报道，但是这种事情头一次在现实里出现在自己面前还是感觉很新奇——而且这可是跳海XD：

img

img

img

img

我一直走，到了更空旷、人更少的一段路的时候，我突然就想到了高中的时候全班在音乐课上一起看的爱乐之城，想了想却觉得没有哪个场景和我看到的这一幕相像。我也不知道我是想到了那一部电影还是想到了我的高中生活。

img

img

走着走着到了就到了一个人特别多特别多的地方，应该是个海水浴场：

img

img

img

img

我就这么一直走了两个小时左右，走到了八大关。但是到了地方，我却没看出来到底我要看些什么风景，正好这时候yolbby告诉我说他很饿了，我就去找地铁站赶往山大了。

写到这里突然很想说几句感性的话，因为海和山带给人的感觉不一样，爬了很多次山，都没有过这次沿海边走两小时的心情。上一次去海边已经是小学的事情了，当时和爸妈一起去了秦皇岛，人比较小，除了旅行的开心之外，没有什么别的感受；之后18年初中刚毕业的时候和父母旅行，来了一次上海，但是没有去海边玩；再之后是21年，高中毕业了来上海上大学，但在上海待了快三年了也没有去过一趟海边；再之后就到现在了，终于又一次看见了海。

海让我觉得广阔，但是也让我觉得很不轻松——也许是因为海太广阔了吧。

img