[Zer0pts 2023] - elliptic ring rsa

이 문제는 rsa 계산을 Elliptic ring 내에서 하는 문제이다. 문제를 해석하고 나면 신박한 발상이라고 생각되기도 하는데, 어떻게 이런 생각으로 문제를 냈는지 신기하다. 문제를 풀면서 한 가지 이상했던 점은,, 뭔가 딱 이거다 !! 라고 생각한 아이디어가 있는 것이 아니라 그냥 적당히 ~ 흘러가다 보니 풀린 문제인 것 같다. ( 아마 인수들이 작아서 생긴 문제가 아닐까..?)

🖲️ Code Analysis

import string
import random

flag = os.environb.get(b"FLAG", b"dummmmy{test_test_test}")

class EllipticRingElement:
	point = None
	def __init__(self, point):
		self.point = point

	def __add__(self, other):
		if self.point == dict():
			return other
		if other.point == dict():
			return self
		res = self.point.copy()
		for k in other.point.keys():
			if k in res:
				res[k] += other.point[k]
				if res[k] == 0:
					res.pop(k)
			else:
				res[k] = other.point[k]
				if res[k] == 0:
					res.pop(k)
		return EllipticRingElement(res)

	def __mul__(self, other):
		if self.point == dict() or other.point == dict():
			return self.point()
		res = dict()
		for k1 in other.point.keys():
			for k2 in self.point.keys():
				E = k1 + k2
				k = other.point[k1] * self.point[k2]
				if E in res:
					res[E] += k
					if res[E] == 0:
						res.pop(E)
				else:
					res[E] = k
					if res[E] == 0:
						res.pop(E)
		return EllipticRingElement(res)

	def __repr__(self):
		st = ""
		for k in self.point.keys():
			st += f"{self.point[k]}*({k[0]}, {k[1]}) + "
		return st[:-3]

class EllipticRing:
	E = None
	Base = None
	def __init__(self, E):
		self.E = E
		self.Base = E.base()

	def __call__(self, pt):
		for P in pt:
			pt[P] = self.Base(pt[P])
		return EllipticRingElement(pt)

	def zero(self):
		return EllipticRingElement(dict())

	def one(self):
		return EllipticRingElement({E(0): self.Base(1)})

	def pow(self, x, n):
		res = self.one()
		while n:
			if (n & 1):
				res = res * x
			x = x * x
			n >>= 1
		return res

	def encode(self, m, length):
		left = random.randint(0, length - len(m))
		pad1 = "".join(random.choices(string.ascii_letters, k=left)).encode("utf-8")
		pad2 = "".join(random.choices(string.ascii_letters, k=length-len(m)-left)).encode("utf-8")
		m = pad1 + m + pad2

		Ps = []
		while len(Ps) < length:
			PP = self.E.random_element()
			if PP not in Ps:
				Ps.append(PP)
		Ps = sorted(Ps)

		M = dict()
		for coef, pt in zip(m, Ps):
			M[pt] = self.Base(coef)
		return EllipticRingElement(M)

def random_prime_bits(nbits):
	return random_prime(2^nbits-1, false, 2^(nbits-1))

nbits = 8
p = random_prime_bits(nbits)
Fp = GF(p)

a = Fp.random_element()
b = Fp.random_element()
E = EllipticCurve(Fp, [a, b])

ER = EllipticRing(E)

P = ER.encode(flag, 30)

e = 13
C = ER.pow(P, e)

print(f"p: {p}")
print(f"C: {C}")
print(f"a: {a}")
print(f"b: {b}")
print(f"e: {e}")

코드를 해석하고 대충 설명해보자면 다음과 같다. 

1. 처음에 flag 의 각 문자의 ord 를 기반으로 elliptic curve 상에 존재하는 점들과 대응시킨 dictionary 를 생성한다. ( 이 과정에서 앞과 뒤에 padding을 붙여주어 30 길이가 되도록 한다.)

2. 그 dictionary 를 13 제곱하게 되는데, 이는 정수에서의 곱셈과 같이, 각 자릿수를 각각 곱해서 더하는 것과 비슷하다. 하지만, 각 점들이 자릿수를 표현하는 하나의 기준이기 때문에, 각 point 를 더한 값에 더해주게 된다.. 

설명이 조금 난잡하여 덧붙이자면, a 라는 point 에 k 값이 대응되는 dictionary 가 있을 때, 이를 제곱하게 되면 a+a 에 k*k 가 대응된다고 보면 되겠다. 이렇게 점을 더했을 때의 결과값이 같은 점으로 대응된다면, 계수를 곱한 값들의 합을 계수로 가진다. 

💡 Main Idea

문제를 처음 보았을 때, 약간 진법? 과 비슷하다고 생각했다. 각 자릿수르 기반으로 곱하고 연산을 진행하기 때문에 결국은 정수 상의 연산, 그리고 진법 연산과 비슷하다고 판단할 수 있다. Elliptic Curve 의 modulus 또한 211 로 상당히 작기 때문에, order 또한 매우 작을 것이고, 그렇다면 역연산도 적은 시간 내에 가능할 것이라고 예상할 수 있다. 

 

여기서 진법을 표현하기 위해서는 Polynomial Ring 을 이용해서 하나의 점을 x 라고 두고, 다른 모든 점들을 $x^i$ 꼴로 표현할 수 있지 않을까? 따라서 $E.order() = 192 $ 이기 때문에 $order$ 가 192 인 특정한 점을 골라 그 점을 x라고 두고 다른 모든 점들을 표현하면 결국 $x^{192}$ 정도의 차수를 가진 방정식이 만들어질 것이다. 

 

또한, 13거듭제곱의 역연산을 해야 하고, E 의 $order$ 이 192이기 때문에 $x^{192} == 1$로 이 방정식을 계산해주어야 한다. 

이 계산을 위해서는 sage 의 GF, 즉 갈루아 필드를 사용해주면 쉽게 계산할 수 있다.  

📖 Exploit Code

from output import *
C = C.split(" + ")
for i in range(len(C)):
    C[i] = C[i].split("*")

Fp = GF(p)
E = EllipticCurve(Fp, [a, b])

enc = dict()
for i in range(len(C)):
    try:
        enc[eval("E"+C[i][1])] = int(C[i][0])
    except:
        enc[E(0)] = int(C[i][0])

proot = None
for e in enc.keys():
    if e.additive_order() == E.order():
        proot = e
        break

P = GF(p^192, "x", modulus=x^192 - 1, check_irreducible=False)
f = 0

for i in range(E.order()):
    try:
        coef = enc[proot * i]
        f += coef * P.gen()^i
    except:
        pass

ord = f.multiplicative_order()
d = inverse_mod(13, ord)
f = f^d

flag = dict()
for i, coeff in enumerate(f.list()):
    flag[proot*i] = coeff

order = sorted(flag)

for c in order:
    try:
        print(chr(flag[c]), end='')
    except:
        pass

이렇게 주어진 f 의 order 를 계산하고, 대응되는 d 를 계산한 후에, f를 다시 역연산해주면 원래 방정식을 구할 수 있다. 

( 앞의 padding 을 제외하고 나면 flag = zer0pts{Gr0up_r1ng_meow!!!} )