idnits 2.17.1 draft-dolmatov-gost34102012-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. 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 == Line 247 has weird spacing: '... V_all set ...' == Line 277 has weird spacing: '... zeta dig...' == Line 283 has weird spacing: '... sqrt squ...' -- Couldn't find a document date in the document -- date freshness check skipped. Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '0' on line 538 == Missing Reference: 'C' is mentioned on line 850, but not defined Summary: 0 errors (**), 0 flaws (~~), 5 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 INTERNET-DRAFT V. Dolmatov, Ed. 3 Intended Status: Informational Cryptocom, Ltd. 4 Expires: November 21, 2013 A. Degtyarev 5 Cryptocom, Ltd. 6 May 21, 2013 8 GOST R 34.10-2012: Digital Signature Algorithm 9 draft-dolmatov-gost34102012-00 11 Abstract 13 This document is intended to be a source of information about the 14 Russian Federal standard for digital signatures (GOST R 34.10-2012), 15 which is one of the Russian cryptographic standard algorithms (called 16 GOST algorithms). Recently, Russian cryptography is being used in 17 Internet applications, and this document has been created as 18 information for developers and users of GOST R 34.10-2012 for digital 19 signature generation and verification. 21 Status of this Memo 23 This Internet-Draft is submitted to IETF in full conformance with the 24 provisions of BCP 78 and BCP 79. 26 Internet-Drafts are working documents of the Internet Engineering 27 Task Force (IETF), its areas, and its working groups. Note that 28 other groups may also distribute working documents as 29 Internet-Drafts. 31 Internet-Drafts are draft documents valid for a maximum of six months 32 and may be updated, replaced, or obsoleted by other documents at any 33 time. It is inappropriate to use Internet-Drafts as reference 34 material or to cite them other than as "work in progress." 36 The list of current Internet-Drafts can be accessed at 37 http://www.ietf.org/1id-abstracts.html 39 The list of Internet-Draft Shadow Directories can be accessed at 40 http://www.ietf.org/shadow.html 42 Copyright and License Notice 44 Copyright (c) 2013 IETF Trust and the persons identified as the 45 document authors. All rights reserved. 47 This document is subject to BCP 78 and the IETF Trust's Legal 48 Provisions Relating to IETF Documents 49 (http://trustee.ietf.org/license-info) in effect on the date of 50 publication of this document. Please review these documents 51 carefully, as they describe your rights and restrictions with respect 52 to this document. Code Components extracted from this document must 53 include Simplified BSD License text as described in Section 4.e of 54 the Trust Legal Provisions and are provided without warranty as 55 described in the Simplified BSD License. 57 Table of Contents 59 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 60 1.1. General Information . . . . . . . . . . . . . . . . . . . 3 61 1.2. The Purpose of GOST R 34.10-2012 . . . . . . . . . . . . . 3 62 2. Scope . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 63 3. Terms, definitions and symbols . . . . . . . . . . . . . . . . 4 64 3.1. Terms and definitions . . . . . . . . . . . . . . . . . . 4 65 3.2. Symbols . . . . . . . . . . . . . . . . . . . . . . . . . 6 66 4. General Statements . . . . . . . . . . . . . . . . . . . . . . 7 67 5. Mathematical Conventions . . . . . . . . . . . . . . . . . . . 8 68 5.1. Mathematical Definitions . . . . . . . . . . . . . . . . . 9 69 5.2. Digital Signature Parameters . . . . . . . . . . . . . . . 11 70 5.3. Binary Vectors . . . . . . . . . . . . . . . . . . . . . . 12 71 6. Main Processes . . . . . . . . . . . . . . . . . . . . . . . . 12 72 6.1. Digital Signature Generation Process . . . . . . . . . . . 13 73 6.2. Digital Signature Verification . . . . . . . . . . . . . . 14 74 7. Test Examples (Appendix to GOST R 34.10-2012) . . . . . . . . 15 75 7.1. The Digital Signature Scheme Parameters . . . . . . . . . 15 76 7.2. Digital Signature Process (Algorithm I) . . . . . . . . . 17 77 7.3. Verification Process of Digital Signature (Algorithm II) . 18 78 8. Security Considerations . . . . . . . . . . . . . . . . . . . 20 79 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20 80 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 20 81 10.1. Normative References . . . . . . . . . . . . . . . . . . 20 82 10.2. Informative References . . . . . . . . . . . . . . . . . 20 83 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 22 85 1. Introduction 87 1.1. General Information 89 1. GOST R 34.10-2012 [GOST3410-2012] was developed by the Center for 90 Information Protection and Special Communications of the Federal 91 Security Service of the Russian Federation with participation of 92 the Open joint-stock company "Information Technologies and 93 Communication Systems" (InfoTeCS JSC). 95 2. GOST R 34.10-2012 was approved and introduced by Decree #215 of 96 the Federal Agency on Technical Regulating and Metrology on 97 07.08.2012. 99 3. GOST R 34.10-2012 intended to replace GOST R 34.10-2001 100 [GOST3410-2001] national standard of Russian Federation. 102 Terms and conceptions of this standard comply with International 103 standards ISO 2382-2 [ISO2382-2], ISO/IEC 9796 [ISO9796-2] 104 [ISO9796-3], series of standards ISO/IEC 14888 [ISO14888-1] 105 [ISO14888-2] [ISO14888-3] [ISO14888-4], and series of standards 106 ISO/IEC 10118 [ISO10118-1] [ISO10118-2] [ISO10118-3] [ISO10118-4]. 108 1.2. The Purpose of GOST R 34.10-2012 110 GOST R 34.10-2012 describes the generation and verification processes 111 for digital signatures, based on operations with an elliptic curve 112 points group, defined over a prime finite field. 114 Necessity for this standard development is caused by the need to 115 implement digital signature of varying resistance due to growth of 116 computer technology. Digital signature security is based on the 117 complexity of discrete logarithm calculation in an elliptic curve 118 points group and also on the security of the hash function used 119 (according to GOST R 34.11-2012 [GOST3411-2012]). 121 2. Scope 123 GOST R 34.10-2012 defines an electronic digital signature (or simply 124 digital signature) scheme, digital signature generation and 125 verification processes for a given message (document), meant for 126 transmission via insecure public telecommunication channels in data 127 processing systems of different purposes. 129 Use of a digital signature based on GOST R 34.10-2012 makes 130 transmitted messages more resistant to forgery and loss of integrity, 131 in comparison with the digital signature scheme prescribed by the 132 previous standard. 134 GOST R 34.10-2012 is recommended to creation, operation and 135 modernization of data processing systems of various purpose. 137 3. Terms, definitions and symbols 139 3.1. Terms and definitions 141 The following terms are used in the standard: 143 3.1.1. appendix: bit string, formed by a digital signature and by 144 the arbitrary text field. [ISO14888-1] 146 3.1.2. signature key: element of secret data, specific to the 147 subject and used only by this subject during the signature 148 generation process. [ISO14888-1] 150 3.1.3. verification key: element of data mathematically linked to 151 the signature key data element, used by the verifier during 152 the digital signature verification process. [ISO14888-1] 154 3.1.4. domain parameter: element of data that is common for all the 155 subjects of the digital signature scheme, known or accessible 156 to all the subjects. [ISO14888-1] 158 3.1.5. signed message: a set of data elements, which consists of the 159 message and the appendix, which is a part of the message. 160 [ISO14888-1] 162 3.1.6. pseudo-random number sequence: a sequence of numbers, which 163 is obtained during some arithmetic (calculation) process, 164 used in a specific case instead of a true random number 165 sequence. 167 3.1.7. random number sequence: a sequence of numbers none of which 168 can be predicted (calculated) using only the preceding 169 numbers of the same sequence. 171 3.1.8. verification process: a process that uses the signed message, 172 the verification key, and the digital signature scheme 173 parameters as initial data and that gives the conclusion 174 about digital signature validity or invalidity as a result. 175 [ISO14888-1] 177 3.1.9. signature generation process: a process that uses the 178 message, the signature key, and the digital signature scheme 179 parameters as initial data and that generates the digital 180 signature as the result. [ISO14888-1]. 182 3.1.10. witness: element of data that states to the verifier whether 183 the digital signature is valid or invalid. 185 3.1.11. random number: a number chosen from the definite number set 186 in such a way that every number from the set can be chosen 187 with equal probability. 189 3.1.12. message: string of bits of a limited length. [ISO14888-1] 191 3.1.13. hash code: string of bits that is a result of the hash 192 function. [ISO14888-1] 194 3.1.14. hash function: the function, mapping bit strings onto bit 195 strings of fixed length observing the following properties: 197 1. it is difficult to calculate the input data, that is the 198 pre-image of the given function value; 200 2. it is difficult to find another input data that is the 201 pre-image of the same function value as is the given 202 input data; 204 3. it is difficult to find a pair of different input data, 205 producing the same hash function value. 207 [ISO14888-1] 209 Notes: 211 1. property 1 in the context of the digital signature area 212 means that it is impossible to recover the initial 213 message using the digital signature; property 2 means 214 that it is difficult to find another (falsified) message 215 that produces the same digital signature as a given 216 message; property 3 means that it is difficult to find 217 some pair of different messages, which both produce the 218 same signature. 220 2. in this standard terms "hash function", "cryptographic 221 hash function", "hashing function" and "cryptographic 222 hashing function" are synonymous to provide 223 terminological succession to native legal documents 224 currently in force and scientific publications. 226 3.1.15. (electronic) digital signature: string of bits obtained as a 227 result of the signature generation process. This string has 228 an internal structure, depending on the specific signature 229 generation mechanism. [ISO14888-1] 230 Notes: 232 1. a string of bits that is signature may have internal 233 structure depending on specific mechanism of signature. 235 2. In this standard terms "electronic signature", "digital 236 signature" and "electronic digital signature" are 237 synonymous to provide terminological succession to 238 native legal documents currently in force and scientific 239 publications. 241 3.2. Symbols 243 The following symbols are used in this standard: 245 V_l set of all binary vectors of a l-bit length 247 V_all set of all binary vectors of an arbitrary finite length 249 Z set of all integers 251 p prime number, p > 3 253 GF(p) finite prime field represented by a set of integers 254 {0, 1, ..., p - 1} 256 b (mod p) 257 minimal non-negative number, congruent to b modulo p 259 M user's message, M belongs to V_all 261 (H1 || H2 ) 262 concatenation of two binary vectors 264 a, b elliptic curve coefficients 266 m points of the elliptic curve group order 268 q subgroup order of group of points of the elliptic curve 270 O zero point of the elliptic curve 272 P elliptic curve point of order q 274 d integer - a signature key 276 Q elliptic curve point - a verification key 277 zeta digital signature for the message M 279 ^ the power operator 281 /= non-equality 283 sqrt square root 285 4. General Statements 287 A commonly accepted digital signature scheme (model) consists of 288 three processes: 290 - generation of a pair of keys (for signature generation and for 291 signature verification); 293 - signature generation; 295 - signature verification. 297 In GOST R 34.10-2012, a process for generating a pair of keys (for 298 signature and verification) is not defined. Characteristics and ways 299 of the process realization are defined by involved subjects, who 300 determine corresponding parameters by their agreement. 302 The digital signature mechanism is defined by the realization of two 303 main processes (Section 6): 305 - signature generation (Section 6.1); 307 - signature verification (Section 6.2). 309 The digital signature is meant for the authentication of the 310 signatory of the electronic message. Besides, digital signature 311 usage gives an opportunity to provide the following properties during 312 signed message transmission: 314 - realization of control of the transmitted signed message integrity, 316 - proof of the authorship of the signatory of the message, 318 - protection of the message against possible forgery. 320 A schematic representation of the signed message is shown in 321 Figure 1. 323 appendix 324 | 325 +-------------------------------+ 326 | | 327 +-----------+ +------------------------+- - - + 328 | message M |---| digital signature zeta | text | 329 +-----------+ +------------------------+- - - + 331 Figure 1: Signed message scheme 333 The field "digital signature" is supplemented by the field "text", 334 that can contain, for example, identifiers of the signatory of the 335 message and/or time label. 337 The digital signature scheme determined in GOST R 34.10-2012 must be 338 implemented using operations of the elliptic curve points group, 339 defined over a finite prime field, and also with the use of hash 340 function. 342 The cryptographic security of the digital signature scheme is based 343 on the complexity of solving the problem of the calculation of the 344 discrete logarithm in the elliptic curve points group and also on the 345 security of the hash function used. The hash function calculation 346 algorithm is determined in GOST R 34.11-2012 [GOST3411-2012]. 348 The digital signature scheme parameters needed for signature 349 generation and verification are determined in Section 5.2. This 350 standard provides the opportunity to select one of two options of 351 parameter requirements. 353 GOST R 34.10-2012 does not determine the process of generating 354 parameters needed for the digital signature scheme. Possible sets of 355 these parameters are defined, for example, in [RFC4357]. 357 The digital signature represented as a binary vector of a 512 or 358 1024-bit length must be calculated using a definite set of rules, as 359 stated in Section 6.1. 361 The digital signature of the received message is accepted or denied 362 in accordance with the set of rules, as stated in Section 6.2. 364 5. Mathematical Conventions 366 To define a digital signature scheme, it is necessary to describe 367 basic mathematical objects used in the signature generation and 368 verification processes. This section lays out basic mathematical 369 definitions and requirements for the parameters of the digital 370 signature scheme. 372 5.1. Mathematical Definitions 374 Suppose a prime number p > 3 is given. Then, an elliptic curve E, 375 defined over a finite prime field GF(p), is the set of number pairs 376 (x,y), where x and y belong to Fp, satisfying the identity: 378 y^2 = x^3 + a * x + b (mod p), (1) 380 where a, b belong to GF(p) and 4 * a^3 + 27 * b^2 is not congruent to 381 zero modulo p. 383 An invariant of the elliptic curve is the value J(E), satisfying the 384 equality: 386 4 * a^3 387 J(E) = 1728 * ------------------ (mod p) (2) 388 4 * a^3 + 27 * b^2 390 Elliptic curve E coefficients a, b are defined in the following way 391 using the invariant J(E): 393 | a = 3 * k (mod p), 394 | (3) 395 | b = 2 * k (mod p), 397 J(E) 398 where k = ----------- (mod p), J(E) /= 0 or 1728 399 1728 - J(E) 401 The pairs (x, y) satisfying the identity (1) are called "the elliptic 402 curve E points"; x and y are called x- and y-coordinates of the 403 point, correspondingly. 405 We will denote elliptic curve points as Q(x, y) or just Q. Two 406 elliptic curve points are equal if their x- and y-coordinates are 407 equal. 409 On the set of all elliptic curve E points, we will define the 410 addition operation, denoted by "+". For two arbitrary elliptic curve 411 E points Q1 (x1, y1) and Q2 (x2, y2), we will consider several 412 variants. 414 Suppose coordinates of points Q1 and Q2 satisfy the condition 415 x1 /= x2. In this case, their sum is defined as a point Q3 (x3, y3), 416 with coordinates defined by congruencies: 418 | x3 = lambda^2 - x1 - x2 (mod p), 419 | (4) 420 | y3 = lambda * (x1 - x3) - y1 (mod p), 422 y1 - y2 423 where lambda = -------- (mod p). 424 x1 - x2 426 If x1 = x2 and y1 = y2 /= 0, then we will define point Q3 coordinates 427 in the following way: 429 | x3 = lambda^2 - x1 * 2 (mod p), 430 | (5) 431 | y3 = lambda * (x1 - x3) - y1 (mod p), 433 3 * x1^2 + a 434 where lambda = ------------ (mod p) 435 y1 * 2 437 If x1 = x2 and y1 = -y2 (mod p), then the sum of points Q1 and Q2 is 438 called a zero point O, without determination of its x- and y- 439 coordinates. In this case, point Q2 is called a negative of point 440 Q1. For the zero point, the equalities hold: 442 O + Q = Q + O = Q, (6) 444 where Q is an arbitrary point of elliptic curve E. 446 A set of all points of elliptic curve E, including zero point, forms 447 a finite abelian (commutative) group of order m regarding the 448 introduced addition operation. For m, the following inequalities 449 hold: 451 p + 1 - 2 * sqrt(p) =< m =< p + 1 + 2 * sqrt(p) (7) 453 The point Q is called "a point of multiplicity k", or just "a 454 multiple point of the elliptic curve E", if for some point P the 455 following equality holds: 457 Q = P + ... + P = k * P (8) 458 -----+----- 459 k 461 5.2. Digital Signature Parameters 463 The digital signature parameters are: 465 - prime number p is an elliptic curve modulus; 467 - elliptic curve E, defined by its invariant J(E) or by 468 coefficients a, b belonging to GF(p). 470 - integer m is an elliptic curve E points group order; 472 - prime number q is an order of a cyclic subgroup of the elliptic 473 curve E points group, which satisfies the following conditions: 475 | m = nq, n belongs to Z, n >= 1 476 | (9) 477 | 2^254 < q < 2^256 or 2^508 < q < 2^512 479 - point P /= O of an elliptic curve E, with coordinates (x_p, 480 y_p), satisfying the equality q * P = O. 482 - hash function h(.):V_all -> V_l, which maps the messages 483 represented as binary vectors of arbitrary finite length onto 484 binary vectors of a l-bit length. The hash function is 485 determined in GOST R 34.11-2012 [GOST3411-2012]. 487 If 2^254 < q < 2^256 then l = 256. 488 If 2^508 < q < 2^512 then l = 512. 490 Every user of the digital signature scheme must have its personal 491 keys: 493 - signature key, which is an integer d, satisfying the inequality 494 0 < d < q; 496 - verification key, which is an elliptic curve point Q with 497 coordinates (x_q, y_q), satisfying the equality d * P = Q. 499 The previously introduced digital signature parameters must satisfy 500 the following requirements: 502 - it is necessary that the condition p^t /= 1 (mod q) holds for 503 all integers t = 1, 2, ..., B, where 505 B = 31 if 2^254 < q < 2^256, or 506 B = 131 if 2^508 < q < 2^512; 508 - it is necessary that the inequality m /= p holds; 509 - the curve invariant must satisfy the condition J(E) /= 0, 1728. 511 5.3. Binary Vectors 513 To determine the digital signature generation and verification 514 processes, it is necessary to map the set of integers onto the set of 515 binary vectors of a l-bit length. 517 Consider the following binary vector of a l-bit length where low- 518 order bits are placed on the right, and high-order ones are placed on 519 the left: 521 H = (alpha[l-1], ..., alpha[0]), H belongs to V_l (10) 523 where alpha[i], i = 0, ..., l-1 are equal to 1 or to 0. The number 524 alpha belonging to Z is mapped onto the binary vector h, if the 525 equality holds: 527 alpha = alpha[0]*2^0 + alpha[1]*2^1 + ... + alpha[l-1]*2^(l-1) (11) 529 For two binary vectors H1 and H2: 531 H1 = (alpha[l-1], ..., alpha[0]), 532 (12) 533 H2 = (beta[l-1], ..., beta[0]), 535 which correspond to integers alpha and beta, we define a 536 concatenation (union) operation in the following way: 538 H1||H2 = (alpha[l-1], ..., alpha[0], beta[l-1], ..., beta[0]) (13) 540 that is a binary vector of 2*l-bit length, consisting of coefficients 541 of the vectors H1 and H2. 543 On the other hand, the introduced formulae define a way to divide a 544 binary vector H of 2*l-bit length into two binary vectors of l-bit 545 length, where H is the concatenation of the two. 547 6. Main Processes 549 In this section, the digital signature generation and verification 550 processes of user's message are defined. 552 For the realization of the processes, it is necessary that all users 553 know the digital signature scheme parameters, which satisfy the 554 requirements of Section 5.2. 556 Besides, every user must have the signature key d and the 557 verification key Q(x_q, y_q), which also must satisfy the 558 requirements of Section 5.2. 560 6.1. Digital Signature Generation Process 562 It is necessary to perform the following actions (steps) according to 563 Algorithm I to obtain the digital signature for the message M 564 belonging to V_all: 566 Step 1. Calculate the message hash code M: 568 H = h(M). (14) 570 Step 2. Calculate an integer alpha, binary representation of which 571 is the vector H, and determine: 573 e = alpha (mod q ). (15) 575 If e = 0, then assign e = 1. 577 Step 3. Generate a random (pseudorandom) integer k, satisfying the 578 inequality: 580 0 < k < q. (16) 582 Step 4. Calculate the elliptic curve point C = k * P and determine: 584 r = x_C (mod q), (17) 586 where x_C is x-coordinate of the point C. If r = 0, return 587 to step 3. 589 Step 5. Calculate the value: 591 s = (r * d + k * e) (mod q). (18) 593 If s = 0, return to step 3. 595 Step 6. Calculate the binary vectors R and S, corresponding to r and 596 s, and determine the digital signature zeta = (R || S) as a 597 concatenation of these two binary vectors. 599 The initial data of this process are the signature key d and the 600 message M to be signed. The output result is the digital signature 601 zeta. 603 6.2. Digital Signature Verification 605 To verify digital signature for the received message M, it is 606 necessary to perform the following actions (steps) according to 607 Algorithm II: 609 Step 1. Calculate the integers r and s using the received signature 610 zeta. If the inequalities 0 < r < q, 0 < s < q hold, go to 611 the next step. Otherwise, the signature is invalid. 613 Step 2. Calculate the hash code of the received message M: 615 H = h(M) (19) 617 Step 3. Calculate the integer alpha, the binary representation of 618 which is the vector H, and determine if: 620 e = alpha (mod q) (20) 622 If e = 0, then assign e = 1. 624 Step 4. Calculate the value: 626 v = e^(-1) (mod q). (21) 628 Step 5. Calculate the values: 630 z1 = s * v (mod q), z2 = -r * v (mod q) (22) 632 Step 6. Calculate the elliptic curve point C = z1 * P + z2 * Q and 633 determine: 635 R = x_C (mod q), (23) 637 where x_C is x-coordinate of the point. 639 Step 7. If the equality R = r holds, then the signature is accepted. 640 Otherwise, the signature is invalid. 642 The input data of the process are the signed message M, the digital 643 signature zeta, and the verification key Q. The output result is the 644 witness of the signature validity or invalidity. 646 7. Test Examples (Appendix to GOST R 34.10-2012) 648 This section is included in GOST R 34.10-2012 as a reference appendix 649 but is not officially mentioned as a part of the standard. 651 The values given here for the parameters p, a, b, m, q, P, the 652 signature key d, and the verification key Q are recommended only for 653 testing the correctness of actual realizations of the algorithms 654 described in GOST R 34.10-2012. 656 All numerical values are introduced in decimal and hexadecimal 657 notations. The numbers beginning with 0x are in hexadecimal 658 notation. The symbol "\\" denotes a hyphenation of a number to the 659 next line. For example, the notation: 661 12345\\ 662 67890 664 0x499602D2 666 represents 1234567890 in decimal and hexadecimal number systems, 667 respectively. 669 7.1. The Digital Signature Scheme Parameters 671 The following parameters must be used for the digital signature 672 generation and verification (see Section 5.2). 674 7.1.1. Elliptic Curve Modulus 676 The following value is assigned to parameter p in this example: 678 p = 57896044618658097711785492504343953926\\ 679 634992332820282019728792003956564821041 681 p = 0x8000000000000000000000000000\\ 682 000000000000000000000000000000000431 684 7.1.2. Elliptic Curve Coefficients 686 Parameters a and b take the following values in this example: 688 a = 7 689 a = 0x7 691 b = 43308876546767276905765904595650931995\\ 692 942111794451039583252968842033849580414 694 b = 0x5FBFF498AA938CE739B8E022FBAFEF40563\\ 695 F6E6A3472FC2A514C0CE9DAE23B7E 697 7.1.3. Elliptic Curve Points Group Order 699 Parameter m takes the following value in this example: 701 m = 5789604461865809771178549250434395392\\ 702 7082934583725450622380973592137631069619 704 m = 0x80000000000000000000000000000\\ 705 00150FE8A1892976154C59CFC193ACCF5B3 707 7.1.4. Order of Cyclic Subgroup of Elliptic Curve Points Group 709 Parameter q takes the following value in this example: 711 q = 5789604461865809771178549250434395392\\ 712 7082934583725450622380973592137631069619 714 q = 0x80000000000000000000000000000001\\ 715 50FE8A1892976154C59CFC193ACCF5B3 717 7.1.5. Elliptic Curve Point Coordinates 719 Point P coordinates take the following values in this example: 721 x_p = 2 722 x_p = 0x2 724 y_p = 40189740565390375033354494229370597\\ 725 75635739389905545080690979365213431566280 727 y_p = 0x8E2A8A0E65147D4BD6316030E16D19\\ 728 C85C97F0A9CA267122B96ABBCEA7E8FC8 730 7.1.6. Signature Key 732 It is supposed, in this example, that the user has the following 733 signature key d: 735 d = 554411960653632461263556241303241831\\ 736 96576709222340016572108097750006097525544 738 d = 0x7A929ADE789BB9BE10ED359DD39A72C\\ 739 11B60961F49397EEE1D19CE9891EC3B28 741 7.1.7. Verification Key 743 It is supposed, in this example, that the user has the verification 744 key Q with the following coordinate values: 746 x_q = 57520216126176808443631405023338071\\ 747 176630104906313632182896741342206604859403 749 x_q = 0x7F2B49E270DB6D90D8595BEC458B5\\ 750 0C58585BA1D4E9B788F6689DBD8E56FD80B 752 y_q = 17614944419213781543809391949654080\\ 753 031942662045363639260709847859438286763994 755 y_q = 0x26F1B489D6701DD185C8413A977B3\\ 756 CBBAF64D1C593D26627DFFB101A87FF77DA 758 7.2. Digital Signature Process (Algorithm I) 760 Suppose that after steps 1-3, according to Algorithm I (Section 6.1), 761 are performed, the following numerical values are obtained: 763 e = 2079889367447645201713406156150827013\\ 764 0637142515379653289952617252661468872421 766 e = 0x2DFBC1B372D89A1188C09C52E0EE\\ 767 C61FCE52032AB1022E8E67ECE6672B043EE5 769 k = 538541376773484637314038411479966192\\ 770 41504003434302020712960838528893196233395 772 k = 0x77105C9B20BCD3122823C8CF6FCC\\ 773 7B956DE33814E95B7FE64FED924594DCEAB3 775 And the multiple point C = k * P has the coordinates: 777 x_C = 297009809158179528743712049839382569\\ 778 90422752107994319651632687982059210933395 780 x_C = 0x41AA28D2F1AB148280CD9ED56FED\\ 781 A41974053554A42767B83AD043FD39DC0493 783 y[C] = 328425352786846634770946653225170845\\ 784 06804721032454543268132854556539274060910 786 y[C] = 0x489C375A9941A3049E33B34361DD\\ 787 204172AD98C3E5916DE27695D22A61FAE46E 789 Parameter r = x_C (mod q) takes the value: 791 r = 297009809158179528743712049839382569\\ 792 90422752107994319651632687982059210933395 794 r = 0x41AA28D2F1AB148280CD9ED56FED\\ 795 A41974053554A42767B83AD043FD39DC0493 797 Parameter s = (r * d + k * e)(mod q) takes the value: 799 s = 57497340027008465417892531001914703\\ 800 8455227042649098563933718999175515839552 802 s = 0x1456C64BA4642A1653C235A98A602\\ 803 49BCD6D3F746B631DF928014F6C5BF9C40 805 7.3. Verification Process of Digital Signature (Algorithm II) 807 Suppose that after steps 1-3, according to Algorithm II (Section 808 6.2), are performed, the following numerical value is obtained: 810 e = 2079889367447645201713406156150827013\\ 811 0637142515379653289952617252661468872421 813 e = 0x2DFBC1B372D89A1188C09C52E0EE\\ 814 C61FCE52032AB1022E8E67ECE6672B043EE5 816 And the parameter v = e^(-1) (mod q) takes the value: 818 v = 176866836059344686773017138249002685\\ 819 62746883080675496715288036572431145718978 821 v = 0x271A4EE429F84EBC423E388964555BB\\ 822 29D3BA53C7BF945E5FAC8F381706354C2 824 The parameters z1 = s * v (mod q) and z2 = -r * v (mod q) take the 825 values: 827 z1 = 376991675009019385568410572935126561\\ 828 08841345190491942619304532412743720999759 830 z1 = 0x5358F8FFB38F7C09ABC782A2DF2A\\ 831 3927DA4077D07205F763682F3A76C9019B4F 833 z2 = 141719984273434721125159179695007657\\ 834 6924665583897286211449993265333367109221 836 z2 = 0x3221B4FBBF6D101074EC14AFAC2D4F7\\ 837 EFAC4CF9FEC1ED11BAE336D27D527665 839 The point C = z1 * P + z2 * Q has the coordinates: 841 x_C = 2970098091581795287437120498393825699\\ 842 0422752107994319651632687982059210933395 844 x_C = 0x41AA28D2F1AB148280CD9ED56FED\\ 845 A41974053554A42767B83AD043FD39DC0493 847 y[C] = 3284253527868466347709466532251708450\\ 848 6804721032454543268132854556539274060910 850 y[C] = 0x489C375A9941A3049E33B34361DD\\ 851 204172AD98C3E5916DE27695D22A61FAE46E 853 Then the parameter R = x_C (mod q) takes the value: 855 R = 2970098091581795287437120498393825699\\ 856 0422752107994319651632687982059210933395 858 R = 0x41AA28D2F1AB148280CD9ED56FED\\ 859 A41974053554A42767B83AD043FD39DC0493 861 Since the equality R = r holds, the digital signature is accepted. 863 8. Security Considerations 865 This entire document is about security considerations. 867 9. IANA Considerations 869 This document has no actions for IANA. 871 10. References 873 10.1. Normative References 875 [GOST3410-2001] "Information technology. Cryptographic data 876 security. Signature and verification processes of 877 [electronic] digital signature.", GOST R 34.10-2001, 878 Gosudarstvennyi Standard of Russian Federation, 879 Government Committee of Russia for Standards, 2001. 880 (In Russian) 882 [GOST3410-2012] "Information technology. Cryptographic data 883 security. Signature and verification processes of 884 [electronic] digital signature.", GOST R 34.10-2012, 885 Federal Agency on Technical Regulating and 886 Metrology, 2012. 888 [GOST3411-2012] "Information technology. Cryptographic Data 889 Security. Hashing function.", GOST R 34.11-2012, 890 Federal Agency on Technical Regulating and 891 Metrology, 2012. 893 [RFC4357] Popov, V., Kurepkin, I., and S. Leontiev, 894 "Additional Cryptographic Algorithms for Use with 895 GOST 28147-89, GOST R 34.10-94, GOST R 34.10-2001, 896 and GOST R 34.11-94 Algorithms", RFC 4357, January 897 2006. 899 10.2. Informative References 901 [ISO2382-2] ISO 2382-2:1976, "Data processing - Vocabulary - 902 Part 2: Arithmetic and logic operations". 904 [ISO9796-2] ISO/IEC 9796-2:2010, "Information technology - 905 Security techniques - Digital signatures with 906 appendix - Part 2: Integer factorization based 907 mechanisms" 909 [ISO9796-3] ISO/IEC 9796-3:2006, "Information technology - 910 Security techniques - Digital signature schemes 911 giving message recovery - Part 3: Discrete logarithm 912 based mechanisms" 914 [ISO14888-1] ISO/IEC 14888-1:2008, "Information technology - 915 Security techniques - Digital signatures with 916 appendix - Part 1: General". 918 [ISO14888-2] ISO/IEC 14888-2:2008, "Information technology - 919 Security techniques - Digital signatures with 920 appendix - Part 2: Integer factorization based 921 mechanisms". 923 [ISO14888-3] ISO/IEC 14888-3:2006, "Information technology - 924 Security techniques - Digital signatures with 925 appendix - Part 3: Discrete logarithm based 926 mechanisms". 928 [ISO14888-4] ISO/IEC 14888-3:2006/Amd 1:2010, "Information 929 technology - Security techniques - Digital 930 signatures with appendix - Part 3: Discrete 931 logarithm based mechanisms. Ammendment 1. Elliptic 932 Curve Russian Digital Signature Algorithm, Schnorr 933 Digital Signature Algorithm, Elliptic Curve Schnorr 934 Digital Signature Algorithm, and Elliptic Curve Full 935 Schnorr Digital Signature Algorithm" 937 [ISO10118-1] ISO/IEC 10118-1:2000, "Information technology - 938 Security techniques - Hash-functions - Part 1: 939 General". 941 [ISO10118-2] ISO/IEC 10118-2:2000, "Information technology - 942 Security techniques - Hash-functions - Part 2: Hash- 943 functions using an n-bit block cipher algorithm". 945 [ISO10118-3] ISO/IEC 10118-3:2004, "Information technology - 946 Security techniques - Hash-functions - Part 3: 947 Dedicated hash-functions". 949 [ISO10118-4] ISO/IEC 10118-4:1998, "Information technology - 950 Security techniques - Hash-functions - Part 4: Hash- 951 functions using modular arithmetic". 953 Author's Address 955 Vasily Dolmatov, Ed. 956 Cryptocom, Ltd. 957 14 Kedrova St., Bldg. 2 958 Moscow, 117218 959 Russian Federation 960 EMail: dol@cryptocom.ru 962 Alexey Degtyarev 963 Cryptocom, Ltd. 964 14 Kedrova St., Bldg. 2 965 Moscow, 117218 966 Russian Federation 967 EMail: degtyarev@cryptocom.ru