writeup for 2020 starCTF Crypto

Posted on Edited on In Word count in article: 30k Reading time ≈ 27 mins.

总之就是吃老本
总之就是曲线好难
这次就差一道MyCurve…找个师傅学习学习再补充这个

Crypto

  • MyEnc
  • GuessKey2
  • little case
  • MyCurve

MyEnc

nc 52.163.228.53 8081
附件:

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 Crypto.Util.number import getPrime,bytes_to_long
import time,urandom
from flag import flag
iv=bytes_to_long(urandom(256))
assert len(flag)==15
keystream=bin(int(flag.encode('hex'),16))[2:].rjust(8*len(flag),'0')
p=getPrime(1024)
q=getPrime(1024)
n=p*q
print "n:",n
cnt=0
while True:
	try:
		print 'give me a number:'
		m=int(raw_input())
	except:
		break
	ct=iv
	for i in range(1,8):
		if keystream[cnt]=='1':
			ct+=pow(m^q,i**i**i,n)
			ct%=n
		cnt=(cnt+1)%len(keystream)
	print "done:",ct


stream cipher的味道
flag 即 keystream 共120位
每次输入一个m , 根据key的7位返回一个ct
第1个m对应key的0~6
第2个m对应key的7~13
…
第17个m对应key的112~118
第18个m对应key的119~5
…
120个m则会回到刚开始一样

而重复传同样的m的时候, 如果取key的7位是相同的, 那么返回的ct也是相同的, 根据这个特点, 重复传120个m=0, 可以得到一些返回相同ct的7位, 也就是key里面相同的两个7位

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
from pwn import *
from hashlib import sha256
import re

printable = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'

con = remote('52.163.228.53', 8081)


def proof(END, SHA):
    for i in printable:
        for j in printable:
            for k in printable:
                for l in printable:
                    start = i + j + k + l
                    ensha = sha256((start + END).encode()).hexdigest()
                    if ensha == SHA:
                        print(start)
                        return start.encode()


resp = con.recvuntil('xxxx:').decode()
END = re.findall(r'xxxx\+(.*)\) ==', resp)[0]
SHA = re.findall(r'== (.*)', resp)[0]
print(resp)
resp = con.recv().decode()
print(resp)
con.sendline(proof(END, SHA))

resp = con.recvuntil('number:').decode()
print(resp)

arr = []
for _ in range(120):
    con.sendline('0'.encode())
    resp = con.recvuntil('number:').decode()
    num = int(resp[6:-17])
    if num not in arr:
        arr.append(num)
    else:
        arr.append(-1)
        print(_, arr.index(num))

得到的输出为:

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
15 12
26 14
32 1
37 9
43 31
52 51
54 14
60 48
69 58
71 31
76 39
77 65
80 8
81 38
82 48
85 63
86 31
88 48
90 7
92 17
93 56
94 2
96 64
98 70
99 0
100 12
103 48
104 12
105 65
106 49
110 73
112 72
114 78
115 87
117 29
118 83

第一行的15 12代表着, key的15 7~15 7+6 == 12 7~12 7+6
也就是key[105:112] == key[84:91]
每一行都能构造出这么一个等式

根据所有等式, 可以将后面的一些位数用前面的位数表示(他们都是相等的)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
arr = [15, 12, 26, 14, 32, 1, 37, 9, 43, 31, 52, 51, 54, 14, 60, 48, 69, 58, 71, 31, 76, 39, 77, 65, 80, 8, 81, 38, 82,
       48, 85, 63, 86, 31, 88, 48, 90, 7, 92, 17, 93, 56, 94, 2, 96, 64, 98, 70, 99, 0, 100, 12, 103, 48, 104, 12, 105,
       65, 106, 49, 110, 73, 112, 72, 114, 78, 115, 87, 117, 29, 118, 83]

key = [i for i in range(120)]


for _ in range(1000):
    for i in range(0, len(arr), 2):

        for (j, k) in zip(range((arr[i + 1] * 7), (arr[i + 1] * 7 + 7)), range((arr[i] * 7), (arr[i] * 7 + 7))):
            if key[j % 120] < key[k % 120]:
                key[k % 120] = key[j % 120]
            else:
                key[j % 120] = key[k % 120]
print(key)

