RU2296427C1 - Method for stream encoding of discontinuous information - Google Patents

Abstract

FIELD: electric communications and computer engineering, area of methods and devices for cryptographic transformation of data.

SUBSTANCE: method includes generation of protection key, sending thereof for beginning filling of shift register, producing pseudo-random series of maximal length, generation of pseudo-random series of symbols, transformation of data stream to encoded message by involution of symbols of source text to power, appropriate for symbols of pseudo-random series, and transfer of encoded message via communication line. In current method, pseudo-random series is formed as pseudo-random series of symbols in form of binary vectors k bit long, while cryptographic transformations are performed in the circle of residue classes with modulus p=2^k.

EFFECT: increased speed of data encoding and expanded range of alternation of resistance of code to attacks on basis of known or matched original texts.

2 cl, 2 dwg

Description

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

Known methods for stream coding of discrete information (see, for example, the Russian encryption standard USSR standard GOST 28147-89 [1], the British algorithm B-Grypt, which is an addition to the US standard DES [2] p. 50, 126, the method described in [ 3] p. 50-51), as well as the method described in the patent for the invention No. 2251816 dated 05/10/2005 [5])

In the known methods, encoding of discrete information is carried out by generating a security key, generating a pseudo-random sequence of binary characters and converting a data stream, including modulo addition operations of two characters of a data stream with pseudo-random sequence characters.

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

Despite the fact that the code based on the addition of the pseudo-random bit stream with the source text bits modulo 2 is generally theoretically unrecognizable (see [2], p. 128), the encoding system itself is not robust and can be disclosed when the presence of a small number of characters of the source and encoded text (see, for example, [4] p. 92).

The closest in technical essence to the claimed method is the method described in [5].

The prototype method includes the formation of a security key in the form of a binary vector of length n bits, feeding it for the initial filling of the shift register with feedback, having n bits and generating a pseudo-random sequence of maximum length containing 2 ⁿ -1 binary characters, the formation of a pseudo-random sequence of characters finite field with characteristic p = 2 ^k +1 in the form of binary vectors of length k bits by taking information from k different bits of the feedback shift register, the numbers of which are determined by the value of the security key, in this case, a pseudo-random sequence of characters from odd values is formed by skipping the shift register feedback cycles, for which the characters of the pseudo-random sequence take even values, dividing the source text data stream into block symbols in the form of binary vectors of length k bits, conversion of characters of the source text into an encoded message by raising them to a power corresponding to characters of a pseudo-random sequence him over the line of communication.

However, the prototype method has a low data decoding rate and a poorly adjustable range of code resistance to attack based on known or selected source texts. The low data decoding speed is due to the fact that to ensure high code resistance to attacks based on known or selected source texts, the operation of raising characters in the final field F _p , p = 2 ^k +1, k ∈ 2, 4, 8, 16 is used. In this case, to decode the data, it is necessary to determine the inverse elements of the symbols x of the pseudo-random sequence. The inverse elements are calculated by raising the symbols x of the pseudo-random sequence to the power p-2 in the final field F _p , x ^-1 ≡x ^p-2 (mod) p, which is a laborious operation, since the number of multiplications in the final field will be large. Since the number k is limited by values k ∈ 2, 4, 8, 16, for which the comparison module p must be a prime number p = 2 ^k +1, this reduces the adjustment of the range of changes in the resistance of the code to attacks based on known and selected source texts.

The invention is aimed at increasing the speed of data decoding and expanding the range of changes in code resistance to attacks based on known or selected source texts.

This is achieved by the fact that in the known method of encoding discrete information, which consists in generating a security key in the form of a binary vector with a length of n bits, supplying it for the initial filling of the shift register with feedback, having n bits and generating a pseudo-random sequence of maximum length containing 2 ⁿ - 1 binary characters, forming a pseudo-random sequence of characters in the form of binary vectors of length k bits by taking information from k different bits of the shift register with feedback, but The measures of which are determined by the value of the security key, while forming a pseudo-random sequence of characters from odd values due to skipping the shift register feedback cycles, for which the characters of the pseudo-random sequence take even values, dividing the source text data stream into block symbols in the form of binary vectors k bits in length, alternately converting the characters of the source text into an encoded message by raising them to the power corresponding to the characters of the pseudorandom after sequence, and transmitting it over the communication line, according to the invention, convert even characters of the source text data stream to odd ones by replacing the character "0" with the character "1" in the zero bit of the binary vector of the source text data stream, and raising the characters of the source text to the power is carried out in the ring of the residue class modulo p = 2 ^k , while the binary vector of the result of raising the characters to the power for even characters of the source text is converted by replacing the binary vector of the character "1" with the character "0" in the zero bit.

