2023 宁波天一永安杯 Crypto - secret 题解：RSA 隐式指数与高次根求解实战

一、题目背景

• 赛事：宁波天一·永安杯 2023
• 题目类型：Crypto（RSA 加密破解）
• 核心线索：给定大素数 p、q，密文 c，公钥指数 e=28，但实际解密需修正指数并通过高次根求解
• 目标：还原明文 Flag，格式为 flag{}

二、解题思路与核心分析

1. 题目核心特征

本题是典型的 RSA 加密逆向题目，但存在两个关键陷阱：

1. 给定的公钥指数 e=28 并非实际解密指数，需通过数学推导还原真实加密/解密逻辑
2. 解密后得到的明文并非直接字符串，而是经过 4 次幂运算后的数值，需对大数进行精确高次根求解

2. 关键数学原理

RSA 加密核心公式：

• 加密：$c = m^e \pmod{n}$
• 解密：$m = c^d \pmod{n}$（其中 $d = e^{-1} \pmod{\phi(n)}$，$\phi(n) = (p-1)(q-1)$）

本题特殊点：

• 计算发现使用 e=28 求解的 d 无法直接得到明文，实际加密指数为 7（脚本中验证的关键参数）
• 明文 m 经过 $m = \text{flag}^4$ 运算后再进行 RSA 加密，因此解密后需对结果求 4 次根还原 Flag

3. 解题脚本解析

我们使用 Python 结合 gmpy2 库完成大数运算与高次根求解，核心步骤如下：

步骤 1：导入依赖库

gmpy2 是处理大数运算的核心库，提供了模逆运算、高次根求解等高效函数：

from gmpy2 import invert, iroot

步骤 2：定义已知参数

将题目给出的 p、q、n、c 及修正后的指数 e=7 代入：

# 已知大素数 p, q
p = 134261118796789547851478407090640074022214132682000430136383795981942884853000826171189906102866323044078348933419038543719361923320694974970600426450755845839235949167391987970330836004768360774676424958554946699767582105556239177450470656065560178592346659948800891455240736405480828554486592172443394370831
q = 147847444534152128997546931602292266094740889347154192420554904651813340915744328104100065373294346723964356736436709934871741161328286944150242733445542228293036404657556168844723521815836689387184856871091025434896710605688594847400051686361372872763001355411405782508020591933546964183881743133374126947753
# 模数 n
n = 19850163314401552502654477751795889962324360064924594948231168092741951675262933573691070993863763290962945190372400262526595224437463969238332927564085237271719298626877917792595603744433881409963046292095205686879015029586659384866719514948181682427744555313382838805740723664050846950001916332631397606277703888492927635867870538709596993987439225247816137975156657119509372023083507772730332482775258444611462771095896380644997011341265021719189098262072756342069189262188127428079017418048118345180074280858160934483114966968365184788420091050939327341754449300121493187658865378182447547202838325648863844192743
# 密文 c
c = 13913396366755010607043477552577268277928241319101215381662331498046080625902831202486646020767568921881185124894960242867254162927605416228460108399087406989258037017639619195506711090012877454131383568832750606102901110782045529267940504471322847364808094790662696785470594892244716137203781890284216874035486302506042263453255580475380742959201314003788553692977914357996982118328587119124144181290753389394149235381045389696841471483947310663329993873046123134587149661347999774958105091103806375702387084149309542351541021140111048408248121408401601979108510758891595550054699719801708646232427198902271953673874
# 修正后的加密指数 e
e = 7

步骤 3：计算私钥 d

通过模逆运算计算 $d = e^{-1} \pmod{\phi(n)}$，其中 $\phi(n) = (p-1)(q-1)$：

# 计算欧拉函数 phi(n)
phi = (p - 1) * (q - 1)
# 计算私钥 d
d = invert(e, phi)

步骤 4：解密得到中间值 m

通过模幂运算还原 $m = c^d \pmod{n}$：

# 解密得到 m = flag^4
m = pow(c, d, n)

步骤 5：高次根求解还原 Flag

由于 $m = \text{flag}^4$，需使用 iroot 函数对 m 求精确 4 次根：

# 对 m 开 4 次方根，exact 表示是否为精确根
flag_num, exact = iroot(m, 4)

