huaweictf2020

Author Avatar
Xzhah 12月 28, 2020
  • 在其它设备中阅读本文章

2020华为CTF

三场比赛的时候都没啥时间，匆匆看了几道题

第一场

divination

主要逻辑就是循环左移,循环右移,异或。那其实每个bit就是循环移位过后的二进制加法，可以视为一个线性方程组。用sage进行求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
rol = lambda val, r_bits, max_bits: \

    (val << r_bits%max_bits) & (2**max_bits-1) | \

    ((val & (2**max_bits-1)) >> (max_bits-(r_bits%max_bits)))

 

# Rotate right: 0b1001 --> 0b1100

ror = lambda val, r_bits, max_bits: \

    ((val & (2**max_bits-1)) >> r_bits%max_bits) | \

    (val << (max_bits-(r_bits%max_bits)) & (2**max_bits-1))

 

max_bits = 256  # For fun, try 2, 17 or other arbitrary (positive!) values

def f(input):

	list1=[13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127]

	xor_res=input

	for i in range(len(list1)):

		if i%2==0:

			t1=rol(input,list1[i],256)

		else:

			t1=ror(input,list1[i],256)

		xor_res=(xor_res^^t1)& 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF

		print hex(xor_res),hex(t1)

	return xor_res

solve.exp

把f变换视为变换视为A*B=C

32字节的flag，可以视为256个未知数(每个bit为一个未知数),A为256256的参数矩阵，B为1\256的未知数向量，C为密文。

那么为了求得A矩阵，我们可以构造256256个随机数矩阵B1，得A\B1=C1。那么C1，B1已知，自然能得到矩阵A，从而得到A的逆矩阵~A,那么B=~A*C,自然求得未知数。

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
rol = lambda val, r_bits, max_bits: \
    (val << r_bits%max_bits) & (2**max_bits-1) | \
    ((val & (2**max_bits-1)) >> (max_bits-(r_bits%max_bits)))
# Rotate right: 0b1001 --> 0b1100
ror = lambda val, r_bits, max_bits: \
    ((val & (2**max_bits-1)) >> r_bits%max_bits) | \
    (val << (max_bits-(r_bits%max_bits)) & (2**max_bits-1))
max_bits = 256  # For fun, try 2, 17 or other arbitrary (positive!) values
def f(input):
	list1=[13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127]
	xor_res=input
	for i in range(len(list1)):
		if i%2==0:
			t1=rol(input,list1[i],256)
		else:
			t1=ror(input,list1[i],256)
		xor_res=(xor_res^^t1)& 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
		print hex(xor_res),hex(t1)
	return xor_res
print #hex(rol(0x3132333435363738393031323334353637383930313233343536373839303132,0xd,256))
print hex(rol(0x3231303938373635343332313039383736353433323130393837363534333231,0xd,256))
print hex(f(0x3231303938373635343332313039383736353433323130393837363534333231))
import random
def calL():
    t = []
    for i in range(256):        t.append(random.randint(0,0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff))
    tmp = []
    for x in t:
        tmp.append(f(x))
    inp = t
    outp = tmp
    I = Integers(2)
    tmp = []
    for x in inp:
        t =map(int ,bin(x)[2:].zfill(256))
        tmp.append(t)
    a = matrix(I,tmp)
    tmp = []
    for x in outp:
        t =map(int ,bin(x)[2:].zfill(256))
        tmp.append(t)
    b = matrix(I,tmp)
    L =  a.solve_right(b)
    L =  L
    return L
L  = calL()
print L
ans = [0xe7764526f1acd0de2548d47dbf701b1988645a56c60fcf307a043dd816d74e5a]
def recover(c,L):
    I = Integers(2)
    tmp = []
    t =map(int ,bin(c)[2:].zfill(256))
    v = vector(I,t)
    r = v*L
    return int(''.join( map(str,map(int,r)) ),2)
L = ~L
flag = ''
0x5A,0x4E,0xD7,0x16,0xD8,0x3D,4,0x7A,0x30,0xCF,0xF,0xC6,0x56,0x5A,0x64,0x88,0x19,0x1B,0x70,0xBF,0x7D,0xD4,0x48,0x25,0xDE,0xD0,0xAC,0xF1,0x26,0x45,0x76,0xE7
for k in ans:
	tmp = recover(k,L)
	print hex(tmp)
	s = hex(tmp)[2:].decode('hex')[::-1]
	print s
	flag+=s
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
from Crypto.Util.number import *
from secret import flag 
from gmpy2 import next_prime,invert,gcd
import os                              

