2023-TPCTF-Crypto-WP

Crypto:

blurred_memory：

题目：

from random import sample
from secret import flag


assert flag[:6] == 'TPCTF{' and flag[-1] == '}'
flag = flag[6:-1]

assert len(set(flag)) == len(flag)

xs = []
for i, c in enumerate(flag):
    xs += [ord(c)] * (i + 1)

p = 257
out = [sum(pow(x, k, p) for x in xs) % p for k in range(1, len(xs) + 1)]
print(f'out={out}')
'''
out = [125, 31, 116, 106, 193, 7, 38, 194, 186, 33, 180, 189, 53, 126, 134, 237, 123, 65, 179, 196, 99, 74, 101, 153, 84, 74, 233, 5, 105, 32, 75, 168, 161, 2, 147, 18, 68, 68, 162, 21, 94, 194, 249, 179, 24, 60, 71, 12, 40, 198, 79, 92, 44, 72, 189, 236, 244, 151, 56, 93, 195, 121, 211, 26, 73, 240, 76, 70, 133, 186, 165, 48, 31, 39, 3, 219, 96, 14, 166, 139, 24, 206, 93, 250, 79, 246, 256, 199, 198, 131, 34, 192, 173, 35, 0, 171, 160, 151, 118, 24, 10, 100, 93, 19, 101, 15, 190, 74, 10, 117, 4, 41, 135, 45, 107, 155, 152, 95, 222, 214, 174, 139, 117, 211, 224, 120, 219, 250, 1, 110, 225, 196, 105, 96, 52, 231, 59, 70, 95, 56, 58, 248, 171, 16, 251, 165, 54, 4, 211, 60, 210, 158, 45, 96, 105, 116, 30, 239, 96, 37, 175, 254, 157, 26, 151, 141, 43, 110, 227, 199, 223, 135, 162, 112, 4, 45, 66, 228, 162, 238, 165, 158, 27, 18, 76, 36, 237, 107, 84, 57, 233, 96, 72, 6, 114, 44, 119, 174, 59, 82, 202, 26, 216, 35, 55, 159, 113, 98, 4, 74, 2, 128, 34, 180, 191, 8, 101, 169, 157, 120, 254, 158, 97, 227, 79, 151, 167, 64, 195, 42, 250, 207, 213, 238, 199, 111, 149, 18, 194, 240, 53, 130, 3, 188, 41, 100, 255, 158, 21, 189, 19, 214, 127]
'''

分析：

• 输入一串字符串，先进行分割处理，如下：

输入:x_1x_2x_3…x_n\ 得到:[x_1,x_2,x_2,x_3,x_3,x_3,…,x_n,x_n]

• 接下来将处理数组的每个元素在有限域GF(257)下做n次幂乘，然后求和添入out中。

大致形式如下：

out[0] = x0 + 2*x1 + 3*x2 + ... + n*x_{n-1}(modp)
out[1] = x0^2 + 2*x1^2 + 3*x2^2 + ... + n*x_{n-1}^{2} (modp)
out[2] = x0^3 + 2*x1^3 + 3*x2^3 + ... + n*x_{n-1}^{3} (modp)
out[3] = x0^4 + 2*x1^4 + 3*x2^4 + ... + n*x_{n-1}^{4} (modp)
out[4] = x0^5 + 2*x1^5 + 3*x2^5 + ... + n*x_{n-1}^{5} (modp)
out[5] = x0^6 + 2*x1^6 + 3*x2^6 + ... + n*x_{n-1}^{6} (modp)

我们的目标是从输出的和中，求出每一个元(x_n)。

先进行一些未知数、可用式子的估计，看看从哪里下手：

通过简单的求和判断可以知道，我们的未知数一共是22个，可用的式子大致55个(没记错的话)，而且这个式子的形式化成矩阵之后可以发现：很像范德蒙德矩阵，但是由于方程组是非线性的，我们也没办法直接通过常规的高斯消元之类的办法解出来。

那么现在就想到有两种办法去解这种问题：

• 通过多项式小根求解的办法(Grobner基)去求多元的根。
• 通过化简多项式的办法，找出根之间的关系，进行消元求解。

所以一开始的思路就自然而然的想要用Gröbner基，去求每一个根。如下：

p = 257
PR.<x0,x1,x2,x3,x4,x5,x6,x7> = PolynomialRing(GF(p))
fs = []

