原文链接: https://lov2.netlify.app/interesting-question/
2023年四川网信人才技能大赛（网络安全管理员赛项）决赛
题目附件
from Crypto.Util.number import *
from secret import flag
from sympy import nextprime
flag=b''
r = getRandomNBitInteger(64)
p = r**5 + r**4 - r**3 + r**2 - r + 2023
q = r**5 - r**4 + r**3 - r**2 + r + 2023
p =nextprime(p)
q =nextprime(q)
n = p*q
def enc(flag, n):
m = bytes_to_long(flag)
return pow(m, 65537, n)
c = enc(flag, n)
print(n)
print(c)
# 25066797992811602609904442429968244207814135173233823574561146780193277243588729282392464721760638040595480284865294238118778099149754637586361909432730412493061503054820202744474632665791457
# 18808483076270941157829928736000549389727451019027515249724024369421942132354537978233676261769285858813983730966871222263698559152437016666829640339912308636169767041243411900882395764607422
Exploit
P.<r> = PolynomialRing(QQ)
fp = r**5 + r**4 - r**3 + r**2 - r + 2023
fq = r**5 - r**4 + r**3 - r**2 + r + 2023
print(f'{latex((fp * fq))}') # n的最大项只有r^8，所以对n开十次过后基本就等于r
r_max = (1 << 64) - 1 # 接着还可以减一个小值来模拟随机, 或者用题目的r生成方式, 会发现对最后的结果没有影响
p = fp(r = r_max)
q = fq(r = r_max)
P = Primes()
p = P.next(Integer(p))
q = P.next(Integer(q))
n = p * q
Diff = int(real_nth_root(n, 10)) - r_max
print(f'{Diff = }') # 于是 换上题目数据
n = 25066797992811602609904442429968244207814135173233823574561146780193277243588729282392464721760638040595480284865294238118778099149754637586361909432730412493061503054820202744474632665791457
r = int(real_nth_root(n, 10)) - Diff
p = fp(r = r)
q = fq(r = r)
p = P.next(Integer(p))
q = P.next(Integer(q))
assert p * q == n
phi = (p - 1) * (q - 1)
e = 0x10001
c = 18808483076270941157829928736000549389727451019027515249724024369421942132354537978233676261769285858813983730966871222263698559152437016666829640339912308636169767041243411900882395764607422
d = inverse_mod(e, phi)
m = power_mod(c, d, n)
from Crypto.Util.number import long_to_bytes
print(long_to_bytes(m))
r^{10} - r^{8} + 2 r^{7} - 3 r^{6} + 4050 r^{5} - 3 r^{4} + 2 r^{3} - r^{2} + 4092529
Diff = -1
b'flag{5afe5cbb-4b4c-9cb6-f8b6-032cabf4b7e7}'
思路
p 与 q 相乘后, 也就是 n 为
r^{10} - r^{8} + 2 r^{7} - 3 r^{6} + 4050 r^{5} - 3 r^{4} + 2 r^{3} - r^{2} + 4092529
对 n 开 10 次方后基本就等于 r, 第二项为 -r^{8}, 是负数, 所以这里能推断差值是负数(次方越大, 对开根的影响越大)
但这道题有趣的点在于 r 在范围(64比特位)内怎么变, 最后的 n 与 r 的差值均为 -1, 优雅, 实在是太优雅了
为什么对 n 开 10 次方后根号下次数比较低的值造成的偏差会很小？
\text{let} \quad C = \sqrt[k]{r^k - r^t} - r \quad (k > t)
糖醋小鸡块:
你把这个式子用2和1列一列(比如 k = 2, t = 1)，然后归纳法
也不叫归纳法，就大致可以类比次数提上去过后
代入大一点值如下
R.<r> = PolynomialRing(RR) # RR表示实数
k = 10
t = 8
f1 = real_nth_root(power(r, k) - power(r, t), k) - r
f1(r = 1000)
别的做法
整数域求解，尝试给素数偏移，有解即为成功找到 p, q
n = 25066797992811602609904442429968244207814135173233823574561146780193277243588729282392464721760638040595480284865294238118778099149754637586361909432730412493061503054820202744474632665791457
P.<r> = PolynomialRing(ZZ)
for i in range(500):
for j in range(500):
fp = r**5 + r**4 - r**3 + r**2 - r + 2023 + i # i, j 来模拟 next_prime 的小偏移
fq = r**5 - r**4 + r**3 - r**2 + r + 2023 + j
f = fp * fq - n
if f.roots():
print(f'{f.roots() = }')
break
实数域求解后对 根 进行偏移爆破
P.<r> = PolynomialRing(RR) # RR表示实数
fp = r**5 + r**4 - r**3 + r**2 - r + 2023
fq = r**5 - r**4 + r**3 - r**2 + r + 2023
n = 25066797992811602609904442429968244207814135173233823574561146780193277243588729282392464721760638040595480284865294238118778099149754637586361909432730412493061503054820202744474632665791457
f = fp * fq - n
print(f'{f.roots() = }')
root = Integer(f.roots()[1][0]) # 取正整数
print('Approximate root =', root)
# 转到整数下, 又因为涉及了 next_prime 所以爆破
P.<r> = PolynomialRing(ZZ)
fp = r**5 + r**4 - r**3 + r**2 - r + 2023
fq = r**5 - r**4 + r**3 - r**2 + r + 2023
print(f'{fp * fq = }')
for root in range(root - 500, root + 1): # 由于 next_prime 的存在, 实际的 r 要小于 fp * fq - n 求根的 r
p = fp(r = root)
q = fq(r = root)
P = Primes()
p = P.next(Integer(p))
q = P.next(Integer(q))
if p * q == n:
print('found it')
print(f'{root = }')
break
一点点无关的小技巧
多个未知数的多项式
n = 10
R = PolynomialRing(Zmod(n), 'argu1, argu2')
argu1, argu2 = R.gens() # gens() 生成多元环的生成元
f = argu1 * argu2 - 1 - n
print(f'{f = }')