BG67431B1 - Method and device for keystream generating for stream ciphers - Google Patents

Abstract

The invention relates to a method and device for generating a keystream in streaming cipher information. The method is distinguished in that it generates a non-linear 17-digit pseudo-random sequence with a uniform distribution of the17-digits therein, and then converts the non-linear 17-digit sequence into a balanced binary sequence. The device implementing the method uses a clock-driven 17-digit shift register with linear feedback building blocks that can store 17-digit numbers, a rule to choose between two techniques for introducing nonlinearity, shrinking and multiplexing, and a nonlinear conversion of each 17-digit into a 4-bit sequence preserving the uniform distribution of bits in the output key sequence.

Description

(54) METHOD AND DEVICE FOR KEYSTREAM GENERATION FOR STREAM CIPHERS

Field of technique

The method and apparatus for generating a key stream for stream ciphers are used in a communication and network environment involving devices with limited resources such as computing power and limited memory, in particular the Internet of Things (IoT), automotive systems, sensor networks, healthcare devices and networks, distributed control systems, cyber-physical systems, smart hotel management networks, and more.

Prior art

Encryption is an effective way to protect sensitive information while it is stored on media or transmitted over an untrusted communication channel in a network, allowing the information to be read and processed only by the entities for which it is intended. Cryptography uses two basic types of cryptographic algorithms, also known as ciphers: symmetric and asymmetric ciphers. Symmetric ciphers, on the other hand, are classified as block and stream ciphers.

Stream ciphers are generated by performing a bitwise XOR operation on a pseudorandom sequence of bits called a keystream and the information to be protected. Stream ciphers in practice apply the principles of the One Time Pad, which is considered secure from the point of view of information theory.

Currently, various types of stream ciphers have been developed, generated using block ciphers or Linear Feedback Shift Registers (LFSRs). Pseudorandom generators based on block ciphers have high computational complexity and are not suitable for application in resource-constrained devices. On the other hand, LFSR registers offer a fast and efficient method of generating a linear pseudorandom sequence. In order to be applicable in cryptography, additional means are applied to them, providing nonlinearity in the output sequence. Modern research is in the field of using structures based on LFSR registers: filter generators, combinational generators or clock-controlled generators, as well as in the use of generators in finite fields [1].

A method is known for generating a stream cipher using a key sequence obtained by sum modulo 2 of two sequences generated by a Lagged Fibonacci generator and a filter generator [2].

A key stream generator for stream ciphers operating in the above method consisting of a delayed Fibonacci generator and a filter generator is known. It is characteristic of the famous generator that it does not provide high security and high efficiency in encryption and decryption. Reasons for this are the small number of feedback links in its building blocks.

Characteristic of the delayed Fibonacci generator used in the patent is its built-in three-point correlation between L _n , Ln-5 and L _n- n , determined by the use of only two feedbacks. This correlation is propagated over tach(5,17) = 17 output elements of the delayed Fibonacci generator, which can lead to significant errors [3].

On the other hand, the filter-generator uses a three-feedback LFSR register, which makes it susceptible to the fast correlation attack proposed in [4]. It is shown that the attack is not applicable if the LFSR register has more than 10 backlinks.

Also, the implementation of the known keystream generator uses one word of 32 bits for processing, because the filter-generator is implemented with an LFSR register structured by 4 in number of 32-bit registers, and the delayed Fibonacci generator performs operations modulo 2 ³² . The operations are in a Galois field GF(2 ³² ). These operations are not suitable for resource-constrained devices based on 8-bit microcontrollers.

In modern spread spectrum communication systems, such as Code Division Multiple Access (CDMA), sequences with more than two levels are increasingly used. Therefore, there is a need to create advanced methods and devices for generating not only binary but also non-binary keystreams with cryptographically strong properties to be used in embedded applications using microcontrollers with low computing power and little memory.

A method of generating a key stream for a stream cipher is known, in which freely fixed data in the form of bits is generated and a shuffling operation is selected, wherein each input bit changes half of the output bits, wherein the shuffling operation includes multiple negative or multiple data selections to be merged or replaced or replaced and added (EP 3337082).

The device implementing the method comprises a stream generator, a bit mixer with hard-coded key material, an input counter, or a combination thereof. It contains a central microprocessor, a security processor, first and second buses, several memory mixers and counters and logic circuits (EP 3337082).

It is characteristic of the known method and device that they are complex, have low security and cannot be implemented in embedded applications using microcontrollers with low computing power and little memory.

Technical essence of the invention

