# Method of generation and authenticity check of electronic digital signature, which certifies electronic document

FIELD: technological processes.

SUBSTANCE: invention is related to the sphere of electrical communication, namely to the sphere of cryptographic devices and methods of electronic digital signature (EDS) check. In the method the secret key (SK) is formed, which includes three many-digit binary numbers (MDN) p, q and γ, where p, q are prime numbers and γ is composite number. The open key (OK) is formed in the form of two many-digit binary numbers n and α, where n = pq and α - number, which is related to index q by module n. Electronic document (ED) is accepted in the form of many-digit binary number H. Electronic digital signature (EDS) Q is formed depending on values of SK, OK and many-digit binary number H. The first checking many-digit binary number A is formed depending on Q. The intermediate many-digit binary number W is generated depending on OK and many-digit binary number H. The second checking many-digit binary number B is formed depending on W, and numbers A and B are compares. In case parameters of A and B numbers match, conclusion is drawn about authenticity of electronic digital signature.

EFFECT: reduces size of electronic digital signature without reduction of its resistance level.

10 cl, 6 ex

The invention relates to the field of telecommunications and computing, and more particularly to the field of cryptographic authentication methods electronic messages transmitted over telecommunication networks and computer networks, and can be used in systems for the transmission of electronic messages (documents), certified by an electronic digital signature (EDS), presented in the form of a multibit binary number (MDC). Here and further below MDC refers to an electromagnetic signal in binary digital form, the parameters of which are: the number of bits and the order of their unit and zero values (the interpretation used in the description of terms are given in Appendix 1.)

There is a method of generating and verifying the digital signature described in the books [1. Maidanov. Cryptography. M, CADIZ IMAGE, 2001; 2. Aguesthouse, Ebechovice. Introduction to public key cryptography. St. Petersburg, the World and the family, 2001. - s.43]. The known method consists in the following sequence of actions:

generate the secret key in the form of three simple MDC p, q and d, form a public key (n, e) as a pair MDC n and e, where n is a number representing the product of two primes MDC p and e, and e - MDC satisfying ed=1 mod(p-1)(q-1), accept an electronic document,

presents MDC H, depending on the values of H and the value of the secret key form Acpw as MDC Q=S=H^{
d}mod n.

form a first test MDC A=H;

form the second test MDC B, which MDC S erected in the integer degree of e modulo n: B=S^{e}mod n;

compare the generated test MDC A and B;

the coincidence of parameters compared MDC A and B make a conclusion about the authenticity of the digital signature.

The disadvantage of this method is the relatively large size of the signature and the need to increase the size of the signature in the development of new, more efficient algorithms for the factorization of n multipliers or growth performance of modern computing devices. This is because the value of an element of the signature S is computed by performing arithmetic operations modulo n, and the resistance of the EDS is determined by the complexity of the decomposition of the module n, the factors p and q.

There is also known a method of forming and authentication EDS El-Gamal, described in the book [Moldovyan A. A., Moldovyan N., Tips BJ Cryptography. - SPb, DOE, 2000. - s-159], which includes the following steps:

form easy MDC p and a binary number G, which is a primitive root modulo p, generate a secret key in the form MDC x, depending on a secret key to form a public key in the form MDC Y=G^{x}mod p, accept an electronic document (ED), presented in the form of MDC H, depending on H and the secret key of the Fort is irout EDS Q in the form of two MDC S and R,
that is, Q=(S, R);

follow the procedure of authentication, digital signature, including the calculation of the two control parameters using the original MDC p, G, Y, H and S by construction MDC G, Y, R in discrete degree modulo p and comparing the calculated control parameters;

if the values match, the control parameters make a conclusion about the authenticity of the digital signature.

The disadvantage of this method is the relatively large size of the EDS. This is because the values of the elements of the signature S and R are calculated by performing arithmetic operations modulo p-1 modulo p, respectively.

