cryptography and useless mathematics. part 1

Knowledge of logarithms and integrals helped few people in everyday life. We perfectly calculate the interest on a mortgage or the size of a discount in a store without it.

Perhaps you came across teachers at school who were more consciously able to explain the importance of this science: gymnastics for the brain, broadening your horizons, understanding the mechanics of the world around you, and so on. If you didn’t come across such teachers or you didn’t believe them, we hope we can convince you today. But be careful: there will be mathematics, probably even too much mathematics. But not terrible.

Useless math

The practical usefulness of mathematics is often not obvious in itself. Sometimes it is not obvious even to mathematicians themselves. Take at least number theory: this is a branch of mathematics in which they study the magical interaction of numbers and notice interesting patterns. However, it is absolutely unsuitable for practical use.

Understanding the uselessness of mathematics is impossible without mathematics itself. Therefore, you can either take our word for it, or attempt to figure out the mechanism of action yourself. Let's conditionally call such mathematical or not so mathematical mechanisms black boxes: we will try to explain each of such simple black boxes that fit into the article in an accessible language.

Pierre Fermat was a cunning guy and left behind theorems that other mathematicians had to prove. For example, in the black box of Fermat's Little Theorem is the statement:

There is a number a, it is an integer, i.e. not fractional. And there is a number p, it is simple, i.e. is only divisible by 1 and itself. If a is not divisible by p, then ap-1-1 is divisible by p. Let's take the numbers 7 and 3. When dividing 7 by 3, you won't get an integer. But if you raise 7 to the power of 3-1 and subtract 1, you get 48. And 48 is perfectly divisible by 3 without a remainder.

An interesting theorem and, at first glance, absolutely useless. And especially in the opinion of mathematicians, who at one time simply did not understand how to use it. Minor spoiler: this theorem protects your information every day, you just don't know it. Don't suspect yet, but we'll get there.

Actually, this article is about cryptography

Man has always had his secrets. And if it is not difficult to retell the secret in the ear of a friend, then it is already much more difficult to convey it at a distance. The statesmen had especially many secrets: this was influenced by the conditions of the war, conspiracies and constant court intrigues. Thus, the first ciphers were invented precisely for political purposes.

The Jews invented the Atbash cipher. The encryption rule was as follows: the n-th letter in the word was replaced by the letter i-n+1. Those. the first letter of the alphabet was replaced by the last, the second by the penultimate, and so on.

The name of this cipher comes from the letters "alef", "tav", "bet" and "shin", that is, the first, last, second and penultimate letters of the Hebrew alphabet.

A little more complicated was the cipher of the Spartans - Skital. To encrypt and decrypt messages, they used special tools - cylinders of different diameters. By spiraling a narrow strip of parchment around a stick, they wrote down the message horizontally. When the parchment was unwound, the phrase was encrypted.

At any lecture on cryptography, you will definitely be told about the Caesar cipher. Sending secret messages to his associates, Caesar shifted the letters in the alphabet to an arbitrary value. For example, in Cyrillic, when shifted three positions forward, the letter "A" will become encrypted "G". Well, if the approximate knew the meaning of this very shift. Otherwise, the Roman emperor doomed his subjects to sleepless nights of unraveling, and himself to the prospect of becoming the salad of the same name.

The Caesar cipher with a shift of thirteen is currently used in the ROT13 algorithm. The number thirteen has no underlying reason: there are simply 26 letters in the Latin alphabet, and when shifted by 13, the encryption algorithm coincides with the decryption algorithm. And Sir Arthur Conan Doyle dabbled in it in his story "The Dancing Men".

All ciphers that use letter shifting are called monoalphabetic ciphers. They were good on the battlefields of Caesar against Obelix and Asterix. Today, any smartphone can decipher them by brute force, but even in those days they were solved without any computers.

Grammar betrayed us all

The secret sooner or later becomes clear. And if your secret that you are a fan of "My Little Pony" does not cause much unrest even among relatives, then revealing the army's offensive plans can be fatal. This information is very important. And, of course, there is always someone who wants to intercept them.

For example, Aristotle was brought in to decipher the Spartan Scytals. And quite successfully. He used a cone, winding an encrypted note around it and changing the diameter. Sooner or later, the words acquired meaning, and the cipher itself lost this very meaning. Other ciphers cannot be cracked this way.

In ancient times, people did not know what cryptographic frequency analysis was, but, without suspecting it, they actively used it - grammar helped them in this. Every language has its weaknesses: the most obvious example is articles in English. They are often repeated in the text and thus make it more vulnerable. Highlighting the same fragments of the cipher, we can assume that this is an article, find out the shift and use the brute force and guesswork method to get the answer.

For the secret to remain secret, you need to better encrypt, Caesar.

Encryption Strikes Back

And then the polyalphabetic cipher was invented. It uses a set of monociphers: not one shift, but several. A good example is the Vigenère cipher. It uses a special table and a code word to encrypt the text. This is how the cipher table for English looks like.

Let's encrypt the phrase "encrypted" in it. Let's think of a key. It can be any word or phrase no longer than the cipher itself: the number of letters in the key must equal the number of letters in the cipher. Let the word "geese" be the key. We repeat the letters in the key as many times as there are letters in the encrypted message. It turns out "gusigusigu". Now we encrypt. At the intersection of the first letters of our phrase and the key there will be the letter "s", at the intersection of the second letters there will also be "s", then "e" and so on. The finished cipher will look like this: “yёshchyudefvo”.

The Vigenère cipher can also be subjected to frequency analysis, but it is much more difficult to trace the patterns in it, because each letter is shifted in a random order. This suited everyone who conveys messages. The enumeration took a lot of time, and it was extremely difficult to decipher the message in time - the information simply became outdated.

Nevertheless, the endless war of encryption and decryption continued. At the beginning of the twentieth century, cryptographic fashion trends changed. Electromechanical machines began to encrypt for us. And decrypt for us too.

The most difficult and interesting thing in cryptography is just beginning.