然后! 就能把key还原成:
1
[0, 0, 2, 0, 2, 0, 2, 0, 0, 2, 0, 0, 0, 0, 2, 2, 0, 2, 0, 2, 0, 2, 0, 0, 0, 2, 0, 0, 0, 2, 2, 0, 0, 2, 34, 35, 36, 0, 2, 2, 40, 41, 42, 43, 2, 0, 0, 2, 0, 2, 0, 0, 2, 34, 35, 36, 0, 2, 2, 2, 0, 2, 0, 2, 0, 2, 0, 0, 0, 2, 2, 2, 0, 0, 2, 2, 0, 0, 0, 0, 0, 2, 2, 2, 0, 2, 0, 0, 0, 0, 2, 2, 0, 0, 0, 2, 0, 2, 0, 2, 0, 2, 0, 0, 0, 0, 2, 0, 0, 0, 0, 2, 0, 113, 114, 2, 2, 2, 0, 2]

0和2分别代表着1或者0(不确定是0对应1还是2对应1
而其他的比较大的数则是未知的, 一共12位,
所以只需要爆破2^12次, 然后再猜一下0对应的是1还是0
这里直接猜0对应0, 中啦!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
for i in range(len(key)):
    if key[i] == 0:
        key[i] = '0'
    elif key[i] == 2:
        key[i] = '1'
    else:
        key[i] = '{}'

key = ''.join(key)

from MyCrypto.Conversion import bin2text
for i in range(2 ** 12):
    pad = bin(i)[2:].zfill(12)
    keystream = key.format(pad[0], pad[1], pad[2], pad[3], pad[4], pad[5], pad[6], pad[7], pad[8], pad[9], pad[10], pad[11])
    flag = bin2text(keystream)
    if flag[0] == '*' and flag[-1] == '}' and '{' in flag:
        print(flag)

得到的输出:
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
*CTF{	HuG0t1T!}
*CTF{	IuG0t1T!}
*CTF{	JuG0t1T!}
*CTF{	KuG0t1T!}
*CTF{	LuG0t1T!}
*CTF{	MuG0t1T!}
*CTF{	NuG0t1T!}
*CTF{	OuG0t1T!}
*CTF{HuG0t1T!}
*CTF{IuG0t1T!}
*CTF{JuG0t1T!}
*CTF{KuG0t1T!}
*CTF{LuG0t1T!}
*CTF{MuG0t1T!}
*CTF{NuG0t1T!}
*CTF{OuG0t1T!}
*CTF{)HuG0t1T!}
*CTF{)IuG0t1T!}
*CTF{)JuG0t1T!}
*CTF{)KuG0t1T!}
*CTF{)LuG0t1T!}
*CTF{)MuG0t1T!}
*CTF{)NuG0t1T!}
*CTF{)OuG0t1T!}
*CTF{9HuG0t1T!}
*CTF{9IuG0t1T!}
*CTF{9JuG0t1T!}
*CTF{9KuG0t1T!}
*CTF{9LuG0t1T!}
*CTF{9MuG0t1T!}
*CTF{9NuG0t1T!}
*CTF{9OuG0t1T!}
*CTF{IHuG0t1T!}
*CTF{IIuG0t1T!}
*CTF{IJuG0t1T!}
*CTF{IKuG0t1T!}
*CTF{ILuG0t1T!}
*CTF{IMuG0t1T!}
*CTF{INuG0t1T!}
*CTF{IOuG0t1T!}
*CTF{YHuG0t1T!}
*CTF{YIuG0t1T!}
*CTF{YJuG0t1T!}
*CTF{YKuG0t1T!}
*CTF{YLuG0t1T!}
*CTF{YMuG0t1T!}
*CTF{YNuG0t1T!}
*CTF{YOuG0t1T!}
*CTF{iHuG0t1T!}
*CTF{iIuG0t1T!}
*CTF{iJuG0t1T!}
*CTF{iKuG0t1T!}
*CTF{iLuG0t1T!}
*CTF{iMuG0t1T!}
*CTF{iNuG0t1T!}
*CTF{iOuG0t1T!}
*CTF{yHuG0t1T!}
*CTF{yIuG0t1T!}
*CTF{yJuG0t1T!}
*CTF{yKuG0t1T!}
*CTF{yLuG0t1T!}
*CTF{yMuG0t1T!}
*CTF{yNuG0t1T!}
*CTF{yOuG0t1T!}
*CTF{‰HuG0t1T!}
*CTF{‰IuG0t1T!}
*CTF{‰JuG0t1T!}
*CTF{‰KuG0t1T!}
*CTF{‰LuG0t1T!}
*CTF{‰MuG0t1T!}
*CTF{‰NuG0t1T!}
*CTF{‰OuG0t1T!}
*CTF{™HuG0t1T!}
*CTF{™IuG0t1T!}
*CTF{™JuG0t1T!}
*CTF{™KuG0t1T!}
*CTF{™LuG0t1T!}
*CTF{™MuG0t1T!}
*CTF{™NuG0t1T!}
*CTF{™OuG0t1T!}
*CTF{©HuG0t1T!}
*CTF{©IuG0t1T!}
*CTF{©JuG0t1T!}
*CTF{©KuG0t1T!}
*CTF{©LuG0t1T!}
*CTF{©MuG0t1T!}
*CTF{©NuG0t1T!}
*CTF{©OuG0t1T!}
*CTF{¹HuG0t1T!}
*CTF{¹IuG0t1T!}
*CTF{¹JuG0t1T!}
*CTF{¹KuG0t1T!}
*CTF{¹LuG0t1T!}
*CTF{¹MuG0t1T!}
*CTF{¹NuG0t1T!}
*CTF{¹OuG0t1T!}
*CTF{ÉHuG0t1T!}
*CTF{ÉIuG0t1T!}
*CTF{ÉJuG0t1T!}
*CTF{ÉKuG0t1T!}
*CTF{ÉLuG0t1T!}
*CTF{ÉMuG0t1T!}
*CTF{ÉNuG0t1T!}
*CTF{ÉOuG0t1T!}
*CTF{ÙHuG0t1T!}
*CTF{ÙIuG0t1T!}
*CTF{ÙJuG0t1T!}
*CTF{ÙKuG0t1T!}
*CTF{ÙLuG0t1T!}
*CTF{ÙMuG0t1T!}
*CTF{ÙNuG0t1T!}
*CTF{ÙOuG0t1T!}
*CTF{éHuG0t1T!}
*CTF{éIuG0t1T!}
*CTF{éJuG0t1T!}
*CTF{éKuG0t1T!}
*CTF{éLuG0t1T!}
*CTF{éMuG0t1T!}
*CTF{éNuG0t1T!}
*CTF{éOuG0t1T!}
*CTF{ùHuG0t1T!}
*CTF{ùIuG0t1T!}
*CTF{ùJuG0t1T!}
*CTF{ùKuG0t1T!}
*CTF{ùLuG0t1T!}
*CTF{ùMuG0t1T!}
*CTF{ùNuG0t1T!}
*CTF{ùOuG0t1T!}

