pyd 逆向

what’s pyd

.pyd 文件本质上是一个 Windows 的 DLL 文件, 通过 C/C++ 编译器（如 MSVC）把 C/C++ 代码编译成二进制形式，实现了 Python 扩展模块的接口，可以通过 import xxx 的方式像普通的 .py 文件那样导入使用

preparation

先在 windows 下自己编译一个带有调试信息的 pyd 文件，主要用于后续 bindiff 比较恢复符号

注意编译时 python 的版本尽量与要逆向的文件一致(可以在 ida string 里面搜 dll 看到类似”python312.dll”的字符串确定题目使用的 python 版本)

准备 test_for_pyd.py 文件 和 setup.py 文件

#test_for_pyd.py
def demo_greet(msg: str) -> None:
    base = 3
    total = base + 5
    extra = 7
    print(msg)
    print(base, total, extra)


def hex_to_decimal(hex_str: str) -> int:
    digits = "0123456789abcdef"
    value = 0
    for ch in reversed(hex_str.lower()):
        value = value * 16 + digits.index(ch)
    return value


if __name__ == "__main__":
    demo_greet("Hello, Python!")
    print(hex_to_decimal("123"))

# setup.py
from setuptools import setup, Extension
from Cython.Build import cythonize
import os
import distutils.util

# 设置使用 MinGW 编译器
os.environ['DISTUTILS_USE_SDK'] = '1'
# 防止链接器剥离调试信息
os.environ['LDFLAGS'] = '-g'

# 修复 MinGW 链接问题
import distutils.cygwinccompiler
distutils.cygwinccompiler.get_msvcr = lambda: []

extensions = [
    Extension(
        "test_for_pyd",
        ["test_for_pyd.py"],
        # define_macros=[("MS_WIN64", None)],  # 移除重复定义，Python.h 已经定义了
        extra_compile_args=["-g", "-O0", "-ggdb3"],  # 添加更详细的调试信息
        extra_link_args=["-g"]  # 链接器生成调试信息
    
    )
]

setup(
    name='test_for_pyd',
    ext_modules=cythonize(extensions)
)

使用以下命令编译生成 pyd 文件：

python setup.py build_ext --inplace
# 或者 python setup.py build_ext --inplace --compiler=mingw32

但是这个 pyd 扔进 ida 之后没有看到 pyx 相关的符号 :sob:

在 linux 下编译了一个类似的 so 文件

创建一个虚拟环境 python3 -m venv myenv

激活虚拟环境 source myenv/bin/activate

在虚拟环境中安装 cython 和 setuptools：

sudo apt install cython3

python setup.py build_ext --inplace

Linux 下的 setup.py ：

# setup.py
from setuptools import setup, Extension
from Cython.Build import cythonize
import os

# 启用详细编译输出
os.environ['CFLAGS'] = '-g -O0'  # -g 添加调试信息，-O0 禁用优化
os.environ['LDFLAGS'] = '-g'     # 链接时包含调试信息

extensions = [
    Extension(
        "test_for_pyd",  # 模块名（与导入名一致）
        ["test_for_pyd.py"],  # 源文件
        # 显式添加编译参数（覆盖环境变量）
        extra_compile_args=["-g", "-O0", "-fPIC"],
        extra_link_args=["-g"]
    )
]

setup(
    name="test_for_pyd",
    version="1.0",
    ext_modules=cythonize(
        extensions,
        # 关键调试设置
        compiler_directives={
            'language_level': "3",  # Python 3
            'linetrace': True,      # 替代 c_line_trace - 启用行跟踪
            'binding': True         # 改善函数签名
        },
        gdb_debug=True,            # 启用GDB调试支持
        annotate=True               # 生成HTML注解文件
    )
)

使用以下命令编译生成 so 文件：

python setup.py build_ext --inplace --force

test_for_pyd.cpython-312-x86_64-linux-gnu.so

除此之外同时还生成了 test_for_pyd.c 和 test_for_pyd.html

