Algorithm of enciphering of GOST 28147-89. A method of simple replacement.

«While you are live, do not die, at this world look.
At many here the soul is dead – they are dead inside.
But go and laugh, without knowing that they are not present,
Do not hurry the death hour »– she has told to me.

Aria, «There it is high»

The maintenance:

1.     Introduction

2. Preliminary data on block code numbers

2.1  Seti Fajstelja.
2.2  Block code number of GOST 28147-89

3. Theoretical minimum

3.1     Key information
3.2     Basic step криптопреобразования

3.3  Base cycles: "32-Z", "32-R".

4. Practice

4.1  Realization of the basic step криптопреобразования
4.2     Increase in speed of algorithm
5.     Requirements to the key information
6. The     list of the used literature
7.     Thanks.

Introduction.

The given document is my attempt to describe a method of simple replacement of algorithm of enciphering of GOST of 28147-89 most simple, but, nevertheless, technically-competent language. About, whether it has how much turned out at me, the reader will tell the opinion after will read first six points.

For this purpose that would wash work has given more advantage I recommend to arm with works of authors specified in the list of the used literature. The calculator that in it were function by calculation of operation XOR since article perusal assumes Is recommended also that the reading has intended to study the given algorithm of enciphering. Though as the handbook it too will approach, but I wrote this article, as training.

Preliminary data on block code numbers.

            Before we will start to consider algorithm, it is necessary for us to familiarise with history of creation of such code numbers. The algorithm concerns the category of block code numbers in which architecture the information breaks into final quantity of blocks, final is natural can not the full. Enciphering process occurs over full blocks which form шифрограмму. The final block if it incomplete is supplemented than or (on its addition I will tell about nuances more low) and is ciphered as well as full blocks. Under шифрограммой I understand – result of action of function of enciphering over a quantity of the data which the user has submitted for enciphering. In other words шифрограмма is an end result of enciphering.

           The history of development of block code numbers associates with the beginning 70х years when company IBM having realised necessity of protection of the information at data transmission on COMPUTER communication channels, has started performance of own program of the scientific researches devoted to protection of the information in electronic networks, including cryptography.

           The group of researchers – developers of firm IBM which have started research of systems of enciphering with the symmetric scheme of use of keys, was headed by doctor Horst Fajstel.

