Method for stream-wise encoding of discontinuous information

FIELD: computer science, communications.

SUBSTANCE: method includes generating a protection key in form of a binary vector n-bit long, sending it for primary filling of displacement register, generating pseudo-random series of maximal length, generating pseudo-random series of symbols, transforming data stream to encrypted message and transmitting the latter along communication line, while pseudo-random series is generated as pseudo-random series of symbols of finite field F_p with characteristic p=2^k+1 in form of binary vectors k-nit long by getting information from k different bytes of displacement register with check connection, numbers of which are determined on basis of protection key, and number k is selected equal to one of members of geometric row, which has denominator and first member equal to two, and also a pseudo-random series of symbols is formed for finite field of odd values of symbols due to skipping clock pulses of displacement register with check connection for which pseudo-random series symbols take even values and serially transforming in finite field F_p symbols of source text by involution thereof, appropriate for pseudo-random series symbols.

EFFECT: higher resistance to attacks on basis of known and sorted out texts.

4 cl, 2 dwg

The invention relates to the field of telecommunications and computing, and more particularly to methods and devices for the cryptographic transformation of data.

Known methods of flow encode discrete data (see, for example, the Russian encryption standard the standard of the USSR GOST 28147-89 [1], the British algorithm B-Grypt, which is a Supplement to the U.S. standard DES [2] p.50, 126, and the method described in [3], p.50-51).

In the known methods of encoding digital data is performed by generating a security key, generating a pseudo-random sequence of binary symbols and converting the data stream, comprising the operations of addition modulo two characters of the data stream with symbols of pseudo-random sequence.

Known methods analogous to stream encoding discrete information ensure the integrity of transmitted information.

The closest to the technical nature of the claimed method is a method presented in [2], str-127 and in [3], p.50-51.

Prototype method includes forming a security key as a binary vector of length n-bits, feed it to the initial filling of the shift register with feedback, having n bits, the formation with the use of the shift register pseudo-random sequence of maximal length, terzidou 2 ⁿ-1 binary symbols, the data flow transformation by adding modulo two characters of the source text with symbols of pseudo-random sequence and transmitting the encoded message over the connection to another network user.