In the totality of the features of the proposed method, a binary vector is understood to mean a signal in the form of a sequence of zero and single bits corresponding to the representation of a number in a binary system.

The listed set of essential features increases the speed of data decoding. This is due to the fact that as a comparison module, numbers of the form p = 2 ^{k are used} . For these numbers, the Euler function is φ (p) = 2 ^(k-1) where k is an integer greater than one. In this case, with respect to the number x in the ring of the residue class modulo (p / 2), there are inverse elements x ^-1 only for odd numbers. These numbers are elements of the multiplicative group of the residue class ring modulo (p / 2). In this case, the inverse elements for decoding the message can be calculated:

x ^-1 ≡x ^q (mod (p / 2)), where q = 2 ^(k-2) -1.

To calculate the reciprocal values, the number of multiplications in the ring of the residue class modulo p / 2 = 2 ^k-1 decreases by more than four times with respect to the calculation of the reciprocal values in the final field F _p , p = 2 ^k +1, for which the Euler function φ (p) = 2 ^k . In this case, q <2 ^k -1 more than four times.

Since the number k for the residue class ring modulo p is not limited to values k ∈ 2, 4, 8, 16, but can take any integers greater than one, this increases the possibility of adjusting the range of changes in the code resistance to attacks based on known or selected initial ones texts.

In this case, the generated pseudo-random sequence of characters in the form of binary vectors of length k bits is a pseudo-random sequence of characters {0, 1, 2, ..., p-1}, has the same period N = 2 ⁿ -1 as the pseudo-random sequence of binary numbers, and provides statistical uniformity of the characters used.

By skipping the shift register clock cycles, for which the characters of the pseudo-random sequence take even values, a pseudo-random sequence of characters x will be formed from the odd numbers 1, 3, 5, 7, ..., p-1, which is used to encode the characters of the source text α by raising them to a power corresponding to the symbols of the pseudo-random sequence x. In this case, the encoded message will represent a sequence of characters β defined by the formula

β≡α ^x (modp)

Since the number p = 2 ^k is even, the Euler function φ (p) = (p / 2) and, in accordance with the Euler-Fermat theorem, will have the following identity

α ^{1 + mφ (p)} = α ^{1 + m (p / 2)} ≡ α (modp).

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

m is an arbitrary positive integer,

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

(p / 2),

. В этом случае вычисленные на приемной стороне значения символов x^-1 в кольце класса вычетов по модулю (p/2) позволяют реализовать обратные преобразования для декодирования исходного текстаthen the relation

. In this case, the values of the symbols x ^-1 calculated on the receiving side in the ring of the residue class modulo (p / 2) make it possible to implement inverse transformations for decoding the source text

.

.

Since the pseudo-random sequence x includes only odd characters 1, 3, 5, ..., p-1, all of them are elements of the multiplicative group of the residue class ring modulo p / 2 and will have inverse values x ^-1 , which can be determined according to the formula

x ^-1 ≡x ^{φ (p / 2) -1} (mod (p / 2)),

where φ (p / 2) is the Euler function for the number (p / 2).

Because (p / 2) = 2 ^k-1, then φ (p / 2) = 2 ^k-2. In this case, x ^-1 can be calculated by the formula

x ^-1 ≡x ^q (mod (p / 2)),

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

Since cryptographic transformations use operations of raising characters to a power modulo p, and a pseudo-random sequence of characters is formed according to the principle of a compression generator with an uneven movement of the shift register, the opening of the state of the shift register is excluded if there are any characters of the source and corresponding characters of the encoded text. This is due to the fact that in order to determine the characters of a pseudo-random sequence from the known characters of the source and encoded text, it is necessary to calculate the discrete logarithm, which can be ensured only as a result of total enumeration of the characters of this field, and to determine the state of the shift register from the calculated characters of the pseudo-random sequence, it is necessary to know the characters of the pseudo-random sequences for skipped clock cycles of the shift register, the beginning and number of which in the process is sequential The motion of the shift register changes according to a pseudo-random law. This ensures that the code is resistant to attacks based on well-known and selected source codes.

The possibility of technical implementation of the claimed method is illustrated as follows. The security key can be generated by entering a password from the keyboard or from a magnetic storage medium into a pseudo-random number generator, receiving at the output a security key of the required size.

The formation of a pseudo-random sequence of maximum length containing 2 ⁿ -1 characters can be achieved by using a linear shift register with n digits, the feedback of which is determined by the form of the selected primitive polynomial of degree n. Finding primitive polynomials of degree n is described in [4] on pp. 106-110.

The formation of a pseudo-random sequence of characters of the final field F _p in the form of binary vectors of length k bits can be accomplished by taking information from k different bits of the shift register, the numbers of which can be determined by the value of the entered security key K. For example, by determining the generating element

