현대 암호학: Finite field

Groups
Rings
Fields

Finite Fields of the Form GF(p)

Polynomial Arithmetic
Finite Fields of the Form GF(2n)

---

Group

 

주로 G라고 부름.

G를 공집합이 아닌 집합이라고 하자. 

G의 연산자를 설정하고 G의 원소(a,b)에 대해 a 연산자 b의 값이 정의되어야 한다.

 

군은 4가지 성질을 모두 지녀야 한다.

1. closure (닫힘)

그 집합의 원소와 관계가 있는 원소가 항상 그 집합에 속한다는 성질(닫혀 있다라고 한다.)

 

예시) 모든 a, b ∈ G에서 a · b가 항상 G안에 있다. 즉 G는 ·에 대해 닫혀 있다.

G가 Z{12}인 경우 a ·b = ab는 닫혀 있지 않다. >> 7 · 5 = 35 는  Z{12}에 없음.

 

2. associative (결합 법칙)

모든 a,b,c ∈ G에 대해 (a·b)·c=a·(b·c)이다.

즉 결합 법칙이 가능해야 한다.

 

3. identity element (항등원)

id ∈ G라는 고유 원소가 있다.

고유의 원소란 a · id = id·a = a이 모든 a ∈ G에서 적용되는 원소이다.

주로 곱셈에서는 1이 고유원소이다.

 

4. inverse element (역원)

모든 a∈G에서 특별한 b∈G가 존재한다.

즉 a·b = b·a = id를 충족하는 b가 있어야 한다.

---

Cyclic Group(순환군)

 

backgrounds

지수화:

the group law '·' 이면 앞으로 이는 a의 거듭제곱으로 표현한다.  == a^n

the group law '+'이면 앞으로 이는 a의 n배로 표현한다. == na

 

군이 '·' 인 곳에서 우리는 지수화라고 부른다.

이곳에서는

a^0 = id =1

a^-1 = a의 역원

a^(-n) = (a^-1)^n  (역원의 거듭제곱) 

 

곱셈군 (+)

[0]a = id =0

[-1]a = -a = a의 역원

[-n]a = [n][-1]a  == a의 역원의 배수

 

Order(위수)

G의 order는 G의 크기를 뜻하며 원소의 개수이다.

*fact: G의 위수 m이 있고 a가 G의 원소이면 a^m = id이다.

**응용: G의 위수 m이 있고 a가 G의 원소이면 모든 G의 원소 i에 대해 아래 식이 성립한다.

a^ i = a^ i mod m

 

Generator(생성자)

G의 위수 m이 있고 g가 G의 원소이면 아래 식이 성립한다. 

⟨g⟩ = {g^i : i ∈ Zm}

⟨g⟩의 크기는 항상 m으로 나뉜다.

즉  ⟨g⟩는 그룹 G의 한 원소 g를 사용하여 그룹의 다른 원소를 생성하는 집합이다.

 

만약 ⟨g⟩ = G이면 g는 생성자이다. g의 위수가 m이 되기 때문이다.
이 상태를 G는 순환군이라고 하며 g∈G인 g가 G의 생성자이기 때문이다. 
g^k=1 (mod N) 이 성립하는 최소 k를 g의 순서라고 한다.

(order of g) = ⟨g⟩는 1로 시작해서 1로 끝나면 생성된다. 

---

Ring

 

R이라고 불리며 때때로 {R, +, ×}로 표기되며, 덧셈(+)과 곱셈(×)이라는 두 개의 이항 연산을 갖는 원소들의 집합이다. R의 모든 원소 a, b, c에 대해 다음 공리들이 성립한다.

(A1-A5) 덧셈에 대한 아벨 군: 환 R은 덧셈에 대해 아벨 군이다. 즉, R은 공리 A1부터 A5까지를 만족한다. (결합 법칙, 항등원 존재, 역원 존재, 교환 법칙)
- 덧셈에 대한 군의 항등원은 0으로 표기한다.
- 원소 a의 덧셈에 대한 역원은 -a로 표기한다.

 

(M1) 곱셈에 대한 닫힘:
만약 a와 b가 R의 원소이면, ab (a 곱하기 b) 또한 R의 원소이다. 즉, 곱셈 연산의 결과는 항상 R의 원소 안에 존재한다.

(M2) 곱셈의 결합 법칙:
R의 모든 원소 a, b, c에 대해, a(bc) = (ab)c 가 성립한다. 
(M3) 곱셈의 분배 법칙:

R의 모든 원소 a, b, c에 대해, a(b+c) = ab +ac 가 성립한다.

 

