Stream Ciphers and Number Theory
By T.W. Cusick, State University of New York, Buffalo, NY, USA
 C. Ding, The National University of Singapore, Singapore
 A. Renvall, University of Turku, Finland
This book is almost entirely concerned with stream ciphers, concentrating on a particular mathematical model for such ciphers which are called additive natural stream ciphers. These ciphers use a natural sequence generator to produce a periodic keystream. Full definitions of these concepts are given in Chapter 2.
This book focuses on keystream sequences which can be analysed using number theory. It turns out that a great deal of information can be deducted about the cryptographic properties of many classes of sequences by applying the terminology and theorems of number theory. These connections can be explicitly made by describing three kinds of bridges between stream ciphering problems and number theory problems. A detailed summary of these ideas is given in the introductory Chapter 1.
Many results in the book are new, and over seventy percent of these results described in this book are based on recent research results.
NorthHolland Mathematical Library
,
Published: April 1998
Imprint: Northholland
ISBN: 9780444828736
Reviews

...This is the first book devoted to the study of the extensive crossfertilization between stream ciphers and number theory. Many results in the book are new, and over seventy percent of the results described are based on recent research by the authors.
Cyptologia, Vol. XXIII, January 1999
...This is a cryptography book which focuses on methods for producing keystream sequences fpr stream ciphers.
Mathematical Reviews, 1999
This book is a readable and important contribution for stimulating the interaction between stream ciphers and number theory.
T. Helleseth, Zentralblatt fur Mathematik, Vol. 916, 1999
Contents
 Preface. Introduction. Applications of number theory. An outline of this book. Stream Ciphers. Stream cipher systems. Additive synchronous stream ciphers. Nonadditive synchronous stream ciphers. Stream ciphering with block ciphers. Cooperative distributed ciphering. Some keystream generators. Generators based on counters. Some numbertheoretic generators. Cryptographic aspects of sequences. Minimal polynominal and linear complexity. Pattern distribution of key streams. Correlation functions. Sphere complexity and linear cryptanalysis. Higher order complexities. Harmony on binary NSGs. Security attacks. Primes, Primitive Roots and Sequences. Cyclotomic polynominals. Two basic problems from stream ciphers. A basic theorem and main bridge. Primes, primitive roots and binary sequences. Primes, primitive roots and ternary sequences. Primes, negord and sequences. Prime powers, primitive roots and sequences. Prime products and sequences. Binary sequences and primes. Ternary sequences and primes. On cryptographic primitive roots. Linear complexity of sequences over Zm. Period and its cryptographic importance. Cyclotomy and Cryptographic Functions. Cyclotomic numbers. Cyclotomy and cryptography. Cyclotomy and difference parameters. Cyclotomy and the differential cryptanalysis. Cryptographic cyclotomic numbers. Cryptographic functions from Zp to Zd. The case d = 2. The case d = 3. The case d = 4. The case d = 5. The case d = 6. The case d = 8. The case d = 10. The case d = 12. Cryptographic functions from Zpq to Zd. Whiteman's generalized cyclotomy and cryptography. Cryptographic functions from Zpq to Z2. Cryptographic functions from Zpq to Z4. Cryptographic functions from Zp2 to Z2. Cryptographic functions defined on GF(pm). The origin of cyclotomic numbers. Special Primes and Sequences. Sophie Germain primes and sequences. Their importance in stream ciphers. Their relations with other numbertheoretic problems. The existence problem. A search for cryptographic Sophie Germain primes. Tchebychef primes and sequences. Their cryptographic significance. Existence and search problem. Other primes of form k x 2n + 1 and sequences. Primes of form (an  1)/(a  1) and sequences. Mersenne primes and sequences. Cryptographic primes of form ((4u)n  1)/(4u  1). Prime repunits and their cryptographic values. n! ± 1 and p# ± 1 Primes and sequences. Twin primes and sequences over GF(2). The significance of twins and their sexes. Cryptographic twins and the sex distribution. Twin primes and sequences over GF(3). Other special primes and sequences. Prime distribution and their significance. Primes for stream ciphers and for RSA. Difference Sets and Cryptographic Functions. Rudiments of difference sets. Difference sets and autocorrelation functions. Differece sets and nonlinearity. Difference sets and information stability. Difference sets and linear approximation. Almost difference sets. Almost difference sets and autocorrelation functions. Almost difference sets, nonlinearity and approximation. Summary. Difference Sets and Sequences. The NSG realization of sequences. Differential analysis of sequences. Linear complexity of DSC (ADSC) sequences. Barker sequences. Binary Cyclotomic Generators. Cyclotomic generator of order 2k. Twoprime generator of order 2. Twoprime generator of order 4. Primesquare generator. Implementation and performance. A summary of binary cyclotomic generators. Analysis of Cyclotomic Generators of Order 2. Crosscorrelation property. Decimation property. Linear complexity. Security against a decision tree attack. Sums of DSC sequences. Linear complexity analysis. Balance analysis. Correlation analysis. Differential analysis. Nonbinary Cyclotomic Generators. The rthorder cyclotomic generator. Linear complexity. Autocorrelation property. Decimation property. Ideas behind the cyclotomic generators. Generators Based on Permutations. The cryptographic idea. Permutations on finite fields. A generator based on inverse permutations. Binary generators and permutations of GF(2n). APN permutations and their properties. Quadratic permutations with controllable nonlinearity. Permutations of order 3. APN permutations of order n  1. Permutations of order n  2. Permutations Xd with d = 2m  1. APN permutations via crosscorrelation function. Other power functions with good nonlinearity. Choosing the linear functions. Cyclickey generators and their problems. Cyclickey generators. Several specific forms: An overview. A generator based on permutations of Zm. Quadratic Partitions and Cryptography. Quadratic partition and cryptography. p = x2 + y2 and p = x2 + 4y2. p = x2 + 2y2 and p = x2 + 3y2. p = x2 + ny2 and quadratic reciprocity. p = x2 + 7y2 and quadratic forms. p = x2 + 15y2 and genus theory. p = x2 + ny2 and class field theory. Other cryptographic quadratic partitions. Group Characters and Cryptography. Group characters. Field characters and cryptography. Field multiplicative characters: most used ones. Field additive characters: most used ones. The nonlinearity of characters. The nonlinearity of multiplicative characters. The nonlinearity of additive characters. Ring characters and cryptography. Group characters and cyclotomic numbers. PAdic Numbers, Class Numbers and Sequences. The 2adic value and 2adic expansion. A fast algorithm for the 2adic expansion. The arithmetric of Q[2] and Z[2]. Feedback shift registers with carry. Analysis and synthesis of FCRSs. The 2adic span and 2RA algorithm. Some properties of FCSR sequences. BlumBlumShub sequences & class numbers. Prime Ciphering Algorithms. Prime32: a description. Theoretical results about prime32. Security arguments. Performing of prime32. Prime32 with a 192bit key. Prime64. Cryptographic Problems and Philisophies. Nonlinearity and linearity. Stability and instability. Stability and diffusion. Stability and local nonlinearities and differences. Correlation stability and pattern stability. Mutual information stability. Localness and globalness. Goodness and badness. About good plus good. About good plus bad. About Bad plus good. Hardware and software model complexity. A. More About Cyclotomic Numbers. Cyclotomic numbers of order 7. Cyclotomic numbers of order 9, 28. Cyclotomic numbers of order eleven. On other cyclotomic numbers. Behind cyclotomic numbers. B. Cyclotomic Formulae of Order 6, 8 and 10. C. Finding Practical Primes. D. List of Research Problems. E. Exercises. F. List of Mathematical Symbols. Bibliography. Index.