Andrey Vinokurov.

Algorithm of enciphering of GOST 28147-89, its use and realisation for computers of platform Intel x86.

Article brought to your attention contains the description of the algorithm accepted as the standard of enciphering in the Russian Federation and its realisation for processors of family Intel x86, and also discussion of various questions of its practical use. The part of the materials which have entered into given article, has been published in magazine "Monitor" №1,5 in 1995.

The maintenance

Instead of the preface...................................................................................................................... 2

1. The algorithm description.................................................................................................................

1.1. Terms and designations.....................................................................................................

1.2. Logic of construction of the code number and structure of the key information STATE THAT.......................

1.3. The basic step криптопреобразования.............................................................................

1.4. Base cycles of cryptographic transformations.....................................................

1.5. The basic modes of enciphering.......................................................................................

2. Discussion of cryptographic algorithms STATE THAT..........................................................

2.1. STATE THAT cryptographic firmness............................................................................

2.2. Remarks on architecture STATE THAT...................................................................................

2.3. Requirements to quality of the key information and sources of keys.........................

3. Remarks on realisation.......................................................................................................

3.1. Three steps of optimisation.....................................................................................................

3.2. The description of functions and feature of realisation............................................................

3.3. A speed question...................................................................................................

4. Questions of use of the standard........................................................................................

4.1. Reliability of realisation...................................................................................................

4.2. Variations on a theme STATE THAT................................................................................................

4.3. Unusual work of cryptographic scale...............................................................

Instead of the preface.

That the information has value, people have realised very much for a long time – not without reason correspondence of the mighty of this world long since was object of steadfast attention of their foes and friends. Then there was a problem of protection of this correspondence from excessively curious eyes. Ancient tried to use for the decision of this problem the diversified methods, and one of them was тайнопись – ability to make the message so that its sense was inaccessible to anybody except let into a secret. There are certificates to that art тайнописи has arisen still in доантичные times. Throughout all centuries-old history, up to absolutely recent time, this art served the little, basically to a society top, without falling outside the limits residences of heads of the states, embassies and – is final! – prospecting missions. And several decades ago all has changed radically – the information has got independent commercial value and became widespread, almost usual goods. It make, store, transport, sell and buy, so – steal and forge – and, hence, it is necessary for protecting. The modern society all in a greater degree becomes information-caused, the success of any kind of activity all depends on possession certain data and from their absence at competitors more strongly. And the the specified effect, the more potential losses from abusings in information sphere is more strongly shown, and the it is more requirement for information protection. In a word, occurrence of the industry of processing of the information with iron necessity has led to occurrence of the industry of protection frames of the information.

Among all spectrum of methods of protection of the data from undesirable access the special place is occupied with cryptographic methods. Unlike other methods, they lean only against properties of the information and do not use property of its material carriers, feature of knots of its processing, transfer and storage. Speaking in images, cryptographic methods build a barrier between the protected information and the real or potential malefactor of the information. Certainly, under cryptographic protection first of all – so has developed historically – enciphering of the data is meant. Earlier when this operation it was carried out by the person manually or with use of various adaptations, and at embassies populous departments шифровальщиков contained, cryptography development restrained a problem of realisation of code numbers, after all it was possible to think up anything you like but as it to realise … the Occurrence of the digital electronic computers which have led finally to creation of the powerful information industry, has changed all radically and in this sphere. On the one hand, burglars of code numbers have received extremely powerful tool in the hands, on the other hand, the barrier of complexity of realisation has disappeared and for founders of code numbers almost boundless prospects have opened. All it has defined prompt progress of cryptography last decades.

As any state respecting, the Russian Federation has the standard of enciphering. This standard is fixed STATE VOLUME №28147-89, accepted as appears from its designation, in 1989 in the USSR. However, undoubtedly, history of this code number much older. The standard was born presumably in bowels of the eighth central administrative board of KGB of the USSR transformed nowadays in Federal agency for government communication and information. I could talk to the people asserting that else in the seventies they participated in projects of creation of program and hardware realisations of this code number for various computer platforms. In those days it had a signature stamp �Owls. Confidentially�, later the signature stamp has been changed on confidential", then removed absolutely. On my copy STATE THAT stood only modest mark�ДСП�. Unfortunately, unlike the standard, the history of its creation and criteria of designing of the code number remain till now secret behind seven seals.

Possible use STATE THAT in your own workings out puts some question. The question the first – whether is not present legal obstacles for this purpose. The answer here idle time – such obstacles is not present also you can freely use GOST, it is not patented, hence, there is nobody to ask permissions. Moreover, you have on this full moral right as successors of those who has paid working out of the standard from the pocket, – first of all I have in view of your parents. №334 from 03.04.95 and the corresponding governmental orders of anything new do not bring the known decree of the President of Russia in this picture. Though they formally also forbid the system engineering, containing means криптозащиты legal and the physical persons who do not have the licences for this appearance of activity, but really the decree extends only on a case of the state secrets given, making bank secret, etc., say, it operates only there where the piece of paper is necessary that �the data is protected�.

Well, with competency of application STATE THAT have understood, now we will stop on an expediency question – first of all, whether we can trust this generation of gloomy Lubjanki, whether security officers of openings companions have built in algorithms of enciphering? It is rather improbable, as GOST was created in those days when its use outside of the state regime objects was impossible. On the other hand, it is impossible to confirm firmness of cryptographic algorithm, it can be denied only breaking. Therefore, the the algorithm is more senior, the it is more than chances that if it is not cracked till now, it will not be cracked and in the nearest foreseeable future. In this light all conversations on the last �original workings out� �talented children� basically cannot be serious – each code number should sustain check by time. But after all the code numbers which have sustained similar check, obviously more than one – except STATE THAT after all is also DES, its senior American brother, is also other code numbers. Why then GOST? Certainly, in many respects this business of personal predilections, but it is necessary to remember also that GOST surpasses all these algorithms in the majority of parametres, including DES. And, eventually, where our Russian Patriotism?!

To wide use STATE THAT in workings out of the Russian programmers disturbs, in my opinion, a lack of the published information on it, and also the certain aura of the mystery which has developed round it and is skilful someone supported. Actually anything difficult in the code number is not present, it is accessible to understanding and realisation to the programmer of any level, but, as well as in all other, for creation of really good realisation it is necessary to be the professional. I worked about STATE VOLUME as the programmer with 91 for 94 year, and in this time at me it has turned out rather successful (well as itself not to praise!) its program realisation for family Intel processors x86, coming nearer on speed to a possible optimum.

The purpose of present article is acquaintance of all interested with algorithm and its realisation on platform Intel x86. STATE THAT I give the realisation developed by me in a public property, everyone can use it under condition of the reference to my authorship. The text of present article can extend beyond all bounds in a printing and electronic kind in that and only in the event that it is not interfaced expressly or by implication to profit extraction, my written permission otherwise is required.

Article consists of four parts. The first part contains the description, and the second – algorithm discussion, the third and fourth parts contain accordingly the description of its realisation and discussion of some aspects of its application. So, we will begin...

1. The     algorithm description.

1.1.     Terms and designations.

The description of the standard of enciphering of the Russian Federation contains in very interesting document entitled �Algorithm of cryptographic transformation of given GOST 28147-89�. That instead of the term "enciphering" appears in its name the more general concept �cryptographic transformation�, not so casually. Besides the several procedures of enciphering closely connected among themselves, in the document one is described constructed on the general principles with them algorithm of development имитовставки. Last is not than other, as a cryptographic control combination, that is a code developed from the initial data with use of a confidential key on purpose имитозащиты, or protection of the data against entering into them of unapproved changes.

On various steps of algorithms STATE THAT the data with which they operate, are interpreted and used in the various image. In certain cases elements of the data are processed as files of independent bits, in other cases – as an integer without a sign, in the third – as a difficult element having structure consisting of several more simple elements. Therefore in order to avoid mess it is necessary to agree about used designations.

Elements of the data in given article are designated by header Latin letters with an inclined tracing (for example, X). Through |X | the size of an element of the data X in bits is designated. Thus, if to interpret an element of the data X as the whole non-negative number, it is possible to write down a following inequality: 0�X <2^{|X |}.

If the element of the data consists of several elements of the smaller size this fact is designated as follows: X = (X₀, X₁..., X_n-1) = X₀ || X₁ ||... || X_n-1. Procedure of association of several elements of the data in one is called конкатенацией the data and is designated by a symbol ||. Naturally, for the sizes of elements of the data the following parity should be carried out: |X | = | X₀ | + | X₁ | +... + |X_n-1 |. At the task of difficult elements of the data and operation конкатенации making elements of the data are listed in ascending order a seniority. Differently, if to interpret a component and all elements of the data entering into it as integers without a sign it is possible to write down following equality:

In algorithm the element of the data can be interpreted as a file of separate bits, in this case bits the file, but in a lower case variant, as is shown in a following example is designated by the same letter, as:

X = (x₀, x₁..., x_n–1) = x₀+2¹�x₁ +... +2ⁿ–1�x_n–1.

If over elements of the data some operation having logic sense it is supposed is carried out that the given operation is carried out over corresponding bits of elements. Differently A•B = (a₀•b₀, a₁•b₁..., a_n-1•b_n-1) where n = | A | = | B |, and the symbol “•” designates any binary logic operation; as a rule, there is in view of operation excluding or, it – summation operation on the module 2: a�b = (a+b) mod 2.

1.2.     Logic of construction of the code number and structure of the key information STATE THAT.

If attentively to study the original STATE THAT 28147–89, it is possible to notice that in it the description of algorithms of several levels contains. On the uppermost there are the practical algorithms intended for enciphering of data files and development to them имитовставки. All of them lean against three algorithms of the lowest level named in the text STATE THOSE cycles. These fundamental algorithms are mentioned in given article as base cycles to distinguish them from all other cycles. They have following names and designations, the last are resulted in brackets and their sense will be explained later:

� a      cycle зашифрования (32-Z);

� a      cycle расшифрования (32-R);

�      a development cycle имитовставки (16-Z).

In turn, each of base cycles represents repeated repetition of the unique procedure named for definiteness further in the present work the basic step криптопреобразования.

So that to understand the VISITOR, it is necessary to understand three following things:

What is the basic step криптопреобразования;

As of the basic steps there are base cycles;

As of three base cycles there are all practical algorithms STATE THAT.

Before to pass to studying of these questions, it is necessary to talk about the key information used by algorithms STATE THOSE. According to a principle of Kirhgofa to which satisfy all modern code numbers known to the wide public, its privacy provides privacy of the ciphered message. In the VISITOR the key information consists of two structures of the data. Besides actually key necessary for all code numbers, it contains also the table of replacements. The basic characteristics of key structures STATE THAT are more low resulted.

1. The key is a file from eight 32-bit elements of a code, further in the present work it is designated by symbol К:. In the VISITOR key elements are used as 32-bit integers without a sign:. Thus, the size of a key makes 32�8=256 bit or 32 bytes.

2. The table of replacements is a matrix 8'16, containing 4-bit elements which it is possible to present in the form of integers from 0 to 15. Lines of the table of replacements are called as knots of replacements, they should contain various values, that is each knot of replacements should contain 16 various numbers from 0 to 15 in any order. In the present article the table of replacements is designated by symbol H:. Thus, the total amount of the table of replacements is equal: 8 knots � 16 elements/knots � 4 bat/element = 512 bits or 64 bytes.

1.3. The     basic step криптопреобразования.

The basic step криптопреобразования inherently is the operator defining transformation of the 64-bit block of the data. Additional parametre of this operator is the 32-bit block in which quality any element of a key is used. The scheme of algorithm of the basic step is resulted in drawing 1. Explanatories to algorithm of the basic step are more low given:

��� 0.         Defines the initial data for the basic step криптопреобразования:

�                          N – преобразуемый the 64-bit block of the data, during performance of its step younger (N₁) and senior (N₂) parts are processed as separate 32-bit integers without a sign. Thus, it is possible to write down N = (N₁, N₂).

�                          X – a 32-bit element of a key;

��� 1.         Addition with a key. The younger half преобразуемого the block develops on the module 2³² with an element of a key used on a step, the result is transferred to the following step;

��� 2.         Block replacement. 32-bit value received on the previous step, is interpreted as a file from eight 4-bit blocks of a code: S = (S₀, S₁, S₂, S₃, S₄, S₅, S₆, S₇).

Further value of each of eight blocks is replaced on new which gets out under the table of replacements as follows: value of block S_i is replaced on S_i-tyj one after another an element (numbering from zero) i knots of replacements (i.e. i lines of the table of replacements, numbering also from zero). In other words, as replacement for value of the block the element gets out of the table of replacements with a line number equal to number of the replaced block, and number of a column equal to value of the replaced block as 4-bit whole non-negative number. Now there is clear a size of the table of replacements: the number of lines in it is equal to number of 4-bit elements in the 32-bit block given, that is eight, and number of columns to equally number of various values of the 4-bit block of the data, equal as it is known 2⁴, sixteen.

Fig. 1. The scheme of the basic step криптопреобразования algorithm of GOST 28147-89.

��� 3.         Cyclic shift on 11 bits to the left. The result of the previous step moves cyclically on 11 bits towards the senior categories and is transferred to the following step. On the scheme of algorithm symbol Q₁₁ designates function of cyclic shift of the argument on 11 bits towards the senior categories.

��� 4.         Bit-by-bit addition: the value received on a step 3, побитно develops on the module 2 with the senior half преобразуемого the block.

��� 5.         Shift on a chain: the younger part преобразуемого the block moves to the place of senior, and on its place the result of performance of the previous step is located.

��� 6. The         received value преобразуемого the block comes back as result of performance of algorithm of the basic step криптопреобразования.

1.4.     Base cycles of cryptographic transformations.

As it is noted in the beginning of present article, GOST belongs to the class of block code numbers, that is unit of processing of the information in it is the block of the data. Hence, it is quite logical to expect that in it algorithms for cryptographic transformations, that is for зашифрования, расшифрования and "account" in a control combination of one block of the data will be defined. These algorithms also are called as base cycles that underlines their fundamental value for construction of this code number.

Base cycles are constructed of the basic steps of the cryptographic transformation considered in the previous section. In the course of performance of the basic step one element of a key while GOST key contains such eight elements is used only. Hence, that the key has been used completely, each of base cycles should carry out repeatedly the basic step with its various elements. At the same time it seems quite natural that in each base cycle all elements of a key should be used identical number of times, for reasons of firmness of the code number this number should be more than one.

All made above the assumption, leaning simply on common sense, have appeared true. Base cycles consist in repeated performance of the basic step with use of different elements of a key and differ from each other only number of repetition of a step and order of use of key elements. This order for various cycles is more low resulted.

1. A   cycle зашифрования 32-Z:

K₀,K₁,K₂,K₃,K₄,K₅,K₆,K₇,K₀,K₁,K₂,K₃,K₄,K₅,K₆,K₇,K₀,K₁,K₂,K₃,K₄,K₅,K₆,K₇,K₇,K₆,K₅,K₄,K₃,K₂,K₁,K₀.

2. A   cycle расшифрования 32-R:

K₀,K₁,K₂,K₃,K₄,K₅,K₆,K₇,K₇,K₆,K₅,K₄,K₃,K₂,K₁,K₀,K₇,K₆,K₅,K₄,K₃,K₂,K₁,K₀,K₇,K₆,K₅,K₄,K₃,K₂,K₁,K₀.

3.   A development cycle имитовставки 16-Z:

K₀,K₁,K₂,K₃,K₄,K₅,K₆,K₇,K₀,K₁,K₂,K₃,K₄,K₅,K₆,K₇.

Each of cycles has own alphanumeric designation corresponding to a template �n-X� where the first element of a designation (n), is set by number of repetitions of the basic step to a cycle, and the second element of a designation (X), the letter, sets an order зашифрования (�З�) or расшифрования (�Р�) in use of key elements. This order requires the additional explanatory:

The cycle расшифрования should be the return to a cycle зашифрования, that is consecutive application of these two cycles to any block should give as a result the initial block that is reflected by a following parity: Ц_32-Р (Ц_32-З (T)) =T, where T – any 64-bit block of the data, Ц_X (T) – result of performance of a cycle X over the block of data T. For performance of this condition for the algorithms, similar STATE THAT, it is necessary and enough that the order of use of key elements corresponding cycles was mutually the return. For a considered case it is easy to be convinced of justice of the written down condition, having compared resulted above sequence for cycles 32-� � 32-�. One interesting consequence follows From the told: property of a cycle to be the return to other cycle is mutual, that is the cycle 32-Z is the return in relation to a 32-river cycle In other words, зашифрование the block of the data can be theoretically executed by means of a cycle расшифрования, in this case расшифрование the block of the data should be executed a cycle зашифрования. From two it is mutual return cycles any can be used for зашифрования then the second should be used for расшифрования the data, however standard ГОСТ28147-89 fixes roles to cycles and does not give to the user of the option in this question.

аааааааааааааааааааааа Fig. 2а. The cycle scheme зашифрования 32-Z. A Fig. 2б. The cycle scheme расшифрования the 32-river

The development cycle имитовставки is twice shorter than enciphering cycles, an order of use of key elements in it same as in the first 16 steps of a cycle зашифрования of what it is easy to be convinced, having considered resulted above sequence, therefore this order in a cycle designation is coded by the same letter �З�.

Fig. 2в. The scheme of a cycle of development имитовставки 16-Z.

Schemes of base cycles are resulted in drawings of 2a-century Each of them accepts as argument and returns the 64-bit block of the data designated on schemes N as result. Symbol Ш�� (N, X) designates performance of the basic step криптопреобразования for block N with use of a key element X. Between enciphering and calculation cycles имитовставки there is one more difference which has been not mentioned above: in the end of base cycles of enciphering the senior and younger part of the block of result are interchanged the position, it is necessary for their mutual convertibility.

 

1.5. The     basic modes of enciphering.

GOST 28147-89 provides three following modes of enciphering of the data:

�      simple replacement,

�      гаммирование,

�      гаммирование with a feedback,

And one additional mode of development имитовставки.

In any of these modes the data is processed by blocks on 64 bits into which the file subjected to cryptographic transformation for this reason GOST concerns block code numbers breaks. However in two modes гаммирования there is a possibility of processing of the incomplete block given in the size less than 8 byte that is essential at enciphering of data files with any size which can be not to multiple 8 bytes.

Before to pass to consideration of concrete algorithms of cryptographic transformations, it is necessary to explain the designations used on schemes in following sections:

T_о, T_ш – files of accordingly open and ciphered data;

, – I one after another 64-bit blocks of accordingly open and ciphered data: 1�i�n, last block can be incomplete:;

n – number of 64-bit blocks in data file;

Ц_X – function of transformation of the 64-bit block of the data on algorithm of a base cycle �X�;

Now we will describe the basic modes of enciphering:

1.     Simple replacement.

Зашифрование in the given mode consists in cycle application 32-Z to blocks of the open data, расшифрование – a cycle 32-R to blocks of the ciphered data. It is most simple of modes, 64-bit blocks of the data are processed in it independently from each other. Schemes of algorithms зашифрования and расшифрования in a mode of simple replacement are resulted in drawings 3а and accordingly, they are trivial and do not require comments.

The size of a file of the open or ciphered data, exposed accordingly зашифрованию or расшифрованию, should be multiple to 64 bits: |T_о | = | T_ш | = 64�n, after performance of operation the size of the received data file does not change.

The mode of enciphering by simple replacement has following features:

1.   As blocks of the data are ciphered independently from each other and from their position in a file, at зашифровании two identical blocks of a clear text identical blocks шифротекста and on the contrary turn out. Noted property will allow криптоаналитику to make the conclusion about identity of blocks of the initial data if in a file of the ciphered data to it there were identical blocks that is inadmissible for the serious code number.

2.   If the length of the ciphered data file is not multiple to 8 bytes or 64 bits, there is a problem than and how to supplement last incomplete block of the data of a file to full 64 bats. This problem not so is simple, as it seems at first sight as obvious decisions of type �to add the incomplete block in zero bits� or, more обще, �to add the incomplete block with the fixed combination of zero and individual bits� can yield under certain conditions криптоаналитика possibility search methods to define contents of this most incomplete block, and this fact means decrease in firmness of the code number. Besides, the length шифротекста thus will change, having increased to the nearest whole, multiple 64 bits that often happens undesirable.

At first sight, listed above feature do almost impossible use of a mode of simple replacement, after all it can be applied only to enciphering of data files with a size to the multiple 64 bits which are not containing repeating 64-bit blocks. It seems that for any real given to guarantee performance of the specified conditions it is impossible. It almost so, but is one very important exception: recollect that the size of a key makes 32 bytes, and the size of the table of replacements – 64 bytes. Besides, presence of repeating 8-byte blocks in a key or the table of replacements will speak about their rather bad quality, therefore in real key elements of such repetition cannot be. Thus we have found out that the mode of simple replacement quite approaches for enciphering of the key information as other modes are less convenient for this purpose as demand presence of an additional synchronising element of the data – синхропосылки (the following section see). Our guess is true, GOST orders to use a mode of simple replacement only for enciphering of the key data.

2.     Гаммирование.

How it is possible to get rid of lacks of a mode of simple replacement? For this purpose не�обходимо to make possible enciphering of blocks with a size less than 64 bats and to provide dependence of the block шифротекста from its number, otherwise, рандомизировать enciphering process. In the VISITOR it is reached in two various ways in two modes of enciphering providing гаммирование. Гаммирование is an imposing (removal) on the open (ciphered) data of cryptographic scale, that is sequence of elements of the data developed by means of some cryptographic algorithm, for reception of the ciphered (open) data. For scale imposing at зашифровании and its removals at расшифровании should be used mutually return binary operations, for example, addition and subtraction on the module 2⁶⁴ for 64-bit blocks of the data. In the VISITOR for this purpose operation of bit-by-bit addition on the module 2 as it is return to herself is used and besides most simply realised. Гаммирование solves both mentioned problems; in the first, all elements of scale are various for real ciphered files and, hence, the result зашифрования even two identical blocks in one data file will be various. In the second though elements of scale also are developed in the identical portions in 64 bits, it can be used and a part of such block with the size equal to the size of the ciphered block.

Now we will pass directly to the mode description гаммирования. The scale for this mode turns out as follows: by means of some algorithmic recurrent generator of sequence of numbers (РГПЧ) 64-bit blocks of the data which are exposed further to transformation on a cycle 32-Z are developed, that is зашифрованию in a mode of simple replacement, scale blocks as a result turn out. Thanks to that imposing and scale removal is carried out by means of the same operation bit-by-bit excluding or, algorithms зашифрования and расшифрования in a mode гаммирования are identical, their general scheme is resulted in drawing 5.

