2022DASCTF MAY 出题人挑战赛

2022DASCTF MAY 出题人挑战赛中 Yusa的密码学课堂——一见如故 的题解。

Crypto

Yusa的密码学课堂——一见如故

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
class Myrand():
	def __init__(self,seed):
		self.index = 0
		self.isInit = 1
		self.MT = [seed] + [0] * 623

		for i in range(1,624):
			t = 1314433253 * (self.MT[i-1] ^ (self.MT[i-1] >> 30)) + 1
			self.MT[i] = t & 0xffffffff


	def generate(self):
		for i in range(624):
			y = (self.MT[i] & 0x80000000) + (self.MT[(i+1)%624] & 0x7fffffff)
			self.MT[i] = self.MT[(i+397)%624] ^ (y >> 1)
			if y & 1:
				self.MT[i] ^= 2567483520

	def rand(self):
		if self.index == 0:
			self.generate()
		y = self.MT[self.index]
		y = y ^ self.cs2l(y, 11) ^ self.cs2l(y,15)
		y = y ^ self.cs2r(y,7) ^ self.cs2r(y,19)
		self.index = (self.index + 1) % 624
		return y

	def cs2l(self, y, shift):
		return ((y << shift) ^ (y >> (32 - shift))) & 0xffffffff
 
	def cs2r(self, y, shift):
		return ((y >> shift) ^ (y << (32 - shift))) & 0xffffffff

import os
r = Myrand(int(os.urandom(4).hex(),16))
out = []

for i in range(624):
	out.append(r.rand())

with open("output.txt","w") as f:
	f.write(str(out))

from hashlib import md5
flag = 'DASCTF{' + md5(str(r.rand()).encode()).hexdigest() + '}'
print(flag)

文件里面是输出的rand数。

1
[3417500333, 4091726338, 652603332, 4187304543, 4293795290, 1622245003, 3383443782, 2420250331, 322010852, 1604005753, 3137930218, 1074571824, 1566336258, 2754341076, 1059426660, 2461569360, 613134153, 860561774, 3003069274, 553387944, 1949778231, 249886857, 2322866121, 3685855175, 1977923546, 1887238269, 253812990, 2188417674, 2718707711, 1599975569, 3254935456, 3199641169, 362166522, 1378687155, 912036995, 3174049018, 780042016, 970421905, 3468971406, 801660807, 833926127, 473587885, 158979812, 405306558, 1363084996, 2023076543, 2069797730, 718155249, 1641186127, 3616747747, 1575693921, 3856591855, 223881884, 3002184567, 1666647440, 617661934, 2673101022, 885332395, 3391329168, 1640225363, 2565685644, 3892963352, 3034627488, 2415435183, 3648712566, 2140877952, 1303506086, 2455662362, 1720382700, 3970268445, 2579167586, 4117229324, 846645263, 3252991293, 79067029, 2756800392, 2212447526, 2203329967, 1270408703, 740176928, 3176125705, 166800854, 3327343902, 2079714725, 3702269956, 3659849279, 3658666909, 797535816, 600857570, 553836307, 2394740468, 1178393549, 2183765310, 4014432190, 652246726, 3693235932, 4046942361, 4105444828, 145386213, 1198390220, 3023119098, 663559283, 225958361, 3893000878, 1615631644, 1941951859, 471085675, 2164362049, 4274234562, 4127314557, 1833529303, 17668093, 3208743142, 3210135945, 1772990736, 3290157875, 3006334453, 3831748800, 1120411838, 690279329, 2436940844, 1440602808, 1552272917, 1321728089, 524486126, 3696307959, 1189129368, 28736041, 3143264315, 3050323849, 1458456612, 389869312, 2360130428, 854837117, 1270423403, 3471650414, 243573262, 3449929772, 2436299611, 420972940, 923873821, 3499748829, 2470333529, 3901870125, 3589884387, 3339475693, 1526947412, 1747516667, 2971536797, 273910310, 2185887289, 2723697010, 1973585459, 1166325256, 1360822059, 416514510, 4038763765, 1816380840, 940152644, 3918708431, 3410593321, 3358844522, 3678637784, 2412834780, 3052967117, 3672611162, 570069042, 95771608, 1210821251, 2163778365, 2739972546, 3094346015, 749719666, 1697477587, 986142486, 2591897292, 1234948693, 3659791160, 3990257960, 501199958, 3029961497, 578415668, 124517322, 1985205894, 3777347400, 1149995545, 290699775, 3399696193, 1062094395, 2896523484, 1562688856, 992098141, 3941170280, 262596967, 2585751001, 3682611205, 530523926, 1202322766, 3777439514, 3051700271, 261632458, 2736123960, 2786338595, 86310784, 2760191516, 1344514731, 350767781, 2858876127, 519088864, 3193340756, 3563489312, 3239917298, 161418824, 470724403, 3310407387, 1743713887, 3064036770, 1175434157, 3029464330, 116086349, 1652489862, 1176236897, 4139800383, 3758499033, 2961626313, 3064683859, 958478146, 596650527, 1000277312, 4102368994, 1480011430, 4001401502, 4004287177, 3202905309, 1754655955, 2064262245, 1840530874, 2284428117, 2281854453, 1023839768, 2166517711, 2709857675, 2005014414, 4161461001, 2932436148, 2411599350, 4267437788, 2132764972, 150665266, 286170947, 2249288787, 3953585886, 1231725143, 2479045931, 2377059462, 281316188, 379113422, 920019004, 163289886, 2210874762, 1578529538, 309521495, 3737017316, 88919917, 559742618, 978230553, 2154491496, 994913727, 498894258, 1355546448, 4023836881, 3014313787, 164044564, 2408825840, 2029992558, 3707778216, 86206872, 3576935874, 185356787, 1774175910, 3145237900, 3497547609, 841914878, 3425254534, 4264030778, 2348022032, 178331591, 943923822, 3384367749, 2806712599, 1178535099, 1251085540, 2410015803, 1480595408, 2732607876, 1579706357, 870791724, 2320512780, 2149666862, 3797999384, 3905363134, 3388169321, 851973359, 1418716205, 207581030, 1740441523, 1173839013, 4280610104, 1769134281, 1758916333, 4061069248, 2147554262, 2749007447, 909878569, 2054562584, 1515003000, 560286390, 2482663802, 2690882951, 3298162668, 2561737261, 167825221, 507375343, 2179952491, 795452860, 2877704207, 3243106071, 1633372043, 2152178033, 2993246714, 4176238981, 3828458887, 695369535, 2514762808, 2251430819, 2743651063, 783239046, 4036497041, 2175424426, 765021321, 897227922, 3192938155, 4173350810, 2290496185, 4215986056, 2448481441, 3114984799, 2920066349, 722868808, 594363801, 4012575088, 454547939, 3331771662, 1267229957, 3170277692, 2446344734, 3730529788, 2621611481, 2972284304, 2580290241, 486727007, 2727955445, 1457071884, 1053028185, 462301682, 3907840756, 1832398102, 3144685297, 3403964915, 4263570498, 792776003, 306771255, 1633688240, 2159479271, 942060576, 1311531808, 3145754189, 4142271069, 2844524541, 4082439147, 2847276716, 1374436698, 2601522390, 529644524, 206090172, 3015114937, 4137169373, 2600331537, 344659140, 155319271, 1724932164, 3187877676, 4020168431, 711431575, 4123955169, 2539963709, 2764832709, 3897838285, 2521203644, 2059212822, 1129046005, 3277260664, 2739869189, 1955591901, 2661672178, 2926355273, 28176978, 706409211, 1432061304, 26517996, 3180196905, 2178525849, 607854674, 3953350517, 3532394548, 4175940932, 626671309, 1273934270, 3481828801, 22643989, 2104739013, 4183577772, 3932721637, 3075788222, 2814353001, 4120869721, 2045506903, 603494333, 335162960, 2069261279, 2278614835, 210140447, 2012566692, 2345710126, 70390387, 457247932, 2764651800, 652766919, 555253440, 864036913, 1720142260, 453262569, 1113437101, 2576419688, 144008475, 1786881829, 2455128823, 2884922345, 4251332234, 58949785, 4206002785, 3374754553, 2976162198, 546450687, 1268444784, 4132330381, 3404894280, 2421962142, 212361299, 2526283704, 1656118437, 1249336298, 305885855, 1090758249, 3752057640, 3508190692, 3637428, 105102422, 2247418237, 1873609555, 1206760240, 3761689119, 3151616638, 1711308858, 1261541178, 1843103377, 3158893523, 1226253110, 3337577909, 126612372, 2239219657, 1415387229, 3657507305, 3330696118, 2304219467, 3782535397, 2523926865, 173770442, 469421316, 4068724979, 567442650, 1996215573, 2071307093, 778899724, 3534102235, 1001138889, 2821812427, 591691317, 1265763678, 2241915660, 3220601768, 653090205, 2367897867, 1393909319, 2691817329, 3098049768, 117121403, 1255294678, 2272844919, 788255921, 2333869622, 4052660679, 2407095869, 2636108242, 2204717619, 1672726444, 2250826426, 258706466, 2295454699, 337308034, 3703973770, 3133498524, 22718827, 3096937679, 2039003308, 1519854757, 568184976, 1986854118, 2888207511, 822307630, 3829301724, 3198527490, 3073739663, 3043580445, 3458239370, 802145890, 376901460, 1251103099, 1143003993, 1280321148, 661386076, 3708710489, 2237151715, 3928104641, 2975550516, 1087492088, 1504028830, 61927086, 3858242888, 1916136658, 2328550074, 3032032377, 2193802260, 3311627503, 3196945045, 3396801792, 806210594, 2449941623, 2514744466, 3922130206, 3245757763, 3128328446, 2335833206, 3205660364, 3527402441, 2174241644, 1262568556, 2360103007, 2490217737, 1485100950, 3407260, 3005226942, 1355314866, 3154763465, 619881867, 2409963438, 2422269402, 205756019, 3300644241, 1157501775, 1229058028, 161050869, 969496287, 3385825249, 2557284067, 4236642714, 169094727, 2698326774, 1863176242, 3532885426, 3046403588, 3869207867, 496104150, 353604631, 1054882225, 152711981, 1362131890, 76912113, 3052177189, 3932252092, 3834713905, 2338378436, 44417325, 117723195, 1089433566, 4166617161, 2848021308, 2229619096, 319957702, 3661655667, 2809620731, 482011930, 3983483016, 82362287, 1518135562, 3490996143, 510129461, 1400609584, 2646113779, 732457215, 3735585198, 3451194227, 959269510, 244188667]

