# Generalization of the Self-Shrinking Generator in the Galois FieldGF(pn)

Authors: Antoniya Todorova Tasheva; Zhaneta Nikolova Tasheva; Aleksandar Petrov Milev
Journal: Advances in Artificial Intelligence
 (2011)

---

## Abstract

The proposed by Meier and Staffelbach Self-Shrinking Generator (SSG) which has efficient hardware implementation only with a single Linear Feedback Shift Register is suitable for low-cost and fast stream cipher applications. In this paper we generalize the idea of the SSG for arbitrary Galois FieldGF(pn). The proposed variant of the SSG is called the p-ary Generalized Self-Shrinking Generator (pGSSG). We suggest a method for transformation of a non-binary self-shrunken pGSSG sequence into balanced binary sequence. We prove that the keystreams of the pGSSG have large period and good statistical properties. The analysis of the experimental results shows that the pGSSG sequences have good randomness properties. We examine the complexity of exhaustive search and entropy attacks of the pGSSG. We show that the pGSSG is more secure than SSG and Modified SSG against these attacks. We prove that the complexity of the used pGSSG attacks increases with increasing the prime p. Previously mentioned properties give the reason to say that the pGSSG satisfy the basic security requirements for a stream chipper and can be useful as a part of modern stream ciphers.


---

## Body

## 1. Introduction

The binary Pseudorandom Sequences (PRSs) with maximum period and good statistical and correlation properties have established themselves as foundation for generation of many signals used in modern communication and information systems. Among the most important applications [1, 2] of these signals are the Code Division Multiple Access (CDMA) systems, wireless networks, and communication systems where the multiple access interference is minimized. Generators of pseudorandom sequences for security at authorization process and stream cipher are other key areas of the PRSs implementation in different kinds of local and global networks.A great number of methods for generation of pseudorandom sequences are used in practice [3–13]. They are divided as linear and nonlinear [5]. Most linear methods such as Linear Congruent Generator, Multiplicative Linear Congruent Generator and Multiply Recursive Generator [5] cannot be used for ensuring the security and for information encryption in the communication network. Digital multi-step and formal series [5] can solve that problem but they are too slow because many steps are done recursive. In order to ensure practical stability of a chosen crypto-algorithm it is necessary to break the linearity in the generated linear sequence. It could be done by applying a nonlinear function over a part of the generated bits for additional allocation [5, 12]. The binary sequences with maximum period (m-sequences) are mainly used in many communication systems because of their properties such as uniformly allocation of the binary digits and the runs over its period and the ideal two-level autocorrelation. The main methods for generation of the m-sequences are Linear Feedback Shift Register (LFSR) which function is described by algebra in finite Galois field GF(2) and Feedback with Carry Shift Register (FCSR) where the algebra in finite 2-adic field is used.Self-shrinking generator [11] is a keystream generator used as a stream cipher. It is based on the shrinking principle [4, 14] and has remarkably low hardware requirements. So far, it has shown considerable resistance against cryptanalysis. The binary sequences generated by shrinking generator have very good encryption properties [4, 5, 9, 12, 15, 16].The self-shrinking generator (SSG) was proposed by Meier and Staffelbach at Euro-crypt'94 in [11]. It is a variant of the original Shrinking Generator given by Coppersmith et al. in [4]. This amazingly simple cipher, containing a single LFSR, has up to now surprisingly well-resisted all the known cryptographic attack techniques. In [17] Mihaljevic presented a faster attack with minimal time complexity O(20.5L) that needs a longer part of keystream sequence. It is shown that cryptanalysis is successful with high probability after 2L-l steps, l≤L/2, where l is l-bit section of the keystream and L is the key length. Since the procedure is done for L/4≤l≤L/2, the running time can vary from 20,5L in the very best case to 20,75L under more unfavorable circumstances. Later Zenner et al. improve the cryptanalysis of self-shrinking generator. The attack [18] is based on a backtracking algorithm and will reconstruct the key from a short sequence of known keystream bits. The algorithm takes at most O(20.694L) steps, where L is the key length.An attack on SSG requiring very small keystream data(2.41n) is the binary decision diagram (BDD) cryptanalysis proposed by Krause in [19] with time complexity O(20.656n) and equivalent memory complexity O(20.656n). The BBD-attack was improved in [20] with the same time complexity and only O(n2) memory complexity.The best tradeoff between time, memory and data complexity today is the new guess-and-determine cryptanalysis [21]. The time complexity of this attack is Ο(20.571n) and memory complexity O(n2) from Ο(20.194n) keystream bits for n<100, and time complexity O(20.556n) and memory complexity O(n2) from Ο(20.161n) keystream bits for n≥100.In this paper ap-ary generalized self-shrinking generator which produces nonbinary sequences is proposed. A method for transformation of nonbinary self-shrunken sequence into balance binary sequence is given.The paper is organized as follows. First, the basic principles of thep-ary LFSR are described. In Section 3 the function of the Self-Shrinking Generator is given. The working algorithm of the p-ary Generalized Self-Shrinking Generator for Galois Field GF(pn) is given in Section 4. Then the properties of the proposed pGSSG are discussed and analyzed. Finally, the security of the pGSSG against the exhaustive search and entropy attacks are analysed.


## 2. Basics Principles of thep-Ary LFSR

The basic principles of wide spread LFSR registers [5, 7, 10, 12] for GF(pn) when p is arbitrary prime will be given in this section.Real systems use pLSFR constructed in two different architectures Fibonachi and Galois. The properties of the finite Galois field [7, 22] are used.Definition 1.
Ifp is a prime then generated p-ary pseudorandom sequence (pPRS) consists of numbers 0÷p-1 and the appearance of every number is independent by the value of the previous and the following digits in the sequence.


### 2.1. pLFSR with Fibonachi Architecture

Definition 2.
p-ary LFSR with Fibonachi architecture and length L (Figure 1) consists of L stages (delay elements) ai, i=0,1,…,L-1, and one input and one output.Figure 1
pLFSR register with Fibonachi architecture.Every element can remember onep-ary number. The register is initialized by p-ary sequence (a0,a1,…,aL-1).During each clock cycle the following operations are performed.(1)
The content of stage 0 is output and forms part of the output sequence.(2)
The content of elementi is passed to element i-1 for each i, 1≤i≤L-1.(3)
A calculation of the linear recurrent dependency is done(1)an=∑i=1Lqian-imod⁡p,forn≥L
and its result is stored in the most left element of the register.The output sequence is described by (1) taking into consideration n≥L, the first L-1p-ary digits are eliminated from the output sequence.Every configuration of this architecture is defined by the feedback coefficientsqi, i=1,2,…,L. The generated output sequence A=(a0,a1,a2,…) is well defined for qL≠0 and the feedback polynomial
(2)q(x)=qLxL+qL-1xL-1+⋯+q1x-1.
Every infinite p-ary sequence A can be represented by its generating function(3)A(x)=∑i=0∞aixi
which is an element of the ring GF(p)[x] of the formal powers with coefficients in GF(p).The generated sequenceA is periodic only if the generating function A(x) could be represented as a quotient of two polynomials(4)A(x)=-h(x)q(x).
The generated sequence A is strictly periodic if the following condition is in effect:(5)deg⁡(h(x))<deg⁡(q(x)).
The reverse dependence is in effect as well. If B=(b0,b1,b2,…) is a strictly periodic sequence and B(x)=-h(x)/q(x) is its generating function then q(x) is a connection polynomial of the pLFSR which generates sequence B and a polynomial h(x) defines the initial state of the register by using
(6)h(x)=∑k=0L-1∑i=0kqiak-ixk.