가환환 (Commutative Ring)
환 R이 다음 추가 조건을 만족하면 가환환이라고 한다.
(M4) 곱셈의 교환 법칙:
R의 모든 원소 a, b에 대해 ab = ba가 성립한다.

 

정역 (Integral Domain)
정역은 다음 공리들을 만족하는 가환환이다.
(M5) 곱셈의 항등원:
R 안에 원소 1이 존재하여 R의 모든 원소 a에 대해 a1 = 1a = a가 성립한다. 이 원소 1은 곱셈의 항등원이다.
(M6) 영인자가 없음 (No zero divisors):
R의 원소 a와 b에 대해 ab = 0이면, 반드시 a = 0이거나 b = 0입니다. 즉, 0이 아닌 두 원소를 곱해서 0이 되는 경우는 없다.

---

Field

 

체는 F로 부르고 때때로 {F, +, ×}로 표기되며, 덧셈(+)과 곱셈(×)이라는 두 개의 이항 연산을 갖는 원소들의 집합이다. 체 F의 모든 원소 a, b, c에 대해 다음 공리들이 성립한다.

(A1-M6) 정역: 체 F는 정역 (Integral Domain)이다. 즉, F는 공리 A1부터 A5 (덧셈에 대한 아벨 군 공리)와 M1부터 M6 (곱셈에 대한 닫힘, 결합 법칙, 곱셈의 항등원, 영인자가 없음, 곱셈의 교환 법칙)을 모두 만족한다.

(M7) 곱셈의 역원:
F의 0이 아닌 모든 원소 a에 대해, a(a⁻¹) = (a⁻¹)a = 1을 만족하는 원소 a⁻¹이 F 안에 존재다. 이 원소 a⁻¹을 a의 곱셈에 대한 역원이라고 부른다.
본질적으로, 체는 집합 내에서 덧셈, 뺄셈, 곱셈, 그리고 나눗셈을 할 수 있는 집합이다.

나눗셈은 다음 규칙으로 정의된다: a / b = a(b⁻¹) (b가 0이 아닐 때). 즉, a를 b로 나누는 것은 a에 b의 곱셈에 대한 역원을 곱하는 것과 같다.

 

체의 친숙한 예시:
유리수 집합 (Rational numbers)
실수 집합 (Real numbers)
복소수 집합 (Complex numbers)

 

주의:
정수 집합 (The set of integers)은 체가 아니다. 왜냐하면 모든 0이 아닌 정수가 곱셈에 대한 역원을 가지고 있지 않기 때문다 (예를 들어, 2의 곱셈에 대한 역원은 1/2인데, 이는 정수가 아니다).

 

미리보기: 현대 암호학에서는 군 (특히 유한 아벨 군)과 체 (특히 유한체)가 매우 중요한 역할을 수행하고 있다. (DLP, AES)

---

Finite Field

 

유한체 (Finite Fields)

유한체 GF(p) 형태:

유한체는 많은 암호 알고리즘에서 중요한 역할을 한다.
유한체의 크기 (원소의 개수)는 반드시 소수 p의 거듭제곱 형태인 pⁿ이어야 함을 보일 수 있다. 여기서 n은 양의 정수입니다.
- 크기가 pⁿ인 유한체는 일반적으로 GF(pⁿ)으로 표기한다.
- GF는 유한체를 처음 연구한 수학자 Galois를 기리는 Galois Field의 약자이다.

결론: 유한체의 원소의 개수는 소수의 거듭제곱 형태임

 

예시) + mod 8

행과 열의 값을 더한 뒤 나온 값을  mod 8한 값들을 표로 표현한 것.

*8보다 작은 수를 나누면 몫은 0이고 나머지는 작은 수가 나온다.

 

예시) + mod 7

 

예시) +, x inverse mod 7

+의 항등원은 0이고 x의 항등원은 1이다.

즉 w의 역원을 더하면 나머지가 0, 곱하면 나머지가 1이 나와야한다.

---

Finite fields of the form GF(p)

 

GF(p) 형태의 유한체
즉 소수 p의 크기를 갖는 유한체 GF(p)를 구성하는 방법이다.

GF(p)는 다음과 같은 속성을 갖도록 정의된다.
1. GF(p)는 p개의 원소로 구성된다.
2. 덧셈(+)과 곱셈(×)이라는 두 개의 이항 연산이 이 집합 위에서 정의된다. 덧셈, 뺄셈, 곱셈, 나눗셈 연산을 집합을 벗어나지 않고 수행할 수 있다. 0이 아닌 집합의 각 원소는 곱셈 역원을 갖는다.
3. GF(p)의 원소는 정수 {0, 1, ..., p-1}이며, 산술 연산은 p를 법으로 하는 덧셈과 곱셈이다.

---

Polynomial Arithmetic

 

