本文最初写于2019年，旨在帮助希望在一些相对较难的CTF国际赛上解出密码学题目的同学构建一个知识框架和学习路线，近日整理了部分内容，发表在看雪论坛上，以下是本文内容（也可访问这里 以PDF格式查看，排版更为清晰）：
作者：道路结冰（roadicing） 日期：2019-12-05
密码学不仅是CTF竞赛中的一个重要的独立考察方向，也经常作为考点出现在其他方向的题目当中。本文从个人作为一名CTF密码学方向选手的视角入手，对需要掌握的相关内容进行整理与分析，以期帮助选手更好的学习密码学，更好的进行密码学方向题目的训练，取得更好的比赛成绩。
密码分析的各个环节都离不开数学分析，对于选手求解一道CTF中的密码学方向题目来讲也是如此。在CTF中，主要考察密码学选手数论和抽象代数两个方向的数学知识。
在数论方向，选手应能较为熟练的了解和掌握包括：
在抽象代数方向，选手应能较为熟练的了解和掌握包括：
除此之外，诸如逻辑学、几何学、拓扑学、泛函分析、概率论、数理统计等其他数学分支，虽然在CTF竞赛中密码学方向题目直接考察较少，但选手应至少对其相关基本知识有一个大致了解。
古典密码学作为早期CTF竞赛中密码学方向的一种常见考察形式，目前已经逐渐退出国际赛的历史舞台了。
现代密码学作为目前CTF竞赛中密码学方向的主要考察形式，从总体上可以分为对称密码学、非对称密码学、哈希函数和数字签名四大类题目，其中每类题目在知识点层面虽互有交集，但由于考察形式各有侧重，因此本文对这四类题目类型分别进行论述。
流密码通常以字节或比特为基本单位来处理信息，其密钥通常派生自一个较短的种子密钥，而派生算法一般为一个伪随机数生成算法，流密码的安全性取决于密钥流的安全性，因此CTF中的流密码类题目也主要以伪随机数生成器部分为主，当然除此之外，题目有时也会考察选手对某一具体的流密码算法的理解和分析能力，如A5/1、RC4等。
块密码使用某一基本块为基本单位来处理信息，在加密时需要将明文数据分成若干基本块，再针对每一块进行加密，如果最后一块的长度小于基本块的长度，还需要进行padding。
CTF竞赛中的非对称密码学主要考察三大类问题，即大整数分解问题、离散对数求解问题（包括椭圆曲线上的离散对数求解问题）和基于格（Lattice）的计算问题：
CTF中大整数分解问题主要以RSA算法为模型进行考察，RSA在目前CTF竞赛中考察频率可以说所有考点第一位，几乎任何一场比赛都会有一道密码学题目考察RSA，根据题目中给定的RSA算法的不同场景，其攻击手法五花八门，需要选手具备很强的数论功底。
CTF中考察DLP类问题主要以Diffie–Hellman 密钥交换协议和ElGamal算法为主，要求选手能够通过审计代码找出问题关键点，并使用攻击算法求解DLP问题，常用的DLP攻击算法包括：
CTF中考察ECDLP类问题主要以椭圆曲线加密（ECC）为主，其曲线有限域通常为以素数为模的域 GF(p)或特征为2的域 GF(2^m)，ECDLP类题目的考察方式除了包括上面提到的DLP的一些常见模型和攻击手法的椭圆曲线版以外，也包括一些针对曲线上存在的问题的攻击形式，如：
CTF中考察格中的计算困难问题主要包括最近向量问题（CVP）和最短向量问题（SVP）问题，其考察形式主要分为两类：
数字签名主要用于对数字消息进行签名，主要用于防止消息被冒名伪造、篡改，以及通信双方的身份鉴别。由于数字签名主要依赖于非对称密码算法，因此CTF当中考察数字签名类题目也主要依托非对称密码体系来进行设计，常见的包括RSA签名、ElGamal签名、DSA签名、针对某一特定椭圆曲线的ECC签名等，题目模型通常为要求我们提供某一特定字符串的签名，如果能正确通过验证则提供给选手FLAG，针对数字签名类题目的攻击我们一般从三个角度来切入：
CTF中考察哈希函数类问题主要以两类场景进行展开：
在考察形式上，题目通常会直接要求选手向服务器提交A、B两个输入，如果满足AB但HASH(A)=HASH(B)，则判断碰撞成功。HASH碰撞类题目虽然场景简单，但通常题目难度较大，而且很多时候都是出题人魔改之后的哈希算法，因此要求选手具备较强的分析能力，在攻击上多以考察代数攻击为主，如：
另一类则是哈希伪造场景，虽然很多时候伪造哈希也可以通过寻找碰撞的方式来实现，但是它和碰撞场景下的考察侧重点通常不同，一种典型的攻击手法即哈希长度扩展攻击，即在已知的值和的长度的情况下（这里的值未知，即代表哈希时的salt），要求选手对于任意一个的值。对于哈希伪造的场景，我们的重点一般直接从攻击手法入手，而不需要对源码进行审计（绝大多数情况下，这类场景也不会给出哈希算法细节，而是直接调用现成的MD5、SHA1库函数）。
自2018年起，大量论文题开始登上CTF历史舞台，然而一场标准的CTF国际赛通常为48小时，留给选手的分析时间是有限的，因此对于很多国际赛上的密码分析类题目来讲，选手是很难在短时间内提出一种可行的攻击手段的。这个时候，就需要快速提炼出题目当中的模型、场景等关键内容，然后去检索并阅读与之对应的会议、期刊论文，从中寻找攻击思想或手段。因此，选手的论文阅读理解能力（尤其是英文文献的阅读能力）对于密码学方向来讲就显得尤为重要。近年来国际赛当中CTF题目与学术界论文或研究成果联系紧密，如：
还有很多题目直接以某一论文或研究成果为背景进行设计，如：
2017年5月，Divesh Aggarwal等学者提出了一种基于梅森素数的公钥密码体系[5]，2个月后，该密码系统被Marc Beunardeau等学者攻破，相关成果以论文形式发表[6]，同年9月，该事件以CTF形式出现在当年的ASIS CTF竞赛当中，预期选手通过阅读论文使用随机划分和LLL攻击攻破密码系统。
2017年2月，马萨里克大学的Matus Nemec和Marek Sys等学者发现英飞凌科技提供的RSALib库中的密钥生成算法存在漏洞，并据此提出了一种可行的RSA ROCA攻击。同年11月，相关攻击细节以论文形式披露[7]（该攻击同步影响了TPM 1.2, 4.3.5版本前的YubiKey 4等产品，CVE编号：CVE-2017-15361），两周后，该事件以CTF形式出现在当年的HXP CTF竞赛当中，预期选手通过阅读论文使用ROCA攻击攻破一个RSA密钥生成算法。
对于绝大多数情况下，当选手通过审计源码或者阅读论文整理出一种攻击手段之后，接下来都需要通过编程的方式写一个solver或exp来计算出你所需要的数据或实现你的攻击方式，这个时候就需要选手具备良好的编程功底，因为很多时候将复杂的数学模型转化成可行的脚本并不是一件容易的事。
由于CTF竞赛中专职密码学方向的选手通常较少，因此一场比赛是否有较高质量的密码学题目其实往往取决于办比赛的战队中有没有一个优秀的密码学选手，目前有一些比赛的密码学题目质量是要远高于其他竞赛的，值得参赛选手去重点关注（另外有一些战队虽然拥有很强的密码学选手，但是战队办比赛较少，可以关注其每次比赛赛后发布的writeup来了解其做题时的一些思路和解法）：
对于一名密码学方向的CTF选手来讲，除了通过活跃于各大CTF比赛和在平时保持足够的CTF题目训练强度来提升自己的水平之外，实际上还有一些其他的密码学相关竞赛可以用来作为训练，每年诸如NSU CRYPTO、WhibOx Contest等解题类密码学竞赛，也可以参加或做赛后练习用，以此来锻炼密码分析能力。
兴趣因素放在本文最后一个环节进行论述，但是实际上这是学习密码学的第一步，也是最重要的一步，拥有对探索密码学领域的无限热情，会使你比任何人都更有可能成为一名优秀的CTF密码学选手。
[1] Ko, K.H., & Lee, J.W. (2006). A fast algorithm to the conjugacy problem on generic braids.
整除理论（了解素数、合数、因数、倍数、整除等基本概念，掌握唯一分解定理、裴蜀定理、扩展欧几里得定理、算数基本定理等基本定理）
同余理论（了解同余、原根、底数、指数、平方剩余、同余式、同余方程等基本概念，掌握欧拉定理、费马小定理、中国剩余定理、二次互反律、威尔逊定理等基本定理）
连分数理论（了解连分数、无穷级数等基本概念，熟悉最佳有理数逼近、循环连分数展开、佩尔方程求解等运算过程）
不定方程（了解低次代数曲线所对应的不定方程的基本模型，熟悉二元一次不定方程、多元一次不定方程、掌握通过代数恒等变化、不等式估算、同余法、构造法、无穷递降法等常用的不定方程求解方法）
数论函数（了解欧拉函数、莫比乌斯函数、单位函数、恒等函数、除数函数等常用函数，掌握莫比乌斯反演、狄利克雷卷积等常用方法）
群论（熟悉群代数结构，掌握群相关性质及其运算律）
环论（熟悉群代数结构，掌握环相关性质及其运算律）
域论（熟悉群代数结构，掌握域相关性质及其运算律）
格论（熟悉格代数结构，掌握格相关性质及其运算律）
线性代数（熟悉向量空间代数结构，掌握向量相关性质及其运算律）
针对模数的攻击：如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攻击（选择密文）。
小步大步法（Baby-step giant-step，中间相遇攻击的思想）
Pollard’s Rho algorithm（基于Miller-Rabin算法，递归求解）
Pollard’s Kangaroo algorithm（基于随机步）
Pohlig-Hellman algorithm（针对阶n是光滑且仅有小素因子）
针对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）。
设法直接计算私钥，比如参数值过小或曲线选择不合适，导致私钥可以被直接计算出来（如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比特币签名算法的银行提款签名）。
同谋碰撞攻击：生成任意两个不同的消息和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)
利用small capacity parameter误用问题构造SHA3 Keccak海绵结构碰撞（2019 0CTF/TCTF Quals-babysponge）
利用Petit-Lauter攻击构造超奇异同构图上Charles-Goren-Lauter哈希函数的弱实例碰撞（2017 HXP CTF-categorical）
2018 PlaidCTF-braid题目，考察选手通过阅读论文[1]，解决一个辫子群（Braid Group）下的 Conjugacy Search 问题。
2018 Hack.lu CTF- Escape the grid题目，考察选手通过阅读论文[2]，攻破一个使用了非安全函数产生仿射变换的 rasta 密码系统。
2019 0CTF/TCTF Quals-zer0lfsr题目，考察选手通过通过阅读论文[3]，利用Fast Correlation Attack恢复出一个Meier-Staffelbach模型下0.75相关性的3个LFSR的初始状态（虽然这道题在当时比赛时被z3非预期了）。
2019 PwnThyBytes CTF-Wrong Ring题目，考察选手通过阅读论文[4]，通过将环上带误差学习（RLWE）样本转化为多项式带误差学习(PLWE)样本，攻击一个（non-dual）RLWE的实例来求私钥。
2017 ASIS CTF Final-Marijuana
Teaser Dragon CTF（波兰Google安全团队Dragon Sector战队主办）
0CTF/TCTF （中国腾讯安全A0 E战队主办）
HXP CTF （德国慕尼黑工业大学HXP战队主办）
ASIS CTF & Crypto CTF （伊朗谢里夫理工大学ASIS战队主办）
CODE BLUE CTF （日本联合战队binja主办）
PlaidCTF （美国卡耐基梅隆大学PPP战队主办）
Midnight Sun CTF （瑞典HackingForSoju战队主办）
SpamAndFlags Teaser CTF （匈牙利布达佩斯技术与经济大学!SpamAndHex战队主办）
PwnThyBytes CTF （罗马尼亚PwnThyBytes战队主办）
整除理论（了解素数、合数、因数、倍数、整除等基本概念，掌握唯一分解定理、裴蜀定理、扩展欧几里得定理、算数基本定理等基本定理） 同余理论（了解同余、原根、底数、指数、平方剩余、同余式、同余方程等基本概念，掌握欧拉定理、费马小定理、中国剩余定理、二次互反律、威尔逊定理等基本定理）
[招生]科锐逆向工程师培训(2024年11月15日实地，远程教学同时开班, 第51期)
