首先声明，这个系列所分享的“好题” 仅代表我个人在解这道题时可能觉得这道题某一个知识点很有趣；或是很新颖；或是出题人对这道题各个知识点的衔接处理的很好，而不是单纯套娃；或是看了出题人的题解觉得特别优雅，或是觉得自己的解法很妙…… 但并不保证这道题目的实时性、原创性，可能我看到这道题的时候它已经是被抄袭过的，但我并没有遇到过原题。（题好，但不对比赛给予评价）另外为了避免纯粹的拿来主义，以给读者一定的思考、操作空间，这个系列也不会直接给出完整的解题 exp，大家自己也多试试叭！
今天这道题目来自 2023 江苏省数据安全竞赛 – hardrsa
from Crypto.Util.number import *
from random import randint
from secret import message
p, q = [getPrime(1024) for _ in range(2)]
n = p * q
def pad(msg: bytes) -> bytes:
return msg + long_to_bytes(len(msg) & 0xff) * (2048 // 8 - len(msg) - 1)
def f(x: int, poly: list[int]) -> int:
return sum([
poly[i] * pow(x, i, n) for i in range(len(poly))
]) % n
def commit(m: int, d: int, key: int, poly: list[int]) -> (int, int):
sig = pow(m, d, n)
c1 = (sig + pow(key, 8, n) + pow(key, 4, n) + pow(key, 2, n)) % n
c2 = f(key, poly)
return c1, c2
def reveal(comm: (int, int), e: int, key: int, poly: list[int]) -> int:
c1, c2 = comm
assert f(key, poly) == c2
sig = (c1 - pow(key, 8, n) - pow(key, 4, n) - pow(key, 2, n)) % n
return pow(sig, e, n)
def part1(msg):
e = 233
assert GCD(e, (p - 1) * (q - 1)) == 1
m = bytes_to_long(pad(msg))
c = pow(m, e, n)
print(f"# Part1: RSA-Encrypted Ciphertextn"
f"{e = }n"
f"{n = }n"
f"{c = }n")
def part2(msg):
e = getPrime(256)
assert GCD(e, (p - 1) * (q - 1)) == 1
d = inverse(e, (p - 1) * (q - 1))
key = getPrime(1024)
poly = [randint(n // 2, n) for _ in range(8)]
m = bytes_to_long(msg)
comm = commit(m, d, key, poly)
print(f"# Part2: RSA-Committed Promisen"
f"{e = }n"
f"{n = }n"
f"{poly = }n"
f"{comm = }n")
part1(message)
part2(message)
题目有两部分，第一部分使用 RSA 加密了 message，并给出了参数
第二部分是一个魔改了的 RSA 的承诺方案，
使用未知的 key ，给出 ，
使用已知的 poly，给出
直观上感觉就是利用 和 poly 恢复出 key 然后再结合 搞出 来，然后计算一下 就可以了。但是实际上好像没那么容易，key 并不是那么容易恢复的。
我们还注意到加密 message 用的 ，如果能直接给 的每项升个 次，也能有 出来，但后面的 也没办法处理。
思路就此卡住了。
赛后问了群友，@春哥 又拿去问了@maple，maple 立刻给出了一种很新我没见过的奇妙解法。
问了学弟 @冰，也想出了一种解法。
最后机缘巧合之下问到了出题人，预期解和学弟的这种解法比较接近。
下面我对这两种解法做一个简要的介绍。
解法一（预期）
注意到我们有以下三个式子
三条式子摆在这，显然是有把 3 式带到 2 式的冲动的，如果把 m 代进 ，这样 和 就只有一个公共的未知量 ，使用结式应该就能把这个 给求出来了。
但是如果直接代进去的话， 的 degree 会太高，所以这里我们还需要优化一下，考虑到 ，即 ，我们知道在模 下满足的式子一定在模 下成立，因此我们把 带进 后再模一个多项式 ， 的度就低于 ，然后再让其和 做结式应该就能求出 了。（由于 式中有一个 pad，所以实际上还需要小小的爆破一下）（PS：自己实现一个模多项式快速幂比在 sagemath 中用 quotient 要快很多）
from copy import deepcopy
# Part1: RSA-Encrypted Ciphertext
e1 = 233
n =
c =
# Part2: RSA-Committed Promise
e2 =
n =
poly = []
comm = ()
R.<x,s>=PolynomialRing(Zmod(n)) # 这里的一个 s 变量看着没用，其实是为了让 f(x) 的类为一个多变量多项式，这样才能用后面的 Ideal
f1 = 0
for i in range(len(poly)):
f1 += poly[i]*x^i
f1 -= comm[1]
# 求 m 模 f1 下的 e 次
f = comm[0]-x^8-x^4-x^2
F = 1
for i in bin(e2)[2:][::-1]:
if i == '1':
F = (F*f)%f1
f = (f*f)%f1
from Crypto.Util.number import *
for i in range(1,255):
print(i)
f = deepcopy(F)
# 爆破一下填充，带入 f2，求 233 次
f = f*256^(255-i)+bytes_to_long(long_to_bytes(i)*(255-i))
FF = 1
for i in bin(e1)[2:][::-1]:
if i == '1':
FF = (FF*f)%f1
f = (f*f)%f1
f2 = FF-c
# 求 f1 和 f2 的结式，得到 (x-k)
ans=Ideal([f1,f2]).groebner_basis()
if ans != [1]:
print(ans)
break
85%|██████████████████████████████████████████████████████████████████████████████████████████████████████▌ | 217/254 [01:09<00:10, 3.47it/s][x + 11804593083540766953191768473584891632857464298610295673456410319093405751966708262984066641796004658380825990723088997287209884308749055923966759203552497405777188930982989535372734594928432767182748217929177897158889489317608554405915470112027996617864702664597137007278287666634774284031478676422259138168270660452037808633419847474475483128590811499676324666087197259465241042751682326546155170750087186789218676468094424397026064636516349145483400088735735646407761831516062003605276354601133145937560346030560793451506650510224288465793253472007049684097685317632151847843384406953550197684350062904939907961706]
测一下，
sage: isPrime(n-11804593083540766953191768473584891632857464298610295673456410319093405751966708262984066641796004658380825990723088997287209884308749055923966759203552497405777188930982989535372734594928432767182748217929177897158889489317608554405915470112027996617864702664597137007278287666634774284031478676422259138168270660452037808633419847474475483128590811499676324666087197259465241042751682326546155170750087186789218676468094424397026064636516349145483400088735735646407761831516062003605276354601133145937560346030560793451506650510224288465793253472007049684097685317632151847843384406953550197684350062904939907961706)
True
bingo！
解法二
根据题目，我们有式子
由于 的次数太高，这里我们直接把 也设为一个变量，于是
我们直接对这两个式子关于变量 求结式能够得到一个关于 的多项式 。
测试代码
from Crypto.Util.number import *
from random import randint
#from secret import message
msg = b"flag{12345678}"
p, q = [getPrime(1024) for _ in range(2)]
n = p * q
def pad(msg: bytes) -> bytes:
return msg + long_to_bytes(len(msg) & 0xff) * (2048 // 8 - len(msg) - 1)
def f(x: int, poly: list[int]) -> int:
return sum([
poly[i] * pow(x, i, n) for i in range(len(poly))
]) % n
def commit(m: int, d: int, key: int, poly: list[int]) -> (int, int):
sig = pow(m, d, n)
c1 = (sig + pow(key, 8, n) + pow(key, 4, n) + pow(key, 2, n)) % n
c2 = f(key, poly)
return c1, c2
e = 233
assert GCD(e, (p - 1) * (q - 1)) == 1
m = bytes_to_long(pad(msg))
c = pow(m, e, n)
e = getPrime(256)
assert GCD(e, (p - 1) * (q - 1)) == 1
d = inverse(e, (p - 1) * (q - 1))
key = getPrime(1024)
poly = [randint(n // 2, n) for _ in range(8)]
m = bytes_to_long(msg)
c1,c2 = commit(m, d, key, poly)
P = Zmod(n)["md,k"]
md, k = P.gens()
f = md + k**8 + k**4 + k**2 - c1
g = sum([poly[i] * k**i for i in range(len(poly))]) - c2
h = f.sylvester_matrix(g, k).det().univariate_polynomial().monic()
assert h(pow(m,d,n)) == 0
注意到 ，我们又知道 ，所以如果能直接把每一项都升 次就好了。（这样我们就能有一个关于 的多项式，和式子 求一个 GCD 就可以了）
如何做呢？这里涉及一下多项式的伴随矩阵 companion_matrix
多项式可以用一个伴随矩阵和一个基函数向量表示，其实我们在 密码学基础之线性代数 Ⅱ (qq.com) 有提到过的类似的
在 wiki 上对伴随矩阵的解释为
我们求出当前多项式 的伴随矩阵 ， C(h) 的特征多项式就是 ，C(h) 的特征值就是 的解，那么 就会是 的对角矩阵上的一个元素。
因此我们求一个 ，那么其对角矩阵上的一个元素就会是 ，也就意味着新特征多项式的一个解是 。
总而言之：我们只需要对 的伴随矩阵求一个 的幂次，再取其特征多项式即可，he = (companion_matrix(h) ** e).charpoly()
验证一下
sage: he = (companion_matrix(h) ** e).charpoly()
sage: he(m)
0
bingo！
后面再爆破一下 的 padding，和 做一个 GCD 就完活了~
原文始发于微信公众号（Van1sh）：好题分享系列 – 2023 江苏省数据安全竞赛 – hardrsa
