2019国赛crypto

Posted on

经过两天的国赛，学到了不少东西，本菜鸡是web手在比赛中搞成了密码选手Orz，记录一下密码

puzzles

这一题简单题，只要会解积分就很快了

flag格式：

question0：

a1a2a3a4通过z3约束求解器解出

question1：

搜索条件给出的3个数字，都在一张质数表，找规律，每两个数间隔37个数，锁定26365399，Part1 = 26365399

question2：

求积分求解得Part2 = 7700，不多说

question3：

电动势=2πrBdr/dt=2π×2×4×5=80πV，根据题目给出的已知条件求解得到Part3 = 18640

question4：

百度大法好，搜索得到答案336π，再根据题目已知条件求解得到Part4 = 40320

https://zhidao.baidu.com/question/330362706543929325.html

part_des

题目给了两个信息，一个是第n轮加密后的密文，第二个是加密过程中产生的16轮加密的子密钥，在DES加密算法中，子密钥都是通过密钥来生成的，那如果我们能得到密钥的话，我们使用密钥对任意8位明文进行加密，在第n轮修改他的子密文，然后将加密后的最终密文解密即可得到flag。

那我们可不可以通过子密钥来反推出密钥呢？答案是可以的：

https://skysec.top/2017/12/25/%E4%B8%80%E9%81%93%E6%9C%89%E5%85%B3%E5%AF%86%E9%92%A5%E7%BC%96%E6%8E%92%E7%9A%84DES%E9%A2%98%E7%9B%AE/

反推密钥脚本：

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
Kn = [
    '111000001011111001100110000100000011001011010101',
    '111100001011011001110110111110000010000010010101',
    '111001001101011001110110001000110110001010001111',
    '111001101101001101110110001101100011000110000011',
    '101011101101001101110011101001100000000101100111',
    '101011110101001101111011010001101010101111000010',
    '101011110101001111011001011101001000010101011001',
    '000111110101101111011001010010111001010001001010',
    '001111110100100111011001010010001001011111101010',
    '000111110110100110011101000111001101110000101001',
    '000111110010110110011101010010100101110001110000',
    '010111110010110010101101100010011110100100111000',
    '110110111010110010101100101000010101111000010000',
    '110110001010111010101110110110010000001000110110',
    '111100001011111000101110100101010100101010001100',
    '111100001011111010100110000100010010111010000100'
]

key1 = '111000001011111001100110000100000011001011010101'
__pc2 = [
		13, 16, 10, 23,  0,  4,
		 2, 27, 14,  5, 20,  9,
		22, 18, 11,  3, 25,  7,
		15,  6, 26, 19, 12,  1,
		40, 51, 30, 36, 46, 54,
		29, 39, 50, 44, 32, 47,
		43, 48, 38, 55, 33, 52,
		45, 41, 49, 35, 28, 31
	]
C1D1 = ['*']*56
for i in range(0,len(key1)):
    C1D1[__pc2[i]] = key1[i]
# print "C1: "+"".join(C1D1)[:28]
# print "D1: "+"".join(C1D1)[28:]

C0 = '000000001*11111111*111*10*00'
D0 = '0000111*11*1001*0000100001*0'

__pc1 = [56, 48, 40, 32, 24, 16, 8,
         0, 57, 49, 41, 33, 25, 17,
         9, 1, 58, 50, 42, 34, 26,
         18, 10, 2, 59, 51, 43, 35,
         62, 54, 46, 38, 30, 22, 14,
         6, 61, 53, 45, 37, 29, 21,
         13, 5, 60, 52, 44, 36, 28,
         20, 12, 4, 27, 19, 11, 3
         ]
C0D0 = C0+D0
res = ['*']*64
deskey = ""
for i in range(0,len(__pc1)):
    res[__pc1[i]] = C0D0[i]
for i in res:
    deskey += i
# print deskey
#deskey: 01100***01**011*0111001*0110101*0110010*01*00*0*0*1*010*0110010*

def zuoyiwei(str,num):
    my = str[num:len(str)]
    my = my+str[0:num]
    return my
def key_change_1(str):
    key1_list = [57,49,41,33,25,17,9,1,58,50,42,34,26,18,10,2,59,51,43,35,27,19,11,3,60,52,44,36,63,55,47,39,31,23,15,7,62,54,46,38,30,22,14,6,61,53,45,37,29,21,13,5,28,20,12,4]
    res = ""
    for i in key1_list:
        res+=str[i-1]
    return res