把这个 so 扔进 ida 里面，发现与之前的那个 pyd 文件相比多了不少符号信息

在 ida 的 File->Produce File->Create C Header File 导出结构体

用 ida 打开要逆向的 pyd 文件，在 File->Load File->Parse C Header File 中导入从 so 文件中导出的 .h 文件(如果遇到报错就修复一下)

CTF pyd 逆向分析

ciscn 2024 rand0m

做法一：静态分析

先看看 string，注意到里面有好几个可疑的字符串和数字，x 交叉引用，找到数字所在函数(sub_xxx2BD0)，里面通过 PyLong_FromLong() 和 PyLong_FromString() 创造了一系列整数对象，将这些对象存储到一个全局指针数组 off_7FF90BEAB688[29] ~ [49]，用于后续查表

rand0m.rand0m:在 sub_xxx12B0 里面，找到关键加密部分

提取出关键部分:

v14 = v12 ^ 2654435769
v6 = v14
v15 = v12 >> 5
v3 = v15
v21 = v12 << 4
v12 = v21
v22 = v12 & 4198170623
v23 = v5
v5 = v22   v5 = v12 & 4198170623
v24 = v3 >> 23   v24 = (v12 >> 5) >> 23 v24 = v12 >> 28
v25 = v22 + v24 v25 = (v12 & 4198170623) + v12 >> 28   v25 = (v12 << 4) & 0xFA3AFFFF + (v12 >> 28)
v27 = v6 >> 11 v27 = v12 ^ 0x9E3779B9 >> 11
v30 = pow(v27, 65537)  v30 = pow((v12 ^ 0x9E3779B9) >> 11, 65537)
v31 = v30 % 4294967293  v31 = pow((v12 ^ 0x9E3779B9) >> 11, 65537, 0xFFFFFFFD)
v5 = v31

整理之后就是

def rand0m(v12):
    v25=((v12<<4)&0xFA3AFFFF)+(v12>>28)
    v31=pow((v12^0x9E3779B9)>>11,65537,0xFFFFFFFD)
    return (v31, v25)

接着看 check 函数，注意到其上方有一个 sub_xxx1960

点进去之后发现它创建了一个 python 列表，存入了八个数据

继续往下看到比较函数

PyObject* PyObject_RichCompare(PyObject *v, PyObject *w, int op)

v,w 分别代表的是比较的两个对象，op 是比较操作的枚举值

具体如下：

#define Py_LT 0  // <
#define Py_LE 1  // <=
#define Py_EQ 2  // ==
#define Py_NE 3  // !=
#define Py_GT 4  // >
#define Py_GE 5  // >=

用 z3 爆破求解

import z3


def rand0m(input: int):
    v0 = ((input << 4) & 0xFA3AFFFF) + (input >> 28)
    v1 = pow((input ^ 0x9E3779B9) >> 11, 65537, 0xFFFFFFFD)
    return (v0, v1)


def main():
    data = [
        304643896,
        2563918650,
        1244723021,
        3773946743,
        37360232,
        2918417411,
        2282784775,
        3628702646,
    ]
    for i in range(0, len(data), 2):
        ans = z3.Solver()
        x = z3.BitVec("x", 32)
        v0 = ((x << 4) & 0xFA3AFFFF) + (x >> 28)
        ans.add(z3.And(data[i] - 16 <= v0, v0 <= data[i] + 16))  # 增大可行解范围
        while ans.check() == z3.sat:
            result = ans.model()
            if result[x] != None:
                val = result[x].as_long()
                ret = rand0m(val)
                if ret[0] == data[i] and ret[1] == data[i + 1]:
                    print(hex(val))
                    break
                ans.add(x != val)


main()

# output:
# 0x813a97f3
# 0xd4b34f74
# 0x802ba126
# 0x78950880

flag 为:flag{813a97f3d4b34f74802ba12678950880}

做法二：动调+frida

基本思路