out = [45, 41, 256, 124, 54, 35]
for i in range(len(out)):
    f = x0^(i+1) + 2*x1^(i+1) + 3*x2^(i+1)- out[i]
    fs.append(f)
    print(f)
I = Ideal(fs)
I.groebner_basis()

求六七个根还好，到后面直接爆了。

队内的师傅告诉我说这个是不行的，因为groebner_basis()的时间复杂度是O(n)，添加的元越多，指数越高，到后面就越难搞，至于题目中的22元更加不用说了，所以思路一自然而然地Fail了。

考虑从化简的地方下手：

先别把变量合并。那这是对称多项式方程组，找了一下symmetric poly system求解方法，牛顿对称多项式能转成初等对称多项式（两者关系叫牛顿恒等式）。而且这些多项式恰对应一个单变量多项式方程的解。从而变元成了一个，自然能求。——密码爷爷

化简的办法如下(化简核心原理)：文章在这

所以求解大致步骤：

1. 用牛顿恒等式，求初等对称多项式的值
2. 找到与之相关的253次首一多项式，其他系数是交错的初等对称多项式的值
3. 直接在Fp上解253次方程。甚至直接代数进去验证就行

那么exp如下：

exp:

#SageMath
output = [125, 31, 116, 106, 193, 7, 38, 194, 186, 33, 180, 189, 53, 126, 134, 237, 123, 65, 179, 196, 99, 74, 101, 153, 84, 74, 233, 5, 105, 32, 75, 168, 161, 2, 147, 18, 68, 68, 162, 21, 94, 194, 249, 179, 24, 60, 71, 12, 40, 198, 79, 92, 44, 72, 189, 236, 244, 151, 56, 93, 195, 121, 211, 26, 73, 240, 76, 70, 133, 186, 165, 48, 31, 39, 3, 219, 96, 14, 166, 139, 24, 206, 93, 250, 79, 246, 256, 199, 198, 131, 34, 192, 173, 35, 0, 171, 160, 151, 118, 24, 10, 100, 93, 19, 101, 15, 190, 74, 10, 117, 4, 41, 135, 45, 107, 155, 152, 95, 222, 214, 174, 139, 117, 211, 224, 120, 219, 250, 1, 110, 225, 196, 105, 96, 52, 231, 59, 70, 95, 56, 58, 248, 171, 16, 251, 165, 54, 4, 211, 60, 210, 158, 45, 96, 105, 116, 30, 239, 96, 37, 175, 254, 157, 26, 151, 141, 43, 110, 227, 199, 223, 135, 162, 112, 4, 45, 66, 228, 162, 238, 165, 158, 27, 18, 76, 36, 237, 107, 84, 57, 233, 96, 72, 6, 114, 44, 119, 174, 59, 82, 202, 26, 216, 35, 55, 159, 113, 98, 4, 74, 2, 128, 34, 180, 191, 8, 101, 169, 157, 120, 254, 158, 97, 227, 79, 151, 167, 64, 195, 42, 250, 207, 213, 238, 199, 111, 149, 18, 194, 240, 53, 130, 3, 188, 41, 100, 255, 158, 21, 189, 19, 214, 127]
len_out = len(output)
print(len_out)

len_flag = int(sqrt(float(len_out * 2)))
assert len_flag * (1+len_flag)//2 == len_out 

p = 257
Fp = GF(p)
xi_list = [f'x{i}' for i in range(len_flag)]
R = PolynomialRing(Fp, xi_list, len_flag)
xi_list = R.gens()

pk_list = output
# add a junk
pk_list.insert(0, None)

# Ref: https://zh.wikipedia.org/wiki/%E7%89%9B%E9%A0%93%E6%81%86%E7%AD%89%E5%BC%8F
# must have a junk at pk_list[0], which won't be used
def solve_elementary_sym_polys(pk_list, num=253):
    assert num == len(pk_list) - 1 

    ek_list = [1]

    # compute ek for 1=< k <= num
    for k in range(1, num+1):
        ek = 0
        # compute kek
        for i in range(1, k+1):
            ek += (-1)**(i-1) * ek_list[k-i] * pk_list[i]
            ek %= p
        ek = (inverse_mod(k, p) * ek) % p
    
        ek_list.append(ek)        
    
    return ek_list
    
    ek_list = solve_elementary_sym_polys(pk_list)
    
    Fpt.<t> = PolynomialRing(Fp)
    Pt = t**253
    for i in range(1, 254):
        Pt += (-1)**i * ek_list[i]* t**(253-i)
    print(Pt)
    
