Introduction

Throughout many centuries the mankind used cryptographic methods for information protection by its transfer and storage. Approximately by the end of XIX century these methods became object of mathematical studying. The branch of mathematics studying protection of the information, traditionally is called as cryptology [cryptology] and is subdivided into cryptography [cryptography], engaged in working out of new methods and a substantiation of their correctness, and криптоанализ [cryptanalysis] which problem - intensive studying of existing methods, is frequent for the purpose of real disclosing of secrets of other party. Cryptography and криптоанализ are in close interaction with each other and with practical needs and develop in parallel closed governmental organisations of many states and the international scientific community.

Now there are thousand the cryptographic systems realised as программно, and is hardware. Among them it is possible to allocate systems, the cryptographic which principle of work is kept a secret as, for example, microcircuit Clipper offered by the government of the USA as the cryptographic standard for telecommunications, and the systems which algorithm is opened, and confidential is only defined, as a rule small, the portion of the information named (confidential) key [(secret) key] - concerns them the majority of the systems realised программно and intended for wide use. Further we will consider only systems of the second type.

In system of considered type a problem of opening of system, that is infringement of protection of the information without preliminary knowledge of a key, as a rule, theoretically разрешима at presence at the opening party of unlimited computing resources. From the mathematical point of view reliability of cryptographic system is defined by complexity of the decision of this problem taking into account real computing resources of the potential opening party. From the organizational point of view the parity of cost of potential opening and value of the protected information matters.

Mathematical research of reliability of cryptographic systems is complicated by absence of universal mathematical concept of complexity. For this reason now it is impossible not only to prove reliability of the majority of cryptographic systems, but even adequately to formulate. As a rule, application of this or that cryptographic system is based on results long-term practical криптоанализа the systems of the given type to some extent supported with a mathematical substantiation. This substantiation can reduce a problem of disclosing given криптосистемы to any problem of the theory of numbers or the combination theory which decision is considered really not realizable, or that it is more preferable, to a class of NP-full problems reducibility to which is "standard" of practical unsolvability. At the same time, the concept of practical unsolvability for concrete practical problems is not accurately defined or stable, thanks to development of computer facilities and methods криптоанализа.
 

Long time the scheme with a symmetric key [symmetric key, dual key] was the traditional cryptographic scheme. In this scheme there is one key which participates in enciphering and information decoding. Ciphering procedure by means of a key makes a number of actions over the initial data, дешифрующая procedure by means of the same key makes return actions over a code. Decoding of a code without a key is supposed almost impracticable. If the information ciphered thus is transferred on usual, i.e. not protected, to a communication channel, the same key should be available for the sender and the addressee owing to what there is a necessity for the additional protected channel for key transfer, vulnerability of system raises and organizational difficulties increase.

The method concerns a class of algorithms with a symmetric key of "a disposable notebook” [one-time pad], consisting in bit-by-bit addition (“гаммировании”) the ciphered text with casual sequence of bits - a key (see [S94]). The length of a key should coincide with length of the ciphered text and each piece of a key should be used unitary; otherwise the text easily gives in to unapproved decoding. At performance of these conditions the given method is the unique method theoretically steady against криптоанализа of the opponent with unlimited computing resources. Despite it, now the method of "a disposable notebook” practically is not applied because of the organizational complexities connected with generation, transfer and storage of superlong keys used in it.

As other example of the scheme with a symmetric key algorithm DES (Data Encryption Standard), accepted as the official cryptographic standard of the USA for protection noncritical [unclassified] can serve on November, 23rd, 1976 the information (see [S94], s.219-243). Position has been included In the standard about obligatory ресертификации algorithm (revision) each five years; last such ресертификация has taken place in 1992 According to experts, in connection with certain successes in криптоанализе DES and occurrence of new methods of enciphering with a symmetric key, the algorithm can not be ресертифицирован for the following five years' term. Nevertheless, DES still it is considered криптографически proof algorithm and remains the most widespread scheme of enciphering with a symmetric key.

