一、数学功底

1 数论

• 整除理论（了解素数、合数、因数、倍数、整除等基本概念，掌握唯一分解定理、裴蜀定理、扩展欧几里得定理、算数基本定理等基本定理）
• 同余理论（了解同余、原根、底数、指数、平方剩余、同余式、同余方程等基本概念，掌握欧拉定理、费马小定理、中国剩余定理、二次互反律、威尔逊定理等基本定理）
• 连分数理论（了解连分数、无穷级数等基本概念，熟悉最佳有理数逼近、循环连分数展开、佩尔方程求解等运算过程）
• 不定方程（了解低次代数曲线所对应的不定方程的基本模型，熟悉二元一次不定方程、多元一次不定方程、掌握通过代数恒等变化、不等式估算、同余法、构造法、无穷递降法等常用的不定方程求解方法）
• 数论函数（了解欧拉函数、莫比乌斯函数、单位函数、恒等函数、除数函数等常用函数，掌握莫比乌斯反演、狄利克雷卷积等常用方法）

2 抽代

在抽象代数方向，选手应能较为熟练的了解和掌握包括：

• 群论（熟悉群代数结构，掌握群相关性质及其运算律）
• 环论（熟悉群代数结构，掌握环相关性质及其运算律）
• 域论（熟悉群代数结构，掌握域相关性质及其运算律）
• 格论（熟悉格代数结构，掌握格相关性质及其运算律）
• 线性代数（熟悉向量空间代数结构，掌握向量相关性质及其运算律）

二、密码学技能树

1 古典密码学

古典密码主要以代替（substitution）密码和置换（permutatuion）密码两种形式出现，在题目当中，出题人通常不会显式的告诉你题目所采用的加密算法，而是仅仅给出密文，预期选手通过特征检索（如密文字符集中存在标志性的特殊字符）、题目暗示（如题目名称、题目描述中出现了对加密算法的隐喻）等方式猜测出题目中可能使用的加密算法，或使用数理统计（针对密钥空间较大的代换密码，如仿射、维吉尼亚等）、爆破（针对密钥空间较小的代换或置换密码，如栅栏、移位等）等方式恢复出密钥，最后解密密文拿到FLAG。

2 现代密码学

总体上可以分为对称密码学、非对称密码学、哈希函数和数字签名四大类题目，其中每类题目在知识点层面虽互有交集，但由于考察形式各有侧重，因此本文对这四类题目类型分别进行论述。

a 流密码(对称密码)

流密码通常以字节或比特为基本单位来处理信息，其密钥通常派生自一个较短的种子密钥，而派生算法一般为一个伪随机数生成算法，流密码的安全性取决于密钥流的安全性，因此CTF中的流密码类题目也主要以伪随机数生成器部分为主，当然除此之外，题目有时也会考察选手对某一具体的流密码算法的理解和分析能力，如A5/1、RC4等。

对于伪随机数生成器来讲，常见的考察模型主要可以分为两类：

一类为线性同余生成器（LCG），题目要求选手通过对生成器源码审计，找出设计缺陷（针对生成器参数随机化的场景）或进行数学推导恢复未知参数（针对参数恒定不变但缺失部分参数的场景），继而连续预测出接下来产生的若干个随机数，从而达到服务器要求拿到FLAG。

另一类为反馈移位寄存器，其中又可分为线性反馈移位寄存器（LFSR）和非线性反馈移位寄存器（NFSR）两类主要考察模型，出题人通常会根据某一初始状态采用某种生成方法生成一份输出结果，然后将生成方法和输出结果提供给选手，预期选手还原出初始状态从而作为FLAG。

b 块密码(对称密码)

块密码使用某一基本块为基本单位来处理信息，在加密时需要将明文数据分成若干基本块，再针对每一块进行加密，如果最后一块的长度小于基本块的长度，还需要进行padding。

目前CTF中针对块密码主要从三个角度考察：

第一类是从块密码当中的ARX（A-有限域上的模加，R-循环移位，X-异或）三种基本操作入手，考察选手对组合运算的熟练程度和理解能力。