РГПЧ, used for scale development, is recurrent function: W_i+1=f (W_i), where W_i – elements of recurrent sequence, f – transformation function. Hence, inevitably there is a question on its initialization, that is on element W₀. Actually, this element of the data is parametre of algorithm for modes гаммирования, on schemes it is designated as S, and is called in cryptography синхропосылкой, and in our VISITOR – as initial filling of one of registers шифрователя. For certain reasons developers STATE THAT have decided to use for initialization РГПЧ not directly синхропосылку, and result of its transformation on a cycle 32-Z: W₀=Ц_32-З (S). The sequence of the elements developed РГПЧ, entirely depends on its initial filling, that is elements of this sequence are function of number and initial filling РГПЧ: W_i=f_i (W₀), where f_i (X) =f (f_i–1 (X)), f₀ (X) =X. Taking into account transformation on algorithm of simple replacement it is added also dependence on a key:

Г_i=Ц_32-З (W_i) =Ц_32-З (f_i (W₀)) =Ц_32-З (f_i (Ц_32-З (S))) =j_i (S, K), where Г_i – i-tyj a scale element, K – a key.

Thus, the sequence of elements of scale for use in a mode гаммирования is unequivocally defined by the key data and синхропосылкой. Naturally, for convertibility of procedure of enciphering in processes for - and расшифрования it should be used same синхропосылка. From the requirement of uniqueness of the scale which default leads to catastrophic decrease in firmness of the code number, follows that for enciphering of two various data files on one key it is necessary to provide use various синхропосылок. It leads to necessity to store or transfer синхропосылку on communication channels together with the ciphered data though in separate special cases it can be predetermined or be calculated in a special way if enciphering of two files on one key is excluded.

Now we will in detail consider РГПЧ, used in the VISITOR for generation of elements of scale. First of all it is necessary to notice that demands of maintenance of any statistical characteristics are not made to it developed последователь�ности numbers. РГПЧ it is designed by developers STATE THAT proceeding from necessity of performance of following conditions:

� the      period of repetition of sequence of the numbers developed РГПЧ, not should differ (in percentage terms) strongly from greatest possible at the set size of the block of value 2⁶⁴;

� the      next values developed РГПЧ, should differ from each other in each byte, differently the problem криптоаналитика will be simplified;

�      РГПЧ should be simply enough realised as it is hardware, and программно on the most widespread types of processors the majority from which word length of 32 bits, as it is known, have.

Proceeding from the listed principles founders STATE THAT have designed rather successful РГПЧ, having following characteristics:

�      in the 64-bit block the senior and younger parts are processed independently from each other: actually, there are two independent РГПЧ for the senior and younger parts of the block.

�      recurrent parities for the senior and younger parts the following:

, Where C₁=1010101₁₆;

, Where C₂=1010104₁₆;

The bottom index in number record means its notation, thus, the constants used on the given step, are written down in 16-richnoj to a notation.

The second expression requires comments as in the text STATE THAT something is resulted another: with the same value of constant C₂. But further in the standard text the comment is given that, it appears, operation of a capture of the rest on the module 2³²–1 there is understood not as the same, as in the mathematician. Difference consists that according to STATE THAT (2³²–1) mod (2³²–1) = (2³²–1), instead of 0. Actually, it simplifies formula realisation, and математически correct expression for it is resulted above.

� the      period of repetition of sequence for a younger part makes 2³², for the senior part 2³²–1, for all sequence the period makes 2³²� (2³²–1), the proof of this fact, rather simple, receive. The first formula from two is realised for one command, the second, despite its seeming bulkiness, for two commands on all modern 32-bit processors.

The scheme of algorithm of enciphering in a mode гаммирования is resulted in drawing 4, explanatories to the scheme are more low stated:

��� 0.         Defines the initial data for the basic step криптопреобразования:

�                          T_{о ()} – a file of the open (ciphered) data of any size, subjected to procedure зашифрования (расшифрования), on a course of procedure the file is exposed to transformation by portions on 64 bits;

�                          S – �������������, a 64-bit element of the data necessary for initialization of the generator of scale;

��� 1.         Initial transformation синхропосылки, carried out for its "randomization", that is for elimination of the statistical regularities which are present at it, result is used as initial filling РГПЧ;

��� 2.         One step of work РГПЧ realising it recurrent algorithm. During the given step senior (S₁) and younger (S₀) parts of sequence of the data are developed independently from each other;

��� 3.         Гаммирование. The next 64-bit element developed РГПЧ, is exposed to procedure зашифрования on a cycle 32-Z, the result is used as an element of scale for зашифрования (расшифрования) the next block of the open (ciphered) data of the same size.

��� 4.         Result of work of algorithm – the ciphered (deciphered) data file.

Features гаммирования as enciphering mode are more low listed.

1.   Identical blocks in open data file will give at зашифровании various blocks шифротекста that will allow to suppress the fact of their identity.

2.   As scale imposing is carried out побитно, enciphering of the incomplete block of the data easily выполнимо as enciphering of bits of this incomplete block for what it is used corresponding bits of the block of scale. So, for зашифрования the incomplete block in 1 bit it is possible to use any bit from the scale block.

3.   Синхропосылка, used at зашифровании, should be somehow transferred for use at расшифровании. It can be reached following ways:

�      to keep or tell синхропосылку together with the ciphered data file that will lead to increase in the size of data file at зашифровании for the size синхропосылки, that is on 8 byte;

�      to use the predetermined value синхропосылки or to develop it synchronously a source and the receiver under the certain law, in this case change of the size transferred or хранимого data file is absent;

Both ways supplement each other, and in those rare occurences where the first does not work, most common of them, the second can be used, more exotic. The second way has much smaller application as to make синхропосылку predetermined it is possible only in the event that on the given complete set of the key information is ciphered obviously no more than one data file that happens in rare instances. To generate синхропосылку synchronously at a source and the addressee of data file also not always it is obviously possible, as demands a rigid binding to something in system. So, sensible at first sight idea to use in quality синхропосылки in system of transfer of the ciphered messages number of the transferred message does not approach, as the message can be lost and not reach the addressee, in this case will occur десинхронизация systems of enciphering of a source and the receiver. Therefore in the considered case there is no alternative to transfer синхропосылки together with the ciphered message.

On the other hand, it is possible to result and a return example. We will admit, enciphering of the data is used for information protection on a disk, and it is realised on a low level, for maintenance of independent access the data is ciphered on sectors. In this case it is impossible to store синхропосылку together with the ciphered data as the size of sector cannot be changed, however it can be calculated as some function from number of a reading out head of a disk, number of a path (cylinder) and sector number on a path. In this case синхропосылка becomes attached to sector position on a disk which hardly can change without disk reformatting, that is without destruction of the data on it.

The mode гаммирования has one more interesting feature. In this mode of a bat of data file are ciphered independently from each other. Thus, each bit шифротекста depends on the corresponding bit of a clear text and, naturally, a bit serial number in a file:. From this follows that bit change шифротекста on opposite value will lead to similar change of bit of a clear text on the opposite:

,

Where designates inverted in relation to t value of bit ().

The given property gives the chance to the malefactor influencing bits шифротекста to bring predicted and even purposeful changes in the corresponding clear text received after it расшифрования, without possessing thus a confidential key. It illustrates the well-known fact in cryptology that �privacy and authenticity an essence various properties of code numbers�. Differently, properties of code numbers to provide protection against unapproved acquaintance with contents of the message and from unapproved modification of the message are independent and only on occasion can be crossed. Told means that there are the cryptographic algorithms providing certain privacy of the ciphered data and thus in any way not protecting from modification and on the contrary, providing authenticity of the data and in any way not limiting access to them. For this reason considered property of a mode гаммирования should not be considered as its lack.

