3) y = a x mod (p) is calculated;

4) the public key of the CPU verification is selected: ( p, a, y) and the secret key to create the CPU: x.

CPU shaping

If user A wants to sign a message m, represented as a number belonging to Zp, then he performs the following operations:

1) generates a secret number k: 1 ≤ k≤ p - 2; gcd ( k, p - l) = 1, where gcd is the gcd

2) calculates r = a k mod (p);

3) calculates k -1 mod (p - 1);

4) calculates s = k -l (m - xr) mod (p - l);

5) Forms the CPU S to the message m as a pair of numbers S = (r, t).

CPU verification (verification)

In order to verify the signature S created by A under the message M, any user takes the following steps:

1) obtains the public key A: (p, a, y);

2) verifies that 1 ≤ r ≤ p - 1, and if it fails, then rejects the CPU;

3) calculates V 1 = y r r s mod (p);

4) calculates V 2 = a m mod (p);

5) accepts the CPU as correct provided that V 1 = V 2

CPU Resilience Based on ElGamal's COP

1) An attacker can try to forge a signature to his message M as follows: generate a random number k, calculate r = a k mod (p), and then try to find s = k - l (m - xr) mod (p - l).

However, in order to perform the last operation, he needs to know a, which cannot be calculated with the appropriate choice of CPU parameters.

3) It should be noted that if not fulfilled step 2 of the CPU verification algorithm then an attacker can correctly sign any message of his choice, provided he has some other message with the correct CPU at his disposal. Thus, when choosing a module R, which in binary representation has a length of about 768 bits, provides good CPU stability, and to ensure long-term stability it is advisable to increase it to 1024 bits.

Requirements for cryptographic HF

1. Unidirectionality, when for a known hash h it is computationally unfeasible (that is, it requires an unrealizable large number of operations) to find at least one value of x for which, that is, h (x) turns out to be a unidirectional function (ONF).

2. Weak collision resistance, when for given x, h (x) = h it is computationally unfeasible to find another x 'value that satisfies the equation h (x') = h.

3. Strong collision resistance, when it is computationally impracticable to find a pair of arguments x, x ’for which the relation h (x) = h (x’) holds.

Vulnerability fix

Denning and Sacco suggested using timestamps in messages to prevent attacks like the one discussed above. Let us denote such a label by the letter t. Consider the option to fix the vulnerability:

PKI components

· Certificate Authority (CA)- the part of the public key system that issues a certificate to validate the rights of users or systems making a request. She creates a certificate and signs it using a private key. Due to its function of creating certificates, the CA is the central part of the PKI.

· Certificate Repository... Repository for valid certificates and Certificate Revocation Lists (CRLs). Applications verify the validity of the certificate and the level of access it grants by checking against the sample contained in the repository.

· Key Recovery Server- a server that performs automatic key recovery, if this service is installed.

· PKI-Enabled Application- applications that can use PKI tools for security. PKI manages digital certificates and keys used to encrypt information on web servers when using e-mail, exchanging messages, browsing the Internet, and transferring data. Some applications may use PKI natively, while others require programmers to modify.

· Registration Authority- a module responsible for registering users and accepting requests for a certificate.

· Security Server- A server that manages user access, digital certificates, and strong relationships in a PKI environment. The Security Server centrally manages all users, certificates, CA connections, reports, and verifies the certificate revocation list.

PKI functions

· Registration- the process of collecting information about a user and verifying its authenticity, which is then used during user registration, in accordance with security rules.

· Certificate Issuance... Once the CA has signed the certificate, it is issued to the applicant and / or sent to the certificate store. CA affixes a validity period to the certificates, thus requiring periodic renewal of the certificate.

· Certificate Revocation... A certificate can become invalid before expiration for various reasons: the user has left the company, changed his name, or if his private key has been compromised. Under these circumstances, the CA will revoke the certificate by entering its serial number on the CRL.

· Key Recovery... An additional PKI function allows you to recover data or messages in the event of a lost key.

· Lifecycle Management- Continuous support of certificates in PKI, including renewal, restoration and archiving of keys. These functions are performed periodically and not in response to ad hoc requests. Automated key management is the most important feature for large PKIs. Manual key management can limit PKI scalability.

