Quotient Polynomial Ring and Isomorphism

Introduction

Firstly, I will try to introduce some definition and theorem that will be used in this post. I do not proof all the theorem here, but I will try to give some intuition about the theorem.

Definition 1. Polynomial Ring $R[x]$ is the set of all polynomials with coefficients in $R$ for some ring $R$.

Definition 2. $\langle f(x) \rangle$ is the ideal generated by $f(x)$ for some polynomial ring $R[x]$ and $f(x) \in R[x]$. Equivalently, $\langle f(x) \rangle$ is the set of all multiples of $f(x)$.

Definition 3. Quotient Polynomial Ring $R[x]/I$ is the set of all cosets of $I$ in $R[x]$ for some ideal $I$ of $R[x]$.

But in this post, we will only focus the ideal $I$ that is generated by a polynomial $f(x)$, i.e. $I = \langle f(x) \rangle$.

For quotient polynomial ring $R[x]/\langle f(x) \rangle$, we can think of it as the set of all polynomials with coefficients in $R$ modulo $f(x)$. For example in $\mathbb{Z}[x]/\langle x^2 + 1 \rangle$ has element \(\{a + bx \mid a,b \in \mathbb{Z}\}\) and take some element $\mathbb{Z}[x]$, for instance $x^3+5x^2+3x+1$. Because $x^3+5x^2+3x+1 = (x+5)(x^2+1) + 2x-4$, then $x^3+5x^2+3x+1$ is equivalent to $2x-4$ in $\mathbb{Z}[x]/\langle x^2 + 1 \rangle$.

Theorem 1. Let $R$ be a ring and $f(x) \in R[x]$. If $f(x)$ is irreducible in $R[x]$, then $R[x]/\langle f(x) \rangle$ is a field.

For the proof, we can argue that since $f(x)$ is irreducible, every non-zero element in $R[x]/\langle f(x) \rangle$ has an inverse, making it a field.

From theorem 1, we can say that all nonzero element in $R[x]/\langle f(x) \rangle$ for some irreducible polynomial $f(x)$ form a group under multiplication. This group is called the multiplicative group of $R[x]/\langle f(x) \rangle$. Moreover this multiplicative group is cyclic for finite field.

Definition 4. Let $G_1$ and $G_2$ be groups. A group isomorphism $\phi: G_1 \to G_2$ is a bijective function that satisfies the following properties:

1. $\phi(ab) = \phi(a)\phi(b)$ for all $a,b \in G_1$.

Isomorphism is basically just saying that two groups are “the same” in some sense. Term Isomorphism not only used in group, but also in other algebraic structure like ring, field, etc. We will use either isomorphism between group or ring based on the context.

Definition 5. Let $G_1$ and $G_2$ be groups. $G_1$ is isomorphic to $G_2$ if there exists a group isomorphism $\phi: G_1 \to G_2$. We will usually denote this as $G_1 \cong G_2$.

Theorem 2. Multplicative group of $Z_p[x]/\langle f(x) \rangle$ for some irreducible polynomial $f(x)$ with degree $n$ is isomorphic to $\mathbb{Z}_{p^n - 1}^*$.

Theorem 3. If $n=pq$, where $p$ and $q$ are prime, and suppose $f(x)$ is irreducible in $\mathbb{Z}_n[x]$. Then $\mathbb{Z}_n[x]/\langle f(x) \rangle \cong \mathbb{Z}_p[x]/\langle f(x) \rangle \times \mathbb{Z}_q[x]/\langle f(x) \rangle$.

Theorem 4. If $R$ is ring and $p(x)$ and $q(x)$ relatively prime (the common divisor is unit) for $p(x), q(x) \in R[x]$. Then $R[x]/ \langle p(x)q(x) \rangle \cong R[x]/\langle p(x) \rangle \times R[x]/\langle q(x) \rangle$.

Theorem 2 is group isomorphism, while theorem 3 and 4 is ring isomorphism.

CTF Challenge Settings