def key_change_2(str):
    key2_list = [14,17,11,24,1,5,3,28,15,6,21,10,23,19,12,4,26,8,16,7,27,20,13,2,41,52,31,37,47,55,30,40,51,45,33,48,44,49,39,56,34,53,46,42,50,36,29,32]
    res = ""
    for i in key2_list:
        res+=str[i-1]
    return res
def key_gen(str):
    key_list = []
    key_change_res = key_change_1(str)
    key_c = key_change_res[0:28]
    key_d = key_change_res[28:]
    for i in range(1,17):
        if (i==1) or (i==2) or (i==9) or (i==16):
            key_c = zuoyiwei(key_c,1)
            key_d = zuoyiwei(key_d,1)
        else:
            key_c = zuoyiwei(key_c,2)
            key_d = zuoyiwei(key_d,2)
        key_yiwei = key_c+key_d
        key_res = key_change_2(key_yiwei)
        key_list.append(key_res)
    return key_list
key = "01100abc01de011f0111001g0110101h0110010i01j00k0l0m1n010o0110010p"
# print key_gen(deskey)

unknow = [
    '111000001011111001100110000100000011001011010101',
    '1j1n000010d101100m110110111k100000100000be0a0101',
    '11100100jm010d10011101100010001ae11000101000111b',
    '1d1001101101001m01110nj0001101b000k10e0110000011',
    '10j01110d10100110111001m10k0e1100000000b01100a11',
    '1010111m0101001101n110d1010001101e101011a10000k0',
    'n0d0111101010011m10j10010b110k00100001010101100a',
    '000m1j11010110n111011001e10010a1100101000k00b010',
    '00n111110100m00j1d0110010k00100e10010b11111010a0',
    '000111110dm010011001110j0001ba00110111000010k001',
    '0001111j00101m0d100n1101010010100b0k11000a110e00',
    '0m011n1100101100j010110d10001001a1101001e0k11000',
    '110j10ndm010110010101100b01000010101ka100001000e',
    '1101n00010101110d01011m01101a0e1000000b0001k0110',
    '11md0000101111100010nj10100b010k0a00101e10001100',
    '11110000101mdj10n010011000010e010010a1k010000b00'
]

def check(s):
    look = 1
    count = 0
    for y in xrange(16):
        if s in unknow[y]:
            count += 1
            try:
                assert key[y][unknow[y].index(s)] == "1"
            except:
                look = 0
                break
    if count == 0:
        print x + ": Unknow"
    elif look == 1:
        print x + ": 1"
    else:
        print x + ": 0"

# for x in "abcdefghijklmnop":
#     check(x)

undeskey = "0110011c0110011f0111001g0110101h0110010i0110010l0111010o0110010p"

def bintostr(str):
    res = ""
    for i in range(0,len(str),8):
        res += chr(int(str[i:i+8],2))
    return res
for c in "01":
    for f in "01":
        for g in "01":
            for h in "01":
                for i in "01":
                    for l in "01":
                        for o in "01":
                            for p in "01":
                                deskey = "0110011"+c+"0110011"+f+"0111001"+g+"0110101"+h+"0110010"+i+"0110010"+l+"0111010"+o+"0110010"+p
                                deskey = bintostr(deskey)
                                print deskey