第二类是从具体算法角度入手，考察AES、DES等经典加密算法（或该加密算法的自定义修改版本）的线性攻击、差分攻击、积分攻击等攻击手法和选手做密码分析的能力。

第三类是从分组模式入手，考察算法在padding时（如针对PKCS5 Padding的Padding Oracle攻击）或加密模式上（如CBC字节翻转攻击、CFB重放攻击）可能会出现的问题。

c 非对称密码

大整数分解问题、离散对数求解问题（包括椭圆曲线上的离散对数求解问题）和基于格（Lattice）的计算问题

大整数分解问题

CTF中大整数分解问题主要以RSA算法为模型进行考察，RSA在目前CTF竞赛中考察频率可以说所有考点第一位，几乎任何一场比赛都会有一道密码学题目考察RSA，根据题目中给定的RSA算法的不同场景，其攻击手法五花八门，需要选手具备很强的数论功底。

但也正是由于RSA知识点考察过于热门，导致网上相关资料和现成的攻击脚本较为成熟，对于一些简单的RSA类题目，选手往往只需判断出该题涉及到的RSA的哪一类场景，然后根据特征去检索攻击手法即可，但对于一些国际赛上的高质量RSA类题目，仍然需要选手具备极强的分析和推导能力。目前针对RSA的常见攻击大致包括以下几类：

• 针对模数的攻击：如Pollard’s p -1算法（p-1光滑）、Williams’s p + 1（p+1光滑）、试除法（|p-q|过大）、费马分解（|p-q|过小）、共模攻击、模不互素攻击等。
• 针对公钥的攻击：如小公钥指数攻击、低加密指数广播攻击等。
• 针对私钥的攻击：如Wiener’s attack（基于连分数）、私钥低位泄露攻击等。
• Coppersmith & LLL相关攻击：如已知m高位攻击、已知p高位攻击、Coppersmith’s short-pad attack、Boneh and Durfee attack等。
• 结合Oracle的攻击：有时题目当中除了提供给选手参数之外还会提供一个加密/解密Oracle，结合Oracle可以衍生出更多种攻击形式，如针对加密Oracle的公钥泄露攻击（选择明文），针对解密Oracle的RSA LSB parity Oracle攻击（选择密文）。

d 离散对数求解问题

CTF中考察DLP类问题主要以Diffie–Hellman 密钥交换协议和ElGamal算法为主，要求选手能够通过审计代码找出问题关键点，并使用攻击算法求解DLP问题，常用的DLP攻击算法包括：

• 小步大步法（Baby-step giant-step，中间相遇攻击的思想）
• Pollard’s Rho algorithm（基于Miller-Rabin算法，递归求解）
• Pollard’s Kangaroo algorithm（基于随机步）
• Pohlig-Hellman algorithm（针对阶n是光滑且仅有小素因子）

CTF中考察ECDLP类问题主要以椭圆曲线加密（ECC）为主，其曲线有限域通常为以素数为模的域 GF(p)或特征为2的域 GF(2^m)，ECDLP类题目的考察方式除了包括上面提到的DLP的一些常见模型和攻击手法的椭圆曲线版以外，也包括一些针对曲线上存在的问题的攻击形式，如：

• 针对E(Fp)=p（Frobenius轨迹t=p+1−E(Fp)=1）的上非正规椭圆曲线的Smart’s attack。
• 针对p|q+1−E(Fq)（Frobenius轨迹t是p的倍数）的超奇异椭圆曲线的MOV攻击（借助Tate pairing或者Weil pairing）。

e 基于格的计算问题

CTF中考察格中的计算困难问题主要包括最近向量问题（CVP）和最短向量问题（SVP）问题，其考察形式主要分为两类：

一类是利用格理论去分析已知的经典密码算法，如使用格基规约算法（LLL）来分析DSA签名系统（如DSA nonce biases）、RSA加密系统（如RSA的小私钥攻击、Coppersmith相关的攻击）、背包加密系统（如Merkle–Hellman背包公钥加密算法）等。

