Elliptic Curve Cryptography를 서술하기 위해서 알아두어야 할 수학적 용어들이 너무 많다. 기본적으로 Cheatsheet 느낌으로 최대한 적어보았으니 이해에 도움이 되길 바란다.

집합(Set)

정의는 특정한 조건에 맞는 별개의 원소들의 모임 이다. 수학시간에 이런식으로 정의되어 있는 경우를 많이 보았을 텐데. 이것이 Set이다.

이렇게 정의된 Set이 있을 때, 앞의 $A$ 가 바로 Set 이며, Set 안에 들어있는 숫자 $1, 2, 3, 4, 5$는 각각 Element(원소) 이다. 원소 $elem$ 과 집합 $A$ 가 있다고 할 때, Element와 Set의 관계를 나타내는 기호가 다음과 같다.

• $elem \in A$ : 원소 $elem$이 집합 $A$ 에 속해있다.
• $elem \notin A$ : 원소 $elem$이 집합 $A$ 에 속해있지 않다.

Element와 Set의 관계처럼 두 Set에 대해서도 관계를 서술할 수 있다. 집합 $A, B$ 가 존재할 때

• $A \subset B$ : 집합 $A$ 가 집합 $B$ 에 속해있다 ( A가 B의 subset이다 | 부분 집합이다)
• $A \not\subset B :$ 집합 $A$ 가 집합 $B$ 에 속해있지 않다 ( A가 B의 subset이 아니다 )

정도로 설명할 수 있겠다.

줄임기호

수학 기호를 보다 보면 알 수 없는 글자들이 갑자기 있는 경우가 많은데, 정의를 위해 필요한 여러 문구들을 수학자들이 기호로 정의해 두었기 때문이다. 이후 나올 이야기 중에 등장할 수 있는 줄임 기호는 다음과 같다.

• $\exists$ : that exist
• s.t. : such that
• $\forall$ : for all

즉, 이를 이용해서,

집합 A의 모든 원소 a에 대해 a b = b a = 1을 만족하는 값 원소 b가 있다 ⇒ 라는 의미를

이렇게 정리할 수 있다.

Modulo 연산

즉 $mod\ n$ 일때 $A$ 에 대한 modulo 연산은 A를 n으로 나눈 값의 나머지이다. 예시를 통해 설명해 보자면

이런 식으로 계산할 수 있다. 자연스럽게 모든 자연수에 대하여 modulo N 연산의 결과물은 0부터 N-1 사이의 정수가 되므로, 그 자체로 순환하는 성질을 가지고 있다고 생각할 수 있다.

연산에 대하여

계속 타원곡선 더하기, 타원곡선 곱하기처럼 우리가 알고 있는 더하기와 곱하기라는 용어가 나와서 오히려 헷갈릴 수 있다고 생각한다. 하지만, 이런 곱하기와 더하기라고 생각하는 것이 아닌, 타원곡선 더하기 와 타원곡선 곱하기 와 같이 이름 그대로 받아들여야 한다. 이러한 특수한 그룹 내에서 일반적인 연산으로는 의미있는 결과를 얻어내지 못하는 경우도 많기 때문에, 새로운 연산을 정의해서 사용하는 경우도 꽤나 자주 볼 수 있다.

---

타원 곡선

Group과 Ring 그리고 Field

여기는 정의를 알고, 실제 예시와 비교해보는게 더욱 이해가 빠르다.

Group

정의: 특정한 연산 * 에 대해, * 를 연산으로 갖는 Set $G ( \ne \empty )$ 이 임의의 $\forall a, b, c \in G$ 에 대해 아래 조건을 만족한다면, Set G는 Group이다.

• 결합법칙: $(a * b) * c = a * (b * c)$
• 항등원 e의 존재 : $e \in G,\ a * e = e * a = a$
• 역원 $a^{rev}$ 의 존재 : $a^{rev} \in G,\ a * a^{rev} = a^{rev} * a = e$
• 닫힘: $\forall a, b.\ \ a*b \in G$

이러한 조건을 만족하는, 가장 쉬운 예시로는 정수가 있다. 특정한 연산 * 을 사칙연산의 더하기에 대입해보면 생각이 쉽다. 임의의 정수 $a, b, c$ 에 대해 다음과 같은 조건을 만족하기 때문이다.

• 결합법칙: $(a + b) + c = a + (b+c)$ 성립
• 항등원 $e = 0_{R}$ 의 존재: $0 \in G, a + 0_{R} = 0_{R} + a = a$
• 임의의 a에 대한 역원 -a 존재
• 더하기 연산은 모든 정수에 대해 닫혀있음

이러한 설명들을 찾아보다 보면, 아벨군(Abelian group) 이라는 용어가 자주 보인다. 어려운 내용은 아니다. * 를 연산으로 갖는 그룹 G에 대해, 가환성(Commutativity) 를 만족하는 그룹을 아벨 그룹이라고 부른다. ( 혹은 가환군이라는 표현도 있다 )

가환성이란 다음과 같은 조건을 충족하는지 여부이다.

• $\forall a, b \in G$ 에 대해, $a * b = b* a$ 를 충족

덧셈과 곱셉 연산은 모두 가환성을 충족한다. 그렇기 때문에 덧셈을 연산으로 쓰는 그룹을 덧셈 아벨 그룹, 곱셈을 연산으로 곱셈 아벨 그룹 이라고 부른다.

Ring (환)

두가지 연산 ( 덧셈 +, 곱셈 $\cdot$ )을 모두 충족하는 군을 환(Ring)이라고 한다. 환(Ring)이 되기 위해서 필요한 조건을 정확히 나열하자면 다음과 같다.

• 환 $R$ 은 덧셈 Abelian Group임
• $\forall a, b, c \in R, (a \cdot b) \cdot c = a \cdot ( b \cdot c )$
• $\forall a, b, c \in R, (a + b) \cdot c = a \cdot c + b \cdot c$
• $\forall a, b, c \in R, a \cdot ( b + c ) = a \cdot b + a \cdot c$

Ring에도 가환성이 있는데, 곱셈의 교환법칙을 성립하는 Ring을 의미함, 즉 Ring $R$ 에 대해

• $\forall a, b \in R, a\cdot b = b\cdot a$

가 성립하는 Ring을 Commutative Ring(가환환) 이라고 함. 더 나아가, 곱셈에 대한 항등원이 존재하는 Commutative Ring을 Commutative Unital Ring (단위원을 가진 가환환) 이라고 한다.

• $\forall a \in R, \exists\ 1_{R}\ s.t.\ a\cdot1_{R} = 1_R \cdot a = a$

Field

Ring $R$ 이 Commutative Unital Ring (단위원을 가진 가환환) 일 때,

이때 $a$ 는 가역원, $b$ 는 역원이라고 한다. 이때 단위원을 갖는 가환환 $F$ 에서, $F^* = F - \{0\}$ 의 모든 원소가 가역원이면, 즉

를 충족한다면 이 가환환 $F$ 는 Field(체) 이다.

---