这里我也给出来吧，这样你们要是想做也能做了。

分析一下流程，我们最终实要得到这个r.rand()的值，我们才能得到flag。那么看一看rand是怎么运作的。

1
2
3
4
5
6
7
8
def rand(self):
	if self.index == 0:
		self.generate()
	y = self.MT[self.index]
	y = y ^ self.cs2l(y, 11) ^ self.cs2l(y,15)
	y = y ^ self.cs2r(y,7) ^ self.cs2r(y,19)
	self.index = (self.index + 1) % 624
	return y

可以看到，当index为0的时候，会将MT重新生成。

产生rand的时候，使用当前的index作为索引，使用MT[index]为基值进行变换最后得到我们的rand，同时index增长1。

1
2
3
4
5
6
import os
r = Myrand(int(os.urandom(4).hex(),16))
out = []

for i in range(624):
	out.append(r.rand())

在主流程的时里面，这里我们生成了624个rand。那么我们生成flag的时候，index的值是0。所以我们在生成flag的时候，MT表会先进行重新的生成。那么我们想要得到flag就得先得到对应的MT表。

1
2
3
y = self.MT[self.index]
y = y ^ self.cs2l(y, 11) ^ self.cs2l(y,15)
y = y ^ self.cs2r(y,7) ^ self.cs2r(y,19)

这里可以看到，我们的y是一种循环位移异或的生成方式，而且一共有3项，是奇数项。所以这个过程是可逆的可以计算的。具体的算法可以参照一下链接:

https://www.cnblogs.com/Tf1shC4T/p/15927062.html

那么我们就可以得到对应的MT表。然后对这个表进行重新生成，取第一个数进行随机数生成即可得到对应的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
# solve.py 
with open(r"output.txt") as fp:
    data = eval(fp.read())


def cs2l(y, shift):
    shift %= 32
    return ((y << shift) ^ (y >> (32 - shift))) & 0xffffffff


def cs2r(y, shift):
    shift %= 32
    return ((y >> shift) ^ (y << (32 - shift))) & 0xffffffff


key_right = [7, 19]
key_left = [11, 15]


# 破解右移
def decrypted_first(y, key):
    for _ in range(32):
        y = y ^ cs2r(y, key[0]) ^ cs2r(y, key[1])
        key = [k << 1 for k in key]
    return y


# 破解左移
def decrypted_second(y, key):
    for _ in range(32):
        y = y ^ cs2l(y, key[0]) ^ cs2l(y, key[1])
        key = [k << 1 for k in key]
    return y


MT = []


def generate():
    for i in range(624):
        y = (MT[i] & 0x80000000) + (MT[(i + 1) % 624] & 0x7fffffff)
        MT[i] = MT[(i + 397) % 624] ^ (y >> 1)
        if y & 1:
            MT[i] ^= 2567483520


def rand(index=0):
    if index == 0:
        generate()
    y = MT[index]
    y = y ^ cs2l(y, 11) ^ cs2l(y, 15)
    y = y ^ cs2r(y, 7) ^ cs2r(y, 19)
    index = (index + 1) % 624
    return y


if __name__ == "__main__":
    MT = []
    for i in data:
        MT.append(decrypted_second(decrypted_first(i, key_right), key_left))
    from hashlib import md5

    flag = 'DASCTF{' + md5(str(rand()).encode()).hexdigest() + '}'
    print(flag)

# DASCTF{49e225e5b1b57a1d3c9803b5ddfd38f9}

这里对这个解密多将两句吧。

这个其实可以使用左移右移混杂的，只是这一题不行。

这个方法的使用条件是右边异或的项数必须是奇数个，而且第一项是没有位移的。

例如下面这种情况：

y=x⊕(x⋙p)⊕(x⋘q)y = x \oplus (x \ggg p) \oplus (x \lll q)

那么对应的解密代码就是：

1
2
3
4
5
def decrypted(y, key):
	for _ in range(bitslen): # bitslen表示你进行运算的位宽度，这道题里面就是32位
		y = y ^ cs2r(y, p) ^ cs2l(y, q)
		key = [k << 1 for k in key]
	return y

提供对应的p,q也是可以解的。

一些题外话

好多题目都找不到writeup，每次打完一些比赛，想看看别人是怎么写出来那些我没写出来的题，但是基本上都找不到对应的Writeup。官方writeup也基本上没有。哎，也不认识那些大佬，想要题解都要不到。