The Russian standard on cryptography with a symmetric key is defined GOST 28147-89 “Systems of processing of the information. Protection cryptographic. The algorithm of cryptographic transformation” which has been installed on July, 1st, 1990 Unlike DES, the standard contains instructions that it “by the possibilities does not impose restrictions on degree of privacy of the protected information”. In general the algorithm of GOST 28147 is similar DES, but there is a number of essential differences, as, for example, length of a key and treatment of contents of knots of replacement [in scheme DES named “S-boxes”]. While filling of knots of replacement DES is optimised from the point of view of cryptographic firmness and obviously specified in the standard, filling of knots of replacement of GOST 28147 “is a confidential element and is delivered when due hereunder”. Considering that it at the same time “is a long-term key element, the general for the COMPUTER network”, and that “the established order” delivery can not provide cryptographic optimisation, this point of the standard is represented to one of its weak places, complicating realisation and not promoting cryptographic firmness. However at the task of the optimised values for replacement knots cryptographic firmness of algorithm is comparable with firmness DES.
 

In 1976 U.Diffi and M.Hellmanom [DH76] has been offered new type of cryptographic system - system with an open key [public key cryptosystem]. In the scheme with an open key is available two keys, opened [public] and confidential [private, secret], chosen in such a manner that their consecutive application to data file leaves this file without changes. Ciphering procedure uses an open key, дешифрующая - confidential. Decoding of a code without knowledge of a confidential key is almost impracticable; in particular, the problem of calculation of a confidential key on a known open key is almost unsoluble. The basic advantage of cryptography with an open key - the simplified mechanism of an exchange of keys. At communications realisation on a communication channel the open key that does possible use for this purpose of the usual channel is told only and eliminates requirement for the special protected channel for key transfer.

With the advent of systems with an open key concept about information protection, and together with it cryptography functions have considerably extended. If earlier reliable enciphering of the information, now a cryptography scope was considered as the primary goal of cryptographic systems includes also the digital signature (аутентификацию), licensing, нотаризацию (witnessing), the distributed management, voting schemes, ecash and many other things (see [BFS91], ч.7, [S94], ч.1). The Most widespread functions of cryptographic systems with an open key - enciphering and the digital signature, and a role of the digital signature recently has increased in comparison with traditional enciphering: some of systems with an open key support the digital signature, but do not support enciphering.

The digital signature is used for аутентификации the texts transferred on telecommunication channels. It is similar to the usual hand-written signature and possesses its basic properties: certifies that the signed text proceeds from the face, put the signature, and does not give to the most this person of possibility to refuse from the obligations connected with the signed text. The digital signature represents a small amount of the additional information transferred together with the signed text. Unlike enciphering, at signature formation the confidential key is used, and at check - opened.

Because of features of the algorithms underlying systems with an open key, their speed at processing of the individual block of the information usually in tens times is less, than speed of systems with a symmetric key on the block of the same length. The mixed methods realising cryptographic algorithms of both types are often applied to increase of efficiency of systems with an open key. At information enciphering the casual symmetric key gets out, the algorithm with a symmetric key for enciphering of the initial text is caused. And then algorithm with an open key for enciphering of a symmetric key. On the communication channel the text ciphered by a symmetric key, and the symmetric key ciphered by an open key is transferred. For action decoding are made upside-down: at first by means of a confidential key of the addressee the symmetric key, and then by means of a symmetric key - the ciphered text received on the channel is deciphered. For digital signature formation under the signed text its unidirectional hesh-function (digest) [one-way hash function, digest], representing one short block of the information characterising all text as a whole is calculated; the problem of restoration of the text on its hesh-functions or selection of other text having the same hesh-function, is almost unsoluble. At direct formation of the signature, instead of enciphering by a confidential key of each block of the text the confidential key is applied only to hesh-function; on the channel the text and the generated signature of hesh-function is transferred. For signature check hesh-function from the text received on the channel then by means of an open key it is checked is again calculated that the signature corresponds to the given value of hesh-function. Algorithms of calculation of unidirectional hesh-functions are, as a rule, logically closely connected with algorithms of enciphering with a symmetric key.

The described hybrid methods of enciphering and the digital signature combine efficiency of algorithms with a symmetric key and property of independence of additional confidential channels for transfer of the keys, inherent in algorithms with an open key. Cryptographic firmness of a concrete hybrid method is defined by firmness of the weakest link in a chain consisting of algorithms with symmetric and with an open key, chosen for its realisation.
 

In 1978 R.Rivest, A.Shamir and L.Adleman [RSA78] have created the first криптосистему with an open key for enciphering and the digital signature, received name RSA (under the first letters of surnames of authors). The system is described in terms of the elementary theory of numbers. Its reliability is caused by practical unsolvability of a problem of decomposition of the big natural number on simple multipliers. The current state of algorithms факторизации (decomposition on a multiplier) allows to solve this problem for numbers in length to 430 bats; proceeding from it, the key of 512 bits is considered reliable for protection of the data for the term up to 10 years, and in 1024 bits - certainly reliable. The length of the signature system RSA coincides with length of a key.

