SekaiCTF 2022

浅写两道Crypto

Crypto

Time Capsule

加密代码：

import time
import os
import random

from SECRET import flag

def encrypt_stage_one(message, key):
    u = [s for s in sorted(zip(key, range(len(key))))]
    res = ''

    for i in u:
        for j in range(i[1], len(message), len(key)):
            res += message[j]

    return res

def encrypt_stage_two(message):
    now = str(time.time()).encode('utf-8')
    now = now + "".join("0" for _ in range(len(now), 18)).encode('utf-8')
    
    random.seed(now)
    key = [random.randrange(256) for _ in message]
    
    return [m ^ k for (m,k) in zip(message + now, key + [0x42]*len(now))]


# I am generating many random numbers here to make my message secure
rand_nums = []
while len(rand_nums) != 8:
    tmp = int.from_bytes(os.urandom(1), "big")
    if tmp not in rand_nums:
        rand_nums.append(tmp)

for _ in range(42):
    # Answer to the Ultimate Question of Life, the Universe, and Everything...
    flag = encrypt_stage_one(flag, rand_nums)

# print(flag)

# Another layer of randomness based on time. Unbreakable.
res = encrypt_stage_two(flag.encode('utf-8'))

with open("flag.enc", "wb") as f:
    f.write(bytes(res))
f.close()

加密的密文是二进制，这里就不放出来了。

两个加密元件，一个是选择，一个是异或。第二个函数中，将rand的seed包含在了输出中，而且异或的密钥我们也知道了，所以可以反解出seed的值。从而得到key的序列，从而解密出第二个加密之前的数据。

第一个数据我们直接爆破即可。应为他选择的使用的实际只用8个元素也就是0~7，这个范围很小直接写一个逆过程然后爆破rand_nums的大小顺序即可，这里其实就是0~7的全排列遍历。

import itertools
import os
from Crypto.Util.number import *
from Crypto.Util.strxor import strxor
import time
import random

def reverse_shift(data, sequence):
    res = list("X"*len(data))
    index = 0
    for i in sequence:
        for j in range(i, len(data), len(sequence)):
            res[j] = data[index]
            index += 1
    return res

with open(r"flag.enc", "rb") as fp :
    data = fp.read()

print(time.time())
print(len(str(time.time())))

print(strxor(b"\x42"*18, data[-18:]))

seed = strxor(b"\x42"*18, data[-18:])

random.seed(seed)
key = [random.randrange(256) for _ in range(len(data) - 18)]

data = strxor(bytes(key), data[:len(key)])
print(list(data))

sequence = [i for i in range(8)]

for i in itertools.permutations(sequence,8):
    temp = data
    for _ in range(42):
        temp = reverse_shift(temp, i)
    temp = bytes(temp)
    if b"SEKAI" in temp:
        print(temp)
        
# ...
# b'SEKAI{T1m3_15_pr3C10u5_s0_Enj0y_ur_L1F5!!!}' 

# SEKAI{T1m3_15_pr3C10u5_s0_Enj0y_ur_L1F5!!!}

FaILProof

import hashlib
from os import urandom
from flag import FLAG


def gen_pubkey(secret: bytes, hasher=hashlib.sha512) -> list:
    def hash(m): return hasher(m).digest()
    state = hash(secret)
    pubkey = []
    for _ in range(len(hash(b'0')) * 4):
        pubkey.append(int.from_bytes(state, 'big'))
        state = hash(state)
    return pubkey


def happiness(x: int) -> int:
    return x - sum((x >> i) for i in range(1, x.bit_length()))


def encode_message(message: bytes, segment_len: int) -> list:
    message += bytes(segment_len - len(message) % (segment_len))
    encoded = []
    for i in range(0, len(message), segment_len):
        block = message[i:i + segment_len]
        encoded.append(int.from_bytes(block, 'big'))
    return encoded


