# Research on Feedback with Carry (2-Adic) Shift Registers

This major project is in the area of **Stream Ciphers**. This is a method of
encryption in which a binary sequence (a ``key'') is added to a message bit by
bit to hide it from an eavesdropper. A legitimate receiver who knows the key
can subtract it out to recover the message, but a hostile eavesdropper who does
not know the key cannot. The goal of the study of stream ciphers is to design
key generators that are fast and whose keys resist attack. Conversely, we want
to design attacks on existing key generators to expose their weaknesses. These
attacks are generally of the form ``given a few bits of the key, try to discover
the remainder of the key.''
In joint work with Mark Goresky, I am studying a new type of binary sequence
generator, **Feedback with Carry Shift Registers** or FCSRs which we invented
in 1993. This construction is based on division in the 2-adic numbers. Many of
the algebraic properties of linear feedback shift registers have parallels for
FCSRs. We have developed a method of synthesizing FCSRs from short subsequences
of their output. This provides us with a new measure for cryptologic security
of stream ciphers, the **2-adic span**. Future designers of stream cipher
will have to show that their sequences have large 2-adic span. We have used
these ideas to give an attack on a well known and commercially used stream
cipher, the summation combiner. We have also extended our initial construction
to more general registers based on division in ramified and unramified
extensions of the 2-adic numbers. We are currently studying methods of
modifying FCSRs so the resulting sequences have large 2-adic span, as well as
resistance to other cryptologic attacks. These results have caused
excitement in the cryptography community. I first presented them at the
Cambridge Algorithms Workshop in Cambridge, England, December 1993, and an
abstract appears in the *Springer LNCS volume number 809 ("Fast Software
Encryption")*. I described extensions at several conferences in 1994 and 1995:
*Midwest Theory Day*; *Eurocrypt 1994*; and
*The IEEE International Symposium on Information Theory*. Further results
were presented at the *Leuven Algorithms Workshop* in December 1994.
Results relating to statistical
properties were presented at *Eurocrypt 1995 (Springer LNCS volume 921)*.
The FCSR synthesis algorithm was presented at * Crypto 1995 (Springer LNCS
volume 963)*.

This material is based upon work supported by the National Science Foundation
under Grant No. 9400762

### Papers: