文章总结： 文档记录了作者在第三届数信杯数据安全大赛中解决数据恢复题目的过程。通过分析损坏的RSA密钥文件，发现p的高16位和低48位未知，利用SageMath工具实施Coppersmith攻击成功恢复密钥，并使用OAEP填充解密CSV文件中的加密数据，最终找到指定手机号对应的身份证号和银行卡号。文章提供了完整的攻击代码和解题思路。
综合评分： 87
文章分类： 漏洞分析,CTF,WEB安全,安全工具,实战经验
第三届“数信杯”数据安全大赛wp之数据恢复
原创
一只岸上的鱼 一只岸上的鱼
一只岸上的鱼
2026年4月2日 08:08 江苏
缘起
先说实话，这道题比赛时没做出来😴
RSA题目一直是我的软肋，一般我都是放到最后去碰运气，这道题型也是我第一次遇到，想借这次机会好好学习一下。
这里有2个基本概念，或者说工具、理论，必须先有点认识：
-
SageMath：
是一个强大的开源数学软件系统，支持复杂的数学运算和符号处理
-
Coppersmith攻击：
RSA密码分析中一种基于格理论的强大方法，此处省略一万字…… 不过需要记住他适用场景：当p和q位数相近的时候，他能恢复未知低位，具体来说：
a、1024位RSA：可恢复约256位未知低位 b、2048位RSA：可恢复约512位未知低位
题目
ounter(line某公司截获到密钥文件以及脱敏后的文件，发现密钥文件中的参数存在异常情况，结合密钥文件提供分析，发现可能采用变异RSA算法针对重要文件进行脱敏处理。请结合提供附件内容，进行分析并脱敏恢复，找到PhoneNumber为17962732783对应的id、IndentificationCard、BankCard，并以_进行连接并提交。如id为1，IndentificationCard为2345，BankCard为6789，最终提交1_2345_6789。
题目附件我放在了网盘：
https://cloud.189.cn/t/feMNZbi2qiqa（访问码：cai0）
里面有2个文件：
思路
先看看这个所谓的损坏的密钥，什么样：
openssl pkey -in key_pri.pem -text
输出结果：
分析一下这个输出：
一眼而知的：
- n已知：1024bit
- e已知道：65537 (0x10001)
然后把p和q拷贝出来，删除冒号后比较一下：
可以看到q有512bit，根据n为1024bit分析可知，p应该也是512bit，但是看起来少了16bit，这个应该是高位，p的尾巴的0是丢失的部分，应该是有48位低位未知。
总结为：
3-1. p为512bit 3-2. p的高16bit未知 3-3. p的中间448bit已知 3-4. p的低位48bit未知
根据Coppersmith攻击的条件，512位只有低位48位未知，是可以利用的，至于高位的16bit，可以循环爆破了。
先上代码:
#Sagen = Integer(0xa37afdb7661804f4719e095d4f1717f531cb380155f4929da65c8a449165edad0fc9c2db2ad7bd924251f1694100c10f9bb4fedd37bf6a6b4bf410cad1b15eb6a3b1015b0b3bbbae6d4e4ed914d9721f9cc8c8640afb3a35bc30b16194d0cc4e7107e4cea6526fe17aa06bdbc9fb1e6d47fe5902005136d9b705c784d2011db9)p_known = Integer(0x9d025160d56d4971363f3cf2ce7e3e96215c50bf50d0cc606f5645de7ec113d16d931383e649bc2c7328499d219e2982b726ae41c5370aa8)pbits = 512 # p的位数hbits = 16 # 未知16位高位lbits = 48 # 未知48位低位
# Coppersmith攻击PR.<lp> = PolynomialRing(Zmod(n))for hp in range(1 << hbits,1,-1): # 给点动静：输出爆破的进度 if hp % 1000 == 0: print(hp," of ", 1 << hbits)
test_p = (Integer(hp) << (512-16)) + (p_known << 48) + lp # X=2^50：指定根的上界（即 lp 的最大可能值），这里设为 2^50（略大于 48 位的 2^48，覆盖所有可能的低位值） # beta=0.45：格基约减的参数（经验值），beta 越小，格约减越严格，成功率越高但速度越慢；通常取 0.4~0.5 roots = test_p.small_roots(X=2^50, beta=0.45) if roots: p = (Integer(hp) << (512-16)) + (p_known << 48) + Integer(roots[0]) q = n // p print("====== 成功 !!! ======") print(f'n: {n}') print(f'p: {p}') print(f'q: {q}') break
先跑一下看结果：
再来做个简单的解释：
- 1 << hbits，就是1 << 16，就是2的16次方，这是处理2进制数据的习惯，用位移来表示，更易懂
- PR.= PolynomialRing(Zmod(n))
Zmod(n)：模 n 的整数环（即所有整数对 n 取模后的集合）。PolynomialRing(Zmod(n))：在模 n 的整数环上构造多项式环。PR.<lp>：给多项式环命名为PR，并指定不定元为lp（low part，代表 p 的未知低位）。作用：为后续构造 “以 p 的未知低位为根的多项式” 做准备。
这部分涉及到一些数学的知识，三言两语也说不清，记住Coppersmith攻击的适用条件和使用方法就够啦！
题目中“变异RSA算法”：
先补充一点rsa的基础知识：
RSA 原生算法不安全，必须给明文加一段随机数据，这个过程叫填充。
不加填充 = 容易被破解 加填充 = 安全
PKCS#1 和 OAEP 就是两种最主流的填充标准。
俩填充的区别：
PKCS#1 v1.5：老版本、简单、兼容性好、有安全风险 OAEP：新版本、复杂、更安全、现代标准推荐
上关键代码：
# 构建私钥def build_rsa_key(): from Crypto.PublicKey import RSA phi = (p - 1) * (q - 1) d = pow(e, -1, phi) key = RSA.construct((n, e, d, p, q)) return key
# 使用oaep填充解密def decrypt_oaep(key, ct: bytes) -> Optional[Tuple[bytes, str]]: from Crypto.Cipher import PKCS1_OAEP from Crypto.Hash import SHA1, SHA256 #先猜2个
for name, H in (('SHA1', SHA1), ('SHA256', SHA256)): try: cipher = PKCS1_OAEP.new(key, hashAlgo=H) pt = cipher.decrypt(ct) return pt, name except Exception: continue return None
不用怀疑，这2个方法是这么来的：
剩下的就是读取csv文件，解密而已：
key = build_rsa_key()with open('encrypted_users.csv', 'r', encoding='utf-8') as f: reader = csv.reader(f) next(reader) for row_num, row in enumerate(reader, start=2): pt, alg = decrypt_oaep(key, base64.b64decode(row[2].strip())) #PhoneNumber if pt==b'17962732783': #找到这个手机号，再解密其他信息 pt1, alg1 = decrypt_oaep(key, base64.b64decode(row[3].strip())) # IndentificationCard pt2, alg2 = decrypt_oaep(key, base64.b64decode(row[4].strip())) # BankCard print(f"id：{row[0]}，name：{row[1]}，PhoneNumber：{pt},IndentificationCard:{pt1},BankCard:{pt2}") break;
看一下执行结果：
万事大吉！
补充知识
sagemath，如果不想安装，可以使用官方的docker镜像，我使用的就是：
docker run -d -p 8888:8888 --name sage sagemath/sagemath:latest sage-jupyter
小结
RSA题目始终是自己的软肋，鼓起勇气一题一题的积累，等再积累一些，就可以去学一下RSA的基础理论，数学知识，以期可以举一反三。
免责声明：
本文所载程序、技术方法仅面向合法合规的安全研究与教学场景，旨在提升网络安全防护能力，具有明确的技术研究属性。
任何单位或个人未经授权，将本文内容用于攻击、破坏等非法用途的，由此引发的全部法律责任、民事赔偿及连带责任，均由行为人独立承担，本站不承担任何连带责任。
本站内容均为技术交流与知识分享目的发布，若存在版权侵权或其他异议，请通过邮件联系处理，具体联系方式可点击页面上方的联系我。
本文转载自：一只岸上的鱼 一只岸上的鱼 一只岸上的鱼《第三届“数信杯”数据安全大赛wp之数据恢复》
版权声明
本站仅做备份收录，仅供研究与教学参考之用。
读者将信息用于其他用途的，全部法律及连带责任由读者自行承担，本站不承担任何责任。
评论