Difference between asymmetric and symmetric encryption methods? Cryptographic algorithms used to ensure information security when interacting on the Internet

TERENIN Alexey Alekseevich, Candidate of Technical Sciences

Cryptographic algorithms used to ensure information security when interacting on the INTERNET

A brief overview of the most common encryption algorithms today, their description, as well as problems encountered during their implementation and significant aspects in practical use are presented.

Protecting information using cryptographic transformation methods involves changing its components (words, letters, syllables, numbers) using special algorithms or hardware solutions and key codes, that is, bringing it to an implicit form. To familiarize yourself with encrypted information, the reverse process is used: decoding (decryption). The use of cryptography is one of the common methods that significantly increases the security of data transmission in computer networks, data stored in remote memory devices, as well as when exchanging information between remote objects.

For conversion (encryption), some algorithm or device is usually used that implements a given algorithm, which may be known to a wide range of people. The encryption process is controlled using a periodically changing key code, ensuring an original representation of information each time when using the same algorithm or device. Knowing the key allows you to simply and reliably decrypt the text. However, without knowing the key, this procedure can be practically impossible even with a known encryption algorithm.

Even simple transformation of information is a very effective means of hiding its meaning from most unskilled violators.

Brief historical overview of the development of encryption

The origins of cryptography go back to Egyptian hieroglyphs. Since ancient times, when Egypt and Persia flourished, messengers were used for the most important state and military missions, carrying the text of the message either on parchment or in their heads to convey it in words, the latter method being more preferable. Even then, more or less successful ways to protect transmitted information from attacks by interceptors appeared. Let us cite a well-known legend from the Ancient World. A certain king, having been captured, made a tattoo on the head of a slave - a message to the allies. When the hair grew back, the slave moved to the recipients of the message and the king was freed. The prototype of modern steganography.

The ancient Greeks used round sticks of the same diameter, on which strips of parchment were wound. The inscription was made longitudinally along the length of the stick. It was possible to fold the text into a readable text only if you had a stick of the same diameter.

In Ancient Rome, the science of cryptography, translated from Latin as secret writing, was already clearly beginning to take shape. The Caesar cipher appears when each letter is replaced by a letter three away in the alphabet.

In medieval intriguing Europe and Central Asia, there was a rapid development of cryptography and cryptanalysis - methods of breaking cipher texts. The first systematic work on cryptography is considered to be the book of the architect Leon Battisti Alberti (1404 - 1472). One of the first cryptanalysts was François Viète (1540 - 1603), at the court of King Henry IV of France. At the same time, advisors from the Adgenti family, who can also be called cryptanalysts, served at the court of the Pope. The entire period until the middle of the 17th century. full of works on cryptography and cryptanalysis.

In the 19th and first half of the 20th centuries. For secret diplomatic correspondence, many countries, including Russia, use encryption methods, the keys for which were compiled from excerpts of certain texts of ordinary books (cipher books).

Since the beginning of the twentieth century. - from the First World War - special encryption machines began to be used.

The German Enigma machine, the code of which was revealed by the British, is widely known. In order not to give away the fact of the disclosure of the German code, the British government made great sacrifices among the civilian population, without warning the residents of two large cities about the impending bombing. But this later helped to gain a significant advantage in the northern naval battles with Germany, when the invincible German submarines and cruisers were destroyed.

After World War II, computers took over cryptography. For a long time, this was the domain of the most powerful supercomputers of their time.

Publications on this topic were strictly classified and the use of scientific research in this area was a domestic prerogative. Only Von Neumann's textbook work of the 40s was publicly available, describing, in addition to the principles of constructing computer systems, some other possible malicious methods of influence for disrupting the “legal” computing process, as well as the classic work of Shannon, which laid the foundations of computer cryptography.

Since the 70s open publications appear: Haffey-Dilman in 1976. In 1970, there was a secret invention by James Ellis (Great Britain) in the field of cryptography. The most famous asymmetric cryptography algorithm is RSA, developed by Ronald Rivest, Eddie Shamir and Len Edleman in 1977. The RSA algorithm is of great importance because. can be used both for public key encryption and for creating an electronic digital signature.

This was a revolutionary period in the development of cryptographic science. New methods for secretly distributing key information in open computing systems emerged, and asymmetric cryptography was born.

But even after this, for a long time, the prerogative of using cryptography in data protection was with government services and large corporations. The computing technology of that time, with the power necessary for cryptographic transformations, was very expensive.

At that time, the main state standards of cryptographic algorithms appeared (USA and some European countries), the use of which was prescribed when working with information classified as state secrets.

The veil of secrecy around these technologies even led to the fact that in the United States cryptographic algorithms were equated to weapons, and a ban was introduced on the export of encryption hardware and software. Then export restrictions were introduced on the length of the key used in encryption algorithms outside the United States, which allowed American intelligence agencies to decrypt messages using available computing power without knowing the shortened key. On March 1, 2001, export restrictions were lifted. Due to the events that occurred on September 11 of the same year, there has been a tightening of government control. The US government is considering options to reintroduce export controls on encryption tools.

Let's go back to the 70s. Since that time, neither scientific research nor the development of computing tools has stopped. The computing power of supercomputers increases several times every few years. A personal computer appears. The power of a personal computer is approximately equal to the power of a supercomputer ten years ago. Now personal computers have become even more powerful.

Since the 80s ordinary users have the opportunity to use cryptographic tools on their computers, which is vehemently prevented by government agencies; it becomes more difficult to monitor the activities of the country’s citizens, including criminal elements.

The release of Phil Zimmermann's PGP (Pretty Good Privacy) program (version 1.0 was released in 1991) and its provision of open and free use provided great opportunities for ordinary computer users. Phil Zimmermann was even declared an enemy of the state and sentenced to prison.

Constantly increasing computing power forced the use of increasingly complex crypto-transformation algorithms or increasing the length of the keys used in encryption.

Standards for cryptographic algorithms were becoming outdated and becoming unreliable. Information locked with a certain key could no longer be kept confidential for long enough - as long as required by government regulations. For example, storing information in complete secret in encrypted form for 5 years meant that the enemy, possessing the most powerful computing means, constantly searching through possible keys, would most likely not have found the necessary key to decrypt the stored information during this period.

Competitions began to be held to reveal some information encrypted using the algorithm of one of the standards. The winner was awarded a substantial cash prize, as well as worldwide fame in the information community. By uniting ordinary computers in a computer network to work in parallel on solving a given problem, users gathered in groups and selected a key together.

A key length of 48 bits means that 2 48 searches need to be done. Increasing the key length, for example, by only 16 bits, means that it is necessary to enumerate 2 16 times more.

But even this key size made it possible for united groups to solve the problem of breaking the cipher in days and even hours of parallel work. Subsequently, it was necessary to switch to keys that were several times longer than those mentioned. But this was only a temporary measure, and new standards for crypto-transformation algorithms (AES in the USA) were recently adopted.

Currently, many publications devoted to this problem have appeared in the press. Numerous books are published, both translated and by Russian authors. The problem of protecting information from disclosure and modification can be solved by cryptography. The complexity of the mathematical apparatus of modern cryptography exceeds that used to develop nuclear weapons and space systems.

Modern cryptography is divided into symmetric and asymmetric. Symmetric – for stream cipher, block and composite. Asymmetric cryptography is more resource-intensive, and in symmetric cryptography there is a problem of efficient key distribution. Modern secure exchange systems are based on the use of mixed cryptography. At the beginning of the exchange session, the parties send each other secret session keys via asymmetric cryptography, which are then used to symmetrically encrypt the sent data. An asymmetric cryptography system allows keys to be distributed in symmetric encryption systems.

Government and military telecommunications systems use exclusively symmetric encryption (most often using one-time keys). This is due to the fact that the security of public key systems has not been strictly mathematically proven, but the opposite has not been proven either.

Information encryption should not be accepted as a panacea for all information threats. It should be perceived as one of the mandatory information protection measures as part of a comprehensive information security system. The use of encryption should be combined with legislative, organizational and other protective measures.

Symmetric encryption algorithms

Encryption algorithms are designed to solve the problem of ensuring information confidentiality. Currently, cryptographic methods are intensively used to hide information. Since ancient times, encryption has been and remains the most effective form of protection.

Encryption is defined as the reciprocal transformation of unprotected (open) information into an encrypted (closed) form - ciphertext, in which it is not completely accessible to an attacker. Encryption uses keys, the presence of which means the ability to encrypt and/or decrypt information. It is important to note that the encryption method itself does not need to be kept secret, since knowing it alone will not allow you to decrypt the ciphertext.

Modern cryptosystems can be clearly divided according to the method of using keys into cryptosystems with a secret key (symmetric) and with a public key (asymmetric). If the same key is used for encryption and decryption, the cryptosystem is called symmetric.

Symmetric cryptosystems include DES, AES, GOST 28147-89, etc. A new direction in cryptography was the invention of asymmetric public key cryptosystems, such as RSA, DSA or El-Gamal.