However, the prototype method has drawbacks. Despite the fact that the code is based on the addition of a stream of pseudo-random bits with bits of the original text in module 2 is, in General, theoretically unrecognizable (see [2], str the coding system is not persistent and may be disclosed. If the structure of the shift register having n-bits is known, to find the initial state of the shift register, it is necessary to know n symbols known plaintext, which are summed modulo 2 with the corresponding n-symbols of the encoded text. Received n symbols of pseudo-random sequences are used to indicate the state of the shift register at some point in time. Simulating the operation of the shift register in the reverse direction, it is possible to determine its original state, and therefore the keys used by network users for encoding information.

If the structure of the shift register having n-bits is unknown, it is enough 2· n characters known plaintext and corresponding 2· n symbols of the encoded text, the button relatively quickly (within a few seconds the computer) to determine the state of the shift register and used to compute the keys (see, for example, [4], p.92).

And this leads to decrease in resistance code to attacks based on known and selected source that does not provide confidentiality of information and leads to the need to change the security key. Security keys can be used only once and at the next session should be determined anew.

The invention is aimed at improving the life code to attacks based on known and selected source.

This is achieved by the known method of encoding digital data, which consists in forming a security key as a binary vector of length n bits, feed it to the initial filling of the shift register with feedback, having n bits, the formation with the use of the shift register pseudo-random sequences of maximum length, containing 2ⁿ-1 binary symbols, the data flow transformation of the source text in the encoded message and send it through the communication line, according to the invention a pseudo-random sequence is formed as a pseudo-random sequence of characters of a finite field F_pwith characteristic p=2^k+1 in the form of binary vectors of length k bits by removing information from k different bits of the shift register, and the number k is chosen equal to one of the members of the geometric p is agressie, which the denominator and the first member is equal to two, while miss those cycles of operation of the shift register, for which the symbols of pseudo-random sequences take even values that divide the data stream source blocks of characters of the source text in the form of binary vectors of length k bits, and in turn transform in a finite field F_pthe characters of the source text by raising them to the level corresponding to the symbols of pseudo-random sequence.

In the combination of features of the proposed method under a binary vector refers to the signal as a sequence of zeros and a single bit corresponding to the representation of a number in binary.

Listed set of essential features eliminates the possibility of defining security keys by using the method of cryptanalysis with known plaintext and increases the stability of the code to attacks based on known and selected source. In this case, the generated pseudo-random sequence of characters in the form of binary vectors of length k bits are pseudorandom sequence of symbols {0,1,2,... ,p-1} of a finite field F_phas the same period N=2ⁿ-1, as a pseudo-random sequence of binary numbers and provide statistical uniformity of the used symbols.</>

By skipping stages of the shift register, for which the symbols of pseudo-random sequences take even values will be generated pseudo-random sequence of symbols x of odd numbers 1,3,5,7,... ,p-2, which is used for character encoding of the source text α by constructing them in a degree corresponding to the symbols of pseudo-random sequence X. If this encoded message is to represent a sequence of characters β determined by the formula

β ≡ α^x(modp).

Since the number p=2^k+1 is Prime, then the Euler function ϕ (p)=(p-1) and in accordance with the Euler-Fermat will have the following identity

α^{1+mϕ (b)}=α^1+m(p-1)≡α (modp).

Since x· x^-1=1+m(p-1)≡ 1(mod(p-1)),

where m is an arbitrary positive integer,

x^-1the symbol opposite to the symbol x in the ring of residue class modulo

p-1,

then the relation is valid : In this case, calculated at the receiving side the values of the symbols x^-1in the ring of residue class modulo p-1 allow to implement the inverse transform for decoding the source text

Since a pseudo-random sequence x contains only odd the e symbols 1,3,5,... ,R-2, they are elements of the multiplicative group of the ring of classes of deduction modulo p-1 and will have the opposite values of x^-1that can be defined by the formula

where ϕ (p-1) is the Euler function for the number of R-1. Since p-1=2^kϕ (p-1)=2^k-1. In this case, x^-1can be calculated by the formula

where q=2^(k-1)-1. Thus to calculate the x^-1can be used in the algorithm fast erection of integers modulo presented in [4] on page 39.

As cryptographic transformations are operations of the erection of the characters in the degree in a finite field F_pa pseudo-random sequence of characters is formed on the principle of compression generator with an uneven movement of the shift register, it eliminates the opening state of the shift register in the presence of arbitrarily original characters and symbols of the encoded text. This is because to determine the symbols of pseudo-random sequences for known characters of the original and the encoded text requires the computation of discrete logarithm in a finite field F_pthat can only be achieved as a result of total enumeration of characters this field, and to determine the state of the shift register is calculated by the symbols of pseudo-random sequences, you must know the symbols of pseudo-random sequence to skip stages of the shift register, the beginning and are in the process of a sequential movement of the shift register is changed in a pseudo-random law. This provides resistance code to attacks based on known and selected source, as the opening state of the shift register in this case can only be achieved through a total enumeration of the entire set of possible States of the shift register. Because the U.S. standard DES involves the use of a shift register with 128bit encryption (key length 128 bits), the cardinality of the set of possible States of the shift register will be 10³⁸. If the opening state of the shift register will be implemented using a computer having a clock frequency of 100 GHz, the number of operations performed by the computer during the year will be 3· 10²⁰and time of opening is 10¹⁷years.

In accordance with the Russian standard GOST 28147-89 to the shift register, has 256 bits (256-bit key length), the time of opening state of the shift register will be 10⁵⁷years.

The possibility of technical realization of the inventive method is explained as follows. The formation of the security key can be done by entering password from the keyboard or from the magnetic media in a pseudo-random number generator, which in turn yields a security key required size.

The formation of a pseudo-random sequence of characters of a finite field F_pin the form of binary vectors of length k bits can be done by removing information from k different bits of the shift register numbers that can be defined by the value of the entered security key K. for Example, by defining a generating element

if l₀<2, l₀=2,

and the numbers of discharge of the shift register according to the formula

l₁=l₀,

The value of q is chosen from primes and to the shift register, has 256 bits, q=257, for a shift register having 128 bits, q=127. In this case, due to the exponentiation of the parent number of l₀we will move from one field item F_qto another. In this case, as shown in [4], p.9, if l₀- an element of order k, then allwill be different.

A pseudo-random sequence of characters is the end product of the La F _pyou can also type "compression generator" by removing information from k bits of the shift register and skip those stages of the shift register, for which the symbols of pseudo-random sequences take even values.

Since p must be a Prime number equal to p=2^k+1, as k choose one of the members of a geometric progression 2, 4, 8, 16, 32, 64,... , with the denominator equal to two.

The generated pseudo-random sequence of a finite field F_puse in cryptographic transformation when converting the data stream in the encoded message:

α^x≡β(mod p)

Can be used three variants of the formation of pseudo-random sequences of characters of a finite field as binary vectors.

1. Change the number of digits k, c which information is collected for a pseudo-random sequence of characters of a finite field F_pp=2^k+1 in accordance with the change of the initial filling of the shift register.

2. Change the number of bits of the shift register from which information is collected for a pseudo-random sequence of characters of a finite field, in accordance with the change of the initial filling of the shift register.

3. Change the order of reading data for random effects the successive characters of a finite field in accordance with the change of the initial filling of the shift register.

The formation of a pseudo-random sequence of characters of a finite field according to claim 1, 2 and 3 increases the stability of the code to attacks based on known and selected source code in the formation of a security key or a binary vector of pseudo-random sequences of small length.

The conversion of the data stream in the encoded message can be done by splitting the original data into blocks as symbols α binary vectors of length k bits, the computation in a finite field F_p(p=2^k+1) values of the characters β encoded text in accordance with the selected function encoding, α^x≡ β (mod p), converting the received number β in the binary vector, and transmit it over the wire. This can be used to fast a number raised to a degree in a finite field F_ppresented in [4] on page 39.

The proposed method can be implemented using the device. Figure 1 shows the block diagram of the device, where

unit 1 - forming device protection key and the original signal;

unit 2 - the shift register;

block 3 - shaper pseudo-random sequence;

unit 4 - the encoder;

block 5 - transmitting device.

For the shift register in figure 2 blocks 6-11 - bits 1-6 of the shift register and the block 12 is modulo two.

D is I the simplicity of the description of the operation of the device will use small numbers. We assume that the shift register is 6 bits (the key length is 6 bits), and the entire alphabet of the source text contains 16 characters, then to send a single character can be used a binary vector of length 4 bits, and as the characteristic of a finite field F_pcan be selected number p=17.

To define the structure of the shift register is chosen primitive polynomial of the sixth degree, for example

λ⁶+λ⁵+1

For the selected primitive polynomial, the structural diagram of the shift register with feedback presented in figure 2.

Formed in the block 1 figure 1 using a random number generator security key length of 6 bits

< λ₆thatλ₅thatλ₄thatλ₃thatλ₂thatλ₁>

where λ₁=0, λ₂=0, λ₃=0, λ₄=1, λ₅=1, λ₆=1;

enters the shift register and is used for initial filling of bits of the shift register. Binary characters 5 and 6 of the discharge of the shift register receives at each stage to the input of the adder 12 modulo two, and from the output of the modulo two characters ε proceed to input the first digit of the shift register (block 6, figure 2). The status bits for each measure in the process of the shift register are determined by the expression

λ_i=λ_i-1 λ₁=ε

If the characters will be shot with a sixth category λ₆the shift register (block 11, figure 2), the binary pseudo-random sequence, the maximum period will be

{1110000010000110001010011110100011

100100101101110110011010101111}.

Note that the period of this sequence is any non-zero set of six digits 0 and 1 occurs only once.

If the binary number will be removed from 1, 2, 3 and 4 digits of the shift register (blocks 6, 7, 8, 9, 2) and at each stage of the shift register with a set of <λ₁thatλ₂thatλ₃thatλ₄> will associate a binary vector (number) y=λ₁+2λ₂+2²λ

y={8,0,0,1,2,4,8,0,1,3,6,12,8,1,2,5,10,4,9,3,7,15,14,13,

10,4,8,1,3,7,14,12,9,2,4,9,2,5,11,6,13,11,7,14,13,11,6,12,9,

3,6,13,10,5,10,5,11,7,15,15,15,14,12,... }.

Analysis of the generated sequences have shows that in the interval corresponding to the period equal to 63 cycles of operation of the shift register, each of the C symbols {1, 2,... , 15} occurs exactly four times. The character corresponding to the zero occurs exactly three times in the sequence have no hidden periodicity and provides statistical uniformity of the characters used.

Because in the process of the shift register do not use the cycles in which the characters do take even values, it generates a pseudorandom sequence of numbers (characters) 1, 3, 5, 7, 9,... , 15 in the form:

x=1,1,3,1,5,9,3,7,15,13,1,3,7,9,9,5,11,13,11,7,13,11,9,3,3,13,5,5,11,7,15

Formed in the block 1 1 security key 111000 served in block 2 of figure 1. In block 3 form a pseudo-random sequence of odd characters.

The generated pseudo-random sequence of characters of a finite field x in the form of binary vectors served in the encoder 4 figure 1 where convert the incoming data flow λ encoding the message β in accordance with the selected cryptographic transform in a finite field F₁₇for example

α =7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,

x=1,1,3,1,5,9,3,7,15,13,1,3,7,9,9,5,11,13,11,7,13,

β =7,7,3,7,11,10,3,12,5,6,7,3,12,10,10,11,14,6,14,12,6.

For the obtained values β form a binary vector and pass through the device 5 figure 1 on the receiving end of the radio link.

On the receiving end of the radio link shall decoding the received sequence of symbols β in compliance and with the installed cryptographic transformation α ≡ β^x-1(modl7) in the finite field F₁₇. Since p=17, k=4, x^-1is carried out according to the formula x^-1≡x⁷(mod16). Then for the considered example, the values of the respective symbols by decoding the message will be:

β =7,7,3,7,11,10,3,12,5,6,7,3,12,10,10,11,14,6,14,12,6,

x=1,1,3,1,5,9,3,7,15,13,1,3,7,9,9,5,11,13,11,7,13,

x^-1=1,1,11,1,13,9,11,7,15,5,1,11,7,9,9,13,3,5,3,7,5,

α =7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7.

Implementation of the proposed method is straightforward, since all the blocks and units included in the device that implements the method, well-known and widely described in the technical literature.

Sources of information

1. Russian encryption standard the standard of the USSR GOST 28147-89. The information processing system. The cryptographic protection. The cryptographic transformation.

2. Smarty. Protection mechanisms in computer networks. M., 1993

3. Vienicai. Elements of cryptography. Fundamentals of theory of information security. M.: Higher school, 1999

4. ViewPath. Adaptive protection of information in computer networks. - M.: Radio and communication, 2002

1. The method of flow encoding digital data, namely, that form the security key as a binary vector of length n bits, served for the initial filling of the shift register with feedback having n digits, is formed using Regis is RA shift pseudo-random sequence of maximal length, contains 2ⁿ-1 binary symbols, perform data flow transformation of the original text into a coded message by splitting a data flow of the source text into blocks as symbols of the binary vectors of length k bits and transmit it over the communication line, characterized in that to form a pseudo-random sequence as a pseudo-random sequence of characters of a finite field F_pwith characteristic p=2^k+1 in the form of binary vectors of length k bits by removing information from k different bits of the shift register with feedback, the number of which is determined by the value of the security key, and the number k is chosen equal to one of the members of a geometrical progression, in which the denominator and the first member is equal to two, thus forming a pseudo-random sequence of characters of a finite field of odd values character by skipping stages of the shift register with feedback, for which the symbols of pseudo-random sequence taking odd values, and in turn transform in a finite field F_pthe characters of the source text by raising them to the level corresponding to the symbols of pseudo-random sequence.

2. The method according to claim 1, characterized in that each communication session change number of digits k that information is collected for the formation of binary, etc) the ditch pseudo-random sequence in accordance with the change of the initial filling of the shift register with feedback.

3. The method according to any one of claims 1 to 2, characterized in that each communication session change number of bits of the shift register from which information is collected for the formation of binary vectors of pseudo-random sequence in accordance with the change of the initial filling of the shift register with feedback.

4. The method according to any one of claims 1 to 3, characterized in that each communication session, change the order of reading data from the selected bits of the shift register for the formation of binary vectors of pseudo-random sequence in accordance with the change of the initial filling of the shift register with feedback.