Development of Additive Fibonacci Generators with Improved Characteristics for Cybersecurity Needs

Abstract

Pseudorandom sequence generation is used in many industries, including cryptographic information security devices, measurement technology, and communication systems. The purpose of the present work is to research additive Fibonacci generators (AFG) and modified AFG (MAFG) with modules p prime numbers, designed primarily for their hardware implementation. The known AFG and MAFG, as with any cryptographic generators of pseudorandom sequences, are used in arguments with tremendous values. At the same time, there are specific difficulties in defining of their statistical characteristics. In this regard, the following research methodologies were used in work: for each variant of AFG and MAFG, two models were created—abstract, which is not directly related to the circuit solution, and hardware, which corresponds to the proposed structure; for relatively small values of arguments, the identity of models was proved; the research of statistical characteristics, with large values of arguments, was carried out using an abstract model and static tests NIST. Proven identity of hardware and abstract models suggest that the principles laid down in the organization of AFG and MAFG structures with modules of prime numbers ensure their effective hardware implementation in compliance with all requirements for their statistical characteristics and the possibility of application in cryptographic information security devices.

1. Introduction

Additive Fibonacci generators (AFG) are one of the types of pseudorandom sequence generators that are widely used in many technical means, particularly in cryptographic means of information protection. In their traditional design, they do not provide adequate cryptosecurity, but can be used as part of cryptographic devices [1,2,3,4,5,6,7,8,9]. Recently, we proposed a modified AFG (MAFG), in which the introduction to their structure and additional logic circuit, allowed us to include, in the process of arithmetic addition, the result of a logical function from the binary values of the resulting register, which significantly improved the statistical characteristics of the pseudorandom output sequence [10,11,12,13,14,15].

At present, almost all classic AFGs and new MAFGs, designed for hardware implementation, operate according to recurrent equations with modules whose values are equal to the power of two. It simplifies their hardware implementation but narrows their functionality and worsens the statistical characteristics of the output pseudorandom sequences.

In [16], we proposed AFGs that can work with an arbitrary value of a module, including a module whose value is a prime number. However, these devices do not have an additional logic circuit [10,11,12,13,14,15], which does not allow satisfactory statistical characteristics to be obtained without the involvement of additional devices.

In this article, we reveal the approach to constructing Fibonacci additive generators with modules of prime numbers. This construction method expands the capabilities of the hardware implementation of such generators and improves their output statistical characteristics, which allows them to be used effectively in cryptographic applications. A research methodology is proposed based on using abstract and hardware models of generators. Their identity is proved, which allows investigation of the statistical characteristics of such generators with the large values of arguments, which is especially important for cryptographic generators. The research results indicate that the proposed models and structures of generators can be effectively used to solve cryptographic problems of information security.

The aim of the work is to create and research the characteristics of AFGs and MAFGs with modules whose values are prime numbers. To achieve this goal, new generator structures are proposed, in which the introduction of additional structural elements allows us to ensure the operation of generators with arbitrary values of the recurrent equation modulus. This is the scientific novelty of the obtained results, which significantly improves the statistical characteristics of generators, expands their functionality, and expands the scope of their use in cryptographic means of information protection, particularly in streaming ciphers.

2. Related Works

A large number of works are devoted to the construction of AGF. In particular, analyses of the implementation of Fibonacci hardware generators on FPGA are given in [17]. There are also similar studies of Fibonacci generator implementations on FPGA in [18], and in [19], true random number generators, based on Fibonacci–Galois ring oscillators for FPGA, are considered, and the possibility of using these generators in cryptographic applications is shown. The results of research that used a combination of a hybrid of two existing generators—a linear congruential method and a delayed Fibonacci technique—are presented in [20]. The analysis of the efficiency of using a Fibonacci generator for cryptographic problems is also considered in [21,22]. Moreover, in [23], Fibonacci generators are used for the key generation algorithm with the necessary randomness and low algorithmic complexity. The work in [24] is devoted to the question of the correct choice of Fibonacci generator parameters.

AFGs operate according to the following generalized recurrent equation:

x_i = (x_i−a + x_i−b +…+ x_i−q) mod (m),

(1)

where a > b > … > q > 0.

Usually, AFGs are used in which the module m = 2ⁿ, where n is the number of generator structural elements binary bits, that simplifies their hardware implementation. Under certain conditions, the repetition period of such AFGs is not less than value 2ⁿ − 1 [25].

It is known [26] that, if the module m = p is a prime number, then, according to the theory of finite fields, we can find such multipliers as a₁, a₂,…, a_k, so that the sequence can be defined by the following equation:

x_i = (a_ix_i−1 +…+ a_k−1 x_i−k+1 + a_k) mod p,

(2)