The closest to the technical nature of the claimed is a method of forming an authentication and digital signature, as described in the article [Kostin A. A., Moldovyan D.N., N.A. moldovyan New cryptosystem with public key based on the RSA-module // Problems of information security. 2005 (68). No. 1. P.8-12]. The closest analogue (prototype) is to perform the following sequence of actions:

generate the secret key in the form of three MDC p, q and γwhere p, q are Prime numbers and γ - composite number, form the public key (n, α) as a pair MDC n and αwhere n is a number representing the product of two primes MDC p and q, and α - the number relating to MDC γ as an indicator modulo n, take an electronic document to provide the Lenna H MDC, depending on the values of H and the value of the secret key to form a digital signature Q in the form MDC S, i.e. Q=S;

form a first test MDC A, which MDC S erected in the degree of H modulo n;

form the second test MDC B, which MDC α erected in integer degree u>1 modulo n: B=α^{u}mod n;

compare the generated test MDC A and B;

the coincidence of parameters compared MDC A and B make a conclusion about the authenticity of the digital signature.

The disadvantage of the nearest analogue is also relatively large size of the signature, which is caused by the need to compute S by performing arithmetic operations modulo n, which amount to provide the desired level of firmness EDS is 1024 bits or more.

The aim of the invention is to develop a method of forming an authentication and digital signature, certifying ED, that reduce the size of the signature without compromising durability EDS.

This objective is achieved in that in the known method of forming and authentication, digital signature, certifying the ED, namely, form a secret key, comprising three MDC p, q and γwhere p, q are Prime numbers and γ - composite number, form a public key that includes two MDC n and αwhere α - number related to the metric γ modulo n and n=pq, accept ED, presents MDCN, depending on the values of H and the value of the secret key to form a digital signature Q, form first and second test MDC A and B, compare them, and the coincidence of their parameters make a conclusion about the authenticity of the digital signature, the inventive method is that the EDS form Q in the form of two MDC R and S, i.e. Q=(R, S)form the first test MDC A depending on EDS, generate intermediate MDC W depending on the value MDC R, S, H, n and α and forming a second test MDC B by compressing the intermediate conversion MDC W.

New is also that the first test MDC A form by subtracting S from the value of R.

New is also that the first test MDC A form by dividing the value of R is S.

New also is the fact that the first test MDC A form by multiplying the values of S and R.

New also is the fact that the first test MDC A form by adding the values of S and R.

New is also that the intermediate MDC W generated by the operation of the raising number α the degree of U modulo n, where U IS MDC, which is calculated by the formula U=RS or by the formula U=RSH.

New also is the fact that an intermediate MDC W generated by the operation of the raising number α the degree of U modulo n, where U IS MDC, which is calculated by the formula U=RS or the U=RSH, then the obtained intermediate MDC W additionally transform according to the formula W←WH mod n or the formula W←(W+H)mod n, where the sign ← denotes the assignment operation.

New also is the fact that an intermediate MDC W generated by the operation of the raising number α the degree of U modulo n, where U IS MDC, which is calculated by the formula U=RS or by the formula U=RSH, and then optionally convert the intermediate MDC W by the formula W≥W_{y} ^{S}mod n or the formula W←W_{y} ^{RH}mod n, where the sign ← denotes the assignment operation, y=α^{x}mod n and x - additional random MDC.

New also is the fact that the compressive transformation of intermediate MDC W performed using a hash function.

New also is the fact that the compressive transformation of intermediate MDC W performed by the operation of taking the remainder of the intermediate MDC W on a Prime number δwhose length is in the range from 64 to 256 bits.

Thanks to the new essential features by modifying the procedure of forming a testing MDC is achieved by reduction of the size of the signature, and the choice of a fixed size secret MDC γ ensures the constancy of the size of the signature if you increase the size of the secret MDC p and q, and therefore maintaining stability EDS, taisealised formulated the technical result.

The analysis of the level of technology has allowed to establish that the analogues, characterized by a set of characteristics is identical for all features of the claimed technical solution, there are no known sources of information that indicates compliance of the claimed invention to condition patentability of "novelty."

Search results known solutions in this and related fields in order to identify characteristics that match the distinctive features from the nearest analogue of the features of the declared object, showed that they do not follow explicitly from the prior art that indicates compliance of the claimed invention the term "inventive step".

The possibility of implementing the inventive method is explained as follows. It is known that the complexity of the task decomposition of an integer into two large Prime factor depends on the length of the last, so when new methods of decomposition increases the length of its simple factors. The public key is formed as a composite number n=pq, depending on the secret Prime numbers n and q are chosen such that the number of q - 1 is divisible by a Prime number ε and not divided by a Prime number λand the number of p - 1 is divisible by a Prime number λ and not divided by a Prime number ε. Moreover, the number of ε and λ select length approximately equal 80-256 bits that prevent the et possibility of guessing or picking their values.
Choosing as α a number of related modulo n to the index γ=ελwe can use the following expressions for the formation of the first and second test MDC A and B, respectively: A=F(α^{k}mod n) and B=F(α^{RSH}mod n), where F is some compression function, computed by performing compressive conversion number, which is its argument, and the element of the signature R is calculated according to pre-select a random number k according to the formula R=F(α^{k}mod n). For example, as a compressive function, you can use the operation of taking the remainder after dividing by MDC δhaving the specified length and specifies the size of values of the function f as a compressive function you can also use the hash function described, for example, in the book [Moldovyan A. A., Moldovyan N. Introduction to cryptography with a public key. - SPb. BHV-Petersburg, 2005. - 286 C.; see p.184-204].

Considering the choice of the number α equality A=B runs when comparing k=RSH mod γwhence we obtain the formula for the calculation of the signature:

The owner of the secret number γ can easily compute the correct value of the item signature S, which will depend on the pre-formed values of R and values of H. the width of the element signature S will not exceed the discharge is ti secret number γ as the number S is calculated by the module γ. Thus formed the signature (R, S) will satisfy the authentication procedure EDS. The EDS resistance is determined by the complexity of the decomposition of the module n, multipliers and complexity of taking the logarithm modulo n at the base α. As the number of α belongs to a rather great indicator γ, the complexity of taking the logarithm is not lower than the complexity of the decomposition of the n multipliers. This task if bit n is equal to 1024 bits or more are practically not feasible. When new methods of discrete taking the logarithm or new methods of factorization of n bit multipliers and can be chosen to be 2048 bits or more when storing the bit values of compressive features and capacity of a secret number γ. Bit compression function is 80-256 bits makes negligible the probability of finding the correct values of the signature without using the secret key. Bit compression function determines the bit width of the element the signature of R. Since γ=ελ, width γ approximately equal to the sum of the bit ε bit λthat is 160-512 bit. Taking this into account comments received that the size of the signature (R, S) ranges from 240 to 768 bits. In the present method of forming and validating a signature, there is a mechanism that is especiauy the safety of the size of the signature with larger numbers, specifies the complexity of the task of factoring or discrete taking the logarithm. Compressive function F(W) can be defined through the operation of taking the remainder after division by a Prime number δhaving the desired bit depth: F(W)=W mod δwhere δ≠ε, δ≠λ and the bit number δ equal to between 80 and 256 bits.

Consider the examples of implementation of the claimed technical solution with an artificially reduced bit width used numbers.

Example 1. Implementation of the proposed method with the illustration of specific numerical values.

The example MDC recorded for brevity, in the form of decimal numbers in which computational devices are presented and converted into binary form, i.e. as a sequence of signals of high and low potential. When the authentication EDS perform the following steps.

1. Generate the secret key in the form of a triplet (p, q, γ), where

MDC γ=ελwhere λ=1721, ε=48463 γ=83404823;

MDC p=572λ+1=984413 and MDC q=12ε+1=581557.

2. Generate the public key in the form of pairs of numbers (n, α), where

MDC n=pq=572492271041;

MDC α=286266028236.

3. Take the public key of the signer (n, α)sent, for example, by the certification authority for telecommunication networks.

4. Take ED presented, for example, SL is blowing MDC H (which may be taken in particular, the hash function from ED):

H=37975637.

5. Form a digital signature Q as a pair of numbers (R, S), which performs the following steps:

5.1. Ask a random number k=4757231.

5.2. Form element signature R by performing the operations defined by the formula R=(α^{k}mod n) mod δwhere δ=84713:

S=77530.

5.3. Form element signature S by performing the operations defined by the formula:

S=1371543.

6. Form a first test MDC A depending on EDS: A=R=77530.

7. Generate intermediate MDC W depending on H in accordance with the formula W=α^{U}mod n, where U=RSH=4038167036659489230:

W=179477867971.

8. Form the second test MDC IN by compressive conversion intermediate MDC W, and as a compressive conversion use the operation of taking the remainder from dividing by the number of δ=84713:

B=W mod δ=179477867971 mod 84713=77530.

9. Compare (e.g., bitwise) the parameters of the first and second test MDC A and B. the Comparison shows that the parameters MDC A and B coincide, which indicates the authenticity of the digital signature, i.e. adopted EDS relates to the ED presented MDC H, and formed the signing, which corresponds to the accepted public key (n, α, β).

Considered in the example implementation of the claimed method steps ensure the correctness of the claimed SPO is both since in the General case for arbitrary length integers n, α, p, q, γ, H, R and S, formed in accordance with the claimed method. It is proved theoretically as follows:

The correct value of the EDS can be calculated only when the knowledge of a secret MDC γ. At the same time, the validation of the signature is performed using the public key (n, α). For unauthorized EDS formation it is necessary to decompose the number n on the factors p and q, then arrange the numbers p - 1 and q - 1 and find the value γ. However, when a large bit number n, this task is computationally feasible. When new methods of problem decomposition is possible to increase the length of the numbers p and q, and consequently to increase the length of the number n, while maintaining the same size number γ and still clutching functions. This will ensure the preservation of the size of the signature when setting the desired values of the complexity of the problem of the factorization of n multipliers. However, an increase in size of the number n will also lead to the increasing complexity of discrete tasks taking the logarithm associated with the attempts to calculate the value of k the value of R and then determine the secret value γ as one of the factors of a number RSH - k.

The following additional examples of implementation of the proposed method does not specify any specific the e value of the numerical values. The correctness of the method is proved mathematically for arbitrary values of the parameters selected in accordance with the description of the invention and the specification of the implementation options in the individual examples.

Example 2. Implementation of the proposed method for making digital signature length of 240 bits.

As γ and δ use numbers of length 160 bits and 80 bits, respectively, so the size of the signature is reduced to a length of 240 bits while maintaining high reliability. In this example performs the following sequence of actions.

1. Generate the secret key in the form of a triplet (p, q, γ), where MDC γ=ελ, ε divides evenly the number of q - 1 and λ divides p - 1, MDC p and q are Prime numbers. The length of the numbers ε and λ chosen equal to 80 bits, which specifies the length, number γapproximately 160 bits.

2. Generate the public key in the form of pairs of numbers (n, α), where MDC n=pq and α there are a number relating to the index γ modulo n.

3. Take the public key of the signer (n, α)sent, for example, by the certification authority for telecommunication networks.

4. Take ED presented, for example, the following MDC H (which can be taken, in particular, the hash function from the ED).

5. Form of digital signature in the form of two numbers R and S, which performs the following steps:

5.1. Ask by chance the number k.

5.2. Form element signature R by performing the operations defined by the formula R=F(Hα^{kH}mod n)=(Hα^{kH}mod n) mod δwhere δ - additional Prime number of length 80 bits. Since the latter formula specifies evaluation module length 80 bits, then the value of R also has a length of 80.

5.3. Form element signature S by performing the operations defined by the formula. This formula specifies the evaluation module of length 160 bits, so the value of S also has a length of 160 bits, and EDS - length of 240 bits.

6. Form a first test MDC A depending on EDS: A=R.

7. Generate intermediate MDC W in accordance with the formula W=α^{U}mod n, where U=RSH.

8. Convert the intermediate MDC W in accordance with the formula W←HW mod n, where the sign ← denotes the assignment operation. The result of this transformation, we obtain: W=Hα^{RSH}mod n.

9. Form the second test MDC IN by compressive conversion intermediate MDC W, using as a contractive transformation of the operation of taking the remainder after division by a Prime number δ:

B=W mod δ=(Hα^{U}mod n)mod δ=(Hα^{RSH}mod n)mod δ.

10. Compare (e.g., bitwise) the parameters of the first and second verification numbers A and B.

The coincidence of the values of A and B means that the EDS is podlinnoi, i.e. it refers to the taken who have ED, presents MDC H, and formed the signing, which corresponds to the accepted public key (n, α).

It is proved theoretically as follows. We have B=(Hα^{HRS}mod n)mod δ. Because α there are a number relating to the index γ modulo n, then:

Example 3. Implementation of the proposed method for making digital signature length of 320 bits.

In this example, as γ and δ use numbers with a length of 160 bits, so the size of the signature is equal to 320 bits while maintaining high reliability. In this example performs the following sequence of actions.

1. Generate the secret key in the form of a triplet (p, q, γ), where length is the number of γ chosen equal to 160 bits.

2. Generate the public key in the form of pairs of numbers (n, α), where MDC n=pq and α there are a number relating to the index γ modulo n.

3. Take the public key of the signer (n, α)sent, for example, by the certification authority for telecommunication networks.

4. Take ED presented, for example, the following MDC H (which can be taken, in particular, the hash function from the ED).

5. Form of digital signature in the form of two numbers R and S, which performs the following steps:

5.1. Ask a random number k.

5.2. Ask first additional MDC δ length 160 bits.

5.3. Calculate the which additional MDC G by the formula

G=F(Hα^{k}mod n)=(Hα^{k}mod n)mod δ.

The formula for the formation of the G sets of calculations modulo length 160 bits, so the value of G is of length 160 bits.

5.4. Form of digital signature in the form of the following two numbers:and R=S+G. the Formula for the formation of S specifies evaluation module length 160 bits, so the value of S has a length of 160 bits. Element signature R has a length of about 160 bits, since it is the sum of two numbers of length 160 bits. The length of the digital signature is equal to the sum of the lengths of its elements R and S, i.e. the EDS has a length of 320 bits.

6. Form a first test MDC A depending on EDS:

A=R-S.

7. Generate intermediate MDC W in accordance with the formula W=α^{U}mod n, where U=RSH.

8. Convert the intermediate MDC W in accordance with the formula W←HW mod n, where the sign ← denotes the assignment operation. The result of this transformation, we obtain: W=Hα^{RSH}mod n.

9. Form the second test MDC B:

B=F(W)=W mod δ=(Hα^{U}mod n)mod δ=(Hα^{RSH}mod n)mod δ.

10. Compare (e.g., bitwise) the parameters of the first and second verification numbers A and B.

The coincidence of the values of A and B means that the digital signature is authentic, i.e. it relates to the ED presented MDC H, and formed the signing, which corresponds to the accepted public key (n, α). This is proved in theory and in the following way.
We have In=(Hα^{RSH}mod n)mod δ. Calculate the value of. Then we have:

Since A=R-S=(G+S)-S=G, then A=B.

Example 4. Implementation of the proposed method for making digital signature length of 400 bits.

In this example, as γ and δ use numbers of length 160 bits and 80 bits, respectively, and executes the following sequence of actions.

1. Generate the secret key in the form of a triplet (p, q, γ). Length number γ chosen equal to 160 bits.

2. Generate the public key in the form of a triplet (n, α), where MDC n=pq and α there are a number relating to the index γ modulo n.

4. Take ED presented, for example, the following MDC H (which can be taken, in particular, the hash function from the ED).

5. Form of digital signature in the form of two numbers R and S, which performs the following steps:

5.1. Ask a random number k.

5.2. Ask first additional MDC δ length of 80 bits.

5.3. Calculate the second additional MDC G by the formula

The formula for the formation of the G sets of calculations modulo length 80 bits, so the value of G has a length of 80 bits.

5.4. Form of EDS in the following TLDs are the numbers: and R=S·G. the Formula for the formation of S specifies evaluation module length 160 bits, so the value of S has a length of 160 bits. Element signature R has a length of approximately 240 bits, because it is the product of numbers of length 160 bits and 80 bits. The length of the digital signature is equal to the sum of the lengths of its elements R and S, i.e. the EDS has a length of 400 bits.

6. Form a first test MDC A depending on EDS:

7. Generate intermediate MDC W in accordance with the formula W=α^{U}mod n, where U=RSH.

8. Convert the intermediate MDC W in accordance with the formula W←HW mod n, where the sign ← denotes the assignment operation. The result of this transformation, we obtain: W=Hα^{RSH}mod n.

9. Form the second test MDC B:

B=F(W)=W mod δ=(Hα^{U}mod n)mod δ=(Hα^{RSH}mod n)mod δ.

10. Compare (e.g., bitwise) the parameters of the first and second verification numbers A and B.

The coincidence of the values of A and B means that the digital signature is authentic, i.e. EDS relates to the ED presented MDC H, and was formed signing, which corresponds to the accepted public key (n, α). It is proved theoretically as follows. For digital signature generated with a secret key, we have:

Becausethat is about A=B.

Example 5. Implementation of the proposed method for making digital signature length of 240 bits.

In this example, as γ and β use numbers of length 160 bits and 80 bits, respectively. This example differs from the above that after the formation of the public key to generate the first auxiliary random MDC x and the second auxiliary MDC y that depends on x according to the formula y=α^{x}mod n. In this example performs the following sequence of actions.

1. Generate the secret key in the form of a triplet (p, q, γ), where length is the number of γ chosen equal to 160 bits.

2. Generate the public key in the form of pairs of numbers (n, α).

3. Generate a first auxiliary random MDC x.

4. Generate a second auxiliary MDC y=α^{x}mod n.

5. Take the public key of the signer (n, αand second auxiliary MDC y sent, for example, by the certification authority for telecommunication networks.

6. Take ED presented, for example, the following MDC H (which can be taken, in particular, the hash function from the ED).

7. Form of digital signature in the form of two numbers R and S, which performs the following steps:

7.1. Ask a random number k.

7.2. Ask first additional MDC δ length of 80 bits.

7.3. Calculate the second additional MDC G by the formula

The formula for the formation of the G sets of calculations modulo length 80 bits, so the value of G has a length of 80 bits.

7.4. Form of digital signature in the form of the following two numbers:

R=G and

The formula for the formation of S specifies evaluation module length 160 bits, so the value of S has a length of 160 bits. Element signature R has a length of 80 bits, because MDC G has a length of 80 bits. The length of the digital signature is equal to the sum of the lengths of its elements R and S, i.e. the EDS has a length of 240 bits.

8. Form a first test MDC A depending on EDS:

A=R.

9. Generate intermediate MDC W in accordance with the formula W=α^{U}mod n, where U=RH.

10. Convert the intermediate MDC W in accordance with the formula W←HWy^{S}mod n, where the sign ← denotes the assignment operation. The result of this transformation, we obtain: W=Hα^{RH}y^{S}mod n.

11. Form the second test MDC B:

B=F(W)=W mod δ=(Hα^{RH}y^{S}mod n)mod δ.

12. Compare (e.g., bitwise) the parameters of the first and second verification numbers A and B.

The coincidence of the values of A and B means that the digital signature is authentic, i.e. related to the ED presented MDC H, and formed the signing, which corresponds to the accepted public key. It is proved theoretically as follows. We have:

Since A=G, then A=B.

Example 6. Implementation of the proposed method for making digital signature length of 400 bits.

In this example, as γ and δ use numbers of length 160 bits and 80 bits, respectively. This example (and example 5) reveals the implementation of the proposed method in accordance with claim 8 claims, according to which after the formation of the public key to generate the first auxiliary random MDC x and the second auxiliary MDC y that depends on x according to the formula y=α^{x}mod n. Example 6 executes the following sequence of actions.

1. Generate the secret key in the form of a triplet (p, q, γ), where length is the number of γ chosen equal to 160 bits.

2. Generate the public key in the form of pairs of numbers (n, α).

3. Generate a first auxiliary random MDC x.

4. Generate a second auxiliary MDC y=α^{x}mod n.

5. Take the public key of the signer (n, αand second auxiliary MDC y sent, for example, by the certification authority for telecommunication networks.

6. Take ED presented, for example, the following MDC H (which can be taken, in particular, the hash function from the ED).

7. Form of digital signature in the form of two numbers R and S, which performs the following steps:

7.1. Ask a random number k.

7.2. Ask first additional MDC δ length of 80 bits.

7.3. Vicissitude additional MDC G by the formula

The formula for the formation of the G sets of calculations modulo length 80 bits, so the value of G has a length of 80 bits.

7.4. Form of digital signature in the form of the following two numbers:

and R=GS.

The formula for the formation of S specifies evaluation module length 160 bits, so the value of S has a length of 160 bits. Element signature R has a length of approximately 240 bits, because it is the product of numbers of length 160 bits and 80 bits. The length of the digital signature is equal to the sum of the lengths of its elements R and S, i.e. the EDS has a length of 400 bits.

8. Form a first test MDC A depending on EDS:

9. Generate intermediate MDC W in accordance with the formula W=α^{U}mod n, where U=SH.

10. Convert the intermediate MDC W in accordance with the formula W←Wy^{R}mod n, where the sign ← denotes the assignment operation. The result of this transformation, we obtain: W=α^{SH}y^{R}mod n.

11. By compressing the intermediate conversion MDC W form a second test MDC B:

B=F(W)=W mod δ=(α^{SH}y^{R}mod n)mod δ.

12. Compare (e.g., bitwise) the parameters of the first and second verification numbers A and B.

The coincidence of the values of A and B means that the EDS is podlinnoi, i.e. belongs to the ED presented MDC H, and formed the signer, which are appropriate to esthet adopted public key. It is proved theoretically as follows. For digital signature generated using the correct value of the secret key, we have:

Since A=C, then A=B.

Thus, it is shown that the inventive method can be used as the basis of proof systems EDS, ensure the reduction of the size of the signature in comparison with the known solutions and maintaining the size of the signature with the appearance of new, more efficient algorithms for solving the problem of decomposition of numbers on multipliers and problems of discrete taking the logarithm, i.e. low probability of unauthorized formation of EDS ("false" authentication EDS).

The example and mathematically show that the proposed method for the generation and authentication of digital signature works correctly, technically realistic and allows you to solve the problem.

Appendix 1

Interpretation of terms used in the description of the application

1. Binary digital electromagnetic signal sequence of bits as zeros and ones.

2. Binary options digital electromagnetic signals: capacity and order unit and zero bits.

3. Bit binary digital electromagnetic signal to the total number of unit and zero bits, for example, the number 10011 is a 5-bit.

4. Electronic digital signature (EDS) - binary digital electromagnetic signal whose parameters depend on the signed electronic document and a secret key. Authentication digital signature is performed using a public key, which depends on the secret key.

5. Electronic document (ED) - binary digital electromagnetic signal, the parameters of which depend on a source document and a way of converting it to electronic form.

6. The secret key is a binary digital electromagnetic signal used to generate the signature for a given electronic document. The secret key is represented, for example, in binary form as a series of digits "0" and "1".

7. The public key is a binary digital electromagnetic signal whose parameters depend on the secret key and which is intended to authenticate the digital signature.

8. The hash function from the electronic document is a binary digital electromagnetic signal, the parameters of which depend on the electronic document and the selected method of its calculation.

9. Multibit binary number binary digital electromagnetic signal that is interpreted as a binary number and is represented as a sequence of digits "0" and "1".

10. The operation of the raising number S in a discrete degree of A module is n -
this operation is performed on a finite set of natural numbers {0, 1, 2, ..., n-1}that includes n numbers, which are the remains of the division all kinds of integers on the number n; the operations of addition, subtraction and multiplication modulo n is a number from this set [Vinogradov I.M. fundamentals of theory of numbers. - M.: Nauka, 1972. - 167 S.]; the operation of the raising number S in a discrete degree of Z modulo n is defined as a Z-fold serial multiplication modulo n number of S on itself, i.e. the result of this operation also produces the number W that is less than or equal to the number n-1; even for very large numbers, S, Z and n are efficient algorithms perform construction in a discrete degree modulo [see Moldovyan A. A., Moldovyan N., guts N, Izotov BV Cryptography: speed ciphers. St. Petersburg, BHV-Petersburg, 2002. - p.58-61 or Bsnyen. Applied cryptography. - M., Izd-vo "Triumph", 2002. - s-280] and electronic devices carrying out this operation with great speed [Diffi. The first ten years of public-key cryptography // TIER. 1988. t. No. 5. p.67-68]; the operation of the raising number S in a discrete degree of Z modulo n is denoted as W=S^{Z}mod n, where W is the number resulting from this operation.

11. The Euler function from the natural numbers n is the number of numbers which are relatively Prime and n not exceeding n [Vinogradov I.M. Fundamentals of theory of numbers. - M.: Nauka, 1972. - 167 C.; Buchstab A.A. theory of numbers. - M.: Education, 1966. - 384 p].

12. The index of q modulo n number a, which is relatively Prime to n is the minimum of the numbers γfor which the condition α^{γ}mod n=1, i.e. q=min {γ_{1}that γ_{2}, ...} [Vinogradov I.M. fundamentals of theory of numbers. - M.: Nauka, 1972. - 167 C.].

13. A primitive root is a number related to the metric, which is equal to the Euler function from the module.

14. Inverse element modulo n to the number of αmutually Prime with n, there is a natural number, denoted as α^{-1}for which the condition α^{-1}α=1; for any number of mutually Prime with the module, there is an element of the inverse of this number. Known efficient algorithms for computing the inverse elements [Y. Romanets, Timofeev P.A., Shangin V.F. Protection of information in computer systems and networks. - M, Radio and communications. - s - 310].

15. The operation of integer division And integer modulo n is performed as the operation of multiplication modulo n integers And an integer In^{-1}that is inverse to a In modulo n.

1. Method of forming and authentication of digital signature verifying an electronic document, namely, that form the secret key that includes three multi-bit dvoc who's number, R, q and γwhere p, q are Prime numbers and γ composite number, form a public key that includes two multibit binary numbers n and αwhere α number related to the metric γ modulo n and n=pq, accept an electronic document presents a multi-bit binary number N, depending on the values of N and values of the secret key to form a digital signature Q, form first and second test multiple-bit binary numbers a and b, and compare them with the alignment settings can make a conclusion about the authenticity of a digital signature, wherein the digital signature form Q in the form of two multibit binary numbers R and S, i.e. Q=(R,S)form the first test multibit binary number And depending on electronic digital signature, generate intermediate multi-bit binary number W depending on the values of the multibit binary numbers R, S, H, n and α and forming a second test multi-bit binary number by a compressive conversion of the intermediate multi-bit binary numbers W.

2. The method according to claim 1, characterized in that the first test multi-bit binary number And is formed by subtracting from the value of R.

3. The method according to claim 1, characterized in that the first test multibit binary number And formed the comfort by dividing the value of R is S.

4. The method according to claim 1, characterized in that the first test multi-bit binary number And is formed by the multiplication of the values of S and R.

5. The method according to claim 1, characterized in that the first test multi-bit binary number And is formed by adding the values of S and R.

6. The method according to claim 1, characterized in that the intermediate multi-bit binary number W generated by the operation of the raising number α the degree of U modulo n, where U is a multi-bit binary number, which is calculated by the formula U=RS or by the formula U=RSH.

7. The method according to claim 1, characterized in that the intermediate multi-bit binary number W generated by the operation of the raising number α the degree of U modulo n, where U is a multi-bit binary number, which is calculated by the formula U=RS or by the formula U=RSH, then the received intermediate multi-bit binary number W additionally transform according to the formula W←WH mod n or the formula W←(W+H)mod n, where the sign ← denotes the assignment operation.

8. The method according to claim 1, characterized in that the intermediate multi-bit binary number W generated by the operation of the raising number α the degree of U modulo n, where U is a multi-bit binary number, which is calculated by the formula U=RS or by the formula U=RSH, and then optionally convert the intermediate many who bit binary number W by the formula W←
Wy^{S}mod n or the formula W←Wy^{RH}mod n, where the sign ← denotes the assignment operation, y=α^{x}mod n and x - additional random multi-bit binary number.

9. The method according to claim 1, characterized in that the compressive transformation of the intermediate multi-bit binary number W is performed by using a hash function.

10. The method according to claim 1, characterized in that the compressive transformation of the intermediate multi-bit binary number W is carried out by means of the operation of taking the remainder of the intermediate multi-bit binary numbers W for a Prime number δwhose length is in the range from 64 to 256 bits.

**Same patents:**

FIELD: digital rights control system.

SUBSTANCE: system contains first user device designed for query message setup and transfer, indicating transaction to be run in relation to digital content of at least one object of digital rights (OR), rights issuer aimed to receive query message from first user device, to identify transaction and to process this transaction and to provide access rights to digital content conjointly with server for second user device designed to receive information on stated access right concession. Receive of mentioned information by second user device on digital content access right concession is confirmation of execution of this right to second user device. Method describes operation of mentioned system.

EFFECT: ability of authorized user to transfer partially used or unused object of right to another user and return of OR.

49 cl, 15 dwg, 2 tbl

FIELD: portable electronic devices.

SUBSTANCE: portable electronic device includes memory to store a secret code in the form of pre-defined character sequence; rotating device with touch surface providing for user tactile impact and installed in such a manner as to provide for rotation around its axis; feedback tools separated from the rotating device to provide for feedback to user when turning the rotating device; conversion tool to convert each turn in sequence of turns of the rotating device to a character of corresponding ordered test character sequence, and verification tool to verify the test character sequence by comparing it with pre-defined character sequence.

EFFECT: user convenience during input of test character sequence along with provision of security and restriction of access to the device or to its individual functions.

33 cl, 7 dwg

FIELD: cryptography.

SUBSTANCE: in accordance to the method, cryptographic module is provided with two types of data, which may be received even from a communication partner who is not cryptographically reliable, and which either remain in cryptographic module, or are connected to the document. The information, which remains in cryptographic module, is used to protect the information in the document by generation of a check value, and information which is transferred to document, is used to confirm the fact that the document is protected by a cryptographic module, during the check of document authenticity in a control device.

EFFECT: the contact between cryptographically reliable contact device and document creator is realized directly.

2 cl, 3 dwg

FIELD: infrastructure of public keys (PKI), namely, registration and activation of PKI functions in infrastructures of public keys in SIM-cards.

SUBSTANCE: in accordance to the method, reference code and corresponding activation code are recorded in a table at protection server integrated in PKI or connected to PKI. The user inputs reference code or number in record form together with his personal data, after that the form is sent to PKI and to protection server. After registration is confirmed from the side of PKI, the confirmation information is transmitted to user and supplemented with a request to input activation code at user terminal. Simultaneously, the activation code associated with reference code in the table and identification data of smart-card of user are transmitted to activation module in PKI, then activation code together with identification data of smart-card is transmitted from terminal to activation module and on receipt thereof the activation module determines whether the data coincides with activation code and identification data, provided in advance by protection server, and in case they do, the module performs command of activation of PKI-component of smart-card.

EFFECT: reduced processing time.

13 cl

FIELD: methods and system for processing visualized digital information.

SUBSTANCE: the system for protecting visualized digital data contains a set of computing devices, where at least one of them is the main device, and at least another one is a remote computing device, where each one of aforementioned devices contains one or more processing components, configured for usage in data processing chain, consisting of components for processing protected information, subject to visualization for user, individual processing components which support one or more of such interfaces, such as authentication interface and intermediary authentication interface, where the intermediary authentication interface ensures reading of authentication identifiers and recording of authentication identifiers, and authentication identifier uses for each one of one or more lists for checking each component in each one of aforementioned one or more lists, to determine authorized components, where an authorized component may receive non-encrypted data. Methods describe operation of the system.

EFFECT: protection from unsanctioned access or duplication of unprotected information immediately after that information reaches visualization device, such as a user computer.

20 cl, 8 dwg

FIELD: online transactions.

SUBSTANCE: method for conducting an online transaction includes providing a transaction manager. Single use transaction request identification is generated, transaction manager compares transaction request identification to banking information of registered user. Registered user is provided with transaction request identification, registered user requests purchase of product or service from a merchant, where purchase requests includes providing transaction request identification to the merchant. The merchant dispatches a request to transaction manager for payment by money transfer from user to merchant, where payment request includes identification of transaction request and cost; check by transaction manager of trustworthiness of transaction request identification; and, if transaction request information is trustworthy, request for electronic transfer of money is dispatched to financial institution to transfer a sum of money from user account to another account; it is checked, whether sufficient sum of money is available on banking account of user, and, if sufficient amount is available, the financial institution conducts the transfer according to banking information; and transaction manager receives confirmation about transaction from financial institution and dispatches a confirmation to the merchant.

EFFECT: increased efficiency.

5 cl, 16 dwg

FIELD: protocols for interaction of peer entities of network structure and, in particular, concerns protective infrastructures for protocols of interaction of peer entities.

SUBSTANCE: methods are provided, which suppress capability of malicious node to disrupt normal operation of peer-to-peer network. Claimed methods allow nodes to use both protected and unprotected data about identity, ensuring self-check thereof. Then necessary or comfortable, association of ID is checked by "enclosing" a trustworthiness checking procedure into appropriate messages. Probability of connection to malicious node is initially reduced due to random selection of node with which connection is established. Also, information from malicious nodes is identified and may be discarded by recording information about previous connections, which will require a response in the future.

EFFECT: creation of protection infrastructure for a system with peer-to-peer network structure.

4 cl, 6 dwg

FIELD: communications engineering, possible use for checking protection of message (Msg), which is transmitted and received in electronic form.

SUBSTANCE: in accordance to the invention method contains stages at transmitting side, at which unambiguous message identifier is associated with message (ID_{Msg}) and control identifier (ID_{CONTR}) of identification code of message owner, which is received by applying encoding (12), connected to owner of transmitted message, to unambiguous message identifier (ID_{Msg}). At receiving side method contains stages, at which fact of presence or absence of already received message with the same associated unambiguous message identifier (ID_{Msg}) is checked and transmitted by means of signal, and match is determined between unambiguous message identifier (ID_{Msg}), associated with received message, and result (ID_{DCONTR}) of decoding of user name of control (ID_{CONTR}).

EFFECT: ensured control of protection of message which is transmitted and received in electronic form.

3 cl, 3 dwg

FIELD: computer networks.

SUBSTANCE: in accordance to the invention, in home computer network, formed with presence of controlling devices and control station, device for notifying control station about operation state of digital rights management relatively to control device includes: DRM module, which executes digital rights management; module for generating status variables, which receives information about operation condition of DRM from DRM module, which indicates condition of current active DRM process, and on basis of received DRM status information generates DRM status variables; and module for universal detection and auto-adjustment of devices (uPnP), which, using uPnP protocol, transmits generated status variables to control station.

EFFECT: recognition of operation state of digital rights management (DRM) process in DRM system, which uses universal protocol (uPnP) for recognition and auto-adjustment of devices.

2 cl, 7 dwg

FIELD: engineering of systems for protecting communication channels, which realize claimed method for user authentication on basis of biometric data by means of provision and extraction of cryptographic key and user authentication.

SUBSTANCE: in accordance to the invention, neither biometric template nor cryptographic user key are explicitly represented in information storage device, without provision of biometric sample and information storage device with a pack stored on it, any cryptographic operations with data are impossible.

EFFECT: creation of biometric access system and method for provision/extraction of cryptographic key and user authentication on basis of biometry, increased key secrecy level, increased reliability, expanded functional capabilities and simplified system creation process.

2 cl, 2 dwg

FIELD: information protection.

SUBSTANCE: method for transferring messages while providing for confidentiality of identification signs of communication system objects with interaction of devices of communication system subscribers through central device for each communication session cryptographic conversion of subscriber device identifier is performed using encryption key of current subscriber device, while during said cryptographic conversion symmetrical cryptographic algorithm is used and two message transfer modes are taken in consideration, on initiative from subscriber device to central device and vice versa.

EFFECT: protection from unsanctioned access to identifiers of devices of system subscribers transferred via communication channels, in particular when providing for confidentiality of messages identification signs in communications systems with multiple subscriber devices.

6 dwg

FIELD: computer science.

SUBSTANCE: previously for sender and receiver a binary series of digital watermark k-bit long is formed as well as binary series of secret key, message is certified at sender side using binary series of digital watermark and secret key, certified message is sent to receiver, where authenticity of received message is checked using binary series of digital watermark and secret key.

EFFECT: higher reliability, higher efficiency.

4 cl, 5 dwg

FIELD: mobile communications.

SUBSTANCE: server generates one-time activation code, sends it to user via intellectual card in cell phone and when user inputs an activation code in his cell phone, inputted code is transmitted to server for verification, in case of positive result server sends a command to phone to provide for access, which opens access to appropriate set of functions of intellectual card, while portion of functions can contain, for example, PKI-functions, which were concealed and inaccessible for user until said moment, after that user can select his own PIN-code for authentication, encoding and signature for transactions, and, concerning activation of PKI functions, generation of necessary secret and open keys, and also necessary certification are carried out after verification of activation code.

EFFECT: higher efficiency, broader functional capabilities.

1 cl, 1 dwg

FIELD: computer science.

SUBSTANCE: system has center of certification, forming and distribution of keys, at least one user device and at least one distributed data processing server. Method describes operation of said system. Subsystem for forming open keys contains memory block for tables of secret substitutions of columns and rows of secret keys tables, memory block for table of symmetric substitution of columns and rows of external key table, register for sequence of transitive connection between rows of secret substitutions tables, block for logical output on sequence of transitive dependence, memory block for table of relative non-secret substitution of columns and rows of external key table, open key register, input commutation block and control block.

EFFECT: higher efficiency, broader functional capabilities.

5 cl, 15 dwg

FIELD: mobile communications.

SUBSTANCE: protection means has key module and blocking module. Mobile communication system has protection means and communication port. Method describes operation of said protection means and mobile device.

EFFECT: broader functional capabilities.

3 cl, 5 dwg

FIELD: electrical communications.

SUBSTANCE: proposed method that can be used in attack detection systems for on-line detection and blocking of unauthorized attacks in computer systems including Internet involves presetting of list of authorized connections as aggregate of reference connection identifiers, introduction of factor of urgency of reference authorized-connection identifiers and list of names of authorized processes, generation of list of unauthorized connections received in the course of checkup due to introduction of maximal admissible quantity of any of probable unauthorized connections, and their counting.

EFFECT: enhanced reliability of identifying unauthorized attacks in computer networks.

1 cl, 8 dwg

FIELD: systems and method for controlling transfer of keys for decoding or access to encoded information.

SUBSTANCE: each one of variants of information protection systems for controlling access to protected information has hardware means for storing at least one data element, including decoding key and appropriate information protection code, while information protection code sets number of operations of passage of decoding key, and first user, connected to encoded information, can determine through information protection code, whether second user can transfer code for information protection to third user, while number of generation of data is requested each time after receipt of query for transferring decoding key to another user and is decreased for one unit for each request, and as soon as it reaches zero, system denies all further requests.

EFFECT: improved level of information protection.

3 cl, 6 dwg

FIELD: engineering of object access means.

SUBSTANCE: device has saved standard, containing fingerprint of authorized user, combined with verification code. In case of match between fingerprint of authorized user with one stored in memory, verification code if generated. Device activated by key periodically transmits an identifier, on receipt by access device of identifier, matching one of identifiers stored in memory, appropriate access key is extracted and sent to device activated by key to allow access to user.

EFFECT: high level of protection from unauthorized access.

3 cl, 2 dwg

FIELD: radio engineering, in particular, authentication method for stationary regional wireless broadband access systems, possible use, for example, for protecting transferred data in stationary regional broadband access systems.

SUBSTANCE: in accordance to method, two main procedures are performed - authentication of client station and, also, authentication of base station.

EFFECT: increased protection level of transmitted data in stationary wireless broadband access systems.

4 cl, 6 dwg

FIELD: technology for checking authentication and authorization.

SUBSTANCE: method for checking rights of user of end telecommunication device for using a service, while device for accessing telecommunication network receives at least one certificate and identification data from telecommunication end device, after that network control device together with certification device checks, whether certificate, confirming identification data, is valid and whether it has positive status, whether additional privileges are given by additional certificates, and if that is so, then secret data is transferred to access device (session key), which are also transferred to telecommunication end device in form, encrypted by at least an open key, and access device provides free access by taking a decision, appropriate for rights of user of telecommunication network.

EFFECT: simple and efficient authentication and authorization of users for certain services or transactions, performed via telecommunication network.

11 cl, 1 dwg