[암호수학] 암호수학 요약 - 대수학

 

대수적 구조(Algebraic Structures)

집합과 집합 내 원소들에 적용되는 연산을 통틀어 대수적 구조라 한다.

일반적 세 개의 대수적 구조는 군(Group), 환(Ring), 체(Field) 이다.

 

정의 1. 군 (Group)

공집합이 아닌 집합 \(G\) 위에 다음 조건을 만족하는 이항연산 \(\circ\) 가 정의될 때, \( <G, \circ >\) 를 군이라 한다.

• (닫힘) 집합 \(G\) 의 원소 \(a, b\) 에 대해 정의된 이항연산 \(\circ\) 를 했을 때의 값 \(c\) 는 집합 \(G\)의 원소이다.
  \( a \circ b = c \ (a, b, c \in G)  \)
• (결합법칙) \(G\) 의 임의의 원소 \( a, b, c\ \) 에 다음이 성립한다.
  \( (a\circ b) \circ c = a \circ (b \circ c) \)
• (항등원) \(G\) 의 모든 원소 \(a\) 에 대해 다음이 성립하는 \(e \in G \) 가 존재해야 한다.
  \( a \circ e = e \circ a = a \). 이 때 \(e\)를 \(G\) 의 단위원 또는 항등원(Identity) 라고 한다.
• (역원) \(G\) 의 각 원소 \(a\) 에 대해 다음이 성립하는 \(a^{-1}\) 이 \(G\) 에 존재해야 한다.
  \( a \circ a^{-1} = a^{-1} \circ a = e \). 이 때 \(a^{-1}\) 를 \(a\) 의 역원(inverse)이라 한다.

군이 추가적으로 교환법칙을 성립하면 아벨군(abelian group)이라 한다.

 

정의 2. 아벨군 (Abelian group)

\(<G, \circ >\) 가 군일 때 이 군의 이항연산 \( \circ \) 가 다음을 만족하면 이 군을 아벨군 또는 가환군(commutative group)이라 한다.

• (교환법칙) \(G\) 의 임의의 원소 \(a\) 와 \(b\) 에 대해 다음이 성립한다.
  \(a \circ b = b \circ a\)

군의 이항연산이 덧셈 계열 연산일 때 => 덧셈군(additive group)

군의 이항연산이 곱셈 계열 연산일 때 => 곱셈군(multiplicative group)

군의 집합이 유한할 때 => 유한군(finite group)

군의 집합이 무한할 때 => 무한군(infinie group)

 

위수(order) : 군 집합의 원소 개수 \(|G|\)

군의 위수를 나타내기 위해 \(G_n\) 과 같이 표기할 수 있음.

 

 

정의 3. 부분군 (subgroup)

\(<G, \circ>\) 가 군일 때 \(G\) 의 부분집합 \(H(\ne \varnothing)\) 가 이항연산 \(\circ\) 에 관하여 군을 이루면 \(<H, \circ >\) 는 \(<G, \circ >\) 의 subgroup(부분군)이라 한다.

 

부분순환군 (cyclic subgroup)

군 \(G\) 의 각 원소 \(a\) 에 대해 부분군 \(H = \{a^n | n \in \mathbb{Z}\} \) 는 \(a\) 에 의해 생성된 부분순환군이라 한다.

이 군은 \(<a>\) 로 표기한다.

여기서 \(a^0 = e\) 이며 \(a^n\) 은 \(a\) 를 피연산자로 군의 이항연산을 \(n\) 번 수행한 것을 말하며, \(a^{-n}\) 은 \(a^{-1}\)를 피연산자로 군의 이항연산을 \(n\) 번 수행한 것을 말한다. \(a^3 = a \circ a \circ a\) 이고, \(a^{-2} = a^{-1} \circ a^{-1} \) 이다.

 

\(a^s, a^t \in H\) 에 대해 \(a^sa^t = a^{s+t} \in H\) 이므로 이항연산에 대해 \(H\)는 닫혀있다.

\(a^0 = e \) 이므로 항등원 \(H\) 에 존재하며 모든 원소의 역원이 존재한다.

따라서 \(H\)는 부분군이 된다.

\(G\)가 유한군이면 \(H\)도 유한군이다. 그러므로 \(a\)를 피연산자로 군의 이항연산을 계속 수행하다 보면 \(a^n=e\) 가 되어야한다.

 

생성자(generator)

