今年败在了第九题，头发都掉光了，也没能理清check函数的逻辑，去年也是败在第九题，真的有毒。还是太菜了，心痛啊，我近在咫尺的奖牌啊啊啊啊。本文分享一下其他题的思路。
5.ntfsm
首先需要了解：替代数据流 (Alternate Data Streams, ADS) 是 NTFS (New Technology File System) 文件系统的一项独特功能。我一开始不知道这个东西，然后调试时尝试改变参数，没作用，这个程序还老是注销电脑。。后来我怀疑他可能将参数保存在文件，或注册表，使用pexplorer监视才知道这个，然后问了下AI,这个确实适合干坏事。
使用PowerShell访问 ADS
Get-Item -Path .\ntfsm.exe -Stream *
Get-Content -Path .\ntfsm.exe -Stream input -Raw
Get-Content -Path .\ntfsm.exe -Stream input -Encoding Byte -ReadCount 0 #二进制内容
Get-Content .\ntfsm.exe -Stream state
Get-Content .\ntfsm.exe -Stream position
Get-Content .\ntfsm.exe -Stream transitions
删除流
Remove-Item -Path .\ntfsm.exe -Stream *
后面调试发现：
usage: ./ntfsm <password>\nto reset the binary in case of weird behavior: ./ntfsm -r"
通过动态调试，主要靠x64dbg动态调试，修改进程flag使子进程挂起调试，和一点静态分析，弄清了整个程序逻辑，程序通过state和参数字符，来决定走向不同的分支，如果分支走对了，最后通过比较position，transitions是否都与16相同，一样的话打印correct。动态调试的时候发现分支走向是一棵树，但没有弄清state对结果的影响，然后我想着看看这颗树多大，每次都往最大的分支走，结果发现只比对了15个字符，而且transitions也是15，说明什么，说明最后一个字符是独苗。。直接搜索立即数1629C，然后往前推。
.text:000000014018C9E0 loc_14018C9E0: ; CODE XREF: sub_14000C0B0+9AA↑j
.text:000000014018C9E0 rdtsc ; jumptable 000000014000CA5A case 57775
.text:000000014018C9E2 shl rdx, 20h
.text:000000014018C9E6 or rax, rdx
.text:000000014018C9E9 mov [rsp+59398h+var_680], rax
.text:000000014018C9F1
.text:000000014018C9F1 loc_14018C9F1: ; CODE XREF: sub_14000C0B0+18096E↓j
.text:000000014018C9F1 rdtsc
.text:000000014018C9F3 shl rdx, 20h
.text:000000014018C9F7 or rax, rdx
.text:000000014018C9FA mov [rsp+59398h+var_678], rax
.text:000000014018CA02 mov rax, [rsp+59398h+var_680]
.text:000000014018CA0A mov rcx, [rsp+59398h+var_678]
.text:000000014018CA12 sub rcx, rax
.text:000000014018CA15 mov rax, rcx
.text:000000014018CA18 cmp rax, 12AD1659h
.text:000000014018CA1E jl short loc_14018C9F1
.text:000000014018CA20 movzx eax, [rsp+59398h+var_59368]
.text:000000014018CA25 mov [rsp+59398h+var_4E808], al
.text:000000014018CA2C cmp [rsp+59398h+var_4E808], 51h ; 'Q'
.text:000000014018CA34 jz short loc_14018CA38
.text:000000014018CA36 jmp short loc_14018CA57
.text:000000014018CA38 ; ---------------------------------------------------------------------------
.text:000000014018CA38
.text:000000014018CA38 loc_14018CA38: ; CODE XREF: sub_14000C0B0+180984↑j
.text:000000014018CA38 mov [rsp+59398h+var_668], 1629Ch
.text:000000014018CA44 mov rax, [rsp+59398h+var_8E0]
# 在 IDA 中运行
import ida_bytes, idaapi, idc
jpt_base = 0x140C687B8 # 跳表起始
image_base = idaapi.get_imagebase() # 一般是 0x140000000，但用 API 更稳妥
target = loc_14018C9E0 # 你给的 loc 地址
entry = target - image_base
max_entries = 0x1629C # 或设置更大/更小，按你 cmp 的上限
matches = []
for i in range(0, max_entries+1):
ea = jpt_base + i*4
try:
v = ida_bytes.get_dword(ea)
except:
continue
if (v & 0xFFFFFFFF) == (entry & 0xFFFFFFFF):
matches.append((i, ea, v))
if not matches:
print("没有找到匹配项（请确认 jpt_base 和 max_entries 是否正确）")
else:
for idx, ea, v in matches:
print("index=0x{0:X} ({0}), entry_addr=0x{1:X}, entry=0x{2:X}".format(idx, ea, v))
.\ntfsm.exe iqg0nSeCHnOMPm2Q
correct!
Your reward: f1n1t3_st4t3_m4ch1n3s_4r3_fun@flare-on.com
[hr]
6.Chain of Demands
这个题，我学会了EVM字节码反编译分析。。通过反编译LCGracle的字节码，发现当counter=0时，state = initial_seed，然后就恢复了整个LCG的参数，可以解密LCG-XOR消息，最后发现这对我解密RSA消息好像没有很大作用。。。可能哪里没搞明白或者搞错了。这个题目考察的是RSA N的多因子分解问题，initial_seed是他其中的一个因子，去factordb查了一下，得到其他7个因子。。。
"""
使用已知的 8 个质数解密 RSA 消息
"""
from Crypto.Util.number import inverse, long_to_bytes
from math import gcd
# 8 个质数
primes = [
72967016216206426977511399018380411256993151454761051136963936354667101207529,
62826068095404038148338678434404643116583820572865189787368764098892510936793,
68446593057460676025047989394445774862028837156496043637575024036696645401289,
69802783227378026511719332106789335301376047817734407431543841272855455052067,
75395288067150543091997907493708187002382230701390674177789205231462589994993,
79611551309049018061300429096903741339200167241148430095608259960783012192237,
82836473202091099900869551647600727408082364801577205107017971703263472445197,
88790251731800173019114073860734130032527125661685690883849562991870715928701,
]
# RSA 密文
ciphertexts = [
"680a65364a498aa87cf17c934ab308b2aee0014aee5b0b7d289b5108677c7ad1eb3bcfbcad7582f87cb3f242391bea7e70e8c01f3ad53ac69488713daea76bb3a524bd2a4bbbc2cfb487477e9d91783f103bd6729b15a4ae99cb93f0db22a467ce12f8d56acaef5d1652c54f495db7bc88aa423bc1c2b60a6ecaede2f4273f6dce265f6c664ec583d7bd75d2fb849d77fa11d05de891b5a706eb103b7dbdb4e5a4a2e72445b61b83fd931cae34e5eaab931037db72ba14e41a70de94472e949ca3cf2135c2ccef0e9b6fa7dd3aaf29a946d165f6ca452466168c32c43c91f159928efb3624e56430b14a0728c52f2668ab26f837120d7af36baf48192ceb3002",
"6f70034472ce115fc82a08560bd22f0e7f373e6ef27bca6e4c8f67fedf4031be23bf50311b4720fe74836b352b34c42db46341cac60298f2fa768f775a9c3da0c6705e0ce11d19b3cbdcf51309c22744e96a19576a8de0e1195f2dab21a3f1b0ef5086afcffa2e086e7738e5032cb5503df39e4bf4bdf620af7aa0f752dac942be50e7fec9a82b63f5c8faf07306e2a2e605bb93df09951c8ad46e5a2572e333484cae16be41929523c83c0d4ca317ef72ea9cde1d5630ebf6c244803d2dc1da0a1eefaafa82339bf0e6cf4bf41b1a2a90f7b2e25313a021eafa6234643acb9d5c9c22674d7bc793f1822743b48227a814a7a6604694296f33c2c59e743f4106",
]
print("=" * 80)
print("🔓 FlareOn 12 - 最终解密")
print("=" * 80)
print("\n步骤 1: 验证质数")
print("-" * 80)
from Crypto.Util.number import isPrime
all_prime = True
for i, p in enumerate(primes):
is_p = isPrime(p)
status = "✓" if is_p else "✗"
print(f" 质数 #{i+1}: {status} ({p.bit_length()} bits)")
if not is_p:
all_prime = False
if not all_prime:
print("\n⚠️ 警告: 不是所有数字都是质数!")
print("\n步骤 2: 构建 RSA 密钥")
print("-" * 80)
# 计算 n = p1 * p2 * ... * p8
print("\n计算 n = p1 × p2 × ... × p8 ...")
n = 1
for p in primes:
n *= p
print(f" n = {str(n)[:60]}...")
print(f" n 的位数: {n.bit_length()} bits")
# 计算 phi(n) = (p1-1) * (p2-1) * ... * (p8-1)
print("\n计算 φ(n) = (p1-1) × (p2-1) × ... × (p8-1) ...")
phi = 1
for p in primes:
phi *= (p - 1)
print(f" φ(n) 的位数: {phi.bit_length()} bits")
# 公钥指数
e = 65537
print(f"\n公钥指数 e = {e}")
# 检查 gcd
g = gcd(e, phi)
print(f"gcd(e, φ) = {g}")
if g != 1:
print("❌ 错误: e 和 φ(n) 不互质!")
exit(1)
# 计算私钥
print("\n计算私钥 d = e^(-1) mod φ(n) ...")
d = inverse(e, phi)
print(f" d 的位数: {d.bit_length()} bits")
print(" ✓ 私钥计算成功!")
print("\n步骤 3: 解密 RSA 消息")
print("-" * 80)
for idx, ct_hex in enumerate(ciphertexts):
print(f"\n{'='*60}")
print(f"消息 #{idx + 1}")
print(f"{'='*60}")
# 密文转为整数 (little-endian)
ct_bytes = bytes.fromhex(ct_hex)
ct_int = int.from_bytes(ct_bytes, 'little')
print(f"密文长度: {len(ct_bytes)} bytes")
print(f"密文 (前50字符): {ct_hex[:50]}...")
# RSA 解密: m = c^d mod n
print("\n执行解密: m = c^d mod n ...")
pt_int = pow(ct_int, d, n)
print(f"明文整数: {str(pt_int)[:50]}...")
# 转换为字节
try:
pt_bytes = long_to_bytes(pt_int)
print(f"明文字节长度: {len(pt_bytes)} bytes")
# 尝试解码为 UTF-8
try:
pt_str = pt_bytes.decode('utf-8')
print(f"\n✅ 解密成功!")
print(f"📝 明文: {pt_str}")
# 如果包含 flag 格式
if "flag" in pt_str.lower() or "@" in pt_str or "flare" in pt_str.lower():
print(f"\n🚩🚩🚩 FLAG: {pt_str} 🚩🚩🚩")
except UnicodeDecodeError:
print(f"\n⚠️ 无法解码为 UTF-8")
print(f"原始十六进制: {pt_bytes.hex()}")
# 尝试 ASCII
try:
pt_ascii = pt_bytes.decode('ascii', errors='ignore')
if pt_ascii.strip():
print(f"ASCII (忽略错误): {pt_ascii}")
except:
pass
except Exception as e:
print(f"\n❌ 解密出错: {e}")
print("\n" + "=" * 80)
print("完成!")
print("=" * 80)
[hr]
7.The Boss Needs Help
这个题存在大量算术逻辑混淆，MBA没有作用，所以我没有去混淆。期待大佬们的去混淆方案，学习一波。我直接在汇编窗口下断call指令，关注函数的输入和输出，有意思的函数就静态分析。这个题难在stage1 恢复username@computername。其实逻辑很简单，感觉这个值可能被加密过，因为这是用户数据，c2服务器加密数据也应该要用到，我得到这个值全靠猜。。
mov rax, [rsi] #获取服务器响应字符串
movzx ecx, byte ptr [rax+rbx] #将字符串第rbx位赋值给 ecx
mov rax, cs:Block #获取block表的地址
movzx r10d, byte ptr [rcx+rax] #根据字符串的值，获取block表对应地址的值
sub al, bl #al=0xff-bl
add r10b, al
mov rax, rbx #rbx 最大150
div rdi #rdi username@computername 长度
mov rax, qword ptr [rbp+170h+var_50] #username@computername
xor r10b, [rdx+rax]
inc rbx
call sub_7FF63E11EE00 #保存r10
mov rax, [rsi+8]
sub rax, [rsi]
cmp rbx, rax rax=0x97=151
这里通过服务器返回的16进制数据查表，以username@computername作为key，恢复加密数据。往后面分析，发现恢复的数据是json格式，跳过parse_json的函数后，发现提取key为"ack"的数据，所以一开始我使用{"ack": "这9个字符去尝试恢复username@computername，因为computername的长度不允许超过15个，并且限制为字符，数字和连字符，还有个限制条件是json数据最后的两个字符一定是"}，所以满足条件的username@computername至少11个字符，只有长度为14 17 19 20 22 23满足条件，150mod他们要>=10 ，通过测试，发现长度为19时，不可打印字符最少，并且后面的数据解析到了, "，所以意识到ack所在位置不对，然后分析流量包，发现线索：{"sta": "received"}，Host: theannualtraditionofstaringatdisassemblyforweeks.torealizetheflagwasjustxoredwiththefilenamethewholetime.com:8080，一切都通了，怪不得像，sta长度一样的，出来混全靠蒙。。。将ack换为sta，解密得到TheBoss@THUNDERNODE，恢复数据：{"sta": "excellent", "ack": "peanut@theannualtraditionofstaringatdisassemblyforweeks.torealizetheflagwasjustxoredwiththefilenamethewholetime.com:8080"}。
stage1能出来，后面解密流量包就很简单了，就是标准AES解密，动态调试发现key的生成，与前面可解密c2服务器的指令数据有关，IV没变化
import hashlib, binascii
A = hashlib.sha256(b"TheBoss@THUNDERNODE").digest()
#print(binascii.hexlify(A))
B0 = hashlib.sha256(b"peanut06").digest()
#'06'与时间有关，直接爆破
B1 = hashlib.sha256(b"TheBoss@THUNDERNODE06").digest()
B2 = hashlib.sha256(b"miami06").digest()
IV = b'000102030405060708090A0B0C0D0E0F'
#print(binascii.hexlify(B))
xor0 = bytes(x^y for x,y in zip(A,B0))
xor1 = bytes(x^y for x,y in zip(A,B1))
xor2 = bytes(x^y for x,y in zip(A,B2))
#print(xor)
key0 = binascii.hexlify(xor0)[0:64]
key1 = binascii.hexlify(xor1)[0:64]
key2 = binascii.hexlify(xor2)[0:64]
print(key0,key1,key2)
{"sta": "excellent", "ack": "peanut@theannualtraditionofstaringatdisassemblyforweeks.torealizetheflagwasjustxoredwiththefilenamethewholetime.com:8080"}
{"msg": "cmd", "d": {"cid": 6, "dt": 20, "np": "TheBoss@THUNDERNODE"}}
{"msg": "cmd", "d": {"cid": 6, "dt": 25, "np": "miami"}}
[hr]
8.FlareAuthenticator
Qt程序，一样存在混淆，对去混淆没啥想法，比较懒，主要是菜。通过静态分析，发现三个槽函数，输入，删除，验证。那么没有去混淆的情况下，怎么快速定位主要逻辑呢，我的方法是使用x64dbg trace 验证函数到弹窗wrong passwd的过程，通过不同输入，比对trace的不同，发现每个trace文件中有一块内存各不相同，其余的变化都在寄存器，这块内存肯定与输入数据相关。
通过对这块内存下硬件访问断点，可以在验证槽函数里找到最后数据的比对地方
mov rax, [rax+78h] #输入相关数据
mov rcx, 0BC42D5779FEC401h #目标值
sub rax, rcx
setz al
既然验证槽函数没有输入数据相关信息，说明数据的处理在输入槽函数，继续对那个内存点下硬件访问，写入断点，可以在输入槽函数还原整个逻辑。
mov rcx, [rbp+0FC0h+var_948]
mov rdx, [rbp+0FC0h+var_BC0] 0x100,0x200,0x300....
mov al, [rbp+0FC0h+var_C01]
movsx r9d, al #输入0-9的值
mov eax, r9d
not eax
mov r11d, edx
not r11d
or r11d, eax
mov eax, edx
add eax, r9d
mov r10d, eax
mov r8d, r11d
lea r8d, [r8+r10+1]
or edx, r9d
sub eax, edx
mov edx, eax
or edx, r8d
and eax, r8d
add eax, edx
mov dx, ax
mov rax, cs:off_7FF676A6FE40
mov r8, 64ED705730BC6591h
add rax, r8
call rax #
mov rcx, rax
mov rax, [rbp+0FC0h+var_C00] #每个框值固定，不同框值不同
imul rax, rcx
mov [rbp+0FC0h+var_C78], rax
mov rax, [rbp+0FC0h+var_948]
mov r9, [rbp+0FC0h+var_C78]
mov rdx, [rax+78h] #前一次计算的值
mov rcx, r9
not rcx
mov r8, rdx
not r8
or r8, rcx
mov rcx, rdx
add rcx, r9
lea r8, [r8+rcx+1]
or rdx, r9
sub rcx, rdx
mov rdx, rcx
or rdx, r8
and rcx, r8
add rcx, rdx
mov [rax+78h], rcx #最终结果值
虽然逻辑还原了，但是我是蒙的，一个25个框，每一个框0-9对应不同的数据，进行多次累加操作与最后的目标值比对，我是不知道怎么解决这个问题，所以我把他丢给了chatgpt。他告诉我，本质上在求解一个离散的模加法方程组：
$$
\sum_{i=0}^{N-1} table[i][x_i] \bmod 2^{64} = TARGET
$$
chatgpt告诉我只需要r9的值就够了，call rax 的逻辑不重要。chatgpt真强
#!/usr/bin/env python3
# solve_auth_by_inverse.py
# 纯 Python：验证汇编等价性并用逆推回溯求密码（0..9 per position）
# 运行: python3 solve_auth_by_inverse.py
from functools import lru_cache
import time, random
MASK = (1<<64) - 1
TARGET = 0x0BC42D5779FEC401 # from your assembly
#问题分析：解一个加法模方程
#(sum(table[i][x[i]]) mod 2^64) == TARGET
#从x64dbg日志解析的r9 数值
table = [
[0x0019B3240445AA06,0x000F2EB6684284AC,0x000C38D14DF6D665,0x001D3A557CD3A980,0x0026D8E6DC23319D,0x001C544F24D1B429,0x0017F846E0621293,0x001B6E4030F71F3D,0x00080F42A7139E80,0x001FCAC56F82739C],
[0x006F63394844DF78,0x003ED168087F3548,0x0006391D7049DDE8,0x008114813C91A610,0x00A8FA7B20F1E228,0x00786666BE83B978,0x006AE188A0BC46F0,0x006FB9A153C78328,0x001B18D762CB44C8,0x00921C4279B1A9A8],
[0x006DF6A4586E71C0,0x0049DE34FFC63EC0,0x0039FEE368E99380,0x7A11DE14C79E80,0xD8DC90E996E40,0x7146BFC66E2740,0x680673DB489E00,0x6E31309B7B8940,0x316C3AFCB92AC0,0x82DEEFE21A73C0],
[0x4EA15FC542C9C0,0x1CA2F34F18CD40,0xA614B2DC1C6980,0x60D84A48824900,0x9280B83FADD240,0x60801A9A7374C0,0x49FE057966CC00,0x579189ABC15440,0xB2F907A133B2C0,0x612F00F6EA6080],
[0x3AC57453ACE252,0x6229B366FE169,0xACB3FF351198AB,0x4C6C9CDBCE1FE5,0x7C9128173EA742,0x47ED36357FF53C,0x321B2C8DECC760,0x436E1CAD683194,0x97DE278C5E1226,0x489730C9AA7E6A],
[0x6402164C9FDB19,0x483F192B06217F,0x1E5CB35F54FA69,0x6E1E405C548974,0x137E71B08CA2AA,0x6928A14A143271,0x616EB297EDDB28,0x6431716B60DF88,0x2A4A823D6D822D,0x6E4F38A8434132],
[0x69B5253875B96,0x2BE31F155AB714,0x21AE09901BF552,0xB221597F1D3D8,0x1556DDAA385C92,0x7D821185844EC,0x462D157005089,0x6B104399CEDBC,0x1E79B0A36CDAFF,0xA266DD02D7453],
[0x9C0D47EAC35D2D,0x6FD7CB84FD4AD7,0x6255B824338303,0xAC26E207A0A6C5,0x23700DD18B0E3C,0xABD8D1A448644C,0x97F36052CAA668,0xA3F30CB6971D36,0x4F56BF7AFE673B,0x708E71FCEE988],
[0x30B9DA3C1BFE7,0x16F0557C6F1B97,0x105A5256455ED6,0x575F94A1E493B,0xC0C1389DB1C28,0x4D8773736490A,0x1DC3A46D3EB22,0x43AFA29A5046E,0x12101A50F4E1FB,0x737572378FC07],
[0x3A03C1D1D02F29,0x255E081F63BA07,0x1B8260C83DD73C,0x4188E0049C9EBA,0x527EEC073C111B,0x3DD8DF72E747E1,0x38195731A5D0AE,0x3A28381B02C813,0x162F7A6E9D784F,0x48C67301DAFECB],
[0x1D392355DF459C,0xBC35FAA41240,0x4D5BA7B7C6DB28,0x26C6DD80773E62,0x3C52C884071124,0x1FD5838C6C7F50,0x188898B9E96D66,0x1D66839EF1A1C0,0x58A12D4900A2FA,0x2DB81C4AE88D20],
[0x8484A22A795E4,0x5EB45F3E513AC,0x46247570894A4,0x924CE94DF0690,0x1D5530EA52210,0x920A24B9448D0,0x81027F2A79420,0x8B4887801A9FC,0x35E3DA634FB94,0x928D4D1040ED8],
[0xBE331DD3107AD,0x5E391DD240E89D,0x39874C7FFB294C,0x15E2AB5E23C478,0x312496AE1C4433,0x1356D94E3C824F,0x6FB9313A4228E,0x10CAFC6DD92AE3,0x409BC32BBA4E37,0x13B66FDE55B77C],
[0x19C7C11DA4E4A2,0x7FA2B9A827FAE,0x42193CC5270058,0x2043847B9EEDD8,0x2EE265CBAEA1AE,0x1D1555557808F2,0x1820C6CA831F20,0x19E699125F8740,0x3D81E379F6B82A,0x2062F49DA45AB4],
[0x1796E76685E997,0x5DC0C3E3261CDF,0x3A76362613DD95,0x201BB9EA8ED81C,0x33509B969E3741,0x19EB1C9C94E6A8,0x1368E07F2E794F,0x17BFD098C23630,0x448303CFD4DD31,0x1E41E65B7AFC35],
[0x9BDC1F78073127,0x75583891352145,0x4F18252739A5AC,0xC857C28BE5198,0x32C55970EA1358,0xC421F0A303C70,0x984973478DC5AC,0x56017C15FBDD1,0x5906717CF6C571,0x1A062A307BCABD],
[0xCCE53B2DF56140,0x926EC5880F9992,0x81FA523E38B793,0x481AF6CCB653B,0x39FC6F33CB770B,0xDB8605E2F4AA0E,0xC34699DB257145,0xD6872C5CC11542,0x6AD52B4C617CF3,0x12C1CA7EAE79A6],
[0x1DC6931C286DB2,0xED19AD19480BE,0x3A82193F6EF346,0x23394341031AC0,0x2F828795A6E6BE,0x208D625A5FD472,0x1C635AA6DF8398,0x1DE0F95CF827AE,0x3D2149D449636,0x28782F9453EFDE],
[0x139D946E9D6D82,0xB0E0C55A4D6238,0x97D9725BE8876E,0x26B598F9022C30,0x51C2FA15841D7E,0x18D5FBE4CDA4C8,0xA3F26DF601552,0x13F8DFF2FE8408,0x8A5498F0183BB0,0x3496095EF45282],
[0x72A31CFDE71EF6,0x46A5661935D9CA,0xBD4C34161B102,0x82A99A5DE4C84F,0xAE5A988393338F,0x825E0AE4D3D5F5,0x6E8EA108204593,0x7A7FE273C35A4C,0x172C91B106B2ED,0x82F69B85B1A2A1],
[0x40A5DB3578D586,0x22F572E6839826,0x1133B875BED53A,0x4A9B4A38CF1460,0x65C33E4F5A2FC0,0x481234127842A2,0x3BC3C87F8C0454,0x4588CE32DCF25A,0x573D341F00D72,0x48724D79B38078],
[0xC427156A9E2860,0x88B763CB6FB9F0,0x2F08D6E954E096,0xD9CCF65D9CD7A4,0x17C3E165050BF0,0xCF2B002B1AD140,0xBEA37CEF15E1FA,0xC48CEE7BAE850C,0x489420271C9606,0xDA31DC2C7FDBCE],
[0x537869C92A42D0,0x1DA1D095B7C0B4,0xBF7B1F10223116,0x6586F47FC6CF52,0x8E40676E4927E0,0x58692F2E100A24,0x4A9CA491835636,0x53CFDDBDD2F61C,0xB2B5098A832538,0x619C35508AEABA],
[0x8CC856E432BC50,0x62360169143A78,0x55333012D9DD23,0x9C4964E3F15005,0x18A07DDC589B2C,0x9BFE0FEDBF05DC,0x88D54339CF6CF1,0x9463624AACA2C6,0x42E7AF41E9BD7C,0xAB36B7C0777858],
[0x20CCD008AD41A,0x3684BCD9A0F789,0x2525F943737B70,0x86BB1A4A4AA7D,0x19CA34ADEE1B3A,0x6CC51DF5A1F44,0x4661D5224E5470,0x52CED44ED58CC,0x29A7CADA9C4CB1,0xD0CB5244CA7FD],
]
if len(table) != 25:
print("Warning: parsed blocks != 25, got", len(table))
# ---------- implement update as in assembly (to sanity-check it's addition) ----------
def update_asm(a, b):
# emulate the sequence you gave (translated)
rdx = a & MASK
r9 = b & MASK
rcx = (~r9) & MASK
r8 = (~rdx) & MASK
r8 |= rcx
rcx = (rdx + r9) & MASK
r8 = (r8 + rcx + 1) & MASK
rdx = rdx | r9
rcx = (rcx - rdx) & MASK
rdx = rcx | r8
rcx = rcx & r8
rcx = (rcx + rdx) & MASK
return rcx & MASK
def update_add(a,b):
return (a + b) & MASK
# quick random check: update_asm == a+b ?
#验证加法模型的正确性
print("Sanity testing update function equivalence (assembly-like vs add)...")
for _ in range(200):
a = random.getrandbits(64)
b = random.getrandbits(64)
x = update_asm(a,b)
y = update_add(a,b)
if x != y:
print("Mismatch found! assembly-like update != add for sample")
print(hex(a), hex(b), hex(x), hex(y))
raise SystemExit("update mismatch")
print("All random checks passed: update_asm == (a + b) mod 2^64. Good — we can use addition/inversion.")
# ---------- Prepare ordering and pruning helpers ----------
N = len(table)
abs_coefs = [ max(vals) for vals in table ] # rough magnitude proxy
# better heuristic: for each position compute min and max contribution
mins = [ min(vals) for vals in table ]
maxs = [ max(vals) for vals in table ]
# Order positions by span (max-min) descending to get stronger pruning
order = sorted(range(N), key=lambda i: (maxs[i]-mins[i]), reverse=True)
inv_order = {order[i]: i for i in range(N)}
table_ord = [ table[i] for i in order ]
# Precompute suffix min/max for pruning (in integer domain, not mod)
suf_min = [0]*(N+1)
suf_max = [0]*(N+1)
for i in range(N-1, -1, -1):
su = suf_min[i+1] + mins[order[i]]
sx = suf_max[i+1] + maxs[order[i]]
suf_min[i] = su
suf_max[i] = sx
# We'll search for integer equality with target + k*2^64. Compute feasible k range
total_min = sum(mins)
total_max = sum(maxs)
L_low = total_min
L_high = total_max
# Since final = (sum contributions) & MASK should equal TARGET, there exists integer T = TARGET + k*2^64 in [L_low, L_high]
import math
k_min = math.ceil((L_low - TARGET) / float(1<<64))
k_max = math.floor((L_high - TARGET) / float(1<<64))
candidates_T = [ TARGET + k*(1<<64) for k in range(int(k_min), int(k_max)+1) ]
print("Candidate integer targets count:", len(candidates_T), "k range:", k_min, k_max)
# ---------- DFS backward (subtract contributions) but implemented as forward assignment with pruning ----------
start_time = time.time()
TIMEOUT = 300 # seconds
solution = None
nodes = 0
def dfs(idx, current_sum, assign):
global solution, nodes, start_time
if solution is not None:
return True
if time.time() - start_time > TIMEOUT:
return False
nodes += 1
# pruning by remaining min/max
if current_sum + suf_min[idx] > target_T:
return False
if current_sum + suf_max[idx] < target_T:
return False
if idx == N:
if current_sum == target_T:
# reorder assign to original order
sol = [0]*N
for j, val in enumerate(assign):
orig = order[j]
sol[orig] = val
solution = sol
return True
return False
vals = table_ord[idx]
# choose a promising digit order: try digits sorted by closeness to average
# heuristic: try digits in order of descending contribution (could try both)
digit_order = sorted(range(10), key=lambda d: abs(vals[d] - (target_T - current_sum)/(N-idx + 1)))
for d in digit_order:
new_sum = current_sum + vals[d]
# quick prune
if new_sum + suf_min[idx+1] > target_T:
continue
if new_sum + suf_max[idx+1] < target_T:
continue
assign.append(d)
if dfs(idx+1, new_sum, assign):
return True
assign.pop()
return False
# Try each candidate integer target
for candidate in candidates_T:
target_T = candidate
print("Trying integer target:", target_T, " (hex low64:", hex(target_T & MASK), ")")
solution = None
nodes = 0
start_time = time.time()
ok = dfs(0, 0, [])
print("Nodes searched:", nodes, "time:", time.time()-start_time)
if ok and solution:
print("FOUND solution:", solution)
print("As 5x5 grid:")
for r in range(5):
print(solution[r*5:(r+1)*5])
break
if solution is None:
print("No solution found within timeout. Consider increasing TIMEOUT or improving heuristics.")
else:
print("Done. total time:", time.time() - start_time)
这次比赛尝试了一些新思路，get了一些想法，还是收获良多的。遗憾的是最后一题没解出来，，静态分析功力不够，理不清check函数的逻辑，更别说1万个了。。。最后对完成的大神表示崇高的敬意，特别是前面的，大佬带带我！！神的世界我依然理解不了！！！
发表于 2025-10-25 10:14
