Annotation: This lecture has several goals. Show the difference between traditional and modern symmetric key ciphers. Bring modern block ciphers and discuss their characteristics. Explain why modern block ciphers should be designed as substitution ciphers. Introduce the components of block ciphers such as P-boxes and S-boxes. Discuss and show the difference between two classes of ciphers: Feistel ciphers and non-Feistel ciphers. Discuss two types of attacks specifically aimed at breaking modern block ciphers: differential and linear cryptanalysis. Introduce the concept of "stream ciphers" and show the difference between synchronous and non-synchronous ciphers. Discuss linear versus nonlinear feedback shift registers to implement stream ciphers.

Traditional ciphers with symmetric keythe ones we've studied so far are symbol-oriented. With the advent of the computer, bit-oriented ciphers became necessary. Because the information to be encrypted is not always just text; it can also consist of numbers, graphics, audio and video data. It is convenient to convert these data types to a bitstream in order to encrypt that stream, and then transmit the encrypted stream. In addition, when the text is processed at the bit level, each character is replaced by 8 (or 16) bits, which means that the number of characters becomes 8 (or 16) times more. Mixing more characters increases security.

This chapter provides the necessary foundation for learning modern block and stream ciphers, which are covered in the next three chapters. Most of this chapter is devoted to discussing the general ideas of modern block ciphers, and only a small part is devoted to the principles of modern stream ciphers.

7.1. Modern block ciphers

Modern block cipher with symmetric keys encrypts the n-bit block of the original text or decrypts the n-bit block of the ciphertext. The encryption or decryption algorithm uses a k-bit key. The decryption algorithm must be the inverse of the encryption algorithm, and both operate on the same encryption key so that Bob can recover the message Alice sent. Figure 7.1 shows the general idea of \u200b\u200bencryption and decryption in a modern block cipher.

Figure: 7.1.

If the message is less than n bits, padding must be added to create this n-bit block; if the message has more than n bits, it must be split into n-bit blocks and, if necessary, add padding to the last block. Common values \u200b\u200bfor n are usually 64, 128, 256, or 512 bits.

Example 7.1

How many extra bits do you need to add to a 100-character message if 8-bit ASCII is used for encoding and the block cipher accepts 64-bit blocks?

Decision

Encode 100 characters using 8-bit ASCII. This message contains 800 bits. The original text must be divisible by 64 without a remainder. If | M | and | Pad | - message length and filling length, then

| M | + | Pad | \u003d\u003d 0 mod 64 -\u003e | Pad | \u003d -800 mod 64 -\u003e 32 mod 64

This means that 32 bits of padding (eg zeros) must be added to the message. The text will then be 832 bits, or thirteen 64-bit blocks. Note that only the last block contains padding. The encryptor uses the encryption algorithm thirteen times to create thirteen blocks of ciphertext.

Substitution, or transposition

A modern block cipher can be designed to act as a substitution cipher or as a transposition cipher. This is the same idea used in traditional ciphers, except that characters to be replaced or moved contain bits instead of characters.

If the cipher is designed as substitution cipher, bit values \u200b\u200b1 or 0 in the source text can be replaced with either 0 or 1. This means that the original text and the ciphertext can have a different number of units. A 64-bit block of original text, which contains 12 zeros and 52 ones, can be represented in ciphertext with 34 zeros and 30 ones. If the cipher is designed as permutation (transposition) cipher, the bits only change the order (move), keeping the same number of characters in the original and ciphertext. In any case, the number of possible n-bit sources or ciphers is 2 n, because each of the n bits used in a block can have one of two values \u200b\u200b- 0 or 1.2 64 blocks of 64 bits to find one that makes sense. If Eve could sample 1 billion blocks per second, then it would take her hundreds of years before this work could be successful.

b. In the second case (permutation), Eve knows that there are exactly 10 ones in the original text, because the transposition does not change the number of ones (or zeros) in the ciphertext. Eve can launch an exhaustive search attack using only those 64-bit blocks that are exactly 10 units. There is only (64!) / [(10!) (54!)] = 151 473 214 816 of 2 64 words of 64 bits, which are exactly 10 ones. Eve can test all of them in less than 3 minutes if she can do 1 billion tests per second.

Resistant to an exhaustive search attack, a modern block cipher must be designed as a substitution cipher.

09.07.2003

What is encryption?

Encryption has been used by mankind from the very moment when the first secret information appeared, that is, such, access to which should be limited. It was a long time ago - for example, one of the most famous encryption methods is named after Caesar, who, if not invented it himself, then actively used it (see sidebar).