3.     Гаммирование with a feedback.

The given mode is very similar to a mode гаммирования and differs from it only in the way of development of elements of scale – the next element of scale is developed as result of transformation on a cycle 32-Z the previous block of the ciphered data, and for зашифрования the first block of data file the scale element is developed as result of transformation on the same cycle синхропосылки. It reaches gearing of blocks – each block шифротекста in this mode depends from corresponding and all previous blocks of a clear text. Therefore the given mode sometimes is called гаммированием with gearing of blocks. On firmness of the code number the fact of gearing of blocks does not render any influence.

The scheme of algorithms for - and расшифрования in a mode гаммирования with a feedback is resulted in drawing 5 and in view of the simplicity comments does not require.

Enciphering in a mode гаммирования with a feedback possesses the same features, as enciphering in a mode usual гаммирования, except for influence of distortions шифротекста on a corresponding clear text. For comparison we will write down functions расшифрования the block for both mentioned modes:

, гаммирование;

, гаммирование with a feedback;

If in a mode usual гаммирования changes in certain bits шифротекста influence only corresponding bits of a clear text in a mode гаммирования with a feedback the picture is slightly more difficult. Apparently from the corresponding equation, at расшифровании the block of the data in a mode гаммирования with a feedback, the block of the open data depends on corresponding and previous blocks of the ciphered data. Therefore, if to bring distortions in the ciphered block after расшифрования deformed there will be two blocks of the open data – corresponding and following for it, and distortions in the first case will have the same character, as in a mode гаммирования, and in the second case – as in a mode of simple replacement. In other words, in the corresponding block of the open data deformed there will be same bits, as in the block шифрованных the data, and in the following block of the open data all bits independently from each other with probability 1/2 will change the values.

4.     Development имитовставки to data file.

In the previous sections we have discussed distortion influence шифрованных the data on the corresponding open data. We have established that at расшифровании in a mode of simple replacement the corresponding block of the open data appears in the deformed unpredictable image, and at расшифровании the block in a mode гаммирования changes are predicted. In a mode гаммирования with a feedback deformed there are two blocks, one predicted, and another in the unpredictable image. Whether it means, what from the point of view of protection against imposing of the false data the mode гаммирования is bad, and modes of simple replacement and гаммирования with a feedback good? In no event. At the analysis of the given situation it is necessary to consider that unpredictable changes in the deciphered block of the data can be found out only in case of redundancy of this data, and the more redundancy degree, the distortion detection is more probable. Very big redundancy takes place, for example, for texts on natural and artificial languages, in this case the distortion fact is found out almost inevitably. However in other cases, for example, at distortion of the compressed sound images, we will receive simply other image which can apprehend our ear. Distortion in this case remains not found out if, of course, there is no aprioristic information on character of a sound. A conclusion here the such: as ability of some modes of enciphering to find out the distortions brought in шифрованные the data, essentially leans against presence and degree of redundancy of the ciphered data, this ability is not immanent property of corresponding modes and cannot be considered as their advantage.

For the decision of a problem of detection of distortions in the ciphered data file with the set probability in the VISITOR the additional mode криптографичес�кого transformations – development имитовставки is provided. Имитовставка is control ком�бинация, depending on the open data and the confidential key information. Use purpose ими�товставки is detection of all casual or deliberate changes in an information file. The problem stated in the previous point, can be successfully solved by means of addition to шифрованным to the data имитовставки. For the potential malefactor two following problems are almost unsoluble, if he does not own the key information:

�      calculation имитовставки for the set open file of the information;

�      selection of the open data under set имитовставку;

The scheme of algorithm of development имитовставки is resulted in drawing 6. In quality имитовставки the part of the block received on an exit, usually 32 its younger bits undertakes. At a choice of the size имито�вставки it is necessary to take into consideration that the probability of successful imposing of the false data is equal to size 2 ^{| And |} on one attempt of selection. At use имитовставки in the size 32 bits this probability is equal

2^–32 �0.23�10^–9.

2.    Discussion of cryptographic algorithms STATE THAT.

2.1.    STATE THAT cryptographic firmness.

At a choice of cryptographic algorithm for use in concrete working out by one of defining factors its firmness, that is stability to attempts of an opposite side it is to open. The question on firmness of the code number is on closer examination reduced to two interconnected questions:

     Whether �      it is possible to open the given code number in general;

�      if yes how much it is difficult for making practically;

Code numbers which in general cannot be opened, are called absolutely or as theoretically proof. Existence of similar code numbers is proved by the theorem of Shennona, however by this firmness necessity of use for enciphering of each message of a key, not smaller on the size of the message is. In all cases except for a number special this price is excessive, therefore in practice basically the code numbers which are not possessing absolute firmness are used. Thus, the most common schemes of enciphering can be opened for final time or that is more exact, for final number of steps, each of which is some operation over numbers. For them the most important value has the concept of practical firmness expressing practical difficulty of their disclosing. As quantitative measure of this difficulty the number of elementary arithmetic and logic operations can serve, which are necessary for executing to open the code number that is that for set шифротекста with probability, not the smaller set size, to define a corresponding clear text. Thus in addition to дешифруемому to data file криптоаналитик can have blocks of the ciphered data open given and corresponding to them or even possibility to receive for any open data chosen by it the corresponding ciphered data – depending on the listed and many other not specified conditions distinguish separate kinds криптоанализа.

All modern криптосистемы are constructed by a principle of Kirhgoffa, that is privacy of the ciphered messages is defined by privacy of a key. It means that even if the algorithm of enciphering is known криптоаналитику, that nevertheless not in a condition to decipher the message if has no a corresponding key. All classical block code numbers, including DES and GOST, correspond to this principle and are designed so that there was no way to open in their more effective way, than full search on all key space, i.e. on all possible values of a key. Clearly that firmness of such code numbers is defined by the size of a key used in them.

In GOST code number the 256-bit key and volume of key space is used makes 2²⁵⁶. On one of existing now or assumed to realisation in the near future of the COMPUTER of the general application it is impossible to try a key for time, smaller many hundreds years. The Russian standard was projected with a large supply and in firmness on many usages surpasses the American standard DES with its real size of a key in 56 bits and volume of key space only 2⁵⁶. In the light of progress of modern computing means of it it is obviously not enough. Thereupon DES can represent more likely research or scientific, than practical interest. Predictably, in 1998 it will cease to be the standard of the USA on enciphering.

2.2.    Remarks on architecture STATE THAT.

Well-known that the code number of GOST 28147-89 is the representative of the whole family of the code numbers constructed on the same principles. Its most known "relative" is the American standard of enciphering, algorithm DES. All these code numbers, similarly STATE THAT, contain algorithms of three levels. In a basis certain �the basic step� on which base in the similar image �base cycles� are under construction always lies, and already on their basis practical procedures of enciphering and development имитовставки are constructed. Thus, specificity of each of code numbers of this family is concluded in its basic step, is more exact even in its part. Though the architecture of classical block code numbers which GOST concerns, lies far outside of a theme of present article, nevertheless it is necessary to tell some words in its occasion.

Algorithms �the basic steps криптопреобра�зования� for the code numbers, similar STATE THAT, are constructed in the identical image. Their general scheme is resulted in drawing 7. On an input of the basic step the block of the even size, senior and which younger half are processed separately from each other moves. During transformation the younger half of block is located to the place of senior, and senior, combined by means of operation bit-by-bit excluding or with result of calculation of some function, to the place of the younger. This function accepting as argument a younger half of the block and some element of the key information (X), is a substantial part of the code number and is called as its function of enciphering. Reasons of firmness of the code number demand, that the sizes of all listed elements of blocks were equal: |N₁ | = | N₂ | = | X |, and DESе they are equal in the VISITOR to 32 bits.

