Quotient Ring and isomorphism

hakid29·2023년 9월 11일

최근 quotient ring과 isomorphism을 활용하는 문제를 꽤 접했는데, 신기하기도 하고 흥미로워서 좀 더 공부해 보았다. 꽤나 원초적인 수학적 내용이 있는데, sage를 사용할 때 뭔지 몰랐던 부분들을 좀 더 명확히 하고, 수학도 공부할 겸 용어 정리를 먼저 하겠다.

Term

아이디얼(ideal) : $I$ 가 환 $R$ 의 부분환(subring)이라고 하자. 다음과 같이 ideal을 정의할 수 있다.
-만약 모든 $a ∈ I, r ∈ R$ 에 대하여 $ra ∈ I$ 가 성립하면, $I$ 를 $R$ 의 left ideal이라 한다. $I$ 는 뺄셈에 대하여 닫혀 있고, 동시에 $R$ 의 원소를 왼쪽에서 곱하는 것에 닫혀 있다.
-right ideal 또한 같은 방법으로 정의된다.
-left ideal이면서 right ideal이면 two-sided ideal(또는 ideal)이다. 즉, 임의의 $a, b ∈ I, r ∈ R$ 에 대하여 $a-b, ar, ra ∈ I$ 이면 $I$ 는 $R$ 의 ideal이다.

몫환(Quotient ring) : $I$ 를 환(ring) $R$ 의 ideal이라 하고 $a ∈ R$ 라 하자. $a$ 가 속하는 $I$ 의 잉여류(coset)이란 $a + I = \{a + s \ | \ s ∈ I\}$ 와 같은 형태의 집합을 말한다. 모든 잉여류들의 집합을 몫환(quotient ring)이라 하고 $R/I$ 와 같이 나타낸다.

환준동형사상(ring homomorphism) : $R, S$ 를 두 환(ring)이라고 할 때, 사상(map) $f: R → S$ 이 임의의 $x, y ∈ R$ 에 대하여 $f(x+y) = f(x) + f(y), \ f(xy) = f(x)f(y)$ 을 만족하면 이 사상을 환준동형사상(ring homomorphism)이라 한다.

환동형사상(ring isomorphism) : 주어진 환준동형사상이 전단사(bijection)이면 이를 환동형사상(ring isomorphism)이라 한다. 환 $R$ 에서 환 $S$ 로의 환동형사상 $f : R → S$ 가 존재하면, $R$ 과 $S$ 는 서로 동형(isomorphic)이라 하고, $R≅S$ 로 나타낸다.

Quotient Ring and isomorphism

이제 quotient ring을 이해하는 데에 필요한 용어는 얼추 정리했다. 하지만 수학 전공자가 아니라면 정의를 봐도 무슨 말이지 싶을 것이다. 따라서 예시를 통해 이해해보자.

$ℤ/nℤ$ 는 $n$ 개의 원소를 갖는다
→ $nℤ, nℤ + 1, nℤ + 2, \ ... \ , nℤ + (n-1)$
→ $ℤ_n$ 과 isomorphism
$I$ 를 $x^2+1$ 에 의해 생성된 환 $ℝ[x]$ 의 ideal이라 할 때, 2차 이상의 항은 상쇄되므로 잉여류의 원소는 $a + bx$ 꼴이라고 할 수 있다. 또한, $x^2+1$ 을 $0$ 으로 볼 수 있기 때문에 $x$ 를 $i$ 로 바꾸어 생각하면 이 환은 복소수의 집합과 isomorphism임을 알 수 있다.
$ℝ[x]/(x^2+1) \ ≅ ℂ$
비슷하게 갈루아체 $GF(9)$ 는 quotient ring $ℤ_3[x]/(x^2+1)$ 과 isomorphism임을 보일 수 있다.

reference : https://jjycjnmath.tistory.com/232

이제 이와 연관된 ctf문제들을 살펴보자.

1. [COMPFEST CTF 2023] Swusjask Encryption

chall

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

MultiplicativeGroup이 주어졌고, 이를 활용하여 flag.png를 flag.enc로 저장했다.
MultiplicativeGroup의 곱셈 연산을 보면

a = a_1a_2 - 6969b_1b_2 \ (mod \ p)

b = a_1b_2+a_2b_1-69b_1b_2 \ (mod \ p)