还好小学读过英语, 根据语义猜测flag在*CTF{YOuG0t1T!}和*CTF{yOuG0t1T!}之中

猜猜是哪个呀

GuessKey2

关于出题人忘记把key注释掉多了一题GuessKey2那件事

nc 52.163.228.53 8080
附件

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
from random import randint
import os
from flag import flag
N=64
key=randint(0,2**N)
print key
key=bin(key)[2:].rjust(N,'0')
count=0
while True:
	p=0
	q=0
	new_key=''
	zeros=[0]
	for j in range(len(key)):
		if key[j]=='0':
			zeros.append(j)
	p=zeros[randint(0,len(zeros))-1]
	q=zeros[randint(0,len(zeros))-1]
	try:
		mask=int(raw_input("mask:"))
	except:
		exit(0)
	mask=bin(mask)[2:]
	if p>q:
		tmp=q
		q=p
		p=tmp
	cnt=0
	for j in range(0,N):
		if j in range(p,q+1):
			new_key+=str(int(mask[cnt])^int(key[j]))
		else:
			new_key+=key[j]
		cnt+=1
		cnt%=len(mask)
	key=new_key
	try:
		guess=int(raw_input("guess:"))
	except:
		exit(0)
	if guess==int(key,2):
		count+=1
		print 'Nice.'
	else:
		count=0
		print 'Oops.'
	if count>2:
		print flag

随机生成一个key, 输入mask, 每一轮都会随机的在key中取一段(开头结尾两位必定都是0), 然后与mask对应的一段异或(mask先重复填充成key长度).

题目让我们猜每一轮的key, 连续猜中3轮就能得到flag

