Stream Ciphers And Number Theory

P r e f a c e to t h e R e v i s e d E d i t i o n Since the publication of this monograph in 1998, a considerable amount of advances on interactions between stream ciphers and number theory has been made. The objective of this revised edition is to report the recent advances and correct typos and errors in the original version. Most chapters are revised. In particular, Chapter 6 is completely rewritten. We thank Y.-H. Park, D. Hong and E. Chun for pointing out an error in computing the linear complexity of the prime-square generator in Chapter 8 of the original edition. We are grateful to S.S. Bedi and R. Pillai for pointing an error in Section 14.6, and for providing us with the source code of their C-implementation of the 2-RA algorithm. August 2003 Thomas W. Cusick Cunsheng Ding Ari Renvall P r e f a c e to t h e First E d i t i o n The goal of cryptography is the concealment of messages in such a way that only authorized people can read them. A cipher or cryptosystem is an algorithm for carrying out this concealment. If a message M is represented as a string of characters m l, m2, ... from some fixed character set or alphabet, then a cipher consists of two processes: encryption, a method for converting the message or plaintext into a ciphertext meant to be unreadable by unauthorized people; and decryption, a method for recovering the message from the ciphertext. Broadly speaking, cryptosystems can be classified as either block ciphers or stream ciphers. A block cipher breaks up a message M into successive blocks M1, M2, ... of elements from the alphabet. There is a key set K such that each key k in the set corresponds to an encryption algorithm Ek which acts on the blocks of plaintext. Thus a plaintext M1, M2, ... is encrypted as Ek(M1), Ek(M2), .... There is a decryption algorithm Dk for each key k such that Dk(Ek(Mi)) = Mi; thus