杂记

包括d^3ctf，京麒杯的题目复现

[2025 d^3ctf] d3fnv

题目：

#!/usr/bin/env python3
from Crypto.Util.number import getPrime
from hashlib import sha256
from secret import FLAG
import socketserver
import signal
import random
import string
import os


BANNER = br"""
    ____ //|_____    __________________   ___   ____ ___   ______
   / __ \/||__  /   / ____/_  __/ ____/  |__ \ / __ \__ \ / ____/
  / / / /   /_ <   / /     / / / /_      __/ // / / /_/ //___ \  
 / /_/ /  ___/ /  / /___  / / / __/     / __// /_/ / __/____/ /  
/_____/  /____/   \____/ /_/ /_/       /____/\____/____/_____/   
"""


MENU = br"""
1. Get p
2. H4sh
3. Flag
4. Exit
"""


class FNV():
    def __init__(self):
        self.pbit = 1024
        self.p = getPrime(self.pbit)
        self.key = random.randint(0, self.p)
    
    def H4sh(self, value:str):
        length = len(value)
        x = (ord(value[0]) << 7) % self.p
        for c in value:
            x = ((self.key * x) % self.p) ^ ord(c)
        
        x ^= length
        
        return x


class Task(socketserver.BaseRequestHandler):
    def _recvall(self):
        BUFF_SIZE = 2048
        data = b''
        while True:
            part = self.request.recv(BUFF_SIZE)
            data += part
            if len(part) < BUFF_SIZE:
                break
        return data.strip()

    def send(self, msg, newline=True):
        try:
            if newline:
                msg += b'\n'
            self.request.sendall(msg)
        except:
            pass

    def recv(self, prompt=b'> '):
        self.send(prompt, newline=False)
        return self._recvall()

    def close(self):
        self.send(b"Bye~")
        self.request.close()

    def handle(self):
        signal.alarm(30)

        self.send(BANNER)
        
        n = 32
        cnt = 67
        str_table = string.ascii_letters + string.digits
        self.send(b'Welcome to D^3CTF 2025')
        self.send(b'Could you break my modified fnv hash function?')
        self.fnv = FNV()
        
        for _ in range(cnt):
            self.send(MENU)
            option = self.recv(b'option >')
            if option == b'G':
                p = self.fnv.p
                self.send(f'p = {p}'.encode())
            
            elif option == b'H':
                random_token = ''.join(random.choices(str_table, k=n))
                random_token_hash = self.fnv.H4sh(random_token)
                self.send(b'Token Hash: ' + str(random_token_hash).encode())
            
            elif option == b'F':
                random_token = ''.join(random.choices(str_table, k=n))
                self.send(b'Here is a random token x: ' + random_token.encode())
                ans = self.recv(b'Could you tell the value of H4sh(x)? ').strip().decode()
                if int(ans) % self.fnv.p == self.fnv.H4sh(random_token) % self.fnv.p:
                    self.send(b'Congratulations! Here is your flag: ')
                    self.send(FLAG)
                else:
                    self.send(b'Try again~')
            
            else:
                break
        
        self.close()


class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
    pass


class ForkedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass


if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 10007
    server = ForkedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    server.serve_forever()

在本地复现一下，所以修改一下代码

from Crypto.Util.number import getPrime
from hashlib import sha256
# from secret import FLAG
import socketserver
import signal
import random
import string
import os

class FNV():
    def __init__(self):
        self.pbit = 1024
        self.p = getPrime(self.pbit)
        self.key = random.randint(0, self.p)

    def H4sh(self, value: str):
        length = len(value)
        x = (ord(value[0]) << 7) % self.p
        for c in value:
            x = ((self.key * x) % self.p) ^ ord(c)

        x ^= length

        return x
n = 32
cnt = 67
str_table = string.ascii_letters + string.digits
fnv = FNV()
print(fnv.p)
print(fnv.key)
hashs = []
for _ in range(cnt):
    random_token = ''.join(random.choices(str_table, k=n))
    random_token_hash = fnv.H4sh(random_token)
    print(b'Token Hash: ' + str(random_token_hash).encode())
    hashs.append(random_token_hash)

print(hashs)
print('################################################################')
random_token = ''.join(random.choices(str_table, k=n))
print(b'Here is a random token x: ' + random_token.encode())

题目就是给了一个实现hash的函数
用下式表示：

$hash = 128 \cdot v_0 \cdot k^n + v_0 \cdot k^{n-1} + v_1 \cdot k^{n-2} + \cdots + v_{n-1} \mod p$

只知道p和65组不同字符串的hash值，求解key，并计算出题目要求字符串的hash值
可以写成模p下方程组：

$\begin{cases} 128v_{0}key^n+v_{0}key^{n-1}+...+v_{n-1}=hash_1 \\ 128v^{'}_{0}key^n+v^{'}_{0}key^{n-1}+...+v^{'}_{n-1}=hash_2 \\ 128v^{''}_{0}key^n+v^{''}_{0}key^{n-1}+...+v^{''}_{n-1}=hash_3 \\ \cdots\\ \end{cases}$

很明显就造格
可以把方程用矩阵表示，写成如下形式：

$K_{1 \times 33}V_{33 \times 65}=H_{1 \times 65} \quad(mod\;p)$

利用正交格的想法
先转置一下，得到：

$H^T_{65 \times 1} =V^T_{65 \times 33} K^T_{33 \times 1} \quad(mod\;p)$

找到M ,使下式成立

$MH^T = 0 \quad(mod\;p)$

使用下面这个格来求解M

$(m_1,m_2,...,m_{65},k) \left(\begin{matrix} I_{65 \times 65} & H^T_{65\times 1} \\ O & p \end{matrix}\right) = (m_1,m_2,...,m_{65},0)$

原式可写成：

$MV^TK^T = 0 \quad(mod\;p)$

再转置回来

$KV M^{T} = 0 \quad(mod\;p)$

只需要找到短向量v使得

$v M^{T} = 0 \quad(mod\;p)$

所以使用上面的格就可以了，实际用的时候配一个大系数就行了