[논문]프로그램 가능 최대길이 CA기반 의사난수열 생성기의 설계와 분석

최언숙; 조성진; 김한두; 강성원

doi:10.13067/jkiecs.2020.15.2.319

프로그램 가능 최대길이 CA기반 의사난수열 생성기의 설계와 분석
Design and Analysis of Pseudorandom Number Generators Based on Programmable Maximum Length CA 원문보기

한국전자통신학회 논문지 = The Journal of the Korea Institute of Electronic Communication Sciences, v.15 no.2, 2020년, pp.319 - 326

최언숙 (동명대학교 정보통신공학과) , 조성진 (부경대학교 응용수학과) , 김한두 (인제대학교 컴퓨터공학부) , 강성원 (부경대학교 응용수학과)

초록
AI-Helper

PRNG(Pseudorandom number generator)는 안전한 온라인 통신을 위한 암호화 키 생성에 있어서 필수적이다. PRNG에 의해 생성되는 비트 스트림은 대칭키 암호 시스템에서 빅 데이터를 효과적으로 암호화할 수 있도록 고속으로 생성되어야 하며 또한 여러 통계적 테스트를 통과할 수준의 랜덤성을 확보해야 한다. CA(Cellular Automata) 기반의 PRNG는 하드웨어로 구현이 용이하고, LFSR기반의 PRNG보다 렌덤성이 우수하다고 알려져 있다. 본 논문에서는 대칭키 암호시스템에서 효과적인 키 수열을 생성할 수 있는 PMLCA(Programmable Maximum Length CA)기반의 PRNG를 설계한다. 제안하는 PRNG는 비선형 제어 방식을 통해 비트 스트림을 생성한다. 먼저 주기가 긴 선형 수열을 생성하는 단일 여원벡터를 갖는 (m,n)-셀 PMLCA ℙ 기반의 PRNG를 설계하고 주기와 생성다항식을 분석한다. 또한 ℙ와 주기가 같으면서 비선형 수열을 생성하는 두 개의 여원벡터를 갖는 (m,n)-셀 PC-MLCA기반의 PRNG를 설계하고 비선형 수열이 출력되는 위치를 분석한다.

Abstract ▼ AI-Helper

PRNGs(Pseudorandom number generators) are essential for generating encryption keys for to secure online communication. A bitstream generated by the PRNG must be generated at high speed to encrypt the big data effectively in a symmetric key cryptosystem and should ensure the randomness of the level to pass through the several statistical tests. CA(Cellular Automata) based PRNGs are known to be easy to implement in hardware and to have better randomness than LFSR based PRNGs. In this paper, we design PRNGs based on PMLCA(Programable Maximum Length CA) that can generate effective key sequences in symmetric key cryptosystem. The proposed PRNGs generate bit streams through nonlinear control method. First, we design a PRNG based on an (m,n)-cell PMLCA ℙ with a single complement vector that produces linear sequences with the long period and analyze the period and the generating polynomial of ℙ. Next, we design an (m,n)-cell PC-MLCA based PRNG with two complement vectors that have the same period as ℙ and generate nonlinear sequences, and analyze the location of outputting the nonlinear sequence.

주제어

표/그림 (7)

