90 / 150 Uniform CA의 합성 및 특성다항식 계산

Synthesis of 90/150 Uniform CA and Computation of Characteristic Polynomial corresponding to uniform CA

전이 규칙 90과 150만을 사용하는 90/150 CA는 최소다항식과 특성다항식이 같은 CA로 랜덤성이 우수하여 LFSR의 대안으로 사용되어왔다. 90 Uniform CA와 150 uniform CA는 모든 셀에 동일한 전이규칙이 적용되는 CA로 기밀성과 인증을 제공하는 Sarkar의 암호기법에 사용되었다. 본 논문에서는 전이규칙이 90 또는 150인 uniform CA에 대하여 분석하고 특별한 전이규칙을 갖는 n-셀 90/150 CA를 이용하여2n-셀 uniform CA와 2n -셀 uniform CA를 합성하고 대응하는 특성다항식을 계산하는 효율적 방법을 제안한다

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 2n-cell uniform CA and ？？(2n + 1) -cell uniform CA using a special n-cell 90/150 CA. And we propose an effective method of computation of characteristic polynomial corresponding to uniform CA.