Can you decipher the word once?

Part 1: Basics

The word cryptography is composed of the two Greek words kryptos and graphein, which means "secret" and "write". Accordingly, cryptography is the science that deals with the writing of secret messages - the process that is colloquially referred to as encryption.

Opposite cryptography is cryptanalysis. It is the science that deals with researching, analyzing and deciphering secret messages. In a sense, cryptanalysis is the downside of cryptography.

In fact, cryptography is not the only method of composing secret messages: steganography, for example, is based on the idea of ​​not encrypting messages, but rather hiding them. Most cryptographic methods have the major disadvantage that you can immediately see that the encrypted messages are encrypted - that alone can arouse suspicion.

If you hide the message in an inconspicuous way instead, you may save yourself very unpleasant measures. In connection with cryptography, it certainly makes sense to have heard the term steganography before, but the following is exclusively about cryptography itself.

Alice, Bob and Eve ...

As mentioned earlier, cryptography is about encrypting and decrypting messages. The two processes represent two sides of the same coin and are mutually dependent. In order to be able to carry out encryption, a message must first be available that is to be transmitted. It is called plain text. The encryption turns the plain text into cipher text. If it is decrypted again, the original plain text is obtained.

When messages are to be delivered, there is always a sender and recipient. In cryptography, two personas have become established for this: the sender is usually named Alice, the recipient Bob. Of course, Alice and Bob wouldn't have to protect their communication if there wasn't a third party from whom things have to be kept secret: the attacker is common in cryptography Eve called. She is the one who tries to illegally crack the intercepted messages using the means of cryptanalysis.

The mechanism with which a plain text is converted into a ciphertext or a ciphertext into a plain text is called an algorithm. In order to be able to reuse an algorithm flexibly in different situations, it should be parameterizable, i.e. adaptable to an individual situation using one or more factors. The factors form the key that is used to encrypt and decrypt.

As early as 1883, the Dutch linguist Auguste Kerckhoffs formulated the Kerckhoffs principle, which was subsequently named after him, and which relates to the security of cryptographic algorithms. It says: "It must not require secrecy and should be able to fall into the hands of the enemy without harm."

Ultimately, this means that the security of an encryption may only depend on the selected key, but not on the method used. It must even be possible to publish the process expressly without restricting the security of the encryption at the same time.

There are numerous reasons for the principle. For example, it is far more difficult to keep an algorithm secret than a key, since the algorithm can be determined, for example, by reverse engineering hardware or software. In addition, publicly available algorithms can be analyzed and checked for vulnerabilities much more easily by independent developers - an idea that can be found in a similar form in today's open source movement.

If, on the other hand, the algorithm is kept secret, one speaks of "security by obscurity". Often, however, one only achieves a pretended security in this way, which can lead to nasty surprises.

... meet Caesar

The simplest approach to encrypting messages goes back to the Roman Emperor Caesar, which is why the process is also known as the Caesar cipher. The basic idea is very simple: First, write the alphabet down twice, line by line, so that the second line is below the first:

ABCDEFGHIJKLMNOPQRSTUVWXYZ ABCDEFGHIJKLMNOPQRSTUVWXYZ

Then you shift the upper alphabet by a fixed number of places. This number forms the key. For example, a key of three gives the following shift:

ABCDEFGHIJKLMNOPQRSTUVWXYZ ABCDEFGHIJKLMNOPQRSTUVWXYZ

Now the letters of the upper alphabet can be mapped to those of the lower one. For example, an A becomes a D, a B becomes an E, a C becomes an F, and so on. Since no suitable letter is available in the lower alphabet for the letters from X, the alphabet is broken here so that the X is again mapped to A, the Y to B and the Z to C.
Entire texts can now be encrypted along the way. The plain text ATTACK AT DAWN becomes the following ciphertext: DWWDFN DW GDZQ.

The encryption can also be easily reversed. All that is needed is to set up the same system, only this time the key is negated. Instead of shifting the upper alphabet three places to the right, it is now shifted three places to the left:

ABCDEFGHIJKLMNOPQRSTUVWXYZ ABCDEFGHIJKLMNOPQRSTUVWXYZ

If you use the same process again, you get the original plain text ATTACK AT DAWN.

The approach to shifting the alphabet is the algorithm. The number of places to move is key. There are 25 different options for the key in the Caesar cipher, if you disregard the option of mapping a plain text to yourself. So it is said that the key space has a size of 25.

Admittedly, this is a very small key space, which is why the easiest way to crack a Caesar cipher is to simply try out all the potential keys until you find a meaningful plaintext for one. If you take the given ciphertext and decrypt it with key 1, it becomes clear after the first letters that the result is not a meaningful text: CVVCEM CV FCYP. And even a shift by 2 does not result in any meaningful plain text: BUUBDL BU EBXO. But the text ATTACK AT DAWN already appears on the third attempt. So the encryption is cracked.

The approach of simply trying out all potential keys is ultimately based on brute force, namely the use of sufficient computing power. It is therefore called brute force.

How do you crack encryption?

In fact, there are other approaches to cracking a Caesar cipher. You can proceed much more systematically, which may be a bit exaggerated in this case, but clearly shows that there are other possibilities as well.

If you compare the plain text with the ciphertext, it is noticeable, for example, that letters that appear twice in the plain text are also represented twice in the ciphertext. In addition, the same letters are always encrypted to the same letters in the ciphertext. The two effects are particularly noticeable with the letters T and A:

ATTACK AT DAWN DWWDFN DW GDZQ

You can make use of this, at least if you want to decipher longer texts. The effects mean that the distribution of the individual letters in the plain text is the same as that in the ciphertext: The letter that is most frequently contained in the plain text is also represented in the ciphertext by the most frequently occurring character.

Since the language of a message is often known or at least can be presumed with a high degree of probability, one only needs to know the frequency of letters in the respective language in order to draw conclusions. The most common letter in English is - as is also the case in German - the E. In second place in English are the letters A, I, N, S and T.

If you count the frequencies of the ciphertext, the following distribution results:

  • D: 4
  • W: 3
  • Q: 1
  • N: 1
  • G: 1
  • Z: 1
  • Q: 1

In the middle of the ciphertext is now a word that consists of just two letters. For example, it could be IN, ON, IS, or AT. There are a few possibilities, but a manageable number. Now it is also noticeable that the word consists of letters that also make up two thirds of the first word: If the word in the middle were to say IS, for example, the first word would have to be ISSI .. However, there is no six-letter English word that begins with ISSI. Therefore, the middle word cannot be IS.

The same goes for INNI and ONNO. With ATTA, on the other hand, you come across ATTACK. This means that you now know that the first two words are called ATTACK AT and the third word follows the pattern .A ... Of course, one could guess at DAWN, but enough information is now available to suspect that key 3 was used. If you apply it to the third word, you get DAWN, and you can assume that the message has been decrypted correctly.

If you do not believe that an encrypted message can be decrypted in a reasonable amount of time in this way, you can have fun trying the following ciphertext, which was created with the help of the Caesar cipher from a German-language plain text (umlauts were represented by two letters, a Ä is for example a AE and a ß a SS):

URJ MVIWRYIVE, SVZ TRVJRI VZEWRTY SLTYJKRSVE QL QRVYCVE, ZJK JF VZEWRTY LEU WLEBKZFEZVIK JF XLK, URJJ ZTY JTYFE RCJ BZEU XIFJJVE JGRJJ URIRE YRKKV, UVIRIK MVIJTYCLVJJVCKV ERTYIZTYKVE QL BERTBVE - XVJTYIZVSVE YRK JZV URDRCJ DVZE grgr WLVI DZTY.

The letter frequency table from Wikipedia for German-language texts is recommended as a support.