그림 그림 1. 프로그램 가능 90/150 CA의 구조 Fig. 1 Structure of programmable 90/150 CA
표 표 1. 전이규칙 90, 105, 150, 165의 부울식 Table 1. Boolean expressions of transition rule 90, 105, 150 and 165
그림 그림 2. 단일 여원벡터를 갖는 (m, n)-셀 PMLCA기반의 PRNG의 구조 Fig. 2 Structure of PRNG based on (m, n)-cell PMLCA with a single complement vector
그림 그림 3. 두 개의 여원벡터를 갖는 (m, n)-셀 PC-MLCA기반의 PRNG의 구조 Fig. 3 Structure of PRNG based on (m, n)-cell PC-MLCA with double complement vectors
표 표 2. 단일 여원벡터를 갖는 (3,4)-셀 PMLCA의 출력 비트 스트림 Table 2. Output bit streams of (3,4)-cell PMLCA with a single complement vector
표 표 3. 두 개의 여원벡터를 갖는 (3,4)-셀 PC-MLCA의 출력 비트 스트림 Table 3. Output bit streams of (3,4)-cell PC-MLCA with double complement vectors
표 표 4. MLCA기반의 PRNG 비교 Table 4. Comparison of MLCA based PRNGs

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서는 (m,n)-셀 PMLCA기반의 PRNG와 (m,n)-셀 PC-MLCA기반의 PRNG를 제안한다. 이 PRNG는 m -셀 90/150 MLCA 와 n-셀 여원 MLCA로 구성된다.
또한 여원 최대길이 CA 기반의 PRNG가 제안되었고 여원 최대길 이에 의해 생성되는 수열에 대한 분석이 이루어졌다 [14,16]. 본 논문에서는 대칭키 암호시스템에서 효과적인 키 수열을 생성할 수 있는 프로그램 가능 MLCA 기반의 PRNG를 설계한다. 제안하는 PRNG는 비선형 적인 제어 방식을 통해 비트 스트림을 생성한다.
본 논문에서는 효과적인 암호시스템 설계에 있어 중요한 요소 중 하나인 키 수열을 효과적으로 생성할수 있는 PRNG를 설계하였다. 제안한 방법에 의하여 비선형 제어 신호에 의해 여원벡터가 제어되는 프로 그램 가능 MLCA 기반의 PRNG로 트 스트림을 생성 하였다.
정리 1은 90/150 MLCA로부터 유도된 C-MLCA의셀 중 비선형 수열인 -수열을 출력하는 셀의 위치를 구하는 방법을 소개한다.

제안 방법

Sabater 와 Cho 등은 두 개의 최대길이 CA를 이용하여 출력되는 수열을 비선형적인 방법으로 제어하여, 출력수열의 랜덤성을 높이고 주기를 확장하는 PRNG 를 설계하는 방법을 제안하였다[11-13]. 또한 여원 최대길이 CA 기반의 PRNG가 제안되었고 여원 최대길 이에 의해 생성되는 수열에 대한 분석이 이루어졌다 [14,16]. 본 논문에서는 대칭키 암호시스템에서 효과적인 키 수열을 생성할 수 있는 프로그램 가능 MLCA 기반의 PRNG를 설계한다.
본 논문에서는 두 가지 타입의 PRNG를 제안 하였는데, 먼저 주기가 긴 선형 수열을 생성하는 (m,n)-셀 PMLCA 기반의 PRNG를 설계하고 주기와 생성다항식을 분석하였다. 또한 와 주기가 같으면서 비선형 수열을 생성하는 (m,n)-셀 PC-MLCA 기반의 PRNG를 설계하고 비선형 수열을 출력하는 위치를 분석하였다. 본 논문에서 제안된 (m,n)-셀 PMLCA 기반의 PRNG와 (m,n)-셀 PC-MLCA 기반의 PRNG 는 비선형 제어 방식으로 수열을 생성함으로써 보다 랜덤성이 우수하고, 주기가 긴 비트 스트림을 생성할수 있으며 키 공간도 확장되었다.
먼저 주기가 긴 선형 수열을 생성하는 단일 여원벡터를 갖는 (m,n)-셀 PMLCA 기반의 PRNG를 설계하고 의 주기와 생성다항식을 분석한다.
제안한 방법에 의하여 비선형 제어 신호에 의해 여원벡터가 제어되는 프로 그램 가능 MLCA 기반의 PRNG로 트 스트림을 생성 하였다. 본 논문에서는 두 가지 타입의 PRNG를 제안 하였는데, 먼저 주기가 긴 선형 수열을 생성하는 (m,n)-셀 PMLCA 기반의 PRNG를 설계하고 주기와 생성다항식을 분석하였다. 또한 와 주기가 같으면서 비선형 수열을 생성하는 (m,n)-셀 PC-MLCA 기반의 PRNG를 설계하고 비선형 수열을 출력하는 위치를 분석하였다.
먼저 주기가 긴 선형 수열을 생성하는 단일 여원벡터를 갖는 (m,n)-셀 PMLCA 기반의 PRNG를 설계하고 의 주기와 생성다항식을 분석한다. 또한 ?와 주기가 같으면서 비선형 수열을 생성하는 두 개의 여원벡터를 갖는 (m,n)-셀 PC-MLCA 기반의 PRNG를 설계 하고 비선형 수열이 출력되는 위치를 분석한다.
본 논문에서는 대칭키 암호시스템에서 효과적인 키 수열을 생성할 수 있는 프로그램 가능 MLCA 기반의 PRNG를 설계한다. 제안하는 PRNG는 비선형 적인 제어 방식을 통해 비트 스트림을 생성한다. 먼저 주기가 긴 선형 수열을 생성하는 단일 여원벡터를 갖는 (m,n)-셀 PMLCA 기반의 PRNG를 설계하고 의 주기와 생성다항식을 분석한다.
본 논문에서는 효과적인 암호시스템 설계에 있어 중요한 요소 중 하나인 키 수열을 효과적으로 생성할수 있는 PRNG를 설계하였다. 제안한 방법에 의하여 비선형 제어 신호에 의해 여원벡터가 제어되는 프로 그램 가능 MLCA 기반의 PRNG로 트 스트림을 생성 하였다. 본 논문에서는 두 가지 타입의 PRNG를 제안 하였는데, 먼저 주기가 긴 선형 수열을 생성하는 (m,n)-셀 PMLCA 기반의 PRNG를 설계하고 주기와 생성다항식을 분석하였다.
출력되는 수열에 대하여 확장된 주기는 그대로 유지하며, 비선형 수열을 생성하는 PRNG를 설계하기 위하여 , 와 여원벡터 Fx, Fc 를 이용하여 (m,n) -셀 PC-MLCA기반의 PRNG를 설계한다.