Basic definitions

· Certificate Revocation Lists (CRLs)- list of canceled certificates. Cancellations may be due to a change of job, private key theft, or other reasons. PKI applications can check user certificates against a CRL before granting access against that certificate.

· Digital Certificate / X.509 Certificate... A data structure used to associate a specific module with a specific public key. Digital certificates are used to authenticate users, applications and services, and to control access (authorization). Digital certificates are issued and distributed by CAs.

· Digital Envelope... A method of using public key encryption to securely distribute secret keys used in symmetric encryption and to send encrypted messages. The key distribution problem associated with symmetric encryption is greatly reduced.

· Digital Signature... A method of using public key encryption to ensure data integrity and inability to refuse a parcel. The encrypted block of information, after decryption by the recipient, identifies the sender and confirms the safety of the data. For example: the document is "compressed", HASH is encrypted using the sender's private key and attached to the document (in fact, this means attaching the "fingerprint" of this document). The recipient uses the public key to decrypt the received message to the "squeeze" state, which is then compared with the "squeeze" obtained after the sent document is "compressed". If both "squeezes" did not match, then this means that the document was changed or damaged during the transfer.

· Public Key Cryptography... There are two main types of encryption: public key and secret (symmetric) key. Public key encryption uses a key pair: open, i.e. freely available, and its corresponding private key, known only to the specific user, application or service that owns this key. This key pair is linked in such a way that what is encrypted with the private key can only be decrypted with the public key and vice versa.

· Symmetric encryption (Shared Secret Cryptography)... There are two main types of encryption: public key and secret (symmetric) key. With symmetric encryption, the recipient and sender use the same key for encryption and decryption. This means that many users must have the same keys. Obviously, until the user receives the key, encryption is not possible, and the distribution of the key over the network is not secure. Other distribution methods, such as a special courier, are expensive and slow.

· RSA Algorithm is the first public key encryption system named after its inventors: Ronald Rivest, Adi Shamir and Leonard Adleman.

· Smart card. A credit card-like device with built-in memory and a processor used to securely store user keys and certificates and other information (usually social and medical).

· Digital Credentials. Within the framework of PKI technology, the ISO / TS 17090-1 standard defines this term as a cryptographically protected object that can contain individual user keys, certificates of individual keys, certificates of CAs of the user's PKI structure, a list of trusted CAs, and other parameters related to user domain - user identifier, names of applied cryptographic algorithms, values ​​of starting values, etc. Credentials can be placed on hardware or software media.

Principle of operation

Certificates are typically used to exchange encrypted data over large networks. A public key cryptosystem solves the problem of exchanging secret keys between participants in a secure exchange, but does not solve the problem of trusting public keys. Suppose that Alice, wanting to receive encrypted messages, generates a pair of keys, one of which (public) she publishes in some way. Anyone who wants to send her a confidential message has the opportunity to encrypt it with this key, and be sure that only she (since only she has the corresponding secret key) will be able to read this message. However, the described scheme can in no way prevent the attacker David from creating a key pair and publishing his public key, passing it off as Alice's key. In this case, David will be able to decrypt and read at least that part of the messages intended for Alice, which were mistakenly encrypted with his public key.

The idea behind a certificate is that there is a third party that is trusted by the other two parties to the information exchange. It is assumed that there are few such third parties, and their public keys are known to everyone in some way, for example, stored in the operating system or published in logs. Thus, a forgery of the public key of a third party is easily detected.

In previous issues, we found out that cryptography is a discipline that studies ways of protecting information interaction processes from purposeful attempts to deviate them from the conditions of normal flow, based on cryptographic transformations, that is, transformations of data using secret algorithms. From ancient times up to the present, the most important task of cryptography is to protect data transmitted through 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 the data is sent over the communication line or before being stored, it is subjected to encryption;
- to restore the original data from encrypted data, the procedure is applied to them decryption.

The following figure 1 shows the data conversion scheme for encryption:

Fig. 1. Data conversion scheme for encryption.

Cipher is a pair of algorithms that implement each of the indicated transformations. The secrecy of the second of them makes the data inaccessible for unauthorized acquaintance, and the secrecy of the first makes it impossible to impose false data. Obtaining open data encrypted 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 mixes well the structural units of the message (bits, symbols, etc.).

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

