Andrey Vinokurov.
Problem аутентификации the data and block code numbers.
Given article is continuation of a series of articles of the author about realisations and use of the Russian standard of enciphering [1,2,3] and about architecture and modes of use of block code numbers [4], and is devoted problems of acknowledgement of authenticity and authorship of messages. Article has been written in the autumn of 1995 – almost three years ago, and prepared for the publication in magazine "Monitor" where the author had 2 articles on cryptography. However for various reasons article then has not been published – at first because of shortage of time for its definitive operational development and preparation of codes-examples for article, and then because of "Monitor" closing.
The maintenance
Introduction........... 2
1. A problem аутентификации the data...............................................................................................
2. The control of an invariance of data files.............................................................................
2.1. A problem имитозащиты the data.............................................................................................
2.2. Approaches to the control of an invariance of the data...................................................................
2.3. Code development аутентификации messages..................................................................
2.4. Development of a code of detection of manipulations....................................................................
3. The digital signature on the basis of traditional block code numbers.........................................
3.1. What is the digital signature...........................................................................................
3.2. Base idea of Diffi and Hellmana.....................................................................................
3.3. Updating of the scheme of Diffi-Hellmana for the signature of bit groups........................
3.4. The scheme of the digital signature on the basis of the block code number.................................................
The conclusion..... 24
The literature...... 24
Introduction
Ours absolutely century already close to the end rightfully can be considered as a century of total information of a society – the information role in the modern world is so great that the information industry became one of leading branches of our days, and the devices which have gained huge distribution for processing of figures – computers – are one of symbols of our civilisation. The information presented in the most various forms, like other goods is made, stored, transported to the consumer, on sale, bought at last consumed, becomes outdated, spoils, and т.д. Throughout life cycle information files can be exposed to various influences undesirable to their consumer to problems of struggle with which given article is devoted.
As the information has non-material character, data files do not bear on themselves any prints on which it would be possible to judge their past – about the one who is the author, about creation time, about the facts, time and authors of brought changes. Updating of an information file does not leave tangible traces on it and cannot be found out usual methods.« Updating traces »can be present at this or that form only on material data carriers – so, specialised expert examination is quite capable to establish that sector X on not which to a diskette has been written down after all other sectors with the data on the same path of a diskette, and this record was made on other disk drive. The specified fact, being established, can to mean, for example, that in the data, хранимые on a diskette, changes have been made. But after this data will be copied on other carrier, their copies will not contain any more any traces of updating. The real computer data during the life repeatedly changes a physical basis of representation and constantly wanders from the carrier on the carrier owing to what them not обнаружимое distortion does not represent serious problems. As creation and use of information files practically are always divided in time and-or in space, the consumer can have well-founded doubts that the data file received by it is created by the necessary source and besides in accuracy such what it has reached it.
Thus, in systems of processing of the information besides maintenance of its privacy it is important to guarantee following properties for each processed data file:
· authenticity – it has come to the consumer such with what has been created by a source and has not undergone on the course of life of unapproved changes;
· authorship – it has been created by that source what the consumer assumes.
Maintenance with system of processing of these two qualities of files of the information also makes their problem аутентификации, and corresponding ability of system to provide reliable аутентификацию the data is called as its authenticity.
1. A problem аутентификации the data.
At first sight can seem that the given problem dares simple enciphering. Really, if the data file is ciphered with use of the proof code number, such, for example, as GOST 28147–89 for it practically always will be fairly following:
· it is difficult to make changes by intelligent image as with degree of the probability slightly different from unit, the facts of updating of the ciphered data files become obvious after them расшифрования to it – this evidence is expressed that such data ceases to be correct for their interpreter: instead of the text in Russian there is a rubbish, archivers inform that integrity of archive is broken etc.;
· only possessing a confidential key of enciphering users of system can make the ciphered message, thus, if to the addressee the message ciphered on its confidential key comes, it can be assured of its authorship as except it only the lawful sender could make this message.
Nevertheless, enciphering use in data processing systems in itself is incapable to provide their authenticities for following reasons:
1. The changes brought in the ciphered data, become obvious after расшифрования only in case of the big redundancy of the initial data. This redundancy takes place, for example, if the information file is the text in any human language. However generally this requirement can not be carried out – if casual updating of the data does not do their inadmissible for interpretation with some considerable share of probability enciphering of a file does not provide its authenticity. Telling to cryptology language, authenticity and privacy an essence various properties криптосистем. Or, easier: properties of systems of processing of the information to provide privacy and authenticity of the processed data generally can not coincide.
2. The fact successful (in sense of the previous point) расшифрования the data ciphered on a confidential key can confirm their authorship only in the opinion of the addressee. The third party cannot make on the basis of this unequivocal conclusion about authorship of a file of the information as any of owners of a confidential key can be its author, and them at least two – the sender and the addressee. Therefore in this case disputes on authorship of the message cannot be resolved independent arbitration. It is important for those systems where between participants there is no mutual trust that is rather characteristic for the bank systems connected with management by considerable values.
Thus, existence of a problem of acknowledgement of authenticity and authorship of the data files, separate of a problem of maintenance of their privacy, does not raise the doubts. In the subsequent sections of present article approaches to its decision, based on use of classical block code numbers are stated. In section 2 approaches to the decision of a problem of acknowledgement of authenticity of the data, and in section 3 – to a problem of acknowledgement of their authorship are considered. Basically, for the decision of the specified problems any traditional block cryptographic algorithm can be used. In the computer codes applied on present article, the author uses the code number most familiar and close to it – криптоалгоритм GOST 28147–89.
2. The control of an invariance of data files.
2.1. A problem имитозащиты the data.
Under имитозащитой the data in systems of their processing understand protection against imposing of the false data. As we have already found out, practically always at some stages of the life cycle the information appears out of a zone of the direct control over it. It happens, for example, at data transmission on communication channels or at their storage on magnetic carriers of the COMPUTER physical access to which extraneous persons to exclude almost never it is obviously possible. Only if entirely to conclude the communication line in a casing from firm metal, in a casing закачать gas under pressure and to send a company of submachine gunners to comb district each time when in section of such system the slightest changes of pressure as it, on hearings, the Russian special services responsible for the governmental communication do will be fixed, will be though any guarantee of inviolability of the transferred data, not always, however, sufficient. But the similar approach repeatedly удорожает cost of communication channels, after all cost of the casing, the protected premises for processing of a signal and services of the armed people on many usages exceeds cost of the laid twisted pair wires. And how in this case to be with an electromagnetic signal? – After all not to all places it is possible to hold on a wire, and such signal even if it узконаправленный a laser bunch, without speaking about a usual radio signal, you will not hide in a casing.
Thus, physically to prevent entering of unapproved changes into the data in overwhelming majority of real systems of their processing, transfers and storages it is not obviously possible. Therefore extremely important in due time to find out the fact of such changes – if similar casual or deliberate distortions in time will be revealed, losses of users of system will be minimum and will be limited only to cost of "empty" transfer or storage of the false data that, of course, in all real situations immeasurably less than a possible damage from their use. The purpose of the malefactor imposing to system a false information, its delivery for original is, and it is possible only in the event that the fact of such imposing will not be found out in time, therefore simple fixing of this fact brings to nothing all efforts of the malefactor. Let's sum up – as protection of the data against unapproved changes in cryptography understand not an exception of the possibility of such changes, and a set of the methods allowing reliably to fix their facts if they took place.
Let's try to find universal approaches to construction of such protection. First of all, at the disposal of the addressee of the information there should be a procedure of check or аутентификации A (T), allowing to check up authenticity of the received data file T. On an exit the specified procedure should give out one or the other possible булевых values – the data file is identified as original, or as false: A (T) Î {0,1} for any admissible T. We will agree that value 1 corresponds to original data file, and value 0 – false. Procedure аутентификации should possess the following properties limiting possibility of the malefactor to pick up data file T1, different from original file T (T ¹ T1) which nevertheless would be identified by this procedure as original (A (T1) =1):
· the malefactor should not have a possibility to find such message differently as by search on set of admissible messages – last possibility is at its order always;
· probability successfully to pass check on authenticity at casually chosen message T* should not exceed in advance established value p.
Now we will recollect about universality of the designed scheme of protection which, in particular, means that the scheme should be suitable for protection of any data file T from enough wide class. However, if to realise the scheme it is literally, i.e. to use for check in accuracy that message which the sender should transfer to the addressee, the universality principle can come in the contradiction with the second requirement to check procedure. Really, proceeding from this principle we can demand, that all possible messages T were admissible that will absolutely obviously break the second requirement to check function. That them to reconcile, it is necessary to enter additional steps into the scheme – transformation given by the sender and return transformation by the addressee. The sender carries out transformation of the data with use of some algorithm F: T ' =F (T). Then, besides procedure аутентификации, at the disposal of the addressee there should be procedure G of restoration of the initial data: T=G (T '). All sense of these transformations consists in that the set of the transformed messages {T '}, biunique displayed on set of admissible initial messages {T}, was not known to the malefactor, and probability casually to guess an element from this set was small enough that it could to be taken into consideration.
Last requirement in a combination to a universality principle unequivocally leads to necessity of entering of certain redundancy for the message that means simply that fact that the size of the transformed message should be more size of the initial message on some size, just and making degree of redundancy: |T ' | – |T | = D. It is obvious that the more this size, the is less probability to accept casually taken message for original – this probability is equal 2–D. If not the requirement of entering of redundancy, as functions of transformation F and G the data functions зашифрования and расшифрования the data on some key K could be used: F (T) =EK (T), G (T ') =DK (T '). However at their use the size of a file of ciphered data T ' is equal to the size of a file of initial data T: |T ' | = |T |, therefore the method here does not approach.
It is the most natural to realise algorithm of transformation with redundancy entering by simple addition to the initial data of a control combination of the fixed size calculated as some function from this data: T ' =F (T) = (T, C), C=f (T), |C | = D. In this case allocation of the initial data from the transformed file consists in simple rejection of added control combination C: T=G (T ') =G (T, C) =T. Check on authenticity consists in calculation for substantial part T of the received data file T ' values of control combination C ' =f (T) and its comparison with the transferred value control combination C. If they coincide, the message is considered original, differently – false:
.
Now we will consider properties with which function of development of a control combination f should satisfy:
1. This function should be вычислительно irreversible, that is there should not be a way to pick up data file T under set control combination C differently as search on space of possible values T.
2. This function should not be known to the malefactor – it should not have a way to calculate control combination C for any data file T. This requirement as a matter of fact means that function f should be confidential, we will consider it more in detail:
· first, according to the principle of Kirhgoffa conventional in cryptography it is necessary to replace the requirement of privacy of function of development of a control combination with application of the open function using a vector of confidential parametres (key) – in the same way as it becomes at construction of code numbers: C=f (T) =fK (T).
· secondly, it appears that on occasion this requirement can be weakened essentially. The matter is that the true purpose of this point – to exclude for the malefactor possibility to send untrue report T1, having supplied with its correctly calculated control combination C1=f (T1). It it is possible to reach in two next ways:
(a) By means of used above the requirement of privacy of function of calculation of a control combination or its dependence on a vector of confidential parametres (key);
(b) By means of the organisation of such report of use of protection frames which would exclude possibility of similar imposing of the false data.
It is obvious that possibility (b) can be realised only if the control combination is transferred or stored separately from the protected data. Despite seeming экзотичность, such possibility meets often enough, speech about it ahead.
Let's consider some well-known ways of calculation of a control combination and we will estimate possibility of their use in considered system имитозащиты the data. The elementary example of such combination is the control sum of blocks of the message, taken on the module of some number, usually take two in degree of the size of the block:
If T = (T1, T2..., Tm), C=f (T) = (T1+T2 +... +Tm) mod2N,
Where N = | T1 | = | T2 | =... = |Tm | – the size of blocks of the message.
However such transformation does not correspond to both requirements set forth above to function of calculation of a control combination and consequently is unsuitable for use in the scheme имитозащиты:
· first, and this most important thing – it does not exclude possibility of selection of the data under the set control combination. Really, let the sender of the information has transferred on the unreliable channel message T and control sum C for it, calculated on the formula resulted above. In this case everything that is required to the malefactor for imposing to the addressee of any way taken false data file T ' = (T ' 1, T ' 2..., T'm ') is to add with its one more block calculated under the following formula:
T'm ' +1=C - (T ' 1+T ' 2 +... +T ' m ') mod2N.
All blocks of the untrue report, except one, it is not obligatory the last, the malefactor can establish the any.
· secondly, the considered transformation is not cryptographic, and for the malefactor it is possible to make a control combination for any message chosen by it that allows it to give out successfully it for original – if the control combination is stored or transferred together with the protected data file.
2.2. Approaches to the control of an invariance of the data.
Now two approaches to the decision of a problem of protection of the data from the unapproved change, based on two approaches stated above to development of a control combination are known:
1. Development MAC – Message Authentification Code – a code аутентификации messages. This approach consists that the control combination is calculated with use of a confidential key by means of some block code number. It is important that on the basis of any such code number it is possible to create algorithm of calculation MAC for data files of any size. In literature ÌÀÑ sometimes not quite correctly is called as the cryptographic control sum, or that is more exact, a cryptographic control combination. The given approach to аутентификации the data is conventional and fixed practically in all cryptographic standards - имитовставка, formed according to GOST 28147-89 is typical sample MAC.
2. Development MDC – Ìànipulation Detection Code – a code of detection of manipulations (with the data). For calculation MDC for the block of the data so-called irreversible function of compression of the information, in the literature also named unilateral function, function of unilateral compression (transformation) of the information, cryptographic hesh-function, or simply hesh-function is used. It is clear that its irreversibility should have computing character:
· calculation of direct function Y=f (X) is easily realizable вычислительно;
· calculation of inverse function X=f–1 (Y) is impracticable вычислительно, that is cannot be executed more effective way, than search on set of possible values X;
Both ways of calculation of a control combination – MDC and MAC accept the block of the data of any size as argument and give out the block of the data of the fixed size as result.
In table 1 following more low comparative characteristics of both approaches are resulted:
Table 1. Comparative characteristics of approaches to the decision of a problem of the control of an invariance of data files.
|
№ |
Comparison parametre |
The approach |
|
|
|
|
Calculation MAC |
Calculation MDC |
|
1. |
Used преобразование the data |
Cryptographic преобразование (function зашифрования) |
Unilateral function, function of irreversible compression of the information |
|
2. |
The used classified information |
Confidential key |
It is not used |
|
3. |
Possibility for the third party to calculate контрольную a combination |
The malefactor cannot calculate a control combination if to it the confidential key is not known |
The malefactor can calculate a control combination for произвольного the block of the data |
|
4. |
Storage and transfer контрольной combinations |
The control combination can be stored and передаваться together with защищаемым in data file |
Control комбинация it should be stored and be transferred separately from the protected data file |
|
5. |
Additional conditions |
Demands preliminary distribution of keys between participants информационного an exchange |
Does not demand предварительных actions |
|
6. |
Areas in which подход has advantage |
Protection from несанкционированных changes данных by their transfer |
Single transfer массивов the data, the control of an invariance of files of the data and programs |
Let's comment on differences: the approach on the basis of MAC demands for calculation of a control combination of a confidential key, it is not necessary for the second. The potential malefactor cannot calculate MAC for any message fabricated by it, but can calculate MDC as for this purpose it is not required any confidential data, therefore MAC can be transferred from a source to the receiver on the open channel whereas for transfer MDC the protected channel is required.
It would seem, advantages of the first approach are so obvious that the second approach cannot find of itself of application. However it not so – use MAC demands, that preliminary between participants of an information exchange keys have been distributed. If it has not occurred, the special channel providing privacy and authenticity of the transferred information on which in parallel with data transmission on not protected channel keys will be transferred is necessary for its realisation. For transfer MDC the channel providing only authenticity of the transferred data is required, the privacy requirement is absent, and it does the given method preferable at disposable data transmission: The basic information is transferred on the usual not protected channel, and MDC is informed by the sender to the addressee on the channel which can be listened but cannot be used for imposing of the false data – for example, a voice by phone – if participants of an exchange are personally familiar and well know voices each other. Besides, the approach on the basis of development MDC is more simple and is convenient for systems where creation and use of information files are divided in time, but not in space, that is for the integrity control хранимой, instead of the transferred information – for example, for the control of an invariance of programs and the data in computer systems. Thus the control combination (MDC) should be stored in system so that to exclude possibility of its updating by the malefactor.
Both approaches suppose possibility of realisation on the basis of any classical block code number. Thus reliability of the received system имитозащиты, it is final under condition of its correct realisation, it will be defined by firmness of the used block code number is a statement it is exclusively easily proved. In two subsequent sections both approaches to the control of an invariance of data files will be considered.
2.3. Code development аутентификации messages.
Code development аутентификации messages with use of procedure of cryptographic transformation of the data officially or полуофициально is fixed in many standards on algorithms of enciphering. So, for example, in various comments to the standard of enciphering of the USA it is recommended to use DES for development of a control combination [5]. The Russian standard of enciphering of GOST 28147‑89 [6] evidently provides a development mode имитовставки which is not than other, as sample MAC.
The scheme of use of cryptographic transformation EK for code development аутентификации is rather simple: the initial message breaks into blocks, then is consecutive for each block there is a result of transformation on algorithm EK of the bit-by-bit sum of the block on the module 2 with result of performance of the previous step. Thus, we receive a following equation for development of a control combination:
C=CK (T) =EK (T1ÅEK (T2ÅEK (... ÅEK (Tm)))).
The scheme of algorithm of development MAC is resulted in drawing 1.
Øàã 0. The entrance data – data file T broken on m of blocks of the fixed size, the block of the data of the used code number equal to the size (for the majority of the most known code numbers – 64 bits): T = (T1, T2..., Tm). Last block given Tm is supplemented in any way to the full block of the data if has the smaller size.
Øàã 1. MAC receives zero initial value.
The following step of algorithm 2 are carried out consecutive for each block of the initial data as their following.
Øàã 2. The bit-by-bit sum on the module 2 next blocks initial given Ti c current value MAC S is exposed to transformation on algorithm зашифрования, the result becomes new current value MAC.
|
Fig. 1. Algorithm of development of a code аутентификации for data file. |
Øàã 3. Result of work of algorithm – MAC for entrance data file – is last current value MAC received on a step 2.
Let's consider properties cryptographic преобразований EK, the data used for enciphering, and we will define those from them which are necessary at development MAC:
1. Transformation of the data should use in качестве parametre confidential key K. Its privacy defines privacy of the ciphered data.
2. Transformation of the data should be криптографически proof, that is there should not be other possibility to define the entrance block of algorithm at the known day off and an unknown key, or to define a key at known entrance and target blocks differently as search on possible values of the entrance block and a key in the first and in the second cases accordingly.
3. Transformation of the data should be reversible – that procedure расшифрования was realizable.
If ciphering transformation EK is supposed to be used for code development аутентификации, performance of the third property is not required, as thus transformation is always carried out in one party. Besides криптостойкость algorithm of transformation can be slightly more low, than at enciphering, and it will not lead to decrease in reliability of all scheme. Really, at development MAC on hand криптоаналитика there is only one block of the data – MAC which is function at once all blocks of the initial text, and at зашифровании at its order there is a set of blocks шифротекста, each of which depends only on one block of the initial text. Obviously, in the first case its problem essentially is more difficult. For this reason in the VISITOR 28147–89 for development имитовставки it is used simplified 16-raundovyj a transformation cycle, whereas for enciphering – full 32-raundovyj.
2.4. Development of a code of detection of manipulations.
The approach to development of a control combination of data file with the help вычислительно irreversible functions has had development only recently in connection with occurrence of practical schemes of the digital signature as inherently it is way of calculation of hesh-function which is used in all schemes of the digital signature.
There is a considerable quantity of possible approaches to construction вычислительно irreversible functions, practically always the most difficult is the substantiation of property of irreversibility of the offered function. However there is a class of ways where such property does not require the proof, it simply follows from characteristics of the applied method is a construction of functions of unilateral transformation on the basis of classical block code numbers. The given approach is known for a long time and stated in a number of works, from the Russian-speaking we will note [7], in its basis that fact lies that the equation зашифрования the block of the data on a cycle of simple replacement Y=EK (X) вычислительно is unsoluble concerning key K is is the integral property of any really proof code number. Even at known open (X) and ciphered (Y) blocks key K cannot be defined differently as search on set of possible values. Algorithm of development of a control combination for data file T the following:
· data file T breaks into blocks of the fixed size equal to the size of a key of the used code number:
T = (T1, T2..., Tm);
|T1 | = | T2 | =... = |Tm–1 | = | K |, 0 <|Tm|£|K |.
· if necessary last (incomplete) block is supplemented somehow to the block of the full size;
· MDC or хэш messages it is calculated under the following formula:
C=H (T) =ETm (ETm–1 (... ET1 (S))),
Where S – initial filling of algorithm – can get out any way, usually believe S=0;
It is simple to prove that a problem of selection of data file T ' = (T ' 1, T ' 2..., T'm ') under set control combination C it is equivalent to the following system of the equations of selection of a key for the set entrance and target blocks of the data криптоалгоритма:
ET ' 1 (S) =S1,
ET ' 2 (S1) =S2,
...
ET'm ' (Sm '–1) =C,
There is no necessity to solve at once all these equations concerning key Ti ' – all blocks of data file T ', except one, can be chosen any is will define, all values Si, and only one, any of them, should be certain by the decision of corresponding equation ET'i (Si–1) =Si rather T'i. As the given problem вычислительно is unsoluble owing to use криптостойкого algorithm of the enciphering, the offered scheme of calculation MDC possesses the guaranteed firmness equal to firmness of the used code number.
However the given scheme does not consider a problem of collateral cipher keys which consists in the following: there can be some keys with which use at зашифровании identical blocks of a clear text are translated in identical blocks шифротекста:
EK1 (X) =EK2 (X) at some X and K1 ¹ K2.
One of these keys – on what it was spent зашифрование – "true", and another – "collateral". Thus, as a collateral key for some block of the data X and some true key K is called key K ' which yields precisely same result зашифрования the block X, as true key K: EK ' (X) =EK (X). Clearly that for various blocks of initial data file collateral keys also are generally various – probability to meet steam of the keys translating simultaneously some steam of identical blocks of clear texts in steams of identical blocks шифротекстов promptly decreases with growth of number of these pairs. Therefore detection of a collateral key криптоаналитиком at message decoding is not its special success as with the probability slightly different from 1, on this found key it cannot correctly decipher any other blocks шифротекста. Absolutely other business in algorithm of development MDC – here detection of a collateral key means that the malefactor has picked up such false, that is the block of the data absent in the message, which use leads true MDC initial data file.
To reduce probability of imposing of the false data through a finding of collateral keys, in steps of cryptographic transformation blocks of the initial message, and result of their expansion under some scheme are applied not. The scheme расширениея here is understood as procedure of construction of blocks of the data большего the size from blocks of the data of the smaller size. As an example expansion function in which the output block is under construction of bytes (or 2-, 4 can serve, for example... Etc.-byte words) the initial block, listed in a various order. The specified expansion should be applied, if the size of a key of the used code number several times exceeds the size of its block of the data. So, for algorithm DES, with the size of the block of the data of 64 bit and a key of 56 bits in expansion there is no necessity. If in the scheme the algorithm of GOST 28147–89 with the size of the block 64 bits and the size of a key of 256 bits is used , it is necessary to use 64 or 128-bit blocks of the initial text and to expand them to the sizes of 256 bits. The example of function of expansion of the 128-bit block in 256-bit can be, for example, the following:
The initial block: T = (B1, B2, B3, B4, B5, B6, B7, B8, B9, B10, B11, B12, B13, B14, B15, B16),
After expansion: P (T) = (B1, B2, B3, B4, B5, B6, B7, B8, B9, B10, B11, B12, B13, B14, B15, B16,
B1, B4, B7, B10, B13, B16, B3, B6, B9, B12, B15, B2, B5, B8, B11, B14),
Where Bi – bytes of the block of the data, |Bi | = 8.
The scheme of algorithm of development MDC (hesh-code) with use of the classical block code number is resulted in drawing 2.
|
Fig. 2. Algorithm of development of a code of detection manipu - ляций for data file. |
Øàã 0. The entrance data – data file T broken on m of blocks of the fixed size, a key not exceeding the size used криптоалгоритма and, as a rule, dividing it totally: T = (T1, T2..., Tm). Last block given Tm is supplemented in any way to the full block of the data if has the smaller size.
Øàã 1. MDC receives zero initial value (this value can be, basically, any).
The subsequent steps 2 and 3 algorithms are carried out consecutive for each block of the initial data as their following.
Øàã 2. Expansion of next block Ti of the data by means of function of expansion P till the size of a cipher key is carried out.
Øàã 3. It is carried out зашифрование current value MDC on a key received on a step 2, the result becomes new current value MDC.
Øàã 4. Result of work of algorithm (i.e. MDC for all entrance data file) is last current value MDC received on a step 3.
The considered algorithm also can be used for hesh-code development in schemes of the digital signature.
3. The digital signature on the basis of traditional block code numbers.
At first sight, this idea can seem absurdity. Really, well-known that so-called "modern", it the two-key cryptography has arisen and began to develop quickly last decades just because a number of new cryptographic reports of type of the report of the digital signature in which there was a severe need in connection with penetration of electronic technologies into new spheres, it was not possible to realise on the basis of traditional криптоалгоритмов, widely known and well studied by then. Nevertheless, it is possible. And the first who has paid attention to such possibility, were … ancestors of cryptography with U.Diffi's open key (W.Diffie) and M.E.Hellman (M.E.Hellman). In the work [8] they have published the description of the approach, allowing to carry out procedure of the digital signature of one bit by means of the block code number. Before to state this graceful idea, we will make some remarks on an essence and realisations of the digital signature.
3.1. What is the digital signature.
So, the scheme of the digital signature or the elektronno-digital signature is a set of algorithms and reports [1], allowing to construct information interaction between two and more participants so that the fact of authorship of the transferred data file "signed" by one of participants, could be reliably confirmed or will deny the third party, «independent arbitration». The similar scheme is necessary for all systems of electronic data processing where there is no full mutual trust between participants of information process, first of all it concerns financial sphere. Any scheme of the digital signature assumes addition to "the signed" data file of an additional code – actually «the digital signature», develop which the author of the message possessing a confidential key of the signature can only, and all the others can check up only conformity of this "signature" to the signed data. Therefore each scheme should provide, at least, definition of three following algorithms:
1. Algorithm GK of development of pair keys – signatures KS and checks of signature KC with use of a vector of casual parametres R: (KS, KC) =GK (R), here:
KS – a signature key, it should be known only to the signing;
KC – a key of check of the signature, it is not confidential and is accessible to everyone who should have possibility to check authorship of messages.
2. Algorithm S of the signature of message T with use of a confidential key of signature KS:
s=S (T, KS),
Where s – the digital signature of the message;
3. The algorithm of V check of the signature with use of a key of check of signature KC, giving out as result булево value – proves to be true or the authorship of the message does not prove to be true:
V (T, s, KC) Î {0,1}.
In practice logic result always receive as result of comparison of two numbers, either codes, or blocks of the data – speech about same. Practically in all known schemes of the digital signature it is comparison make as follows:
· calculate a control combination on some algorithm C with use of the signed message and the digital signature:
c=C (T, s);
· compare a control combination c and a key of check of signature KC if they coincide the signature admits true, and the data – original, otherwise the data is considered as the false.
As a matter of fact, it is enough specified three algorithms for realisation of the scheme of the digital signature, however in practice in schemes add one more algorithm – function of development of the hesh-block for the signed data file T. The majority of cryptographic algorithms operate with blocks of the data of the fixed size, and files большего process the size in parts that is necessary for maintenance of efficiency and reliability of these schemes. If the same approach was used at development of the digital signature, blocks of files of the information would subscribe separately from each other, and the size of the signature would appear comparable with the size of the signed data file that understandably it is not convenient. Therefore in practical schemes ЭЦП the message, and its hesh-code, that is result of function evaluation of irreversible compression for this file which has the fixed size subscribes not. Thus, in scheme ЭЦП the fourth algorithm is added:
4. Algorithm H of calculation of irreversible hesh-function for signed files:
h=H (T).
The algorithm of calculation of hesh-function and other algorithms of the scheme do not depend from each other and will be co-ordinated only on the size of blocks with which they operate. It allows to change if necessary in the scheme of the signature a way of calculation of hesh-values.
For the efficient scheme of the elektronno-digital signature performance of following conditions is necessary:
· anybody, except the person possessing a confidential key of signature KS, cannot correctly sign set message T;
As the party checking the signature, possesses open key KC of check of the signature, from the specified property follows that should not exist вычислительно effective algorithm of calculation of confidential key KS on opened KC.
· anybody, including the person possessing a key of the signature, not in a condition to construct message T ', approaching under beforehand set signature s.
At the offer of any scheme of the signature it is necessary to prove both these properties that another about which it is known becomes usually the proof of equivalence of a corresponding problem of opening of the scheme any that it вычислительно is unsoluble. Almost all modern algorithms of the digital signature and other schemes of "modern cryptography» are based on so-called «difficult mathematical problems» type факторизации great numbers or логарифмирования in discrete fields. However the proof of impossibility of the effective computing decision of these problems is absent, and there are no guarantees that they will not be solved in the near future, and corresponding schemes are cracked – as it has occurred with «ранцевой» the scheme of the digital signature [9]. Moreover, with rough progress of means of computer facilities «reliability borders» methods are removed in area of the increasing sizes of the block. To in total steam of decades back, at the beginning of cryptography with an open key was considered that it is enough for realisation of the scheme of signature RSA 128 or even bit numbers. Now this border is removed to 1024-bit numbers – practically 10 times, – and it is far yet a limit. Whether it is necessary to explain that with each such "motion" it is necessary to redesign equipment and to copy the programs realising the scheme. Anything similar is not present in the field of classical block code numbers, short of initially defective and not clear decision of committee on standards of the USA to limit the size of a key of algorithm DES in 56th bits whereas even during algorithm discussion it was offered to use a key большего the size [5]. The schemes of the signature based on classical block code numbers, are free from the specified lacks:
· first, their firmness to breaking attempts follows from firmness of the used block code number;
Whether it is necessary to say that classical methods of enciphering are studied much more, and their reliability is proved immeasurably better, than reliability of methods of "modern cryptography».
· secondly even if firmness used in the scheme of the signature of the code number will appear insufficient computer facilities in the light of progress, it it will be easily possible to replace with another, steadier, with the same size of the block of the data and a key, needlessly to change the basic characteristics of all scheme is will demand only the minimum updating of the software;
3.2. Base idea of Diffi and Hellmana.
So, we will return to the scheme of Diffi and Hellmana of the signature of one bit of the message by means of the algorithm which is based on any classical block code number. We will assume, in our disposal there is an algorithm зашифрования EK, operating with blocks of the data of X size n and an using key in the size nK: |X | = n, |K | = nK. Structure of the key information in the scheme the following:
· the confidential key of signature KS gets out as any pair of keys K0, K1 the used block code number:
KS = (K0, K1);
Thus, the size of a key of the signature is equal to the doubled size of a key of the used block code number:
|KS | = 2|K | = 2nK
· the check key is calculated as steam of blocks криптоалгоритма on following equations:
KC = (C0, C1), where:
C0=EK0 (X0), C1=EK1 (X1),
Where schemes being in the parametre blocks of data X0 and X1 are unclassified and known to the party checking the signature.
Thus, the size of a key of check of the signature is equal to the doubled size of the block of the used block code number:
|KC | = 2|X | = 2n.
Algorithms of the scheme of the digital signature of Diffi and Hellmana the following:
1. Algorithm G of development of key pair:
We take the casual block of the data of the size 2nK, it and will be a confidential key of the signature:
KS = (K0, K1) =R.
The key of check of the signature is calculated as result of two cycles зашифрования on algorithm EK:
KC = (C0, C1) = (EK0 (X0), EK1 (X1)).
2. Algorithm S of development of the digital signature for bit t (t Î {0,1}) consists simply in a choice of a corresponding half from the pair making a confidential key of the signature:
s=S (t) =Kt.
3. The algorithm of V check of the signature consists in check of equation EKt (Xt) =Ct which, obviously, should be carried out for ours t. To the addressee all used sizes are known:
Kt=s – The digital signature of bit,
Ct – a corresponding half of key of check,
Xt – unclassified parametre of algorithm.
Thus, function of check of the signature will be following:
.
Isn't that so, all three algorithms of this scheme of amazingly simplicity in comparison with schemes RSA and an ale-gamalja?! We will show that the given scheme is efficient, for what we will check up performance of necessary properties of the scheme of the digital signature:
1. Impossibility to sign bit t if the signature key is unknown.
Really, for performance of it the malefactor would need to solve equation Es (Xt) =Ct rather s, this problem is equivalent to definition of a key for the known block шифротекста and a clear text corresponding to it that вычислительно it is impossible owing to use of the proof code number.
2. The impossibility to pick up other value of bit t which would approach under the set signature is obvious, because number of possible values of bit only two and the probability of performance of two following conditions simultaneously пренебрежимо is small in simple owing to use криптостойкого algorithm:
Es (X0) =C0,
Es (X1) =C1.
Thus, offered Diffi and Hellmanom the scheme of the digital signature on the basis of the classical block code number криптостойка so, how much racks the used code number, also is thus rather simple. Now it is a high time to tell, why this remarkable scheme has not found some considerable practical application. All the matter is that at it is two lacks. Only two, but what!
The first lack is evident at once – it consists that the given scheme allows to sign only one bit of the information. In the block большего the size it is necessary to sign separately each bit, therefore even with the account хеширования messages all components of the signature – the confidential key, a verifying combination and actually the signature turn out big enough on the size and more than on two order surpass the size of the signed block. We will assume that in the scheme cryptographic algorithm EK with the size of the block and a key, expressed in bits, accordingly n and nK is used. We will assume also that the size of the hesh-block is equal in the scheme nH. Then the sizes of the basic working blocks will be the following:
· the size of a key of the signature:
nS=nH×2nK=2nHnK.
· the size of a key of check of the signature:
nС=nH×2n=2nHn.
· the size of the signature:
nSg=nH×nK=nHnK.
If, for example, as a basis in the given scheme the code number of GOST 28147–89 with the size of the block n=64 a bat and the size of a key nK=256 bit is used , and for development of hesh-blocks the same code number in a mode of development MDC that will give the size of the hesh-block nH=64 that the sizes of working blocks will be used will be the following:
· the size of a key of the signature:
nS=nH×2nK=2nHnK=2×64×256=215 Bit = 4096 byte.
· the size of a key of check of the signature:
nС=nH×2n=2nHn=2×64×64=213 Bit = 1024 bytes.
· the size of the signature:
nSg=nH×nK=nHnK=64×256=214 Bit = 2048 byte.
Agree, heavy enough keys.
The second lack of the given scheme, perhaps, is swept less up, but is much more serious. The matter is that pair of keys of the signature and check in it disposable! Really, performance of procedure of the signature of bit of the message leads to disclosing of half of confidential key then it any more is not completely confidential and cannot be used repeatedly. Therefore the complete set of keys of the signature and check is necessary for each signed message. It excludes possibility of practical use of the considered scheme of Diffi-Hellmana in originally offered variant in real systems ETSP.
Owing to the specified two lacks offered schemes till rather recent time it was considered only as funny theoretical possibility, anybody seriously did not consider possibility of its practical use. However some years ago in work [7] updating of the scheme Diffi-Hellmana actually eliminating its lacks has been offered. In the present work the given scheme is not considered in all details, only main principles of the approach to updating of the initial scheme of Diffi-Hellmana and the description of working algorithms here are stated.
3.3. Updating of the scheme of Diffi-Hellmana for the signature of bit groups.
In the given section ideas of the authors [7], allowed to pass from the signature of separate bits in initial schemes of Diffi-Hellmana to the signature of bit groups are stated. In this approach the algorithm of "unilateral cryptographic scrolling» which to a certain extent can serve as analogue of operation of exponentiation is central. As usually, suppose, that in our disposal there is cryptographic algorithm EK with the size of the block of the data and a key accordingly n and nK bits, and the size of the block of the data does not exceed the size of a key: n£nK. Let in our disposal also there is some function of "expansion" of n-bit blocks of the data in nK-bit Y=Pn®nK (X), |X | = n, |Y | = nK. We will define function Rk «unilateral scrolling» block given T in the size n bit k time (k³0) by means of the following recursive formula:
Where X – any unclassified n-bit block of the data which are in parametre of procedure of scrolling. On the idea function of unilateral scrolling is extremely simple, it is necessary only (k) to execute the necessary quantity of times following actions: to expand the n-bit block of data T to the size of a key used криптоалгоритма (nK), on the received expanded block as on a key to cipher the block of the data X, result зашифрования to bring to the place of the initial block of the data (T). Owing to definition operation Rk (T) possesses two extremely important for us properties:
1. Additivity on number прокручиваний:
Rk+k ' (T) =Rk ' (Rk (T)).
2. Односторонность or irreversibility of scrolling: if some value of function Rk (T) вычислительно it is impossible to find value Rk ' (T) for any k ' <k is known only – if it was possible, in our disposal there would be a way to define an enciphering key on known entrance and to an output block криптоалгоритма EK. That contradicts the assumption of firmness of the code number.
Now we will show, how the specified operation can be used for the signature of group of bits: we will state the description of the scheme of the signature of block T consisting from nT of bits, under precisely same scheme on which in the previous section the scheme of the signature of one bit is described.
· the confidential key of signature KS gets out as any pair of blocks K0, K1, having the size of the block of the data of the used block code number:
KS = (K0, K1);
Thus, the size of a key of the signature is equal to the doubled size of the block of the data of the used block code number:
|KS | = 2n;
· the check key is calculated as steam of the blocks having the size of blocks of the data used криптоалгоритма under following formulas:
KC = (C0, C1), where:
C0=R2nT–1 (K0), C1=R2nT–1 (K1).
In these calculations unclassified blocks of data X0 and X1, functions being in the parametres of "unilateral scrolling» also are used, they necessarily should be various.
Thus, the size of a key of check of the signature is equal to the doubled size of the block of the data of the used block code number:
|KC | = 2n.
Algorithms of [7] schemes of the digital signature of Diffi modified by authors and Hellmana the following:
1. Algorithm G of development of key pair:
We take the casual block of the data of the suitable size 2n, it and will be a confidential key of the signature:
KS = (K0, K1) =R.
The key of check of the signature is calculated as result of "unilateral scrolling» two corresponding half of confidential key of the signature on the number equal to the maximum possible numerical value of the nT-bit block of the data, that is on 2nT–1.
KC = (C0, C1) = (R2nT–1 (K0), R2nT–1 (K1)).
2. Algorithm SnT of development of the digital signature for the nT-bit block T limited, on the value, a condition 0£T£2nT–1, consists in performance of "unilateral scrolling» both half of key of signature T and 2nT–1–T time accordingly:
s=SnT (T) = (s0, s1) = (RT (K0), R2nT–1–T (K1)).
3. Algorithm VnT of check of the signature consists in check of the validity of parities:
R2nT–1–T (s0) =C0, RT (s1) =C1 which, obviously, should be carried out for the original block of data T:
R2nT–1–T (s0) =R2nT–1–T (RT (K0)) =R2nT–1–T+T (K0) =R2nT–1 (K0) =C0,
RT (s1) =RT (R2nT–1–T (K1)) =RT+2nT–1–T (K1) =R2nT–1 (K1) =C1.
Thus, function of check of the signature will be following:
Let's show that for the given scheme necessary conditions of working capacity of the scheme of the signature are satisfied:
1. We will assume that at the disposal of the malefactor there is nT-bit block T, its signature s = (s0, s1), and a key of check KC = (C0, C1). Using this information, the malefactor tries to find the correct signature s' = (s ' 0, s ' 1) for other nT-bit block T '. For this purpose he should solve following equations rather s ' 0 and s ' 1:
R2nT–1–T ' (s ' 0) =C0,
RT ' (s ' 1) =C1.
At the disposal of the malefactor there is a block of data T with the signature s = (s0, s1), and it allows it to calculate one of values s ' 0, s ' 1, at all without owning a signature key:
(a) If T <T ', s ' 0=RT ' (K0) =RT '–T (RT (K0)) =RT '–T (s0),
(b) If T> T ', s ' 1=R2nT–1–T ' (K1) =RT–T ' (R2nT–1–T (K1)) =RT–T ' (s1).
However for a finding of second half of signature (s ' 1 in a case (a) and s ' 0 in a case (b)) it is necessary for it to execute scrolling in the opposite direction, i.e. to find Rk (X), having only value for большего k: Rk ' (X), k '> k that is вычислительно impossible. Thus, the malefactor cannot forge the signature under the message if has no a confidential key of the signature.
2. The second requirement also is carried out: the probability to pick up the block of data T ', distinct from block T, but possessing same digital signature, is extremely small and can not be taken into consideration. Really, let the digital signature of blocks T and T ' coincides. Then signatures of both blocks will be equal accordingly:
s=SnT (T) = (s0, s1) = (RT (K0), R2nT–1–T (K1)),
s' = SnT (T ') = (s ' 0, s ' 1) = (RT ' (K0), R2nT–1–T ' (K1)),
s=s', hence:
RT (K0) =RT ' (K0) AND R2nT–1–T (K1) =R2nT–1–T ' (K1).
Let's put for definiteness T£T ', then fairly following:
RT '–T (K0 *) = K0 *, RT '–T (K1 *) = K1 *, where K0 * = RT (K0), K1 * = R2nT–1–T ' (K1)
Last condition means that прокручивание two various blocks of the data the same number of times leaves their values invariable. The probability of such event is extremely small and can not be taken into consideration.
Thus the considered updating of the scheme of Diffi-Hellmana does possible the signature not one bit, and the whole bit group. It allows to reduce several times the size of the signature and keys of the signature/check of the given scheme. However it is necessary to understand that the increase in the size of signed bit groups leads экспоненциальному to growth of volume of necessary calculations and since some value does scheme work is inadmissible the inefficient. The border signed group is of "the reasonable size» somewhere near to восемью in bits, and blocks большего all the same are necessary for signing the size "in parts".
Now we will find the sizes of keys and the signature, and also volume necessary for realisation of the scheme of calculations. Let the size of the hesh-block and the block of the used code number are identical and equal n, and the size of signed bit groups is equal nT. We will assume also that if last group contains smaller number of bits, it is processed all the same as full nT-bit group. Then the sizes of keys of the signature/check and the signature coincide and are equal to the following size:
Bit,
Where éxù designates a number rounding off x to the nearest whole towards increase. Number of operations of enciphering EK (X), demanded for realisation of procedures of the scheme, are defined by below-mentioned parities:
· at development of the key information it is equal:
,
· at the signature and check of the signature it is twice less:
.
In table 2 following more low the calculated values of the sizes of keys and the signature, and number of demanded operations of enciphering depending on the size of signed bit groups under condition of use block криптоалгоритма with the size of the block n=64 a bat are resulted:
Table 2. Numerical indicators of the scheme of the signature depending on the size of bit groups.
|
nT |
Number of bats. |
The size of the signature and keys, byte |
Number of operations of enciphering |
|
|
|
Groups |
|KS | = | KC | = | s | |
WK |
WS=WC |
|
1 |
64 |
1024 |
128 |
64 |
|
2 |
32 |
512 |
192 |
96 |
|
3 |
22 |
352 |
308 |
154 |
|
4 |
16 |
256 |
480 |
240 |
|
5 |
13 |
208 |
806 |
403 |
|
6 |
11 |
176 |
1386 |
693 |
|
7 |
10 |
160 |
2540 |
1270 |
|
8 |
8 |
128 |
4080 |
2040 |
|
9 |
8 |
128 |
8176 |
4088 |
|
10 |
7 |
112 |
14322 |
7161 |
|
11 |
6 |
96 |
24564 |
12282 |
|
12 |
6 |
96 |
49140 |
24570 |
|
13 |
5 |
80 |
81910 |
40955 |
|
14 |
5 |
80 |
163830 |
81915 |
|
15 |
5 |
80 |
327670 |
163835 |
|
16 |
4 |
64 |
524280 |
262140 |
The size of a key of the signature and signature check can be reduced in addition following receptions:
1. There is no necessity to store keys of the signature of separate bit groups, they can be developed dynamically in the fullness of time by means of the generator криптостойкой scales. A signature key will be in this case the usual key used in the scheme of the signature of the block code number. For STATE THAT of 28147-89 this size is equal to 256 bits, therefore if the signature scheme is constructed on the VISITOR, the size of a key of the signature will be equal to the same to 256 bits.
2. In the same way, there is no necessity to store a file of keys of check of the signature of separate bit groups of the block, it is enough to store its hesh-combination. Thus the algorithm of development of a key of the signature and algorithm of check of the signature will be added by one more step – calculation of a hesh-code for a file of verifying combinations of separate bit groups.
Thus, the problem of the size of keys and the signature is completely solved, however, the main lack of the scheme – одноразовость keys – is not overcome, as it is impossible within the limits of the approach of Diffi-Hellmana. For practical use of such scheme calculated for signature N of messages, it is necessary for sender to store N signature keys, and to the addressee – N check keys that is inconvenient enough. However this problem can be solved in accuracy the same as the problem of keys for plural bit groups – generation of keys of the signature for all N messages from one master key and curling of all verifying combinations in one control combination by means of algorithm of development of a hesh-code has been solved. Such approach would solve a problem of the size хранимых keys, however would lead to necessity together the signature of each message to send lacking N–1 the verifying combinations necessary for calculation of a hesh-code from a file of all control combinations of separate messages. Clearly that such variant does not possess advantages in comparison with the initial. However in [7] the mechanism allowing considerably to lower a sharpness of a problem has been offered. Its basic idea – to calculate a control combination (a key of check of the signature) not as хэш from a linear file of verifying combinations of all messages, and in pairs – by means of a binary tree. At each level the verifying combination is calculated as хэш from two verifying combinations of younger level. The above combination level, the more than separate keys of check in it "is considered". We will assume that our scheme is calculated on 2L messages. We will designate through Ci (l) i combination of l levels. If numbering of combinations and levels to begin with zero, fairly following condition: 0£i <2L–l, and i verifying combination of l levels is calculated on 2l messages with numbers from i×2l to (i+1) ×2l–1 inclusive. The number of combinations of the bottom, zero level equally 2L, and the uppermost, L levels – one, it also is a control combination of all 2L messages on which the scheme is calculated. At each level, since the first, verifying combinations pay off under the following formula:
Ci (l+1) =H (C2 (il) || C2 (il) +1),
Where through A || B the result конкатенации two blocks of the data – A and B, and through H (X) – procedure of calculation of a hesh-code of the block of the data X is designated.
At use of the specified approach together with the message signature необходимо to transfer not N–1, as in an initial variant, but only log2N control combinations. The combinations corresponding to adjacent branches of a tree on a way from final top, the used signature corresponding to number, to a root should be transferred.
|
Level
аааааа 0: C0 (0) C1 (0) C2 (0) C3 (0) C4 (0) C5 (0) C6 (0) C7 (0) Fig. 3. The scheme paired хеширования verifying ааааааааааа combinations at development of the general key ааааааааааа signature checks. |
The scheme paired хеширования verifying combinations at development of the general key of check of the signature on eight messages приведена in drawing 3. So, in the scheme to 8 messages by transfer сообщения №5 (the control combination is allocated by a framework) together with it подписью should be transferred контрольная a combination of the message №4 (C4 (0)), the general for messages №№ 6–7 (C3 (1)) and the general for сообщений №№ 0–3 (C0 (2)), all of them выделены in drawing other background. At check of the signature value C5 (0) will be calculated from the message and its signature, and the total control combination which is subject to comparison with reference, under the following formula:
C=C0 (3) =H (C0 (2) || H (H (C4 (0) || C5 (0)) || C3 (1))).
Numbers of control combinations of each level, which should be transferred together with the signature of the message with number i (0£i <2L), are calculated under the following formula: Cë (il/) 2lûÅ1, l=0..., L–1 where xÅ1 means the number which is turning out as a result of inverting of younger bit in number x.
Necessity to send together with the message signature the additional information necessary for check of the signature, actually is not so burdensome. Really, in system on 1024=210 signatures together with the message and its signature it is necessary to transfer in addition 10 control combinations, and in system on 1048576=220 signatures – only 20 combinations. However at a great number of signatures on which the system is calculated, there is other problem – storage of additional combinations if they are calculated preliminary, or their development at the moment of signature formation.
Additional control combinations which are transferred together with the signature and are used at its check, developed at formation of a key of check on a key of the signature and can be stored in system and be used at the moment of signature formation, or be calculated anew during this moment. The first approach assumes expenses of disk memory as it is necessary to store 2L+1–2 hesh-combinations of all levels, and the second demands great volume of calculations at the moment of signature formation. It is possible to use and the compromise approach – to store all hesh-combinations since some level l *, and combinations of smaller level to calculate at signature formation. On 8 messages it is possible to store all in the scheme of the signature considered above 14 control combinations used at check (all them 15, but the uppermost is not used) then at check of the signature they should not be calculated anew. It is possible to store 6 combinations since level 1 (C0 (1), C1 (1), C2 (1), C3 (1), C0 (2), C1 (2)) then at check of the signature of the message №5 it will be necessary to calculate anew combination C4 (0), and the others (C0 (2), C3 (1)) to take from "storehouse", and т.д. The Specified approach allows to reach the compromise between speed and to requirements to occupied quantity of disk space. It is necessary to notice that refusal of storage of combinations of one level leads to economy of memory and growth of computing expenses approximately twice, that is dependence carries экспоненциальный character.
3.4. The scheme of the digital signature on the basis of the block code number.
Numerical parametres and used auxiliary algorithms of the considered scheme of the digital signature are more low resulted:
· EK – algorithm зашифрования with the size of the block of the data and a key n and nK bits accordingly;
· Гm (s, K) – the algorithm of development m bits криптостойкой scales with use of a n-bit vector of initial parametres (синхропосылки) s and nK-bit key K, represents recurrent algorithm of development of n-bit blocks of the data and their the subsequent зашифрования on algorithm EK;
· Pm®nK – a set of functions of expansion of m-bit blocks of the data to nK-bit for various m (it is typical – for multiple n, smaller nK);
· L – the factor of quantity of signatures (the system is calculated on N=2L signatures);
· nT – number of bits in signed bit groups, then number of groups equally
.
Algorithms of the scheme of the signature are more low stated:
1. Algorithm of formation of keys of the signature and signature check.
(a) Formations of a key of the signature.
The signature key is formed as the nK-bit block of the data by means of the hardware generator of casual codes or криптостойкого the program generator of pseudo-casual codes KS=GnT (...). Key bits should be independent and with equal probability to accept both possible values – 0 and 1.
(b) Formations of a key of check of the signature. The scheme of algorithm of formation of a key of check of the signature is represented in drawing 4.
Øàã 0. The initial data of algorithm – nK-bit data file KS – a signature key.
Øàã 1. We calculate nG – quantity of nT-bit groups in signed blocks.
Following steps 2–9 are carried out so much time, on how many signatures the scheme, i.e. for each number of the signature of system is calculated.
|
Fig. 4. Algorithm of development of a key of check of the signature. |
Øàã 2. To develop the block of scale in the size 2nnG bit by means of the generator криптостойкой scales on key KS with initial filling i (signature number) and to place it in a 2nnG-bit file X.
Øàã 3. The 2nnG-bit file X is interpreted as a file from 2nG n-bit elements Xj, X = (X1, X2..., X2nG), |Xj | = n,
Then for each element of this file its result of "unilateral scrolling» 2nT–1 time is calculated.
Øàã 4. For a file X its hesh-code which number i is an individual verifying combination for the signature is calculated and registers in the block of data S.
Following steps 5,6 are carried out the quantity of times equal to the factor of quantity of signatures L.
Øàã 5. If l younger bats of number of the signature – units, transition to a step 6, differently – cycle performance stops also management is transferred to a step 7.
Øàã 6. Current hesh-combination S unites c flowing õýø-êîìáèíàtsiej Dl level l, and for the received file hesh-value which becomes a new current hesh-combination is calculated.
Øàã 7. Current hesh-combination S replaces õýø-êîìáèíàtsiju Dl level l.
Øàã 8. Last calculated at algorithm performance current hesh-combination S also will grow out of algorithm work – a key of check of the signature. Besides, during algorithm performance hesh-combinations of all levels from 0 to L
, 0£l£L will be consistently developed, 0£i <2L–l which can be stored in system and are used at signature formation.
2. Algorithm of the signature of the hesh-block of data file.
The scheme of algorithm of the signature of the hesh-block of data file is represented in drawing 5.
Øàã 0. The initial data of algorithm:
· T – signed – the n-bit hesh-block of data file;
· KS – a signature key – nK-bit data file;
· i – a signature serial number.
Øàã 1. We calculate nG – number of nT-bit groups in the signed n-bit hesh-block.
Øàã 2. To develop the block of scale in the size 2nnG bit by means of the generator криптостойкой scales on key KS with initial filling i (signature number) and to place it in a 2nnG-bit file X.
Øàã 3. The 2nnG-bit file X is interpreted as a file from nG steam of n-bit elements X = ((X1, X2)..., (X2nG–1, X2nG)), |Xj | = n,
Then for each component of each element of this file, соответствующего to certain bit group of the hesh-block, the necessary number of times is carried out procedure of "unilateral scrolling».
|
Fig. 5. Algorithm of the signature of a hesh-code of the message. |
Øàã 4. To an individual verifying combination it is consistently added paired hesh-combinations, on one combination from each level from 0 to L–1 which are necessary at calculation of a verifying combination of the uppermost level (L), the general for all messages. Number of an added combination of each level is defined by rejection of quantity of last bats in number of the signature, level equal to number, and in inverting of younger bit of the received number.
Øàã 5. It is As a result received the digital signature of the hesh-block of message S = (X, D), consisting of a file of signatures of bit groups of the block X = (X1, X2..., X2nG) and from a file of additional verifying combinations D = (D0, D1..., DL–1), necessary for performance of procedure of check of the signature and paired verifying combinations used at calculation.
3. Algorithm of check of the signature of the hesh-block of data file.
The scheme of algorithm of check of the signature of the hesh-block of data file is represented in drawing 6.
|
|
Øàã 0. The initial data of algorithm:
· T – signed – the n-bit hesh-block of data file;
· s – the hesh-block signature, consists of a file X containing 2nG of n-bit elements of the signature of bit groups, and file D containing L of n-bit hesh-combinations;
· i – a signature serial number.
Øàã 1. We calculate nG – number of nT-bit groups in the signed hesh-block having the size n bit.
Øàã 2. According to rules of check of the signature «unilateral scrolling» elements of the signature of the bit groups containing in a file X, on two elements on each group is made.
Øàã 3. For a file X is calculated and registers in S its hesh-code which should be equal an individual verifying combination for i signatures.
Following steps 4–6 are carried out the quantity of times equal to the factor of quantity of signatures L.
Øàã 4. The choice on value of l bits (numbering with 0 from outside younger bit) signature numbers is made.
Øàã 5. If value of bit equally 0 to a code the next hesh-combination containing in the signature on the right is added, for the received block is calculated hesh-function which replaces the previous contents S.
Øàã 6. If value of bit equally 1 the same is carried out, only a hesh-combination is added to a code at the left.
Øàã 7. In the end of algorithm performance in S the code which should be compared to a key of check of the signature if codes are identical contains, the signature is considered true, differently – incorrect.
The conclusion.
Firmness of the offered scheme of the digital signature is defined by firmness of the used block code number, and stability to opening by reboric methods – least of numbers n, nK. The key complete set in the given scheme is calculated on certain number of signatures that, on the one hand, can be perceived as a scheme lack, but with another allows to licence quantity of signatures, facilitating that its commercial use. The considered scheme of the signature does not correspond to the standard of Russia for the digital signature, and algorithm of calculation MDC – to the standard on development of a hesh-code of data file that does impossible certification in the corresponding organisations of devices and software products, their realising. However the stated schemes quite can be used there where questions at issue cannot be taken out on level arbitration and proceedings, for example, in systems of automation of internal document circulation of establishments, especially if electronic document circulation does not replace paper, and exists in addition to it for acceleration of passage of documents.
As the appendix to the present article initial texts in language of the assembler for processors of clone Intel of 8086 functions of calculation MDC for blocks of the data and the functions realising algorithms of the described scheme of the digital signature are resulted. Function of development of a hesh-code (MDC) is written in such a manner that allows to process blocks of the data in parts, that is for some calls. All functions use as a basis algorithm зашифрования in accordance with GOST 28147–89. Also texts of test programs in language of Si for check of an invariance of files on the basis of MDC and the digital signature are applied.
The literature.
1. A.J.Vinokurov. GOST is not simple..., and it is very simple, М, Monitor.-1995.-N1.
2. A.J.Vinokurov. Once again about GOST., М, Monitor.-1995.-N5.
3. A.J.Vinokurov. Algorithm of enciphering of GOST 28147-89, its use and realisation for computers of platform Intel x86., the Manuscript, 1997.
4. A.J.Vinokurov. How the block code number is arranged?, the Manuscript, 1995.
5. M.E.Smid, D.K.Bransted. The standard of enciphering of the data: the past and the future. / the lane with English / М, the World, ТИИЭР.–1988.–т.76.–N5.
6. Systems of processing of the information. Protection cryptographic. Algorithm of cryptographic transformation of GOST 28147–89, М, Gosstandart, 1989.
7. B.V.Berezin, P.V.Doroshkevich. The digital signature on the basis of traditional cryptography//information Protection, вып.2., М: MT of "Irbis-Ii", 1992.
8. W.Diffie, M.E.Hellman. New Directions in cryptography//IEEE Trans. Inform. Theory, IT 22, vol 6 (Nov. 1976), pp. 644-654.
9. U.Diffi. First ten years of cryptography with an open key. / the lane with English / М, the World, ТИИЭР.–1988.–т.76.–N5.
[1] Reports in cryptography the set is called corrected also the algorithms of higher order regulating use of algorithms of the lowest order. Its basic purpose – to guarantee correct use of cryptographic algorithms.
|
|