[长城杯 2024]rasnd

Problem: [长城杯 2024]rasnd

思路

• 解题大致思路

EXP

from pwn import *
from itertools import product

# context.log_level = 'debug'


io = remote('node1.anna.nssctf.cn', 28785)


def attack1(n,c,hint1,hint2):
    for a, b in product(range(int(2**11)), repeat=2):
        q = gcd(a * (hint1 + 0x114) - b * (hint2 + 0x514), n)
        if q != 1 and q < n:
            print(q, n)
            break
    p = n // q

    d = pow(0x10001,-1,(p-1)*(q-1))
    m = pow(c,d,n)
    # print(bytes.fromhex(hex(m)[2:]))
    return bytes.fromhex(hex(m)[2:])


def attack2(n,c,hint):
    P.<x> = PolynomialRing(ZZ)
    f = 514*x^2 - pow(hint,-1,n)*x - 114*n
    p = int(f.roots()[0][0])
    q = n // p

    d = pow(0x10001,-1,(p-1)*(q-1))
    m = pow(c,d,n)
    # print(bytes.fromhex(hex(m)[2:]))
    return bytes.fromhex(hex(m)[2:])


io.recvline()
n = int(io.recvline().decode().strip())
c = int(io.recvline().decode().strip())
hint1 = int(io.recvline().decode().strip())
hint2 = int(io.recvline().decode().strip())

print(attack1(n,c,hint1,hint2))

io.recvline()

n = int(io.recvline().decode().strip())
c = int(io.recvline().decode().strip())
hint = int(io.recvline().decode().strip())

print(attack2(n,c,hint))
​

总结

• 对该题的考点总结