In asymmetric cryptosystems, different keys that are practically indeducible from each other are used for encryption and decryption, one of which (the decryption key) is made secret, and the other (the encryption key) is made public. This makes it possible to transmit secret messages over an insecure channel without first transmitting a secret key. It was public key cryptography that broke the vicious circle of symmetric ciphers, when in order to organize the exchange of secret information it was necessary to first distribute secret keys.

Public key cryptosystems will be discussed in detail later, but now let’s return to symmetric cryptosystems (KS).

The most important component of the CS are ciphers or procedures for the inverse transformation of plaintext M into ciphertext M":

M' = E(M),
M = D(M’),

where E is the encryption function and D is the decryption function.

The generally accepted approach in cryptography is to construct a cipher in such a way that its secrecy is determined only by the secrecy of the key K S (Kerkoff's rule). Thus, the cipher must be resistant to cracking, even if the potential cryptanalyst knows the entire encryption algorithm except the value of the key used, and has the full text of the intercepted ciphergram.

Practice has shown that the more well-known an algorithm is, the more people have worked with it, the more proven, and therefore reliable, it becomes. Thus, publicly known algorithms now stand the test of time, but secret government ciphers reveal many errors and shortcomings, since it is impossible to take everything into account.

The generally accepted scheme for constructing symmetric cryptosystems is cyclic permutations and substitutions of bits in a block of fixed length, the algorithm of which is determined by the secret key.

An encryption algorithm is considered strong if, having private data and knowing the secret key, it is impossible to obtain information about open data. It has been strictly proven that it is impossible to construct an absolutely strong cipher, except for the case when the size of the secret key is equal to (or greater than) the size of the encrypted data. This case is difficult to implement in practice, because actually used and available on the market cryptographic protection tools use ciphers for which the task of restoring the plaintext from the closed text is difficult to calculate, that is, it requires so many resources that the attack becomes economically impractical.

Among the symmetric ciphers, the most famous and frequently used are the following (the block size in bits is denoted by b, the number of cycles is r, and the key length is l):

DES- US government standard (b = 64, r = 16, l = 56). Currently, DES has been proven to be insufficiently robust against brute-force attacks.
Triple DES and DESX(b = 64, r = 16, l = 168;112) - sequential application of the DES algorithm with different keys, which provides significant resistance to hacking.
IDEA- (b = 64, r = 8, l = 128) . Active research into its strength has revealed a number of weak keys in it, but the likelihood of their use is negligible.
RC5- a parameterized cipher with variables block size (b I), number of cycles (r Ј 255) and number of key bits (l Ј 2040). Studies of its strength have shown that at b = 64 it is inaccessible for differential cryptanalysis at r = 12 and for linear cryptanalysis at r = 7.
GOST 28147-89- Russian data encryption standard (b = 64, r = 32, l = 256). Many weak keys have been found for GOST, significantly reducing its effective strength in simple encryption modes. Assessing the cryptographic strength of GOST is also complicated by the fact that the most important part of the algorithm - replacement nodes or S-boxes in the terminology of the DES cipher - is not described in the standard and the laws of its generation remain unknown. At the same time, it has been proven that there is a high probability of obtaining weak replacement nodes that simplify the cryptanalysis of a given cipher.
Blowfish is a 64-bit block cipher developed by Schneier in 1993, implemented through key-dependent permutations and substitutions. All operations are based on XORs and additions on 32-bit words. The key has a variable length (maximum 448 bits) and is used to generate several subkey arrays. The cipher was created specifically for 32-bit machines and is significantly faster than DES.

The US has now adopted a new encryption standard, AES. A competition was held among encryption algorithms, which was won and formed the basis of AES - Rijndael. Rijndael is an iterative block cipher having variable block lengths and varying key lengths. A more detailed description of this algorithm and the results of the competition is given in.

A fairly large number of symmetric algorithms have been developed, published and studied in the world (Table 1), of which only DES and its modification Triple DES have been sufficiently time-tested. The table does not include little-known and poorly studied algorithms, such as Safer, etc.

Table 1. Overview of symmetric encryption methods

	Key length, bits	Block size, bits	Key selection costs, MIPS x years	Note
DES				Developed in 1977 by IBM for the US government. For 20 years, no way has been found to crack the cipher, except for exhaustive search on average of 25% of all keys, but with modern capabilities it allows you to achieve success
Triple DES				Repeating the DES algorithm three times with different keys. The effective key length is 112 bits.
IDEA				Developed in 1992 by Lai and Massey. Not hacked to date
GOST 28147-89			no data	Is the State standard in Russia
RC5			10 3 and above	A 40-bit key was cracked by brute force in 1997 in 3.5 hours, a 48-bit key in 313 hours
Blowfish			no data	Developed by Schneier in 1993. This Feistel cipher was created specifically for 32-bit machines and is significantly faster than DES
AES (Rijndael)	Key length and block length can be 128, 192 or 256 bits, independently of each other			Proposed by cryptanalysts Joan Daemen and Vincent Rijmen. The algorithm has no known security weaknesses (according to NIST).

Currently, symmetric algorithms with a key length greater than 100 bits (Triple DES and IDEA, etc.) are not unbreakable. The domestic GOST algorithm, in comparison with them, is characterized by increased complexity both when generating replacement nodes and when generating keys. Also, for the GOST algorithm, there is a high probability of generating an unstable key, which in some encryption modes reduces its effective key length from 2,256 to 2,62.

Triple DES is a more proven algorithm than IDEA and provides acceptable performance. The Triple DES algorithm is the application of the DES algorithm three times to the same data, but with different keys.

DES has penetrated into Russia and is quite widely used in practice as an integral part of various software and hardware, of which the most widely known are the S.W.I.F.T. system, secret VISA and EUROPAY modules, secret modules of ATMs and trading terminals, and, finally, smart cards. Particularly intense discussions around data encryption algorithms are caused by smart cards. At the same time, there are serious reasons to believe that the reliability of domestic cryptosystems of conversion origin will be superior to their foreign counterparts.

However, Russian legislation, like the legislation of many other countries, only allows the use of national encryption standards.

The GOST 28147-89 algorithm is built on the same principle as DES; it is a classic block cipher with a secret key, but differs from DES in a larger key length, a larger number of rounds, and a simpler scheme for constructing the rounds themselves. In table 2 shows its main parameters, for convenience - in comparison with the parameters of DES.

Table 2. Comparison of parameters of DES and GOST ciphers

If secret information needs to be exchanged between persons who trust each other, i.e. members of the same organization can use symmetric cryptography. Of course, both (or more) parties must already have encryption keys for interaction.

To briefly describe the information exchange scenario, it is as follows:

• an existing file containing secret information is created or used;
• the file is encrypted using a key known to both parties, determined by the encryption algorithm;
• the encrypted file is transferred to the subscriber, the storage medium is not so important, it can be a floppy disk, e-mail, a message on the network or a modem connection; it is very convenient, to reduce the risk, to also store all files containing secret information in encrypted form. Then, if a computer, a laptop of a business trip employee, or a hard drive falls into the hands of an attacker, the files locked with the key will not be available for direct reading. Nowadays the world uses systems that automatically encrypt all information stored in a laptop; they also provide a forced login mode; if an employee is forced to boot a laptop, then by entering a special password instead of the usual one, all information can be destroyed; of course, a recovery mode is provided after this action. The hard drive can simply be removed from the computer; it is not so difficult to remove it from the protected area (compared to a whole computer);
• on the receiving side, the legitimate recipient, in possession of the key, opens the encrypted files for further use.

Many modern methods of protective transformations can be classified into four large groups: permutations, substitutions (substitutions), additive and combined methods. Permutation and substitution methods are usually characterized by a short key length, and the reliability of their protection is determined by the complexity of the conversion algorithms. Additive methods are characterized by simple conversion algorithms, and their cryptographic strength is based on increasing the key length.

Breaking the cipher

There is a way to break a cipher based on trying all the key options. The criterion for the correctness of a variant is the presence of a “probable word” in the text.

The set of all possible keys is enumerated, and the ciphertext is decrypted using each key. In the resulting “pseudo-open” text, a probable word is searched. If there is no such word, the current text is rejected and the transition to the next key is carried out. If such a word is found, a variant of the key is displayed on the screen. Then the search for keys continues until the entire set of options is exhausted. It is possible to detect several keys in which there is a probable word in the “pseudo-plaintexts”.

After the search is completed, it is necessary to decrypt the text using the found keys. “Pseudo-plaintext” is displayed on the screen for visual control. If the operator recognizes the text as open, then the opening work ends. Otherwise, this key option is rejected and the transition to the next key is carried out.

The brute force method can be combated by increasing the length of the encryption key used. Moreover, increasing its length by only 8 bits increases the number of search options by 2 8 times, respectively, by 64 bits – by 2 64 times.

Among the problems inherent in the use of cryptographic encryption algorithms, it is necessary to highlight the problem of key distribution. Before communicating parties can send encrypted messages to each other, they must exchange encryption keys over some secret channel. In addition, a huge number of keys must be kept up to date in the information exchange system.

Cryptographic encryption algorithms do not make it possible to establish the integrity of the received message (i.e., to ensure that the message was not modified during transmission). Authorship can only be confirmed by possession of a specific key, so anyone who becomes the owner of someone else's key will be able to pass off their messages as messages sent from another user.

The problem of distributing secret keys over a public communication channel can be solved by the Diffie-Hellman algorithm. But this algorithm belongs to asymmetric cryptographic algorithms. They use two keys: public and private.

Asymmetric cryptographic algorithms received rapid development in the 70s. last century. Such algorithms can also solve the problems of confirming authorship and authenticity, making it possible to organize the exchange of encrypted information between parties that do not trust each other. In addition, the use of asymmetric algorithms reduces by an order of magnitude the number of keys that must be distributed between interacting parties. Asymmetric encryption systems include a publicly available database of public keys that can be distributed over open communication channels and their disclosure will in no way lead to compromise of the system, which is why they are called open.

Asymmetric encryption algorithms

Public key cryptosystems are usually built on the basis of a complex mathematical problem of calculating a function that is the inverse of a given one. Such functions are called unidirectional, i.e. their reversal is an almost impossible task. The essence of the encryption method is that the function of an encrypted message is calculated in the forward direction using the public key of the receiving subscriber, and when decrypting (calculating the inverse function) its secret key is used. As one might expect, little is known about mathematical problems that satisfy the listed requirements, and only a few of them have been used to construct ciphers used in practice. Let's consider a number of the most well-known public key cryptosystems.

• RSA. The problem of factorization (calculating prime factors) of a large integer is used. Constructed based on the multiplication of two large-digit prime numbers. Widely used in cryptographic privacy and authentication protocols.
• El-Gamal. Based on the discrete logarithm problem in a finite field. Used in electronic digital signature (EDS) standards DSS, GOST R34.10-94, etc.
• Elliptic curves. Based on the discrete logarithm problem on elliptic curves in a finite field.

Inverse problems of factorization and discrete logarithmization are solved by methods close to exhaustive search, and when the numbers are large, they are difficult to calculate.
Public key cryptosystems are used mainly in three ways:

• information closure;
• authentication using digital signature;
• interception-protected distribution of public keys (Diffie-Hellman cryptosystem).

The advantages and disadvantages of asymmetric cryptosystems are discussed in more detail in.

Hash functions

Protocols for protecting integrity and authenticity when generating imitations and digital signatures use cryptographic “compression” hash functions that make it possible to obtain a value with a fixed number of bits from a data block of arbitrary length.
In order to reduce the volume of digital signature and reduce the time for its generation and verification, it is applied to hash values, which are usually much shorter than the original messages. A number of requirements are imposed on cryptographic hash functions aimed at making it difficult to forge digital signatures by finding such a modification of a data block in which the hash function value and, consequently, the digital signature remain unchanged.
The most widely used hash functions are based on a system of cyclically repeated permutations and substitutions (the length of the generated hash value in bits is indicated in parentheses):

• MD5 (128);
• SHA-1 (160);
• GOST (256).

Table 1. List and parameters of hash functions

Hash function	Value length, bits	Block size, bits	Performance, Mb/s	Note
			no data	Developed by Ron Rivest in 1989. Collisions detected in simplified compression function
				Developed by Ron Rivest in 1990. Collisions detected
				Developed by Ron Rivest in 1991. Collisions detected in the compression function
				Developed in 1995 in the European RIPE project
				Developed in 1995 by NIST
				GOST of Russia

In table 1 does not show rarely used and exotic hash functions, as well as hash functions built on symmetric block ciphers according to the Meyer–Matyas and Davies–Price schemes.
The mentioned hash functions are described in more detail in.
Although public key cryptographic protection or asymmetric cryptosystems have been especially widely used since the late 70s. , they have a very serious drawback - extremely low performance. In this regard, in practice a combined cryptographic protection scheme is usually used. When establishing a connection and authenticating the parties, “public key” cryptography is used, then a session key is generated for symmetric encryption, which closes all traffic between subscribers. The session key is also distributed using the public key.

Rice. 2. Scheme of the asymmetric cryptosystem algorithm

Table 2. Asymmetric cryptosystems

Method name	Hacking method (mat. problem)	Cryptographic strength, MIPS	Note
		2.7 1028 for 1300 bit key	Developed in 1977 by Ron Rivest, Adi Shamir and Leonard Eidelman. Included in many standards
	factorization of large prime numbers
El-Gamal (El Gamal)	finding a discrete logarithm in a finite field	with the same key length, the cryptographic strength is equal to RSA	Designed by ElGamal. Used in the digital signature algorithm of the DSA standard DSS
Elliptic equations	solving elliptic equations	cryptographic strength and speed are higher than RSA	Modern direction. Developed by many leading mathematicians

The RSA method is currently the de facto standard in information security systems and is recommended by the CCITT (Consultative Committee in International Telegraphy and Telephony) in the X.509 standard. RSA is used in many international standards (S-HTTP, PEM, S-MIME, S/WAN, STT, SSL, PCT, SWIFT, ANSI X.9.31, etc.), in credit card processing systems, in operating systems for protection of network protocols.
A huge amount of scientific research has been carried out on the RSA and El-Gamal methods, a large number of methods for their cryptanalysis and protection against attacks have been studied, and cryptographic strength has been calculated in detail depending on the key length and other parameters. Both methods have the same cryptographic strength (with the same key length) and approximately the same speed. Considering that the elliptic curve method is undergoing testing and has not been subjected to as many hacking attempts as the RSA and El-Gamal methods, the use of the latter two in encryption systems looks preferable.
A detailed description of these algorithms is given in.

Electronic digital signature

If information is exchanged between parties that do not trust each other or are interested in carrying out actions directed against each other (bank and client, store and buyer), it is necessary to use asymmetric encryption methods, as well as the digital signature method.
It is necessary to ensure not only confidentiality, but also the integrity of the message (the inability to replace the message or change anything in it), as well as authorship. In addition, it is necessary to prevent the author of the message from refusing to send a signed message.
An electronic signature of a document allows you to establish its authenticity. In addition, cryptographic measures provide protection against the following malicious actions:

• refusal (renegade) - subscriber A declares that he did not send a message to B, although in fact he did;
• modification (alteration) – subscriber B changes the document and claims that he received this document (modified) from subscriber A;
• substitution - subscriber B generates a document (new) and states that he received it from subscriber A;
• active interception - an intruder (connected to the network) intercepts documents (files) and changes them;
• “masquerade” – subscriber B sends a document on behalf of subscriber A;
• repeat – subscriber B repeats a previously transmitted document that subscriber A sent to subscriber B.

All of the above types of malicious actions cause significant damage. In addition, the possibility of malicious acts undermines trust in computer technology. The authentication problem can be solved based on a cryptographic approach by developing special algorithms and programs.
When choosing an authentication algorithm and technology, it is necessary to provide reliable protection against all of the above types of malicious actions (threats). However, within the framework of classical (single-key) cryptography, it is difficult to protect against all of the above types of threats, since there is a fundamental possibility of malicious actions by one of the parties who owns the secret key.
No one can prevent a subscriber, for example, from generating any document, encrypting it using an existing key common to the client and the bank, and then declaring that he received this document from a legitimate transmitter.
It is effective to use schemes based on two-key cryptography. In this case, each transmitting subscriber has its own secret signature key, and all subscribers have the non-secret public keys of the transmitting subscribers.
These public keys can be interpreted as a set of verification relations that allow one to judge the truth of the signature of the transmitting subscriber, but do not allow one to recover the secret signature key. The transmitting subscriber is solely responsible for his or her private key. No one but him is able to generate a correct signature. The secret key of the transmitting subscriber can be considered as a personal seal, and the owner must in every possible way limit access to it by unauthorized persons. .
To practically implement the idea of ​​open encryption, it was necessary to find specific and constructive answers to the following questions:

• how to “mix” the user’s individual key with the contents of the document so that they become inseparable?
• how to check that the contents of the document being signed and the user’s individual key are authentic without knowing either one or the other in advance?
• How to ensure that the author can reuse the same individual key to digitally sign a large number of electronic documents?
• How can we guarantee that it is impossible to recover a user’s individual key using any number of electronic documents signed with it?
• How to guarantee the authenticity of the verification of a digital signature and the contents of an electronic document?
• How to ensure the legal validity of an electronic document with digital signatures that exists without a paper duplicate or other substitute?

It has taken about 20 years to answer all these questions since the idea was first formulated in 1976 in a paper by Whitfield Diffie and Martin Hellman. Now we can definitely say that all these issues have been resolved: there is a full arsenal of technical means for authorizing electronic documents, called digital signatures. Modern principles for constructing a digital signature system are simple and elegant:

• methods for calculating and verifying digital signatures of all system users are the same and are based on well-known mathematical problems;
• methods for calculating digital signature verification keys and individual digital signature generation keys are also the same for everyone and are well known;
• individual keys for generating digital signatures are selected by the users themselves according to a random law from a large set of all possible keys;
• With a specific digital signature algorithm, its strength can be assessed without involving any “secret” information based only on known mathematical results and reasonable assumptions about the computing power of a potential attacker.

Cryptographic protection means ensure the authenticity and authenticity of information, in addition to solving the problem of maintaining its confidentiality. These functions are performed by digital signature technology.
The digital signature operation diagram is shown in Fig. 3.

Rice. 3. Electronic digital signature algorithm

The input of the algorithm is a file, not necessarily a text one, the main requirement for the input parameters of the digital signature is a fixed length, for this a hash function is used.
Theoretically, the use of various encryption means promises bright prospects for all companies that use the Internet in their activities, but here a new problem arises - to find a compromise with the state and its laws, this problem is covered in detail in.
In accordance with the Federal Law “On Electronic Digital Signature” No. 1-F3 of January 10, 2002, an electronic digital signature in an electronic document is recognized as equivalent to a handwritten signature in a paper document. Legal regulation is also provided for the organization of electronic document management, distribution of public and private keys, construction of certification centers, and the responsibilities of the parties are determined.
The adoption of this law, although there are some uncertainties in it, made it possible to regulate the use of asymmetric encryption means, in this case digital signature, to protect data on the Internet.

Literature

1. Shannon C.E. Communication Theory of Secrecy Systems. Bell Systems Technical Journal 28, 1949, p. 656 - 715.
2. Federal Information Processing Standards Publication 46-2. Data Encryption Standard (DES). NIST, US Department of Commerce, Washington D.C., 1993.
3. GOST 28147-89. Information processing systems. Cryptographic protection. Cryptographic conversion algorithm.
4. Bruce Schneier, Applied Cryptography: Protocols, Algorithms and Source Code in C. John Willey & Sons, 1994.
5. Nechvatal James. Public-Key Cryptography. NIST, Gaithersburg, 1990.
6. Weiner M. Efficient DES key search: Technical Report TR-244, School of Computer Science, Carleton University, 1994.
7. Odlyzko A.M. The Future of Integer Factorization. Cryptobytes, RSA Laboratories.- vol. 1, N 2, 1995, p. 5 - 12.
8. Rogaway P. The security of DESX. Cryptobytes, RSA Laboratories, vol. 2, N 2, 1996, p. 8 - 11.
9. Kaliski B., Robshaw M. Multiple encryption: weighing security and performance. //Dr. Dobb's Journal, January 1996, p. 123 - 127.
10. Rivest R.L. The RC5 Encryption Algorithm. Cryptobytes, RSA Laboratories, vol. 1, N 1, 1995, p. 9 - 11.
11. Kaliski B., Yiqun Lisa Yin. On the Security of the RC5 Algorithm. Cryptobytes, RSA Laboratories, vol. 1, N 2, 1995, p. 12.
12. Oleinik V. Cycles in the algorithm for cryptographic data conversion GOST 28147-89. http://www.dekart.ru
13. Andrey Vinokurov. GOST 28147-89 encryption algorithm, its use and implementation for computers on the Intel x86 platform.
14. What is Blowfish? http://www.halyava.ru/aaalexey/CryptFAQ.html.
15. Linn J. Privacy Enhancement for Internet Electronic Mail: Part I: Message Encryption and Authentication Procedures. RFC 1421, 1993.
16. Evtushenko Vladimir. Triple DES. New standard? http://www.bgs.ru/russian/security05.html.
17. What is GOST28147-89? http://www.halyava.ru/aaalexey/GOST.html.
18. Andrew Jelly. /Cryptographic standard in the new millennium/, http://www.baltics.ru/~andrew/AES_Crypto.html.
19. Rijndael encryption algorithm. http://www.stophack.ru/spec/rijndael.shtml.

To exchange messages and hide content from third parties, encryption is used. It is used where an increased level of protection is required. There are two encryption schemes: symmetric and asymmetric.

What is encryption

Encryption will be useful when you need to hide some information from unauthorized persons and provide sensitive data to authorized users.

A feature of this type of data transfer is the use of a key.

There are three security states:

• hiding information from strangers;
• preventing change;
• maintaining the integrity of information;
• sender identification.

To read information other than the key, a decoder is required. This is what ensures that it is impossible for attackers to obtain data, because if they intercept the data but do not have the key, it is impossible to read it.

There are two types of encryption: symmetric and asymmetric.

The main purpose of encryption is to store information. This allows you to work with some data from unreliable sources and transmit messages over unsecured channels. Sending information happens like this:

• the sender encrypts the data;
• the recipient decrypts.

Each transformation is implemented using algorithms that use keys to solve them. Symmetric and asymmetric encryption methods are distinguished by their cryptographic strength.

Cryptographic strength

Symmetric and asymmetric encryption systems have a characteristic that makes it difficult to gain unauthorized access.

There are 2 main types of cryptographic strength of an encryption system.

1. A completely resistant system cannot be compromised, even with infinitely large computing resources. It is characterized by the fact that for each message its own separate key is generated. Its length is equal to or greater than the message length.
2. Sufficiently strong systems are used in cryptographic systems for civilian purposes. Such an algorithm is difficult to decipher, but with the appropriate resources it becomes possible.

Comparison of the cryptographic strength of some encryption systems

The maximum RSA key size is 4096 bits.

It is used for encryption and signing. The cryptographic strength can be described as 2.7.1028 for a 1300 Bit key. The scheme is used in many standards; the RSA encryption principle is one of the first asymmetric algorithms.

The key size of the ElGamal scheme is equal to RSA - 4096 Bits. It is used for both encryption and digital signing. The cryptographic strength of this system is no different from RSA with the same key size.

The DSA method uses a much smaller key - 1024 bits. It is used exclusively for digital signatures.

Symmetric and asymmetric encryption

These two types of encryption differ in the number of keys and the level of resistance to hacking.

If one key is used for encoding and decoding, then the encryption is symmetric. Asymmetric encryption involves using one key for each algorithm.

1. A public key encrypts a certain code that represents a specific message. The key is known to both parties, it is transmitted over an unsecured channel, and can be intercepted. The most important task of storing information is to protect the key from interception.
2. The private one is used for decryption. Known only to one side. It cannot be intercepted, since it is always with one interlocutor.

The purpose of encryption determines the method for maintaining confidentiality. One of the first was symmetric encryption; asymmetric encryption was invented later to provide greater security.

Features of symmetric encryption

The symmetrical protection system has the following advantages.

The disadvantages include the following:

• complexity of key management in a large network;
• complexity of key exchange;
• the need to find a reliable channel for transmitting the key to the parties;
• impossibility of using digital signatures and certificates.

To compensate for the shortcomings, a combined scheme is used, in which the key used for decryption is transmitted using asymmetric encryption. It is transmitted using symmetric encryption.

Features of asymmetric encryption

Using a public-private key pair can be used as:

• independent means of information security;
• key distribution facility;
• user authentication means.

Has the following advantages:

• storing the secret key in a safe place, instead of which the open key is transmitted over the open channel;
• the decryption key is known only to one party;
• in a large asymmetric system, use fewer keys than in a symmetric system.

It is difficult to make any changes in such algorithms. Such a system has long keys. If the symmetric key is 128 Bits, then the RSA key is 2304 Bits. Because of this, the decryption speed suffers - it is 2-3 times slower. Decryption requires large computing resources.

There are many examples of symmetric and asymmetric encryption systems.

Symmetric encryption - what does it look like?

An example of symmetric encryption and implementation diagram is below.

1. There are two interlocutors who plan to exchange confidential information.
2. The first interlocutor generates a key d, encryption algorithms E and decryption D. Then he sends this information to the second interlocutor.
3. The message is decrypted with key d.

The main disadvantage is the inability to establish the authenticity of the text. If the key is intercepted, the attacker will decrypt the secret information.

There are classical methods.

1. Simple and double permutation.
2. Magic square.
3. Single permutation.

The first method is one of the simplest, the scheme of which does not use a key. The sender and receiver agree on some key, represented as a table size. The transmitted message is written to the columns of the table, but is read row by row. Knowing the size of the table, the recipient decrypts the message.

To ensure greater secrecy, a double rearrangement is used. In this way, the previously encrypted text is encrypted. To do this, the tables must differ in the number of rows and columns. They are filled vertically, horizontally, in a snake, in a spiral. This method does not strengthen the encryption, but the hacking process becomes longer.

“Magic square” is a more complex structure that is a matrix. Natural numbers are entered into the cells in such a way that the sum of the numbers in each column, row, and diagonal is the same. Each number corresponds to a letter of the message. The resulting text is written into a line, matching numbers and symbols.

Examples of asymmetric encryption

In this case, the public key is sent over an open channel and could theoretically be intercepted by attackers.

Unlike symmetric ones, asymmetric encryption keys are different. A public key is used for encryption, and a private key is used to decrypt the message. Using two keys solves the problem of eavesdropping that was present in the symmetric method. It is implemented like this.

1. The first interlocutor selects encryption and decryption algorithms and a pair of keys. The public key is sent to the second interlocutor.
2. The second interlocutor encrypts the information using the received key. Sends information to the first interlocutor, who decrypts the message using the private key.

There are such basic methods of asynchronous encryption.

1. ElGamal code.

RSA

RSA is the first cryptographic algorithm used for both encryption and digital signature.

It is described like this.

1. Two prime numbers are selected, for example, 3 and 7.
2. The module n is calculated - the product of two numbers. That turns out to be 21.
3. The Euler function φ=(p-1)×(q-1)=2×6=12 is calculated.
4. Any prime number e less than φ and prime with φ are calculated. Available options: 5, 7, 11.

A pair of numbers e, n (5, 21) is a public key. Now the numbers d and n of the private key are calculated. The number d satisfies the condition (d×e) mod φ=1 and is equal to 17. As a result, the second pair of numbers 17 and 21 is the private key. Encryption is performed as follows: the message is raised to the power of e, the remainder of division by n is taken, and the result must be less than the number n. It turns out 10 - this will be encoded data. To decode, e is raised to the power d, and the remainder of division by n is calculated.

DSA

DSA (unlike RSA) is used only for digital signing, not encryption. A given signature can be publicly verified. There are two algorithms for signature creation and verification. It is the hash message that represents the text in digital form that is encrypted. Therefore, a complex hash function is chosen to avoid collisions. Building a digital signature consists of the following steps.

1. Selecting a cryptographic hash function H(x).
2. The bit size of the prime number q must be equal to the hash function value H(x).
3. Selecting a prime number p such that p-1 is divisible by q without a remainder.
4. Calculation of the number g = h (p-1)/q mod p. h must be an arbitrary number in the range from 1 to p-1.
5. A random number k from 0 to q is selected.
6. Calculate r = (g k mod p) mod q.
7. Then s = k-1(H(m) + xr)) mod q .
8. If r=0 or s=0, another number k is chosen.

