최근 통신망의 급격한 발전과 더불어 디지털 콘텐츠 데이터가 고화질/고용량의 멀티미디어 자료 형태로 변모해가고 있으며, 이에 따라 암호 알고리즘도 고비도, 고속화 및 고신뢰도 설계가 요구된다.

선형 귀환 이동 레지스터(Linear Feedback Shift Registers:LFSR)는 하드웨어와 소프트웨어에 적합하며 빠른 암호율과 복호율이 허용되어 일반적으로 스트림 암호에 사용된다. 또한, LFSR에 의해 주 귀환 다항식은 큰 주기 및 우수한 통계적 특성을 가지며 연속적으로 생성된다[1].

일반적으로 선형성은 취약점 회피와 LFSR에 계산된 수열 특성을 이용하기 위해 수열 발생기의 구성 요소로 LFSR을 사용하고, 비선형성은 조합함수, 필터링 함수로 비선형 부울 함수를 사용하여 양쪽 모두 불규칙한 주기 LFSRs를 사용한다[2,3]. 또한 클럭 조절형을 사용하여 비선형성을 높일 수 있다[4,5].

자체 수축형(Self_Decimation) LM-128[6]은 LFSR에 자기 클럭 조절형 구조(Self_Decimated clock control Structure)가 추가 되었으며, 2개의 비트 메모리를 가지고 있는 합산 수열 발생기[7]를 기초로 한 발생기이다.

본 논문에서 제안된 임계 클럭 조절형(Threshold clock-controlled) LM-128은 클럭 조절형 알고리즘인 자체 수축형 LM-128에서 클럭의 최대 주기를 최소화시켜 키의 발생 속도를 향상 시켰으며 출력되는 키 수열에 비선형성을 증가시켜 상관 공격[8] 등의 암호 해독을 어렵게 하였으며, 소프트웨어적으로 키 수열의 생성시간을 단축시키는데 목적이 있다.

일반적으로 지칭하는 합산 수열 발생기(r=2)는 그림 1과 같이 2개의 LFSR과 1개 비트의 메모리에 기초를 두는 합산 수열 발생기이다. 그림 2의 LM 합산 수열 발생기[9]는 2개의 비트 메모리를 가지고 있으며 여기서 두 개의 LFSR을 L_a와 L_b로 표시하고 각각의 메모리 비트는 C, D로 시간을 j라 할 때 A_j와 B_j는 각각 L_a와 L_b의 출력이며 캐리(carry) C_j는 f_c에 의해 결정되고, D_j는 f_d에 의해 결정 된다. 출력 함수 f_z는 키 수열 비트와 z_j로 나타내어지며 출력 함수를 f_c, f_d, f_z로 정의하면 다음과 같다.

자체 수축형 LM-128 합산 수열 발생기는 자기 클럭조절 구조가 추가된 합산 수열 발생기 계열이며, 그림 3과 같다. 그림에서 키 수열 발생기는 두 개의 LFSR로 구성되며, 다음 메모리 상태와 키 수열 비트를 생성하기 LFSR의 출력 비트는 결합 함수 f_z, 캐리 함수 f_c 및 메모리 함수 f_d에 각각 입력된다. LFSR 에는 불규칙한 클럭이 공급되며, 하나의 LFSR에 공급되는 불규칙한 클럭수는 자신의 LFSR에서 생성된 비선형 필터함수(f_a 또는 f_b)로부터 얻어진다.

캐리 상태 C_j는 f_c에 의해, 메모리 상태 D_j는 f_d에 의해 정의된다. 클럭 조절 함수 f_a와 f_b는 두 LFSR의 현 상태에 의해 얻어지며, LFSR은 랜덤하게 클럭 조절된 후 캐리, 메모리 및 키 수열 출력을 생성한다. 자체 수축형 LM-128은 처음 초기화 과정에서 키(k)와 초기값(iv)로 부터 내부 상태가 채워지며, 내부 상태 길이가 키 길이보다 더 길기 때문에 내부 상태를 채우기 위한 키 확장과정이 요구된다.

2.2.1. 키 수열 발생

