第三届“数信杯”数据安全大赛wp之数据恢复

缘起

先说实话，这道题比赛时没做出来😴

RSA题目一直是我的软肋，一般我都是放到最后去碰运气，这道题也是我第一次遇到，想借这次机会好好学习一下。

这里有2个基本概念，或者说工具、理论，必须先有点认识：

1. SageMath： 是一个强大的开源数学软件系统，支持复杂的数学运算和符号处理

2. Coppersmith攻击： RSA密码分析中一种基于格理论的强大方法，此处省略一万字……
   不过需要记住他适用场景：当p和q位数相近的时候，他能恢复未知低位，具体来说：

a、1024位RSA：可恢复约256位未知低位
b、2048位RSA：可恢复约512位未知低位

题目

某公司截获到密钥文件以及脱敏后的文件，发现密钥文件中的参数存在异常情况，结合密钥文件提供分析，发现可能采用变异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

输出结果：

分析一下这个输出：

一眼而知的：

1. n已知：1024bit
2. 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，可以循环爆破了。

先上代码:

#Sage
n = 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. 1 << hbits，就是1 << 16，就是2的16次方，这是处理2进制数据的习惯，用位移来表示，更易懂
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之数据恢复