Feedback shift registers, 2-adic span, and combiners with memory |
| |
Authors: | Andrew Klapper Mark Goresky |
| |
Affiliation: | (1) Department of Computer Science, University of Kentucky, 763H Anderson Hall, 40506-0047 Lexington, KY, U.S.A.;(2) School of Mathematics, Institute for Advanced Study, Princeton, NJ, U.S.A. |
| |
Abstract: | Feedback shift registers with carry operation (FCSRs) are described, implemented, and analyzed with respect to memory requirements,
initial loading, period, and distributional properties of their output sequences. Many parallels with the theory of linear
feedback shift registers (LFSRs) are presented, including a synthesis algorithm (analogous to the Berlekamp-Massey algorithm
for LFSRs) which, for any pseudorandom sequence, constructs the smallest FCSR which will generate the sequence. These techniques
are used to attack the summation cipher. This analysis gives a unified approach to the study of pseudorandom sequences, arithmetic
codes, combiners with memory, and the Marsaglia-Zaman random number generator. Possible variations on the FCSR architecture
are indicated at the end.
Andrew Klapper was sponsored by the Natural Sciences and Engineering Research Council under Operating Grant OGP0121648, the
National Security Agency under Grant Number MDA904-91-H-0012, and the National Science Foundation under Grant Number NCR9400762.
The United States Government is authorized to reproduce and distribute reprints notwithstanding any copyright notation hereon.
Mark Goresky was partially supported by the Ellentuck Fund and National Science Foundation Grant Number DMS 9304580. |
| |
Keywords: | Binary sequence Shift register Stream cipher Combiner with memory Cryptanalysis 2-Adic numbers Arithmetic code 1/q Sequence Linear span |
本文献已被 SpringerLink 等数据库收录! |
|