分区赛

题不难,要查找信息and稳住心态

dual

前一部分是要用xy求椭圆曲线的生成参数;

后一部分是NSA的后门,是一个随机数发生器,用一系列貌似随机的数和椭圆上的点做乘积,最后输出低240位作为每一轮的结果。因为P, Q是固定的,椭圆曲线的参数也是固定的,P、Q之间必然存在一个线性关系,那么就用这个线性关系去预测下一次的结果。

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
from pwn import *
from Crypto.Util.number import *
from sys import stdout
from fastecdsa.curve import P256
from fastecdsa.point import Point
from Crypto.Cipher import AES
from tqdm import trange

VERBOSE = True

G = P256.G

def pad(s):
return s + (16 - len(s) % 16) * b"\x00"

class PRNG:
def __init__(self, e, seed):
self.state = seed
self.Q = e * G
self.P = G
self.mask = 2**240 - 1

def gen(self):
new_point = self.state * self.P
r = new_point.x
self.state = r
ret = r * self.Q
return ret.x & self.mask

def p256_mod_sqrt(c):
p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
t1 = pow(c, 2, p)
t1 = (t1 * c) % p
t2 = pow(t1, 2**2, p)
t2 = (t2 * t1) % p
t3 = pow(t2, 2**4, p)
t3 = (t3 * t2) % p
t4 = pow(t3, 2**8, p)
t4 = (t4 * t3) % p
r = pow(t4, 2**16, p)
r = (r * t4) % p
r = pow(r, 2**32, p)
r = (r * c) % p
r = pow(r, 2**96, p)
r = (r * c) % p
return pow(r, 2**94, p)

def find_point_on_p256(x):
# equation: y^2 = x^3-ax+b
y2 = (x * x * x) - (3 * x) + P256.b
y2 = y2 % P256.p
y = p256_mod_sqrt(y2)
return y2 == (y * y) % P256.p, y

class Solve:
def __init__(self) -> None:
self.conn = remote('192.168.0.64', 58010)
self.n = 15

def s_3(self):
self.conn.sendlineafter('>', '3')

x0 = eval(self.conn.recvline())
x = eval(self.conn.recvline())
y = eval(self.conn.recvline())
x1 = x[:self.n]
x2 = x[self.n:]
p_list = []
PR = PolynomialRing(Zmod(x0), 'x')
x_ = PR.gen()
f = x_ + y
sol = f.small_roots(X=2**20, beta=1./20)
p_list = [ZZ(gcd(t + y, x0)) for t in sol]
print(len(p_list))
e = min(p_list)
# print(set(p0) == set(p_list))
return e


def gen_prediction(self, observed, Q, d):
ret = []
for high_bits in trange(2**15): # 2**16: have sol, 2**15: 1/2 prob
guess = (high_bits << (8 * 30)) | observed
on_curve, y = find_point_on_p256(guess)

if on_curve:
# use the backdoor to guess the next 30 bytes
point = Point(guess, y, curve=P256)
s = (d * point).x
r = (s * Q).x & (2**(8 * 30) - 1)
ret.append(r)

return ret

def s_pred(self, e):
d = int(inverse(e, P256.q))
Q = e * G
self.conn.sendlineafter('>', '1')
observed = eval(self.conn.recvline())
# print(guess)
# pred = eval(self.conn.recvline())
# print(pred)
predicted = self.gen_prediction(observed, Q, d)
# print(len(predicted))
# print(pred in predicted)

return predicted

def s_2(self, pred):
self.conn.sendlineafter('>', '2')
self.conn.recvuntil('ct: ')
ct = self.conn.recvline().strip()
ct = base64.b64decode(ct)
for nx in pred:
key = pad(long_to_bytes(nx))
cipher = AES.new(key, AES.MODE_ECB)
pt = cipher.decrypt(ct)
if (all(64 < x < 128 for x in pt)):
print(pt)
self.conn.sendlineafter('pt:', base64.b64encode(pt))
self.conn.interactive()
return True
else:
self.conn.close()
return False

def s(self):
e = int(self.s_3())
pred = self.s_pred(e)
if (pred == 0):
self.conn.close()
return False
is_success = self.s_2(pred)
return is_success

if __name__ == '__main__':
while True:
print('Begin try...')
s = Solve()
is_success = s.s()
if (is_success):
break
print('Failed')

因为环境问题最后在队友电脑上出的--

RSA

送分

1
2
3
4
5
6
7
8
9
10
from Crypto.Util.number import *
import gmpy2
from hashlib import md5

lcm = 4292158730589770192682795435047249488185453170529228019750042608688907718268448193363838203887391025871515871000364259326343790645215256385842265899206372365402431198699714374850409466996627163968391249416054093529090485677808301343590811445080871279796162536469847469761747058736980603093722710824453312207182881241846080117790728778291633761198069016865260030288832065807438020772711645648333908622890343009942617559434851450007195025869850769670769715654662127278293639938359741401336592219730356884542179574372134014927006215640945952229142436595334916765255426954857520777553915330597952622785359222832224632624
c = 4288727484183191191687364666620023549392656794153112764357730676861570386983002380982803054964588111708662498647767438881892355599604826306427809017097724346976778230464708540600157055782723189971534549543664668430013171469625043063261219462210251726207552819381767396148632877168530609902046293626355744288863460554297860696918890189350721960355460410677203131993419723440382095665713164422367291153108363066159712951217816814873413423853338021627653555202253351957999686659021298525147460016557904084617528199284448056532965033560516083489693334373695545423561715471204868795248569806148395196572046378679014697206
N = 17168634922359080770731181740188997952741812682116912079000170434755630873073792773455352815549564103486063484001457037305375162580861025543369063596825489461609724794798857499401637867986508655873564997664216374116361942711233205374363245780323485119184650145879389879046988234947922412374890843297813248828996855478005656041814919367820336728271583686844991928889831691815821365423570311291064846736832327637944358854661523107817781673029406341843040857813841671405147146887291204140157388049394514390098066284975682117038362207142272098796924412602725857521665773622056312191400612944442008222587867782281556388669
E = 65537
d = gmpy2.invert(E, lcm)
print('flag{' + md5(long_to_bytes(pow(c,d,N))).hexdigest() + '}')