用 frida hook（或者 ida 打条件断点）pyd 中的运算和比较相关的函数名来 trace，根据 trace 的结果再结合动调梳理出加密逻辑

由于 pyd 文件不能直接动调，这里采用 attch python 进程的方式

可以在附件给的 challenge.py 中加上 import sys ，print(sys.executable)和import os,print(os.getpid())，以便查看运行该文件的 Python 解释器路径和 pid，然后运行 .py 文件之后去 ida，选择 Local Windows debugger 作调试器，在 Debugger -> Attach to Process 中选择对应的 python 进程(| 刚刚解释器的路径下的 python.exe)进行调试

frida 的话可以运行 .py 文件后执行命令 frida-ps | findstr python 找到 pid

先运行 题目给的 challenge.py 文件,得到 pid

然后运行 hook 脚本

# hook_python.py
import frida
import sys
import time

with open("rand0m.js", encoding="utf-8") as f:
    jscode = f.read()

def on_message(message, data):
    print("[*]", message)

def main():
    try:
        device = frida.get_local_device()
    
        # target = input("Enter PID or process name: ").strip()
        target = 35164
        
        try:
            pid = int(target)
            session = device.attach(pid)
        except ValueError:
            session = device.attach(target)
        
        print(f"[*] Attached to {target}")
        
        script = session.create_script(jscode)
        script.on('message', on_message)
        script.load()
        
        print("[*] Script loaded. Monitoring Python operations...")
        print("[*] Press Ctrl+C to stop and analyze.\n")
        
        
        try:
            while True:
                time.sleep(1)
        except KeyboardInterrupt:
            print("\n[*] Stopping trace and analyzing...")
            script.exports.stop()
            time.sleep(2)  
        
    except KeyboardInterrupt:
        print("\n[*] Exiting...")
    except Exception as e:
        print(f"[-] Error: {e}")

if __name__ == "__main__":
    main()

frida hook 脚本 rand0m.js

console.log("[*] Python Crypto Trace Script Started");

var hook_list = [
    "PyNumber_Add", "PyNumber_And", "PyNumber_Rshift", "PyNumber_Lshift",
    "PyNumber_Xor", "PyNumber_InPlaceRshift", "PyNumber_InPlaceAdd",
    "PyNumber_Multiply", "PyNumber_Power", "PyNumber_Index",
    "PyObject_RichCompare", "PyNumber_Remainder"
];

var callSequence = 0;
var traceData = [];
var isTracing = true;

function findExportByName(moduleName, exportName) {
    if (typeof Module.findExportByName === 'function') {
        return Module.findExportByName(moduleName, exportName);
    } else if (typeof Module.getExportByName === 'function') {
        return Module.getExportByName(moduleName, exportName);
    } else if (typeof Module.getGlobalExportByName === 'function') {
        if (moduleName === null) {
            return Module.getGlobalExportByName(exportName);
        } else {
            const module = Process.findModuleByName(moduleName);
            if (module) {
                const exports = module.enumerateExports();
                for (let i = 0; i < exports.length; i++) {
                    if (exports[i].name === exportName) {
                        return exports[i].address;
                    }
                }
            }
        }
    }
    return null;
}

function parsePyLong(addr) {
    try {
        if (!addr || addr.isNull()) {
            return 0;
        }
        
        const ob_size = addr.add(0x10).readS64();
        if (ob_size === 0) return 0;
        
        const isNegative = ob_size < 0;
        const numdigits = Math.abs(Number(ob_size));
        
        if (numdigits > 0x1000) {
            const digit = addr.add(0x18).readU32();
            return isNegative ? -digit : digit;
        }
        
        if (numdigits > 2) {
            let bigVal = 0n;
            for (let i = 0; i < numdigits; i++) {
                const digit = addr.add(0x18 + 4 * i).readU32();
                bigVal += BigInt(digit) * (1n << (30n * BigInt(i)));
            }
            return isNegative ? -bigVal : bigVal;
        }
        
        let val = 0;
        for (let i = 0; i < numdigits; i++) {
            val += addr.add(0x18 + 4 * i).readU32() * Math.pow(2, 30 * i);
        }
        return isNegative ? -val : val;
        
    } catch (e) {
        return 0;
    }
}