2.1 Seti Fajstelja

        Offered Fajstelem architecture of a new method of enciphering in the classical literature has received the name «Architecture of Fajstelja», but at present in the Russian and foreign literature more settled term – "a network of Fajstelja" or Feistel ` s NetWork is used. In a consequence on the given architecture the code number "Lucifer" has been constructed - which later has been published and has caused a new wave of interest to cryptography as a whole.

           The idea of architecture of "a network of Fajstelja" consists in the following: the entrance stream of the information breaks into blocks in the size in n bits, where n even number. Each block shares on two parts – L and R, further these parts move in the iterative block code number in which the result of j th stage is defined by result of the previous stage j-1! Told it is possible to illustrate on an example:

Fig. 1

 Where, function And is basic action of the block code number. Can be simple action, such as operation XOR, and can have more difficult appearance to be sequence of some simple actions – addition on the module, shift to the left, replacement of elements etc., in aggregate these simple actions form so-called – the basic step криптопреобразования.

It is necessary to notice that key elements of work of function is giving of elements of keys and operation XOR and from that are how much well thought over work of these operations, speaks about криптостойкости the code number as a whole.

That the idea of networks of Fajstelja was definitive is clear, we will consider the elementary case represented on fig. 1 where in function And – will act operations “mod 2” (“xor”), but it is the elementary case, in more serious situation, for example concealment of the information of the state importance function And can be more difficult (how many I saw function And really happens very difficult):

Initial data:

L = 1110b, R = 0101, K = 1111b

The purpose:

To receive шифрограмму

The decision:

1. (R + K) mod 2⁴ = Smod, Smod = 0100b

2. (Smod + L) mod 2 = Sxor, Sxor = 1010b

3. L = R, R = Sxor

Result:

 L = 0101b, R = 1010b

           Let's explain our actions:

1.      This operation addition on mod 2⁴. In practice such operation is reduced to simple addition where we should combine two numbers and ignore carrying over in 5й the category. As if to put down over categories of binary representation of number to put down exponents, over the fifth category just there will be an indicator four, will look at drawing more low where actions of our operation are represented:

Fig. 2

Here I an arrow have specified in exponents, apparently, the result should turn out 10100 but as at operation mod 2⁴ carrying over is ignored, we receive 0100.

2. This operation in the literature is called mod 2, in assembler language is realised by command XOR. But its more correct name mod 2¹. Without this unique operation hardly it is possible to construct fast, easily realised algorithm of enciphering and thus that it was more enough криптостойким. Uniqueness of this operation consists that she to itself return! For example, if number And поXORить with number, as a result we will receive In, further it is enough переXORить number and In among themselves to receive former value And!

In this operation we have received 1010 having numbers 1110 and 0100 to receive back 1110, there is enough переXORрить among themselves number 0100 and 1010! In more details about this operation it is possible to esteem in article which is enclosed on a site www.wasm.ru, «the Elementary management on CRC_алгоритмам detection of errors» the author, which Ross N. Williams. In this work there is a point - «5. Binary arithmetics without carryings over». That's it in this article operation xor also is described! I exclaim because in this article this operation so is painted that the reader not simply understands as this operation works, he even starts it to see, hear and feel!

3. This action is necessary, that at deciphering from шифрограммы it was possible to receive reference values.

2.2 Block code number of GOST 28147-89

        The algorithm of enciphering of GOST 28147 – 89 concerns the category of block code numbers of the balanced networks of Fajstelja working on architecture where two parts of the chosen block of the information have the equal size. The algorithm has been developed in bowels of the eighth department of KGB transformed nowadays in Federal agency for government communication and information and has been fixed, as the standard of enciphering of the Russian Federation in 1989 at the USSR.

           For work of the given method of algorithm it is necessary to break the information into blocks in the size in 64 bits. To generate or enter into enciphering system, the following key information: a key and the table of replacements. At enciphering it is necessary to be in earnest about a choice of a key and the table of replacements very much since it is the base of safety of your information. About what requirements are imposed on a key, and the table of replacements look point «Requirements to the key information».

By consideration of a method we will not point at it attention since this article as I already spoke above, is written on purpose, to learn reading, to cipher the data on a method of simple replacement of the given algorithm of enciphering, but we will necessarily concern this question in the end of article.

Theoretical minimum.

3.1 Key information

As I already spoke above, in enciphering of the data active participation accept:

3.1.1. The key is a sequence of eight elements in the size in 32 bits everyone. We will designate further a symbol To, and elements from which it consists – k1, k2, k3, k4, k5, k6, k7, k8.

           3.1.2 Table of replacements – a matrix from eight lines and sixteen columns, further – Hij. Each element on crossing of a line i and a column j occupies 4 bits.

3.2 Basic step криптопреобразования

           The basic action in the course of enciphering is – the basic step криптопреобразования. It anything other as action on enciphering of the data on certain algorithm, only developers have entered the name painfully bulky :).

           Before to start to cipher, the block break on two parts L and R, on 32 bits everyone. Choose an element of a key and only these two parts of the block, an element of a key then submit the table of replacements to function of the basic step, the result of the basic step is one iteration of a base cycle of which it will be a question in following point. The basic step consists of following actions:

1. Addition block R part is summarised with an element of key K on mod 2³². About similar operation I have described above, here too most only an exponent not «4», but «32» - result of this operation I will designate further Smod.
2. Result Smod received earlier we divide into four bit elements s7, s6, s5, s4, s3, s2, s1, s0 and we submit to replacement function. Replacement occurs as follows: element Smod - s_i gets out, from the beginning is begun with a younger element, and we replace with value from the table of replacements on i - to that line and a column in which specifies value of an element s_i. We pass to s_i+1 to an element both we arrive similarly and it is continued so, yet we will not replace value of last element Smod – result of this operation we will designate as, Ssimple.
3. In this operation value Ssimple it is shifted cyclically to the left on 11 bits and it is received Srol.
4. We choose the second part of block L and it is put on mod 2 with Srol, as a result it is had Sxor.
5. At this stage block L part becomes equal to value of part R, and part R is in turn initialized by result Sxor and on it function of the basic step is finished!

3.3 Base cycles: "32-Z", "32-R".

           To cipher the information it is necessary to break it into blocks in the size in 64 bits, be natural last block can less than 64 bits. This fact is an Achilles' heel of the given method «simple replacement». As its addition to 64 bats is very important problem on increase криптостойкости шифрограммы and to this sensitive place if it is present at an information file, and it can and not to be (for example, a file in the size in 512 byte!), it is necessary to concern with the big responsibility!

           After you have broken the information into blocks, it is necessary to break a key into elements:

K = k1, k2, k3, k4, k5, k6, k7, k8

           Enciphering consists in use, so-called – base cycles. Which in turn include n – ое quantity of the basic steps криптопреобразования.

           Base cycles have, as though it to tell, marks: n – m. Where n – the quantity of the basic steps криптопреобразования in a base cycle, and m is "type" of a base cycle i.e. about what there is a speech, about «З» ашифровывании or «Р» асшифровывании the data.

           The base cycle of enciphering 32-Z consists of 32 basic steps криптопреобразования. To function realising step actions are submitted by block N and a key element To and, the first step occurs with к1, the second over the received result to an element к2 etc. under the following scheme:

k1,k2,k3,k4,k5,k6,k7,k8,k1,k2,k3,k4,k5,k6,k7,k8,k1,k2,k3,k4,k5,k6,k7,k8k8,k7,k6,k5,k4,k3,k2,k1

           Deciphering process 32-R occurs similarly, but key elements move in return sequence:

k1,k2,k3,k4,k5,k6,k7,k8,k8,k7,k6,k5,k4,k3,k2,k1,k8,k7,k6,k5,k4,k3,k2,k1,k8,k7,k6,k5,k4,k3,k2,k1

Practice.

4.1 Realization of the basic step криптопреобразования

        After we have got acquainted with the theory how to cipher the information has come to look, as there is an enciphering in practice.

Initial data:

           We take the block of information N = 0102030405060708h, here parts L and R are equal:

L = 01020304h, R =05060708h, we take a key:

K = ‘ as28zw37q8397342ui238e2twqm2ewp1 ’ (it ASCII – codes to look hexadecimal representation, it is possible to open this file in a viewing mode in Total Commander having pressed a key «F3» and further a key «3»). Herein values of elements will be:

k1 = ‘ as28 ’, k2 = ‘ zw37 ’, k3 = ‘ q839 ’, k4 = ‘ 7342’

k5 = ‘ ui23 ’, k6 = ‘ 8e2t ’, k7 = ‘ wqm2 ’, k8 = ‘ ewp1’

Also we take the following table of replacements:

Fig. 3

Here lines are numbered from 0 to 7, columns from 0 to F.

The prevention: All information including a key with the table of replacements it is taken as an example for algorithm consideration!

Problem:

Using «the Initial data», it is necessary to receive result of action of the basic step криптопреобразования.

The decision:

1. We choose part R = 05060708h and a key element k1 = ‘ as28 ’, in a hexadecimal kind the key element will look so: 61733238h. Now we do summation operation on mod 2³²:

Fig. 4

Apparently in drawing we did not have a carrying over to 33 bits marked with red colour and to an exponent «32». And if we would have other values R and a key element is quite could occur, and then we would ignore it, and further used only the bits marked with yellow colour.

        I carry out such operation by an assembler command add:

           ; eax = R, ebx = ‘ as28’

           add eax, ebx

           ; eax = Smod

Result of this operation Smod = 66793940h

2. Now the most intricate operation but if to look narrowly on more attentive, it not so such terrible as it seems at first. We will present Smod in a following kind:

Fig. 5

I have tried to present visually elements Smod in drawing, but all the same I will explain:

s0 = 0, s1 = 4, s2 = 9 etc.

Now since a younger element s0, we make replacement. Recollecting point «3.2 Basic step криптопреобразования» i Yo - a line, s_i – a column, we search in a zero line and a zero column for value:

Fig. 6

Thus, current value Smod, not 66793940h, and 66793945h.

We start to replace s1, i.e. the four. Using the first line and the fourth column (s1 = 4!). We look at drawing:

Fig. 7

Already value Smod, not 66793945h, 66793925h. I assume that now the algorithm of replacement to the reader is clear, and I can tell that after end result Ssimple will have following value – 11e10325h.

About how it most easier to realise in the form of commands of the assembler I I will tell later in following point after I will tell about the expanded table.

2. We should shift received value Ssimple on 11 bits to the left.

Fig. 8

Apparently this action simple enough, also is realised by one command of language of the assembler – rol and the result of this operation Srol is equal 0819288Fh.

4. Now there is part L of our block of the information поXORить with value Srol. I take the calculator from w2k sp4 and I receive Sxor = 091b2b8bh.

5. Total and we simply appropriate this action, clean R value of part L, and part L we initialize value Sxor.

End result:

L = 091b2b8bh, R = 01020304h

4.2 Increases in speed of algorithm

        Now we will talk about algorithm optimisation on speed. At process of realisation what or the project, it is necessary to consider that the program which works with registers more often, than with memory works most faster here again this judgement too very important, since over one block of the information of the whole 32 actions of encoding!

           When I realised algorithm of enciphering in the program, I have arrived as follows:

1.     Has chosen block L part in the register eax, and R in edx.

2.     In the register esi initialized the address of the expanded key, about it more low.

3.     In the register ebx appropriated value of the address of the expanded table of replacements, about it too more low

4.     Handed over the information of points 1,2, 3 in function of a base cycle 32 – З or 32 – Р, depending on a situation.

Studying algorithm of enciphering, and, further realising, it I have faced difficulty of giving of elements of a key in function of a base cycle. But I have solved a problem by means of transformation of a key to the expanded.

If to look at the scheme of giving of elements of a key in point «Base cycles:“ 32-Z "," 32-R ”» for a base cycle 32 – З it is possible to present our key in the following:

К_32-З = жas28Т,жzw37Т,жq839Т,С7342Т,жui23Т,С8e2tЖ,жwqm2Т,жewp1Т,

жas28Т,жzw37Т,жq839Т,С7342Т,жui23Т,С8e2tЖ,жwqm2Т,жewp1Т,

жas28Т,жzw37Т,жq839Т,С7342Т,жui23Т,С8e2tЖ,жwqm2Т,жewp1Т,

жewp1Т,жwqm2Т,С8e2tЖ,жui23Т,С7342Т,жq839Т,жzw37Т,жas28Т

I.e. from the beginning go k1, k2, k3, k4, k5, k6, k7, k8 - ‘ as28 ’, ‘ zw37 ’, ‘ q839 ’, ‘ 7342 ’, ‘ ui23 ’, ‘ 8e2t ’, ‘ wqm2 ’, ‘ ewp1 ’ three times this sequence repeats. Then elements go upside-down, i.e.: k8, k7, k6, k5, k4, k3, k2, k1 - ‘ ewp1 ’, ‘ wqm2 ’, С8e2tЖ,жui23Т,С7342Т,жq839Т,жzw37Т,жas28Т.

I have arranged in advance in a file elements in that order as they should move in 32 – I have increased the memory demanded on a turn-key basis, but have relieved myself of some processes of thinking which were not necessary to me, and have increased speed of work of algorithm, at the expense of reduction of time of the reference to memory! Here I have described only a key for 32 – З, for a cycle 32 – Р I have arrived similarly, but using other scheme of giving of elements which I too described in point «Base cycles:“ 32-Z "," 32-R ».

           Time has come to describe realisation of work of function of replacements as I promised above. I could not describe earlier since it demands input of new concept – the expanded table of replacements. I cannot explain you that this such. Instead I will show you it, and you formulate for myself, what this such – the expanded table of replacements?

           So, to understand that such the expanded table of replacements is required to us the table of replacements, for an example I will take that that is represented on fig. 3.

           For example, we needed to replace, number 66793940h. I will present it in a following kind:

Fig. 9

Now if to take elements s1, s0, i.e. younger byte the result of function of replacement will be equal 25h! Почитав Andrey Vinokurova's article which I have resulted in point «the List used the literature», you really will find out that if to take two lines it is possible to receive a file allowing quickly to find elements of replacement by means of a command of the assembler xlat. Speak it is possible and in another way for faster, but Andrey Vinokurov has spent for research of fast algorithms for realisation STATE THAT about four years! I think, it is not necessary to invent a bicycle when it already is.

           So, about a file:

We take the two first lines zero and the first, we will create a file on 256 byte. Now we observe one feature that if it is necessary to transform 00h the result will be 75h (we lean against fig. 3) – we put this value in a file on displacement 00h. We take value 01h, result of function of replacements 79h, we put it in a file on displacement 01 and so on to 0FFh which will give to us 0FCh which we will put in a file on displacement 0FFh. Here we also have received the expanded table of replacements for the first group of lines: the first and zero. But still there are three groups: the second p. 2, p. 3, the third p. 4, p. 5, the fourth p. 6, p. 7. With it three groups we arrive in the same way, as with the first. Result – the expanded table of replacements!

           Now it is possible to realise algorithm which will make replacement. For this purpose we take initial codes which were laid out by Andrey Vinokurov on the page, look «the List of the used literature».

           lea ebx, extented_table_simple

           mov eax, [to put number which it is necessary to replace]

REPT 3

           xlat

           ror eax, 8d

           add ebx, 100h  ; transition to two following knots

ENDM

           xlat

           sub ebx, 300h  ; that further ebx showed on the table

Now one more feature, we not only have replaced with the previous actions, but also have shifted number on 8 bits to the left! We need to shift only number on 3 bits to the left:

rol eax, 3h

And we receive result of operation rol eax, 11!

           I am more I can add than nothing on optimisation, the only thing that I can underline that I spoke above – use registers more often, than the reference to memory. I think these words only for beginners, skilled and without my words it perfectly understand :).

Requirements to the key information.

           As it is told in Andrey Vinokurova's article a key choose by two criteria:

- Criterion of equiprobable distribution of bits between values 1 and 0. Usually as criterion of equiprobable distribution of bits – the criterion Pirsona ("hi-square") acts.

It means a key, any number basically can. That is at formation of the next bit of a key probability of its initialization unit or in zero 50/50!

I ask to notice that a key from eight elements, everyone on 32 bits, thus all in a key 32*8 = 256 bits and quantity of possible keys 2²⁵⁶! It amazes you? :)

- Criterion of series.

           If we look at our key which I have resulted in point «4.1 Realization of the basic step криптопреобразования» you will notice that the following record is fair:

Fig. 10

One phrase value k₁ should not repeat not in k₂, not in what or other element of a key.

That is the key which we have chosen as consideration of algorithm of enciphering, quite corresponds to two criteria resulted above.

Now about a choice of the table of replacements:

Now we will talk how correctly to choose the table of replacements. The basic requirement to a choice of tables of replacements is the phenomenon «неповторяемости» elements, each of which in the size in 4 bits. As you already saw above, each line of the table of replacements consists of values 0h, 1h, 2h, 3h, …, 0fh. And so the basic requirement says that in each line there are values 0h, 1h, 2h, …, 0fh and each such value in one copy. For example, sequence:

1 2 3 4 5 6 7 8 9 A B C D E F

Quite corresponds to this requirement, but nevertheless! As a line it is not recommended to choose such sequence. As if you will submit value on an input of function which leans for such line on an exit you receive the same value! Do not trust? Then take number 332DA43Fh and such eight lines, as the table of replacements. Perform replacement operation, and I assure you, on an exit you receive number 332DA43Fh! That is same that you have submitted on an operation input! And it is not a good form sign at enciphering, and whether was? :)

It was one requirement, the following criterion says that – each bit of an output block should be statistically independent of each bit of the entrance block!

How it looks easier? And here is how, for example, we have chosen from resulted above number an element s0 = 0Fh, 01111b. Probability of that we now will replace the first bit with unit or zero is equal 0,5! Probability of replacement of the second, third and fourth bit, each bit, we consider separately, units or in zero too it is equal 0, 5. At a choice s1 = 0Eh, probability of that we the zero bit, and is «0», we will replace with zero or unit too is equal – 0,5! Thus, according to this criterion between replacement of zero bits of elements s0, s1 there is no law! Yes, you could replace with units, but you also could put and zero. :)

For a table estimation by this criterion it is possible to construct the table of factors the correlations calculated under the formula:

Where

0≤i≤3

0≤j≤3

N=4

- If p = 1, value of bit j on an exit to equally value of bit i on an input at any combinations of bats on an input;

- If p =-1 value of bit j on an exit always is inversion of entrance bit i;

- If p = 0 the target bit j with equal probability accepts values 0 and 1 at any fixed value of entrance bit i.

We will follow an example of one line:

Let's spread out to "components":

Input

Exit

Let's calculate one factor under the formula resulted above. That it was easier to understand, how it becomes, I will explain in more details:

- We take 0th bit of 0th (0) on an input and 0th bit of 0th on an exit (1) we perform operation 0 XOR 1 = 1.

- We take 0th bit of 1st (1) on an input and 0th bit of 1st on an exit (1) we perform operation 1 XOR 1 = 0.

- We take 0th bit of 2nd (0) on an input and 0th bit of 2nd on an exit (0) we perform operation 0 XOR 0 = 0.

- We take 0th bit of 3rd (1) on an input and 0th bit of 3rd on an exit (1) we perform operation 1 XOR 1 = 0.

… ….

Having performed consistently operations XOR in such sequence, we count up quantity of all nonzero values, we receive value 6. From here P₀₀ = 1 (6/2^4-1) = 0,25. So, it was found out that value of bit 0 on an exit to equally value of bit 0 on an input in 4 cases from 16;

The total table of factors:

Apparently from the table of correlation factors of bats 3 on an input it is inverted concerning bit 0 on an exit in 14 cases from 16 that makes 87.5 % Here it is not admissible not so for normal systems of enciphering. For a change we take still примерчик:

The table of factors will be following (to whom it is not lazy can to count)

Well, in this table of business are even worse – bits of 1 and 2 groups remain invariable! Криптоаналитику is where to be developed Taking into account :) all these requirements by simple search («in a forehead») shift tables corresponding to the specified theory (for today – 1276 combinations) Here some of them have been found:

The list of the used literature.

1. Andrey Vinokurova's article:

Algorithm of enciphering of GOST 28147-89, its use and realisation

For computers of platform Intel x86.

(It is possible to find to the address: http://www.enlight.ru/crypto/frame.htm).

There and then and initial codes, by realisation of algorithm of enciphering.

2. Article of Horsta Fajstelja:

Cryptography and Computer safety.

(It is possible to find to the same address as the previous article)

3. Ross N. Williams:

Elementary management on CRC to algorithms of detection of errors

It is laid out on a site www.wasm.ru.

Thanks.

           It would be desirable to express gratitude to all visitors of a forum www.wasm.ru. But especially it would would be desirable to thank ChS which is at the moment known, as SteelRat, he has helped me to understand such things that I, probably, never would understand, and as the help at a point writing: «Requirements to the key information», the basic the part of the given point has been written them. Also it is deeply grateful to employee КГТУ of A.N.Tupolev and a sin that he is and Volodya / wasm.ru for its manuals would be not to notice Chris Kasperski. Oh, also gets to me from it :). As I wish to notice Sega-Zero / Callipso but that has informed to my reason some mathematical jungle.

It, perhaps, everything that I would like to tell to you.

I will be, it is grateful for criticism or the questions connected with this article or it is simple councils. My contact data: int20h@yandex.ru, ICQ – 337310594.

Yours faithfully Evil ` s Interrupt.

+ P.S.: this article I did not try to outdo someone. It has been written intentionally, to facilitate studying STATE THAT and if at you difficulties it does not mean have turned out that I am guilty in it. Be are reasonable, and have patience, all to you kind!