위와 같다. 곱셈 연산의 인자가 $a, b$ 두 개인 것을 보아, 2차식에 대한 polynomial ring이라고 추측할 수 있고, 따라서 $bx+a$ 꼴임을 알 수 있다.

이차식을 $x^2+mx+n$ 이라고 했을 때, $(a_1x+b_1)(a_2x+b_2)$ 를 $x^2+mx+n$ 으로 나눈게 위의 식과 같아야 한다. 계산해보면, $m$ 은 69, $n$ 은 6969임을 알 수 있다.

따라서, 문제에 나온 MultiplicativeGroup의 quotient ring은 $ℤ_n[x]/(x^2+69x+6969)$ 임을 알 수 있다. 이 ring의 order을 구해서 답을 찾는 것은 trivial한 문제이니 생략하겠다.

exploit code

from Crypto.Util.number import *

p = 1179478847235411356076287763101027881
e = 0x10001

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})"

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)

with open("flag.enc", "rb") as f:
    out = f.read()
	output = out.strip()
	enc = bytes_to_block(output)

"""
R = PolynomialRing(Integers(p), 'x')
f = R(x^2 + 69*x + 6969)
quotient_ring = R.quotient_ring(f)
print(quotient_ring.order())
"""

order = 1391170351075774838726551176294895766714925713718991823094447038739350161

flag = []
for i in range(len(enc)):
    a, b = enc[i]%p, enc[i]//p
    m = MultiplicativeGroup(a, b)
    ori = m**(inverse(e, order-1))
    a, b = ori.a, ori.b
    flag.append(a + b*p)

print(block_to_bytes(flag))
open("flag.png", "wb").write(block_to_bytes(flag))

COMPFEST15{find_the_order_of_gruop_81ee36780a}

2. [Imaginary CTF 2023] Sus

chall

from Crypto.Util.number import getPrime, isPrime, bytes_to_long


def sus(sz, d):
    while True:
        p = getPrime(sz)
        pp = sum([p**i for i in range(d)])
        if isPrime(pp):
            return p, pp


p, q = sus(512, 3)
r = getPrime(512 * 3)
n = p * q * r
e = 65537
m = bytes_to_long(open("flag.txt", "rb").read().strip())
c = pow(m, e, n)

print(f"{n = }")
print(f"{e = }")
print(f"{c = }")

만약 quotient ring과 isomorphism을 아는 상태에서 이 문제를 풀었다면, 과연 이러한 풀이를 생각할 수 있었을지 의문이 드는 신박하고 인상 깊었던 문제이다.

문제 제작자인 maple3142의 공식 풀이를 보자.
무작위 3차 polynomial $f(x)$ 에 대하여 quotient ring $ℝ = ℤ_n[x]/f(x)$ 를 생각했을 때, $f(x)$ 가 $p$ 에서의 다항식 field에서 인수분해되지 않는다면 이는 $GF(p^3)$ 과 isomorphism이라는 것이다.

$GF(p^3)$ 의 $order$ 은 $p^3-1$ 이므로 이는 $(p-1)(p^2+p+1)$ 으로 인수분해할 수 있다. 여기서 문제를 보자. $n = p(p^2+p+1)r$ 이므로 만약 $f(x)$ 를 $ℤ_n[x]/f(x)$ 에서 $n$ 제곱하면 그 결과는 $order$ 가 $p-1$ 이 되고, $order$ 가 $p-1$ 이 되려면 $u + 0x + 0x^2$ 꼴이 될 수밖에 없다. 즉, 1차 혹은 2차항의 계수가 $p$ 의 배수가 되는 것이다. 이를 이용하여 $p$ 를 구할 수 있다.

*의문점 - $0+ux+0x^2$ 또는 $0+0x+ux^2$ 꼴이 되는 것이 아닌 $u+0x+0x^2$ 꼴이 되는 이유는 무엇인가? (아는 분이 있다면 댓글로 알려주시면 감사하겠습니다.)

exploit code (sage)

from Crypto.Util.number import *

