# 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

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

Many results in the book are new, and over seventy percent of these results described in this book are based on recent research results.

View full description*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.

### Book information

- Published: April 1998
- Imprint: NORTH-HOLLAND
- ISBN: 978-0-444-82873-6

### Reviews

...This is the first book devoted to the study of the extensive cross-fertilization 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

### Table of 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 number-theoretic 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

*Z*. Period and its cryptographic importance.

_{m}**Cyclotomy and Cryptographic Functions.**Cyclotomic numbers. Cyclotomy and cryptography. Cyclotomy and difference parameters. Cyclotomy and the differential cryptanalysis. Cryptographic cyclotomic numbers. Cryptographic functions from

*Z*to

_{p}*Z*. The case

_{d}*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

*Z*to

_{pq}*Z*. Whiteman's generalized cyclotomy and cryptography. Cryptographic functions from

_{d}*Z*to

_{pq}*Z*. Cryptographic functions from

_{2}*Z*to

_{pq}*Z*. Cryptographic functions from

_{4}*Z*to

_{p2}*Z*. Cryptographic functions defined on

_{2}*GF(p*. The origin of cyclotomic numbers.

^{m})**Special Primes and Sequences.**Sophie Germain primes and sequences. Their importance in stream ciphers. Their relations with other number-theoretic 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 2

^{n}+ 1 and sequences. Primes of form (

*a*- 1)/(

^{n}*a*- 1) and sequences. Mersenne primes and sequences. Cryptographic primes of form ((4

*u*)

*- 1)/(4*

^{n}*u*- 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. Two-prime generator of order 2. Two-prime generator of order 4. Prime-square 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

*r*th-order 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*(2

*). APN permutations and their properties. Quadratic permutations with controllable nonlinearity. Permutations of order 3. APN permutations of order*

^{n}*n*- 1. Permutations of order

*n*- 2. Permutations

*X*with

^{d}*d*= 2

*- 1. APN permutations via crosscorrelation function. Other power functions with good nonlinearity. Choosing the linear functions. Cyclic-key generators and their problems. Cyclic-key generators. Several specific forms: An overview. A generator based on permutations of*

^{m}*Z*.

_{m}**Quadratic Partitions and Cryptography.**Quadratic partition and cryptography.

*p*=

*x*+

^{2}*y*and

^{2}*p*=

*x*+ 4

^{2}*y*.

^{2}*p*=

*x*+

^{2}*2y*and

^{2}*p*=

*x*+ 3

^{2}*y*.

^{2}*p*=

*x*+

^{2}*ny*and quadratic reciprocity.

^{2}*p*=

*x*+

^{2}*7y*and quadratic forms.

^{2}*p*=

*x*+

^{2}*15y*and genus theory.

^{2}*p*=

*x*+

^{2}*ny*and class field theory. Other cryptographic quadratic partitions.

^{2}**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.

**The 2-adic value and 2-adic expansion. A fast algorithm for the 2-adic expansion. The arithmetric of**

*P*-Adic Numbers, Class Numbers and Sequences.*Q*

_{[2]}and

*Z*

_{[2]}. Feedback shift registers with carry. Analysis and synthesis of FCRSs. The 2-adic span and 2-RA algorithm. Some properties of FCSR sequences. Blum-Blum-Shub sequences & class numbers.

**Prime Ciphering Algorithms.**Prime-32: a description. Theoretical results about prime-32. Security arguments. Performing of prime-32. Prime-32 with a 192-bit key. Prime-64.

**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.**