2024CISCN

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 3.1k 阅读时长 ≈ 11 分钟

记录国赛

浅浅记录一下第一天被学长和队友带飞的小高光

第一天的题，对我这种中等水平的密码手并不友好

第二天定榜70，华东南15，被队友带进半决赛了(今天终于是做出题了，两道50分的密码😭)

用户信息访问控制

这道题是和队友们一起做出来的，由我记录一下

要求①：选手修改instance/server目录下策略文件record.list，补全表1中所有记录项对应的客体安全属性

根据

record.list本来就存在的一些数据，只需要添加下面内容即可完成要求①

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
{
        "name":"cell",
        "isleveladjust":1,        //需要调整级别
        "isselfdefine":0,         //该内容没有自己的专门类别
        "class":0,                //
        "level_fix":0,            //该项级别不固定
        "level_adjust":-1         //低1级
}
{
        "name":"email",
        "isleveladjust":1,        //需要调整级别
        "isselfdefine":0,         //该内容没有自己的专门类别
        "class":0,
        "level_fix":0,            //该项级别不固定
        "level_adjust":-2         //低2级
}

要求②：修改src/record_acl/record_acl.c中except_rule，以在数据读取行为符合例外规则时返回1,并在record_acl目录下用make命令编译。而后执行sh record_access.sh自行测试，观察输出，如输出符合第一节中访问控制要求，则可执行sh player.sh ，提交答案，等待赛题裁决机制的输出，如输出flag，则提交flag，否则如果题目给出错误提示，则修改策略文件和代码，对代码重新编译后再次提交进行测试。

根据要求实现查询薪资的功能，把函数修改为下面内容：

1
2
3
4
5
6
7
8
9
int except_rule(char * record_name,char * read_user,char * record_user)
{
    int ret;
    if (!strncmp(record_name,"salary",6) && !strncmp(read_user,record_user,strlen(record_user))){
        return 1;
    }
    // 要求查询用户与被查询用户两个值相同，而且查询字段为薪水(salary)
    return 0;
}

在make之前，需要在cube-userinfo-access下运行source set_env.sh

然后再在record_acl下make

hash——复现

task.py

1
2
3
4
5
6
7
8
9
10
11
12
#!/usr/bin/python2
# Python 2.7 (64-bit version)
from secret import flag
import os, binascii, hashlib
key = os.urandom(7)
print hash(key)
print int(hashlib.sha384(binascii.hexlify(key)).hexdigest(), 16) ^ int(binascii.hexlify(flag), 16)

"""
7457312583301101235
13903983817893117249931704406959869971132956255130487015289848690577655239262013033618370827749581909492660806312017
"""

这题赛后在鸡块师傅指导下复现的

首先查源码：py27hash · PyPI

比赛的时候，从官网查的源码是c语言，不太懂指针导致没理解hash的过程。这方面还得练

得知hash实现如下：

1
2
3
4
5
6
7
8
9
def hash(s):
    mask = 0xffffffffffffffff
    s = s.encode()
    x = s[0] << 7
    for char in s:
        x = (1000003 * x) & mask ^ char
    x ^= len(s) & mask
        
    return x

& mask相当于模$2^{64}$

写成数学式子

$$
x_0 = s_0 \times 2^7
$$

$$
x_1 = 1000003\times x_0 \mod 2^{64} \otimes s_0
$$

$$
x_2 = 1000003\times x_1 \mod 2^{64} \otimes s_1
$$

$$
x_3 = 1000003\times x_2 \mod 2^{64} \otimes s_2
$$

$$
x_4 = 1000003\times x_3 \mod 2^{64} \otimes s_3
$$

$$
x_5 = 1000003\times x_4 \mod 2^{64} \otimes s_4
$$

$$
x_6 = 1000003\times x_5 \mod 2^{64} \otimes s_5
$$

$$
x_7 = 1000003\times x_6 \mod 2^{64} \otimes s_6
$$

$$
x = x_7 \otimes length \mod 2^{64}\
$$

逆向回来的话很容易
$$
x_7 = x \otimes length \mod 2^{64}
$$

$$
x_6 = x_7 \otimes s_6 \times 1000003^{-1} \mod 2^{64}
$$

$$
x_5 = x_6 \otimes s_5 \times 1000003^{-1} \mod 2^{64}
$$

$$
x_4 = x_5 \otimes s_4 \times 1000003^{-1} \mod 2^{64}
$$