Cryptography provides hiding the meaning of a message and revealing it by decrypting it using special algorithms and keys. We understand the key as a specific secret state of the parameters of the encryption and decryption algorithms. Knowing the key makes it possible to read the secret message. However, as you will see below, ignorance of the key does not always guarantee that the message cannot be read by a stranger.

The process of breaking a cipher without knowing the key is called cryptanalysis. The time it takes to break a cipher is determined by its cryptographic strength. The larger it is, the "stronger" the encryption algorithm. Even better, if you can't initially figure out whether the result of a hack is achievable.

Basic modern encryption methods

Among the variety of encryption methods, the following main methods can be distinguished:

• Algorithms of substitution or substitution - the characters of the original text are replaced with characters of another (or the same) alphabet in accordance with a predetermined scheme, which will be the key of this cipher. Separately, this method is practically not used in modern cryptosystems due to extremely low cryptographic strength.
• Permutation algorithms - the characters of the original text are interchanged according to a certain principle, which is a secret key. The permutation algorithm itself has low cryptographic strength, but it is included as an element in many modern cryptosystems.
• Gamma algorithms - the symbols of the original text are added to the symbols of a certain random sequence. The most common example is encrypting "username.pwl" files, in which operating system Microsoft Windows 95 stores passwords to network resources given user (passwords for entering NT servers, passwords for DialUp access to the Internet, etc.).

When a user enters his password when logging into Windows 95, a gamma (always the same) is generated from it using the RC4 encryption algorithm, which is used for encryption network passwords... The ease of guessing the password is due in this case to the fact that Windows always prefers the same gamut.

• Algorithms based on complex mathematical transformations of the source text according to a certain formula. Many of them use unsolved math problems. For example, the RSA encryption algorithm widely used on the Internet is based on properties of prime numbers.

Symmetric and asymmetric cryptosystems

Before moving on to individual algorithms, let's briefly consider the concept of symmetric and asymmetric cryptosystems. Generating a private key and encrypting a message with it is half the battle. But how can you send such a key to someone who should use it to decrypt the original message? The transmission of the encryption key is considered one of the main problems of cryptography.

Remaining within the framework of a symmetric system (as it is named because the same key is suitable for encryption and decryption), it is necessary to have a reliable communication channel for transmitting the secret key. But such a channel is not always available, and therefore the American mathematicians Diffie, Hellman and Merkle developed in 1976 the concept of a public key and asymmetric encryption... In such cryptosystems, only the key for the encryption process is publicly available, and the decryption procedure is known only to the owner of the secret key.

For example, when I want to be sent a message, I generate public and private keys. I send you open, you encrypt the message with it and send it to me. Only I can decrypt the message, since I did not give the secret key to anyone. Of course, both keys are related in a special way (in each cryptosystem in different ways), and the distribution of the public key does not destroy the cryptographic strength of the system.

In asymmetric systems, the following requirement must be met: there is no such algorithm (or it is not yet known) that would deduce the source text from the cryptotext and public key. An example of such a system is the well-known RSA cryptosystem.

RSA algorithm

The RSA algorithm (based on the first letters of the names of its creators Rivest-Shamir-Adleman) is based on the properties of prime numbers (and very large ones). Prime numbers are those numbers that have no divisors, except for themselves and one. And relatively prime numbers are those that have no common divisors except 1.

First, let's choose two very large primes (large initial numbers are needed to build large cryptographically strong keys. For example, the Unix program ssh-keygen generates keys with a length of 1024 bits by default).

Let's define the parameter nas a result of multiplication pand q... Let's choose a large random number and let's call it d, and it must be coprime with the result of multiplication (p -1) * (q -1).

Let us find a number e for which the relation

(e * d) mod ((p -1) * (q -1)) \u003d 1

(modis the remainder of the division, i.e. if e multiplied by d is divided by ((p -1) * (q -1)), then in the remainder we get 1).

The public key is a pair of numbers e and n, and closed - d and n.

When encrypting, the original text is treated as a number series, and on each of its numbers we perform an operation

C (i) \u003d (M (i) e) mod n.

The result is the sequence C (i), which will make up the cryptotext. Decoding of information occurs according to the formula

M (i) \u003d (C (i) d) mod n.

As you can see, decryption requires knowledge of the secret key.

Let's try on small numbers.

Install p \u003d 3, q \u200b\u200b\u003d 7... Then n \u003d p * q \u003d 21. We choose das 5. From the formula (e * 5) mod 12 \u003d 1 calculate e \u003d 17... Public key 17, 21 , secret - 5, 21 .

Let's encrypt the sequence "12345":

