TU Dresden · TECHNISCHE UNIVERSITÄT DRESDEN Fakultät Elektrotechnik und Informationstechnik Institut für Nachrichtentechnik Lehrstuhl Theoretische Nachrichtentechnik Diplomarbeit

TECHNISCHE UNIVERSITÄT DRESDEN

Fakultät Elektrotechnik und Informationstechnik

Institut für Nachrichtentechnik

Lehrstuhl Theoretische Nachrichtentechnik

Diplomarbeit

Thema: Analyse und Synthese von Pseudozufallsgeneratoren für Stromchiffrierungen

vorgelegt von: Martin Mittelbach

geboren am: 14. Januar 1978 in: Leinefelde

zur Erlangung des akademischen Grades

Diplomingenieur (Dipl.-Ing)

Betreuer: Dr.-Ing. H. Wiehl

Verantwortlicher Hochschullehrer: Prof. Dr.-Ing. habil. A. Finger

Tag der Einreichung: 24. April 2003

To my parents

Selbstständigkeitserklärung

Hiermit erkläre ich, dass die vorliegende Diplomarbeit mit dem Thema

„Analyse und Synthese von Pseudozufallsgeneratoren für Stromchiffrierungen“

von mir selbstständig verfasst wurde. Dabei sind keine anderen aufzählungspflichtigen

Hilfsmittel als die angegebenen Quellen benutzt worden. In dieser Arbeit verwendete Zitate

sind als solche gekennzeichnet.

Dresden, 23. April 2003

Martin Mittelbach

Aufgabenstellung

Contents 1

Contents

1 Introduction 3 1.1 Motivation ............................................................................................................... 3

1.2 Background and Classification................................................................................ 3

1.3 Objective of Thesis and Outline.............................................................................. 5

2 Stream Ciphers and Feedback Shift Registers 6 2.1 Introduction ............................................................................................................. 6

2.1.1 Block and Stream Ciphers......................................................................... 6

2.1.2 The One-Time-Pad.................................................................................... 7

2.1.3 Synchronous Stream Ciphers .................................................................... 7

2.1.4 Self-synchronous Stream Ciphers ............................................................. 8

2.2 Pseudorandom Sequences for Stream Ciphering .................................................... 9

2.3 Feedback Shift Registers ....................................................................................... 11

2.3.1 Linear Feedback Shift Registers ............................................................. 11

2.3.1.1 Register Architecture ............................................................... 11

2.3.1.2 Analysis of LFSRs ................................................................... 12

2.3.2 Feedback Carry Shift Registers............................................................... 13

2.3.2.1 Mathematical Foundations ....................................................... 13

2.3.2.2 Register Architecture ............................................................... 17

2.3.2.3 Analysis and Synthesis of FCSRs ............................................ 18

2.3.2.4 Properties of l-sequences.......................................................... 21

2.4 Complexity Measures............................................................................................ 22

2.4.1 Linear Complexity .................................................................................. 23

2.4.2 2-adic Complexity................................................................................... 24

2.5 Keystream Generators Based on LFSRs ............................................................... 27

2.5.1 Classification........................................................................................... 27

2.5.2 The Geffe-Generator ............................................................................... 29

3 Keystream Generators Based on FCSRs 31 3.1 Simulation ............................................................................................................. 31

3.2 Some more Properties of l-sequences ................................................................... 32

Contents 2


3.2.2 Autocorrelation Function ........................................................................ 33

3.3 The lp-Geffe-Generator.......................................................................................... 34

3.3.1 Period ...................................................................................................... 35

3.3.2 Bit Pattern Distribution ........................................................................... 37



3.4 The 2-adic-Geffe-generator and FCSRs with Composed Connection Integer...... 47

3.4.1 Period ...................................................................................................... 47

3.4.2 Bit Pattern Distribution ........................................................................... 51



4 Summary 60

Glossary 61

Literature References 66

List of Figures 68

List of Tables 70

Appendixes 71

A 1. List of 2-Primes............................................................................................ 71

A 2. The Berlekamp-Massey Algorithm.............................................................. 72

A 3. The Rational Approximation Algorithm...................................................... 73

A 4. Linear complexity of FCSR sequences with 2-prime connection integer

(q < 10000)................................................................................................... 74

A 5. List of 2-prime Connection Integers for lp-Geffe-Generators Producing

Sequences with Complementary Period Halves (q ≤ 509) .......................... 75

1 Introduction 3

1 Introduction

1.1 Motivation

In history, cryptography has been a privilege reserved for governments and military, which are concerned about protecting their own secrets and information relevant to national security and public safety. As the world moved into an information society, securely protecting data has become important also in the private sector. Today, more and more data is stored and transmitted electronically and the privacy of individual people as well as of organizations relies heavily on the possibility of secure communication. Therefore, securing and authenticating data has become an important aspect of modern computer and communication systems. A number of developments have caused the need for cryptographic technologies and systems for private and commercial use:

• Some industries, in particular financial services, operate funds transfers to a large and increasing extent in electronic form.

• The development of the world economy has lead to an increasing number of internationally operating companies, which electronically exchange and transfer sensitive information such as confidential documents containing e.g. intellectual proprietary.

• The fast development of the internet and the broadening use of computers and computer networks initiate an increased computerization of economical life and a widespread use of electronic services such as electronic banking, e-commerce, or music and video on demand services.

• Wireless communications systems, such as cellular telephones, which are highly vulnerable to unauthorized intercepts, have become increasingly important in recent times.

All these examples show that cryptography has become a part of nearly everyone’s life and indicate the need for advanced and fast cryptographic systems enabling secure high-speed communications.

1.2 Background and Classification

Cryptographic systems allow information to be sent in a secure form so that only the intended recipient is able to recover this information1. All modern cryptosystems make use of a key-pair in such a way that the security lies completely in the keys, meaning all details of the employed algorithm or hardware may be publicly available. At the sending site the plaintext message is transformed (encrypted) into a ciphertext message under control of the encryption key and is then transmitted over a public, unsecured channel. At the receiver, the encryption process is reversed, i.e. the ciphertext is turned back (decrypted) into the original plaintext. This decryption process is controlled by the secret decryption key. There are two general types of key-based algorithms: public-key and symmetric-key algorithms.

1 Most of the facts presented in this section are of very general and introductory nature and can be found in every book about cryptography so that respective literature references are omitted.

1 Introduction 4

Public-key algorithms are asymmetric meaning that the key used for encryption is different from the key used for decryption. Furthermore, the decryption key cannot be determined from the encryption key so that the recipient can make his encryption key public to all, intended to securely send him a message (giving the algorithm’s name). The most commonly used system of this type is the RSA2 cryptosystem [RIV78]. Since, public-key algorithms are computationally intensive, encryption and decryption is slow. This is not significant for short messages, but certainly is for large amounts of data such as video or audio.

Symmetric-key algorithms are algorithms where the same key is used for both encryption and decryption, hence their name. Sender and receiver need to agree on an identical key that must remain secret as long as their communication needs to remain secret. The key itself must be transmitted to the recipient in a secure way, which is mostly accomplished with a public-key algorithm. This type of cryptosystem is very important in modern cryptography because, in general, symmetric-key cryptosystems are much faster than public-key systems. They are commonly classified into block and stream ciphers.

Block ciphers group the plaintext into fixed size blocks and encrypt each block

independently. Widely used block ciphers are the DES3 [DES99] and the AES4 [AES01]. In contrast, stream ciphers subdivide the plaintext into smaller entities, called characters (usually bits), and operate on each character under a time-varying function. Stream ciphers are generally faster to execute in hardware than block ciphers. They are more suitable or even obligatory in situations where buffering is limited or when characters must be immediately processed as they are received (e.g. telecommunications applications or pay television). Moreover, when transmission errors are highly probable, stream ciphers may also be advantageous because they have limited or no error propagation. There is much theoretical knowledge on stream ciphers allowing systematic design procedures, whereas there is only very little theory on block ciphers. Furthermore, well-designed stream ciphers can destroy statistical properties of the plaintext while block ciphers may not. Because of these significant advantages stream ciphers are very important and widely used today, particularly in high-speed and real-time applications.

The central design problem for stream ciphers is the development of devices which can

efficiently generated pseudorandom sequences. Most pseudorandom generators are based on feedback shift registers (FSRs) because they are well suited to hardware implementations. Especially linear feedback shift registers (LFSRs) have widely been used as building blocks for fast pseudorandom generators. Many modern stream ciphers are designed by combining several LFSRs in various nonlinear ways to obtain highly complex sequences. As alternative to this feedforward structure, a great amount of effort has been spent to study nonlinear feedback architectures but with only very little success. A new analyzable feedback architecture was introduced by Klapper and Goresky [KLA97] called “feedback with carry” shift registers (FCSRs). An FCSR is a feedback shift register together with a small amount of extra memory. The algebraic structure of 2-adic numbers [KOB77] is the mathematical tool with which sequences generated by FCSRs can be analyzed in the same way as the algebra over finite fields can be used to analyze LFSR-sequences. The investigation of FCSRs and FCSR-based sequence generators is the main objective of this thesis.

2 named after its inventors Rivest, Shamir, and Adleman 3 Data Encryption Standard 4 Advanced Encryption Standard

1 Introduction 5

1.3 Objective of Thesis and Outline

The objective of this thesis is the analysis of pseudorandom sequence generators that are based on feedback shift registers. Starting from the linear feedback architecture the thesis mainly focuses on feedback with carry shift register-based pseudorandom generators and particularly on nonlinear combinations of these basic registers. The cryptographic strength of the considered generators and the “randomness quality” of the generated sequences are empirically, numerically, and analytically evaluated in terms of pattern distribution and autocorrelation properties as well as of certain complexity measures such as the linear complexity. In agreement with the supervisor, the investigation of parallel structures for bus-system applications, as postulated in the thesis task, is left out to allow a deeper study of the previously mentioned aspects. In the remainder of the thesis only the case of binary sequences will be considered.

The thesis is organized as follows: In chapter §2 the theory and basic concepts relevant to the thesis are introduced. The first section (§2.1) describes stream ciphers as symmetric key systems in comparison to block ciphers (§2.1.1), introduces the notion of pseudorandom generators (§2.1.2), and explains synchronous (§2.1.3) and self-synchronous (§2.1.4) stream ciphers as common subclasses. The next section (§2.2) presents randomness criteria of cryptographically useful pseudorandom sequences such as Golomb’s randomness postulates. LFSRs and FCSRs are studied in section §2.3. In subsection §2.3.1 a brief review of main properties of LFSRs are provided. The LFSR architecture is described in §2.3.1.1 and the underlying theory is summarized in §2.3.1.2. Subsequently, FCSRs are introduced similarly to LFSRs but in much more detail: Mathematical foundations (§2.3.2.1), register architecture (§2.3.2.2) and analysis (§2.3.2.3), and maximal-period FCSR-sequences (§2.3.2.4) are discussed. Section (§2.4) introduces complexity measures based on the linear feedback and the feedback carry register type, namely the linear complexity (§2.4.1) and the 2-adic complexity (§2.4.2). In the last section (§2.5), it is described how LFSRs are used as building blocks in nonlinear pseudorandom sequence generators (§2.5.1) with the purpose to provide a basis for the construction and analysis of FCSR-based generators. The Geffe-generator is examined in more detail as a special type of a nonlinear generator (§2.5.2).

In chapter §3 FCSR-based pseudorandom sequence generators are analyzed. At first (§3.1), technical aspects concerning the generation and analysis of simulation data are discussed. Second (§3.2), some more characteristics of maximal-period FCSR-sequences regarding linear complexity and autocorrelation properties are presented. The nonlinear combination of FCSRs using the Geffe-function is examined in section (§3.3) with respect to period (§3.3.1), bit pattern distribution (§3.3.2), linear complexity (§3.3.3), and autocorrelation properties (§3.3.4) of the generated sequences. A further modification of this structure that employs 2-adic arithmetic instead of Boolean operations to combine the outputs of FCSRs is investigated in section §3.4. The resulting generator is equivalent to a more general FCSR and is studied likewise regarding period (§3.4.1), bit pattern distribution (§3.4.2), linear complexity (§3.4.3), and autocorrelation properties (§3.4.4) of the output sequences.

The last chapter (§4) summarizes the main results of the thesis and discusses questions that still remain open.

I would like to thank Prof. Finger for his confidence, his great support and help whenever I was asking for, and all of his valuable comments and suggestions. I am grateful to DI Schönfeld and Dr. Wiehl for their technical support. Especially and emphatically, I would like to thank my girlfriend Anja, my family, and my friends for their important personal support.

2 Stream Ciphers and Feedback Shift Registers 6

2 Stream Ciphers and Feedback Shift Registers

As already stated, stream ciphers are an important class of symmetric-key encryption algorithms. They are employed when large amounts of data need to be encrypted very quickly. Since many applications require secure ultra-high-speed data communications, stream ciphers are widely used today. Most modern stream ciphers are based on linear feedback shift registers (LFSRs) because they provide an economical, fast, and efficient method for generating pseudorandom sequences. During the last few years, feedback carry shift registers (FCSRs) have been investigated as alternative method for the efficient generation of long pseudorandom binary sequences. The analysis of FCSR-based sequence generators is the main objective of this thesis.

This chapter introduces the theory and basic concepts relevant to the thesis. It is organized as follows: The first section (§2.1) explains what stream ciphers are, describes common subclasses of stream ciphers, and introduces the notion of pseudorandom generators. The next section (§2.2) discusses randomness criteria of cryptographically useful pseudorandom sequences. LFSRs and FCSRs are studied in section §2.3 as a certain kind of pseudorandom generator. Complexity measures based on these two register types, namely the linear complexity and the 2-adic complexity, are discussed in section §2.4. In the last section (§2.5), keystream generators employing nonlinear extensions of LFSRs are introduced to serve as starting point for the construction of FCSR-based keystream generators. The Geffe-generator is examined in more detail as a special type of a nonlinear generator (§2.5.2).

2.1 Introduction

2.1.1 Block and Stream Ciphers

The two major categories of symmetric key systems are block and stream ciphers [RUE86]. The essential distinction between block and stream ciphers is the memory.

A block cipher breaks the plaintext into fixed size blocks and under control of a key each block is encrypted independently. The same transformation is used to process consecutive blocks, thus block ciphers are memoryless. Since, block ciphers encrypt identical plaintext blocks into identical ciphertext blocks they are simple substitution ciphers. Therefore they must have large alphabets, i.e. large block sizes, to provide security.

Stream ciphers operate on small blocks or characters (usually bits) and the encryption function depends on not only the secret key but also on the current state of the system. Therefore, stream ciphers are devices with internal memory. The state is changed after the encryption of each character with respect to some state-change function. Consequently, two identical plaintext characters are usually transformed into different ciphertext characters. The sequence, which controls the encryption, is called the keystream or running key. The deterministic automaton, which produces the keystream from the current key and the internal state, is called the keystream generator.

The given classification into block and stream ciphers is not absolute, since, adding memory to a block cipher results in a stream cipher with large characters.


2.1.2 The One-Time-Pad

Theoretically, a truly random keystream having the same length as the message and that is used only once for encryption provides perfect security [RUE86]. This keystream, consisting of independently and randomly generated characters, is called a one-time-pad. Perfect security means that ciphertext and plaintext are statistically decoupled, i.e. the ciphertext does not transfer any information about the plaintext regardless of the statistical distribution of the plaintext. The obvious drawbacks of the one-time-pad are that it has to be generated by a true random process and that it should be as long as the plaintext. Because of the difficulties of key generation, key distribution, and key management, the one-time-pad is impractical.

This motivates the design of stream ciphers where the purely random keystream generator is replaced by a finite state machine, which generates a deterministic pseudorandom sequence. Such stream ciphers are not perfectly secure but, if well designed, they are computationally secure. The security of such a stream cipher depends on the “randomness quality” of the generated keystream. Hence, a central design problem is the development of devices, which can efficiently generate large period sequences that satisfy various statistical criteria.

Stream ciphers are usually classified into synchronous and self-synchronous systems [RUE86].

2.1.3 Synchronous Stream Ciphers

In a synchronous stream cipher, the next state depends only on the previous state. The keystream is therefore independent of the plaintext message and of the ciphertext message. The encryption transformation of a synchronous stream cipher can be described by the following set of equations: where f denotes the next-state function, g is the function that produces the keystream zi, and h is the output function which generates the ciphertext ci by combining the keystream and the message stream mi. The initial state is σ0 and can possibly be derived from the key k. Figure 1 on the next page illustrates the encryption and decryption processes5.

A synchronous stream cipher is synchronized when the key and the internal state of the keystream generators at the sending and receiving site are identical. If a ciphertext character is lost, inserted, or deleted during transmission, decryption becomes impossible and the sender and receiver must resynchronize their generators before they can proceed further. Consequently, special resynchronization techniques have to be employed. Moreover, there are no propagation errors because the modification of one ciphertext character due to transmission errors does not effect the decryption of another ciphertext character.

5 The figures and the notations in this section are adopted from [MEN01].