function formatHex(val, minWidth = 8) {
    if (typeof val === 'bigint') {
        return val.toString(16).toUpperCase().padStart(minWidth, '0');
    }
    return val.toString(16).toUpperCase().padStart(minWidth, '0');
}


function getOperationType(op) {
    if (op.includes('Add') || op.includes('Subtract') || op.includes('Multiply')) {
        return 'ARITHMETIC';
    } else if (op.includes('And') || op.includes('Or') || op.includes('Xor')) {
        return 'BITWISE';
    } else if (op.includes('Rshift') || op.includes('Lshift')) {
        return 'SHIFT';
    } else if (op.includes('Power')) {
        return 'POWER';
    } else if (op.includes('RichCompare')) {
        return 'COMPARE';
    } else {
        return 'OTHER';
    }
}

function logOperation(seq, op, arg1, arg2, result) {
    const type = getOperationType(op);
    const arg1Hex = formatHex(arg1, 16);
    const arg2Hex = formatHex(arg2, 16);
    const resultHex = formatHex(result, 16);
    
    console.log(`\n[${seq.toString().padStart(4, '0')}] ${type.padEnd(10)} | ${op.padEnd(20)}`);
    console.log(`       INPUT:  0x${arg1Hex}`);
    console.log(`       PARAM:  0x${arg2Hex}`);
    console.log(`       OUTPUT: 0x${resultHex}`);
    

    traceData.push({
        sequence: seq,
        type: type,
        operation: op,
        arg1: arg1,
        arg2: arg2,
        result: result,
        timestamp: Date.now()
    });
}

function analyzeEncryptionFlow() {
    console.log("\n" + "=".repeat(50));
    console.log("           TRACE COMPLETED");
    console.log("=".repeat(50));
    
    
    const shiftOps = traceData.filter(op => op.type === 'SHIFT');
    
    if (shiftOps.length > 0) {
        console.log("\nSHIFT OPERATIONS:");
        shiftOps.forEach(op => {
            const direction = op.operation.includes('Lshift') ? 'LEFT' : 'RIGHT';
            console.log(`   [${op.sequence}] ${direction.padEnd(5)} shift by ${op.arg2} bits: 0x${formatHex(op.arg1)} -> 0x${formatHex(op.result)}`);
        });
    }
    
    console.log("=".repeat(50));
}

// 主 Hook 逻辑
function installHooks() {
    console.log("[*] Installing Python operation hooks...");
    
    const pythonModule = Process.findModuleByName('python312.dll');
    if (!pythonModule) {
        console.error('Python312.dll module not found');
        return;
    }
    
    console.log(`[*] Found Python module: ${pythonModule.name} at ${pythonModule.base}`);
    console.log(`[*] Starting trace...\n`);
    
    let successCount = 0;
    
    for (let i = 0; i < hook_list.length; i++) {
        const op = hook_list[i];
        
        try {
            const funcAddress = findExportByName('python312.dll', op);
            
            if (!funcAddress || funcAddress.isNull()) {
                console.warn(`[WARN] Function not found: ${op}`);
                continue;
            }
            
            Interceptor.attach(funcAddress, {
                onEnter: function(args) {
                    if (!isTracing) return;
                    
                    this.op = op;
                    this.sequence = ++callSequence;
                    this.timestamp = Date.now();
                    
                    try {
                        this.arg1 = parsePyLong(args[0]);
                        this.arg2 = parsePyLong(args[1]);
                    } catch (e) {
                        this.arg1 = 0;
                        this.arg2 = 0;
                    }
                },
                
                onLeave: function(retval) {
                    if (!isTracing) return;
                    
                    try {
                        const result = parsePyLong(retval);
                        logOperation(this.sequence, this.op, this.arg1, this.arg2, result);
                    } catch (e) {
                        console.log(`[${this.sequence}] ${this.op} completed with error: ${e.message}`);
                    }
                }
            });
            
            successCount++;
            
        } catch (e) {
            console.error(`Failed to hook ${op}: ${e.message}`);
        }
    }
    
    console.log(`[*] Successfully hooked ${successCount}/${hook_list.length} functions\n`);
}


