Now, having learned the purpose of cryptography, let's get acquainted with the basic terms that we will use when studying cryptographic methods of information protection.

Cipher– a set of predetermined ways to transform the original secret message in order to protect it.

The original messages are usually called plain texts. In foreign literature for plaintext use the term plaintext.

Symbol is any character, including a letter, number, or punctuation mark.

Alphabet- a finite set of symbols used to encode information. For example, the Russian alphabet contains 33 letters from A to Z. However, these thirty-three characters are usually not enough to record messages, so they are supplemented with a space character, a dot, a comma, and other characters. The alphabet of Arabic numerals is the symbols 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. This alphabet contains 10 characters and can be used to write any natural number. Any message can also be written using binary alphabet, that is, using only zeros and ones.

The message received after conversion using any cipher is called encrypted message(Closed text, cryptogram). In foreign literature, a closed text uses the term ciphertext.

Converting a plaintext to a cryptogram is called encryption. The reverse action is called decryption. In the English-language literature, the terms "encryption / decryption" correspond to the terms "enciphering/deciphering".

Key– information needed to encrypt and decrypt messages.

From the point of view of the Russian language, the terms "decryption" and "decryption" are synonymous. However, in works on cryptography of recent decades, these words are often distinguished. We will assume that the terms "decryption" and "decryption" are not synonymous. Let us assume that the legal recipient of the message (the one who knows the key) is decrypting, and the person to whom the message is not intended, trying to understand its meaning, is decrypting.

Encryption system, or cipher system, is any system that can be used to reversibly change the text of a message to make it incomprehensible to anyone but the intended recipient.

Crypto resistance is the characteristic of a cipher that determines its resistance to decryption without knowledge of the key (i.e., the ability to resist cryptanalysis).

Thus, taking into account all the definitions made, it is possible to give a more precise definition of the science of "cryptography". Cryptography studies the construction and use of encryption systems, including their strength, weaknesses and degree of vulnerability relative to various methods autopsy.

All methods of information transformation in order to protect against unauthorized access are divided into two large groups: private key encryption methods and public key encryption methods. Private Key Encryption(encryption with private key or symmetric encryption) has been used by humans for quite some time long time. These methods use the same key to encrypt and decrypt data, which both parties try to keep secret from the adversary. Public Key Encryption (asymmetric encryption) began to be used for cryptographic closure of information only in the second half of the 20th century. This group includes encryption methods in which two methods are used to encrypt and decrypt data. different key. In this case, one of the keys (public key) can be transmitted over an open (unprotected) communication channel. Electronic (digital) signature is a block of data, usually attached to a message, obtained using a cryptographic transformation. Electronic signature allows you to check the authorship and authenticity of the message when another user receives the text.

Cryptographic information security system- an information security system that uses cryptographic methods for data encryption.

3.5.3 Encryption/decryption models and methods discrete messages

Discrete messages can be represented by signals that have a finite number of states. These are various kinds of data, printed texts, as well as speech signals and images if they are previously converted into discrete (digital) signals.

A mathematical model of a system for encrypting/decrypting discrete messages is a pair of functions

E = f(M,K w), M = g(E,K d),

which convert the message M into the cryptogram E using the encryption key Ksh and, conversely, the cryptogram E into the message M using the decryption key Kd. Both functions defining the cryptosystem must satisfy the following requirements:

functions f(M, K w) and g(E, K d) with known arguments are calculated simply;

· the function g(E,?) with an unknown key Kd is difficult to calculate.

It is assumed that the decryption key Kd is unknown to illegal users, although they may know the functions f and g, as well as the encryption key Ksh if it does not match the key Kd. Last condition constitutes the so-called Kaziska principle.

Three main types of attacks on a cryptosystem should be distinguished:

only with a known cryptogram E;

· with a known cryptogram E and a known message M, which corresponds to a certain part of the cryptogram obtained using the same key (attack with a partially known open message);

· with a known cryptogram and a specially selected part of the message corresponding to the part of the cryptogram received on the same key (attack with a partially selected open message).

Modern cryptosystems are considered secure if they are resistant against all three types of attacks.

If the encryption key is equal to the decryption key, i.e.

K w \u003d K d \u003d K

then the system is called symmetric (one-key). For its operation, the encryption and decryption points must have the same keys.

If K w is not equal to K d, then the encryption system is called asymmetric (two-key). In this case, the key K w is delivered to the encryption point, and the key K d - to the decryption point. Both keys obviously need to be linked. functional dependence Kd = j(Kw), but such that it would be impossible to recover the decryption key Kd from the known encryption key Kw. This means that for an asymmetric encryption system j() should be a hard-to-compute function. In such a system, it is possible to secretly distribute among legitimate users only their decryption keys, and make the encryption keys public, including for publication. Therefore, the cryptosystem under consideration is called a system with a public (public) key.

The first of these types of ciphers implies the presence of some information (key), the possession of which allows you to both encrypt and decrypt the message.

On the one hand, such a scheme has the disadvantages that, in addition to an open channel for transmitting a ciphertext, the presence of secret channel to transfer the key, and besides, if information about the key is leaked, it is impossible to prove from which of the two correspondents the leak occurred.