if exact:
    # 将数字转换为字节流再解码为 UTF-8 字符串
    try:
        # 计算字节长度并转换为大端序字节
        flag_bytes = flag_num.to_bytes((flag_num.bit_length() + 7) // 8, 'big')
        flag = flag_bytes.decode('utf-8')
        print(f"Flag: {flag}")
    except Exception as ex:
        print(f"解码失败: {ex}")
        print(f"Flag 数值: {flag_num}")
else:
    print("未找到精确的 4 次根。")
    print(f"m = {m}")
    print(f"iroot(m, 4) = {iroot(m, 4)}")

三、解题结果

脚本运行后，成功求解出精确 4 次根，最终得到 Flag：

Flag: flag{cfc48290383943a2cbf3c2d70db44690}

四、核心知识点总结

1. RSA 解密关键避坑

• 指数修正：题目给出的 e=28 为干扰项，需通过数学验证确定真实加密指数（本题为 7）
• 大数运算：处理超过 Python 原生整数范围的大数时，必须使用 gmpy2 库，避免运算溢出或效率低下

2. 高次根求解原理

• 当明文经过 $k$ 次幂运算后再加密，解密后需对结果求 $k$ 次根
• gmpy2.iroot(x, n) 函数返回元组 (root, exact)，其中 exact 为布尔值表示是否为精确根，必须验证精确性，否则会得到错误结果

3. 数字转字符串规范

• 使用 int.to_bytes(length, byteorder, signed=False) 将大数转换为字节流
• 固定使用 byteorder='big'（大端序），符合 CTF 题目通用编码规范
• 解码时需捕获 UnicodeDecodeError，避免因编码格式错误导致脚本崩溃

五、完整运行脚本

from gmpy2 import invert, iroot

# 已知参数
p = 134261118796789547851478407090640074022214132682000430136383795981942884853000826171189906102866323044078348933419038543719361923320694974970600426450755845839235949167391987970330836004768360774676424958554946699767582105556239177450470656065560178592346659948800891455240736405480828554486592172443394370831
q = 147847444534152128997546931602292266094740889347154192420554904651813340915744328104100065373294346723964356736436709934871741161328286944150242733445542228293036404657556168844723521815836689387184856871091025434896710605688594847400051686361372872763001355411405782508020591933546964183881743133374126947753
n = 19850163314401552502654477751795889962324360064924594948231168092741951675262933573691070993863763290962945190372400262526595224437463969238332927564085237271719298626877917792595603744433881409963046292095205686879015029586659384866719514948181682427744555313382838805740723664050846950001916332631397606277703888492927635867870538709596993987439225247816137975156657119509372023083507772730332482775258444611462771095896380644997011341265021719189098262072756342069189262188127428079017418048118345180074280858160934483114966968365184788420091050939327341754449300121493187658865378182447547202838325648863844192743
c = 13913396366755010607043477552577268277928241319101215381662331498046080625902831202486646020767568921881185124894960242867254162927605416228460108399087406989258037017639619195506711090012877454131383568832750606102901110782045529267940504471322847364808094790662696785470594892244716137203781890284216874035486302506042263453255580475380742959201314003788553692977914357996982118328587119124144181290753389394149235381045389696841471483947310663329993873046123134587149661347999774958105091103806375702387084149309542351541021140111048408248121408401601979108510758891595550054699719801708646232427198902271953673874

# 使用 e = 7（不是 28！）
e = 7

# 计算私钥 d
phi = (p - 1) * (q - 1)
d = invert(e, phi)

# 解密得到 m = flag^4
m = pow(c, d, n)

# 对 m 开 4 次方根得到 flag
flag_num, exact = iroot(m, 4)

if exact:
    # 将数字转换为字符串
    try:
        flag_bytes = flag_num.to_bytes((flag_num.bit_length() + 7) // 8, 'big')
        flag = flag_bytes.decode('utf-8')
        print(f"Flag: {flag}")
    except Exception as ex:
        print(f"Decoding failed: {ex}")
        print(f"Flag number: {flag_num}")
else:
    print("Failed to find exact 4th root.")
    print(f"m = {m}")
    print(f"iroot(m, 4) = {iroot(m, 4)}")
---