C (1) \u003d 1 17 mod 21 \u003d 1

C (2) \u003d 2 17 mod 21 \u003d 11

C (3) \u003d 3 17 mod 21 \u003d 12

C (4) \u003d 4 17 mod 21 \u003d 16

C (5) \u003d 5 17 mod 21 \u003d 17

Cryptotext - 1 11 12 16 17.

Let's check the decryption:

M (1) \u003d 1 5 mod 21 \u003d 1

M (2) \u003d 11 5 mod 21 \u003d 2

M (3) \u003d 12 5 mod 21 \u003d 3

M (4) \u003d 16 5 mod 21 \u003d 4

M (5) \u003d 17 5 mod 21 \u003d 5

As you can see, the result is the same.

The RSA crypto system is widely used on the Internet. When you connect to a secure server via SSL, install a WebMoney certificate on your PC, or connect to a remote server using Open SSH or SecureShell, then all these programs use encryption public key using the ideas of the RSA algorithm. Is this system really that reliable?

RSA Hacking Contests

Since its inception, RSA has been constantly exposed to brute-force attacks (brute force attacks). In 1978, the authors of the algorithm published an article where they presented a string encrypted with a method they had just invented. The first person to decipher the message was given a $ 100 reward, but that required a 129-digit number to be split into two factors. This was the first competition to hack RSA. The problem was solved only 17 years after the publication of the article.

The cryptographic strength of RSA is based on the assumption that it is extremely difficult, if not impossible, to determine the private key from the public key. This required solving the problem of the existence of divisors of a huge integer. Until now, no one has solved it using analytical methods, and the RSA algorithm can only be broken by exhaustive search. Strictly speaking, the claim that the factoring problem is hard and that breaking the RSA system is hard is also not proven.

The number obtained as a result of processing the message text by the hash function is encrypted using the RSA algorithm on the user's private key and sent to the addressee along with the letter and a copy of the public key. The addressee, using the sender's public key, performs the same hash function on the incoming message. If both numbers are equal, this means that the message is genuine, and if at least one character has been changed, then the numbers will not match.

One of the most common in Russia mail clients, program The bat!, has built-in capabilities to add digital signatures to letters (pay attention to the Privacy menu item when editing a letter). Read more about this technique in the article (see "PC World", No. 3/02).

Figure: 3

Cryptography

Cryptography is the science of the principles, means and methods of transforming information to protect it from unauthorized access and distortion. IN recent times it is developing very, very rapidly. It is an endless, exciting race that requires a lot of time and effort: cryptanalysts are cracking algorithms that until recently were standards and were widely used. By the way, recently mathematicians Dan Goldston (USA) and Kem Ildirim (Turkey) proved the first regularity in the distribution of prime numbers (until now, such regularities have not been noticed). Prime numbers are located on the number axis in some clusters, which makes them somewhat easier to find.

Mathematical research, conducted all over the world, constantly leads everything to new and new discoveries. Who knows, maybe we are on the verge of breaking the RSA algorithm or other cryptosystems based on unsolved mathematical problems.

Oleg Bunin - specialist in software development for large Internet projects, employee of Rambler, http: //www..htm).

Caesar's encryption system

An example of a replacement algorithm is the Caesar encryption system. This method is based on replacing each letter of the message with another by offsetting from the original by a fixed number of characters. Try to decipher the quatrain of Omar Khayyam (execution time - 10 minutes).

RLZ YOMEYZ AVBZHU IYZAVLU, BZHSCHLU ZHSCHEZZHZ ZHYUYOSCHEZ, EYSH YSHAZHFO ISYSCHYVESH BSHIZEZHV EESH ZHRSCHSCH: LF EMRSU YZEZESHG, RYU RLZ ISCHEESYUZYUKYUKLU, DYO RLZ ISCHEESYUZYUKYUKLU

Did you have time? Here is the "answer":

To live life wisely, you need to know a lot,

Two important rules remember to start:

You'd rather starve than eat anything

And it is better to be alone than with just anyone.

Decryption key: shift it by seven characters (take the seventh) to the left in alphabetical order. The alphabet is looped. The characters are not case sensitive.

Windows and passwords

How does Windows encrypt passwords?

The system takes the password, converts it to uppercase, truncates to 14 characters, then divides them into two halves of 7, encrypts each one separately and stores it in this way, which makes it somewhat easier to crack. By the way, when you come up with a password, keep in mind that a combination longer than 14 characters makes little sense.

AES (Advanced Encryption Standard) Competition

