LOV3 -> OV3

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

Sage

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))

Output

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)，然后归纳法

也不叫归纳法，就大致可以类比次数提上去过后

代入大一点值如下

Sage

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$

Sage

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

实数域求解后对 根 进行偏移爆破

Sage

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

又一道类似的题

# [LitCTF 2023]easy_math (中级)
from Crypto.Util.number import *
# from secret import flag
flag = b'flag{test}'

m = bytes_to_long(flag)
e = 65537
p = getPrime(512)
q = getPrime(128)
n = p*q
print(f'p = {p}')
print(f'q = {q}')
hint = p**3-q**5
c = pow(m,e,n)
print(f'n = {n}')
print(f'c = {c}')
print(f'hint = {hint}')

# Data
n = 2230791374046346835775433548641067593691369485828070649075162141394476183565187654365131822111419512477883295758461313983481545182887415447403634720326639070667688614534290859200753589300443797
c = 2168563038335029902089976057856861885635845445863841607485310134441400500612435296818745930370268060353437465666224400129105788787423156958336380480503762222278722770240792709450637433509537280
hint = 392490868359411675557103683163021977774935163924606169241731307258226973701652855448542714274348304997416149742779376023311152228735117186027560227613656229190807480010615064372521942836446425717660375242197759811804760170129768647414717571386950790115746414735411766002368288743086845078803312201707960465419405926186622999423245762570917629351110970429987377475979058821154568001902541710817731089463915930932142007312230897818177067675996751110894377356758932

# sol
from gmpy2 import iroot, next_prime, powmod, invert
p_3 = iroot(hint, 3)[0]
cnt = 0
while True:
    q = n // p_3
    if n != p_3 * q:
        p_3 = next_prime(p_3)
        cnt += 1
    else:
        phi = (p_3 - 1) * (q - 1)
        d = invert(65537, phi)
        m = powmod(c, d, n)
        print(long_to_bytes(m))
        print(f'{cnt = }')
        break

一点点无关的小技巧

多个未知数的多项式

Sage

n = 10
R = PolynomialRing(Zmod(n), 'argu1, argu2')
argu1, argu2 = R.gens() # gens() 生成多元环的生成元
f = argu1 * argu2 - 1 - n
print(f'{f = }')