Koharu

This was a warmup crypto challenge at Seccon CTF 2020.

while True:
    p = random_prime(1<<64)
    if is_prime((p+1) // 2):
        break

with open("flag.txt", "rb") as f:
    flag = f.read()
flag = int.from_bytes(flag, "big")


PR.<x> = PolynomialRing(GF(p))
while True:
    P = PR.random_element(degree=64)
    if P.is_irreducible():
        break

while True:
    Q = PR.random_element(degree=64)
    if Q.is_irreducible():
        break

NP = p**P.degree()
NQ = p**Q.degree()

while True:
    R = PR.random_element(degree=64)
    if power_mod(R, (NP-1)//2, P) != 1 and power_mod(R, (NQ-1)//2, Q) != 1:
        break

PQ = P*Q
c = []
while flag:
    S = PR.random_element(degree=64)
    if flag & 1:
        c.append((S * S) % PQ)
    else:
        c.append((S * S * R) % PQ)
    flag = flag >> 1

print("p =", p)
print("PQ =", PQ)
print("R =", R)
print("c =", c)

The flag is encoded bit per bit, using a different polynomial multiplication depending on the bit's value.

while True:
    R = PR.random_element(degree=64)
    if power_mod(R, (NP-1)//2, P) != 1 and power_mod(R, (NQ-1)//2, Q) != 1:
        break

The above piece of code make sure that the polynomial \(R\) is a non-quadratic residue both mod \(P\) and \(Q\).

If the bit we want to encode is 1, the encoding polynomial is \(S \times S \mod PQ\), which is obv. a quadratic residue. However, if the bit is 0, the encoding polynomial is \(S \times S \times R \mod PQ\), meaning we multiply a square by a non-quadratic residue, which yields a non-quadratic residue.

That means that given \(P\) or \(Q\), one can retrieve the bits value by checking if the encoding polynomials are quadratic residue or not.

As \(P\) and \(Q\) are degree 64 polynomials over \(GF(p)\) with \(p\) some prime, sage can easily factor \(PQ\) to get them back.

Here is a script implementing all of this:

p = 4832823609987476353
PR.<x> = PolynomialRing(GF(p))
PQ = [...]
R = [...]
c = [...]

facs = PQ.factor()
P = facs[0][0]
Q = facs[1][0]
NP = p**64

flag = 0
for i,bit in enumerate(c):
    a = power_mod(bit, (NP-1)//2, P)  # or power_mod(bit, (NQ-1)//2, Q)
    if a == 1:
        flag += (1 << i)

from Crypto.Util.number import long_to_bytes
print(long_to_bytes(flag).decode())

which yields SECCON{p01y-p01y-p3r0-p3r0-hy0ukun-p3r0p3r0} .