简单的rsa（攻防世界）

发表于 更新于 分类于 阅读次数：

简单的rsa（攻防世界）

7634d7960e85494bb9ae648ea871f085.py

题目分析

这是一个基于RSA加密系统的密码题目，主要特点如下：

  1. 首先生成标准的RSA参数（p, q, n, e, d）
  2. 然后对原始素数p和q进行”破坏”处理
  3. 使用破坏后的新素数生成新的RSA模数进行加密

关键代码分析

1
2
3
4
5
6
def destory(x, num):
    while True:
        dt = getRandomNBitInteger(num)  # 生成num位的随机数
        r = x ^ dt  # 与原素数异或
        if isPrime(r):  # 确保结果是素数
            return r

破坏函数将原始素数p和q分别与900位的随机数进行异或操作，确保结果是素数。

解题思路

第一步：分解原始n

题目给出了原始的n, e, d，我们可以利用这些信息分解n：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def factorize_n_with_d(n, e, d):
    k = e * d - 1
    s = 0
    t = k
    while t % 2 == 0:
        s += 1
        t //= 2

    for _ in range(100):
        g = 2
        y = pow(g, t, n)
        if y == 1 or y == n-1:
            continue
        for _ in range(s-1):
            x = pow(y, 2, n)
            if x == 1:
                p = sympy.gcd(y-1, n)
                if p != 1 and p != n and n % p == 0:
                    q = n // p
                    return p, q
            elif x == n-1:
                break
            y = x
        g = nextprime(g)

第二步：利用Coppersmith攻击

由于破坏操作只改变了p和q的低900位，高位保持不变，我们可以使用Coppersmith方法进行攻击：

1
2
3
4
5
6
p_high = int(bin(p)[2:2050-900],2)  # 提取p的高位(2048-900=1148位)
p = p_high << 900  # 左移900位，低位补0

PR.<x> = PolynomialRing(Zmod(new_n))
f = x + p  # 构造多项式f(x) = x + p_high*2^900
roots = f.small_roots(X=2**900, beta=0.4)  # 寻找小根

第三步：恢复新素数并解密

1
2
3
4
5
6
7
8
9
if roots:
    p += int(roots[0])  # 恢复完整的new_p
    assert new_n % p == 0
    q = new_n // p  # 计算new_q

    phi = (p - 1) * (q - 1)
    d = pow(e, -1, phi)  # 计算私钥
    m = pow(enc_flag, d, new_n)  # 解密
    print(long_to_bytes(m).decode())

数学原理

Coppersmith方法的核心思想是：如果知道一个数的高位，可以在多项式时间内恢复其低位。在这个题目中：

  • 我们知道原始素数p
  • 新素数new_p = p ⊕ dt，其中dt是900位的随机数
  • 因此new_p和p只有低900位不同，高位完全相同
  • 我们可以构造多项式f(x) = p_high × 2^900 + x，在模new_n下寻找小根x

解题代码

完整的解题代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import sympy
from Crypto.Util.number import long_to_bytes
from sympy import nextprime

# 第一步：分解原始n
def factorize_n_with_d(n, e, d):
    k = e * d - 1
    s = 0
    t = k
    while t % 2 == 0:
        s += 1
        t //= 2

    g = 2
    for _ in range(100):
        y = pow(g, t, n)
        if y == 1 or y == n-1:
            continue
        for _ in range(s-1):
            x = pow(y, 2, n)
            if x == 1:
                p = sympy.gcd(y-1, n)
                if p != 1 and p != n and n % p == 0:
                    q = n // p
                    return p, q
            elif x == n-1:
                break
            y = x
        g = nextprime(g)

# 给定参数
n = 0x73cec712124b33c0294e01eb52e8c3cd2fe9ddbcbf457b3b950360063dfae42cbbe9855bd986bcfea0948fadfb252f5e2ff3c982ff47afb6596a496636f1fc5ecfe9f5db7620b23fe9e30d230aa9299ab9a78bfb5e0630fd1149259b2b2104ea65d2e27b89785e4bf01d0594d9f94575cbcc3383f63c5aabe4d5b48eb761cce3ab21689b3f3155b5f15efee240d5ac149318ff80bd72a75fccdc57402aa197b472d98758019df8e9edb31bda82967dc66bcad845df824775eeb66ee304664d7929e8405122f9b0a5406887729dbe9760eb62dd7018087723c07c07082d1d51035fb211a9fc6d8fb5b3ee5bb91af5e3d0b89addce289041a5683a1fe7dc06a3bae283062ba3febdd987b5ac9b9a8ae4b8b02b804accc0a413bb144680fd8d0d8d8bebe176e5a9121f7653c31ede984d234ccce50e688f7048a0bfdfc84004c006ae912c4d4e514c200883e8dabaeb4bf57a5f628eb4bd2e6688d9b7688bc3eed4ce03831be5044dedbd5fddc43a3274b26c990a0e444fcf4a607de59c4906dfd1ea111920c38b4a365c5838e9cf1a22b146aa7afbc6e2e29ebe35aee4bf4d2fbe186c0f359c71f80b8f6298ad38619168d5986a857f558017c546d6df896c690896601aabd48398e957b77ef0e15d6cda339050b74cda3328c34c889306d089efc95ff467a4a775d3e104642cd9819f002b5db8c5f39b4e8d1a83007276b8a0b7
e = 0x10001
d = 0x37f2646fd190ad1e9f95c50d97cf4590a21e1c766bfd382cafafa2bb41442ce9839aac47944e288de6abfec1b17be4675f492a47f3e600f85a3823df9299d32f46c8a372f39d961f9471914e257f55cf1ef3d7878783fc34b61e1d61da332879c8d9597b0f0dac988916ac349e1d73b615cfbfef778ceeccee4f63dc32b1b7d7213c9199b6acb1d8a5141c94d777a29b89f8e0aea457788eaa9ca43626a24c74ebab355c89e3747626d4899745d148500c91416c782f2b30c9332f5cd32a4d3144d2a407ce9acc00f99dc619d425586285350cff734cdba9d4fad636d7fcbabfa382965005d8343e36ffe72604e557bae5044435ad990b6dca6d922e64387cee4abc0574d2eeeb42dda977be1e1064f6a6b00e78db75a7bf8e6e0c2ac3c6a52b2e6670cad3c907d990e53a7a311ef7b097c7644ff6f2bf96573e47d33031eeabf22620bdbc254a8fff8b0fa6f90d320c45e8d9094c26401f78560e16f77d6e09bc219c9849f1b68dc84ed36eb0cec7df16c4672c16a6b704ef2185ce04539f08688b72d48f9491e55be0095ee74f9622e8ae6835381e2efcd520cd02d1eeeb09bc11ab75bc903053102bc92718f2bf8691561a40026e53e950674f712aaef8cc69360df54c1af8b1f4aef997371b8a108e9b193a51002fe8d61f3991153e7ebd9593d68cd03b2f252c3d9d7a5bf802dcd150bd86028bd3b07cb415b767d716c1