### 2.2. pLFSR with Galois Architecture

Definition 3.
p-ary LFSR with Galois architecture and length L (Figure 2) consists of L delay elements ai, i=0,1,…,L-1, and one input and one output. The multipliers of the feedback are given as q1,q2,…,qL. Every element can remember one p-ary number. The register is initialized by p-ary sequence (a0,a1,…,aL-1).Figure 2
pLFSR register with Galois architecture.During each clock cycle the following operations are performed.(1)
The content of stage 0 is output and forms part of the output sequence.(2)
The content of elementi is passed to element i-1 for each i, 1≤i≤L-1, and the following recurrent dependencies are in effect
(7)ai′=(ai+1+qi+1a0)mod⁡p,0≤i≤L-2,aL-1′=qLa0mod⁡p.(3)
The output of the element 0 is implemented in every multiplier of feedbacks and a sum with the previous element by modulop is done.The Galois architecture of pLFSR is described by the feedback polynomialq(x) which is defined by (2) and the polynomial h(x)(8)h(x)=a0+a1x+⋯+aL-1xL-1
which is defined by the initial state of the register (a0,a1,…,aL-1).The generated output sequenceB=(b0,b1,b2,…) is a sequence of polynomial coefficients B(x)=-h(x)/q(x). The reverse statement for defining q(x) and initial state by using (8) is also in effect.


### 2.3. Properties of the pLFSR Sequences

One of the most important properties of the pLFSR is the maximal period [22] and it depends on the length of the registers L(9)T≤pL-1.
pPRS sequences which have a maximal period (mp-sequences) are used in cryptography and in communication systems for designing complex signals due to their good correlation properties. In order to generate mp-sequences it is necessary that the feedback polynomial q(x) of the pLFSR is primitive in extended Galois field GF(pL).The uniform allocation of thep-ary digits and their runs (series) is another important property. The following statements are true.(i)
The number of appearances of all nonzero elementsNj in maximal period T=pL-1 is Ni=pL-1 for i=1,2,…,p-1 and the number of zero elements is N0=pL-1-1.(ii)
Every nonzerop-ary runs (series) B with length s, 1≤s≤L appears in a period pL-s times and pL-s-1 times if it is zero.Figure3 shows the 3LFSR register with Galois architecture and length L=2. As one can see the output numbers 1 and 2 appear N1=N2=3 times in one period and the number of zeros is N0=2. All nonzero runs with length 2 appear only ones and zero run is not used.Figure 3
3LFSR register with Galois architecture and lengthL=2.


## 2.1. pLFSR with Fibonachi Architecture

Definition 2.
p-ary LFSR with Fibonachi architecture and length L (Figure 1) consists of L stages (delay elements) ai, i=0,1,…,L-1, and one input and one output.Figure 1
pLFSR register with Fibonachi architecture.Every element can remember onep-ary number. The register is initialized by p-ary sequence (a0,a1,…,aL-1).During each clock cycle the following operations are performed.(1)
The content of stage 0 is output and forms part of the output sequence.(2)
The content of elementi is passed to element i-1 for each i, 1≤i≤L-1.(3)
A calculation of the linear recurrent dependency is done(1)an=∑i=1Lqian-imod⁡p,forn≥L
and its result is stored in the most left element of the register.The output sequence is described by (1) taking into consideration n≥L, the first L-1p-ary digits are eliminated from the output sequence.Every configuration of this architecture is defined by the feedback coefficientsqi, i=1,2,…,L. The generated output sequence A=(a0,a1,a2,…) is well defined for qL≠0 and the feedback polynomial
(2)q(x)=qLxL+qL-1xL-1+⋯+q1x-1.
Every infinite p-ary sequence A can be represented by its generating function(3)A(x)=∑i=0∞aixi
which is an element of the ring GF(p)[x] of the formal powers with coefficients in GF(p).The generated sequenceA is periodic only if the generating function A(x) could be represented as a quotient of two polynomials(4)A(x)=-h(x)q(x).
The generated sequence A is strictly periodic if the following condition is in effect:(5)deg⁡(h(x))<deg⁡(q(x)).
The reverse dependence is in effect as well. If B=(b0,b1,b2,…) is a strictly periodic sequence and B(x)=-h(x)/q(x) is its generating function then q(x) is a connection polynomial of the pLFSR which generates sequence B and a polynomial h(x) defines the initial state of the register by using
(6)h(x)=∑k=0L-1∑i=0kqiak-ixk.


## 2.2. pLFSR with Galois Architecture

Definition 3.
p-ary LFSR with Galois architecture and length L (Figure 2) consists of L delay elements ai, i=0,1,…,L-1, and one input and one output. The multipliers of the feedback are given as q1,q2,…,qL. Every element can remember one p-ary number. The register is initialized by p-ary sequence (a0,a1,…,aL-1).Figure 2
pLFSR register with Galois architecture.During each clock cycle the following operations are performed.(1)
The content of stage 0 is output and forms part of the output sequence.(2)
The content of elementi is passed to element i-1 for each i, 1≤i≤L-1, and the following recurrent dependencies are in effect
(7)ai′=(ai+1+qi+1a0)mod⁡p,0≤i≤L-2,aL-1′=qLa0mod⁡p.(3)
The output of the element 0 is implemented in every multiplier of feedbacks and a sum with the previous element by modulop is done.The Galois architecture of pLFSR is described by the feedback polynomialq(x) which is defined by (2) and the polynomial h(x)(8)h(x)=a0+a1x+⋯+aL-1xL-1
which is defined by the initial state of the register (a0,a1,…,aL-1).The generated output sequenceB=(b0,b1,b2,…) is a sequence of polynomial coefficients B(x)=-h(x)/q(x). The reverse statement for defining q(x) and initial state by using (8) is also in effect.


## 2.3. Properties of the pLFSR Sequences

One of the most important properties of the pLFSR is the maximal period [22] and it depends on the length of the registers L(9)T≤pL-1.
pPRS sequences which have a maximal period (mp-sequences) are used in cryptography and in communication systems for designing complex signals due to their good correlation properties. In order to generate mp-sequences it is necessary that the feedback polynomial q(x) of the pLFSR is primitive in extended Galois field GF(pL).The uniform allocation of thep-ary digits and their runs (series) is another important property. The following statements are true.(i)
The number of appearances of all nonzero elementsNj in maximal period T=pL-1 is Ni=pL-1 for i=1,2,…,p-1 and the number of zero elements is N0=pL-1-1.(ii)
Every nonzerop-ary runs (series) B with length s, 1≤s≤L appears in a period pL-s times and pL-s-1 times if it is zero.Figure3 shows the 3LFSR register with Galois architecture and length L=2. As one can see the output numbers 1 and 2 appear N1=N2=3 times in one period and the number of zeros is N0=2. All nonzero runs with length 2 appear only ones and zero run is not used.Figure 3
3LFSR register with Galois architecture and lengthL=2.


## 3. Nonbinary Self-Shrinking Generator

### 3.1. Basics of Shrinking Generators