\(a \in G\) 에 대해 \(G = <a>\) 이면 \(G\)를 순환군(subgroup)이라 하며, 이 때 \(a\)를 이 군의 생성자(generator) 라 한다.

어떤 원소가 군의 생성자가 되기 위해서는 그 원소의 위수가 군의 위수와 같아야 한다.

\(n > 0\)이 원시근을 가지기 위한 필요충분조건은 \(p\) 가 소수이고, \(k \ge 1\) 인 정수일 때, \(n = 2, 4, p^k, 2p^k\) 이다.

따라서 \(\mathbb{Z}^{*}_n\) 가 순환군이 되기 위해서는 \(n = 2, 4, p^k, 2p^k\) 이어야 한다.

 

군 \(G\)의 원소 \(a\)의 위수가 \(n\)일 때, 정수 \(m\)에 대해 \(a^m\)의 위수는 \(\frac{n}{gcd(n, m)}\) 이다. 즉, \(a^m\)들의 위수는 항수 \(a\) 의 위수의 약수가 된다.

 

 

정리 1. 위수 \(n\) 인 유한순환군 \(G=<a>\)의 부분군은 모두 순환군이고, 그 위수는 \(n\)의 약수이다.

 

정리 2. 위수 \(n\) 인 유한순환군 \(G=<a>\)에 대해 \(d\)가 \(n\)의 양의 약수이면 위수가 \(d\) 인 \(G\)의 부분군은 오직 하나 존재한다.

 

정리 3. 유한순환군 \(G = <a>\)의 위수가 소수인 \(q\) 이면 항등원 \(e\) 를 제외한 \(G\)의 모든 원소는 \(G\) 의 생성자가 된다.

 

 

 

정의 4. 환(Ring)

집합 \(R(\ne \varnothing) \) 위에 이항연산 덧셈\(+\)과 곱셈 \(\bullet\)이 정의되어 있고, 또 다음이 성립하면 \(<R, +, \bullet>\) 를 환이라 한다.

 

• A. \(<R, +>\) 는 아벨군이다.
  • A.1 (결합법칙): \( (a+b)+c = a+(b+c)\)
  • A.2 (교환법칙): \( a+b = b+a\)
  • A.3 (영원(항등원)): 모든 원소 \(a \in R\) 에 대해 \(a+0=0+a=a\)가 성립하는 \(0 \in R\) 이 존재한다.
  • A.4 (역원): 각 원소 \(a \in R\)에 대해 \(a+(-a)=(-a)+a=0\)이 성립하는 \(-a \in R\) 이 존재한다.
• M.1 (결합법칙): \((a \bullet b) \bullet c = a \bullet (b \bullet c) \)
• D. (분배법칙): \( a \bullet (b+c) = (a \bullet b) + (a \bullet c), (a+b) \bullet c = (a \bullet c) + (b \bullet c) \)

환은 덧셈연산과 곱셈연산을 모두 고려하는 대수적구조이다.

덧셈연산에 대해서는 군을 형성하지만 곱셈연산에 대해서는 군을 형성하지 않아도 된다.

곱셈에 대해 교환법칙이 성립하면 가환환(commutative ring)이라 하며, 가환환이 아닌 환을 비가환환(non-commutative ring)이라 한다.

 

• M.2 (결합법칙): \(a \bullet b) = (b \bullet a)\)

환 \(R\)이 다음 조건을 추가적으로 만족하면 이 환을 단위원 1을 가진 환이라 한다.

• M.3 (단위원): 모든 원소 \(a \in R\)에 대해 \(a \bullet 1 = 1 \bullet a = a \) 가 성립하는 \(1 \in R\)이 존재한다.

M.3 조건까지 만족하면 환 \(R\)은 덧셈과 곱셈에 대한 항등원을 모두 같는다. (0은 덧셈의 항등원, 영원. 1은 곱셈의 항등원, 단위원)

 

• M.4 (역원): 각 원소 \( a \in R, a \neq 0\) 에 대해 \(a^-1 \bullet a = 1\) 이 성립하는 \( a^{-1} \in R \) 이 존재한다.
  \( a \bullet b = 0\) 이면 \(a = 0 \) 또는 \(b = 0\)이다.

 

정의 5. 체(Field)

덧셈과 곱셈에 대해 모두 아벨군을 형성한 환 \(R\) 은 체(field)라 한다.

아벨 군이 아닌 군일 경우 사체(skew field)라 한다.

 

정의 6. 갈로아 체 (Galois field)