Now, let’s try to solve some CTF challenge that use the concept of quotient polynomial ring and isomorphism. The first challenge is my written challenge from COMPFEST CTF 2023 and the rest of challenge is from BackdoorCTF 2023 that I found many interesting challenge related to this topic.

Swusjask Encryption [COMPFEST CTF 2023]

from Crypto.Util.number import long_to_bytes, bytes_to_long

p = 1179478847235411356076287763101027881
e = 0x10001


def bytes_to_block(msg: bytes):
    res = []
    msg_int = bytes_to_long(msg)
    while msg_int:
        res.append(msg_int % (p**2))
        msg_int //= p**2
    return res


def block_to_bytes(blocks: list[int]):
    res = 0
    for i in range(len(blocks) - 1, -1, -1):
        res *= p**2
        res += blocks[i]
    return long_to_bytes(res)


class MultiplicativeGroup:
    def __init__(self, a, b):
        self.a = a
        self.b = b

    def __mul__(self, other) -> "MultiplicativeGroup":
        a = (self.a * other.a - 6969 * self.b * other.b) % p
        b = (self.a * other.b + self.b * other.a - 69 * self.b * other.b) % p
        return MultiplicativeGroup(a, b)

    def __pow__(self, n) -> "MultiplicativeGroup":
        res = MultiplicativeGroup(1, 0)
        base = self
        while n:
            if n & 1:
                res *= base
            base *= base
            n >>= 1
        return res
    
    def __repr__(self):
        return f"({self.a}, {self.b})"


if __name__ == "__main__":
    FLAG = open("flag.png", "rb").read()
    blocks = bytes_to_block(FLAG)
    enc = []
    for block in blocks:
        assert block < p**2
        a = block % p
        b = block // p
        m = MultiplicativeGroup(a, b)
        c = m ** e
        enc.append(c.a + c.b * p)
        
    open("flag.enc", "wb").write(block_to_bytes(enc))

Overview

The flag is in .png format that first encode the bytes data into per blocks with size $p^2$ in group \(({\mathbb{Z}_{p} \times \mathbb{Z}_{p}}^*, \cdot )\) (the notation $*$ is just I set up that it indicates only some element only that will be included in this group, not all of $\mathbb{Z}_p \times \mathbb{Z}_p$). The group operation is as follow. Let \((a_1,b_1), (a_2,b_2) \in {\mathbb{Z}_{p} \times \mathbb{Z}_{p}}^*\). Then

\[(a_1,b_1) \cdot (a_2,b_2) = (a_1a_2 - 6969b_1b_2, a_1b_2 + b_1a_2 - 69b_1b_2)\]

The encryption is just like RSA with $e=0x10001$ and the ciphertext is $(a,b)^e$.

Solution

In order to get back to original $(a,b)$ from $(a,b)^e$, just like RSA, we need to find the order of group used in the encryption. Actually, indeed all nonzero element is element in group. So the order is $p^2 - 1$ and just decrypt the element like RSA. Actually from here you have solved the challenge (yeah the challenge is just like guessing though 🗿, also during the contest, all team that solved just guessing the order without knowing why), but maybe interesting question is why the order is $p^2 - 1$. Here is the explanation.

The group \(({\mathbb{Z}_{p} \times \mathbb{Z}_{p}}^*, \cdot )\) is isomorphic with multiplicative group of \(\mathbb{Z}_p[x] / \langle x^2 + 69x + 6969 \rangle\). Given by isomorphism \(\phi: ({\mathbb{Z}_{p} \times \mathbb{Z}_{p}}^*, \cdot ) \to \mathbb{Z}_p[x] / \langle x^2 + 69x + 6969 \rangle\) with $\phi(a,b) = a + bx$. Notice that $\forall (a_1,b_1), (a_2,b_2) \in {\mathbb{Z}_p \times \mathbb{Z}_p}^*$