Obviously, the Caesar cipher is not a serious method of encrypting messages these days, but it still has useful uses today. One of the most famous is based on the fact that by shifting 26 you will map the alphabet back to yourself. The key 26 in turn can be interpreted as a double Caesar cipher with the key 13.

This means that you can convert a plaintext into a ciphertext by shifting it by 13, and by shifting it again by 13 the ciphertext can be converted back into the original plaintext. There is no need to negate the key for decryption. Although the procedure does not offer any security, it prevents a message from being readable at first glance.

Therefore, for example, various discussion forums use the Caesar cipher with a key of 13 to obscure forum posts that contain a spoiler. The procedure is called ROT13 because the message is rotated by 13 characters each time it is called.

From antiquity to the Middle Ages

Even if the Caesar cipher may seem trivial from today's point of view, it was nonetheless without competition for centuries. But even as new approaches emerged in the 16th century, they too were based on shifting the alphabet. The most fundamental innovation, however, was not to use just one alphabet, but several: That is why these procedures are called polyalphabetic procedures, whereas the Caesar cipher is a monoalphabetic procedure.

The best known is the Vigenère cipher, which was developed by the French diplomat Blaise de Vigenère and named after him. To use the cipher, you first write all possible Caesar alphabets in a square one below the other:

ABCDEFGHIJKLMNOPQRSTUVWXYZ BCDEFGHIJKLMNOPQRSTUVWXYZA CDEFGHIJKLMNOPQRSTUVWXYZAB: XYZABCDEFGHIJKLMNOPQRSTUVW YZVIQMNOPLQRSTUVW YZVIQXRLKUKFG

If you want to encrypt a message, you first need a key again. At Vigenère, however, not just a number is used, but a code word, for example ABBA. Now write the plain text and the code word on top of each other and repeat the code word as often as necessary:

ABBA ABBA ABBA AB ATTA CK A T DA WN

Then each letter of the plain text is encrypted with the alphabet that results from the letter of the code word. For the first character of the plaintext, the A, this means that it is encrypted with the A of the code word. The first thing to do is to find the right alphabet in the Vigenère square. To do this, look for the line whose first character corresponds to the letter of the code word, which in this case supplies the first line. Then look for the letter of the plaintext in the first line of the Vigenère square, and then take the intersection of the line and column. In this example, this means that the A remains an A.

The second letter, a T, should be encoded with a B. So you take the B line and look to see which letter is there in the column in which the T is in the first line. This leads to a U. If you continue this procedure, you get the following ciphertext:

AUUACL AT EAWO

What is striking is the high similarity between plain text and ciphertext. The second word of the message, AT, has even been preserved in its entirety. This is due to the high number of the letter A in the code word, which leads to a mapping to itself. Take another code word, for example DEVELOPER, the result is much better:

EGMWKM LX HNPJ

The Vigenère method solves some of the problems of the Caesar cipher: It prevents the same letters in plain text from always being mapped onto the same letter in ciphertext. In fact, the A from the plaintext in the example has never been mapped to the same character in the ciphertext. Instead, the characters E, W, L and N were used. This makes the frequency analysis much more difficult, which is why the process was considered indecipherable for almost 300 years. It was not until 1854 that Charles Babbage found an approach to cracking the procedure.

The core of the cryptanalysis at this point is to first determine the length of the code word. To do this, one looks for pairs of letters that occur periodically. From the repetitions, conclusions can be drawn about the length of the key. Once you have determined it, you know that every nth character was encrypted with the same alphabet - which again corresponds to the cracking of Caesar with a frequency analysis.

It is obvious that the shorter the key used, the better the procedure works. Ideally, the key is as long as the plaintext. In this case one speaks of a Vernam cipher. But even then, the procedure is not infallible: Complex modern statistical procedures still provide more than enough options for recognizing patterns.

A pinch of coincidence, please!