On the other hand, among the ciphers of this particular group, there is the only encryption scheme in the world that has absolute theoretical stability. All others can be deciphered at least in principle. Such a scheme is a normal encryption (for example, XOR operation) with a key whose length is equal to the length of the message. The key must only be used once. Any attempt to decipher such a message is useless, even if there is a priori information about the text of the message. By selecting the key, you can get any message as a result.

Public key ciphers imply the presence of two keys - public and private; one is used to encrypt and the other to decrypt messages. The public key is published - brought to the attention of everyone, while the secret key is kept by its owner and is the key to the secrecy of messages. The essence of the method is that what is encrypted with the secret key can only be decrypted with the public key and vice versa. These keys are generated in pairs and have a one-to-one correspondence to each other. Moreover, it is impossible to calculate another from one key.

characteristic feature ciphers of this type, which distinguish them favorably from ciphers with a secret key, is that the secret key here is known only to one person, while in the first scheme it must be known by at least two. This provides the following benefits:

no secure channel is required to send the secret key, all communication is done over open channel;

"What two people know, the pig knows" - the presence the only a copy of the key reduces the possibility of its loss and allows you to establish a clear personal responsibility for keeping the secret;

the presence of two keys allows you to use this encryption system in two modes - secret communication and digital signature.

The simplest example of the encryption algorithms under consideration is RSA algorithm. All other algorithms of this class differ from it unprincipally. It can be said that by by and large, RSA is the only public key algorithm.

A mathematical model of a system for encrypting/decrypting discrete messages is a pair of functions

,
,

that transform the message
into a cryptogram using an encryption key
and, conversely, a cryptogram to the message
using the decryption key . Both functions that define the cryptosystem must satisfy the following requirements:

The Dutch cryptographer A. Kerkhofs (1835 - 1903) suggested that the secrecy of ciphers should be based only on the secrecy of the key, and not on the secrecy of the encryption algorithm, which, after all, may be known to the enemy.

If the encryption key is equal to the decryption key, i.e.

= =,

then the system is called symmetrical(single key). For its operation, the same keys must be secretly delivered to the points of encryption and decryption. .

If
, i.e. the encryption key is not equal to the decryption key, then the encryption system is called asymmetrical(two-key). In this case the key
is delivered to the encryption point, and the key – to the decryption point. Both keys should obviously be linked by a functional dependency

, but such that by the known encryption key
it would be impossible to recover the decryption key . This means that for an asymmetric encryption system, the function  () must be difficult to calculate.

There are two main classes of security of cryptosystems:

Ideally(certainly) persistent or committed cryptosystems for which resistance to cryptanalysis (decryption) without knowing the key does not depend on the computing power of the opponent. They are called theoretically indecipherable(TNDSh) systems.

Computing strong cryptosystems whose resistance to cryptanalysis depends on the power computing system opponent.

1. RSA cryosystem

Select an integer for encryption. N =p q, where p And q are two large prime numbers. Message M appears as one of the numbers

M {2,3,...,N –1}.

The formulas describing encryption/decryption are as follows:

,
,

where K- public encryption key, k– private decryption key.

From these two relations follows the equality

,

which in ordinary arithmetic holds if kK= 1, and in modular arithmetic and for

kK = 1 + l (N ), (*)

where l- whole. Indeed, using the Euler theorem, we check

,

if M And N are relatively prime numbers.

The considered relations indicate the way of key generation. First, very large random numbers are chosen. prime numbers p And q with a slightly different number of digits so that the product N = pq had at least 768 bits (according to 2001 data). Calculate the Euler function

(N ) = (p –1)(q –1).

Equality (*) is equivalent

Kk= 1 mod ( N ),

whence it follows that both keys are mutually inverse modulo ( N ).

public key K choose according to the following conditions:

K< (N ), GCD( K, (N )) = 1.

private key k calculate

k = K – 1 mod ( N ),

using the Euclid algorithm. After completing the preparatory work, the public key K and module N placed in open directory by taking steps to ensure that substitution is not possible. Numbers p And q kept secret.

Note that the condition of coprime numbers M And N, the failure of which makes it impossible to decode, does not create serious restrictions. First, among the numbers smaller N proportion of coprime numbers with N equals ( p–1)(q–1)/(pq), i.e. is indistinguishable from unity, and, secondly, the condition is easily provided by an insignificant modification of the message. Also degree M K should not be less N. If this condition is not met, the cryptogram has the form

and without modulo calculations, it is easily opened, because K known.

Obviously, in the considered ratios, the numbers K And k equal, i.e. keys can be swapped and used k as a public encryption key, and K how private key decryption.

So both RSA keys are given by pairs of integers: ( K, N) And ( k, N).

When the authors R. Rivest, A. Shamir, L. Adleman (Rivest, Shamir, Adleman) in 1977 proposed the RSA cryptosystem, they encrypted the phrase “ItsallGreektome”, presented in digital form. Values ​​have been published M, K, N indicating that 129 decimal places N obtained by multiplying 64-bit and 65-bit numbers p And q. Factorization N and the opening of the cryptogram were performed in about 220 days only in 1994 after preliminary theoretical preparation. The work involved 600 volunteers and 1600 computers connected to a network using the Internet.

