# 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 = 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} .