老样子，赛后解题

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

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)

函数__init__(self,seed)用于初始化
函数rand(self)为主要函数
函数generate(self)用于当index为0时重新生成列表MT
函数cs2l(self, y, shift)用于将y按bit循环左移shift位
函数cs2r(self, y, shift)用于将y按bit循环右移shift位

由于是先生成了624个随机数，即遍历了一遍列表MT，再生成了flag
所以我们用给出的624个随机数逆推出列表MT的状态，再调用一下函数generate(self)，最后在生成一个随机数即可获得flag

此题的难点在于这两条语句的逆算法

1 2	y = y ^ self.cs2l(y, 11) ^ self.cs2l(y, 15) y = y ^ self.cs2r(y, 7) ^ self.cs2r(y, 19)

先看第一条语句，产生的结果等价如下方程组
$\begin{cases} a_{0} = b_{0} \oplus b_{11} \oplus b_{15} \\ a_{1} = b_{1} \oplus b_{12} \oplus b_{16} \\ a_{2} = b_{2} \oplus b_{13} \oplus b_{17} \\ a_{3} = b_{3} \oplus b_{14} \oplus b_{18} \\ a_{4} = b_{4} \oplus b_{15} \oplus b_{19} \\ a_{5} = b_{5} \oplus b_{16} \oplus b_{20} \\ a_{6} = b_{6} \oplus b_{17} \oplus b_{21} \\ a_{7} = b_{7} \oplus b_{18} \oplus b_{22} \\ a_{8} = b_{8} \oplus b_{19} \oplus b_{23} \\ a_{9} = b_{9} \oplus b_{20} \oplus b_{24} \\ a_{10} = b_{10} \oplus b_{21} \oplus b_{25} \\ a_{11} = b_{11} \oplus b_{22} \oplus b_{26} \\ a_{12} = b_{12} \oplus b_{23} \oplus b_{27} \\ a_{13} = b_{13} \oplus b_{24} \oplus b_{28} \\ a_{14} = b_{14} \oplus b_{25} \oplus b_{29} \\ a_{15} = b_{15} \oplus b_{26} \oplus b_{30} \\ a_{16} = b_{16} \oplus b_{27} \oplus b_{31} \\ a_{17} = b_{17} \oplus b_{28} \oplus b_{0} \\ a_{18} = b_{18} \oplus b_{29} \oplus b_{1} \\ a_{19} = b_{19} \oplus b_{30} \oplus b_{2} \\ a_{20} = b_{20} \oplus b_{31} \oplus b_{3} \\ a_{21} = b_{21} \oplus b_{0} \oplus b_{4} \\ a_{22} = b_{22} \oplus b_{1} \oplus b_{5} \\ a_{23} = b_{23} \oplus b_{2} \oplus b_{6} \\ a_{24} = b_{24} \oplus b_{3} \oplus b_{7} \\ a_{25} = b_{25} \oplus b_{4} \oplus b_{8} \\ a_{26} = b_{26} \oplus b_{5} \oplus b_{9} \\ a_{27} = b_{27} \oplus b_{6} \oplus b_{10} \\ a_{28} = b_{28} \oplus b_{7} \oplus b_{11} \\ a_{29} = b_{29} \oplus b_{8} \oplus b_{12} \\ a_{30} = b_{30} \oplus b_{9} \oplus b_{13} \\ a_{31} = b_{31} \oplus b_{10} \oplus b_{14} \end{cases}$

其中 $a$ ， $b$ 代表32位bit
已知 $a$ ，求 $b$

使 $a_{0} = a_{0} \oplus a_{11} \oplus a_{15}$ ，余下的式子模32递增下标
可得
$a_{0} = b_{0} \oplus b_{22} \oplus b_{30}$
$...$

重复上述操作得到
$a_{0} = b_{0} \oplus b_{12} \oplus b_{18}$

于是我猜想可能在进行足够多次的迭代运算后得到的结果是
$a_{0} = b_{0} \oplus b_{0} \oplus b_{0}$

即 $a_{0} = b_{0}$

编写脚本验证想法

equ = [
[0, 11, 15],
[1, 12, 16],
[2, 13, 17],
[3, 14, 18],
[4, 15, 19],
[5, 16, 20],
[6, 17, 21],
[7, 18, 22],
[8, 19, 23],
[9, 20, 24],
[10, 21, 25],
[11, 22, 26],
[12, 23, 27],
[13, 24, 28],
[14, 25, 29],
[15, 26, 30],
[16, 27, 31],
[17, 28, 0],
[18, 29, 1],
[19, 30, 2],
[20, 31, 3],
[21, 0, 4],
[22, 1, 5],
[23, 2, 6],
[24, 3, 7],
[25, 4, 8],
[26, 5, 9],
[27, 6, 10],
[28, 7, 11],
[29, 8, 12],
[30, 9, 13],
[31, 10, 14]]

import copy

def self_xor(number1, number2):
	new_equ = []
	length = len(equ)
	for _ in range(length):
		equ1 = [x for x in equ[_]]
		equ2 = [x for x in equ[(_ + number1)%length]]
		equ3 = [x for x in equ[(_ + number2)%length]]
		for __ in equ2:
			if __ in equ1:
				equ1.pop(equ1.index(__))
			else:
				equ1.append(__)
		for __ in equ3:
			if __ in equ1:
				equ1.pop(equ1.index(__))
			else:
				equ1.append(__)
		new_equ.append(equ1)
	return new_equ


equ = self_xor(25, 13)
equ = self_xor(18, 26)
equ = self_xor(4, 20)
for _ in equ:
	print(_)

最后的输出结果可以验证想法正确，且获得了迭代异或运算的shitf值
第二条语句的逆向算法同理

def bits_xor(bits, shift1, shift2):
	old_bits = bits
	length = len(bits)
	new_bits = ""
	for _ in range(length):
		new_bits = new_bits + str(int(old_bits[_]) ^ int(old_bits[(_+shift1)%length]) ^ int(old_bits[(_+shift2)%length]))
	return new_bits

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

def reverse_cs2l(y):
	bits = bin(y)[2:]
	bit_len = len(bits)
	bits32 = "0" * (32 - bit_len) + bits
	bits32 = bits_xor(bits32, 11, 15)
	bits32 = bits_xor(bits32, 22, 30)
	bits32 = bits_xor(bits32, 12, 28)
	number = int(bits32, 2)
	return number

def reverse_cs2r(y):
	bits = bin(y)[2:]
	bit_len = len(bits)
	bits32 = "0" * (32 - bit_len) + bits
	bits32 = bits_xor(bits32, 25, 13)
	bits32 = bits_xor(bits32, 18, 26)
	bits32 = bits_xor(bits32, 4, 20)
	number = int(bits32, 2)
	return number

f = open("./output.txt", "r")
data = f.read().split(", ")
f.close()
MT = []
for _ in data:
	MT.append(reverse_cs2l(reverse_cs2r(int(_))))

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

y = MT[0]
y = y ^ cs2l(y, 11) ^ cs2l(y, 15)
y = y ^ cs2r(y, 7) ^ cs2r(y, 19)
from hashlib import md5
flag = 'DASCTF{' + md5(str(y).encode()).hexdigest() + '}'
print(flag)

1	DASCTF{49e225e5b1b57a1d3c9803b5ddfd38f9}

后面两题随缘更新

更个锤子，Crypto2 3想破头都没思路

xXxYOLOxXx

DASCTF_MAY_2022

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