\[\begin{align*} \phi((a_1,b_1) \cdot (a_2,b_2)) &= \phi(a_1a_2 - 6969b_1b_2, a_1b_2 + b_1a_2 - 69b_1b_2) \\ &= a_1a_2 - 6969b_1b_2 + (a_1b_2 + b_1a_2 - 69b_1b_2)x \\ &= a_1a_2 - 6969b_1b_2 + (a_1b_2 + b_1a_2 - 69b_1b_2)x + b_1b_2(x^2 + 69x + 6969) \\ &= a_1a_2 + (a_1b_2 + b_1a_2)x + b_1b_2x^2 \\ &= (a_1 + bx)(a_2 + bx) \\ &= \phi(a_1,b_1)\phi(a_2,b_2) \end{align*}\]

Also it obvious that $\phi$ is bijective. Hence it proved that it indeed isomorphic. Also using sagemath we can check that $x^2 + 69x + 6969$ is irreducible in $\mathbb{Z}_p[x]$ given $p$ in challenge.

from sage.all import *

p = 1179478847235411356076287763101027881
x = PolynomialRing(ZZ, 'x').gen()

f = x**2 + 69*x + 6969

f.is_irreducible()

True

Then, by theorem 2, the order of group is $p^2 - 1$. Then, here is the decryption look like.

1. Calculate $d = e^{-1} \mod (p^2 - 1)$
2. For each block $(a,b)$, calculate $(a,b)^d$ and get back to the original plaintext.
3. Concatenate all plaintext block and write back to png file.

from sage.all import *

from Crypto.Util.number import long_to_bytes, bytes_to_long

def bytes_to_block(msg: bytes):
    res = []
    msg_int = bytes_to_long(msg)
    while msg_int:
        res.append(msg_int % (p**2))
        msg_int //= p**2
    return res


def block_to_bytes(blocks: list[int]):
    res = 0
    for i in range(len(blocks) - 1, -1, -1):
        res *= p**2
        res += blocks[i]    
    return long_to_bytes(res)

p = 1179478847235411356076287763101027881
e = 0x10001
F = GF(p)
R = PolynomialRing(F, "x")
x = R.gen()
Q = R.quotient_ring(x**2 + 69 * x + 6969, "w")
w = Q.gen()

ord = p * p - 1
d = pow(e, -1, ord)

FLAG_ENC = open("flag.enc", "rb").read()
blocks = bytes_to_block(FLAG_ENC)
dec = []
for block in blocks:
    a = block % p
    b = block // p
    c_K = a + b * w
    m_K = c_K ** d
    coeff = m_K.list()
    res = 0
    for i in range(len(coeff) - 1, -1, -1):
        res *= int(p)
        res += int(coeff[i])
    dec.append(int(res))

open("flag_dec.png", "wb").write(block_to_bytes(dec))

Flag: COMPFEST15{find_the_order_of_group_81ee36780a}

Curvy Curves [BackdoorCTF 2023]

from Crypto.Util.number import getRandomNBitInteger, bytes_to_long, long_to_bytes
from sage.all import *

# non-residue
D = ...

# redacted
p = "REDACTED" 
q = "REDACTED"

# n = p*q
n = ...

flag = b"flag{REDACTED}"

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    def __add__(self, other):
        x = (self.x*other.x + D*self.y*other.y)%n
        y = (self.y*other.x + self.x*other.y)%n
        return Point(x, y)
    def __mul__(self, d):
        Q = Point(1, 0)
        P = Point(self.x, self.y)
        while d != 0:
            if d&1 == 1:
                Q += P
            P += P
            d >>= 1
        return Q
    def __str__(self) -> str:
        return f"{self.x}, {self.y}"

