5.1. 갈루아 체에서 수열
체 중에서 “갈루아 체”(Galois Field)는 임의의 소수 \(p\)와 양의 정수 \(n\)에 대하여 \(p^n\)개의 원소를 가진 유한 체를
“위수 \(p^n\)인 갈루아 체”라고 정의하고, \(F_{p^n}\) 또는 \(GF(p^n)\)으로 표현합니다.
길루아 체에 대해서는 엄밀하게 따지면 현대 대수학의 상당한 내용과 함께 엮이게 되므로
이번 장에서는 갈루아 체를 공부하기 보다 갈루아 체에서의 수열들 특히,
\(GF(2)\)에 해당하는 체에서의 수열에 대해서만 다룰 예정입니다. ( \(F_2 = GF( 2 ) = { 0, 1 }\) 인 체 )
\(GF(2^n)\) 위의 다항식들을 하나로 표현한다면 다음과 같을 것입니다.
\(GF(2^n)[ x ] \)\(= \{ a_0 + a_1x + \ldots + a_nx^n | a_i \in GF(2) , 0 \le i \le n \}\) 이고,
각 차항을 독립으로 \(GF(2)\)의 \(n + 1\) 차원 부분공간이라고 볼 수 있으며,
\(GF(2^n)[ x ]\)의 기저는 \(\{1, x, \ldots, x^n \}\) 가 될 것 입니다. ( \(|GF(2^n)[ x ]| = n + 1\) )
그래서 각 기저의 원소 \(( x_0, \ldots, x_n )\) 들을 “\(n\) 차원 이진 벡터”로 표현 하기도 합니다.
체 \(GF(2)\) 에서 어떤 수열 \(\{ x_i \}\) 에 대해서 \(\exists r \in N : ( x_{n + r} = x_n )\) 이 성립한다면,
이 때의 수열 \(\{ x_i \}\)를 “순환 이진 수열”(periodic binary sequence)라고 정의하고, \(\overline{ x_0x_1 \cdots x_{r-1} }\) 로 표현합니다.
또한 위의 식이 성립하는 \(r\)중 최소 값을 순환 이진 수열의 “주기”(period)라고 정의하고,
\(x_0, x_1, \ldots, x_{r-1}\) 들을 수열 \(\{x_n\}\) 의 “생성 순환 마디”라고 정의합니다.
쉽게 비트를 시프트 연산을 했을 때, 자신과 같아지는 비트열을 순환 이진 수열 이라고 하고,
그때의 시프트연산 최소 횟수를 주기라고 하는 것과 같을 것입니다.
체 \(F\)위의 벡터공간 \(V\)의 부분집합 \(B = {x_i | i \in I}\) 가 \(V\)의 “기저”(basis)일 조건은 다음과 같습니다.
1). \(\forall v \in V\) \(: (\) \(v\)가 \(B\)의 유한개의 원소의 일차 결합으로 표현됨 \()\)
2). 집합 \(B\) \(:=\) 일차 독립, \(| B | = n\) 이면,
\(V\)를 \(n\)차원 벡터 공간 이라고 표현하고, \(dim_FV = n\) 으로도 표현 가능합니다.
5.2. 선형 점화 수열
갈루아 체 \(GF(2)\)에서 무한 수열 \(\{s_t\}\)를 생성해 내는 \(n\)단계 축차생성기(n-stage shift register)를 정의하면
다음과 같습니다.
\(f : GF(2)^n\) -> \(GF(2) ,\) \(y = f\)\((x_0, x_1, \cdots, x_{n-1})\) 이고, 각 단계 \(S_i\)의 값은 단위 시각 \(t\)에 따라 \(s_i(t)\)로,
\(s_i(t)\)는 다음 두 가지 조건을 만족합니다.
1). \(s_i(t+1) \)\(= s_{i+1}(t) ,\) \((0 \le i \le n – 2)\)
2). \(s_{t + n} \)\(= s_0(t + n) \)\(= \cdots \)\(= s_{n-1}(t + 1) \)\(= f( s_t, s_{t+1}, \cdots, s_{t+n-1} )\)
위의 두 조건은 시각 \(t\)에 대해 \(s_0(t), s_1(t), \ldots, s_{n-1}(t)\)이면,
시각 \(t+1\)에 대해 \(s_0(t+1), s_1(t+1), \ldots, s_{n-1}(t+1)\)인데,
이는 \(s_1(t), s_2(t), \ldots, s_n(t)\)과 같아지게 되고, 시각이 바뀔 때 마다 우측 시프트를 한 것과 비슷하여
\(s_0, s_1, s_2, \ldots\)으로 부터 ( 순환하는 )무한이진 수열\(\{s_t\}\)를 얻을 수 있습니다.
이 때, 함수 \(f\)를 “귀환 함수”(Feedback Function)라고 표현하고,
수열 \(\{s_t\}\)의 초기 값 수열을 “초기 상태 벡터”(Initial State Vector)라고 표현합니다.
( 즉, 축차생성기에 의해 생성되는 무한이진 수열\(\{s_t\}\)는 초기 상태 벡터가 주어지고,
귀환 함수 \(f\)를 적용한 결과라고 볼 수 있습니다. )
함수 \(f : F^n_2\) -> \(F_2\) 에서 \(y = f( x_0, x_1, \cdots, x_{n-1} )\) \(= c + c_0x_0 + c_1x_1 + \cdots + c_{n-1}x_{n-1}\) \(( c, c_0, c_1, \ldots, c_{n-1} \in F_2 )\)
함수 \(f\)를 “선형 함수”(Linear Function)라고 정의하고,
특히, \(c = 0\) 일때는 “동차 선형 함수”(Homogeneous Linear Function)라고 표현합니다.
선형 함수를 귀환 함수로 가지는 축차생성기를
“선형 귀환 축차생성기”(Linear Feedback Shift Register) 줄여서 “LFSR”이라고 표현하고,
비선형 함수를 귀환 함수로 가지는 축차생성기를
“비선형 귀환 축차생성기”(Nonliear Feedback Shift Register)라고 표현합니다.
\(F_2\) 위에서 무한이진 수열 \(\{s_t\}\)가 LFSR에 의해 생성된 수열이면,
\(s_{t+n} = f( s_t, s_{t+1}, \cdots, s_{t+n-1} )\) \(= c + c_0s_t + c_1s_{t+1} + \cdots + c_{n-1}s_{t+n-1}\) \(( t = 0, 1, \ldots )\)
이 때, 이 수열 \({s_t}\)을 \(F_2\)에서의 “선형 점화 수열”(Linear Recurring Sequence)이라고 표현하고,
식 \(s_{t+n}\)을 \(F_2\)에서의 “선형점화식”(Linear Recurring Relation) 또는
“차분방정식”(difference Equation)이라고 표현합니다.
특히, \(c = 0\)일 때 \(\{s_t\}\)를 “동차 선형 점화 수열” 이라고 표현하고,
\(c \neq 0\)일 때, \(\{s_t\}\)를 “비동차 선형 점화 수열” 이라고 표현합니다.
5.3. 스트림암호
암호 시스템은 평문을 암호화하는 크기나 단위에 따라 블록암호와 스트림암호로 분류됩니다.
블록암호는 암호알고리즘을 공개하고 특정 함수나 열쇠를 어떻게 설계하는지에 따라
암호의 비도를 유지하는 방식을 사용하지만,
스트림암호는 암호열쇠 생성 알고리즘을 공개하지 않고 한 번 사용된 알고리즘을 재사용 불가능하게 하여
임의 선택된 비트열을 열쇠로 사용하는 방식입니다. ( “1회용 패드”(One Time Pad) 암호로도 불립니다. )
블록암호 대비 스트림암호가 가지는 장점으로는 다음과 같습니다.
1). 암호화 복호화 속도가 빠릅니다.
블록암호와 달리, 암호화 및 복호화를 비트 XOR연산 단 한 번으로도
이론적으로 해독불가능 하게 할 수 있기 때문입니다.
2). 전송손실 및 변조공격에 타격이 적습니다.
블록암호는 단위가 블록단위이므로 한 비트를 변경해도 블록단위가 사용 불가능 한 분해능을 가지지만,
스트림암호는 바뀐 한 비트나 몇 비트 정도의 분해능을 가지므로 변조류의 상황에 상대적으로 타격이 적습니다.
블록암호 대비 스트림암호가 가지는 단점으로는 열쇠비트가 상당히 길다는 것 입니다.
열쇠는 짧을수록 보관, 전송 편의성이 있지만, 스트림암호는 평문과 열쇠가 거의 1 : 1 비율의 길이를 가지므로
실제 사용환경에서는 잘 사용되지 않는 암호입니다.
스트림 암호에서 열쇠 비트열을 생성하는 함수 \(f\)가 존재할 때, \(f\)는 “부울함수”(boole function)라고 표현하고,
\(f : F^n_2\) -> \(F_2\)로 정의 할 수 있으며, \(F^n_2 = \{(x_1, x_2, \ldots, x_n) | x_i \in F_2 , 1 \le i \le n\}\) 일 때,
\(f(x_1, x_2, \ldots, x_n)\) \(= c_0 \oplus \Sigma_{i=1}^{n} c_ix_i\) \(\oplus \Sigma_{i=1}^{n – 1} \Sigma_{j=i+1}^{n} c_{(i, j)}x_i \wedge x_j\) \(\oplus \cdots\) \(\oplus c_{(1, 2, \ldots, n)} x_1 \wedge x_2 \wedge \cdots \wedge x_n\)가 됩니다.
( \(c_{(1, 2, \ldots, n)} x_1 \wedge x_2 \wedge \cdots \wedge x_n\) 은 \(\Sigma_{i_1=1}^{1} \Sigma_{i_2=i_1+1}^{2} \cdots \Sigma_{i_n = i_{n-1}+1}^{n} c_{(i_1, i_2, \ldots, i_n)}x_{i_1} \wedge x_{i_2} \wedge \cdots \wedge x_{i_n}\) 을 줄여서 표현했습니다. )
위의 대수적 정규형에서 \(2\)차 이상의 \(c\)가 모두 \(0\)인 즉, 일차와 \(c_0\)만 정의 된 \(f\) 함수가
\(f(x_1, x_2, \ldots, x_n) = c_0\) \(\oplus c_1x_1\) \(\oplus c_2x_2\) \(\oplus \cdots\) \(\oplus c_nx_n\) 일 때,
\(f\)를 “아핀함수”(affine function)라고 정의하고, 추가로 \(c_0 = 0\)인 아핀함수 \(f\)를 “선형 함수”라고 정의합니다.
부울함수는 추가적으로 “열쇠 수열 생성자”(Key Sequence Generator , KSG) 또는 “수열생성자” 라고도
표현합니다.
부울함수의 핵심은 “임의성”에 있는데 쉽게, 어떤 비트 수열의 값을 알고있어도 다음 비트 수열이 알고있는 수열과
아무런 관계가 없도록 하는 함수를 만들어야 하는 것 입니다.
해당 함수를 만드는 데 중요한 개념인 “골룸의 공리”(Galomb)는 세 가지 공리를 제공하는데,
이 세 가지가 임의적인 수열, “의사난수열”(Pseudorandom Sequence)을 만족하는 조건이 됩니다.
다음은 골룸의 공리를 바탕으로 LFSR을 사용하여 의사난수열을 생성하는 조건 세 가지를 나열한 것 입니다.
1). 열쇠의 경우의 수가 계산상 불가능 한 정도까지 증가시켜 주어야 합니다.
2). 생성되는 무한 이진 수열의 주기를 파악할 수 있어야 합니다.
3). 수열은 임의적 이어야 합니다. ( 모두 서로 독립적이고 생성 근거가 없어야 합니다. )
스트림암호는 열쇠 비트 수열을 생성하는 방식에 따라 크게 두 가지로 구별됩니다.
1). 동기식(Synchronous) 스트림암호 :
주어진 초기상태 벡터로 LFSR에 의해 생성된 비트 수열이 다시 재 반영되어
다음 비트를 생성하는 방식의 열쇠 비트 수열로 주어진 평문을 암호화 합니다.
( 즉, LFSR의 결과값(현재 수열)을 다음 수열의 원인으로 사용하는 방식입니다. )
특징으로는 열쇠 비트 수열이 평문과 암호문간의 종속성 없이 독립적으로 생성되므로
수신자와 송신자간에는 미리 약속된 비밀열쇠와 초기상태벡터를 공유하고
암호화 또는 복호화하는 방식을 사용합니다.
이는 문제점으로 변조등의 상황에 대해 에러 감지 또는 제대로 된 복호화를 진행 할 수 없어
수시로 상태벡터를 검증하는 과정을 넣어서 이를 해결하고 있습니다.
2). 자기동기식(Self-Synchronous) 스트림암호 :
주어진 초기상태 벡터로 LFSR에 의해 생성된 비트 수열이 다시 재 반영되는 점은 유사하지만,
해당 비트 수열로 만들어진 암호문을 재 반영하여 다음 비트를 생성하는 방식을 사용합니다.
( 즉, LFSR의 결과값(현재 수열)을 사용한 암호문을 다음 수열의 원인으로 사용하는 방식입니다. )
특징으로는 열쇠 비트 수열이 암호문에 종속되어 생성되기 때문에 암호문을 이용한 해독이 가능할 수 있지만
비밀열쇠 개념이 필요없고, 변조등의 상황에 대해 현재 수열에 한해서 오류가 전파되고
다음 수열부터는 다시 정상적인 복호화가 이루어지게 됩니다. ( 오류전파 차단 )