스트림암호에서 원시다항식에 대한 고찰

국문 초록 (Abstract)

스트림 암호는 1회용 패드(one time pad)형 암호 알고리즘으로 랜덤한 비트(또는 문자)들의 열을 열쇠로 사용하여 평문과 XOR과 같은 간단한 연산을 통해 암호화하므로 알고리즘의 안전성은 사용되는 열쇠의 난수성에 의존한다. 그러므로 사용되는 열쇠에 대해 주기, 선형복잡도, 비선형도, 상관면역도 등의 수학적 분석을 통해 보다 안전한 암호시스템을 설계할 수 있는 장 점이 있다. 스트림 암호에서의 암호화 열쇠는 고유다항식을 가지고 LFSR(linear feedback shift register)에서 열쇠이진 수열을 생성하여 사용한다. 이 고유다항식 중 비도가 가장 우수한 다항식이 바로 원시다항식이다. 원시다항식은 스트림 암호뿐만 아 니라 8차 원시 다항식을 사용한 블록암호인 SEED암호, 그리고 24차 원시 다항식을 사용하여 설계한 공개열쇠암호인 CR(Chor-Rivest) 암호 등에서도 널리 이용되고 있다. 본 논문의 주요내용은 이러한 암호알고리즘을 연구하는데 사용되는 갈 루아(Galois)체에서의 원시다항식에 대한 개념과 다양한 성질들을 고찰해 보고 소수 p의 값이 2이상인 경우 Fp에서의 기약 다항식과 원시다항식의 개수를 구하는 정리를 증명해 보았다. 이러한 연구는 보다 비도가 높은 원시다항식을 찾아 새로운 암 호알고리즘을 개발하는 기반 연구가 될 수 있다.

다국어 초록 (Multilingual Abstract)

Stream cipher is an one-time-pad type encryption algorithm that encrypt plaintext using simple operation such as XOR with random stream of bits (or characters) as symmetric key and its security depends on the randomness of used stream. Therefore we can design more secure stream cipher algorithm by using mathematical analysis of the stream such as period, linear complexity, non-linearity, correlation-immunity, etc. The key stream in stream cipher is generated in linear feedback shift register(LFSR) having characteristic polynomial. The primitive polynomial is the characteristic polynomial which has the best security property. It is used widely not only in stream cipher but also in SEED, a block cipher using 8-degree primitive polynomial, and in Chor-Rivest(CR) cipher, a public-key cryptosystem using 24-degree primitive polynomial. In this paper we present the concept and various properties of primitive polynomials in Galois field and prove the theorem finding the number of irreducible polynomials and primitive polynomials over Fp when p is larger than 2. This kind of research can be the foundation of finding primitive polynomials of higher security and developing new cipher algorithms using them.

목차 (Table of Contents)

• 요약
• ABSTRACT
• 1. 서론
• 1-1 다항식
• 1-2 예제
• 2. 원시다항식과 그 성질
• 2-1. f(x) 의 분해 체와 원시다항식
• 2-2. 예제
• 3. 주요 정리 및 예제
• 3-1. 주요 정리
• 3-2. 주요 예제
• 참고문헌

참고문헌 (Reference)

1 김응태, "현대 암호학" 경문사 475-483, 2003

2 이민섭, "현대 암호학" 경문사 168-258, 2007

3 이민섭, "이진수열의 비선형성과 Correlation Attack에 관한 연구" 한국전자통신연구소 1992

4 양정모, "스트림 암호에서 높은 비선형도의 상관면역함수의 설계와 그의 안전성 분석" 한국정보보호학회 17 (17): 89-96, 2007

5 R.J. Anderson, "Solving a class of stream ciphers" 14 (14): 1990

6 양정모, "SEED암호에서 S-함수에 대한 고찰" 한국정보보호학회 27 (27): 1295-1305, 2017