El Gamal scheme

ElGamal encryption is used for digital signatures. It is a continuation of the Diffie-Hellman algorithm.

When working according to this scheme, it is important to take into account the following feature. ElGamal encryption is not a digital signature algorithm based on the scheme of the same name. When encrypting, the text is converted into a cipher that is 2 times longer than the original message.

Key generation occurs as follows.

1. A random prime number p is selected.
2. The number g must be the primitive root of p.
3. The number x must be greater than 1 and less than p-1. This will be the private key.
4. Then the public key y is calculated using the formula g^x mod p .

When encrypting text M, the system key K is selected. It is greater than one and less than p-1. Then the numbers a and b are calculated, which are the ciphertext, a = g^k mod p and b = y^k M mod p .

Classical or single-key cryptography relies on the use of symmetric encryption algorithms, in which encryption and decryption differ only in the order of execution and the direction of some steps. These algorithms use the same secret element (the key), and the second action (decryption) is a simple reversal of the first (encryption). Therefore, usually each of the exchange participants can both encrypt and decrypt the message. The schematic structure of such a system is shown in Fig. 2.1.

Rice. 2.1.

On the sending side there is a message source and a key source. The key source selects a specific key K among all possible keys of a given system. This key K is transmitted in some way to the receiving party, and it is assumed that it cannot be intercepted, for example, the key is transmitted by a special courier (therefore symmetric encryption also called encryption with private key). The message source generates some message M, which is then encrypted using the selected key. As a result of the encryption procedure, an encrypted message E (also called a cryptogram) is obtained. Next, the cryptogram E is transmitted over the communication channel. Since the communication channel is open, unprotected, for example, a radio channel or a computer network, the transmitted message can be intercepted by the enemy. On the receiving side, the cryptogram E is decrypted using the key and the original message M is received.