另一类是分析基于格中困难问题设而设计新的后量子密码体制，如NTRU密码系统、GGH密码系统、Gentry算法的全同态加密系统、基于LWE问题的密码系统、Ajtai–Dwork概率公钥密码系统等。

基于格的计算问题类题目在目前CTF竞赛中频繁出现，一度成为国际赛当中的主流考点，尤其是对LLL算法的理解和使用，成为解出许多高分值题目的关键。很多时候格相关攻击较为复杂，需要选手结合论文来进行推导，关于CTF竞赛中的论文问题会在后面的章节具体阐述。

f 数字签名

数字签名主要用于对数字消息进行签名，主要用于防止消息被冒名伪造、篡改，以及通信双方的身份鉴别。由于数字签名主要依赖于非对称密码算法，因此CTF当中考察数字签名类题目也主要依托非对称密码体系来进行设计，常见的包括RSA签名、ElGamal签名、DSA签名、针对某一特定椭圆曲线的ECC签名等，题目模型通常为要求我们提供某一特定字符串的签名，如果能正确通过验证则提供给选手FLAG，针对数字签名类题目的攻击我们一般从三个角度来切入：

• 设法直接计算私钥，比如参数值过小或曲线选择不合适，导致私钥可以被直接计算出来（如2019 ASIS CTF Quals-Halloween Party题目，给定y坐标求x坐标，计算2在模P.order()上的逆并将结果乘2*P直接得到P）
• 设法恢复私钥，即通过若干特殊明文签名对，采用建立方程等方式重构出密钥（如2019 DEFCON CTF Quals-Tania题目，通过LLL算法和Babai最近平面算法恢复出密钥）
• 设法伪造签名，即在不知道私钥的情况下，直接构造出特定字符串的签名来拿到FLAG（如2019 RealWorld CTF-bank题目，通过rogue-key attack伪造Schnorr比特币签名算法的银行提款签名）。

g 哈希函数

CTF中考察哈希函数类问题主要以两类场景进行展开：

一类是哈希碰撞类场景，常见的攻击类型包括：

• 同谋碰撞攻击：生成任意两个不同的消息和x和y，使得哈希值f(x)=f(y)
• 第二原像攻击：给定任意一个x及其哈希值f(x)，可以生成一个与之不同的y使得哈希值f(x)=f(y)
• 相同前缀攻击：给定任意一个前缀p，可以生成两个不同的后缀和x和y，使得哈希值f(p+x)=f(p+y)
• 选择前缀攻击：给定任意两个不同的前缀p和q，可以生成两个不同的后缀x和y，使得哈希值f(p+x)=f(q+y)

在考察形式上，题目通常会直接要求选手向服务器提交A、B两个输入，如果满足AB但HASH(A)=HASH(B)，则判断碰撞成功。HASH碰撞类题目虽然场景简单，但通常题目难度较大，而且很多时候都是出题人魔改之后的哈希算法，因此要求选手具备较强的分析能力，在攻击上多以考察代数攻击为主，如：

• 利用small capacity parameter误用问题构造SHA3 Keccak海绵结构碰撞（2019 0CTF/TCTF Quals-babysponge）
• 利用Petit-Lauter攻击构造超奇异同构图上Charles-Goren-Lauter哈希函数的弱实例碰撞（2017 HXP CTF-categorical）

另一类则是哈希伪造场景，虽然很多时候伪造哈希也可以通过寻找碰撞的方式来实现，但是它和碰撞场景下的考察侧重点通常不同，一种典型的攻击手法即哈希长度扩展攻击，即在已知的值和的长度的情况下（这里的值未知，即代表哈希时的salt），要求选手对于任意一个的值。对于哈希伪造的场景，我们的重点一般直接从攻击手法入手，而不需要对源码进行审计（绝大多数情况下，这类场景也不会给出哈希算法细节，而是直接调用现成的MD5、SHA1库函数）。