What conditions must the cipher satisfy? Well, first of all, the decryption procedure should always restore an open message in its 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 the cipher must satisfy is the following: 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 the encrypted data. In addition, the cipher must be cryptographically secure, that is, resistant to attempts to decrypt messages. It is clear that the issue of the strength of ciphers 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 undefined for him and, naturally, for the attacker - if this were not so, then there would be no point in sending it at all. Make it possible to send messages T1, T2, ..., Tn with probability p1, p2, ..., pn respectively. Then measure ambiguity of the message 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 reason, it is convenient to choose 2 as the base of the logarithm:

This value has a completely understandable physical meaning: the number of bits of information that necessary on average, transmit to completely eliminate uncertainty. If there is no a priori information about the message other than its size of N bits, then all possible 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. What if nothing is known about the source text, not even its size? In this case, it is still necessary to take as a basis any distribution model. As a rule, in reality, such difficulties do not arise, since many very strong ciphers<не считают нужным>to hide the size of the encrypted message, since this is almost never really necessary, and this characteristic is a priori considered known to the attacker. Where this size really needs to be hidden, all messages are converted to data arrays of the same length before encryption, and we again get the situation discussed above.

After the 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 encrypted message T " ... Now it is given by the following formula:

,

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

One of the most important characteristics of the cipher quality is the amount of information about the original 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 the uncertainty of the source text will decrease - it is clear that it cannot increase - when the corresponding ciphertext is received, in comparison with the a priori uncertainty, and whether it will not become less than the minimum allowable value.

In the best case for cipher developers, both of these uncertainties are equal:

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

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

Naturally, the main question that interested cryptographers was whether absolutely strong ciphers exist in practice. Experts intuitively understood that they exist, and an example of such a cipher was given by Vernam 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 strength of the cipher:

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

The uncertainty of the encryption algorithm is defined in the same way as the uncertainty of the message - the mathematical expectation of the binary logarithm of the probability of using the algorithm with a minus sign - and it makes sense only if a set of possible algorithms is defined and the probability of using each of them is set. The strength of ciphers is based on secrecy, that is, on the uncertainty for the attacker of the decryption algorithm - if this were not the case, anyone could decrypt the encrypted data. The less an attacker knows about the cipher, the less likely it is to successfully decrypt the message. Let us explain what has been said with an example: let a short 12-bit encryption be intercepted, which has the following content:

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

For simplicity, let's assume 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 variants is equally probable, and, thus, the probability of correctly identifying the original message by simple guessing is 2 -12. Suppose now that the attacker knows a priori that encryption is the imposition of the same 4-bit mask on every 4-bit group of the message using the operation bitwise exclusive or. Obviously, 16 = 2 4 different variants of the bit mask are possible, respectively, 16 different values ​​of the original text are possible:

mask original text 0000 100101110101 0001 100001100100 0010 101101010110 ..... 1111 011010001010

Thus, now the probability of correctly guessing the original text is 1/16 - knowledge of the peculiarities of the used encryption method increased it 256 times. An interesting conclusion follows from this: the greater the uncertainty in the encryption transformation for an outsider, the further it is from solving the cipher, the more reliable the cipher. A cipher completely undefined for an attacker

is unrevealed for him, that is, absolutely resistant! 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 is difficult to keep complete uncertainty about the cipher from the attacker - he can obtain information about the cipher in the following ways:

Analyze an intercepted encrypted message - he almost always has a certain set of ciphertexts at his disposal, for some of them there may be corresponding plaintext, or even the ability to get a ciphertext for any predetermined plaintext;

An attacker may 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 specific text, now - a piece of computer code or a microcircuit that implements hardware encryption.

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

1. Analysis of encrypted data should not give an attacker any information about the internal structure of the cipher. In the ciphertext, no statistical patterns should be traced - for example, statistical tests should not reveal any dependencies or deviations from the equiprobable distribution of the bits (symbols) 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 to avoid having to completely replace the algorithm at 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" Kerkhoff, which is not entirely true, since he is a Dutchman, not an Englishman, and the transcription of his surname should be German, not English), which is unconditionally accepted now in the art of building reliable 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 the transformations. Disclosing only the procedural part should not lead to an increase in the probability of successful decryption of the message by an attacker above the allowed limit. For this reason, and also due to the fact that declassification of this part is quite likely in itself, there is little sense in keeping it secret. A certain part of the algorithm parameters is kept secret, which is called cipher key:

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

