第九届西湖论剑·网络安全大赛（crypto篇）
如果有错误，请大家提醒我
01 - Yusa 的密码学课堂——PKCS#1
附件与 payload
附件： E:\DasCTF\正式赛\Crypto\10732-CRYPTO-01\attachment\Yusa的密码学课堂——PKCS#1的附件\tempdir\CRYPTO附件源码： source\extracted\task.py关键输入： source\extracted\PKCS#1.v1.5.enc、source\extracted\task.pyPayload： analysis\solve_pkcs1.py源码代码块：见文末 ### 01 - task.pyPayload 代码块：见文末 ### 01 PKCS#1
思路
题目使用三素数 RSA：n = p*q*r，但源码直接打印了 p。解密 AES 密钥时使用的 RSA 私钥模数其实是 q*r，并且源码最后打印了
pow(bytes_to_long(AES_KEY_ENC), d, q*r)
该值正是 PKCS#1 v1.5 编码块 00 02 || PS || 00 || AES_KEY 的整数表示。将它转成 256 字节后取最后 16 字节即可得到 AES key，再用 AES-ECB 解密密文 PDF。
运行
wsl.exe bash -lc "python3 '/mnt/e/DasCTF/正式赛/Crypto/10732-CRYPTO-01/analysis/solve_pkcs1.py'"
输出：
AES key: 44bfc33d0bfb3cd688a074a7adad1504
Recovered: .../analysis/recovered.pdf
恢复的 PDF 末页直接给出 flag。
Flag
DASCTF{6b3ed7dc3c1c6615fb97a7020922f7a5}
02 - How_many_rot_are_there
附件与 payload
附件： E:\DasCTF\正式赛\Crypto\10733-CRYPTO-02\attachment\How_many_rot_are_there的附件\tempdir\CRYPTO附件源码： source\extracted\tempdir\CRYPTO附件\task.pyPayload： analysis\solve.py源码代码块：见文末 ### 02 - task.pyPayload 代码块：见文末 ### 02 How_many_rot_are_there
思路
RSA 参数为 e = 65536 = 2^16。题目泄露
hint = (e*p + e^2)^q mod n
模 p 后，hint ≡ e^(2q) (mod p)。又因为 q ≡ n (mod p-1)，所以可以计算：
p = gcd(n, hint - pow(e, 2*n, n))
q = n // p
得到 p,q 后，密文分别在模 p、模 q 下做连续 16 次平方根，枚举根组合并 CRT 合并。正确明文以 QNFPGS{...} 开头，这是 DASCTF{...} 的 ROT13，因此最后对字符串执行 ROT13。
运行
wsl.exe bash -lc "python3 '/mnt/e/DasCTF/正式赛/Crypto/10733-CRYPTO-02/analysis/solve.py'"
关键输出：
root counts: 2 x 2
DASCTF{rabbits6sc5mpl8x6s9w6n6nc5mpl8x6s9w6n6nc5mpl8}
Flag
DASCTF{rabbits6sc5mpl8x6s9w6n6nc5mpl8x6s9w6n6nc5mpl8}
03 - llfsrr
附件与 payload
附件： E:\DasCTF\正式赛\Crypto\10742-CRYPTO-03\attachment\llfsrr的附件\tempdir\CRYPTO附件\llfsrr\llfsrr源码： source\extracted\tempdir\CRYPTO附件\llfsrr_inner\llfsrr\llfsrr.pyPayload： analysis\solve.sage源码代码块：见文末 ### 03 - llfsrr.pyPayload 代码块：见文末 ### 03 llfsrr
思路
这是 32 位 LFSR。已知明文前缀 DASCTF{，而密文满足 cipher_bit = plain_bit XOR output_bit，所以前缀可以恢复连续的 LFSR 输出比特。
对每个时刻，当前 32 位 state 与反馈 mask 的内积（GF(2)）等于输出比特。累计足够多的方程后，用 Matrix(GF(2), ...).solve_right(...) 直接求出 32 位反馈 mask，再从初始 state=1 重放整个密文。
运行
wsl.exe bash -lc "sage '/mnt/e/DasCTF/正式赛/Crypto/10742-CRYPTO-03/analysis/solve.sage'"
输出：
feedback mask: b0b53939
DASCTF{5e1996755a3811ef93ccc03c59457d50}
Flag
DASCTF{5e1996755a3811ef93ccc03c59457d50}
05 - number_inner / number
附件与 payload
附件： E:\DasCTF\正式赛\Crypto\10752-CRYPTO-05\source\extracted\tempdir\CRYPTO附件\number_inner\number关键输出： output.txt源码： source\extracted\tempdir\CRYPTO附件\number_inner\number\task.pyPayload： analysis\solve.sage源码代码块：见文末 ### 05 - task.pyPayload 代码块：见文末 ### 05 number_inner
思路
题目给出 x1 = m^p mod n，其中 m 只有 160 bit。模 p 时有 x1 ≡ m (mod p)，因此 m 是多项式 z-x1 在模 n 下的小根。用 Sage Coppersmith：
m = (z - x1).small_roots(X=2^160, beta=0.5)[0]
p = gcd(n1, x1 - m)
恢复 p 后，后续数据满足
r_i*x + t_i*b_i - s_i*k_i = 0 (mod q)
其中 b_i,k_i 只有约 480 bit。脚本构造加权嵌入格并 LLL，使用 nearest-plane 从约束中恢复 x,b_i,k_i。AES key 为：
sha256(str(2024*b0 + 2023*k0 + x).encode()).digest()[:16]
IV 为 SHA256(str(p))[:16]，最后 AES-CBC 解密并去 PKCS#7 padding。
运行
wsl.exe bash -lc "sage '/mnt/e/DasCTF/正式赛/Crypto/10752-CRYPTO-05/analysis/solve.sage'"
输出：
IV: 8076dd87467b159231123921f92dd39b
key: e0140084b9cda109eca9869167cb8d16
plaintext: DASCTF{b157059c-2871-421f-8cec-332b617de4d5}
Flag
DASCTF{b157059c-2871-421f-8cec-332b617de4d5}
06 - challenge（RSA 近似 phi 泄漏）
附件与 payload
附件： E:\DasCTF\正式赛\Crypto\10753-CRYPTO-06\source\extracted\tempdir\CRYPTO附件\challenge.py源码： source\extracted\tempdir\CRYPTO附件\challenge.pyPayload： analysis\solve.sage源码代码块：见文末 ### 06 - challenge.py（核心生成逻辑摘录）Payload 代码块：见文末 ### 06 approximate phi
思路
令 t = p+q-1，则 phi(n)=n-t。题目给出多组近似关系 X_i*t + w_i，这些值是 n 的倍数加上小误差。脚本把它们写成带 embedding 坐标的整数格：
row_i = n*e_i
last rows = (X_0,...,X_k,1,0), (w_0,...,w_k,0,n^0.86)
LLL 找到最后坐标为 n^0.86 的向量，从而得到 t。接着：
s = t+1 = p+q
Δ = s² - 4n
p,q = (s ± sqrt(Δ))/2
恢复 RSA 私钥 d = 65537^{-1} mod phi(n) 后直接解密 enc。
运行
wsl.exe bash -lc "sage '/mnt/e/DasCTF/正式赛/Crypto/10753-CRYPTO-06/analysis/solve.sage'"
输出：
p = 12200691529942889495830668295457182078521603703660491452285381700757295167461568004820942013215965563688817302760316154975158608059460538225320679314255097
q = 11380363748810811127979538969303596358591124434645487396373500007401636423879147226538991114977748871548442400582206693014874965914751388532037476032179079
flag = DASCTF{R4a11y_n4w_l1ttice!!!}
Flag
DASCTF{R4a11y_n4w_l1ttice!!!}
07 - RSA_E
附件与 payload
附件： E:\DasCTF\正式赛\Crypto\10762-CRYPTO-07\source\extracted\tempdir\CRYPTO附件\RSA_E.py源码： source\extracted\tempdir\CRYPTO附件\RSA_E.py第一阶段： analysis\solve.sage第二阶段： analysis\franklin_reiter.cpp源码代码块：见文末 ### 07 - RSA_E.pyPayload 代码块：见文末 ### 07 RSA_E - stage 1和### 07 RSA_E - stage 2
思路
这是两层 RSA。
内层 RSA 的私 exponent 很小。 solve.sage实现 Boneh-Durfee 格攻击：构造f(x,y)=x((n+1)/2+y)+1的移位多项式，LLL 后从两条独立关系的 resultant 中恢复d。用内层 d解密e_c，得到明文Congratulations_you_find_e_65003，因此外层 RSA 的公开指数是e=65003。外层给出两个相关消息/密文。 franklin_reiter.cpp在 NTL 中构造两条同模多项式并求 gcd，恢复共同消息根，转成 flag。
运行
第一阶段：
wsl.exe bash -lc "sage '/mnt/e/DasCTF/正式赛/Crypto/10762-CRYPTO-07/analysis/solve.sage'"
输出：
inner plaintext = Congratulations_you_find_e_65003
Run franklin_reiter.cpp with NTL to recover the related-message root.
第二阶段：
wsl.exe bash -lc "g++ -O3 -std=c++17 '/mnt/e/DasCTF/正式赛/Crypto/10762-CRYPTO-07/analysis/franklin_reiter.cpp' -lntl -lgmp -o /tmp/franklin_reiter && /tmp/franklin_reiter"
输出：
DASCTF{c89e370f-c7c9-47f6-9d2f-42e0837a21e5}
Flag
DASCTF{c89e370f-c7c9-47f6-9d2f-42e0837a21e5}
08 - matrix protocol
附件与 payload
附件： E:\DasCTF\正式赛\Crypto\10763-CRYPTO-08\source\extracted\tempdir\CRYPTO附件\chall.sage源码： source\extracted\tempdir\CRYPTO附件\chall.sagePayload： analysis\solve.sage源码代码块：见文末 ### 08 - chall.sagePayload 代码块：见文末 ### 08 matrix protocol
思路
协议公开了矩阵 A,T,S,G,F，且满足：
(A Q)^2 = A T
因此先计算 B=A*T，在 GF(p^2) 上求 3×3 矩阵平方根，再计算 Q=A^{-1}sqrt(B)。平方根有多个符号组合，利用题目给出的交换条件 QG=GQ 筛掉错误根。
同理对 E=A*T*A 与 F 求平方根得到 D，验证 DE D=F 和 DG=GD。最终：
K = D*S*D
mask = int(SHA256(str(sum(K)).encode()).hexdigest(), 16)
plaintext = ct XOR mask
脚本自行实现了商域上的 Tonelli-Shanks，并使用最小多项式分解和 CRT 组合矩阵平方根。
运行
wsl.exe bash -lc "sage '/mnt/e/DasCTF/正式赛/Crypto/10763-CRYPTO-08/analysis/solve.sage'"
输出：
flag = DASCTF{QAQ~4_Br0ken_Crypto_Sy5tem~TAT}
Flag
DASCTF{QAQ~4_Br0ken_Crypto_Sy5tem~TAT}
09 - approximate multiples
附件与 payload
附件： E:\DasCTF\正式赛\Crypto\10764-CRYPTO-09\source\extracted\tempdir\CRYPTO附件\tasks.py源码： source\extracted\tempdir\CRYPTO附件\tasks.py正确 Payload： analysis\solve.sageanalysis\solve.py是早期脚本；本文复现流程使用solve.sage。源码代码块：见文末 ### 09 - tasks.pyPayload 代码块：见文末 ### 09 approximate multiples
思路
题目给出四个近似倍数：
x_i = p*q_i + e_i
其中隐藏的 q_i 为约 1000 bit 素数，误差 e_i 只有 256 bit。四个 x_i 之间存在秩为 3 的整数关系。脚本构造：
[2^256 I | x]
并做 LLL，得到三条近似关系。三条关系的右核给出与 (q_0,q_1,q_2,q_3) 成比例的向量；除以 gcd 后恢复所有 q_i。最后：
p = round(x_i / q_i)
验证误差小于 2^256 后输出 p，即 flag 中的十进制内容。
运行
wsl.exe bash -lc "sage '/mnt/e/DasCTF/正式赛/Crypto/10764-CRYPTO-09/analysis/solve.sage'"
输出：
relation residual bit lengths: [586, 588, 585, 767]
p = 814717455548517808986181410586394354109647699929322981368461837445925965322205350796397641559934522652724773905724982591757228274565439544175507827688617021282332056672069056063857212371078735053697735921587690134019252689216497709
DASCTF{814717455548517808986181410586394354109647699929322981368461837445925965322205350796397641559934522652724773905724982591757228274565439544175507827688617021282332056672069056063857212371078735053697735921587690134019252689216497709}
Flag
DASCTF{814717455548517808986181410586394354109647699929322981368461837445925965322205350796397641559934522652724773905724982591757228274565439544175507827688617021282332056672069056063857212371078735053697735921587690134019252689216497709}
复核汇总
e=2^16 多重平方根 + ROT13 | ||
附录：完整 Payload 源码
以下代码块是 WP 引用的实际 payload 文件的完整内容；可直接保存为对应路径中的文件运行。
01 PKCS#1
路径：正式赛\Crypto\10732-CRYPTO-01\analysis\solve_pkcs1.py
from pathlib import Path
from Crypto.Cipher import AES
ROOT = Path(__file__).parents[1]
SOURCE = (
ROOT.parents[2]
/ "1"
/ "第九届西湖论剑·中国杭州网络安全技能大赛正式赛-附件"
/ "Crypto"
/ "10732-CRYPTO-01"
/ "source"
/ "extracted"
/ "task.py"
)
ENC = ROOT / "source" / "extracted" / "PKCS#1.v1.5.enc"
OUT = Path(__file__).with_name("recovered.pdf")
def main():
# The final numeric comment is pow(AES_KEY_ENC, d, q*r), namely the
# PKCS#1 v1.5 encoded message 00 02 || PS || 00 || AES_KEY.
leaked = int([line[2:] for line in SOURCE.read_text().splitlines()
if line.startswith("# ") and line[2:].isdigit()][-1])
encoded = leaked.to_bytes(256, "big")
assert encoded[:2] == b"\x00\x02"
aes_key = encoded[-16:]
plaintext = AES.new(aes_key, AES.MODE_ECB).decrypt(ENC.read_bytes())
assert plaintext.startswith(b"%PDF-")
OUT.write_bytes(plaintext)
print(f"AES key: {aes_key.hex()}")
print(f"Recovered: {OUT}")
if __name__ == "__main__":
main()
02 How_many_rot_are_there
路径：正式赛\Crypto\10733-CRYPTO-02\analysis\solve.py
import codecs
from math import gcd
E = 65536
HINT = int(
"101048855492044571417475830924088947184757234444475406804947498377420789778570832667138477666669908690663759417316798982038542431531087217671616502327573935462498550576600180793553880691247281813287212166428236802504214599757066100450668324529765827891463527861160593648623157792143035729770978865516948880313"
)
C = int(
"62214676810380175097525195047581624344610596576389901532958749194333175927146005969879818861882074690471600028484419966943711467342568120045965690332607166015419112255944582319675084071747302548088333383655637474764450810187215177625206094644430662667402073753343732910706186228919546522301643978766618493433"
)
N = int(
"131232786046474875167899992758388342524496883222860498694293714537118780151392850883679257361099172761516964104115167485944225089583991161038144993589322315250529302275646269196618503385962458635181473103926087951239559460161218447795578503981054097990206859884036249764383918404640987230150854235563692800669"
)
def sqrt_mod_prime(value, prime):
"""Return both square roots of a quadratic residue modulo an odd prime."""
if value == 0:
return (0,)
if pow(value, (prime - 1) // 2, prime) != 1:
return ()
if prime % 4 == 3:
root = pow(value, (prime + 1) // 4, prime)
return (root, prime - root)
odd_part = prime - 1
two_power = 0
while odd_part % 2 == 0:
odd_part //= 2
two_power += 1
non_residue = 2
while pow(non_residue, (prime - 1) // 2, prime) != prime - 1:
non_residue += 1
m = two_power
c = pow(non_residue, odd_part, prime)
t = pow(value, odd_part, prime)
root = pow(value, (odd_part + 1) // 2, prime)
while t != 1:
index = 1
power = t * t % prime
while power != 1:
power = power * power % prime
index += 1
factor = pow(c, 1 << (m - index - 1), prime)
root = root * factor % prime
c = factor * factor % prime
t = t * c % prime
m = index
return (root, prime - root)
def roots_of_power_of_two(value, exponent, prime):
roots = {value}
for _ in range(exponent.bit_length() - 1):
roots = {candidate for root in roots for candidate in sqrt_mod_prime(root, prime)}
return roots
def crt(left, right, p, q):
return (left + ((right - left) * pow(p, -1, q) % q) * p) % (p * q)
def main():
# hint == (e*p + e^2)^q (mod n). Modulo p this becomes e^(2q).
# As n = p*q and p == 1 (mod p-1), q == n (mod p-1).
p = gcd(N, HINT - pow(E, 2 * N, N))
q = N // p
assert 1 < p < N and p * q == N
roots_p = roots_of_power_of_two(C % p, E, p)
roots_q = roots_of_power_of_two(C % q, E, q)
print(f"root counts: {len(roots_p)} x {len(roots_q)}")
for root_p in roots_p:
for root_q in roots_q:
message = crt(root_p, root_q, p, q)
data = message.to_bytes((message.bit_length() + 7) // 8, "big")
if data.startswith(b"QNFPGS{") and data.endswith(b"}"):
print(codecs.decode(data.decode(), "rot_13"))
return
raise ValueError("Flag-shaped root not found")
if __name__ == "__main__":
main()
03 llfsrr
路径：正式赛\Crypto\10742-CRYPTO-03\analysis\solve.sage
ciphertext = "0110110010011011010100001001110010000010010110011010000011101000110010000110000111010000100000011001111100111000000000000101001100100010101101011111011000100011010110010100001110000111110010010011111010010001100011111101000100100010010000001001010100111011010011000010111001010001011100011001100010000010011011011111000"
# Each known LFSR output bit is a linear equation in the 32 mask bits.
# Given the output, the next state is known, so construct the rows online.
known = format(ord("D"), "b") + "".join(format(ord(ch), "08b") for ch in "ASCTF{")
state = 1
rows = []
rhs = []
for plain_bit, cipher_bit in zip(known, ciphertext):
output = Integer(plain_bit) ^^ Integer(cipher_bit)
rows.append([(state >> bit) & 1 for bit in range(32)])
rhs.append(output)
state = ((state << 1) & 0xffffffff) ^^ output
mask_bits = Matrix(GF(2), rows).solve_right(vector(GF(2), rhs))
mask = sum(Integer(mask_bits[bit]) << bit for bit in range(32))
print("feedback mask: %08x" % mask)
state = 1
plain_bits = []
for cipher_bit in ciphertext:
output = (state & mask).popcount() % 2
plain_bits.append(str(Integer(cipher_bit) ^^ output))
state = ((state << 1) & 0xffffffff) ^^ output
message = int(Integer("".join(plain_bits), 2)).to_bytes((len(plain_bits) + 7) // 8, "big")
print(message.decode())
05 number_inner
路径：正式赛\Crypto\10752-CRYPTO-05\analysis\solve.sage
import ast
import re
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
OUTPUT = "正式赛/Crypto/10752-CRYPTO-05/source/extracted/tempdir/CRYPTO附件/number_inner/number/output.txt"
data = open(OUTPUT).read()
n1 = Integer(re.search(r"^n = (\d+)", data, re.M).group(1))
x1 = Integer(re.search(r"^x = (\d+)", data, re.M).group(1))
# x1 = m^p (mod n1), so x1 == m (mod p); m is only 160 bits.
R.<z> = PolynomialRing(Zmod(n1))
m = Integer((z - x1).small_roots(X=2^160, beta=0.5)[0])
p = gcd(n1, x1 - m)
iv = sha256(str(p).encode()).digest()[:16]
print("IV:", iv.hex())
s = [Integer(value) for value in ast.literal_eval(re.search(r"^s = (.*)$", data, re.M).group(1))]
t = [Integer(value) for value in ast.literal_eval(re.search(r"^t = (.*)$", data, re.M).group(1))]
r = [Integer(value) for value in ast.literal_eval(re.search(r"^r = (.*)$", data, re.M).group(1))]
q = Integer(re.search(r"^q = (\d+)", data, re.M).group(1))
cipher = ast.literal_eval(re.search(r"^cipher = (.*)$", data, re.M).group(1))
count = len(s)
# r_i*x + t_i*b_i - s_i*k_i == 0 (mod q). The b_i/k_i values are
# 480-bit, while x is about q. Weight the residue coordinates so LLL
# selects a vector with all residues equal to zero.
weight = 2^1024
small_weight = 2^544
dimension = count + 1 + 2 * count
basis = []
for index in range(count):
row = [0] * dimension
row[index] = q * weight
basis.append(row)
row = [Integer(value) * weight for value in r] + [1] + [0] * (2 * count)
basis.append(row)
for index in range(count):
row = [0] * dimension
row[index] = t[index] * weight
row[count + 1 + index] = small_weight
basis.append(row)
for index in range(count):
row = [0] * dimension
row[index] = -s[index] * weight
row[count + 1 + count + index] = small_weight
basis.append(row)
reduced = Matrix(ZZ, basis).LLL(delta=0.99)
target = vector(ZZ, [0] * count + [3 * q // 4] + [3 * 2^478 * small_weight] * (2 * count))
# Sage 9.5 does not expose a Babai helper on IntegerLattice, so use the
# standard nearest-plane reduction directly on the LLL-reduced row basis.
real = RealField(4096)
row_vectors = [vector(ZZ, row) for row in reduced.rows()]
orthogonal = []
for row in row_vectors:
projected = vector(real, row)
for previous in orthogonal:
projected -= (projected * previous / (previous * previous)) * previous
orthogonal.append(projected)
remaining = vector(real, target)
closest = vector(ZZ, [0] * dimension)
for index in range(dimension - 1, -1, -1):
coefficient = ZZ(round(remaining * orthogonal[index] / (orthogonal[index] * orthogonal[index])))
closest += coefficient * row_vectors[index]
remaining -= coefficient * vector(real, row_vectors[index])
solution = None
for candidate in list(reduced.rows()) + [closest]:
for sign in [1, -1]:
candidate *= sign
value_x = Integer(candidate[count])
bs = [Integer(candidate[count + 1 + index] // small_weight) for index in range(count)]
ks = [Integer(candidate[count + 1 + count + index] // small_weight) for index in range(count)]
if q // 2 <= value_x < q and all(2^479 <= value < 2^480 for value in bs + ks):
if all((r[index] * value_x + t[index] * bs[index] - s[index] * ks[index]) % q == 0
for index in range(count)):
solution = (value_x, bs, ks)
break
if solution is not None:
break
assert solution is not None
x, bs, ks = solution
key = sha256(str(2024 * bs[0] + 2023 * ks[0] + x).encode()).digest()[:16]
plaintext = AES.new(key, AES.MODE_CBC, iv).decrypt(cipher)
print("key:", key.hex())
print("plaintext:", unpad(plaintext, 16).decode())
06 approximate phi
路径：正式赛\Crypto\10753-CRYPTO-06\analysis\solve.sage
#!/usr/bin/env sage
"""Recover the RSA modulus factors from noisy phi*x mod n leaks."""
import ast
import re
from pathlib import Path
CHALLENGE = Path(__file__).parents[1] / "source" / "extracted" / "tempdir" / "CRYPTO附件" / "challenge.py"
def published_value(name):
text = CHALLENGE.read_text(encoding="utf-8")
match = re.search(r"(?m)^# " + name + r" = (.+)$", text)
if not match:
raise ValueError("missing published " + name)
return ast.literal_eval(match.group(1))
n = Integer(published_value("n"))
xs = [Integer(x) for x in published_value("X")]
ws = [Integer(w) for w in published_value("XXX")]
enc = Integer(published_value("enc"))
# phi = n - t, t = p + q - 1. Thus X_i*t + w_i is an integer
# multiple of n plus an error smaller than d = n^0.86.
dimension = len(xs)
bound = Integer(n ** RR(0.86))
embedding = bound
rows = []
for i in range(dimension):
row = [Integer(0)] * (dimension + 2)
row[i] = n
rows.append(row)
rows.append(xs + [Integer(1), Integer(0)])
rows.append(ws + [Integer(0), embedding])
reduced = Matrix(ZZ, rows).LLL()
t = None
for vector in reduced.rows():
if abs(vector[-1]) == embedding:
candidate = abs(Integer(vector[-2]))
if candidate > 0:
t = candidate
break
if t is None:
raise RuntimeError("embedding vector not found; vary the embedding scale")
s = t + 1 # p + q
discriminant = s * s - 4 * n
root = isqrt(discriminant)
if root * root != discriminant:
raise RuntimeError("recovered value does not factor n")
p = (s + root) // 2
q = (s - root) // 2
assert p * q == n
phi = (p - 1) * (q - 1)
d = inverse_mod(65537, phi)
plaintext = Integer(pow(int(enc), int(d), int(n)))
flag = int(plaintext).to_bytes((plaintext.nbits() + 7) // 8, "big")
print("p =", p)
print("q =", q)
print("flag =", flag.decode())
07 RSA_E - stage 1
路径：正式赛\Crypto\10762-CRYPTO-07\analysis\solve.sage
#!/usr/bin/env sage
"""Solve RSA_E: Boneh-Durfee followed by a Franklin-Reiter attack."""
import re
from pathlib import Path
CHALLENGE = Path(__file__).parents[1] / "source" / "extracted" / "tempdir" / "CRYPTO附件" / "RSA_E.py"
text = CHALLENGE.read_text(encoding="utf-8")
def value(name):
match = re.search(r"(?m)^#?\s*" + name + r"\s*=\s*(\d+)\s*$", text)
if not match:
raise ValueError("missing " + name)
return Integer(match.group(1))
def boneh_durfee(public_exponent, modulus, delta=0.270, mm=6, tt=2):
"""Return the unusually short RSA private exponent using Boneh-Durfee."""
PR = PolynomialRing(ZZ, names=("x", "y"))
x, y = PR.gens()
A = (modulus + 1) // 2
polynomial = x * (A + y) + 1
XX = Integer(2 * modulus ** RR(delta))
YY = isqrt(modulus)
shifts = []
for kk in range(mm + 1):
for ii in range(mm - kk + 1):
shifts.append(x ** ii * public_exponent ** (mm - kk) * polynomial ** kk)
for jj in range(1, tt + 1):
for kk in range(floor(mm / tt) * jj, mm + 1):
shifts.append(y ** jj * public_exponent ** (mm - kk) * polynomial ** kk)
# The n^m constant shift can never encode a root; removing it avoids an
# unhelpful constant vector dominating the reduced basis.
shifts = [shift for shift in shifts if shift != modulus ** mm]
monomials = []
for shift in shifts:
for monomial in shift.monomials():
if monomial not in monomials:
monomials.append(monomial)
monomials.sort(key=lambda monomial: (monomial.degree(x), monomial.degree(y)))
basis = Matrix(ZZ, len(shifts), len(monomials))
for row, shift in enumerate(shifts):
for column, monomial in enumerate(monomials):
coefficient = shift.monomial_coefficient(monomial)
basis[row, column] = coefficient * monomial(XX, YY)
reduced = basis.LLL()
def reconstruct(vector):
result = PR(0)
for coefficient, monomial in zip(vector, monomials):
scale = monomial(XX, YY)
if coefficient:
result += (coefficient // scale) * monomial
return result
# Two independent nonconstant short relations have the common root
# (2*k, -(p+q)/2). The shortest vector itself may be a constant.
relations = [reconstruct(row) for row in reduced.rows()]
relations = [relation for relation in relations if relation.total_degree() > 0]
for left in range(len(relations)):
for right in range(left + 1, len(relations)):
first, second = relations[left], relations[right]
resultant = first.resultant(second, y).univariate_polynomial()
if resultant == 0 or resultant.degree() <= 0:
continue
for root, _ in resultant.roots():
root = Integer(root)
if root <= 0:
continue
# x = 2*k and e*d - k*phi = 1. Verify candidates later.
for y_root, _ in first(root, y).univariate_polynomial().roots():
y_root = Integer(y_root)
phi = 2 * (((modulus + 1) // 2) + y_root)
if phi <= 0:
continue
d = inverse_mod(public_exponent, phi)
if (public_exponent * d - 1) % phi == 0 and d.nbits() <= 290:
return Integer(d)
raise RuntimeError("Boneh-Durfee did not yield a private exponent")
inner_n = value("e_n")
inner_e = value("e_e")
inner_c = value("e_c")
n = value("n")
nn = value("nn")
c = value("c")
cc = value("cc")
inner_d = boneh_durfee(inner_e, inner_n)
recovered_e = Integer(pow(int(inner_c), int(inner_d), int(inner_n)))
hint = int(recovered_e).to_bytes((recovered_e.nbits() + 7) // 8, "big")
print("inner plaintext =", hint.decode())
# The plaintext explicitly reveals the exponent used by the second RSA.
e = 65003
print("Run franklin_reiter.cpp with NTL to recover the related-message root.")
07 RSA_E - stage 2
路径：正式赛\Crypto\10762-CRYPTO-07\analysis\franklin_reiter.cpp
#include <NTL/ZZ.h>
#include <NTL/ZZ_p.h>
#include <NTL/ZZ_pX.h>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace NTL;
int main() {
ZZ nn, n, c, cc;
conv(nn, "131077846729571191034786174968268020540664496824346422452459297864474645955379112117178639541857556845436516755887182161374188402081265714045647078572800331940546587903983232622220954912958437951329679115311024771532121638211796657046539645788501380187382822337026432982247316941339844876146196383520183619087");
conv(n, "80385730664777285961742751986194927974224573183573385505782927323084828500212022799582404100885133219868630357072797297844021086947361417681384499141731238407791623878101611077223493615482510697016598350264688509131659013650412161189655017879373627986858575377462236884088674660641837791868610983403065202413");
conv(c, "70310808721371541616307060709831828385731760272174192661532585617061937870999420495902023304817967786660092017059908366303600162581085179221648314339479192994638308143585592807680836073519145115386892468077124033957757478367491381013175698707554615927636166569153081650683459904970039192919552236837897749002");
conv(cc, "107108489485050943797347935142741800429559337229692953978219453389687636126030266569872176532772256275799421763491414457505814771033024446779195686448961662418875491204121350198365301806529080891405201956810039296881490127714815437778198930226347022749944359222669307080149948514664887407300714997720369188950");
ZZ_p::init(nn);
const long exponent = 65003;
ZZ_pX x, f, g, h, a_minus_x;
SetX(x);
SetCoeff(a_minus_x, 0, conv<ZZ_p>(n));
SetCoeff(a_minus_x, 1, -1);
power(f, x, exponent);
SetCoeff(f, 0, coeff(f, 0) - conv<ZZ_p>(c));
power(g, a_minus_x, exponent);
SetCoeff(g, 0, coeff(g, 0) - conv<ZZ_p>(cc));
GCD(h, f, g);
if (deg(h) != 1) {
std::cerr << "unexpected gcd degree " << deg(h) << std::endl;
return 1;
}
ZZ_p root = -coeff(h, 0) / coeff(h, 1);
ZZ message = rep(root);
std::vector<unsigned char> bytes(NumBytes(message));
BytesFromZZ(bytes.data(), message, bytes.size());
std::reverse(bytes.begin(), bytes.end());
std::cout.write(reinterpret_cast<const char*>(bytes.data()), bytes.size());
std::cout << std::endl;
}
08 matrix protocol
路径：正式赛\Crypto\10763-CRYPTO-08\analysis\solve.sage
#!/usr/bin/env sage
"""Break the matrix protocol by recovering Q from (A*Q)^2 = A*T."""
import re
from itertools import product
from hashlib import sha256
from pathlib import Path
CHALLENGE = Path(__file__).parents[1] / "source" / "extracted" / "tempdir" / "CRYPTO附件" / "chall.sage"
published = re.search(r'"""\n(.*?)\n"""', CHALLENGE.read_text(encoding="utf-8"), re.S).group(1)
p = Integer(re.search(r"p =\s*(\d+)", published).group(1))
Fp2.<i> = GF(p^2, modulus=x^2 + 1)
M = MatrixSpace(Fp2, 3, 3)
# The published values use Sage's field-element representation and are safe
# to evaluate after binding i to the generator of GF(p^2).
exec(published)
A, T, S, G = [M(value) for value in pk]
F = M(F)
B = A * T
def field_sqrt(value, order):
"""Tonelli-Shanks for Sage quotient fields which lack .sqrt()."""
field = value.parent()
if not value:
return field.zero()
if value ** ((order - 1) // 2) != 1:
raise ValueError("element is not a square")
twos, odd = 0, order - 1
while odd % 2 == 0:
twos += 1
odd //= 2
non_residue = field.gen()
offset = 0
while non_residue ** ((order - 1) // 2) == 1:
offset += 1
non_residue = field.gen() + field(offset)
c = non_residue ** odd
root = value ** ((odd + 1) // 2)
test = value ** odd
exponent = twos
while test != 1:
index, power = 1, test * test
while power != 1:
index += 1
power *= power
factor = c ** (2 ** (exponent - index - 1))
root *= factor
c = factor * factor
test *= c
exponent = index
return root
def matrix_square_roots(matrix):
"""Square root of a 3x3 matrix via its minimal-polynomial algebra."""
minimum = matrix.minpoly()
factors = minimum.factor()
roots = []
moduli = []
for factor, multiplicity in factors:
if multiplicity != 1:
raise RuntimeError("non-separable minimal polynomial")
extension = Fp2.extension(factor, "z")
root = field_sqrt(extension.gen(), p ** (2 * factor.degree()))
roots.append(PolynomialRing(Fp2, "x")(root.list()))
moduli.append(factor)
answers = []
for signs in product((-1, 1), repeat=len(roots)):
polynomial = CRT_list([sign * root for sign, root in zip(signs, roots)], moduli)
answer = sum((polynomial[index] * matrix ** index
for index in range(polynomial.degree() + 1)), M.zero_matrix())
assert answer * answer == matrix
answers.append(answer)
return answers
q_candidates = [A.inverse() * root for root in matrix_square_roots(B)]
q_candidates = [candidate for candidate in q_candidates if candidate * G == G * candidate]
if not q_candidates:
raise RuntimeError("could not identify Q")
Q = q_candidates[0]
assert Q * A * Q == T
E = A * T * A
for root in matrix_square_roots(E * F):
D = E.inverse() * root
if D * G != G * D:
continue
assert D * E * D == F
K = list(D * S * D)
key = sum(K[0]) + sum(K[1]) + sum(K[2])
mask = Integer(sha256(str(key).encode()).hexdigest(), 16)
plaintext = Integer(ct) ^^ mask
flag = int(plaintext).to_bytes((plaintext.nbits() + 7) // 8, "big")
print("flag = DASCTF{" + flag.decode() + "}")
09 approximate multiples
路径：正式赛\Crypto\10764-CRYPTO-09\analysis\solve.sage
#!/usr/bin/env sage
"""Recover the common divisor of the four DGHV approximate multiples."""
import re
from itertools import product
from pathlib import Path
CHALLENGE = Path(__file__).parents[1] / "source" / "extracted" / "tempdir" / "CRYPTO附件" / "tasks.py"
published = re.search(r'"""\n(.*?)\n"""', CHALLENGE.read_text(encoding="utf-8"), re.S).group(1)
xs = [Integer(line) for line in published.splitlines() if re.fullmatch(r"\d+", line)]
assert len(xs) == 4
rho = 256
eta = 768
bound = 2^rho
# q_i have size 1000 bits. Their rank-3 integer relation lattice has
# coefficients near 2^(1000/3). Any exact relation gives
# sum(a_i*x_i) = sum(a_i*e_i), which is only about 2^590.
coefficient_scale = 2^rho
lattice = Matrix(ZZ, [[coefficient_scale if row == column else 0
for column in range(4)] + [xs[row]]
for row in range(4)])
reduced = lattice.LLL()
relations = Matrix(ZZ, [[vector[index] // coefficient_scale for index in range(4)]
for vector in reduced.rows()])
print("relation residual bit lengths:", [abs(sum(row[i] * xs[i] for i in range(4))).nbits()
for row in relations.rows()])
# Three LLL vectors are independent q-relations. The one-dimensional right
# kernel is the primitive vector (q_0, ..., q_3).
kernel = relations[:3].right_kernel().basis()[0]
qs = [Integer(value) for value in kernel]
if any(value < 0 for value in qs):
qs = [-value for value in qs]
common = gcd(qs)
qs = [value // common for value in qs]
assert all(value.is_prime() for value in qs)
ps = [(value + divisor // 2) // divisor for value, divisor in zip(xs, qs)]
assert len(set(ps)) == 1
p = ps[0]
assert all(abs(value - p * divisor) < bound for value, divisor in zip(xs, qs))
print("p =", p)
print("DASCTF{" + str(p) + "}")
附录：核心源码
以下代码块为每题附件中的核心源码。第 6 题原始 challenge.py 主要由 69 KB 的常量输出组成，因此单独摘录生成逻辑，常量数据仍保留在附件文件中。
01 - task.py
源码路径：正式赛\Crypto\10732-CRYPTO-01\source\extracted\task.py
#!/usr/bin/env python2.7
from Crypto.Util.number import inverse,getPrime,bytes_to_long,long_to_bytes
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_v1_5,AES
from secret import hint
from os import urandom
def gcd(a,b):
while b:
a,b = b,a%b
return a
BITS = 1024
p = getPrime(BITS)
q = getPrime(BITS)
r = getPrime(BITS)
n = p*q*r
e = 0x3
hint = bytes_to_long(hint)
assert hint.bit_length() < BITS
hint_enc = pow(hint,e,n)
print("My gift for you: "+str(p))
print("hint_enc: "+str(hint_enc))
print("n: "+str(n))
with open("PKCS#1.v1.5.pdf","rb") as f:
data = f.read()
assert gcd(e,(q-1)*(r-1)) == 1
d = inverse(e,(q-1)*(r-1))
key = RSA.construct((q*r,e,d))
KEY = PKCS1_v1_5.new(key)
AES_KEY = urandom(16)
AES_KEY_ENC = KEY.encrypt(AES_KEY)
print("AES_KEY_ENC: "+str(bytes_to_long(AES_KEY_ENC)))
print(pow(bytes_to_long(AES_KEY_ENC),d,q*r))
A = AES.new(AES_KEY,AES.MODE_ECB)
ENCFILE = A.encrypt(data)
with open("PKCS#1.v1.5.enc","wb") as f:
f.write(ENCFILE)
# My gift for you: 147612801338322849336372804020042713889200260658658250281321148754923977621848092406213271730611643234599187709671298242281943415877821773850278928497761750345963119163320746829194054261413068986310037934255035583493524350058455093234690771095591840464014915933321899825441059533996418048402450423957127942583
# hint_enc: 31219309987806318855202923923652705875136543987738597559144952944603219852701491961029022534070616291804536311105660555375106897399355580711754918935751290725757284552594247179087605556033205176034226045813202640994020893165790060861352118316308881832907312443902559950242898606613714728528266995176412072527878628269642180762801982919428865735063405508069207651513436536953276224856983510372667463413644786602471346207865664895034374738304110116493271731792794026740001266027114981281023553628933223524790549289
# n: 1888485392347931742555276708543398419486868748132669765791937111451654147570995353961416158513445410755111363079058433943084150686336415180968052534926017073449878376596484136740581059489164616052504134704655201326190954434188356318366622141592025511416207796578506079684339441373127420961416080388154125758346582673066809789498718140984296615260714342755348929748530833500605555443339811685274501617370061106152093837326193827062354290863923634563029083113859344763620887581178372822646692533653235242747996031904880180014737927164012612495148029550139635771704312886930572366896209239274786814577984820908455698334816121170992317488960557661739312886877252495017362275464797544441125702997299276816976010832019679313779971949087198889193791977233767685881890681369618132608855585021962330176958135767147246282700155383446549841322757360029839015754755903736813467664783514944455353306887421062248353130462339893143947602771
# AES_KEY_ENC: 4588890414895509822209535365194595973298869448418294819980501843212066859947634687942172682894253064447184578739672911132349250143222108868603328264736633937004974366394732808421883706630507243670295128695059769322277498660410496323092458604732956188196497634363915512044048758095249006392569645410935887174435249419648615310266586040721809151546093289462564194827513904137071119516281595950638378142850793910863059806757921976601314560991461507660956050690711361631165759573106464332365610251198647359316617593601947765074296909531866478037541141355195435813324382734093323062326401192323881408828901943551158490038
# 986236757547332986472011617696226561292849812918563355472727826767720188564083584387121625107510786855734801053524719833194566624465665316622563244215340671405971599343902468620306327831715457360719532421388780770165778156818229863337344187575566725786793391480600129482653072861971002459947277805295727097226389568776499707662505334062639449916265137796823793276300221537201727072401742985542559596685092673521228140822200236743113743661549252453726123450722876929538747702356573783116366629850199080495560991841329893037292397105499226019760899853193278062243717512000415272209561906185887862944154882587563268
02 - task.py
源码路径：正式赛\Crypto\10733-CRYPTO-02\source\extracted\tempdir\CRYPTO附件\task.py
from Crypto.Util.number import *
from libnum import *
from gmpy2 import *
flag = b'******'
e = 65536
p = getPrime(512)
q = getPrime(512)
n = p*q
m = bytes_to_long(flag)
hint = pow((e*p + e**2), q , n)
c = pow(m, e, n)
print("hint=", hint)
print("c=", c)
print("n=", n)
print("p=", p)
print("q=", q)
'''
hint= 101048855492044571417475830924088947184757234444475406804947498377420789778570832667138477666669908690663759417316798982038542431531087217671616502327573935462498550576600180793553880691247281813287212166428236802504214599757066100450668324529765827891463527861160593648623157792143035729770978865516948880313
c= 62214676810380175097525195047581624344610596576389901532958749194333175927146005969879818861882074690471600028484419966943711467342568120045965690332607166015419112255944582319675084071747302548088333383655637474764450810187215177625206094644430662667402073753343732910706186228919546522301643978766618493433
n= 131232786046474875167899992758388342524496883222860498694293714537118780151392850883679257361099172761516964104115167485944225089583991161038144993589322315250529302275646269196618503385962458635181473103926087951239559460161218447795578503981054097990206859884036249764383918404640987230150854235563692800669
'''
03 - llfsrr.py
源码路径：正式赛\Crypto\10742-CRYPTO-03\source\extracted\tempdir\CRYPTO附件\llfsrr_inner\llfsrr\llfsrr.py
from Crypto.Util.number import *
from Crypto.Util.number import *
from os import urandom
from secret import flag
feedback_mask = *******
assert len(feedback_mask) <= 32
m = bytes_to_long(feedback_mask)
a = getPrime(512)
b = getPrime(512)
k = getPrime(32)
t = ((k+a)**4+(k+a)**3+(k+a)**2+(k+a)+231242352) % (a*b)
print('t = ', t)
print('ab = ', a*b)
# LFSR function
def llfsrr(state, feedback_mask):
next_state = (state << 1) & 0xffffffff
feedback = (state & feedback_mask) & 0xffffffff
xor_bit = 0
while feedback != 0:
xor_bit ^= (feedback & 1)
feedback >>= 1
next_state ^= xor_bit
return (next_state, xor_bit)
initial_state = 1
flag_as_long = bytes_to_long(flag)
binary_flag = bin(flag_as_long)[2:]
with open("key", "w+", encoding='utf-8') as key_file:
for bit in binary_flag:
current_bit = int(bit)
(initial_state, lfsr_output) = llfsrr(initial_state, feedback_mask)
key_file.write(str(current_bit ^ lfsr_output))
# t = 91382535280257427134645475292237370082014960334515793211075353297452528338087723860112500826044315845467866696617210023335073518286557543508973024219498337078664658414429832547727301006395271538112010076478786610620719945533602948865710425310086023764396885711302199872083882843343469761410625171475691201467
# ab = 108581219204181379968406768097000406760485946015874041061926288327189337067803660023783016802477064591575836196791927515457036336144887258713026071061767514656130657910150017352882598127439639684676273256839442573534485707623657551991097483458113034891615193028029470001702625456268539470045114945318927654937
05 - task.py
源码路径：正式赛\Crypto\10752-CRYPTO-05\source\extracted\tempdir\CRYPTO附件\number_inner\number\task.py
from Crypto.Util.number import *
import os
from hashlib import *
from random import *
p = getPrime(512)
q = getPrime(512)
n = p*q
m = bytes_to_long(os.urandom(20))
x = pow(m,p,n)
y = pow(m,q,n)
with open('output.txt', 'w') as file:
file.write('n = ' + str(n) + '\n')
file.write('x = ' + str(x) + '\n')
file.write('y = ' + str(y) + '\n')
iv = sha256(str(p).encode()).digest()[:16]
n = 17
q = getPrime(1024)
x = randint(q//2,q-1)
S = 2**544
K = 2**480
s = [randint(S//2,S-1) for i in range(n+1)]
t = [randint(S//2,S-1) for i in range(n+1)]
k = [randint(K//2,K-1) for i in range(n+1)]
b = [randint(K//2,K-1) for i in range(n+1)]
r = [(s[i]*k[i] - b[i]*t[i]) * inverse(x,q) % q for i in range(n+1)]
with open('output.txt', 'a') as file:
file.write(f"s = {s}\n")
file.write(f"t = {t}\n")
file.write(f"r = {r}\n")
file.write('q = ' + str(q) + '\n')
key = sha256(str(2024*b[0]+2023*k[0] + x).encode()).digest()[:16]
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from uuid import *
from flag import flag
aes = AES.new(key,AES.MODE_CBC,iv)
cipher = aes.encrypt(pad(flag.encode(),16))
with open('output.txt', 'a') as file:
file.write(f"cipher = {cipher}")
07 - RSA_E.py
源码路径：正式赛\Crypto\10762-CRYPTO-07\source\extracted\tempdir\CRYPTO附件\RSA_E.py
from Crypto.Util.number import *
from gmpy2 import *
from libnum import *
from secret import flag
m = bytes_to_long(flag)
size(e_d) = 276
size(e_n) = 1024
e_c = pow(e, e_e, e_n)
print(f'e_n = {e_n}')
print(f'e_e = {e_e}')
print(f'e_c = {e_c}')
p = getPrime(512)
q = getPrime(512)
n = p * q
pp = getPrime(512)
qq = getPrime(512)
nn = pp * qq
c = pow(m,e,nn)
cc = pow(n-m,e,nn)
print('n = '+ str(n))
print('nn= '+ str(nn))
print('c = '+ str(c))
print('cc = '+ str(cc))
'''
e_n = 115492797439504383499316789087564855277202276993914396940612462105690325303558598961706823643279927219244680600342228187979029716193733881668587240508756170029604463972172604593855336781585589234031030649601280647502536698928394780022705858885481209420839357682298617690280666435139405046804423055376878450607
e_e = 83015035348786159111042059826917339120202290969382724146248733130869544045042674918766280681166748211969282456252952695587153465788828540953299151305200582232154203769401467882501993126551703604018003398791427788229441096964289448577881837556333707237639163111639711103859725193478604363695828097082617304715
e_c = 85611408356925163919462298169089009462271705377529102512660341527647253765697540404347655862618734565892053591206318165238272929137619968338300174889937394337634501729621937430171541091106939500041524911322541552541161669848574042067541586389568275002269001838865923511116796622042187813658408056616018207686
n = 80385730664777285961742751986194927974224573183573385505782927323084828500212022799582404100885133219868630357072797297844021086947361417681384499141731238407791623878101611077223493615482510697016598350264688509131659013650412161189655017879373627986858575377462236884088674660641837791868610983403065202413
nn = 131077846729571191034786174968268020540664496824346422452459297864474645955379112117178639541857556845436516755887182161374188402081265714045647078572800331940546587903983232622220954912958437951329679115311024771532121638211796657046539645788501380187382822337026432982247316941339844876146196383520183619087
c = 70310808721371541616307060709831828385731760272174192661532585617061937870999420495902023304817967786660092017059908366303600162581085179221648314339479192994638308143585592807680836073519145115386892468077124033957757478367491381013175698707554615927636166569153081650683459904970039192919552236837897749002
cc = 107108489485050943797347935142741800429559337229692953978219453389687636126030266569872176532772256275799421763491414457505814771033024446779195686448961662418875491204121350198365301806529080891405201956810039296881490127714815437778198930226347022749944359222669307080149948514664887407300714997720369188950
'''
08 - chall.sage
源码路径：正式赛\Crypto\10763-CRYPTO-08\source\extracted\tempdir\CRYPTO附件\chall.sage
from Crypto.Util.number import *
from hashlib import sha256
from secret import flag
m = bytes_to_long(flag)
def enc(pt, G, A, T, S, p):
s = randint(0,p-1)
D = G^s
E = A*T*A
F = D*E*D
K = list(D*S*D)
key = sum(K[0])+sum(K[1])+sum(K[2])
mask = int(sha256(str(key).encode()).hexdigest(),16)
ct = pt ^^ mask
return ct, F
def dec(ct, Q, F, p):
K = Q*F*Q
key = sum(K[0])+sum(K[1])+sum(K[2])
mask = int(sha256(str(key).encode()).hexdigest(),16)
pt = ct ^^ mask
return pt
p = getPrime(256)
Fp2.<i> = GF(p^2, modulus=x^2+1)
M = MatrixSpace(Fp2, 3, 3)
while True:
Q = M.random_element()
A = M.random_element()
if Q*A != A*Q:
break
T = Q*A*Q
S = T*A*T
r1 = randint(0,p-1)
G = Q^r1
pk = (list(A), list(T), list(S), list(G))
ct, F = enc(m, G, A, T, S, p)
print("p = ",p)
print("pk = ", pk)
print("F = ", list(F))
print("ct = ", ct)
"""
p = 72887242108660141996862343556330151015969690949835567252527194788428065480383
pk = ([(17721183402259872020800275954210023274983052570120081248291897425608931477093*i + 32398110280895896734010284949974832063887503132353681078977206899204202173789, 54531634495057046991515273558305428867102201405617856305008554208336946545276*i + 53559176432820530464958340934397135653021175198597495321065224929188410347695, 27719945502856754481236098196014205483081586087367078493933408080194499938927*i + 1450628736387393873166171805424299538505476789523674611289973478290718453200), (57242423786686483363839647362581564383925732392730073374546590355998555747077*i + 573726326354574516128249317235875704460857319673337707555095009277545125755, 33631043256657770245013631632455702904903259491780484310654749784948198388976*i + 17344746653834202604930860577508757708688427949046279718508635007113840369042, 37771390186920740637371383242878514021347606565375600086363978842439775164973*i + 60264754185911116825495147907207494752330900415794996812483089251259003404228), (1163730453993018743008743150834548760986076138562570206571825145859591284352*i + 69245390362211526197537288211735612650619880945856387683074182933575799994162, 11137807706588795799057940108843238078078690609437386007163034291855328303661*i + 50795522649623533714787572047531722836395032085224035511036953078383612475598, 14354786571703727534706086386589187674076604263117377684131521866407943036307*i + 63028649680815097939155846824928638616844025040257105384123424769274942520895)], [(22137116252880790433838296157765927318220905592359967466680754349755815464341*i + 35503968364379821899511866562472775961434113516937033217642581531414863539290, 38346074307552448152239080224505166810289185210503265380269711384969731945517*i + 9333819647786551924409858116441570177115099865486742684028611902450000042407, 24608192510515673607042276468532809071945836783394960695059783085937608049755*i + 27099766371861599260580052331632986107092105438254563604629919595057370886149), (57539731529782952718529369617033412770127782205874818027724894673104814770991*i + 12431864123786174601413168140961685219607645783666490625760143190724674574386, 33510082449726132893492104159133966168598115972734064630878005553829725389082*i + 30594711977745700371548334707069524826346332947574826081979927125841475148328, 8911862104171403632946802970568635607253840071000107875759139060453368618583*i + 51594672749496705581452789883241278156858476777167382827032876227546058970732), (58105830161247358431125768499050987088161417325586965601350797391396603985470*i + 10949064084676782939947256128733523229613253182051362970560478801614590446300, 6665352489343222248969975791152178151760060704226637217535985452272551528693*i + 16163109497937280055564868323730465088174193174761590036929535644203224067166, 26147088265849488467397913386934580340556987670869413865359802108333761377560*i + 14170094609019059182842713618319151553137248441974849089555832123638494739417)], [(60066006389024369318961505483331049048095679333675437984483948643792214278503*i + 67617085525047580942273623886038114942547589259839196477555874755427651308048, 38692305959834079988532869421062338838072016075793686080934562521314366274998*i + 21104829450473981189549299039898127784065322316764325995863199136802573514, 7207625628360021282792621977024027446511231977201394776410095364976996279450*i + 23039079766688651678553952766794875180844089420934577132338235904018762773928), (10808368042897084491009063074724200907600038030639153659288985642861405920614*i + 33955795465220353002933680692690511153845418737513482128237117905262919879043, 21645210772494061734726430463955231707074915293749580279327741388687068110310*i + 62225984739450865202997071369617271241348810092608626482294704825641320606694, 14572118842071162051223076904993643512402905544627821044103215186921277812496*i + 63504547636870837320642724540312613748726280369811190421219651308407770510674), (6529211642735966744323364626486352288002532267939478445216264742350974653419*i + 43426895500365913698127867498420593427453574994051597107529725996420257433857, 66636149494607064863031794353485502915121295051850619450321561966293398587284*i + 51049172134567530748763269555600518661288880531459625871071308764595168859033, 42297258788816007263333796194491196601979606573843177791726417124128570106777*i + 45527674821983322767637713856131638914194577467349514130179266972864796164733)], [(47645610858583239528541540288030905132801730740336899517917521534427703920375*i + 13272393664089987551368548207128885229248289454405159277755757369580866096516, 60503024931869977830369448001966194434192750710631225090391559259672930497207*i + 22742672333325631628906219543935772962495637869131049729874762344108069789046, 18239371575343144081671835175136676417172797381923442300525086630600561560114*i + 53605095942301227312866863441233162082087535371838738595931070092230378325532), (49652795839344946948771531270341537200526957150620826334216871981974859849848*i + 72788891932812016325514298655742330969740202920835574638161526839627026310392, 58465406030985457122487065262985150103086610852826560192123766406670919681919*i + 41631921368744416558173670147590406285376603436284660888096365325833457519047, 2867068797023070369258694926242485369317317985428997150826022662547346928319*i + 199536555238705400453079146297641296197748614855192340202929119323998667173), (19319782936524636558881137449470396788888469756320580071801690941326971557928*i + 34694728896207512382372151140975478616355941017631874070450334268575015485538, 60420266086997924618637147844041161464210208935194926422677077391866663978425*i + 13672363312837218411993834816309940812825734002380106434784905443915361955247, 56317025568717741728727542740124505299029374963112095990350877412868385510001*i + 56960621295573230601502052571104746367180500789238336757504091383665514782189)])
F = [(36081831373398765496490121898118275331597167308301671911642273861563666664545*i + 20818485079783326431414952124332440995164298376805349071762867760925654560129, 2080527476644284459469754065728582261439110792635520661740429151724797376184*i + 22485923248080983391383279592637691489160934672854638306617785344436031827838, 15544373162545014827602222261755865080947187122261471926061663568794038512828*i + 65994932829738499994169748656063604384011854387402875895186473718226656419067), (3553534440103543686958858303956716887328727627636404431097647427819509340361*i + 41182149981825439188243414995474733005799065992663037326956422731949977723727, 11444151159046255413538671703716370245288291793592500278345001664024824339590*i + 1802783416049323926195923226865768221398255563865542946492803065162093093803, 15739175840903697568714274177182938758189586472507039731239155962622285528109*i + 38249065906628598713138583591858150126778794837077688369911160900556744463900), (14364753807737302773559096493138893453118094354943941768609481298414054855231*i + 16290236676179704559365899211744462983770375364688247022596145726641137243214, 3863306473986430132042752882629555431418515741358351198972027547882636615940*i + 1209446834271293681961506708684952401569936830292701272655835127315444154958, 21868026584808712490812183410257662299067350008298604021123682243508255905173*i + 12828201007038003022201361213007595366913298546122923089499182187938898042596)]
ct = 96910798667771988374291172958072220832574586618080134344021393928577220469428
"""
09 - tasks.py
源码路径：正式赛\Crypto\10764-CRYPTO-09\source\extracted\tempdir\CRYPTO附件\tasks.py
from Crypto.Util.number import getPrime, getRandomRange
def gen(k:int, gamma: int, eta: int, rho: int):
xs = []
qs = []
es = []
p = getPrime(eta)
for _ in range(k):
q = getPrime(gamma - eta)
e = getRandomRange(-pow(2, rho-1) + 1, pow(2, rho-1) - 1)
qs.append(q)
es.append(e)
xs.append(p * q + e)
return p, qs, es, xs
k = 4
eta = 768
gamma = 1000 + eta
rho = 256
p, qs, es, xs = gen(k, gamma, eta, rho)
print(p)
for x in xs:
print(x)
"""
7286602644894347905698877185006886062766603336098651145708618257426896498601438194818405176376998357154846239925108795918211744886731571266744871908463835351995189784312085830285088365342080806811314047882453402592133074499069282870744236160215512216478789267594028132748508140080189837224089073913522991827904722259140858601642592466315776021315586438508197663608590812749450817365064347439560883042009204050351693713820588889060849655679914847278675752145553961823946981967169055185529737402521407509263021789077125016742255715760
5230952259217719373451288600605694729007492237169927997823214951918450708970497355235418799314073627589124050832789070592194142892137496197782948844507440729494129127326826986001351848921996887252514377638280576136864865587600778883326741625167048874313825133026683820914940523608112111525189712638841735445342804486682657815023936771511350194415118747576763915047759919721983363867337811246200882629774305946208917774071048260034384488337583881876926649372038650806406479863141932268756290007122767070707541568217633666823942767630
6634396750920568285608095346195329118689097605994669634518316951192506731923068736273476052320642960726963932454848348066913054010051606781532862880707753022193473836326795829631429615685808176184842533562632931011621810840291571855376807721443083529317792844472049240727433533493468591987710033174905312247446273166915934371589745530975428330655972863314230695429710915699801228301493075605786710443768747383021956670013493099376120239576125225920151034511467122583704756994064073049424978126007943448882667862038745782477628408003
5206967518961960112660221968771713864784691153181370679825018817838185859421615186098940654940704354246503769468859488659689494119991783464734247926184421441233523723102514720513272413216800777125028472595562428391474002300021110853098159434700293331046532929525141162455736314162160456306022511785772125837018470201639642987557826155895644564724745314165471429499074795110110906392223770428469036209454246746770408469494816865235942622698472278595153047673886819995225231883995391098290313071949911543891398398297286813045525879691
"""
06 - challenge.py（核心生成逻辑摘录）
源码路径：正式赛\Crypto\10753-CRYPTO-06\source\extracted\tempdir\CRYPTO附件\challenge.py。原文件中其余部分是题目发布的 110 组常量数据。
from Crypto.Util.number import *
from flag import flag
p, q = [getPrime(512) for _ in range(2)]
n = p*q
d = int(n ** (1 - 0.14))
phi = (p - 1) * (q - 1)
X = [getRandomRange(1, n - 1) for _ in range(110)]
XX = [phi * x // n for x in X]
XXX, i = [], 0
while True:
w = getRandomRange(phi * X[i] - XX[i] * n - d,
phi * X[i] - XX[i] * n + d)
if abs(phi * X[i] - XX[i] * n - w) < d and w < n:
XXX.append(w)
i += 1
if i == 110:
break
m = bytes_to_long(flag)
e = 65537
enc = pow(m, e, n)
print(f"n = {n}")
print(f"X = {X}")
print(f"XXX = {XXX}")
print(f"enc = {enc}")