e = 65537
## level1
x = getPrime(290)
y = next_prime(21*x)
z = next_prime(3*x*y)
n1 = x*y*z
msg = flag+os.urandom(100)
m = bytes_to_long(msg)
assert(m < n1)
print n1
c1 = pow(m,e,n1)

## level2
m = c1
o = getPrime(300) 
s = getPrime(300)
t = next_prime(o)
u = next_prime(s)
print o*s
n2 = o*s*t*u
assert(m<n2)
print n2
c2 = pow(m,e,n2)
## level3
m = c2
p = getPrime(800)
q = getPrime(800)

n3 = p * q
phi = (q-1)*(p-1)
assert(m < n3)
print n3
while True:
    s = getPrime(10)
    if(gcd(s,p-1) == 1):
        sinv = invert(s,p-1)
        e = 4*s*sinv+3
        if(gcd(phi,e) == 1):
            break
c3 = pow(m,e,n3)
print c3
m = bytes_to_long(os.urandom(128))

print m
assert(m<n3)
print pow(m,e,n3)

从后往前，第三层

e=4*s*sinv+3=4(1+k\(p-1))+3=4*k*(p-1)+7

pow(m,e,p)=pow(m,7,p)

pow(m,e,n)-pow(m,7,n)=x*p % n

n=p*q

gcd(n,pow(m,e,n)-pow(m,7,n))=p

然后可以爆破s得到e

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

c4=22238585749689335043198360403653248049710943304594623939441271714322821476047298977043454290592085809700500599520080107736858423927071836758485527270617538166045213386679961664240306883126224169183649140929168343634245637578487850945986688768857954082116136864696582066988005306045105860368497626822666433678879698344619056273526837700698315346972423482713305543394110949178233504551465821354514535155389087138867576532139739270960823294873497825040963862751772914087741831403951901
n3=24502730939655407292543436897382196297516664227273320602397906878696723372242877776550446563950867624819352853122033114711732125433588724779869985477495098802744344448915032607469954642257825855931872281908232331623829725043031800535739432133948607448362641204034546581444904408754892037110031202573463399201625812005615264689877537231974023870006792196961829162058446662172634212427186470724599941352830546043772969297733239518604749366684163813795999625784931375110137805143337329
m4_old=81225738828166640599054154023183465870678960906769673605358084529196871174429427936591822589995476552044227730868809310992934103731850597399114246762836121101348301079296663951503688072299542357013093324718850936925265954204973634470836187733828189312553819810470405246669124171178070485118436102895117354417

p3=gcd(n3,c4-pow(m4_old,7,n3))
print p3
q3=n3/p3
phi3=(p3-1)*(q3-1)
c3=2385064917660948806957457681641614888669217960607006360543268900921017481245498563263991410918604891314384810533439253814523067168636768976220059028108900592323119524657903364697700329145453517769093265052715204625870232288203427545150983037310876534801548309890853026234248412421497939811385725642492104262954059677793538707604205179344884142656842895567795000647837461835179395742399372683460208271310884657279893532539121893558143029933794905470899127632780110459122203796256514
for s in range(2**10,2**11):
    #s = getPrime(10)
    if(gcd(s,p3-1) == 1):
        sinv = invert(s,p3-1)
        e = 4*s*sinv+3
        if(gcd(phi3,e) == 1):
            if(powmod(m4_old,e,n3)==c4):
				print 'e3 is ',e
				break
	if s%10000==0:
	 print s
d3=invert(e3,phi3)
m3=powmod(c3,d3,n3)
c2=m3

第二层t和o接近，u和s接近，所以我们设x=t-o,y=u-s

然后对x，y进行一个爆破。

已知o*s=a，(o+x)*(s+y)=b

我们想求o,x,s,y四个值

有（xy-((o+x)*(s+y)-o*s))^2=(xy-xs-xy-oy)^2=xs^2+oy^2+2xsoy

所以我们可以有(xs-oy)^2=xy-((o+x)*(s+y)-o*s))^2-4osxy

开根得到xs-oy或者oy-xs，那么我们用(o+x)*(s+y)-(os+xy+xs-oy)=2oy，2oy/y得到o值，得到四个o,x,s,y值