n = 1125214074953003550338693571791155006090796212726975350140792193817691133917160305053542782925680862373280169090301712046464465620409850385467397784321453675396878680853302837289474127359729865584385059201707775238870232263306676727868754652536541637937452062469058451096996211856806586253080405693761350527787379604466148473842686716964601958192702845072731564672276539223958840687948377362736246683236421110649264777630992389514349446404208015326249112846962181797559349629761850980006919766121844428696162839329082145670839314341690501211334703611464066066160436143122967781441535203415038656670887399283874866947000313980542931425158634358276922283935422468847585940180566157146439137197351555650475378438394062212134921921469936079889107953354092227029819250669352732749370070996858744765757449980454966317942024199049138183043402199967786003097786359894608611331234652313102498596516590920508269648305903583314189707679
e = 65537
c = 27126515219921985451218320201366564737456358918573497792847882486241545924393718080635287342203823068993908455514036540227753141033250259348250042460824265354495259080135197893797181975792914836927018186710682244471711855070708553557141164725366015684184788037988219652565179002870519189669615988416860357430127767472945833762628172190228773085208896682176968903038031026206396635685564975604545616032008575709303331751883115339943537730056794403071865003610653521994963115230275035006559472462643936356750299150351321395319301955415098283861947785178475071537482868994223452727527403307442567556712365701010481560424826125138571692894677625407372483041209738234171713326474989489802947311918341152810838321622423351767716922856007838074781678539986694993211304216853828611394630793531337147512240710591162375077547224679647786450310708451590432452046103209161611561606066902404405369379357958777252744114825323084960942810

R = PolynomialRing(Zmod(n), "x")

while True:
    qr = R.quotient_ring(R.random_element(3))
    res = gcd(int(list(qr.random_element() ^ n)[1]), n)
    if res > 1:
        p = res
        q = p^2 + p + 1
        r = n // (p*q)
        assert p * q * r == n

        phi = (p-1)*(q-1)*(r-1)
        d = inverse(e, phi)
        flag = pow(c, d, n)
        print(long_to_bytes(int(flag)).decode())
        break

ictf{idk_if_it_solvable_if_q_is_2+p+p^2_instead}

3. [WACON CTF 2023] Cry

chall

from Crypto.Util.number import bytes_to_long, getStrongPrime, isPrime

SIZE = 512
e = 65537

with open("flag.txt", "rb") as f:
    m = bytes_to_long(f.read())


def encrypt(m):
    while True:
        p = getStrongPrime(SIZE)
        if p % 4 != 3:
            continue
        q = p**2 + 1
        assert q % 2 == 0
        if isPrime(q // 2):
            break

    r = getStrongPrime(SIZE * 3)
    n = p * q * r
    c = pow(m, e, n)
    return n, c

if __name__ == "__main__":
    n0, c0 = encrypt(m)
    n1, c1 = encrypt(c0)
    n2, c  = encrypt(c1)
    
    assert m < n0 and c0 < n1 and c1 < n2

    print(f"{n0 = }")
    print(f"{n1 = }")
    print(f"{n2 = }")
    print(f"{c = }")

Sus와 같은 컨셉의 문제이다. 이번엔 $n = p(p^2+1)r$ 인 상황이다. 따라서 자연스럽게 4차 방정식을 생각할 수 있다. $order$ 가 $p^4-1$ 인 $x^4+ax^2+b$ 꼴의 4차식에 대한 quotient의 요소를 $n$ 제곱한 결과가 $cx^2+d$ 꼴의 2차식이 되도록 하여, 확률적으로 이들의 $order$ 가 $p^2-1$ 이 되게 할 수 있다. 즉, Sus에서는 $order$ 가 $p-1$ 이었기 때문에 상수 하나만 남게 된 것이고, 이 문제에서는 $order$ 가 $p^2-1$ 이기 때문에 2개의 항만 남기면 된다.

exploit code (sage)

from Crypto.Util.number import *
import random

exec(open("output", "r").read())

e = 0x10001

def dec(n, c):
    R = PolynomialRing(Zmod(n), "x")
    while True:
        a = random.randint(0, n)
        Q = R.quotient((x^2+a)^2+1)
        res = gcd(int(list(Q.random_element() ^ n)[-1]), n//2)
        if res > 1:
            p = res
            q = (p^2 + 1) // 2
            r = n // (2*p*q)
            assert p * q * r * 2 == n

            phi = (p-1)*(q-1)*(r-1)
            d = inverse(e, phi)
            return pow(c, int(d), n)

c1 = dec(n2, c)
c0 = dec(n1, c1)
flag = dec(n0, c0)
print(long_to_bytes(int(flag)).decode())

WACON2023{75e7511bccf428abfb98da2226b5712ce709a9fc9b92ad1b0a3ccb5f2b1cd772}

hakid29

이전 포스트