rpc.exports = {
    stop: function() {
        isTracing = false;
        console.log("\n[*] Tracing stopped. Analyzing...");
        analyzeEncryptionFlow();
    }
};

SetTimeout(() => {
    installHooks();
}, 1000);

运行后在 ida 中附加进程开始动调，input 的内容稍微可以长一点 ##### trace 结果

[*] Attached to 35164
[*] Python Crypto Trace Script Started
[*] Script loaded. Monitoring Python operations...
[*] Press Ctrl+C to stop and analyze.

[*] Installing Python operation hooks...
[*] Found Python module: python312.dll at 0x7ff8ab110000
[*] Starting trace...

[*] Successfully hooked 12/12 functions


[0001] BITWISE    | PyNumber_Xor
       INPUT:  0x100001FFEAB611810000000000000001000000011111111
       PARAM:  0x100001FFEAB6118100000000000000020000220E808A7A00000000000000100001FFEAB61181000000000000000100000009E3779B9
       OUTPUT: 0x80001FFEAB6118100000000000000010000220E7B902A00000000000000100001FFEAB61181000000000000000100000008F2668A8

[0002] BITWISE    | PyNumber_And
       INPUT:  0x100001FFEAB6118100000088E81846B00000000459042280000000000000080001FFEAB6118100000088E8184670000000111111110
       PARAM:  0x100001FFEAB611810000000000000001000000098D24B3A0000000000000100001FFEAB6118100000000000000020000000FA3AFFFF
       OUTPUT: 0x100001FFEAB6118100000088E81846B0000000010101110

[0003] ARITHMETIC | PyNumber_Add
       INPUT:  0x100001FFEAB6118100000088E81846B0000000010101110
       PARAM:  0x80001FFEAB6118100000000FFFFFFFF000000000000001
       OUTPUT: 0x100001FFEAB611810000000000000001000000010101111

[0004] POWER      | PyNumber_Power
       INPUT:  0x100001FFEAB6118100000000000000010000220C011E4CD
       PARAM:  0x80001FFEAB611810000000000000002000000040010001
       OUTPUT: 0x0000000016C5E4CD

[0005] OTHER      | PyNumber_Remainder
       INPUT:  0x0000000016C5E4CD
       PARAM:  0x80001FFEAB6118100000000000000010000001111111100000000000000100001FFEAB6118100000088E81846700000000FFFFFFFD
       OUTPUT: 0x80001FFEAB6118100000000000000010000220E7B902A00000000000000100001FFEAB6118100000000000000010000000F9704BDF

[0006] COMPARE    | PyObject_RichCompare
       INPUT:  0x100001FFEAB611810000000000000001000000010101111
       PARAM:  0x80001FFEAB611810000000000000002000000052287F38
       OUTPUT: 0x0000000000000000

[0007] BITWISE    | PyNumber_Xor
       INPUT:  0x100001FFEAB611810000000000000001000000022222222
       PARAM:  0x100001FFEAB6118100000000000000020000220E808A7A00000000000000100001FFEAB61181000000000000000100000009E3779B9
       OUTPUT: 0x10768767A969790B0000000000000000000000000000000000000687675A50000000000000100001FFEAB6118100000088E81846B00000000BC155B9B

[0008] BITWISE    | PyNumber_And
       INPUT:  0x10768767A969790B000000000000000000000000000000000000222222220
       PARAM:  0x100001FFEAB611810000000000000001000000098D24B3A0000000000000100001FFEAB6118100000000000000020000000FA3AFFFF
       OUTPUT: 0x0000000022222220