The shrinking generator [4, 9] consists of two Linear Feedback Shift Registers (LFSR) A and B generating the m-sequences (ai)i≥0 (denoted as A sequence) and (bi)i≥0 (denoted as B sequence), respectively. The keystream sequence (zj)j≥0 is constructed from these two sequences according to the following selection rule: for every clock i, consider the selection bit bi. If bi=1, the output is ai. Otherwise, discard both bi and ai. This way, a nonlinear keystream is generated. Even a cryptanalyst who knows part of the keystream sequence cannot tell easily which (zj)j≥0 corresponds to which ai, since the length of the gaps (i.e., the number of ai that has been discarded) is unknown. In [4, 14] the shrinking generator is shown to have good algebraic and statistical properties. It is shown that the number of attacks that could reconstruct the initial state of A and B increases and requires exponential running time in the length of |B| register (LFSR B).The self-shrinking generator is a modified version of the shrinking generator and was first presented by Meier and Staffelbach in [11].The self-shrinking generator requires only one LFSRA, whose length will be denoted by L. The LFSR generates an m-sequence (ai)i≥0. The selection rule is the same as for shrinking generator, using the even bits a0,a2,a4,… as B-bits and the odd bits a1,a3,a5,…  as A-bits in the above sense. Thus, the self-shrinking rule requires a couple (a2i,a2i+1) as input and outputs a2i+1 if a2i=1.The close relationship between shrinking and self-shrinking generator is shown in Figure4.Shrinking and self-shrinking generator.
(a)(b)In [12] an algorithm is given that transforms an L-bit self-shrinking generator into a 2L-bit shrinking generator. It is also shown that a shrinking generator with register lengths |A| and |B| has an equivalent self-shrinking generator of length L=2·(|A|+|B|). Despite this similarity, the self-shrinking generator has shown even more resistance to cryptanalysis than the shrinking generator [18].


### 3.2.p-ary Generalized Self-Shrinking Generator