Zₚ 계수를 갖는 다항식 연산
이 파트는 유한체 Zₚ (또는 GF(p))의 원소를 계수로 갖는 다항식들의 연산에 대한 설명이다.

각각의 구별되는 다항식을 집합의 원소로 간주하면, 그 집합은 환(ring)을 이룬다. (다항식 덧셈은 아벨 군을 이루고, 다항식 곱셈은 결합 법칙을 만족하며, 분배 법칙이 성립한다.)
체(field) 위에서 다항식 연산을 수행하면 나눗셈이 가능하다.
주의: 이것은 정확한 나눗셈이 항상 가능하다는 의미는 아니다. (나머지가 0이 아닐 수 있다.)

 

계수 집합이 체가 아닌 경우 다항식 나눗셈을 시도하면, 나눗셈이 항상 정의되지 않는다는 것을 알 수 있다.
- 계수 집합이 체인 경우에도 다항식 나눗셈이 반드시 존재하지 않는다.
- 나머지가 허용된다는 이해 하에, 계수 집합이 체이면 다항식 나눗셈이 가능하다고 말할 수 있다.


다항식 나눗셈과 기약 다항식
우리는 임의의 다항식 f(x)를 다음과 같은 형태로 쓸 수 있다.
f(x) = q(x)g(x) + r(x)

여기서 r(x)는 나머지이다.
따라서 r(x) = f(x) mod g(x).
만약 나머지가 없다면, g(x)가 f(x)를 나눈다.

이것은 g(x) | f(x) 와 같이 표기한다.
이때 g(x)는 f(x)의 인수(factor) 또는 약수(divisor)라고 말할 수 있다.
체 F 위의 다항식 f(x)는 만약 f(x)가 F 위에서, 그리고 f(x)보다 차수가 낮은 두 다항식의 곱으로 표현될 수 없을 때, 기약(irreducible)이라고 불린다.
- 기약 다항식은 소수 다항식(prime polynomial)이라고도 불린다.

Polynomial GCD

 

다항식의 최대공약수 (Greatest Common Divisor, GCD)에 대한 정의
다항식 c(x)는 다음 조건들이 참일 때 다항식 a(x)와 b(x)의 최대공약수라고 한다.

- c(x)는 a(x)와 b(x) 둘 다를 나눈다.
- a(x)와 b(x)의 임의의 공약수는 c(x)의 약수이다.

 

동등한 정의는 다음과 같다.
gcd[a(x), b(x)]는 a(x)와 b(x) 둘 다를 나누는 다항식 중에서 가장 높은 차수를 갖는 다항식이다.

 

계수가 체(field)의 원소인 두 다항식의 최대공약수는 유클리드 알고리즘을 확장하여 찾을 수 있다.

---

Finite Fields of the Form GF(2ⁿ)

 

 

 

 

1. 덧셈 및 곱셈표의 대각선 대칭: 덧셈표와 곱셈표는 주대각선을 기준으로 대칭이다. 이는 덧셈과 곱셈의 교환 법칙(a + b = b + a, a * b = b * a)을 따른 것이다. 이러한 대칭성은 8을 법으로 하는 연산을 사용하는 표 5.1에서도 나타난다.

2. GF(2³)의 0이 아닌 원소의 곱셈 역원 존재: 표 5.2로 정의된 GF(2³)의 모든 0이 아닌 원소는 곱셈 역원을 갖는다. 이는 표 5.1의 경우와는 대조적이다. 

3. GF(2³)의 체 조건 만족: 표 5.2로 정의된 구조는 유한체의 모든 요구 사항을 만족한다. 따라서 이 구조를 GF(2³)이라고 부를 수 있다. (유한체는 덧셈과 곱셈에 대해 특정 공리들을 만족해야 하며, 특히 0이 아닌 모든 원소가 곱셈 역원을 가져야 한다.)

4. GF(2³) 원소의 3비트 할당: 편의를 위해 GF(2³)의 각 원소에 사용된 3비트 할당 방식을 보여준다. (이전 답변에서 설명된 다항식 표현과 이진수 표현 간의 대응 관계를 의미한다.)

 

GF(2³)은 덧셈과 곱셈에 대해 교환 법칙이 성립하고, 0이 아닌 모든 원소가 곱셈 역원을 갖는 체의 모든 조건을 만족한다는 중요한 속성을 강조한다. 또한 GF(2³)의 원소들이 3비트 이진수로 표현될 수 있다.

 

---

유한체 GF(2³) 구성:

n차 기약 다항식을 법으로 하는 모든 다항식의 집합은 그림 5.2의 공리를 만족하며, 따라서 유한체를 형성함을 보일 수 있다. 또한, 주어진 크기의 모든 유한체는 동형이다. 즉, 원소의 표현이나 레이블은 다를 수 있지만 구조는 동일하다.

