CTF BUUOJ [HDCTF2019]basic rsa 详细解题思路

一、 题目描述

题目来源：[HDCTF2019]basic rsa
题目给出了一个 Python 加密脚本 attachment.py 以及加密后的输出结果。
题目文件内容如下：

import gmpy2
from Crypto.Util.number import *
from binascii import a2b_hex,b2a_hex
flag = "*****************"
p = 262248800182277040650192055439906580479
q = 262854994239322828547925595487519915551
e = 65533
n = p*q
c = pow(int(b2a_hex(flag),16),e,n)
print c
# 27565231154623519221597938803435789010285480123476977081867877272451638645710

二、 题目分析

这是一道非常标准的 RSA 解密题目，考察的是对 RSA 加密算法基本原理的理解以及 Python 相关库的使用。
RSA 算法基础回顾：

1. 公钥与私钥生成：
   • 选择两个大素数 $p$ 和 $q$。
   • 计算模数 $n=p\times q$。
   • 计算欧拉函数 $\varphi (n)=(p-1)\times (q-1)$。
   • 选择公钥指数 $e$，通常为 65537，本题中为 65533。
   • 计算私钥指数 $d$，满足 $e\times d\equiv 1(\mathrm{mod}\varphi (n))$。
2. 加密过程：
   • $c=m^e(\mathrm{mod}n)$
3. 解密过程：
   • $m=c^d(\mathrm{mod}n)$
     本题情况：
     题目直接给出了 $p,q,e$ 和密文 $c$。这意味着我们可以直接计算出 $\varphi (n)$，进而求出私钥 $d$，最后解密得到明文 $m$。
     另外需要注意明文的转换方式：
     代码中使用 int(b2a_hex(flag),16) 将 flag 字符串转为整数。

• b2a_hex(flag)：将字符串转为十六进制字符串（例如 ‘A’ -> ‘41’）。
• int(..., 16)：将十六进制字符串转为整数。
  因此，解密出的整数 $m$ 需要逆向上述过程才能还原为字符串。

三、 解题步骤

1. 计算模数 $n$（虽然解题不一定需要显式计算，但这是 RSA 的基础）。
2. 计算欧拉函数 $\varphi (n)$：$\varphi (n)=(p-1)\times (q-1)$。
3. 计算私钥 $d$：利用 gmpy2.invert(e, phi_n) 求模逆元。
4. 解密求明文 $m$：$m=\text{pow}(c,d,n)$。
5. 还原 Flag：将整数 $m$ 转为十六进制字符串，再转为字节串。

四、 解题脚本

我们可以编写如下 Python 脚本进行解密：

import gmpy2
from binascii import a2b_hex
# 1. 题目给出的已知参数
p = 262248800182277040650192055439906580479
q = 262854994239322828547925595487519915551
e = 65533
c = 27565231154623519221597938803435789010285480123476977081867877272451638645710
# 2. 计算关键参数
n = p * q
phi_n = (p - 1) * (q - 1)
# 3. 求私钥 d
# d 是 e 关于 phi_n 的模逆元
d = gmpy2.invert(e, phi_n)
# 4. 解密
# m = c^d mod n
m = pow(c, int(d), n)
# 5. 将整数转换回字符串
# 题目加密时使用了 b2a_hex，解密时反向操作
# 先将整数转为十六进制字符串
hex_m = hex(m)[2:] # hex(m) 返回 '0x...'
# a2b_hex 要求字符串长度为偶数，如果结果长度为奇数需补 '0'
if len(hex_m) % 2 != 0:
    hex_m = '0' + hex_m
# 将十六进制字符串转为字节串并解码
flag_str = a2b_hex(hex_m).decode('utf-8')
print("解密得到的明文:", flag_str)
print("最终 Flag:", flag_str)

五、 运行结果

运行上述脚本，得到输出如下：

解密得到的明文: flag{B4by_Rs4}
最终 Flag: flag{B4by_Rs4}

六、 总结

这道题主要考查了 RSA 解密的基本流程。当题目给出了素数 $p$ 和 $q$ 时，RSA 算法就没有秘密可言了，直接计算私钥即可破解。同时，在做 Crypto 题时，要注意明文与数字之间的转换方式（如 ASCII 码、十六进制转换等），确保最后还原出的字符串格式正确。
Flag:

flag{B4by_Rs4}