The proposedp-ary generalized Self-Shrinking Generator (pGSSG), given in Figure 4, consists of a pLFSR generator A, whose length will be denoted by L. It generates sequence (ai)i≥0 with p-ary digits (i.e., (ai)i≥0, 0≤ai≤p-1) and 0≤i≤L-1. The multipliers of the feedbacks are given by coefficients q1,q2,…,qL, qL∈[0,1,…,p-1] of the primitive polynomial in GF(pL). Every element can remember one p-ary number. The register is initialized by p-ary sequence (a0,a1,…,aL-1).The pGSSG selects a portion of the outputp-ary LFSR sequence by controlling the p-ary LFSR itself using the following algorithm.Definition 4.
The algorithm of thep-ary Generalized Self-Shrinking Generator (Figure 5) consists of the following steps.(1)
Thep-ary LFSR is clocked with clock sequence with period T.(2)
The output pLFSR sequence is split intop-tuples api,api+1,api+2,…,api+(p-1), i=0,1,….(3)
Ifapi=0 the whole p-tuple is discarded from the GSSG output, that is, the output is shrunken.(4)
Whenapi≠0, the corresponding digit api+api in the p-tuple forms the output of the GSSG. For example, if api=1, then api+1 is output and the other digits api,api+2,…,api+(p-1) are discard. If api=2, then api+2 is output and the other digits api,api+1,api+3,…,api+(p-1) are discard and so on. If api=p-1, then api+(p-1) is output and the other digits api,api+1,…,api+(p-2) are discard.(5)
The shrunkenp-ary GSSG output sequence is transformed into binary sequence in which every p-ary number is presented with ⌈log2(p-1)⌉ binary digits, where ⌈x⌉ is the smallest integer which is greater or equal to x. Every output number i from 1 to p-1 of p-ary GSSG sequence is depicted with p-ary expansion of the number:
(10)(i-1)+2⌈log2p-1⌉-p-12.
For example the transformation of every p-ary digit for p=3,5,7,11,13 is done according to the Table 1.(6)
Everyp-ary zero in its i appearance (i=1,2,3,…) of the generated p-ary sequence can be represented binary by number di,
(11)di={(di-1+1)mod⁡pifdi-1<p-11ifdi-1=p-1
and initial condition d0=0.Table 1
Binary transformation ofp-ary digit.
p-ary numberBinary presentation ofp-ary digitp=3p=5p=7p=11p=131000001001100102101010010000113—10011010101004—11100011001015——101011101106——110100001117———100110008———101010019———1011101010———1100101111————110012————1101Figure 5
p-ary Generalized Self-Shrinking Geneator.


### 3.3. Examples

#### 3.3.1. 3GSSG

Let us chose Extended Galois fieldGF(33) and the primitive polynomial that generates GF(33) is a3+2a2+1. Then the corresponding pLFSR (i.e., 3LFSR) will be as shown in Figure 6.Figure 6
3LFSR forGF(33) and primitive polynomial a3+2a2+1.The feedback polynomial isq(x)=2x3+x2-1 and all algebraic function is done modulo p (i.e., p=3).Let the initial state be[a2,a1,a0]=[0,0,1].For all possible 3-tuples generated by the 3LFSR the 3GSSG output for a period will be[011120210220022110] and the way of its derivation according to the given algorithm is shown in Table 2.Table 2
Output of the 3GSSG.
3-tupleOutput  (binary)3-tupleOutput  (binary)3-tupleOutput  (binary)1010(0)2111(0)2011(0)1101(0)0202122(1)2100(1)2222(1)0010121121(0)0111000(0)2022(1)1222(1)1020(1)2200(0)0101212(1)1202(1)1111(0)0020212211(0)0222000(1)The period of sequence isT=18. The output is chosen from the value of the first symbol of 3-tuple, which defines which symbol forms the 3GSSG output. It is pointed out by the bold digits. Then the 3-ary output sequence is transformed into binary by the rules 5 and 6 in the pGSSG algorithm for p=3 given in Table 1.The binary output is given in the brackets in Table2.


#### 3.3.2. 5GSSG

Let us chose Extended Galois fieldGF(53) and primitive polynomial is a3+3a2+2. The corresponding pLFSR (i.e., 5LFSR) is shown in Figure 7.Figure 7
3LFSR forGF(53) and primitive polynomial a3+3a2+2.The feedback polynomial isq(x)=2x3+x2-1 and all algebraic function is done modulo 5 (i.e., p=5).Let the initial state be[a2,a1,a0]=[1,1,0].For a part of all possible 5-tuples generated by the 5LFSR the output of the 5SSG generator for a part of period will be[01422213100342201230103404012000]. The way of its derivation according to the given algorithm is shown in Table 3.Table 3
Output of the 5GSSG.
5-tupleOutput  (binary)5-tupleOutput  (binary)5-tupleOutput  (binary)102220(00)110321(00)332434(11)314212(01)00202423022(01)120442(01)422011(00)411433(10)112341(00)200400(11)434100(10)424033(10)334404(11)232232(01)122412(01)340030(00)0313203430111331(00)04144124432(01)213003(10)101210(11)401311(00)02221103230(00)324333(10)142104(11)02024230210(01)204444(11)220140(01)114311(00)123422(01)00404341040(10)240330(01)344020(10)The period isT=100. The output is chosen from the value of the first symbol of 5-tuple, which defines which position symbol from this point to be selected to exit. Finally the 5-ary output sequence is transformed into binary by the rules 5 and 6 in the pGSSG algorithm for p=5 given in Table 1. The binary output is given in the brackets in Table 3.


## 3.1. Basics of Shrinking Generators

The shrinking generator [4, 9] consists of two Linear Feedback Shift Registers (LFSR) A and B generating the m-sequences (ai)i≥0 (denoted as A sequence) and (bi)i≥0 (denoted as B sequence), respectively. The keystream sequence (zj)j≥0 is constructed from these two sequences according to the following selection rule: for every clock i, consider the selection bit bi. If bi=1, the output is ai. Otherwise, discard both bi and ai. This way, a nonlinear keystream is generated. Even a cryptanalyst who knows part of the keystream sequence cannot tell easily which (zj)j≥0 corresponds to which ai, since the length of the gaps (i.e., the number of ai that has been discarded) is unknown. In [4, 14] the shrinking generator is shown to have good algebraic and statistical properties. It is shown that the number of attacks that could reconstruct the initial state of A and B increases and requires exponential running time in the length of |B| register (LFSR B).The self-shrinking generator is a modified version of the shrinking generator and was first presented by Meier and Staffelbach in [11].The self-shrinking generator requires only one LFSRA, whose length will be denoted by L. The LFSR generates an m-sequence (ai)i≥0. The selection rule is the same as for shrinking generator, using the even bits a0,a2,a4,… as B-bits and the odd bits a1,a3,a5,…  as A-bits in the above sense. Thus, the self-shrinking rule requires a couple (a2i,a2i+1) as input and outputs a2i+1 if a2i=1.The close relationship between shrinking and self-shrinking generator is shown in Figure4.Shrinking and self-shrinking generator.
(a)(b)In [12] an algorithm is given that transforms an L-bit self-shrinking generator into a 2L-bit shrinking generator. It is also shown that a shrinking generator with register lengths |A| and |B| has an equivalent self-shrinking generator of length L=2·(|A|+|B|). Despite this similarity, the self-shrinking generator has shown even more resistance to cryptanalysis than the shrinking generator [18].


## 3.2.p-ary Generalized Self-Shrinking Generator

The proposedp-ary generalized Self-Shrinking Generator (pGSSG), given in Figure 4, consists of a pLFSR generator A, whose length will be denoted by L. It generates sequence (ai)i≥0 with p-ary digits (i.e., (ai)i≥0, 0≤ai≤p-1) and 0≤i≤L-1. The multipliers of the feedbacks are given by coefficients q1,q2,…,qL, qL∈[0,1,…,p-1] of the primitive polynomial in GF(pL). Every element can remember one p-ary number. The register is initialized by p-ary sequence (a0,a1,…,aL-1).The pGSSG selects a portion of the outputp-ary LFSR sequence by controlling the p-ary LFSR itself using the following algorithm.Definition 4.
The algorithm of thep-ary Generalized Self-Shrinking Generator (Figure 5) consists of the following steps.(1)
Thep-ary LFSR is clocked with clock sequence with period T.(2)
The output pLFSR sequence is split intop-tuples api,api+1,api+2,…,api+(p-1), i=0,1,….(3)
Ifapi=0 the whole p-tuple is discarded from the GSSG output, that is, the output is shrunken.(4)
Whenapi≠0, the corresponding digit api+api in the p-tuple forms the output of the GSSG. For example, if api=1, then api+1 is output and the other digits api,api+2,…,api+(p-1) are discard. If api=2, then api+2 is output and the other digits api,api+1,api+3,…,api+(p-1) are discard and so on. If api=p-1, then api+(p-1) is output and the other digits api,api+1,…,api+(p-2) are discard.(5)
The shrunkenp-ary GSSG output sequence is transformed into binary sequence in which every p-ary number is presented with ⌈log2(p-1)⌉ binary digits, where ⌈x⌉ is the smallest integer which is greater or equal to x. Every output number i from 1 to p-1 of p-ary GSSG sequence is depicted with p-ary expansion of the number:
(10)(i-1)+2⌈log2p-1⌉-p-12.
For example the transformation of every p-ary digit for p=3,5,7,11,13 is done according to the Table 1.(6)
Everyp-ary zero in its i appearance (i=1,2,3,…) of the generated p-ary sequence can be represented binary by number di,
(11)di={(di-1+1)mod⁡pifdi-1<p-11ifdi-1=p-1
and initial condition d0=0.Table 1
Binary transformation ofp-ary digit.
p-ary numberBinary presentation ofp-ary digitp=3p=5p=7p=11p=131000001001100102101010010000113—10011010101004—11100011001015——101011101106——110100001117———100110008———101010019———1011101010———1100101111————110012————1101Figure 5
p-ary Generalized Self-Shrinking Geneator.


## 3.3. Examples

### 3.3.1. 3GSSG

Let us chose Extended Galois fieldGF(33) and the primitive polynomial that generates GF(33) is a3+2a2+1. Then the corresponding pLFSR (i.e., 3LFSR) will be as shown in Figure 6.Figure 6
3LFSR forGF(33) and primitive polynomial a3+2a2+1.The feedback polynomial isq(x)=2x3+x2-1 and all algebraic function is done modulo p (i.e., p=3).Let the initial state be[a2,a1,a0]=[0,0,1].For all possible 3-tuples generated by the 3LFSR the 3GSSG output for a period will be[011120210220022110] and the way of its derivation according to the given algorithm is shown in Table 2.Table 2
Output of the 3GSSG.
3-tupleOutput  (binary)3-tupleOutput  (binary)3-tupleOutput  (binary)1010(0)2111(0)2011(0)1101(0)0202122(1)2100(1)2222(1)0010121121(0)0111000(0)2022(1)1222(1)1020(1)2200(0)0101212(1)1202(1)1111(0)0020212211(0)0222000(1)The period of sequence isT=18. The output is chosen from the value of the first symbol of 3-tuple, which defines which symbol forms the 3GSSG output. It is pointed out by the bold digits. Then the 3-ary output sequence is transformed into binary by the rules 5 and 6 in the pGSSG algorithm for p=3 given in Table 1.The binary output is given in the brackets in Table2.


### 3.3.2. 5GSSG

Let us chose Extended Galois fieldGF(53) and primitive polynomial is a3+3a2+2. The corresponding pLFSR (i.e., 5LFSR) is shown in Figure 7.Figure 7
3LFSR forGF(53) and primitive polynomial a3+3a2+2.The feedback polynomial isq(x)=2x3+x2-1 and all algebraic function is done modulo 5 (i.e., p=5).Let the initial state be[a2,a1,a0]=[1,1,0].For a part of all possible 5-tuples generated by the 5LFSR the output of the 5SSG generator for a part of period will be[01422213100342201230103404012000]. The way of its derivation according to the given algorithm is shown in Table 3.Table 3
Output of the 5GSSG.
5-tupleOutput  (binary)5-tupleOutput  (binary)5-tupleOutput  (binary)102220(00)110321(00)332434(11)314212(01)00202423022(01)120442(01)422011(00)411433(10)112341(00)200400(11)434100(10)424033(10)334404(11)232232(01)122412(01)340030(00)0313203430111331(00)04144124432(01)213003(10)101210(11)401311(00)02221103230(00)324333(10)142104(11)02024230210(01)204444(11)220140(01)114311(00)123422(01)00404341040(10)240330(01)344020(10)The period isT=100. The output is chosen from the value of the first symbol of 5-tuple, which defines which position symbol from this point to be selected to exit. Finally the 5-ary output sequence is transformed into binary by the rules 5 and 6 in the pGSSG algorithm for p=5 given in Table 1. The binary output is given in the brackets in Table 3.


## 3.3.1. 3GSSG

Let us chose Extended Galois fieldGF(33) and the primitive polynomial that generates GF(33) is a3+2a2+1. Then the corresponding pLFSR (i.e., 3LFSR) will be as shown in Figure 6.Figure 6
3LFSR forGF(33) and primitive polynomial a3+2a2+1.The feedback polynomial isq(x)=2x3+x2-1 and all algebraic function is done modulo p (i.e., p=3).Let the initial state be[a2,a1,a0]=[0,0,1].For all possible 3-tuples generated by the 3LFSR the 3GSSG output for a period will be[011120210220022110] and the way of its derivation according to the given algorithm is shown in Table 2.Table 2
Output of the 3GSSG.
3-tupleOutput  (binary)3-tupleOutput  (binary)3-tupleOutput  (binary)1010(0)2111(0)2011(0)1101(0)0202122(1)2100(1)2222(1)0010121121(0)0111000(0)2022(1)1222(1)1020(1)2200(0)0101212(1)1202(1)1111(0)0020212211(0)0222000(1)The period of sequence isT=18. The output is chosen from the value of the first symbol of 3-tuple, which defines which symbol forms the 3GSSG output. It is pointed out by the bold digits. Then the 3-ary output sequence is transformed into binary by the rules 5 and 6 in the pGSSG algorithm for p=3 given in Table 1.The binary output is given in the brackets in Table2.


## 3.3.2. 5GSSG

Let us chose Extended Galois fieldGF(53) and primitive polynomial is a3+3a2+2. The corresponding pLFSR (i.e., 5LFSR) is shown in Figure 7.Figure 7
3LFSR forGF(53) and primitive polynomial a3+3a2+2.The feedback polynomial isq(x)=2x3+x2-1 and all algebraic function is done modulo 5 (i.e., p=5).Let the initial state be[a2,a1,a0]=[1,1,0].For a part of all possible 5-tuples generated by the 5LFSR the output of the 5SSG generator for a part of period will be[01422213100342201230103404012000]. The way of its derivation according to the given algorithm is shown in Table 3.Table 3
Output of the 5GSSG.
5-tupleOutput  (binary)5-tupleOutput  (binary)5-tupleOutput  (binary)102220(00)110321(00)332434(11)314212(01)00202423022(01)120442(01)422011(00)411433(10)112341(00)200400(11)434100(10)424033(10)334404(11)232232(01)122412(01)340030(00)0313203430111331(00)04144124432(01)213003(10)101210(11)401311(00)02221103230(00)324333(10)142104(11)02024230210(01)204444(11)220140(01)114311(00)123422(01)00404341040(10)240330(01)344020(10)The period isT=100. The output is chosen from the value of the first symbol of 5-tuple, which defines which position symbol from this point to be selected to exit. Finally the 5-ary output sequence is transformed into binary by the rules 5 and 6 in the pGSSG algorithm for p=5 given in Table 1. The binary output is given in the brackets in Table 3.


## 4. Properties of the pGSSG Output Sequence

The research of thep-ary GSSG has been modeled with Visual C++. To analyze the properties of the p-ary GSSG output sequence have been made more than 1000 tests with prime p up to 257 and various primitive feedback polynomials and initial states.In this section first the pGSSG period is established. Then is proven that the output pGSSG sequence is balanced, that is, the number of 1s and 0s are equal in a period of pGSSG sequence. In Section4.3 the minimum length of the used pLFSR registers to guarantee a key length of 512 and 1024 bits, which is useful for cryptographic applications nowadays, is calculated. Finally the good randomness properties of the pGSSG output sequences are proven by the results of the statistical NIST test suite.


### 4.1. Period of pGSSG

Hence ap-ary LFSR sequence is with period T=pL-1 then the pGSSG output sequence also is periodic. In fact after p(pL-1) bits of the original sequence, the sequence of p-tuples api,api+1,api+2,…,api+(p-1) has been processed and the next p-tuple will be the same as first a0,a1,a2,…,ap-1. As is well known, the p-tuples occurs balanced in one pm-sequence period. Therefore 1/p of all  p-tuples will begin with bit 0,1/p of all will begin with 1 and so on 1/p of all will begin with p-1. Thus the pL-1  p-tuples will be discarding because they begin with 0 bit. Remaining (p-1)pL-1  p-tuples will produce an one bit in the output sequence because this p-tuples begin with nonzero bits. Consequently the period of the p-ary GSSG output sequence will be(12)TpGSSG=(p-1)pL-1p-ary digits.When pGSSG output sequence is transformed into balanced binary sequence the period will be(13)T2GSSG=TpGSSG⌈log⁡2(p-1)⌉
bits.


### 4.2. Number of Elements inp-Ary GSSG Sequence

Since thepm-sequence, produced by the p-ary LFSR is balanced and the pGSSG output sequence also is balanced the number of the each elements 0,1,…,p-1 is equal to(14)Ni=(p-1)pL-2,i=0,1,…,p-1.
After binary transformation the balanced property is in fact also, thus the number of zeros and ones are equal to(15)Nb0=Nb1=(p-1)pL-2⋅⌈log⁡2(p-1)⌉.
The experimental results for different pGSSG and their parameters are given in Table 4.Table 4
Results for simulated 3GSSG and 5GSSG.
GF(pn)Primitive polynomialTpLFSRTpGSSGN0N1N2N3N4T2GSSGNb0Nb1GF(33)a3 + 2a2 + 126186661899GF(34)a4 + 2a3 + 28054181818542727GF(35)a5 + 2a2 + a + 12421625454541628181GF(35)a5 + 2a + 12421625454541628181GF(36)a6 + a + 2728486162162162486243243GF(37)a7 + a2 + 2a + 1218614584864864861458729729GF(53)a3 + 3a2 + 21241002020202020200100100GF(54)a4 + a2  + 2a + 36245001001001001001001000500500GF(55)a5 + 4a + 231242500500500500500500500025002500GF(56)a6 + a + 2156241250025002500250025002500250001250012500GF(57)a7 + 3a + 2781246250012500125001250012500125001250006250062500


### 4.3. Key for Encryption

The encryption key for thepGSSG is an initial state (a0,a1,…,aL-1) of the pLFSR register. Thus the encryption key will be long Lp-ary digits.Onep-ary digit may be presented by ⌊log2p⌋ bits, where ⌊x⌋ denote the smallest integer greater and equal to x. Consequently length of the encryption key is(16)LKey=L⋅⌊log⁡2⁡p⌋.
As one can see the greater p is the longer the key is. Table 5 shows the minimum length of the used pLFSR register to guarantee a key length of 512 and 1024 bits, which are useful for cryptographic applications nowadays.Table 5
Minimum length of pLFSR to guarantee a given min key length.
pLmin for key length512 bits1024 bits2512102432565125, 717134211, 1312825617, 19, 23, 29, 3110320537, 41, 43, 47, 53, 59, 618617167, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 12774147131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 25164128


### 4.4. Statistical Properties

To test statistical properties of the keystreams generated by the pGSSG with primep up to 257, 1000 sequences of length 106 have been tested by the National Institute of Standards and Technology (NIST) statistical test suite [23]. Table 6 shows the NIST test results for two sets of 100 keystreams each of length 106 for p=17 and p=257. To generate these 100 keystreams randomly chosen primitive polynomials and initial states are used.Table 6
Results from the NIST test suite for two sets of 100 keystreams of length 106, generated by the pGSSG.
NIST Statistical Test17GSSG257GSSGP-valuePass rateP-valuePass rateFrequency.7981390.990000.9558351.000000Block-frequency.3345380.990000.8343080.980000Cumulative-sums 1.6371190.990000.2896671.000000Cumulative-sums 2.8513830.990000.5955491.000000Runs.0308061.000000.8676921.000000Longest-run.8676920.970000.1626060.980000Rank.1718671.000000.4372741.000000FFT.5749031.000000.1916870.990000Nonperiodic-templates*.4785120.988784.5049900.990676Overlapping-templates.0965780.990000.3345380.990000Universal.2133091.000000.1296201.000000Apen.0002300.960000.9114131.000000Random-excursions**.2465910.993663.5641580.993738Random-excursions-variant***.2692480.992489.4796770.996289Serial 1.0965781.000000.4372740.990000Serial 2.8513831.000000.5749030.990000Lempel-ziv.0126500.990000.0251930.980000Linear-complexity.7399180.990000.9716990.970000*The given values are average of the all 148 nonperiodic-templates NIST tests.**The given values are average of the all 8 random-excursions NIST tests.***The given values are average of the all 48 random-excursions-variant NIST tests.The results demonstrate that pGSSG keystreams have good randomness properties, that is, they are well balanced, uniform, scalable and uncompressible.


### 4.5. Implementation

Unfortunately, the hardware implementation of the pGSSG is not as simple as the original SSG, because the algebraic operations are performed in theGF(p), p≥3. It takes ⌊log2p⌋ triggers to present one p-ary number. Hardware accelerators can perform the computationally intensive operations far quicker. Field-Programmable Gate Arrays (FPGAs) are well-suited for this application due to their reconfigurability and versatility.The pGSSG is more suitable for software implementation. The cases withp=17 and p=257 are particularly suitable, because the binary output of the generator produces 4 or 8 bits at a time, respectively.


## 4.1. Period of pGSSG

Hence ap-ary LFSR sequence is with period T=pL-1 then the pGSSG output sequence also is periodic. In fact after p(pL-1) bits of the original sequence, the sequence of p-tuples api,api+1,api+2,…,api+(p-1) has been processed and the next p-tuple will be the same as first a0,a1,a2,…,ap-1. As is well known, the p-tuples occurs balanced in one pm-sequence period. Therefore 1/p of all  p-tuples will begin with bit 0,1/p of all will begin with 1 and so on 1/p of all will begin with p-1. Thus the pL-1  p-tuples will be discarding because they begin with 0 bit. Remaining (p-1)pL-1  p-tuples will produce an one bit in the output sequence because this p-tuples begin with nonzero bits. Consequently the period of the p-ary GSSG output sequence will be(12)TpGSSG=(p-1)pL-1p-ary digits.When pGSSG output sequence is transformed into balanced binary sequence the period will be(13)T2GSSG=TpGSSG⌈log⁡2(p-1)⌉
bits.


## 4.2. Number of Elements inp-Ary GSSG Sequence

Since thepm-sequence, produced by the p-ary LFSR is balanced and the pGSSG output sequence also is balanced the number of the each elements 0,1,…,p-1 is equal to(14)Ni=(p-1)pL-2,i=0,1,…,p-1.
After binary transformation the balanced property is in fact also, thus the number of zeros and ones are equal to(15)Nb0=Nb1=(p-1)pL-2⋅⌈log⁡2(p-1)⌉.
The experimental results for different pGSSG and their parameters are given in Table 4.Table 4
Results for simulated 3GSSG and 5GSSG.
GF(pn)Primitive polynomialTpLFSRTpGSSGN0N1N2N3N4T2GSSGNb0Nb1GF(33)a3 + 2a2 + 126186661899GF(34)a4 + 2a3 + 28054181818542727GF(35)a5 + 2a2 + a + 12421625454541628181GF(35)a5 + 2a + 12421625454541628181GF(36)a6 + a + 2728486162162162486243243GF(37)a7 + a2 + 2a + 1218614584864864861458729729GF(53)a3 + 3a2 + 21241002020202020200100100GF(54)a4 + a2  + 2a + 36245001001001001001001000500500GF(55)a5 + 4a + 231242500500500500500500500025002500GF(56)a6 + a + 2156241250025002500250025002500250001250012500GF(57)a7 + 3a + 2781246250012500125001250012500125001250006250062500


## 4.3. Key for Encryption

The encryption key for thepGSSG is an initial state (a0,a1,…,aL-1) of the pLFSR register. Thus the encryption key will be long Lp-ary digits.Onep-ary digit may be presented by ⌊log2p⌋ bits, where ⌊x⌋ denote the smallest integer greater and equal to x. Consequently length of the encryption key is(16)LKey=L⋅⌊log⁡2⁡p⌋.
As one can see the greater p is the longer the key is. Table 5 shows the minimum length of the used pLFSR register to guarantee a key length of 512 and 1024 bits, which are useful for cryptographic applications nowadays.Table 5
Minimum length of pLFSR to guarantee a given min key length.
pLmin for key length512 bits1024 bits2512102432565125, 717134211, 1312825617, 19, 23, 29, 3110320537, 41, 43, 47, 53, 59, 618617167, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 12774147131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 25164128


## 4.4. Statistical Properties

To test statistical properties of the keystreams generated by the pGSSG with primep up to 257, 1000 sequences of length 106 have been tested by the National Institute of Standards and Technology (NIST) statistical test suite [23]. Table 6 shows the NIST test results for two sets of 100 keystreams each of length 106 for p=17 and p=257. To generate these 100 keystreams randomly chosen primitive polynomials and initial states are used.Table 6
Results from the NIST test suite for two sets of 100 keystreams of length 106, generated by the pGSSG.
NIST Statistical Test17GSSG257GSSGP-valuePass rateP-valuePass rateFrequency.7981390.990000.9558351.000000Block-frequency.3345380.990000.8343080.980000Cumulative-sums 1.6371190.990000.2896671.000000Cumulative-sums 2.8513830.990000.5955491.000000Runs.0308061.000000.8676921.000000Longest-run.8676920.970000.1626060.980000Rank.1718671.000000.4372741.000000FFT.5749031.000000.1916870.990000Nonperiodic-templates*.4785120.988784.5049900.990676Overlapping-templates.0965780.990000.3345380.990000Universal.2133091.000000.1296201.000000Apen.0002300.960000.9114131.000000Random-excursions**.2465910.993663.5641580.993738Random-excursions-variant***.2692480.992489.4796770.996289Serial 1.0965781.000000.4372740.990000Serial 2.8513831.000000.5749030.990000Lempel-ziv.0126500.990000.0251930.980000Linear-complexity.7399180.990000.9716990.970000*The given values are average of the all 148 nonperiodic-templates NIST tests.**The given values are average of the all 8 random-excursions NIST tests.***The given values are average of the all 48 random-excursions-variant NIST tests.The results demonstrate that pGSSG keystreams have good randomness properties, that is, they are well balanced, uniform, scalable and uncompressible.


## 4.5. Implementation

Unfortunately, the hardware implementation of the pGSSG is not as simple as the original SSG, because the algebraic operations are performed in theGF(p), p≥3. It takes ⌊log2p⌋ triggers to present one p-ary number. Hardware accelerators can perform the computationally intensive operations far quicker. Field-Programmable Gate Arrays (FPGAs) are well-suited for this application due to their reconfigurability and versatility.The pGSSG is more suitable for software implementation. The cases withp=17 and p=257 are particularly suitable, because the binary output of the generator produces 4 or 8 bits at a time, respectively.


## 5. Cryptanalysis

The goal of the stream cipher attack based on a clock controlled generators is to recover the secret key that includes the initial state of the used LFSRs. For better security the key may contain the feedback polynomial of the LFSRs. In this section, the security of the pGSSG against the exhaustive search and entropy attacks are analysed.The suggested from Maier and Staffelbach two general attacks named exhaustive search attack and entropy attack [11] recover the initial state of the SSG from the knowledge of the short segment of the generated keystream requiring respectively O(20.79n) and O(20.75n) computational steps.In these attacks we assume that the secret key consists only of the initial state of thep-ary GSSG.


### 5.1. Exhaustive Search Attack

Letz0,z1,z2,… be a known portion of the binary keystream generated by pGSSG. As the prime p is also known the attacker can divide it by ⌈log2p-1⌉ bits. Each portion of ⌈log2p-1⌉ bits presents one p-ary number.Let thenb0,b1,b2,… be a known p-ary portion of the pGSSG. The p-ary number bj for some j is generated by the p-tuple ai,ai+1,ai+2,…,ai+(p-1) of the output pLFSR sequence a0,a1,a2,…, ai∈[0,1,…,p-1], where the index i is unknown.From the knowledge of the firstp-ary number b0 one can conclude that for the first p-tuple there is p-1 possible cases:(17)1,b0,ai+2,…,ai+(p-1),2,ai+1,b0,…,ai+(p-1),⋯p-1,ai+1,ai+2,…,b0.
For each case in (17) there are pp-2 possibilities for the p-2 unknown p-ary numbers. In other hand by definition 4 of the pGSSG algorithm for the p-ary number b0 there are two possible cases: first, the one p-ary number from 1 to p-1, defined by (10) or second, the p-ary zero in its appearance by (11).Therefore the number of possibilities for the firstp-ary number b0 is 2·(p-1)·pp-2.For the next knownp-ary number b1 there are the same 2·(p-1)·pp-2 possible cases for the second p-tuple ap+i,ap+i+1,ap+i+2,…,ap+i+(p-1):(18)1,b1,ap+i+2,…,ap+i+(p-1),2,ap+i+1,b1,…,ap+i+(p-1),⋯p-1,ap+i+1,ap+i+2,…,b1.
In addition to the above cases there are another pp-1 possibilities for which the output pGSSG sequence is shrunken(19)0,ap+i+1,ap+i+2,…,ap+i+(p-1).
Hence all possible cases for the p-ary number b1 are (20)V=2⋅(p-1)⋅pp-2+pp-1.
For each of these V possibilities there are another V possibilities for the next p-tuple and so on.Therefore, for reconstructingm  p-tuples, that is, n=m·p  p-ary numbers, are needed(21)S=Vm-1≈Vn/p
possible states for the pLFSR.Example 1 (p=3).
The known bit portion of the sequencez0,z1,z2,… is equal to the known p-ary portion b0,b1,b2,… of the pGSSG because ⌈log2(3-1)⌉=1 bits. Every bit 0 can present the 3-ary bit 1 or the 3-ary zero. The bit 1 can present the 3-ary bit 2 or the 3-ary zero (see Table 1). From the known first bit b0 there are two possible cases for the first triple ai,ai+1,ai+2(22)1,b0,ai+2,2,ai+1,b0.
Each 3-ary number ai∈[0,1,2], that is, the six possible cases are
(23)1,b0,02,0,b01,b0,12,1,b01,b0,12,2,b0
and another six possible cases in which b0 is 3-ary zero are
(24)1,0,02,0,01,0,12,1,01,0,12,2,0.
For the next triple ai+3,ai+4,ai+5 there are 12 possibilities of the same kind
(25)1,b1,02,0,b11,b1,12,1,b11,b1,12,2,b11,0,02,0,01,0,12,1,01,0,12,2,0
and 9 possible cases 0,ai+4,ai+5 when the output is shrunken
(26)0,0,00,1,00,2,00,0,10,1,10,2,10,0,20,1,20,2,2.
Therefore the possible cases are
(27)V=2⋅(p-1)⋅pp-2+pp-1=2.3.3+32=21,
which is listed above.
Then we calculate the possible pLFSR states(28)S≈Vn/p≈21n/3=2(log⁡221/3)n=21.464n.Example 2 (p=5).
The number of possible cases for the  5-tuples are(29)V=2⋅(p-1)⋅pp-2+pp-1=2.4.53+54=1625
and states of the used pLFSR are
(30)S≈Vn/p≈1625n/5=2(log⁡21625/5)n=22.133n.


### 5.2. Entropy Attack

The entropy of thep-tuples will be calculated. As mentioned above for the p-tuple ap+i,ap+i+1,ap+i+2,…,ap+i+(p-1) there are V possibilities, where 2·(p-1)·pp-2 are in the form (18). In the half of these possibilities p-ary number b1∈[1,2,…,p-1] and the probability of each of them is (p-1)/pp. In the other half b1=0 and each of them has probability 1/pp. The other pp-1 possibilities of the form (19) also have probability 1/pp.Therefore, the entropy of thep-tuple is(31)H=-(p-1)⋅pp-2⋅(p-1)pplog⁡2p-1pp-(p-1)⋅pp-2⋅1pplog⁡21pp-pp-1⋅1pplog⁡21pp=-(p-1)2p2⋅log⁡2p-1pp-p-1p2⋅log⁡21pp-1p⋅log⁡21pp=-(p-1)2p2⋅log⁡2p-1pp-(p-1p2+1p)⋅log⁡21pp.
Because the entropy per one p-ary number is H/p, the entropy search among all different cases would require 2n·H/p steps.Forp=3 the entropy of 3-tuples is(32)Hp=3=-6.227⋅log⁡2227-15⋅127log⁡2127=4.3104.
Hence, the complexity of the entropy attack is O(2n·H/p)=O(21.43684n).The complexity of exhaustive search and entropy attack of the pGSSG for primes up to 17 is compared to the SSG and recently proposed MSSG [8] in Table 7.Table 7
A comparison of the complexity of the used attack for SSG, MSSG and pGSSG.
AttackSSGMSSGpGSSGp=3p=5p=7p=11p=13p=17Exhaustive searchO(20.79n)O(20.862n)O(21.464n)O(22.133n)O(22.612n)O(23.281n)O(23.532n)O(23.937n)EntropyO(20.75n)O(20.833n)O(21.437n)O(22.066n)O(22.536n)O(23.210n)O(23.465n)O(23.879n)The results show that the pGSSG is more secure than SSG and MSSG against exhaustive search and entropy attack. The complexity of the used pGSSG attack increases with increasing the primep.


## 5.1. Exhaustive Search Attack

Letz0,z1,z2,… be a known portion of the binary keystream generated by pGSSG. As the prime p is also known the attacker can divide it by ⌈log2p-1⌉ bits. Each portion of ⌈log2p-1⌉ bits presents one p-ary number.Let thenb0,b1,b2,… be a known p-ary portion of the pGSSG. The p-ary number bj for some j is generated by the p-tuple ai,ai+1,ai+2,…,ai+(p-1) of the output pLFSR sequence a0,a1,a2,…, ai∈[0,1,…,p-1], where the index i is unknown.From the knowledge of the firstp-ary number b0 one can conclude that for the first p-tuple there is p-1 possible cases:(17)1,b0,ai+2,…,ai+(p-1),2,ai+1,b0,…,ai+(p-1),⋯p-1,ai+1,ai+2,…,b0.
For each case in (17) there are pp-2 possibilities for the p-2 unknown p-ary numbers. In other hand by definition 4 of the pGSSG algorithm for the p-ary number b0 there are two possible cases: first, the one p-ary number from 1 to p-1, defined by (10) or second, the p-ary zero in its appearance by (11).Therefore the number of possibilities for the firstp-ary number b0 is 2·(p-1)·pp-2.For the next knownp-ary number b1 there are the same 2·(p-1)·pp-2 possible cases for the second p-tuple ap+i,ap+i+1,ap+i+2,…,ap+i+(p-1):(18)1,b1,ap+i+2,…,ap+i+(p-1),2,ap+i+1,b1,…,ap+i+(p-1),⋯p-1,ap+i+1,ap+i+2,…,b1.
In addition to the above cases there are another pp-1 possibilities for which the output pGSSG sequence is shrunken(19)0,ap+i+1,ap+i+2,…,ap+i+(p-1).
Hence all possible cases for the p-ary number b1 are (20)V=2⋅(p-1)⋅pp-2+pp-1.
For each of these V possibilities there are another V possibilities for the next p-tuple and so on.Therefore, for reconstructingm  p-tuples, that is, n=m·p  p-ary numbers, are needed(21)S=Vm-1≈Vn/p
possible states for the pLFSR.Example 1 (p=3).
The known bit portion of the sequencez0,z1,z2,… is equal to the known p-ary portion b0,b1,b2,… of the pGSSG because ⌈log2(3-1)⌉=1 bits. Every bit 0 can present the 3-ary bit 1 or the 3-ary zero. The bit 1 can present the 3-ary bit 2 or the 3-ary zero (see Table 1). From the known first bit b0 there are two possible cases for the first triple ai,ai+1,ai+2(22)1,b0,ai+2,2,ai+1,b0.
Each 3-ary number ai∈[0,1,2], that is, the six possible cases are
(23)1,b0,02,0,b01,b0,12,1,b01,b0,12,2,b0
and another six possible cases in which b0 is 3-ary zero are
(24)1,0,02,0,01,0,12,1,01,0,12,2,0.
For the next triple ai+3,ai+4,ai+5 there are 12 possibilities of the same kind
(25)1,b1,02,0,b11,b1,12,1,b11,b1,12,2,b11,0,02,0,01,0,12,1,01,0,12,2,0
and 9 possible cases 0,ai+4,ai+5 when the output is shrunken
(26)0,0,00,1,00,2,00,0,10,1,10,2,10,0,20,1,20,2,2.
Therefore the possible cases are
(27)V=2⋅(p-1)⋅pp-2+pp-1=2.3.3+32=21,
which is listed above.
Then we calculate the possible pLFSR states(28)S≈Vn/p≈21n/3=2(log⁡221/3)n=21.464n.Example 2 (p=5).
The number of possible cases for the  5-tuples are(29)V=2⋅(p-1)⋅pp-2+pp-1=2.4.53+54=1625
and states of the used pLFSR are
(30)S≈Vn/p≈1625n/5=2(log⁡21625/5)n=22.133n.


## 5.2. Entropy Attack

The entropy of thep-tuples will be calculated. As mentioned above for the p-tuple ap+i,ap+i+1,ap+i+2,…,ap+i+(p-1) there are V possibilities, where 2·(p-1)·pp-2 are in the form (18). In the half of these possibilities p-ary number b1∈[1,2,…,p-1] and the probability of each of them is (p-1)/pp. In the other half b1=0 and each of them has probability 1/pp. The other pp-1 possibilities of the form (19) also have probability 1/pp.Therefore, the entropy of thep-tuple is(31)H=-(p-1)⋅pp-2⋅(p-1)pplog⁡2p-1pp-(p-1)⋅pp-2⋅1pplog⁡21pp-pp-1⋅1pplog⁡21pp=-(p-1)2p2⋅log⁡2p-1pp-p-1p2⋅log⁡21pp-1p⋅log⁡21pp=-(p-1)2p2⋅log⁡2p-1pp-(p-1p2+1p)⋅log⁡21pp.
Because the entropy per one p-ary number is H/p, the entropy search among all different cases would require 2n·H/p steps.Forp=3 the entropy of 3-tuples is(32)Hp=3=-6.227⋅log⁡2227-15⋅127log⁡2127=4.3104.
Hence, the complexity of the entropy attack is O(2n·H/p)=O(21.43684n).The complexity of exhaustive search and entropy attack of the pGSSG for primes up to 17 is compared to the SSG and recently proposed MSSG [8] in Table 7.Table 7
A comparison of the complexity of the used attack for SSG, MSSG and pGSSG.
AttackSSGMSSGpGSSGp=3p=5p=7p=11p=13p=17Exhaustive searchO(20.79n)O(20.862n)O(21.464n)O(22.133n)O(22.612n)O(23.281n)O(23.532n)O(23.937n)EntropyO(20.75n)O(20.833n)O(21.437n)O(22.066n)O(22.536n)O(23.210n)O(23.465n)O(23.879n)The results show that the pGSSG is more secure than SSG and MSSG against exhaustive search and entropy attack. The complexity of the used pGSSG attack increases with increasing the primep.


## 6. Conclusions and Future Works

In this paper the generalization of the self-shrinking generator in Galois FieldGF(pn) for arbitrary prime p is proposed. The architecture of the new p-ary Generalized Self-Shrinking Generator is suggested. It is proved that the pGSSG has large period and good statistical properties. The experimental results analysis shows that the sequence generated by pGSSG is well balanced, uniform, scalable, uncompressible and unpredictable.The complexity of the exhaustive search and entropy attack of the pGSSG is established. It is shown that the pGSSG is more secure than SSG and MSSG against exhaustive search and entropy attack. It is proven that the complexity of the used pGSSG attack increases with increasing the primep.Above-mentioned properties give the reason to consider the pGSSG as a pseudorandom generator that can be useful as a part of modern stream ciphers.However, there are some theoretical and practical issues that need to be addressed. From a theoretical point of view, improved cryptanalysis of the pGSSG keystream sequences is necessary to be done and the complexity of other known self-shrinking attacks like attack using long keystream segment, BDD-based attack and guess-and-determine attack, must be investigated.On the practical side, the hardware FPGA implementation of the pGSSG generator must be designed. It will provide faster execution of the algebraic operations in theGF(p) for any prime number P≥3.



---

*Source: 464971-2011-05-03.xml*