$$
x_3 = x_4 \otimes s_3 \times 1000003^{-1} \mod 2^{64}
$$

$$
x_2 = x_3 \otimes s_2 \times 1000003^{-1} \mod 2^{64}
$$

$$
x_1 = x_2 \otimes s_1 \times 1000003^{-1} \mod 2^{64}
$$

$$
x_0 = x_1 \otimes s_0 \times 1000003^{-1} \mod 2^{64}
$$

中间相遇攻击的思路在于，假设密钥是abcdefg

我们从前面加密4个字符，即加密到$x_4$，并把他作为元组记录下来。

再把得到的密文从后面逆向，逆到$x_4$,如果和前面的对应上了，即爆破出key

exp

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
from itertools import product
from Crypto.Util.number import *
from tqdm import trange

mask = 0xffffffffffffffff
inv = inverse(1000003,2**64)
x7 = 7457312583301101235
cipher = 13903983817893117249931704406959869971132956255130487015289848690577655239262013033618370827749581909492660806312017

table = {}
for i in trange(256):
    # 这是第一个字符
    for tmp in product([i for i in range(256)],repeat=3):
        # 下面便是hash的实现,但是我们只乘上3个字符
        x = (i << 7) & mask                       
        x = (1000003 * x) & mask ^ i
        pre = list(tmp)
        for char in pre:
            x = (1000003 * x) & mask ^ char
        
        table[x] = pre
        # 记录下来
    
    for tmp in product([i for i in range(256)],repeat=3):
        tail = list(tmp)
        x7 = (x7 ^ 7) & mask
        x6 = (x7 ^ tail[-1]) * inv & mask
        x5 = (x6 ^ tail[-2]) * inv & mask
        x4 = (x5 ^ tail[-3]) * inv & mask
        if x4 in table.keys():
            print(i,table[x4],tail)
            # 93 [140, 240, 63] [90, 8, 82]
            break

整个程序差不多2.5小时，没跑全，问了鸡块师傅。正确的是93，最后key = [93,140,240,63,90,8,82]

1
2
3
4
5
6
7
8
9
10
11
import hashlib
import binascii

m = [93,140,240,63,90,8,82]
key = b""
for i in m:
    key += long_to_bytes(i)

flag = long_to_bytes(int(hashlib.sha384(binascii.hexlify(key)).hexdigest(), 16) ^ cipher) 
print(flag)
# flag{bdb537aa-87ef-4e95-bea4-2f79259bdd07}

用格来做

根据hash函数的过程，其中$s_0,…,s_6$都是$0-255$的值，可以把异或看作加或者是减去一个值，可以认为是偏移量，把偏移量记为$b$

所以相当于是下面这个过程

$$
x_0 = b_0 \times 2^7
$$

$$
x_1 \equiv ax_0 + b_0 \mod 2^{64}
$$

$$
x_2 \equiv ax_1 + b_1 \mod 2^{64}
$$

$$
x_3 \equiv ax_2 + b_2 \mod 2^{64}
$$

$$
x_4 \equiv ax_3 + b_3 \mod 2^{64}
$$

$$
x_5 \equiv ax_4 + b_4 \mod 2^{64}
$$

$$
x_6\equiv ax_5 + b_5 \mod 2^{64}
$$

$$
x_7 \equiv ax_6 +b_6 \mod 2^{64}
$$

$$
res \equiv x_7 \otimes 7 \mod 2^{64}
$$

最后可以把他写成一个多项式:
$$
x_7 \equiv 128a^7b_0 + a^6b_0 + a^5b_1 + a^4b_2 + a^3b_3 + a^2b_4 + ab_5 + b_6 \mod 2^{64}\
$$

构造格

目标向量大概在$(-256,255)$

规约出来的向量，不是原本的字符值。我们可以通过这样的关系来得到:
$$
x_7 = x_6 \otimes s_6
$$
而$x_6 = x_7 - b_6$

所以$s_6 = (x_7 - b_6) \otimes x_7$

以此类推，我们就可以求出key

exp

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
from Crypto.Util.number import long_to_bytes
import hashlib
import binascii

mask = 0xffffffffffffffff
res = 7457312583301101235
cipher = 13903983817893117249931704406959869971132956255130487015289848690577655239262013033618370827749581909492660806312017
MOD = 2^64
a = 1000003

x7 = (res ^^ 7) & mask
xishu = [128*a^7+a^6,a^5,a^4,a^3,a^2,a,1]

