Blind detection of parameters of LFSR-based scramblers in digital data

Master thesis in the field

Electrical Engineering

Communication-system

Abstract

Blind detection of parameters of LFSR-based scramblers in digital data

In digital telecommunication systems, linear scramblers are used both for simple encryption and for breaking large sequences of identical bits. The bit sequence issue, i.e. a large number of 0's and 1's in a row, usually leads to synchronization problems. In fact, the methods of whitening the statistics of the digital source without using the content data are called scrambling. In telecommunications and decoders, a scrambler is a device that manipulates and changes data before it is sent. These changes are done in reverse in the receiver in order to reach the primary data.

In this thesis, after introducing the scrambler and its components, the methods of finding the scrambler parameters in two cases of having the sequence of the input text (Berlkamp-Messi method) and the other case of having only the scrambled sequence (Clausio algorithm) are discussed and the results are examined. After that, we consider the case where the scrambled data has an error after passing through the channel, and in the presence of channel noise, we identify the scrambler parameters and observe the effect of noise on the output data of two types of scramblers (multiplicative scramblers and collective scramblers). After that, we investigate the feedback polynomial identification method of linear scramblers assuming that the source bits are encoded by error correction coding before they are scrambled.

Key words: Scrambler, linear transmission registers with feedback, encryption, symmetric binary channel BSC, signal listening

1-1- What is a scrambler and why do we use it?

A digital data transmission system always causes errors and damages in sending data, and the amount of these disturbances and damages changes depending on the statistics of the source. Sometimes synchronization, interference and equalization problems are related to source statistics. Although the use of internals in sending codes makes the system performance independent from the source statistics to some extent, there are always dependencies, in addition, adding internals data causes problems such as increasing the rate of sent symbols or adding alignment in symbols. In a code sending system, if we assume that the symbols sent are statistically independent, it will be much easier to analyze and find errors. We call such a source whose symbols are statistically independent from each other as a white source because its analysis is like Gaussian white noise. Whitening methods of digital source statistics without using content data are described as scrambling[1]. In telecommunications and decoders, a scrambler[2] is a device that manipulates and changes data before it is sent. These changes are done in reverse in the receiver to get the original data. Various scrambling methods are used in satellite and PSTN modems [3]. The scrambler can be placed just before an FEC encoder[4] or it can be placed after the FEC and before the modulation block.

Our effort in this research is to investigate different methods and techniques in identifying the parameters of linear scramblers. This is done by having a string of output bits and based on assumptions on the input bits of the scrambler. Of course, someone who does this using the output bits must consider two categories: first, error correction, and then extracting the scrambler parameters. Considering the linearity of the discussed scramblers, using algebraic methods to estimate the scrambler parameters is the most efficient method. Especially the linear shift registers with feedback, whose feedback function is a linear function, which is further explained in this regard.

1-2- Advantages of using scrambling before sending data

With this method, without adding content data to the sent message, the accuracy of Time Recovery can be increased in the receiver equipment.

By dispersing the energy throughout the carrier signal, the possibility of signal interference It reduces the carrier and eliminates the dependence of the spectral density between the scrambled data and the actual data sent.

It increases the security of data transmission and scramblers can be used in encryption.Because the ideal state of a ciphertext is to be a completely random sequence. In other words, the bits of the sequence should be completely independent from each other and the probability of being zero and one is equal, and a long and i.i.d sequence can be produced from a limited and short key.

1-3- Pseudo-random sequences

In order to simulate and test digital communication systems, we need sequences that are approximations of ideal binary random sequences. We use linear feedback shift registers in the generation of binary pseudo-random sequence. With a simple modification to these circuits, they can be used as self-synchronous digital scramblers/descramblers. Scramblers allow the tracking loops at the receiver to be protected and hidden in a hidden manner by breaking up the long string of 0's or 1's in the data. If the data rate is very high, these scramblers and descramblers can be made with simple circuits. At moderate data rates such as telephone line modems, it can be implemented with a few simple lines of code. By combining this function and other features into the code, you can eliminate additional hardware. This method increases reliability and reduces production costs.

An ideal binary random sequence is actually an independent infinite sequence with a uniform distribution in which the random variables accept any of the values ??0 or 1 with a probability of 0.5. This sequence can be modeled by the data string produced by the binary sources. With linear feedback shift registers, the best approximation for binary random sequences can be achieved. The sequence obtained in this way is called pseudo-random, pseudo-noise, maximum-length, or sequence.

To simulate a random binary sequence, we are looking for a shift register that, if its length is a register, the sequence it produces has the largest possible period, i.e. Such a sequence is called a "maximum length sequence". It can be shown that the shift register produces a sequence with the maximum length, whose connection polynomial (in the next chapter, it is explained about the connection polynomial) is of the fundamental polynomial type. There are fundamental polynomials of any degree. A necessary condition for a polynomial to be fundamental is that it is indecomposable, but this condition is not sufficient. When a polynomial with binary coefficients in the binary basis is indecomposable when we cannot decompose it into a binary polynomial with coefficients and at least 1.

1-4- Criteria of the degree of randomness of a sequence

The degree of randomness of a sequence refers to the degree of unpredictability of a sequence. Any random sequence produced by processes used in practical applications is not necessarily random. Here we are going to state some characteristics of random sequences and we call any sequence that has these characteristics random or more precisely pseudo-random.

Criteria and principles provided by Glomb for the randomness of a sequence:

Glomb criteria for sequences with a period of periodicity are from the vector space in the field, but because the field of this thesis is on binary sequences in the field is We express these properties for binary sequences.

Balance law: in each period of these sequences, the number of zeros and the number of ones is almost equal. One-eighth of them have a length of three and are In total, the number of executions of zeros and executions of ones is equal.

Self-dependence and cross-correlation: If and are two binary sequences with periodicity, their cross-correlation is shown with the symbol and defined as follows:

which can be calculated as the inner product of two vectors and in which the indices are calculated by the scale. If it is, then the autocorrelation of the sequence is calculated with this relationship. In this case, the correlation value of a sequence is with its own shift, and its maximum value is when it is equal to . Now for a random sequence, the autocorrelation function has the following two values: It is a constant value.