flags = Pt.roots()
print(flags)

flag = ""
for mi, _ in flags:
    flag += chr(mi)
print(flag)

sort-teaser:

题目:

import re
from Crypto.Util.number import bytes_to_long
import random

letters=set(bytes(range(65,91)).decode())
class Command:
    def __init__(self, target_var, op, l, r=0):
        self.target_var = target_var
        self.op = op
        self.l = l if l in letters else int(l)
        self.r = r if r in letters else int(r)
    def __str__(self):
        return self.target_var+"="+str(self.l)+((self.op+str(self.r)) if self.op!="=" else "")
    __repr__=__str__

class Computation:
    def __init__(self):
        self.vars={x:0 for x in letters}
    
    def resolve_val(self,symbol):
        return self.vars[symbol] if type(symbol)==str else symbol
    
    def run(self,cmd):
        if cmd.op=='+':
            self.vars[cmd.target_var]=self.resolve_val(cmd.l)+self.resolve_val(cmd.r)
            if self.vars[cmd.target_var].bit_length()>100000:
                raise OverflowError
        elif cmd.op=='-':
            self.vars[cmd.target_var]=self.resolve_val(cmd.l)-self.resolve_val(cmd.r)
            if self.vars[cmd.target_var].bit_length()>100000:
                raise OverflowError
        elif cmd.op=='*':
            self.vars[cmd.target_var]=self.resolve_val(cmd.l)*self.resolve_val(cmd.r)
            if self.vars[cmd.target_var].bit_length()>100000:
                raise OverflowError
        elif cmd.op=='/':
            self.vars[cmd.target_var]=self.resolve_val(cmd.l)//self.resolve_val(cmd.r)
        elif cmd.op=='%':
            self.vars[cmd.target_var]=self.resolve_val(cmd.l)%self.resolve_val(cmd.r)
        elif cmd.op=='&':
            self.vars[cmd.target_var]=self.resolve_val(cmd.l)&self.resolve_val(cmd.r)
        elif cmd.op=='|':
            self.vars[cmd.target_var]=self.resolve_val(cmd.l)|self.resolve_val(cmd.r)
        elif cmd.op=='^':
            self.vars[cmd.target_var]=self.resolve_val(cmd.l)^self.resolve_val(cmd.r)
        elif cmd.op=='<':
            self.vars[cmd.target_var]=int(self.resolve_val(cmd.l)<self.resolve_val(cmd.r))
        elif cmd.op=='>':
            self.vars[cmd.target_var]=int(self.resolve_val(cmd.l)>self.resolve_val(cmd.r))
        elif cmd.op=='<=':
            self.vars[cmd.target_var]=int(self.resolve_val(cmd.l)<=self.resolve_val(cmd.r))
        elif cmd.op=='>=':
            self.vars[cmd.target_var]=int(self.resolve_val(cmd.l)>=self.resolve_val(cmd.r))
        elif cmd.op=='!=':
            self.vars[cmd.target_var]=int(self.resolve_val(cmd.l)!=self.resolve_val(cmd.r))
        elif cmd.op=='==':
            self.vars[cmd.target_var]=int(self.resolve_val(cmd.l)==self.resolve_val(cmd.r))
        elif cmd.op=='<<':
            if self.resolve_val(cmd.l).bit_length()+self.resolve_val(cmd.r)>100000:
                raise OverflowError
            self.vars[cmd.target_var]=int(self.resolve_val(cmd.l)<<self.resolve_val(cmd.r))
        elif cmd.op=='>>':
            self.vars[cmd.target_var]=int(self.resolve_val(cmd.l)>>self.resolve_val(cmd.r))
        elif cmd.op=='=':
            self.vars[cmd.target_var]=self.resolve_val(cmd.l)