자체 수축형 LM-128 합산 수열 발생기는 두개의 클럭 조절형 LFSR과 캐리 및 메모리 비트를 가지며, LFSR의 길이는 각각 127비트와 129비트 이다. 모든 메모리 비트들은 자체 수축형 LM-128에게 256비트의 내부 상태 비트를 제공하며, 128비트 키와 128비트 초기화 벡터에 의하여 내부 상태가 채워진다.

자체 수축형 LM-128 합산 수열 발생기의 출력 키 수열은 LFSR 수열과 캐리 및 메모리 수열이 합쳐져서 생성된다. 자체 수축형 LM-128의 LFSR은 모든 비트가 “0”인 상태로 초기화되는 것을 허용하지 않는다.

출력 키 수열 비트 Z_j, 캐리비트 C_j, 메모리 비트 D_j는 구조상 LM 합산 수열 발생기와 동일한 형태(식 (1)∼(3))를 취하지만, 출력 수열의 비도 수준이 크게 개선된다.

2.2.2. 클럭제어

자체 수축형 LM-128은 자신의 LFSR의 주기를 제어하여 각각의 레지스터에 불규칙한 주기 LFSR을 발생하는데 두 단의 범위{1...4}값을 계산하기 위하여 L_a로부터 두 단의 값을 받아서 f_a의 계산에 의해 La의 주기[1-4]를 선택하는 값을 가지게 된다. 유사하게 L_b의 두 단 값을 받아서 L_b의 주기를 준다. 주기는 제어함수 f_a와 f_b에 의해 얻는다.

이 설계는 클럭 조절형 LM 계열에 적용되며, 키 수열 발생기는 일반형에서 LFSR의 개수 n=2를 선택하여 LFSR에 L_i의 주기는 L_i+1 또는 L₁부터 L_n까지의 주기가 사용된다.

임계 클럭 조절형 LM-128 발생기는 클럭 조절 구조가 추가된 합산 수열 발생기 계열이며, 최대 클럭 주기를 최소화 시킨 합산 수열 발생기이며 그림 4와 같다.

그림에서 키 수열 발생기는 두 개의 LFSR로 구성되며, 다음 메모리 상태와 키 비트 수열을 생성하기 LFSR의 출력 비트는 결합 함수 f_z, 캐리 함수 f_c 및 메모리 함수 f_d에 각각 입력된다. LFSR에는 불규칙한 클럭이 공급되며, 하나의 LFSR에 공급되는 불규칙한 클럭수는 두개의 LFSR에서 생성된 비선형 필터함수(g)로부터 얻어진다. 이 때 클럭 조절의 방법은 g=(f_a+f_b)mod4로 발생된 클럭 수만큼 홀수(odd)일 때는 위쪽 L_a 레지스터를 작동하고, 짝수(even)일 때는 아래쪽 L_b 레지스터를 작동하게 된다.

캐리 상태 C_j는 f_c에 의해, 메모리 상태 D_j는 f_d에 의해 정의된다. 클럭 조절 함수 g는 두 LFSR의 현 상태에 의해 얻어지며, LFSR은 랜덤하게 클럭 조절된 후 캐리, 메모리 및 키 수열 출력을 생성한다. 임계 클럭 조절형 LM-128은 처음 초기화 과정에서 키(k)와 초기값(iv)로 부터 내부 상태가 채워지며, 내부 상태 길이가 키 길이보다 더 길기 때문에 내부 상태를 채우기 위한 키 확장 과정이 요구된다.

2.3.1. 키 수열 발생

임계 클럭 조절형 LM-128 합산 수열 발생기는 두 개의 클럭 조절형 LFSR과 캐리 및 메모리 비트를 가지며, LFSR의 길이는 각각 127비트와 129비트 이다. 모든 메모리 비트들은 임계 클럭 조절형 LM-128에게 256비트의 내부 상태 비트를 제공하며, 128비트 키와 128비트 초기화 벡터에 의하여 내부 상태가 채워진다. 임계 클럭 조절형 LM-128 합산 수열 발생기의 출력 키 수열은 LFSR 수열과 캐리 및 메모리 수열이 합쳐져서 생성된다. 임계 클럭 조절형 LM-128의 LFSR은 모든 비트가 “0”인 상태(all zero state)로 초기화되는 것을 허용하지 않는다. 출력 키 수열 비트 Z_j, 캐리비트 C_j, 메모리 비트 D_j는 구조상 LM 합산 수열 발생기와 동일한 형태(식 (1)∼(3))를 취하지만, 출력 수열의 비도 수준이 크게 개선된다.

