Chapter 4 암호 수학 제 2부 대수구조 Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.

Chapter 4 Objectives □ 대수적 구조의 개념 □ 군(group)의 정의와 예제 □ 환(ring)의 정의와 예제 □ 체(field)의 정의와 예제 □ 현대 블록암호에서 n-비트 워드에 대한 덧셈, 뺄셈, 곱셈, 나눗셈과 같은 연산을 수행 가능하게 하는 GF(2n)형식의 유한체(finite field)

4-1 ALGEBRAIC STRUCTURES 2장에서 와 같은 어떤 숫자들의 집합을 살펴보았다. 암호(cryptography)는 정수들의 집합과 이들 집합에 정의된 특정한 연산들을 필요로 한다. 그 집합과 그 집합에 포함된 원소들에 적용되는 연산을 통틀어 대수적 구조(algebraic structure)라 한다. 이 장에서는 일반적인 3 개의 대수적 구조인 군(group), 환(ring), 체(field)에 대해서 정의한다 (그림 4.1 참조).

Topics discussed in this section: 4-1 ALGEBRAIC STRUCTURES Topics discussed in this section: 4.1.1 군(Groups) 4.1.2 환(Rings) 4.1.3 체(Fields)

4.1 Continued Figure 4.1 일반적인 대수적 구조

4.1.1 군(Groups) 군(G)은 네 개의 성질(혹은 공리)을 만족하는 이항 연산 “•”이 정의된 원소들의 집합이다. 가환군(Commutative group) 혹은 아벨군(Abelian group)은 군에 대한 네 개의 성질에 교환법칙을 추가로 만족하는 집합이다. 군에 대한 네 개의 성질과 교환 법칙은 다음과 같이 정의된다.

4.1.1 군(Groups) ❏ 닫힘(Closure) ❏ 결합법칙(Associativity:) ❏ 교환법칙(Commutativity:) ❏ 항등원의 존재(Existence of identity:) ❏ 역원의 존재(Existence of inverse:)

4.1.1 Continued Figure 4.2 군

4.1.1 Continued 응용(Application) 하나의 군에는 한 개의 연산만이 정의되지만, 그 연산에 대한 성질들은 그 연산과 역함수 관계에 있는 연산의 사용을 허용한다. 예를 들어, 정의된 연산이 덧셈이라면 뺄셈은 덧셈의 역함수 관계를 가지기 때문에 군은 덧셈과 뺄셈 모두를 사용한다. 이것은 또한 곱셈과 나눗셈에 대해서도 적용된다.

4.1.1 Continued Example 4.1 덧셈 연산이 정의된 잉여류(residue integers)의 집합 G = < Zn , +>, 는 가환군이다. 이 군은 새로운 원소를 추가하지 않고 덧셈과 뺄셈 모두 사용할 수 있다. 이 군이 위에서 언급한 다섯 가지 성질을 만족하는지 살펴보자.

4.1.1 Continued Example 4.1 의 결과 1. 집합은 연산에 대하여 닫혀있다. 왜냐하면 Zn의 두 원소에 대한 합은 Zn에 있는 다른 원소이기 때문이다. 2. 결합 법칙을 만족한다. 예를 들어, 4+(3+2)의 결과는 (4+3)+2와 같다. 3. 교환 법칙을 만족한다. 예를 들어, 3+5=5+3임을 쉽게 알 수 있다. 4. 항등원은 0이다. G의 원소 3에 대하여, 3+0=0+3=3 이다. 5. 모든 원소는 덧셈에 대한 역원을 갖는다. 어떤 원소에 대한 역원은 그 원소의 보수(complement)이다. 예를 들어, 3의 역원은 -3이다(Zn의 n-3) . 그리고 -3의 역원은 3이다. 덧셈에 대한 역원은 집합에서 뺄셈을 사용할 수 있게 해준다.

4.1.1 Continued Example 4.2 곱셈 연산이 정의된 집합 Zn*(G = <Zn*, ×>)는 가환군이다. 이 군은 새로운 원소를 추가하지 않고 곱셈과 나눗셈 모두 사용할 수 있다. 이 군이 처음 세 가지 성질을 만족하는 것을 쉽게 보일 수 있다. 이 집합에 대한 항등원은 이다. Example 4.3 G = < {a, b, c, d}, •> 와 아래 표 4.1과 같이 정의된 연산을 생각해보자.