def parse_command(cmdstr):
    cmdstr=re.sub("\s","",cmdstr)
    m=re.match("^([A-Z])=([A-Z]|-?\d+)$",cmdstr)
    if m:
        return Command(m[1],"=",m[2])
    m=re.match("^([A-Z])=([A-Z]|-?\d+)([+\-*/%&|^><]|[><!=]=|<<|>>)([A-Z]|-?\d+)$",cmdstr)
    if m:
        return Command(m[1],m[3],m[2],m[4])
    m=re.match("^([A-Z])=-([A-Z])$",cmdstr)
    if m:
        return Command(m[1],"-",0,m[2])
    raise SyntaxError

def run_commands(fun, init_state):
    comp=Computation()
    comp.vars.update(init_state)
    try:
        for i in fun:
            comp.run(i)
    except Exception as e:
        pass # exceptions are suppressed
    return comp.vars

def input_function(line_limit, cmd_limit):
    fun=[]
    while True:
        line = input().strip()
        if line == "EOF":
            break
        if len(line)>line_limit:
            assert False, "command too long"
        fun.append(parse_command(line))
        if len(fun)>cmd_limit:
            assert False, "too many commands"
    return fun

flag=open(f"flag.txt").read().strip()
assert len(flag)<32

print("Enter your function A:")
fun_A=input_function(100,30)


flag_array=list(flag.encode()) # the flag is static
A=[]
B=[]
for i in range(100):
    cur_A=bytes_to_long(bytes(flag_array))
    cur_res=run_commands(fun_A,{"A":cur_A})
    A.append(cur_A)
    B.append(cur_res["B"])
    random.shuffle(flag_array)

assert len(set(B))==1, "results are not same"
print(f'B={B}')
print(f'A={A}')


target_B=bytes_to_long(bytes(sorted(flag_array)))
print(f'target_B={target_B}')
if target_B==B[0]:
    print(flag)
else:
    print("You did not sort correctly")
exit(0)

分析：

题目很长，得先做源审，看看能输入什么和处理什么：

• 我们可以定义一个functionA，通过输入一些二元数学运算符和定义一些参数，对这个functionA进行100轮运算。（注意只能是顺序结构，而且不能注入其他指令）
• 对于每一轮的结果，都会把flag_array作为参数A代入计算，将参数B作为结果保存。
• 经过100轮计算后，如果发现第一轮的计算结果与flag相同，那么将给出flag。

简单地摆弄了一下题目之后，当真无奈了(赛后复盘发现确实是自己的想象力不够充分)。

那么通过一定的复盘，发现这道题其实和sql注入这种东西有种同工异曲之处，利用异常判断，去注入一些“搜索”命令，使得程序给出的反馈形成"Oracle"。

以下将给出队内师傅的解法：

exp:

这里注意到两种不同情况。如果100次测试输出不是完全相同，那么会抛出一个assert异常；而如果全都相同，但不等于要求的结果，则会给出另一种提示。从这里入手作区分，可以利用类似侧信道的思想去泄露出一些东西出来。

首先可以测出flag的长度，利用右移，不断调整移位长度即可：

'B=A>>232'
'EOF'
#flag_len:29

接着泄露字符。由于flag是静态的，而每次nc限制30行指令，因此需要爆破+分段来处理。指令大概就是按字符去比较，每次比较6个字符刚好极限30行（或许有更优的方法）。

from pwn import *
from Crypto.Util.number import *
import re,string,itertools
from hashlib import sha256

#context.log_level = 'debug'

#sh=remote('202.112.238.82','13371')
#sh=process(['python3','sort-teaser.py'])
global sh

sla = lambda a,b  :sh.sendlineafter(str(a),str(b))
sa  = lambda a,b  :sh.sendafter(str(a),str(b))
lg  = lambda name,data : sh.success(name + ": 0x%x" % data)
se  = lambda payload: sh.send(payload)
rl  = lambda      : sh.recvline()
rv  = lambda n    : sh.recv(n)
sl  = lambda payload: sh.sendline(payload)
ru  = lambda a     :sh.recvuntil(str(a))
rud = lambda a     :sh.recvuntil(str(a),drop=True)

#泄露字符种类
def test(o,i):
    global sh
    #sh=process(['python3','sort-teaser.py'])
    sh=remote('202.112.238.82','13371')
    rl()
    sl(f'C={o}')
    sl('T=A&255')
    sl('N=0')
    sl(f'A=A>>{i*6*8}')
    for _ in range(6):
        sl('F=A&255')
        sl('G=C==F')
        sl('N=N+G')
        sl('A=A>>8')
    sl('B=T&N')
    sl('EOF')
    res=b'Traceback' in rl()
    sh.close()
    return res
 