length = len(xishu)

Ge = Matrix(ZZ,length+2,length+2)

for i in range(length):
    Ge[i,i] = 1
    Ge[i,-1] = xishu[i]
    
Ge[-2,-2] = 256
Ge[-2,-1] = -x7
Ge[-1,-1] = MOD

Ge[:,-1:] *= 2^200
c = x7
for line in Ge.LLL():
    key = b""
    if line[-1] == 0 and line[-2] == 256:
        tmp = line[:-2]
        for i in range(len(tmp)):
            tmpc = (c - tmp[6-i]) % 2^64
            s = (tmpc ^^ c)
            key += long_to_bytes(s)
            c = (c ^^ s) * gmpy2.invert(a,2^64) % 2^64
    m = int(hashlib.sha384(binascii.hexlify(key[::-1])).hexdigest(), 16) ^^ cipher
    print(long_to_bytes(m))
    # flag{bdb537aa-87ef-4e95-bea4-2f79259bdd07}

myagcd——紧急下线的题目

task.py

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
from random import randint
from Crypto.Util.number import getPrime

def gen_param(x, p, BITS):
    r = getPrime(BITS//2)
    while True:
        q = getPrime(BITS)
        if q < p:
            break
    b = (x * q + r) % p
    return r, b, q

def gen_key(BITS):
    p = getPrime(BITS)
    x = randint(1, p-1)
    
    sk = [x]
    pk = [p]
    for _ in range(2):
        r, b, q = gen_param(x, p, BITS)
        sk.append(r)
        pk.extend([b, q])
    return sk, pk

if __name__ == "__main__":
    print("welcome to my game, you need to pass 10 rounds to get the flag")
    round = 10
    for _ in range(round):
        sk, pk = gen_key(256)
        x = sk[0]
        print("pk: ", pk)
        x_ = int(input("give me x: "))
        if x_ == x:
            print("good")
        else:
            print("wrong!")
            exit(0)
    print("congratulation, here is your flag")
    with open("flag.txt") as f:
        print(f.read())

由题意知
$$
b_0 = xq_0 + r_0 \mod p
$$

$$
b_1 = xq_1 + r_1 \mod p
$$

已知$b,q,p$，思路是消去x，把$r_0$或$r_1$求出来(r的数量级只有128)，再求解x

作推导可以得到
$$
b_0q_1 \equiv xq_0q_1 + r_0q_1 \mod p\
b_1q_0 \equiv xq_1q_0 + r_1q_0 \mod p
$$

$$
b_0q_1 - b_1q_0 \equiv r_0q_1 - r_1q_0 \mod p
$$

$$
0 = r_0q_1 - r_1q_0 + b_0q_1 - b_1q_0 + kp
$$

最后一列需要乘一个大数，大概$2^{128}$，实际上会卡界

因为r是128bit的素数，所以r的最高位和最低位是1，可以把r写成$2^{127} + r_0 + 1$

这样的话，等式写为
$$
0 = (2^{127} + r_0\times 2 + 1)q_1 - (2^{127} + r_1\times 2+1)q_0 + b_0q_1 - b_1q_0 + kp
$$

即
$$
0 = (2^{127} + 1)q_1 - (2^{127}+1)q_0 + b_0q_1 - b_1q_0 + kp
$$
构造格

还是需要在最后一列乘上大数

exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from Crypto.Util.number import *

sk = [31067408706118531778836025838205112775236644965865772823812117127751271259476, 290929702745799288901141574400839037929, 321295811382361172183984777251716725209]
pk = [71326246066892613373620794096364722364475105426485661989214263916039351653301, 39065868145148974053618331846930041188453567579625647858296606637712340989831, 60701185955859641632147876660678128394101873280164553720147323354883999537411, 6495230186702141273101847496975434679236671407037295404955773501796732774419, 60522146751495726051537052036607716455760564547991467652808039897553164071019]

x = sk[0]
p,b0,q0,b1,q1 = pk

T = 2^128
Ge = Matrix(ZZ,[
    [1,0,0,2*q1*T],
    [0,1,0,-2*q0*T],
    [0,0,2^126,((2^127+1)*q1-(2^127+1)*q0 + b1*q0-b0*q1)*T],
    [0,0,0,p*T]
])

for line in Ge.LLL():
    t0 = abs(line[0])
    t1 = abs(line[1])
    r0 = 2^127 + 2*t0 + 1
    r1 = 2^127 + 2*t1 + 1
    if isPrime(r0) and isPrime(r1):
        xx = (b0 - r0)*inverse(q0,p) % p
        print(xx == x)

自己测的数据

OvO

task.py

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
from Crypto.Util.number import *
from secret import flag

nbits = 512
p = getPrime(nbits)
q = getPrime(nbits)
n = p * q
phi = (p-1) * (q-1)
while True:
    kk = getPrime(128)
    rr = kk + 2
    e = 65537 + kk * p + rr * ((p+1) * (q+1)) + 1
    if gcd(e, phi) == 1:
        break
m = bytes_to_long(flag)
c = pow(m, e, n)

e = e >> 200 << 200
print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')

"""
n = 111922722351752356094117957341697336848130397712588425954225300832977768690114834703654895285440684751636198779555891692340301590396539921700125219784729325979197290342352480495970455903120265334661588516182848933843212275742914269686197484648288073599387074325226321407600351615258973610780463417788580083967
e = 37059679294843322451875129178470872595128216054082068877693632035071251762179299783152435312052608685562859680569924924133175684413544051218945466380415013172416093939670064185752780945383069447693745538721548393982857225386614608359109463927663728739248286686902750649766277564516226052064304547032760477638585302695605907950461140971727150383104
c = 14999622534973796113769052025256345914577762432817016713135991450161695032250733213228587506601968633155119211807176051329626895125610484405486794783282214597165875393081405999090879096563311452831794796859427268724737377560053552626220191435015101496941337770496898383092414492348672126813183368337602023823
"""

$$
e = 65537 + kp + (k+2)(p+1)(q+1) + 1
$$

化简得
$$
e = 65537 + (k+2)n + 2(k+1)p + (k+2)q + k+3
$$
注意数量级，把e // n之后，等号右边只剩下$k+2$，可以求出k，这个可以自己生成数据检验，没有什么问题

我们把$65537 +(k+2)n+k+3$记为a
$$
e = a + 2(k+1)p+(k+2)q
$$
两边同乘p
$$
ep = ap + 2(k+1)p^2 + (k+2)n
$$
这里只有p是未知的，但是因为这里e是模掉低200位，所以求的p会缺失200位

这个方程求解之后，用高位泄露的思路求解即可

exp

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
#sage
from Crypto.Util.number import *

def get_p(phigh,n):
    PR.<x> = PolynomialRing(Zmod(n))
    f = x + phigh
    roots = f.monic().small_roots(X = 2^200,beta=0.4)
    if roots:
        x0 = roots[0]
        p = int(x0) + phigh
        assert isPrime(p)
        return p
    
n = 111922722351752356094117957341697336848130397712588425954225300832977768690114834703654895285440684751636198779555891692340301590396539921700125219784729325979197290342352480495970455903120265334661588516182848933843212275742914269686197484648288073599387074325226321407600351615258973610780463417788580083967
e = 37059679294843322451875129178470872595128216054082068877693632035071251762179299783152435312052608685562859680569924924133175684413544051218945466380415013172416093939670064185752780945383069447693745538721548393982857225386614608359109463927663728739248286686902750649766277564516226052064304547032760477638585302695605907950461140971727150383104
c = 14999622534973796113769052025256345914577762432817016713135991450161695032250733213228587506601968633155119211807176051329626895125610484405486794783282214597165875393081405999090879096563311452831794796859427268724737377560053552626220191435015101496941337770496898383092414492348672126813183368337602023823

k = e // n - 2
print(k)
a = 65537 + (k+2)*n + (k+2) + 3

R.<x> = PolynomialRing(RealField(1024))
f = e*x - (2*(k+1)*x^2 + (k+2)*n + a*x)
res = f.roots()

for root in res:
    p_high = int(root[0])
    p_high = p_high >> 200 << 200
    p = get_p(p_high,n)
    if p != None:
        q = n // p
        e = 65537 + k * p + (k+2) * ((p+1) * (q+1)) + 1
        d = inverse(e,(p-1)*(q-1))
        m = pow(c,d,n)
        print(long_to_bytes(int(m)))
        # flag{b5f771c6-18df-49a9-9d6d-ee7804f5416c}

古典密码

密文：AnU7NnR4NassOGp3BDJgAGonMaJayTwrBqZ3ODMoMWxgMnFdNqtdMTM9

在Atbash码解码之后，再base64解码得到

fa{2b838a-97ad-e9f743lgbb07-ce47-6e02804c}

flag一般是uuid4的格式，括号内应该是8-4-4-4-12

这里解出来的是6-4-12-4-8，试了下围栏密码，得到flag:flag{b2bb0873-8cae-4977-a6de-0e298f0744c3}

ezrsa——复现

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
import random
from secret import flag

m = bytes_to_long(flag)
key = RSA.generate(1024)
passphrase = str(random.randint(0,999999)).zfill(6).encode()
output = key.export_key(passphrase=passphrase).split(b'\n')
for i in range(7, 15):
    output[i] = b'*' * 64
with open("priv.pem", 'wb') as f:
    for line in output:
        f.write(line + b'\n')
with open("enc.txt", 'w') as f:
    f.write(str(key._encrypt(m)))

priv.pem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
-----BEGIN RSA PRIVATE KEY-----
Proc-Type: 4,ENCRYPTED
DEK-Info: DES-EDE3-CBC,435BF84C562FE793

9phAgeyjnJYZ6lgLYflgduBQjdX+V/Ph/fO8QB2ZubhBVOFJMHbwHbtgBaN3eGlh
WiEFEdQWoOFvpip0whr4r7aGOhavWhIfRjiqfQVcKZx4/f02W4pcWVYo9/p3otdD
ig+kofIR9Ky8o9vQk7H1eESNMdq3PPmvd7KTE98ZPqtIIrjbSsJ9XRL+gr5a91gH
****************************************************************
****************************************************************
****************************************************************
****************************************************************
****************************************************************
****************************************************************
****************************************************************
****************************************************************
hQds7ZdA9yv+yKUYv2e4de8RxX356wYq7r8paBHPXisOkGIVEBYNviMSIbgelkSI
jLQka+ZmC2YOgY/DgGJ82JmFG8mmYCcSooGL4ytVUY9dZa1khfhceg==
-----END RSA PRIVATE KEY-----

类似蓝帽杯2022的corrupted_key

不一样的是，这题得到的pem文件内容是加密的

根据代码

1
key.export_key(passphrase=passphrase).split(b'\n')

找到Crypto下的源代码 RSA.py

发现关键代码

如果passphrase存在，则随机生成一个salt，然后使用PKBDF1方法加密两次拼接得到key。

此时使用的加密方式为3des ，模式为cbc，iv为salt

由此我们可以根据passphrase的生成方式来爆破出唯一的passphrase

根据私钥的格式，开头一定是30820，再根据n为1024bit，那么在私钥中n的格式为02818xxxxxx,加密参数e大概率为65537，即0x10001

那么其在私钥中则为 0203010001。

解密后存在如下特征的明文，那么当前的passphrase为所求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Cipher import DES3
from Crypto.Protocol.KDF import PBKDF1
from Crypto.Hash import MD5
import base64


enc1 = "9phAgeyjnJYZ6lgLYflgduBQjdX+V/Ph/fO8QB2ZubhBVOFJMHbwHbtgBaN3eGlhWiEFEdQWoOFvpip0whr4r7aGOhavWhIfRjiqfQVcKZx4/f02W4pcWVYo9/p3otdDig+kofIR9Ky8o9vQk7H1eESNMdq3PPmvd7KTE98ZPqtIIrjbSsJ9XRL+gr5a91gH"
enc2 = "hQds7ZdA9yv+yKUYv2e4de8RxX356wYq7r8paBHPXisOkGIVEBYNviMSIbgelkSIjLQka+ZmC2YOgY/DgGJ82JmFG8mmYCcSooGL4ytVUY9dZa1khfhceg=="

salt = bytes.fromhex("435bf84c562fe793")
dict = [str(i).zfill(6).encode() for i in range(0,1000000)]
for passphrase in dict:
    key = PBKDF1(passphrase, salt, 16, 1, MD5)
    key += PBKDF1(key + passphrase, salt, 8, 1, MD5)
    cipher = DES3.new(key, DES3.MODE_CBC, salt)
    data = cipher.decrypt(base64.b64decode(enc1)).hex()
    if data.startswith("30820") and "02818" in data and "0203010001" in data:
        print(data)
        print(passphrase)
        data2 = cipher.decrypt(base64.b64decode(enc2)).hex()
        print(data2)
        break

得到

1
2
3
3082025c02010002818100a18f011bebacceda1c6812730b9e62720d3cbd6857af2cf8431860f5dc83c5520f242f3be7c9e96d7f96b41898ff000fdb7e43ef6f1e717b2b7900f35660a21d1b16b51849be97a0b0f7cbcf5cfe0f00370cce6193fefa1fed97b37bd367a673565162ce17b0225708c032961d175bbc2c829bf2e16eabc7e0881feca0975c810203010001

6a033064c5a0dffc8f2363b340e502405f152c429871a7acdd28be1b643b4652800b88a3d23cc57477d75dd5555b635167616ef5c609d69ce3c2aedcb03b62f929bbcd891cadc0ba031ae6fec8a2116d0808080808080808

再根据私钥格式提取n,e,dq,inv

因为本题中中间部分的私钥文件缺失，而且加密是cbc的，导致enc2第一块解密的结果错误，需要去掉，也就是说正确的dq只有48bit

因此得到

1
2
3
4
n = 0xa18f011bebacceda1c6812730b9e62720d3cbd6857af2cf8431860f5dc83c5520f242f3be7c9e96d7f96b41898ff000fdb7e43ef6f1e717b2b7900f35660a21d1b16b51849be97a0b0f7cbcf5cfe0f00370cce6193fefa1fed97b37bd367a673565162ce17b0225708c032961d175bbc2c829bf2e16eabc7e0881feca0975c81
e = 65537
dq_leak= 0x8f2363b340e5
inv = 0x5f152c429871a7acdd28be1b643b4652800b88a3d23cc57477d75dd5555b635167616ef5c609d69ce3c2aedcb03b62f929bbcd891cadc0ba031ae6fec8a2116d

$$
\because ed_q = 1 + k(q-1)
$$

$$
\therefore kq = ed_q +k-1
$$

k可以爆破，但不知道q，所以没办法构造1元coppersmith
$$
\because inv \times q \equiv 1 \mod p
$$

$$
\therefore inv \times q - 1 \equiv 0 \mod p
$$

同乘kq
$$
inv \times q \times kq - kq \equiv 0 \mod n
$$
此时会有个突兀的q，不好处理，我们再同乘k，得到
$$
inv \times (kq)^2 - k\times kq \equiv 0 \mod n
$$
得到两个式子：
$$
tmp = e(x + dq_{low})+k-1
$$

$$
inv\times tmp^2 - k\times tmp \equiv 0 \mod n
$$

恢复出dq之后，$q = (ed_q + k - 1) // k$

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
from tqdm import *
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP

n = 0xa18f011bebacceda1c6812730b9e62720d3cbd6857af2cf8431860f5dc83c5520f242f3be7c9e96d7f96b41898ff000fdb7e43ef6f1e717b2b7900f35660a21d1b16b51849be97a0b0f7cbcf5cfe0f00370cce6193fefa1fed97b37bd367a673565162ce17b0225708c032961d175bbc2c829bf2e16eabc7e0881feca0975c81
e = 65537
dq_leak= 0x8f2363b340e5
inv = 0x5f152c429871a7acdd28be1b643b4652800b88a3d23cc57477d75dd5555b635167616ef5c609d69ce3c2aedcb03b62f929bbcd891cadc0ba031ae6fec8a2116d
c = 55149764057291700808946379593274733093556529902852874590948688362865310469901900909075397929997623185589518643636792828743516623112272635512151466304164301360740002369759704802706396320622342771513106879732891498365431042081036698760861996177532930798842690295051476263556258192509634233232717503575429327989

def coppersmith(k):
    R.<x> = PolynomialRing(Zmod(n))
    tmp = e * (x * 2^48 + dq_leak) + k - 1          # kq
    f = inv * tmp^2 - k*tmp
    f = f.monic()
    x0 = f.small_roots(X=2^464,beta=1,epsilon=0.09)
    return x0

for k in trange(1，e):
    x0 = coppersmith(k)
    if x0 != []:
        dq = int(x0[0]) * 2^48 + dq_leak
        q = (e*dq + k - 1) // k
        # print(f"k = {k}")
        # k = 47794
        p = n // q
        d = inverse(e,(p-1)*(q-1))
        m = pow(c,d,n)
        print(long_to_bytes(int(m)))
        # b'flag{df4a4054-23eb-4ba4-be5e-15b247d7b819}'
        break

参考：20220709-蓝帽杯-CryptoSecWriteUp | 4XWi11’s Blog

在求出q后，其实pow(c,dq,q)也能出flag，不用求p

-------------已经到底啦！-------------