성능/효과

또한 와 주기가 같으면서 비선형 수열을 생성하는 (m,n)-셀 PC-MLCA 기반의 PRNG를 설계하고 비선형 수열을 출력하는 위치를 분석하였다. 본 논문에서 제안된 (m,n)-셀 PMLCA 기반의 PRNG와 (m,n)-셀 PC-MLCA 기반의 PRNG 는 비선형 제어 방식으로 수열을 생성함으로써 보다 랜덤성이 우수하고, 주기가 긴 비트 스트림을 생성할수 있으며 키 공간도 확장되었다. 특히 PC-MLCA 기반의 PRNG는 비선형 수열을 출력함으로써 비밀키 암호 시스템에서 효과적인 키 생성기로 응용할 수 있을 것으로 사료된다.

후속연구

본 논문에서 제안된 (m,n)-셀 PMLCA 기반의 PRNG와 (m,n)-셀 PC-MLCA 기반의 PRNG 는 비선형 제어 방식으로 수열을 생성함으로써 보다 랜덤성이 우수하고, 주기가 긴 비트 스트림을 생성할수 있으며 키 공간도 확장되었다. 특히 PC-MLCA 기반의 PRNG는 비선형 수열을 출력함으로써 비밀키 암호 시스템에서 효과적인 키 생성기로 응용할 수 있을 것으로 사료된다.

질의응답

핵심어	질문	논문에서 추출한 답변
	CA란 어떤 시스템인가?	이산적 공간인 셀룰러 공간은 셀이라는 기억소자로 구성되어 있다. CA는 각 셀이 취할 수 있는 상태를 유한하게 처리하며 각 셀들의 상태가 국소적인 상호작용에 의해 동시에 업데이 트되는 시스템이다. 특히 1차원 CA는 그 물리적 배열이 매우 간단하면서도 랜덤성이 좋은 의사난수열을 효과적으로 생성할 수 있는 PRNG로 응용되었다.
	난수란 무엇인가?	난수는 키 생성, 암호화, 마스킹 프로토콜 또는 인터넷 게임과 같은 많은 암호화 응용프로그램의 기본 도구이다. 비밀키 및 공개키 알고리즘에서 키 생성을 위한 시드, 암호화 및 인증에 사용되는 세션 키, 암호로 해시 될 솔트 및 식별 프로토콜에서 사용된 문제는 모두 시스템 설계자에 의해 임의으로 가정된다.
	비트 스트림에 가장 흔하게 요구되는 특성은 무엇인가?	비트 스트림에 요구되는 특성은 매우 다양하다. 그 중에서 가장 흔하게 요구되는 특성은 랜덤성이다. 그리고 또 하나의 중요한 요구사 항은 일반적으로 하나의 랜덤 비트 스트림이 한번 사용된 후에 폐기하는 것이 아니라 정확히 동일한 랜덤 비트 스트림을 다시 발생시켜서 재사용해야 한다는 것이다.