One of the highest goals in cryptography is therefore to eliminate patterns. The more uniform and inconspicuous a ciphertext appears, the more difficult it becomes to crack the procedure and to restore the plaintext without knowing the key or to reconstruct the key. If you think about the task of developing an encryption algorithm that avoids patterns, you realize that one actually already exists: The Caesar cipher fulfills the requirements wonderfully as long as you only encrypt a single character. If the intercepted message consists of a J, there is no systematic way of determining whether the associated plaintext is an A, a B, a C, or any other letter.

So if you were to encode each letter of a plaintext independently of the others with the Caesar cipher, you would have a perfect procedure: The problem with the patterns arises precisely from the fact that information from the surroundings of each individual character can be determined. If this is omitted and each character is individually encrypted, decryption without a key becomes impossible.

On the one hand, this means that you need a key that is as long as the plain text (like the Vernam cipher). On the other hand, this also means that the key used must be random - otherwise the key also contains patterns from which information can be derived. If you then use such a key only once and use a new key for each new plaintext, you have a perfect encryption system based on very simple principles.

The procedure is known as a one-time pad (OTP). It is trivial to implement and mathematically demonstrably absolutely safe if one adheres to the conditions repeated here:

  • The key is as long as the plaintext.
  • The key is chosen at random.
  • A key that is used once is not used again.

The prize question is: If there is such a method that solves all problems and that provably cannot be cracked, why is the method not used on a large scale everywhere and by everyone? Why should one even bother with other procedures?

The problem with the One-Time Pad is the key exchange. Since the key has to be regenerated for each message, Alice not only has to transmit the message to Bob, but also the key. The dilemma lies in the transmission: If there is a secure way of transmitting the key, the actual message could have been transmitted along the way. However, if there are concerns about transmitting a message, one must also have the same concerns about the transmission of the key.

The problem is exacerbated by the fact that Alice and Bob are, strictly speaking, not the only parties who want to communicate securely with each other. If Alice and Bob each have other communication partners, each of them needs their own key for each one - a new one for each individual message. The number of keys used grows disproportionately with the number of participants, which turns out to be unsuitable for everyday use.

The procedure is therefore only viable if it involves a small group of participants and there is a secure way for them to transmit a large number of keys in advance, which can then be used by both parties. Of course, the effort for this is very high. In fact, the one-time pad is used in practice, but only in environments where the effort justifies the benefit, for example in high diplomatic and military circles.

If one disregards these problems, however, the process is trivial to implement. Since it should work for any characters and not just for the capital letters of the alphabet, it is advisable to link the ASCII code of a plain text character with the ASCII code of a key character using XOR. XOR has the great advantage that the same combination, applied twice in a row, returns the original value:

65 XOR 97 => 32 32 XOR 97 => 65

The first call to XOR encrypts, the second decrypts. In JavaScript, the code looks like this:

const encrypt = function (plain, key) {const cipher = plain.charCodeAt (0) ^ key.charCodeAt (0); return cipher; };

If you want to encrypt a whole string, you just have to iterate over its individual characters and the function for each encrypt as shown in Listing 1.

const plainText = 'Attack at dawn!'; const key = 'grgzuoqfg348qfg'; const cipherText = []; for (let i = 0; i This results in an array of numbers that can then be converted back into the original text using a similar loop and the same key.

outlook

Unfortunately, there is another problem with the One-Time Pad: How do you generate the random key? In spite of all computing power and storage capacity, computers are one thing above all else: deterministic. After all, they're very complex calculating machines, and chance is pretty much the only thing you don't want in a calculating machine. So what to do And what to do if the one-time pad proves to be too expensive for purely practical reasons? What is a viable alternative?

These questions are addressed in the second part, in which it is explained how the generation of random numbers works, what to look out for, and what a viable alternative to the methods presented so far that can be used in everyday life looks like.

Even if the procedures presented so far are either too unsafe or too complex, it is important to be familiar with them. They form the basis for everything else and are also ideal for introducing basic terms and approaches. So it remains exciting.