정보보안:: 유한체 (Introduction to Finite Fields)

유한체 (Introduction to Finite Fields)

이번에 정리할 내용은 AES를 정리하기 전 필요한 이산수학2의 유한체 내용이다.

---

Groups, Rings, and Fields

개요도

Group

• Associative law (교환 법칙)
• Identity (항등원이 있다)
• Inverse (역원이 있다)

• commutative 추가시 abelian group

Subgroup

같은 연산자에 대해서 group의 하위 집합이 group의 성질을 띄우면 subgroup 이라고 한다.

 

Cyclic Subgroup

특정 원소(generator)를 powering하여 group의 모든 원소를 표현할 수 있으면 cyclic group이라고 하고
cyclic group은 subgroup이 될 수 있다.

Ring

Commutative Ring, Integral Domain

• Commutative Ring : Ring + 곱셈 연산에 Commutativity 성질이 있음
• Integral Domain : 곱셈 연산이 identity를 가지고 zero divisor를 가지지 않는 것 (no zero divisor)
  
  • No zero divisor
    a, b가 0이 아닐 때, ab = 0이면 zero divisor라고 한다. 따라서 ab=0이면 a = 0 또는 b = 0이 나와야 한다

 

Field

연산 : addition, subtraction, multiplication, divison (즉, 역원이 존재함을 의미)

---

Modular Arithmetic

나머지 연산 (mod)를 뜻함. 나머지는 양수이며 나누는 수 n 이상이 될 수 없음.

congruence

나머지가 같다는 뜻

congruence

• divisor : b | a = b가 a를 나누어 떨어지게 함.
• congruence의 성질
  두 수가 congruent하다면 a-b는 n으로 나누어 떨어짐

Zn

정수 범위에서 나머지 집합을 의미함

ex) Z_8 = { 0, 1, 2, 3, 4, 5, 6, 7}

• 특징1 : 연산 특징

• 특징2 : commutative ring

Ring 예시 : Z_8

---

The Euclidean Algorithm

확장된 유클리드 알고리즘은 inverse를 구하는데 사용됨

 

---

Finite Fields of the form GF(p)

Finite Field

• 무한한 범위에서 살펴보기 힘드므로 유한한 범위로 제한해서 성질을 살펴볼 것임.\
• Field가 되려면 소수에 대해서 다루어야 함. p^n = Galois Field

Galois Field GF(p)

GCD & Extended Euclidean Algorithm

GCD를 구할 때 ro-r1한 결과와 r1의 GCD를 구하는 것과 동일함

Extended Euclidean Algorithm으로 역원 구하기

참고자료

예시

확장된 유클리드 알고리즘으로 GF(2^8)에서 다항식의 역원 구하기
(Extended euclidean polynomial inverse gf(2^8))

참고자료

https://math.stackexchange.com/questions/67969/linear-diophantine-equation-100x-23y-19/68021#68021

https://math.stackexchange.com/questions/529156/extended-euclidean-algorithm-in-gf28

---

Polynomial Arithmetic

Irreducible polynomial (minimal prime)

g(x)가 1과 자기자신만을 약수로 가지면 irreducible polynomial이라고 한다.

---

Finite Fields of the form GF(2n)

GF(2^8)