If M is a message, K is a key, and E is an encrypted message, then we can write

that is, the encrypted message E is some function of the original message M and the key K. The encryption method or algorithm used in a cryptographic system determines the function f in the above formula.

Due to the great redundancy of natural languages, it is extremely difficult to make a meaningful change directly into an encrypted message, so classical cryptography also provides protection against the imposition of false data. If natural redundancy is not enough to reliably protect a message from modification, redundancy can be artificially increased by adding a special control combination to the message, called imitation insertion.

There are different methods of encryption with a private key (Fig. 2.2. In practice, permutation and substitution algorithms, as well as combined methods, are often used.

Rice. 2.2.

In permutation methods, the characters in the source text are swapped with each other according to a certain rule. In replacement (or substitution) methods, plaintext characters are replaced with some ciphertext equivalent. To improve the security of encryption, text encrypted using one method can be encrypted again using another method. In this case, a combination or composition cipher is obtained. Block or stream symmetric ciphers currently used in practice are also classified as combined ciphers, since they use several operations to encrypt a message. “Principles of constructing block ciphers with a private key”, “DES and AES encryption algorithms”, “Algorithm for cryptographic data conversion GOST 28147-89”, and this lecture discusses substitution and permutation ciphers used by humans since ancient times. We should become familiar with these ciphers because substitution and permutation are used as compound operations in modern block ciphers.

We've released a new book, Social Media Content Marketing: How to Get Inside Your Followers' Heads and Make Them Fall in Love with Your Brand.

Subscribe

HTTP is what allows data to be transferred. Initially, it was created for sending and receiving documents containing links inside to make the transition to third-party resources.

The abbreviation reads “HyperText Transfer Protocol,” which translated means “transfer protocol.” HTTP belongs to the application layer group based on the specifics used by OSI.

To better understand what HTTP means, let's look at a simple analogy. Let's imagine that you are communicating with a foreigner on a social network. He sends you a message in English, you receive it. But you cannot understand the content because you do not speak the language well. To decipher the message, use a dictionary. Having understood the essence, you answer the foreigner in Russian and send the answer. The foreigner receives the answer and, with the help of a translator, deciphers the message. To simplify the whole mechanism, the Internet protocols HTTP perform the function of a translator. With their help, the browser can translate the encrypted content of web pages and display their content.

What is HTTP for?

The HTTP protocol is used to exchange information using a client-server model. The client composes and transmits a request to the server, then the server processes and analyzes it, after which a response is created and sent to the user. At the end of this process, the client issues a new command, and everything is repeated.

Thus, the HTTP protocol allows you to exchange information between various user applications and special web servers, as well as connect to web resources (usually browsers). Today, the described protocol ensures the operation of the entire network. The HTTP data transfer protocol is also used to transfer information over other lower-level protocols, for example, WebDAV or SOAP. In this case, the protocol is a means of transportation. Many programs also rely on HTTP as the primary tool for exchanging information. Data is presented in various formats, for example, JSON or XML.

HTTP is a protocol for exchanging information over an IP/TCP connection. Typically, the server uses TCP port 80 for this purpose. If the port is not specified, the client software will use TCP type port 80 by default. In some cases, other ports may be used.

The HTTP protocol uses a symmetric encryption scheme and uses symmetric cryptosystems. Symmetric cryptosystems involve the use of the same key to encrypt and decrypt information.

What is the difference between HTTP and HTTPS

The difference can be detected even from the decoding of abbreviations. HTTPS stands for Hypertext Transfer Protocol Security. Thus, HTTP is an independent protocol, and HTTPS is an extension to protect it. HTTP transmits information unprotected, while HTTPS provides cryptographic protection. This is especially true for resources with responsible authorization. These could be social networks or payment system sites.

What are the dangers of transmitting unprotected data? An interceptor program can transfer them to attackers at any time. HTTPS has a complex technical organization, which allows you to reliably protect information and eliminate the possibility of unauthorized access to it. The difference lies in the ports. HTTPS typically works on port 443.

Thus, HTTP is used for data transfer, and HTTPS allows for secure data transfer using encryption and authorization on resources with a high level of security.

Additional functionality

HTTP is rich in functionality and is compatible with various extensions. The 1.1 specification used today allows the Upgrade header to be used to switch and work through other protocols when exchanging data. To do this, the user must send a request to the server with this header. If the server needs to switch to a specific exchange using a different protocol, it returns a request to the client, which displays the status “426 Upgrade Required”.

This feature is especially relevant for exchanging information via WebSocket (has the RFC 6455 specification, allowing you to exchange data at any time, without unnecessary HTTP requests). To migrate to WebSocket, one user sends a request with the Upgrade header and the value “websocket”. Next, the server responds with “101 Switching Protocols.” After this moment, information transfer via WebSocket begins.

Few people know exactly how asymmetric encryption works. For example, there are people who do not consider the https protocol to be any adequate protection for transmitted data. And as a rule, when trying to convince them otherwise, they respond with something along the lines of “if we transmit encrypted data, then we must say how to decrypt it, and this information can be intercepted and, therefore, the data can be decrypted.” And to the arguments that this is not so and that asymmetric encryption is the basis, the answer is “So what?”

Okay, I understand that not everyone needs to know all the intricacies of implementing asymmetric encryption. But I think everyone who has anything to do with computers should know the general principle of operation.

I would like to summarize the essence of this post in this annotation: Remember, asymmetric encryption is secure, of course, if all conditions are met. And to prove this, I will try to describe the algorithm in understandable language so that everyone can understand that it is safe. Meet Alice, Bob and Eve and the transmission of their secret message under the cut.

By the way, why Alice and Bob? There is a short article about this on Wikipedia: Alice, Bob and Eve. To make it clearer, Alice and Bob want to exchange messages, and Eve is trying to intercept and read these messages.

A little history

Cryptography of past centuries had one huge problem - the problem of key transfer. At that time, there were only so-called “symmetric” ciphers - ciphers in which data is encrypted and decrypted with the same key.

For example, Alice encrypted some message and wants to send it to Bob. Naturally, for Bob to read it, he needs the key with which the message was encrypted. And then the problem arises of how to transfer the key so that no one can intercept it. Inquisitive minds will make an offer - let them pass it on in person, and then communicate as much as they want. Yes, I don’t argue, it’s a way out. Now imagine for a second that your Internet mail, before you log in to it, will require you to travel to the physical location of the mail server. Comfortable? Perhaps not very much.

Of course, the key can be transmitted over another communication channel. But cryptography considers all unsecured communication channels as insecure. That is, transferring the key to Bob over the phone, for example, is considered unsafe, just as nothing prevents Eve from listening to the phone as well.

Until the 70s, this problem became so commonplace that it was considered an axiom that in order to transmit a message you need to transmit the key with which the message is encrypted (and some people still think this way). But in 1976, Diffie and Hellman proposed their “exponential key exchange method.” Since these years, the development of asymmetric cryptosystems began.

A little bit of real life

Before studying any algorithm, you need to imagine how it works. And the easiest way is to compare it with how something works in reality.

Let's imagine that Alice and Bob live in a country where the entire postal system is completely immoral and postal employees read all unsecured mail. Alice, a not stupid girl, before sending a message to Bob, took an iron box and, putting the letter inside and closing it with her lock, sent this box to Bob.

Naturally, the post office cannot read this letter, but Bob himself cannot read it, since he does not have the key with which the lock is closed. Alice, of course, can take another iron box, put the key from the previous one in it, and send it to Bob, but Bob will not be able to open it either...

The only way is to make a duplicate key and give it to Bob in person...

And so it begins to seem that key exchange is an inevitable part of encryption - or is it not?

Let's imagine a different picture. I'll write it down step by step:

1. Alice puts her letter in an iron box and, locking it, sends it to Bob.
2. When Bob receives the box, (attention!) he takes his lock and, having additionally locked the box with it, sends it back.
3. Alice already receives the box with two locks (let me remind you, Alice’s first lock, for which she has the key, and Bob’s second, for which only Bob has the key).
4. Alice removes her lock and sends the box back to Bob
5. Bob receives a box with one of his locks for which he has a key
6. Bob unlocks his remaining lock with his key and reads the message

The significance of this short story is enormous. It shows that two people can transmit a secret message without exchanging keys. Think about it! This story actually destroys all the axioms on which the cryptography of that time was built. Yes, we get some complication of the process (the box had to be sent three times), but the result...

Let's get back to cryptography

It would seem that a solution has been found. The sender and receiver encrypt their message, and then the interlocutors take turns deciphering theirs.


But the point is that there are no ciphers that would allow one to remove a cipher from another cipher. That is, the stage where Alice removes her cipher is impossible:


Unfortunately, all existing algorithms still require the removal of ciphers in the queue in which they were applied. I’m afraid to call this an axiom (since history already knows cases when such axioms were shattered to smithereens), but this is still the case.

Let's get back to math

The box idea I described above inspired Diffie and Hellman to look for a way to convey a message. Eventually they ended up using one-way functions.

What is a one-way function? For example, there is a doubling function, i.e. double(4)=8, it is two-sided, because from result 8 it is easy to obtain the initial value 4. A one-way function is a function after applying which it is almost impossible to obtain the initial value. For example, mixing yellow and blue paint is an example of a one-way function. Mix them up easily, but to get the original components back - impossible. One such function in mathematics is modulo calculation.

As a basis for the algorithm, Hellman proposed the function Y x (mod P). The inverse transformation for such a function is very difficult, and we can say that, in essence, it consists of a complete enumeration of the original values.

For example, you were told that 5 x (mod 7) = 2, try to find x, A? Found it? Now imagine that numbers on the order of 10,300 are taken as Y and P.

By the way, to increase durability, the number P must be a prime number, and Y- be a primitive root modulo P. But since we are still trying to understand the theory, I don’t see the point in bothering with this.

Diffie-Hellman algorithm

And then one day it dawned on Hellman and he was able to develop a working key exchange algorithm. This algorithm requires steps on both sides to work, so I'll put it in a table:

	Alice	Bean
Stage 1	Both participants agree on meanings Y And P for a general one-way function. This information is not secret. Let's say the values ​​were selected 7 And 11 . The general function would look like this: 7 x (mod 11)
Stage 2	Alice chooses a random number, for example 3 A	Bob chooses a random number, for example 6 , keeps it secret, let's denote it as a number B
Stage 3	Alice substitutes the number A 7 3 (mod 11)= 343 (mod 11) = 2 a	Bob plugs in the number B into a general function and calculates the result 7 6 (mod 11)= 117649 (mod 11) = 4 , denotes the result of this calculation as a number b
Stage 4	Alice passes the number a Bob	Bob passes the number b Alice
Stage 5	Alice gets b from Bob, and calculates the value b A (mod 11)= 4 3 (mod 11) = 64 (mod 11) = 9	Bob gets a from Alice, and calculates the value a B (mod 11)= 2 6 (mod 11) = 64 (mod 11) = 9
Stage 6	Both participants ended up with a number 9 . This will be the key.

Magic? I don’t argue, it’s not clear at first glance. But after reading and thinking about this table, it becomes clear how it works. However, if it is not clear, then scroll to the end of the chapter, where I posted an explanatory video.

Moreover, please note that to obtain the key in the final formula, any person needs to have three values:

• Values a And P, and Bob's secret number B
• or meanings b And P, and Alice's secret number A

But secret numbers are not transmitted over the channel! Eve won't be able to recover the key without someone's secret number. Why - I wrote above, this function is one-way. Try solving the equation 4 x (mod 11) = 2 y (mod 11) having found x And y.

To make it clearer how the Hellman scheme works, imagine a cipher that somehow uses color as a key:

Let's first assume that everyone, including Alice, Bob and Eve, has a three-liter jar into which one liter of yellow paint is poured. If Alice and Bob want to agree on a secret key, they each add one liter of their own secret paint to their jars.

Alice can add purple paint, and Bob can add crimson. After that, each of them sends his jar with the mixed contents to the other.

Finally, Alice takes Bob's mixture and adds one liter of her secret paint to it, and Bob takes Alice's mixture and adds one liter of his secret paint to it. The paint in both cans will now be the same color, since each can contains one liter of yellow, purple and crimson paint.

It is this color, obtained by adding twice to the paint jars, that will be used as a key. Alice has no idea what kind of paint Bob added, and Bob also has no idea what kind of paint Alice poured, but they both achieved the same result.

Meanwhile, Eve is furious. Even if she were able to intercept the jars containing the intermediate product, she would not be able to determine the final color, which would be the agreed upon key. Eve can see the color of the paint obtained by mixing the yellow paint and Alice's secret paint in the jar sent to Bob, and she can see the color of the paint obtained by mixing the yellow paint and Bob's secret paint in the jar sent to Alice, but to find the key, she, in fact, it is necessary to know the colors of Alice and Bob's original secret paints. However, by looking at the jars of mixed paints, Eve will not be able to identify Alice and Bob's secret colors. Even if she takes a sample of one of the mixed paints, she will not be able to separate it into the original paints to find the secret one, since mixing paint is a one-way function.

Still not clear? Then watch the video:

Well, I hope you understand that there is a very real way to exchange keys securely. But please note that it is not yet possible to call this algorithm an asymmetric cipher, since in essence it is just a key exchange algorithm.

Asymmetric encryption

The asymmetric algorithm assumes the presence of two keys - public and private. That is, the message is encrypted with a public key and decrypted with a private key and nothing else. Actually, it was this concept that Diffie formulated.

In general, the essence of this algorithm is that the receiving side, before receiving the message, generates a pair of keys based on the modular arithmetic algorithm (the principle is the same as in the Diffie-Hellman algorithm), the actual private and public key. Before sending, the sender receives a public key and encrypts the message with this key, after which this message can only be decrypted with a private key, which is kept secret by the receiving party.


If we return to the analogy with locks, then public key encryption can be thought of as follows:

Anyone can lock a lock by simply clicking it until it closes, but only someone who has the key can unlock it. Locking a lock (encryption) is easy, almost everyone can do it, but only the owner of the key can open it (decryption). Understanding how to latch a lock so it closes won't tell you how to unlock it.

A deeper analogy can be drawn.

Imagine that Alice is designing a lock and key. She vigilantly guards the key, but at the same time makes thousands of duplicate locks and sends them to post offices around the world. If Bob wants to send a message, he puts it in a box, goes to the local post office, asks for an "Alice lock" and locks the box with it. Now he will no longer be able to open the box, but when Alice receives the box, she will be able to open it with her only key.

Putting a lock and clicking it to close is equivalent to a shared key for encryption, since everyone has access to the locks and everyone can use the lock to lock the message in the box. The key to the lock is equivalent to the secret decryption key because only Alice has it, only she can open the lock, and only she can access the message in the box.

There are several algorithms that implement asymmetric encryption. The most famous of them is RSA. I don’t see the point in describing it, since I still won’t be able to understand how it works right away, and I still won’t be able to write it better than what’s written on Wikipedia.

Conclusion

Well, I hope that once you understand how asymmetric encryption works from the inside, you will begin to trust it more and, accordingly, use SSL more often =)