\(p\)가 소수일 때 \(\mathbb{Z}_p\)는 위수가 \(p\)인 체가 되며, 이 체를 \(GF(p)\) 또는 \(F_p\)로 표기하고, 갈로아 체(Galois field)라고 한다. 또 유한체의 위수는 반드시 소수의 거듭제곱(\(p^n\)) 형태로 표현된다.

 

• \(q\)개의 원소를 갖는 유한체 표현 : \(GF(q)\) 또는 \(F_q\) 또는 \(GF(p^n))\)
• \(GF(p^n)\) : \(q = p^n \) 개의 유한개 원소를 갖는 유한체(Galois 체)
• \(q\) : 소수의 거듭제곱 형태만 가능(\(p \ is \ prime, \ n \in \mathbb{Z}_{>0}\))
• \(GF(q)\) : 차수(order) \(q\)를 갖는 유한체

 

다항식체 : \(n\)차 다항식을 원소로 갖는 유한체 -> \(n\) 비트 워드 정보를 표현

8-bit 워드 표현을 다항식으로 

8-bit word 1 0 0 1 1 0 0 1 => \( 1x^7+0x^6+0x^5+1x^4+1x^3+0x^2+0x^1+1x^0\)

first simplification         => \( 1x^7+1x^4+1x^3+1x^0\)

second simplification    => \( x^7+x^4+x^3+1\)

 

\(GF(2^n)\) 다항식들은 다항식 집합에 차수가 \(n\)차인 다항식의 모듈러로 정의한다.

이때, 구성된 다항식들이 체를 이루기 위해서는 모듈러로 기약다항식으로 사용해야한다. 즉, 주어진 다항식의 차수보다 작은 차수들의 모든 다항식으로 나누어지지 않는(인수분해가 되지 않는) 다항식을 사용한다.

 

다항식체는 \(GF(2)\)와 \(GF(2^n)\)을 사용하여 연산.

덧셈과 뺄셈은 \(GF(2)\)에서 이루어지며 그 결과는 같은 연산이다. (XOR 연산)

 

곱셈 : 계수 곱셈은 \(GF(2)\)에서 이루어지고, 변수 곱셈은 지수법칙을 따르며 모듈러 다항식을 사용하여 모듈러 연산을 수행한다.

 

역수 구하기 : 확장 유클리드 알고리즘 사용.

 

 

정의 7. (환 \(R\) 위의 다항식)

\(R\)을 단위원 1을 가진 가환환이라 하고, \(x\)를 부정원이라 할 때, 다음과 같은 형태의 형식적인 무한합을 환 \(R\)위의 ((\x\)에 관한) 다항식이라 한다.

(부정원 : 어떤 연산을 정의할 때, 그 연산이 적용되지 않는 원소. 연산 결과로 나오지 않거나 연산 결과가 정의되지 않음.)

\( f(x) = a_0+a_1x + ... +a_nx^n... (a_i \in R) \)

단, 유한개를 제외하고는 모든 \(i\)에 대해 \(a_i = 0\) 이어야 한다.

 

다항식도 정수와 유사하게 사칙연산을 할 수 있다. 하지만 계수들이 환 또는 체에 속하는 환 위의 다항식을 이용한 사칙연산은 우리가 알고 있는 일반 다항식 사칙연산과 다르다.

ex.

\(f(x) = x^3+x^2+1,\ g(x)=x^2+x+1\) 라고 하자. 이 두 다학식을 이용한 사칙연산의 결과는 다음과 같다.

• 덧셈: \( f(x) + g(x) = x^3+2x^2+x+1 \)
• 뺄셈: \( f(x) - g(x) = x^3-x\)
• 곱셈: \(f(x) \times g(x) = x^5+2x^4+x^3+2x^2+2x+1\)
• 나눗셈: \(f(x)/g(x)\) 에서 몫은 \(x\)이고 나머지는 \(-x+1\)이다.

하지만 위 두 다항식이 \(GF(2)\) 위의 체라 가정하자.

\(GF(2)\) 의 원소는 0과 1밖에 없다. 다라서 \(GF(2)\) 에서 사칙연산의 결과는 다음과 같다.

 

• 덧셈: \(f(x)+g(x)=x^3+x\)
• 뺄셈: \(f(x)-g(x)=x^3+x\)
• 곱셈: \(f(x)+g(x)=x^5+x^3+1\)
• 나눗셈: \(f(x)/g(x)\) 에서 몫은 \(x\) 이고 나머지는 \(x+1\) 이다.

 

 

-------------------------------------------------------------------

11p/13p