In the guests' sitting "Grasshopper"
In June of this year, a new block encryption standard was adopted in Russia - GOST R 34.12-2015. This standard, in addition to the good old GOST 28147-89, which is now called "Magma" and has a fixed set of substitutions, contains a description of the Grasshopper block cipher. I will tell about it in this post.
In contrast to GOST 28147-89, the new cipher is not a network of its Feistel, but the so-called. SP network: a transformation consisting of several identical rounds, with each round consisting of non-linear and linear transformations, as well as a key-overlay operation. Unlike the Feistel network, using the SP network converts the entire input block, not half of it. Such a structure is sometimes also called AES-like (similar to AES), however, unlike the latter, “Grasshopper” has a number of its own “chips”:
The length of the input block "Grasshopper" - 128 bits, key - 256 bits.
Encryption is based on the sequential application of several of the same type of rounds, each of which contains three transformations: addition with a round key, transformation by a substitution unit, and linear transformation.
The 128-bit input vector of the next round is added bit by bit with a round key:
')
The nonlinear transformation is the application to each 8-bit sub-vector of a 128-bit input vector of a fixed substitution:
The Grasshopper uses the same substitution as the Stribog hash function.
Linear transformation, as I have already said, can be implemented not only as usual in block ciphers — a matrix, but also with the help of a RLOS — a linear feedback shift register, which moves 16 times.
The register itself is realized over a Galois field modulo an irreducible polynomial of degree 8:
:
Round conversion can be represented as follows:
Now consider the procedure for generating round keys from the master key. The first two are obtained by splitting the master key in half. Next, to generate the next pair of round keys, 8 iterations of the Feistel network are used, where, in turn, the counter sequence using the linear transformation of the algorithm is used as the round keys:
The key sweep round can be represented as follows:
And the whole procedure for generating round keys as follows:
As a result, the encryption of a single 128-bit input block is described by the following equation:
And in the form of a flowchart can be represented as follows:
Decryption is implemented by reversing the basic transformations and applying them in the reverse order:
In contrast to GOST 28147-89, the new cipher is not a network of its Feistel, but the so-called. SP network: a transformation consisting of several identical rounds, with each round consisting of non-linear and linear transformations, as well as a key-overlay operation. Unlike the Feistel network, using the SP network converts the entire input block, not half of it. Such a structure is sometimes also called AES-like (similar to AES), however, unlike the latter, “Grasshopper” has a number of its own “chips”:
- linear transformation can be implemented in using the shift register;
- the key scan is implemented using the Feistel network, which uses a round transformation of the original algorithm as a function.
The length of the input block "Grasshopper" - 128 bits, key - 256 bits.
Transformations
Encryption is based on the sequential application of several of the same type of rounds, each of which contains three transformations: addition with a round key, transformation by a substitution unit, and linear transformation.
The 128-bit input vector of the next round is added bit by bit with a round key:
')
The nonlinear transformation is the application to each 8-bit sub-vector of a 128-bit input vector of a fixed substitution:
The Grasshopper uses the same substitution as the Stribog hash function.
Linear transformation, as I have already said, can be implemented not only as usual in block ciphers — a matrix, but also with the help of a RLOS — a linear feedback shift register, which moves 16 times.
The register itself is realized over a Galois field modulo an irreducible polynomial of degree 8:
:Round conversion can be represented as follows:
Generation of round keys
Now consider the procedure for generating round keys from the master key. The first two are obtained by splitting the master key in half. Next, to generate the next pair of round keys, 8 iterations of the Feistel network are used, where, in turn, the counter sequence using the linear transformation of the algorithm is used as the round keys:
The key sweep round can be represented as follows:
And the whole procedure for generating round keys as follows:
Encryption and decryption
As a result, the encryption of a single 128-bit input block is described by the following equation:
And in the form of a flowchart can be represented as follows:
Decryption is implemented by reversing the basic transformations and applying them in the reverse order:
Links
- The original description of the standard is available here .
- You can also download the reference implementation .
- In addition, Markku-Juhani Saarinen has his own realization on the githaba .
Source: https://habr.com/ru/post/266359/
All Articles