which will have the maximum possible period equal to p^k − 1. In this case, the following theorem holds. If the constants a₁, a₂,…, a_k are such that the polynomial x^k − a₁x^k−1 − … − a_k is primitive over the field GF(p), and at least one of the elements x₀, x₁,…, x_k is not zero, then the generator period is equal to p^k − 1, at any initial values of the structural elements of the generator.

It is also known [26,27] that the search for primitive polynomials for prime number modules is a difficult task.

In [10,11,12,13,14,15] we proposed modified MAFGs, in which the module is determined by the equation m = 2ⁿ, but they include an additional logic circuit (LC), the function of which is logical addition of the module 2 of the bits values of one of the generator registers, and then the result is added to the main operation of the arithmetic addition. This allows a significant increase in the repetition periods of the output sequences and an improvement of their statistical characteristics.

However, for today, there are no reasonable developments in which the structures of AFGs and MAFGs are proposed with an arbitrary value of the module of the recurrent equation.

3. Structure Scheme and Work Principle of AFG and MAFG with Arbitrary Value of the Module of the Recurrent Equation

Figure 1 shows the structure scheme of AFG and MAFG, which can operate with any value of the recurrent equation module. The AFG consists of registers RG1–RG6, adders AD1 and AD2, multiplexer MUX, and logical element OR. The logic circuit LC is additionally introduced to the MAFG structure.

The schemes are given for generators operating according to the following equations:

x_i = (x_i−5 + x_i−4) mod p, (for AFG)

(3)

x_i = (x_i−5 + x_i−4 + a) mod p, (for MAFG)

(4)

where: x_i, x_i−4, x_i−5—numbers at the outputs of registers RG1, RG5, and RG6, respectively.

In Equation (4):

a = b₀ ⊕ b₁ ⊕ … ⊕ b_s,

(5)

where: b_i (i = 0, 1, …, s; s ≤ n)—values of the number x_i binary bits; n—the total number of binary bits.

With each clock pulse, new values of numbers are formed in the registers RG1–RG6, in particular in the register RG1—the number determined by the output signal of the multiplexer MUX.

At the output of the logic circuit LC, the signal a is formed in accordance with logic Equation (5). Adding the LC output signal a, in the process of arithmetic addition, implemented by the adder AD1, can significantly improve the statistical characteristics of the output pseudorandom signals of the generator.

In the absence of carry signals at the outputs of the adders AD1 and AD2, to the information inputs of the memory register RG1, through the multiplexer MUX, arrives a number from the information outputs of the adder AD1; moreover, if at least one of them is present, the number of information outputs are those of the adder AD2.

Compared with the known AFG and MAFG [10,11,12,13,14,15,28], the introduction of the second adder AD2, multiplexer MUX, and the establishment of new connections between these and other structural elements, allows changing the numbers in the registers RG1–RG6 in the range of values 0 ÷ (p − 1). Thus, AFG and MAFG operate with arbitrary module values according to Expressions (3) and (4), which confirmed our research, as mentioned in the following sections.

4. Methods of AFG and MAFG Statistical Characteristics Research

AFG and MAFG, as with any cryptographic generators of pseudorandom sequences, are used in arguments whose values are enormous; therefore, there are some difficulties in determining their statistical characteristics.

In this regard, the following research methodology was used. Two models were created for each AFG and MAFG variant: firstly, the abstract, which is not directly related to the circuit design solution, and hardware, which corresponds to the proposed structure. For relatively small values of arguments, the identity of the models is proved. The study of statistical characteristics, with large values of arguments, is carried out using an abstract model.

The following algorithms represent different AFG and MAFG models. The hardware models are represented by equations that correspond to the structures’ processes, shown in Figure 1. Abstract models are represented by equations that correspond to the processes that must occur in the additive Fibonacci generator when it operates with a module whose value can be arbitrary. Proving the identity of the results obtained with these models proves the correctness of the structures shown in Figure 1, in terms of achieving the desired result.

4.1. Research of AFG Models

In AFG models, the logic circuit LC is not involved in the generator structure scheme (Figure 1).

The AFG hardware model operates in accordance with the following algorithm:

A = 2ⁿ − p, x_i−5 = x_i−4, x_i−4 = x_i−3, x_i−3 = x_i−2, x_i−2 = x_i−1, x_i−1 = x_i, x_i = x_mp,

x_ad1 = (x_i−5 + x_i−4) mod 2ⁿ, if (x_i−5 + x_i−4) < 2ⁿ then P_ad1 = 0 else P_ad1 = 1,

x_ad2 = (x_ad1 + A) mod 2ⁿ, if (x_ad1 + A) < 2ⁿ then P_ad2 = 0 else P_ad2 = 1,