The strength of a public key system, and RSA in particular, depends on the choice of its parameters. If you choose log 2 N= 200 bits, then the factorization will require approximately 2.710 11 operations, which will take several days on a personal computer. If you choose log 2 N= 664 bits, then factorization will require 1210 23 operations. At a speed of 10 6 operations per second, factorization will take several billion years.

Thus, if the parameters of the RSA cipher are chosen correctly and the module N taken large enough, for example
, then this system can be considered fairly stable. To date, there are no methods for its successful cryptanalysis.

The implementation of the RSA cipher has been worked out both in software and in hardware. Used by RSA for smart card encryption. In the software version, the encryption speed is of the order of 1 kbps, in the hardware version it is 1050 kbps.

The relatively low speed of encryption and decryption compared to symmetric, block or stream systems is a disadvantage of all asymmetric encryption systems, including RSA.

1. Digital signature

The authenticity of the document is traditionally certified by the usual "paper" signature. Signature permanence, i.e. the impossibility of its forgery by unauthorized persons is ensured by two main conditions: firstly, its uniqueness, based on the individual characteristics of the handwriting, and secondly, the physical integrity of the paper document on which the signature was made. At the same time, the signature cannot be forged even by the person who verifies its authenticity.

However, when transmitting documents over computer networks, it is impossible to use these conditions, including when transmitting facsimile messages (FAX), since they allow simple forgery.

Digital signatures are used to certify documents transmitted over computer networks. A digital signature solves the problem of a possible dispute between the sender and the recipient, including in court, if there is a legal basis for its application.

A digital signature must have the properties of a regular signature and at the same time be a chain of data that can be transmitted over networks, i.e. it must meet the following four basic requirements:

the digital signature must be unique, i.e. no one, except the author, can create the same signature, including those who verify its authenticity;

every netizen, legal or illegal, can test the truth digital signature;

the signatory cannot refuse a message certified by his digital signature;

both the implementation and verification of the digital signature should be fairly simple.

To satisfy all the above requirements, a digital signature, unlike a "paper" one, must depend on all bits of the message and change even when one bit of the signed message changes. To implement a digital signature based on symmetric cryptosystems, the participation of a trusted person - an arbiter - is necessary. The implementation of a digital signature without an arbiter is possible only through the use of asymmetric systems.

There are various types of digital signature based on public key cryptosystems. Consider the implementation of the CPU based on the RSA cryptosystem.

In this case, the user A signing the message M, generates a key pair k A ,K A and informs network users of the values K A And N. Next user A creates a control group

,

which will be the digital signature (Fig. 17). The control group is assigned to the message and transmitted along with it.

It is easy to verify that in this case all four digital signature requirements stated earlier are met if the RSA cipher is chosen to be strong enough.

However, the considered system for generating a digital signature has two significant drawbacks:

there is significant redundancy due to the assignment of a control group, the length of which is equal to the length of the message, which requires doubling the amount of memory, transmission time, etc.;

for messages of large length, the exponentiation operation when calculating the control group and checking it will be performed in an unacceptably long time.

State and military correspondence originated in ancient times and were accompanied by the invention of various methods of protecting this correspondence from being read by the enemy.

Translated from Greek, cryptography is cryptography (now understood in a broad sense). In cryptography, text is visible but cannot be read. Cryptography uses the transformation of some characters into others taken from the same or another alphabet.

Latent (sympathetic) writing should not be confused with cryptography, the essence of which is to hide the visibility of what is written. For example, an inscription made with milk on white paper is not visible unless the paper is heated.

So for 400 years BC. e. in Sparta, encryption was used on a circular cylinder. A scroll was wound around it, after which text was written along the scroll parallel to the axis of the cylinder - line by line. As a result, on the unfolded scroll, the letters were arranged in no apparent order. To read the message, the recipient had to wind the scroll around exactly the same cylinder.

For 300 years BC. e. in Greece, the Tacticus was written about hidden messages. For 200 years BC. e. a polybian square was invented containing 5x5=25 cells for twenty-four letters of the Greek alphabet and a space inscribed in random order. When encrypting the text, the desired letter was found in the square and replaced with another letter from the same column, but inscribed in the line below. The letter that was in the bottom line of the square was replaced by a letter from top line the same column. The recipient, who had exactly the same square, decrypted the message by performing the indicated operations in reverse order.

Caesar, in his correspondence with Cicero, used what is now called Caesar cipher. Caesar's method is as follows. First, each letter of the alphabet is assigned its ordinal number. Then, when encrypting, it is not the letter itself that is written, but the one whose number is greater by an integer TO, called a key. For an alphabet containing T letters, the encryption rule is given by:

n \u003d (K + I) mod m,

where P- number of the letter obtained as a result of encryption of the letter with the number I Here we use the modulo operation T, upon execution of which not the amount itself is recorded K + I, and the remainder after dividing this sum by T.

A generalization of the Caesar cipher is called simple substitution cipher. Its essence lies in the fact that all letters of the alphabet are replaced by other letters of the same alphabet according to the rule, which is the key. For example, but is replaced by in, b-on from, to- on the in,..., I- on the G. The number of permutations possible with such encryption, corresponding to an alphabet with a volume T= 32, is m! =32! = 2, 63 10 35 . If in one second, when decrypting by simple enumeration, one million keys are sorted out, then the total time for decryption will be 8.3-10 21 years.