4.1.1 Continued Example 4.3의 결과 이 집합은 가환군이다. 그리고 위에 언급된 다섯 가지 성질을 모두 만족한다. 1. 집합은 연산에 대하여 닫혀있다. 임의의 두 원소들에 대한 연산 결과값은 집합 내의 다른 원소이다. 2. 결합 법칙 또한 성립한다. 이를 증명하기 위해, 세 원소의 임의의 조합에 대하여 확인할 필요가 있다. 예를 들어, (a+b)+c=a+(b+c)임을 쉽게 알 수 있다. 3. 정의된 연산은 교환 법칙을 만족한다. 예를 들어, a+b=b+a이다. 4. 항등원은 0이다. 5. 각 원소는 역원을 갖는다. 역원 쌍은 각 행에서 항등원을 찾음으로서(음영 부분) 얻을 수 있다. 그 역원 쌍들은 (a,a), (b,d), (c,c) 이다.

4.1.1 Continued Example 4.4 군에서, 집합의 원소들이 숫자나 어떤 물체일 필요는 없다. 그것은 규칙이나 사상(mapping), 함수(function)가 될 수도 있고 혹은 어떤 작용(action)도 될 수도 있다. 매우 흥미로운 군 중의 하나는 치환군(permutation group)이다. 이 집합은 모든 치환을 모아놓은 집합이며 이 집합에 정의된 연산은 두 치환에 대한 합성이다.

4.1.1 Continued Example 4.4 Figure 4.3 치환의 합성(예 4.4)

4.1.1 Continued Example 4.4 Continued Table 4.2 치환 군의 연산

4.1.1 Continued Example 4.5 앞의 예제에서 합성 연산이 정의된 치환들의 집합은 군임을 보였다. 이는 하나의 치환을 수행한 후에 다른 치환을 수행하는 방법은 암호의 안전성을 강화시키지 못하는 것을 의미한다. 왜냐하면 군의 닫혀 있는 성질을 이용해서 항상 같은 결과값을 출력하는 다른 치환을 찾아낼 수 있기 때문이다.

4.1.1 Continued 유한군(Finite Group) 군의 위수(Order of a Group) 부분군(Subgroups)

4.1.1 Continued Example 4.6 군 H = <Z10, +> 는 군 G = <Z12, +>의 부분군인가? Solution 아니다. 비록 H 는 G의 부분집합이지만, 두 군들에 대해 정의된 연산은 다르다. H의 연산은 모듈러 10에서의 덧셈이고 G의 연산은 모듈러 12에서의 덧셈이다.

4.1.1 Continued 순환 부분군(Cyclic Subgroups) 만약 군의 부분군이 어떤 원소의 멱승(power)을 사용하여 생성된다면 부분군을 순환 부분군(Cyclic Subgroup)이라고 한다. 여기서 멱승은 원소에 군의 연산을 반복적으로 적용한 것을 의미한다.

4.1.1 Continued Example 4.7 군 G = <Z6, +> 로부터 네 개의 순환 부분군 H1 = <{0}, +>, H2 = <{0, 2, 4}, +>, H3 = <{0, 3}, +>, 와 H4 = G. 들이 생성될 수 있다.

4.1.1 Continued Example 4.8 군 G = <Z10∗, ×>로부터 세 개의 순환 부분군 H1 = <{1}, ×>, H2 = <{1, 9}, ×>, 와 H3 = G들이 생성될 수 있다. G 는 오직 4 개의 원소: 1, 3, 7, 9를 갖는다.

4.1.1 Continued 순환군(Cyclic Groups) 순환군은 그 자신이 하나의 순환 부분군인 군이다.

4.1.1 Continued Example 4.9 군 G = <Z10∗, ×>로부터 3 개의 순환 부분군이 생성된다. G 는 오직 4 개의 원소: 1, 3, 7, 9를 갖는다. 이 3 개의 순환부분군은 H1 = <{1}, ×>, H2 = <{1, 9}, ×>, 와 H3 = G 이다. a. 군 G = <Z6, +> 는 두 개의 생성원 g = 1 과 g = 5를 갖는 순환부분군이다. b. 군 G = <Z10∗, ×> 는 두 개의 생성원 g = 3 과 g = 7을 갖는 순환부분군이다..