In the 80s. the United States adopted a symmetric encryption standard for internal use - DES ((Data Encryption Standard, there is a similar standard in Russia). But in 1997, when it became clear that the 56-bit DES key was not enough for a reliable cryptosystem, the American Standards Institute announced competition for a new standard algorithm, out of 15 options, the best one was chosen: the Belgian algorithm Rijndael (its name is made up of the authors' surnames - Rijmen and Daemen, reads “Reindal.” This algorithm is already embedded in various cryptographic tools supplied to the market). Other finalists competition was MARS, RC6, Serpent, TwoFish All these algorithms were found to be quite robust and successfully resist all well-known cryptanalysis methods.

Cryptographic hash functions

Cryptographic hash functions convert input data of any size to a fixed-size string. It is extremely difficult for them to find:

• two different datasets with the same transformation result (collision resistance); for example, the number of arithmetic operations required to find a data block also having a short message for the MD5 hash function is approximately 2 64;
• input value based on a known hashing result (irreversibility); for MD5, the estimated number of operations required to compute the original message is 2,128.

In the 21st century, cryptography plays a significant role in digital life modern people... Let's briefly consider the ways of encrypting information.

Cryptography is not just some kind of computer thing

Most likely, you have already encountered the simplest cryptography and, perhaps, know some methods of encryption. For example, the Caesar Cipher is often used in educational games for children.

ROT13 is another common type of message encryption. In it, each letter of the alphabet is shifted by 13 positions, as shown in the figure:

As you can see, this cipher does not really provide reliable protection information: it is a simple and straightforward example of the whole idea of \u200b\u200bcryptography.

Today we talk about cryptography most often in the context of some kind of technology. How is personal and financial information securely transferred when we shop online or view bank accounts? How can you store data safely so that no one can just open the computer, pull out the hard drive and have full access to all the information on it? We will answer these and other questions in this article.

Definitions and quick guide on cybersecurity

There are a number of things in cybersecurity that worry users when it comes to any data. These include confidentiality, integrity, and availability of information.

Confidentiality - the data cannot be received or read by unauthorized users.

Integrity of information - confidence that the information will remain 100% intact and will not be changed by an intruder.

Availability of information - getting access to data when needed.

The article will also look at the various forms of digital cryptography and how they can help achieve the goals listed above.

Basic encryption methods:

• Symmetrically
• Asymmetrical
• Hashing
• Digital signature

Symmetric encryption

Before we get started, let's answer a simple question: what exactly is meant by "encryption"? Encryption is the transformation of information in order to hide it from unauthorized persons, but at the same time, providing authorized users with access to it.

To properly encrypt and decrypt data, you need two things: the data and the decryption key. When using symmetric encryption, the key for encrypting and decrypting data is the same. Let's take a string and encrypt it using Ruby and OpenSSL:

Ruby

require "openssl" require "pry" data_to_encrypt \u003d "now you can read me!" cipher \u003d OpenSSL :: Cipher.new ("aes256") cipher.encrypt key \u003d cipher.random_key iv \u003d cipher.random_iv data_to_encrypt \u003d cipher.update (data_to_encrypt) + cipher.final binding.pry true

This is what the program will output:

Note that the variable data_to_encrypt, which was originally the string “now you can read me!”, is now a bunch of incomprehensible characters. Reverse the process using the key that was originally stored in a variable key.

After using the same key that we set for encryption, we decrypt the message and get the original string.

Let's look at other encryption methods as well.

Asymmetric encryption

The problem with symmetric encryption is this: suppose you want to send some data over the Internet. If the same key is required to encrypt and decrypt data, then it turns out that you first need to send the key. This means that you will have to send the key through an insecure connection. But this way the key can be intercepted and used by a third party. To avoid this outcome, asymmetric encryption was invented.

In order to use asymmetric encryption, two mathematically related keys must be generated. One is private keythat only you can access. The second is open, which is publicly available.

Let's consider an example of communication using asymmetric encryption. In it, the server and the user will send messages to each other. Each of them has two keys: private and public. Earlier it was said that the keys are coherent. Those. a message encrypted with a private key can only be decrypted using the adjacent public key. Therefore, to start communication, you need to exchange public keys.

But how do you know that the server's public key belongs to this particular server? There are several ways to solve this problem. The most common method (and the one used on the Internet) is using a public key infrastructure (PKI). In the case of websites, there is a Certification Authority, which has a directory of all sites to which certificates and public keys have been issued. When connecting to a website, its public key is first verified by a certification authority.

Let's create a pair of public and private keys:

Ruby

require "openssl" require "pry" data_to_encrypt \u003d "now you can read me!" key \u003d OpenSSL :: PKey :: RSA.new (2048) binding.pry true

It turns out:

Note that the private key and public key are separate entities with different identifiers. Using #private_encrypt, it is possible to encrypt the string with the private key, and using #public_decrypt - decrypt the message:

Hashing information

Hashing, unlike symmetric and asymmetric encryption, is a one-way function. It is possible to create a hash from some data, but there is no way to reverse the process. This makes hashing not a very convenient way to store data, but it is suitable for checking the integrity of some data.

The function takes some information as input and outputs a seemingly random string, which will always be the same length. An ideal hashing function creates unique values \u200b\u200bfor different inputs. The same input will always produce the same hash. Therefore, you can use hashing to check the integrity of the data.

Introduction

The problem of protecting information by transforming it, excluding its reading by an unauthorized person has worried the human mind for a long time. The history of cryptography is the same age as the history of the human language. Moreover, originally, writing itself was a cryptographic system, since in ancient societies only a select few owned it.

The sacred books of Ancient Egypt, Ancient India are examples of this.

With the widespread use of writing, cryptography began to form as an independent science. The first cryptosystems are found already at the beginning of our era. So, Caesar in his correspondence used a more or less systematic cipher that received his name.

Cryptographic systems were rapidly developed during the First and Second World Wars. From the post-war period to the present day, the advent of computing has accelerated the development and improvement of cryptographic methods.

Why is the problem of using cryptographic methods in information systems (IP) has become particularly relevant at the moment?

On the one hand, the use of computer networks, in particular global network The Internet, through which large volumes of information of a state, military, commercial and private nature are transmitted, which does not allow unauthorized persons to access it.

On the other hand, the emergence of new powerful computers, technologies for network and neural computing made it possible to discredit cryptographic systems that were considered practically undetectable until recently.

In the first chapter of this work, you can get acquainted with the basic concepts of modern cryptography, the requirements for them, the possibilities of its practical application.

In the second chapter of working with protocols for the distribution of cryptographic keys, the concept electronic signature and electronic signature protocols ..

The third chapter of this work talks about hash functions and (methods) algorithms for their construction.

The fourth chapter will talk about the modernization of El Gamal's electronic signature and the problem of discrete logarithm.

Chapter 1. Basic concepts of modern cryptography

Cryptology (kryptos - secret, logos - science) deals with the problem of protecting information by transforming it. Cryptology is divided into two areas - cryptography and cryptanalysis. The goals of these directions are directly opposite.

Cryptography is concerned with finding and researching mathematical methods for transforming information.

The sphere of interest of cryptanalysis is the study of the possibility of decrypting information without knowing the keys.

This work will focus on cryptographic techniques.

Modern cryptography includes four major sections:

Symmetric cryptosystems.

Public key cryptosystems.

Electronic signature systems.

Key management.

The main directions of using cryptographic methods are the transfer of confidential information through communication channels (for example, email), authentication of transmitted messages, storage of information (documents, databases) on media in encrypted form.

Cryptography makes it possible to transform information in such a way that its reading (recovery) is possible only with knowledge of the key.

As the information to be encrypted and decrypted, we will consider texts built on a certain alphabet. These terms mean the following.

The alphabet is a finite set of characters used to encode information.

Text is an ordered collection of alphabetical elements.

Examples of alphabets used in modern IP include the following:

alphabet Z33 - 32 letters of the Russian alphabet and a space;

alphabet Z256 - characters included in the standard ASCII and KOI-8 codes;

binary alphabet - Z2 \u003d (0,1);

octal alphabet or hexadecimal alphabet;

Encryption is a transformation process: the original text, which is also called plain text, is replaced by cipher text.

Decryption is the reverse process of encryption. Based on the key, the cipher text is converted to the original one.

The key is the information necessary for unhindered encryption and decryption of texts.

A cryptographic system is a family of T transformations of the plaintext. The members of this family are indexed or denoted by the symbol k; parameter k is the key. The key space K is the set of possible key values. Typically, a key is a sequential series of letters of the alphabet.

Cryptosystems are divided into symmetric and public key.

In symmetric cryptosystems, both encryption and decryption use the same key.

Public key systems use two keys, public and private, which are mathematically related to each other. Information is encrypted using a public key that is available to everyone, and decrypted using a private key known only to the recipient of the message. The terms key distribution and key management refer to the processes of an information processing system, the content of which is the compilation and distribution of keys among users.

An electronic (digital) signature is a cryptographic transformation attached to the text, which allows, when the text is received by another user, to verify the authorship and authenticity of the message.

Crypto resistance is a characteristic of a cipher that determines its resistance to decryption without knowing the key (i.e. cryptanalysis). There are several indicators of cryptographic strength, including:

the number of all possible keys;

average time required for cryptanalysis.

The transformation Tk is determined by the corresponding algorithm and the value of the parameter k. The effectiveness of encryption to protect information depends on maintaining the secret of the key and the cryptographic strength of the cipher.

The process of cryptographic data closure can be carried out both in software and hardware. The hardware implementation is distinguished by a significantly higher cost, but it also has advantages: high performance, simplicity, security, etc. Software implementation is more practical and allows for a certain flexibility in use.

For modern cryptographic information security systems, the following generally accepted requirements are formulated:

an encrypted message should only be readable if a key is present;

the number of operations required to determine the used encryption key from the fragment of the encrypted message and the corresponding plain text must be at least the total number of possible keys;

the number of operations required to decrypt information by enumerating all possible keys must have a strict lower bound and go beyond the capabilities modern computers (taking into account the possibility of using network computing);

knowledge of the encryption algorithm should not affect the reliability of protection;

a slight change in the key should lead to a significant change in the type of encrypted message, even when using the same key;

the structural elements of the encryption algorithm must be unchanged;

additional bits introduced into the message during the encryption process must be completely and reliably hidden in the cipher text;

the length of the cipher text must be equal to the length of the original text;

there should not be simple and easily established dependencies between keys that are consistently used in the encryption process;

any key from a variety of possible ones should provide reliable information protection;

the algorithm should allow both software and hardware implementation, while changing the key length should not lead to a qualitative deterioration of the encryption algorithm.

Chapter 2. Protocols of distribution of cryptographic keys and protocols of electronic signature.

No matter how complex and reliable cryptographic systems are, their weak point in practical implementation, the problem of key distribution. In order to be able to exchange confidential information between two IP subjects, the key must be generated by one of them, and then somehow, again in a confidential manner, transferred to the other. Those. in the general case, to transfer the key again requires the use of some kind of cryptosystem.

To solve this problem, based on the results obtained by classical and modern algebra, public key systems have been proposed.

Their essence lies in the fact that each addressee of the IS generates two keys linked together according to a certain rule. One key is declared public and the other private. The public key is published and available to anyone who wishes to send a message to the addressee. The secret key is kept secret.

The original text is encrypted with the recipient's public key and transmitted to him. The encrypted text, in principle, cannot be decrypted by the same open

Public key cryptographic systems use so-called irreversible or one-way functions, which have the following property: given a value of x, it is relatively easy to compute f (x), but if y \u003d f (x), then there is no easy way to compute x.

Many classes of irreversible functions give rise to all the variety of public key systems. However, not every irreversible function is suitable for use in real ICs.

As you remember, shift, substitution, permutation, and Vernam ciphers apply the operation to each specific character in the text. You need to shift - we shift the character, apply the key - apply to the character, then to the next character, and so on, until we encrypt all the plaintext characters. This encryption method is called streaming - we encrypt each character separately. There is another approach: split the original plaintext into groups of several characters (blocks) and perform encryption operations in each block. This is a block encryption method.

To make the difference between block and stream ciphers clearer, let's give an example using a simple replacement cipher.

Stream encryption

Let's encrypt the CIPHER word with the replacement stream cipher:

Each character was encrypted and received a ciphertext. Easy peasy.

BLOCK ENCRYPTION

Let's encrypt the word AVADAKEDAVRA. Since the cipher is block, we will split the plaintext into blocks of four characters: AVAD | AKED | AVRA (in practice, blocks of text are 64-256 bits). Let's come up with our own replacement table for each block:

And now we encrypt each of the blocks with the corresponding alphabet:
It turned out slightly better than the inline approach in terms of resilience. After all, we learned to decipher the usual replacement cipher with one left. And with such a block approach, an attacker will have to break his head pretty much before he can choose the block length and even then apply cryptanalysis for replacement ciphers for each block.

FEISTEL CHAIN

Now we are ready to move on to a very important topic that opens the door to the endless world modern systems encryption. The Feistel network is a block cipher technique developed by Horst Feistel in the IBM lab in 1971. Today, the Feistel network underlies a large number of cryptographic protocols. Let's try to make out "on the fingers" what it is.

The Feistel network operates with blocks of plain text, so we will consider the mechanism of its operation on one of the blocks. With the rest of the blocks, the actions will be similar.

• The block is split into two equal parts - left (L) and right (R).
• After splitting, the left subblock is changed by function f using the key K: x \u003d f (L, K). As a function, you can imagine any transformation you want - for example, the good old shift cipher with the key K.
• The resulting subblock is added modulo 2 with the right subblock R, which was out of work before: x \u003d x + R
• Further, the resulting parts are swapped and glued.

As you can see, everything is quite simple. To understand how this works, take a look at the diagram:

This is called a Feistel cell. The Feistel network itself consists of several cells. The sub-blocks obtained at the output of the first cell go to the input of the second cell, the resulting sub-blocks from the second cell go to the input of the third cell, and so on, depending on the number of rounds of the Feistel network. Each such round applies a predetermined round key. Most often, the round keys are derived from the main secret key K. When all the rounds have been completed, the sub-blocks of the text are glued together, and a normal ciphertext is obtained.

Now let's see how the Feistel network works with an example. Let's take the word AVADAKEDAVRA and divide it into two blocks of six characters - AVADAK | EDAVRA. As a function, we take the shift cipher by the number of positions defined by the round key. Let the secret key K \u003d. Let us take K \u003d 1, K \u003d 2 as round keys. For addition modulo 2, we translate the text into a binary code according to the telegraph alphabet, which hardly anyone else uses at all.

Here's what happened:

Now let's run the first block through the Feistel network from two rounds:

Try to encrypt the second block yourself, I got MOSSTR.

Decryption is carried out in the same way: the ciphertext is divided into blocks and then subblocks, the left subblock enters the function, is added modulo 2 with the right one, and then the subblocks are swapped. The difference lies in the fact that the round keys are served in the reverse order, that is, in our case, in the first round we use the key K \u003d 2, and then in the second round K \u003d 1.

Studies of the Feistel network have shown that with independent round keys and a cryptographically strong pseudo-random function f, three rounds of the Feistel network will be enough for the ciphertext to be pseudo-random. This suggests that ciphers based on the Feistel network are currently quite cryptographically strong.

GOST 28147-89 (MAGMA)

The arsenal already contains almost all the necessary concepts, so we are ready to move on to the first important topic of domestic cryptography - GOST 28147-89. It is worth saying that only the lazy has not yet written about this standard, so I will try for the million first time, briefly and without a cloud of formulas, to outline the essence of the encryption modes of the great and terrible Magma. If you decide to read the standard itself, then you should stock up on time, energy, patience and food, because, as you know, it is strictly forbidden to write standards in human language.

Key features: 256 bit key, 64 bit block.

Before parsing Magma, you need to learn a new concept - replacement tables, or S-boxes. This is a table of the same type as the table in the replacement cipher. Designed to replace the subblock symbols with symbols fixed in the table. Don't think that the S-box is random numbers generated by the rand () function. S-boxes are the result of well-thought-out generated sequences, because they hold the cryptographic strength of the entire cipher.

GOST 28147 rather sparingly characterizes its replacement tables. It only says that they are an additional secret element (along with the secret key) and “are supplied in established order". Nothing else. Since the adoption of GOST 28147, the scientific and technical uncertainty associated with the choice of S-boxes has generated rumors and speculation. There was talk about secret criteria known only to GOST developers. Naturally, this uncertainty reduced the credibility of the cryptosystem.

This shortcoming provided excellent ground for criticism of the standard. French cryptographer Nicolas Courtois has published several articles containing a number of controversial provisions regarding the strength of GOST. Courtois believes that it is easy to build an attack on the Russian standard and can in no way be considered international. However, Courtois conducts his analysis for S-boxes different from the current ones, so you should not rely on his opinion.

Now let's see what they thought up within the walls of the gloomy Lubyanka.

Easy replacement mode

In the 32 round simple substitution mode, according to the standard, we need 32 round keys. To generate round keys, the original 256-bit key is split into eight 32-bit blocks: K1 ... K8. Keys K9 ... K24 are a cyclic repetition of keys K1 ... K8. Keys K25 ... K32 are keys K8 ... K1.

1. Each block of 64 bits is divided into two sub-blocks - Ai and Bi.
2. The left subblock Ai is added modulo 232 with the round key K1: Ai + 1 \u003d Ai + Ki mod 232.
3. The left sub-block goes through the S-box.
4. The bits in the left sub-block are shifted 11 positions (cyclic shift).
5. The left subblock is added to the right one modulo 2: A \u003d A ⊕ B. iii
6. The right subblock takes on the original value of the left subblock: Bi + 1 \u003d Ai.
7. Subblocks are swapped.

Just an example of one round. 256 bit key:

Then round keys

How to use this S-box? Very simple! If the input of the S-box is 0, then the output will be 1 (we take the 0th character of the S-box), if 4, then the output will be 5 (we take the 4th character), if the input is 7, then the output is 4, and so on.

Plain text:

Divided into two 32-bit blocks of the most significant and least significant bits:

The example, of course, turned out to be a wild one, because GOST is still not such a standard that everyone could touch it with pens.

The simple replacement mode is too simple and has significant disadvantages:

• one error in an encrypted block distorts all the bits of that block;
• when encrypting identical blocks of plaintext, identical blocks of ciphertext are obtained, which can provide certain information to a cryptanalyst.

Thus, it is desirable to use GOST 28147-89 in the simple replacement mode only for encrypting key data.

GAMMING MODE

This mode has no disadvantages of the simple replacement mode. The gamma mode is called so because it uses gamma - a pseudo-random sequence, which in each round is added modulo 2 with plain text. The gamma is formed from the sync message S - a pseudo-random sequence that changes with each iteration and undergoes encryption in the simple replacement mode, after which it turns into a gamma and is superimposed on the plain text.

And now everything is in order.

Steps 3-5 are repeated for each block. All these manipulations can be seen in the diagram.

Decryption is performed in the same way, instead of a plaintext block, a ciphertext block is supplied.

Gamma mode with feedback

We go to complication. The algorithm is similar to the gamma mode, but the gamma is generated from the previous block of encrypted data, so the encryption result of the current block also depends on the previous blocks. 1. Synchro message S - 64-bit pseudo-random sequence.

2. S is encrypted in simple replace mode.
3. The plain text is added modulo 2 with the resulting gamut.
4. The received ciphertext arrives as a synchro-message for the next block, and also goes to the output. You can see how it looks on the diagram.

Simulation mode

In this mode, an imitating insert is generated - an additional block of a fixed length, depending on the source text and keys. Such a small block is needed to confirm that the ciphertext was not accidentally or intentionally corrupted - that is, to verify the integrity. This mode works like this:

1. The plaintext block goes through 16 rounds in simple substitution mode.
2. Another block of plaintext is added to the resulting block mod 2.
3. The sum goes 16 more rounds in the simple substitution mode.
4. The next block of plaintext is added and again simple replacement and so on, until the blocks of plaintext run out.

For verification, the recipient, after decrypting the text, carries out a similar procedure as described. If the result does not coincide with the transmitted imitating insert, all corresponding M blocks are considered false.

GOST 34.12-2015 (Kuznechik)

Many consider GOST 28147-89 morally outdated and insufficiently stable in comparison with foreign algorithms. To replace it, domestic cryptographers released a new encryption standard. They say that this happened either due to a large number of attacks on the old GOST, or because such a block length is already outdated and too small for modern data arrays. Nobody advertises the true reasons. Of course, there were some changes in the main characteristics.

Main characteristics: 256 bit key, 128 bit block.

It should also be said that in the new standard S-boxes are fixed and well thought out, so you shouldn't invent your own miraculous random substitutions. In the new GOST, there are much more encryption modes:
easy replacement mode (Electronic Codebook, ECB);
gamma mode (Counter, CTR);
gamma mode with output feedback (Output Feedback, OFB);
simple replacement mode with engagement (Cipher Block Chaining, CBC);
gamma mode with cipher feedback (CFB);
mode of generating a simulated insert (Message Authentication Code algorithm).

Let's consider the new modes.

Mesh Simple Swap Mode

As it was seen in the previous standard, the simple replacement mode is the weakest of the modes, so in the new standard it now appears with engagement and has become not so simple at all.

1. The initialization vector sounds scary, but in reality it is just a sequence of bits entering the input.
2. The vector is split into two parts - L and R, one of which is added modulo 2 with plain text, and the other becomes half of the initializing vector for the next block.
3. The sum of the plaintext and a slice of the initialization vector goes through the simple replacement cipher.
4. The resulting blocks of ciphertext are glued together.

It is worth looking at the diagram, and everything becomes clear at once.

Of course, the initialization vector is not so simple: it goes through a series of linear transformations (using a linear shift register) before starting to encrypt a new block. But to get acquainted with the cipher, it is enough to imagine such a scheme. Decryption in this mode is also not entirely obvious, so it's better to look at the diagram.

For the pros - Encryptions. Among domestic developments, this is the CryptoPro CSP crypto provider.

A few words about the strength of encryption modes. Many foreign cryptographers have tried to raise their hand against our standard, but at the moment there is not a single attack known that can be implemented at the modern technological level of development. For a long time, this standard was not very popular among programmers, since it is difficult to understand the operation algorithm from its text, and there are not enough clear descriptions. But now it is already full of implementations in many programming languages. So now the use of GOST is quite realistic, and in many respects it surpasses foreign standards. After all, where is patriotism ?!