Materials were used from the book Singh Simon - Book of Codes. By the way, the best book for those who want to understand at least a little about cryptography. I advise everyone to read it.

1. tv

   Selecting such a key will take you a lot of time. Little more than the universe exists. Even on very powerful computers.

2. Igor

   What is this nonsense with public keys for? Symmetrical ones are more reliable.
   Good afternoon
   Good site, the material is clearly presented, many thanks to the author. I came here by accident in September, when I was looking for information on practical encryption.
   I am writing because I want to ask: Anyone want to know how to find numbers for symmetric encryption? I can teach you how to quickly check the number P for primality (without searching for the number g) - but this is unlikely to be interesting. The most interesting:
   Find the number P of any length and the number g to it. I don’t use any 2 to the power of n plus one (or minus one). Naturally, it's free. There is even a website where I posted my work.

Uasya Petrovich

I understand that a lot of time has passed, but I will still answer for new readers like me.

This won't work because... after actions 2 and 3 we see the difference by which the number of each of the blocks has changed, therefore Bob’s secret number becomes obvious to us and we can only intercept the message after the 4th action (i.e. without Alice’s cipher) and use what is already known to us Bob's number.

Eugene

Thank you so much for the article!
After reading, almost everything fell into place on its own shelves and acquired a structure that was easy to expand upon.
Having such a structure, it is easy to generate the right questions (MiTM attack shelf, special thanks to Mikhail :)).