If to apply told to the scheme of the basic step of algorithm of GOST, becomes obvious that blocks 1,2,3 algorithms define calculation of its function of enciphering, and blocks 4 and 5 set formation of an output block of the basic step proceeding from the contained entrance block and value of function of enciphering.

Fig. 7. С��������� the basic step криптопреобразования for the block code numbers, similar STATE THAT.

In the previous section we have already compared DES and GOST on firmness, now we will compare them under the functional maintenance and convenience of realisation. In enciphering cycles STATE THAT the basic step repeats 32 times, for DESа this size is equal 16. However function of enciphering STATE THAT essentially is easier than similar function DESа at which there is a set of code conversions under tables with change of the size of recoded elements. Besides, between the basic steps to cycles of enciphering DESа it is necessary to carry out bit shifts in blocks of the data. All these operations are extremely inefficiently realised on modern unspecialized processors. GOST does not contain similar operations, therefore it is much more convenient for program realisation. Any of realisations DESа considered by the author for platform Intel x86 does not reach even half of productivity brought to your attention in the present article of realisation STATE THAT, despite twice shorter cycle. All told above testifies that developers STATE THAT have considered both positive, and negative sides DESа, and also have more really estimated current and perspective possibilities криптоанализа.

2.3.    Requirements to quality of the key information and sources of keys.

Not all keys and tables of replacements provide the maximum firmness of the code number. For each algorithm of enciphering there are criteria of an estimation of the key information. So, algorithm DES knows existence so-called �weak keys� at which use communication between the open and ciphered data does not mask in the sufficient image, and the code number is rather simply opened.

The irrefragable answer on a question on criteria of quality of keys and tables of replacements STATE THAT if also can be received somewhere in general, only at developers of algorithm. The corresponding data has not been published in the open press. However according to the established order, for enciphering of the information having a signature stamp, the key data received from the authorised organisation should be used. Indirectly it can testify to presence of techniques of check of the key data on "pediculosis". The fact of existence of the weak key data in the Russian standard of enciphering does not raise the doubts. Obviously, zero key and the trivial table of replacements on which any value is replaced but it, are weak, at use at least one of them the code number is simply enough cracked, whichever there was a second key element.

As already it has been noted above, criteria of an estimation of the key information are inaccessible, however into their account nevertheless it is possible to make some observations:

1. The key should be a file of statistically independent bits accepting with equal probability of value 0 and 1. Thus some concrete values of a key can appear "weak", that is the code number can not provide the set level of firmness in case of their use. However, presumably, a share of such values in a lump of all possible keys it is insignificant it is small. Therefore the keys developed by means of some gauge of truly random numbers, will be qualitative with the probability different from unit on is insignificant small size. If keys are developed by means of the generator of pseudo-random numbers the used generator should provide the statistical characteristics specified above, and, besides, to possess high криптостойкостью, not smaller, than at most STATE THAT. Differently, the problem of definition of absent members of sequence of elements developed by the generator should not be easier, than a problem of opening of the code number. Besides, for rejection of keys with bad statistical characteristics various statistical criteria can be used. In practice two criteria usually suffice, – for check of equiprobable distribution of bits of a key between values 0 and 1 the criterion of Pirsona (�хи a square�), and for check of independence of bits of a key – criterion of series is usually used. About the mentioned criteria it is possible to read in textbooks or directories on the mathematical statistics.

2. The table of replacements is a long-term key element, that is the separate key operates during much longer term, than. It is supposed that it is the general for all knots of enciphering within the limits of one system of cryptographic protection. Even at infringement of confidentiality of the table of replacements firmness of the code number remains extremely high and does not decrease below an admissible limit. It is possible to make the demand resulted more low to quality of separate knots of replacements. Each knot of replacements can be described the four of logic functions, each of which has four logic arguments. It is necessary, that these functions were difficult enough. It is impossible to express this requirement of complexity formally, however as a necessary condition it is possible to demand, that the corresponding logic functions which have been written down in the minimum form (i.e. with is minimum possible length of expression) with use of the basic logic operations, were not shorter than some necessary minimum. In the first and very rough approach this condition can descend and for the sufficient. Besides, separate functions within all table of replacements should differ from each other sufficiently. In practice happens to receive enough knots of replacements as independent casual shifts of numbers from 0 to 15, it can be almost realised, for example, by means of hashing of a pack from sixteen cards, one of values of the specified range is fixed to each of which.

It is necessary to note one more interesting fact concerning the table of replacements. For convertibility of cycles of enciphering 32-Z and 32-R it is not required, that knots of replacements were shifts of numbers from 0 to 15. All works even in the event that in knot of replacements there are repeating elements, and the replacement defined in such knot, is irreversible, however firmness of the code number in this case decreases. Why it so, is not considered in the present article, however of the fact to be convinced simply. For this purpose it is enough, using the demonstration program of enciphering of files of the data, applied on the present article, to cipher and then to decipher a file of the data, having used for this procedure "the defective" table of the replacements which knots contain repeating values.

If you develop the programs using cryptographic algorithms, it is necessary for you to take care of the utilities developing the key information, and the source of random numbers is necessary for such utilities (СЧ) high statistical quality and криптостойкости. Use of hardware gauges SCH would be the best approach here, however it is not always comprehensible for economic reasons. As reasonable alternative probably (and very widespread) use of various program gauges SCH. At generation of a small file on volume of the key information the method of "an electronic roulette� when the next portion of casual bits received from such gauge depends on the moment of time of pressing by the operator of some key on the computer keyboard is widely applied.

This approach is used in the program of generation of one key which initial text in language of Si with ассемблерными impregnations is applied on the present article in a file make1key.c. For development of random numbers from the set range the channel 2 system timers is used, the information is read out from it by pressing by the operator of any key the display keyboard. For one pressing one byte of a key is generated and on the screen the point is deduced. That it was impossible to generate bytes of a key key deduction in the pressed condition, between generation cycles the time delay is entered and in the beginning of each cycle is checked, whether was during a pause key pressing. If that took place, the sound signal and pressing stands out is ignored. The program is expedient for starting only from "naked" DOSа, in DOS-session Windows 3.x/95 it also works, but there is no confidence of maintenance of the necessary statistical characteristics, and under Windows NT the program understandably (climbs directly in ports) at all does not work correctly.

3.    Remarks on realisation.

3.1.    Three steps of optimisation.

Not creation of the maximum code by efficiency at any cost was the purpose of realisation described in the present article STATE THAT, creation near optimal on speed, but thus compact and easy for perception the programmer of a code was the purpose.

Programming of algorithms STATE THAT �in a forehead� even in assembler language yields the result very far from a possible optimum. The problem of creation of effective realisation of the specified algorithms for 16-digit processors Intel 8088–80286 represents though and not superdifficult, but nevertheless and not quite trivial problem, and demands very good knowledge of architecture and system of commands of the mentioned family of processors. Difficulty here consists that for achievement of the maximum productivity program realisation should as it is possible to carry out the most part of operations with the data in registers and as seldom as possible to address to memory, and at considered processors not so it is a lot of registers and all of them 16-digit. With 32-bit processors of the same line (Intel 80386 also is more senior) all much easier owing to their 32-word length, here will not be difficulties even at the beginner.

In realisation of algorithms the approaches stated more low, allowed to reach the maximum productivity have been used. First two of them are obvious enough, so, that meet practically in each realisation STATE THAT.

1.   Base cycles STATE THAT contain the enclosed cycles (sounds clumsily, but in another way you will not tell), and in an internal cycle the order of use of eight 32-bit elements of a key can be direct or return. It is essential to simplify realisation and to raise efficiency of base cycles it is possible if to avoid use of the enclosed cycles and to look through sequence of elements of a key only once. For this purpose it is necessary to generate preliminary последователь�ность key elements in that order in which they are used in a corresponding base cycle.