if (P_ad1 = 0), and (P_ad2 = 0), then x_mp = x_ad1, or x_mp = x_ad2,

where: x_i, x_i−1, x_i−2, x_i−3, x_i−4, x_i−5—numbers in registers RG1–RG6, respectively; x_ad1 and x_ad2—numbers at the sum outputs of adders AD1 i AD2; P_ad1 and P_ad2—numbers at the carry outputs of adders AD1 and AD2; x_mp—the number at the output of the multiplexer MUX; n—the number of the generator’s structural elements binary bits (Figure 1).

The abstract AFG model is described by the following equations:

x_i−5 = x_i−4, x_i−4 = x_i−3, x_i−3 = x_i−2, x_i−2 = x_i−1, x_i−1 = x_i, x_i = x_ad1, x_ad1 = (x_i−5 + x_i−4) mod p.

Figure 2 shows the dependences of the current values of pseudorandom numbers X, generated by AFG on the iteration step number, i, for the hardware and abstract model with the same initial value, X(0).

Numbers X and X(0) are defined by the following expressions:

X = p⁵x_i + p⁴x_i−1 + p³x_i−2 + p²x_i−3 + px_i−4 + x_i−5,

(6)

X(0) = p⁵x_i(0) + p⁴x_i−1(0) + p³x_i−2(0) + p²x_i−3(0) + px_i−4(0) + x_i−5(0),

(7)

where: x_i(0), x_i−1(0), x_i−2(0), x_i−3(0), x_i−4(0), x_i−5(0)—initial values of numbers x_i, x_i−1, x_i−2, x_i−3, x_i−4, x_i−5, respectively.

Figure 3 on a logarithmic scale shows the dependence of the repetition periods of the AFG pseudorandom sequence numbers from the initial values, X(0).

The results (Figure 2 and Figure 3) indicate complete identity of hardware and abstract models for forming a pseudorandom numbers sequence. Similar results were obtained for other p values, in particular for p values that are primes.

4.2. Research of MAFG Models

MAFG models: Figure 1 shows generator structure scheme with using logic circuit LC. The hardware model of the MAFG, operating according to the following algorithm:

A = 2ⁿ − p, x_i−5 = x_i−4, x_i−4 = x_i−3, x_i−3 = x_i−2, x_i−2 = x_i−1, x_i−1 = x_i, x_i = x_mp,

a = b_{0 ⊕} b_{1 ⊕} … _⊕ b_s

x_ad1 = (x_i−5 + x_i−4 + a) mod 2ⁿ, if (x_i−5 + x_i−4 + a) < 2ⁿ then P_ad1 = 0 else P_ad1 = 1,

x_ad2 = (x_ad1 + A) mod 2ⁿ, if (x_ad1 + A) < 2ⁿ then P_ad2 = 0 else P_ad2 = 1,

if (P_ad1 = 0) and (P_ad2 = 0) then x_mp = x_ad1 else x_mp = x_ad2,

where: b_i—values of the number xi binary bits.

Abstract model of the MAFG operating according to the following equation:

x_i−5 = x_i−4, x_i−4 = x_i−3, x_i−3 = x_i−2, x_i−2 = x_i−1, x_i−1 = x_i, x_i = x_ad1,

a = b_{0 ⊕} b_{1 ⊕} … _⊕ b_s

x_ad1 = (x_i−5 + x_i−4 + a) mod p.

Figure 4 shows the dependences of the current values of pseudorandom numbers, X, that were generated by the MAFG on the iteration step number, i, for the hardware and abstract model with the same initial value, X(0).

Figure 5 shows, on a logarithmic scale, the dependences of repetition periods of MAFG pseudorandom sequence on the initial values, X(0).

The results (Figure 4 and Figure 5) indicate complete identity hardware and abstract models for forming the pseudorandom numbers sequence. Similar results were obtained for other p values, in particular for p values that are primes.

5. Results

5.1. Research of Repetition Periods of AFG and MAFG Pseudorandom Sequences

The following research was conducted using an abstract model considering proven identity hardware and abstract generators models. It is necessary to speed up the simulation process.

Table 1. Repetition periods of AFG and MAFG output sequences for p value on the whole set of possible values, X(0) = 0 ÷ p⁶ − 1.

Some p Values	Max and Min Repetition Period Values
	AFG (without Logic Circuit LC)	MAFG (with Logic Circuit LC)
2	63	10
		2
3	728	315
		5
5	3124	14,409
	4	5
7	2400	105,833
	24	11,360

presents the received results of AFG and MAFG repetition periods, Tp, for a few small module p values that determined on the whole set of possible values of the initial number, X(0) = 0 ÷ p⁶ − 1.