From a pedagogical point of view, you did everything perfectly. I think you are right that you did not add MiTM attacks to this article, otherwise there would have been information overload.

The video is adorable, especially considering its age.

PS: the use of metaphors to explain “complex” systems is frankly difficult to overestimate. Thanks again!

dbzix

From this article I did not catch the moment of transition from the Diffie-Hellman algorithm, where two subscribers exchange public data and intermediate results of calculations to obtain a secret key (in the example there were as many as 6 stages) to the stage where a certain public key is used for encryption, which is then decrypted using a private one (I count here only 2 stages of data transfer - sending a public key and sending a message encrypted with this key).
Those. I understand that somewhere between these two explanations there is probably a lot of mathematics hidden, and in the end the explanation boils down to “this is how it works, just trust me.” But it would probably be easier to understand this sudden transition if the analogy with paints were extended to explain the essence of encryption with a public key followed by decryption with a private one. In the meantime, it turns out that “B works because A,” while there is no clear connection between A and B. At least for me.
Dear author, would you be so kind as to explain to me this mystical jump from A to B? :) Thank you!

Eugene

Good afternoon,

Given: there is a formula Y^x (mod P).
the example in the article is based on the formula 7^x (mod 11)

I took 4^x (mod 7) for my example
and I couldn’t come up with a common key.
Question: why does the algorithm in the example work for 7^x (mod 11) and not for 4^x (mod 7)?