here K - cipher key.

Using the Kirchhoff principle allows you to get the following advantages in the construction of ciphers:

Disclosure of a specific cipher (algorithm and key) does not lead to the need to completely replace the 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 secure 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 likelihood 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 the cipher for ciphers built in accordance with the Kirchhoff principle. Assuming that there is no a priori data about the encrypted text except for its length, we get that the uncertainty of the original text is equal to its length, expressed in bits:

H ( T ) = | T |.

The maximum possible uncertainty of a fixed-size data block is achieved when all possible values ​​of this block are equally probable - in this case, it is equal to the block size in bits. So 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 strong, it is necessary that the size of the key used for encryption be no less than the size of the encrypted data,

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

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

The operation used for imposing a gamma must satisfy certain conditions, which can be summed up as follows: the encryption equation must be unambiguously resolvable with respect to open data with known encrypted and key, and unambiguously resolvable with respect to the key with known open and encrypted data. If the operation satisfies this property, it is suitable. Among the suitable operations, there are no better ones and worse ones; from the point of view of the strength of the cipher, they are all the same - the concept of "perfection" does not know comparative degrees, it either exists or it does not exist. For this reason, for practical use, the most convenient operation in implementation is usually chosen - bitwise sum modulo 2 or bitwise exclusive OR, because she is:

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

It is the reverse of itself, so the same procedure is used for decryption and decryption.

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

Naturally, for such ciphers, the issue of a reliable assessment of their strength is relevant. For them, knowledge of the ciphertext makes it possible to reduce the uncertainty of the corresponding plaintext, thereby increasing the likelihood of successful decryption. However, contrary to popular misconception, it does not at all follow 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 oversimplification and is generally incorrect.

The point is that to slightly increase the probability of successful decryption and make it equal to one is not the same thing. This idea can be easily illustrated with an example: let a certain 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 source 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. It is obvious that our cipher is not absolutely secure. Let's assume that encryption "10" is intercepted. What is the source code? It is clear that it can be either 00 or 11, depending on the key value, and it is impossible to unambiguously determine this, which was required to be proved. For more advanced ciphers, the cryptanalyst will simply have more "choices" in 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 this decryption possible? Shannon explored this issue in detail in his works. For the analysis, he introduced the following characteristics of the cipher into consideration, in order to simplify the presentation, here they are given for the version of the bit representation of data:

1. Key unreliability function - key ambiguity for known n bits of ciphertext:

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

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

2. Distance of uniqueness of the cipher - 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-minimal of those for which

Shannon showed that both values ​​defined above depend on the redundancy of the plaintext, and the uniqueness distance is 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. In this case, the uncertainty of the source text will be equal to the uncertainty, and, therefore, to the size of the key:

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

The complete absence of redundancy in the source text means that no matter what key we take, after decryption we will receive the "correct" initial data, and there will simply be no reason to prefer one option to the other. From this, in particular, it follows that in real practice, before encrypting the data, it is very useful to "squeeze" some kind of archiver. Of course, complete redundancy of the source text is unattainable in this case, but such a "compression" will greatly complicate cryptanalysis based only on ciphertext.

Similar numerical characteristics of the strength of the cipher can be obtained for the situation when the cryptanalyst has at his disposal not only the ciphertext, but also the corresponding plain text. 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, it is very small. For these reasons, such a cipher can be easily broken with unlimited computing resources of an analyst, and completely different principles come to the fore when designing strong ciphers. But this will be discussed in the next issue.

(To be continued)

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 very 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 required to break a cipher is determined by its cryptographic strength. The larger it is, the "stronger" the encryption algorithm. It is even better if you cannot 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:

• Replacement or substitution algorithms - 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 the 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 the encryption of "username.pwl" files, in which the Microsoft Windows 95 operating system stores passwords for a given user's network resources (passwords for logging into NT servers, passwords for DialUp Internet access, 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 to encrypt 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 to 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 satisfied: there is no such algorithm (or it is not yet known) that would deduce the source text from the cryptotext and the public key. An example of such a system is the well-known RSA cryptosystem.

RSA Algorithm

The RSA algorithm (according to the first letters of the surnames of its creators Rivest-Shamir-Adleman) is based on the properties of prime numbers (and very large ones). Simple numbers are those numbers that have no divisors, except for themselves and one. Numbers that have no common divisors other than 1 are called coprime.

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 n as a result of multiplication p and q... Let's choose a large random number and 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)) = 1

(mod is the remainder of the division, that is, if e multiplied by d, 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.

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

C (i) = (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) = (C (i) d) mod n.

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

Let's try on small numbers.

Install p = 3, q ​​= 7... Then n = p * q = 21. We choose d as 5. From the formula (e * 5) mod 12 = 1 calculate e = 17... Public key 17, 21 , secret - 5, 21 .

Let's encrypt the sequence "12345":

C (1) = 1 17 mod 21 = 1

C (2) = 2 17 mod 21 = 11

C (3) = 3 17 mod 21 = 12

C (4) = 4 17 mod 21 = 16

C (5) = 5 17 mod 21 = 17

Cryptotext - 1 11 12 16 17.

Let's check the decryption:

M (1) = 1 5 mod 21 = 1

M (2) = 11 5 mod 21 = 2

M (3) = 12 5 mod 21 = 3

M (4) = 16 5 mod 21 = 4

M (5) = 17 5 mod 21 = 5

As you can see, the result is the same.

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

RSA Hacking Contests

Since its inception, RSA has undergone constant brute force attacks. In 1978, the authors of the algorithm published an article where they gave a string encrypted with a method they had just invented. The first person to decode the message was given a $ 100 reward, but that required factoring a 129-digit number 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 cracked by exhaustive search. Strictly speaking, the claim that the factoring problem is hard and that breaking the RSA system is hard has also not been 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 widespread email clients in Russia, The Bat! Program 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).

Rice. 3

Cryptography

Cryptography is the science of the principles, means and methods of transforming information to protect it from unauthorized access and distortion. Recently, it has been developing very, very rapidly. It is an endless and 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 numerical 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 ZHYUESHEZ, EYSCH YSHAZHFO ISYSCHYVESCH BSHIZEZHV EESH ZHRSCHSCH: LF EMRSU YZEZESHCHG, RYU RLZ ISCHEESYUZYUKYUKLU, DYO RLZ ISCHEESYUZYUKYUKLU

Were you in time? Here is a "solution":

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

Remember two important rules to start with:

You'd rather starve than eat anything

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

Decryption key: shift 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 that 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 built into various cryptographic tools supplied to the market). competition was MARS, RC6, Serpent, TwoFish All these algorithms were found to be quite robust and successfully opposed to 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;
• an 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.

Cryptographic System Models

Ciphertext- the result of the encryption operation. It is also often used instead of the term "cryptogram", although the latter emphasizes the very fact of the message being transmitted, not encryption.

The process of applying an encryption operation to a ciphertext is called re-encryption.

Ciphertext properties

Considering the ciphertext as a random variable depending on the corresponding random values ​​of the plaintext X and the encryption key Z, the following properties of the ciphertext can be determined:

The property of unambiguous encryption:

The chain equalities imply

(from the decryption unambiguity property)

(from the principle of independence of the plaintext from the key and the property of unambiguous encryption) then

this equality is used to derive the uniqueness distance formula.

For an absolutely reliable cryptosystem

That is

Usage for cryptanalysis

Shannon in his 1949 article "Theory of communication in secret systems" showed that for some random cipher it is theoretically possible (using unlimited resources) to find the original plaintext if the letters of the ciphertext are known, where is the entropy of the cipher key, r is the redundancy of the plaintext (including number including checksums, etc.), N is the size of the alphabet used.

Encryption- reversible transformation of information in order to hide it from unauthorized persons, with the provision, at the same time, authorized users of access to it. Mainly, encryption serves the purpose of maintaining the confidentiality of transmitted information. An important feature of any encryption algorithm is the use of a key that approves the choice of a specific transformation from the set of possible ones for this algorithm.

In general, encryption has two parts - encryption and decryption.

With the help of encryption, three states of information security are provided:

· Privacy: encryption is used to hide information from unauthorized users during transmission or storage.

· Integrity: encryption is used to prevent information being changed during transmission or storage.

· Identifiability: encryption is used to authenticate the source of information and prevent the sender of information from denying the fact that the data was sent to them.

Encryption and decryption

As it was said, encryption consists of two mutually opposite processes: encryption and decryption. Both of these processes at the abstract level are representable by mathematical functions to which certain requirements are imposed. Mathematically, the data used in encryption can be represented in the form of sets over which these functions are built. In other words, suppose there are two sets representing data - M and C; and each of the two functions (encryption and decryption) is a mapping of one of these sets to the other.

Encryption function:

Decryption function:

The elements of these sets - ~ m and ~ c - are the arguments of the corresponding functions. Also, the concept of a key is already included in these functions. That is, the required key for encryption or decryption is part of the function. This allows us to consider encryption processes in an abstract way, regardless of the structure of the keys used. Although, in general, for each of these functions, the arguments are data and an input key.

If the same key is used for encryption and decryption, then such an algorithm is referred to as symmetric. If it is algorithmically difficult to obtain the decryption key from the encryption key, then the algorithm is referred to as asymmetric, that is, to public-key algorithms.

· For use for encryption purposes, these functions must first of all be mutually inverse.

An important characteristic of the encryption function E is its cryptographic strength... An indirect assessment of cryptographic strength is an assessment of the mutual information between the plaintext and the ciphertext, which should tend to zero.

Cryptographic strength of the cipher

Cryptographic strength- the property of a cryptographic cipher to resist cryptanalysis, that is, an analysis aimed at studying the cipher in order to decrypt it. To study the crypto resistance of various algorithms, a special theory was created that considers the types of ciphers and their keys, as well as their strength. The founder of this theory is Claude Shannon. The cryptographic strength of a cipher is its most important characteristic, which reflects how successfully the algorithm solves the encryption problem.

Any encryption system, except for absolutely cryptographically secure ones, can be broken by a simple enumeration of all the keys possible in this case. But you will have to sort it out until the only key is found that will help decrypt the ciphertext.

Absolutely resistant systems

Shannon's assessment of the cryptographic strength of the cipher determines the fundamental requirement for the encryption function E. For the most cryptographically strong cipher, the uncertainties (conditional and unconditional), when intercepting messages, must be equal for an arbitrarily large number of intercepted ciphertexts.

Thus, an attacker would not be able to extract any useful information about the plaintext from the intercepted ciphertext. A cipher with this property is called absolutely resistant.

Requirements for absolutely strong encryption systems:

· A key is generated for each message (each key is used once).

· The key is statistically reliable (that is, the probabilities of occurrence of each of the possible symbols are equal, the symbols in the key sequence are independent and random).

· The length of the key is equal to or greater than the length of the message.

The durability of such systems does not depend on the capabilities of the cryptanalyst. However, the practical application of absolutely secure cryptosystems is limited by considerations of the cost of such systems and their convenience. Ideal secret systems have the following disadvantages:

The encryption system must be created with an extremely deep knowledge of the structure of the used message transmission language

· The complex structure of natural languages ​​is extremely complex and an extremely complex device may be required to eliminate the redundancy of the transmitted information.

· If an error occurs in the transmitted message, then this error grows strongly at the stage of encoding and transmission, due to the complexity of the devices and algorithms used.

Public Key Cryptographic System(or asymmetric encryption, asymmetric cipher) - an encryption and / or electronic signature (ES) system, in which the public key is transmitted over an open (that is, unprotected, accessible for observation) channel and is used to verify the ES and to encrypt the message. A private key is used to generate ES and to decrypt the message. Public key cryptographic systems are now widely used in various network protocols, in particular in the TLS protocols and its predecessor SSL (underlying HTTPS), in SSH. Also used in PGP, S / MIME.

Symmetric cryptosystems(also symmetric encryption, symmetric ciphers) - an encryption method in which the same cryptographic key is used for encryption and decryption. Before the invention of the asymmetric encryption scheme, the only existing method was symmetric encryption. The algorithm key must be kept secret by both parties. The encryption algorithm is chosen by the parties prior to starting the exchange of messages.

State and military correspondence arose in ancient times and was 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 a different alphabet.

Not to be confused with cryptography latent (sympathetic) writing, the essence of which is to hide the visibility of the written. For example, an inscription made with milk on white paper is not visible without heating this paper.

So for 400 years BC. NS. 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 on exactly the same cylinder.

For 300 years BC. NS. in Greece, the work "Tacticus" was written about hidden messages. 200 years BC. NS. 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 required letter was found in the square and replaced with another letter from the same column, but inscribed in the line below. The letter in the bottom row of the square was replaced with the letter in the top row of the same column. The recipient, who had exactly the same square, decrypted the message by performing the indicated operations in the reverse order.

Caesar, in correspondence with Cicero, used what is now called Caesar's cipher. Caesar's method is as follows. First, each letter of the alphabet is associated with its serial number. Then, during encryption, not the letter itself 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 set by the ratio:

n = (K + I) mod m,

where NS- the number of the letter obtained as a result of encrypting the letter with the number I Here we used the operation of calculating modulo T, when performed, not the amount itself is recorded K + I, and the remainder of dividing this sum by T.

The generalization of the Caesar cipher is called a simple replacement 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 that is the key. For example, a is replaced by v, b-on with, in- on v,..., I am- on G. The number of possible permutations with such encryption corresponding to an alphabet with volume T= 32 is m! =32! = 2, 63 10 35. If in one second, when decrypting by a simple brute-force method, one enumerates a million keys, then the total decryption time will be 8.3-10 21 years.

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

Many famous mathematicians such as Viet, Cardano, Leibniz and, finally, Francis Bacon were involved in cryptography. The latter proposed a binary encoding of the 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 encryption 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 offered in 1917 by Vernam. In the same year, a rotary encryption machine was invented, later produced by Siemens under the name "Enigma" (mystery) - the main enemy of the cryptographers of the Allied Powers during the Second World War.

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

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

Simultaneously with the improvement of the art of encryption (Fig. 1), there was the development of cryptanalysis, 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, there are a number of significant differences between the modern stage and the previous ones, namely:

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

Use of high-speed computing equipment,

Discovery of a new type of cryptography with more "transparent" cryptanalysis methods (public key cryptography),

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

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

2. Mathematical model of the encryption / decryption system of discrete messages

We will consider encryption and decryption of so-called discrete messages, which can be represented by signals with 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. In the case of analog signals, other methods are used, which will be discussed separately.

The mathematical model of the encryption / decryption system for discrete messages is a pair of functions

, (1)

, (2)

which transform the message M into cryptogram E using an encryption key K W and, conversely, a cryptogram E in the message M using the decryption key To DS. Both the functions defining the cryptosystem must meet the following requirements:

Functions f(,) and g (,) for known arguments are calculated simply,

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

The decryption key is assumed K DSh 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 DS. The last condition is the so-called Kaziski principle.

If the encryption key is equal to the decryption key, i.e. K W = K DSh then the system is called symmetric (single-key). For its operation, identical keys must be secretly delivered to the encryption and decryption points.

If K W = K DSh, then the encryption system is called asymmetrical (two-key). In this case, the key K W delivered to the encryption point, and the key K DSh - to the decryption point. Both keys should obviously be linked by functional dependency. K LH = φ (K W) but such that according to the known encryption key K W it would be impossible to recover the decryption key K DSh This means that for an asymmetric encryption system φ(.) 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 to make the encryption keys public 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 Hellman in 1976. It is necessary to distinguish between three main types of attacks (attacks) of opponents on the cryptosystem:

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 (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 to all three types of attacks.

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

Decryption after the transmission of the cryptogram over the noisy channels should not increase the number of errors in comparison with the number of errors that formed in the communication channel due to interference, in other words, there should be no multiplication of errors after decryption.

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

The location and magnitude of errors in the received cryptogram are determined by the vector of channel errors e... With a binary transmission system, the received cryptogram will have the form E- E ® ё where is the sign ® means bitwise addition modulo 2, and the total number of errors 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.