Asymmetric cryptography is a fundamentally new branch of cryptography dealing with public key cryptoalgorithms, that is, algorithms for electronic signatures, asymmetric encryption and obtaining a shared secret.
The essence
Until 1976, humanity, which already had strong ciphers like Lucifer, faced a serious problem of distributing the keys to such algorithms. To start encrypting, the two parties had to agree on the key to use over another eavesdropping-protected channel, for example, in a face-to-face meeting. This, in principle, is logical, but workarounds have nevertheless been found.
At first, smart people offered various crutches. For example, in the case of a radio exchange, one party could noise the air with a random signal during the transmission of the key by the other party, and then subtract this noise from the received information and calculate the key. An outside observer could not make out which of the sources was emitting noise and which was secret data, and separate them from each other.
But in 1976, Whitfield Diffie and Martin Hellman still erupted with a normal universal solution that allowed starting a secret communication without first knowing the shared key. The only condition is that although the channel could be listened to, it could not be modified. Then, as is the case with any breakthrough invention, many alternatives appeared, arranged on a completely different principle.
Getting a shared key
Among the asymmetric algorithms, there are encryption and electronic signature algorithms, but both of these actions can be performed in a symmetric form if two parties are involved with a shared secret key. It can be used to encrypt with regular AES ciphers or to create an HMAC impersonation.
Merkle's puzzle
Before the invention of the world's first asymmetric algorithm, there were already attempts to assemble something similar based on symmetric circuits. So, an American student - Ralph Merkle (who became a cool cryptographer and invented a lot of things, for example, the Merkle tree used in Bitcoin) in his course described a very simple scheme:
- I create 240 large random numbers and encrypt them all with weak 40-bit keys, adding a bit of redundancy, such as assigning a few zeros to the right of the numbers before encrypting them. The result is several terabytes of selective noise, which I send you by email.
- You completely randomly select any encrypted number from there and brute force it all day on your Radeon. This is easy enough because the key is weak.
- That's it - now you have decrypted this number and will use it as a key to communicate with me, most importantly, do not forget to hint to me which number you have chosen, for example, by sending its hash.
Diffie-Hellman algorithm
The first purebred asymmetric algorithm was invented by two American smart girls in 1976. The ambitious NSA later stated that it knew about such a possibility back in 1966, but no one believed them.
The algorithm is based on a commutative irreversible operation. This operation can be either exponentiation modulo a prime number, or multiplication of a number by a point on an elliptic curve in a finite field. This is very difficult mathematics, but the simplest case - with degrees - is easy to understand.
As you know, a number can be raised to several powers in a different order, and the result will not change: (ab) c = (ac) b. Exponentiation is easy to handle - knowing A = ax, I can compute x = logaA. But it becomes irreversible if you execute it modulo a prime number, that is, after raising to a power, divide the result by this number and take the remainder of the division. For example: 1517 = 98526125335693359375, the remainder of dividing this number by 29 is 18. This is written as 18 = 1517 mod 29. If we imagine that in place of these 15, 17 and 29 there are huge numbers, then knowing 18 = 15x mod 29, you there is no way you can figure out x.
It is noteworthy that the properties of the degrees are preserved when operating modulo, that is, if you first calculate ab mod p, and then raise to the power c modulo the same, the result will be the same as if you calculate it in a different order (ac) b mod p. Well, then you don't need to be a super genius to add a cryptoalgorithm from this (mod is omitted for clarity, but it is implied):
- We choose the base of degree a - this is an unclassified number, it can be published or even sewn into the program.
- I am generating my huge number b and counting B = ab. I publish the big B, while the small b is my secret key.
- You generate your huge number c and consider C = ac. You publish the big C, while the small c is your secret key.
- I take your C and get our shared secret K = Cb from it.
- You take my B and get our shared secret K = Bc from it.
Security
It is worth noting that the inversion of exponentiation modulo or scalar multiplication of a number by a point on an elliptic curve in a finite field - discrete logarithm - is a potentially irreversible operation. Many asymmetric algorithms rely on the belief in the inequality of complexity classes NP and P, which has not yet been proven. This means that one day someone can break such algorithms, and all at once, by solving any NP-complete problem that boils down to all problems from this class. And this beautiful day will surely come when powerful quantum computers appear.
Merkle's puzzle and several other asymmetric algorithms, not like all asymmetric algorithms, are not subject to such a problem, but no one uses them either because they are impractical or because they are poorly understood.
Electronic signature
In addition to algorithms for obtaining a shared secret, there are specialized algorithms designed for signing or encryption, or even for both purposes at once.
An electronic signature is a set of bytes that is associated with a message and can be generated only by the owner of the private key, and verified by anyone who has the public key. The signed document cannot be modified without damaging the electronic signature, therefore it is used for authorization. At the same time, once having signed the document, it will not be possible to renounce the signature in the future - you can sign contracts.
As a rule, it is not the message itself that is signed, but its hash, because the hash length is small enough and always fixed, in contrast to the message length.
Lamport's scheme
Lamport's scheme is the most natural EDS algorithm, but it has a drawback - it can only sign one message.
If I think of two random strings and post their hashes, then that can be considered my public key. With this key, I can sign one bit of information: if it is 0, then I publish the first line, otherwise - the second. Anyone can check the hash of the published string and make sure it matches my public key, that is, the signature was made by me.
The logical continuation of the idea is to publish more than one pair of lines so that you can sign many bits at once. Ralph Merkle made a bunch of improvements to this idea, bringing it to a very practical candy, in particular, he came up with a Merkle tree, which allows you to make more than one signature with one key.
Encryption
There are also special algorithms for encryption. The public key is not a secret and anyone can use it and encrypt the message, but only the owner of the corresponding private key can decrypt the message.
Rabin's scheme
Michael Rabin, widely known in narrow circles (the one who invented the simplicity test used to generate large primes), created a simple asymmetric encryption scheme: c = m2 mod n. The encrypted text is converted into a number, squared, and the final result is the remainder of dividing the square by the public key n.
An extremely important property of such a scheme is its proof - it is reliably known that finding the root modulo is no less difficult than factoring a private key. The same RSA (similar algorithm) can be cracked even without solving the NP-complete problem, which is factorization (and such a cracking was demonstrated for small values of the encryption exponents).
For decryption, you need to know the prime factors (p and q) of the public key n, they are the private key and must also be large enough. For the sake of simplifying decryption using the Chinese remainder theorem, it is recommended to choose p and q so that they lack 1 to divisibility by 4. The procedure itself looks a little brain-fucking, so there is no point in describing it here, you just have to note that the result will be 4 different messages one of which is true. Therefore, it is necessary to add a little redundancy to the message before encryption so that the recipient can determine which version is correct.
Yet
The article describes the simplest algorithms for general understanding, since there are such. It makes no sense to describe here all the algorithms and their technical details - there are books and documentation for this.
There are a great many asymmetric ciphers, and new ones with different interesting properties periodically appear, but RSA, Diffie-Hellman (in HTTPS) and El Gamal derivatives and their elliptical versions (DSA, ECDSA, patriotic bicycle GOST R 34.10-94) are mainly used. They are easy to master by understanding Diffie-Hellman). There are purely academic variants such as Rabin, Shnor, GHR schemes - a more complete list in the English Wikipedia.
The man in the middle
Without a single exception, all asymmetric algorithms are susceptible to a man-in-the-middle attack, and nothing can be done about it.
As mentioned in the introduction, during communication over an unsecured channel, asymmetric ciphers ensure that an eavesdropping attacker cannot find out what the conversation is about. But if he is able not only to listen, but also to intervene, modifying the transmitted information, then he can easily invisibly break into the conversation.
The idea is that at the moment of exchange of public keys, the attacker stops this exchange and gives the parties his own keys. The parties cannot detect this, so in the future they use these fake keys, actually communicating with the attacker, who simply re-encrypts and forwards all messages from one interlocutor to another, so as not to get fired up.
It is worth noting that from an ethical point of view, there is no problem at all. If two people start communicating as anonymous, then we can rightfully assume that each of them communicates with the asshole who intervened in the middle, but where he gets the answers does not matter - he is also anonymous. It's like playing chess over the Internet, transferring all moves to a computer game.
If one of the parties is not anonymous, then the problem of connecting a real person with the keys is completely natural, and one cannot do without help from non-virtual reality. Therefore, to establish a trusted HTTPS connection, certification authorities are needed, which, being legally obligated, will say with their authoritative word that such and such a key really belongs to such and such a bank.
If it is required to establish a connection between a key and some human-readable string (for example, a domain name), then it is also impossible to do without external intervention, since the concept of private ownership of this string is required. But the most modern advanced technologies allow you to solve this without a centralized certifying agent - using a decentralized one.
