首页 | 本学科首页   官方微博 | 高级检索  
     


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号