2.   In the basic step криптопреобразования 8 times are carried out substitution of 4-bit groups of the data. The target processor of realisation has no command of replacement of 4-bit groups, however has a convenient command of byte replacement (xlat). Its use gives following benefits:

�      for one command two replacements are carried out at once;

�      necessity to allocate half-bytes from double words for replacement performance disappears, and then of 4-bit results of replacements again to form a double word.

It reaches substantial growth of speed of a code, however the world is arranged so that it is necessary to pay for all, and in this case a payment is necessity of transformation of the table of replacements. Each of four pairs 4-digit knots of replacements is replaced with one 8-digit knot which, speaking to mathematical language, represents direct product of the knots entering in pair. The pair of 4-digit knots demands for the representation of 16 bytes, one 8-digit – 256 bytes. Thus, the size of the table of replacements which should be stored in memory of the computer, increases to 4�256=1024 bytes, or to one kilobyte. Certainly, such payment for essential increase in efficiency of realisation is quite comprehensible.

3.   After performance of substitutions of a code by the table of replacements the basic step криптопреобразования assumes cyclic shift of a double word to the left on 11 bits. Owing to 16-digit architecture of considered processors rotation of the 32-bit block even on 1 bit cannot be realised less, than for three ассемблерные commands, and rotation on большее number of categories only as sequence of separate rotations on 1 category. Fortunately, on 11 bits to the left it is possible to present rotation as rotation on 8 bits, and then on 3 bits to the left. I think, it is obvious to all that the first rotation is realised by three commands of an exchange of byte registers (xchg). But a secret of the third optimisation at all in it. Replacement of one byte under the table of replacements is carried out by a command xlat, which carries out operation over argument in register AL to replace all bytes of a double word, they should be placed consistently in this register. The secret of the third optimisation consists that these shifts can be organised so that as a result the double word will appear turned on 8 bit to the left, that is in replacement combination under the table and in rotation on byte to the left. One more moment on which it is necessary to pay attention, this optimum coding of three consecutive rotations to 1 bit, it can be realised differently and it was important to choose an optimum way which has appeared not so obvious as has demanded an exit for limits of logic of bit shifts and use of a command of summation with carrying over bits (adc), that is the bit is located on the position not with a shift command, and a summation command!

3.2. The    description of functions and feature of realisation.

Taking into account stated above principles two realisations STATE THAT for family Intel processors x86, relatives on speed to a possible optimum – accordingly for 16 and 32 bit processors are created. A code for 32-bit processors approximately in one and a half time of faster corresponding code for 16-digit processors. A kernel is the subroutine realising a universal base cycle STATE THOSE. Initial texts of all subroutines are led as appendices to the present article in separate files, they are listed in table 1 following more low. All functions are self-documented, everyone is described in a corresponding file with its initial text.

Table 1. The list of files.
№	Module function	Name of a file of the ref. text
		16 bits	32 bits
1.	Universal base cycle STATE THAT	gost.asm	gost ~. asm
2.	Function for - and расшифрования the data in a mode of simple replacement	simple.asm	simple ~. asm
3.	Function for - and расшифрования the data in a mode гаммирования	gamma.asm	gamma ~. asm
4.	Function зашифрования the data in a mode гаммирования with a feedback	gammale.asm	gammale ~. asm
5.	Function расшифрования the data in a mode гаммирования with a feedback	gammald.asm	gammald ~. asm
6.	Calculation function имитовставки for data file	imito.asm	imito ~. asm
7.	Function of construction of the expanded key	expkey.asm	expkey ~. asm
8.	Function of construction expanded (1Кбайт) forms of the table of replacements from the usual form (128 byte)	expcht.asm
9.	Check function, whether is the processor on which the appendix, 32-bit is executed.	—	ge386cpu.asm
10.	Heading file for use криптографи�ческих functions in programs in language of Si	gost.h

The complete set of modules includes functions for the basic modes of enciphering, and also two auxiliary functions intended for construction expanded accordingly key and the table of replacements. Principles of construction of program modules are more low stated.

1.   All functions of enciphering and calculation имитовставки process (i.e. cipher or calculate имитовставку) areas with a size, multiple eight. The length of processed area by a call of the mentioned functions is set in восьмибайтных blocks. In real situations it does not lead to inconvenience for following reasons:

�      at enciphering by simple replacement the size of ciphered area is obliged to be to multiple eight bytes;

�      at enciphering гаммированием (with or without a feedback) data file with a size, not multiple eight, it will be ciphered also and "the dust" containing in last eight-byte block outside of the meaning data, however its contents does not render any influence on the meaning data and can not be taken into consideration;

�      at calculation имитовставки for data files their size should be led to value, multiple eight, addition of any fixed code (usually zero bits).

2.   Cryptographic functions of enciphering and calculation имитовставки allow to carry out processing of data files in parts. It means that by a call of corresponding function once for some area of the data and by several calls of the same function for consecutive fragments of the same area (naturally their size should be to multiple eight bytes, the previous remark see) the same result will be received. It allows to process given in the portions, using the buffer in the size of only 8 bytes.

3.   For for - and расшифрования data file in a mode of simple replacement the same function is used. The choice of one of two specified operations is carried out by the task of the corresponding expanded key. The sequence of elements of a key should be mutually the return for the specified operations.

4.   For for - and расшифрования the block of the data in a mode гаммирования the same function as in the given mode зашифрование and расшифрование the data are identical is used. The function realising enciphering гаммированием does not carry out initial transformation синхропосылки (see the algorithm scheme on fig. 5, the block 1), it is necessary for executing by means of an obvious call of function of enciphering in a mode of simple replacement for синхропосылки, is a payment for possibility to cipher a file in parts.

5.   For the sake of universality of a code all indexes on area of the processed data are made by the distant. If to make the code for each model of memory, probably, some will be reached nonzero (but very small!) economy of memory and performance time, but in my opinion, this it's not worth the trouble.

6.   For assemblage (compilation) and assemblage of the enclosed modules I used means of working out of firm Borland – TASM 2.5 and above, Borland C/C ++ 2.0 and above. At use of other means of working out modification of initial texts of programs probably is required.

For an illustration of use of the presented cryptographic functions to the present article are enclosed also the text of the program of enciphering of files of the data in language of Si and corresponding files of the project. These files the following:

�      cryptor.c Initial texts of the program of enciphering of files;

�                                                              gost.mak the File of the project for the 16-digit version of the program of enciphering of files;

�                                                              gost386.mak the File of the project for the 32-bit version of the program of enciphering of files.

The description of construction and syntax of a call (command line) programs of enciphering of files also is applied on the present article.

3.3. A    speed question.

After working out of new program realisation it has been measured it быстро�действие for what the complete set of the simple modules intended for construction of a measuring problem has been developed. This problem fixes and deduces on the display time (in steps of the generator of clock frequency of the timer, 1193180 Hertz), spent by the tested subroutine on performance. On the measured operating time of the subroutine then its speed as the relation of quantity of work up the time of its performance is calculated (manually).

The maximum duration of process measured by the program is equal 2³²/1193180 �3599.6 seconds, that is approximately to one hour. The program works correctly and yields correct results, only if is started from ДОСа.