The object of the invention is to provide a method and device for a synchronous stream cipher using a 17-bit nonlinear pseudorandom sequence and a binary key sequence, which is suitable for use in a communication and network environment involving resource-constrained devices with increased security and efficiency of encryption and decryption processes.

This task is solved by a method of generating a key stream for a stream cipher containing a selection operation, of input information /in bits/, a shuffling operation /mixing/, in which each input bit changes the output bits. The method is distinguished by choosing a primitive polynomial q(x) from received or calculated data q(x) = qiX + qL- 1XL ¹ + ... + q ix - 1 (1) in the Galois field GF(17 ^L ), which defines the architecture of a 17-LFSR linear feedback shift register generating a 17-th linear recurrent sequence with a maximum period of 17 ^L - 1.

It chooses between two nonlinear functions, compression and multiplexing, by a selection rule, to generate a nonlinear 17 sequence.

A trailing zero seed value is determined when converting each 17 digit of said non-linear 17 sequence to a 4-bit sequence to obtain a non-linear balanced binary pseudo-random sequence.

Computes the key stream for a stream cipher according to said selected primitive polynomial, said selected nonlinear function, and said selection of a trailing zero seed value when converting to a balanced binary sequence.

A Galois field GF(17 ^L ) is chosen based on the byte organization of processors in resource-constrained devices.

The selection of the non-linear function is done depending on the value of the first 17 digit of each 17-tuple of said 17 linear recursion sequence, if it is 0, collapse is performed and no 17 digit is output, and if is greater than zero, its value determines which of the remaining 16 17 digits to output in said non-linear 17 sequence.

Each 17 digit, if non-0, is decremented by one and represented in 4-bit binary, and if equal to 0, each occurrence is represented by a trailing zero.

To extend the application of the method to devices with limited resources and little memory, the device contains a 17-bit linear feedback shift register 17-LFSR, the architecture of which is defined by the primitive polynomial q (x) = 11 x ¹⁸ + 11 x ¹² + 14x ¹⁰ + 6x ⁹ + 9x ⁸ + 11x ⁷ + 14x ⁵ + 2x ⁴ + 7x ³ + 7x ² + 14x - 1 (2) generating a 17-th linear recurrent sequence with maximum period 17 ¹⁸ - 1 connected via a selection rule with the option of choosing between the non-linear compression and multiplexing functions to a binary balanced sequence converter.

The device implementing the key stream generation method for a stream cipher consists of a register, a multiplexer and logic blocks. The device differs from known ones in that it contains a 17-LFSR linear feedback shift register and L number of elements ai, i = 0, 1, ., L - 1, c the possibility that each of them can store one 17 -ical digit in the interval [0, 16]. The output of the last element a ₀ is connected to each multiplier in a Galois field GF(17), capable of being multiplied by the coefficients q,, i = 1, 2, ., L, and is connected to the first input of a corresponding adder in a field of Galois GF(17). The second input of the Galois field adder GF(17) is connected to the element a,. The output of the corresponding adder in a Galois field GF(17) is connected to the input of the element a—.

To increase the crypto-resistance of the generator, the output of the last element ao is connected to a selection rule block, including a buffer capable of storing 17 consecutive 17-digits (a _17i , a _17i+ ι, ., at+1b), i = 0, 1, . With a _17i = 0, no 17 digit is output at the output of said non-linear 17 sequence, i.e. contraction takes place. The first output of the buffer is connected to the output of a 16:1 multiplexer and to the balanced binary sequence converter and controls the uneven clocking of the generator. When ai7i > 0, the output of said non-linear 17 sequence is introduced by multiplexing, and the second output of the element ai7i is connected through a first subtraction block to the second input of the 16:1 multiplexer. The value of ai7i - 1 from the output of the first subtraction block determines which of the remaining 16 of the number of 17-digits (am ₊₁ , ..., ant ₊₁₆ ), i = 0, 1, ... should be output of said non-linear 17 sequence.

To increase crypto-resistance and security, each 17-digit bi, i = 0, 1, ..., of said non-linear 17-sequence is checked for a value of 0 in the memory element, the first output of which, for bi > 0, is connected through a second extraction block to the first key input. With bi = 0, the second output of the memory element is connected to the first input of a counter to 16 and to the second input of the switch. The second input of the counter to 16, defining its initial state, is connected to the initial value of the running zero, which is the 4-bit representation of the number qo. The output of the switch is the output of the generator.

A suitable platform for implementing the stream cipher keystream generation method and device of the present invention is any microprocessor device and its associated software, firmware, devices and communication networks. The method and device provide a wide range of devices with limited resources, small memory and high speed.

Explanation of the attached figures

Figure 1 presents a block diagram of keystream generation for stream ciphers.