The development of the simple substitution cipher was the cipher of Blaise Vigenère (XVI century, France). In this cipher, the key is the word, i.e. sequence of serial numbers key letters. The key, repeating if necessary, is signed under the message, after which modulo addition is performed T in each column, which contains one letter of the message and the key.

Many well-known mathematicians were involved in cryptography, such as Viet, Cardano, Leibniz and, finally, Francis Bacon. Last suggested binary encoding Latin alphabet.

In Russia, an independent cryptographic service was first organized by Peter I, who, under the influence of communication with Leibniz, established a digital chamber for the development and use of cryptography.

The industrial revolution in developed countries led to the creation of cipher machines. At the end of the 18th century, Jefferson (the future third president of the United States) invented encryption wheels. The first practically working encryption machine was proposed in 1917 by Vernam. In the same year, a rotary cipher machine was invented, later produced by Siemens under the name "Enigma" (riddle), - the main opponent of the cryptographers of the Allied Powers during the Second World War.

An invaluable contribution to cryptography was made by K. Shannon, especially with his work "Secrecy and secrecy", written in 1948. In 1976, Diffie and Hellman proposed public-key cryptosystems. In 1977, the United States introduced the open Federal Unclassified Message Encryption Standard (DES). In 1989, an open domestic system encryption GOST 28147-89.

Rice. 1. The main stages in the development of cryptographic systems

Simultaneously with the improvement of the art of encryption (Fig. 1), cryptanalysis was also developing, the subject of which is the opening of cryptograms without knowing the keys. Although the constant competition between encryption and cryptanalysis continues at the present time, however, there are a number of significant differences between the current stage and the previous ones, namely:

The widespread use of mathematical methods to prove the strength of ciphers or to conduct cryptanalysis,

The use of fast-acting computer science,

Opening of a new kind of cryptography with more "transparent" methods of cryptanalysis (public key cryptography),

The emergence of new additional features security, in addition to encryption and decryption,

Use of the latest physical methods in cryptography (dynamic chaos, quantum cryptography, quantum computer).

2. Mathematical model discrete message encryption/decryption systems

We will consider the encryption and decryption of the so-called discrete messages, which can be represented by signals that have a finite number of states. These are data, printed texts, as well as speech signals and images, if they are previously converted into discrete (digital) signals. When analog signals use other methods, which will be discussed separately.

A mathematical model of a system for encrypting/decrypting discrete messages is a pair of functions

, (1)

, (2)

that transform the message M into a cryptogram E using an encryption key K W and, conversely, a cryptogram E to the message M using the decryption key To DSh. Both the functions that define the cryptosystem must meet the following requirements:

Functions f(,) And g(,) with known arguments are calculated simply,

Function g(E, K LW) with an unknown key K LH difficult to calculate.

It is assumed that the decryption key K LH unknown to illegal users, although they may know the functions f(.) And g(.) as well as the encryption key K W if it doesn't match the key To DSh. The last condition constitutes the so-called Kaziska principle.

If the encryption key is equal to the decryption key, i.e. K W = K LH then the system is called symmetrical (single-key). For it to work, the same keys must be secretly delivered to the encryption and decryption points.

If K W = To DSh, then the encryption system is called asymmetrical (two-key). In this case the key K W is delivered to the encryption point, and the key To DSh - to the decryption point. Both keys should obviously be linked by a functional dependency K LH = φ(K W) but such that by a known encryption key K W it would be impossible to recover the decryption key K LH This means that for an asymmetric encryption system φ(.) must be a hard-to-compute function. In such a system, it is possible to secretly distribute among legitimate users only their decryption keys, and make the encryption keys open and publish, for example, in a public directory. Therefore, the cryptosystem under consideration is called a system with open (public) key. The public key cryptosystem was first proposed by Diffie and Helman in 1976. Three main types of attack (attacks) of opponents on the cryptosystem should be distinguished:

Only with a known cryptogram E,

With a known cryptogram E and famous message M, which corresponds to a certain part of the cryptogram obtained using the same key (partially known open message attack).

With a known cryptogram and a specially selected part of the message corresponding to the part of the cryptogram received on the same key (partially selected open message attack),

Modern cryptosystems are considered secure if they are resistant against all three types of attacks.

For cryptosystems that encrypt messages with low requirements for transmission error probability (digital speech, digital image) it is necessary to add a fourth, additional, requirement:

Decryption after the transmission of the cryptogram through channels with interference should not increase the number of errors compared to the number of errors that were formed in the communication channel due to interference, in other words, there should be no propagation of errors after decryption.

Let us explain the essence of the concept of error propagation. Let when transmitting a cryptogram E errors occurred on the communication channel (Fig. 2).

The location and magnitude of errors in the received cryptogram are determined by the channel error vector e. At binary system transmission, the received cryptogram will look like E- E ® yo, where the sign ® means bitwise addition modulo 2, and total number mistakes t is equal to the norm of the error vector |e|, i.e. t=|e|. The number of errors e" in the decrypted message M is calculated as t"=|f |, where 1= R8A/. Errors do not multiply provided that f = t.

