Cryptographic algorithms.

a) introduction

Cryptology is a science dealing with encryption and decryption methods. It consists of two branches: cryptography and cryptanalysis.

Cryptography is the science of how to transform (encrypt) information in order to protect it from illegal users.

Cryptanalysis is the science (and the practice of its application) about the methods and methods of cipher disclosure.

Encryption (encryption) - the process of applying a cipher to the protected, i.e. transformation of information (plaintext) of the protected into an encrypted message (ciphertext, cryptogram) using certain rules contained in the cipher.

Decryption is a process that is inverse to encryption, that is, the transformation of an encrypted message into information protected by certain rules contained in the cipher.

A cipher is a set of inverse transformations of a data set into a set of encrypted data.

The key is the specific secret state of some parameters of cryptographic transformation algorithms.

The ability of a cipher to withstand all sorts of attacks on it is called cipher strength. By attack on a cipher they understand the attempt to open this cipher.

Cryptoalgorithms (ciphers) are divided into three categories (Table 6.1):

1) keyless algorithms that do not use keys in the process of cryptographic transformations;

2) single-key algorithms that use some secret key in their calculations;

3) two-key algorithms, in which at different stages of the computation two types of keys are used: secret and public.

Let us briefly review the main types of cryptoalgorithms:

- hash functions. Perform a convolution of variable length data into a sequence of fixed size. Used to confirm data integrity, in electronic signature schemes, in user authentication schemes;

- random number generators. Necessary for calculating the ES and for authentication algorithms;

- Symmetric encryption algorithms - the same key is used for encryption and decryption.

Symmetric encryption algorithms come in block and stream:

a) block encryption - information is divided into blocks of fixed length (64 or 128 bits), after which these blocks are alternately encrypted. In different algorithms or in different modes, blocks can be encrypted independently of each other or with coupling — when the result of encrypting the current data block depends on the value of the previous block or the result of encrypting the previous block;

b) stream encryption — used when information cannot be broken into blocks. Data is encrypted bit by bit or by character;

- pseudorandom number generators - based on symmetric encryption algorithms;

- authentication algorithms - allow you to check that the user really is who he claims to be.

Classification of cryptographic algorithms

An example authentication algorithm:

1) the server generates a random number;

2) sends it to the user;

3) the user encrypts the received number with a secret key and sends the result to the server;

4) the server encrypts the received data with the same secret key;

5) the server compares the received ciphertext with the initial number. Asymmetric encryption algorithms - use two types of keys: a public key for encrypting information and a secret key for decrypting. The secret and public keys are interconnected by a rather complicated relationship, the main thing in which is the ease of calculating the public key from the secret and the impossibility (for a limited time with real resources) of calculating the secret key from the public one.

b) Symmetric encryption algorithms

The overwhelming majority of modern symmetric encryption algorithms work in a very similar way: some transformation is performed on ciphertext with the participation of an encryption key, which is repeated a certain number of times (rounds). At the same time, by the type of transformations are repeated, encryption algorithms can be divided into several categories. There are also various classifications here. One of the most popular types of symmetric encryption is encryption algorithms based on the Feistel network.

b .1) Algorithms based on the network of Feistel

The Feistel network implies splitting the processed data block into several subblocks (most often into two), one of which is processed by a certain function and superimposed on one or several other subblocks. Figure 1 shows the structure of the algorithms most commonly found on the basis of the Feistel network.

An optional function argument, denoted as, is called a round key. The key of the round is the result of processing the encryption key by the key expansion procedure, the task of which is to obtain the required number of keys from the initial encryption key of a relatively small size.

The imposition of the processed subunit on the untreated one is most often performed using a logical exclusive OR (XOR) operation. Quite often, instead of XOR, modulo addition is used, where is the subblock size in bits. After overlaying subblocks are swapped, that is, in the next round of the algorithm, another data subblock is processed.

Based on the Feistel network, the majority of modern encryption algorithms are based on the many advantages of this structure, among which the following should be noted:

Figure 1 - Feistel Network

- algorithms based on the Feistel network can be designed in such a way that the same algorithm code can be used for encryption and decryption - the difference between these operations can be only in the order of using the keys: this property of the algorithm is most useful for its hardware implementation or on platforms with limited resources;

