Method for stream encoding of digital information

FIELD: electrical communications and computer engineering; cryptographic data conversion.

SUBSTANCE: proposed method includes generation of protection key in the form of n-bit binary vector, its supply for initial filling of shift register producing maximal-length pseudorandom character sequence, conversion of data stream into encoded message, and its transfer over communication line; in the process total character of encoded text is shaped and its value is conveyed at moment when search sequence character assumed value equal to unity.

EFFECT: reduced redundancy in message transferred and enhanced message transfer speed.

1 cl, 2 dwg

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

Known methods of flow encode discrete data (see, for example. Russian encryption standard, the standard of the USSR GOST 28147-89 [1], the British algorithm B-Grypt, which is in addition to the U.S. standard DES [2] p.50, 126, [3] pages 50-51, and the method described in patent 2002104639/09, IPC 7 H 04 L 9/00 [4], Pat. No. 2205516.

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 in the encoded message using symbols of pseudo-random sequence.

Known methods analogous to stream encoding discrete information ensure its integrity. The methods described in [1-3], are vulnerable to attacks based on known or selected source, the method described in [4], provides the immunity of the transmitted information with the active intrusion.

The closest to the technical nature of the claimed method is a method presented in [4].

Prototype method includes forming a security key as a binary vector of length n bits, feed it to DL the initial filling of the shift register with feedback, having n bits and generating a pseudorandom sequence of maximal length, containing 2ⁿ-1 binary symbols, the formation of a pseudo-random sequence of characters of a finite field F_pwith characteristic p=257 in the form of binary vectors of length 8 bits by removing information from eight different bits of the shift register, the formation in the form of binary vectors of characters out of sequence due to the exponentiation of a generating element in a finite field F_pdividing the data stream into blocks of characters of the source text in the form of binary vectors of length 8 bits, the formation of a summary character of the source text in the form of a binary vector by addition in a finite field F_pcharacter of the original text with all the previous characters of the source text and the alternate transformation binary vectors-characters of the source text is multiplied by the characters out of sequence and addition in the finite field F_pthe obtained result with the symbols of the pseudo-random sequence, adding to the converted binary vector of the source text redundant bits for checking the encoding of a symbol on parity, the replacement of the generating element out of sequence when in its composition symbol “1” to the total symbol of the outcome of the CSO text, the encoding of new generating element, a data flow transformation of the source text in the encoded message and the transmission of coded messages and generating new item on line.

However, the prototype method has a drawback. To correct the distorted when receiving a character much redundancy is introduced by adding to the converted binary vector of the source text redundant bits for checking the encoding of a symbol on parity. The number of symbols in the transmitted message is increased by 13%.

The invention is aimed at reducing the redundancy in the transmitted message and increase the speed of transmission of the message.

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, applying it to the initial filling of the shift register with feedback having n bits and generating a pseudorandom sequence of maximal length, containing 2ⁿ-1 binary symbols, the formation of a pseudo-random sequence of characters of a finite field F_pwith characteristic p=257 in the form of binary vectors of length 8 bits by removing information from eight different bits of the shift register, the formation in the form of binary vectors of symbols re irawma sequence due to the exponentiation of a generating element in a finite field F _p, splitting the data stream into blocks of characters of the source text in the form of binary vectors of length 8 bits, the total character of the source text in the form of a binary vector by addition in a finite field F_pcharacter of the original text with all the previous characters of the source text and the alternate converting binary vectors of characters multiplied by the characters out of sequence and addition in the finite field F_pthe obtained result with the symbols of the pseudo-random sequence, the replacement of the generating element out of sequence when in its composition symbol “1” on the overall character of the source text; the encoding of new generating element, the data flow transformation of the source text in the encoded message and the transmission of coded messages and generating new item line, according to the invention form the total symbol of the encoded text as a binary vector by addition in a finite field F_panother symbol of the encoded text with all the previous characters of the encoded text and the transfer of the total symbol of the coded text line after replacement and transfer of the generating element out of sequence.

In the combination of features claimed which the procedure under binary vector refers to the signal as a sequence of zero and unit bits corresponding to the representation of a number in binary.

Listed set of essential features reduces the redundancy in the transmitted message and increases the speed of transmission of the message due to the fact that precluded the addition of redundant bits to verify the encoded message on parity. To determine the character, in which there was a single error, and to correct this error is transmitted via the communication line, the total symbol encoded text at the moment of changing the generating element out of sequence, when her character takes a value of “1”. Because a change of the generating elements through a sequence of a finite field F₂₅₇the average is over 256 characters, one total symbol encoded text will be transferred to a binary vector of length 8 bits on average over 256 characters. While the redundancy of the transmitted message will be 0.4%.

If one error occurs in the interval corresponding to the change of the generating elements out of sequence, the error will be detected and corrected. To do this:

- calculate the discrepancy Δ α total characters transferred to the source text Cα and calculatedat the receiving side

- calculate the discrepancy Δ β total characters transmitted encoded text Cβ and calculatedPA receiving side

- compute the character sort sequence used to encode the distorted when receiving

x≡ Δ β · Δ α^-1(mod p),

where Δ α^-1≡(Δ α )^p-2(md)is the inverse element with respect to the symbol Δ α F_p:

- correct the distorted character of the source text by the formula

α ≡ α +Δ α (mod p).

The possibility of technical realization of the inventive method is explained as follows. The formation of a security key allows you to enter the 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 pseudo-random sequences of maximum length, containing 2ⁿ-1 character, can be done by using a linear shift register having n bits, the feedback of which is determined by referring to the selected primitive polynomial of degree n. Finding primitive polynomials of degree n is given in [5| p.106-110.

The formation of a pseudo-random sequence is of ingelow finite field F ₂₅₇in the form of binary vectors of length 8 bits can be done by removing information from eight different bits of the shift register numbers that can be defined but the value of the entered security key K. for Example, by defining a generating element

l₀=K(mod q), if l₀&λτ;2, the l₀=2,

and the numbers of discharge of the shift register but the formula

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. As shown in [5] 9 if l₀- an element of order k, then all elements of l₀l

The formation of symbols x enumerating sequences as binary vectors at each stage of the shift register can be defined as generated by the s elements of the field F _pby multiplying the previous character of this sequence by the generating element of x_n:

x≡ x· x_n(mod p)

If the calculation process at some the first stage of the shift register, it turns out that x=1, then in this case you will have a generating element of x_nfield F_p. At the same time as a new generating element x_naccepted element formed at this stage of the shift register, the total character of the source text With the target zero F_p, x_n=If&λτ; 2, x_n=2. The generated sequence of a finite field F_puse in cryptographic transformation when converting the data stream in the encoded message:

α · x+y=β (mod p)

Because enumerating sequence of a finite field elements are formed by raising to the power generating element x_nwith order k, then all elements of x_nx

Converting the data stream and the encoded message is carried out by splitting the original data into blocks as symbols α -binary vectors of length 8 bits, is calculated in a finite field F_p, [p=257)values of the characters β encoded text in accordance with the selected function encoding α · x+y≡ β (mod p), convert the number β binary vector and pass them on line.

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 out of 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.

Laprotomy describe 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 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). When this status bits for each measure in the process of the shift register are determined by the expression

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 λ₄&γτ;we shall compare the 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 that is the work of the shift register, each of the symbols {1, 2,... , 15} occurs exactly four times. The symbol for zero, occurs exactly three times in the sequence have no hidden periodicity and provides statistical uniformity of the characters used.

Formed in the block 1 1 security key 111000 together with the signal of the source text entered in block 3 of figure 1. In this unit form a generating element of x_nby bringing the number that corresponds to the security key in a nite set of fields F₁₇

x_n=2³+2⁴+2⁵(mod l7)=5,

and calculate for each stage of the shift register elements of a finite field F₁₇

x=x x_n(mod 17),

who are the characters out of sequence:

x 5, 8, 6, 13, 14, 2, 10, 16, 12, 9, 11, 4, 3, 15, 7, 1, 10, 15, 14, 4, 6.

and also calculate the total characters of the source text

Withα =α_-1α (mod 17)

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

Cα =7, 14, 4, 11, 1, 8, 15, 5, 12, 2, 9, 16, 6, 13, 3, 10, 0, 7, 14, 4, 11.

If the character sort sequence takes the value "1", then change the generating element of x_nin accordance with the value of the total character of the source text. For the above example, the new generating element is equal to "10". This item code in the device of figures 1 and 4 transmit using devices 5 figure 1 on the receiving to the end of the radio link encoded symbol 12.

The generated sequence of characters of a finite field x and y as binary vectors received 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=5, 8, 6, 13, 14, 2, 10, 16, 12, 9, 11, 4, 3, 15, 7, 1, 10, 15, 14, 4, 6,

y=8, 0, 0, 1, 2, 4, 8, 0, 1, 3, 6, 12, 8, 1, 2, 5, 10, 4, 9, 3, 7,

β =9, 5, 8, 7, 15, 1, 10, 10, 0, 15, 15, 6, 12, 4, 0, 12, 12, 7, 5, 14, 5.

For the obtained values β will generate the total symbol of the encoded text Withβ =β_-1+β (mod 17)

Withβ =9, 14, 5, 12, 10, 11, 4, 14, 14, 12, 10, 16, 11, 15, 15, 10, 5, 12, 0, 14, 2.

If the character sort sequence takes the value "1",then the total symbol of the encoded text (in our case, the symbol 10) in the form of a binary vector is passed through the communication line after the transfer of the parent element.

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 accordance with the established cryptographic transformation α ≡ (β +y* )· x^-1(mod 17) in the finite field F₁₇for example:

β =9, 5, 8, 7, 15, 1, 10, 10, 0, 15, 15, 6, 12, 4,0, 12, 15, 10, 12, 7, 5, 14, 5,

y* =9, 0, 0, 16, 15, 13, 9, 0, 16, 14, 11, 5, 9, 16, 15, 12, 7, 13, 8, 14, 10,

x^-1=7, 15, 3, 4, 11, 9, 12, 16, 10, 2, 14, 13, 6, 8, 5, 1,, 12, 8, 11, 13, 3,

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

If you receive a message, an error has occurred, for example, when receiving a tenth of symbol instead of symbol 15 adopted the symbol 10, the decoding of the message this symbol will correspond to the symbol 14 (instead of the symbol 7). This error is corrected as follows:

- calculate the total character of the original text

Withα * =7, 14, 4, 11, 1, 8, 15, 5, 12, 9, 16, 6, 13, 3, 10, 0.

- calculate the discrepancy Δ α total characters transferred the original text Withα and calculatedα * at the receiving side

Δ α ≡α -Cα * (mod p)=10-0≡ 10(mod 17);

- calculate the total symbol of the encoded text

Withβ * =9, 14, 5, 12, 10, 11, 4, 14, 14, 7, 5, 11, 6, 10, 10, 5,

- calculate the discrepancy Δ β total characters transmitted encoded text Withβ and calculatedβ * at the receiving side

Δ β ≡β -Cβ * (mod p)=10-5≡ 5(mod 17);

- compute the character sort sequence used to encode the distorted when receiving

x≡ Δ β · Δ α^-1(mod p)=5· 12=60≡ 9(mod 17),

where Δ α^-1≡(Δ α )^p-2(mod p) is the inverse element is the compared to the symbol Δ α F_p:

- correct the distorted character of the source text by the formula

α ≡ α +Δ α (mod p)=14+10=24=7(mod 17).

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

Sources of information

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

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

3. Vienicai. Elements of cryptography. Fundamentals of theory of protection inrormation. - M.: Higher school, 1999

4. Way line coding discrete information. Patent for invention No. 2002104639/09, IPC 7 H 04 L 9/00.

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

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 bits and generating a pseudorandom sequence of maximal length, containing 2ⁿ-1 binary symbols, to form a pseudo-random sequence of characters of a finite field F_pthe characteristic p=257 in the form of binary vectors of length 8 bits by removing information from eight different bits of the shift register, numbers that determine the value of the security key, create characters out of sequence in the form of binary vectors at each stage of the shift register with feedback by multiplying the previous character of this sequence by the generating symbol of a finite field F_p, break the data stream into blocks of characters of the source text in the form of binary vectors of length 8 bits, form the total character of the source text in the form of a binary vector by addition in a finite field F_pcharacter of the original text with all the previous characters of the source text and in turn encode the characters of the source text is multiplied by the characters out of sequence and addition in the finite field F_pthe obtained result with the symbols of the pseudo-random sequence, when in enumerating the sequence of symbol "1" change generating symbol, and as a new generating character take the total character of the source text, formed at this stage of the shift register with feedback, encode new generating symbol and transmit the encoded characters of the source text and coded new generating symbol on the communication line, wherein forming the total symbol of the encoded text as a binary vector by adding in the final paragraph is Le F _panother symbol of the encoded text with all the previous characters encoded text and send the total symbol of the coded text line after the transmission of the encoded new generating character sort sequence.