In previous editions, we found out that cryptography is a discipline that studies how to protect processes information exchange from purposeful attempts to deviate them from the conditions of normal flow, based on cryptographic transformations, that is, data transformations using secret algorithms. From ancient times up to the present time, the most important task of cryptography is to protect data transmitted over communication channels or stored in information processing systems from unauthorized acquaintance with them and from their deliberate distortion. Cryptography solves this problem by encrypting the protected data, which involves the use of the following two mutually inverse transformations:

Before data is sent over the communication line or before it is stored, it is subject to encryption;
- to restore the original data from the encrypted ones, a procedure is applied to them decryption.

The following figure 1 shows the scheme of data transformation during encryption:

Fig.1. Scheme of data conversion during encryption.

Cipher is a pair of algorithms that implement each of these transformations. The secrecy of the second of them makes the data inaccessible for unauthorized access, and the secrecy of the first makes it impossible to impose false data. Obtaining open data from encrypted data without knowing the decryption algorithm is called decryption. Initially, encryption was used to protect transmitted messages from both of these threats, but later it was shown that it can protect data from unauthorized modification only if certain conditions are met, namely:

The encrypted message contains a lot of redundancy;
- the encryption process well "mixes" the structural units of the message (bits, symbols, etc.).

Since these conditions are by no means always satisfied, in the general case, encryption is not a means of imitation protection- protection against the imposition of false data. One or more future issues will be devoted to this problem, but for now we will "forget" about it for a while.

What conditions must a cipher satisfy? Well, first of all, the decryption procedure should always restore open message in his original form. In other words, for every valid message T transformations for- and decryption must satisfy the following property:

T = D(E(T))

The second condition that a cipher must satisfy is that it must... encrypt data, that is, to make them incomprehensible to the uninitiated.

In other words, there should be no easily traceable links between the original and encrypted data. In addition, the cipher must be crypto-resistant, that is, resistant to attempts to decrypt messages. It is clear that the issue of cipher strength is the main one in this branch of cryptography, and we will begin its consideration by finding out what can serve as a measure of strength.

The sent message before reaching the recipient is indeterminate for him and, of course, for the attacker - if this were not so, then there would be no point in sending it at all. Let messages be sent T1,T2,...,Tn with probability p1, p2,..., pn respectively. Then measure message uncertainty for everyone who has this a priori information, the value of the mathematical expectation of the logarithm of the probability of one message, taken with a minus sign, can serve; for some reasons, it is convenient to choose 2 as the base of the logarithm:

This value has a quite understandable physical meaning: the number of bits of information that necessary average pass to completely eliminate the uncertainty. If there is no a priori information about the message except for its size in N bits, then all possible out of 2 N options are considered equally probable and then the uncertainty of the message is equal to its size:

H( T ) = -2 N 2 - N log 2 (2 - N ) = N = | T |,

where through | X| the size of the data block is indicated X in bits. And if nothing is known about the source text, even its size? In this case, it is still necessary to take some distribution model as a basis. As a rule, in reality, such difficulties do not arise, since many very strong ciphers<не считают нужным>hide the size of the encrypted message, since there is almost never a special need for this, and this characteristic is a priori considered to be known to the attacker. Where this size really needs to be hidden, all messages are converted into data arrays of the same length before encryption, and we again get the situation discussed above.

After interception of the ciphertext, this value, of course, can change, now it becomes a posteriori ("post-experimental") conditional uncertainty - the condition here is the intercepted cipher message T " . Now it is given by the following formula:

,