[0009] ARITHMETIC | PyNumber_Add
       INPUT:  0x0000000022222220
       PARAM:  0x80001FFEAB6118100000000FFFFFFFF000000000000002
       OUTPUT: 0x100001FFEAB611810000000000000001000000022222222

[0010] POWER      | PyNumber_Power
       INPUT:  0x100001FFEAB6118100000088E81846700000001001782AB
       PARAM:  0x80001FFEAB611810000000000000002000000040010001
       OUTPUT: 0x00000000151B82AB

[0011] OTHER      | PyNumber_Remainder
       INPUT:  0x00000000151B82AB
       PARAM:  0x100001FFEAB6118100000088E81846700000001001782AB0000000000000080001FFEAB6118100000000000000010000000FFFFFFFD
       OUTPUT: 0x100001FFEAB6118100000088E81846D00000000113A5AEB

[0012] COMPARE    | PyObject_RichCompare
       INPUT:  0x100001FFEAB611810000000000000001000000022222222
       PARAM:  0x100001FFEAB6118100000000000000010000220E807DCB00000000000000100001FFEAB61181000000000000000100000004A30F74D
       OUTPUT: 0x0000000000000000

[0013] BITWISE    | PyNumber_Xor
       INPUT:  0x100001FFEAB611810000000000000001000000033333333
       PARAM:  0x100001FFEAB6118100000000000000020000220E808A7A00000000000000100001FFEAB61181000000000000000100000009E3779B9
       OUTPUT: 0x80001FFEAB6118100000000000000010000220E8080B300000000000000100001FFEAB6118100000000000000010000000AD044A8A

[0014] BITWISE    | PyNumber_And
       INPUT:  0x0000000333333330
       PARAM:  0x100001FFEAB611810000000000000001000000098D24B3A0000000000000100001FFEAB6118100000000000000020000000FA3AFFFF
       OUTPUT: 0x10768767A969790B000000000000000000000000000000000000032323330

[0015] ARITHMETIC | PyNumber_Add
       INPUT:  0x10768767A969790B000000000000000000000000000000000000032323330
       PARAM:  0x80001FFEAB6118100000000FFFFFFFF000000000000003
       OUTPUT: 0x100001FFEAB611810000000000000001000000032323333

[0016] POWER      | PyNumber_Power
       INPUT:  0x80001FFEAB61181000000000000000100000010015A089
       PARAM:  0x80001FFEAB611810000000000000002000000040010001
       OUTPUT: 0x0000000015BDA089

[0017] OTHER      | PyNumber_Remainder
       INPUT:  0x0000000015BDA089
       PARAM:  0x80001FFEAB61181000000000000000100000010015A0890000000000000080001FFEAB6118100000000000000010000000FFFFFFFD
       OUTPUT: 0x80001FFEAB6118100000000000000010000220E8080B300000000000000100001FFEAB6118100000000000000010000000592EC804

[0018] COMPARE    | PyObject_RichCompare
       INPUT:  0x100001FFEAB611810000000000000001000000032323333
       PARAM:  0x100001FFEAB6118100000000000000010000000423A1268
       OUTPUT: 0x0000000000000000

[0019] BITWISE    | PyNumber_Xor
       INPUT:  0x100001FFEAB6118100000000000000010000220E80684E00000000000000100001FFEAB611810000000000000001000000044444444
       PARAM:  0x100001FFEAB6118100000000000000020000220E808A7A00000000000000100001FFEAB61181000000000000000100000009E3779B9
       OUTPUT: 0x10768767A969790B0000000000000000000000000000000000000323233300000000000000080001FFEAB6118100000088E81846B00000000DA733DFD