可以看到只有输入mask才能改变key, 想到key中拿来跟mask异或的第一位必定是0, 如果最前面的0被改成了1, 那么它前面的位数和它本身就再也不会改变了, 利用这个特点, 可以疯狂传mask=1,让key的所有位数变成1, 当key变成全1之后, 传mask=0就能保持key不变了, 一直传guess=int('1'*64,2)就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from random import randint
from pwn import *

mask = '1'
key = '1'*64

mask = str(int(mask,2))
key = str(int(key,2))
print(mask)
print(key)

con = remote('52.163.228.53', 8082)
resp = con.recv().decode()
print(resp)
i = 0
while True:
    con.sendline(mask.encode())
    resp = con.recv().decode()
    con.sendline(key.encode())
    resp = con.recvuntil('mask:').decode()
    print(resp)
    if 'e' in resp:
        for _ in range(3):
            con.sendline('0'.encode())
            resp = con.recv().decode()
            con.sendline(key.encode())
            resp = con.recvuntil('mask:').decode()
            print(resp)
	break
    i += 1
    print(i)

大概跑个一两百轮?就能出结果了
1
*CTF{27d30dad45523cbf88013674a4b5bd29}

little case

总会有一道RSA的对吧?

附件:

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
from Crypto.Util.number import *
from libnum import *
from secret import flag,special,p,q,n


def little_trick(msg):
    p1 = getPrime(1024)
    q1 = getPrime(1024)
    n1 = p1 * q1
    d1=random.randint(1,2**256)
    e1=inverse(d1,(p1-1)*(q1-1))
    print(n1)
    print(e1)
    print(pow(msg,e1,n1))


def real_trick():
    assert (special > (ord("*")*100) and gcd(special,(p-1)*(q-1))!=1 )
    print(n)
    print(pow(libnum.s2n(flag),special,n))


if __name__ == '__main__':
    little_trick(p-1)
    real_trick()

'''
输出
21669699875387343975765484834175962461348837371447024695458479154615348697330944566714587217852888702291368306637977095490953192701450127798670425959768118384915082017373951315699899009631834471691811815393784748930880954114446745814058132752897827717077886547911476575751254872623927783670252969995075629255541621917767501261249192653546875104532649043219697616464205772025267019328364349763854659490144531087349974469079255236823096415094552037488277752927579909539401311624671444833332618177513356173537573280352724384376372955100031534236816681805396608147647003653628203258681097552049114308367967967184116839561

20717541468269984768938524534679430706714860712589983300712432366828367981392533792814384884126053081363266457682162675931547901815985830455612301105504518353600255693451085179954519939635263372257973143178677586338992274607959326361412487748088349413448526455377296931144384663805056580662706419414607407821761761574754611275621927387380065975844282519447660467416826579669726178901884060454994606177784839804528666823956703141147239309978420776148158425922031573513062568162012505209805669623841355103885621402814626329355281853436655713194649170570579414480803671531927080535374958180810697826214794117466378050607

17653913822265292046140436077352027388518012934178497059850703004839268622175666123728756590505344279395546682262531546841391088108347695091027910544112830270722179480786859703225421972669021406495452107007154426730798752912163553332446929049057464612267870012438268458914652129391150217932076946886301294155031704279222594842585123671871118879574946424138391703308869753154497665630799300138651304835205755177940116680821142858923842124294529640719629497853598914963074656319325664210104788201957945801990296604585721820046391439235286951088086966253038989586737352467905401107613763487302070546247282406664431777475

22346087036331379968192118389403047568445805414881948978518580277027027486284293415097623011228506968071753709256352246733181304513713003096615266613365080909760605498017330085960699607777361429562376124376340215426398797920168016137830563564636922257215066266075494625782943973857490781916694118187094786034792437781964601089843549995939887939410763350338658901108020658475956489391300528691289604149598720803012371765770928211044755626045817053870803040863722458554924076011151695567147976903053993914859714631837755435592006986598006207692599019026644753575853382810261910332197447386727419606073948645238377595719

12732299056226934743176360461051108799706450051853623472248552066649321279227693844417404789169416642586313895494292082308084823101092675162498154181999270703392144766031531668783213589136974486867571090321426005719333327425286160436925591205840653712046866950957876967715226097699016798471712274797888761218915345301238306497841970203137048433491914195023230951832644259526895087301990301002618450573323078919808182376666320244077837033894089805640452791930176084416087344594957596135877833163152566525019063919662459299054294655118065279192807949989681674190983739625056255497842063989284921411358232926435537518406
'''

