카테고리 없음

GCM 운영모드 곱셈 연산

 

GCM 운영모드 표준 문서는 다음 주소에서 확인할 수 있습니다.

 

(SEED 블록암호 알고리즘에 대한 소스코드 활용 매뉴얼 pdf 파일에 gcm에 관한 내용이 있습니다.)

 

NIST 800-38d 문서의 그림이 이해하기 좋게 잘 나와 있습니다. 그림을 보면 '구조처럼 동작하고 내부적으로 inc\(_{32}\), GHASH 함수와 GCTR 함수가 필요하다' 라고 볼 수 있습니다. 

NIST 문서의 GCM AE 구조. GCM-AE(IV, P, A) = (C, T)

GHASH 함수 내부에는 곱셈 연산을 필요로 합니다. 이 곱셈은 일반 곱셈이 아닌 이진 유한체상의 곱셈입니다. GCM 운영모드의 곱셈 연산에 대해서 알아보고 확인하는 방법에 대해서 소개하겠습니다.

 

NIST 문서의 곱셈 연산을 수정하여 작성했습니다. 국내 문서와 큰 차이는 없습니다. 다만 여러 문서를 볼 경우, 기호를 헷갈리지 않게 주의하도록 합니다.

GCM 운영모드 이진 유한체 곱셈 알고리즘

이진 유한체 곱셈이지만 유한체 관한 내용 없이 shift 연산과 xor 연산으로 간단하게 동작하는 것을 확인할 수 있습니다.

여기서 한 가지 의문이 생깁니다.

 

'이 결과가 정확한 값인가?'

 

방법과 함께 결과를 확인하기 위한 방법을 알아보겠습니다.

 

다시 표현부터 정리하겠습니다. (기호는 문서 처음에 보는 것을 권장합니다.)

\(X\)를 다음과 같이 128비트로 표현할 수 있습니다.

 

$$ X = x_1x_2\ldots x_{127}. $$

다항식으로 표현하면 다음과 같습니다.

 

\begin{align} X&= a_0+a_1x + \cdots + a_{127}x^{127} \\ &= a_{127}x^{127} + \cdots + a_1x + a_0,\quad (a_i\in\{0,1\}, 1\leq i \leq 127 ).\end{align}

 

이러한 표현이 중요한 이유는 표현에 따라 구현 방법이 바뀌기 때문입니다. 예를 들어, 최상위 비트 \( a^{127}\)를 찾는다면  위의 식에서는 가장 오른쪽을, 아래 식에서는 가장 왼쪽을 확인해야 합니다.

 

국내 문서는 다음과 같이 표현되어 있습니다.

$$g(u) = u^{128} + u^7 + u^2 + u + 1.$$

 

하지만 NIST 문서와 같은 곱셈을 사용합니다. 이 표현을 주의 하면 되겠습니다.

 

곱셈에서 나오는 \( 11100001||0^{120} \)이 값은 \(1+x+x^2+x^7 \)을 의미합니다. 헥사로 0xe1 입니다.

 

알고리듬 1의 pseudo code는 다음과 같습니다.

/*
*	16 바이트 기준, check_index, XOR, rightshift1 구현 필요
*/
void GMul(unsigned char* dst, unsigned char* src1, unsigned char* src2)
{
	int iter;
	unsigned char V[16] = {0x0, };
	unsigned char Z[16] = {0x0, };

	memcpy(V, src1, 16);

	for(iter = 0; iter < 128; ++iter)
	{
		if(check_index(src2, iter))
		{
			XOR(Z, Z, V, 16);
		}	
		if((V[15] & 0x01) == 1)
		{
			rightshift1(V, V);
			V[0] ^= 0xe1;	/* R */
		}
		else
			rightshift1(V, V);
	}

	memcpy(dst, Z, 16);
	
}

이제 결과값을 확인하는 방법을 보겠습니다.

 

수학 연산을 지원하는 SageMath를 이용하겠습니다. 온라인 터미널을 제공하고 있어 설치하지 않아도 됩니다.

 

이진유한체 상의 곱셈 연산이기에 이진 유한체를 설정해 주어야 합니다.

 

예시로 \( z^{127} \)을 제곱한 값을 보도록 하겠습니다. 코드는 다음과 같습니다.

bin.<z> = GF(2)[]
poly = 1+z+z^2+z^7+z^128
S = bin.quotient(poly, 'z')

A = z^127
B = z^127

print(S(A*B))
z^127 + z^126 + z^12 + z^6 + z^5 + z^2 + z + 1 #출력 결과

16바이트를 기준으로 0x00000000000000000000000000000001을 입력합니다.

결과값으로 0xe6080000000000000000000000000003을 얻었습니다.

 

\( 1110\ 0110\ 0000\ 1000 || 0^{108} || 0011 \) 으로 표현할 수 있고 이는 sage에서 얻은 결과와 동일한 것을 확인할 수 있습니다.

 

입력값을 여러 번 다르게 입력하여 곱셈 결과가 맞는지 확인합니다. (한두 번은 우연히 맞을 수 있기에)

 

이상으로 GCM 모드의 이진유한체 곱셈 방법과 확인 과정을 알아보았습니다.

저작자표시 비영리 변경금지
샘플2