运行脚本可以得到无数个key，接下来就是修改pyDES脚本getflag，脚本太长了，就贴个修改部分

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
def __des_crypt(self, block, crypt_type):
	"""Crypt the block of data through DES bit-manipulation"""
	block = self.__permutate(des.__ip, block)
	self.L = block[:32]
	self.R = block[32:]

	# Encryption starts from Kn[1] through to Kn[16]
	if crypt_type == des.ENCRYPT:
		iteration = 0
		iteration_adjustment = 1
	# Decryption starts from Kn[16] down to Kn[1]
	else:
		iteration = 15
		iteration_adjustment = -1

	i = 0
	while i < 16:
		# Make a copy of R[i-1], this will later become L[i]
		tempR = self.R[:]

		# Permutate R[i - 1] to start creating R[i]
		self.R = self.__permutate(des.__expansion_table, self.R)

		# Exclusive or R[i - 1] with K[i], create B[1] to B[8] whilst here
		self.R = list(map(lambda x, y: x ^ y, self.R, self.Kn[iteration]))
		B = [self.R[:6], self.R[6:12], self.R[12:18], self.R[18:24], self.R[24:30], self.R[30:36], self.R[36:42], self.R[42:]]
		j = 0
		Bn = [0] * 32
		pos = 0
		while j < 8:
			# Work out the offsets
			m = (B[j][0] << 1) + B[j][5]
			n = (B[j][1] << 3) + (B[j][2] << 2) + (B[j][3] << 1) + B[j][4]
			
			# Find the permutation value
			v = des.__sbox[j][(m << 4) + n]

			# Turn value into bits, add it to result: Bn
			Bn[pos] = (v & 8) >> 3
			Bn[pos + 1] = (v & 4) >> 2
			Bn[pos + 2] = (v & 2) >> 1
			Bn[pos + 3] = v & 1

			pos += 4
			j += 1

		# Permutate the concatination of B[1] to B[8] (Bn)
		self.R = self.__permutate(des.__p, Bn)

		self.R = list(map(lambda x, y: x ^ y, self.R, self.L))
		#while j < len(self.R):
		self.L = tempR
		if (i == 2):
			self.L = [0,0,0,0,0,0,0,1,0,0,0,1,1,0,0,1,1,1,1,0,0,0,0,1,0,0,1,0,1,0,1,1]
			self.R = [1,0,0,1,0,0,1,0,1,1,0,1,1,0,0,1,0,0,0,1,0,1,0,1,0,0,1,0,0,1,0,1]
		i += 1
		iteration += iteration_adjustment
	# Final permutation of R[16]L[16]
	self.final = self.__permutate(des.__fp, self.R + self.L)
	return self.final

warmup

打开看到是AES CTR加密模式，该模式存在一个缺点：主动攻击（改明文，后续内容不影响，只要误差不传递该缺点就存在）

操作流程：

  • 连接服务器，第一次什么都不输入，获得第一条密文c1，知道flag加密后的密文有48个字节
  • 第二次输入1111111111111111（16个1），获得第二条密文c2
  • 第三次输入11111111111111111111111111111111（32个1），获得第三条密文c3
  • 第四次输入111111111111111111111111111111111111111111111111（48个1），获得第四条密文c4
  • 将c1[0:16]与c2[0:16]异或再与1111111111111111异或得到flag第一部分
  • 将c1[16:32]与c3[16:32]异或再与1111111111111111异或得到flag第二部分
  • 将c1[32:48]与c3[32:48]异或再与1111111111111111异或得到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
import binascii
def xor_encrypt(tips,key):
    lkey = len(key)
    secret = []
    num = 0
    for each in tips:
        if num >= lkey:
            num=num%lkey
        secret.append( chr( ord(each)^ord(key[num]) ) )
        num += 1
    return ''.join(secret)
a = "1111111111111111"
c1 = "a09ce5b95c937382cac3fa7b0e34e7bb864db853eb47a19c97c79f8fd1b87d2a92d5aa6583530cc66123febf0befb19c"
c2 = "f7c1b5ef169b7285c893f97c0828e4bf8144f400a51fa2879dc59bdccba37d7cc3d5e560d2500d8e613dcedc20df85f961a8e4786b4ac8f2cff4f1d30355acb5"
c3 = "f7c1b5ef169b7285c893f97c0828e4bfd619a456ef17a3809f9598dbcdbf7e78c4dca9339c080e956b3fca8f3ac485af30a8ab7d3a49c9bacfeac1b0286598d0b64e2dc2592645911262abdd51714025"
c4 = "f7c1b5ef169b7285c893f97c0828e4bfd619a456ef17a3809f9598dbcdbf7e789381f965d6000f92696fc9883cd886ab37a1e72e7411caa1c5e8c5e3327e9886e74e62c7082544d9127c9bbe7a41744008d205546ce4ce446e7fd4439beb537f"

c1 = binascii.unhexlify(c1)
c2 = binascii.unhexlify(c2)
c3 = binascii.unhexlify(c3)
c4 = binascii.unhexlify(c4)

c1_1 = c1[0:16]
c1_2 = c1[16:32]
c1_3 = c1[32:48]
c2_1 = c2[0:16]
c3_2 = c3[16:32]
c4_3 = c4[32:48]
p1 = xor_encrypt(xor_encrypt(c1_1,c2_1),a)
p2 = xor_encrypt(xor_encrypt(c1_2,c3_2),a)
p3 = xor_encrypt(xor_encrypt(c1_3,c4_3),a)
print p1+p2+p3

Asymmetric

这题是一道rsa，n = p**r，r在2-10，并且n已知，因此可以使用gmpy2.iroot函数爆破得到