Jessi-jane

Andrey

Thank you, great article!
Only now I almost figured out the algorithm, how to calculate through the module.
Could you tell me how to calculate the number B if the number A is less than the modulus?
Well, for example:
3(mod 13) = ?

I know that if, for example, you need to calculate 625(mod 13), you need 625/13, and then multiply the largest possible integer divisor (48) by the modulus (which here will be equal to 624), and finally 625-624 = 1
The numbers 625 and 1 are comparable modulo 13, since 624 is divisible by 13.
This is what I understand. But what if the module is greater than the number a?

Yellow Horror

1. Man-in-the-middle attack is a serious problem. As far as I can tell, within the framework of cryptography alone, this problem cannot be solved in principle: if we accept that Eve is capable of intercepting and imperceptibly replacing ALL data coming to Alice or emanating from her via ANY communication channels, no encryption will help. At least one certificate must be obtained by Alice from a completely reliable source. But if an attacker can only listen to the communication channel and not change the data in it, asymmetric encryption is quite reliable.
2. As for the ability to remove one “cipher layer” from under another, the banal XOR function, widely used in cryptography from ancient times to this day, has this property. I don't think it can be patented :(

1. Dmitry Amirov Author

   Yes, you are right, the mitm attack today cannot be solved in any way if you are absolutely paranoid. If they are not, then fiddling with certificates and signatures will provide “necessary and sufficient” protection.

   As for the XOR function, it can hardly be called a cipher, because it is not one in its essence.

   1. Yellow Horror

      Come on? Google the Vernam Cipher. This is a messaging system with absolute crypto-resistant. And it is based precisely on XOR. Leaving aside some organizational difficulties (creating truly random keys with uniform distribution, maintaining the secrecy of the encryption pad in an unfriendly environment, and securely destroying used keys), humanity has not yet come up with anything simpler and more reliable.

   2. Yellow Horror

      Although, upon reasonable reflection, I realized that the double reversible encryption method does not work if the attacker knows the encryption algorithm. Let's look at Mikhail's ideas as an example:

      1. We break the encrypted information into blocks. Each block is represented by a number. The block size (number of bits) determines the number of possible block values ​​and (accordingly?) the strength of the encryption.
      2. To encrypt the message, Alice selects a secret number (which she does not send to anyone), which she adds to each of the numbers in the blocks and sends the message encrypted in this way to Bob.

      So far so good: Eve can't read Alice's message because... does not know the key number. If the blocks are large enough, it is difficult to recover Alice’s message, but if the block is longer than the message and the key does not have vulnerabilities, it is impossible. But Eve can and does copy Alice's ciphergram.

      3. Bob receives the encrypted message, chooses his secret number (which he also does not send to anyone), adds this number to each of the numbers in the blocks of the message encrypted by Alice, and sends this double-encrypted message to Alice.

      And here the problems begin: Eve still cannot read Alice’s message, but, having a copy of the ciphergram received by Bob and the double encryption sent by him, she can easily restore key Boba.

      4. Alice subtracts her secret number from each number in the blocks of this double-encrypted message and sends the resulting message to Bob.

      Alice has removed her “layer” of cipher and now sends Bob her letter, encrypted only with Bob’s key. Which Eva already has! Eve decrypts the letter and reads it, and, just in case, can recover Alice’s key using the decrypted text of the letter and the first ciphergram she intercepted.

Dmitriy

Hello. Good article, but I also did not understand some of the points described above.
It is the transition from the algorithm for obtaining a secret key by both interlocutors (Alice and Bob) (without putting them into public access) to asymmetric encryption.
You write that the message is encrypted on Alice's side with the public key received from Bob. But if we encrypt with a public key, then Eve can easily get it and decrypt it herself, right?
It still remains unclear to me how you can encrypt with a public key and decrypt only secret on Bob's side. That is, they encrypted it with the word “Home”, and deciphered it with the word “World”. For me this is some kind of nonsense.
Based on these obvious gaps (either yours or mine), I concluded that the circuit here must be more complicated than in the picture. Most likely, the arrow from Bob’s public key to Alice means something else, namely the entire sequence of actions to obtain “Y” and “P”, obtain intermediate results, etc. In other words, I think that when the original message is encrypted with a supposedly public key, it is actually encrypted not with a public key, but with a secret one, which is calculated on each side separately.

I also had a question about decrypting a double-encrypted message. If we take, say, the Caesar cipher, where each letter is encrypted with another letter, standing, say, 3 positions further. If Alice encrypts the letter A in the message with the letter B, and then Bob encrypts this letter B with the letter G, then it will be easy to obtain the letter A from G, and in any order. True, this will most likely work only in cases where both know the encryption type of the interlocutor and with fairly simple encryption types (monoalphabetic/polyalphabetic). I'm also new to cryptography, so this is my opinion ;)