chars=[]
for o in range(32,126):
    tmp=0
    for i in range(5):
        if test(o,i):
            tmp+=1
    if tmp==5:
        chars.append(o)
    print(chars)
s=''.join(map(chr,chars))
print(s,len(s))
print(bytes_to_long(s.encode()))
sh.interactive()
'''
[49, 65, 67, 70, 80, 84, 95, 97, 99, 100, 101, 103, 104, 108, 110, 114, 115, 116, 123, 125]
1ACFPT_acdeghlnrst{} 20
'''

flag字符种类20个，长度为29。看来确实需要统计次数，然而这个不咋好弄，想了个办法先把2次以上的统计出来，具体就是在位运算上做了点trick。严格意义上不是精确统计，但概率还是比较大（100次里至少1次发生2个以上相同字符出现在6个字符里）。

#统计出现2次以上的字符
def test(o,i):
    global sh
    #sh=process(['python3','sort-teaser.py'])
    sh=remote('202.112.238.82','13371')
    rl()
    sl(f'C={o}')
    sl('T=A&254')
    sl(f'N=0')
    sl(f'A=A>>{i*6*8}')
    for _ in range(6):
        sl('F=A&255')
        sl('G=C==F')
        sl('N=N+G')
        sl('A=A>>8')
    #sl('N=N&2)
    sl('B=T&N')
    sl('EOF')
    res=b'Traceback' in rl()
    sh.close()
    return res

chars=[49, 65, 67, 70, 80, 84, 95, 97, 99, 100, 101, 103, 104, 108, 110, 114, 115, 116, 123, 125]
dic={}
for o in chars:
    dic[o]=1
    for i in range(5):
        if test(o,i):
            #print(o,i)
            dic[o]=2
            break
    print(dic)
s=''.join([ chr(k)*v for k,v in dic.items()])
print(s,len(s))
'''
{49: 1, 65: 2, 67: 1, 70: 1, 80: 1, 84: 2, 95: 2, 97: 1, 99: 1, 100: 1, 101: 2, 103: 1, 104: 1, 108: 1, 110: 2, 114: 1, 115: 2, 116: 1, 123: 1, 125: 1}
1AACFPTT__acdeeghlnnrsst{} 26
'''

后面差3个字符，懒得改trick了，连蒙带猜出来的。

res='1AACFPTT___acdeeeghlnnnrsst{}'
res=bytes_to_long(res.encode())
rl()
sl(f'B={res}')
sl('EOF')
#TPCTF{A_strAnge_s1de_channel}

确实蛮震撼的。

复现不动另外几个密码了，感觉有点诡异：

这里贴一下部分的wp:

sort三连：WP

Reverse:

apple:

题目:

flag = "QWERTYUIOPASDFGHJKLZXCVBNM01234567"
def funcA(num):
    result = 0
    n = num
    i=0
    while(n!=0):
        if(n & 1):
            result ^= (0b11011 << i)
        n >>= 1
        i+=1
    return result 

def revA(num):
    result = 0
    n = num
    i=0
    while(n!=0):
        if(n & 1):
            result |= 1 << i
            n ^= 0b11011
        n = n >> 1
        i += 1
    return result
    
flagInputted = []
for i in range(len(flag)):
    flagInputted.append((flag[i:]+flag[0:i]))
    
sortedFlag = sorted(flagInputted)

# for f in sortedFlag :
#     print(f)

flag2 = ""
for f in sortedFlag :
    id = flagInputted.index(f)
    # print((id-1)%len(flag),flag[(id-1)%len(flag)])
    flag2 += flag[(id-1)%len(flag)]
    