For modules STATE THAT was measured duration of enciphering of one Mbyte of the data which was modelled by 32-fold enciphering 32-Kilobajtnoj memory areas. Measurements were spent by cars of various classes, results of measurement are resulted more low in table 2. For 32-bit processors speed of 32-bit realisations of cryptographic modules (the bottom number in a corresponding cell) also is resulted. For comparison measurements of speed of realisation of the American standard of enciphering DES, published in magazine "Monitor" №7/1994 also are resulted. Results of tests have shown that speed of modules STATE THAT is approximately identical to all modes of enciphering, and speed of the module of calculation имитовставки approximately twice exceeds speed of enciphering – that, actually, and it was expected. Enciphering realisation it is in accordance with GOST essential (more than twice) exceeds investigated realisation DES on speed.

Table 2. Results of measurement of speed of modules of enciphering
Mark of the computer,	т.ч.,	Speed of cryptographic modules
Processor type	MHz	gamma	gammaLD	gammaLE	simple	imito	DES
Spark 1031, К1810ВМ88	4.52	8.4	8.6	8.7	8.7	16.9	There is no data
AMI 286 Intel 80286	10	20.4	20.7	20.8	20.8	40.8	11.2
Prolinea 325 Intel 386SX-25	25	48.0 66.0	48.6 71.1	48.8 67.4	48.0 71.5	93.7 139	22.0
Неизв.модель Intel 386SX-33	33	63.8 87.6	64.5 94.5	64.7 89.5	63.8 95.0	124 185	25.9
BYTEX Intel 386DX-40	40	89 120	90 135	91 122	91 135	177 264	39.3
Acer Intel486SX33	33	114 150	113 161	114 151	114 162	226 321	41.2
Presario 460 Intel486SX2-66	66	225 298	222 319	229 303	227 324	451 637	82.2
Acer Pentium-66	66	302 351	296 397	307 355	293 405	601 777	88.7

Now we will estimate the reached indicators from the qualitative point of view. Speed limits of enciphering much more exceed speed of work of a payment of hardware enciphering of "Kripton-3" (to 70 Kb\ss) and approximately correspond to speed of a payment of "Kripton-4" (about 400 Kb\ss). The reached productivity has enough for really transparent enciphering of the data, хранимых on hard disks or transferred through a fast network. At the same time, speed of realisation quite suffices for enciphering of the data in switched communication channels and for many other cases.

Whether it is possible to increase still speed of realisation STATE THAT? It is possible, but ненамного if to remain within the limits of the formal specification STATE THAT. For this purpose it is necessary to refuse a cycle in the subroutine �gost�, продублировав a body of a cycle 32 times as it was made by the author of the program emulator of a payment of "Kripton". Thus it is possible not to develop a key in linear sequence of elements but then for each base cycle of cryptographic transformation it is necessary to make the program module and a code of the basic step will be present at codes of cryptographic procedures in 32+32+16=80 copies. Such way of increase of efficiency leads to repeated swelling of a code at more than modest prize in производительно�сти, therefore hardly it is possible to consider it good.

4.    Questions of use of the standard.

4.1.    Reliability of realisation.

Question of reliability of a software of cryptographic protection it not only a question of firmness of the used algorithm. Use of the proof code number in itself cannot make your system reliable though is a necessary condition. Rather important role is played also by a way of application of cryptographic algorithm. So, in the program of enciphering of files enclosed to the present article, storage of the key information on disks in an open kind does system which would be realised on this program, potentially unstable. Procedures and the rules of higher level regulating use of algorithms of enciphering and all connected with it, in aggregate make the so-called cryptographic report. This report defines regulations of development, use, storage and change of the key information, and other, not less important questions. And so, that your system using realisation of algorithms STATE THOSE, was really reliable, it will be necessary for you to take care of working out of the corresponding report.

4.2.    Variations on a theme STATE THAT.

Very often for use in system of cryptographic protection of the data the algorithm with big is required, than at STATE THAT speed of realisation, and thus it is not required same high as at STATE THAT криптостойкость. A typical example of similar problems are any the exchange trading systems operating trading sessions in real time. Here from the used algorithms of enciphering it is required, that it was impossible to decipher the operative given systems during session (the data about the exposed demands, about the concluded transactions, etc.), after its expiration this data, as a rule, is already useless for malefactors. In other words, the guaranteed firmness of all at some o'clock (such is typical duration of trading session) is required. Clearly that use sound STATE THAT in this situation would be shooting from a gun on sparrows.

Fortunately, from this situation there is easy enough exit – to use updating of algorithm of GOST with smaller quantity of the basic steps to base cycles. It can be reached two ways – reduction of length of a key and reduction of number of cycles of use of elements of a key – recollect that the number of the basic steps to base cycles of enciphering is equal N=n�m, where n – number of 32-bit elements in a key, m – number of cycles of use of key elements, in the standard n=8, m=4. In how many time decreases number of the basic steps to cycles, approximately in as much time speed of a code increases.

Unfortunately, there are no data on how STATE THAT changes криптостойкость the similar weakened variant. As to криптоанализа on a statistical line (search of all possible values of a key) here all is clear enough as this size is defined only by the size of a key. It is much more difficult to predict, to how much less difficult becomes криптоанализ on an algorithmic line (the analysis of the equations of transformation of the data at their enciphering).

At a choice of the size of "the reduced cycle� it is necessary to take into consideration that GOST was projected taking into account possible progress of computer facilities for some decades forward and in it the huge stock криптостойкости is put. In my opinion (deeply personal), in the majority of practical cases use of the reduced variants STATE THAT without change of the scheme of use of a key (m=4=3+1) is represented reasonable, but with the quartered size of a key (n=2) is will allow to quadruple speed of enciphering approximately. On firmness to statistical methods криптоанализа the given updating with its 64-bit key will be more reliable, than DES with the size of a key in 56 bits.

Functions криптопреобразования, applied on the present article, suppose similar use as the length of the developed key is transferred as parametre in each of subroutines of cryptographic transformation, and the subroutine of "expansion" of a key allows to work with any length of a key and the scheme of expansion of a key.

4.3.    Unusual work of cryptographic scale.

Certainly, the basic purpose криптоалгоритмов STATE THAT is this enciphering and имитозащита the data. However the cryptographic scale has one more important application – development of the key information. Development of a file key or парольной information of great volume is a typical problem of the manager of safety of system. As already it has been noted above, the key can be generated as a file of the necessary size of 0 and equiprobably distributed between values 0 and 1 bits, for this purpose it is possible to use the program developing a key by a principle of "an electronic roulette�. But such approach does not suit at all when the volume of the necessary key information is great. In this case use of hardware random-number generators is ideal that, however, is not always possible for economic or technical reasons. In this case as a source of a stream of casual bits the generator of scale on the basis of any block code number, including GOST 28147-89 as, by definition, the cryptographic scale possesses necessary statistical characteristics and криптостойкостью can be used. Thus, for development of several keys it is necessary to generate only data file on algorithm of development of scale, and to cut it for a portion of the necessary size, for a standard variant – 32 bytes.

With passwords business is slightly more difficult. First of all there is a question, what for in general it is necessary to generate them, whether to take easier as required than them from a head. The inconsistency of such approach has been visually shown by a series of incidents in computer networks largest of which was the daily paralysis of network Internet in November, 1988 One of ways of access of the ill-intentioned program in system there was a selection of passwords: the program tried to enter into system, consistently trying passwords from the internal list in some hundreds, and in a considerable share of cases to it it managed to be made – the imagination of the person on an inventing of passwords has appeared very poor. For this reason in those organisations where the proper attention is given to safety, passwords generates and the system administrator on safety distributes to users.

Development of passwords is hardly more difficult, than development of keys as thus "the crude" binary scale is necessary for transforming to a symbolical kind, instead of simply to "cut" on pieces. The core, on what is necessary to pay attention thus – maintenance of equal probability of occurrence of each of alphabet symbols.

Initial texts of programs of development of a file of passwords and keys in language of Si are enclosed to the present article.