과포화(Overdefined) 연립방정식을 이용한 LILI-128 스트림 암호에 대한 분석

Vol. 13, No. 1, pp. 139-146, 2월. 2003
10.13089/JKIISC.2003.13.1.139, Full Text:
Keywords: Stream Cipher LILI_128, 0verdefined System of Multivariate Equations, XL-Algorithm
Abstract

본 논문은 과포화 다변수 방정식을 이용하여 LILI-128 스트림 암호를 분석한다. LILI-128 암호$^{[8]}$ 는 128비트 키를 가진 선형귀환 쉬프트 레지스터 기반의 스트림 암호로 구조를 살펴보면 크게 “CLOCK CONTROL” 부분과 “DATA GENERATION” 부분으로 나뉘어진다. 분석 방법은 “DATA CENERATION” 부분에 사용되는 함수 \ulcorne $r^{d}$ 의 대수적 차수가 높지 못하다는 성질을 이용한다. 간략히 설명하면 차수(K)가 6차인 다변수 방정식을 많이 얻을 수 있고, 이를 7차 (D)의 다변수 방정식으로 확장하여 주어진 변수보다 많은 연립방정식을 얻어 그 해를 구하는 XL 알고리즘을 통해 전수조사보다 빠르게 키정보를 찾을 수 있다. 결과 중 가장 좋은 것은 출력 키수열 2$^{26.3}$비트를 가지고 2$^{110.7}$ CPU 시간을 통해 128비트 키정보를 얻는 것이다.다.

Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from December 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
문덕재, 홍석희, 이상진, 임종인 and 은희천, "Cryptanalysis of LILI-128 with Overdefined Systems of Equations," Journal of The Korea Institute of Information Security and Cryptology, vol. 13, no. 1, pp. 139-146, 2003. DOI: 10.13089/JKIISC.2003.13.1.139.

[ACM Style]
문덕재, 홍석희, 이상진, 임종인, and 은희천. 2003. Cryptanalysis of LILI-128 with Overdefined Systems of Equations. Journal of The Korea Institute of Information Security and Cryptology, 13, 1, (2003), 139-146. DOI: 10.13089/JKIISC.2003.13.1.139.