# 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}`

.