참고문헌 (18)

A. Desai, A. Hevia, and Y. L. Yin, "A Practice-Oriented Treatment of Pseudorandom Number Generators," EUROCRYPT 2002, Amsterdam, The Netherlands, 2002, pp. 368-383.
J. Kim and J. Chon, "Decoding problem of random linear codes and its cryptographic application," J. of the Korean Institute of Communication Sciences, vol. 32, no. 6, 2015, pp. 30-38.
E. Jang, "Synchronization and Secure Communication Application of Chaos Based Malasoma System," J. of the Korea Institute of Electronic Communication Sciences, vol. 12, no. 5, 2017, pp. 747-754.

원문보기 상세보기
J. Saidov, B. Kim, J. Lee, and G. Lee, "Distributed Hardware Security System with Secure Key Update," J. of the Korea Institute of Electronic Communication Sciences, vol. 12, no. 4, 2017, pp. 671-678.

원문보기 상세보기
N. Jang, C. Kim, S. Hong, and Y. Park, "Efficient Bit-Parallel Shifted Polynomial Basis Multipliers for All Irreducible Trinomial," J. of the Korea Institute of Information Security & Cryptology, vol. 19, no. 2, 2009, pp.49-61.
S. Wolfram, "Cryptography with Cellular Automata," in Advances in Cryintology: Crypto '85 Proceedings, Lecture Notes in Computer Science vol. 218, 1986, pp. 429-432.
S. Nandi, B. Kar, and P. Chaudhuri, "Theory and Applications of Cellular Automata in Cryptography," IEEE Trans. on Computers, vol. 43, no. 12, 1994, pp. 1346-1357.
S. Das and D. Chowdhury, "On usage of cellular automata in strengthening stream ciphers," J. Discrete Mathematical Sciences and Cryptography, vol. 14, no. 4, 2011, pp. 369-390.

상세보기
U. Choi, S. Cho, J. Kim, S. Kang, H. Kim, and S. Kim, "Color image encryption based on PC-MLCA and 3-D chaotic cat map," 2019 IEEE 4th International Conference on Computer and Communication System, Singapore, Singapore, 2019, pp. 272-277.
K. Cattell and J. Muzio, "Synthesis of one-dimensional linear hybrid cellular automata," IEEE Trans. Comput-Aided Design Integrated Circuits and Systems, vol. 15, no. 3, 1996, pp. 325-335.
A. Sabater and D. Martinez, "Simple Cellular Automata-Based Linear Models for the Shrinking Generator," Proc. of IEEE Information Theory Workshop, 2003, pp. 143-146.
A. Sabater and P. Gil, "Synthesis of cryptographic interleaved sequences by means of linear cellular automata," Applied Mathematics Letters, vol. 22, 2009, pp. 1518-1524.

상세보기
S. Cho, U. Choi, H. Kim, and H. An, "Analysis of nonlinear sequences based on shrinking generator," J. of the Korea Institute of Electronic Communication Sciences, vol. 5, no. 4, 2010, pp. 412-417.
G. Y. Li, S. J. Cho, and S. T. Kim, "Complemented Maximum-Length Cellular Automata Applied on Video Encryption," J. The Institute of Internet, Broadcasting and Communication, vol. 17, no. 1, 2017, pp. 13-18.

원문보기 상세보기
U. Choi, S. Cho, H. Kim, and J. Kim, "90/150 CA corresponding to polynomial of maximum weight," J. of Cellular Automata, vol. 13, no. 4, 2018, pp. 347-358.
U. Choi and S. Cho, "Analysis of Pseudorandom Sequences Generated by Maximum Length Complemented Cellular Automata," J. of the Korean Institute of Communication Sciences, vol. 14, no. 5, 2019, pp. 1001-1008.
P. P. Chaudhuri, D. R. Chowdhury, S. Nandi, and S. Chattopadhyay, Additive Cellular Automata Theory and Applications. Los Alamitos, California: IEEE Computer Society Press, 1997.
R. Lidl and H. Niederreiter, Finite Fields. Cambridge: Cambridge University Press, 2008.

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증