where through p (T i | T") denotes the probability that the original message is T i provided that the result of its encryption is T".

One of the most important characteristics The quality of the cipher is the amount of information about the source text that an attacker can extract from the intercepted ciphertext - it is found as the difference between the a priori and a posteriori uncertainty of the original message:

I= H (T ) - H (T | T" ).

This value is always non-negative. The indicator here is how much it will decrease - it is clear that it cannot increase - the uncertainty source code when receiving the corresponding ciphertext compared to the a priori uncertainty, and whether it will not become less than the minimum allowable value.

In the cipher developer's best case, both of these uncertainties are equal:

H( T | T" ) = H (T ),

that is, the attacker cannot extract any useful information about the plaintext from the intercepted ciphertext: I = 0. In other words, knowledge of the ciphertext does not reduce the uncertainty of the corresponding plaintext, improve its estimate, and increase the probability of its correct determination. Ciphers that satisfy this condition are called absolutely resistant or perfect ciphers, since messages encrypted using them not only cannot be decrypted in principle, but the attacker will not even be able to come close to successfully determining the source text, that is, to increase the probability of its correct decryption.

Naturally, the main question that interested cryptographers was whether there are absolutely strong ciphers in practice. It was intuitively clear to specialists that they exist, and Vernam gave an example of such a cipher more than two decades before one of the founders of information theory, K. Shannon, formally proved their existence. In this proof, Shannon also obtained the necessary condition for the absolute security of a cipher:

In order for the cipher to be absolutely secure, it is necessary that the uncertainty of the encryption algorithm be no less than the uncertainty of the encrypted message:

The ambiguity of an encryption algorithm is defined in exactly the same way as the ambiguity of a message - the mean of the binary logarithm of the probability of using the minus algorithm - and is meaningful only if the set possible algorithms and the probability of using each of them is given. The strength of ciphers is based on secrecy, that is, on the uncertainty for an attacker of the decryption algorithm - if this were not the case, anyone could decrypt the encrypted data. The less the attacker knows about the cipher, the less likely it is to successfully decrypt the message. Let's explain the above with an example: let's intercept a short 12-bit encryption with the following content:

1 0 0 1 0 1 1 1 0 1 0 1

For simplicity, let's assume that the original message is the same length. If the attacker does not have any a priori information about the encrypted message, for him each of the 2 12 initial options is equally probable, and thus the probability of correctly guessing the original message is 2 -12. Let us now assume that the attacker knows a priori that encryption is the imposition of the same 4-bit mask on each 4-bit group of the message using the operation bitwise exclusive or. Obviously, maybe 16 = 2 4 various options bit mask, respectively, possibly 16 different meanings source text:

mask plaintext 0000 100101110101 0001 100001100100 0010 101101010110 ..... 1111 011010001010

Thus, now the probability of correctly guessing the source text is 1/16 - knowledge of the features of the encryption method used has increased it by 256 times. An interesting conclusion follows from this: the greater the uncertainty in the encryption transformation for outsider, the farther it stands from the solution of the cipher, the more reliable the cipher. A cipher completely indeterminate for an attacker

is unrevealable for him, that is, absolutely persistent! It turns out that the reliability of the cipher depends solely on its secrecy and does not depend on its other properties.

The most interesting thing is that this is true, and there is no paradox here. However, in practice it can be difficult to keep the attacker completely uncertain about the cipher - he can get information about the cipher in the following ways:

Analyze an intercepted encrypted message - almost always it has a certain set of ciphertexts at its disposal, for some of them there may be corresponding plaintexts, or even the ability to obtain a ciphertext for any pre-specified plaintext;

An attacker can have a priori information about the cipher obtained from various sources - for example, earlier it could be an encryption instruction or a draft with intermediate results for a particular text, currently it is a fragment computer code or a chip that implements encryption in hardware.

The attacker always has the first possibility, the second is also very likely - it is difficult to keep an actively "working" algorithm secret from strangers. Based on the above, we can list several qualities that a cipher must satisfy in order to be considered good.

1. Analysis of encrypted data should not give an attacker any information about the internal structure of the cipher. There should not be any statistical regularities in the ciphertext - for example, statistical tests should not reveal any dependences and deviations from the equiprobable distribution of bits (characters) of the ciphertext in the encrypted data.

2. The algorithm must be reconfigurable. Sooner or later, an attacker may have at his disposal a description of the algorithm, its software or hardware implementation. In order not to have to completely replace the algorithm in all encryption nodes where it is used in this case, it must contain an easily replaceable part.

The second condition leads us to the Kirchhoff principle (in translations from English he is sometimes "called" Kerckhoff, which is not entirely true, since he is Dutch, not English, and the transcription of his surname should be German, not English), unconditionally accepted now in the art of building secure ciphers. This principle is as follows: a cipher is defined as a parameterized algorithm consisting of a procedural part, that is, a description of exactly what operations and in what sequence are performed on the encrypted data, and parameters - various data elements used in transformations. Disclosure of only the procedural part should not lead to an increase in the probability of successful decryption of the message by an attacker above the allowable limit. For this reason, and also because the declassification of this part is quite likely in itself, there is not much point in keeping it secret. Some part of the parameters of the algorithm is kept secret, which is called cipher key:

T" = E (T )= E K (T ),

here K - cipher key.

Using the Kirchhoff principle makes it possible to obtain the following benefits in building ciphers:

Disclosure of a specific cipher (algorithm and key) does not lead to the need complete replacement implementation of the entire algorithm, it is enough to replace only the compromised key;

Keys can be alienated from other components of the encryption system - stored separately from the implementation of the algorithm in a more reliable place and loaded into the encryptor only as needed and only for the duration of the encryption - this significantly increases the reliability of the system as a whole;

It becomes possible to accurately estimate the "degree of uncertainty" of the encryption algorithm - it is simply equal to the uncertainty of the key used:

H( E K ) = H (K ).

Accordingly, it becomes possible to estimate the probability and complexity of successful decryption, that is, the amount of computational work that an attacker needs to perform for this.

Let us return to the necessary condition for the absolute strength of a cipher for ciphers constructed in accordance with the Kirchhoff principle. Assuming that there are no a priori data about the ciphered text except for its length, we obtain that the uncertainty of the original text is equal to its length expressed in bits:

H( T ) = | T |.

Maximum possible data block uncertainty fixed size achieved when all possible values of this block are equiprobable - in this case it is equal to the block size in bits. Thus, the uncertainty of the key K does not exceed its length:

Taking into account the above, we obtain the necessary condition for absolute security for ciphers that satisfy the Kirchhoff principle:

In order for a cipher built according to the Kirchhoff principle to be absolutely secure, it is necessary that the size of the key used for encryption is not less than the size of the data being encrypted,

Exact equality is possible only if all possible key values ​​are equally likely, which is equivalent to the condition that the key bits are equally likely and statistically independent of each other.

An example of an absolutely secure cipher is Vernam's one-time gamma - an overlay on open data ( T) key ( K) of the same size, composed of statistically independent bits that take on possible values ​​with the same probability, using some binary operation °:

The operation used to overlay the gamma must satisfy certain conditions, which can be summarized as follows: the encryption equation must be uniquely resolvable with respect to the plaintext given the encrypted data and the key, and uniquely resolvable with respect to the key with the known public and encrypted data. If an operation satisfies this property, it is eligible. Among the suitable operations, there are no suitable better and suitable worse, from the point of view of the security of the cipher, they are all the same - the concept of "perfection" does not know comparative degrees, it either exists or it does not. For this reason, for practical use usually choose the most convenient operation in the implementation - bitwise modulo 2 summation or bitwise XOR, because she is:

Requires for its implementation the minimum complexity of the logic of all possible operations;

It is inverse to itself, so the same procedure is used to decrypt and decrypt.

Let's return to the issue of absolute strength of ciphers: as noted earlier, absolutely strong ciphers require the use of a key that is no smaller in size than the data being encrypted. Both the sender and the recipient must have this key, that is, it must first be delivered to them, and this requires a secure channel. Thus, along with a potentially insecure channel for transmitting encrypted data, it is necessary to have a secure channel for transmitting a key of the same size. This is not always acceptable for economic reasons, so similar systems are used only in exceptional cases to protect information of particular value. The vast majority real systems encrypted communication, algorithms are used that do not have absolute security and are therefore called imperfect ciphers.

Naturally, for such ciphers, the question of a reliable assessment of their strength is relevant. For them, knowledge of the ciphertext reduces the uncertainty of the corresponding plaintext, thereby increasing the probability of successful decryption. However, contrary to popular misconception, it does not follow at all that such decryption is possible. always.

The opinion that a message encrypted with an imperfect cipher can always be unambiguously decrypted if the cryptanalyst has sufficient ciphertext and unlimited computational capabilities is an overly rough simplification and is generally incorrect.

The thing is that to slightly increase the probability of successful decryption and make it equal to one- not the same thing. This idea can be easily illustrated by an example: let an array of bits be encrypted, the key has a size of one bit, and encryption is carried out according to the following rules:

If the key is 0, the odd-numbered bits of the original text are inverted, numbering from left to right;

If the key is 1, the even-numbered bits of the original text are inverted;

Thus, E 0 (01) = 11, E 1 (01) = 00. Obviously, our cipher does not have absolute security. Let's assume that the cipher "10" is intercepted. What is the original text? It is clear that it can be either 00 or 11 depending on the value of the key, and it is impossible to uniquely determine this, which was required to be proved. For more serious ciphers, the cryptanalyst will simply have more "choices" in the plaintext, and no indication of which one to prefer.

Thus, the question of the possibility of unambiguous decryption of a message encrypted with an imperfect cipher remains open. When is such decryption possible? Shannon explored this issue in detail in his works. For analysis, he introduced following characteristics cipher, in order to simplify the presentation, they are given here for the variant of the bit representation of data:

1. Key unreliability function - key uncertainty with known n bits of the ciphertext:

f( n ) = H (K | T" ), where | T" | = n .

It is clear that f(n) may not be defined for everyone n.

2. The cipher uniqueness distance is such a value n, at which the unreliability function, that is, the uncertainty of the key, becomes close to 0 .

U(E) = n, where n is the minimum of those for which

Shannon showed that both quantities defined above depend on the redundancy of the plaintext, with the uniqueness distance being directly proportional to the key size and inversely proportional to the redundancy:

,

where the redundancy of the original text R is determined by the following relationship:

This means that by completely eliminating the redundancy of the plaintext, we will make it impossible to unambiguously decrypt it based on knowledge of only the corresponding ciphertext, even if the cryptanalyst has unlimited computational capabilities at his disposal. In this case, the uncertainty of the source text will be equal to the uncertainty, and, consequently, the key size:

H( T ) = H (K ) = | K |

Complete absence redundancy in the source text means that no matter what key we take, after decryption we will get the "correct" source data, and there will simply be no reason to prefer one option to another. From this, in particular, it follows that in real practice, before encryption, the data is very useful to "shrink" some archiver. Of course, the complete non-redundancy of the source text is unattainable in this case, however, such "squeezing" will greatly complicate cryptanalysis based only on the ciphertext.

Similar numerical characteristics of the strength of a cipher can also be obtained for a situation where the cryptanalyst has at his disposal not only the ciphertext, but also the corresponding plaintext. It is clear that they will no longer depend on the redundancy of the original messages. In this case, the uniqueness distance of the cipher is of the order of the size of its key, that is, very small. By virtue of given reasons such a cipher can be easily broken with unlimited computing resources of the analyst, and when designing strong ciphers, completely different principles come to the fore. But this will be discussed in the next issue.

(To be continued)

Academic year

Theoretical part

1. The main types of cryptographic transformations of information. The essence of each transformation, the scope.

2. Representation of the encryption system by a graph, the principle of uniqueness of encryption-decryption.

3. Mathematical model of the information encryption-decryption system.

4. Strength of the encryption system, classification of encryption systems by strength. Types of attacks on the encryption system.

5. Definition of an unconditionally strong encryption system, statement about necessary conditions the existence of an unconditionally stable system.

6. Definition of an unconditionally secure encryption system, statement about sufficient conditions for the existence of an unconditionally secure system.

7. Computing persistent systems encryption, the concept of the complexity of cryptanalysis, the main approaches to the opening of cryptographic systems, the analysis of brute-force attacks and attacks based on message statistics.

8. Block cipher, Feistel scheme, block cipher properties.

9. Substitution cipher, its properties.

10. Code of gamming and its properties.

11. Mods (modes of operation) of block ciphers, a brief description of modes.

12. Encryption standard GOST R34.12-2015, the basic encryption algorithm for a 64-bit block.

13. Encryption standard GOST R34.12-2015, the basic encryption algorithm for a 128-bit block.

14. Encryption standard GOST R34.13-2015, encryption algorithm in the simple replacement mode, encryption algorithm in the gamma mode and gamma with feedback. Comparison of modes.

15. Linear recurrent register, algebraic properties linear recurrent sequence, analysis of the predictability property.

16. Linear recurrent register, statistical properties of a linear recurrent sequence.

17. Principles of constructing ciphering gamma generators (the concept of equivalent linear complexity, the use of non-linear nodes to increase linear complexity).

18. Code A5/1, characterization of the cipher, principle of construction, application.

19. The principle of construction and characteristics of the AES cipher.

20. The concept of a one-way function, general principle building cryptographic systems with a public key.

21. The concept of a hash function, the requirements for cryptographic hash functions.

22. Hashing function according to GOST R34.11-12, characteristic, construction principle, application.

23. ElGamal encryption system, attacks on the system.

24. RSHA encryption system, attacks on the system.

25. Definition, classification, basic properties, EP model.

26. Scheme of EP RSHA.

27. Scheme of the El-Gamal EP.

28. EDS according to GOSTR 34.10-12, general characteristics, the principle of signature formation and verification.

29. Authentication of messages in telecommunication systems (model of the imitation protection system, imposition strategies, indicators of imitation protection).

30. The concept of a key hash function. A class of strictly universal hash functions, examples of the implementation of these hash functions.

31. Building authentication systems with a guaranteed probability of imposition.

32. Building an authentication system for multiple message transmission.

33. Computing-resistant authentication systems.

34. Development of an imitation insert in accordance with GOST R34.12-2015.

35. Key management model in symmetric cryptographic systems, characteristic life cycle key.

36. Ways of distribution of keys on the basis of mutual exchange of messages between correspondents. Diffie-Hellman method.

37. Methods for generating random numbers when generating keys.

38. Methods for distributing keys using the CRC at the initial stage.

39. Methods of key distribution using the CRC in interactive mode. Needham-Schroeder protocol.

40. The principle of distribution public keys.

41. The concept of public key infrastructure (PKI), composition, principle of interaction of elements of the structure.

42. Purpose, principle of formation and characteristics of the public key certificate.

Practical part

1. Encrypt (decrypt) the message in manual mode substitution, permutation and gamming cipher. Program LR1_1.exe.

2. Decrypt the cryptogram based on the analysis of its statistics using the CHANGE.EXE program.

3. Find the error multiplication factor when decrypting the cryptogram of a block substitution-permutation cipher with a block length of 16 bits. tst program.

4. Decipher the cryptogram of the substitution-permutation cipher by exhaustive enumeration of keys using the tst program. Justify the parameters for making a decision on the correct decoding.

5. Encrypt a 64-bit message with the basic encryption algorithm GOST R 34.12-2015 (1 round)

6. Encrypt a 128-bit message using the AES.exe program. Check that the first transformation (SubBytes operation) uses the element in the GF(2 8) field.

7. Based on the characteristic polynomial h(x), construct an LRR (initial filling 10…01) Determine the period of the sequence. Find a balance, check the properties of the series and the window. Check the result using the LRR 1 program.

8. Find the sequence at the output of the encoding gamma generator containing the elements OR, AND-NOT, Jeff. Using the LRR 2 program, determine the equivalent complexity of the sequence. Construct an equivalent LRR. To conclude.

9. Perform the following calculations in the section of discrete mathematics:

Find the greatest common divisor using Euclid's algorithm;

Calculate a x modp using the fast exponentiation algorithm;

To find inverse element to a number modulo p.

Find the Euler function of the number x;

10. - using the Fermat test to check if the number x is prime, find the probability that the test gives an erroneous result.

11. The parameters of the ElGamal encryption system are set a=4, p=11, private key x=7 , encrypt the message M= . Decrypt the cryptogram.

12. The parameters of the RSA encryption system p=11, q=13 are set, to encrypt the message M=5. Decrypt the cryptogram.

13. The parameters of the ElGamal encryption system are set a=4, p=11, private key x=8, sign the message, the hash code of which is h(M)= . Check signature.

14. The parameters of the RSA encryption system p=11, q=13 are set, sign the message, the hash code of which is h(M)= 6. Check the signature.

15. Using the RSA program, encrypt a large file with a secure RSA cryptosystem and estimate the time of encryption and decryption.

16. Using the RSA program, sign the messages and verify the signature. The message length is at least 100 bits.

17. An elliptic curve E13(1,1) is given. Find point C equal to the sum of two points, coordinates of points and x 1 = , y 1 = , x 2 = , y 2 = . Find the opposite point. Calculate the point where k =3.

18. Generate Authenticator for Binary Message M=1010 based on strictly universal hash functions by algorithm K 0 \u003d 0101, K1= (ticket number) . Calculations in the field are carried out modulo an irreducible polynomial , b=4.