In this case, for MAFG, the output signal value a of the logic circuit LC (Figure 1) was determined, according to Equation (5), as the sum for the module 2 for all bits of number x_i in the register Pr1.

Table 1 shows the maximum and minimum values of the period Tp. It should be noted that when p = 2 and p = 3 on the whole set, X(0) = 0 ÷ p⁶ − 1 fixed only one value Tp = p⁶ − 1. It coincides with the known theoretical results presented in Ref. [25].

Where for larger values of module p, determination of repetition period, Tp, on the whole set of values, X(0) = 0 ÷ p⁶ − 1, requires a lot of machine time, all the following research was conducted for a fixed value, X(0) = 1.

Table 2. Repetition periods of AFG and MAFG output sequences for some p values when X(0) = 1.

Some p Values	Repetition Periods Tp
	AFG (without Logic Circuit LC)	MAFG (with Logic Circuit LC)
11	118,103	1,601,719
13	371,291	2,636,108
17	88,415	9,810,767
19	2,476,097	26,974,957
37	845,657	382,733,921
41	1679	432,850,590
43	1,116,087	5,459,242,931
73	1,401,242,835	8,949,513,501
137	4,387,429,945	>1010

shows the repetition period, Tp, for some p values and fixed values, X(0) = 1.

Based on the research results of the output sequences, repetition periods of the AFG and proposed MAFG, in which the modules of the recurrent equations are prime numbers, such a conclusion can be made. When p > 3 the repetition periods MAFG is significantly greater than the AFG. When p = 2 and p = 3, the repetition periods of AFG reach, theoretically, the maximum value, Tp = p⁶ − 1, for all possible values, X(0).

5.2. Research of Statistical Characteristics of AFG and MAFG Pseudorandom Sequences

Research the statistical characteristics of the output pseudorandom bit sequences of AFG and MAFG for some p values were carried out with the NIST test package [29,30,31]. Results shows in Figure 6, Figure 7, Figure 8 and Figure 9. Figure 6 presents a statistical portrait of the AFG output sequence at p = 137.

As can be seen from Figure 6, the most tests valued at 0 and did not fall within the specified interval; meaning that the sequence does not meet the randomness requirements.

Figure 7 shows MAFG using the same initial data as AFG. The sequence also does not meet the randomness requirements, but there is a significant improvement over the AFG. In particular, most test values are above 0. So, the proposed modification demonstrates positive dynamics.

Figure 8 shows the statistical portrait of the AFG output sequence at p = 65,537. The tests failed and did not meet the randomness requirements.

Figure 9 presented the statistical portrait of the MAFG output sequence using the same parameters as AFG. As can be seen, all tests are within the allowable range. It means that such sequence has high statistical characteristics and meet the randomness requirements.

Analysis of statistical portraits (Figure 6, Figure 7, Figure 8 and Figure 9) shows that, with the same parameters, the statistical characteristics of the output pseudorandom sequences of MAFG significantly predominated in the AFG. Thus, at p = 65,537, X(0) = 1, and a = b_{0 ⊕} b₁ …_⊕ b₁₆ (Figure 9) MAFG statistical characteristics entirely pass all NIST tests.

The conducted research proves that the proposed Fibonacci additive generators can operate by recurrent equations, whose modules values can be arbitrary, including modules whose values are prime numbers. It distinguishes them from the known additive Fibonacci generators, whose value of the modules is equal to the power of two. That is, the class of proposed generators includes the known generators as a subclass. At the same time, the proposed generators have the best statistical characteristics and designs for hardware implementation primarily, in which will achieve their maximum speed when implementing the proposed structures in a modern element base, for example, in programmable logic integrated circuits (PLDs).

6. Conclusions

The present article proposes new structures of AFG and MAFG, in which adding additional structural elements allows the operation of the generator with arbitrary values of the modulus of the recurrent equation, in particular, with modules whose values are prime numbers.

In the present study, we proved the identity of hardware and abstract models, suggesting that the principles laid down in the organization of the AFG and MAFG structures with modules of prime numbers ensure their effective hardware implementation.

For the basic function x_i = (x_i−5 + x_i−4) mod p, the MAFG selected for the research, which functions according to the equation x_i = (x_i−5 + x_i−4 + a) mod p, significantly predominated over AFG in the repetition period and statistical characteristics for all module values p > 3.

The AFG, at p = 2 and p = 3, fixed the maximum possible repetition period, T_p = p⁶ − 1, for all possible initial values of generator registers settings.

In further research, an important task is to find primitive polynomials over the field GF(p) for other values, p > 3, create AFG and MAFG structures for these values, and research their characteristics.

The obtained results can be used not only in the design of information security tools but also in other technology fields, such as in simulating random processes in measuring technologies.