目录：
- 前言
这篇文章是2024 SpiritCTF Warmup中一些题目（见目录）的官方题解。
- Crypto - What is RSA?
附件在此：
RSA是由Ron Rivest、Adi Shamir和Leonard Adleman提出的一种非对称密码系统。传输信息时，加密者使用公钥加密信息，解密者使用私钥解密信息。与对称密码不同的是，使用公钥加密后的信息必须使用私钥解密（而非公钥）。RSA的基本原理是欧拉定理（Euler's theorem）（参见OI-Wiki）：
\[ ed\equiv 1\pmod{\varphi(N)},\quad N=pq,\quad \varphi(N)=(p-1)(q-1) \] \[ c\equiv m^e\pmod{N},\quad c^d\equiv m^{ed}\equiv m^{1+k\varphi(N)}\equiv m\cdot (m^{\varphi(N)})^k\equiv m \pmod{N} \]其中\(e\)是我们的公钥，而\(d\)是我们的私钥，\(m,c\)分别是明文和密文。本题给出了\(p,q,e\)的值，并且（一般情况下）\(e\)与\(\varphi(N)\)不互素，因此我们可以通过求解\(e\)在模\(\varphi(N)\)意义下的乘法逆元（参见OI-Wiki）轻易地求出\(d\)的值：
# Python 3.x
phi = (p-1) * (q-1)
d = pow(e, -1, phi)通过私钥\(d\)与密文\(c\)即可还原出明文\(m\)的值：
# pip install pycryptodome
from Crypto.Util.number import *
m = pow(c, d, N)
flag = long_to_bytes(m)其中明文的字节经过大端序编码，比如：
Char: S p i r i t { }
| | | | | | | |
v v v v v v v v
Ascii: 53 70 69 72 69 74 7B 7D也即
bytes_to_long(b'Spirit{}') == 0x5370697269747B7D == 6012421442656041853Proof of Concept：
Flag🚩：
Spirit{w3lc0mE_t0_7he_W0rLd_oF_Crypt0graphy_:p}- Crypto - Secret Shredder 1
附件在此：
也是一个RSA的问题，不过这次没有p和q了，得通过其他的方法把私钥d给求出来，而这通常意味着我们需要知道N的所有因子（N=pq）。题目泄露出来了一个特殊的参数dp
dp = d % (p-1)尝试将这个参数带入到公钥和私钥满足的方程中：
\[ \begin{aligned} e\cdot\text{dp} &= e\cdot (d+k_1(p-1))\\ &=1+k_2(p-1)(q-1)+k_1e(p-1)\\ &=1+k(p-1) \end{aligned} \]现在，由于\(0 \le \text{dp} < p-1\)，我们知道：
\[ 0\le k = \frac{e\cdot\text{dp}-1}{p-1} < e \]本题中公钥指数\(e\)是一个不大的数字（0x114514 + 1 = 1131797），在0~e的范围内穷举k，对于每个k而言计算对应的p，验证p是不是N的因子即可。
Proof of Concept：
Flag🚩：
Spirit{dp_0r_dq_l3akAg3_1s_dAn6er0us_(s0rt_of)}- Crypto - Long Words 1
附件在此：
源码第三行给了一个Flag🚩长度的提示：
assert len(flag) == 54 # Oh...也就是说，明文m的大小大致为：
\[ 2^{431}=2^{54\times 8-1}\le m < 2^{54\times 8}=2^{432} \]可以求出N的大小大致为
\[ 2^{419} \le N < 2^{420} \]在加解密的过程中m会被模掉N，因此m在超过N的时候会发生改变，但是与改变前的m只相差N的某个整数倍：
\[ m\bmod{N} = m - k\cdot N,\quad 0 < k < 2^{13} \]穷举这个k，直至解出来的字节串开头为Spirit{即可。
Proof of Concept：
- sol_long-words-1.py
（pip install tqdm）
Flag🚩：
Spirit{0verflOwing_oF_iNpu7s_1s_Ov3rf1owIn9_0f_j0y_:p}- Crypto - Essence of The Elders
附件在此：
给了四个密文：
Vyjuru{fubvbjfjm_frqknsv_jsh_
2C602?4:6?E05F==02?50H62<
aHdkTHhBSjFtWFdtTWtXRUJNU0d3Qm5aZVdCNWZlcDV1UWliWGdnaXJiR0Y4Szh0SHRIMTRIa010elkyUzJwMmpDNXg=
nhxalwuhyasen_fxflgzf}分别对应四种不同的古典密码。解密后拼接在一起就是Flag🚩。可以使用CyberChef辅助分析。
对于第一个密文而言，可以尝试Caesar密码和Vigenère密码，由于Flag🚩的开头是Spirit{，可以推断出加密用的密钥：
V - S = 3 = d
y - p = 9 = j
j - i = 1 = b
u - r = 3 = d
r - i = 9 = j
u - t = 1 = b可见加密用的密钥为djb，解密后第一句明文即为
Spirit{classical_ciphers_are_第二句明文中含有:=<?之类的字符（它们在ASCII码表上很接近），注意到ROT47编码后的小写字母中就含有这些字符（23456789:;<=>?@ABCDEFGHIJK），使用ROT47将密文变换一次即可得到第二段明文：
are_ancient_dull_and_weak第三句密文为Base系列的编码套娃，使用CyberChef可以很快地找到每层套娃使用了哪种Base编码——将密文丢进CyberChef中，反复点击Output一栏中的魔术棒，可以发现使用的编码方式依次为Base32、Base85、Base58以及Base64，解码后的第三句明文为
_preceding_the_modern_第四句密文经过了某个随机的单表替换加密，这种加密的严重缺陷就在于密文足够长后，可以通过频率分析来推测出使用的替换表是什么。这里的第四句密文已经很长了，使用quipqiup
cryptographic_systems}Flag🚩：
Spirit{classical_ciphers_are_ancient_dull_and_weak_preceding_the_modern_cryptographic_systems}- Crypto - Secret Shredder 2
附件在此：
根据task.py的第六行，Flag🚩的长度很短，只有62个字节，因此
task.py中泄露出来了dr的值，并且可以通过r = n // N求出r的值，此外，
Proof of Concept：
Flag🚩：
Spirit{wHy_1s_7hIs_s3ntenc3_s0_sh0rt_:P_haaahahhahahahahahaha}- Crypto - Secret Shredder 3
附件在此：
我们的模数N由11个较小的因子组成，使用yafu分解出所有的素因子：
p1 = 1456816928952903451288321
p2 = 1180631507244313172259317
p3 = 3508528846920815938385917
p4 = 874477631144547516656417
p5 = 18142637370007560313
p6 = 9354603989443008841
p7 = 616731256885779378669619
p8 = 10675957053962043419
p9 = 733512956178311394656173
p10 = 1070216324958435392922817
p11 = 659277714257194585234501接下来还需要确定这些因子的顺序，我们不能仅仅凭借yafu来判断p1对应的是p、q、...、y还是z。p~z这十一个因子的比特位数都是确定的，因此我们可以首先按照比特位数来给p1~p11分组，对于每个组内的因子而言，穷举这个组的置换，当所有组的顺序都正确后，解出来的字节串会以Spirit{开头。时间复杂度为
其中\(k_1,\cdots,k_r\)为每个组中因子的数量。在本题中我们只需要进行\(3!\cdot 6!=4320\)次穷举即可，而每次穷举时只需要对所有的密文应用一次中国剩余定理恢复出模N意义下的密文c，接下来只需按照常规的RSA解密步骤进行解密即可。（pad函数将明文填充到100个字节，这样一来m既比N（829比特位）小，又比N的任何一个因子都大）
Proof of Concept：
Flag🚩：
Spirit{Ch1nes3_r3mainder_7HeoRem_1s_A_p0werful_t00l_aNd_a_fUd5mentaL_pr0pertY_1n_nuMb3r_7He0ry_:D}- Crypto - Secret Shredder 4
附件在此：
同一份明文用同样的模数N和三个不同的公钥e1,e2,e3分别加密了三份，也即：
\[ \left\{ \begin{aligned} c_1&\equiv m^{e_1} \pmod{N}\\ c_2&\equiv m^{e_2} \pmod{N}\\ c_3&\equiv m^{e_3} \pmod{N}\\ \end{aligned}\right. \]如果我们能够找到\(s_1,s_2,s_3\)使得
\[ s_1e_1+s_2e_2+s_3e_3=1 \]那么我们就可以恢复出明文\(m\)：
\[ m=m^{s_1e_1+s_2e_2+s_3e_3}\equiv c_1^{s_1}c_2^{s_2}c_3^{s_3}\pmod{N} \]如何求解这三个参数呢？可以先对e1与e2应用扩展欧几里得算法，找到k1、k2使得
\[ k_1e_1+k_2e_2=\text{gcd}(e_1,e_2)=e_{12} \]再找到k3、k4使得
\[ k_3e_{12}+k_4e_3=\text{gcd}(e_{12},e_3)=\text{gcd}(e_1,e_2,e_3) \]于是
\[ \left\{ \begin{aligned} s_1 &= k_1k_3\\ s_2 &= k_2k_3\\ s_3 &= k_4\\ \end{aligned}\right. \]不过不幸的是，本题中\(\text{gcd}(e_1,e_2,e_3)=2\ne 1\)，这也就意味着我们最多只能恢复出\(m_2=m^2\bmod{N}\)：
\[ m^2=m^{s_1e_1+s_2e_2+s_3e_3}\equiv c_1^{s_1}c_2^{s_2}c_3^{s_3}\pmod{N} \] \[ m_2 = m^2 + k\cdot N \]我们知道Flag🚩经过填充后的长度为129字节，也即
\[ \begin{aligned} m &< 2^{129\times 8}=2^{1032}\\ m^2 &< 2^{2064}\\ N &< 2^{2048}\\ \end{aligned} \]因此
\[ k < 2^{16} \]类似地，我们可以像Crypto - Long Words 1那样穷举k来寻找真正的明文m。
Proof of Concept：
- sol_secret-shredder-4.py
（pip install gmpy2）
Flag🚩：
Spirit{eXt3nDed_Eucl1d_s_alg0ri7hm_:)}- Crypto - ⑨チルノのパーフェクトさんすう教室
附件在此：
baka.py中将Flag🚩分成了三份并分别进行了不同的加密，解出这三个问题才能还原原来的Flag🚩。
① 第一个问题给出了Q1_1与Q1_2的结果，它们与第一个RSA加密的因子p1、p2之间满足如下的关系式：
\[ \left\{ \begin{aligned} Q_{11} &= k_1\cdot p_1^{e_1} + k_2\cdot q_1^{e_2}\bmod{N_1}\\ Q_{12} &= k_3\cdot p_1^{e_3} + k_4\cdot q_1^{e_4}\bmod{N_1}\\ \end{aligned}\right. \tag{1}\label{1} \]注意到（Freshman's dream）：
\[ (ap+bq)^k \equiv a^k p^k + b^k q^k \pmod{N},\quad N=pq \]我们可以从\(\eqref{1}\)式中恢复出\(p_1\)与\(q_1\)：
\[ \left\{ \begin{aligned} q_1 &= \text{gcd}(k_3^{e_1}Q_{11}^{e_3}-k_1^{e_3}Q_{12}^{e_1}\bmod{N_1}, N_1)\\ p_1 &= N_1/q_1\\ \end{aligned}\right. \]据此解密第一个RSA密文得到：
Spirit{u_r_a_baka_1n_m4② 第二个问题需要我们求出模数N2。baka.py的83~97行是一个泰勒级数部分和的计算过程，如下：
我们知道：
\[ \begin{aligned} \text{ln}\ \left(\frac{1+x}{1-x}\right) &= \sum\limits_{k=1}^{\infty}\left(\frac{(-1)^{k+1}}{k}x^k+\frac{1}{k}x^k\right)\\ &= \sum\limits_{k=1}^{\infty} \frac{2}{2k-1}x^{2k-1},\qquad \vert x\vert < 1 \end{aligned} \]也即
\[ \text{ln}\ x = \sum\limits_{k=1}^{\infty} \frac{2}{2k-1}\left(\frac{x-1}{x+1}\right)^{2k-1},\qquad x > 0 \]解谜的时候只需要推到这一步就够了（甚至于，随便取几个值代入\(\eqref{2}\)式中，猜出这是一个求自然对数的过程也可以）。我们也可以更进一步地分析一下误差：
\[ \text{ln}\ x = \left[\sum\limits_{k=1}^{n} \frac{2}{2k-1}\left(\frac{x-1}{x+1}\right)^{2k-1}\right] + \left[\sum\limits_{k=n+1}^{\infty} \frac{2}{2k-1}\left(\frac{x-1}{x+1}\right)^{2k-1}\right], \qquad x > 0 \]于是，
\[ \begin{aligned} \text{ln}\ N_2' - Q_2 &< \sum\limits_{k=n+1}^{\infty} \frac{2}{2k-1}\beta^{2k-1}\\ &< \frac{2}{2n+1}\cdot\frac{\beta^{2n+1}}{1-\beta}\\ &< 10^{-1019},\qquad \beta=\frac{2^{2048}/10^{615}-1}{2^{2048}/10^{615}+1},\qquad n=18905 \end{aligned} \]我们计算幂时的绝对误差满足
\[ \begin{aligned} \Delta &< e^{2^{2048}/10^{615}+10^{-1019}} - e^{2^{2048}/10^{615}}\\ &< 10^{-1004} \end{aligned} \]这个粗糙的估计说明我们足以通过输出中的Q2来求出\(N_2'\)：
- （两种方法）
- Python：
N2 = round(Decimal(Q2).exp() * 10**615) - SageMath（安装教程，网页端）：
rr = RealField(10000); N2 = round(exp(rr(Q2)) * 10**615)
⑨ 第三个问题是一个定积分的近似计算过程：
To Be Continued...