In spite of the fact that is absent математически the proved data of a problem of disclosing RSA to a decomposition problem on a multiplier, and also decomposition problems on a multiplier to a class of NP-full problems, the system has passed test by practice and is the recognised standard de-facto in industrial cryptography, and also the official standard of some the international organisations. On the other hand, free distribution of the software based on RSA, is limited by that algorithm RSA is protected in the USA by a number of patents.
 

In 1991 in the USA the project of the federal standard of the digital signature - DSS (Digital Signature Standard, [DSS91], see also [S94], s.304-314), digital signatures DSA describing system (Digital Signature Algorithm) has been published. Its patent cleanliness was one of the basic criteria at project creation.

Offered algorithm DSA, has, as well as RSA, teoretiko-numerical character, and is based on cryptographic system the Ale-gamalja [E85] in a variant of Shnorra [S89]. Its reliability is based on practical unsolvability of a certain special case of a problem of calculation of the discrete logarithm. Modern methods of the decision of this problem have the approximately same efficiency, as methods of the decision of a problem факторизации; in this connection it is offered to use keys in length from 512 to 1024 bats with the same characteristics of reliability, as in system RSA. The length of the signature system DSA is less, than in RSA, also makes 320 bits.

From the moment of publication the project has received many critical responses (see, e.g., [R92]), many of which have been considered at its completion. One of the main arguments against DSA is that, unlike the general problem of calculation of the discrete logarithm, its special case used in the given scheme, is a little studied and, probably, has essentially smaller complexity of opening. Besides, the standard does not specify a way of reception of the pseudo-random numbers used at formation of the digital signature, and does not specify that this element of algorithm is one of the most critical on cryptographic firmness.

Functions DSA are limited only by the digital signature, the system essentially is not intended for enciphering of the data. On speed system DSA is comparable with RSA at signature formation, but it is essential (at 10-40 time) concedes to it at signature check.

Together with project DSS the project of standard SHS (Secure Hash Standard), describing unidirectional hesh-function SHA (Secure Hash Algorithm), recommended for use together with DSA (see [S94], s.333-336) is published. Hesh-function SHA is updating of algorithm MD4, well-known in the cryptographic literature.
 

In 1993 in Russia two state standards “Procedures of development and check of the electronic digital signature on the basis of asymmetric cryptographic algorithm” and “Function хэширования”, under the general heading “Information technology have been published. Cryptographic protection of the information”.

The standard “Procedures of development and check of the electronic digital signature...” It is in many respects similar to the American analogue DSS. For formation and check of the digital signature in it the same algorithm the Ale-gamalja and Shnorra, as in DSS, with insignificant updatings is used. There are two alternative lengths of a key, 512 and 1024 bits; the length of the signature makes 512 bits.

For generation of keys a number of new algorithms is offered. The keys received by means of these algorithms, have a special appearance that can potentially simplify a problem of opening of system in comparison with DSS. Criticism DSS connected with insufficiently developed theoretical substantiation of algorithm, in a case росийского the standard is a little softened with that the key element q gets out longer, than in DSA. Criticism. Connected with absence of the specification for a way of reception of pseudo-random numbers, remains in force.

As well as DSS, the Russian standard defines only algorithm of the digital signature, but not enciphering. Speed of both algorithms approximately coincides.

The standard “Function хэширования” is intended for use together with the standard “Procedures of development and check of the digital signature” and represents the original algorithm based on a method of enciphering with a symmetric key of GOST 28147. The standard does not contain a cryptographic substantiation of the chosen algorithm and does not correct GOST 28147 regarding filling of knots of replacement.

Despite the specified lacks, the system described in the Russian standard, is applicable in many areas, especially for commercial appendices.
 

St.-Petersburg МГП “ТЕРКОМ” the cryptographic system TerKript representing a complex of programs in language C of standard ANSI is developed. The system realises in full algorithms DES, GOST 28147, RSA, DSS/SHS and the Russian cryptographic standards. Algorithms are realised on the basis of the general procedures of the theory of the numbers using modern teoretiko-numerical methods for achievement of peak efficiency. There is the special version of system optimised for work on personal computers IBM AT 286, 386, 486.