S4CTF 2021 | merles - crypto-writeup-public

#s4ctf_2021

$p$ が与えられるので $3x^3 + 4y^3 + 5z^3 \equiv 0 \mod p$ が成り立つような $0 < x,y,z < p$ を求めよ、という問題。ちなみにこの式はSelmer's exampleと言われている

$p \equiv 2 \mod 3$ のとき、 $\mathbb{Z_p}$ のすべての要素は3乗根を持つので $x, y$ を適当に決めたあと、 $z^3 \equiv -(3x^3 + 4y^3)/5 \mod p$ のcube rootを求めれば良い

from ptrlib import Socket

# https://stackoverflow.com/questions/6752374/cube-root-modulo-p-how-do-i-do-this
def cuberoot(a, p):
    if p == 2:
        return a
    if p == 3:
        return a
    if (p%3) == 2:
        return pow(a,(2*p - 1)//3, p)
    if (p%9) == 4:
        root = pow(a,(2*p + 1)//9, p)
        if pow(root,3,p) == a%p:
            return root
        else:
            return None
    if (p%9) == 7:
        root = pow(a,(p + 2)//9, p)
        if pow(root,3,p) == a%p:
            return root
        else:
            return None
    raise ValueError("unimplemented for this p")

p = 8588632695475579713474064187795203206189568433129980048149925153771311219941332235026390321557701502107143737053278095095348293621267487730567324309075029


while True:
    sock = Socket("157.90.231.113", 3776)

    sock.sendlineafter("uit\n", "P")
    p = int(sock.recvlineafter("p = "))
    if not is_prime(p) or p % 3 != 2:
        sock.close()
        continue

    break

x = randint(2, p-1)
y = randint(2, p-1)

z3 = int(- (3*pow(x, 3, p) + 4*pow(y, 3, p)) * inverse_mod(5, p) % p)
z = int(cuberoot(int(z3), p))
assert (3*pow(x, 3, p) + 4*pow(y, 3, p) + 5*pow(z, 3, p)) % p == 0

print("[+] p = {}".format(p))
print("[+] (x, y, z) = ({}, {}, {})".format(x, y, z))

# sock.sendlineafter("uit\n", "R")
# sock.sendlineafter("(x, y, z):\n", "({}, {}, {})".format(x, y, z))
sock.interactive()