GOST 28147-89 (Part 1. Introduction and general principles)

Very often on Habré there are articles about the essence, software implementations, opening ciphers. But one thing is not clear: why among them there are no our, domestic encryption algorithms?

I decided to correct this by writing a story article, divided into 5 parts for better perception of the standard GOST 28147-89. Each part, except the first (describes the algorithm scheme and general principles), tells about each of the four possible modes of operation of the standard with the application of C ++ code to them.

Algorithm Description

GOST 28147-89 is a domestic block cipher. That is, the plaintext is divided into blocks (in this case, 64 bits), and each block is converted separately.
')
The algorithm is based on the Feistel network presented in the figure below.

I will explain the work of this scheme.

1. Each block is divided into two “sub-blocks” (left and right, respectively).
2. The initial filling of the right block is recorded in the left block at the output.
3. Above the right block, a cryptographic transformation is performed using key data.
4. The left (source) and right (converted) blocks are added modulo 2 in the adder modulo 2.
5. This is repeated several times.

Algorithm block diagram

This scheme contains:

• Four 32-bit drives: N ₁ , N ₂ , N ₃ , N ₄ .
• Two 32-bit drives: N ₅ and N ₆ , - with permanent fillings C ₂ and C ₁ recorded in them, respectively.
• 256 bit key memory. consists of eight drives of 32 bits each: X ₀ , X ₁ , X ₂ , X ₃ , X ₄ , X ₅ , X ₆ , X ₇ .
• Modulo 2 32-bit adder: CM ₂ .
• Another adder modulo 2, which has no restrictions on the bit width (but uses 64 bits): CM ₅ .
• Two adders modulo 2 ³² bit width 32 bits: CM ₁ , CM ₃ .
• Modulo (2 ³² -1): ₄ .
• K substitution block: eight K ₁ , K ₂ , K ₃ , K ₄ , K ₅ , K ₆ , K ₇ , K ₈ replacement nodes, each with 64 bit memory.
• The cyclic shift left register is 11 bits R.

Keys

In KZU

KZU allocated 256 bits, in GOST 28147-89 key is used with a length of 256 bits. The key is divided into eight blocks of 32 bits, and each bit of each block is sequentially entered into drive X of the corresponding order.

That is, the 1st bit of the key is entered into the 1st bit of the drive X ₀ , the 2nd bit into the 2nd bit of the drive X ₀ , the 33rd bit into the 1st bit of the drive X ₁ , the 65th bit into 1 th bit of drive X ₂ , and so on, the 224th key bit is entered into the 1st bit of the drive X ₇ , the 256th bit of the key is entered into the 32nd bit of the drive X ₇ .

The key is read in accordance with the selected mode of the algorithm, but in the following parts of the article.

In substitution block K

The substitution block contains a replacement table with a dimension of 16x8, which is a long-term key.

Rows of the table determine, roughly speaking, that you want to replace (a number from 0 to 15 in hexadecimal notation). Columns also indicate what to replace. In this case, the incoming 32-bit vector into a block is divided into eight 4-bit ones, each of which is converted in accordance with the replacement table.

Keys in both the KZU and block K are secret, and measures are needed to prevent them from being compromised.

Modes of operation

Finally, I would like to note that GOST 28147-89 works in 4 modes, each of which will be discussed in the next 4 articles (with code in C ++):

• Simple replacement mode.
• Gamma mode.
• Gamma mode with feedback.
• Mode of production imitovstavki.

Yes, at this moment, all, gentlemen, next time we consider the simple replacement mode, which is the base for all other modes.

UPD: The next part of the article "Simple replacement mode" is available here .