Figure 2 shows a 17-bit linear feedback shift register 17-LFSR.

Figure 3 presents the block diagram of the selection rule.

Figure 4 shows the block diagram of the binary balanced sequence converter.

Figure 5 is a block diagram of an exemplary key stream generator for a stream cipher according to the present invention.

Figure 6 shows a block diagram of a network of a central device and one or more end devices where the key stream generator for a stream cipher according to the present invention may be implemented.

Exemplary embodiment of the invention

The block diagram for generating a key stream for stream ciphers is shown in Fig. 1. The stream cipher keystream generator 4 consists of a 17-bit linear feedback shift register 1 (17-LFSR) connected through a selection rule block 2, capable of introducing non-linearity into the output 17 bit sequence, and is connected to a balanced binary sequence converter 3, with the ability to preserve the even distribution of zero and one bits in the output key stream.

The block diagram of the linear feedback shift register 17-LFSR 1 is presented in Figure 2. It consists of L number of elements 21 ai, i = 0, 1, ... L - 1, each of which is capable of storing one 17 digit in the interval [0, 16]. The output of the last element a ₀ 21d is connected to each multiplier in a Galois field GF(17) 23, with the possibility of multiplying by the coefficients qi ₊₁ , i = 0, 2, ..., L - 2, and is connected to adder in a Galois field GF(17) 22 and is capable of addition to the content of the preceding element. The last element ao 21g is connected to the output and is capable of forming part of the output 17 linear sequence. In 17-LFSR register 1 operation, when the content of element i is moved to element i - 1 for each i, 1 < i < L - 1, the following recursive dependencies are fulfilled:

a ' = (at+1 + qt+1 ao) mod 17, for 0 < i < L - 2 (3) a 2 _-x = qLa o mod 17

The feedback multipliers qi, i = 1, 2, ..., L in the 17-LFSR register 1 are determined by the coefficients of the primitive polynomial q (x) (1) in GF(17 ^L ) to obtain a sequence with maximum period.

With 17 elements in field GF(17) and length L of the 17-LFSR register 1 used, the maximum sequence period is T = 17 ^L - 1. Register 1 is initialized with the 17 sequence (aL-1, ..., a 1, ao).

Figure 3 presents the block diagram of the selection rule 2, which introduces non-linearity into the linear 17 sequence produced by the 17-LFSR register 1. For this purpose, two techniques of introducing non-linearity, namely compression and multiplexing, are applied.

Buffer 3.1 contains 17 consecutive 17 digits (a ₁₇ i, a ₁₇ i ₊₁ , ..., a ₁₇ i ₊₁₆ ), i = 0, 1,.... The value of the first of them a ₁₇ i specifies which of the two nonlinearity techniques to perform. If a ₁₇ i = 0, no 17th digit is output, i.e. contraction takes place. Applying compression allows the generation of 17-digits at the output not to occur every clock of the 17-LFSR register 1, but at irregular intervals. The resulting non-uniform timing of the keystream generator in this way makes it invulnerable to correlation attacks and fast correlation attacks.

If a ₁₇ i > 0, the technique of introducing nonlinearity multiplexing is performed. The value of the 17 digit a ₁₇ i is decremented by one by a subtractor block 3.3 and with the ability to determine which of the 16 inputs of the 16:1 multiplexer 3.2 will be output to the output of the selection rule 2. The multiplexer 3.2 selects one of the 17 -ical digits a ₁₇ i ₊₁ , a ₁₇ i ₊₂ , ..., a ₁₇ i ₊₁₆ depending on the binary value of a ₁₇ i - 1 obtained by the subtraction block 3.3. Thus, the use of multiplexer 3.2 increases the security of the generated 17-digit nonlinear sequence and binary key sequence by masking parts of 16 consecutive 17-digit digits.

Figure 4 presents the block diagram of the balanced binary sequence converter 3, which converts each 17-digit into a sequence of 4 bits, the output binary sequence having an equal number of zeros and ones, i.e. it is balanced. Each 17-digit stored in memory element 4.0 bi, i = 0, 1, ..., of the non-linear 17-sequence is checked for the value 0. If bi = 0, the value of the counter to 16 4.2 is incremented by 1 and the resulting 4 output bits from counter 4.2 through switch 4.3 are output to the output of the generator. The initial value of the counter is the 4-bit binary

BG 67431 Bl representation of the number qo defining the initial state of the running zero. If bi > 0, the value of b is reduced by one by the subtractor 4.1 and the binary code of b is output through the key 4.3