1. Dmitriy

   I forgot to ask.
   What is the difference between symmetrical and asymmetrical methods?
   

   1. Dmitriy

      I read it, more or less somehow grouped everything in my mind.
      I will answer the questions I wrote, perhaps thereby helping other readers.
      1. About

      You write that the message is encrypted on Alice's side with the public key received from Bob. But if we encrypt with a public key, then Eve can easily get it and decrypt it herself, right?
      It also remains unclear to me how it is possible to encrypt with a public key and decrypt only with a secret one on Bob’s side. That is, they encrypted it with the word “Home”, and deciphered it with the word “World”. For me this is some kind of nonsense.

      This article mentions the RSA algorithm. Symmetric encryption algorithm. It actually uses the following algorithm:
      1) Based on a certain one-way encryption function (a function that is easy to calculate in one direction, but very difficult in the other. A) we create a pair on the recipient (public key; private key). This pair is unique, that is, each public key corresponds to a unique private key for this one-way function.
      
      3) The sender encrypts the message
      4) Transfers to the recipient
      

      As you can see, the sender does not know the private key and he is not able to decrypt his own encrypted message. That's why it's called asymmetric, because one has all the keys, and the other only has the part needed for encryption.

      What is the difference between symmetrical and asymmetrical methods?
      If I used the Diffie and Hellman algorithm to transmit the secret key, and then was able to securely transmit the encrypted message, would this method be symmetric?

      The Daffy-Hellman algorithm, which serves for key exchange and further symmetric encryption. That is, its essence is that first both receive the full key for encryption and decryption and then begin the most common symmetric encryption.

      Asymmetric method - one node has all the information for encryption/decryption, and the other, as a rule, only for encryption

      Symmetric - both nodes know all the information for encryption/decryption.

      I hope I helped someone;3

      1. Dmitriy

         This article mentions the RSA algorithm. Asymmetric encryption algorithm I sealed it.

      2. Dmitry Amirov Author

         Hmm... just now noticed your comments. My apologies.

         Everything seems to be correct. There is one thing about your last paragraph, specifically the terms:

         • Daffy-Hellman algorithm- is an algorithm that allows you to obtain one shared secret key and nothing more
         • Asymmetric/symmetric encryption- in general, everything is correct with you
         • RSA- an algorithm that is a combination of these things. On your fingers: using asymmetric encryption using the Deffie-Helman protocol, a secret key is established with the help of which messages between interlocutors are encrypted using the symmetric encryption method.
      3. Dmitriy

         I still didn't understand the statement:
         2) The public key is transferred to the sender.
         3) The sender encrypts the message
         4) Transfers to the recipient
         5) The recipient decrypts using the private key. This message cannot be decrypted using the public key.

         It turns out that you had in mind from the very beginning. We encrypt with the word Home, and decrypt with the word World. Does this mean that there is another algorithm connecting the World and the Home with each other?

Robert

Thanks a lot!!!

Novel

Thank you. I finally decided to figure out how it works and learned from this article. Only, I think, if the accomplices know each other and there is an opportunity to safely exchange public keys, then it’s worth doing. To eliminate the detrimental impact of the possible appearance of a person in the middle when exchanging keys, who will pretend to be A as B and B as A, replacing the keys with their own and ultimately viewing all the information.

And in the video, I think it’s in vain that they use this 3^(24*54), because It’s not at all obvious where it came from, or they would explain that it’s conditional.

RinswinD

Thank you for the article. Everything is explained very clearly.

grigory

Well, this illiteracy of spelling irritates everyone - “one-sided”, “applied”, “long”, as if in the 5th grade. And so, not bad for understanding the basics.

grigory

Sometimes the question is simple. Ransomware viruses use a private key. There is an original file, there is an encrypted file. Task: find an algorithm, so to speak, that looks for an algorithm for converting the first file into the second...

Allexys

Thank you for the clear and fun article! Finally I got the hang of the basics :).

Yaroslav

Unfortunately, all existing algorithms still require the removal of ciphers in the queue in which they were applied.

This is not entirely true. I'll give you an example:
— suppose that each letter corresponds to a digital code A = 1, B = 2, C = 3, etc.;
— suppose that Alice sends Bob a letter consisting of a single letter A (to simplify the example);

Alice: puts her cipher A + 2 = B

Bob: puts his cipher B + 3 = E
Bob: sends a letter to Alice
Alice: removes her cipher E - 2 = G
Alice: sends a letter to Bob
Bob: removes his cipher G - 3 = A

Here the number 2 is Alice's secret key, 3 is Bob's secret key. Moreover, it may not be one-character. In principle, its length is unlimited.

Dmitriy

For a long time I avoided the theoretical foundations of asymmetric encryption. I knew superficially - there is a public key with which the data is encrypted, and there is a private key with which the data is decrypted. But the thought of implementing such encryption has always bothered me.
Your article helped a lot, thank you very much for that!
Only towards the end of it did I see this nonsense again - “encrypted with a public key.” After all, strictly speaking, the message is encrypted not with a public key, but with a key obtained based on the sender’s private key and the recipient’s public key (which, in turn, was generated based on the recipient’s private key). Indeed, in the table about Alice and Bob - they and only they were able to obtain the same key “9” - it is used to encrypt and decrypt the message. But this key can only be obtained based on a pair of keys - secret (Alice/Bob) and public (Bob/Alice).
Figuratively - yes, the message is always encrypted with the sender’s secret key (it is, roughly speaking, constant) and the recipient’s public key (it depends on the specific recipient), therefore, in the description, encryption with the “secret” key is omitted - and this omission breaks the whole order of reasoning.

Clarkson

I read the article and didn’t understand it very well, although it was better than on the wiki. But there’s just one thing I don’t understand. If anyone can answer correctly, please help.

if I send everyone the question “how much is 2+2?”, I tell them how to encrypt the answer to me (I tell everyone the public key), and everyone will send me an answer to the question, how do I find out who exactly I’m waiting for an answer from, that is, who with whom Did I really want to make a connection?

1. Dmitry Amirov Author

   Here you are asking the question a little wrong.

   If you need to establish a connection with someone, then you need to go from the opposite direction. You connect to your interlocutor, and already he will tell you provides your public key, not you.

   UPD: wrote an article about, I think this will be the correct answer to your question.

   1. Clarkson

      I'll have to fight my stupidity. the topic is discussed in the comments and in your article, it seems that everything was explained.

      yet. Why do I need to publish his key? tell me if I don't understand correctly.
      I am the initiator (I need answers, in the example I am the receiving party), which means I generate a pair. it’s him who responds (the sender in your example) who needs my public

      Before sending, the sender receives a public key and encrypts the message with this key, after which this message can only be decrypted with a private key, which is kept secret by the receiving party.

Beshot

I re-read this article and others on the topic several times, but the algorithm for using digital signatures in email is unclear. documents If it’s like this here: https://ru.wikipedia.org/wiki/Electronic_signature, then discrepancies arise. So do we still encrypt using a private key or a public one?

1. Dmitry Amirov Author

   If we sign something, we form the signature based on our private key. And the recipient must have our public key, with the help of it he will be able to decrypt this signature.

   If the signature is “decrypted”, then the public key corresponds to the private key, and since a priori, only the sender has the private key, which means it was the sender who signed the document.

   1. Beshot

      Dmitry, your article helped me a lot, you have a good style. But there is an incomprehensible point: you claim that the asymmetric algorithm assumes the presence of two keys - public and private. That is, the message is encrypted with a public key and decrypted with a private key and nothing else.

      It may be a matter of the original task, for example the recipient needs to authenticate the messenger.
      Then I can’t imagine how this scheme can help?

      1. Dmitry Amirov Author

         That is, the message is encrypted with a public key and decrypted with a private key and nothing else.

         Not entirely true. The message is encrypted with one key and decrypted with another. Those. It is quite possible to encrypt it privately and decrypt it publicly.

         Let's look at an example. You want to send me a message, I want to make sure that it was you who sent it to me. Step by step:
         1) You encrypt the message with the private key
         2) Send it to me
         3) I contact you and receive your public key from you
         4) I decrypt the received message with your public key
         5) If the message is decrypted, it means you were the one who sent it

         No one else can send this message pretending to be you, because only you have the private key.

         1. Beshot

            Ok, but what if you need to hide a message from prying eyes?

Anya

Good afternoon I liked the article, but I still had questions (there were even a couple of similar ones in the comments, but without answers).
If in the second part of the article we move on to the analogy with Alice and Bob, in particular to the numbers A, B, a, b, P and the number 9 obtained in the example, which of them will be the private key and which will be the public key? Thanks in advance for your answer!

1. Anya

   It’s not clear whether my comment was posted or not :(

2. Dmitry Amirov Author

   It would be more correct to say that in the process of exchanging data, Alice and Bob receive a common key 9 , which can later be used to encrypt their messages. In fact, in the article I described not asymmetric encryption itself, but the key exchange protocol, which gave impetus to the development of asymmetric encryption.
   The algorithm for generating a private/public key pair is actually a little more complicated, although it is similar to the algorithm outlined above, but still probably deserves a separate article. I won’t write this out right away in the comments, because I might confuse a lot of things.

Gregory