90 / 150 Uniform CA의 합성 및 특성다항식 계산
최언숙
*
․조성진**․임지미***Synthesis of 90/150 Uniform CA and Computation of Characteristic Polynomial corresponding to uniform CA
Un-Sook Choi
*ㆍ Sung-Jin Cho
**ㆍJi-Mi Yim
***요 약
전이 규칙 90과 150만을 사용하는 90/150 CA는 최소다항식과 특성다항식이 같은 CA로 랜덤성이 우수하여 LFSR의 대안으로 사용되어왔다. 90 Uniform CA와 150 uniform CA는 모든 셀에 동일한 전이규칙이 적용되 는 CA로 기밀성과 인증을 제공하는 Sarkar의 암호기법에 사용되었다. 본 논문에서는 전이규칙이 90 또는 150 인 uniform CA에 대하여 분석하고 특별한 전이규칙을 갖는 -셀 90/150 CA를 이용하여 -셀 uniform CA와 -셀 uniform CA를 합성하고 대응하는 특성다항식을 계산하는 효율적 방법을 제안한다.
ABSTRACT
90/150 CA is a CA completely specified by using rule 90 and rule 150. Since 90/150 CA whose minimal and characteristic polynomials are identical has outstanding randomness, this CA is more attractive than LFSR. Sarkar proposed a scheme based on the 90 uniform CA and the 150 uniform CA. That scheme provided authentication by digital signature and other basic security requirements like confidentiality. In this paper we analyze 90 or 150 uniform CA and give a synthesis method of
-cell uniform CA and
-cell uniform CA using a special
-cell 90/150 CA. And we propose an effective method of computation of characteristic polynomial corresponding to uniform CA.키워드
uniform CA, 합성, 90/150 CA, 특성다항식, 전이규칙, 상태전이행렬
* 동명대학교 미디어공학과([email protected]) ** 교신저자, 부경대학교 응용수학과([email protected])
*** 부경대학교 응용수학과([email protected])
접수일자 : 2009. 12. 5 심사완료일자 : 2010. 1. 10
Ⅰ. 서 론
셀룰라 오토마타(Cellular Automata 이하 CA)는 von Neumann에 의해서 생물학적으로 자체 재생산에 대한 모델로 처음 소개되었다[1]. Wolfram는 스스로 조직화하는 시스템에 대한 수학적 모델들로써 CA의 연구를 개척하였고, 간단한 두 상태 0, 1과 1-차원에 서 셀들이 선형으로 배열된 3-이웃 CA를 이용하여 제한하였다. 이러한 CA는 LFSR(linear feedback shift register)과 달리 간단하고 규칙적이고 국소적이며 작
은 단위로 확장연결이 가능한 구조적인 장점을 가지 고 있어 하드웨어로 구현하는 것이 용이하다. 또한 단 위 시간에 모든 셀의 값이 동시에 변화되는 특성을 가지고 있으므로 한 비트씩 셀의 값을 이동시키는 LFSR보다 랜덤성이 뛰어나 LFSR의 대안으로 제안 되었으며 매우 폭넓게 응용되고 있다[2-8].
이러한 CA를 효과적으로 사용하기 위하여 많은 연
구자들이 CA의 특성을 분석하고 또한 LFSR에 대응
하는 CA의 합성방법에 대하여 연구하였다. Das 등은
행렬을 이용하여 선형 CA와 여원 CA를 특성화 하였
다[2-3]. Cattell 등에 의하여 LFSR에 대응하는 CA에 대한 연구가 이뤄졌으며, 최대 길이를 갖는 CA를 찾 는 연구가 수행되었다[9-10]. 이후 Cho 등은 CA 다 항식에 대한 90/150 선형 hybrid 그룹 CA의 합성에 대한 효과적인 방법을 제안하였다[11]. 비그룹 CA에 대한 합성방법은 Chattopadhyay[12]가 해쉬함수에 응 용에 효과적인 MACA(multiple-attractor CA)를 찾 는 알고리즘을 처음으로 제안하였다. Cho 등은 특성 다항식과 최소다항식이 동일 90/150 MACA를 합성하 기 위해 90/150 SACA(single-attractor CA)를 이용하 여 유도함으로 시간복잡도가 인 MACA 합성법 을 제안하였다[13].
본 논문에서는 기밀성과 인증을 제공하는 Sarkar의 암호기법[14]에 사용된 전이규칙이 90 또는 150인 uniform CA(이하 UCA)에 대하여 분석하고 특별한 전이규칙을 갖는 -셀 90/150 CA를 이용하여 -셀 UCA와 -셀 UCA를 합성하고 대응하는 특성 다항식을 계산하는 방법을 제안한다.
Ⅱ. CA 배경지식
본 논문에서 다루는 1차원 3-이웃(linear 3-neighbourhood) CA는 모든 셀이 선형으로 배열되 어 있고, 국소적 상호작용이 자신과 인접한 두 셀에 의하여 이루어지는 CA이다. CA에 대한 상태전이함수 (state transition function)는 식(1)과 같이 나타낸다.
(1) 여기서
는 시간 에서 번째 셀의 상태를 나타 낸다. 그리고 이러한 는
개가 있으며 이것을 CA 의 전이규칙이라 한다. 본 논문에서 사용되는 전이규 칙 90과 150은 각각 식(2), (3)와 같다.
전이규칙 90 : ⊕ (2) 전이규칙 150 : ⊕ ⊕ (3) CA는 전이규칙에 의해 변화되는 상태를 나타낸 상태전이 그래프의 형태에 따라 그룹 CA와 비그룹 CA로 분류할 수 있다. 그룹 CA는 모든 셀들의 상태 가 몇 개의 사이클을 이루며 반복되는 CA로 임의의 한 상태에 대한 이전상태가 유일하다. 그러나 비그룹 CA는 트리구조를 이루며 이전상태가 유일하지 않다.
각 셀에 적용되는 규칙이 모두 같은 CA를 Uniform CA(이하 UCA)라 하고 두 개 이상의 서로 다른 전이 규칙이 적용되는 CA를 hybrid CA(이하 HCA)라 한 다. 각 셀에 적용되는 전이 규칙이 XOR함수로 모두 표현 될 때, 이러한 CA를 선형 CA(linear CA)라 한 다. 개의 셀로 이루어진 선형 CA의 상태전이함수 는 × 행렬로 나타낼 수 있으며, 이를 상태전이행 렬(state transition matrix)이라 한다. 주어진 -셀 CA의 상태전이행렬 의 특성다항식(characteristic polynomial) 는 위에서 ⊕ 이 다. 여기서, 는 차 단위행렬이다. 또, 특성다항식의 인수 중 를 근으로 갖는 차수가 가장 낮은 다항식 을 최소다항식(minimal polynomial)이라 한다. 그룹 CA의 상태전이그래프에서 사이클의 구조는 CA의 최 소다항식에 의하여 특성화된다. 특히, 전이규칙 90과 150만이 셀에 적용되는 CA인 90/150 CA는 특성다 항식과 최소다항식이 같다[10].
n차 벡터 ⋯ 을 전이규칙 벡터라고 한다. 여기서 는 식(4)을 나타낸다.
번째 셀의 전이규칙
번째 셀의 전이규칙 (4) 전이규칙 벡터가 ⋯ 인 CA라면, 이 CA의 상태전이 행렬은 식(5)와 같은 삼중대각행렬이 다.
⋯
⋯
⋯
⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ ⋮
⋯
⋯
(5)
표기상의 편리함을 위하여 ⋯ 로 쓴다.
Ⅲ. Uniform CA(UCA)의 분석
전이규칙이 90인 UCA ℂ 와 전이규칙이 150인 UCA ℂ 에 대한 분석과 합성을 위하여 식 (6), (7) 과 같은 두 개의 특별한 HCA를 고려해보자.
ℍ : ⋯ (6)
ℍ : ⋯ (7)
셀의 크기에 따른 ℍ ,ℍ 의 특성다항식의 변화는 표 1과 같다. ℍ 의 특성다항식을 라 하고 ℍ 의 특성다항식을 라 하면 두 특성다항식의 관계 는 을 만족한다.
표 1. ℍ ,ℍ 의 특성다항식 Table 1. characteristic polynomials of ℍ ,ℍ
[정리 1] -셀 HCA ℍ 는 그룹 CA이다.
(증명) ℍ 가 그룹 HCA임을 보이기 위해 상태전 이행렬 의 행렬식이 0이 아님을 보이면 된다. - 셀 ℍ 의 의 행렬식은 식(8)과 같다.
(8)
따라서 이다. 그런데
이 홀수인 경
우에는
⋯
1이고
이 짝수인 경우에는 ⋯ 1이다. 그러므로 모든 에 대하여 행렬식 값은 0이 아니다. 따라서 -셀 ℍ 는 그룹 HCA이다. □
[정리 2] -셀 150 UCA는 ∈ℕ일 때만 비그룹 CA이고, 나머지는 그룹 CA이다.
(증명) -셀 150 uniform CA의 행렬 의 행렬식 은 식(9)과 같다.
(9) 같은 방법으로 하면 식(10)을 만족하게 된다.
=( )+ (10)
① 인 경우는 식(11)과 같다.
⋯
1 (11)
② 인 경우는 식(12)과 같다.
⋯
1 (12)
③ 인 경우는 식(13)와 같다.
⋯
0 (13) 따라서-셀 150 UCA는 ∈ℕ일 때 만 비그룹 CA이고, 나머지는 그룹 CA이다. □
[정리 3] -셀 HCA ℍ 는 ∈ ℕ
일 때는 비그룹 CA이고 나머지는 그룹 CA이다.
(증명) -셀 ℍ 의 상태전이행렬 의 행렬식은
식(14)과 같다.
⋯
⋯
⋯
⋮
⋯
⋯
⋯
⋯
⋮
⋯
⋯
⋯
⋯
⋯
⋮
⋯
⋯
(14)
( 는 -셀 150 UCA ℂ 의 상태전이행 렬이다.)
이므로 정리2에 의해 인 경 우는 이고, 인 경우는 이다. 마지막으로
인 경우는 이다. 따 라서 ℍ 는 ∈ ℕ 일 때만 비그룹 CA 이고 나머지는 그룹 CA이다. □
[정리 4] 비그룹 -셀 HCA ℍ 의 상태전이행렬
에 대한 영공간은 다음과 같다.
⋯⋯
(증명) -셀 ℍ 이 비그룹인 경우는 정리3에 의해
∈ ℕ이다. 의 영공간을
⋯ 라 하면 식(15)를 만족한다.
⋯
⋯
⋯
⋮
⋯
⋯
⋮
⋮
(15)
즉, , , ,
⋯
, , 을 만족해야 하므 로 , , , ,
⋯, ,
이다. 따라서 ⋯ 이고 나머지는 모두 0이거나 모두 1인 형태이다. 그러므로 영공간은 ⋯⋯ 이다.
-셀 ℍ ,ℍ 을 이용하여 -셀 90 UCA ℂ 와
150 UCA ℂ 의 합성하는 과정을 보이고 -셀 ℍ , ℍ 의 특성다항식으로부터 -셀 ℂ 와 ℂ 의 특성 다항식을 유도한다.
90/150 CA에서 ⋯ 의 특성다항 식이 이면 의 전이규칙을 mirror 이미지로 합 성한 CA ⋯ ⋯ 의 특 성다항식은 이다[13]. 이러한 성질로부터 - 셀 ℂ 와 ℂ 의 합성이 가능하다. 즉 -셀 ℍ ,ℍ 의 전이규칙을 mirror 이미지로 합성한 CA가 -셀 ℂ 와 ℂ 가 되기 때문이다. 따라서 -셀 ℍ ,ℍ 의 특성다항식이 라 할 때, -셀 ℂ 와 ℂ 의 특성 다항식은 이 된다. 또한 -셀 ℂ 와 ℂ 을 이용 하여 -셀 ℂ 와 ℂ 의 특성다항식의 유도가 가능하다. 다음의 두 정리는 이러한 과정을 보인다.
표 2. ℍ ,ℂ 의 특성다항식 Table 2. characteristic polynomials of ℍ ,ℂ
[정리 5] -셀 ℂ 의 특성다항식이 일 때
-셀 ℂ 의 특성다항식은 이다.
(증명) -셀 ℂ 의 특성다항식을 라 고 하면 식(16)를 만족한다.
⋯
⋯
⋯
⋮ ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ ⋮
⋯
⋯
⋯
(16) 여기서 은 -셀 ℂ 의 특성다항식이다. □
위 정리로부터 -셀 ℂ 는 그 특성다항 식이
이므로 비그룹 CA이다. 표 2는 ℂ 의 특성 다항식이 유도되는 과정을 보여준다. 짝수 셀의 ℂ
는 ℍ 로부터 유도되며 홀수셀의 ℂ 는 ℂ 로부터 유도되고 있음을 알 수 있다.
[정리 6] -셀 ℍ 의 특성다항식이 일 때
-셀 ℂ 의 특성다항식은
이다.
(증명) -셀 ℂ 의 특성다항식을 라 고 하면 식(17)을 만족한다.
⋯ ⋯ ⋯
⋮ ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ ⋮
⋯
⋯
⋯
(17) 여기서 은 -셀 ℂ 의 특성다항식이다. □
위 정리로부터 -셀 ℂ 는 그 특성다항식 이
이므로 길이가 1인 사이클에 놓이는 0 이 아닌 상태가 존재함을 알 수 있다. 정리 7에서 길 이가 1인 사이클에 놓이는 상태를 밝힌다.
[정리 7] -셀 ℂ 의 상태전이그래프에서 사이클의 길이가 1인 상태는 ⋯과
⋯이다.
(증명) x ⋯ 를 -셀 ℂ 의 상태전이그래프에서 길이가 1인 사이클에 놓여 있는 상태라 하면, x x이므로 ⊕ x 이 고 식(18)을 만족한다.
⋯
⋯
⋯
⋮
⋯
⋯
⋮
⋮
(18)
즉, , , ,
⋯,
, 을 만족해야 하므로
⋯ 이고 ⋯
이다. □
표 3은 ℂ 의 특성다항식이 유도되는 과정을 보여 준다. 짝수 셀의 ℂ 은 ℍ 로부터 유도되며 홀수셀의 ℂ 는 ℂ 로부터 유도되고 있음을 알 수 있다.
표 3. ℍ ,ℂ 의 특성다항식 Table 3. characteristic polynomials of ℍ ,ℂ
Ⅳ. 결 론
본 논문에서는 기밀성과 인증을 제공하는 Sarkar의
암호기법[13]에 사용된 전이규칙이 90 또는 150인
uniform CA(이하 UCA)에 대하여 분석하였다. 특별
한 전이규칙을 갖는 -셀 90/150 HCA의 특성다항식
을 이용하여 -셀 UCA의 특성다항식을 유도하였
다. 또한 -셀 UCA를 이용하여 -셀 UCA가 유도되는 과정을 보이고 특성다항식을 유도하였다. 복 잡한 시스템을 모델링하는데 사용하기위해 CA의 크 기가 커져야 하는 것은 불가피한 일이다. 본 논문의 연구결과는 -셀 CA의 특성다항식을 계산하기위해
⌊⌋-셀 CA의 특성다항식만을 계산하면 되는 것 을 보임으로써 다양한 응용분야에 사용되는 CA의 분 석을 위해 유용한 결과라 사료된다.
참고 문헌
[1] S. Wolfram, O. Martin and A. M. Odlyzko,
“Algebraic properties of cellular automata,”
Communications in Mathematical Physics, 3, pp. 219-258, 1984.
[2] A.K. Das, “Additive Cellular Automata: The- ory and Applications as a Built-In Self-Test Structure,” Ph. D. Thesis, I.I.T. Kharagpur, India, 1990.
[3] A.K. Das and P.P. Chaudhuri, “Efficient characterization of cellular automata,” Proc.
IEE(Part E), Vol. 137, pp. 81-87, 1990.
[4] A.K. Das and P.P. Chaudhuri, “Vector space theoretic analysis of additive cellular automata and its application for pseudo-exhaustive test pattern generation,” IEEE Trans. Comput., Vol.
42, pp. 340-352, 1993.
[5] S. Nandi, B.K. Kar and P.P. Chaudhuri,
“Theory and applications of cellular automata in cryptography,” IEEE Trans. Computers, Vol.
43, pp. 1346-1357, 1994.
[6] S. Chakraborty, D.R. Chowdhury, P.P. Cha- udhuri, “Theory and application of nongroup cellular automata for synthesis of easily testable finite state machines,” IEEE Trans.
Computers, Vol. 45, pp. 769-781, 1996.
[7] S. Nandi and P.P. Chaudhuri, “Analysis of periodic and intermediate boundary 90/150 cellular automata,” IEEE Trans. Computers, Vol. 45, pp. 1-12, 1996.
[8] S.J. Cho, U.S. Choi, Y.H. Hwang, Y.S. Pyo, H.D. Kim and S.H. Heo, “Computing Phase Shifts of Maximum-Length 90/150 Cellular Automata Sequences,” LNCS, Vol. 3305, pp.
31-39, 2004.
one-dimensional linear hybrid cellular automata over
,” IEEE Transactions of Computers, Vol. 45, pp. 782-792, 1996.
[10] K. Cattell and J. Muzio, “Synthesis of one-dimensional linear hybrid cellular aut- omata,” IEEE Transactions on Computer-Aided Design of Integrated Circuit and Systems, Vol.
15, pp. 325-335, 1996.
[11] S.J. Cho, U.S. Choi, H.D. Kim and Y. H.
Hwang, “New synthesis of one-dimensional 90/150 linear hybrid group cellular automata,”
IEEE Trans. Comput-Aided Des. Integr.
Circuits Syst., Vol. 26(9), pp. 1720-1724, 2007.
[12] S. Chattopadhyay, “Some studies on theory and application of additive cellular automata,”
PhD thesis, I.I.T., Kharagpur, India, 1995.
[13] S.J. Cho, U.S. Choi, H.D. Kim and Y. H.
Hwang, J.G. Kim, “Analysis of 90/150 Two Predecessor Nongroup Cellular Automata,”
ACRI 2008 LNCS Vol. 5191, pp. 128-135, 2008.
[14] S.K. Sarkar, T. Karmakar, A. Kumar, K.
Sharma, P.C. Pradhan and C. Puttamadappa,
“A One Dimensional Cellular Automata based Security Sheme providing both Authentication and Confidentiality,” IE(I) Journal-CP, Vol. 87, pp. 1-8, 2006.
저자 소개
최언숙(Un-Sook Choi)
1992년 2월 성균관대학교 산업공 학과 졸업 (공학사)
2000년 2월 부경대학교 대학원 응용수학과 졸업(이학석사) 2004년 2월 부경대학교 대학원 응용수학과 졸업(이 학박사)
2009년 8월 부경대학교 대학원 정보보호학과 졸업 (공학박사)
동명대학교 미디어공학과 전임강사
※ 주 관심분야 : 셀룰라 오토마타론, 정보보호, 암
호이론
조성진(Sung-Jin Cho)
1979년 2월강원대학교 수학교육 과 졸업 (이학사)
1981년 2월 고려대학교 대학원 수학과 졸업(이학석사)
1988년 2월 고려대학교 대학원 수학과 졸업(이학박사) 부경대학교 응용수학과 교수
※ 주 관심분야 : 셀룰라 오토마타론, 정보보호, 부 호이론, 컴퓨터 구조론
임지미(Ji-Mi Yim)
