MoeCTF 2024 WriteUp Crypto方向（详细）

MoeCTF2024 WriteUP

CTFerName:fifker
题目链接：https://ctf.xidian.edu.cn/training/10
文章内容有些是大一刚学习的时候写的，有些是后来补写的，没有仔细核验校改。如果出现有误或者语言风格不统一请见谅！

Crypto

现代密码学入门指北

题目如下：

from Crypto.Util.number import bytes_to_long, getPrime
from secret import flag
p = getPrime(128)
q = getPrime(128)
n = p*q
e = 65537
m = bytes_to_long(flag)
c = pow(m, e, n)
print(f"n = {n}")
print(f"p = {p}")
print(f"q = {q}")
print(f"c = {c}")
'''
n = 40600296529065757616876034307502386207424439675894291036278463517602256790833
p = 197380555956482914197022424175976066223
q = 205695522197318297682903544013139543071
c = 36450632910287169149899281952743051320560762944710752155402435752196566406306

很基础的题目，相当于是教你如何认识RSA算法了。

RSA基础知识

RSA是一种非对称加密算法，由Ron Rivest、Adi Shamir和Leonard Adleman在1977年提出。它基于一个简单的数论事实：将两个大素数相乘很容易，但将其乘积分解为两个素数却极其困难。

首先我们来看看密钥生成过程：

1. 选择两个大素数

随机选择两个不同的大素数 $p$ 和 $q$。

1. 计算模数 $n$

$$n = p \cdot q$$

$n$ 的长度（位数）就是RSA密钥的长度，通常为1024、2048或4096位。

1. 计算欧拉函数 $\varphi(n)$

$$\varphi(n) = (p - 1) \cdot (q - 1) = p \cdot q - (p + q) + 1$$

$\varphi(n)$ 表示小于 $n$ 且与 $n$ 互质的正整数个数。

1. 选择公钥指数 $e$

选择整数 $e$，满足：

$$1 < e < \varphi(n), \qquad \gcd(e, \varphi(n)) = 1$$

其中 $\gcd$ 表示最大公约数，即 $e$ 与 $\varphi(n)$ 互质。

常用值：$e = 65537$（因为它是素数且二进制中只有两个1，加密速度快）

1. 计算私钥指数 $d$

计算 $d$，使得：

$$d \cdot e \equiv 1 \pmod{\varphi(n)}$$

即 $d$ 是 $e$ 关于 $\varphi(n)$ 的模逆元。

1. 生成密钥对

其中：

$$\text{公钥} = (e, n), \qquad \text{私钥} = (d, n)$$

公钥可以公开，而私钥必须保密。

然后就是RSA的加密公式：

将明文 $m$（必须是小于 $n$ 的整数）加密为密文 $c$：

$$c = m^e \bmod n$$

加密步骤如下：

1. 将明文转换为整数 $m$（通常使用字节转整数的函数，如 bytes_to_long）
2. 确保 $0 \leq m < n$
3. 计算 $c = m^e \bmod n$
4. 得到密文 $c$

那么，与加密相反，解密公式就是使用私钥 $(d, n)$ 解密密文 $c$ 得到明文 $m$：

$$m = c^d \bmod n$$

解密步骤如下：

1. 获取密文 $c$
2. 使用私钥 $d$ 计算 $m = c^d \bmod n$
3. 将整数 $m$ 转换为字节，再解码为字符串

本题

回归本题：题目直接把 $n$、$p$、$q$、$e$ 都给我们了。

基于上面的知识，我们可以直接算出：

$$\varphi(n) = (p - 1) \cdot (q - 1) = p \cdot q - (p + q) + 1$$

进一步通过 $e$ 把私钥 $d$ 算出来。

最后通过公式：

$$m = c^d \bmod n$$

求出 $m$，最后通过 long_to_bytes 获得 flag。

解题脚本如下：

from Crypto.Util.number import*

n = 40600296529065757616876034307502386207424439675894291036278463517602256790833
p = 197380555956482914197022424175976066223
q = 205695522197318297682903544013139543071
c = 36450632910287169149899281952743051320560762944710752155402435752196566406306

phi_n = (p - 1) * (q - 1)

d = pow(65537, -1, phi_n)

m = pow(c, d, n)

print(long_to_bytes(m))

Signin

题目如下：

from Crypto.Util.number import*
from secret import flag


m = bytes_to_long(flag)
p = getPrime(1024)
q = getPrime(1024)
n = p*q
e = 65537
c = pow(m,e,n)
pq = (p-1)*(q-2)
qp = (q-1)*(p-2)
p_q = p + q


print(f"{c = }")
print(f"{pq = }")
print(f"{qp = }")
print(f"{n = }")
print(f"{p_q = }")
'''
c = 5654386228732582062836480859915557858019553457231956237167652323191768422394980061906028416785155458721240012614551996577092521454960121688179565370052222983096211611352630963027300416387011219744891121506834201808533675072141450111382372702075488292867077512403293072053681315714857246273046785264966933854754543533442866929316042885151966997466549713023923528666038905359773392516627983694351534177829247262148749867874156066768643169675380054673701641774814655290118723774060082161615682005335103074445205806731112430609256580951996554318845128022415956933291151825345962528562570998777860222407032989708801549746
pq = 18047017539289114275195019384090026530425758236625347121394903879980914618669633902668100353788910470141976640337675700570573127020693081175961988571621759711122062452192526924744760561788625702044632350319245961013430665853071569777307047934247268954386678746085438134169871118814865536503043639618655569687154230787854196153067547938936776488741864214499155892870610823979739278296501074632962069426593691194105670021035337609896886690049677222778251559566664735419100459953672218523709852732976706321086266274840999100037702428847290063111455101343033924136386513077951516363739936487970952511422443500922412450462
qp = 18047017539289114275195019384090026530425758236625347121394903879980914618669633902668100353788910470141976640337675700570573127020693081175961988571621759711122062452192526924744760561788625702044632350319245961013430665853071569777307047934247268954386678746085438134169871118814865536503043639618655569687077087914198877794354459669808240133383828356379423767736753506794441545506312066344576298453957064590180141648690226266236642320508613544047037110363523129966437840660693885863331837516125853621802358973786440314619135781324447765480391038912783714312479080029167695447650048419230865326299964671353746764860
n = 18047017539289114275195019384090026530425758236625347121394903879980914618669633902668100353788910470141976640337675700570573127020693081175961988571621759711122062452192526924744760561788625702044632350319245961013430665853071569777307047934247268954386678746085438134169871118814865536503043639618655569687534959910892789661065614807265825078942931717855566686073463382398417205648946713373617006449901977718981043020664616841303517708207413215548110294271101267236070252015782044263961319221848136717220979435486850254298686692230935985442120369913666939804135884857831857184001072678312992442792825575636200505903
p_q = 279533706577501791569740668595544511920056954944184570513187478007551195831693428589898548339751066551225424790534556602157835468618845221423643972870671556362200734472399328046960316064864571163851111207448753697980178391430044714097464866523838747053135392202848167518870720149808055682621080992998747265496
'''

看得出就是一道正常的RSA加密，相比于上文也就是没有直接把 $p$、$q$ 给你。

但是关于RSA的解密只需要计算 $\varphi(n)$ 就行了：

$$\varphi(n) = (p - 1) \cdot (q - 1) = p \cdot q - (p + q) + 1$$

题目给出了 p_q，且它的值正好是 $p + q$。又因为 $n = p \cdot q$，所以：

$$\varphi(n) = n - (p + q) + 1 = n - \texttt{p\_q} + 1$$

剩下的步骤与前一题相同，计算私钥指数 $d$ 后即可解密得到 flag。

解题脚本如下：

from Crypto.Util.number import*

c = 5654386228732582062836480859915557858019553457231956237167652323191768422394980061906028416785155458721240012614551996577092521454960121688179565370052222983096211611352630963027300416387011219744891121506834201808533675072141450111382372702075488292867077512403293072053681315714857246273046785264966933854754543533442866929316042885151966997466549713023923528666038905359773392516627983694351534177829247262148749867874156066768643169675380054673701641774814655290118723774060082161615682005335103074445205806731112430609256580951996554318845128022415956933291151825345962528562570998777860222407032989708801549746
n = 18047017539289114275195019384090026530425758236625347121394903879980914618669633902668100353788910470141976640337675700570573127020693081175961988571621759711122062452192526924744760561788625702044632350319245961013430665853071569777307047934247268954386678746085438134169871118814865536503043639618655569687534959910892789661065614807265825078942931717855566686073463382398417205648946713373617006449901977718981043020664616841303517708207413215548110294271101267236070252015782044263961319221848136717220979435486850254298686692230935985442120369913666939804135884857831857184001072678312992442792825575636200505903
p_q = 279533706577501791569740668595544511920056954944184570513187478007551195831693428589898548339751066551225424790534556602157835468618845221423643972870671556362200734472399328046960316064864571163851111207448753697980178391430044714097464866523838747053135392202848167518870720149808055682621080992998747265496

phi_n = n - p_q + 1

d = pow(65537, -1, phi_n)

m = pow(c, d, n)

print(long_to_bytes(m))

Big and small

题目如下：

from secret import flag
from Crypto.Util.number import*
m = long_to_bytes(flag)
p = getPrime(1024)
q = getPrime(1024)
n = p*q
e = 3
c = pow(m,e,n)
'''
c = 150409620528288093947185249913242033500530715593845912018225648212915478065982806112747164334970339684262757
e = 3
n = 20279309983698966932589436610174513524888616098014944133902125993694471293062261713076591251054086174169670848598415548609375570643330808663804049384020949389856831520202461767497906977295453545771698220639545101966866003886108320987081153619862170206953817850993602202650467676163476075276351519648193219850062278314841385459627485588891326899019745457679891867632849975694274064320723175687748633644074614068978098629566677125696150343248924059801632081514235975357906763251498042129457546586971828204136347260818828746304688911632041538714834683709493303900837361850396599138626509382069186433843547745480160634787
'''

这道题很特别，只给出了 $n$，而没有给出任何与 $p$、$q$ 相关的信息。前面在 RSA 基础中提到，RSA 正是基于“大素数分解困难”这一事实提出的，因此不考虑从 $n$ 中分解出 $p$ 和 $q$，再进一步计算私钥 $d$。

但是有一个特殊点值得关注：$e = 3$（前面两道题均取 $e = 2^{16} + 1 = 65537$）。前面我们知道 RSA 加密满足：

$$c \equiv m^e \pmod n$$

由于 $e$ 很小，我们不一定需要计算私钥 $d$；将 $e = 3$ 代入后，可以尝试直接恢复明文，这就是经典的低加密指数攻击。

当 $m^e > n$ 时，由同余式可知存在整数 $k$，使得：

$$m^e = k \cdot n + c, \qquad k \in \mathbb{Z}_{\geq 1}$$

因此可以不断提高 $k$ 的上限，暴力枚举 $k$ 并尝试求解。

解题脚本：

from Crypto.Util.number import*
import gmpy2

c = 150409620528288093947185249913242033500530715593845912018225648212915478065982806112747164334970339684262757
e = 3
n = 20279309983698966932589436610174513524888616098014944133902125993694471293062261713076591251054086174169670848598415548609375570643330808663804049384020949389856831520202461767497906977295453545771698220639545101966866003886108320987081153619862170206953817850993602202650467676163476075276351519648193219850062278314841385459627485588891326899019745457679891867632849975694274064320723175687748633644074614068978098629566677125696150343248924059801632081514235975357906763251498042129457546586971828204136347260818828746304688911632041538714834683709493303900837361850396599138626509382069186433843547745480160634787

for k in range(1, 100000000):
    i = (k * n) + c
    m, exact = gmpy2.iroot(i, e)
    if exact == True:
        print(long_to_bytes(m))
        break
else:
    print("k too small")

但是，上述脚本中，$k$ 取到 $99999999$ 都没有找到合适的结果，此时脚本的运行时间已经变得不再合理。

那我们就不由得可以想到，会不会是另一种更简单的情况呢？

如果 $m^e < n$ 呢？此时是否有：

$$c = m^e \bmod n = m^e$$

那么可以直接对 $c$ 求立方根恢复明文：

$$m = \sqrt[3]{c}$$

解题脚本：

from Crypto.Util.number import*

c = 150409620528288093947185249913242033500530715593845912018225648212915478065982806112747164334970339684262757
e = 3

m = c ** (1 / e)

if m ** e == c:
    print(long_to_bytes(m))
else:
    print("Nope.")

没有结果？为什么？思路错了吗？

我们的思路是直接对 $c$ 开三次方根，但是浮点数只能精确表示约 $15$ 至 $17$ 位十进制数字，而本题的 $c$ 有 $100+$ 位，这就是二进制浮点数的局限性：

计算机使用 IEEE 754 双精度浮点数（64位）表示小数：

符号位(1位) | 指数位(11位) | 尾数位(52位)

尾数部分虽然存储 $52$ 位，但加上隐含的最高有效位后，双精度浮点数共有 $53$ 位有效精度；它能精确表示的整数最大为：

$$2^{53} \approx 9 \times 10^{15}$$

超过这个范围，整数会被四舍五入到最近的浮点数。但是很显然，本题的 $c$ 远大于这个数字。

那怎么办呢？我们依然使用上文 $m^e > n$ 时用到的 gmpy2.iroot()。该函数使用整数运算计算 $k$ 次方根，全程不会产生精度损失（详细方法不再赘述，读者可以自行搜索了解）。

解题脚本：

from Crypto.Util.number import*
import gmpy2

c = 150409620528288093947185249913242033500530715593845912018225648212915478065982806112747164334970339684262757
e = 3
n = 20279309983698966932589436610174513524888616098014944133902125993694471293062261713076591251054086174169670848598415548609375570643330808663804049384020949389856831520202461767497906977295453545771698220639545101966866003886108320987081153619862170206953817850993602202650467676163476075276351519648193219850062278314841385459627485588891326899019745457679891867632849975694274064320723175687748633644074614068978098629566677125696150343248924059801632081514235975357906763251498042129457546586971828204136347260818828746304688911632041538714834683709493303900837361850396599138626509382069186433843547745480160634787

m, exact = gmpy2.iroot(c, e)
if exact == True:
    print(long_to_bytes(m))
else:
    print("Nope.")

获得flag：

flag{xt>is>s>b}

批评出题人把moectf和其他比赛弄混了，flag不是moectf开头。

补充解法：

不依赖 gmpy2 时，也可以使用二分查找实现整数三次开方：

def integer_cube_root(n: int) -> int:
    """Return the floor of the cube root of *n* using binary search."""
    if n < 0:
        raise ValueError("n must be non-negative")

    low, high = 0, n + 1
    while low < high:
        mid = (low + high) // 2
        if mid**3 <= n:
            low = mid + 1
        else:
            high = mid
    return low - 1


root = integer_cube_root(c)
if root**3 != c:
    raise ValueError("c is not an exact cube")

b = root.to_bytes((root.bit_length() + 7) // 8, "big")
print(b.decode("utf-8"))

这段代码使用的就是二分查找法。它并非在有序数组中查找某个固定元素，而是在单调递增函数 $f(x) = x^3$ 的定义域中，查找满足条件的最大整数。目标是求出：

$$r = \max \left\{x \in \mathbb{Z}_{\geq 0} \mid x^3 \leq n\right\} = \left\lfloor \sqrt[3]{n} \right\rfloor$$

由于 $x^3$ 在非负整数范围内单调递增，任意中点 $\mathrm{mid}$ 只有两种情况：

$$\mathrm{mid}^3 \leq n$$

说明 $\mathrm{mid}$ 及其左侧都满足条件，答案只可能在 $\mathrm{mid}$ 或其右侧，因此将 low 更新为 mid + 1；反之，若：

$$\mathrm{mid}^3 > n$$

则 $\mathrm{mid}$ 及其右侧均不可能是答案，故将 high 更新为 mid。循环始终维持以下边界：

$$\forall x < \mathrm{low},\ x^3 \leq n, \qquad \forall x \geq \mathrm{high},\ x^3 > n$$

循环结束时，low = high，两者指向第一个不满足 $x^3 \leq n$ 的整数，因此 low - 1 正好是向下取整的整数立方根。

本题已经满足 $c = m^3$，所以 integer_cube_root(c) 恰好恢复 $m$。额外的 root**3 != c 判断用于验证 $c$ 是否为精确立方数；若条件不成立，函数返回的只是向下取整的立方根，不能直接当作明文。最后使用 to_bytes() 将整数 $m$ 还原为字节串，再使用 UTF-8 解码得到 flag。

ez_hash

baby_equation

More_secure_RSA

ezlegendre

大白兔

new_system

RSA_revenge

EzMatrix

EzPack

One more bit

ezLCG

babe-Lifting

hidden-poly