(Eq. 2.1)

),(1 kf ii σσ =+

),( kgz ii σ=

),( iii mzhc =

(a)

(b)

(c)


One of the most important stream cipher is the additive synchronous stream cipher. Its

output function h implements a simple addition of the keystream character and the plaintext character. Most commonly, the plaintext, ciphertext and keystream characters are binary digits and the output function h is therefore the XOR-function. In this case encryption and decryption are the same. Because the method of combining plaintext and keystream characters is very simple, the employed keystream generators must be sufficiently strong.

2.1.4 Self-synchronous Stream Ciphers

In a self-synchronous stream cipher, each keystream character is produced as a function of the key and a fixed number n of proceeding ciphertext characters. The following equations describe the encryption process: where f denotes the next-state function, g is the function that produces the keystream zi, and h is the output function which generates the ciphertext ci by combining the keystream and the message stream mi. The initial state is σ0 and k is the key. The encryption and decryption processes are depicted in Figure 2 on the next page.

If a ciphertext character is lost, deleted, inserted, or altered during transmission, the error propagates forward for n characters because the decryption function depends only on a fixed number of preceding ciphertext characters. The cipher resynchronizes itself automatically and performs proper decryption after n correct ciphertext characters have been received. In contrast to synchronous stream ciphers, self-synchronous stream ciphers are non-periodic because each keystream character is functionally dependent on the preceding message stream.

Figure 1 Model of a synchronous stream cipher

(Eq. 2.2) ),( kgz ii σ=

),,...,,( 11 kcccf ininii +−−+ =σ

),( iii mzhc =

(a)

(b)

(c)

Encryption Decryption

iσ

zi ci

mi

Plaintext mi Ciphertext ci Key k Keystream zi

h

f

g k

Keystream generator

iσ

zi mi

ci

h-1

f

g k

Keystream generator

1+iσ 1+iσState iσ


2.2 Pseudorandom Sequences for Stream Ciphering

As motivated in the previous section, stream ciphers employ deterministically generated “random” sequences, i.e. pseudorandom sequences, to encrypt the message stream. Such a pseudorandom sequence is generally defined as a sequence that “appears” to be random. The objective in stream ciphering is to use a short, truly random sequence (the key) and expand it to a sequence of much larger length, which should be as statistically indistinguishable as possible from a truly random sequence [MEN01].

Since a keystream generator is a finite state machine the generated sequence is naturally periodic. If something is periodic, it is, by definition, predictable and therefore cannot be random with respect to the strict meaning of randomness [SCH96]. Thus, the randomness of periodic sequences − or finite sequences, if only one period is considered − has to be defined. It seems to be a difficult problem because every finite sequence is equally likely to occur or equally random if the probability of generating a single zero or one is assumed to be equal and each bit is independent of the previous bits. But there exist sequences that are more typical than others. For example, a sequence that has about the same number of ones and zeros is considered to be more “typical” than the all-zeros sequence, even though both sequences are equally likely. This typically-concept forms the basis of how randomness of a finite sequence is defined. Various statistical tests designed to detect specific randomness characteristics are described in [MEN01].

The important criterion of distribution properties follows intuitively from what is regarded

as “typical”. It states that a finite sequence of length T may be called “random” if every binary k-tuple for all k smaller then some upper bound (e.g. log2(T)) appears about equally often [RUE86]. The widely accepted “randomness postulates” of S. Golomb [GOL67] are based on this definition. To measure the randomness of periodic binary sequences the following requirements have been proposed:

Figure 2 Model of a self-synchronous stream cipher

Encryption Decryption

iσ

zi ci

mi

Plaintext mi Ciphertext ci Key k Keystream zi

h

f

g k

Keystream generator

iσ

zi mi

ci

h-1

f

g k

Keystream generator

1+iσ 1+iσ

• • • • • •

State iσ


(G1) The number of ones and zeros within one period of the sequence differs at most by one.

(G2) In every period, (1/2i) of the total number of runs (subsequences of the same bit) has length i, as long as there are at least 2 runs of length i.

(G3) The periodic autocorrelation function (ACF) is two-valued. The periodic ACF of a binary sequence is defined as follows [FUM94, p.115]:

where τ indicates a cyclic shift of the sequence and T is the length of the period. A(τ ) and D(τ ) denote the number of agreements and disagreements between the shifted and the original version of the sequence within one period.

Sequences satisfying (G1)-(G3) are called pseudo-noise sequences. In most practical cases, the rough agreement with these criteria is sufficient.

The first requirement (G1) is cryptographically relevant because, if there are many more ones than zeros in a binary sequence, then the sequence becomes more predictable because each bit could be guessed with a probability of greater than ½. Furthermore, bad pattern distributions may be used to accumulate statistics for an efficient attack. It is also known that uniform pattern distributions and good autocorrelation properties are closely related and that the periodic autocorrelation function reflects global randomness properties [CUS98]. These facts are captured with (G2) and (G3).

For many communications applications, such as radar systems, spread spectrum communication systems, multiple-terminal identification or code-division multiple access communication systems, sequences are sufficient that possess specific correlation properties and certain statistical characteristics. But meeting the above described statistical criteria is only necessary and not sufficient for cryptographic applications. Cryptographic randomness does not mean just statistical randomness. For a sequence to be cryptographically secure pseudorandom it must be unpredictable. It must be computationally infeasible to predict the next bit given complete knowledge of the algorithm or hardware generating the sequence and of all the previous bits of the sequence [SCH96]. The security of a stream cipher depends primarily on the property of unpredictability of the keystream. Starting point in stream cipher design and analysis is therefore the assessment of the security of keystream generators in terms of predictability. Particularly important is the linear unpredictability or linear complexity of a sequence, which is measured by the length of the shortest LFSR that is able to generate a given sequence. The linear complexity and the associated linear complexity profile are criteria that allow one to efficiently judge the unpredictability of pseudorandom sequences due to the Berlekamp-Massey algorithm (BM-algorithm) [MAS69]. Equivalent complexity measures based on FCSRs, namely the 2-adic complexity and the 2-adic complexity profile, may also be used. More details on these measures are provided in chapter §2.4 below. In this thesis, the previously discussed pattern distribution and autocorrelation properties as well as the complexity measures will be used to empirically and analytically evaluate the cryptographic strength of the investigated keystream sequences.

(Eq. 2.3) T

DAC )()()( τττ −=


2.3 Feedback Shift Registers

Linear feedback shift registers (LFSRs) are basic components in many keystream generators. Because of their structure, they can be fully analyzed using algebraic tools and they are well suited to hardware implementations. Moreover, the produced sequences may have large period and good statistical properties. Although LFSRs are not directly analyzed in this thesis, they are of theoretical interest and provide the basis for further investigations.

The analysis of feedback carry shift register (FCSR) sequences is quite different from that of LFSR-sequences. Instead of algebra over finite fields, algebra over the 2-adic numbers is employed. However, there are many parallel properties between LFSRs and FCSRs.

In subsection §2.3.1 a brief review of the main properties of LFSRs is given. The theory behind LFSRs is assumed to be basically known. Only selected results about LFSRs are summarized which are important for the remainder of the thesis. FCSRs are described in more detail in subsection §2.3.2. They are presented in the same way as LFSRs to emphasize the parallels between these two types of feedback shift registers. Unless otherwise stated the theoretical results are taken from [KLA97]. The theory of 2-adic numbers is introduced at the beginning of subsection §2.3.2.

2.3.1 Linear Feedback Shift Registers

2.3.1.1 Register Architecture

An LFSR consists of a series of cells with feedback connections on a subset of these cells. The architecture of an LFSR is depicted in Figure 3, where {an-1, an-2, … , an-r} ∈ {0,1} is the cell contents and the symbol ⊕ denotes addition modulo 2. The coefficients {q1, q2,…, qr} ∈ {0,1} represent the existence or nonexistence of a feedback tap. Since, the register has length r it is called an r-stage LFSR.

The shift register works as follows:

1. The register cells {an-1, an-2, …, an-r} are initialized.

2. The contents of the tapped register cells are added modulo 2:

Figure 3 A linear feedback shift register

(Eq. 2.4) )();2(mod1

rnaqar

iinin >= ∑

=−


3. The cell contents are shifted right by one position outputting the rightmost bit an-r.

4. The sum an is returned into the leftmost cell an-1 of the shift register.

Because the LFSR implements a linear recursion (see (Eq. 2.4)), the output sequence is also referred to as linear recurrence sequence.

2.3.1.2 Analysis of LFSRs

LFSRs are analyzed using arithmetic in finite fields. The basic algebraic structure is the ring GF(2)[[X]] of formal power series in X with coefficients in GF(2)6. Details about this mathematical notion can be found in [FUM94] and [RUE86].

The feedback taps {q1, q2,..., qr} of an r-stage LFSR correspond to a connection polynomial with qi ∈ GF(2). The LFSR is said to be non-singular if the degree of q(X) is r, otherwise it is singular. Many properties of LFSR-sequences may be described with this polynomial.

An infinite binary sequence (a)∞ = (a0, a1, a2, … ) may be represented by its generating function ∑∞

==

0)(

ii

i XaXA ∈ GF(2)[[X]]. The sequence (a)∞ is eventually periodic if and only if A(X) is equal to the quotient of two polynomials:

The denominator q(X) is the connection polynomial of an LFSR and the numerator r(X) corresponds to a specific initial loading that has to be nonzero. The sequence (a)∞ is strictly periodic if and only if the degree of r(X) is less than the degree of q(X) (deg(r(X)) < deg(q(X))) in which case the LFSR is non-singular. For a primitive7 connection polynomial the output sequence has maximum possible period Tmax = 2r-1 and is called m-sequence.

m-sequences have nice statistical properties. They are balanced and have the de Bruijn property, that is, every nonzero subsequence of length s occurs exactly once. Furthermore, the ACF of an m-sequence is two-valued. Therewith Golomb’s randomness postulates (G1) − (G3) (see §2.2) are satisfied so that every m-sequence is also a pseudo-noise sequence.

If the connection polynomial q(X) is irreducible8 over GF(2), then there is a convenient description of the ith term of the output sequence (a)∞ = (a0, a1, a2, … ) of the LFSR. Let denote the trace function which maps any element β of the extension field GF(2r) into the groundfield GF(2). Furthermore, let γ ∈ GF(2r) be a root of q(X), then the sequence (a)∞ is defined as follows: 6 GF(p) is the Galois field of order p or simply the finite field with p elements. p is prime or a prime power. 7 A primitive polynomial of degree n with coefficients over GF(q) is one that is irreducible and divides xN-1 for N = qn-1 but no smaller N. 8 A polynomial with coefficients in GF(p) is irreducible over GF(p) if it allows only trivial factorisation.

(Eq. 2.5)

(Eq. 2.6)

(Eq. 2.7)

1)( 11

1 −+++= −− qXqXqXq r

rr

r K

).(/)()( XqXrXA =

)1(22)(−

+++=r

rT ββββ K


K,2,1,0)( == iATa iri γ

where A ∈ GF(2r) corresponds to a certain initial loading of the shift register. This trace description is particularly suited for the analysis of nonlinear combinations of LFSRs.

2.3.2 Feedback Carry Shift Registers

2.3.2.1 Mathematical Foundations

The analysis of FCSR-sequences is based on the arithmetic in the 2-adic numbers. The following subsection briefly introduces this mathematical tool. For a more comprehensive treatment of the theory see for example [CUS98], [GOU97], or [KOB77].

Let p be a fixed prime number, then any x ∈ Z (Z denotes the integers) can be written as an expansion in “base p” in the form:

with coefficients ai ∈ {0,1, …, p-1}. This representation is also referred to as p-adic expansion. For example, the 2-adic expansion of x = 35 is 1⋅25 + 0⋅24 + 0⋅23 + 0⋅22 + 1⋅21 + 0⋅20, in short 1000112. Generalizing equation (Eq. 2.9) to x ∈ Q (Q denotes the rationals) results in the following sum: In this formulation, the integers are those numbers where ai = 0 for all i < 0. As an alternative, if one extends the p-adic expansions by allowing infinite sums of the form where k is some (possibly negative) integer, we obtain the field Qp of p-adic numbers. Those p-adic numbers with ai = 0 for all i < 0 are also called p-adic integers (Zp) [WIK03].

Based on that, a 2-adic integer is defined as follows:

Definition 2.1 A 2-adic integer is a formal power series

with ai ∈ {0,1}.

The ring of all such power series is the ring Z2 of 2-adic integers. There is a one-to-one correspondence between rational numbers α = p/q (q odd) and 2-adic integers given by the 2-adic expansion of α [KLA97]. That means every such rational number has a unique 2-adic expansion. This 2-adic expansion is an eventually periodic sequence (a)∞ of binary coefficients (a0, a1, a2, … ). Conversely, for every eventually periodic binary sequence (a)∞ the associated 2-adic integer α = ∑ai2i is the 2-adic expansion of a rational number [CUS98].

To expand a rational number α = p/q 2-adically, one has to expand both numerator p and denominator q in powers of 2 and then divide formally (similar to polynomial division) where

(Eq. 2.8)

(Eq. 2.9)

(Eq. 2.10)

(Eq. 2.11)

(Eq. 2.12)

∑=

±=n

iii pax

0

.∑−∞=

±=n

iii pax

∑∞

=

=ki

ii pax

∑∞

==

02

ii

iaα


2 is treated as an indeterminate. But one may have to “carry”. For example, the sum of two coefficients may be larger than 2. Then the overflow bits are carried to higher order terms [GOU97]. The following example illustrates this concept.

Example 2.1

Let 193

==qpα , then

01 2121 ⋅+⋅=p and 01234 2121202021 ⋅+⋅+⋅+⋅+⋅=q are the expansion of p and q in powers of 2. Dividing these two expressions as described above results in

K+++++++=++

+= 1211109640

014

01

2222222222

22qp .

The coefficient sequence of the 2-adic expansion is the eventually periodic binary sequence )1011000010100111101000()( =∞a with a prefix of 4 bits and a period length of 18.

If –q < p ≤ 0 (q odd), then the bit sequence for the 2-adic expansion of α = p/q is strictly periodic. If also p and q are relatively prime (gcd9(p,q) = 1), then α is a reduced rational number and the period is: where ordq(2) is the order10 of 2 modulo q.

An FCSR is exactly performing this 2-adic expansion of some rational number α = p/q (q odd), outputting the binary coefficient sequence. There exists a fast software-oriented algorithm as alternative to this hardware implementation. It can be summarized as follows [CUS98, p. 313]:

begin: Input p and q. Conditions: q odd; q ≥ 1; gcd(p,q) = 1 repeat:

If |p| is even, then output 0 and set p ← p/2; otherwise output 1 and set p ← (p − q)/2. end

An example, demonstrating the algorithm is given below (Example 2.2).

Example 2.2

Suppose: 193

==qpα

1. |p| = |3| is odd: output: 1 p ← (p − q)/2 = (3 – 19)/2 = –8

2. |p| = |–8| is even: output: 0 p ← p/2 = (–8)/2 = –4

9 greatest common divisor 10 The order of 2 modulo q, denoted ordq(2), is the smallest positive integer x such that 2x≡1 (mod q).

(Eq. 2.13) )2(qordT =


3. |p| = |–4| is even: output: 0 p ← p/2 = (–4)/2 = –2 M

Continuing the procedure yields the sequence already determined in Example 2.1.

In this thesis, the simulation-based investigation of FCSR-sequences has been carried out using the above presented algorithm.

The arithmetic in the ring of 2-adic integers (Z2) is defined by the following operations [CUS98, p. 316]. Suppose that α und β are two 2-adic integers with

where ai, bi ∈ {0,1}, then the addition α + β is defined by the series where each ri is computed by ( ⎣ ⎦ denotes the integer part) where the ci’s are carry bits and c-1 is defined to be 0. The next example demonstrates these calculations.

Example 2.3

Let ∑∞

=

===0

251

i

iia

qp

α

αα with )01101()( =∞a

and ∑∞

=

===0

294

i

iib

qp

β

ββ with )001110001()( =∞b then α + β is the result of

the following calculation:

i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 … ai 1 0 1 1 0 0 1 1 0 0 1 1 0 0 1 … bi 0 0 1 0 0 1 1 1 0 0 0 1 1 1 0 … ci 0 0 1 1 0 0 1 1 0 0 0 1 1 1 1 … ri 1 0 0 0 1 1 0 1 1 0 1 0 0 0 0 …

→ ∑∞

=

=+0

2i

iirβα with )0000011011011()( =∞r . This 2-adic sum of α and β is

(of course) identical to the 2-adic expansion of the rational number =+ βα

4529

94

51

=+=+

=+βα

αββα

β

β

α

α

qqqpqp

qp

qp

.

The subtraction α − β is defined to be α + (–β) where (–β) is the additive inverse of β. If β is the complementary 2-adic integer of β, formed by taking the complement of each bit (replace 0 by 1 and 1 by 0), then − β is given by [GOR97]:

(Eq. 2.14)

(Eq. 2.15)

(Eq. 2.16)

(Eq. 2.17)

∑∑∞

=

∞

=

==00

2,2i

ii

i

ii ba βα

∑ ∑∞

=

∞

=

=+=+0 0

22)(i i

ii

iii rbaβα

2mod)( 1−++= iiii cbar⎣ ⎦2/)( 1−++= iiii cbac

.1+=− ββ


The multiplication of two 2-adic integers α and β (same notation as in (Eq. 2.14)) is defined by the equation [CUS98, p. 317]

where

Because the ui’s could be larger then 2, the same reduction procedure as before has to be applied to obtain where each ri ∈ {0,1} is calculated by where the ci’s are carry bits and c-1 is defined to be 0. With the subsequent example, these operations are made explicit.

Example 2.4 Let α and β be the same as in Example 2.3, then α ⋅ β is determined as follows:

i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 … ai 1 0 1 1 0 0 1 1 0 0 1 1 0 0 1 … bi 0 0 1 0 0 1 1 1 0 0 0 1 1 1 0 … ui 0 0 1 0 1 2 1 2 3 3 1 2 4 5 3 … ci 0 0 0 0 0 1 1 1 2 2 1 1 2 3 3 … ri 0 0 1 0 1 0 0 1 0 1 1 1 1 1 0 …

→ ∑∞

=

=0

2i

iirαβ with )100100101111001()( =∞r . This 2-adic product of α and

β is (of course) equal to the 2-adic expansion of the rational number =⋅ βα

454

94

51

=⋅==⋅βα

βα

β

β

α

α

qqpp

qp

qp

.

Clearly, division of two 2-adic numbers is defined to be α/β = αβ−1 where β−1 denotes the multiplicative inverse of β.

The above described operations 2-adic sum and 2-adic product of two binary sequences are a natural consequence of the one-to-one correspondence between the set of binary, eventually periodic sequences and the set of 2-adic integers (or rational numbers α = p/q with q odd). These operations may be quite useful in constructing sequences for a variety of applications, especially for keystream generators as will be discussed later in this thesis.

(Eq. 2.18)

(Eq. 2.19)

(Eq. 2.20)

(Eq. 2.21)

∑∞

=

=0

2i

iiuαβ

.∑=+

=ijk

jki bau

2mod)( 1−+= iii cur

⎣ ⎦2/)( 1−+= iii cuc

∑∞

=

=0

2i

iirαβ


2.3.2.2 Register Architecture

FCSRs can be thought of as LFSRs with ordinary addition in place of addition modulo 2 and auxiliary memory for storing the carry. The architecture of an FCSR is depicted in Figure 4, where {an-1, an-2, … , an-r} ∈ {0,1} is the cell contents, mn-1 is the current contents of the memory, and the symbol ∑ denotes integer addition. Notice that the memory contains a nonnegative integer. The coefficients {q1, q2, … , qr} ∈ {0,1} represent the existence or nonexistence of a feedback tap. Since, the register has length r it is called an r-stage FCSRs.

The shift register works as follows:

1. The register cells {an-1, an-2, … , an-r} and the memory mn-1 are initialized.

2. The contents of the tapped register cells are added as integers to the current contents of the memory:

3. The cell contents are shifted right by one position, outputting the rightmost bit an-r.

4. The parity bit an of nσ is returned into the leftmost cell an-1 of the shift register: 5. The higher order bits of nσ are retained for the new value of the memory:

where ⎣ ⎦ denotes the integer or floor part. Alternative architectures and hardware implementations of FCSRs are proposed in [KLA97] and [GOR02].

Figure 4 A feedback carry shift register

(Eq. 2.22)

(Eq. 2.23)

(Eq. 2.24)

.1

1∑=

−− +=r

ininin maqσ

).2(modnna σ=

⎣ ⎦.2/2/)( nnnn am σσ =−=


2.3.2.3 Analysis and Synthesis of FCSRs

As already mentioned in §2.3.2.1, the ring of 2-adic integers (Z2) and the arithmetic over this ring is required to analyze FCSRs and its output sequences. In this subsection, the basic properties of FCSRs are presented in terms of the theory derived in §2.3.2.1.

The feedback taps {q1, q2,…, qr} of an r-stage FCSR correspond to the binary expansion of an integer q:

with qi ∈ {0,1} and qr = 1. (Notice that q0 = −1 does not correspond to a feedback tap.) The integer q is referred to as the connection integer because the above binary expansion gives the analog to the connection polynomial in the usual theory of LFSRs. Many properties of FCSR- sequences may be described with this integer. The length r of an FCSR is related to the connection integer by the following equation:

As described in §2.3.2.1, an infinite binary sequence (a)∞ = (a0, a1, a2, …) may be represented by the formal power series ∑∞

==

02

ii

iaα ∈ Z2. The sequence (a)∞ is eventually

periodic if and only if α is equal to the quotient of two integers p and q (q odd). In this case, the sequence is identical to the output of an FCSR that computes the coefficient sequence of the 2-adic expansion of that rational number p/q. The denominator q (q > 0 is assumed without loss of generality) is the connection integer of the FCSR and generates the periodic part of (a)∞. The numerator p corresponds to a specific register initialization with where the qj’s are the feedback taps, {ar-1, ar-2, …, a1, a0} ∈ {0,1} are the initial loadings of the register cells and mr-1 ∈ Z is the initial memory value.

The sequence (a)∞ is strictly periodic if and only if |p| < |q| and α < 0, i.e. if –q < p ≤ 0. If also p and q are relatively prime (gcd(p,q) = 1), then the period is T = ordq(2) (see (Eq. 2.13)). In case p and q have a common factor, then the period T is a divisor of ordq(2). If p ≥ 0 or p ≤ –q then the sequence has a transient prefix before it drops into a periodic state. If p is a multiple of q, then α corresponds to a usual integer. In this case, after a transient prefix the output consists of all 0’s or all 1’s depending on whether p is positive or negative. This is due to (Eq. 2.17) and due to the fact, that the 2-adic expansion of a positive integer is actually its expansion in base 2, which is a finite series.

The maximum possible period for an FCSR with connection integer q is achieved if and only if q is prime and 2 is a primitive root11 modulo q. With (Eq. 2.13) the maximum period is 11 An integer N is a primitive root modulo q (q prime) if it has maximum possible order modulo q, i.e. if NT≡1(mod q) for T = q-1 but no smaller T.

(Eq. 2.25)

(Eq. 2.26)

(Eq. 2.27)

(Eq. 2.28)

⎣ ⎦ . )1(log 2 += qr

1222 11

1 −+++= −− qqqq r

rr

r K

20

2 Zqpa

i

ii ∈== ∑

∞

=

α

∑∑−

= =−− −=

1

0 01 22

r

i

i

j

rr

ijij maqp


Sequences generated by this type of FCSR are called l-sequences to stress the analogy to m-sequences. They have nice properties that are discussed in §2.3.2.4 below.

The requirements for the additional memory of an r-stage FCSR depend on its feedback connections. At most, bits of memory are necessary. If an FCSR is in a periodic state, then the memory value lies in the range 0 ≤ m < ω , where ω = ωt(q+1) is the Hamming weight of q + 1, i.e. the number of nonzero feedback taps. In this case, no more than bits of memory are required. In general, memory values outside the range 0 ≤ m < ω are also possible. If the initial memory value is mr-1 ≥ ω, then it will monotonically decrease and will drop into the range 0 ≤ m < ω within steps. If the initial memory is mr-1 < 0, then it will monotonically increase and will arrive in the range 0 ≤ m < ω within steps, where ⎡ ⎤ denotes the next greater integer.

It has already been discussed that an FCSR outputs all 1’s or 0’s if the rational number α = p/q corresponding to the output sequence is a usual integer, i.e. if p is a multiple of q. In this case, the associated initial loading, which is specified by (Eq. 2.28), is said to be degenerated. From a cryptographic point of view, degenerated initial loadings are critical because they constitute a set of weak keys.

Almost always, strictly periodic sequences are desired. In order to guarantee a strictly periodic output the following initial loadings may be used:

• m = 1 and all the aj = 0, → p = −2r

• m = 1, a0 = 1, and all the other aj = 0, → p = q − 2r+1

• m = 0, ar-1 = 1, and all the other aj = 0, → p = − 2r-1.

If the initial loading and the initial memory of an FCSR for a given rational number α = p/q (q an odd positive integer) are to be determined, one has to solve (Eq. 2.28), which may be accomplished by the subsequent procedure (The same notation as in (Eq. 2.25) and (Eq. 2.26) is assumed.):

1. Compute {a0, a1, … , ar-1} by the software algorithm for the 2-adic expansion described in §2.3.2.1.

2. Compute ∑ ∑−

= = −=1

0 02r

i

i

ji

jij aqy .

3. Compute m = (y − p) / 2r.

(Eq. 2.29)

(Eq. 2.30)

(Eq. 2.31)

(Eq. 2.32)

(Eq. 2.33)

.1max −= qT

⎣ ⎦ ⎣ ⎦⎣ ⎦))1(log(log)(log 222 += qr

⎣ ⎦ 1)1(log2 +−ω

⎣ ⎦ rmr +−− )(log 12 ω

⎡ ⎤ rmr +− |)(|log 12


An FCSR with these parameters and q as connection integer will output the 2-adic expansion of p/q. If the given rational number α = p/q is not in lowest terms, by reduction a shorter FCSR can be found that produces the same sequence.

Similar to the trace representation of periodic LFSR sequences there exists an exponential representation for periodic sequences of bits obtained from FCSRs. Let (a)∞ = (a0, a1, a2, … ) be a periodic sequence generated by an FCSR and γ = 2−1 ∈ Z/(q) be the multiplicative inverse of 2 in the ring Z/(q) of integers modulo q. Then (a)∞ is defined by

where A ∈ Z/(q) corresponds to a specific initial loading. The notation (mod q)(mod 2) means that Aγi is reduced modulo q and the result of this reduction is reduced modulo 2 to obtain an element of GF(2). The introduced exponential representation plays an important role in the analysis of FCSR-sequences.

With a final numerical example the previously presented theory of FCSRs is illustrated:

Example 2.5 Suppose an FCSR with connection integer q = 19.

− With (Eq. 2.26) it follows that the register has r = 4 stages.

− Since q = 24 + 22 − 1 there are feedback connections on the second and fourth cell (compare to (Eq. 2.25) and Figure 4).

− At most 2 bits of extra memory are required (see (Eq. 2.30)). If the FCSR is in a periodic state, then only 1 memory bit is necessary (see (Eq. 2.31)).

− Because 2 is a primitive root modulo 19 the FCSR outputs a strictly periodic l-sequence with period T = 18 (see (Eq. 2.29)). This is true for any initial loading that corresponds to an integer p with –19 < p ≤ 0. For all the other non-degenerated initial loadings the periodic part of the sequence will have a finite prefix. The sequence in Example 2.1 is an instance for p = 3.

− For an initial memory of m = 0 and an initial cell loading of {a0 = 1, a1 = 0, a2 = 1, a3 = 0} the associated integer is p = –1 (see (Eq. 2.28). This initial loading is obtained by the procedure given on the previous page.

− Using the initial load for p = −1 the output sequence is given by (Eq. 2.34) with γ = 2−1 = 10 (Note: 2⋅10 ≡ 1 (mod 19), hence 2−1 = 10 ∈ Z/(19)) and A = 1 for i = 0, 1, 2, … . Equivalently, the equations (Eq. 2.22) through (Eq. 2.24) may be used to determine the output of the FCSR. In Table 1 the resulting sequence is shown. The contents of the four register cells, the output bit, and the value of the memory (m) are listed for every index i. Each state of the shift register corresponds to a rational number αi = pi/19. The nominator pi is related to the second column of the table by pi = −Aγi.

(Eq. 2.34) K,2,1,0)2)(mod(mod == iqAa ii γ


i Aγi register output (ai) m 0 1 0101 1 0 1 10 0010 0 1 2 5 1001 1 0 3 12 1100 0 0 4 6 1110 0 0 5 3 1111 1 0 6 11 0111 1 1 7 15 1011 1 1 8 17 0101 1 1 9 18 1010 0 1

10 9 1101 1 0 11 14 0110 0 1 12 7 0011 1 1 13 13 0001 1 1 14 16 0000 0 1 15 8 1000 0 0 16 4 0100 0 0 17 2 1010 0 0

Table 1 The states of an FCSR with q = 19

2.3.2.4 Properties of l-sequences

In the previous subsection l-sequences have been introduced as FCSR-sequences with maximum possible period Tmax = q − 1, where q is the connection integer of the FCSR. This period is achieved for any non-degenerated initial loading if and only if q is prime and 2 is primitive root modulo q. However, depending on the initialization there may be a transient prefix before the register drops into the big periodic state (see §2.3.2.3).

Primes having 2 as primitive root are called 2-primes. About 37.4% of all primes are 2-primes which means an infinite number of them do exist. There are efficient techniques for finding large 2-primes [COH93] which is a necessary condition for practical applications. A list of 2-primes with an associated register length of up to r = 8 is given in appendix A.1. For these primes 2 is also a primitive root of any of their powers. Another list with all 2-primes q < 10000 is provided in [SCH96].

An l-sequence is a shift of the bitwise complement of a 1/q-sequence. A 1/q-sequence is

the binary expansion of the fraction 1/q

and has the following properties:

1. The number of 0’s and the number of 1’s in one period is equal.

2. The second half of the period is the bitwise complement of the first half of the period.

3. In any given period of the sequence, every string of length ⎣ ⎦)(log2 q occurs at least once and every binary string of length ⎣ ⎦ 1)(log2 +q occurs at most once. This is called the generalized de Brujin property.

(Eq. 2.35) K+++= −−− 32

21

10 222/1 bbbq


The second property has been found in this thesis through simulation and was proven in [GOR97]. For cryptographic applications this property is undesirable because only half of the period is sufficient to specify the whole sequence.

The ACF of an l-sequence is in general difficult to determine. However, some evaluations have been carried out that are discussed in the next chapter (§3.2.2).

Based on the arithmetic in the 2-adic integers there is an analog to the usual ACF called arithmetic autocorrelation function (AACF). It is defined as follows. If α = ∑an2n and α[i] = ∑an2n+i = 2iα represent the 2-adic integers corresponding to a sequence (a)∞ and its shift by i positions, then the AACF Ri((a)∞) is the number of 1’s minus the number of 0’s in any period of the eventually periodic bit sequence of the 2-adic sum α + α[i]. An l-sequence has the ideal autocorrelation property with respect to this function, i.e. Ri((a)∞) is two-valued.

The arithmetic crosscorrelation function (ACCF) is the equivalent analog to the usual crosscorrelation (CCF). It is possible to construct large families of sequences with ideal ACCF using d-fold decimations of l-sequences. This fact possibly makes l-sequences suitable for several practical applications, such as spread-spectrum communication systems, radar systems, signal synchronization, signal identification, or cryptanalysis. Details about the concept of arithmetic correlations of FCSR-sequences are provided in [KLA95] and [GOR97].

Long pseudorandom sequences can also be obtained by FCSRs with nonprime connection integer. If the connection integer q is a power of a prime such that q = pe with p prime, p > 2, e ≥ 2, and 2 primitive root modulo q, then the period of the output sequence is

FCSR-sequences of this type are also referred to as l-sequences. Their properties are almost identical to those of l-sequences with prime connection integer. The difference is that they are only close to have the generalized de Brujin property, that is, the number of occurrences of any two substrings of length log2(T) (T period) within a period differs by at most 2.

Although l-sequences are not satisfying all of the randomness postulates introduced by S. Golomb (see §2.2) they have good statistical properties, which are parallel to those of m-sequences. In addition, they may also have large periods, which is a necessary requirement for keystream sequences. Finally, it should be noted that the presented results of this section (§2.3.2) apply to binary FCSR-sequences. For non-binary FCSR-sequences the theory of p-adic instead of 2-adic numbers has to be employed. This register type and variations with multiple carry registers are introduced in [KLA95a], [KLA97], and [GOR02].

2.4 Complexity Measures

It has already been stated in §2.2 that for a keystream generator to be secure it must be unpredictable. Complexity measures are mathematical tools for evaluating the unpredictability and therewith the security level offered by a keystream with respect to some computational model or machine. They are cryptographically important only if there are efficient algorithms for determining the parameters of the underlying model. Some

(Eq. 2.36) ).1(1 −= − ppT e


computable complexity measures are discussed in [NIE98]. The most important standard measure is the linear complexity where the underlying machine is that of an LFSR. It had long been the only general-purpose tool until the FCSRs were discovered. This type of feedback shift register provides a straightforward analog to the linear complexity, called the 2-adic complexity, where LFSRs are replaced by FCSRs. The next two subsections are devoted to the linear complexity and the 2-adic complexity, respectively. The corresponding synthesis algorithms, namely the Berlekamp-Massey algorithm (BM-algorithm) and the rational-approximation algorithm (RA-algorithm), are also discussed.

2.4.1 Linear Complexity

The linear complexity (or linear span) L of an eventually periodic binary sequence is the length of the shortest LFSR that is able to reproduce this sequence [RUE86]. The linear complexity is cryptographically significant due to the BM-algorithm [MAS69].

The BM-algorithm is an efficient procedure for determining the linear complexity and the corresponding LFSR of a given sequence. It is an optimal algorithm since, for a sequence with linear complexity L only a minimum of 2L consecutive bits is required to construct the shortest possible LFSR. A detailed study of the algorithm is provided in [FUM94]. In appendix A.2 a pseudocode version is given that was adopted from [FUM94].

Due to the efficient BM-algorithm, it is a necessary condition for a keystream to have large

linear complexity. Since, truly random sequences have large linear complexity, this measure can also be regarded as randomness criteria. However, a large linear complexity is not sufficient to guarantee randomness or unpredictability of a keystream. For example, the periodically repeated sequence (0…01)∞ consisting of a zero string and a single 1 at the end, has maximum linear complexity that is equal to the length of the period. Only the circulating shift register is able to produce the sequence. But obviously the sequence is almost completely predicted by the allzero sequence and has bad distributional properties and is therefore cryptographically useless. Conversely, good statistical properties do not imply a large linear complexity. For example, m-sequences with excellent pattern distributions have minimum linear complexity with respect to their period length.

The previous examples clearly indicate the weaknesses of the linear complexity as metric

for the evaluation of keystreams. A further enhancement is the notion of the linear complexity profile. It is defined as follows: If Li denotes the linear complexity of a subsequence consisting of the first i terms of a given sequence, then the series L1, L2, L3, … is called linear complexity profile [RUE86]. It can be calculated by recording the intermediate results of the BM-algorithm.

Typical random sequences are shown to have a typical linear complexity profile. In Figure 5 such a profile is shown for a periodically repeated truly random sequence with period T. The linear complexity approximately increases by n/2, where n denotes the number of processed bits. As a result, one expects the linear complexity profile of a “typical” random sequence to closely follow the n/2 line. Two “untypical” examples are also shown in Figure 5, where the linear complexity profile of an m-sequence (T = 2r – 1) and of the sequence (0…01)∞ are depicted. Both curves clearly indicate that the sequences are not satisfying this randomness criterion.

As is the case with all statistical tests for randomness, the condition that a sequence has a linear complexity profile that closely follows that of a random sequence is only necessary but not sufficient for a sequence to be considered random. For instance, linear complexity profile


of the sequence (a)∞ = (a0, a1, … ) with ai = 1 for i = 2j – 1 (j = 0, 1, 2, … ) and ai = 0 otherwise, follows the line n/2 as close as possible but is obviously non-random.

Various theoretical results about the linear complexity and the linear complexity profile can be found in [RUE86] and [FUM94]. In this thesis, these metrics are regarded as primary criteria to judge the randomness of the keystreams and the BM-algorithm is therefore the primary empirical evaluation tool.

2.4.2 2-adic Complexity

In the previous subsection, the linear complexity or linear span was defined to be the length of the shortest LFSR that outputs a given sequence. Since FCSRs require extra memory for the carry, the definition of an equivalent measure is more complex. In case of a strictly periodic sequence, the extra memory is small and could be ignored but an eventually periodic sequence may require a significant amount of memory. This motivates a separate definition of the 2-adic span and the 2-adic complexity (see [KLA97]).

Suppose (a)∞ = (a0, a1, … ) is an eventually periodic sequence and q = qr2r + … + q121 – 1 is the connection integer of an r-stage FCSR with initial memory m that outputs this sequence. Then the 2-adic span of (a)∞ is the number

(ωt(q+1) is the Hamming weight of q + 1) which corresponds to the smallest FCSR whose output is the sequence (a)∞. In other words, the 2-adic span is the number of bits in the basic register plus the number of memory bits needed. Note, that the last “+1” is a sign bit to allow negative memory values.

If ∑∞

=∈==

0/2

ii

i qpaα Z2 is a reduced rational number whose 2-adic expansion

coincides with the sequence (a)∞, then the 2-adic complexity of the sequence (a)∞ is the real number

Figure 5 Linear complexity profiles

(Eq. 2.37) ⎣ ⎦ ⎣ ⎦ 1)1|)(|log,1))1((logmax())(( 222 +++++=∞ mqtra ωλ

T 2T

L

n

T

r

2r

m-sequence

(0…01)∞ sequence

truly random sequence

n/2 line

T = 2r−1: period


)),((log))(( 22 qpa Φ=∞φ where Φ(p,q) = max(|p|,|q|). If (a)∞ is strictly periodic, then the number of cells in the basic register is ⎡ ⎤2φ which means that this measure is the analog to the linear complexity. However, from an engineering perspective the 2-adic span is the more useful number.

The relation between these two measures is given by

meaning that their difference is at most log2(φ2).

An interesting result about the 2-adic span of a sequence is the following: If T is the period of a strictly periodic sequence, then the 2-adic span of this sequence is at least log2(r + 1) + 1, where r is the smallest prime divisor of 2T – 1. In the special case where the period is T = 2N–1 with 2T – 1 being prime, the 2-adic span is T + 2. This implies that there exist m-sequences with maximal 2-adic span. More results about these metrics can be found in [KLA97].

A similar notion to the linear complexity profile is the 2-adic complexity profile, which

measures the 2-adic complexity of a sequence as it gets longer and longer. It may be calculated using the rational approximation algorithm (RA-algorithm) that is presented in the next paragraph.

The RA-algorithm is an analog to the BM-algorithm and optimally constructs the smallest

FCSR which generates a given sequence. The algorithm is adaptive because each time a new bit is processed, the previously determined FCSR is updated. It requires only the first 2λ2 + 2log2(λ2) bits, where λ2 is the 2-adic span of the sequence. The algorithm is based on the p-adic approximation theory and basically determines the smallest fraction p/q that is associated to the analyzed sequence. A detailed description of the algorithm is given in [KLA97] and in appendix A.3 a pseudocode version is presented.

Due to the RA-algorithm the 2-adic complexity becomes cryptographically relevant and

binary sequences are required to have large 2-adic complexity to be computationally unpredictable. Furthermore, a random sequence will typically have a 2-adic complexity profile that grows with n/2 where n denotes the number of processed bits. With these measures two additional randomness criteria have been introduced. In this thesis they have been used only very limited. Although the RA-algorithm was implemented as evaluation tool, only short sequences could be studied. This is why the algorithm relies on exponentiations with exponents that are proportional to the length of the sequence. Thus, for the analysis of longer sequences special computer arithmetic has to be employed which may be accomplished using [WEL98]. Because such an implementation is beyond the scope of the thesis, this approach has not been further pursued. However, the following example shows the results of some initial 2-adic complexity analysis of m-sequences.

Example 2.6 The sequence (a)∞ = (0010111)∞ which is generated by a 3-stage LFSR with primitive connection polynomial q(X) = X3 + X – 1 and initial loading {a0 = 0, a1 = 0, a2 = 1} is considered.

− The results of the RA-algorithm for each processed bit are listed in Table 2.

(Eq. 2.38)

(Eq. 2.39) )))(((log))(()2))((( 2222∞∞∞ ≤−− aaa φφλ


The index n of the current input bit (an) is recorded as the first column. The column (p,q)n indicates the calculated rational number p/q whose 2-adic expansion coincides with the first n bits of (a)∞. The initial memory value of the associated FCSR is m and λ2(n) is the 2-adic span of each processing step.

n input (an) (p,q)n m λ2(n) 0 0 (0,0) 0 01 0 (0,0) 0 02 1 (4,1) -2 43 0 (4,1) -2 44 1 (-4,3) 1 45 1 (-4,11) 0 66 1 (-4,11) 0 67 0 (-4,11) 0 68 0 (-36,35) 1 89 1 (-28,13) 3 6

10 0 (-28,13) 3 611 1 (-60,101) 1 1012 1 (-116,127) 0 913 1 (-116,127) 0 9M M M M M

Table 2 Rational approximation results

− The algorithm converges after 13 input bits and finally outputs the rational number –116/127 which corresponds to a 7-stage FCSR with initial memory m = 0 and an initial loading equal to a complete period of (a)∞. The register has two additional memory bits, one for the carry and one sign bit. The sequence (a)∞ has therewith a 2-adic span of λ2 = 9. This is the maximum possible value for a strictly periodic sequence with a period of T = 7 which means only the circulating FCSR of length 7 can generate the sequence (a)∞.

− Knowing a complete period of a strictly periodic sequence the equation

can be used to determine the rational number p/q whose 2-adic expansion coincides with the sequence. If this fraction cannot be reduced to lower terms, it corresponds to the circulating shift register with an initial load equal to a complete period of the sequence. In the presented case one obtains with (Eq. 2.40): α = −(22 + 24 + 25 + 26)/(27 – 1) = –116/127, which is the same result as calculated with the RA-algorithm.

− The 2-adic span could also be determined with the theorem on the previous page about m-sequences with maximum 2-adic span. Since, the period of (a)∞ is T = 23 – 1 and 2T – 1 = 127 is prime the 2-adic span is λ2 = T + 2 = 9 which is consistent with the computed result.

− Figure 6 shows the 2-adic span profile (λ2(n)) and the 2-adic complexity profile (φ2(n)) of the sequence (a)∞. While the 2-adic span profile is quite fluctuating the 2-adic complexity profile closely follows the n/2-line and thus indicates good randomness properties of (a)∞.

Figure 6 2-adic span and complexity profiles

(Eq. 2.40)

0

2

4

6

8

10

1 3 5 7 9 11 13 15 17 19

λ/φ

n

λ2(n) n/2 line

φ2(n)

1221

0

−−= ∑ −

=T

T

ii

iaα


2.5 Keystream Generators Based on LFSRs

Since LFSRs are well suited to hardware implementations and produce pseudorandom sequences having large periods and good statistical properties, they are very attractive in stream cipher design. However, their output sequences are also highly predictable due to the efficient BM-algorithm, which requires only 2L bits where L is the length of the generating register. Consequently, LFSRs should never be used itself as keystream generators. The purpose of this section is to describe, how LFSRs are used as building blocks in keystream generators. The intent is to provide the basis for the construction and analysis of FCSR-based generators, which is the main focus of this thesis.

2.5.1 Classification

Designing secure keystream generators requires the introduction of nonlinear transformations, which may be accomplished in two basic ways [RUE86]. The first method is to use nonlinear feedback in the register but there is no well-developed mathematical theory to analyze this kind of generator. The second method is to use a nonlinear feedforward transformation on the register output. Because adequate mathematical tools allow the analysis of such generators, this is the standard way in constructing LFSR-based keystream generators.

There are principally three classes of nonlinaer output mappings: using a nonlinear function to combine the output of several LFSRs, using a nonlinear filtering function to combine different stages of the same LFSR, and using the output of one (or more) LFSRs to control the clock of one (or more) LFSRs. Even if these transformations are quite different, they all should satisfy the following requirements [RUE86]:

• The generated keystream should possess the same good statistical properties as the driving sequences.

• The period of the keystream should be maximized with respect to the single periods of the driving sequences.

• The linear (and 2-adic) complexity of the keystream should be maximized with respect to the linear (and 2-adic) complexities of the driving sequences.

• The transformation should be constructed so that there is no statistical dependence between any small subset of the driving sequences and the keystream, which can be used for modularizing attacks against the modules of the driving system.

• The transformation should be easy to implement.

Like all requirements for keystream generators these are only necessary but not sufficient conditions for cryptographically useful pseudorandom generators. Since the security of such generators is not mathematically provable the best one can hope for is to find computationally secure generators.

Generators, which generate the keystream as a nonlinear function f of the output of several LFSRs, are called nonlinear combining generators (see Figure 7).


The combining function f is a Boolean function that can be expressed in the so called

algebraic normal form. The algebraic normal form is a sum of products of binary variables where addition and multiplication are defined over GF(2). Note that these arithmetic operations correspond to the XOR- and the AND-function in switching theory, respectively. A product of m variables is called an mth-order product and the order of the function f is defined as the maximum of the orders of its product terms [RUE86]. For example, the function f(x1,x2,x3,x4) = x1x2x3 + x1x4 + x3 has order 3 and is the sum of a 1st-, 2nd-, and 3rd-order product. The order of f is the determining factor for the linear complexity of the output sequence in the way that high nonlinear order of f causes high linear complexity of the output sequence. A main result about nonlinear combining generators is the following [FUM94, p 155].

Suppose n LFSRs with primitive connection polynomial, whose lengths L1, L2, …, Ln are pairwise distinct, are combined by a nonlinear function f(x1,x2,…,xn), where f is in algebraic normal form. Then the linear complexity of the keystream is

where f is evaluated over the integers. More results about nonlinear combining generators, in particular with LFSRs having nonprimitive connection polynomials, can be found in [FUM94] and [RUE86].

Unfortunately, there is a tradeoff between the nonlinear order of f and the number of driving sequences of which the keystream is statistically independent. A Boolean combining function f(x1,x2,…,xn) is called mth-order correlation immune if the keystream is statistically independent of any subset of m driving sequences. If the function f(x1,x2,…,xn) with n random variables is m-th order correlation immune, then the nonlinear order is at most n – m. This tradoff between high nonlinear order (and therewith high linear complexity of the output sequence) and high correlation immunity can be avoided by introducing memory into the combining function. An example for this type of generator is the summation combiner which is discussed in [RUE86] where also more details about constructing correlation immune combining generators are provided. The summation combiner uses addition with carry and has high period, linear complexity and correlation immunity. However, it has low 2-adic span and may therefore be attacked with the RA-algorithm [KLA97].

A classical example of a nonlinear combining generator is the Geffe-generator [GEF73].

The Geffe-generator is discussed in more detail at the end of this section (see §2.5.2) because it is the basic nonlinear structure that is investigated in this thesis in conjunction with FCSRs.

If a nonlinear filtering function is used to combine different stages of the same LFSR, then the generator is called a nonlinear filter generator as depicted in Figure 8.

Figure 7 A nonlinear combining generator

(Eq. 2.41) ),...,,( 21 nLLLfL =

f

LFSR 1

LFSR 2

LFSR n

z

x1

x2

xn

• • •


If the stages of an LFSR of length L with primitive connection polynomial are filtered by

an mth-order filtering function, then the linear complexity of the keystream is upper-bounded by For LFSRs with primitive connection polynomial and large prime length, almost all filtering functions f produce keystreams that reach this maximum [RUE86]. But for suitable generators, the filtering function should include many terms of each order up to the maximum order.

Opposed to nonlinear combining generators and nonlinear filter generators where all component LFSRs are regularly clocked, in clock-controlled generators the LFSRs are clocked at different rates. Mostly, one LFSR controls the clock of another LFSR. The basic idea is to prevent attacks that assume regular clocking. Examples for clock-controlled generators are the alternating step generator or the shrinking generator [SCH96].

There is a great variety of generators having one of the presented structures to destroy the linearity properties of LFSRs. In [SCH96] many of them are introduced.

2.5.2 The Geffe-Generator

The Geffe-generator is composed of three LFSRs R1, R2, and R3 as depicted in Figure 9 [FUM94].

Figure 8 A nonlinear filter generator

(Eq. 2.42)

Figure 9 The Geffe-generator

• • •

• • •

⊕

f z

q1 qr

an-1 an-r

. 1

max ∑=

⎟⎟⎠

⎞⎜⎜⎝

⎛=

m

i iL

L

• • •

• • •

• • •

x1

x2

x3

f

z

R1

R2

R3


The corresponding Boolean function is where x1, x2, and x3 are the outputs of the LFSRs. The basic principle of this structure is that the second LFSR is switching between the first and the third LFSR. This structure yields a fairly balanced output sequence and overcomes therewith the drawback of the simple product function of bad bit pattern distributions.

If the LFSRs (primitive connection polynomial) have length L1, L2, and L3, respectively, that are pairwise distinct, then the linear complexity of the keystream z is Lz = L1L2 + L2L3 + L3 (see (Eq. 2.41)). The period of the generator is the least common multiple (lcm) of the periods of the three driving sequences. If the lengths of the LFSRs are pairwise relatively prime, then their periods are also relatively prime [RUE86, p. 93] and the period of the generated keystream is the product of the single periods which is maximum.

Although the generator has good statistical properties, large period, and large linear

complexity, it does not satisfy strict cryptographic requirements because it is only 1st-order correlation immune (see previous section §2.5.1). But correlation immunity is not the main concern of this thesis and the Geffe-generator is used as primary nonlinear structure.

(Eq. 2.43) 332213221321 )()(),,( xxxxxxxxxxxxf ++=∧∨∧=

3 Keystream Generators Based on FCSRs 31

3 Keystream Generators Based on FCSRs

As described in the previous chapter, FCSR-sequences may be efficiently generated and have nice pseudorandom properties which make them interesting for stream ciphering. However, they are also highly predictable due to the efficient RA-algorithm so that they cannot be used as keystream generators directly; they can only be used as components of keystream generators. This is exactly the same as LFSRs.

In [SCH96] numerous FCSR-based keystream generators are proposed that are either identical to well known LFSR generators or that use LFSRs and FSCRs in combination. In this chapter, generators employing the nonlinear Geffe-function (see §2.5.2) are investigated. Two different versions are studied: First, the usual Geffe-generator is modified in such a way that the LFSRs are replaced by FCSRs (§3.3). For constructing the second type of generator not only the registers but also the arithmetic operations are substituted (§3.4). The generator uses 2-adic addition and multiplication and is equivalent to an FCSR with a composed connection integer. But before studying these structures, some more properties of l-sequences produced by maximal-period FCSRs are presented (§3.2) and some technical issues concerning the generation and analysis of simulation data are discussed (§3.1).

3.1 Simulation

Most of the results given below are derived from simulation and numerical analysis. All necessary calculations were carried out using C/C++ and sometimes MATLAB programs. Source code modules have been developed to perform the following tasks (list contains only major modules):

• generation of FCSR-sequences (implementation of the software algorithm presented in §2.3.2.1)

• nonlinear combination of binary (FCSR-)sequences

• generation of parameter sets for systematically investigating specific nonlinear combining generators (e.g. determining all possible combinations of several FCSRs out of a given set)

• determination of sequence characteristics (e.g. period of a sequence; number of ones and zeros of a sequence; verification if sequence is maximal-period; verification if sequence’s first and second half of the period are complementary)

• calculation of the periodic ACF and CCF of a sequence

• calulation of the linear complexity, the linear complexity profile, and the connection polynomial of a sequence (The implementation of the BM-algorithm was adopted from [MEN01].)

These analysis tools output the results in file format so that they can be further evaluated and processed with other programs. Usually this has been accomplished with Microsoft Excel. The simulation results are than used as starting point to derive analytical coherences describing the observations. Some results are of complete analytical nature and could be mathematically proven by using for example 2-adic arithmetic.


3.2 Some more Properties of l-sequences

In subsection §2.3.2.4 some characteristics of maximal-period FCSR-sequences (l-sequences), such as period and pattern distributions, were discussed. The objective of this section is to provide some more results about l-sequences regarding their linear complexity and autocorrelation properties.


Crucial for the linear complexity analysis of maximal-period FCSR-sequences (l-sequences) is the property that the second half of the period is the bitwise complement of the first half (see §2.3.2.4). The condition for an FCSR to generate a periodic l-sequence is that the connection integer q has to be either a prime (q = p) or a power of a prime (q = pe), so that 2 is a primitive root modulo q (see §2.3.2.3 and §2.3.2.4). Such an l-sequence has the form (a)∞ = (u, ū, u, ū, … ), where u = (a0, a1, … ,aT /2 – 1), ū is the complement sequence of u, and T is the period of (a)∞ given by (Eq. 2.29) or (Eq. 2.36). Then an LFSR with a connection polynomial that divides can reproduce the sequence [SEO00]. Therefore, the linear complexity of an l-sequence is upper-bounded by Note that equation (Eq. 3.2) is true for all sequences having complementary period halves.

The numerical evaluation of l-sequences generated with a 2-prime connection integer has shown that the linear complexity is most of the time equal to the upper bound LUB or at least very close to that. For the analysis all sequences with 2-prime connection integer q < 10000 (see [SCH96, p.406-407]) have been evaluated using the BM-algorithm. The simulation results are listed in appendix A.4 and clearly indicate that the linear complexity of such sequences is well approximated by L ≈ (q+1)/2. In the very most cases (≈ 88%) this relation even gives the exact value. Equivalent results could be obtained for l-sequences where the connection integer is a prime power. Thus, a maximum-period FCSR has much better cryptographic properties with respect to the linear complexity compared to that of an LFSR. Since the underlying computational model of the linear complexity is that of an LFSR this result is not surprising.

Unfortunately, this empirical result about the linear complexity of l-sequences could not be proven in general. However, some analytical expressions for special 2-primes are derived and proven in [SEO00] which are briefly summarized in the following.

Suppose the connection integer of an FCSR has the form q = 2p + 1, where p is prime and

q is 2-prime, then the linear complexity of the corresponding l-sequence is at least ordp(2) + 2. If p is also 2-prime, then q is called a strong 2-prime and it follows that the linear complexity of the sequence is at least (p – 1) + 2. Since this lower bound is equal to the upper bound LUB (see (Eq. 3.2)) the linear complexity of FCSRs with strong 2-prime connection integer is L = (q + 1)/2. The simulation has shown that most 2-primes yield a linear complexity equal to the upper bound LUB. But there are only few strong 2-primes among all 2-primes12 so that one 12 In the list of 2-primes given in appendix A.1 only 11, 59, 107, and 347 are strong 2-primes.

(Eq. 3.1)

(Eq. 3.2)

1)( 22)2( −++= + XXXXq TT

.2)2( += TLUB


may assume there exists a much weaker condition to reach the maximum linear complexity. If the connection integer of an FCSR is q = re (e ≥ 2), where r = 2p + 1 is 2-prime and p is

prime, then the linear complexity L of the corresponding output sequence is lcm13[ordp(2) ; re–2(r – 1)] + 2. It follows, that if r is a strong 2-prime, then the linear complexity is lower-bounded by re–2⋅p⋅(p – 1) + 2.

In Figure 10 a representative example of the linear complexity profile of an l-sequence (q = 179) is given. All investigated sequences are shown to have associated such a “typical” linear complexity profile. The growth of the linear complexity closely follows the n/2-line which indicates that l-sequences possess good randomness properties with respect to this measure.

3.2.2 Autocorrelation Function

In general, it is quite difficult to determine the ACF of an l-sequence. There seem to be no adequate mathematical tools for a comprehensive analytical description. However, some important properties could be obtained by simulation.

Based on equation (Eq. 2.3) the periodic ACF has been computed for all sequences generated by FCSRs with 2-prime connection integer q ≤ 509 (see appendix A.1) and connection integers that are low powers (e ≤ 4) of that 2-primes. In Figure 11 the first period of a typical example (q = 67) is depicted. The following properties can be observed that are common to all evaluated sequences. For the remainder of this section only the first period of the ACF is considered, i.e. Cl(τ) with 0 ≤ τ ≤ T where T is the period of the sequence.

1. Cl(τ) is symmetric to τ = (q – 1)/2.

2. Cl(τ = (q – 1)/2) = –1

3. Cl(τ) with τ ∈ [0 ; (q – 1)/2] is point-symmetric to τ = (q – 1)/4. Equivalently, Cl(τ) with τ ∈ [(q – 1)/2 ; q – 1] is point-symmetric to τ = 3(q – 1)/4.

13 least common multiple

Figure 10 Linear complexity profil of an FCSR sequence with q = 179

0

20

40

60

80

100

1 21 41 61 81 101 121 141 161 181

L

n

T = q – 1 = 178

L = (q + 1)/2 = 90


4. Cl(τ = (q – 1)/4) = Cl(τ = 3(q – 1)/4) = 0 if (q – 1) is divisible by 4. If (q – 1) is not divisible by 4, then Cl(τ) ≠ 0 for all τ ∈ [0 ; (q – 1)].

5. |Cl(τ)| ≤ 1/3 for τ ∉ {0; (q – 1)/2; (q – 1)}

The first property is common to all periodic ACFs. Property 2 and 3 are due to the fact that for l-sequences the second half of the period is the bitwise complement of the first half. The last two properties are purely empirical observations but the large number of investigated sequences gives rise to the conjecture that these are also provable properties of all l-sequences.

Compared to m-sequences the ACF of l-sequences has some disadvantageous

characteristics. One major drawback is, for example, that its values can be as large as 1/3 for non-trivial shifts. But with respect to the arithmetic analog of the usual ACF, the AACF, the properties are similar to those of m-sequences with respect to the usual ACF (see §2.3.2.4, [KLA95], and [GOR97]).

3.3 The lp-Geffe-Generator

The generator investigated in this section uses the nonlinear Boolean function of the Geffe-generator (see §2.5.2: (Eq. 2.43) and Figure 9) to combine the outputs x1, x2, and x3 of three distinct FCSRs. For the remainder of the section only the case of maximal-period FCSRs with 2-prime connection integer is considered. The generator will be referred to as lp-Geffe-generator and is defined by an ordered tuple of connection integers (q1,q2,q3) that are associated to the component registers R1, R2, and R3 (see Figure 9), respectively. To completely specify the output sequence the FCSRs need to be initially loaded. The following discussion is restricted to strictly periodic driving and output sequences so that for simulations the initial loadings have to be chosen properly (see §2.3.2.3). Unless otherwise stated initial loadings corresponding to the integer p = −1 (see (Eq. 2.28)) are assumed to assure strict periodicity. Extensive simulation has shown that this assumption do not limit the scope of the analysis because validly altering the initial loading has only very little impact on the results.

Figure 11 Autocorrelation function of the l-sequence with q = 67

-1

-0,75

-0,5

-0,25

0

0,25

0,5

0,75

1

1 6 11 16 21 26 31 36 41 46 51 56 61 66

(q-1)/4 3(q-1)/4 (q-1)/2 (q-1)

τ

Cl(τ)

0 5 10 15 20 25 30 35 40 45 50 55 60 65


Basis for the numerical and empirical analysis are the set of lp-Geffe-generators with 2-prime connection integers (q1,q2,q3) ≤ 509 (see appendix A.1). In the following, these generators are examined regarding their period (§3.3.1), bit pattern distribution (§3.3.2), linear complexity (§3.3.3), and autocorrelation function (§3.3.4) and the simulation results are used to possibly find general analytical expression describing the observed properties.

3.3.1 Period

The period of the lp-Geffe-generator can be easily derived from that of the usual Geffe-generator. If the lp-Geffe-generator is defined by a 3-tuple (q1,q2,q3) of 2-prime connection integers and T1, T2, and T3 are the periods of the distinct, strictly periodic driving sequences x1, x2, and x3 with Ti = qi – 1 (i = 1, 2, 3), then the period Tz((q1,q2,q3)) (short Tz) of the output sequence z is where lcm(…) denotes the least common multiple. It is obvious that all permutations of the tuple (q1,q2,q3) will result in the same period Tz. The relation (Eq. 3.3) is lower-bounded by This bound is reached if two of the periods are divisors of the third one. For example, the output sequence z of the generator defined by the 3-tuple (13,19,37) has period Tz((13,19,37)) = 36 which is equal to the period T3 of the driving sequence x3 because T1 = 12 and T2 = 18 are factors of T3 = 36.

The maximum possible value for the period Tz((q1,q2,q3)) is given by

This upper bound can be derived as follows. Since the connection integers q1, q2, and q3 are (2-)prime the periods T1, T2 and T3 are always even numbers. They can therefore be represented as T1 = 2⋅Ť1, T2 = 2⋅Ť2, and T3 = 2⋅Ť3. If Ť1, Ť2, and Ť3 are pairwise relatively prime, then Tz((q1,q2,q3)) = lcm(2⋅Ť1, 2⋅Ť2, 2⋅Ť3) = 2⋅Ť1Ť2Ť3 = (T1T2T3)/4 which is the maximum possible value. It follows that Tz((q1,q2,q3)) = TUB((q1,q2,q3)) if and only if the condition is satisfied.

Generators of interest are clearly those having maximal period whereas constellations for which the period of the output sequence is equal to that of a driving sequence should be avoided. The computational evaluation of all lp-Geffe-generators with 2-prime connection integers (q1,q2,q3) ≤ 509 has shown that approximately 30,1% of all combinations (9139 possibilities) yield a maximal-period sequence (Tz((q1,q2,q3)) = TUB((q1,q2,q3))) and approximately 0,01% a minimal-period sequences (Tz ((q1,q2,q3)) = TLB((q1,q2,q3))).

In Figure 12 on the next page the period Tz((q1,q2,q3)) is plotted as a function of the 3-tuple (q1,q2,q3) where all 2-prime connection integers less than or equal to 227 are considered (2024 combinations). Two curves are given: In Figure 12 (a) the tuples (q1,q2,q3) are systematically ordered, i.e. (3,5,11) is the first tuple, (3,5,13) the second, … and (197,211,227) the last. An alternative representation is shown in Figure 12 (b) where the tuples are sorted by the sum of

(Eq. 3.3)

(Eq. 3.4)

(Eq. 3.5)

(Eq. 3.6)

)1,1,1(lcm),,(lcm)),,(( 321321321 −−−== qqqTTTqqqTz

).,,max()),,(( 321321 TTTqqqTLB =

.4

)1)(2)(1(4

)),,(( 321321321

−−−==

qqqTTTqqqTUB

2),gcd(),gcd(),gcd( 323121 === TTTTTT


the 2-adic complexities of the associated component FCSRs, denoted φ2(q1,q2,q3). This measure is calculated by φ2(q1,q2,q3) = log2(q1q2q3) (see (Eq. 2.38)) and characterizes the complexity of the whole generator in terms of its size, i.e. by the number of cells in the basic registers.

Figure 12 Period of lp-Geffe-generators

The alternating curves in Figure 12 indicate that a growth in the complexity of the

generator does not necessarily imply a larger period. For example, the generator given by the tuple (179,181,227) has a complexity of φ2(179,181,227) ≈ 22,810 and a period of Tz((179,181,227)) = 1810260. The generator defined by the tuple (181,197,211) has almost the same complexity (φ2(181,197,211) ≈ 22,843) but a much lower period of Tz((181,197,211)) = 8820. Using a more complex generator results only in a larger period if condition (Eq. 3.6) is met. Then the period is proportional to 1/4 times the product of the periods of the driving sequences and exponentially grows with the complexity φ2(q1,q2,q3).

0,00E+00

5,00E+05

1,00E+06

1,50E+06

2,00E+06

2,50E+06

upper bound TUB((q1,q2,q3))

maximal period tuple

Tz (q1,q2,q3)

(3,5,11) (197,211,227)

0,00E+00

5,00E+05

1,00E+06

1,50E+06

2,00E+06

2,50E+06

(q1,q2,q3)

upper bound TUB((q1,q2,q3))

maximal period tuple

Tz (q1,q2,q3)

φ2(3,5,11) φ2(197,211,227) φ2(q1,q2,q3)

(a)

(b)


Compared to the usual Geffe-generator the maximal possible period is reduced by a factor of 4 (see §2.5.2). Moreover, the period of an m-sequence is larger than the period of an l-sequence assumed the generating registers have a comparable size. Thus, an equally complex Geffe-generator is able to produce sequences with significantly larger periods.

3.3.2 Bit Pattern Distribution

The distribution of zeros and ones in output sequences of lp-Geffe-generators has been evaluated on a large set of examples covering a wide range of parameter constellations. This test set is composed as follows. Consider the systematically sorted set of all lp-Geffe-generators with 2-prime connection integers (q1,q2,q3) less than or equal to 227, i.e. {(3,5,11); (3,5,13); (3,5,19); … ; (5,11,13); (5,11,19); … ;(197,211,227)}. For the numerical analysis the first 1060 tuples {(3,5,11); … ;(29,37,83)} and the 6 possible permutations of each tuple are considered resulting in an overall number of 6360 different generators.

The first important result regarding bit pattern distributions is that in most cases the number of zeros and ones within one period of the sequence is nearly identical. For about 77,6% of the investigated tuples of connection integers at least two of their 6 possible permutations even yield a balanced sequence. In the case of imbalanced sequences, the difference of occurrences of zeros and ones becomes insignificant as the period gets longer. This is illustrated in Figure 13 where for each tuple the number of ones of the worst-case-sequences is given, i.e. of the permutations yielding a minimum or a maximum. Thus, the curves constitute an upper and a lower bound. Note that in the diagram the number of ones Nones((q1,q2,q3)) is given relative to the length of the period Tz((q1,q2,q3)) and the tuples are sorted with respect to the period of the associated sequences (ascending order).

Figure 13 Relative number of ones in lp-Geffe-generator-sequences

0,25

0,3

0,35

0,4

0,45

0,5

0,55

0,6

0,65

0,7

0,75Nones / Tz

(q1,q2,q3)

Tz

(19,197,227)

199332

(3,5,13)

12

curve of maximums

curve of minimums


The fact that the minimum and the maximum curve in Figure 13 are mirrored versions of one another can be explained as follows. Suppose an lp-Geffe-generator is defined by the tuple (a,b,c), the generated output sequence has period Tz((a,b,c)) and the number of ones in the sequence is Nones((a,b,c)). Then the number of ones in the output sequence of the generator with connection integers (c,b,a) is This is an intrinsic property of the Geffe-structure and immediately follows from the fact that the second register (R2) is switching between the first (R1) and the third register (R3) to generate the output (see Figure 9).

Among the balanced sequences are those for which the second half of the period is the bitwise complement of the first half of the period. Note that this is only possible because the driving sequences x1 and x3 have this property too. Figure 14 illustrates the constellations required to generate such sequences. The period length T2 of the control sequence x2 has to be a divisor of Tz/2, where Tz is the period of the output sequence z. This results in an alignment of the period boundary of sequence x2 with the beginning of the second half of the sequence z. Furthermore, the sequences x1 and x3 need to have a period length T1 and T3 such that the beginning of their second halves are aligned with the beginning of the second half of the output sequence z. The effect of these constellations is that the selected bits in x1 and x3 are always complementary in the first ([0, Tz/2]) and second half ([Tz/2, Tz]) of the period of the sequence z.

Mathematical conditions that assure this property are the following. Let (q1,q2,q3) be the connection integers of an lp-Geffe-generator, T1 = q1 – 1, T2 = q2 – 1, and T3 = q3 – 1 the periods of the driving FCSRs R1, R2, and R3, and Tz the period of the output sequence z. If T1, T2, and T3 are represented as T1 = 2⋅Ť1, T2 = 2⋅Ť2, and T3 = 2⋅Ť3, then the conditions are:

(C1) Ť2 odd,

(C2) Ť1 and Ť3 even,

(C3) Ť1/2 and Ť3/2 odd.

In appendix A.5 a list of 2-prime connection integers (≤ 509) for R1, R2, and R3 satisfying (C1) − (C3) is given. From the test set about 11.3% of the generators have this property.

It is an important but undesirable property of sequences to have complementary period

(Eq. 3.7)

Figure 14 Constellations for generating lp-Geffe-generator-sequences with complementary period halves

)).,,(()),,(()),,(( cbaNcbaTabcN oneszones −=

R1: x1

R2: x2

R3: x3

...

...

...T3/2

T3

T2/2 T2

T1/2 T1

Tz/2 Tz

1st half of the period 2nd half of the period (bitwise complement of 1st half)


halves because their linear complexity is already upper-bounded by approximately half the period length (see (Eq. 3.1) and (Eq. 3.2)). More results about the linear complexity of lp-Geffe-generators are presented in the next section (§3.3.3).

It is an interesting observation that some output sequences of lp-Geffe-generators are either

identical or shifted versions of one another, even though the associated 3-tuples of connection integers are different (e.g. (5,19,11) and (13,19,11) or (11,37,19) and (19,37,11)). Obviously, those generators necessarily have the same period but finding general conditions for two lp-Geffe-generators to be equivalent remains an open question.


The results presented in this section are based on the same test set already used to analyze the distribution properties of lp-Geffe-generator-sequences (see §3.3.2). For the remainder of the section L((q1,q2,q3)) denotes the linear complexity of an lp-Geffe-generator with 2-prime connection integers (q1,q2,q3).

The first observations about the linear complexity of lp-Geffe-generators are concerned with different register permutations and can be described as follows. Suppose an lp-Geffe-generator is defined by the tuple (a,b,c) of 2-prime connection integers and a second generator is defined by the tuple (c,b,a) where only the registers R1 and R3 are exchanged. Then the linear complexities L((a,b,c)) and L((c,b,a)) of these two generators are either identical or at least almost identical, i.e.

)).,,(()),,(( abcLcbaL ≅ 14 In Figure 15 the relative frequency hDiff of the difference LDiff = |L((a,b,c)) – L((c,b,a))| is depicted for the set of all numerically analyzed generators. The diagram shows that equality is obtained in most cases (67,5%) and the probability of larger differences rapidly converges towards zero.

If the connection integers a, b, and c satisfy the inequality a < b < c then it can be observed that

14 The symbol ≅ denotes equality or “almost equality”.

(Eq. 3.8)

Figure 15 Relative frequency of the difference LDiff = |L((a,b,c)) – L((c,b,a))|

(Eq. 3.9)

0

0,1

0,2

0,3

0,4

0,5

0,6

0,7

0,8

LDiff

hDiff

)),,(()),,(( bcaLcbaL ≈

0 1 2 3 4 5 6 7 8 9


and in most cases An example illustrating these relations is given in Figure 16 where the computed linear complexities of all generators with a = 5, b = 29, and 37 ≤ c ≤ 227 are compared.

Figure 16 Linear complexity of lp-Geffe-generators for different register permutations

Since, the usual Geffe-generator with LFSR driving sequences shows similar behaviour, it is straightforward to utilize the results about this generator to analytically describe the linear complexity of the lp-Geffe-generator.

In a first approach, an upper bound on the linear complexity was derived. Recall that the linear complexity Lz of a usual Geffe-generator is determined by the equations (Eq. 2.41) and (Eq. 2.43)) which results in Lz = L1L2 + L2L3 + L3, where L1, L2, and L3 are the linear complexities of the component LFSRs R1, R2, and R3, respectively. This expression is only valid if the driving LFSRs have primitive connection polynomials. However, in the case of non-primitive connection polynomials Lz can be regarded as an upper bound. Furthermore, the linear complexity of an FCSR with 2-prime connection integer q is limited by LUB = (q + 1)/2 (see (Eq. 3.2)). Combining these results yields the following upper bound for the linear complexity of an lp-Geffe-generator where (q1,q2,q3) are the 2-prime connection integers of the driving registers R1, R2, and R3, respectively. Note that the linear complexity of a sequence cannot exceed the period length but the values of the above equation are possibly larger than the actual period. An improved expression can therefore be obtained by where Tz is the period of the output sequence (see (Eq. 3.3)). The numerical results for all lp-Geffe-generators with (q1 = 19, q2 ≤ 227, q3 ≤ 227) are compared against this bound in Figure 17. The order of the plotted data is given by the complexity of the generators, i.e. by

(Eq. 3.10)

(Eq. 3.11)

(Eq. 3.12)

)).,,(()),,(( cabLcbaL >>

c 0

250

500

750

1000

1250 a

b

c

L((a = 5, b = 29, c))L((b = 29, a = 5, c)) L((a = 5, c, b = 29))

21

4)1)(1(

4)1)(1(

)),,(( 33221321

++

+++

++=

qqqqqqqqLUB

)));,,((min()),,((~321321 zUBUB TqqqLqqqL =

37 53 59 61 67 83 101 107 131 139 149 163 173 179 181 197 211 227

L


φ2(q1,q2,q3) = log2(q1q2q3). The diagram shows that UBL~ ((q1,q2,q3)) is a suitable upper bound and often resembles the actually computed values. However, there are also many cases in which large differences occur.

Figure 17 Linear complexity of lp-Geffe-generators compared to the upper bound

UBL~

As described in subsection §3.3.1, special lp-Geffe-generators are those for which the

period of the output sequence takes on the maximum possible value of (T1T2T3)/4, where T1, T2, and T3 are the periods of the driving sequences (see (Eq. 3.5)). The condition to achieve the maximum period is that the greatest common divisor of T1, T2, and T3 equals 2 (see (Eq. 3.6)). A separate analysis of this type of generator has shown that the upper bound UBL~ ((q1,q2,q3)) is very close to the actual value of the linear complexity. This remarkable result is illustrated in Figure 18 on the next page, where the linear complexity and the corresponding upper bound are depicted for all maximal-period sequences of the data set used in Figure 17 above.

Both curves are closely related. They grow nearly identical and differ only by a slightly varying and increasing offset. One can conclude that equation (Eq. 3.12) may serve as a proper approximation for the linear complexity of maximal-period lp-Geffe-generator-sequences. This result is summarized by the following theorem. Let (q1,q2,q3) be the 2-prime connection integers of an lp-Geffe-generator with gcd(q1 – 1; q2 – 1) = gcd(q1 – 1; q3 – 1) = gcd(q2 – 1; q3 – 1) = 2 then the linear complexity L((q1,q2,q3)) of the output sequence is Note that UBL~ ((q1,q2,q3)) is always equal to LUB((q1,q2,q3)) for maximal-period sequences so that taking the minimum of Tz and LUB((q1,q2,q3)) as in (Eq. 3.12) is superfluous. From (Eq. 3.13) and (Eq. 2.26) it follows that the linear complexity of such sequences grows exponentially with the complexity of the generator, i.e. with the number of cells in the basic registers.

(Eq. 3.13)

0

2000

4000

6000

8000

10000

12000

14000L((q1,q2,q3))

φ2(q1,q2,q3) φ2(19,211,227)φ2(19,3,5)

upper bound UBL~ ((q1,q2,q3))

L((q1,q2,q3))

.2

14

)1)(1(4

)1)(1()),,(( 33221

321+

+++

+++

≈qqqqq

qqqL


Figure 18 Linear complexity of maximal-period lp-Geffe-generator-sequences compared to the upper

bound UBL~

The next diagram (see Figure 19) gives the relative difference between the computed and

the estimated values of the linear complexity for the same data evaluated in Figure 18. The estimation error rapidly decreases below 10% and for more complex generators one can expect much lower and continually decreasing relative errors. The approximation is therefore suitable for sufficiently complex generators. To obtain an exact value of the linear complexity of these sequences equation (Eq. 3.13) may be corrected by subtracting a weighted factor. At least the curves in Figure 18 do imply this conjecture because the difference is fairly constant for equally complex generators and increases slightly with the complexity. Furthermore, the linear complexity of a driving FCSR with 2-prime connection integer q may be sometimes slightly less than the theoretical maximum of (q + 1)/2. This should also be taken into account for a more precise approximation or even an exact calculation.

Figure 19 Relative error of the estimated linear complexity for maximal-period sequences

0

0,1

0,2

0,3

0,4

0,5

0,6

0,7

0

2000

4000

6000

8000

10000

12000

14000

φ2(q1,q2,q3) φ2(19,197,227)φ2(19,3,5)

L((q1,q2,q3))

φ2(19,197,227) φ2(19,3,5) φ2(q1,q2,q3)

UBUB LLL ~/)~( −

upper bound UBL~ ((q1,q2,q3))

L((q1,q2,q3))


Compared to the usual Geffe-generator a maximal-period lp-Geffe-generator is able to produce sequences with significantly larger linear complexity assumed the driving registers have an equivalent size. This is due to the fact that the linear complexity is determined by the same relation (see (Eq. 2.43)) but an FCSR has a larger linear complexity than a comparable LFSR.

Another special type of lp-Geffe-generators is the one for which the output sequences have

complementary period halves. The conditions to generate those sequences were discussed in section §3.3.2. Note that maximal-period lp-Geffe-generator-sequences never have this property because the respective conditions excluding each other.

Since the maximal possible linear complexity of sequences with complementary period

halves is given by equation (Eq. 3.2) the previously derived upper bound (see (Eq. 3.12)) can be further improved for this special case. Let (q1,q2,q3) be the 2-prime connection integers of an lp-Geffe-generator with (q1 – 1) = 22⋅t1, (q2 – 1) = 2⋅t2, and (q3 – 1) = 22⋅t3, where t1, t2, and t3 are odd numbers (see §3.3.2: (C1)-(C3)), then the adapted upper bound is where LUB((q1, q2, q3)) is defined by equation (Eq. 3.11) and Tz denotes the period of the output sequence. This bound is evaluated in Figure 20 for all lp-Geffe-generators with (q1 = 13, q2 ≤ 227, q3 ≤ 227) that generate sequences with complementary period halves (see appendix A.5). The associated relative differences between the computed linear complexities and the upper bound )),,((ˆ

321 qqqLUB (short UBL̂ ) are depicted in Figure 21 on the next page.

Figure 20 Linear complexity of sequences with complementary period halves compared to the upper

bound UBL̂

(Eq. 3.14)

0

2000

4000

6000

8000

10000

12000

14000

)2/)2());,,((min()),,((ˆ321321 += zUBUB TqqqLqqqL

φ2(q1,q2,q3)φ2(13,3,5) φ2(13,227,197)

L((q1,q2,q3))

)),,((ˆ321 qqqLUB

L((q1,q2,q3))


Figure 21 Relative difference of the linear complexity and the upper bound

UBL̂ of sequences with complementary period halves

The first diagram (Figure 20) indicates that UBL̂ is well suited as an upper bound. The values of the bound are very similar or even equal to the computed values and mostly differ by only a small amount. It follows that UBL̂ can be used as an approximation for the linear complexity of sequences with complementary period halves. Since the relative approximation error averagely decreases while the complexity φ2(q1,q2,q3), i.e. the size, of the corresponding generator increases (see Figure 21), the approximation is particularly suitable for more complex generators having a practically relevant size. Even though this behaviour is analogous to that of the previously derived approximation for the linear complexity of maximal-period sequences, there are significant differences. In the case of maximal-period sequences there is always a certain difference between the true and the estimated values (see Figure 18). This difference is fairly constant for equally complex generators and increases only slightly with the complexity φ2(q1,q2,q3). In the case of sequences with complementary period halves, the difference is quite alternating. For local minimums of the curve the approximation yields most of the time the exact value whereas the error is large for local peaks of the curve. These facts may serve as clues to derive a better approximation or to find additional conditions for which (Eq. 3.14) gives the exact value.

The linear complexity profile of sequences generated by lp-Geffe-generators shows the typical behaviour of random sequences. It grows approximately by n/2 (n is the number of considered sequence bits) indicating good randomness properties with respect to this criterion. All investigated sequences have associated such a “typical” linear complexity profile. A representative example is given in Figure 22 on the next page for the output sequence of an lp-Geffe-generator with (q1 = 37, q2 = 53, q3 = 59).

0

0,1

0,2

0,3

0,4

0,5

0,6

0,7

0,8

0,9

φ2(q1,q2,q3)φ2(13,3,5) φ2(13,227,197)

LLL ˆ/)ˆ( −


Figure 22 Linear complexity profil of the lp-Geffe-generator-sequence with (q1 = 37, q2 = 53, q3 = 59)

To summarize this section, one can say that sequences having maximal period deserve particular attention. The linear complexity of such sequences grows exponentially with the complexity φ2(q1,q2,q3) or the number of basic register cells of the generator and is well-approximated by equation (Eq. 3.13). To maximize the linear complexity for a given set of driving FCSRs the control register (R2) has to be the one with the largest connection integer (see (Eq. 3.10)).

A comparable estimation of the linear complexity of sequences with complementary period halves was also derived. However, the period and the linear complexity of such sequences are not necessarily related to the size of the generator. A large number of register cells, i.e. a large complexity φ2(q1,q2,q3), may result in a large or a small period length and linear complexity, which is undesirable and makes this special generator type unattractive. In addition, the property of complementary period halves is in general undesirable for cryptographic applications.

An important goal in stream cipher design is to find sequences for which the linear complexity approaches the period. This is the maximal possible value of periodic sequences and corresponds to the expected value for periodically repeated, truly random sequences [RUE86, p.52]. As for the usual Geffe-generator this is not possible for lp-Geffe-generator-sequences with larger periods due to the underlying combining function. As the period increases the ratio L/T decreases. Generators which produce sequences with a ratio of L/T near 1, are studied in section §3.4 below.

The Geffe-function is one example of a nonlinear combining function. The results presented in this section mostly have a straightforward extension to general nonlinear combining functions in algebraic normal form. Rigorous mathematical proofs of the results remain open to do.


Some numerical analysis has been done on the periodic ACF of sequences generated by lp-Geffe-generators. With respect to correlation properties there are basically two types of

0

200

400

600

800

1000

1200

1 501 1001 1501 2001 n

L

2L = 2062

L = 1031

500 1000 1500 2000 0


lp-Geffe-generator-sequences: those with and those without complementary period halves. The ACF of the first type has equivalent symmetry properties as an l-sequence (see §3.2.2 property 2 and 3). For the second type no general properties could be determined. In Figure 23 below a representative example for each sequence type is depicted. Both curves, but especially the one in Figure 23 (a), show some sort of regular or quasi-periodic behaviour. Furthermore, the correlation values for non-trivial shifts are often quite large, even up to 0.64! These characteristics indicate that the sequences possess some regular structure and that there is similarity between subsequences. However, to disclose this regularity a deeper analysis is necessary. Applications using correlation techniques mostly require low correlation values for non-trivial shifts so that the observed properties are undesirable. From a cryptographic point of view sequences with high autocorrelation values are not suitable because they are vulnerable to correlation attacks.

Figure 23 Autocorrelation functions of lp-Geffe-generator-sequences

-1

-0,75

-0,5

-0,25

0

0,25

0,5

0,75

1

-1

-0,75

-0,5

-0,25

0

0,25

0,5

0,75

1

C(τ)

τ

Tz/4

Tz/2

Tz/2

τ

C(τ)

(b) (q1 = 3,q2 = 19,q3 = 61) ; Tz = 180

(a) (q1 = 13,q2 = 19,q3 = 61); Tz = 180; complementary period halves

0 10 20 30 40 50 60 70 80 90

0 10 20 30 40 50 60 70 80 90


3.4 The 2-adic-Geffe-generator and FCSRs with Composed Connection Integer

In the previous section, the lp-Geffe-generator was investigated, which employs the Geffe-function to nonlinearly combine the output sequences of three distinct maximal-period FCSRs. A further modification of this structure, that uses 2-adic arithmetic instead of arithmetic over GF(2) to generated the keystream, is considered in this section. Suppose the driving FCSRs R1, R2, and R3 (see Figure 9) are defined by the distinct connection integers q1, q2, and q3 and the initial loadings correspond to the integers p1, p2, and p3 (see (Eq. 2.28)). If 2-adic addition and multiplication (see (Eq. 2.14) − (Eq. 2.21)) are used in equation (Eq. 2.43), then the generated keystream coincides with the 2-adic expansion of the rational number Thus, the resulting structure is equivalent to an FCSR with composed connection integer q´ and a specific initial loading corresponding to p´. The subsequent analysis is therefore not restricted to the lp-Geffe-generator with 2-adic arithmetic but largely focuses on the more general configuration of an FCSR with composed connection integer. The Geffe-function is used as an example and serves as starting point for further investigations. However, some specific aspects of that generator are discussed in more detail.

For the remainder of the section the connection integers qj are considered to be prime or a power of a prime. If 2-primitivity is required then it will be explicitly stated. Furthermore, the integer pj will be referred to as the initial loading of the FCSR with connection integer qj and the lp-Geffe-generator with 2-adic arithmetic is called 2-adic-Geffe-generator. If several connection integers are involved in an operation then they are always assumed to be pairwise distinct. The notion “composed connection integer” will be referred to as a connection integer that has several distinct prime factors. Prime factor means that the factor is either a prime or a power of a prime.

In the following, 2-adic-Geffe-generators and FCSRs with composed connection integer are studied regarding their period (§3.4.1), bit pattern distributions (§3.4.2), linear complexity (§3.4.3), and autocorrelation properties (§3.4.4). Numerical results are discussed for 2-prime connection integers qj ≤ 509 and are compared to analytical expressions. The derivation of analytical results is mainly based on (Eq. 3.15) and generalizations of that equation.

3.4.1 Period

For an lp-Geffe-generator the output sequence is strictly periodic if the driving sequences x1, x2, and x3 are strictly periodic. If 2-adic addition and multiplication are used as combining operations the situation is completely different. Suppose a 2-adic-Geffe-generator is given with connection integers (q1,q2,q3) and initial loadings (p1,p2,p3), then strict periodicity is only achieved if (see §2.3.2.3) where p´ = p1p2q3 + p2p3q1 + p3q1q2, q´ = q1q2q3, and α´ = p´/q´ (see (Eq. 3.15)). These conditions may or may not be satisfied with strictly periodic inputs. For example, if strictly periodic driving sequences x1, x2, and x3 are given by (q1 = 3, q2 = 5, q3 = 83) and (p1 = −1, p2 = −1, p3 = −1), then the output sequence is identical to the 2-adic expansion of

(Eq. 3.15)

(Eq. 3.16)

.321

213132321

3

3

3

3

2

2

2

2

1

1

qp

qqqqqpqppqpp

qp

qp

qp

qp

qp

′′

=++

=++=′α

)0( <′∧′<′ pqp


p´/q´ = 71/1245 which is an eventually (and not strictly!) periodic sequence because p´ > 0. Conversely, if x1, x2, and x3 are given by (q1 = 3, q2 = 5, q3 = 83) and (p1 = −1, p2 = 1, p3 = 1), then the output is the strictly periodic 2-adic expansion of p´/q´ = −65/1245 even though x2 and x3 are not strictly periodic. This seems to be a little bit strange but results from the fact that the 2-adic operations have memory (see (Eq. 2.14)−(Eq. 2.21)).

There are various possibilities to meet (Eq. 3.16). For example, if the initial loadings are set to be (p1 = −1, p2 = −1, p3 = −1), as in the previous section §3.3, then the keystream coincides with the 2-adic expansion of p´/q´ = (q1 + q3 − q1q2) / (q1q2q3) and strict periodicity is assured if (q3 < q1) and (q2 > 2). Alternatively, one can specify the connection integers and then determine adequate initial loadings.

Provided that the generated keystream is strictly periodic, i.e. if (Eq. 3.16) is satisfied, and that (same notation as for (Eq. 3.16)), then the period Tα´ of the 2-adic-Geffe-generator is given by which follows from (Eq. 2.13). Consequently, the period Tα´ is equal to where )2(ord

iqiT = are the periods of the driving sequences xi (i = 1,2,3). Note that equation (Eq. 3.18) does not require strictly periodic driving sequences, however, equation (Eq. 3.19) does. Otherwise the relation )2(ord

iqiT = is not valid. Equation (Eq. 3.19) can be proven as follows: Proof:

given: pairwise distinct primes q1, q2, q3

to show: ))2(ord);2(ord);2(ord(lcm)2(ord321321 )( qqqqqq =

− The definition of ordz(y) (read: order of y modulo z) implies that

2x ≡ 1 (mod q1q2q3)

with )2(ord )( 321 qqqx = where x is the smallest possible value for which (I) is true. − From the Chinese Remainder Theorem (CRT) [BUN96, p.89] it follows that

2x ≡ 1 (mod q1) ∧ 2x ≡ 1 (mod q2) ∧ 2x ≡ 1 (mod q3). − With Fermat’s Little Theorem [BUN96, p.96] which says

a(q – 1) ≡ 1 (mod q)

if q is prime, one obtains

x ≡ 0 (mod q1 – 1) ∧ x ≡ 0 (mod q2 – 1) ∧ x ≡ 0 (mod q3 – 1).

(Eq. 3.17)

(Eq. 3.18)

(Eq. 3.19)

)2(ord)2(ord )( 321 qqqqT == ′′α

1),gcd( =′′ qp

);;(lcm))2(ord);2(ord);2(ord(lcm 321321TTTT qqq ==′α

(I)

(II)

(III)


− Hence,

(q1 – 1) | x ∧ (q2 – 1) | x ∧ (q3 – 1) | x,

where y | z denotes that y is a divisor of z. − Since ordz(y) is always a divisor of (z – 1) if z is prime, it follows that

)2(ord1q | (q1 – 1) ∧ )2(ord

2q | (q2 – 1) ∧ )2(ord3q | (q3 – 1)

and therewith

)2(ord1q | x ∧ )2(ord

2q | x ∧ )2(ord3q | x.

− Thus,

lcm( )2(ord1q ; )2(ord

2q ; )2(ord3q ) | x

and

x ≡ 0 (mod lcm( )2(ord1q ; )2(ord

2q ; )2(ord3q )).

− The smallest possible x for which (VIII) is true, is

x = lcm( )2(ord1q ; )2(ord

2q ; )2(ord3q )

which completes the proof. The proof for n distinct primes is equivalent.

If the rational number p´/q´ associated to the keystream satisfies (Eq. 3.16) but do not satisfy (Eq. 3.17), then p´ and q´ share a common factor and the period Tα´ is a divisor of

)2(ord321 qqq and therewith of ))2(ord);2(ord);2(ord(lcm

321 qqq . As an example, consider the 2-adic-Geffe-generator defined by (q1 = 179, q2 = 13, q3 = 3) and (p1 = −1, p2 = −1, p3 = −1). The strictly periodic keystream corresponds to the 2-adic expansion of p´/q´ = −2145/6961. The connection integers are 2-prime so that the orders of 2 modulo q1, q2, and q3 and therewith the periods of the driving sequences x1, x2, and x3 are given by T1 = q1 – 1, T2 = q2 – 1, and T3 = q3 – 1, respectively. Because gcd(p´,q´) = 39 > 1, the rational number p´/q´ can be reduced to –55/179 and the period of the keystream results in Tα´ = 178 which divides lcm(q1 − 1; q2 − 1, q3 − 1) = 1068. This example points out that the initial loadings of the driving generators largely influence the period of the generated keystream. Note that this is in contrast to usual nonlinear combining generators with Boolean combining function, where the initial loading has no influence on the period of the output sequence.

In case the pairwise distinct connection integers are 2-prime and (Eq. 3.16) and (Eq. 3.17) are satisfied, then the period Tα´ of the 2-adic-Geffe-generator is identical to that of the lp-Geffe-generator (see (Eq. 3.3) and (Eq. 3.19)). All results previously derived in §3.3.1, especially about the upper and lower bound of the period (see (Eq. 3.4) − (Eq. 3.6)) are unrestrictedly applicable.

The above results are specific to the 2-adic-Geffe-generator but can be easily extended to a

general 2-adic combining generator. Suppose the outputs of n FCSRs with connection integers (q1,q2, …, qn) and initial loadings (p1,p2, …, pn) are combined by an arbitrary function f that implements a 2-adic sum of 2-adic products (corresponds to algebraic normal form, see §2.5.1). Then the output sequence coincides with the 2-adic expansion of the rational number

(IV)

(V)

(VI)

(VII)

(VIII)

(IX)


where p´ is a function of f, the initial loadings pj, and the connection integers qj. This means that any 2-adic combination of n FCSRs leads to a larger FCSR with connection integer q´ = q1q2…qn. The specific form of the 2-adic combining function f does only influence the initial loading p´. Applied to the 2-adic-Geffe-generator this implies that different permutations of the registers R1, R2, and R3 only result in different p´.

If (Eq. 3.16) and (Eq. 3.17) are satisfied then the period Tα´ of the output sequence of the 2-adic generator (or equivalently of the FCSR with composed connection integer q´) is

where )2(ordiqiT = are the periods of the strictly periodic driving sequences xi (i = 1,2, …,n).

The equation (Eq. 3.21) is lower-bounded by The bound is reached if the periods of (n – 1) sequences are divisors of the period of the nth one. In case the connection integers qj are prime factors and 2 is primitive root modulo qj, then the maximal possible value of Tα´ is: The condition for Tα´ = Tα´,UB is that the greatest common divisor of any pair (Ti,Tj) (i ≠ j) is minimal and thus equals 2.

Equations (Eq. 3.21) − (Eq. 3.23) are also true if the combining function f is Boolean. Hence, they constitute a generalization of (Eq. 3.3) − (Eq. 3.5).

The subsequent analysis is focussed on FCSRs with composed connection integer rather than on the special case of the 2-adic-Geffe-generator. The numerical analysis of these generators includes 2-prime factors qj up to 509. The following cases are considered:

− q´ has 2 distinct 2-prime factors: q´ = q1q2; (q1,q2) ≤ 509 (741 combinations)

− q´ has 3 distinct 2-prime factors: q´ = q1q2q3; (q1,q2,q3) ≤ 227 (2024 combinations)

− q´ has 4 distinct 2-prime factors: q´ = q1q2q3q4; (q1,q2,q3,q4) ≤ 101 (715 combinations)

− q´ has 5 distinct 2-prime factors: q´ = q1q2q3q4q5; (q1,q2,q3,q4,q5) ≤ 101 (1287 combinations).

All subsequent simulations are based on an initial loading of p´ = −1 which assures (Eq. 3.16) and (Eq. 3.17). Extensive analysis has shown that all other initial loadings that satisfy these conditions yield very similar or identical results so that this predefinition is reasonable and does not restrict the scope of the investigation

Connection integers of interest are clearly those, which yield a maximal-period sequence, i.e. for which Tα´ = Tα´,UB. The simulation has shown that the more (2-)prime factors a connection integer has, the smaller the probability that this connection integer generates a maximal-period sequence. This is illustrated in Figure 24 where the relative frequency hUB of maximal-period sequences is depicted as a function of the number n of prime factors.

(Eq. 3.20)

(Eq. 3.21)

(Eq. 3.22)

(Eq. 3.23)

,...21 q

pqqq

p

n ′′

=′

=′α

);...;;(lcm))2(ord);...;2(ord);2(ord(lcm)2(ord 2121 nqqqq TTTTn

=== ′′α

.2

...2

)2(ord)...2(ord)2(ord1

211´,

21

−− == nn

nqqq

UBTTT

T nα

).(max))2(ord(max11, i

n

iq

n

iLB TTi ==

′ ==α


Figure 24 Relative frequency of maximal-period sequences generated by FCSRs with composed

connection integer The result is not surprising because it is “more difficult” for a connection integer with a greater number of prime factors to met the condition for generating a maximal-period sequence. With an increasing number of factors qj the number of pairs (Ti,Tj) (i ≠ j) exponentially increases for which the greatest common divisor has to be minimum. Therefore, the probability that this condition is satisfied decreases exponentially. As will be seen below, this effect is undesirable if maximal linear complexity is to be guaranteed.

3.4.2 Bit Pattern Distribution

For the set of FCSRs with composed connection integer q´, that were already examined in the previous subsection (see §3.4.1: qj’s are distinct 2-primes and p´ = −1), it has been verified that the generated sequences are either balanced or at least very close to have this property. The simulation has shown that the portion (hbs) of exactly balanced sequences rapidly decreases as the number n of (2-)prime factors of q´ increases (see Figure 25).

Figure 25 Relative frequency of balanced sequences generated by FCSRs with composed connection

integer

0

0,2

0,4

0,6

0,8

1

0

0,2

0,4

0,6

0,8

1

1 2 3 4 5 n

hUB

n

hbs

1 2 3 4 5


For imbalanced sequences the difference between the number of zeros and ones within one period is only small. The relative number of ones Nones / Tα´ (Tα´ period) for sequences with longer period is very close to ½ (equivalently for the number of zeros). As an illustration, the ratio Nones / Tα´ is depicted in the subsequent diagram for all connection integers q´ composed of 4 distinct 2-prime factors ((q1,q2,q3,q4) ≤ 101) that generate sequences with Tα´ < 20000 (see Figure 26 below; q’s sorted by increasing period).

Figure 26 Relative number of ones in sequences generated by FCSRs with connection integers composed

of 4 distinct 2-primes

The same effect could be observed for the lp-Geffe-generator but the “convergence” in that case is significantly worse (compare to Figure 13).

Almost all balanced sequences are those for which the second half of the period is the bitwise complement of the first half of the period. A condition that guarantees the generation of this sort of sequence has been derived and is made explicit with the following theorem.

Suppose q´ = q1q2…qn is the composed connection integer of an FCSR where the qj‘s are prime factors. Suppose further that the generated sequence (a)∞ is strictly periodic (conditions (Eq. 3.16) and (Eq. 3.17) are satisfied) with period Tα´ and that Tα´ is even, i.e. 2 | Tα´

15. Then the sequence (a)∞ has the form (u, ū, u, ū, … ), where u = (a0, a1, …, 12/ −′αTa ) and ū is the complement sequence of u, if and only if A proof of this theorem is given below for connection integers being composed of two distinct primes. The actual proof requires the expression

15 Note that this condition is always satisfied for 2-prime factors or if qj is a prime power for which 2 is a primitive root (compare to (Eq. 2.29) and (Eq. 2.36)).

(Eq. 3.24)

(Eq. 3.25)

0,2

0,25

0,3

0,35

0,4

0,45

0,5

0,55

0,6Nones / Tα´

Tα´

q´ = q1q2q3q4 q´ = 3⋅5⋅13⋅19 19188 36

)).12()12((|)...( 2/))2(ord);...;2(ord);2(ord(lcm2/21

21 +=+=′ ′ nqqqTnqqqq α

1)12 ; 12gcd( =−+ kk

q´ = 19⋅37⋅53⋅83


(k is some positive integer) which is proven beforehand. Proof:

given: p: pime; p > 2, k ∈ Z, k > 0

to show: 1)12 ; 12gcd( =−+ kk

assumption: p | )12 ; 12gcd( −+ kk (p > 2 can be assumed since )12 ; 12gcd( −+ kk is an odd number)

− From the assumption it follows that

p | ) 12( +k and p | ) 12( −k . − Hence,

) 12( +k ≡ 0 (mod p) ∧ ) 12( −k ≡ 0 (mod p). − Thus,

− From (IIIc) it follows that p | 2. But this is a contradiction because p > 2. Therefore )12 ; 12gcd( −+ kk has no prime factor which means )12 ; 12gcd( −+ kk = 1.

The proof of (Eq. 3.24) for two distinct prime factors is then as follows: Proof:

given:

to show: (a)∞ has the form (u, ū, u, ū, … ), where u = (a0, a1, …, 12/ −′αTa ) and ū = ( 0a , 1a , …, 12/ −′αTa ) is the complement sequence of u, if and only if

)).12()12((|)( 2/))2(ord);2(ord(lcm2/21

21 +=+=′ ′ qqTqqq α − The period of a strictly periodic FCSR-sequence with connection integer q´ = q1q2 is

given by

))2(ord);2(ord(lcm)2(ord)2(ord2121 qqqqqT === ′′α

(see (Eq. 3.18) and (Eq. 3.19)) if conditions (Eq. 3.16) and (Eq. 3.17) are satisfied.

− From the definition of ordq´(2) it follows that

(I)

(II)

(IIIa)(IIIb)

(IIIc)

) 12( +k ≡ ) 12( −k (mod p) 1 ≡ −1

2 ≡ 0

(I)

) (mod 122 )2( qTordq ′≡= ′′ α

) (mod 0)12( qT ′≡−′α

(IIa)(IIb)

(mod p)

(mod p).

• q´ = q1q2: composed connection integer; q1 and q2 are distinct prime factors

• (a)∞: binary, strictly periodic FCSR-sequence arising from connection integer q´ = q1q2

• Tα´: period satisfying 2 | Tα´


and therewith

q´ | )12( −′αT .

− Since 2 | Tα´, the term )12( −′αT can be decomposed into

)12)(12( 2/2/ +− ′′ αα TT

and hence

(q´ = q1q2) | ).12)(12( 2/2/ +− ′′ αα TT − Since 1))12();12gcd(( 2/2/ =+− ′′ αα TT (see (Eq. 3.25)) there are 3 possible

constellations:

(1) q1 | )12( 2/ −′αT ; q1 )12(| 2/ +¬ ′αT and q2 | )12( 2/ +′αT ; q2 )12(| 2/ −¬ ′αT

(2) q1q2 | )12( 2/ −′αT ; q1q2 )12(| 2/ +¬ ′αT

(3) q1q2 | )12( 2/ +′αT ; q1q2 )12(| 2/ −¬ ′αT

(“¬|“ denotes “is not a divisor of”).

Case (2): − If q1q2 | )12( 2/ −′αT , then

) (mod 0)12( 212/ qqT ≡−′α

− Tα´ is the order of 2 modulo (q´ = q1q2) (see (I)), i.e. Tα´ is the smallest possible

value for which the congruence ) (mod 12 21qqx ≡ is true. Thus, (I) and (IXb) lead to a contradiction so that case (2) is not possible.

Case (3): − If q1q2 | )12( 2/ +′αT , then

− The exponential representation for strictly periodic sequences of bits obtained from FCSRs with connection integer q´ is given by

K,2,1,0)2))(mod(mod( =′= iqAa ii γ

(see (Eq. 2.34)), where A ∈ Z/(q) corresponds to a specific initial loading and γ = 2−1 ∈ Z/(q´) is the multiplicative inverse of 2 in the ring Z/(q´) of integers modulo q´.

− The element 2/α ′+Tia is given by

K,2,1,0)2))(mod(mod( 2/2/ =′= ′

′

++ iqAa Ti

Tiα

αγ .

(III)

(IV)

(V)

(VI)

(VII)

(VIII)

(IXa)

12 2/ ≡′αT (mod q1q2 ) (IXb)

12 2/ −≡′αT (mod q1q2). ≡+′ )12( 2/αT 0 (mod q1q2) (Xa)

(Xb)

(XI)

(XII)


− Since,

ordq´(2) = ordq´(2−1),

for all integers q´, the above equations (IIa) − (Xa) can be equivalently derived if 2 is replaced by 2−1. It follows that,

) (mod 1)2()( 2/12/ qTT ′−≡= ′′ − ααγ

(see equation (Xb)). Hence,

)2))(mod(mod( 2/2/ qAa Ti

Ti ′= ′

′+α

αγγ

)2))(mod(mod( qA i ′−= γ .

− The term ( iAγ− ) is the additive inverse of iAγ in the ring Z/(q´) of integers modulo q´ and is calculated by

iAγ− = q´ − iAγ

Hence, i

iTi aqAqa =′−′=

′+ )2))(mod(mod(2/ γα

. − From (XVII) it follows that the second half of the period is the complement of the

first half of the period. Case (1) − Equation (VI) leads to the congruences

) (mod 12 12/ qT ≡′α

) mod( 12 22/ qT −≡′α .

− With (XII) and the CRT one obtains

K,2,1,0)2))(mod(mod( 12/

2/ == ′

′+ iqAa TiTi

α

αγγ

K,2,1,0)2))(mod(mod( 22/

2/ == ′

′+ iqAa TiTi

α

αγγ .

− Combining (XIII) and (XVIII – XXI) results in

ii

Ti aqAa ==′+ )2))(mod(mod( 12/ γ

α

ii

Ti aqAa =−=′+ )2))(mod(mod( 22/ γ

α

− Since (XXII) and (XXIII) cannot be combined to (XVII), constellation (VI) do not

yield complementary period halves which completes the proof.

The generalization of this proof to composed connection integers with n prime factors is straightforward and the argumentation is equivalent. The special case where all qj’s are identical leads to an FCSR with a connection integer that is a prime power. This case is treated in [GOR97].

(XIV)

(XVb)

(XVa)

(XVI)

(XVII)

(XIII)

(XVIII)

(XIX)

(XX)

(XXI)

(XXIII)

(XXII)


Based on the above proof the probability that an FCSR-sequence has complementary period halves can be derived as follows. Suppose q´ = q1q2…qn (n ≥ 2) is the composed connection integer of an FCSR that generates a strictly periodic sequence (a)∞ with period Tα´ where 2 | Tα´. Then a prime factor qj either divides )12( 2/ −′αT or )12( 2/ +′αT (see (VI) – (VIII) in the proof above). It is natural to assume that both cases are equally likely, i.e. that

where P(A) denotes the probability of the event A. Then the probability that q´ = q1q2…qn divides )12( 2/ +′αT is given by Equation (Eq. 3.27) includes the case of n = 1 in which it is guaranteed that (q´ = q1) | )12( 2/ +′αT . The results obtained for the relative frequency of balanced sequences as a function of n (see Figure 25) approximately coincides with (Eq. 3.27) which shows that assumption (Eq. 3.26) is valid. Deviations may be due to statistical variations and due to the fact that not all balanced sequences have complementary period halves. An analytical expression for the probability of maximal-period sequences (compare to Figure 24) as a function of n may be derived in a similar way.

The property of complementary period halves is crucial for the linear complexity of a sequence as have been discussed in §3.2.1. This discussion will be continued in the next subsection for FCSRs with composed connection integer.


The linear complexity Lα´ of FCSRs with composed connection integer has been numerically evaluated for the same test set already used in the previous subsections (see §3.4.1 and §3.4.2). Because of the time consuming calculations not all of these generators were considered but a sufficiently large number of representative ones. The most important result is that the linear complexity is either very close to ½⋅Tα´ or to Tα´, where Tα´ is the period of the strictly periodic output sequence.

Unexceptionally all investigated sequences with Lα´ ≅ ½⋅Tα´ are those having complementary period halves. As previously derived in §3.2.1 the linear complexity of such sequences is at most Lα´,max = (Tα´ + 2)/2 (see (Eq. 3.2)), which coincides in many cases with the calculated value or at least gives a very good approximation. Since the small differences between the upper bound Lα´,max and the computed values are not reasonably presentable a respective diagram is omitted at this point.

The linear complexity of the remaining sequences without the property of complementary period halves was determined to be Lα´ ≅ Tα´. Using equation (Eq. 3.24) these results can be summarized as follows: Suppose q´ = q1q2…qn is the composed connection integer of an FCSR that generates a strictly periodic sequence (a)∞ (see conditions (Eq. 3.16) and (Eq. 3.17)) with period Tα´, where 2 | Tα´. Then the linear complexity Lα´ of (a)∞ is given by

(Eq. 3.26)

(Eq. 3.27)

(Eq. 3.28)

2/1))12(|())12(|( 2/2/ =−=+ ′′ αα Tj

Tj qPqP

.)2/1())12(|)...(( )1(2/21

−=+=′ ′ nTnqqqqP α

⎩⎨⎧ +=′≈+

≅′

′′∞′

)12(| )...( if /2 2/)2())((

2/21

ααα

α

TnqqqqTT

aL)12(| )...( if 2/

21 +¬=′ ′′

αα

TnqqqqT


where ))2(ord);...;2(ord);2(ord(lcm)2(ord21 nqqqqT == ′′α . An analytical proof that the linear

complexity only takes on one of these two values could not be found but the obtained numerical results strongly imply this conjecture. But note that the simulation only included 2-prime factors qj so that the situation might be different if the qj’s are not 2-prime.

From equation (Eq. 3.27) and (Eq. 3.28) it follows that the probability that an FCSR with composed connection integer q´ = q1q2…qn (n prime factors) generates a strictly periodic sequence (a)∞ with linear complexity Lα´((a)∞) ≅ Tα´ is given by For the test set the relative frequency hL≅T of sequences with Lα´ ≅ Tα´ was determined and compared to P(Lα´ ≅ Tα´) (see Figure 27). Both curves are very similar. The differences are only very small and may be due to statistical variations.

Figure 27 Relative frequency and probability of FCSR-sequences with Lα´ ≅ Tα´

A consequence of (Eq. 3.29) is that the linear complexity of a strictly periodic FCSR-

sequence is almost certainly close to the period length provided that the connection integer is composed of a sufficiently large number of prime factors. To increase the probability of P(Lα´ ≅ Tα´) one only needs to increase the number n of prime factors. For example, if the connection integer q´ has n = 10 prime factors then P(Lα´ ≅ Tα´) = 99,8%, which almost guarantees that Lα´ ≅ Tα´. But note that the more prime factors the connection has the smaller the probability that the generated sequence has the maximal possible period (see (Eq. 3.23) and Figure 24). Thus, there is a classical design tradeoff between achieving maximal period and maximal linear complexity.

As stated before, the linear complexity of a strictly periodic sequence is at maximum equal

to the length of the period. The expected value of the linear complexity of a periodically repeated truly random sequence is close to that maximum [RUE86, p.52] which means that a good pseudorandom generator should approach this maximum too. In that sense FCSRs with connection integers composed of many prime factors are well suited for generating “linear unpredictable” pseudorandom sequences; much better than lp-Geffe-generators, where the

(Eq. 3.29) .)2/1(1)( )1( −′′ −=≅ nTLP αα

0

0,25

0,5

0,75

1

1 2 3 4 5 n

hL≅T / P

P(Lα´ ≅ Tα´)

hL≅T


linear complexity is far below the period length. However, the 2-adic complexity of these sequences is only small compared to the period length because the underlying computational model is equal to the sequence generator itself. Thus, those generators are highly predicable with respect to this complexity measure due to the efficient RA-algorithm so that they cannot be used as keystream generators directly.

The linear complexity profile of sequences generated by an FCSR with composed

connection integer shows the typical behaviour of random sequences. Since, the measured profiles are identical to those depicted in Figure 10 and Figure 22, a respective diagram is left out at this point.


Similar to the lp-Geffe-generator one can distinguish between two types of sequences with respect to autocorrelation properties: the ones with and the ones without complementary period halves. A typical example for each type is depicted in Figure 28. All other evaluated sequences (connection integers with up to 5 prime factors) show analogous behaviour. The symmetry properties as described for l-sequences (see §3.2.2) apply also to this kind of sequences with complementary period halves. Both curves are irregularly shaped and show the same random-looking behaviour as the periodic ACF of l-sequences (compare to Figure 11). Compared to lp-Geffe-generator-sequences this is quite a difference because their ACF is much more regular. The values for non-trivial shifts are not that large and the peaks are significantly lower than those for lp-Geffe-generator-sequences, even lower than those for l-sequences. Although the ACF of FCSR-sequences arising from composed connection integers is by far not ideal, it shows better properties than the ACF of the sequences discussed in the previous chapters.

-1

-0,75

-0,5

-0,25

0

0,25

0,5

0,75

1C(τ)

τ

(a) q´ = q1q2q3 = 5⋅37⋅61; Tα´ = 180; complementary period halves

Tα´/4 Tα´/2

0 10 20 30 40 50 60 70 80 90


Figure 28 Autocorrelation function of sequences generated by FCSRs with composed connection integer

-1

-0,75

-0,5

-0,25

0

0,25

0,5

0,75

1

C(τ)

Tα´/2 (b) q´ = q1q2q3 = 11⋅13⋅19; Tα´ = 180

τ0 10 20 30 40 50 60 70 80 90

4 Summary 60

4 Summary

In this thesis, FCSR-based pseudorandom sequence generators were investigated. After introducing the theory and criteria required to analyze and design pseudorandom generators, the basic FCSR and maximal-period FCSR-sequences (l-sequences) were theoretically and practically studied. Results were derived concerning the linear complexity and concerning the autocorrelation function of l-sequences. An important result is that the linear complexity of l-sequences is approximately equal to half the period length. Although no general proofs could be delivered, the large number of investigated cases strongly implies that the results are of general nature.

The Boolean Geffe-function was considered as particular nonlinear combining function. The lp-Geffe-generator that employs this combining function with maximal-period FCSRs (2-prime connection integer) as driving registers was analyzed in detail. It turned out that sequences with practically relevant period lengths are at least close to be balanced. Conditions could be found to maximize the period and to generate sequences with complementary period halves. For these two types of sequences a tight upper bound for the linear complexity was derived that may serve as a very good approximation for sequences with sufficiently long period. It is still open to provide rigorous mathematical proofs for the results regarding the linear complexity or to find expressions for an exact calculation. The ACF of lp-Geffe-generator-sequences was only initially examined so that a deeper analysis is also open for future work.

A modified Geffe-structure that employs 2-adic arithmetic instead of Boolean operations to

combine the outputs of FCSRs was investigated similarly to the lp-Geffe-generator. Since the generator is equivalent to an FCSR with composed connection integer the analysis was focussed on this more general configuration. Conditions for generating sequences with maximal period or with complementary period halves could be derived and proven. The probability that an FCSR generates a sequence with one of these two properties was shown to be related to the number of prime factors of the composed connection integer. Practically relevant sequences are at least close to be balanced and the linear complexity is either very close to half or to the full period length. The condition that the linear complexity approaches the maximum was found to be based on the condition to generate complementary period halves so that the probability for taking on this maximum increases with the number of prime factors of the corresponding connection integer. The linear complexity of an FCSR with composed connection integer can thus be expressed in terms of the probability that a specific condition is satisfied. Precisely proving this result is still an open problem. Since, only some analysis was done on the ACF, there remains also a plenty of room for further investigations.

In addition to open problems pointed out in corresponding sections, there are a number of

interesting questions in connection with the topic of this thesis, that remain for future research. For instance: What are the properties of generators with LFSRs as driving registers and a 2-adic combining function? What is the relation between the 2-adic and the linear span? How to design generators with both large linear and 2-adic span? How to extended the presented results to the non-binary case? Even though the generators considered in this thesis do not suffice rigorous cryptographic requirements, the obtained results may be suitable to serve as starting point or clues to solve the listed problems or to design and analyze FCSR-based pseudorandom sequence generators.

Glossary 61

Glossary

2-adic generator combining generator with FCSRs as component registers and 2-adic combining function

2-prime prime number having 2 as a primitive root

a 2-prime connection integer or integer

(a)∞ infinite (binary) sequence

A element of GF(2r) corresponding to initial loading of LFSR or element of Z/(q) corresponding to initial loading of FCSR, random event

AACF arithmetic autocorrelation function

ACF autocorrelation function

ai, an contents of a register cell; element of the sequence (a)∞; coefficient of a formal power series; coefficient of the 2-adic expansion of a rational number; input bit to the BM/RA-algorithm

ia complementary bit to ai

AND Boolean and-function

A(τ ) number of agreements between original sequence and its shifted version (shift by τ positions)

A(X) generating function in X of an infinite (binary) sequence

α, α´, αi rational number; 2-adic integer; formal series in powers of 2

α[i] shift of 2-adic integer α by i positions

b 2-prime connection integer

(b)∞ infinite (binary) sequence

bi element of the sequence (b)∞; coefficient of the 2-adic expansion of a rational number

BM-algorithm Berlekamp-Massey algorithm

β rational number; 2-adic integer; element of some extension field GF(2r)

β−1 multiplicative inverse of β

−β additive inverse of β

β complementary 2-adic integer of β

c 2-prime connection integer

ci ciphertext character; carry for 2-adic addition / multiplication

CCF crosscorrelation function

Cl(τ) periodic autocorrelation function in τ of an l-sequence

CRT Chinese Remainder Theorem

C(τ ) periodic autocorrelation function in τ

Glossary 62

D(τ ) number of disagreements between original sequence and its shifted version (shift by τ positions)

deg(r(x)) degree of the polynomial r(x)

e exponent

f(…) Boolean function; combining function in a nonlinear combining generator or a 2-adic generator; nonlinear filtering function; next-state function of a keystream generator

FCSR feedback carry shift register

FSR feedback shift register

φ2((a)∞), φ2 2-adic complexity of the sequence (a)∞

φ2(n) 2-adic complexity of the first n bits of a sequence

Φ(p,q) maximum function of |p| and |q|

φ2(q1,q2,q3) (2-adic) complexity of an lp-Geffe-generator

g(…) keystream-generation function of a keystream generator

GF(q) Galois field (finite field) of order q

GF(q)[[X]] ring of formal power series in X with coefficients in GF(q)

gcd greatest common devisor

γ root of connection polynomial q(X) (∈ GF(2r)); multiplicative inverse of 2 in the ring Z/(q)

h(…) output function of a keystream generator

hbs relative frequency of balanced sequences generated by FCSRs with composed connection integer

hDiff relative frequency of LDiff

hL≅T relative frequency of sequences having a linear complexity close to or identical to the period length

hUB relative frequency of maximal-period sequences generated by FCSRs with composed connection integer

i index variable

j index variable, exponent

k key, integer

L linear complexity

Lα´ linear complexity of an FCSR with composed connection integer

Lα´,max maximal linear complexity of a sequences with complementary period halves generated by an FCSR with composed connection integer

lcm least common multiple

LDiff difference between linear complexities of lp-Geffe-generators with permuted component registers

Glossary 63

LFSR linear feedback shift register

Li linear complexity of a driving sequence xi in a nonlinear combining generator; linear complexity of a subsequence consisting of the first i terms of a given sequence

Lmax maximal linear complexity of a nonlinear filter generator

log2(…) logarithm in base 2

lp-Geffe-generator Geffe-generator with FCSRs as component registers

L((q1,q2,q3)) linear complexity of an lp-Geffe-generator with 2-prime connection integers (q1,q2,q3)

LUB upper bound of the linear complexity of a maximal-period FCSR

LUB((q1,q2,q3)) upper bound of the linear complexity of an lp-Geffe-generator with 2-prime connection integers (q1,q2,q3)

UBL~ ((q1,q2,q3)), UBL~ improved upper bound of the linear complexity of an lp-Geffe-generator with 2-prime connection integers (q1,q2,q3)

)),,((ˆ321 qqqLUB , UBL̂ upper bound of the linear complexity of an lp-Geffe-generator with

2-prime connection integers (q1,q2,q3) that generates a sequence with complementary period halves

Lz linear complexity of the keystream z of a nonlinear combining generator

λ2((a)∞), λ2 2-adic span of the sequence (a)∞

λ2(n) 2-adic span of the first n bits of a sequence

m order of a Boolean function; order of the correlation immunity of a Boolean function; number of driving sequences in a nonlinear combining generator; memory value of an FCSR

max maximum function

mi plaintext character

min minimum function

mn memory value of an FCSR

mod modulo

N exponent

Nones number of ones in a binary sequence

n index variable; number of terms in a finite series or sequence; number of processed bits in the BM/RA-algorithm; number of ciphertext characters considered in the next-state function of a keystream generator; number of driving sequences in a combining generator; number of prime factors of a composed connection integer

Nones((q1,q2,q3)) number of ones in the output sequence of an lp-Geffe-generator with 2- prime connection integers (q1,q2,q3)

ordy(x) order of x modulo y

|p| absolute value of p

Glossary 64

p, p´, pβ, pα, pi, pj prime number; integer; numerator of a rational number corresponding to a specific initial loading of an FCSR

P(A) probability of the event A

(p1,p2,p3) 3-tuple of integers defining the initial loading of a 2-adic Geffe-generator

(p1,p2,…,pn) n-tuple of integers defining the initial loadings of n FCSRs

(p,q)n rational number p/q whose 2-adic expansion coincides with the first n bits of a given sequence

Q the set of rational numbers

q, q´, qβ, qα integer; denominator of a rational number; connection integer of an FCSR

(q1,q2,q3) 3-tuple of connection integers defining an lp-Geffe-generator or a 2-adic Geffe-generator

(q1,q2,…,qn) n-tuple of connection integers defining n FCSRs

qi feedback coefficient of an FSR; coefficient of a feedback polynomial; coefficient of binary expansion of a connection integer

qj connection integer of an FCSR; prime factor

Qp field of p-adic numbers

q(X) connection polynomial in X of an LFSR

r length or number of cells of an FSR

(r)∞ infinite (binary) sequence

RA-algorithm rational approximation algorithm

ri coefficient of 2-adic sum/product of two binary sequences

Ri component FSR of a nonlinear combining generator

Ri((a)∞) arithmetic autocorrelation function of the sequence (a)∞ for a shift of i positions

r(X) polynomial in X corresponding to an initial loading of an LFSR

s length of a subsequence

strong 2-prime 2-prime of the form q = 2p + 1 where p is also 2-prime

σi internal state of a keystream generator

σn integer sum of cell and memory contents of an FCSR

T length of a finite sequence or period of an infinite, periodic sequence

Tα´ period of 2-adic generator or 2-adic-Geffe-generator

Tα´,LB lower bound of the period of a 2-adic generator

Tα´,UB upper bound of the period of a 2-adic generator

ti odd number

Glossary 65

Ti period of a driving sequence xi in a nonlinear combining generator or a 2-adic generator

Ťi factor of the period Ti

TLB((q1,q2,q3)) lower bound of the period of an lp-Geffe-generator with 2-prime connection integers (q1,q2,q3)

Tmax maximum possible period of a sequence

Tr(β) trace function mapping β in GF(2r) into GF(2)

TUB((q1,q2,q3)) upper bound of the period of an lp-Geffe-generator with 2-prime connection integers (q1,q2,q3)

Tz((q1,q2,q3)), Tz period of an lp-Geffe-generator with 2-prime connection integers (q1,q2,q3)

τ discrete shift variable

u binary subsequence half the period long

ū bitwise complement sequence of the sequence u

ui non-binary coefficient of 2-adic product of two binary sequences

ωt(q), ω Hamming weight of q

x integer or rational number

⎣ ⎦x greatest integer less than or equal to x

⎡ ⎤x least integer greater than or equal to x

xi Boolean variable, driving sequence in a nonlinear combining generator

XOR Boolean exclusive-or-function

x | y x divides y

x ¬| y x does not divide y

y integer; initialization value of FCSR

z keystream, integer

Z the set of integers

Z2 ring of 2-adic integers

zi keystream character

Zp ring of p-adic integers

Z/(q) ring of integers modulo q


Literature References

[AES01] Advanced Encryption Standard – Announcement, http://csrc.nist.gov/ publications/fips/fips46-3/fips46-3.pdf, November 2001

[BUN96] Bundschuh, P.: Einführung in die Zahlentheorie, Springer Verlag, 1996

[COH93] Cohen, H.: A Course in Computational Algebraic Number Theory, Springer Verlag, 1993

[CUS98] Cusick, T. W.; Ding, C.; Renvall, A.: Stream Ciphers and Number Theory, Elsevier Science B.V., 1998

[DES99] Data Encryption Standard – Announcement, http://csrc.nist.gov/publications/ fips/fips46-3/fips46-3.pdf, October1999

[FUM94] Fumy, W., Rieß, H. P.: Kryptographie: Entwurf, Einsatz und Analyse symmetrischer Kryptoverfahren; Oldenbourg Verlag GmbH, München 1994

[GEF73] Geffe, P. R.: How to Protect Data with Ciphers that are Really Hard to Break, in Electronics, Jan 1973

[GOL67] Golomb, S. W.: Shift Register Sequences, Holden-Day, San Francisco, Calif., 1967

[GOR97] Goresky, M.; Klapper, A.: Arithmetic Crosscorrelations of Feedback with Carry Shift Register Sequences, in IEEE Trans. Info. Theory, vol. 43(4), pp. 1342 – 1345, July 1997

[GOR02] Goresky, M.; Klapper, A.: Fibonacci and Galois Representations of Feedback Carry Shift Registers, in IEEE Trans. Info. Theory, vol 48(11), pp. 2826-2836, Nov. 2002

[GOU97] Gouvea, F. Q.: p-adic Numbers – An introduction, Springer Verlag, 1997

[KLA95] Klapper, A.; Goresky, M.: Large Period Nearly deBruijn FCSR Sequences, in Advances in Cryptology – EUROCRYPT ’95, LNCS 921, pp.263 – 274, Springer Verlag, 1995

[KLA95a] Klapper, A.: Feedback with Carry Shift Registers over Finite Fields, in Fast Software Encryption, LNCS 1008, pp. 170-179, Springer Verlag,1995

[KLA97] Klapper, A.; Goresky, M.: Feedback shift registers, 2-adic span, and combiners with memory, in Journal of Cryptology, vol.10, pp. 111-147, 1997

[KOB77] Koblitz, N.: p-adic Numbers, p-adic Analysis, and Zeta-Functions, Springer Verlag, 1977

[KOB98] Koblitz, N.: Algebraic Aspects of Cryptography, Springer Verlag, 1998

[MAS69] Massey, J. M.: Shift-Register Synthesis and BCH Decoding, in IEEE Trans. Info. Theory, vol. IT-15, Jan 1969

[MEN01] Menezes, A. J.; van Oorschot, P. C.; Vanstone, S. A.: Handbook of Applied Cryptography, CRC Press, 2001

[NIE98] Niederreiter, H.: Some Computable Complexity Measures for Binary Sequences, in Proc. of SETA’98, pp. 67 – 78, 1998


[RIV78] Rivest, R. L.; Shamir, A.; Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, vol. 21(2), pp.120 − 126. February 1978

[RUE86] Rueppel, R.: Analysis and Design of Stream Ciphers, Springer Verlag, New York, 1986

[SCH96] Schneier, B.: Applied Cryptography (Second Edition): protocols, algorithms, and source code in C, John Wiley & Sons, Inc., 1996

[SEO00] Seo, C.; Lee, S.; Sung, Y.; Han, K.; Kim, S.: A Lower Bound on the Linear Span of an FCSR, in IEEE Trans. Info. Theory, vol. 46(2), pp. 691 – 693, March 2000

[WEL98] Welschenbach, M.: Kryptographie in C und C++, Springer Verlag, 1998

[WIK03] Wikipedia, the free encyclopedia, http://www.wikipedia.org/wiki/p-adic+numbers, 2003

List of Figures 68

List of Figures

Figure 1 Model of a synchronous stream cipher ...................................................................... 8

Figure 2 Model of a self-synchronous stream cipher ............................................................... 9

Figure 3 A linear feedback shift register ................................................................................ 11

Figure 4 A feedback carry shift register ................................................................................. 17

Figure 5 Linear complexity profiles........................................................................................ 24

Figure 6 2-adic span and complexity profiles......................................................................... 26

Figure 7 A nonlinear combining generator ............................................................................ 28

Figure 8 A nonlinear filter generator ..................................................................................... 29

Figure 9 The Geffe-generator ................................................................................................. 29

Figure 10 Linear complexity profil of an FCSR sequence with q = 179 ................................ 33

Figure 11 Autocorrelation function of the l-sequence with q = 67......................................... 34

Figure 12 Period of lp-Geffe-generators................................................................................. 36

Figure 13 Relative number of ones in lp-Geffe-generator-sequences ..................................... 37

Figure 14 Constellations for generating lp-Geffe-generator-sequences with complementary

period halves .......................................................................................................... 38

Figure 15 Relative frequency of the difference LDiff = |L((a,b,c)) – L((c,b,a))| ...................... 39

Figure 16 Linear complexity of lp-Geffe-generators for different register permutations ....... 40

Figure 17 Linear complexity of lp-Geffe-generators compared to the upper bound UBL~ ........ 41

Figure 18 Linear complexity of maximal-period lp-Geffe-generator-sequences compared to

the upper bound UBL~ ............................................................................................... 42

Figure 19 Relative error of the estimated linear complexity for maximal-period sequences. 42

Figure 20 Linear complexity of sequences with complementary period halves compared to

the upper bound UBL̂ ................................................................................................ 43

Figure 21 Relative difference of the linear complexity and the upper bound UBL̂ of sequences

with complementary period halves......................................................................... 44

Figure 22 Linear complexity profil of the lp-Geffe-generator-sequence with (q1 = 37, q2 = 53,

q3 = 59)................................................................................................................... 45

Figure 23 Autocorrelation functions of lp-Geffe-generator-sequences................................... 46

Figure 24 Relative frequency of maximal-period sequences generated by FCSRs with

composed connection integer ................................................................................. 51

List of Figures 69

Figure 25 Relative frequency of balanced sequences generated by FCSRs with composed

connection integer .................................................................................................. 51

Figure 26 Relative number of ones in sequences generated by FCSRs with connection

integers composed of 4 distinct 2-primes............................................................... 52

Figure 27 Relative frequency and probability of FCSR-sequences with Lα´ ≅ Tα´ ................. 57

Figure 28 Autocorrelation function of sequences generated by FCSRs with composed

connection integer .................................................................................................. 59

List of Tables 70

List of Tables

Table 1 The states of an FCSR with q = 19 ............................................................................ 21

Table 2 Rational approximation results.................................................................................. 26

Appendixes 71

Appendixes

A 1. List of 2-Primes

r q 1 3 2 5 3 11, 13 4 19, 29 5 37, 53, 59, 61 6 67, 83, 101, 107 7 131, 139, 149, 163, 173, 179, 181, 197, 211, 227 8 269, 293, 317, 347, 349, 373, 379, 389, 419, 421, 443, 461, 467, 491, 509

Note: ⎣ ⎦)1(log2 += qr is the length of the associated FCSR.

Appendixes 72

A 2. The Berlekamp-Massey Algorithm

Notation

• (a)(k) = (a0, a1, …, ak-1) := input sequence of length k • Li := linear complexity of (a)(i) • fi := connection polynomial for (a)(i) with minimum degree • coeff(f,j) := jth coefficient of f • deg(f) := degree of f

Algorithm BEGIN

{ input: (a)(k) = (a0, a1, …, ak−1) } f0 := f–1 := 1; L0 := L–1 := 0; FOR i:=0 TO k – 1

Li := deg(fi);

di := jiii

L

j

ajLfi

−=

⋅−∑ ),(coeff0

;

IF di = 0 THEN fi+1 := fi ; ELSE

max{ j | Lj < Lj+1 }; if { j | Lj < Lj+1 } ≠ ∅ m :=

−1; otherwise IF m – Lm ≥ i – Li THEN

fi+1 := ;)()(m

LiLmi fXf im −−−+

ELSE fi+1 := ;)()(

miLmLi ffX mi +−−−

END END

END END (adopted from [FUM94, p.143])

Appendixes 73

A 3. The Rational Approximation Algorithm

Notation

• (a)(k) = (a0, a1, …, ak-1) := input sequence of length k • f = (f1,f2) := integer pair • g = (g1,g2) := integer pair • Φ(p,q) = max(|p|,|q|)

Algorithm

BEGIN input aj’s until the first nonzero aj is found; α = aj ⋅ 2j ; f = (0,2); g = (2j ,1); FOR i:=j + 1 TO k – 1 input ai; α = α + ai ⋅ 2i; IF α ⋅ g2 – g1 ≡ 0 (mod 2i + 1) THEN f = 2f; ELSE IF Φ(g) < Φ(f) THEN Let d be odd and minimize Φ(f + dg); (*) ⟨g,f⟩ = ⟨f + dg,2g⟩; ELSE Let d be odd and minimize Φ(g + df); (**) ⟨g,f⟩ = ⟨g + df,2f⟩; END END END RETURN g END Comments

(*): Minimizing Φ(f + dg)

If g1 ≠ ±g2, then d is among the odd integers immediately less than or greater than (f1 – f2) / (g1 – g2) and –(f1 + f2) / (g1 + g2). If g1 = ±g2, one or the other of these quotients is not considered.

(**) Minimizing Φ(f + dg)

The same as in (*) but the roles of f and g are switched.

(adopted from [KLA97])

Appendixes 74

A 4. Linear complexity of FCSR sequences with 2-prime connection integer (q < 10000)

The table below lists only the cases where the linear complexity of the l-sequence is lower than the maximum of LUB = (q + 1)/2. For all remaining 2-prime connection integers q < 10000, the linear complexity is equal to that maximum LUB.

q L q L q L 291631973493734214915476597017098278538839411117117114992131

1280961711822072402723273483514084254364635545827471064

2221279728032843303730673517355735713613385139073931409942194261435743974789

1107139514001419151515221757177217781804192319511962204821082127217521962385

4957565957415779646966376709702772117477758977578429873188219181928394219859

2476282828652888323233173353351236033736378938764212436444084583464047074925

Appendixes 75

A 5. List of 2-prime Connection Integers for lp-Geffe-Generators Producing Sequences

with Complementary Period Halves (q ≤ 509)

Connection integers for register R1 and R3 (q ≤ 509)

r q 1 - 2 5 3 13 4 29 5 37, 53, 61 6 101 7 149, 173, 181, 197 8 269, 293, 317, 349, 373, 389, 421, 461, 509

Connection integers for register R2 (q ≤ 509)

r q 1 3 2 - 3 11 4 19 5 59 6 67, 83, 107 7 131, 139, 163, 179, 211, 227 8 347, 379, 419, 443, 467, 491

Note: ⎣ ⎦)1(log2 += qr is the length of the associated FCSR.

Documents

TU Dresden · TECHNISCHE UNIVERSITÄT DRESDEN Fakultät Elektrotechnik und Informationstechnik Institut für Nachrichtentechnik Lehrstuhl Theoretische Nachrichtentechnik Diplomarbeit