一共两个问题吧

  1. 根据n1,e1以及pow(p-1,e1,n1)求p-1
  2. 根据上面的p, n 还有一些e有关的条件, 求flag

根据n1,e1以及pow(p-1,e1,n1)求p-1

e1够大, 直接上Boneh_Durfee, 直接拿github上面的脚本跑了(不想改了….

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
import time

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

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

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

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

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

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

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

""" 
Returns:
* 0,0   if it fails
* -1,-1 if `strict=true`, and determinant doesn't bound
* x0,y0 the solutions of `pol`
"""
def boneh_durfee(pol, modulus, mm, tt, XX, YY):
    """
    Boneh and Durfee revisited by Herrmann and May
    
    finds a solution if:
    * d < N^delta
    * |x| < e^delta
    * |y| < e^0.5
    whenever delta < 1 - sqrt(2)/2 ~ 0.292
    """

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

    UU = XX*YY + 1

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

    # x-shifts list of monomials
    monomials = []
    for polynomial in gg:
        for monomial in polynomial.monomials():
            if monomial not in monomials:
                monomials.append(monomial)
    monomials.sort()
    
    # y-shifts (selected by Herrman and May)
    for jj in range(1, tt + 1):
        for kk in range(floor(mm/tt) * jj, mm + 1):
            yshift = y^jj * polZ(u, x, y)^kk * modulus^(mm - kk)
            yshift = Q(yshift).lift()
            gg.append(yshift) # substitution
    
    # y-shifts list of monomials
    for jj in range(1, tt + 1):
        for kk in range(floor(mm/tt) * jj, mm + 1):
            monomials.append(u^kk * y^jj)

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

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

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

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

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

    BB = BB.LLL()

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

    # transform vector i & j -> polynomials 1 & 2
    if debug:
        print ("looking for independent vectors in the lattice")
    found_polynomials = False
    
    for pol1_idx in range(nn - 1):
        for pol2_idx in range(pol1_idx + 1, nn):
            # for i and j, create the two polynomials
            PR.<w,z> = PolynomialRing(ZZ)
            pol1 = pol2 = 0
            for jj in range(nn):
                pol1 += monomials[jj](w*z+1,w,z) * BB[pol1_idx, jj] / monomials[jj](UU,XX,YY)
                pol2 += monomials[jj](w*z+1,w,z) * BB[pol2_idx, jj] / monomials[jj](UU,XX,YY)

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

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

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

    # solutions
    soly = rr.roots()

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

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

    #
    return solx, soly

def example():

    N = 21669699875387343975765484834175962461348837371447024695458479154615348697330944566714587217852888702291368306637977095490953192701450127798670425959768118384915082017373951315699899009631834471691811815393784748930880954114446745814058132752897827717077886547911476575751254872623927783670252969995075629255541621917767501261249192653546875104532649043219697616464205772025267019328364349763854659490144531087349974469079255236823096415094552037488277752927579909539401311624671444833332618177513356173537573280352724384376372955100031534236816681805396608147647003653628203258681097552049114308367967967184116839561
    # the public exponent
    e = 20717541468269984768938524534679430706714860712589983300712432366828367981392533792814384884126053081363266457682162675931547901815985830455612301105504518353600255693451085179954519939635263372257973143178677586338992274607959326361412487748088349413448526455377296931144384663805056580662706419414607407821761761574754611275621927387380065975844282519447660467416826579669726178901884060454994606177784839804528666823956703141147239309978420776148158425922031573513062568162012505209805669623841355103885621402814626329355281853436655713194649170570579414480803671531927080535374958180810697826214794117466378050607
    # the hypothesis on the private exponent (the theoretical maximum is 0.292)
    delta = .29 # 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)
    for m in range(1,20):
#         m = 4 # 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:
            print ("=== solution found ===")
            if False:
                print ("x:", solx)
                print ("y:", soly)

            d = int(pol(solx, soly) / e)
            print ("private key found:", d)
        else:
            print ("=== no solution was found ===")

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

if __name__ == "__main__":
    example()

跑出d1 =36167461773898995192586226632578677184913220227461899855497899052924496298787

解rsa , 有p = 199138677823743837339927520157607820029746574557746549094921488292877226509198315016018919385259781238148402833316033634968163276198999279327827901879426429664674358844084491830543271625147280950273934405879341438429171453002453838897458102128836690385604150324972907981960626767679153125735677417397078196059

根据上面的p, n 还有一些e有关的条件, 求flag

通过p,n得到

1
2
3
4
c = 12732299056226934743176360461051108799706450051853623472248552066649321279227693844417404789169416642586313895494292082308084823101092675162498154181999270703392144766031531668783213589136974486867571090321426005719333327425286160436925591205840653712046866950957876967715226097699016798471712274797888761218915345301238306497841970203137048433491914195023230951832644259526895087301990301002618450573323078919808182376666320244077837033894089805640452791930176084416087344594957596135877833163152566525019063919662459299054294655118065279192807949989681674190983739625056255497842063989284921411358232926435537518406
p = 199138677823743837339927520157607820029746574557746549094921488292877226509198315016018919385259781238148402833316033634968163276198999279327827901879426429664674358844084491830543271625147280950273934405879341438429171453002453838897458102128836690385604150324972907981960626767679153125735677417397078196059
q = 112213695905472142415221444515326532320352429478341683352811183503269676555434601229013679319423878238944956830244386653674413411658696751173844443394608246716053086226910581400528167848306119179879115809778793093611381764939789057524575349501163689452810148280625226541609383166347879832134495444706697124741
e=

这里有个e是未知的, 但是assert (e > (ord("*")*100) and gcd(e,(p-1)*(q-1))!=1 )
可以看到e>4200而且e与phi不是互素的…

马上想到AMM了, 但是这个e不知道
试试从4200开始爆破e….结果AMM实在是跑的太久了(也不知道为啥
根本没办法往下爆…

想回去看看之前找到AMM的那个博客, 想自己重新写一个来着……
http://yulige.top/?p=752#Sore667pt_6solvers - easyRSA
然后…就发现 怎么博客那道题的p和q和这道题的一模一样啊!
会不会e也没改?
于是试了一下原题的e = 0x1337, 然后把慢到打把游戏都跑不完的组合ART改成直接遍历mod p下的0x1337次方根(只有flag够短才能成功, 事实上做出答案了发现出题人是有做padding的, 但是似乎还是太短了?

然后就直接跑出来了….

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
import random
import time

# About 3 seconds to run
def AMM(o, r, q):
    start = time.time()
    print('\n----------------------------------------------------------------------------------')
    print('Start to run Adleman-Manders-Miller Root Extraction Method')
    print('Try to find one {:#x}th root of {} modulo {}'.format(r, o, q))
    g = GF(q)
    o = g(o)
    p = g(random.randint(1, q))
    while p ^ ((q-1) // r) == 1:
        p = g(random.randint(1, q))
    print('[+] Find p:{}'.format(p))
    t = 0
    s = q - 1
    while s % r == 0:
        t += 1
        s = s // r
    print('[+] Find s:{}, t:{}'.format(s, t))
    k = 1
    while (k * s + 1) % r != 0:
        k += 1
    alp = (k * s + 1) // r
    print('[+] Find alp:{}'.format(alp))
    a = p ^ (r**(t-1) * s)
    b = o ^ (r*alp - 1)
    c = p ^ s
    h = 1
    for i in range(1, t):
        d = b ^ (r^(t-1-i))
        if d == 1:
            j = 0
        else:
            print('[+] Calculating DLP...')
            j = - dicreat_log(a, d)
            print('[+] Finish DLP...')
        b = b * (c^r)^j
        h = h * c^j
        c = c ^ r
    result = o^alp * h
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    print('Find one solution: {}'.format(result))
    return result

def findAllPRoot(p, e):
    print("Start to find all the Primitive {:#x}th root of 1 modulo {}.".format(e, p))
    start = time.time()
    proot = set()
    while len(proot) < e:
        proot.add(pow(random.randint(2, p-1), (p-1)//e, p))
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    return proot

def findAllSolutions(mp, proot, cp, p):
    print("Start to find all the {:#x}th root of {} modulo {}.".format(e, cp, p))
    start = time.time()
    all_mp = set()
    for root in proot:
        mp2 = mp * root % p
        assert(pow(mp2, e, p) == cp)
        all_mp.add(mp2)
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    return all_mp

from Crypto.Util.number import long_to_bytes
c = 12732299056226934743176360461051108799706450051853623472248552066649321279227693844417404789169416642586313895494292082308084823101092675162498154181999270703392144766031531668783213589136974486867571090321426005719333327425286160436925591205840653712046866950957876967715226097699016798471712274797888761218915345301238306497841970203137048433491914195023230951832644259526895087301990301002618450573323078919808182376666320244077837033894089805640452791930176084416087344594957596135877833163152566525019063919662459299054294655118065279192807949989681674190983739625056255497842063989284921411358232926435537518406
p = 199138677823743837339927520157607820029746574557746549094921488292877226509198315016018919385259781238148402833316033634968163276198999279327827901879426429664674358844084491830543271625147280950273934405879341438429171453002453838897458102128836690385604150324972907981960626767679153125735677417397078196059
q = 112213695905472142415221444515326532320352429478341683352811183503269676555434601229013679319423878238944956830244386653674413411658696751173844443394608246716053086226910581400528167848306119179879115809778793093611381764939789057524575349501163689452810148280625226541609383166347879832134495444706697124741
e = 0x1337
cp = c % p
mp = AMM(cp, e, p)
p_proot = findAllPRoot(p, e)
mps = findAllSolutions(mp, p_proot, cp, p)


def check(m):
    if long_to_bytes(m).decode('utf-8','ignore').startswith('*CTF'):
        print(long_to_bytes(m))
        exit()
        return True
    elif long_to_bytes(m).decode('utf-8','ignore').startswith('*ctf'):
        print(long_to_bytes(m))
        exit()
        return True
    else:
        return False

for mpp in mps:
    check(int(mpp))

输出
1
b'*CTF{S0_Y0u_ARE_REA11Y_GOOd_At_Pla1_This}Ifyoumissthetrainimonyouwillknowthatiamgoneyoucanheartheflagfluwwwwwwwwww'

看这个flag好像又是歪打正着的一题….Pla1估计是某个方法吧?等个官方wp咯
还好padding长度不够hhhh, 不过要是长度够跑那个组合ART应该也是可以出结果的, 就是要多打两把游戏而已
顺便一提, 这个padding是歌词吧! 500 miles好听!

MyCurve

附件

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
from Crypto.Util.number import bytes_to_long
from flag import flag
assert flag[:5]=='*CTF{' and flag[-1]=='}'
flag=flag[5:-1]
def add(P,Q):
	if Q==0:
		return P
	x1,y1=P
	x2,y2=Q
	return (d1*(x1+x2)+d2*(x1+y1)*(x2+y2)+(x1+x1^2)*(x2*(y1+y2+1)+y1*y2))/(d1+(x1+x1^2)*(x2+y2)),(d1*(y1+y2)+d2*(x1+y1)*(x2+y2)+(y1+y1^2)*(y2*(x1+x2+1)+x1*x2))/(d1+(y1+y1^2)*(x2+y2))

def mul(k,P):
	Q=(0,0)
	while k>0:
		if is_even(k):
			k/=2
			P=add(P,P)
		else:
			k-=1
			Q=add(P,Q)
	return Q

F=GF(2**100)
R.<x,y>=F[]
d1=F.fetch_int(1)
d2=F.fetch_int(1)
x,y=(698546134536218110797266045394L, 1234575357354908313123830206394L)
G=(F.fetch_int(x),F.fetch_int(y))
P=mul(bytes_to_long(flag),G)
print (G[0].integer_representation(),G[1].integer_representation())
print (P[0].integer_representation(),P[1].integer_representation())
#(698546134536218110797266045394L, 1234575357354908313123830206394L)
#(403494114976379491717836688842L, 915160228101530700618267188624L)


椭圆曲线… 第一次做这样的
比赛的时候也没做出来 查了查https://www.hyperelliptic.org (应该是一个曲线库
发现里面有一种曲线就是题目给的曲线就是这个
具体是啥玩意还搞不懂 只能先按着库里面的数据把脚本写好 学完ECC再来看看了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import long_to_bytes
F=GF(2**100)
R.<x,y>=F[]
def _map(p):
    x,y = F.fetch_int(p[0]),F.fetch_int(p[1])
    u = 3*(x+y)/(x*y+x+y)
    v = 3*(x/(x*y+x+y)+2)
    return (u,v)
G = (698546134536218110797266045394,1234575357354908313123830206394)P = (403494114976379491717836688842,915160228101530700618267188624)
E = EllipticCurve(GF(2**100),[1, 2, 0, 0, 3])
base = E(_map(G))
res = E(_map(P))
flag = discrete_log(res,base,base.order(),operation="+")
print(long_to_bytes(flag))