2.3.2. 클럭 제어

임계 클럭 조절형 LM-128은 각 탭 L_a와 L_b의 값으로 부터 g값을 구한 후 g값이 5이상이면 g값에서 4만큼의 수를 차감한 값의 수만큼 LFSR A의 클럭을 1∼4회 귀환이동하고, 4미만이면 g값만큼 LFSR B를 1∼4의 클럭 수만큼 귀환 이동하며, 나머지 선택에서 제외된 LFSR은 1회 클럭 이동하게 된다. 주기는 제어함수 f_a, f_b, g 그리고 g_a 및 g_b를 다음 수식과 같이 얻는다. f_a 와 f_b는 수식(4)~(5)와 같은 함수를 사용한다.

이 설계는 클럭 조절형 LM 계열에 적용되며, 키 수열 발생기는 일반형에서 LFSR의 개수 n=2를 선택하여 LFSR에 L_i의 주기는 L_i+1 또는 L₁부터 L_n까지의 주기가 사용된다.

임계 클럭 조절형 LM-128 키 수열 발생기를 이용하여 연속되는 출력 데이터 16만 비트씩 샘플 값을 출력한 후 빈도 검증(Frequency test), 계열 검증(Serial test), 일반화 계열검증(Generalized serial test), 포커 검증 (Poker test) 및 자기상관성 검증(Autocorrelation test) [10]등의 랜덤 검증 및 선형 복잡도(Linear Complexity: LC), 주기 (Period: P) 등의 시험검증을 실시하였다.

각각의 선택된 검증 항목을 시험하여 모든 항목 검증 결과가 기준 이내에서 표 1 및 표2와 같이 양호한 출력을 얻을 수 있음을 확인하였다. (표에서 시험 결과 값은 판정치의 범위 이내에 포함되면 각 항목별 랜덤성이 양호함)

정리 1. 선형 복잡도 LC와 주기 P는 아래와 같다.

보조정리 1. 자체 수축형 LM-128과 임계 클럭 조절형 LM-128의 선형 복잡도 LC 및 주기 P는 다음과 같다.

자체 수축형 LM-128과 임계 클럭 조절형 LM-128 알고리즘에 대해 5회씩 156,000개의 키수열을 생성시켰으며, 각각의 시간에 대해 평균값을 표 3과 같이 생성됨을 알 수 있었다.

자체 수축형 LM-128과 임계 클럭 조절형 LM-128 알고리즘은 랜덤성이 양호할 뿐만 아니라 주기, 선형복잡도 등 암호 안정성이 좋다는 것을 확인 할 수 있었다. 임계 클럭 조절형 LM-128의 경우에는 클럭주기의 향상으로 인해 자체 수축형 LM-128 보다 소프트웨어적으로 30%가량 생성시간이 향상되었음을 확인할 수 있었다.

본 논문에서는 LM-128 발생기를 개선하여 콘텐츠 보호에 적합한 구조로 기존의 클럭 조절 구조의 효율성을 높이는 임계 클럭 조절형 LM-128을 제시하였고, 기존의 자체 수축형 LM-128과 비교하기 위하여 랜덤성 시험, 주기 및 LC와 같은 비도(안전성) 요소에 대한 안전성 검증을 실시하였다. 검증 결과 임계 클럭 조절형 LM-128은 랜덤성이 양호 할뿐 아니라 암호 안정성 요소인 주기와 LC 값이 2¹²⁸(현재 수준의 최소 기준인 2⁸⁰을 크게 초과)으로 크게 개선된 알고리즘이며, 고화질/고용량의 콘텐츠 보호에 많은 응용이 예상될 수 있다.