home - links - about - rss

Seccon 2020 - Koharu [EN]


This was a warmup crypto challenge at Seccon CTF 2020.

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

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():

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

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:

PQ = P*Q
c = []
while flag:
    S = PR.random_element(degree=64)
    if flag & 1:
        c.append((S * S) % PQ)
        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:

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

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

Creative Commons License