Crypto Challenge: DLP over Composite Modulus#

题目分析#

1
m = bytes_to_long(flag)
2
n = 12658496303201581987904413378231672705848324463557650748242993254944407255926163828010653564020917857620982783176641954529909922267412737349457807433073478956716588664201001
3
print(pow(7,m,n))
4
# 输出: 965034179468698868811585108402708910494957686334522514089846951965123540637986716168374511689067098771159300199946023700677529514020404560754430727137920456537319123516664

已知 7^m mod n = c，需要求 m，属于离散对数问题（DLP）。

1. 分解模数 n#

用 factorint 对 n 进行因子分解：

1
n = p^5 × q
2

3
p = 10532208912748542707
4
q = 97675309052127525561124163779796696566431155872900589821544185613370103125443

2. 检查 p-1 和 q-1 的因子平滑度#

p-1 = 2 × 33857 × 38917 × 62131 × 64327（全部是小素数）
q-1 = 2 × 12653² × 15679³ × 22367 × 34439³ × 51157³ × 54851³ × 62617²（小素数的高次幂，同样平滑）

两个阶均高度平滑，因此可用 Pohlig-Hellman 算法逐一求解。

3. 分别求解 DLP#

3.1 模 p 部分：求解 DLP mod p#

由于 p 是素数，直接用 discrete_log 解 DLP mod p：

1
m ≡ 2302925804021240453 (mod p-1)

3.2 模 p^5 部分：P-adic 提升（Hensel Lifting）#

由于群阶随模的幂次增长：

|---|---| | p¹ | p-1 | | p² | p × (p-1) | | p³ | p² × (p-1) | | p⁴ | p³ × (p-1) | | p⁵ | p⁴ × (p-1) |

采用逐级提升法：已知 mod pᵏ 的解，求 mod p^(k+1)。

令 mod pᵏ 的解为 mₖ，阶为 ordₖ。设：

1
m_{k+1} = mₖ + t × ordₖ

则需满足：

1
7^{m_{k+1}} ≡ c (mod p^{k+1})
2
7^{mₖ} × (7^{ordₖ})^t ≡ c (mod p^{k+1})

令 base = 7^{ordₖ} mod p^{k+1}，由于 ordₖ 是 mod pᵏ 的阶，有 base ≡ 1 (mod pᵏ)，即 base = 1 + b × pᵏ。

令 delta = c × (7^{mₖ})^{-1} mod p^{k+1}，同样有 delta ≡ 1 (mod pᵏ)，即 delta = 1 + r × pᵏ。

由 (1 + b × pᵏ)^t ≡ 1 + t × b × pᵏ (mod p^{k+1}) 得：

1
t ≡ r × b^{-1} (mod p)

逐级计算得：

1
m ≡ 706900059475081675955418970903030737455000707376266479970373529597124989 (mod p^4 × (p-1))

3.3 模 q 部分：Pohlig-Hellman#

同样用 discrete_log 求解 mod q：

1
m ≡ 706900059475081675955418970903030737455000707376266479970373529597124989 (mod q-1)

4. 结果#

两个模下的解恰好相同，说明 m 本身即为该值。转换为字节：

1
>>> long_to_bytes(m)
2
b'flag{p4d1c_8r34k5_5m007h_d1p!}'

5. 验证#

1
pow(7, m, n) == c  →  True

核心技巧总结#

因子分解 n → 发现 n = p⁵·q
检查阶的平滑性 → p-1 和 q-1 均为小素数，适用 Pohlig-Hellman
P-adic 提升（Hensel Lifting） → 将模 p 的解逐级提升到 p⁵
直接求解 mod q → 利用 q-1 的平滑性
bytes_to_long 转换 → 得到 flag

Flag: flag{p4d1c_8r34k5_5m007h_d1p!}

double_crypto 题解（超详细版）#

你在看什么？#

这是一道 CTF（Capture The Flag，夺旗赛）密码学题目的完整解答。即使你完全没学过密码学，这篇文档也会一步步教会你如何解题。

一、题目给了我们什么？#

题目给的是一段 Python 代码和它的输出。代码做了以下几件事：

1
1. 用 RSA 算法加密 flag（一段秘密文字）
2
2. 把 RSA 的加密结果再用 AES 算法加密了一遍
3
3. 打印出了 AES 的密钥（key）、初始向量（IV）、以及最终密文（ciphertext）
4
4. 打印出了 RSA 的公钥（n 和 e）

但注意：IV 是被 ROT13 编码过的，不是原始值。这从代码注释 #caesar_13_iv 可以看出来。

题目的源码：

1
#caesar_13_iv
2
import os
3
from Crypto.Cipher import AES
4
from Crypto.Util.Padding import pad
5
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
6
import random
7

8
script_dir = os.path.dirname(os.path.abspath(__file__))
9
output_path = os.path.join(script_dir, "encrypted_params.txt")
10

11
p = getPrime(128)
12
q = getPrime(128)
13
n = p * q
14
e = 65537
15
phi = (p - 1) * (q - 1)
16
d = pow(e, -1, phi)
17