def check_residue(y):
    if pow(y, (p - 1)//2, p) == 1 and pow(y, (q - 1)//2, q) == 1:
        return True
    return False

def gen_point():
    while True:
        x = getRandomNBitInteger(1023 - 240)
        x = bytes_to_long(flag + long_to_bytes(x))
        x %= n
        y2 = ((x*x - 1)*pow(D, -1, n))%n
        if(check_residue(y2)):
            yp = pow(y2, (p + 1) // 4, p)
            yq = pow(y2, (q + 1) // 4, q)
            y = crt([yp, yq], [p, q])
            return Point(x, y)

M = gen_point()
e = 65537
C = M*e
print(C)
# Cx = ..., Cy = ...

Overview

The flag is embedded in x-coordinate of point $M$ which lie inside group \((\mathbb{Z}_n \times \mathbb{Z}_n^*, \cdot)\) where the group operation is defined as follow. Let \((a_1, b_1), (a_2, b_2) \in \mathbb{Z}_n \times \mathbb{Z}_n^*\), Then

\[(a_1, b_1) \cdot (a_2, b_2) = (a_1a_2 + Db_1b_2, a_1b_2 + b_1a_2)\]

The challenge settings is still same with challenge before, we are given $M^e$ and we need to find $M$.

Solution

For $n$ actually the factorization already discovered from factordb. So our main focus now on the group characterization. The group \((\mathbb{Z}_n \times \mathbb{Z}_n^*, \cdot)\) is isomorphic with multiplicative group of $\mathbb{Z}_n[x] / \langle x^2 - D \rangle$. Given by isomorphism \(\phi: (\mathbb{Z}_n \times \mathbb{Z}_n^*, \cdot) \to \mathbb{Z}_n[x] / \langle x^2 - D \rangle\) with $\phi(a,b) = a + bx$. Notice that $\forall (a_1,b_1), (a_2,b_2) \in {\mathbb{Z}_n \times \mathbb{Z}_n}^*$

\[\begin{align*} \phi((a_1,b_1) \cdot (a_2,b_2)) &= \phi(a_1a_2 + Db_1b_2, a_1b_2 + b_1a_2) \\ &= a_1a_2 + Db_1b_2 + (a_1b_2 + b_1a_2)x \\ &= a_1a_2 + Db_1b_2 + (a_1b_2 + b_1a_2)x + b_1b_2(x^2 - D) \\ &= a_1a_2 + (a_1b_2 + b_1a_2)x + b_1b_2x^2 \\ &= (a_1 + bx)(a_2 + bx) \\ &= \phi(a_1,b_1)\phi(a_2,b_2) \end{align*}\]

By theorem 3, we can say this group also isomorphic with multiplicative group of $\mathbb{Z}_p[x] / \langle x^2 - D \rangle \times \mathbb{Z}_q[x] / \langle x^2 - D \rangle$. Moreover, given by $D$ is non-residue from source code, it must be $x^2 - D$ is irreducible in $\mathbb{Z}_p[x]$ and $\mathbb{Z}_q[x]$. Then, the order of group is $(p^2 - 1)(q^2 - 1)$ by Theorem 2.

Then, the decryption is just like before. Here is the decryption look like. For simplicity, we don’t need to convert the point to polynomial ring just work with the defined group. Because the only thing we need to know is the order of group.

from Crypto.Util.number import getRandomNBitInteger, bytes_to_long, long_to_bytes

# # non-residue
D = ...

# # redacted
p = ...
q = ...

# # n = p*q
n = ...
assert n == p * q

flag = b"flag{REDACTED}"


class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __add__(self, other):
        x = (self.x * other.x + D * self.y * other.y) % n
        y = (self.y * other.x + self.x * other.y) % n
        return Point(x, y)

    def __mul__(self, d):
        Q = Point(1, 0)
        P = Point(self.x, self.y)
        while d != 0:
            if d & 1 == 1:
                Q += P
            P += P
            d >>= 1 
        return Q

    def __str__(self) -> str:
        return f"{self.x}, {self.y}"


def check_residue(y):
    if pow(y, (p - 1) // 2, p) == 1 and pow(y, (q - 1) // 2, q) == 1:
        return True
    return False


def gen_point():
    while True:
        x = getRandomNBitInteger(1023 - 240)
        x = bytes_to_long(flag + long_to_bytes(x))
        x %= n
        y2 = ((x * x - 1) * pow(D, -1, n)) % n
        if check_residue(y2):
            yp = pow(y2, (p + 1) // 4, p)
            yq = pow(y2, (q + 1) // 4, q)
            y = crt([yp, yq], [p, q])
            return Point(x, y)

Cx = ...
Cy = ...
C = Point(Cx, Cy)
e = 65537
d = pow(e, -1, (p**2 - 1) * (q**2 - 1))
M = C * d
print(long_to_bytes(M.x))

Flag: flag{pHUCk_150M0rPh15m_1n70_p2}

PRSA [BackdoorCTF 2023]

from sage.all import *
from Crypto.Util.number import bytes_to_long, getPrime

import random
import time
random.seed(time.time())

message = b'flag{REDACTED}' ## the flag has been removed
F.<x> = PolynomialRing(GF(2), x)

p, q = [F.irreducible_element(random.randint(2 ** 10, 2 ** 12)) for _ in range(2)]
R.<y> = F.quotient_ring(p * q)

n = sum(int(bit) * y ** (len(bin(bytes_to_long(message))[2:]) - 1 - i) for i, bit in enumerate(bin(bytes_to_long(message))[2:]))

e = 2 ** 256
c = n ** e 

print(e) ## to be given to the user
print(c) ## to be given to the user
print(p * q) ## to be given to the user

Overview

Given $p(x),q(x) \in \mathbb{Z}_2[x]$ is irreducible polynomial with degree from $2^{10}$ to $2^{12}$. Now, the flag is encoded into $n \in \mathbb{Z}_2[x] / \langle p(x)q(x) \rangle$ and we are given the value of $n^e$ with $e = 2^{256}$

Solution

By theorem 4, $\mathbb{Z}_2[x] / \langle p(x)q(x) \rangle$ is isomorphic with $\mathbb{Z}_2[x] / \langle p(x) \rangle \times \mathbb{Z}_2[x] / \langle q(x) \rangle$. Then, the order of group is $(2^{\deg(p)} - 1)(2^{\deg(q)} - 1)$ by theorem 2. Then, the decryption is just like before. Here is the solver script.

from sage.all import *
from Crypto.Util.number import long_to_bytes

PR = PolynomialRing(GF(2), "x")
x = PR.gen()
with open("output.txt", "r") as f:
    e = int(f.readline().strip())
    c = f.readline().strip()
    pq = PR(f.readline().strip())

for a in range(2**10, 2 ** 12 + 1):
    p = PR.irreducible_element(a)
    if pq % p == 0:
        q = pq // p
        break

PQR = PR.quotient_ring(p * q, "y")
ord_ = (2 ** p.degree() - 1) * (2 ** q.degree() - 1)
d = pow(e, -1, ord_)
c = PQR(c)
n = c ** d
m = int(n.lift().change_ring(ZZ)(2))
print(long_to_bytes(m))

Flag: flag{S0_1mPL3m3n71nG_R54_0n_P0lYn0m1aL5_1n5734d_d1dn7_w0rk_hUh!!?}

Rebellious [BackdoorCTF 2023]

from sage.all import *
from Crypto.Util.number import *
import random
import time
random.seed(time.time())


FLAG = b'flag{REDACTED}' ## flag removed
flag = bytes_to_long(FLAG)

f = open('./output.txt', 'w')

p = ...
F = GF(p)

a, b = random.randint(2, p), random.randint(2, p)
f.write(f"a = {a}\nb = {b}")

def point_addition(px, py, qx, qy):
    rx = F((pow(a, -1, p) * (px * qx - py * qy * (a ** 2) * (pow(b ** 2, - 1, p)))) % p)
    ry = F((pow(a, -1, p) * (px * qy + py * qx)) % p)
    return (rx, ry)

def scalar_multiplication(px, py, k):
    rx = a
    ry = 0
    while k:
        if k % 2:
            rx, ry = point_addition(rx, ry, px, py)
        px, py = point_addition(px, py, px, py)
        k >>= 1
    return rx, ry

G = generator_curve() ## implementation hidden for enhancing security

x1 = G[0]
y1 = G[1]

H = scalar(multiplication(x1, y1, flag))

x2 = H[0]
y2 = H[1]

f.write(f"x1 = {x1}\n")
f.write(f"y1 = {y1}\n")
f.write(f"x2 = {x2}\n")
f.write(f"y2 = {y2}\n")

Overview

We are given point $(x_1,y_1)$ and $(x_2,y_2)$ that lies inside group \((\mathbb{F}_p \times \mathbb{F}_p^*, \cdot)\) where the group operation is defined as follow. Let \((a_1, b_1), (a_2, b_2) \in \mathbb{F}_p \times \mathbb{F}_p^*\), Then

\[(a_1, b_1) \cdot (a_2, b_2) = \left({1 \over a}(a_1b_1-a_2b_2{a^2 \over b^2}), {1 \over a}(a_1b_2 + b_1a_2)\right)\]

The two point that we are given satisfy $(x_2,y_2) = (x_1,y_1)^{flag}$. So the problem is we must find the discrete log of given group to get the flag.

Solution

The group \((\mathbb{F}_p \times \mathbb{F}_p^*, \cdot)\) is isomorphic with multiplicative group of $\mathbb{F}_p[x] / \langle x^2 + {a^2 \over b^2} \rangle$. Given by isomorphism \(\phi: (\mathbb{F}_p \times \mathbb{F}_p^*, \cdot) \to \mathbb{F}_p[x] / \langle x^2 + {a^2 \over b^2} \rangle\) with $\phi(a_1,b_1) = {1 \over a}(a_1 + b_1x)$. Notice that $\forall (a_1,b_1), (a_2,b_2) \in {\mathbb{F}_p \times \mathbb{F}_p}^*$

\[\begin{align*} \phi((a_1,b_1) \cdot (a_2,b_2)) &= \phi\left({1 \over a}(a_1b_1-a_2b_2{a^2 \over b^2}), {1 \over a}(a_1b_2 + b_1a_2)\right) \\ &= {a_1b_1 \over a^2} - {a_2b_2 \over b^2} + \left({a_1b_2 \over a^2} + {b_1a_2 \over a^2}\right)x \\ &= {a_1b_1 \over a^2} - {a_2b_2 \over b^2} + \left({a_1b_2 \over a^2} + {b_1a_2 \over a^2}\right)x + {a_2b_2 \over a^2} (x^2 + {a^2 \over b^2}) \\ &= {a_1b_1 \over a^2} + \left({a_1b_2 \over a^2} + {b_1a_2 \over a^2}\right)x + {a_2b_2 \over a^2}x^2 \\ &= {1 \over a}(a_1 + b_1x) {1 \over a}(a_2 + b_2x) \\ &= \phi(a_1,b_1)\phi(a_2,b_2) \end{align*}\]

It also obvious that $\phi$ is bijective. Hence it proved that it indeed isomorphic. But, one can check that $x^2 + {a^2 \over b^2}$ reducible in $\mathbb{F}_p[x]$ for $p \equiv 1 \pmod 4$ (why?). By theorem 4 and theorem 2 we can conclude that the order of this multiplicative group is $(p-1)^2$. Moreover, the degree of element cannot exceed $(p-1)$. So we can just use the discrete log builtin function in sagemath and passing $(p-1)$ the order of element. Here is the solver script.

from sage.all import *
from Crypto.Util.number import *

p = ...
F = GF(p)

a = ...
b = ...

x1 = ...
y1 = ...

x2 = ...
y2 = ...

R = PolynomialRing(F, "x")
x = R.gen()
quotient_ring = R.quotient_ring(R(x**2 + ((a ** 2) * pow(b, -2, p) % p)))

w = quotient_ring.gen()
G = F(x1 * pow(a, -1, p) % p) + F(y1 * pow(a, -1, p) % p) * w
H = F(x2 * pow(a, -1, p) % p) + F(y2 * pow(a, -1, p) % p) * w



flag = int(discrete_log(H, G, ord=Integer(p-1)))
print(long_to_bytes(flag))

Flag: flag{gR0uP_150M0rPH15m5_4R3_g0NN4_b3_7h3_3nD_0f_y0Ur_L1f3!}