中国剩余定理(CRT)详解—从孙子定理到 RSA 应用
“有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”——《孙子算经》 这就是中国剩余定理（CRT）的起源。在 CTF 密码学中，CRT 无处不在：RSA 加速解密、共模攻击、广播攻击、Elliptic Curve 点合并……不会 CRT，密码学题基本做不动。 1. 定理内容给定一组同余方程： 1234x ≡ a₁ (mod m₁)x ≡ a₂ (mod m₂)...x ≡ aₖ (mod mₖ) 如果 m₁, m₂, …, mₖ 两两互质，则存在唯一解 mod M = m₁ × m₂ × … × mₖ。 2. 标准 CRT 实现1234567891011...
线段树详解—从单点修改到区间操作
线段树是竞赛算法中最常用的数据结构之一。它把数组按区间分治组织，让单点修改、区间查询、区间修改都能在 O(log n) 时间完成。CTF 中的 Misc、逆向、甚至部分 Pwn 题都可能用到。 这篇文章从基础线段树讲起，到懒标记（Lazy Propagation）的区间修改，最后讲几个经典建模。 1. 为什么需要线段树先想一个问题：给一个数组 a[1..n]，需要支持两种操作： 修改某个元素 a[i] = v 查询区间 [l, r] 的和 朴素做法：修改 O(1)，查询 O(n)。n=10^6 时查询太慢。 前缀和：修改 O(n)，查询 O(1)。修改太多又太...
Miller-Rabin 素性测试与 Pollard's Rho 分解详解
大数分解是 RSA 密码学的命门。CTF 密码学题里，给你一个几百位的 n 让你分解，你总不能从 2 试到 √n 吧？这时候就需要 Miller-Rabin 判断是不是质数，Pollard’s Rho 做概率分解。 这篇文章把这两个算法讲透，附上可直接用的 Python 实现。 1. Miller-Rabin 素性测试原理费马小定理：如果 p 是质数，那么对任意 a，a^(p-1) ≡ 1 (mod p)。 反过来，如果 a^(n-1) ≢ 1 (mod n)，那 n 一定不是质数。这就是 Miller-Rabin 的基础。 但费马小定理的逆命题不成立——存在 Carmichael ...
反调试与反反调试技巧详解—从原理到实战
做逆向分析的人都绕不开反调试。CTF Pwn 题里经常埋各种反调试，商业软件更是把反调试做成了一套体系。你不会反反调试，连主函数都看不到。 这篇文章按”从用户态到内核态、从简单到复杂”的顺序，梳理 Windows 下常见的反调试手段和对应的绕过方法。不是教程式的罗列，而是讲清楚每个手段的原理——原理懂了，变种一眼就能看出来。 1. 最简单的：检查 BeingDebugged 标志位原理PEB（Process Environment Block）的偏移 0x02 处有一个 BeingDebugged 字节。如果进程被调试器附加，这个字节为 1。 12345; 经典反调试代码mov ea...
Dinic 网络流算法详解—从原理到竞赛实战
网络流是图论中最实用的算法之一。最大流最小割定理把”求最大流”和”求最小割”等价起来，于是大量看似和流没关系的问题——二分图匹配、边连通度、选边方案、拆点建模——都能套上网络流的框架。 Dinic 算法是实际竞赛中最高效的最大流算法，复杂度 O(V²E)，在实际图中远快于理论上界。这篇文章把 Dinic 的原理讲透，然后落地到建模套路。 1. 流网络的基本概念一个流网络是一个有向图 G=(V,E)，每条边有容量 c(u,v)，有一个源点 s 和汇点 t。 流 f 满足三个条件： 容量限制：0 ≤ f(u,v) ≤ c(u,v) 流量守恒：除 s 和 t 外，所有点的流入量...
二次剩余与 Tonelli-Shanks 算法详解
二次剩余（Quadratic Residue）是 CTF 密码学里的高频考点。RSA 中解密需要求模 n 的平方根，ECDSA 签名验证涉及二次剩余判定， even 简单的”猜数”题都可能藏着 Legendre 符号的套路。 这篇文章从定义出发，讲清楚什么是二次剩余、怎么判定、怎么求平方根，最后落地到 CTF 中的常见应用。 1. 什么是二次剩余给定奇质数 p 和整数 a，如果存在 x 使得： 1x² ≡ a (mod p) 则称 a 是模 p 的二次剩余（Quadratic Residue, QR），否则称为二次非剩余（Quadratic Non-Residue, QNR）。 举...
服了某中学
NBNB，关系户这一块，带手机不管（别对号入座
Rust 系统编程入门—从 unsafe 到安全工具开发
很多人对 Rust 的印象停留在”安全、 borrow checker、学习曲线陡峭”。但在安全工具开发领域，Rust 真正的价值是：它让你能写 C 级别的底层代码，同时不 segfault。 你写过 pwntools 就知道 Python 做性能敏感的事情有多痛苦——解析大二进制文件、批量 fuzz、hook 系统调用，Python 永远慢半拍。Rust 刚好填了这个坑：编译成原生机器码，零成本抽象，内存安全，还有成熟的 FFI 可以和 C 库互操作。 这篇文章不讲 Rust 语法基础，直接讲写安全工具时最需要的东西：unsafe、FFI、进程注入、内存操作。 1. 为什么安全工具...
椭圆曲线密码学(ECC)详解—从数学原理到 CTF 密码学实战
椭圆曲线密码学（ECC）是现代密码学的基石之一。Bitcoin 用 secp256k1，TLS 用 secp256r1，Signal 用 X25519，WhatsApp 用 Curve25519。CTF 密码学题里，ECC 更是常客——从小白友好的非ce点攻击，到高难度的 SMART 攻击、无效曲线攻击、MOV 攻击，变种繁多。 这篇文章从零开始讲 ECC 的数学原理，然后落地到 CTF 中常见的攻击手法和解题套路。 1. 什么是椭圆曲线在密码学中，椭圆曲线定义在有限域上，形如： 1y² = x³ + ax + b (mod p) 其中 p 是一个大质数，a、b 满足 4a³ +...
后缀自动机(SAM)详解—从原理到 CTF 字符串题实战
后缀自动机（Suffix Automaton，简称 SAM）是处理字符串问题最强大的数据结构之一。它能在 O(n) 时间内构造出一个状态数 O(n) 的自动机，之后可以在线性时间内回答大量字符串相关的问题：不同子串个数、最长重复子串、出现次数最多的子串、子串出现次数、最小表示法……在 CTF 的 Misc 和逆向题中，SAM 经常用来做字符串匹配、密码分析、文本去重等任务。 很多人觉得 SAM 难，其实核心就两条：endpos 等价类和后缀链接。把这两个概念搞懂了，剩下的都是工程细节。 1. 为什么需要 SAM先想一个朴素问题：给一个长度为 n 的字符串，统计它有多少个不同的子串。 ...