18
print(f"[RSA] n = {n}")
19
print(f"[RSA] e = {e}")
20

21
m = bytes_to_long(flag)
22
c_rsa = pow(m, e, n)
23
print(f"[RSA] c_rsa = {c_rsa}")
24

25
c_rsa_bytes = long_to_bytes(c_rsa, (n.bit_length() + 7) // 8)
26
aes_key = random.randbytes(16)
27
iv = random.randbytes(16)
28
cipher_aes = AES.new(aes_key, AES.MODE_CBC, iv)
29
padded_data = pad(c_rsa_bytes, AES.block_size)
30
c_aes = cipher_aes.encrypt(padded_data)
31

32
print(f"[AES] key = {aes_key.hex()}")
33
print(f"[AES] iv  = {iv.hex()}")
34
print(f"[AES] ct  = {c_aes.hex()}")
35

36
n          = 108460347539116548233850259329362939266582518558734624388997849930646568128401
37
e          = 65537
38
key        = 8c0c5db5efdd4505b1cd88569b6bf8f5
39
IV         = 6144s1oo1s1p7osq442p6qsr5733701p          ← 注意：里面有字母！不正常！
40
ciphertext = 0ffb5c8356bf6a0ea8e541fbc7f27aa00095f302dbc27b7e4842a500cfd9767b16c9fc8f7a8d420e8bd604b727a363fb

二、解题的整体思路#

加密的顺序是：

1
flag  →  RSA加密  →  中间结果  →  AES加密  →  最终密文

所以解密的顺序要反过来：

1
最终密文  →  AES解密  →  中间结果  →  RSA解密  →  flag

就像拆一个套娃，先拆外面一层（AES），再拆里面一层（RSA）。

三、第一步：修复被篡改的 IV（ROT13 解码）#

3.1 什么是 IV？#

IV（Initialization Vector，初始向量）是 AES-CBC 加密模式需要的一个随机数，长度固定为 16 字节（128 位）。它确保了即使同样的内容加密两次，结果也不同。

3.2 IV 有什么问题？#

一个正常的 IV 应该是 16 字节，用十六进制表示就是 32 个字符，每个字符只能是 0-9 或 a-f。

但题目给的 IV 是 6144s1oo1s1p7osq442p6qsr5733701p——里面有 s、o、p、q、r！这些字母不在十六进制范围内（十六进制只到 f），所以这肯定不是正常的 IV。

3.3 什么是 ROT13？#

ROT13 是凯撒密码的一种，把字母向后移动 13 位：

1
a → n    b → o    c → p    d → q    e → r    f → s
2
g → t    h → u    i → v    j → w    k → x    l → y
3
m → z    n → a    o → b    p → c    q → d    r → e
4
s → f    t → g    u → h    v → i    w → j    x → k
5
y → l    z → m

ROT13 是自反的：加密和解密是同一个操作（移 13 位，移两次 13 位 = 移 26 位 = 回到原位）。

3.4 解码实际操作#

把 IV 中的每个字母做 ROT13，数字不动：

位置	原始	操作	结果
1	6	数字，不动	6
2	1	数字，不动	1
3	4	数字，不动	4
4	4	数字，不动	4
5	s	s → f	f
6	1	数字，不动	1
7	o	o → b	b
8	o	o → b	b
9	1	数字，不动	1
10	s	s → f	f
11	1	数字，不动	1
12	p	p → c	c
13	7	数字，不动	7
14	o	o → b	b
15	s	s → f	f
16	q	q → d	d
17	4	数字，不动	4
18	4	数字，不动	4
19	2	数字，不动	2
20	p	p → c	c
21	6	数字，不动	6
22	q	q → d	d
23	s	s → f	f
24	r	r → e	e
25	5	数字，不动	5
26	7	数字，不动	7
27	3	数字，不动	3
28	3	数字，不动	3
29	7	数字，不动	7
30	0	数字，不动	0
31	1	数字，不动	1
32	p	p → c	c

解码后的 IV = 6144f1bb1f1c7bfd442c6dfe5733701c

现在所有的字符都在 0-9a-f 范围内了，这是一个合法的十六进制 IV。

四、第二步：AES-CBC 解密#

4.1 什么是 AES-CBC？#

AES（Advanced Encryption Standard）是一种对称加密算法。CBC（Cipher Block Chaining，密文分组链接）是一种加密模式。

通俗理解：

AES 就像一个锁，key（密钥）是开锁的密码
CBC 模式意味着每块数据在加密前会和前一块的密文做 XOR 运算
IV 是第一块数据的”前一块密文”的替代品

要解密 AES-CBC，你需要三样东西：

key（密钥）：8c0c5db5efdd4505b1cd88569b6bf8f5
IV（初始向量）：我们刚解码出来的 6144f1bb1f1c7bfd442c6dfe5733701c
密文：0ffb5c8356bf6a0ea8e541fbc7f27aa00095f302dbc27b7e4842a500cfd9767b16c9fc8f7a8d420e8bd604b727a363fb

4.2 用 Python 解密#

使用 pycryptodome 库（先 pip install pycryptodome）：

1
from Crypto.Cipher import AES          # 导入 AES 加密库
2
from Crypto.Util.Padding import unpad  # 导入去填充函数
3

4
# 这些字符串都是十六进制表示，用 bytes.fromhex() 转为字节
5
key = bytes.fromhex('8c0c5db5efdd4505b1cd88569b6bf8f5')  # 16 字节
6
iv  = bytes.fromhex('6144f1bb1f1c7bfd442c6dfe5733701c')  # 16 字节
7
ct  = bytes.fromhex('0ffb5c8356bf6a0ea8e541fbc7f27aa00095f302dbc27b7e4842a500cfd9767b16c9fc8f7a8d420e8bd604b727a363fb')
8

9
# 创建一个 AES-CBC 解密器
10
cipher = AES.new(key, AES.MODE_CBC, iv)
11

12
# 解密
13
padded = cipher.decrypt(ct)
14

15
# AES 加密要求数据长度是 16 的倍数，所以加密前会填充（padding）
16
# 解密后需要去掉填充，恢复原始数据
17
c_rsa_bytes = unpad(padded, AES.block_size)
18

19
# 把字节转为一个大整数
20
c_rsa = int.from_bytes(c_rsa_bytes, 'big')
21

22
print(c_rsa)
23
# 输出: 24801123111312041315611103206161524142788727970567838474575269110507371838307

这个巨大的数字 c_rsa 就是 RSA 加密后的结果（第一层加密的输出）。

五、第三步：破解 RSA——分解 n#

5.1 RSA 基础（如果你不知道 RSA 是什么）#

RSA 是现在最常用的公钥加密算法。它的工作原理是：

选两个超大素数 p 和 q
计算 n = p × q（这个 n 是公钥的一部分，想破解 RSA 就要把 n 分解回 p 和 q）
计算 φ(n) = (p-1) × (q-1)
选一个 e（通常是 65537），计算 d = e⁻¹ mod φ(n)
加密：c = m^e mod n
解密：m = c^d mod n

关键点：如果不知道 p 和 q，就无法计算 φ(n)，也就无法计算 d，无法解密。RSA 的安全性建立在”大数分解很难”这个事实上。

5.2 分解 n#

题目中的 n 大约 256 位（约 77 个十进制数字），这个大小现代计算机是可以分解的。我们可以用在线工具 factordb.com 来分解。

把 n 输入 factordb，得到：

1
n = 319604865451981917438227037590936720137 × 339357623313190301253627442856667763273

所以：

p = 319604865451981917438227037590936720137
q = 339357623313190301253627442856667763273

验证：p × q = n √（自己乘一遍确认）

5.3 计算私钥 d 并解密#

有了 p 和 q，就可以计算私钥了：

1
p = 319604865451981917438227037590936720137
2
q = 339357623313190301253627442856667763273
3
n = p * q
4
e = 65537
5

6
# 计算 φ(n) = (p-1) × (q-1)
7
phi = (p - 1) * (q - 1)
8

9
# 计算私钥 d = e⁻¹ mod φ(n)
10
# pow(e, -1, phi) 是 Python 3.8+ 的写法，计算 e 在模 phi 下的乘法逆元
11
d = pow(e, -1, phi)
12

13
# 解密：m = c^d mod n
14
c_rsa = 24801123111312041315611103206161524142788727970567838474575269110507371838307
15
m = pow(c_rsa, d, n)
16

17
# 把大整数 m 转回字节（即 flag）
18
from Crypto.Util.number import long_to_bytes
19
flag = long_to_bytes(m)
20
print(flag)  # b'flag{crypto_1s_fun}'

六、完整解题脚本#

1
from Crypto.Cipher import AES
2
from Crypto.Util.Padding import unpad
3
from Crypto.Util.number import long_to_bytes
4

5
# ===== 第一步：ROT13 解码 IV =====
6
# IV 被 ROT13 编码过，字母移 13 位，数字不动
7
iv_enc = '6144s1oo1s1p7osq442p6qsr5733701p'
8
iv_hex = ''
9
for c in iv_enc:
10
    if c.isdigit():                         # 如果是数字，保持原样
11
        iv_hex += c
12
    elif 'a' <= c <= 'z':                   # 如果是小写字母，ROT13
13
        # ord('a') = 97，减 97 得到 0-25，加 13，取模 26，再加回 97
14
        iv_hex += chr((ord(c) - ord('a') + 13) % 26 + ord('a'))
15

16
# ===== 第二步：AES-CBC 解密 =====
17
key = bytes.fromhex('8c0c5db5efdd4505b1cd88569b6bf8f5')
18
iv  = bytes.fromhex(iv_hex)  # 解码后: 6144f1bb1f1c7bfd442c6dfe5733701c
19
ct  = bytes.fromhex('0ffb5c8356bf6a0ea8e541fbc7f27aa00095f302dbc27b7e4842a500cfd9767b16c9fc8f7a8d420e8bd604b727a363fb')
20

21
cipher = AES.new(key, AES.MODE_CBC, iv)     # 创建 AES-CBC 解密器
22
padded_data = cipher.decrypt(ct)            # 解密
23
c_rsa_bytes = unpad(padded_data, AES.block_size)  # 去除填充
24
c_rsa = int.from_bytes(c_rsa_bytes, 'big')  # 字节 → 大整数
25

26
# ===== 第三步：RSA 解密 =====
27
n = 108460347539116548233850259329362939266582518558734624388997849930646568128401
28
p = 319604865451981917438227037590936720137   # 从 factordb 分解 n 得到
29
q = 339357623313190301253627442856667763273
30
e = 65537
31

32
phi = (p - 1) * (q - 1)                    # 计算 φ(n)
33
d = pow(e, -1, phi)                        # 计算私钥 d
34
m = pow(c_rsa, d, n)                        # 解密
35
flag = long_to_bytes(m)                     # 大整数 → 字节
36

37
print(flag.decode())                        # 输出 flag

七、Flag#

1
flag{crypto_1s_fun}

八、核心知识点总结#

概念	一句话解释
ROT13	字母移动 13 位，加密解密是同一个操作
AES-CBC	对称加密，需要 key + IV 才能解密
IV	16 字节随机数，确保相同内容加密结果不同
RSA	公钥加密，安全性依赖大数分解困难
n = p × q	分解 n 得到 p 和 q 是破解 RSA 的关键
φ(n)	欧拉函数，RSA 中 φ(n) = (p-1)×(q-1)
d = e⁻¹ mod φ(n)	私钥是公钥 e 在模 φ(n) 下的乘法逆元
factordb	在线大数分解网站，对小规模 RSA 很有效

140128_task 题解（超详细版）#

你在看什么？#

这是一道 CTF 密码学题目的完整解答。题目涉及 RSA 加密和一个特殊的 hint。即使你第一次接触这类问题，本文也会从最基础的概念讲起，一步步带你理解解题过程。

一、先搞懂题目在说什么#

1.1 题目代码#

1
from Crypto.Util.number import *
2

3
nbits = 1024
4
p = getPrime(nbits)          # 生成一个 1024 位的素数 p
5
q = getPrime(nbits)          # 生成一个 1024 位的素数 q
6
n = p * q                    # RSA 的模数
7
e = 65537                    # RSA 的公钥指数
8
m = bytes_to_long(flag)      # 把 flag 字符串转成一个大整数
9
c = pow(m, e, n)             # RSA 加密：c = m^e mod n
10
hint = p ^ int(bin(q)[:1:-1], 2)   # 这是关键！一个提示信息
11

12
print(f"n = {n}")
13
print(f"e = {e}")
14
print(f"c = {c}")
15
print(f"hint = {hint}")
16

17
'''
18
n = 15506029124581759883731877010026678084317596564623845887899438092385502505788876763933964579361424109382021382231528496798732059024524482151713325171639486420457394941860866209473196191369593552699332037800406803188425744888879341669298117415522135256197760970433068295376433901825213472877775961650704735980110797478663530226550826927371472539708004955260217467349256084341561939393239965422086991362274959066287273337775441222341779953501432423374860117147450567097601484513951627635181267391943247398991455924080275444033891766100290675621003429909230692808817844612088084185283952020514285897020048017098285487607
19
e = 65537
20
c = 3404828797407616762356057717328373023632337739358306740074913353654682753878441781707680321614928566526027104942039703664029951473159370373414396427796575662072885942253508395714925320824108994494818019552089038861843245914594176758067401273263619855151412631121305316746504116601393720951436954904410743447522317796529783182597484907144278305759260804616925210823084069899530710204757384834603517279458503129155125367916881883415239168542343899364769463318925187623514473074347933245188732089331953708333419481376964544509315472577419374465938363973415564516515135968931067578017564025321585478866998020572475056104
21
hint = 35080869474740923288440667226139263766809663972741616010125167413870818807731263611720339202493658576179169864796373789589720908588556372613040136899161161977582187646286542111786933046030864726526268890301129489800434114004740826222610096433130207488091525467451311102574449006410417503469441144272955120060
22
'''

1.2 什么是 RSA？（最小必要知识）#

RSA 加密就像一个有锁的邮箱：

公钥 (n, e)：任何人都能用它把信锁进去（加密）
私钥 d：只有拥有者能用它开锁（解密）
n = p × q：锁的核心是两个大素数 p 和 q 的乘积
只要你能把 n 分解成 p 和 q，就能算出私钥 d，从而解密

1.3 hint 到底是什么意思？#

1
hint = p ^ int(bin(q)[:1:-1], 2)

拆开来看：

第一步：`bin(q)` 是什么？#

bin() 把数字转成二进制字符串。比如 bin(13) = '0b1101'（0b 是前缀，表示二进制）。

q 是一个 1024 位的素数，所以 bin(q) 是一个 1024+2=1026 字符的字符串：'0b + 1024 个 0/1。

第二步：`bin(q)[:1:-1]` 是什么？#

这是 Python 的切片操作 [start:stop:step]：

:1:-1 表示：从最后一个字符开始，倒着走（步长 = -1），到索引 1 停止（不包含索引 1）

索引 0 和 1 是 0 和 b。所以这个切片正好跳过了 0b 前缀，把剩下的 1024 个二进制位反转过来。

用例子说明（假设 q 只有 4 位，即 13）：

1
bin(13) = '0b1101'
2
索引:     012345
3

4
bin(13)[:1:-1]: 从末尾(索引5)倒着取到索引1(不包含)
5
                取: 索引5='1', 索引4='0', 索引3='1', 索引2='1'
6
                结果: '1011'

第三步：`int(..., 2)` 是什么？#

把二进制字符串转回整数。int('1011', 2) = 11（因为 1×8 + 0×4 + 1×2 + 1×1 = 11）。

所以在 4 位的例子中，rev(13) = 11。二进制 1101 反转后是 1011 = 11。

第四步：`p ^ ...` 是什么？#

^ 是 Python 的按位异或（XOR）操作符。对两个数的每一个二进制位做 XOR：

位 a	位 b	a XOR b
0	0	0
0	1	1
1	0	1
1	1	0

简单说：两个位相同得 0，不同得 1。

1.4 总结：题目给了什么约束？#

1
已知: n = p × q          （RSA 的公开模数）
2
已知: hint = p ⊕ rev(q)  （p 和 q 反转后的异或结果）
3
已知: e = 65537          （RSA 公钥指数）
4
已知: c                  （加密后的密文）
5
目标: 求 p 和 q，从而解密得到 flag

其中 rev(q) 表示把 q 的 1024 个二进制位前后反转。

二、为什么直接分解 n 行不通？#

这道题的 p 和 q 都是 1024 位的素数（约 308 位十进制数字）。n ≈ 2048 位（约 617 位十进制数字）。

这个规模远超过了现代计算机直接分解的能力（目前公开记录大约分解到 829 位的 RSA 模数）。所以不能用 factordb 之类的工具了。

必须利用 hint 提供的信息来恢复 p 和 q。

三、核心思想：逐位恢复 p 和 q#

3.1 比特位的”耦合”关系#

从 hint = p ⊕ rev(q) 可以推出一个关键关系：

1
p 的第 i 位 = hint 的第 i 位 ⊕ q 的第 (1023-i) 位

也就是说：

p 的低位取决于 q 的高位（因为反转：q 的高位变成了 rev(q) 的低位）
p 的高位取决于 q 的低位（因为反转：q 的低位变成了 rev(q) 的高位）

这叫”交叉耦合”——p 和 q 的低位和高位互相依赖，不能单独从一端开始推导。

3.2 已知的初始比特#

因为 p 和 q 都是 1024 位素数：

q[0] = 1：因为 q 是奇数（所有大于 2 的素数都是奇数），最低位（第 0 位）必须是 1
q[1023] = 1：因为 q 有 1024 位，最高位（第 1023 位）必须是 1
p[0] = 1：同理
p[1023] = 1：同理

从 hint 公式还可以推出：

1
p[0]    = hint[0] ⊕ rev(q)[0]    = hint[0] ⊕ q[1023]  = hint[0] ⊕ 1
2
p[1023] = hint[1023] ⊕ rev(q)[1023] = hint[1023] ⊕ q[0] = hint[1023] ⊕ 1

3.3 怎么推断更多比特？#

思路很简单：从两端同时往中间猜。

1
第 0 步：已知 q[0] 和 q[1023]
2
第 1 步：猜 q[1] 和 q[1022]，然后验证
3
第 2 步：猜 q[2] 和 q[1021]，然后验证
4
...
5
第 511 步：猜 q[511] 和 q[512]，然后验证

每步猜两个比特（4 种组合：00, 01, 10, 11），用两个约束条件来验证哪个是正确的。

四、两个验证条件（剪枝规则）#

4.1 低位约束（精确匹配）#

原理：两个数乘起来，结果的低位只由两个数的低位决定。

举个例子（十进制）：23 × 47 = 1081。只关心个位的话：3 × 7 = 21，个位是 1。不管高位是什么，个位只和个位有关。

二进制也一样：p 和 q 的低 k 位相乘，结果的低 k 位必须等于 n 的低 k 位。

1
(p 的低 k 位) × (q 的低 k 位) 的结果的低 k 位 == n 的低 k 位

写成公式（mod 2^k 意思是”只看低 k 位”，因为除以 2^k 的余数就是低 k 位）：

1
(p_low × q_low) mod 2^k == n mod 2^k

这个约束是精确的——只要有一点点不匹配，这个候选就一定错了。

4.2 高位约束（范围匹配）#

原理：两个数的最高几位相乘，结果接近但不超过 n 的最高几位。

为什么呢？看 n = p × q 的展开：

1
把 p 写成: p = p_hi × 2^m + p_lo    （p_hi 是高位，p_lo 是低位）
2
把 q 写成: q = q_hi × 2^m + q_lo
3

4
n = p × q = (p_hi × 2^m + p_lo) × (q_hi × 2^m + q_lo)
5
  = p_hi × q_hi × 2^(2m)                    ← 主要贡献
6
  + (p_hi × q_lo + q_hi × p_lo) × 2^m       ← 交叉项
7
  + p_lo × q_lo                             ← 低位乘积

当取 n 的高位（除以 2^(2m)）时，交叉项和低位乘积最多贡献 p_hi + q_hi 的”进位”。所以：

1
0 ≤ (n 的高 2k 位) - (p_hi × q_hi) ≤ p_hi + q_hi

这个约束是范围性的——不要求精确相等，只要求差值在合理范围内。

五、逐位搜索算法（BFS + 剪枝）#

5.1 算法流程（文字版）#

初始化：q = 2^1023 + 1（只有最高位和最低位是 1），k = 1（已有 1 对位确定）
把初始状态放入候选列表
循环（重复直到 k = 512，即所有 1024 位都确定）：
- 清空下一轮候选列表
- 对当前每个候选：
  - 尝试 q[k] = 0 或 1 和 q[1023-k] = 0 或 1 的 4 种组合
  - 用 hint 计算出对应的 p[k] 和 p[1023-k]
  - 检查低位约束：通过？继续；不通过？丢弃
  - 检查高位约束：通过？加入下一轮；不通过？丢弃
- 如果下一轮候选太多（> 500），按高位匹配度排序只留前 500
- 更新候选列表，k = k + 1
循环结束后，检查所有候选：p × q == n 的那个就是正确答案

5.2 为什么叫 BFS（广度优先搜索）？#

因为我们是一层一层地搜索。先把第 k 层的所有可能都找出来，再去第 k+1 层。这和在迷宫中一层层往外走是同样的道理。

5.3 为什么不会爆炸？（剪枝的作用）#

如果没有任何约束，每步有 4 种组合 × 上一步的候选数，候选数会以 4^512 ≈ 10^308 的速度增长——比宇宙中的原子还多。

但有了两个约束条件：

低位约束把大部分组合直接淘汰
高位约束进一步缩小范围
候选数失控时（> 500），只保留最可能的

实际运行中，候选数始终保持在 100 以下，总工作量约 100 万次检查，Python 跑几分钟就能完成。

六、代码中的关键优化：增量更新#

6.1 为什么要优化？#

如果不优化，每步都要重新计算 rev(q)——这需要遍历 1024 个比特位。在循环中做这件事等于每次多做 1024 次操作，严重拖慢速度。

6.2 如何增量更新？#

rev(q) 的增量更新：

当我们加入两个新比特 q[k] 和 q[1023-k] 时，在 rev(q) 中：

rev(q) 的第 k 位 = q 的第 1023-k 位（这不就是刚确定的吗？）
rev(q) 的第 1023-k 位 = q 的第 k 位（这也是刚确定的）

所以不需要重新计算整个 rev(q)，只要在原来的 rev_q 上把这两个位置设好就行：

1
rev_q_new = rev_q | (q_mk << k) | (qk << (1023 - k))
2
#                    ↑              ↑
3
#            q[1023-k] 放到 rev 的 k 位    q[k] 放到 rev 的 1023-k 位

p 的增量更新：

p = hint ⊕ rev(q)，所以当 rev(q) 变了，p 也要跟着变。原来：

p[k] 应该是 hint[k] ⊕ q[1023-k]
p[1023-k] 应该是 hint[1023-k] ⊕ q[k]

如果计算出的新值和旧值不同，翻转对应位：

1
# 如果 p 的第 k 位的新值不等于旧值，翻转它
2
if ((p_val >> k) & 1) != ((hint >> k) & 1 ^ q_mk):
3
    p_new ^= (1 << k)    # ^ 可以翻转单个位：0→1, 1→0

七、完整解题脚本#

1
from Crypto.Util.number import long_to_bytes
2

3
# ===== 题目数据 =====
4
n = 15506029124581759883731877010026678084317596564623845887899438092385502505788876763933964579361424109382021382231528496798732059024524482151713325171639486420457394941860866209473196191369593552699332037800406803188425744888879341669298117415522135256197760970433068295376433901825213472877775961650704735980110797478663530226550826927371472539708004955260217467349256084341561939393239965422086991362274959066287273337775441222341779953501432423374860117147450567097601484513951627635181267391943247398991455924080275444033891766100290675621003429909230692808817844612088084185283952020514285897020048017098285487607
5
hint = 35080869474740923288440667226139263766809663972741616010125167413870818807731263611720339202493658576179169864796373789589720908588556372613040136899161161977582187646286542111786933046030864726526268890301129489800434114004740826222610096433130207488091525467451311102574449006410417503469441144272955120060
6
e = 65537
7
c = 3404828797407616762356057717328373023632337739358306740074913353654682753878441781707680321614928566526027104942039703664029951473159370373414396427796575662072885942253508395714925320824108994494818019552089038861843245914594176758067401273263619855151412631121305316746504116601393720951436954904410743447522317796529783182597484907144278305759260804616925210823084069899530710204757384834603517279458503129155125367916881883415239168542343899364769463318925187623514473074347933245188732089331953708333419481376964544509315472577419374465938363973415564516515135968931067578017564025321585478866998020572475056104
8

9
NBITS = 1024    # p 和 q 都是 1024 位
10

11
# ===== 工具函数 =====
12
def get_bit(x, i):
13
    """取整数 x 的第 i 位（0 = 最低位）"""
14
    return (x >> i) & 1
15

16
def init_rev(q):
17
    """初始化 rev(q) —— 只设置已知的两个位（位 0 = q 的 MSB，位 1023 = q 的 LSB）"""
18
    rev_q = 0
19
    if get_bit(q, 0):           # q[0] = 1，放到 rev 的最高位
20
        rev_q |= 1 << (NBITS - 1)
21
    if get_bit(q, NBITS - 1):   # q[1023] = 1，放到 rev 的最低位
22
        rev_q |= 1
23
    return rev_q
24

25
# ===== 初始化候选 =====
26
q_init = (1 << (NBITS - 1)) | 1      # q = 2^1023 + 1 (只有 MSB 和 LSB 是 1)
27
rev_q_init = init_rev(q_init)         # rev(q) = 2^1023 + 1 (对称)
28
p_init = hint ^ rev_q_init            # p = hint ⊕ rev(q)
29

30
candidates = [(q_init, rev_q_init, p_init, 1)]  # (q, rev_q, p, k=已确定对数)
31

32
# ===== BFS 主循环 =====
33
for step in range(1, NBITS // 2):     # step 从 1 到 511
34
    new_candidates = set()             # 用 set 去重
35

36
    for q_val, rev_q, p_val, k in candidates:
37
        # 尝试 q[k] 和 q[1023-k] 的 4 种组合
38
        for qk in (0, 1):              # q[k] 的值
39
            for q_mk in (0, 1):        # q[1023-k] 的值
40

41
                # --- 增量更新 q ---
42
                q_new = q_val | (qk << k) | (q_mk << (NBITS - 1 - k))
43

44
                # --- 增量更新 rev(q) ---
45
                # rev(q)[k] = q[1023-k], rev(q)[1023-k] = q[k]
46
                rev_q_new = rev_q | (q_mk << k) | (qk << (NBITS - 1 - k))
47

48
                # --- 增量更新 p ---
49
                p_new = p_val
50
                # p[k] = hint[k] ⊕ q[1023-k]
51
                if ((p_val >> k) & 1) != ((hint >> k) & 1 ^ q_mk):
52
                    p_new ^= (1 << k)
53
                # p[1023-k] = hint[1023-k] ⊕ q[k]
54
                if ((p_val >> (NBITS - 1 - k)) & 1) != ((hint >> (NBITS - 1 - k)) & 1 ^ qk):
55
                    p_new ^= (1 << (NBITS - 1 - k))
56

57
                # ===== 检查约束 =====
58

59
                # 低位约束：(p_low × q_low) mod 2^(k+1) == n mod 2^(k+1)
60
                mask_low = (1 << (k + 1)) - 1          # 低 k+1 位的掩码
61
                p_low = p_new & mask_low
62
                q_low = q_new & mask_low
63
                if (p_low * q_low) & mask_low != n & mask_low:
64
                    continue    # 不通过，丢弃
65

66
                # 高位约束：0 ≤ n_hi - p_hi×q_hi ≤ p_hi + q_hi
67
                shift_top = NBITS - (k + 1)            # 右移量，保留高 k+1 位
68
                p_hi = p_new >> shift_top              # p 的高 k+1 位
69
                q_hi = q_new >> shift_top              # q 的高 k+1 位
70
                shift_n = 2 * NBITS - 2 * (k + 1)      # n 的对应移位
71
                n_hi = n >> shift_n                    # n 的高 2(k+1) 位
72
                prod = p_hi * q_hi
73
                if not (0 <= n_hi - prod <= p_hi + q_hi):
74
                    continue    # 不通过，丢弃
75

76
                # 两个约束都通过，加入下一轮
77
                new_candidates.add((q_new, rev_q_new, p_new, k + 1))
78

79
    # ===== 剪枝：候选太多时只保留最好的 500 个 =====
80
    if len(new_candidates) > 500:
81
        nc_list = list(new_candidates)
82
        # 按高位匹配度排序（差值越小越好）
83
        nc_list.sort(key=lambda x:
84
            abs((n >> (2 * NBITS - 2 * x[3])) - ((x[0] >> (NBITS - x[3])) * (x[2] >> (NBITS - x[3]))))
85
        )
86
        new_candidates = set(nc_list[:500])
87

88
    candidates = list(new_candidates)
89

90
# ===== 验证并解密 =====
91
for q_val, rev_q, p_val, k in candidates:
92
    if p_val * q_val == n:                          # 找到了！
93
        phi = (p_val - 1) * (q_val - 1)             # 计算 φ(n)
94
        d = pow(e, -1, phi)                         # 计算私钥 d
95
        m = pow(c, d, n)                             # 解密
96
        flag = long_to_bytes(m)                      # 大整数 → 字符串
97
        print(flag.decode())
98
        break

八、算法运行过程（实际数据）#

步数	候选数	说明
1	2	2 种可能
10	~10	约束开始生效
100	47	剪枝策略保持候选数可控
200	34	候选数在波动
300	42
400	74
500	83
511	61	最后一轮，61 个候选
最终	1	只有 1 个满足 p×q=n

这个过程量不算大，普通笔记本能在一分钟内跑完。

九、找到的 p 和 q#

1
p = 904128526061673680003166936997782157365873300871400393475801595378309234887137933
2
    199110209313730088000540340052588306931715181650504063078772026750438712112086013
3
    248025341784304300312736774657841992653808619644529310351900408081008496548263015
4
    23422892460364891880416873615758354556765590586662627258250184083
5

6
q = 171502487507224619194297010461826250695923309705395491120276133063231455398517208
7
    653922687432000303452387181110846761910520063595315766863862561666419686501779240
8
    914743017673926456677623397985057678737021154281158447040030501365754817928470048
9
    946327309984899736879000447870921328070213940980387089165997452429

十、Flag#

1
flag{4160r17hm1c_15_4150_1mp0r74n7!}

（Leet speak 解码为：algorithmic_is_also_important!，意为”算法思维也很重要”）

十一、为什么这道题叫”algorithmic”？#

因为这道题不能用工具直接分解（n 太大了），必须要自己写一个算法——用 BFS + 剪枝从 hint 中逐位恢复 p 和 q。这正是”算法思维”的体现。

十二、核心知识点总结#

概念	一句话解释
RSA	公钥加密，安全性依赖大数分解困难，n = p×q
XOR (⊕)	按位异或，相同得 0，不同得 1
rev(q)	把 q 的二进制位首尾反转
hint = p ⊕ rev(q)	p 和 q 的比特位交叉耦合的线索
BFS（广度优先搜索）	一层层地搜索所有可能的状态
剪枝（Pruning）	用约束条件淘汰不可能的分支
低位约束	p 和 q 的低位乘积必须精确匹配 n 的低位
高位约束	p 和 q 的高位乘积必须在 n 高位的一定范围内
增量更新	只更新变化的部分，避免重复计算全量 rev(q)

音乐

音乐

GDUT-2026密码学的ai的markdown

Crypto Challenge: DLP over Composite Modulus#

题目分析#

1. 分解模数 n#

2. 检查 p-1 和 q-1 的因子平滑度#

3. 分别求解 DLP#

3.1 模 p 部分：求解 DLP mod p#

3.2 模 p^5 部分：P-adic 提升（Hensel Lifting）#

3.3 模 q 部分：Pohlig-Hellman#

4. 结果#

5. 验证#

核心技巧总结#

double_crypto 题解（超详细版）#

你在看什么？#

一、题目给了我们什么？#

二、解题的整体思路#

三、第一步：修复被篡改的 IV（ROT13 解码）#

3.1 什么是 IV？#

3.2 IV 有什么问题？#

3.3 什么是 ROT13？#

3.4 解码实际操作#

四、第二步：AES-CBC 解密#

4.1 什么是 AES-CBC？#

4.2 用 Python 解密#

五、第三步：破解 RSA——分解 n#

5.1 RSA 基础（如果你不知道 RSA 是什么）#

5.2 分解 n#

5.3 计算私钥 d 并解密#

六、完整解题脚本#

七、Flag#

八、核心知识点总结#

140128_task 题解（超详细版）#

你在看什么？#

一、先搞懂题目在说什么#

1.1 题目代码#

1.2 什么是 RSA？（最小必要知识）#

1.3 hint 到底是什么意思？#

第一步：bin(q) 是什么？#

第二步：bin(q)[:1:-1] 是什么？#

第三步：int(..., 2) 是什么？#

第四步：p ^ ... 是什么？#

1.4 总结：题目给了什么约束？#

二、为什么直接分解 n 行不通？#

三、核心思想：逐位恢复 p 和 q#

3.1 比特位的”耦合”关系#

3.2 已知的初始比特#

3.3 怎么推断更多比特？#

四、两个验证条件（剪枝规则）#

4.1 低位约束（精确匹配）#

4.2 高位约束（范围匹配）#

五、逐位搜索算法（BFS + 剪枝）#

5.1 算法流程（文字版）#

5.2 为什么叫 BFS（广度优先搜索）？#

5.3 为什么不会爆炸？（剪枝的作用）#

六、代码中的关键优化：增量更新#

6.1 为什么要优化？#

6.2 如何增量更新？#

七、完整解题脚本#

八、算法运行过程（实际数据）#

九、找到的 p 和 q#

十、Flag#

十一、为什么这道题叫”algorithmic”？#

十二、核心知识点总结#

文章分享

音乐

文章目录

第一步：`bin(q)` 是什么？#

第二步：`bin(q)[:1:-1]` 是什么？#

第三步：`int(..., 2)` 是什么？#

第四步：`p ^ ...` 是什么？#