[정보보안] 보안 수학 (Group, Ring, Field, GF, 유클리드 알고리즘)

1. Group, Ring, Field

Group은 집합 $G$와 이항 연산 $\cdot$에 대해 다음 네 가지 공리(Axioms)를 만족하는 구조이다.

• 닫힘 (Closure): 모든 $a, b \in G$에 대해 $a \cdot b \in G$이다.
• 결합법칙 (Associative): $(a \cdot b) \cdot c = a \cdot (b \cdot c)$가 성립한다.
• 항등원 (Identity): 모든 $a \in G$에 대해 $e \cdot a = a \cdot e = a$를 만족하는 $e \in G$가 존재한다.
• 역원 존재 (Inverse): 각 $a \in G$에 대해 $a \cdot a^{-1} = e$를 만족하는 $a^{-1} \in G$가 존재한다.

이를 $G = \langle S, \cdot \rangle$의 형식으로 쓴다. 예를 들어 $\langle Z_{10}, + \rangle$에서는

• 집합 ($Z_{10}$): 모듈로 10에 대한 집합 ${0, 1, 2, 3, 4, 5, 6, 7, 8, 9}$를 의미한다.
• 연산 ($+$): 해당 집합 내에서 수행되는 이항 연산으로, 여기서는 모듈로 10 덧셈을 의미한다.

이런 뜻이다. 이게 Group을 만족하는데 Closure, 결합법칙, 항등원, 역원을 만족하기 때문이다. 

 

 

Abelian Group은 Group에 교환법칙(Commutative)인 $a \cdot b = b \cdot a$까지 만족하면 Abelian Group이된다. 위 예시에서도 덧셈 연산에 대해 교환법칙($a + b = b + a$)이 성립하므로 Abelian Group이라고 할 수 있다.

 

 

Ring은 두가지 연산 (덧셈, 곱셈)에 대해 아래 3가지 조건들을 만족해야한다.

1. 덧셈에 대해 abelian group이어야한다. (Closure, 결합법칙, 항등원, 역원, 교환법칙)
2. 곱셈에 대해 Closure, 결합법칙을 만족해야함.
3. 덧셈과 곱셈의 분배법칙이 성립해야한다. $a(b+c) = ab + ac$.

 

Integral Domain은 Ring 중에 다음 조건을 추가로 만족해야한다.

1. 곱셈에 대해 교환법칙을 만족해야한다. ($ab = ba$)
2. 곱셈 항등원 1이 존재해야한다.
3. Zero Divisor가 없어야한다. ( $ab = 0$ 이면 $a=0$ 또는 $b=0$ 이어야한다.)

*Zero Divisor: 0이 아닌 두 원소를 곱했을 때 결과가 0이 되게 만드는 원소 ($Z_8$에서 6과 4는 Zero divisor이다. $6 \times 4 = 24 % 8 = 0 $)

 

 

Field는 수집합과 두개의 이항연산(덧셈, 곱셈)으로 다음 조건을 만족해야한다.

1. 덧셈에 대해 abelian group 만족 (Closure, 결합법칙, 항등원, 역원, 교환법칙)
2. 곱셈에 대해 0을 제외한 abelian group 만족 (Clousre, 결합법칙, 항등원, 역원, 교환법칙)
3. 덧셈과 곱셈의 분배법칙: $a(b + c) = ab + ac$ 및 $(a + b)c = ac + bc$가 성립한다.

Field는 Integral Domain의 성질을 포함한다. 따라서 Field내에서는 Zero Divisor가 존재하지 않는다. 이는 0이 아닌 모든 원소가 곱셈 역원을 가진다는 성질과 일치한다. 이를 통해 나눗셈을 $a / b = a \cdot b^{-1}$로 정의할 수 있다.

 

 

---

2. Finite Field - GF

Finite Field(유한체)는 원소의 개수가 유한한 Field를 말한다. Finite Field에서 원소의 개수는 반드시 소수 $p$의 거듭제곱 형태인 $p^n$이어야 한다. 이를 갈루아 체(Galois Field)라고 하며 $GF(p^n)$으로 표기한다.

• 소수 체 (Prime Field, $n=1$): $GF(p)$ 형태로, 모듈로 $p$ 연산을 수행하는 정수 집합 $Z_p$
• 이진 체 (Binary Field, $p=2, n>1$): $GF(2^n)$ 형태로, 다항식 연산을 사용한다.

 

$GF(p)$는 집합 ${0, 1, \dots, p-1}$에 대해 모듈로 $p$ 산술 연산을 수행하는데 결과적으로 $GF(p)$ 내에서는 덧셈, 뺄셈, 곱셈뿐만 아니라 0으로 나누는 것을 제외한 나눗셈이 자유롭게 가능해야한다. 예를 들어 GF(7)은 다음과 같다.

 

---

3. 유클리드 알고리즘

유클리드 알고리즘은 큰 수들의 최대 공약수를 쉽게 구하는 알고리즘이다. 

$$gcd(a, b) = gcd(b, a \pmod b)$$

위 식을 재귀적으로 반복한다. $gcd(a, b) = 1$인 경우 두 수를 서로소(Relatively Prime)라고 한다.

연산의 종료 조건은 b=0일 때 a가 최대공약수가 된다는 것이다. $gcd(a, 0)=a$

 

$gcd(6, 4)$ → $gcd(4, 2)$ → $gcd(2, 0)$

∴ $gcd(6, 4) = 2$

 

cpp 코드로 확인해보면 아래와 같다.

gcd 연산의 종료조건은 b가 0이 되었을 때 a가 최대 공약수가 된다는 것이다.

 

[반복문 방식]

int gcd(int a, int b) {
    int r;
    while (b > 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

 

[재귀 방식]

int gcd(int a, int b) {
    if (b==0) return a;
    return gcd(b, a % b);
}