The balanced binary sequence converter 3 represents each of the 17 numbers b, in the interval [1, 16] by the binary representation of the number b, - 1, and the 17 zero as a running zero with initial state qo. At every /th occurrence of the zero (i = 1, 2, ...) in the nonlinear 17 pseudorandom sequence, it is binary represented as the number q,:

qt = (qi-i + 1) mod 16 (4)

The trailing zero further increases the security of the binary keystream generation method because it masks the 17th zero consecutively with different non-zero 17th digits.

The method according to the present invention simultaneously generates two non-linear balanced sequences: 17-bin sequence A and binary B.

The period Ta of the 17-sequence is Ta = 2 ⁴ . 17 ^L ~\ and the number of occurrences of each 17 digit i = 0, 1,..., 16 is equal to:

Ni = 2 ⁴ .17 ^{£ 2} , i = 0.1.16.

The period Tv of the binary sequence is Tv = 2^17^ and the number of occurrences of each bit is

Figure 5 is a block diagram of an exemplary stream key generator for a stream cipher of the present invention.

The selected primitive polynomial (2) defining the feedbacks of the 17-LFSR register 1 in the exemplary stream cipher key stream generator 4 of the present invention is of degree 18 and has 11 non-0 coefficients excluding the free one. The primitive polynomial is chosen with more than 10 feedbacks to thwart the possibility of a successful fast correlation attack on the stream cipher.

In this case, the 17-LFSR register 1 consists of 18 number of elements 21, 11 number of feedbacks with multipliers in Galois field GF(17) 23 and 11 number of adders in Galois field GF(17) 22. Each element 21, storing one 17 digit, occupies 5 bits and can be represented by one byte of microprocessor device memory.

An example of the operation of the key stream generator for the stream cipher of FIG. 5 is shown in Table 1, showing how only the first 7 of the 17 digits and their binary equivalent are obtained. In the second column of the table, the contents of the buffer 3.1 are presented, in the third column - the output of the selection rule 2, and in the fourth column - the output of the balanced binary sequence converter 3.

(D 0, ...,1),

In the example, the initial load of the 17-LFSR register 1 is the 17 sequence ¹⁰ which in binary form is represented by 18.5 = 90 bits. 17 17-digit numbers are stored in buffer 3.1. If the first of them is 0, the non-linear contraction operation is implemented and no value is output at the output (in the table it is marked with If the first digit is different from 0, it is reduced by one in the subtracter 3.3, the value controlling which input of the multiplexer 3.2 will be output to the selection rule 2 output.

To determine the initial state of the running zero, qo = 3 is chosen. To convert to a balanced binary sequence, each non-zero 17 digit stored in the memory element 4.0 is decremented by one in the subtracter 4.1 and converted to binary form , being represented by 4 bits and through the switch 4.3 is output to the output of the converter 3. The counter to 16 4.2 is initially loaded with the value qo = 3 and at each new occurrence of zero at the output of the selection rule 2, the counter to 16 4.2 is increased by one, and its value is output in binary form through switch 4.3 at the output of converter 3.

BG 67431 Bl

Table 1.

no Buffer 3.1 Ruled O 13 choice 2 Binary type 3 1 1116751121715189 9 4 6 5 4 5 3 14 1101 2 11129172610004111 0 5 0 5 2 1 1 0 UN 3 0009661 10644] 1 1 1 1 6 4 5 2 6 0 — 4 01114640111111110 6 6 6 5442022 — —

5 27411764100195319 2 0 5 1 3 4 0011 6 21111639151311324 4 4 0 6 3 1 3 14 1 101 7 14511481443411121 3 11 6 0 4 1 3 14 1 101 8 13 61 1237781556872 3 3 2 0 6 0101 9 53496072219 111811 0 15 1 4 0 0 0100

BG 67431 Bl

The first 20 digits of the 17 non-linear key sequence generated by the exemplary stream cipher key stream generator of FIG. 5, are 14 0 4 14 14 6 0 10 5 2 13 4 11 15 13 12 11 14 11 0, and the principle of obtaining the first 7 of them is shown in Table 1. The resulting balanced binary sequence generated by the example key generator stream for the stream cipher of FIG. 5, for these 20 digits is 1101 0011 0011 1101 1101 0101 0100 1001 0100 0001 1100 0011 1010 1110 1100 1101 1010 1101 1010 0101.

