chapter 4 대칭 키 암호 수학: 대수 구조 - 2절 GF(p^n) 체

1. GF(p^n) 체의 중요성

 컴퓨터는 양의 정수를 n-비트 워드로 저장한다. 따라서 컴퓨터가 저장하는 모든 수는 모듈로 2^n이다. 컴퓨터에서는 원소의 개수가  2^n인 GF(2^n) 체를 사용해야 한다.  하지만 n-비트 워드들에는 일반적인 네 개의 연산들을 적용할 수 없기 때문에 새로운 두 개의 연산을 정의할 필요가 있다.

 

2. 다항식

  n-비트 워드들을 차수 n - 1의 다항식(polymomial) 형태로 생각하면 다루기 편리하다. x의 지수승이 n-비트 워드에서 비트들의 위치를 정의한다. 가장 오른쪽에 있는 비트를 x^0, 가장 왼쪽에 있는 비트를 x^(n-1)위치에 놓는다. 항의 계수는 비트값을 나타낸다. 0 또는 1의 값을 갖는다.

 

1. 연산
 다항식에 관한 연산은 계수에 관한 연산과 두 개의 다항식에 관한 연산으로 나눠볼 수 있다. 따라서 두 개의 체를 정의해야 한다. 계수에 대한 연산으로는 GF(2) 체를 사용하고 다항식에 대한 연산에서는 GF(2^n) 체를 사용한다.

2. 모듈로
 GF(2^n)의 다항식의 집합에 대해서 차수 n의 군은 모듈로로 정의된다. 이 모듈로는 어떤 다항식으로도 나눌 수 없는 소수 다항식(prime polynomial)으로 동작한다. 따라서 우리는 GF(2^n)를 정의할 때 모듈로로 사용할 소수 다항식을 반드시 정해야 한다.

3. 덧셈
 GF(2)에서 계수를 갖는 다항식의 덧셈은 XOR연산이다. 덧셈에 대한 항등식은 0의 다항식이며 덧셈에 대한 역원은 자기 자신이다. 즉, 뺄셈은 덧셈과 같다.
 
4. 곱셈
 다항식의 곱셈은 첫 번째 다항식의 각 항과 두 번쨰 다항식의 각 항의 곱셈의 합이다. 곱셈을 하면 차수가 늘어날 수 있으므로 곱셈을 한 뒤에는 모듈로 연산을 해야 한다. 곱셈에 대한 항등원은 항상 1이며 곱셈에 대한 역원은 확장 유클리드 알고리즘을 통해 구할 수 있다.

5. 컴퓨터를 이용하는 곱셈
 n-비트 워드를 한 비트 이동함으로써 x에 의한 곱셈을 할 수 있다. 만약 이전 결과의 최상위 비트가 0이면 이전 결과를 왼쪽으로 이동하면 되고, 이전 결과의 최상위 비트가 1이면 왼쪽으로 한 비트 이동한 뒤 최상위 비트를 제외하고 모듈로 다항식과 XOR 연산을 하면 된다.

 

3. 생성원의 사용

 GF(2^n) 체의 원소를 생성원 g을 통해 정의하면 다루기 편리하다. 기약 다항식 f(x)가 정의된 체에서 체의 원소 a는 반드시 f(a) = 0을 만족해야 한다는 점을 이용한다.

 

1. 덧셈에 대한 역원
 각 원소의 덧셈에 대한 역원은 바로 그 원소 자신이다. 따라서 -g = g이다.

2. 곱셈에 대한 역원
 멱승은 모듈로 2^n - 1로 계산되는데, 이를 활용하여 모듈로 연산을 통해 역원을 계산한다. 가령 GF(2^4)일 때, (g^3)^(-1) = g^(-3) = g^12이다.

4. 덧셈과 뺼셈
 덧셈과 뺄셈은 같은 연산이다.

5. 곱셈과 나눗셈
 곱셈은 모듈로 2^n - 1의 멱승의 덧셈이다. 나눈셈은 곱셈의 역원을 사용한 곱셈이다.