2023 宁波天一永安杯 Crypto - rsa 题解：低指数 RSA 特殊构造解密实战

一、题目背景

• 赛事：宁波天一·永安杯 2023
• 题目类型：Crypto（RSA 加密逆向·特殊构造）
• 核心线索：给定公钥 e=65537、模数 n、密文 c 及特殊值 a，需通过非标准 RSA 解密逻辑还原明文
• 目标：还原明文 Flag，格式为 flag{}

二、解题思路与核心分析

1. 题目核心特征

本题并非标准 RSA 解密题，而是基于 RSA 思想的特殊构造加密：

• 题目未直接给出素数 p、q，而是提供了一个关键值 a
• 解密过程不依赖标准 RSA 私钥计算，而是通过模幂运算结合偏移量穷举还原明文
• 核心逻辑：通过 c 与 a 计算出基础值 x，再通过 m = x + k*a（k 为偏移量）穷举得到明文

2. 解题脚本解析

脚本结合 gmpy2 与 PyCryptodome 库，实现特殊构造 RSA 的解密流程：

步骤 1：导入依赖库

• gmpy2.invert：计算模逆元

• Crypto.Util.number.long_to_bytes：将大数转换为字节流

  from gmpy2 import invert
  from Crypto.Util.number import long_to_bytes

步骤 2：定义题目参数

将题目给出的 e、n、c、a 代入脚本：

# 题目给定参数
e = 65537
n = 36535558847082719901201561031181835346574576610950713924924272947759193576365817762980927638691696601293089537315055413746788190208875234794229119049056299551864869870291634941246362436491006904347559559494705922259007299126640817275929491680601926404543198957206717290905220235571289759182878331893962038379
c = 532997872940452282189043430008002793694788439822465302532208754231005799057972378308576109082463996551992533174546386979606697890310597738637156771564229
a = 2694858406312563434474553988904403597551484373358339092528913028454100111881368126493990657117571672510331411186745639563619323775673115439

步骤 3：计算基础解密值 x

通过模逆与模幂运算，基于 a 计算出基础解密值 x：

# 计算模逆元 d，对应 e 在模 (a-1) 下的逆
d = invert(e, a-1)
# 计算 x = c^d mod a
x = pow(c, d, a)

步骤 4：穷举偏移量还原明文

由于明文 m 满足 m ≡ x (mod a)，即 m = x + k*a（k 为非负整数），通过穷举 k 并验证解码结果，找到符合 flag{} 格式的明文：

# 穷举偏移量 k，范围 0-19
for k in range(20):
    m = x + k * a
    try:
        # 将大数转换为字节流并解码为 UTF-8 字符串
        flag = long_to_bytes(m).decode('utf-8')
        # 验证是否为题目要求的 flag 格式
        if flag.startswith('flag{') and flag.endswith('}'):
            print(flag)
            break
    except:
        continue

三、解题结果

脚本运行后，在 k=1 附近穷举得到符合格式的明文：

flag{p01la4d_rHo_a1gOr1thM_r1gh4}

四、核心知识点总结

1. 特殊构造 RSA 解密思路

本题并非标准 RSA 解密，而是利用模运算的周期性构造的特殊加密：

• 明文 m 满足 m ≡ x (mod a)，因此 m 是 x 加上 a 的整数倍
• 穷举 k 时，由于 Flag 长度固定，k 通常为较小的非负整数（本题 k 在 0-20 范围内即可命中）

2. 大数转字符串避坑

• 使用 long_to_bytes(m).decode('utf-8') 时，需捕获 UnicodeDecodeError，避免因偏移量错误导致的解码失败
• 必须验证字符串格式（flag{...}），防止误判非明文的解码结果

3. 常见特殊 RSA 变种

五、完整运行脚本

from gmpy2 import invert
from Crypto.Util.number import long_to_bytes

# 题目给定参数
e = 65537
n = 36535558847082719901201561031181835346574576610950713924924272947759193576365817762980927638691696601293089537315055413746788190208875234794229119049056299551864869870291634941246362436491006904347559559494705922259007299126640817275929491680601926404543198957206717290905220235571289759182878331893962038379
c = 532997872940452282189043430008002793694788439822465302532208754231005799057972378308576109082463996551992533174546386979606697890310597738637156771564229
a = 2694858406312563434474553988904403597551484373358339092528913028454100111881368126493990657117571672510331411186745639563619323775673115439

# 计算模逆元 d
d = invert(e, a-1)
# 计算基础解密值 x
x = pow(c, d, a)

# 穷举偏移量 k 还原明文
for k in range(20):
    m = x + k * a
    try:
        flag = long_to_bytes(m).decode('utf-8')
        if flag.startswith('flag{') and flag.endswith('}'):
            print(f"Flag: {flag}")
            break
    except:
        continue