Andrey Vinokurov. How the block code number is arranged?

You will find the description of traditional architecture of construction of the block code numbers in the present article, underlying most known of modern unclassified code numbers, such, as the Russian and American standards of enciphering. Article has been written exactly 3 years ago – the author has finished it in first half of April, 1995, but for various reasons could not then to publish. At that time the information on architecture of classical block code numbers practically was absent in the Russian open press, and Russian-speaking terminology in this area was in a formation stage. For the past since then time has appeared huge number of materials on a discussed theme, therefore today article can seem slightly naive. However its radical alteration would occupy too much time, to write new article and consequently the author in parallel with this work has decided to publish the current version with minor alterations easier. Article does not assume preliminary acquaintance of the reader to cryptography, however contains sufficient number of mathematical formulas and means possession of a corresponding mathematical apparatus.

Introduction

Coming to an end 20 century is a century not only an electricity and atom, in even большей degrees it can apply for being called as a century of total information and a society computerisation. With that moment when in its middle have appeared and have begun victorious procession on a planet of the device for processing of figures – computers, there was an industry of manufacture, processing and consumption of the information which became now an integral part of our life. Now it makes sense to judge technological level of the states not by quantity of a steel melted per capita or made combines for cleaning of a sugar beet, and on cumulative capacity of all computing means having on one inhabitant of the country.

About importance of the information in the modern world it is most indicative following facts testify: First, the possession a certain digital code can open access to its owner to considerable material assets and services – such state of affairs takes place thanks to that information of a society has not avoided bankovsko-financial sphere. Secondly, has developed and the industry of information services has extraordinary got stronger – the information became the ordinary goods, that is object of purchase and sale. Many firms succeed only thanks to that the important data for their activity of all at some o'clock or days before the competitors can receive. In the third, by estimations of foreign economists the considerable share of the western firms would be ruined in a current of several days after disclosure of the crucial information, their underlying activity.

Special, non-material character of the information does exclusively easy its copying and modifying owing to what it becomes seductive any object of abusings. Besides, enough the situation when its owners would disagree to sell the information necessary to someone not at any price, and it is a unique way typical to receive is to steal. The specified reasons have led to occurrence of the whole branch of the human activity which basic purpose – to extract the information in any possible and impossible ways, – is final, it is a question of investigation. A trade of the spy along with others, it is fine all known, is one of the most ancient on a planet. On the other hand, the statistics inevitably testifies that the increasing share of all crimes is made in sphere of an information technology "white" and “dark blue collars”, using "gaps" of information systems to suit the own ends. Really, now, to plunder bank, it is not necessary to break walls of storehouses and to cut autogenous cutting safes, it is enough to learn a code operating access to one of bank accounts. Everything that for this purpose is required, is a computer and access to a bank network, well and is final, a quantity of grey substance in a cranium. Regrettably, but the fact – number of crimes with use of "high technologies” grows fast rates.

High vulnerability of an information technology to various ill-intentioned actions has generated a severe need in means of counteraction to it that has led to occurrence and a development of the region of protection of the information (ЗИ) as to an integral part of the information industry. The most ancient problem of sphere ЗИ is protection of transferred messages against unapproved acquaintance with their contents, there are certificates of understanding people of this problem still in to-antique times – in ancient Egypt and Babylon, and the information on ways of its decision in a classical antiquity has reached us in the form of references on so-called “Caesar's code” – the elementary code number applied at first by Juliem Caesar, and subsequently and other Roman emperors, for protection of the correspondence against unduly curious eyes. However up to new time тайнопись was not craft, and art and as a science, the cryptography has developed only in the present century. But still long time after that шифровальные departments were an exclusive prerogative diplomatic and intelligence services, the situation has cardinally changed only last decades.

Now concept “information protection” unites in itself set of the most various values – from reservation of a food for protection of the information against destruction at possible failures in a power line and security guards in the doorway of the computer hall, extraneous persons interfering an input and carrying out by employees of data carriers, to generators of the hindrances "suppressing" radiations carrying away the information. From all variety of methods ЗИ us what are not connected in any way with characteristics of its material carriers interest only, and are based on a manipulation by the information and use only its immanent properties. This area ЗИ is called as cryptographic protection of the information and endures now the present boom. For today the considerable quantity of the problems concerning sphere ЗИ is known, – such abundance is caused by that information interactions, developing, get more and more difficult character, accordingly there are more various and refined threats in their party, and it in turn leads to occurrence of new problems. If earlier all requirements for information protection were reduced to maintenance of privacy and authenticity of transferred messages, that is to their protection against reading and modification by extraneous persons, now actually much bigger number of problems. Among new problems we will note only two, the most known: dispatch of confidential keys on not protected communication channels (open distribution of keys) and acknowledgement of authorship of messages (the digital signature). And after all there is a considerable quantity less known, but not less important problems.

According to classes of solved problems now there were two areas of cryptography: classical, or cryptography with a confidential key, and modern, or cryptography with an open key. The history of the first totals a millenium whereas the official age of the second has not passed for three ten years. We will short stop on distinctions between them.

1.    Classical and modern cryptography.

Classical, or the one-key cryptography solves actually only two problems: protection of transferred messages against perusal and against updating by extraneous persons. She leans against use of symmetric algorithms of enciphering in which for - and расшифрование differ only order of performance and a direction of some simple steps. These algorithms use the same confidential element (key), and the second action (расшифрование) is the simple reference of the first (зашифрования). Therefore each of participants of an exchange can both to cipher, and to decipher the message. Because of the big redundancy of natural languages directly intelligent change, therefore classical cryptography is extremely difficult to make to the ciphered message provides also protection against imposing of the false data. If it appears natural redundancy insufficiently for reliable protection of the message against updating, it can be artificial is increased by addition to it of the special control combination named имитовставкой.

The classical scheme of enciphering perfectly works, while between participants of an information exchange there is a mutual trust. If it is not present, there can be various collisions as because of full symmetry of the scheme in case of the conflict between the parties for the independent observer there is no possibility to draw an unequivocal conclusion who from two participants of the rights. Really, the addressee can make itself the ciphered message and then to declare that it is received by it from the lawful sender, and that, in turn, can refuse authorship of the message actually transferred to it, declaring that it was fabricated by the addressee, the blessing corresponding possibility at that is available. In these cases the independent arbitration which functions include the resolution of conflicts between participants of information process, cannot define, who from them the rights and who – is not present. The resulted fact means that the considered cryptographic scheme does not allow to confirm or deny authorship of the message unequivocally. Besides, this scheme requires the special service which is engaged in manufacturing of confidential keys and delivery to their participants of an information exchange. Certainly, if participants of an exchange of all two the problem is insignificant – the role of such service can carry out one of them or even both of them alternately. But if the system totals hundreds or even thousand knots of processing of the information connected among themselves, it is a small problem grows in the big headache.

The contradiction between restrictions of classical cryptography and constantly arising new problems has led to that per second half seventieth essentially new approaches have been developed, allowing to solve both listed above a problem, and a great number of others. As a basis opening so-called asymmetric криптоалгоритмов has served, or methods in which procedures direct and return криптопреобразования are carried out on various keys and have among themselves no obvious and easily traced communications which would allow to define another on one key. In such scheme the knowledge only a key зашифрования does not allow to decipher the message, therefore it is not a confidential element of the code number and is usually published by the participant of an exchange that any interested person could send it шифрованное the message.

As we see, the modern cryptography allows to solve much more a wide range of problems, than cryptography classical. At the beginning of its development opinions were expressed even that it for some years completely will supersede the predecessor, however it has not occurred for following reasons: First, algorithms with a confidential key are much easier realised as программно, and is hardware, owing to what at identical characteristics of productivity and firmness complexity so also the price of the hardware realising the code number with an open key considerably above the price of equipment, realising the classical code number, and at program realisation on the same type of the processor one-key code numbers work faster the two-key. Secondly, reliability of algorithms with an open key is proved now much worse, than reliability of algorithms with a confidential key and is not present a guarantee that after a while they will not be opened, as it has turned out with криптосистемой, based on a problem about satchel packing. Therefore шифрованной communications are applied now to the organisation exclusively classical code numbers, and methods of modern cryptography are used only there where they do not work, that is for the organisation of various smart reports of type of the digital signature, open distribution of keys and game in poker on correspondence. As asymmetric cryptographic algorithms are not a theme of present article, the author will not be late more on it. The interested reader can find their description and discussion in a considerable quantity of sources, for example, in [1,3,4,8].

It is necessary to notice that the considerable number of scientific and popular works on modern cryptography whereas not numerous publications in which classical code numbers are considered, are devoted basically or to questions of history of art тайнописи now is published, or contain the description of concrete algorithms without research of the general principles lying in their basis. Such state of affairs on the one hand, is a craze, and with another – a consequence excessive засекреченности classical cryptography, anyway, normal it is impossible to name it. For this reason in the present work the author has decided to tell about the general principles of construction криптоалгоритмов with a confidential key, more precisely, one of its classes named block code numbers, at simple enough level that article was clear to at all not very prepared reader, and at the same time with necessary severity. There is no necessity in detail to paint advantages of principles of construction of algorithms of enciphering considered in article, it is enough to tell only that they underlie two most known code numbers in Russia from among the strongest, or if so it is pleasant to you, two strongest code numbers from among the most known – the Russian and American standards of enciphering, algorithms of GOST 28147-89 and DES more , and also a great number of less known and-or less strong code numbers. We will pass directly to their studying.

2. The    basic concepts.

There are some principles of construction криптоалгоритмов with a confidential key – distinguish потоковые and block code numbers, it is possible to spend classification and by other signs. To tell about all possible types of code numbers of the given class it is necessary to write not article, and voluminous enough book or even some books. Therefore the author will not try объять immense, and will be limited in given article to the story about the architecture embodied in the Russian and American standards of enciphering – at all of them distinctions they are similar as brothers, let even not twins. Perhaps, the data stated in article will inspire the reader with inquisitive mind on creation of own code number – in it there is nothing impossible, after all the cryptography last years has reached such successes that now even the countries least developed in a science, not to mention large prospering firms from the developed states, presume to create to themselves almost not opened code number. To that there is a vivid example – the American standard of enciphering (DES) has originally been developed by firm IBM for own needs, and only then, after some processings, has been accepted as the federal standard of the USA [2]. Achievements of modern cryptography allow to provide so full confidentiality at information processing, what even the most ardent advocates of a privacy and non-interference of the state to private affairs of citizens are afraid of its consequences. So, the Congress of the United States considers the acts resolving application of cryptographic means only under the control of corresponding services. Thus all procedures of an exchange шифрованными messages should be under construction in such a manner that in need of special service under the decision of judicial bodies could decode them. Probably that business and at us soon enough before will reach. In this direction some steps are already made – read the decree of the president of Russia №334 from April, 3rd, 1995 “About measures on observance of legality in the field of working out, manufacture, realisation and operation шифровальных means, and also granting of services in the field of information enciphering”, actually establishing state control over working out and use of means криптозащиты information. Doubts about that, whence “ears grow” cannot be – the Federal agency for government communication and information intends to be a monopolist in this rather attractive market of devices, programs and services, and the state does not want, that its citizens had secrets from it.

