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