Lecture
Symmetric cryptosystems (also symmetric encryption, symmetric ciphers) (англ. symmetric-key algorithm) — are a class of cryptographic systems in which the same key is used both for encrypting and for decrypting messages. This means that both parties, the sender and the recipient, share a common secret key. Before the invention of the asymmetric encryption scheme, symmetric encryption was the only method that existed. The algorithm's key must be kept secret by both parties, and measures must be taken to protect access to the channel along the entire path of the cryptogram, or by the interacting parties via crypto-objects and messages, if this communication channel is marked «Not for use by third parties». The encryption algorithm is chosen by the parties before the exchange of messages begins.
Data encryption algorithms are widely used in computer technology in systems for concealing confidential and commercial information from malicious use by third parties. The main principle behind them is the condition that the transmitter and the receiver know the encryption algorithm in advance, as well as the key to the message, without which the information is merely a set of characters with no meaning.
Classic examples of such algorithms are the symmetric cryptographic algorithms listed below:
Simple transposition without a key is one of the simplest encryption methods. The message is written into a table by columns. After the plaintext has been written in columns, it is read off by rows to form the ciphertext. To use this cipher, the sender and receiver need to agree on a shared key in the form of the table's dimensions. Grouping the letters is not part of the cipher key and is used only for convenience in writing down meaningless text.
A more practical encryption method, called single columnar transposition with a key, is very similar to the previous one. It differs only in that the columns of the table are rearranged according to a keyword, phrase, or set of numbers whose length equals a row of the table.
For additional secrecy, a message that has already been encrypted can be encrypted again. This method is known as double transposition. To do this, the size of the second table is chosen so that the lengths of its rows and columns differ from the lengths in the first table. It is best if they are coprime. In addition, in the first table the columns can be rearranged, and in the second the rows. Finally, the table can be filled in a zigzag, a snake pattern, a spiral, or some other way. Such methods of filling the table, even if they do not strengthen the cipher's security, make the decryption process considerably more entertaining.
Magic squares are square tables whose cells are filled with consecutive natural numbers starting from 1, such that the sum is the same for every column, every row, and every diagonal. Such squares were widely used for entering the text to be encrypted according to the numbering inscribed in them. If the contents of the table were then written out row by row, the result was a cipher formed by letter transposition. At first glance it may seem that there are very few magic squares. Nevertheless, their number grows very quickly as the size of the square increases. For example, there is only one magic square of size 3 x 3, not counting its rotations. There are already 880 magic squares of size 4 x 4, and the number of magic squares of size 5 x 5 is around 250,000. Therefore, magic squares of larger sizes could serve as a good basis for a reliable encryption system of that era, because manually brute-forcing all key variants for this cipher was unthinkable.
In a square of size 4 by 4, the numbers from 1 to 16 were entered. Its magic consisted in the fact that the sum of the numbers along the rows, columns, and full diagonals was equal to the same number — 34. These squares first appeared in China, where they were attributed a certain «magical power».
| 16 | 3 | 2 | 13 |
| 5 | 10 | 11 | 8 |
| 9 | 6 | 7 | 12 |
| 4 | 15 | 14 | 1 |
Encryption using the magic square was carried out as follows. For example, suppose we need to encrypt the phrase: «ПриезжаюСегодня.» («I am arriving today.»). The letters of this phrase are entered sequentially into the square according to the numbers written in it: the position of the letter in the sentence corresponds to the ordinal number. A period is placed in the empty cells.
| 16. | 3 и | 2 р | 13 д |
| 5 з | 10 е | 11 г | 8 ю |
| 9 С | 6 ж | 7 а | 12 о |
| 4 е | 15 я | 14 н | 1 П |
After this, the encrypted text is written out in a line (reading is done from left to right, row by row):
.ирдзегюСжаоеянП
During decryption, the text is entered into the square, and the plaintext is read off in the sequence of numbers of the «magic square». The program must generate «magic squares» and select the required one based on the key. The size of the square is larger than 3x3.
Complete loss of all statistical regularities of the original message is an important requirement for a symmetric cipher. For this, the cipher must have an «avalanche effect» — a strong change in the ciphertext block must occur with a 1-bit change in the input data (ideally, 1/2 of the bits of the ciphertext block should change).
Another important requirement is the absence of linearity (that is, the condition f(a) xor f(b) == f(a xor b)), since otherwise the application of differential cryptanalysis to the cipher is made easier.
At present, symmetric ciphers are:
Most symmetric ciphers use a complex combination of a large number of substitutions and permutations. Many such ciphers are executed over several passes (sometimes up to 80), using a «round key» on each pass. The set of «round keys» for all passes is called the «key schedule». As a rule, it is generated from the key by performing certain operations on it, including permutations and substitutions.
A typical way of building symmetric encryption algorithms is the Feistel network. The algorithm builds the encryption scheme based on a function F(D, K), where D is a portion of data half the size of the encryption block, and K is the «round key» for the given pass. The function is not required to be invertible — its inverse function may be unknown. The advantages of the Feistel network are that decryption almost completely coincides with encryption (the only difference being the reverse order of the «round keys» in the schedule), which greatly simplifies hardware implementation.
The permutation operation shuffles the bits of the message according to some rule. In hardware implementations it is trivially realized as a rearrangement of wires. It is precisely the permutation operations that make it possible to achieve the «avalanche effect». The permutation operation is linear — f(a) xor f(b) == f(a xor b)
Substitution operations are performed as replacing the value of some part of the message (often 4, 6, or 8 bits) with a standard value hard-wired into the algorithm, by referring to a constant array. The substitution operation introduces nonlinearity into the algorithm.
Often the strength of the algorithm, especially against differential cryptanalysis, depends on the choice of values in the substitution tables (S-boxes). At the very least, it is considered undesirable to have fixed points S(x) = x, as well as the absence of influence of some bit of the input byte on some bit of the result — that is, cases where the result bit is the same for all pairs of input words differing only in that bit.
There are many (at least two dozen) symmetric cipher algorithms, whose essential parameters are:
block ciphers
stream ciphers
To compensate for the drawbacks of symmetric encryption, a combined (hybrid) cryptographic scheme is now widely used, in which a session key is transmitted using asymmetric encryption, and this key is then used by the parties to exchange data via symmetric encryption.
An important drawback of symmetric ciphers is the impossibility of using them in mechanisms for generating digital signatures and certificates, since the key is known to each party.
Comments