l ₀ ≡K (mod q), if l ₀ <2, then l ₀ = 2,

and calculating the number of the discharge register shift according to the formula

.l ₁ = l ₀ , l _i ≡l ₀ l _i-1 (mod q),

.

,...,

будут различны.The q value is selected from primes and for a shift register having 256 bits, q = 257, for a shift register having 128 bits, q = 127. In this case, due to raising to the power of the generating number l ₀ we will pass from one element of the field F _q to another. Moreover, as shown in [4] p. 9, if l ₀ is an element of order k, then all elements l ₀ ,

, ...,

will be different.

A pseudo-random sequence of characters can be formed as a “compression generator” by taking information from k bits of the shift register and skipping those clock cycles of the shift register for which the characters of the pseudo-random sequence take even values.

The generated pseudo-random sequence is used in cryptographic transformations when converting a data stream into an encoded message:

α ^x ≡β (mod p)

Four more options for generating pseudorandom sequences of characters in the form of binary vectors can be used.

1. Pseudorandom sequences of characters of the multiplicative group of the residue class ring modulo p = 2 ^k are formed as binary vectors of length k bits by using the symbol "1" in the zero bit of the binary vector, and for the remaining bits of the binary vector, use characters removed from k-1 different bits of the shift register

2. Change the number of bits k from which information is taken for the pseudo-random sequence of characters of the final field F _p , p = 2 ^k +1 in accordance with the change in the initial filling of the shift register.

3. Change the numbers of the bits of the shift register, from which information is removed for the pseudo-random sequence of characters of the final field, in accordance with the change in the initial filling of the shift register.

4. Change the reading order for the pseudo-random sequence of characters of the final field in accordance with the change in the initial filling of the shift register.

The formation of a pseudo-random sequence of characters according to claim 1, 2, 3 and 4 increases the resistance of the code to attacks based on known and selected source texts when generating a security key or a binary vector of a pseudo-random sequence of small length.

The conversion of the data stream into an encoded message is carried out by breaking the data stream of the source text into blocks in the form of α symbols of binary vectors of length k bits, converting the even symbols of the source text into odd ones by replacing the binary vector of the symbol "0" with the symbol "1" in the zero bit, calculate modulo (p = 2 ^k ) the values of the symbols β of the encoded message in accordance with the selected encoding function, α ^x ≡ β (mod p), convert the resulting number β to a binary vector, while in the zero bit of the binary vector I replace t character "1" to character "0" for even characters of the source text and transmit the encoded message on the communication line.

The proposed method can be implemented using a computer or device.

Figure 1 presents the structural diagram of the device, where

block 1 - device for generating a security key and an initial signal;

block 2 - shift register;

block 3 - shaper pseudo-random sequence;

block 4 - encoding device;

block 5 is a transmitting device.

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

For simplicity, the description of the operation of the device will use small numbers. We assume that the shift register has 6 digits (the key length is 6 bits), and the entire alphabet of the source text contains 16 characters, then a binary vector 4 bits long can be used to transmit one character, and the number p = can be chosen as a comparison module 16.

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

λ ⁶ + λ ⁵ +1

For the selected primitive polynomial, the block diagram of the feedback shift register is shown in FIG. 2.

Formed in block 1 (Fig. 1) using a random number generator, a security key 6 bits in length

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

where 0 = λ _1, λ ₂ = 0, λ ₃ = 0, λ ₄ = 1, λ ₅ = 1, λ 1 = _6;

enters the shift register and is used to initially fill the bits of the shift register. Binary symbols from the 5th and 6th bits of the shift register are received in each operation cycle at the input of the adder 12 modulo two, and from the output of the adder modulo two symbols ε are fed to the input of the first bit of the shift register (block 6, Fig. 2). In this case, the state of the discharges for each cycle during the operation of the shift register is determined by the expression

, λ₁=ελ _i = λ _i-1 for

, λ ₁ = ε

If the characters will be removed from the sixth digit λ ₆ of the shift register (block 11, figure 2), then the binary pseudorandom sequence of the maximum period will have the form

{1110000010000110001010011110100011

100100101101110110011010101111}.

Note that on the period of this sequence, any nonzero set of six digits 0 and 1 occurs only once.

If we take binary numbers from the 1st, 2nd, 3rd and 4th digits of the shift register (blocks 6, 7, 8, 9, Fig. 2) and at each clock cycle of the shift register with the set <λ ₁ , λ ₂ , λ ₃ , λ ₄ > we will compare the binary vector (number) y = λ ₁ + 2λ ₂ +2 ² λ ₃ +2 ³ λ ₄ , then the sequence of binary numbers in the process of register operation can be considered as a sequence of y numbers (characters) {0, 1, 2 , ..., 15} in the form

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, ...}.