A suitable platform for implementing the stream cipher keystream generation method and device of the present invention is any microprocessor device and its associated software, firmware, devices and communication networks. Figure 6 shows an exemplary block diagram of a network of a central device and one or more end devices connected via the Internet or intranet where the stream cipher key stream generator of the present invention is used. The central unit 6.1 comprises a processor 6.2 bi-directionally connected to a memory 6.3 to which bi-directionally connected detected data 6.4 and a key stream generator for a stream cipher 4 of the present invention. Bidirectionally connected to module 2 adder 6.7 is detected data 6.4, encrypted data 6.5, and unidirectionally the stream key generator for stream cipher 4 of the present invention. The encrypted data 6.5 via a two-way connection via a communication interface 6.6 is connected via a communication network 8 to one or more end devices 7.1. The end unit 7.1 has the same structure as the center unit 6.1. The end device comprises a memory 7.3 bidirectionally connected to a processor 7.2, a stream cipher key stream generator 4 and exposed data 7.4. Modulus adder 2 is connected via a one-way connection to a stream key generator for a stream cipher 4 of the present invention and two-way connections with exposed data 7.4 and encrypted data 7.5. The encrypted data 7.5 is bidirectionally connected via a communication interface 7.6 to a communication network 8. The processor 6.2 can process an operating system or firmware, application programs and data.

The stream encryption system processes the detected data 6.4 stored in the memory 6.3 as a bit stream and performs the sum modulo 2 operation 6.7 between the detected data 6.4 and the output of the stream cipher key stream generator 4, obtaining encrypted data 6.5. The encrypted data 6.5 by means of the communication interface 6.6 is transmitted through the communication network 8 to the end device 7.1. The stream encryption system uses in the central device 6.1 and the end device 7.1 the same key stream generators for the stream cipher 4, which with the same initial loading of the 17 -LFSR register 1 and the initial state of the running zero q ₀ produce the same pseudo-random bit stream. Similarly, in the end device under the same initial conditions, the same pseudo-random stream of bits is generated, and from the encrypted data 7.5, through the sum modulo 2 operation 7.7, the discovered data 7.4 is recovered, which is written in the memory 7.3 for further processing by the processor 7.2.

In addition, the stream encryption system in the central device 6.1 can configure the parameters of the stream encryption system in the end devices 7.1. As a result, the central device 6.1 and the end devices 7.1 can encrypt and decrypt information using the stream cipher. Furthermore, they can exchange information encrypted by the stream cipher by means of the communication interfaces 6.6 and 7.6 over the communication network 8 such as the Internet, intranet, GSM, UMTS, LTE and others.

The central device 6.1 can reconfigure the parameters of the stream encryption system in the end devices 7.1 by providing information to change the initial load of the 17-LFSR register 1 or the initial state of the running zero qo. As a result, the stream encryption system implemented in the end device 7.1 can be easily modified.

The above-described implementation and other principles and aspects of the present invention may be applied in a variety of environments. These environments and associated applications may be specifically designed to perform the various operations of the invention through an appropriate combination of hardware and/or firmware. The method and apparatus according to the various embodiments of the present invention can be practically implemented in any way on a computing device, including a desktop computer, a notebook computer, a tablet or a wireless notebook computer, or in embedded devices with limited resources, such as passive smart devices, sensor networks, healthcare networks, distributed control systems, cyber-physical systems, smart hotel management networks and more.

Claims (2)

Method for generating a key stream for a streaming cipher, comprising an operation for selecting input information in bits, a shuffling operation, in which each input bit changes the output bits, characterized in that a primitive polynomial is selected from received or calculated data q (x) = qLxL + qL-1xL-1 +… + q1x - 1 in the Galois field GF (17L), defining the architecture of a moving register with linear feedback 17-LFSR (1), generating a 17-bit linear recurrent sequence with a maximum period of 17L - 1; - is selected between two nonlinear functions, shrinkage and multiplexing, by a selection rule (2) introducing nonlinearity in the said 17-LFSR register said 17-line linear recurrent sequence to generate a non-linear 17-line sequence; - an initial running zero value is selected for the balanced binary sequence converter, which transforms each 17-digit digit of said non-linear 17-bit sequence into a 4-bit sequence to obtain a non-linear balanced binary pseudo-random sequence; - the key stream for the stream cipher is calculated in accordance with said selected primitive polynomial, said selected nonlinear function and said choice of the initial value of the running zero when converting to a balanced binary sequence Device performing the method for generating a key stream for a streaming cipher, comprising a register, multiplexer and logic blocks, characterized in that it contains a 17-bit shift register with linear feedback 17-LFSR (1), the architecture of which is determined by the primitive polynomial generating q (x) from obtained or calculated data q (x) = q_L x ^ L + q_ (L-1) x ^ (L-1) +… + q_1 x-1 (1) 17-line linear a recurrent sequence with a maximum period of 17L - 1 connected via a selection rule block (2) to a binary balanced sequence converter (3)