Scramblers.
Recently, the scope of application of scrambling algorithms has significantly decreased.
This is primarily due to the decrease in the volume of bit-by-bit sequential transmission of information, for the protection of which these algorithms were developed.
Packet-switched networks are used almost everywhere in modern systems, for the maintenance of confidentiality of which block ciphers are used.
And their cryptographic resistance exceeds, and sometimes quite significantly, the cryptographic resistance of scramblers.
The essence of scrambling is the bit-by-bit change of the data stream passing through the system. Almost the only operation used in scramblers is XOR – «bitwise exclusive OR».
In parallel with the passage of the information flow in the scrambler, a bit stream is generated according to a certain rule — the coding stream.
Both direct and reverse encryption is carried out by superimposing the coding sequence on the original one by XOR.
The coding sequence of bits is generated cyclically from a small initial volume of information — the key according to the following algorithm.
The values of certain digits are selected from the current set of bits and added together by XOR.
All bits are shifted by 1 bit, and the newly obtained value («0» or «1») is placed in the vacated least significant bit. The value that was in the most significant bit before the shift is added to the coding sequence, becoming its next bit (see Fig. 1).
Cryptography borrowed the binary system of recording such schemes from the theory of data transmission. According to it, the scrambler shown in the figure is written with the combination «100112 » – the units correspond to the digits from which the bits are removed to form feedback.
Let's consider an example of encoding the information sequence 0101112 with a scrambler 1012 with an initial key of 1102.
As we can see, the scrambler device is extremely simple. Its implementation is possible both on an electronic and electrical basis, which ensured its wide application in the field. Moreover, the fact that each bit of the output sequence depends only on one input bit further strengthened the position of scramblers in protecting streaming data transmission. This is due to the inevitable interference in the transmission channel, which can distort in this case only those bits to which they fall, and not the group of bytes associated with them, as is the case in block ciphers.
Decoding of scrambled sequences occurs according to the same scheme as encoding. This is why the resulting encoding by «exclusive OR» is used in the algorithms — a scheme that is uniquely restored during decoding without any additional computational costs. Let's decode the resulting fragment.
As you can guess, the main problem of ciphers based on scramblers is the synchronization of the transmitting (encoding) and receiving (decoding) devices. If even one bit is missed or inserted incorrectly, all transmitted information is irreversibly lost.
Therefore, in encryption systems based on scramblers, a lot of attention is paid to synchronization methods.
In practice, a combination of two methods is usually used for these purposes:
a) adding synchronization bits to the information flow, known in advance to the receiving side, which allows it, if such a bit is not found, to actively begin searching for synchronization with the sender, and
b) the use of high-precision time pulse generators, which allows decoding of received bits of information «from memory» without synchronization at moments of synchronization loss.
The number of bits covered by the feedback, i.e. the bit capacity of the memory device for generating the coding sequence of bits, is called the bit capacity of the scrambler. The scrambler shown above has a bit capacity of .
In terms of cryptographic strength parameters, this value is completely identical to the length of the block cipher key, which will be analyzed further. At this stage, it is important to note that the larger the scrambler bit depth, the higher the cryptographic strength of the system based on its use.
If the scrambler operates for a sufficiently long time, it will inevitably become looped. After a certain number of cycles have been performed, a combination of bits will be created in the scrambler cells that has already appeared in it once, and from that moment on, the coding sequence will begin to repeat cyclically with a fixed period.
This problem is inherently unsolvable, since there cannot be more than 2N bit combinations in the N digits of the scrambler, and therefore, after a maximum of 2N-1 cycles, the combination will definitely repeat.
The combination «all zeros» is immediately excluded from the scrambler state graph chain – it brings the scrambler to the same position «all zeros». This also indicates that the key «all zeros» is not applicable to the scrambler.
Each bit generated during the shift depends only on a few bits of the combination currently stored by the scrambler. Therefore, after repeating a certain situation that has already been encountered in the scrambler, all the following ones will exactly repeat the chain that has already passed through the scrambler.
Different types of scrambler state graphs are possible.
Figure 2 shows approximate options for a 3-bit scrambler.
In case A, in addition to the always present cycle «000»>»000″, we see two more cycles — with 3 states and 4 states. In case B, we see a chain that converges to a cycle of 3 states and never leaves it.
And finally, in case B, all possible states except zero are combined into one closed cycle.
Obviously, it is in this case, when all 2N-1 states of the system form a cycle, that the repetition period of the output combinations is maximum, and there is no correlation between the cycle length and the initial state of the scrambler (key), which would lead to the appearance of weaker keys.
Fig. 2.
And here mathematics presented another gift to the applied science, which is cryptography.
A consequence of one of the theorems proves (in terms applicable to scrambling) that for a scrambler of any bit depth N, there always exists such a choice of bits covered by feedback that the bit sequence generated by them will have a period equal to 2N-1 bits.
For example, in an 8-bit scrambler, when covering the 0th, 1st, 6th and 7th digits, all numbers from 1 to 255 are actually sequentially passed through during the generation of 255 bits, without repeating even once.
Circuits with feedback selected according to this law are called longest sequence generators (LSGs), and they are used in scrambling equipment.
Of the many PND generators of a given bit capacity, at the time when they were implemented on an electric or minimal electronic base, those were selected in which the number of bits participating in the creation of the next bit was minimal. Usually, the PND generator could be achieved in 3 or 4 connections.
The bit capacity of the scramblers themselves exceeded 30 bits, which made it possible to transmit up to 240 bits = 100 MB of information without fear of the beginning of the repetition of the coding sequence.
IDPs are inextricably linked with the mathematical theory of irreducible polynomials. It turns out that it is sufficient for a polynomial of degree N not to be representable modulo 2 as a product of any other polynomials for a scrambler based on it to create an IDP.
For example, the only irreducible polynomial of degree 3 is x3+x+1, in binary form it is written as 10112 (the ones correspond to the present digits).
Scramblers based on irreducible polynomials are formed by discarding the most significant digit (it is always present, and therefore carries information only about the degree of the polynomial), so based on the specified polynomial, we can create a scrambler 0112 with a cycling period of 7 (=23-1).
Naturally, in practice, polynomials of much higher orders are used. And tables of irreducible polynomials of any order can always be found in specialized mathematical reference books.
A significant drawback of scrambling algorithms is their vulnerability to falsification. This problem will be discussed in more detail in the next lecture, as applied to the creation of entire cryptosystems.