6.1. 선형복잡도(선형 점화 수열)
체 \(F_2\)에서의 무한 이진 수열 \(\{s_t\}\)가 정의 될 때,
선형점화식 \(s_{t+n} = \Sigma^{n-1}_{i = 0} {c_is_{t+i}}\) \(: ( t = 0, 1, 2, \cdots ),\) \(( c_i \in F_2 )\)을 만족 할 때,
위 \(\{s_t\}\)의 선형변환 식 \(f\)를 구하면 다음과 같습니다. ( 쉽게, \(\{s_t\}\)의 일반 해와 \(f\)의 해가 같은 변환식 \(f\) )
\(f(x) = c_0 + c_1x + c_2x^2 + \cdots\) \(+ c_{n-1}x^{n-1} + x^{n}\) 가 되고,
이 때, \(f\)를 \(\{s_t\}\) 의 “고유다항식”(Characteristic Polynomial) 또는 “특성다항식”이라고 표현하고,
위의 \(n\)을 “LFSR의 길이” 라고도 표현하며, 계수 \(c_i\) 는 \(\{0, 1\}\) 중 하나를 가지는 데
이 때, \(0\)이 아닌 \(c_i\)의 개수를 (즉, \(c_i\)가 \(1\)인 개수를 ) “탭의 수”라고 표현합니다.
\(\{s_t\}\)의 선형변환 식 \(f\)의 관계에 따라 \(\{s_{t+n}\}\)을 만족시키는 모든 무한 이진 수열 \(\{s_t\}\)의 전체 집합을
\(f(x)\)의 “해공간”(Solution Space)이라고 할 수 있고, \(f(x)\)의 해공간을 \(\Omega(f(x))\)라고 정의한다면,
\(\Omega(f(x))\) \(= \{ \{s_t\} \in F^{\infty}_2 |\) \(s_{t+n} = \Sigma^{n-1}_{i=0}c_is_{t+i},\) \(t = 0, 1, 2, \cdots \}\) 일 것입니다.
( 또한, \(\{s_t\} \in \Omega(f(x))\) 도 성립합니다. )
체 \(F_2\)위에서 \(n\)차 다항식 \(f(x) = c_0 + c_1x + c_2x^2 + \cdots\) \(+ c_{n-1}x^{n-1} + x^{n}\)가 정의 될 때,
\(A = \begin{bmatrix} 0 & 0 & \cdots & 0 & c_0 \\ 1 & 0 & \cdots & 0 & c_1 \\ 0 & 1 & \cdots & 0 & c_2 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & c_{n-1} \\ \end{bmatrix}\) 를 정의한다면,
다음 두 가지 식을 도출 해낼 수 있습니다.
1). \(\{s_t\} \in \Omega(f(x))\) <=> \(\begin{bmatrix} s_{t+1} & s_{t+2} & \cdots & s_{t+n} \end{bmatrix}\) \(= \begin{bmatrix} s_{t} & s_{t+1} & \cdots & s_{t+n-1} \end{bmatrix} A,\) \(( t = 0, 1, 2, \cdots )\)
2). \(\{s_t\} \in \Omega(f(x))\) => \(\forall i \in \mathbb{N} + {0} :\) \(\begin{bmatrix} s_{t+i} & s_{t+i+1} & \cdots & s_{t+i+n-1} \end{bmatrix}\) \(= \begin{bmatrix} s_{i} & s_{i+1} & \cdots & s_{i+n-1} \end{bmatrix} A^t,\) \(( t = 0, 1, 2, \cdots )\)
위의 두 가지 식은 해공간과 주기에 대해 사용 될 수 있습니다.
추가로 위의 정의된 \(A\)를 “동반행렬”(companion matrix)이라고 표현합니다.
만약, 주기가 \(r\)인 무한 이진 수열 \(\{s_t\}\)가 정의될 때,
주기의 정의에 따라 \(s_t\)와 \(s_t\)를 \(r\)번 평행이동(쉬프트) 한 수열은 같은 값이 될 것입니다.
( 즉, \({s_t}\) \(= \begin{bmatrix} s_{0} & s_{1} & \cdots & s_{t} \end{bmatrix}\) <=> \(\begin{bmatrix} s_{r} & s_{r+1} & \cdots & s_{t+r} \end{bmatrix}\) )
\(\{s_t\}\)를 \(d\)번 쉬프트 한 수열을 \(_d\{s_t\}\)로 정의한다면, \(_0\{s_t\} = \{s_t\}\)이고, \(_{ir + j}\{s_t\} = \{s_{t+j}\}\) \(( ( i, j ) \in \mathbb{Z}^{+} )\)일 것입니다.
위의 정의 \(_d\{s_t\}\) 를 “\(d\)만큼 평행이동 시킨 수열”( translate by \(d\) ) 라고 표현하고,
위의 \(\{s_t\}\)를 주기가 \(r\)인 “순환수열”이라고 표현합니다.
스트림 암호에서 열쇠를 생성하는 고유 다항식에 대해서 조금 더 자세히 들여다 봅시다.
먼저, 갈루아 체 \(F_{p^n}\) ( \(p\)는 임의의 소수, \(n\)은 임의의 양의 정수 ) 가 존재 할 때,
\(F_{p^n} = \{ 0 \} + <a>\) \(= \{ 0 \} + {1, a, a^2, \ldots, a^{p^n – 2}},\) \(a^{p^n – 1} = 1\) 인 원소 \(a : ( a \in F_{p^n} )\)을
\(F_{p^n}\) 의 “원시원소”(Primitive Element) 라고 표현하고,
\(F_{p^n}\) 의 최소 다항식 \(p(x) = min.poly_{F_p}(a),\) \(p(x) \in F_p[x]\)을
\(F_{p}\) 위에서의 “원시다항식”(Primitive Polynomial)이라고 표현합니다.
( \(p(x) = irr(a, F)\)로도 표현 가능하고, “기약다항식”(Irreducible Polynomial)이라고도 표현합니다. )
체 \(F_2\) 위의 \(n\)차 원시다항식 \(f(x)\)에 의해 생성되는 영이 아닌 수열 \(\{s_t\} \in \Omega(f(x))\)을
주기가 \(2^n-1\) 인 “최대 주기 수열”(Maximal Length Sequence) 또는
“\(PN\)수열”(Pseudo-Noise Sequence)이라고 표현합니다.
체 \(F_2\)위의 \(f(0) \neq 0\) 인 \(n\)차 다항식 \(f(x)\) 에 대하여 \(( x^e – 1 )\)가 \(f(x)\)로 나누어 떨어지는
\(( x^e – 1 )\)중 가장 작은 \(e\)를 \(f(x)\)의 “위수”(order)라고 하고, \(ord(f(x)) = e\) 로 정의합니다.
또한, 나누어 떨어진다면, \(f(x) | ( x^e – 1 )\)로도 표현 가능 할 것입니다.
\(ord( f(x) )\)는 다음 세 가지 식을 반드시 만족합니다.
1). \(f(x)\)의 근을 \(a\)라 정의 할 때, \(ord( f(x) )\)는 곱셈군 \(F_2^n\)에서의 \(a\)의 위수와 같습니다.
2). \(ord( f(x) ) | (2^n – 1)\)입니다.
3). 영이 아닌 수열 \(\{s_t\} \in \Omega(f(x))\)는 주기가 모두 \(ord(f(x))\)인 순환 이진 수열입니다.
최소다항식과 선형복잡도를 설명하기 위해서 먼저 다항식 \(m(x)\)에 대해 선 정의 할 필요가 있습니다.
체 \(F_2\) 위에서의 이진 수열 \(\{s_t\}\)가 존재 할 때, \(m(x)\)는 \(m(x) \in F_2[x]\)이고,
다음 세 가지 조건을 만족하는 유일한 다항식이라 정의합니다. 세 가지 조건은 다음과 같습니다.
1). \(m(x)\) 의 최고차항의 계수는 \(1\)이고, \(deg(m(x)) \leq 1\)입니다.
2). \(m(x)\)는 \(\{s_t\}\)의 고유다항식 입니다. (즉, \(\{s_t\} \in \Omega( m(x) )\) )
3). 임의의 최고차항 계수가 \(1\)인 다항식 \(f(x) \in F_2[x]\) 에 대하여 \(\{s_i\} \in \Omega(f(x))\) <=> \(m(x) | f(x)\)입니다.
이 때의 \(m(x)\) 을 \(\{s_t\}\)의 “최소다항식”( Minimal Polynomial )이라 정의하고,
다항식 \(m(x)\)의 차수를 \(\{s_t\}\)의 “선형복잡도”( Linear Complexity ) 표현합니다.
6.2. 선형복잡도(비선형 점화 수열)
위의 체\(F_2\)에서의 \(n\)차 다항식 \(f(x) = c_0 + c_1x + c_2x^2 + \cdots + c_{n-1}x^{n-1} + x^{n}\) 에서
가능한 \(f(x)\)의 경우의 수로는 \(2^{n}\) 이고, \(c_0\)를 \(1\)로 하는 \((1, c_1, c_2, \ldots, c_{n-1})\)인 경우의 수가 \(2^{n}-1\)인데,
이를 원시다항식이라 표현 했었고, \(\lambda(n) = \frac{\phi(2^n – 1)}{n}\)으로 표현합니다.
그렇다면, 스트림암호의 열쇠 경우의 수는 원시다항식 \(\times\) 초기 상태 벡터 이고,
초기 상태 벡터는 역시 \(2^{n}-1\) 개의 벡터 \((s_0, s_1, s_2, \cdots, s_{n-1})\) 을 사용하기 때문에,
열쇠의 경우의 수 = \((2^{n}-1) \times \lambda(n)\) \(= \frac{(2^n – 1)\phi(2^n – 1)}{n}\) 가 됩니다.
또한, \(n\)차 원시다항식을 \(n\)단계 LFSR로 이진수열을 생성하는 경우, 선형복잡도는 \(n\)이 되므로,
어떠한 순서를 가지든 해당 이진수열의 확장 버전, \(2n\)개 항들의 값을 찾아내면,
\(c_i\)와 수열 \(\{s_t\}\)를 모두 알아 낼 수 있게 됩니다.
이런 LFSR의 취약점을 보완하기 위해서 이전에 언급한 골룸의 공리에서
열쇠이진수열은 “비선형”(Nonlinear)이어야 한다는 조건이 추가되어야 합니다.
( 비선형이어야 주기가 유효하게 길어지고, 예측이 더욱 더 힘들어지기 때문입니다. )
비선형함수에 의해 생성되는 이진수열 중에 대표적으로 “벤트”(Bent)함수의 수열과 “카사미”(Kasami)수열 등이 있고,
상당히 좋은 성능을 내는 수열들이라 알려져 있습니다.
그렇다면, 비선형 이진 수열을 생성하는 방법은 어떻게 될까요?
1). 비선형 결합생성기 : LFSR을 병렬로 두고 어떤 함수 \(f\)를 이용하여 비선형 이진 수열을 만드는 방법입니다.
이 때, \(f\)를 “비선형 결합생성기”(Nonlinear Combination Generator)
또는 “결합함수”(Combine Function)라고 표현합니다.
결합 함수 중에서 “게페 생성기”(Geffe Generator)는 LFSR을 세 개\((L_1, L_2, L_3)\)를 사용하여, 결합하는 함수입니다.
게페 생성기 \(f\) 는 \(f(L_1, L_2, L_3)\) \(= L_1L_2 + (1 + L_2)L_3\)로 정의되고, 주기는 \((2^{L_1}-1)\)\((2^{L_2}-1)\)\((2^{L_3}-1)\)가 됩니다.
2). 비선형 여과생성기 : LFSR의 또 다른 출력수열을 생성하는 함수 \(f\)를 사용하는 방법입니다.
이 때, \(f\)는 LFSR의 여과장치를 추가하여 또 다른 출력수열을 생성하는 함수이고,
이를 “비선형 여과생성기”(Nonlinear Filter Generator)라고 표현합니다.
선형 여과생성기와의 차이점은 선형은 LFSR들이 단순 덧셈식으로 결합이 되어있는 반면에,
비선형은 곱셈식과 덧셈식을 섞어 각 LFSR에 독립적인 새로운 형태의 수열을 만들어냅니다.
이 때 비선형 여과함수에 의해 출력 되는 열쇠 이진 수열을 “Groth수열”이라고 표현합니다.
이 Groth수열 역시 비선형 답게 주기가 곱의 형태를 가져 상당히 긴 주기를 가질 수 있게 됩니다.
3). 시간제어 생성기 : 시간신호를 사용하여 수열을 혼합시켜, 비선형성을 만드는 방법입니다.
이를, “시간제어 생성기”(Clock-Controlled Generator, CCG)라고 표현합니다.
이 시간제어 생성기는 다음 두 가지로 분류 할 수 있습니다.
i). “선택단계 생성기”(Alternating Step Generator, ASG) : 3개의 LFSR이 정의 될 때,
하나의 LFSR이 다른 두 개의 LFSR을 제어하면서 비선형성을 만드는 방법입니다.
ii). “축약단계 생성기”(Shrinking Step Generator, SSG) : 두 개의 LFSR이 정의 될 때,
어떤 “계기”(Clock)에 의해 둘 중 하나의 값을 만들면서, 하나를 \(x_i\), 하나를 \(y_i\)이라 할 때,
\(y_i\)를 열쇠 수열로 사용하는데 사용여부는 \(x_i\)이 결정하는 방식을 사용합니다.
\(x_i\)가 1이면 \(y_i\)를 사용하고 \(x_i\)가 0이면 \(y_i\)를 버려서, 원래 \(y\)의 축약형을 사용하는 방법입니다.
( 즉, 이 방식이 안전하려면 두 LFSR이 많은 주기를 가져야 하고, 빠른 연산이 가능해서 실제로 쓰이는 방법입니다. )
이 외에도 비선형 이진수열을 생성하는 대표적인 수열이 “다중”(multiplexed)수열과 “BRM”수열 등이 존재합니다.
6.3. 스트림암호 분석
스트림암호의 비도를 높이기 위해, 주기를 길게 만들 수 있는 비선형 함수와 LFSR의 조합으로 열쇠를 만들어
스트림암호를 사용했었습니다. 바로 이 성질이 열쇠를 찾는 약점이 될 수도 있습니다.
이런 공격방법을 “상관공격”(Correlation Attack)이라고 표현합니다.
만약, 결합 함수 f를 이미 알고있다고 가정한다면, \(\Pi_{k = 1}^{m}(2^{r_k} – 1)\lambda(r_k)\)개의 경우가 존재하게 됩니다.
이 때, LFSR값이 생각보다 작으면,
어떤 LFSR_i의 출력 이진 수열이 열쇠수열과 상관관계가 있는 LFSR_i를 찾아낼 수 도 있을 것입니다.
이 때의 경우의 수는 \(\Sigma_{k = 1}^{m}(2^{r_k} – 1)\lambda(r_k)\)로 획기적으로 줄일 수 있습니다.
물론, f와 LFSR_i를 특정해야 하는 까다로운 조건이 걸리지만,
실제로 LFSR이 50자 이하라면, 해당공격이 유효하다고 평가 됩니다.
게페생성기의 상관공격법에 대해 자세하게 알아봅시다.
게페생성기 함수 f는 f(L_1, L_2, L_3) = L_1L_2 + L_2L_3 + L_3 이고,
이진 진리표를 생성하여 조건부 확률을 계산해본다면, 열쇠수열이 L_1, L_3과 상관관계가 있고,
L_2는 독립적임을 알 수 있습니다.
실제로 L_1과 L_3를 알아낸다면, 열쇠를 75%까지 추정할 수 있음을 알아 내었습니다.
이런 구조적 한계를 LFSR에서 원인을 찾았고, 이 LFSR을 아무리 늘리거나 줄여도,
늘릴경우에는 종속비율이 높아서 상관공격 확률이 높아지고, 줄일경우 전사공격 확률이 높아지기 때문에,
LFSR에 의해 출력되는 값의 상관관계를 최대한 줄이기 위해 비선형 결합함수를 신경써서 고안해야 합니다.
이러한 비선형 결합함수를 “상관 면역 함수”(Correlation Immune Function)이라고 표현하고,
상관 면역 함수의 면역 정도를 “상관 면역도”(Correlation Immune Order)라고 표현합니다.
입력 역시 LFSR에서 0과 1의 확률이 같은 “BSS”(Binary-Symmetric Source)를 사용하여 값을 구합니다.
비선형 함수 f의 출력 수열이 m( 1 \leq m < n )개 이하의 임의의 입력 수열 성분들과 독립일 때,
f는 “위수 m의 상관면역” 또는 “상관면역도 m”을 가진다고 표현합니다.
즉, P( z = 1 | x_{i_1} = a_1, x_{i_2} = a_2, \ldots, x_{i_m} = a_m ) = P( z = 1 ) : ( 1 \leq i_1 \leq i_2 \leq \cdots \leq i_m \leq n , a_i \in F_2 ) 이면,
f는 상관면역도 m을 가진다고 표현합니다.
추가로 출력수열 z = f(x_1, x_2, \ldots, x_n) 이 존재하고, f의 비선형위수가 k, 상관면역도를 m이라 정의한다면,
1). k + m \leq n 가 성립합니다.
2). P( z = 0 ) = P( z = 1 ) = \frac{1}{2} => k + m \leq n – 1 가 성립합니다.
따라서 비선형위수 k, 상관면역도 m, 둘 다 적절하게 높은 값을 유지해야 좋은 암호로 평가됩니다.