4.1.1 Continued 라그랑지 정리(Lagrange’s Theorem) 라그랑지 정리(Lagrange's Theorem)는 군의 위수와 부분군의 위수와 관련이 있다. G가 군이고 H가 G의 부분군일 때, G와 H 의 위수를 각각 |G|, |H| 라고 하면, 이 정리에 의해 |H| 는 |G|를 나눈다. 원소의 위수(Order of an Element) 원소의 위수는 “그 원소가 생성하는 순환군의 위수”로 정의할 수도 있다. 원소 a의 위수는 ord(a)로 표시한다.

4.1.1 Continued Example 4.10 군 G = <Z6, +>에서, 각 원소들의 위수를 계산해보면 다음과 같다. ord(0) = 1, ord(1) = 6, ord(2) = 3, ord(3) = 2, ord(4) = 3, ord(5) = 6. b. 군G = <Z10*, ×>에서, 각 원소들의 위수를 계산해보면 다음과 같다. ord(1) = 1, ord(3) = 4, ord(7) = 4, ord(9) = 2.

4.1.2 환(Ring) 환 R = <{…}, •,
>, 은 두 개의 연산을 가지는 대수적 구조이다. Figure 4.4 환

4.1.2 Continued Example 4.11 덧셈과 곱셈의 두 연산이 정의된 집합 Z 는 가환환이다. 이 예에서는 이 집합을 R = <Z, +, ×> 로 나타낸다. 덧셈은 다섯 개의 모든 성질을 만족한다. 곱셈은 단지 세 개의 성질을 만족한다. 곱셈은 또한 덧셈 위에서 분배 법칙을 만족한다.

4.1.3 체(Field) 로 F = <{…}, •, > 표기되는 체(Field)는 특정한 성질을 만족하는 두 개의 연산이 정의된 가환환이다. 일반적인 가환환과 마찬가지로 첫 번째 연산은 아벨군에 대해 요구되는 다섯 가지 성질을 모두 만족한다. 두 번째 연산은 첫 번째 연산의 항등원(때때로 원소라고 불린다)이 역원을 갖지 않는다는 것을 제외하고 군의 모든 다섯 가지 성질을 만족한다. 그림 4.5는 체를 보여준다.

4.1.3 체(Field) Figure 4.5 체

갈로아 체, GF(pn), 는 pn 개의 원소를 갖는 유한체이다. 4.1.3 Continued 유한체(Finite Fields ) 유한체(Finite Field)는 유한개의 원소를 갖고 있는 체이다. 유한체는 암호에서 매우 중요한 구조이다. 갈로아는 원소들의 개수가 pn인 유한개의 원소를 갖는 체가 존재함을 보였다. p는 소수이고, n 은 양정수이다. Note 갈로아 체, GF(pn), 는 pn 개의 원소를 갖는 유한체이다.

4.1.3 Continued 체 GF(p) n = 1 일 때, GF(p) 는 체이다. 이 체는 두 개의 산술 연산(덧셈과 곱셈)을 갖고 있는 집합 Zp, {0, 1, …, p − 1}, 가 될 수 있다.

4.1.2 Continued Example 4.12 암호 분야에서 가장 널리 쓰이는 체는 그림 4.6의 집합 {0, 1}과 두 개의 연산, 덧셈과 곱셈을 갖고 있는 GF(2)이다.  Figure 4.6 체 GF(2)

4.1.2 Continued Example 4.13 집합 Z5 위에 그림 4.7에 보인 것처럼 합과 곱 연산이 정의되는 체 GF(5) 를 정의 할 수 있다. 여기서 5는 소수임에 주의 하라. Figure 4.7 체 GF(5)

4.1.3 Continued 요약(Summary) 세 가지 대수적 구조의 연구는 덧셈/뺄셈과 곱셈/나눗셈과 같은 비슷한 연산이 정의된 집합들을 사용할 수 있도록 해준다. 세 구조들 사이를 구별할 필요가 있다. 군은 하나의 연관된 연산들의 쌍을 지원한다. 환은 하나의 연관된 연산들의 쌍과 하나의 독립적인 연산을 지원한다. 체는 연산들의 두 쌍을 지원한다. 표 4.3은 세 구조들의 차이점을 나타낸다.

4.1.3 Continued 요약(Summary) Table 4.3 요약

4-2 GF(2n) FIELDS 암호에서는 자주 네 개의 연산(덧셈, 뺄셈, 곱셈, 나눗셈)을 필요로 한다. 다시 말해서, 암호에서는 체가 필요하다. 그러나 컴퓨터에서 체에 정의된 연산을 수행할 때, 양의 정수들은 컴퓨터에 n-비트 워드들로 저장된다. n은 보통 8, 16, 32, 64 등의 배수형태를 취한다. 이것은 정수들의 범위가 0에서 2n-1까지인 것을 의미한다. 즉, 모듈러는 2n이다. 따라서 체를 사용할 때는 두 가지 방법이 있다.

Topics discussed in this section: 4-2 GF(2n) FIELDS Topics discussed in this section: 4.2.1 다항식(Polynomials) 4.2.2 생성원 사용하기(Using A Generator) 4.2.3 요약(Summary)

4.2 Continued Example 4.14 네 개의 2-비트들로 구성된 집합 {00, 01, 10, 11}인 체 GF(22)를 정의 할 수 있다. 이 체에 대한 덧셈과 곱셈을 그림 4.8에 보인 것처럼 새롭게 정의할 수 있다. 이 연산들은 위에서 언급한 모든 성질들을 만족한다. Figure 4.8 체GF(22) 의 예

4.2.1 Polynomials 차수가 n − 1 인 다항식은 다음과 같이 표현된다. 여기서 xi 는 i번째 항(term)이라고 하고, ai 는 i번째 항(term)의 계수라고 부른다.

4.2.1 Continued Example 4.15 그림 4.9는 다항식을 사용해서 8-bit 워드 (10011001) 를 어떻게 표현할 수 있는지 보여준다. Figure 4.9 다항식을 이용한 8-비트 워드 표현

4.2.1 Continued Example 4.16 8-bit word related 다항식 x5 + x2 + x 와 연관된 8-비트 워드를 만들기 위해, 우선 생략된 항들을 채워넣는다. n = 8이기 때문에, 이 다항식은 차수가 7이다. 확장된 다항식은 이것이 바로 8-bit word 00100110에 대응되는 다항식이다.

n-bit 워드들을 표현하는 다항식들은 두 개의 체 GF(2) 와 GF(2n)를 사용한다. 4.2.1 Continued 체 GF(2n) Note n-bit 워드들을 표현하는 다항식들은 두 개의 체 GF(2) 와 GF(2n)를 사용한다.

4.2.1 Continued Modulus GF(2n)의 다항식들의 집합들에 대해서, 차수 n의 다항식의 어떤 집합은 군은 모듈러로서 정의된다. 이 경우에 모듈러는 소수 다항식(prime polynomial)으로서 행동하는데 다항식은 집합에서 이 다항식을 나누는 다항식이 없는 다항식을 의미한다. 소수 다항식은 보다 작은 차수들의 다항식으로 분해될 수 없다. 이런 다항식을 기약 다항식(irreducible polynomial)이라 한다.

4.2.1 Continued Modulus Table 4.9 기약다항식

4.2.1 Continued Addition Note 다항식의 덧셈과 뺄셈 연산은 같은 연산이다.

4.2.1 Continued Example 4.17 GF(28)에서 (x5 + x2 + x) Å (x3 + x2 + 1) 를 계산해보자. 여기서 사용한 연산 기호 Å 는 다항식의 덧셈을 의미한다. 그 절차를 아래에 나타내었다.

4.2.1 Continued Example 4.18 더 간단한 다른 방법이 있다. GF(2)에서의 덧셈은 exclusive-or (XOR)연산을 의미한다. 그래서 두 워드의 비트별 배타적 합을 계산하여 결과를 얻을 수 있다. 앞의 예에서 x5 + x2 + x 는 00100110 이고 x3 + x2 + 1 는 00001101이다. 그 결과는 00101011 이고 이것은 바로 다항식으로 표현하면 x5 + x3 + x + 1이 된다.

4.2.1 Continued 1. 계수 곱셈은 GF(2)에서 이루어진다. 곱셈(Multliplication) 1. 계수 곱셈은 GF(2)에서 이루어진다. 2. xi 에 xj 를 곱하면 결과로 xi+j을 얻는다. 3. 곱셈은 n − 1보다 큰 차수를 가지는 항을 생성할 수도 있다. 따라서 모듈러 다항식을 사용하여 곱셈한 결과를 줄일 필요가 있다.

4.2.1 Continued Example 4.19 기약다항식 (x8 + x4 + x3 + x + 1)을 갖는 GF(28) 에서 (x5 + x2 + x) ⊗ (x7 + x4 + x3 + x2 + x) 를 계산하라. 여기서 사용한 연산기호 ⊗은 두 다항식의 곱셈을 의미한다. Solution 최종 결과를 계산하기 위해서 12차수 의 다항식을 8차수 의 다항식으로 나누고(modulus) 나머지만을 취한다. 이 과정은 대수학에서의 나눗셈과 같다. 하지만 여기서 뺄셈은 덧셈과 같다. 그림 4.10은 나눗셈의 전체 과정을 보여준다.

4.2.1 Continued Figure 4.10 GF(2)의 계수들을 갖는 다항식 나눗셈

4.2.1 Continued Example 4.20 GF (24)에서, 모듈로 (x4 + x + 1) 에 대한 (x2 + 1)의 역원을 구하라. Solution 답은 아래의 표 4.5에 나타내었듯이 (x3 + x + 1) 이다. Table 4.5 연습문제 4.20 에 대한 유클리드 알고리즘

4.2.1 Continued Example 4.21 GF(28)에서, 모듈로 (x8 + x4 + x3 + x + 1)에 대한 (x5)의 역원을 구하라 Solution 답은 아래의 표 4.6에 나타내었듯이 (x5 + x4 + x3 + x) 이다. Table 4.6 연습문제 4.21 에 대한 유클리드 알고리즘

4.2.1 Continued 컴퓨터를 사용한 곱셈(Multliplication Using Computer) 나눗셈 연산 때문에 두 다항식을 곱하기 위한 프로그램을 개발하는데 포함되는 효율적인 알고리즘이 존재한다. 컴퓨터의 구현에서는 x에 의해 줄여진 다항식을 반복적으로 곱하는 더 좋은 알고리즘을 사용한다.

4.2.1 Continued Example 4.22 위에서 언급된 방법을 사용하여 기약 다항식 (x8 + x4 + x3 + x + 1)을 갖는 GF(28) 에서의 P1 = (x5 + x2 + x) 과 P2 = (x7 + x4 + x3 + x2 + x) 의 곱셈에 대한 결과를 찾아라. Solution 이 과정은 표 4.7에 나타나 있다. 우선 P2 에 x0, x1, x2, x3, x4, x5 를 곱한 부분 결과를 찾는다. 각 계산은 이전 결과에 의존하기 때문에 0에서 5까지의 x2 ⊗ P2 의 곱셈은 쉽게 계산된다. 비록 3 개의 항만이 필요하지만 m 이 0 부터 5까지에 대해서 곱셈 xm ⊗ P2 를 계산 해야 한다. 왜냐하면 이 계산값들이 이전에 계산 한 값들에 종속되기 때문이다.

4.2.1 Continued Continued Example 4.22 Table 4.7 다항식을 사용한 곱셈에 대해 효율적인 알고리즘(예제 4.22)

4.2.1 Continued Example 4.23 크기 의 비트 형식을 이용하여 예제 4.22를 반복해라. Solution P1 = 000100110 이고 P2 = 10011110 이다. 모듈로 = 100011010(9- 비트). 연산 Å은 배타적 합을 의미한다. Table 4.8 n-비트 워드들을 사용한 곱셈에 대한 효율적인 알고리즘

4.2.1 Continued Example 4.24 GF(23) 체는 개의 원소들을 갖고 있다. 기약 다항식(x3 + x2 + 1) 을 사용하여 이 체에 대한 덧셈과 곱셈표를 구할 수 있다. 또한 - 비트 워드와 다항식을 구할 수 있다. 차수 인 두 개의 기약 다항식이 존재한다. 다른 하나는 (x3 + x + 1)이고 이 다항식은 곱셈에 대해 전혀 다른 곱셈표를 생성한다. 표 4.9는 덧셈을 보여주고 있다.

4.2.1 Continued Example 4.24 Continued Table 4.9 GF(23)에 대한 덧셈 표

4.2.1 Continued Example 4.24 Continued Table 4.10 GF(23)에 대한 곱셈표

4.2.2 Using a Generator 때로는 GF(2n) 의 원소를 정의할 때 생성원을 이용하는 것이 더 편리할 때가 있다.

4.2.1 Continued Example 4.25 기약다항식 ƒ(x) = x4 + x + 1 를 이용해서 GF(24)의 원소를 생성하라. Solution 군의 원소 0, g0, g1, g2, 와 g3 를 쉽게 생성할 수 있다. 왜냐하면 이 원소들은 0, 1, x2, 과 x3 의 4-비트 표현이기 때문이다. x4 부터 x14 까지 나타내는 원소 g4 부터 g14 는 기약다항식으로 나누어질 필요가 있다. 그렇지만 ƒ(g) = g4 + g + 1 = 0 의 관계식을 사용하여 다항식의 나눗셈을 피할 수 있다.

4.2.1 Continued Example 4.25 Continued

4.2.1 Continued Example 4.26 덧셈과 뺄셈 연산의 결과는 다음과 같다.

4.2.1 Continued Example 4.27 다음은 곱셈과 나눗셈 연산의 결과들을 보여준다.

4.2.3 Summary 유한체 GF(2n)은 n-비트워드들에 대한 덧셈, 뺄셈, 곱셈, 나눗셈의 네 개의 연산들을 정의하기위해 사용될 수 있다. 유한체에서는 0에 의한 나눗셈을 제외한 모든 연산을 사용할 수 있다.