1
2
r = 4
p = 165740755190793304655854506052794072378181046252118367693457385632818329041540419488625472007710062128632942664366383551452498541560538744582922713808611320176770401587674618121885719953831122487280978418110380597358747915420928053860076414097300832349400288770613227105348835005596365488460445438176193451867

因为p为质数，因此欧拉函数φ(p^r)=p^r-p^(r-1)，知道欧拉函数和e，那么就可以求出d，从而求出flag

脚本如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import gmpy2
import binascii

pubkey = (58134567416061346246424950552806959952164141873988197038339318172373514096258823300468791726051378264715940131129676561677588167620420173326653609778206847514019727947838555201787320799426605222230914672691109516799571428125187628867529996213312357571123877040878478311539048041218856094075106182505973331343540958942283689866478426396304208219428741602335233702611371265705949787097256178588070830596507292566654989658768800621743910199053418976671932555647943277486556407963532026611905155927444039372549162858720397597240249353233285982136361681173207583516599418613398071006829129512801831381836656333723750840780538831405624097443916290334296178873601780814920445215584052641885068719189673672829046322594471259980936592601952663772403134088200800288081609498310963150240614179242069838645027877593821748402909503021034768609296854733774416318828225610461884703369969948788082261611019699410587591866516317251057371710851269512597271573573054094547368524415495010346641070440768673619729280827372954003276250541274122907588219152496998450489865181536173702554116251973661212376735405818115479880334020160352217975358655472929210184877839964775337545502851880977049299029101466287659419446724781305689536816523774995178046989696610897508786776845460908137698543091418571263630383061605011820139755322231913029643701770497299157169690586232187419462594477116374977216427311975598620616618808494138669546120288334682865354702356192972496556372279363023366842805886601834278434406709218165445335977049796015123909789363819484954615665668979L, 754600786340927688096652328072061561501667781193760284816393637647032362908189628005150802929636396969230958922073774180726205402897453096041624408154494621307262657492560975357997726055874834308239749992507552325614973631556754707427580134609221878324704469965450463088892083264951442562525825243127575048386573246756312509362222667015490013299327398464802116909245529065994770788125182846841016932803939806558559335886481214931253578226314057242462834149031625361286317307273138514126289052003214703248070256059405676891634792175775697355408418965738663732479622148276007308404691800186837579126431484536836513358124181380166971922188839934522356902295160649189850427580493328509329115798694580347461641487270793993129066433242544366683131231903590153844590595882428219010673818765995719694470668924781499987923250883546686344997580959954960334567874040563037167422839228466141912000421309282727363913908613116739074234989825489075148091144771967111113068647060175231126374070143480727000247378471525286907200601035581143391602569836131345909055708005758380081303860198696570649330092070410465978479841469533490522594827330661914537170063053059393550673731195548189192109328158876774080143171304333338291909598353550442855717204721L)
e = pubkey[0]
n = pubkey[1]

#爆破p、r
# for i in range(2,10):
#     print gmpy2.iroot(n,i)

r = 4
p = 165740755190793304655854506052794072378181046252118367693457385632818329041540419488625472007710062128632942664366383551452498541560538744582922713808611320176770401587674618121885719953831122487280978418110380597358747915420928053860076414097300832349400288770613227105348835005596365488460445438176193451867
c = 397664589731174185244807196969081295636743791347632992634877550171968202027583158122965358524605148382084087083055292775614950985582170471137600161892882032418551412966830769759927895880547815633951497722234770712306297076112879370771232002533504544337602525761984751743331880661186125346775270009628518533444304138475743540761869803954394981015216901027389649277312518044879870118578221153501921121767735420588646590238714924432821796920521634258142397614044689209502427096357648434975129259602082825127577076206003397304427079424477492861403400315663250325072548968845681025152851701569515687341859140204177488152275522562157702438579218042125793735027062228793066059121344460139665832155539640935735205492779952978907816559262061499244528361109871020021430760020031419798283808270133071565808900320433503202909269829912391264709602543303699123003147709062800113790217663557468058878220523200876377904766404202224175582491708673210826668402867922460431914279888880230599188839367957343839752438896262332473564984706656652754054197747324605372489970688044871961691577273950534597267097030840338786892644592482975063818909397183558108598420167691316258539257369739732052074157931998072754050437812781241004016365131849522113541913181

phi = p**r - p**(r-1)
d = gmpy2.invert(e, phi)
print binascii.a2b_hex(hex(pow(c,d,n))[2:])