idnits 2.17.1 draft-dolmatov-cryptocom-gost34102001-08.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** The document seems to lack a License Notice according IETF Trust Provisions of 28 Dec 2009, Section 6.b.ii or Provisions of 12 Sep 2009 Section 6.b -- however, there's a paragraph with a matching beginning. Boilerplate error? (You're using the IETF Trust Provisions' Section 6.b License Notice from 12 Feb 2009 rather than one of the newer Notices. See https://trustee.ietf.org/license-info/.) -- The document has an IETF Trust Provisions (28 Dec 2009) Section 6.c(i) Publication Limitation clause. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (December 21, 2009) is 5233 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Missing Reference: 'Electronic' is mentioned on line 227, but not defined == Missing Reference: '255' is mentioned on line 514, but not defined == Missing Reference: '0' is mentioned on line 514, but not defined == Missing Reference: 'C' is mentioned on line 819, but not defined == Unused Reference: 'GOST3410' is defined on line 871, but no explicit reference was found in the text == Unused Reference: '4' is defined on line 898, but no explicit reference was found in the text == Unused Reference: '5' is defined on line 902, but no explicit reference was found in the text == Unused Reference: '7' is defined on line 909, but no explicit reference was found in the text == Unused Reference: '8' is defined on line 913, but no explicit reference was found in the text == Unused Reference: '9' is defined on line 916, but no explicit reference was found in the text Summary: 1 error (**), 0 flaws (~~), 11 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Internet-Draft V. Dolmatov, Ed. 2 Intended status: Informational Cryptocom Ltd. 3 Expires: June 21, 2010 December 21, 2009 5 GOST R 34.10-2001 6 digital signature algorithm 7 draft-dolmatov-cryptocom-gost34102001-08 9 Status of This Memo 11 This Internet-Draft is submitted to IETF in full conformance with the 12 provisions of BCP 78 and BCP 79. 14 Internet-Drafts are working documents of the Internet Engineering 15 Task Force (IETF), its areas, and its working groups. Note that 16 other groups may also distribute working documents as Internet- 17 Drafts. 19 Internet-Drafts are draft documents valid for a maximum of six months 20 and may be updated, replaced, or obsoleted by other documents at any 21 time. It is inappropriate to use Internet-Drafts as reference 22 material or to cite them other than as "work in progress." 24 The list of current Internet-Drafts can be accessed at 25 http://www.ietf.org/ietf/1id-abstracts.txt. 27 The list of Internet-Draft Shadow Directories can be accessed at 28 http://www.ietf.org/shadow.html. 30 This Internet-Draft will expire on June 21, 2010. 32 Copyright Notice 34 Copyright (c) 2009 IETF Trust and the persons identified as the 35 document authors. All rights reserved. 37 This document is subject to BCP 78 and the IETF Trust's Legal 38 Provisions Relating to IETF Documents in effect on the date of 39 publication of this document (http://trustee.ietf.org/license-info). 40 Please review these documents carefully, as they describe your rights 41 and restrictions with respect to this document. 43 This document may not be modified, and derivative works of it may 44 not be created, except to format it for publication as an RFC or to 45 translate it into languages other than English. 47 Abstract 49 This document is intended to be a source of information about the 50 Russian Federal standard for digital signatures (GOST R 34.10-2001), 51 which is one of the Russian cryptographic standard algorithms (called 52 GOST algorithms). Recently, Russian cryptography is being used in 53 Internet applications, and this document has been created as 54 as information for developers and users of GOST R 34.10-2001 for 55 digital signature generation and verification. 57 Table of Contents 59 1. Introduction.....................................................2 60 1.1. General information.........................................2 61 1.2. The purpose of GOST R 34.10-2001............................3 62 2. Applicability....................................................3 63 3. Definitions and notations........................................3 64 3.1. Definitions.................................................3 65 3.2. Notations...................................................5 66 4. General statements...............................................6 67 5. Mathematical conventions.........................................7 68 5.1. Mathematical definitions....................................7 69 5.2. Digital signature parameters................................9 70 5.3. Binary vectors.............................................10 71 6. Main processes..................................................10 72 6.1. Digital signature generation process.......................11 73 6.2. Digital signature verification.............................11 74 7. Test examples (Appendix B to GOST R 34.10-2001).................13 75 7.1. The digital signature scheme parameters....................13 76 7.2. Digital signature process (Algorithm I)....................15 77 7.3. Verification process of digital signature (Algorithm II)...16 78 8. Security considerations.........................................17 79 9. IANA considerations.............................................17 80 10. Normative references...........................................18 81 11. Informative references.........................................18 83 1. Introduction 85 1.1. General information 87 1. GOST R 34.10-2001 was developed by the Federal Agency for 88 Government Communication and Information under the President of 89 Russian Federation with participation of the All-Russia Scientific 90 and Research Institute of Standardization. 92 GOST R 34.10-2001 was submitted by Federal Agency for Government 93 Communication and Information at President of Russian Federation. 95 2. GOST R 34.10-2001 was accepted and activated by the Act 380-st of 96 12.09.2001 issued by the Russian federal committee for standards. 98 3. GOST R 34.10-2001 was developed in accordance with terminology and 99 concepts of international standards ISO 2382-2-76. "Data processing. 100 Dictionary. Part 2. Arithmetic and logic operations", ISO/IEC 9796-91 101 "Information technology. Secure methods. Digital signature scheme 102 with message recovering", series ISO/ IEC 14888 "Information 103 technology. Secure methods. Digital signatures and application" and 104 series ISO/ IEC 10118 "Information technology. Secure methods. Hash 105 functions" 107 4. GOST R 34.10-2001 replaces GOST R 34.10-94. 109 1.2. The purpose of GOST R 34.10-2001 111 GOST R 34.10-2001 describes generation and verification processes for 112 digital signature, based on operations with elliptic curve points 113 group, defined over prime finite field. 115 GOST R 34.10-2001 is developed to replace GOST R 34.10-94. Necessity 116 for this development is caused by the need to increase the digital 117 signature security against unauthorized modification. Digital 118 signature security is based on complexity of discrete logarithm 119 calculation in elliptic curve points group and also on the security 120 of the hash function used (according to [GOST3411]). 122 Terminologically and conceptually GOST R 34.10-2001 is in accord with 123 international standards ISO 2382-2 [1], ISO/ IEC 9796 [2], series 124 ISO/ IEC 14888 [3]-[5] and series ISO/ IEC 10118 [6]-[9]. 126 Note: the main part of GOST R 34.10-2001 is supplemented with two 127 appendixes: 129 extra terms in digital signature area (Appendix A to this memo); 131 test examples (section 7 of this memo); 133 a bibliography in digital signature area (section 12 of this memo). 135 2. Applicability 137 GOST R 34.10-2001 defines an electronic digital signature (or simply 138 digital signature) scheme, digital signature generation and 139 verification processes for a given message (document), meant for 140 transmission via insecure public telecommunication channels in data 141 processing systems of different purposes. 143 Use of digital signature based on GOST R 34.10-2001 makes transmitted 144 messages more resistant to forgery and loss of integrity, in 145 comparison with digital signature scheme prescribed by the previous 146 standard. 148 GOST R 34.10-2001 is obligatory to use in Russian Federation in all 149 data processing systems providing public services. 151 3. Definitions and notations 153 3.1. Definitions 155 The following terms are used in the standard: 157 3.1.1 Appendix: Bit string, formed by digital signature and by 158 arbitrary text field (ISO/IEC 148881-1 [3]). 160 3.1.2 Signature key: Element of secret data, specific to the subject 161 and used only by this subject during the signature generation process 162 (ISO/IEC 14888-1 [3]). 164 3.1.3 Verification key: Element of data mathematically linked to the 165 signature key data element, used by the verifier during the digital 166 signature verification process (ISO/IEC 14888-1 [3]). 168 3.1.4 Domain parameter: Element of data which is common for all the 169 subjects of the digital signature scheme, known or accessible to all 170 the subjects (ISO/IEC 14888-1 [3]). 172 3.1.5 Signed message: A set of data elements, that consists of the 173 message and the appendix, which is a part of the message. 175 3.1.6 Pseudo-random number sequence: A sequence of numbers, which is 176 obtained during some arithmetic (calculation) process, used in 177 specific case instead of a true random number sequence (ISO 2382-2 178 [1]). 180 3.1.7 Random number sequence: A sequence of numbers none of which can 181 be predicted (calculated) using only the preceding numbers of the 182 same sequence (ISO 2382-2 [1]). 184 3.1.8 Verification process: A process using the signed message, the 185 verification key and digital signature scheme parameters as initial 186 data and giving the conclusion about digital signature validity or 187 invalidity as a result. (ISO/IEC 14888-1 [3]). 189 3.1.9 Signature generation process: A process using the message, the 190 signature key and digital signature scheme parameters as initial data 191 and generating the digital signature as the result (ISO/IEC 14888-1 192 [3]). 194 3.1.10 Witness: Element of data (resulting from the verification 195 process) which states to the verifier whether digital signature is 196 valid or invalid (ISO/IEC 148881-1 [3]). 198 3.1.11 Random number: A number chosen from the definite number set in 199 such a way that every number from the set can be chosen with 200 equal probability (ISO 2382-2 [1]). 202 3.1.12 Message: String of bits of a limited length (ISO/IEC 9796 203 [2]). 205 3.1.13 Hash code: String of bits that is a result of the hash 206 function (ISO/IEC 148881-1 [3]). 208 3.1.14 Hash function: The function, mapping bit strings onto bit 209 strings of fixed length observing the following properties: 211 1) it is difficult to calculate the input data, that is the 212 pre-image of the given function value; 214 2) it is difficult to find another input data that is the 215 pre-image of the same function value as is the given input data; 216 3) it is difficult to find a pair of different input data, 217 producing the same hash function value. 219 Note: The property 1 in the context of the digital signature area 220 means that it is impossible to recover the initial message using the 221 digital signature; property 2 means that it is difficult to find 222 another (falsificated) message that produces the same digital 223 signature as a given message; property 3 means that it is difficult 224 to find some pair of different messages, that both produce the same 225 signature. 227 3.1.15 [Electronic] Digital signature: String of bits obtained as a 228 result of signature generation process. This string has an internal 229 structure, depending on the specific signature generation mechanism. 231 Note: In GOST R 34.10-2001 terms "Digital signature" and "Electronic 232 sigital signature" are synonymous to save terminological succession 233 to native legal documents currently in force and scientific 234 publications. 236 3.2 Notations 238 In GOST R 34.10-2001 the following notations are used: 240 V256 - set of all binary vectors of length 256 bit; 242 V_all - set of all binary vectors of an arbitrary finite 243 length; 245 Z - set of all integers; 247 p - prime number, p > 3; 249 GF(p) - finite prime field represented by a set of integers 250 {0, 1, ..., p - 1}; 252 b (mod p) - minimal nonnegative number, congruent to b modulo p; 254 M - user's message, M belongs to V_all; 256 (H1 || H2 ) - concatenation of two binary vectors; 258 a,b - elliptic curve coefficients; 260 m - points of the elliptic curve group order; 262 q - subgroup order of group of points of the elliptic curve; 264 O - zero point of the elliptic curve; 266 P - elliptic curve point of order q; 268 d - integer - a signature key; 270 Q - elliptic curve point - a verification key; 271 ^ - the power operator; 273 /= - non-equality; 275 sqrt - square root; 277 zeta - digital signature for the message M. 279 4. GENERAL STATEMENTS 281 A commonly accepted digital signature scheme (model) (see 6 ISO/IEC 282 14888-1 [3]) consists of three processes: 284 - generation of a pair of keys (for signature generation and for 285 signature verification); 287 - signature generation; 289 - signature verification. 291 In GOST R 34.10-2001 a process for generating a pair of keys (for 292 signature and verification) is not defined. Characteristics and ways 293 of the process realization are defined by involved subjects, who 294 determine corresponding parameters by their agreement. 296 The digital signature mechanism is defined by realization of two main 297 processes (see part 7): 299 - signature generation (see. 6.1); 301 - signature verification (see. 6.2). 303 The digital signature is meant for authentication of the signatory of 304 the electronic message. Besides, the digital signature usage gives an 305 opportunity to provide the following properties during signed message 306 transmission: 308 - realization of control of the transmitted signed message 309 integrity, 311 - proof of the authorship of the signatory of the message, 313 - protection of the message against possible forgery. 315 A schematic representation of the signed message is shown in the 316 figure 1. 317 appendix 318 | 319 +-------------------------------+ 320 | | 321 +-----------+ +------------------------+- - - + 322 | message M |---| digital signature zeta | text | 323 +-----------+ +------------------------+- - - + 325 Figure 1 - Signed message scheme 326 The field "digital signature" is supplemented by the field "text" 327 (see figure 1), that can contain for example identifiers of the 328 signatory of the message, and/or time label. 330 The digital signature scheme determined in GOST R 34.10-2001 must be 331 implemented using operations of elliptic curve points group, defined 332 over a finite prime field, and also with the use of hash function. 334 The cryptographic security of the digital signature scheme is based 335 on complexity of solving the problem of calculation the discrete 336 logarithm in elliptic curve points group, and also on the security of 337 the hash function used. The hash function calculation algorithm is 338 determined in [GOST3411]. 340 The digital signature scheme parameters needed for signature 341 generation and verification are determined in 5.2. 343 GOST R 34.10-2001 does not determine the process of generating 344 parameters needed for digital signature scheme. Possible sets of 345 these parameters are defined for example in [RFC4357]. 347 The digital signature represented as a binary vector of length 512 348 bit, must be calculated using definite set of rules stated in 6.1. 350 The digital signature of the received message is accepted or denied 351 in accordance with the set of rules, stated in 6.2. 353 5. Mathematical conventions 355 To define a digital signature scheme it is necessary to describe 356 basic mathematical objects, used in the signature generation and 357 verification processes. This section lays out basic mathematical 358 definitions and requirements for the parameters of the digital 359 signature scheme. 361 5.1 Mathematical definitions 363 Suppose a prime number p > 3 is given. Then an elliptic curve E, 364 defined over a finite prime field GF(p), is the set of number pairs 365 (x,y), x, y belong to Fp , satisfying the identity 367 y^2 = x^3 + a*x + b (mod p), (1) 369 where a, b belong to GF(p) and 4*a^3 + 27*b^2 is not congruent to 370 zero modulo p. 372 An invariant of the elliptic curve is the value J(E) satisfying the 373 equality 375 4*a^3 376 J(E) = 1728 * ------------ (mod p) (2) 377 4*a^3+27*b^2 378 Elliptic curve E coefficients a,b are defined in the following way 379 using the invariant J(E): 381 | a=3*k (mod p) 382 | J(E) 383 | b=2*k (mod p), where k = ----------- (mod p), J(E) /= 0 or 1728 (3) 384 1728 - J(E) 386 The pairs (x,y) satisfying the identity (1) are called the elliptic 387 curve E points, x and y are called x- and y-coordinates of the point 388 correspondingly. 390 We will denote elliptic curve points as Q(x,y) or just Q. Two 391 elliptic curve points are equal if their x- and y-coordinates are 392 equal. 394 On the set of all elliptic curve E points we will define the addition 395 operation, denoted by "+". For two arbitrary elliptic curve E points 396 Q1 (x1, y1) and Q2 (x2, y2) we will consider several variants. 398 Suppose coordinates of points Q1 and Q2 satisfy the condition x1 /= 399 x2. In this case their sum is defined as a point Q3 (x3,y3) with 400 coordinates defined by congruences 402 | x3=lambda^2-x1-x2 (mod p), y1-y2 403 | where lambda= ------- (mod p). (4) 404 | y3=lambda*(x1-x3)-y1 (mod p), x1-x2 406 If x1 = x2 and y1 = y2 /= 0, then we will define point Q3 407 coordinates in a following way 409 | x3=lambda^2-x1*2 (mod p), 3*x1^2+a 410 | where lambda= --------- (mod p) (5) 411 | y3=lambda*(x1-x3)-y1 (mod p), y1*2 413 If x1 = x2 and y1 = - y2 (mod p), then the sum of points Q1 and Q2 414 is called a zero point O, without determination of its x- and 415 y-coordinates. In this case point Q2 is called a negative of point 416 Q1. For the zero point the equalities hold 418 O+Q=Q+O=Q, (6) 419 where Q is an arbitrary point of elliptic curve E. 421 A set of all points of elliptic curve E including zero point forms a 422 finite abelian (commutative) group of order m regarding introduced 423 addition operation. For m the following unequalities hold: 425 p + 1 - 2*sqrt(p) =< m =< p + 1 + 2*sqrt(p). (7) 427 The point Q is called a point of multiplicity k, or just a multiple 428 point of the elliptic curve E, if for some point P the following 429 equality holds: 431 Q = P + ... + P = k*P. (8) 432 -----+----- 433 k 435 5.2 Digital signature parameters 437 The digital signature parameters are: 439 - prime number p is an elliptic curve modulus, satisfying the 440 inequality p > 2^255. The upper bound for this number must be 441 determined for specific realization of digital signature 442 scheme; 444 - elliptic curve E, defined by its invariant J(E) or by 445 coefficients a, b belonging to GF(p). 447 - integer m is an elliptic curve E points group order; 449 - prime number q is an order of a cyclic subgroup of the 450 elliptic curve E points group, which satisfies the following 451 conditions: 453 | m = nq, n belongs to Z , n>=1 454 | ; (9) 455 | 2^254 < q < 2^256 457 - point P /= O of an elliptic curve E, with coordinates 458 (x_p, y_p), satisfying the equality q*P=O. 460 - hash function h(.):V_all -> V256, which maps the messages 461 represented as binary vectors of arbitrary finite length onto 462 binary vectors of length 256 bit. The hash function is 463 determined in [GOST3411]. 465 Every user of the digital signature scheme must have its personal 466 keys: 468 - signature key, which is an integer d, satisfying the 469 inequality 0 < d < q; 471 - verification key, which is an elliptic curve point Q with 472 coordinates (x_q, y_q), satisfying the equality d*P=Q. 474 The previously introduced digital signature parameters must satisfy 475 the following requirements: 477 - it is necessary that the condition p^t/= 1 (mod q ) holds for 478 all integers t = 1, 2, ... B where B satisfies the inequality 479 B >= 31; 481 - it is necessary that the inequality m /= p holds; 483 - the curve invariant must satisfy the condition 484 J(E) /= 0, 1728. 486 5.3 Binary vectors 488 To determine the digital signature generation and verification 489 processes it is necessary to map the set of integers onto the set of 490 binary vectors of length 256 bit. 492 Consider the following binary vector of length 256 bit where 493 low-order bits are placed on the right, and high-order ones are 494 placed on the left 496 H = (alpha[255], ... , alpha[0]), H belongs to V256 (10) 498 where alpha[i], i = 0, ... , 255 are equal to 1 or to 0. We will say 499 that the number alpha belonging to Z is mapped onto the binary vector 500 h, if the equality holds 502 alpha = alpha[0]*2^0 + alpha[1]*2^1 + ... + alpha[255]*2^255. (11) 504 For two binary vectors H1 and H2 , which correspond to integers alpha 505 and beta, we define a concatenation (union) operation in the 506 following way. Let 508 H1 = (alpha[255], ... , alpha[0]), 509 (12) 510 H2 = (beta[255], ..., beta[0]), 512 then their union is 514 H1||H2 = (alpha[255], ... , alpha[0], beta[255], ..., beta[0]) 515 (13) 516 that is a binary vector of length 512 bit, consisting of coefficients 517 of the vectors H1 and H2. 519 On the other hand, the introduced formulae define a way to divide a 520 binary vector H of length 512 bit into two binary vectors of length 521 256 bit, where H is the concatenation of the two. 523 6. Main processes 525 In this section the digital signature generation and verification 526 processes of user's message are defined. 528 For the realization of the processes it is necessary, that all users 529 know the digital signature scheme parameters, which satisfy the 530 requirements of section 5.2. 532 Besides, every user must have the signature key d and the 533 verification key Q(x[q], y[q]) , which also must satisfy the 534 requirements of section 5.2. 536 6.1 Digital signature generation process 538 It is necessary to perform the following actions (steps) according to 539 Algorithm I to obtain the digital signature for the message M 540 belonging to V_all: 542 Step 1 - calculate the message hash code M: H = h(M). (14) 544 Step 2 - calculate an integer alpha, binary representation of which 546 is the vector H , and determine e = alpha (mod q ) . (15) 548 If e = 0, then assign e = 1. 550 Step 3 - generate a random (pseudorandom) integer k, satisfying the 551 inequality 553 0 < k < q. (16) 555 Step 4 - calculate the elliptic curve point C = k*P and determine 557 r = x_C (mod q), (17) 559 where x_C is x-coordinate of the point C. If r = 0, return to step 3. 561 Step 5 - calculate the value 563 s = (r*d + k*e) (mod q). (18) 565 If s = 0, return to step 3. 567 Step 6 - calculate the binary vectors R and S , corresponding to r 569 and s, and determine the digital signature zeta = (R || S) as 570 concatenation of these two binary vectors. 572 The initial data of this process are the signature key d and the 573 message M to be signed. The output result is the digital signature 574 zeta. 576 6.2 Digital signature verification 578 To verify digital signature for the received message M belonging to 579 V_all it is necessary to perform the following actions (steps) 580 according to Algorithm II: 582 Step 1 - calculate the integers r and s using the received signature 583 zeta. If the inequalities 0 < r < q, 0 < s < q hold, go to the next 584 step. In the other case the signature is invalid. 586 Step 2 - calculate the hash code of the received message M 588 H = h(M). (19) 590 Step 3 - calculate the integer alpha, the binary representation of 592 which is the vector H , and determine 594 e = alpha (mod q). (20) 596 If e = 0, then assign e = 1. 598 Step 4 - calculate the value v = e^(-1) (mod q) . (21) 600 Step 5 - calculate the values 602 z1 = s*v (mod q), z2 = -r*v (mod q). (22) 604 Step 6 - calculate the elliptic curve point C = z1*P + z2*Q and 605 determine 607 R = x_C (mod q), (23) 609 where x_C is x-coordinate of the point . 611 Step 7 - if the equality R = r holds, than the signature is accepted, 612 in the other case the signature is invalid. 614 The input data of the process are the signed message M, the digital 615 signature zeta and the verification key Q. The output result is the 616 witness of the signature validity or invalidity. 618 7. Test examples (Appendix to GOST R 34.10-2001) 620 This sectin is included in GOST R 34.10-2001 as an appendix but is 621 officially mentioned as not a part of the standard. 623 This is a reference appendix and is not a part of the standard. The 624 values given here for the parameters p, a, b, m, q, P, the signature 625 key d and the verification key Q are recommended only for testing 626 correctness of actual realizations of the algorithms described in 627 GOST R 34.10-2001. 629 All numerical values are introduced in decimal and hexadecimal 630 notations. The numbers beginning with 0x are in hexadecimal notation. 631 The symbol "\\" denotes a hyphenation of a number to the next line. 632 For example, the notation 634 12345\\ 635 67890 637 0x499602D2 639 represents 1234567890 in decimal and hexadecimal number systems 640 correspondingly. 642 7.1 The digital signature scheme parameters 644 The following parameters must be used for the digital signature 645 generation and verification (see section 5.2). 647 7.1.1 Elliptic curve modulus 649 The following value is assigned to parameter p in this example 651 p= 57896044618658097711785492504343953926\\ 652 634992332820282019728792003956564821041 654 p = 0x8000000000000000000000000000\\ 655 000000000000000000000000000000000431 656 7.1.2 Elliptic curve coefficients 658 Parameters a and b take the following values in this example: 660 a = 7 661 a = 0x7 663 b = 43308876546767276905765904595650931995\\ 664 942111794451039583252968842033849580414 666 b = 0x5FBFF498AA938CE739B8E022FBAFEF40563\\ 667 F6E6A3472FC2A514C0CE9DAE23B7E 669 7.1.3 Elliptic curve points group order 671 Parameter m takes the following value in this example: 673 m = 5789604461865809771178549250434395392\\ 674 7082934583725450622380973592137631069619 676 m = 0x80000000000000000000000000000\\ 677 00150FE8A1892976154C59CFC193ACCF5B3 679 7.1.4 Order of cyclic subgroup of elliptic curve points group 681 Parameter q takes the following value in this example: 683 q = 5789604461865809771178549250434395392\\ 684 7082934583725450622380973592137631069619 686 q = 0x80000000000000000000000000000001\\ 687 50FE8A1892976154C59CFC193ACCF5B3 689 7.1.5 Elliptic curve point coordinates 691 Point P coordinates take the following values in this example: 693 x_p = 2 694 x_p = 0x2 696 y_p = 40189740565390375033354494229370597\\ 697 75635739389905545080690979365213431566280 699 y_p = 0x8E2A8A0E65147D4BD6316030E16D19\\ 700 C85C97F0A9CA267122B96ABBCEA7E8FC8 702 7.1.6 Signature key 704 It is supposed in this example that the user has the following 705 signature key d: 707 d = 554411960653632461263556241303241831\\ 708 96576709222340016572108097750006097525544 709 d = 0x7A929ADE789BB9BE10ED359DD39A72C\\ 710 11B60961F49397EEE1D19CE9891EC3B28 712 7.1.7 Verification key 714 It is supposed in this example that the user has the verification key 715 Q with the following coordinate values: 717 x_q = 57520216126176808443631405023338071\\ 718 176630104906313632182896741342206604859403 720 x_q = 0x7F2B49E270DB6D90D8595BEC458B5\\ 721 0C58585BA1D4E9B788F6689DBD8E56FD80B 723 y_q = 17614944419213781543809391949654080\\ 724 031942662045363639260709847859438286763994 726 y_q = 0x26F1B489D6701DD185C8413A977B3\\ 727 CBBAF64D1C593D26627DFFB101A87FF77DA 729 7.2 Digital signature process (Algorithm I) 731 Suppose that after 1-3 steps according to the Algorithm I (6.1) are 732 performed the following numerical values are obtained: 734 e = 2079889367447645201713406156150827013\\ 735 0637142515379653289952617252661468872421 737 e = 0x2DFBC1B372D89A1188C09C52E0EE\\ 738 C61FCE52032AB1022E8E67ECE6672B043EE5 740 k = 538541376773484637314038411479966192\\ 741 41504003434302020712960838528893196233395 743 k = 0x77105C9B20BCD3122823C8CF6FCC\\ 744 7B956DE33814E95B7FE64FED924594DCEAB3 746 And the multiple point C = k * P has the coordinates: 748 x_C = 297009809158179528743712049839382569\\ 749 90422752107994319651632687982059210933395 751 x_C = 0x41AA28D2F1AB148280CD9ED56FED\\ 752 A41974053554A42767B83AD043FD39DC0493 754 y[C] = 328425352786846634770946653225170845\\ 755 06804721032454543268132854556539274060910 757 y[C] = 0x489C375A9941A3049E33B34361DD\\ 758 204172AD98C3E5916DE27695D22A61FAE46E 760 Parameter r = x_C(mod q) takes the value: 762 r = 297009809158179528743712049839382569\\ 763 90422752107994319651632687982059210933395 765 r = 0x41AA28D2F1AB148280CD9ED56FED\\ 766 A41974053554A42767B83AD043FD39DC0493 768 Parameter s = (r*d + k*e)(mod q) takes the value: 770 s = 57497340027008465417892531001914703\\ 771 8455227042649098563933718999175515839552 773 s = 0x1456C64BA4642A1653C235A98A602\\ 774 49BCD6D3F746B631DF928014F6C5BF9C40 776 7.3 Verification process of digital signature (Algorithm II) 778 Suppose that after the steps 1-3 according to the Algorithm II (6.2) 779 are performed the following numerical value is obtained: 781 e = 2079889367447645201713406156150827013\\ 782 0637142515379653289952617252661468872421 784 e = 0x2DFBC1B372D89A1188C09C52E0EE\\ 785 C61FCE52032AB1022E8E67ECE6672B043EE5 787 And the parameter v = e^(-1) (mod q) takes the value: 789 v = 176866836059344686773017138249002685\\ 790 62746883080675496715288036572431145718978 792 v = 0x271A4EE429F84EBC423E388964555BB\\ 793 29D3BA53C7BF945E5FAC8F381706354C2 795 The parameters z1 = s*v(mod q) and z2 = -r*v(mod q) take the values: 797 z1 = 376991675009019385568410572935126561\\ 798 08841345190491942619304532412743720999759 800 z1 = 0x5358F8FFB38F7C09ABC782A2DF2A\\ 801 3927DA4077D07205F763682F3A76C9019B4F 803 z2 = 141719984273434721125159179695007657\\ 804 6924665583897286211449993265333367109221 806 z2 = 0x3221B4FBBF6D101074EC14AFAC2D4F7\\ 807 EFAC4CF9FEC1ED11BAE336D27D527665 809 The point C = z1*P + z2*Q has the coordinates: 811 x_C = 2970098091581795287437120498393825699\\ 812 0422752107994319651632687982059210933395 814 x_C = 0x41AA28D2F1AB148280CD9ED56FED\\ 815 A41974053554A42767B83AD043FD39DC0493 816 y[C] = 3284253527868466347709466532251708450\\ 817 6804721032454543268132854556539274060910 819 y[C] = 0x489C375A9941A3049E33B34361DD\\ 820 204172AD98C3E5916DE27695D22A61FAE46E 822 Then the parameter R = x_C (mod q) takes the value: 824 R = 2970098091581795287437120498393825699\\ 825 0422752107994319651632687982059210933395 827 R = 0x41AA28D2F1AB148280CD9ED56FED\\ 828 A41974053554A42767B83AD043FD39DC0493 830 Since the equality R = r holds, the digital signature is accepted. 832 Appendix A. Extra terms in digital signature area 834 The appendix gives extra international terms applied in the 835 considered and allied areas. 837 1. Padding: Extending of a data string with extra bits (ISO/IEC 838 10118-1 [6]). 840 2. Identification data: A list of data elements, including specific 841 object identifier, that belongs to the object and is used for its 842 denotation (ISO/IEC 148881-1 [3]). 844 3. Signature equation: An equation, defined by the digital signature 845 function (ISO/IEC 148881-1 [3]). 847 4. Verification function: A verification process function, defined by 848 the verification key, which outputs a witness of the signature 849 authenticity (ISO/IEC 148881-1 [3]). 851 5. Signature function: A function within a signature generation 852 process, defined by the signature key and by the digital signature 853 scheme parameters. This function inputs a part of initial data and, 854 probably, a pseudorandom number sequence generator (randomizer), and 855 outputs the second part of the digital signature. 857 8. Security considerations 859 This entire document is about security considerations. 861 Current cryptographic resistance of GOST R 34.10-2001 digital 862 signature algorithm is estimated as 2**128 operations of multiple 863 elliptic curve point computations on prime modulus of order 2**256. 865 9. IANA Considerations 867 This document has no actions for IANA. 869 10. Normative references 871 [GOST3410] "Information technology. Cryptographic data security. 872 Signature and verification processes of [electronic] 873 digital signature. GOST R 34.10-2001, Gosudarstvennyi 874 Standard of Russian Federation, Government Committee of 875 the Russia for Standards, 2001. (In Russian) 877 [GOST3411] "Information technology. Cryptographic Data Security. 878 Hashing function.", GOST R 34.10-94, Gosudarstvennyi 879 Standard of Russian Federation, Government Committee of 880 the Russia for Standards, 1994. (In Russian) 882 [RFC4357] RFC 4357. V.Popov, I.Kurepkin, S.Leontiev. Additional 883 Cryptographic Algorithms for Use with GOST 28147-89, 884 GOST R 34.10-94, GOST R 34.10-2001, and GOST R 34.11-94 885 Algorithms 887 11. Informative references 889 [1] ISO 2382-2-76 Data processing. Dictionary. Part 2. Arithmetic and 890 logic operations 892 [2] ISO/IEC 9796-91 Information technology. Secure methods. Digital 893 signature scheme with message recovering 895 [3] ISO/IEC 14888-1-98 Information technology. Secure methods. 896 Digital signatures and application. Part 1. General statements 898 [4] ISO/IEC 14888-2-99 Information technology. Secure methods. 899 Digital signatures and application. Part 2. Mechanisms on 900 authentication base 902 [5] ISO/IEC 14888-3-99 Information technology. Secure methods. 903 Digital signatures and application. Part 3. Mechanisms on certificate 904 base 906 [6] ISO/IEC 10118-1-94 Information technology. Secure methods. Hash 907 functions Part 1. General statements. 909 [7] ISO/IEC 10118-2-94 Information technology. Secure methods. Hash 910 functions Part 2. Hash functions using n-bit block encryption 911 algorithm 913 [8] ISO/IEC 10118-3-98 Information technology. Secure methods. Hash 914 functions Part 3. Decimal hash functions 916 [9] ISO/IEC 10118-4-98 Information technology. Secure methods. Hash 917 functions Part 4. Hash functions using modular arithmetic. 919 Authors' Addresses 921 Vasily Dolmatov, Ed. 922 Cryptocom Ltd. 923 Kedrova st., 14, bld.2 924 Moscow, 117218, Russian Federation 926 EMail: dol@cryptocom.ru 928 Dmitry Kabelev 929 Cryptocom Ltd. 930 Kedrova st., 14, bld.2 931 Moscow, 117218, Russian Federation 933 EMail: kdb@cryptocom.ru 935 Igor Ustinov 936 Cryptocom Ltd. 937 Kedrova st., 14, bld.2 938 Moscow, 117218, Russian Federation 940 EMail: igus@cryptocom.ru 942 Sergey Vyshensky 943 Moscow State University 944 Leninskie gory, 1 945 Moscow, 119991, Russian Federation 947 EMail: svysh@pn.sinp.msu.ru