new_n = 0x73cec712124b33c0294e01eb52e8c3cd2fe9ddbcbf457b3b950360063dfae42cbbe9855bd986bcfea0948fadfb252f5e2ff3c982ff47afb6596a496636f1fc5ecfe9f5db7620b23fe9e30d230aa9299ab9a78bfb5e0630fd1149259b2b2104ea65d2e27b89785e4bf01d0594d9f94575cbcc3383f63c5aabe4d5b48eb761cce3ab21689b3f3155b5f15efee240d5ac11cee2acbd019de7c06f607ea618b5cd735b5a6972d2b446a12ff58cf8314822fa5ea09d0963acd00441b2a1b37aca01d7f39052927db98a0bd5ca1c49a7ad67923e3aac30ecd33cc8b4b30a40cdb3acc721ee5da53a02977cee959affe672a668525eb78df96af0a14f4ac04fab68efa8eabe9535e1064a5fc2ff7cac9520210311db0c3bf91101bc55a67a81e4f69364c724ee6ad6bdc301df642c9392e9befa4ff0d65481adb6feac251cd207044587da9710809700246cb3c63e659a97249f5e7418568e37db2fb2c1115e719d6682bb2e89b4e23d40ba4c532f289e10e0b89a5647c486a09b9e376844171b229d74f871004d4945a702a391a04ac704f43809e972891e6ab33b3c0f03f0b6f9ae005b26be6e647a1865c727277423f59a595187ffbfea13501e23b6b57ef115eaa6febcb207a3112628652a39578847241c33989e84607b0f683b30ddf773348b07360b063d9120a397809591ca18a04cd32ad9cbfe0494ed3ae8d2c5b43fdb51cb
enc_flag = 0x3b0487110b2d61683fc9e65717d6431281c25ceda38915c9c2ff16013066e8cbe9d5f6c1f05988333d96e861f1b216f85d537aa70f603b3d20487a18c5e0d3a03556be88f984f508803f4bb25300149e805204c91f7aea038e545cf588a29bcb20113f81b16d9aacdbd820aa48615a5227ab2f329423da0a254c8f318dff4a7b75cf48e5ac18abc2975fee111ee56297fd7778b49320f6427227f21c08391d7429c49b399c366db38467a339229048e50735dff071bf89dbbab22997071a6b5a16935f5b65032f2cefb9c670cddd1470f6bf16d7c46d0fff22b82b2c1d867f4faa60e5daaad35a15ac0413a17beb5371a06f22c646336ae5e5738cfc5e997860056fb8bf1e02f27031ecd2b7983df510c4cdebbc644ea49e99e2376b89a90be8c89e4995c6689cc39d01fcc8ffef416e49684c0a01fdffab4613cb8eddbfa9e14d9b2daca6ad57c4e440a049d04b915ecfd64095c549bb9d22fb502a740a7373c1961c8cb7a58604bcbca3e5a97e28d5f498061db7cfbf07085ec84f47856e88992ab08870cbdb050431260861d0bcc9bbdf9a4164b8581f1f67e86ab854db1769418e300d73cf902509c76969473d0ee1b70c3b24085942fa9782507b359ffe049b18832610b4555b9bfe8eeae14cec53ab21881475f81069a6a33d6e38e3825eeb13874da8f0c91160712090a092286ea3838d88020e459f795783ad099367

# 分解原始n得到p和q
p, q = factorize_n_with_d(n, e, d)

# 第二步：使用Coppersmith攻击
p_high = int(bin(p)[2:2050-900],2)  # 提取p的高1148位
p_val = p_high << 900  # 左移900位

# 在SageMath环境中使用Coppersmith方法
# PR.<x> = PolynomialRing(Zmod(new_n))
# f = x + p_val
# roots = f.small_roots(X=2**900, beta=0.4)

# 第三步：恢复新素数并解密
# if roots:
#     new_p = p_val + int(roots[0])
#     new_q = new_n // new_p
#     phi = (new_p - 1) * (new_q - 1)
#     d_new = pow(e, -1, phi)
#     m = pow(enc_flag, d_new, new_n)
#     flag = long_to_bytes(m).decode()
#     print(flag)

最终结果

成功解密后得到flag：flag{6b1ff461dc15e5476cafe887189178e3924dad84}

事后发现new_n可直接分解hhhhhh