크기 2³의 유한체 GF(2³)을 구성하기 위해서는 3차 기약 다항식을 선택해야 한다. GF(2) 위에는 두 개의 3차 기약 다항식만 존재한다: x³ + x + 1과 x³ + x² + 1. (x³ + x² + 1)을 사용하여 GF(2³)의 덧셈 및 곱셈표 (표 5.3)를 구성했다. 표 5.3의 표 구조는 표 5.2와 동일하다. 따라서 크기 2³의 체를 정의하는 방법을 성공적으로 찾았다.

이제 표에서 덧셈과 곱셈을 쉽게 읽을 수 있다. 예를 들어, 이진수 100과 010의 합은 110이다. 이는 다항식 x²와 x의 합이 x² + x와 동일하다는 의미이다. 또한, 100과 010의 곱은 011입니다. 이는 x² * x = x³이 되고, x³ mod (x³ + x + 1) = x + 1과 동일하며, 이는 011과 같다는 의미이다.

---

곱셈 역원 찾기:

확장된 유클리드 알고리즘은 두 다항식의 최대공약수(GCD)를 찾는 데 적용될 수 있을 뿐만 아니라, 다항식 a(x)를 법으로 하는 다항식 b(x)의 곱셈 역원을 찾는 데에도 적용될 수 있다. 특히, 다항식 b(x)의 차수가 다항식 a(x)의 차수보다 작고, gcd(a(x), b(x)) = 1이라면, 알고리즘은 a(x)를 법으로 하는 b(x)의 곱셈 역원을 찾을 수 있다.

 

a(x)가 기약 다항식이면, 그 자체 또는 1 이외의 인수를 갖지 않으므로, gcd(a(x), b(x)) = 1이다. 따라서 확장된 유클리드 알고리즘은 정수에서와 유사한 방식으로 사용할 수 있다. 정수 a(x)의 차수가 정수 b(x)의 차수보다 크면, 방정식 a(x)v(x) + b(x)w(x) = gcd(a(x), b(x))의 해 v(x)와 w(x)를 찾고자 한다.

만약 d(x) = 1이면, w(x)는 a(x)를 법으로 하는 b(x)의 곱셈 역원입니다. 계산은 다음과 같습니다.

a(x)v(x) + b(x)w(x) = d(x)

만약 d(x) = 1이면, b(x)w(x) = 1 (mod a(x))이므로, w(x)는 a(x)를 법으로 하는 b(x)의 곱셈 역원입니다.

---

컴퓨터 기반 비트 사용

계수가 0 또는 1이기 때문에, 이러한 다항식은 비트 스트링으로 표현될 수 있다. (예: x² + 1은 계수 1, 0, 1을 갖는 2차 다항식이므로 비트 스트링 101로 표현될 수 있다.)

덧셈은 이러한 비트 스트링들의 배타적 논리합 (XOR) 연산이 된다. (이전 GF(2³) 덧셈표에서 확인한 내용과 같다.)

곱셈은 시프트 (shift) 연산과 XOR 연산의 조합으로 수행될 수 있다. (이는 손으로 하는 긴 곱셈 방식을 컴퓨터 연산에 맞게 최적화한 것이다.)

모듈로 축약 (기약 다항식으로 나눈 나머지 계산)은 가장 높은 차수의 항을 기약 다항식으로 나눈 나머지로 반복적으로 치환함으로써 수행된다(이 또한 시프트 및 XOR 연산을 사용합니다).

---

생성자 사용
크기가 q인 유한체 F의 생성자 g는 그 첫 번째부터 q-1번째 거듭제곱(g¹, g², ..., g^(q-1))이 F의 모든 0이 아닌 원소를 생성하는 원소이다.

즉, F의 원소는 0, g⁰(=1), g¹, ..., g^(q-2)로 구성된다.
다항식 f(x)에 의해 정의된 체 F를 생각해 보자.

F에 포함된 원소 b가 f(b) = 0을 만족하면 b를 다항식의 근(root)이라고 한다.
마지막으로, 기약 다항식의 근 g는 해당 다항식으로 정의된 유한체의 생성자임을 보일 수 있다.

유한체의 0이 아닌 모든 원소를 거듭제곱으로 생성할 수 있는 특별한 원소인 생성자의 개념을 소개합니다. 또한, 다항식의 근의 정의를 설명하고, 특히 기약 다항식의 근이 해당 다항식으로 만들어진 유한체의 생성자가 될 수 있다는 중요한 사실을 강조합니다. 이는 유한체의 구조를 이해하고 효율적인 연산을 수행하는 데 유용합니다.