A statistical test for stream ciphers based on the maximum order complexity

被引：4

作者：

Kasselman, PR ^{[1
]}

机构：

[1] Ciphertec CC, ZA-0102 Menlo Pk, South Africa

来源：

PROCEEDINGS OF THE 1998 SOUTH AFRICAN SYMPOSIUM ON COMMUNICATIONS AND SIGNAL PROCESSING: COMSIG '98 | 1998年

关键词：

statistical tests; stream ciphers; maximum order complexity; Gamma distribution;

D O I：

10.1109/COMSIG.1998.736951

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

The maximum order complexity determines the shortest feedback shift register which can generate a given sequence utilising a memoryless, possibly non linear, feedback function. The maximum order complexity of a sequence is a potentially useful measure of the randomness of a sequence. In this paper a statistical test based on the maximum order complexity is proposed. The proposed test requires that the distribution of the maximum order complexity of a random sequence of arbitrary length is known. Erdmann and Murphy derived an expression which approximates the distribution of the maximum order complexity [1]. Evaluating this expression is computationally expensive and an alternative approximation to the distribution of the maximum order complexity is proposed. The alternative approximation is then used to construct a computationally efficient statistical test which may be used to evaluate the randomness of a sequence. The proposed test is specifically concerned with binary sequences and the distribution of the maximum order complexity of binary sequences.

引用

页码：213 / 218

页数：6