def encrypt(pubkey: list, message: bytes) -> list:
    encrypted_blocks = []
    for block_int in encode_message(message, len(pubkey) // 4):
        encrypted_blocks.append([happiness(i & block_int) for i in pubkey])
    return encrypted_blocks


secret = urandom(16)
A = gen_pubkey(secret, hashlib.sha256)
enc = encrypt(A, FLAG)
print(secret.hex())
print(enc)
"""
d83ff3295e051dbbe9d49a3a701ab028
[[67, 70, 70, 71, 75, 76, 66, 68, 74, 73, 65, 61, 74, 72, 64, 73, 66, 71, 68, 72, 63, 76, 78, 72, 72, 70, 66, 69, 76, 75, 63, 76, 71, 78, 70, 66, 70, 69, 85, 68, 72, 62, 77, 78, 65, 67, 73, 69, 65, 71, 73, 72, 59, 73, 64, 68, 76, 74, 69, 75, 76, 61, 68, 68, 68, 62, 73, 71, 69, 74, 68, 66, 64, 81, 72, 59, 61, 73, 72, 63, 68, 49, 71, 79, 78, 57, 66, 71, 72, 68, 66, 68, 65, 72, 82, 83, 70, 63, 70, 62, 76, 69, 58, 68, 70, 76, 67, 76, 66, 70, 75, 64, 64, 67, 69, 63, 71, 68, 70, 69, 66, 73, 77, 67, 70, 66, 75, 81], [71, 71, 62, 69, 71, 76, 66, 52, 69, 72, 67, 59, 73, 70, 65, 66, 65, 65, 70, 75, 64, 77, 72, 74, 66, 70, 66, 71, 72, 73, 58, 67, 70, 72, 67, 67, 77, 74, 80, 64, 72, 61, 69, 73, 75, 59, 69, 68, 65, 72, 72, 65, 56, 67, 64, 73, 73, 73, 63, 71, 68, 60, 60, 71, 63, 62, 66, 65, 69, 68, 68, 67, 69, 75, 72, 60, 61, 74, 60, 63, 70, 66, 68, 79, 72, 59, 68, 69, 57, 71, 71, 67, 67, 70, 71, 81, 69, 63, 69, 57, 74, 61, 67, 78, 64, 71, 63, 71, 65, 69, 72, 66, 57, 72, 71, 60, 72, 68, 77, 70, 64, 64, 70, 69, 64, 64, 76, 79], [28, 29, 24, 30, 34, 34, 30, 24, 29, 27, 23, 33, 29, 28, 29, 37, 32, 20, 31, 35, 29, 29, 30, 38, 26, 36, 30, 27, 32, 28, 21, 28, 29, 34, 24, 31, 33, 34, 36, 25, 32, 29, 31, 27, 30, 28, 33, 31, 30, 29, 33, 26, 29, 31, 29, 34, 31, 26, 30, 31, 33, 35, 32, 26, 29, 26, 28, 32, 32, 31, 26, 29, 30, 34, 33, 23, 28, 31, 26, 25, 32, 30, 29, 27, 31, 26, 28, 29, 32, 31, 33, 25, 28, 38, 31, 33, 27, 29, 29, 23, 33, 26, 30, 38, 38, 27, 32, 31, 24, 25, 35, 33, 29, 25, 32, 24, 29, 26, 29, 24, 27, 31, 28, 28, 28, 24, 28, 36]]

184add015c820d022133c0094fafadc4
[[79, 64, 71, 67, 75, 72, 79, 72, 78, 64, 65, 67, 73, 68, 63, 59, 67, 64, 69, 64, 67, 70, 69, 64, 64, 67, 67, 71, 62, 70, 67, 66, 62, 72, 65, 68, 59, 62, 73, 67, 63, 68, 74, 71, 62, 69, 62, 64, 73, 70, 73, 71, 74, 71, 65, 74, 67, 54, 78, 72, 68, 75, 70, 71, 75, 64, 76, 71, 72, 75, 86, 73, 73, 77, 71, 68, 69, 63, 77, 62, 69, 64, 62, 73, 71, 76, 61, 74, 69, 74, 74, 62, 69, 64, 70, 64, 77, 78, 71, 79, 67, 73, 63, 72, 80, 66, 67, 76, 65, 72, 74, 55, 71, 75, 71, 73, 61, 62, 79, 65, 76, 72, 76, 68, 81, 86, 65, 71], [80, 59, 70, 72, 76, 64, 77, 75, 67, 66, 59, 71, 70, 69, 62, 71, 65, 65, 70, 72, 62, 66, 70, 69, 69, 63, 66, 66, 61, 61, 69, 68, 67, 66, 66, 62, 61, 61, 74, 73, 66, 65, 63, 75, 63, 64, 62, 64, 73, 68, 67, 73, 76, 69, 58, 73, 58, 57, 66, 66, 74, 78, 70, 71, 69, 60, 75, 61, 70, 72, 83, 72, 61, 80, 69, 68, 62, 71, 72, 64, 61, 72, 53, 67, 66, 75, 63, 65, 67, 62, 74, 68, 72, 70, 70, 59, 80, 76, 72, 75, 78, 72, 71, 65, 75, 63, 66, 81, 71, 70, 72, 58, 69, 77, 74, 64, 64, 67, 82, 61, 72, 73, 73, 62, 75, 81, 72, 67], [28, 27, 32, 31, 30, 32, 31, 24, 32, 32, 30, 23, 28, 30, 21, 30, 29, 28, 32, 31, 23, 33, 29, 28, 30, 31, 30, 29, 28, 23, 31, 30, 32, 28, 33, 31, 30, 25, 30, 30, 31, 29, 27, 35, 29, 28, 30, 32, 29, 35, 38, 29, 32, 34, 31, 37, 29, 31, 31, 29, 29, 32, 32, 33, 30, 29, 34, 26, 27, 29, 35, 27, 30, 34, 33, 26, 24, 36, 30, 31, 25, 30, 28, 31, 34, 30, 29, 30, 23, 30, 29, 32, 33, 27, 24, 29, 34, 33, 29, 32, 36, 32, 28, 33, 35, 28, 29, 34, 30, 33, 34, 27, 35, 32, 34, 34, 23, 31, 38, 25, 30, 32, 34, 31, 34, 38, 31, 30]]
"""

这里secret给了，所以PK就知道了，我们直接计算出来。给的enc输出是三组，代码中明文按32字节分块。所以明文至少有65字节。这个encoded其实就是pad我觉得。

encrypt中，实际上是输出的PK[i]与明文组异或后，输出的值中有多少二进制1。

def happiness(x: int) -> int:
    return x - sum((x >> i) for i in range(1, x.bit_length()))

这个函数就是干这个功能的。

这里其实就可以看成矩阵的乘法。

$XM = Y \\$

输出的结果就是Y，而M就是PK的二进制按照列排列组成的矩阵。所以直接解矩阵方程就行了。这里我们需要两组密文才能解，这样才能使得M为一个方阵。我们可以用两次连接来获取两组数据来组合。

但是SageMath解出来的结果明显不对。还是等等别人的wpkankan咋写吧。

别人用的是:

$MX = Y$

这个难道和我那个有区别吗…怎么这个就能解，我的解不了…又是一道临门一脚的题。

事后发现，我矩阵生成的代码写错了。😦

忘了考虑前导0的问题，没有做pad处理，导致构造矩阵的时候部分数据发生了错位…

from sage.all import *
import hashlib
from Crypto.Util.number import *
from libnum import *

def gen_pubkey(secret: bytes, hasher=hashlib.sha512) -> list:
    def hash(m): return hasher(m).digest()
    state = hash(secret)        
    pubkey = []
    for _ in range(len(hash(b'0')) * 4): # 256
        pubkey.append(int.from_bytes(state, 'big'))
        state = hash(state)
    return pubkey

PK1 = gen_pubkey(long_to_bytes(int("d83ff3295e051dbbe9d49a3a701ab028",16)), hashlib.sha256)
PK2 = gen_pubkey(long_to_bytes(int("184add015c820d022133c0094fafadc4",16)), hashlib.sha256)

PK = PK1 + PK2

M = Matrix(ZZ, len(PK), len(PK))

M_PK = []
for i in PK:
    temp = list(map(int, list(bin(i))[2:]))
    temp = [0]*(256 - len(temp)) + temp
    M_PK.append(temp)

M = Matrix(ZZ, M_PK)

Res1 =  ...
Res2 =  ...

flag = ""
for u,v in zip(Res1, Res2):
    Res = u + v
    R = vector(ZZ, Res)
    res = M.solve_right(R)
    for i in res:
        flag += str(i)

print(b2s(flag))

# b'SEKAI{w3ll_1_gu355_y0u_c4n_4lw4y5_4sk_f0r_m0r3_3qu4t10n5_wh3n_n0_0n3s_l00k1ng}\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'

# SEKAI{w3ll_1_gu355_y0u_c4n_4lw4y5_4sk_f0r_m0r3_3qu4t10n5_wh3n_n0_0n3s_l00k1ng}