Let's return to a problem essence: so, let two parties which we name lawful participants of information interchange, try to adjust confidential communication. From them one is the sender, and another – and to each of them it is necessary to be the addressee of the message though, of course, in real situations these roles are not fixed to participants rigidly both the sender, and the addressee. The problem of the sender consists in generating and sending to the addressee message T. The problem of the addressee consists in that the sent message to receive and understand its maintenance. That one only the addressee could familiarise with the message maintenance, it is necessary for sender to transform it according to some algorithm E in such a manner that who, except for the lawful addressee and, perhaps, the sender, could not restore it in a former kind. This transformation is called зашифрованием messages T, and that turns out as a result of this procedure, is called шифротекстом T '. Communication between initial text T, шифротекстом T ' and algorithm зашифрования E can be symbolically expressed by means of the following formula: T ' = E (T). Shifrovannoe message T ' is transferred by the sender to the addressee on a communication channel. That the lawful addressee could familiarise with contents of the received message, it should decipher preliminary it, that is apply to шифротексту T ' algorithm расшифрования D therefore initial message T will be restored. Thus, расшифрование the data it is carried out according to equation T = D (T '). To provide privacy of communication, algorithm расшифрования it should not be known to extraneous persons as its privacy defines privacy of the communication organised thus.

At our situation there is a third party named according to developed tradition the malefactor which wishes to prevent realisation of intentions of lawful participants of an exchange. In the most general case to execute the intentions the malefactor can intercept шифрованные messages and send the messages of one fabricated by him of the parties on behalf of another. Certainly, he does not own algorithm расшифрования – in this case all would be extremely simple for it. The circle of problems which can try to solve криптоаналитик, is wider than message decoding is simple – we will list these problems called in cryptography by threats:

·       to decode message T ', that is to receive clear text T corresponding to it ' in full or in part, or at least to make some conclusions about the maintenance of the intercepted message, leaning against the laws found out in it;

·       to generate on the basis of the data available for it message T ~ ' which the lawful addressee would accept for the original. It is thus not so obligatory, though, of course, it is rather desirable for the malefactor that he could understand sense of the made message or even could fabricate any message chosen by it at own discretion;

As code number disclosing understand successful realisation at least one of the specified threats. The first threat if it will be carried out, will break privacy of the message, and the second will break its authenticity. Degree of success in realisation listed above threats also can be various. If to exclude casual good luck successful realisation of threat of privacy of the data means mastering by the malefactor by algorithm расшифрования D, or construction of algorithm D functionally equivalent to it ', allowing for any ciphered message T ', or at least for шифротекстов from some class, to receive corresponding open message T. Similarly, successful realisation of threat of integrity of the data means mastering by the malefactor by algorithm зашифрования E, or construction of algorithm E functionally equivalent to it ', allowing for any open message T, or at least for messages from some class, to receive corresponding ciphered message T ', or, in the least successful for it a case, creation of algorithm E ~ allowing to create such ciphered message T ' which the lawful addressee would accept for the original.

For realisation of the threats the malefactor needs to perform some intellectual enough work with the intercepted data, with it to it can help криптоаналитик. It is easy to guess that the problem of the last includes криптоанализ, that is the analysis of the intercepted messages for the purpose of realisation of one of listed above threats. Thus the analyst can have the following information:

·       дешифруемый text T ', also can be available intercepted earlier шифрованные messages

(T1 ', T2 '..., Tn ' ), ciphered with use of the same algorithm, as T ';

· the       open messages corresponding to some earlier intercepted encryptions:

(T1, T2..., Tm ), Ti ' = E (Ti), i = 1..., m, where m £ n;

·       possibility to receive for any open message T chosen by the malefactor corresponding шифротекст T ' = E (T);

·       possibility to receive for any chosen by the malefactor шифрованного messages T ' corresponding clear text T = D (T ');

According to these three possibilities distinguish following principal views криптоанализа:

· the       analysis on a basis only шифротекста;

· the       analysis on the basis of not chosen clear text;

· the       analysis on the basis of the chosen clear text;

· the       analysis on the basis of chosen шифротекста;

The first possibility is at the disposal of an analyst practically always. The second possibility also is quite real: for example, investigation through an agency managed to get decoding of one of confidential messages. Moreover, this possibility is rather typical in those spheres where term of a life of the classified information is rather small, and it is quickly made public – by transfer of advertising materials, the various reportings published subsequently by mass media etc., a word everywhere where it is necessary to outstrip competitors of all at some o'clock or days. The third and fourth possibilities though seem exotic, nevertheless also can take place – if the employee of the organisation working on other party, has access to the general шифровальным to means. Certainly, the third case makes sense with reference to a decoding problem, and the fourth – imposings of the false data. First two are actual for both threats.

At a reality situation considered by us there is one more party which role ourselves will try to execute. It криптограф into which problem enters to supply lawful participants of an exchange with such algorithms for - and расшифрования that the malefactor could not execute any of the threats even in the situation most favorable for it, that is at possibility криптоанализа on the basis of any way chosen clear text. Differently, a problem криптографа is working out of confidential and authentic system of data transmission. Generally speaking, it is various, though at times and the properties connected closely enough in concrete code numbers криптосистем. We will explain their sense:

Authenticity is security of cryptographic system from imposing of the false data.

 

Privacy is security of cryptographic system from несанкциониро­ванного acquaintance with contained the data closed by system.

3.    Code numbers with a confidential key.

So, our problem consists in supplying participants of an exchange with reliable algorithms of enciphering. The first question which we to ourselves will set – whether it the problem basically, and if yes we can provide what maximum degree of privacy is solved? The answer to this question has been found by Shennonom – the theorem carrying his name, says that there are absolutely proof code numbers, that is such code numbers which cannot be opened even if криптоаналитик possesses an unlimited stock of time and computing resources. Шенноном also it has been established that a condition of absolute firmness of the code number is use in algorithm of enciphering not smaller quantity of the classified information, than contains information in the ciphered message.

How to realise such code number? Before to answer this question we will recollect that all modern code numbers are based on a principle of Kirhgofa which says that algorithms of enciphering should be under construction so that even at their disclosure all of them still provided certain level of reliability. By the way, about the author of a principle – in the literature him wrongly call "Kerkhoffom" – the author has not met a uniform case of a correct transcription of this surname. It is written “Kirchhoff” – in the same way, as a surname of the author of laws of Kirhgofa known in the electrical engineer. Кирхгоф was the Dutch, instead of the Englishman, therefore to say its surname follows according to rules of a German transcription, instead of English. We will return to a discussed theme – clearly that криптоалгоритмы, Kirhgofa constructed according to a principle should use the confidential data named a key which provide privacy of the message in the conditions of an openness of the algorithm at enciphering. In other words, privacy of the code number should be provided with privacy of a key, instead of privacy of algorithm of enciphering. It means that algorithms E and D, entered by us in consideration in the previous section, use confidential key K, and can be designated us now as EK and DK. Then the enciphering equations will have the following appearance:

T ' = EK (T) ааааааааааааа (зашифрование),

T = DK (T ') ааааааааааааа (расшифрование).

Let's recollect that in code numbers of a considered class for for - and расшифрования the same key is used. Clearly that procedure расшифрования should lead in any case to correct result. It means that what block of data T and key K were admissible, following equality should be carried out: EK (DK (T))  = T.

Let's return to absolutely proof code numbers realising a principle of Kirhgofa. As all their privacy is concentrated in key K, with reference to them the requirement of Shennona means that the size of a key of enciphering should not be less size of the ciphered message: K | ³ T |. We will believe that they have the identical size equal N bit: | K | = T | = N. It is a minimum at which absolute firmness is still possible. For зашифрования it is necessary to combine message T with key K by means of some binary operation ° so that received шифротекст depended and on initial text T, and from key K. Thus the equation зашифрования will have the following appearance:

T ' = EK (T) = T ° K.

The size шифротекста thus also is equal N bit: T ' | = T | = K | = N. For maintenance of absolute firmness of the code number the quantity of the classified information in key K should be greatest possible for its size. It means that all bits of a key should be casual with equiprobable values and are statistically independent. Such key can be received only in the hardware way, algorithmically it is impossible to develop it, as in this case the specified requirement will be broken also the code number will cease to be absolutely proof.

Let's discuss now requirements with which operation ° should satisfy. First, that enciphering was reversible, equation T ° K = T ' should be unequivocal разрешимо rather T at any values T ' and K. It means that binary operation ° should have return which we will designate through and what were N-bit blocks of data T and K, equality (T  ° K)   K = T always should be carried out      . In the second, for maintenance of full privacy of the code number it is necessary, that different keys gave for identical initial texts different шифротексты. It is equivalent to the requirement of unequivocal resolvability of equation T ° K = T ' rather K. As privacy шифрованного messages entirely leans against privacy of a key, in all the rest operations ° and can get out of convenience reasons. As such operations addition and subtraction on the module 2N can be used:

T ° K = (T + K)  mod  2N, T   K = (T – K)  mod  2N.

To carry out calculations over the message as a single whole it can appear inconvenient because of its considerable size, therefore it is expedient break the message and a key into blocks of the smaller size and to apply the specified operations to these blocks:

T = (T1, T2..., Tn), K = (K1, K2..., Kn), |Ki | = |Ti | = Ni,

Ti ° Ki = (Ti + Ki)  mod  2Ni, Ti   Ki = (Ti – Ki)  mod  2Ni.

If to finish this process of crushing to the logic end, we will come to operation of bit-by-bit addition on the module 2, named also bit-by-bit excluding or:

T ° K = T   K = T  Å K.

Last operation has appeared return to itself and for this reason, and also owing to the simplicity and ease of realisation (separate bits of the message in it are processed independently from each other), has gained the greatest distribution.

Let's short stop on the reached: the code number which we have now received, is called as disposable scale of Vernama. This code number possesses absolute firmness which, however, is paid by enough expensive price – for message enciphering the key of the same size preliminary delivered to the sender and the addressee is necessary.

It is impossible to apply the same sequence of elements of scale to enciphering of two various messages. If this requirement is broken, always it is possible to find such pair of binary operations Ä and Æ which, being applied accordingly to blocks opened and ciphered with use of the same element of scale of the data, will yield identical results:

Ti ' Ä T~i ' = Ti  Æ T~i.

It will make a problem криптоанализа especially easy, than more redundancy contains in the message. For texts in natural languages in view of their enormous redundancy this problem becomes almost trivial – to separate from each other such messages does not represent work. Such division can be executed a search method, and on each step to search some symbols participate.

If for scale imposing operation of bit-by-bit summation on the module 2 as the binary operations eliminating influence of confidential scale on result, the same operation can be used is used. Really, let, for example, two blocks are ciphered by means of the same element of scale Gi imposed on them by operation of bit-by-bit addition on the module 2:

Ti ' = Ti  Å Gi,

T~i ' = T~i  Å Gi.

Let's execute bit-by-bit addition of blocks шифротекста on the module 2:

Ti ' Å T~i ' = (Ti  Å Gi)  Å (T~i  Å Gi) = (Ti  Å T~i)  Å (Gi Å Gi) = (Ti  Å T~i)  Å 0 = Ti  Å T~i.

As we see, the result coincides with the bit-by-bit sum on the module of 2 blocks of a clear text that does криптоанализ trivial.

The requirement of unique scale for each ciphered message does enciphering by means of disposable scale of Vernama so unprofitable that its use is economically justified only in communication channels for message transfer of the exclusive importance, involved besides is not too frequent.

The barrier before which we have stopped, is insuperable: to reach эффектив­ности practical realisation криптоалгоритма it is possible only having refused absolute firmness. The code number which is not absolutely proof, can be opened for final time, more precisely, for final number of steps, each of which consists in performance of elementary arithmetic or logic operation. However nothing prevents to create to us such theoretically unstable code number for which disclosing it would be required to execute so a great number of operations that it was impracticable on computing means modern and expected in not so far prospect for reasonable time. As a measure of practical firmness of code numbers of this kind, expressed in elementary operations or the quantity of work necessary for their disclosing can serve in duration of corresponding calculations on modern computers. Let's notice that in real systems криптозащиты information are used almost exclusively theoretically unstable code numbers.

The good code number should be steady against the statistical and algorithmic analysis, that is should not exist easily обнаружимых statistical communications between opened both a text in code and dependences between them should be difficult enough for this purpose that they could be found out by the analysis. There is a clear boundary between good and the not so well designed block code numbers: the first cannot be opened in the way, more effective than full search on all possible values of a key, for disclosing of the second can appear suitable and more effective ways. How to build proof code numbers? The science about it is coded practically everywhere where deal with cryptography – the reasons which have the most general character and not containing any reality are published only. To join this secret knowledge it is possible, only working in corresponding division of corresponding special service. Well and we will try to contemplate a problem exclusively from a common sense position. By and large, it is possible to offer only two fundamental approaches to construction of the code number with a confidential key:

·       the developed element of scale Gi does not depend on the ciphered block of data Ti;

·       enciphering of a file of information T is carried out by a manipulation with it;

The first approach evidently follows from the code number of Vernama. All difference consist that in it the scale in itself is not a key element but only it is developed from key K of the fixed size by means of some set of functions fi : Gi = fi (K), or, more precisely, one universal function Gi f (i, K) – though from the point of view of mathematics this same, from the algorithmic point of view is different things. The requirement of a practical realizability of the code number in the form of the device or the computer program leads to necessity of possibility of its description in the form of algorithm with final number of the possible conditions as most which general model the final automatic machine can serve. Thus, the scale generator can be defined by means of following parities as the final automatic machine without an input:

Si =  WK (Si–1),   Gi =  QK (Si), (idle time гаммирование)

Or as the final automatic machine with an input if the developed block of scale depends on the previous block шифротекста and-or a clear text:

Si =  WK (Si1, Ti1, Ti '1),   Gi =  QK (Si) ааааааааа (гаммирование with a feedback).

The first of two parities defines a rule of change of the conditions, the second – a rule of development of a target element, that is a scale element. Clearly that for maintenance of privacy of the code number both these rules should or to be confidential, or to depend on value of confidential key K. The code numbers constructed under the given scheme, are called потоковыми as in them the stream of scale developed by the generator is used. Зашифрование (расшифрование) it is carried out by simple imposing of elements of scale on blocks opened (шифрованного) the text by means of corresponding binary operations: Ti ' = Ti  ° Gi , Ti = Ti '   Gi. Depending on used operations scale imposing can be carried out as побитово, and blocks of other size. The basic complexity at realisation of the given approach consists in working out of really qualitative source криптостойкой scales.

The second approach to construction of code numbers with a confidential key does not comprise any hints for possible ways of its realisation. In following section of article we will try to grope these ways.

4.    Base idea of the block code number.

Starting point in realisation of the considered approach is the idea to develop scale for зашифрования messages … from the message! However to make it it is directly impossible, as thus there are difficulties with расшифрованием: let the scale is developed from the ciphered block according to equation G = f (T), where fsome function. Thus the equation зашифрования will have the following appearance: T ' = EK (T) = T ° G T  ° f (T). For расшифрования messages its addressee should solve this equation rather T: T  ° f (T) = T '. If function f is difficult and нелинейна that is required for sufficient firmness of the code number, the given problem can appear almost unsoluble.

Nevertheless, by working out of the new cryptographic scheme we would not like to refuse earlier used and well proved decisions which number scale imposing on the data for their enciphering concerns. How to leave from this a difficult situation in which we have appeared? We will try to solve at least a problem part for what we will present the ciphered data file T of the size |T | N in a kind of pair blocks of the smaller size: T = (T0, T1), |T0 | = N0, |T1 | = N1, N0 N1 N where T0 will designate younger, and T1 – the senior part of file T. We will execute зашифрование the senior block by means of younger, using thus some function f, displaying the N1-bit block of the data on N0-bit, and reversible binary operation ° over N0-bit blocks of the data. The received ciphering transformation we will designate through Gf °. The equation of this transformation will be the following:

Gf ° (T) =  Gf ° (T0, T1) = (T0, T1 ° f (T0)).

For Gf ° it is easy to construct the return, or deciphering transformation Gf :

Gf (T) =  Gf (T0, T1) = (T0, T1  f (T0)).

Really, if binary operations ° and mutually return whichever there was a N-bit block of data T = (T0, T1), always fairly following equality:

Gf (Gf ° (T)) =  Gf (Gf ° (T0, T1)) =  Gf (T0, T1  ° f (T0)) = (T0, (T1  ° f (T0))  f (T0)) = (T0, T1) = T.

Clearly that function appointment f consists in masking dependence between block T0 and scale for enciphering of block T1 which of it is developed. For this purpose function f should be a confidential element of our code number – we while we will shut eyes to this infringement of a principle of Kirhgofa. We will note very important fact: our scheme is efficient at any function f, after расшифрования we will always obtain the same data which were before зашифрованием.

Before to pass to studying of the further material, readers, not so strong in the mathematician, it is necessary to get acquainted with some mathematical concepts, namely, with concept of a composition of displays and transformations. The same who owns this material sufficiently, can not read the following paragraphs printed in small print.

All articles of transformation considered in a given part are operators in set of blocks of the data, that is the functions which are accepting as argument and giving out as result blocks of the data.

1.     We name a composition of transformations A and B such transformation C = AB that whichever there was a block of data T, equality C (T) B (A (T)) is always carried out  . Thus, by definition of composition AB (T) B (A (T)).

2.     For a composition of transformations the associative law, that is for any transformations A, B is fair, C the identity is fair: A (BC) = (AB) C. Really, whatever was the block of data T, fairly following equality:

(A (BC)) (T) BC (A (T)) C (B (A (T))) C (AB (T)) = ((AB) C) (T).

Therefore in expression for a composition of three and more transformations of a bracket излишни: A (BC) = (AB) C = ABC.

3.     Among all transformations there is one special, named identical and designated by us through I. Distinctive feature of the given transformation is that it leaves the argument invariable: whichever there was a block of data T, it is always fair I (T) = T. It is obvious that the composition of any transformation A with identical gives as a result the same transformation A: IA = AI = A. Really, for any block of data T following equalities are fair: AI (T) = I (A (T)) = A (T) and IA (T) = A (I (T)) = A (T).

4.     Transformation B is called as the return to transformation A if their composition is identical transformation that is if condition AB = I is satisfied  or for any block of data T equality B (A (T)) = T is fair  . Transformation A is called as reversible if there is the return to it the transformation designated A–1: AA‑1 = I.

From the point of view stated just ciphering transformation should be reversible, that is property Gf°Gf  = I should be carried out  . It is necessary to notice that the given property is carried out always, f we would not use what function in our transformation if only binary operations ° and are mutually the return.

Now we will recollect about that the scheme offered by us has solved only half of problem as younger part T0 of block T remained not ciphered. But this problem has the obvious decision: on a following step it is necessary to cipher part T0 of file T, using the element of scale developed from part T1 ' of block T with use of some other function g, displaying N0-bit blocks of the data on N1-bit. Now both parts of the initial block will appear ciphered. For some reasons, however, it is accepted that ciphered on each such step and used for development of scale of a part are on the fixed positions in the block – the tradition orders to develop scale from a younger part and to impose it on the senior. At least, business is so in the VISITOR, DESе, and all other code numbers constructed on their image and similarity. To provide the specified property, between enciphering steps it is necessary to execute shift of parts of the block, placing corresponding parts on appropriate places.

For reasons of maintenance maximum криптостойкости and efficiency of realisation of the code number it is expedient to take the sizes of the senior and younger parts of the ciphered block identical: N0 N1 = N/2. Such condition was chosen by developers of the majority of code numbers of considered architecture. In this case between steps of algorithm of a part of the ciphered block are simply interchanged the position. However there are the code numbers which are not submitting to this rule, some words will be told about them more low in the present article.

Let's designate through S operation of shift of the senior and younger parts of a file of the information: S (T) = S (T0, T1) = (T1, T0). It is obvious that operation S is return for itself: S2 = S · S = I. Really, for any block of data T = (T0, T1) equality is fair:

S2 (TS2 (T0, T1= S (S (T0, T1)) = S (T1, T0) = (T0, T1) = T.

Then our new scheme of enciphering can be presented a composition of more simple steps:

Gf °, g =  Gf ° · S ·  Gg °.

Thus the return, or deciphering transformation can be presented a following parity:

Gg , f =  Gg  · S ·  Gf .

Really, fairly following equality:

Gf °, g ·  Gg , f = (Gf ° · S·Gg °) · (Gg · S·Gf ) =  Gf ° · S·Gg ° · Gg · S·Gf  =  Gf ° · S · (Gg°Gg ) · S·Gf  =  Gf ° · S·I·S·Gf  =  

 = Gf ° · (S·I) ·S·Gf  =  Gf ° · S·S·Gf  =  Gf ° · (S·S) ·Gf  =  Gf ° · I·Gf  = (Gf ° · I) ·Gf  =  Gf ° · Gf  = I.

Operations of imposing of scale in steps of enciphering of the block, generally speaking, can be various, however special sense in it during creation of code numbers did not see.

As already it was marked above, there are code numbers in which the ciphered block of the data shares on two not identical parts on the size. If the scale element is developed from the younger part of the block having the size N0 and imposed on the senior part having the size N1 the scheme is steadier to криптоанализу when condition N1 < N0 is satisfied  . Thus simply to interchange the position of block parts between enciphering steps does not suit any more, it is necessary to segment anew after each such shift the block. Usually in such situation use cyclic shift (rotation) of the block on N1 bit to the left or to the right, and at расшифровании between steps it will be necessary to turn the block on the same number of bits in the opposite direction. In the specified case of expression for transformations зашифрования and расшифрования the block will be the following:

Gf °, g =  Gf ° · R®N1 ·  Gg °,

Gg , f =  Gg  · R¬N1 ·  Gf ,

Where through R¬m and R®m operators of rotation of the block of the data on m bit to the left and to the right accordingly are designated. As for one step of algorithm it is ciphered N1 < N/2 block bits for зашифрования all block it is required more than two steps. Exact value of number of is minimum demanded steps to such algorithm equally éN/N1ù where through éxù the result of a rounding off of number x to the nearest whole towards increase is designated. From a reason of simplicity of realisation of the code number usually choose N1 so that the size of block N shared on it without the rest. As a rule, if N  = 64 take N1 = 16 or N1 = 8.

It is necessary to notice that the code numbers constructed by such principle, it is much less than code numbers in which the block shares on two identical parts on the size. It is caused by that in them for one step the smaller quantity of bits is ciphered, and, accordingly, it is required more steps. By such principle the code number code-named “албер”, created in bowels of one of numerous scientific research institutes, for example, is constructed, and, say, even applying for the post of the Russian standard of enciphering, for it N1 = 8.

5. The    code number of simple replacement.

That the block scheme of enciphering was steady to криптоанализу, it should possess properties of hashing and dispersion. It means that each bit of the initial text should influence all bits шифротекста, and character of this influence should not be traced neither statistically, nor algorithmically. This requirement important for block code numbers for the following reason: for code number disclosing on an algorithmic line криптоаналитик can try to deduce in an explicit form the parities connecting inputs and exits of algorithm. For потокового the code number it is useless, because these parities are entirely defined by elements of scale which are various for various blocks of the ciphered data. And here that криптоанализ has not crowned success for the block code number, it is required, that character of influence of the entrance data for the weekend was difficult enough that it could be revealed by the analysis of files of the entrance and target data. It, in particular, means absence of statistical dependence of bits of an output block from bits entrance that means in practice that in whatever image we have changed the block of the open data T, all bits of the block шифрованных data T ' = EK (T) with probability 1/2 independently from each other will change the value. But the scheme of enciphering constructed in the previous section does not possess such property. Really, let зашифрованию the block of data T = (T0, T1) then as a result we will receive is exposed  :

T ' =  Gf °, g (T) =  Gf °, g (T0, T1) = (Gf ° · S·Gg °) (T0, T1) = (S·Gg °) (Gf ° (T0, T1)) = (S·Gg °) (T0, T1  ° f (T0)) =  

 = Gg ° (S (T0, T1  ° f (T0))) =  Gg ° (T1  ° f (T0), T0) = (T1  ° f (T0), T0 ° g (T1  ° f (T0))) = (T0 ', T1 ')

Let's consider a younger part of the ciphered block of the data: T0 ' = T1  ° f (T0). It is easy to notice that dependence of bits of part T0 ' block T ' from bits of part T1 is trivial enough and does not meet the requirements stated above. Therefore designed by us криптопреобразование Gf °, g =  Gf ° · S ·  Gg ° it is insufficiently difficult that it was possible to name without stretches its cryptographic. But it can in rather simple way be extended to any number of steps n: let functions f1 are set..., fn displaying on itself set N / 2-bit blocks of the data, and steam of mutually return binary operations and in the same set. Then ciphering and deciphering transformations can be defined as follows:

Induction on number of the basic steps n it is possible to show that the second transformation back to the first:

Consistently to realise in the code number a hashing and dispersion principle, it is expedient to present ciphering transformation in the form of enough great number (n) steps each of which represents realisation concerning the simple code number. So, in the Russian standard of enciphering the number of such steps equally 32, and in American – 16, but steps to it is slightly more difficult. Is криптоалгоритмы similar architecture with smaller number of steps n, for example – FEAL [7], for which various variants n = 4 or n = 8.

As it was already marked, the kind of binary operations of imposing of scale and is not so important from the point of view of firmness of the code number, therefore, as a rule, the idle time for practical realisation a variant – operation bit-by-bit excluding undertakes or. It allows to realise direct and return procedure of transformation by the same image, they will differ only order of use of ciphering functions f1..., fn. For fuller dispersion of the information of the initial data криптопреобразование can be added initial (Y0) and final (Y1) by shifts of bits or others simple and evidently reversible transformations. As a result we will receive following ciphering transformations:

As usually, through Y–1 the return is designated to Y transformation. To keep uniformity direct and return криптопреобразований, it is necessary to provide performance of conditions Y0–1 =  Y1, Y1–1 =  Y0, that is substitutions Y0 and Y1 should be mutual the return. We receive following formulas for direct and return криптопреобразований:

Transformation with additional shift of bits possesses higher криптостойкостью in comparison with similar transformation without shift only in that case when it is a confidential element of the code number. Really, if it not so the first action криптоаналитика will subject all available in its order blocks of the data, both opened, and ciphered, this shift Y, and thus to reduce an initial problem to a problem of disclosing of the code number without shift. From this point of view initial and final bit shifts in algorithm DES are no more, than ornaments and do not render appreciable influence on it криптостойкость.

Now we will recollect about infringement of a principle of Kirhgofa consisting in use as confidential elements of functions of enciphering fi. That our algorithm of enciphering did not break it, slightly we will change the scheme of use of functions fi – we will make their depending on confidential key K: fi (T) = fi (T, K), where fi – known (open) function, and a K-confidential element of the code number (key). As a rule, all functions fi equally use преобразуемый the block of data T and differ only with the scheme of use of key K, that is it is possible to write down: fi (T, K) = f (T, j i (K)) = f (T, Ki ) where through Ki =  j i (K) we have designated a code developed from key K and used on i th step of enciphering which we name for brevity “a step-by-step key”.

We needed to discuss last detail in construction of the block code number. Till now we did not demand, that the size of ciphered block T was to constants, however now we should make it for following reasons:

·       Many elements of the code number, such as shifts of bits and function of replacement of bit groups in data file assume that преобразуемый the block has the fixed size. Though basically it is possible to set a rule of construction of such elements for blocks of any size, to put this rule into practice would be extremely inconveniently.

·       If was probably any to increase the size of the ciphered block, it would lead to a situation when the block of the data of the big size is ciphered for one pass on a key much the smaller size, and such scheme becomes less steady against attempts algorithmic криптоанализа.

Owing to the specified reasons for enciphering under the scheme considered by us blocks of the data of the fixed size for this reason the given code number is called as block should be exposed only. If necessary message T breaks into some blocks of the identical size which are ciphered independently from each other:

T = (T1, T2..., Tn),  T ' = (T1 ', T2 '..., Tn ') = (EK (T1), EK (T2)..., EK (Tn)).

For this reason the given scheme of enciphering name the code number of simple replacement as finally it is reduced to replacement of one values of blocks of the data by others. For the algorithm of enciphering constructed by us, obviously, there is a problem if the size of the ciphered text is not multiple to the size of the block криптоалгоритма. This, and a number of other questions will be discussed in following section.

The size of blocks of enciphering is defined by the developer of the code number from a condition of achievement necessary криптостойкости. The choice of the insufficient size of blocks will make possible криптоанализ on the basis of statistical regularities. On the other hand, the unjustified increase in the size of the block will make the code number bulky and inconvenient for application, therefore in this point in question it is necessary to search for the compromise. Practically in all code numbers of considered architecture known to the author the size of the block equal to 64 bits is used.

In summary we will bring some result of our researches: For definition of the block code number it is necessary to set the following:

 

1.    Numerical parametres of algorithm:

· the                size of the ciphered block of the data |T | N;

· the                size of a key |K | = NK;

· the                size of a "step-by-step" key |Ki | = NK ';

·                number of steps of enciphering (rounds) n;

2.    Enciphering function f, accepting as argument and returning as value N / 2-bit blocks of the data. Enciphering function depends also from NK ' - the bit confidential block of the data – "a step-by-step" key;

3. A    set of functions j i, 1  £ i  £ n for development of "step-by-step" keys Ki from an initial key of enciphering K: Ki =  j i (K);

4.    Shifts of bits Y in the N-bit block of the data;

 

Ciphering and deciphering cryptographic transformations are under construction as a composition described above simple steps Gi S, Y:

E~KY = Y ·  G1 · S ·  G2 · S ·... · S ·  Gn · Y–1,

D~KY = Y ·  Gn · S ·... · S ·  G2 · S ·  G1 · Y–1.

Here Gi and S designate accordingly a step of ciphering transformation and shift of the senior and younger half of ciphered block:

Gi (T) =  Gi (T0, T1) = (T0, T1 Å f (T0, Ki)) = (T0 ', T1 ') = T ',

S (T) = S (T0, T1) = (T1, T0).

As it has been noted above, the given scheme can be generalised on a case of division of the ciphered block of data T on two subblocks unequal on the size. Additional transformations of the data to the beginning, the end, or at the intermediate stages криптопреобразования Besides, can be added, and also instead of function bit-by-bit excluding or it is possible to use any another for scale imposing on a part of the ciphered block. The code number which we have just constructed, is called as the code number of simple replacement as as a matter of fact its action consists that ciphered blocks of the data are replaced with blocks шифротекста irrespective of other blocks.

6. The    Russian standard of enciphering.

Time has come to tell about the algorithm of enciphering which is the Russian standard. This standard has a designation of GOST 28147-89 of which appears that it has been accepted in 1989. Its basis is made by procedures зашифрования and расшифрования on algorithm of simple replacement of 64-bit blocks of the data, and already with their use other algorithms of enciphering are under construction – as it to make, is discussed in following sections. In the present article it is considered only криптоалгоритм GOST 28147-89 [6], the description of some other code numbers with similar architecture can be found in the literature [2,7,8], therefore the author has decided not to stop on them. Now we will consider GOST under the scheme planned above:

1.    We will define numerical characteristics of algorithm:

· the       size of the ciphered block is equal to 64 bits: |T | =64;

· the       size of a key is equal to 256 bits K | = 256;

·       on each step of algorithm the 32-bit key element is used: | Ki | = 32;

·       number of repetitions of the basic step (number of rounds) n = 32;

2.    Enciphering function is defined as follows:

· the       initial data for enciphering function are 32-bit the element of data T and "step-by-step" key Ki;

· the       block of data T and "step-by-step" key Ki develop on the module 232: S = (T + Ki)  mod 232;

· the       received 32-bit block of the data is interpreted as a file from eight 4-bit groups S = (S1, S2..., S8), | Si | = 4, and in each group substitution by means of the corresponding knot of replacements is carried out: Si ' =  hi, Si. As a result we receive the following block of the data: S' = (S1 ', S2 '..., S8 ') = (h1, S1, h2, S2..., h8, S8);

· the       result of the previous step rotates on 11 bits to the left, that is towards the senior categories: if S' = b31b30... b21b20... b1b0, T ' = R¬11 (S') = b20... b1b0b31b30... b21;

· the       received block of data T ' is value of function of enciphering: T ' = fi (T, K);

3.    At enciphering the following confidential (key) information is used:

· a       key – a 256-bit file of the information structured in a file from eight 32-bit elements which we will number as their use in an enciphering cycle: K = (k1, k2..., k8), | K | = 256, | ki | = 32;

· the       table of replacements – a set from eight – on number of bit groups into which the 32-bit block of the data breaks at enciphering function evaluation – knots of replacements: H = (H1, H2..., H8). Each knot of replacements is substitution in 16-element set of all possible values of 4-bit codes, and thus can be presented in the form of a file from 16 various 4-bit numbers: Hi = (hi, 0, hi, 1..., hi, 15), | hi, j | = 4, 0  £ hi, j  £ 15, for any ijk (j  ¹ k), the condition hi, j ¹ hi, k should be satisfied  . The size of each knot of replacements is equal | Hi | = 8× | hi, j | = 64 bits, and the size of all table of replacements | H | = 8× | Hi | = 8×64 =  512 bits or 64 bytes;

4.    We will define an order of use of a key at enciphering, that is we will set function j i developments of a "step-by-step" key from an initial key of enciphering K: Ki =  j i (K). As "step-by-step" keys Ki in the VISITOR certain elements kj key K undertake: Ki = kj. However such elements only 8, and steps to a cycle of enciphering 32, means, it is necessary to set function p (i), displaying 32-element set of steps to an enciphering cycle in 8-element set of parts of a key: Ki = kp (i), 1  £ i  £ 32 1  £ p (i) £ 8 we Will set this function in a tabular and formular kind:

         

i

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

p (i)

1

2

3

4

5

6

7

8

1

2

3

4

5

6

7

8

i

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

p (i)

1

2

3

4

5

6

7

8

8

7

6

5

4

3

2

1

         

                

       Differently, during a cycle зашифрования key elements are used consistently one after another, thus the key "is looked through" four times – first three in a direct direction, the fourth – in the return. The readers who have well acquired a material of the previous sections, without effort will think that in a cycle расшифрования key elements are used in the return in relation to a cycle зашифрования an order, that is at first the key is looked through once in a direct direction, then three times in the return.

Now we will talk about the table of replacements. It is some analogue of S-blocks (S-boxes) the American standard, but, unlike the last, first, same on all steps of a cycle of enciphering and secondly, is not fixed and is a confidential element of the code number. It is necessary to notice that the algorithm of enciphering is reversible at any filling of knots of replacements even if they and do not set correct substitutions in 16-element set, that is contain repeating elements of replacement: hi, j hi, k at some ijk (j  ¹ k). However such replacement conducts to loss of the information on replaced value, and, as consequence, to decrease криптостойкости the code number, therefore possibility of it is not provided in the VISITOR.

Let's notice that the basic confidential element of the Russian code number is the key. The algorithm should remain криптостойким even in case of disclosing of the table of replacements that, however, takes place not at all its possible values. Existence of "weak" tables of replacements, that is tables at which use криптостойкость the code number essentially decreases, does not raise the doubts – as an example the trivial table at which use any value is replaced with it here can serve. However in wide ranges of experts-kriptografov it is for certain not known, how is similar tables much and whether there is a criterion allowing for the concrete table unequivocally to define, whether it is weak or not. It is obvious that if such criteria and exist, they are carefully coded, any data on this question, no less than concerning quality of keys, not published in the open press.

However business with a choice of the key data is not too badly – with the probability slightly different from unit, in a random way chosen key data will not lead to catastrophic decrease криптостойкости the code number, and cost of its disclosing still remains enough high and hardly it will appear on a teeth to any commercial structure, let even very large. Well and civil services if necessary can receive all their interesting information and without resorting to decoding. For this reason for the usual user, cost of the protected which information does not exceed the sum of an order of several hundreds thousand US dollars, will be the good statistical quality of the key information consisting in the following quite enough:

· the       key should be a file from 256 independent bits with equiprobable values;

· the       table of replacements should be a set from eight independent knots, each of which is casual substitution in 16-element set;

In addition it is necessary to rebuke the following: if the functions expressing bits of result of replacement through bits of the initial block turn out simple enough, it will weaken the code number. So, harmless at first sight knot of replacements Hi  = (9, 8, 3, 10, 12, 13, 7, 14, 0, 1, 11, 2, 4, 5, 15, 6) actually is weak as leaves the second and third bits of group invariable that becomes obvious if to write down it in the tabular form with binary values of argument and function:

S

0000

0001

0010

0011

0100

0101

0110

0111

H (S)

1001

1000

0011

1010

1100

1101

0111

1110

S

1000

1001

1010

1011

1100

1101

1110

1111

H (S)

0000

0001

1011

0010

0100

0101

1111

0110

Besides, the table of replacements can contain roundabout ways of other types, allowing to decipher the message in more effective image, than full search on possible values of a key – but it already a theme not for journal article.

7.    Lacks of a mode of simple replacement.

Use of the block code number in a mode of simple replacement has a number of the lacks reflected in firmness and convenience of use of the code number. The first and most serious lack of simple replacement consists that in this mode зашифрование identical blocks of the initial text gives as a result identical blocks шифротекста that facilitates a problem криптоаналитика. Really, on a basis only шифрованных the data it can make some conclusions about properties of the initial text that, certainly, is not advantage of the code number.

Let's result a typical example: let зашифрованию the information on a floppy disk is exposed. Seldom there is a situation when the data occupies all disk, as a rule its considerable part remains free. The diskette part, never containing the helpful information, is usually filled by the fixed codes which have been written down there at formatting, and at it зашифровании we will receive the fixed blocks шифротекста. Then, analyzing given a diskette, криптоаналитик can define to within several bytes the size of a file of the helpful information containing on it that in some cases, for example, if the format and the message maintenance are connected with the size of a corresponding file, can facilitate to it a decoding problem.

It is possible to offer updating of the scheme of enciphering on algorithm of the simple replacement, eliminating the given lack – for this purpose before зашифрованием messages it is necessary to execute its randomization. This action consists that blocks of the initial text are modified in the individual image, for example, комбинируют­ся with the data developed by the gauge of pseudo-random numbers (ПСЧ) by means of some binary operation °, having return operation . Зашифрование and расшифрование it will be carried out according to following equations:

Ti ' = EK (Ti  ° Gi),

Ti = DK (Ti ')   Gi

Where Gi – the blocks of the data developed by gauge PSCH. As already it was marked earlier, as operation of imposing/removal of scale most all procedure bit-by-bit excluding approaches or. The period of repetition of sequence ПСЧ {Gi}, developed by the gauge, should exceed the greatest possible number of blocks in the message.

However the given report is insolvent, if криптоаналитик possesses possibility of the analysis on the basis of the chosen clear text that is if it can receive any open message chosen by it ciphered on the same key and with use of same elements Gi , as дешифруемый the text. Really, suppose, that криптоаналитик has such possibility. Then it can subject зашифрованию a file consisting of one blocks-fillers and to compare the received result with analyzed шифротекстом:

Ui = U, where U – a probable block filler,

Ui ' = EK (Ui  ° Gi).

If condition Ui ' = Ti ' is satisfied  , it means that Ti = U, and our cryptographic report does not carry out the problems assigned to it.

To get rid of the specified lack, the enciphering report should provide uniqueness of sequence of elements of scale Gi. How it can be carried out? As a rule, all algorithms of development ПСЧ have some set of numerical parametres unequivocally defining received target sequence {Gi}. It allows to provide its uniqueness for various processes of enciphering by one of next two ways:

·       to make numerical parametres of algorithm of development ПСЧ Gi confidential. It is impossible to name this way good as it leads to increase of total amount of the confidential key information, that is, inherently, assumes use of additional algorithm of enciphering.

·       to provide uniqueness of a used set of numerical parametres with corresponding construction шифрователя. Also it is impossible to consider this way comprehensible as шифрователь in this case should contain some block providing reception of a unique vector of initial parametres for development Gi that will complicate its structure. Besides, in this case it is necessary to forbid enciphering on algorithm of simple replacement without use of elements Gi as if it not to make, криптоаналитик can execute a combination of the block-filler with elements Gi independently, having subjected зашифрованию последователь­ность blocks {Ui}, where Ui = U  ° Gi.

As we see, the given way of randomization of the initial message in itself generates more problems, than allows to solve, and consequently its use though and it is possible basically, has not received some considerable distribution. Moreover, further we will see that at enciphering on a method гаммирования there are similar problems.

The second lack which is taking place at use of the block code number in a mode of simple replacement, is caused by a problem of incomplete blocks, or "tails". As in the given mode криптопреобразованию blocks of the fixed size are exposed only, there is a problem if the size of the ciphered message is not multiple to the size of the block used криптоалгоритма. The problem essence consists in what and how to supplement "tails" to full-size blocks that it was convenient in use and did not reduce криптостойкости the code number. We will consider possible ways of the decision of the given problem:

·       it is possible to add "tail" with the fixed data – for example, zero. It, however, will essentially lower криптостойкость last block as криптоаналитику, possessing the information on a way of addition of "tail", it is required to execute search on set of possible values of this block, the full space of values of the block is ready smaller, than.

·       it is possible to supplement "tails" with the data from full blocks. As a whole this quite good decision, but it does not work, if the incomplete block – unique that is if the length of the message is less than size of the block of the code number. Besides, using the given approach, we will come up against sooner or later a situation when for "tail" addition the fixed parts of the message possessing insufficient uncertainty for криптоаналитика will be used. So, for example, many messages begin with a signature stamp which can accept only two – three possible values, and various forms of its record in a text kind there can be a maximum some tens variants. If for "tail" addition the part of such block there is a situation similar considered in previous point is used – "tail" can become an easy mark криптоаналитика.

·       application for addition of "tail" of a separate constant confidential element does not approach for the same reason, as the first way – use of the given element in parts does its vulnerable to криптоанализу. Such scheme appears defenceless before the analysis on the basis of the chosen clear text. Besides, the given way increases total amount of the confidential (key) information that is rather undesirable.

·       perhaps, the best possible way consists in using for addition of "tail" the data from the hardware random-number generator. Here the gauge developing really random numbers, having high statistical quality is necessary. For this reason various program gauges PSCH here do not approach. Owing to it often such way appears unacceptable for economic reasons as demands presence on each computer-shifrovatele of rather expensive equipment room components.

As we see, the second problem of enciphering in a mode of simple replacement also has no effective and at the same time economic decision. Besides, this problem creates one more, purely technical complexity – after зашифрования in a mode of simple replacement all categories of the received block become meaning, and it means that together with шифротекстом it is necessary to store now the size (number of bits or bytes) last, incomplete block of the initial text that leads to change of its size, and it in certain cases is undesirable.

The third lack of enciphering of a mode of simple replacement consists in its instability before the updating of the message consisting in shift of blocks шифротекста. Really, if we make changes to the block шифротекста "at random" that most likely after расшифрования it it will appear “запорченным”, that is its contents will be senseless. The reason of it consists that all natural and artificial languages have huge redundancy, and the changes brought in the block шифротекста casual, that is the unpredictable image for us, influence the corresponding deciphered data and probability to receive making sense result is smallest. An another matter if we simply interchange the position, we delete or we duplicate blocks шифрованного messages. In this case we can receive the result having some sense, and such infringement of integrity of the data can appear not noticed if not to accept special measures.

Owing to stated above reasons use of the block code number in a mode of simple replacement can be recommended only for enciphering of small data files on the volume which size is multiple to the size of the block used block криптоалгоритма and which do not contain repeating blocks. To this set of requirements quite satisfy only files of the key information. For this reason DES does not recommend, and the Russian standard of GOST 28147-89 directly forbids to use enciphering in a mode of simple replacement for the data which is not the key.

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

The procedure of enciphering offered in the previous section on a method of simple replacement from use of the gauge of pseudo-random numbers can be slightly changed that will release it from a number of lacks. Зашифрованию on algorithm of simple replacement it is necessary to subject the blocks developed by gauge PSCH, and already them to use as the scale combined with blocks of the data by means of binary operations ° and :

Ti ' = Ti  ° EK (Gi) (зашифрование),

Ti = Ti '   EK (Gi) (расшифрование),

Where blocks of scale Gi in the size | Gi | = | T | = N are developed by means of the gauge of pseudo-random numbers which is, as a rule, recurrent algorithm:

Gi+1 =  g (Gi), where g – some function realised algorithmically.

What requirements should be shown to ПДПСЧ to provide sufficient quality of the code number? First of all we will notice that is not required криптостойкости, good statistical parametres for developed sequence as they are provided further зашифрованием blocks on algorithm of simple replacement.

1.    It is necessary, that the period of repetition of generated sequence ПСЧ {Gi} was big enough, it is better – greatest possible. At least, it should surpass the greatest possible quantity of blocks in the ciphered data file. If to proceed only from this requirement, use of elementary of the possible gauges, defined by a following parity would be the most suitable: Gi+1 =  (Gi + 1) mod 2N, or simply Gi =  i mod 2N. But the matter is that this gauge PSCH does not provide performance of second enough important requirement to ПДПСЧ:

2.    It is necessary, that the elements of sequence next or close on an arrangement {Gi} it is enough, that is at least, in several bits, differed from each other. It would be extremely desirable, that distinctions between them were in each byte. For the elementary generator offered in point 1, half of pairs the next values differs only in one bit: G2i+1 =  G2i Å 1.

The sense of the first requirement becomes obvious recognising that a method гаммирования inherently demands disposable scale, differently it is easily opened on an algorithmic line. If the period of repetition of developed scale is insufficiently great, various parts of the same long message can appear ciphered by means of identical sites of scale. It on many usages reduces firmness of the code number, doing by its easy mark криптоаналитика. The second requirement is less obvious, and, generally speaking, takes place only for code numbers of quite certain architecture in which the enciphering step is a combination of several rather simple transformations, during each of which distinction in ciphered blocks of the data increase rather slightly. Therefore, if we subject to enciphering two blocks different only in a unique bit, serious distinctions between them will appear only through some such simple steps that reduces firmness of the code number a little and facilitates a problem криптоаналитика. Certainly, in a case STATE THAT this decrease not so is great, but developers of algorithm have decided to make secure. Gauge PSCH entering into the Russian standard on enciphering, assumes independent processing of the senior and younger half of developed block Gi = (Gi, , Gi, 1):

Gi+1,0 =  (Gi, 0 + C0) mod 232,

Gi+1,1 =  (Gi, 1 + C1 – 1) mod (232 – 1) + 1,

Where constants C0 and C1 have following values in 16-richnoj to a notation: C0 =  101010116, C1 =  101010416.

Such ДПСЧ ненамного it is more difficult than the elementary, however meets all requirements listed above: the period of repetition of sequence developed with its help is great enough and close to maximum, and blocks received with its help differ at least in one bit in each byte.

Let's notice that the given algorithm is simple both in an equipment room, and in program realisation, – we will recollect that all integer calculations in the COMPUTER are conducted on the module 2N, where N-word length of a machine word. The first of two parities is realised on all without an exception 32-bit types of processors for one command, the second though looks more terribly, than the first, actually is realised ненамного more difficult it. It becomes obvious if it to write down in the following form:

On all 32-bit processors known to the author recurrent parities for development of the next element it is realised all for three machine commands:

add

G0,01010101h

add

G1,01010104h

adc

G1,0

Commands are given in mnemonic of firm Intel for the processor made by it iAPX386, G0, G1 – 32 bit elements of the data – registers or double words in memory, accordingly younger and senior half of 64-bit block of the data from which after зашифрования on algorithm of simple replacement the scale block turns out.

It is obvious that at mode use гаммирования, as well as in any other case when recurrent gauge PSCH is used, the additional element of data G0, the first in recurrent sequence {Gi} is necessary. To complicate some possible ways криптоанализа, in the Russian standard of enciphering element G0 turns out зашифрованием on algorithm of simple replacement of the block of data S of the same size | S | = | G0 | = 64, named синхропосылкой or initial filling: G0 = EK (S). For enciphering scale blocks, since G1 are used. Синхропосылка it should be known to the party accepting the message, but the requirement of uniqueness of scale of the enciphering unequivocally defined by a combination синхропосылка+ключ, leads to necessity to use unique синхропосылку for each transferred message. As its privacy is not required for maintenance of firmness of the message, синхропосылка is usually transferred in an open kind together with the ciphered message.

It is obvious that гаммирование is a variant потокового enciphering, that is in the present section we have constructed the mechanism, allowing to create потоковые code numbers on the basis of the block. According to it the algorithm of enciphering offered by us possesses all advantages and lacks потоковых code numbers. First of all we will notice that гаммирование it is free from many lacks of simple replacement.

First, identical blocks of the initial text after зашифрования will give various blocks шифротекста that does not facilitate a problem криптоанализа on a basis only шифротекста.

Secondly, as well as in all line code numbers, there is no problem of the incomplete block of the data. Really, at зашифровании the last in the message of the block of data Tn of the incomplete size Tn |  < N from developed for this block of scale we can take a fragment of the same size. This approach is obvious, if operation of imposing of scale is bit-by-bit, but can be applied and in other cases. It is important that thus we will receive the block шифротекста the same size, as the block of the initial data. Thus, зашифрование on a method гаммирования does not change the size of the ciphered data that in some cases happens important.

In the third, the facts of any manipulations both over parts криптоблоков, and over the whole blocks, such as their shift, removal, duplication, become obvious after расшифрования is it is shown by that in a greater degree, than more redundancy contains in the ciphered message. Especially brightly this effect is shown for text files – if to such manipulations to subject шифрованное the message made on one of natural languages after расшифрования we will receive full rubbish.

гаммирования in much bigger degree, than to a mode of simple replacement, property of non-distribution of an error is inherent in a mode. If in the second case the error extends within all changed cryptographic block in the unpredictable image for the malefactor in the first case its influence on the corresponding block of a clear text is rather easily predicted that does possible the directed updating of blocks шифротекста. If to updating to subject bit in the data file ciphered гаммированием with use of operation bit-by-bit excluding or after расшифрования changed there will be only a same bit in a clear text.

The specified property гаммирования is unpleasant enough, as inherently means that the malefactor, influencing only on шифротекст, can change at own discretion any categories in a corresponding clear text. How much it can be dangerous, we will explain on a following example: let the postman – the malefactor transfers шифрованное the message which it cannot decipher, however can make to it any changes. The worker of branch of a company serving communication ЭМВ, intended for message transfer in head branch of firm can be such postman, for example. Let it transfers the certain document made in the form of a text file, ciphered in a mode гаммирования in which as he knows, record of some number begins with 13 positions, for example, the sums of its premium. It can quite appear that to it all sum is known or, at least its some part – we will assume that number record begins with a symbol ‘ 1 ’, and the malefactor knows it. Then for it it is possible to forward this figure on another, for example – on ‘ 9 ’. All that for this purpose is required is to replace 13th byte of message B13 with the new value calculated as follows: B ' 13 = B13 Å ' 1 '  Å ' 9 '. Through ' 1 ' and ' 9 ' we have designated codes of figures 1 and 9 accordingly in that system of the coding in which the message text is prepared. If it ASCII enough to invert only one bit of the message: B ' 13 = B13 Å 8. After расшифрования the addressee will receive the message in which instead of true figure 1 there is figure 9, and more no changes are present! It is obvious that the given substitution cannot be found out, if in the transferred data file there is no additional information, except the ciphered initial message. The resulted example once again illustrates that fact that maintenance of privacy of the message (its enciphering) in itself does not provide its authenticity, that is authenticity. In what the reason of such feature гаммирования? The matter is that this mode does not provide rather desirable for all code numbers of hashing of bits of the message, that is influence of one bit of the initial text on some bits шифротекста.

Other feature гаммирования, complicating the mechanism of its use is a necessity of maintenance of uniqueness of scale. As the scale is unequivocally defined by a key and синхропосылкой, this pair should be unique for everyone шифрованного the document that leads at a constancy of a key of necessity of appointment to each message unique синхропосылки. Therefore any report of enciphering (algorithm of enciphering of higher level) is completely unstable to the analysis on the basis of any way chosen clear text if криптоаналитик can appoint at own discretion синхропосылку or use for enciphering of the message a method of simple replacement.

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

At synthesis of algorithm of block enciphering we already faced idea to develop scale for enciphering of the next block of the data with use of one or several previous blocks of the data.

Gi+1 = f (Ti), or, more обще:

Gi+1 = f (T1, T2..., Ti).

At this scheme of enciphering as well as at usual гаммирования, there is a problem of reception of the first element of scale. The way of its decision is quite traditional: the initial text is supplemented with the fictitious unclassified block T0 which unique appointment – to be a basis for development of the first block of scale: G1 = f (T0).

As well as at гаммировании without OS, this block should be a part шифрованного messages:

T ' = (T0, T1 ', T2 '..., Tn ' ).

If we have decided to develop blocks of scale from blocks of the initial text it is necessary for us to hide thus any statistical regularities of this text. The most obvious and already tested way for this purpose – to use ciphering transformation, that is algorithm of simple replacement:

Gi = EK (Ti),

Ti ' = Ti  Å Gi = Ti  Å EK (Ti1).

But the offered approach in its original form possesses many lacks of algorithm of simple replacement for which overcoming we, actually, and have started various improvements of the scheme of enciphering. We will pay attention that at its use the block шифротекста depends only on blocks of the initial text corresponding and previous it:

Ti ' = Ti  Å EK (Ti1) = f (Ti, Ti1).

It means that at зашифровании a file of identical blocks of the data corresponding blocks шифротекста, since the second of them, also will be identical are becomes obvious of consideration of the equations зашифрования:

Ti ' = f (Ti, Ti1),

Ti ' +1 = f (Ti+1, Ti),

Ti1 = Ti = Ti+1 ® Ti ' = Ti ' +1.

As we see, on the given property the algorithm of enciphering offered by us is not better at all than simple replacement. However it very easily can be improved, if for scale development to use blocks шифротекста, instead of a corresponding clear text:

Gi = EK (Ti '1),

Ti ' = Ti  Å Gi = Ti  Å EK (Ti '1) (зашифрование),

Ti = Ti ' Å Gi = Ti ' Å EK (Ti '1) (расшифрование).

Now each block шифротекста depends not only from corresponding, but also on all previous blocks of the initial text:

Ti ' = Ti  Å EK (Ti '1) = f (Ti, Ti '1), but

Ti '1 = Ti1 Å EK (Ti '2) = f (Ti1, Ti '2), therefore

Ti ' = f (Ti, Ti '1) = f (Ti, Ti1, Ti '2) = ... = f (Ti, Ti1..., T1, T0), where

T0синхропосылка.

The improvement executed by us does гаммирование with a feedback free from lacks of simple replacement. Really, both modification of blocks шифротекста, and a manipulation the whole blocks leads to unpredictable changes for the malefactor in the deciphered text therefore it loses possibility to render such influences purposefully.

As we have shown earlier, each block шифротекста at зашифровании is influenced by all previous blocks of the initial text and синхропосылка: Ti ' = f (Ti, Ti1..., T1, T0). A bit different though rather similarly on the blocks of a clear text received at расшифровании, blocks шифротекста influence. For explanation of character of this influence once again we will write down the equations расшифрования for two adjacent blocks of the data:

Ti = Ti '  Å EK (Ti '1),

Ti+1 = Ti ' +1 Å EK (Ti ').

From these equations it becomes clear that each block шифротекста at расшифровании influences only two blocks of a clear text: on the block corresponding to it, and on the block following it. And in the first case this influence has the same character, as well as at use usual гаммирования, and in the second – as at simple replacement. Thus, if the malefactor makes changes to the block шифротекста, they will be reflected in current and following blocks of the message.

It is convenient to explain display of this influence on an example from the previous section: if the message has been ciphered on a method гаммирования with a feedback and the changes specified in an example after расшифрования the addressee will see the following picture have been made to it:

·       in the changed block all also, as well as at usual гаммировании – instead of true figure one costs the nine imposed by the malefactor, and more no changes are present;

·       in the block following for changed, a picture same, as well as at simple replacement – the block represents a casual senseless combination of bits;

·       all other blocks remained invariable;

Thus, the mode гаммирования with a feedback has the same advantages, as usual гаммирование, and at the same time is free from its lacks. Гаммирование from OS it is steady against shifts of blocks and to the directed updatings шифротекста if not last block only is modified. Differently, the malefactor making changes in шифротекст, cannot precisely calculate their influence on a clear text if, of course, does not possess a confidential key. On the other hand, for this mode as for a special case гаммирования, there is no "tail" problem – last incomplete block of the data and unlike гаммирования without OS not so a uniqueness acute problem синхропосылки. We will explain last remark: really, at usual гаммировании the developed scale is unequivocally defined синхропосылкой and a key: Gi = f (i , T0 , K ) whereas at гаммировании from OS it depends also on the ciphered data: Giос = f (i , T0, T1..., Ti–1, K ). Therefore, if two messages, not containing identical blocks, are ciphered with use of the same key and синхропосылки equality Ti ' Å T~i ' = Ti  Å T~i is carried out only at i = 1 that facilitates a decoding problem only the first, but in any way the subsequent blocks of the message. It reduces a problem sharpness, but, certainly, does not remove it completely. If криптоаналитик possesses possibility of the analysis on the basis of any clear text, including a choice синхропосылки, such scheme of enciphering is unstable to the analysis. Thus, and in this case it is necessary to take care of originality синхропосылки.

Finishing the story about гаммировании we will notice that the Russian standard of enciphering does not provide any other modes of enciphering, except described above. The American standard defines some more modes with a feedback, however they is unprofitable differ from described above themes that for one reference to procedure of simple replacement the portion of the data t, in the sizes smaller is ciphered, than the full 64-bit block of the data of algorithm DES, |t | < 64 that, certainly, reduces speed шифрователя without some appreciable increase of its firmness. Besides we will notice that all told in the given section of article remains true if instead of algorithm of simple replacement in accordance with GOST to use any other algorithm of simple replacement to it can be DES, FEAL, албер etc. – firmness received thus потокового the code number completely is defined by firmness of the used code number of simple replacement.

10.    Имитозащита.

As we already repeatedly showed in examples, enciphering in itself cannot protect the transferred data from modification. It is reflexion of that fact that privacy and authenticity – an essence незави­симые properties of cryptographic systems. Thus, at the organisation шифрованной communication needs to take care separately about имитозащите the transferred data.

Имитозащита there is a system protection шифрованной communications or other криптосистемы from imposing of the false data.

As we consider systems of protection the information providing necessary characteristics only by a manipulation by the information irrespectively of properties of its material carriers, maintenance of authenticity of the message can be reached only a bookmark in it of certain redundancy which with sufficient degree of reliability would allow to find out all made in it in the unapproved image of change. The most simple and obvious way it to make – to add to the message the additional code named a control combination or имитовставкой, depending on its maintenance:

T ~ = (T, Y ), where Y = f (T ).

At message reception the party which has accepted it checks performance of condition Y = f (T ) and if it is fair, the message is considered original, otherwise it is rejected as false.

Имитовставка there is the control combination added to transferred сообще­нию for the purpose of protection of system from imposing of the false data and depending on its maintenance.

As the elementary way of calculation of a control combination the control sum of blocks of the message on the module of some number can serve – usually the size of a control combination is equal to the size of blocks of the data:

f (T) = (T1 + T2 +... + Tn) mod 2N, where N = | Ti | – the size of blocks.

However it is obvious that the given way of calculation of a control combination is not necessary for имитозащиты as its fake does not represent a special problem. To understand what properties the algorithm of development имитовставки should possess, we will consider possible threats of authenticity of the data:

 

· the       malefactor can try to change data T ® T ~ so that them имитовставка remained invariable: f (T) = f (T ~);

· the       malefactor can try to supply message T fabricated by it ~ with correctly calculated control combination f (T ~), having given out that it for the original;

 

Any practical scheme имитозащиты should provide effective protection against two listed above threats that it is impossible to tell about имитовставке – the control sum.

For calculation of such control combination irreversible function can be used so-called вычислительно. Function Y = f (T ) is called вычислительно as irreversible if definition of such values T for which the equation f (T )  = Y is fair   , that is calculation of inverse function T = f1 (Y ) вычислительно is impossible. In practice it means that such value T cannot be defined in more effective way, than search on set of all its possible values. The size имитовставки Y |Y | =  N should exclude a little significant probability of a successful fake of the message which for an analyst a case is equal in the worst p = 2N.

Clearly that the concept of computing irreversibility extremely difficultly is formalized and consequently its performance cannot be checked up for concrete algorithms. The scheme имитозащиты, based on irreversible function, is steady in relation to the first threat. Really, that it to realise, the malefactor should pick up message T under set control combination Y for what it is necessary for it to decide the equation f (T )  = Y rather T that under our assumption it is impossible for comprehensible time. However the given scheme имитозащиты does not protect from the second threat. To make its steady against it, it is possible to transfer имитовставку together with the message ciphered on the same or other key. The control combination calculated thus, in the foreign literature is called by a code of detection of manipulations with the data (Manipulation Detection Code), and is in abbreviated form designated MDC. Irreversible function of compression of the data is necessary for realisation of the given method вычислительно. The word "compression" is present at the function name because irrespective of the size of the message the size of a control combination is always constant, and, naturally, in the majority of practical cases there is less than size of the message. However the corresponding area of mathematics is so difficult that computing irreversibility while formally is not proved for one algorithm of compression of the data used in practice. On enciphering and имитозащиту the data the approach on the basis of MDC has not found reflexion in the Russian standard.

That the malefactor could not realise any of the threats listed above accessible it on infringement of integrity of the data, it is enough to provide impossibility of calculation with it of a control combination f (T ) for any text T. For this purpose it is just necessary to make algorithm of its calculation f (T ) a confidential element криптосистемы. Consecutive carrying out in a life of a principle of Kirhgofa leads to the scheme in which function f in itself is not confidential, but depends on a vector of confidential parametres – key K:

I = f (K , T ) = f (K, T1..., Tn), where

T = (T1..., Tn) – the initial text broken into blocks of the fixed size. The control combination developed in such a way has received the code name аутентификации messages (Message Autentification Code) and is in abbreviated form designated MAC. In the domestic literature it sometimes (not quite correctly) is called as the cryptographic control sum. How to us to realise this function f (K , T )? In our disposal there is an algorithm of cryptographic transformation I = EK (T ) (simple replacement) which possesses necessary for construction of similar functions by properties, however allows to work only with blocks of the text of the fixed size T | = N.

The first idea which comes to mind, it to cipher the control sum calculated in the usual image. However the inconsistency of such approach is obvious – he allows us to be protected from the second of the resulted threats, however not quite protects from the first. Really, the malefactor having some message intercepted earlier both in opened, and in the ciphered form with имитовставкой, without effort can impose such крипто­системе the untrue report for this purpose it fabricates the message with precisely same control sum, as available at it, and supplies with its same имитовставкой. The only thing that can prevent the malefactor in it, is impossibility is correct to cipher the forged message. However we cannot hope for it – the requirement of maintenance of authenticity of the message irrespective of its privacy remains in force.

Our first approach to a problem of construction of algorithm of calculation имитовставки has appeared unsuccessful. We will try to improve it slightly: we will cipher at first message blocks, and only then to find the control sum received шифроблоков:

f (T) = (EK (T1) + EK (T2) +... + EK (Tn)) mod 2N.

The given approach is steady on those lines on which it was opened previous, however and it takes an obvious weak place: does not react in any way to possible shift of blocks шифротекста. For overcoming of this lack it is possible to try to use instead of summation another, некоммутативную function of a combination of blocks, however it generates set of various unpleasant problems and consequently the given approach has not found practical application.

How to us to arrive in the circumstances? Here it is a high time to recollect about a mode гаммирования with a feedback – in this mode each block шифротекста depends on all blocks of the initial text from the first to corresponding to it. Means, last block шифротекста depends on all blocks of the initial text, a confidential key and, in addition, is steady against possible shifts of blocks шифротекста, before which спасовал the previous variant. Thus, we can try to use it in quality имитовставки:

I = Tn ' = f (Tn, Tn '1) = f (Tn, Tn1, Tn '2) =... = f (Tn, Tn1..., T1, T0).

Thus, however, it is necessary to pay attention on two things:

·       синхропосылка for calculation имитовставки it is not necessary – transformation can be begun directly with the first block of the data: I = Tn  Å EK (Tn1 Å EK (... EK (T1)...));

· the       given scheme is vulnerable on last block – really, total result for имитовставки is formed by bit-by-bit summation on the module 2 last blocks of the data with some code depending on all previous blocks: I = Tn ' = Tn  Å EK (Tn '1) is means that the malefactor can fabricate any message, and then add to it one more block calculated under formula Tn = I  Å EK (Tn '1) that the control combination for it was equal to a preset value I;

The given remarks are easy for considering – it is necessary to change only use order on each step of operations bit-by-bit excluding or and simple replacement, – then the algorithm of calculation имитовставки will look as follows: I = EK (Tn  Å EK (Tn1 Å ... EK (T1)...))).

Use in quality имитовставки last block received at enciphering of data file гаммированием with a feedback, or any function from it, can make some cryptographic reports insolvent. It takes place, if for зашифрования the text and development имитовставки the same algorithm – гаммирование with a feedback, and the same key is used. We will show that this scheme does not provide имитостойкости. Let message T = (T1, T2..., Tn) it is ciphered on key K on algorithm гаммирования from OS: T ' = (T1 ', T2 '..., Tn ' ). Let as a code аутентификации the code I is used calculated on the same algorithm and on the same key, it is obvious T = Tn '. Then full шифрованное the message with a code аутентификации has the following appearance: T ~ ' = (T ', I) = (T1 ', T2 '..., Tn ', Tn '). If the malefactor makes changes in шифротекст nevertheless our scheme аутентификации will not find out changes though, received at расшифровании the text will be rather far from the true. The reason of it is covered that as criterion of authenticity of the message equality of last block шифротекста here serves a control combination, and it to provide rather easily. The situation cardinally will not improve, if instead of direct last block шифротекста in quality имитовставки to use function from it, received let even by means of algorithm of simple replacement: I = EK (Tn ').

Thus, cryptographic schemes in which имитозащита it is not separated from enciphering, that is as a code аутентификации the part шифротекста is used or the function calculated with use only of such part, can appear unstable to manipulation with шифротекстом. From this it follows that there are two ways of elimination of the specified lack:

·       to use for calculation имитовставки various криптоалгоритмы, or various modes of the same algorithm;

·       to use for enciphering and calculation имитовставки various keys;

Use of two keys instead of one is not absolutely convenient, therefore founders STATE THAT have gone on the first way – they have developed separate algorithm EK ', intended only for calculation имитовставки. If for enciphering by simple replacement on each step the cycle 32-Z, expressed in terms of a composition of simple transformations (section 4 of present article see) as follows is used: at calculation имитовставки the simplified cycle 16-Z, containing the first 16 steps of a cycle 32-Z is used:. The simplified algorithm of calculation имитовставки allows to reach approximately twice большего speed in comparison with enciphering modes.

Other differences of algorithm of calculation имитовставки from algorithm гаммирования with a feedback are caused by the reasons resulted earlier and consist in the following:

·       it is not used синхропосылка;

· the       combination of a code with the data by means of function Å is carried out not after, and to a step криптопреобразования: I0 = 0, Ii = EK ' (Ii1 Å Ti), i = 1,2..., n.

The second property eliminates vulnerability имитовставки on last block of the message.

Let's notice that in quality имитовставки everything can undertake, but only a part of received block In: I = ( In ) 1... L, where L = | I | – the size имитовставки. As a rule, it is 32 younger bits of block In. The size имитовставки L defines probability of successful imposing of the false data which is equal p = 2L. In the conclusion of the given section we will notice that in a calculation mode имитовставки GOST allows to add in the text beginning its registration parametres, such, as date of last updating of a file and its size, etc.: I (T) = I (U, T), where U – a vector of registration parametres.

The conclusion.

The author is compelled to put an end though without consideration there was a great number of the important questions to it at all questions of realisation of the Russian standard in the form of the device or the computer programs representing recently the greatest interest for a wide range of experts, in particular, have not been mentioned. Nevertheless the author hopes that given article will be useful to all interested cryptographic methods of protection of the information. As addition to article the set of the equations for all modes криптопреобразований in accordance with GOST 28147-89 is applied , being as a matter of fact formal and the standard complete description suffices.

The literature.

1.    J.  L.Messi. Introduction in modern cryptology. ТИИЭР, т.76, №5, May 88, M, the World, 1988, s.24-42.

2.      M.E.Smid,  D.K.Bransted. The standard of enciphering of the data: the past and the future. ТИИЭР, т.76, №5, May 88, M, the World, 1988, s.43-54.

3.     U.Diffi. First ten years of cryptography with an open key. ТИИЭР, т.76, №5, May 88, M, the World, 1988, s.54-74.

4.      A.N.Lebedev. Cryptography with an open key and possibilities of its practical application. That. Сб. «Information Protection», вып. 2, M. 1992, s.129-147.

5.    And.  V.Spesivtsev, etc. information Protection in personal computers. М, Radio and communication, 1992, s.140-149.

6.    GOST 28147–89. Systems of processing of the information. Protection cryptographic. Algorithm of cryptographic transformation.

7.     S.Maftik. Protection mechanisms in COMPUTER networks. М, the World, 1992.

8.     V.Zhelnikov. Cryptography from the papyrus to the computer. М, ABF, 1996.


¤Ёшыюцхэшхаааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааа the Equations of cryptographic transformations it agree GOST 28147-89

Mode

The equation зашифрования

The equation расшифрования

The additional information

Simple replacement

Ti ' =  EK (32) (Ti), 1  £ i  £ n

Ti =  DK (32) (Ti '), 1  £ i  £ n

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

Ti ' =  Ti Å EK (32) (Gi), 1  £ i  £ n

Ti =  Ti ' Å EK (32) (Gi), 1  £ i  £ n

G0 =  EK (S), Gi =  (Gi, 0, Gi, 1), 0  £ i  £ n

Gi, 0 =  (Gi1,0 + C0) mod 232, 1  £ i  £ n

Gi, 1 =  (Gi1,1 + C1 – 1) mod (232 – 1) + 1,

1  £ i  £ n, C0 =  101010116, C1 =  101010416.

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

Ti ' =  Ti Å EK (32) (Ti '–1), 1  £ i  £ n

Ti =  Ti ' Å EK (32) (Ti '–1), 1  £ i  £ n

T0 ' =  S.

Development имитовставки

I0 =  0, Ii =  EK (16) (Ii1 Å Ti), 1  £ i  £ n,

I = (In) 1. L

Explanatories:

Ti, Ti 'i-tyj the block of the open and ciphered text accordingly;

S-sinhroposylka – Data file in the size | S | = 64 bits;

I-imitovstavka – Data file in the size L no more than 64 bats: L = | I | < 64;

EK (32) = (G1SG2S... SG8S) 3 (G8S... SG2SG1) cycle transformation зашифрования (32-Z);

DK (32) = (G1SG2S... SG8S) (G8S... SG2SG1) 3 cycle transformation расшифрования (32-R);

EK (16) = (G1SG2S... SG8S) 2 transformation of a cycle of development имитовставки (32-Z);

S (T0, T1) = (T1, T0) operation of shift of the senior and younger 32-bit half преобразуемого the block of the data;

Gi (T0, T1) = (T0, T1 Å fH (T0, Ki)) operation of one step of transformation of the 64-bit block of the data, 1 £ i £ 8;

fH (t, k) = R¬11 (CH ((t + k) mod 232)) – enciphering function, t-preobrazuemyj the block of the data which is k-used on a step an element of a key – 32-bit blocks of the data: | t | = k | = 32;

R¬11Rotation operation (cyclic shift) the 32-bit block of the data on 11 bits to the left (towards the senior bits);

CHoperation of transformation of the 32-bit block of the data, consisting in block substitution of 4-bit groups of the data under the table of replacements H = {hi, j} 1 £ i £ 8,1 £ j £ 16:;



Ð¯Ð½Ð´ÐµÐºÑ Ñ†Ð¸Ñ‚Ð¸Ñ€Ð¾Ð²Ð°Ð½Ð¸Ñ

Subscribe Subscribe.Ru
The Family Tree of Family