flag2 = bytearray(flag2.encode())
if(len(flag2) // 8 != 0):
    flag2 += b'\x00' * (8 - ((len(flag2) % 8)))
print(flag2)
    
#Binary

#NOT
for i in range(len(flag2)):
    flag2[i] = (~flag2[i])%256
    
#REVERSE BIN
for i in range(len(flag2)):
    t = bin(flag2[i])[2:].zfill(8)[::-1]
    flag2[i] = int(t,2)
    
#NOT
# for i in range(len(flag2)):
#     flag2[i] = (~flag2[i])%256

print(flag2.hex())

flag3 = []
for i in range(len(flag2)//8):
    part = flag2[8*i:8*i+8]
    num = int.from_bytes(part,'big')
    num1 = funcA(num)
    num2 = funcA(num1 >> 64)
    num3 = (num2 ^ num1) & 0xffffffffffffffff
    
    # NOT 
    num3 ^=  0xffffffffffffffff
    #REVERSE BIN
    result = bin(num3)[2:].zfill(64)[::-1]
    flag3.append(result)
    print(result)
    
#LAST

final_result = [48 for _ in range(64)]
for i in range(len(flag3)):
    for j in range(64):
        final_result[j] += int(flag3[-(i+1)][j]) * (2**i) 
        
final_flag = "".join([chr(i) for i in final_result])

print(final_flag[4:])

'''
TEST OK
QWERTYUIOPASDFGHJKLZXCVBNM012345
1?9>31:0=756>?682=74411836632074040=:7:;65::78;772=1;71=:61>

QWERTYUIOPASDFGHJKLZXCVBNM01234567
GJ2@9CCA7M=GE1O91I1;5?5G=;55?17??5;CG?CK5=CM1DF5=>D8C1:@M77D

FIND 
T]OZ7E7UG59[G[456^Tb6=>B`QGhfLBTUQ2hRYFTT7XdDg__?Z9cVZ17ZR02

TPCTF{}
'''

队内大手子贴心地帮我们逆完了程序，直接给出测试样例和Python源码，那么这时候的工作就和干密码分析、逆向差不多了。

分析：

• 首先这个源码因为是直接硬扒下来做源审的，通过测试样例之后可以确定有效性，那么就确定可以当做密码题来写了。接下来从上到下去分析这个加密的逻辑、以及逆向的思路
• Encrypt1:将输入的flag进行一定的乱序排序(不完全无规则，后文会给出原因)。
• Encrypt2:将输入的flag进行类似于DES中S盒、P盒一样的变换，将源输入拓展成num1,num2，并异或后再与掩码异或输出。
• Encrypt3:类似于背包加密一样，在bit级别程度上，将输入的比特每一位分散到final_result每一位的上面。

像这种纯对称的，照着逻辑一点点拼回去就行，难度没什么大的，但是为什么要在这里写这篇分析？(因为我解出来了)

因为这里可以注意到输出结果的时候是丢失了四位密文的（就在最后一步输出那里），简单地想一下，如果我照着完全密文去逆，然后求出Encrypt1那部分的输出(因为还原第一部分还要处理一个乱序，这个后面再说)。时间复杂度会不会太高了？我们需要爆破4位字符！(大小写字母、数字、特殊字符)，加上一堆运算，这个能跑是能跑，但是得跑半天都有可能。

那么这里给出写这篇分析的理由：我们可以用一定的办法去缩减这种情况的复杂度！

总之，先把正常情况下，无信息缺失的解密逆出来，然后再考虑信息缺失的情况：

part1:逆向操作

from Crypto.Util.number import *
import itertools
import string
from tqdm import tqdm

def funcA(num):
    result = 0
    n = num
    i=0
    while(n!=0):
        if(n & 1):
            result ^= (0b11011 << i)
        n >>= 1
        i+=1
    return result 

def revA(num):
    result = 0
    n = num
    i = 0
    k = 0
    while (n != 0):
        k+=1
        if (n & 1):
            result |= 1 << i
            n ^= 0b11011
        n = n >> 1
        i += 1
        if k > 100:
            return 0
    return result

def re3(text):
    result = ['']*6
    tmp = [ord(i)-48 for i in text]
    for i in range(64):
        for j in range(5):
            if tmp[i] & (1<<j):
                result[j] += '1'            
            else:
                result[j] += '0'
    return result[::-1]


def re2(text):
    result = b''
    tmp  = eval('0b'+text[::-1])
    num3 = tmp ^ 0xffffffffffffffff
    for high_bit in range(16):
        num2 = funcA(high_bit)
        num1_ = num3^num2
        num1 = (high_bit << 64) + num1_
        #print(num1)
        num = revA(num1)
        num_ = long_to_bytes(num)
        if len(num_) > len(result):
            result = num_
    return result

def re(text):
    text = bytearray(text)
    for _ in range(len(text)):
        t = bin(text[_])[2:].zfill(8)[::-1]
        text[_] = int(t,2)
    for i in range(len(text)):
        text[i] = (~text[i])%256
    return text

def encrypt2(part):
    num = int.from_bytes(part,'big')
    num1 = funcA(num)
    num2 = funcA(num1 >> 64)
    num3 = (num2 ^ num1) & 0xffffffffffffffff
    num3 ^=  0xffffffffffffffff
    result = bin(num3)[2:].zfill(64)[::-1]
    return result

def encrypt(flag2):
    flag2 = bytearray(flag2)
    for i in range(len(flag2)):
        flag2[i] = (~flag2[i])%256
    for i in range(len(flag2)):
        t = bin(flag2[i])[2:].zfill(8)[::-1]
        flag2[i] = int(t,2)
    return flag2

def dec(text):
    mid = re3(text)
    result = b''
    for _ in mid:
        result += re2(_)
    result = re(result)
    return result

除了encrypt1都弄好了。正常的输出（无缺失的情况下），也是可以逆的（程序解密无问题）。

在爆破之前，想一个问题，这个缺失的四字符是会对每一个密文块都有影响吗？好像确实不是，虽然这个程序仿造了DES的一些处理逻辑，但是这个缺失的四字符并不是构成逆解密的唯一解！我们是有机会通过其他情况(解密有效字符较多的时候)，得到部分密文前缀的。

例如：假设我现在的字典只有大写字母，这个爆破的时间复杂度完全是可以接受的，所有的解密里面，出现了那么几组有效字符位置相同，内容相同的情况，我们是否可以认为这种情况下撞对了部分字符？只要撞出一个字符，后面三个的爆破就是轻而易举了！

照着这个思路去碰，碰第一组得到Z，X，z，x开头前缀情况下得到的有效信息很多，那么根据ascii码判断可以知道，前缀肯定是在这个范围区间里面，第一位大概率是X,Z——或是旁边的相关特殊字符等。

如下尝试：

valid_char = [ord(x) for x in string.digits +
              string.ascii_letters + string.punctuation]

def check(s: bytes): #检查有效字符
    r = list(map(lambda x: x in valid_char, s))
    if False in r:
        return 0
    else:
        return 1

dic = '!@#$%^&*()_+{}":?><,./;\'[]=-'

#tmp = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ[]\\^-\'abcdefghijklmnopqrstuvwxyz'
#tmp = tmp[::-1]
#print(len(string.ascii_letters+string.digits+dic))
with open('flag1.txt','w') as f:
    for i in tqdm(itertools.product(string.ascii_letters+string.digits+dic, repeat=3)):
            x = "[{}{}{}".format(i[0],i[1],i[2])
            enc = x+'T]OZ7E7UG59[G[456^Tb6=>B`QGhfLBTUQ2hRYFTT7XdDg__?Z9cVZ17ZR02'
            mid = re3(enc)
            enc2 = b''
            enc2 += re2(mid[0])
            enc2 += re2(mid[1])
            enc2 += re2(mid[2])
            result = re(enc2)
            if check(result):
                f.write(str(result)+f'fix={x}'+'\n')
                print(dec(enc),f'fix={x}')
                #break

我们可以利用上述的思路很快的碰出前缀：[ecGT，然后得到乱序的密文：

s5vrn6__3C{_R_PTPTACC}-43LrhelWerr4e0ruwBv4oF3

part2:

再去分析第一段加密的逻辑：

• 可以发现排序的id是按照首字母大小排的（很大概率）
• 取字符的时候是取该字母的前一位

那么我们有如下的映射关系：

![1}P1AVR)RIGFCPRADL@$R.png](/upload/$R.png)

下面的flag2是正常排序，flag的乱序后输出的，上下位大概会是一一对应的映射关系，我们可以得到两字母的顺序，通过组合起来，极大概率能得到flag:

flag2 = 's5vrn6__3C{_R_PTPTACC}-43LrhelWerr4e0ruwBv4oF3'
print(flag2)
sortedFlag = sorted(list(flag2))
print(''.join(sortedFlag))
flagInputted = {}
flag = []
p = 17
tmp0 = [[flag2[p], sortedFlag[p]]]
flag_ = list(flag2)
tmp1 = [flag_[:p] + flag_[p+1:]]
sortedFlag_ = list(sortedFlag)
tmp2 = [sortedFlag[:p]+sortedFlag_[p+1:]]

for i in range(len(flag2)):
    flag, tmp0 = tmp0, []
    flag_, tmp1 = tmp1, []
    sortedFlag_, tmp2 = tmp2, []
    for j in range(len(flag_)):
        for k in range(len(sortedFlag_[j])):
            if flag[j][1][-1] == flag_[j][k]:
                if (i >= 6 and flag[j][0].startswith('TPCTF{')) or i <6:
                    tmp0.append([flag[j][0]+flag_[j][k], flag[j][1]+sortedFlag_[j][k]])
                    tmp1.append(flag_[j][:k] + flag_[j][k+1:])
                    tmp2.append(sortedFlag_[j][:k] + sortedFlag_[j][k+1:])

2万种可能，看起来很迷惑，再丢进去加密看结果是否和原密文一样就好：

def encode(flag):
    def funcA(num):
        result = 0
        n = num
        i = 0
        while (n != 0):
            if (n & 1):
                result ^= (0b11011 << i)
            n >>= 1
            i += 1
        return result

    def revA(num):
        result = 0
        n = num
        i = 0
        while (n != 0):
            if (n & 1):
                result |= 1 << i
                n ^= 0b11011
            n = n >> 1
            i += 1
        return result

    flagInputted = []
    for i in range(len(flag)):
        flagInputted.append((flag[i:] + flag[0:i]))

    sortedFlag = sorted(flagInputted)

    # for f in sortedFlag :
    #     print(f)

    flag2 = ""
    for f in sortedFlag:
        id = flagInputted.index(f)
        # print((id-1)%len(flag),flag[(id-1)%len(flag)])
        flag2 += flag[(id - 1) % len(flag)]

    flag2 = bytearray(flag2.encode())
    if (len(flag2) // 8 != 0):
        flag2 += b'\x00' * (8 - ((len(flag2) % 8)))

    # Binary

    # NOT
    for i in range(len(flag2)):
        flag2[i] = (~flag2[i]) % 256

    # REVERSE BIN
    for i in range(len(flag2)):
        t = bin(flag2[i])[2:].zfill(8)[::-1]
        flag2[i] = int(t, 2)

    # NOT
    # for i in range(len(flag2)):
    #     flag2[i] = (~flag2[i])%256


    flag3 = []
    for i in range(len(flag2) // 8):
        part = flag2[8 * i:8 * i + 8]
        num = int.from_bytes(part, 'big')
        num1 = funcA(num)
        num2 = funcA(num1 >> 64)
        num3 = (num2 ^ num1) & 0xffffffffffffffff

        # NOT
        num3 ^= 0xffffffffffffffff
        # REVERSE BIN
        result = bin(num3)[2:].zfill(64)[::-1]
        flag3.append(result)

    # LAST

    final_result = [48 for _ in range(64)]
    for i in range(len(flag3)):
        for j in range(64):
            final_result[j] += int(flag3[-(i + 1)][j]) * (2 ** i)

    final_flag = "".join([chr(i) for i in final_result])
    return final_flag
    
for i in flag:
    if encode(i[0])[4:]=='T]OZ7E7UG59[G[456^Tb6=>B`QGhfLBTUQ2hRYFTT7XdDg__?Z9cVZ17ZR02':
        print(i[0])

可惜拿的是四血，没有播报，sad。

虽然是逆向，但是着实是密码手魅力时刻了。

最后总结一下这次比赛的收获：

• 大比赛很多方向的考点的内容都是和其他方向联动互通的，单学密码学的话这把确实输得挺惨。有一些内容可能会在WEB的注入里面出现过，有些逆向分析的技巧和手法确实会对写脚本和分析挺有用的。
• 关于多项式的根、多项式的性质运算技巧之类的(又学一轮grobner basis)，期间还翻了一堆small_root的解法，学到了蛮多办法的（除了Coppersmith）。
• 逆向，逆个痛快了。

当然还有一些密码题解，例如nanoOTP那个，之后大概率还会再弄弄，去年的revenge，虽然去年全场都是非预期的（

比赛时候发现本地的话去年的办法还是可以通的，远程就不行了，这几天听别队师傅透露了一些解法，大概率会再学学，学好了再发（