[0020] BITWISE    | PyNumber_And
       INPUT:  0x100001FFEAB6118100000088E81846D00000000000000010768767A969790B000000000000000000000000000000000000444444440
       PARAM:  0x100001FFEAB611810000000000000001000000098D24B3A0000000000000100001FFEAB6118100000000000000020000000FA3AFFFF
       OUTPUT: 0x0000000040004440

[0021] ARITHMETIC | PyNumber_Add
       INPUT:  0x0000000040004440
       PARAM:  0x80001FFEAB6118100000000FFFFFFFF000000000000004
       OUTPUT: 0x3569453C2D9A35111CBA10000000000000180001FFEAB6118100000088E816B5700000B24C1F4C8F8C13326F00000000000000040004444

[0022] POWER      | PyNumber_Power

[0023] OTHER      | PyNumber_Remainder
       INPUT:  0x0000000036634E67
18100000088E81846700000000FFFFFFFD
       OUTPUT: 0x10768767A969790B0000000000000000000000000000000000004444444400000000000000100001FFEAB6118100018100000088E81846700000000FFFFFFFD
       OUTPUT: 0x10768767A969790B0000000000000000000000000000000000004444444400000000000000100001FFEAB6118100000088E81846D000000007ACF1933


[0024] COMPARE    | PyObject_RichCompare
[0024] COMPARE    | PyObject_RichCompare
       INPUT:  0x87BBEC3CD29C7BC326BE100000000000001800       INPUT:  0x87BBEC3CD29C7BC326BE10000000000000180001FFEAB6118100000088E816B5A00000B24C1F4C8F8C13326F0000001FFEAB6118100000088E816B5A00000B24C1F4C8F8C13326F00000000000000040004444
       PARAM:  0x80001FFEAB6118100000000000000020000000400100010000000000000080001FFEAB611810000000000000001000000088108807
       OUTPUT: 0x0000000000000000

从 trace 中可以发现一些关键数据，并且观察出输入长度应该是 32，分成了四组，这里的 trace 结果并没有看到左移和右移的操作，可以动调分析去找找

爆破脚本

from itertools import product

# 掩码参数和加密常量
MASK = 0xFA3AFFFF
BIT_INDICES = [26, 24, 23, 22, 18, 16]
# 0xFA3AFFFF = 11111010001110101111111111111111
CONST_XOR = 0x9e3779b9
MOD = 0xfffffffd
EXP = 0x10001

# 已知加密后的结果
CIPHERS1 = [0x12287F38, 0x4a30f74d, 0x23a1268, 0x88108807]
CIPHERS2 = [0x98d24b3a, 0xe0f1db77, 0xadf38403, 0xd8499bb6]


def set_bits(val, bits):
   # 恢复被掩掉的 6 个比特位
    for idx, sel in zip(BIT_INDICES, bits):
        val = val | (1 << idx) if sel else val & ~(1 << idx)
    return val

    # if sel == 1:
    #     val = val | (1 << idx)  # 把第 idx 位设为 1
    # else:
    #     val = val & ~(1 << idx)  # 把第 idx 位清为 0
    # return val


# x = (part >> 28)          # 取最高4位
# y = (part << 4) & MASK    # 低28位左移4位并掩码
# y += x                    # 把最高4位加入

def decrypt_block(cipher1, cipher2):
    
    x = cipher1 & 0xF # 取最低4位
    y = cipher1 - x

    for bits in product([0, 1], repeat=len(BIT_INDICES)):
        y_restored = set_bits(y, bits)
        part = ((x << 28) | (y_restored >> 4)) & 0xFFFFFFFF

        p1 = (part ^ CONST_XOR) >> 11
        res = pow(p1, EXP, MOD)

        if res == cipher2:
            return part
    return None


def main():
    recovered = [decrypt_block(c1, c2) for c1, c2 in zip(CIPHERS1, CIPHERS2)]
    flag_hex = ''.join(f"{p:08x}" for p in recovered)
    print(flag_hex)


if __name__ == "__main__":
    main()

# output:813a97f3d4b34f74802ba12678950880