- algorithms based on the Feistel network are the most studied - a huge number of cryptanalytic studies are devoted to such algorithms, which is an undoubted advantage both in the development of the algorithm and in its analysis. As an example, consider the algorithm GOST 28147-89, which is mandatory for use as encryption algorithms in state organizations of the Russian Federation and in a number of commercial organizations.

b . 2) Algorithm GOST 28147-89

The algorithm of GOST 28147-89 is shown in the figure. As can be seen, the scheme of this algorithm is quite simple, which uniquely simplifies its software or hardware implementation (Fig. 2).

The GOST 28147-89 algorithm encrypts information in blocks of 64 bits, which are divided into two sub-blocks of 32 bits (and). The subblock is processed in a definite way, after which its value consists of the value of the subblock (addition is performed modulo 2), then the subblocks are swapped. Such a transformation is performed a certain number of rounds: or, depending on the mode of operation of the algorithm. The following operations are performed in each round:

Figure 2 - The algorithm scheme GOST 28147-89

1) overlay key. The content of the subunit is folded modulo a part of the key. The encryption key of the GOST 28147-89 algorithm has a dimension of 256 bits, and this is its 32-bit part, that is, the 256-bit encryption key is represented as a concatenation of 32-bit subkeys. The encryption process uses one of these subkeys, depending on the round number and the mode of operation of the algorithm;

2) table replacement. After the keys are superimposed, the subblock is divided into 8 parts by 4 bits, the value of each of which is individually replaced in accordance with the replacement table for this part of the subblock. Table replacements (Substitution boxes, S-boxes) are often used in modern encryption algorithms. Table replacement is used as follows: a block of data of a certain dimension (in this case, -bit) is supplied to the input, the numerical representation of which determines the number of the output value. For example, we have an S-box of the following form: 4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1. Let the 4-bit block “ 0100 ", that is, the value" 4 ". According to the table, the initial value will be 15, that is, the value “1111” (0 is replaced by 4, 1 by 11, value 2 does not change, etc.). As you can see, the scheme of the algorithm is very simple, which means that the greatest load on data encryption falls on the replacement table;

3) bitwise cyclic shift left to bit.

c) Asymmetric encryption algorithms

The idea of ​​public-key cryptography is very closely related to the idea of ​​one-way functions, that is, such functions f (x), that by the known it is quite simple to find the value of f (x), while defining with f (x) is impossible for a reasonable time. But the one-way function itself is useless in its application: it can encrypt a message, but it cannot be decrypted. Therefore, public key cryptography uses one-way functions with a loophole. A loophole is some secret that helps decipher. That is, there is such that knowing f (x) and y, you can calculate x. For example, if you disassemble a clock into many parts, it is very difficult to assemble a newly working clock. But if there is an assembly instruction (loophole), then this problem can be easily solved. The scheme of the asymmetric encryption algorithms is as follows (Fig. 3):

- selects the pair (e, d) and sends the encryption key e (public key) over the open channel, and the decryption key d (private key) is protected and secret (it should not be transmitted over the open channel);

- to send the message m for B, A uses the encryption function defined by the public key e: Ee (m) = c, c, - the received ciphertext;

- B decrypts the ciphertext c, applying the inverse Dd transform, uniquely determined by the value d.

Figure 3 Asymmetric cipher operation scheme

d) Electronic signature

Electronic signature - an attribute of an electronic document, which allows you to establish the absence of distortion of information in an electronic document from the time you generate the electronic signature and verify that the signature belongs to the holder of the signature key certificate. The value of the props is obtained as a result of cryptographic transformation of information using the private key of the electronic signature. A digital signature or digital signature scheme is a set of algorithms and protocols that allow for building informational interaction between two or more participants so that the fact of the authorship of the transferred data file, “signed” by one of the participants, can be reliably confirmed or disproved by a third party, “independent arbitration. " A similar scheme is needed for all electronic data processing systems, where there is no complete mutual trust between participants in the information process, first of all it concerns the financial sector. Any digital signature scheme implies adding an additional code to the “signed” data array — the “digital signature” itself, which only the message author can generate, has a private signature key, and all others can only verify the compliance of this “signature” with the signed data.