An analysis of the generated sequence y shows that on the interval corresponding to the period equal to 63 clock cycles of the shift register, each of the symbols {1, 2, ..., 15} occurs exactly four times. A symbol corresponding to zero occurs exactly three times, while in the sequence y there are no hidden periodicities and statistical uniformity of the symbols used is ensured.

Since the shift register does not use clock cycles in which the characters y take even values, a pseudo-random sequence of numbers of characters) 1, 3, 5, 7, 9, ..., 15 is formed 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, ...

The security key 111000 generated in block 1 (Fig. 1) is supplied to block 2. In block 3, a pseudo-random sequence of odd characters is formed.

The generated pseudo-random sequence of characters x in the form of binary vectors is fed to the encoding device 4 (Fig. 1), where the incoming data stream α is converted into an encoded message β in accordance with the selected cryptographic conversion, while even characters of the source text are replaced by odd ones, for example

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

α = 3, 3, 5, 5, 7, 7, 9, 9, 11, 11, 13, 13, 15, 11 ,,

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

β = 11, 3, 3, 13, 7, 7, 9, 9, 3, 3, 5, 13, 1, 3 ,.

For the obtained values of β, a binary vector is formed and transmitted using the device 5 of FIG. 1 to the receiving end of the radio link, while the odd characters of the binary vector β are replaced with even characters for the source text by replacing the binary vector of the character "1" with the character " 0 ".

β = 10, 3, 2, 13, 6, 7, 8, 9, 2, 3, 4, 13, 0, 3 ,.

At the receiving end of the radio link, the received sequence of symbols β is decoded in accordance with the established cryptographic conversion, while even symbols of the binary vector β are replaced with odd ones by replacing the binary vector of the symbol “0” with the symbol “1” in the zero bit, and for the found symbol α the odd the characters are replaced with even ones by replacing in the zero bit of the binary vector of the received result the character "1" with the character "0".

(mod16).α≡

(mod16).

Since p = 16, k = 4, the calculation of x ^{-1 is} carried out according to the formula x ^-1 ≡x ³ (mod8). Then, for the considered example, the values of the corresponding symbols when decoding the message will look like:

β = 10, 3, 2, 13, 6, 7, 8, 9, 2, 3, 4, 13, 0, 3 ,.

β = 11, 3, 3, 13, 7, 7, 9, 9, 3, 3, 5, 13, 1, 3 ,.

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

x ¹ = 3, 5, 1, 7, 7, 5, 1, 3, 3, 7, 7, 1, 3, 7,

α = 3, 3, 5, 5, 7, 7, 9, 9, 11, 11, 13, 13, 15, 11 ,,

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

The implementation of the proposed method does not cause difficulties, since all the blocks and nodes included in the device that implements the method are well known and widely described in the technical literature.

Information sources

1. Russian encryption standard USSR standard GOST 28147-89 Information processing systems. Cryptographic protection. Cryptographic conversion algorithm.

2. S. Maftik. Protection mechanisms in computer networks, M., 1993

3. V.I. Nechaev. Elements of cryptography. Fundamentals of the theory of information security, M .: Higher school, 1999

4. V.I. Tupota. Adaptive means of information security in computer networks, - M .: Radio and communications, 2002

5. The method of stream coding of discrete information. Patent for invention No. 2251816 according to application No. 2003117834 dated June 16, 2003.

Claims (2)

1. The method of stream coding of discrete information, which consists in generating a security key in the form of a binary vector with a length of n bits, serves it for the initial filling of a shift register with feedback having n bits and generating a pseudorandom sequence of maximum length containing 2 ⁿ -1 binary characters, form a pseudo-random sequence of characters in the form of binary vectors of length k bits by taking information from k different bits of the feedback shift register, the numbers of which determine p about the value of the security key, while forming a pseudo-random sequence of characters from odd values of the characters by skipping the shift register feedback cycles for which the characters of the pseudo-random sequence take even values, break the data stream of the source text into block characters in the form of binary vectors of length k bits , alternately convert the characters of the source text into an encoded message by raising them to the power corresponding to the characters of the pseudo-random sequence, and before they are transmitted via a communication line, characterized in that they convert even characters of the source text data stream to odd ones by replacing the character “0” with the character “1” in the zero bit of the binary vector of the source text data stream, and raising the characters of the source text to a power is performed in the ring the class of residues modulo p = 2 ^k , while the binary vector of the result of raising the characters to a power for even characters of the source text is converted by replacing the binary vector of the character "1" with the character "0" in the zero bit. 2. The method according to claim 1, characterized in that the pseudo-random sequence of characters is formed in the form of binary vectors of length k bits by using the character "1" in the zero bit of the binary vector, and for the remaining bits of the binary vector, characters are removed from k-1 different bits of the shift register.

Images