第一层

其实可以用https://www.alpertron.com.ar/ECM.HTM强行分解

x = getPrime(290)
y = next_prime(21x)
z = next_prime(3x*y)

n1=xyz约等于x(21x)(3x21x)=3*21*21*x^4

所以其实n1/(3*21*21)然后开四次方可以得到x的近似值，然后在那附近爆破x就行了。

第三场

因为忘记&0xff了，所以以为求解工具有问题，撸了z3，sage，numpy三个板子。线性方程最好z3还是用Int，约束里不要做异或。粗心害死人啊

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
from z3 import *
from sys import *
flag=[Int('flag[%d]'%i)for i in range(42)]
s=Solver()
def get_models(s):
    while s.check() == sat:
        m = s.model()
        yield m
        s.add(Or([sym() != m[sym] for sym in m.decls()]))
xor_table=[0xA0
,0xE4
,0xBA
,0xFB
,0x10
,0xDD
,0xAC
,0x65
,0x8D
,0xB
,0x57
,0x1A
,0xE4
,0x28
,0x96
,0xB3
,0xC
,0x79
,0x4D
,0x80
,0x90
,0x99
,0x58
,0xFE
,0x50
,0xD3
,0xF9
,0x3C
,0xF
,0xC1
,0xE3
,0xA6
,0x39
,0xC3
,0x28
,0x75
,0xF8
,0xC9
,0xC8
,0xCD
,0x78
,0x26]
data=[]
tmp=int(argv[1])
print 'key is ',tmp
data.append(tmp)
for i in range(0x1e):
	res=16807 * (tmp % 127773) - 2836 * (tmp // 127773)
	#print hex(abs(res))
	if(res<0):
		tmp=res+0x7FFFFFFF
	else:
		tmp=res
	data.append(tmp)
print map(hex,data)
for i in range(10):
	for j in range(0x1f):
		#print "%x + %x =%x"%(data[(j+3)%0x1f],data[j],data[(j+3)%0x1f]+data[j])
		data[(j+3)%0x1f]=(data[(j+3)%0x1f]+data[j])&0xffffffff
'''for j in range(42+1):
		#print "%x + %x =%x"%(data[(j+3)%0x1f],data[j],data[(j+3)%0x1f]+data[j])
		data[(j+3)%0x1f]=(data[(j+3)%0x1f]+data[(j)%0x1f])&0xffffffff
'''
def div2(num):
	return num//2
print map(hex,map(div2,data))
print map(hex,data)
table1=[]
input='flag{111111111111111111111111111111111111}'
input_list=[]
for i in range(42):
	input_list.append(ord(input[i])^xor_table[i])
v6=[0]*42
for i in range(42):
	table2=[]
	for j in range(42):
		#print "%x + %x =%x"%(data[(j+3)%0x1f],data[j],data[(j+3)%0x1f]+data[j])
		data[(i*42+j+3)%0x1f]=(data[(i*42+j+3)%0x1f]+data[(i*42+j)%0x1f])&0xffffffff
		table2.append((((data[(i*42+j+3)%0x1f]//2)&0xff)+1)&0xff)
		v6[i]+=table2[j]*input_list[j]
	table1.append(table2)
for i in range(42):
	print map(hex,table1[i])
final=[0xbd360
,0xb3ec5
,0x8d98e
,0xcb266
,0xb497f
,0xa861e
,0x97acd
,0xbfe57
,0xa7d14
,0xd4786
,0xa3d60
,0xac342
,0xa9d96
,0xb143b
,0xa9633
,0xb1463
,0xc2acc
,0xcd008
,0xc2d4d
,0xbcee2
,0xb2cf6
,0x9a886
,0xb4e48
,0xbd5e8
,0xad646
,0xd1a30
,0xa7a1e
,0x94a80
,0xc6fdc
,0x7f5f8
,0xa93cd
,0x88dc5
,0xd816e
,0x9b1aa
,0xb2c7d
,0xbc10e
,0xab72d
,0x9a7ba
,0xcd12a
,0xc6a1f
,0x9f2d2
,0xd5cbd
]
print map(hex,v6)
#for i in range(42):
	#print	'(flag[%d]*table1[i][%d])+'%(i,i),
s.add(flag[0]==(ord('f')^xor_table[0]))
s.add(flag[1]==(ord('l')^xor_table[1]))
s.add(flag[2]==(ord('a')^xor_table[2]))
s.add(flag[3]==(ord('g')^xor_table[3]))
s.add(flag[4]==(ord('{')^xor_table[4]))
s.add(flag[41]==(ord('}')^xor_table[41]))
tmp2=[0]*42
for i in range(42):
	for j in range(42):
		tmp2[i]+=flag[j]*table1[i][j]
	s.add(tmp2[i]==final[i])
	#s.add((flag[0]*table1[i][0])+ (flag[1]*table1[i][1])+ (flag[2]*table1[i][2])+ (flag[3]*table1[i][3])+ (flag[4]*table1[i][4])+ (flag[5]*table1[i][5])+ (flag[6]*table1[i][6])+ (flag[7]*table1[i][7])+ (flag[8]*table1[i][8])+ (flag[9]*table1[i][9])+ (flag[10]*table1[i][10])+ (flag[11]*table1[i][11])+ (flag[12]*table1[i][12])+ (flag[13]*table1[i][13])+ (flag[14]*table1[i][14])+ (flag[15]*table1[i][15])+ (flag[16]*table1[i][16])+ (flag[17]*table1[i][17])+ (flag[18]*table1[i][18])+ (flag[19]*table1[i][19])+ (flag[20]*table1[i][20])+ (flag[21]*table1[i][21])+ (flag[22]*table1[i][22])+ (flag[23]*table1[i][23])+ (flag[24]*table1[i][24])+ (flag[25]*table1[i][25])+ (flag[26]*table1[i][26])+ (flag[27]*table1[i][27])+ (flag[28]*table1[i][28])+ (flag[29]*table1[i][29])+ (flag[30]*table1[i][30])+ (flag[31]*table1[i][31])+ (flag[32]*table1[i][32])+ (flag[33]*table1[i][33])+ (flag[34]*table1[i][34])+ (flag[35]*table1[i][35])+ (flag[36]*table1[i][36])+ (flag[37]*table1[i][37])+ (flag[38]*table1[i][38])+ (flag[39]*table1[i][39])+ (flag[40]*table1[i][40])+ (flag[41]*table1[i][41])==final[i])

for m in get_models(s):
    serial = [m[flag[i]].as_long() for i in range(42)]
    for i in range(len(serial)):
		print chr(serial[i]^xor_table[i])
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
xor_table=[0xA0
,0xE4
,0xBA
,0xFB
,0x10
,0xDD
,0xAC
,0x65
,0x8D
,0xB
,0x57
,0x1A
,0xE4
,0x28
,0x96
,0xB3
,0xC
,0x79
,0x4D
,0x80
,0x90
,0x99
,0x58
,0xFE
,0x50
,0xD3
,0xF9
,0x3C
,0xF
,0xC1
,0xE3
,0xA6
,0x39
,0xC3
,0x28
,0x75
,0xF8
,0xC9
,0xC8
,0xCD
,0x78
,0x26]
data=[]
tmp=82
print 'key is ',tmp
data.append(tmp)
for i in range(0x1e):
	res=16807 * (tmp % 127773) - 2836 * (tmp // 127773)
	#print hex(abs(res))
	if(res<0):
		tmp=res+0x7FFFFFFF
	else:
		tmp=res
	data.append(tmp)
print map(hex,data)
for i in range(10):
	for j in range(0x1f):
		#print "%x + %x =%x"%(data[(j+3)%0x1f],data[j],data[(j+3)%0x1f]+data[j])
		data[(j+3)%0x1f]=(data[(j+3)%0x1f]+data[j])&0xffffffff
def div2(num):
	return num//2
print map(hex,map(div2,data))
print map(hex,data)
table1=[]
input='flag{111111111111111111111111111111111111}'
input_list=[]
for i in range(42):
	input_list.append(ord(input[i])^xor_table[i])
v6=[0]*42
for i in range(42):
	table2=[]
	for j in range(42):
		#print "%x + %x =%x"%(data[(j+3)%0x1f],data[j],data[(j+3)%0x1f]+data[j])
		data[(i*42+j+3)%0x1f]=(data[(i*42+j+3)%0x1f]+data[(i*42+j)%0x1f])&0xffffffff
		table2.append((((data[(i*42+j+3)%0x1f]//2)&0xff)+1)&0xff)
		v6[i]+=table2[j]*input_list[j]
	table1.append(table2)
final=[0xbd360
,0xb3ec5
,0x8d98e
,0xcb266
,0xb497f
,0xa861e
,0x97acd
,0xbfe57
,0xa7d14
,0xd4786
,0xa3d60
,0xac342
,0xa9d96
,0xb143b
,0xa9633
,0xb1463
,0xc2acc
,0xcd008
,0xc2d4d
,0xbcee2
,0xb2cf6
,0x9a886
,0xb4e48
,0xbd5e8
,0xad646
,0xd1a30
,0xa7a1e
,0x94a80
,0xc6fdc
,0x7f5f8
,0xa93cd
,0x88dc5
,0xd816e
,0x9b1aa
,0xb2c7d
,0xbc10e
,0xab72d
,0x9a7ba
,0xcd12a
,0xc6a1f
,0x9f2d2
,0xd5cbd
]
import random
def calL():
    t = []
    tmp=[]
    a=matrix(table1)
    b = matrix(final)
    L =  a.solve_right(b.T)
    L =  L
    return L
L  = calL()
print L
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
import numpy as np
from sys import *
xor_table=[0xA0
,0xE4
,0xBA
,0xFB
,0x10
,0xDD
,0xAC
,0x65
,0x8D
,0xB
,0x57
,0x1A
,0xE4
,0x28
,0x96
,0xB3
,0xC
,0x79
,0x4D
,0x80
,0x90
,0x99
,0x58
,0xFE
,0x50
,0xD3
,0xF9
,0x3C
,0xF
,0xC1
,0xE3
,0xA6
,0x39
,0xC3
,0x28
,0x75
,0xF8
,0xC9
,0xC8
,0xCD
,0x78
,0x26]
data=[]
tmp=82
print 'key is ',tmp
data.append(tmp)
for i in range(0x1e):
	res=16807 * (tmp % 127773) - 2836 * (tmp // 127773)
	#print hex(abs(res))
	if(res<0):
		tmp=res+0x7FFFFFFF
	else:
		tmp=res
	data.append(tmp)
#print map(hex,data)
for i in range(10):
	for j in range(0x1f):
		#print "%x + %x =%x"%(data[(j+3)%0x1f],data[j],data[(j+3)%0x1f]+data[j])
		data[(j+3)%0x1f]=(data[(j+3)%0x1f]+data[j])&0xffffffff
def div2(num):
	return num//2
#print map(hex,map(div2,data))
#print map(hex,data)
table1=[]
input='flag{111111111111111111111111111111111111}'
input_list=[]
for i in range(42):
	input_list.append(ord(input[i])^xor_table[i])
v6=[0]*42
table3=[]
for i in range(42):
	table2=[]
	for j in range(42):
		#print "%x + %x =%x"%(data[(j+3)%0x1f],data[j],data[(j+3)%0x1f]+data[j])
		data[(i*42+j+3)%0x1f]=(data[(i*42+j+3)%0x1f]+data[(i*42+j)%0x1f])&0xffffffff
		table2.append((((data[(i*42+j+3)%0x1f]//2)&0xff)+1)&0xff)
		v6[i]+=table2[j]*input_list[j]
		table3.append((((data[(i*42+j+3)%0x1f]//2)&0xff)+1)&0xff)
	table1.append(table2)
final=[0xbd360
,0xb3ec5
,0x8d98e
,0xcb266
,0xb497f
,0xa861e
,0x97acd
,0xbfe57
,0xa7d14
,0xd4786
,0xa3d60
,0xac342
,0xa9d96
,0xb143b
,0xa9633
,0xb1463
,0xc2acc
,0xcd008
,0xc2d4d
,0xbcee2
,0xb2cf6
,0x9a886
,0xb4e48
,0xbd5e8
,0xad646
,0xd1a30
,0xa7a1e
,0x94a80
,0xc6fdc
,0x7f5f8
,0xa93cd
,0x88dc5
,0xd816e
,0x9b1aa
,0xb2c7d
,0xbc10e
,0xab72d
,0x9a7ba
,0xcd12a
,0xc6a1f
,0x9f2d2
,0xd5cbd
]
a = np.array(table1)
tmp1=[]
for i in range(42):
	tmp1.append([final[i]])
b = np.array(tmp1)
x = np.linalg.solve(a, b)
print x