GOST R 34.102001: Digital Signature Algorithm
draftdolmatovcryptocomgost3410200108
This document is an InternetDraft (ID) that has been submitted to the Independent Submission stream.
This ID is not endorsed by the IETF and has no formal standing in the
IETF standards process.
The information below is for an old version of the document that is already published as an RFC.
Document  Type 
This is an older version of an InternetDraft that was ultimately published as RFC 5832.



Author  Vasily Dolmatov  
Last updated  20200121 (Latest revision 20091222)  
RFC stream  Independent Submission  
Intended RFC status  Informational  
Formats  
Stream  ISE state  (None)  
Consensus boilerplate  Unknown  
Document shepherd  (None)  
IESG  IESG state  Became RFC 5832 (Informational)  
Action Holders 
(None)


Telechat date  (None)  
Responsible AD  Russ Housley  
Send notices to  igus@cryptocom.ru, kdb@cryptocom.ru, svysh@pn.sinp.msu.ru, rfcise@rfceditor.org 
draftdolmatovcryptocomgost3410200108
InternetDraft V. Dolmatov, Ed. Intended status: Informational Cryptocom Ltd. Expires: June 21, 2010 December 21, 2009 GOST R 34.102001 digital signature algorithm draftdolmatovcryptocomgost3410200108 Status of This Memo This InternetDraft is submitted to IETF in full conformance with the provisions of BCP 78 and BCP 79. InternetDrafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet Drafts. InternetDrafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use InternetDrafts as reference material or to cite them other than as "work in progress." The list of current InternetDrafts can be accessed at http://www.ietf.org/ietf/1idabstracts.txt. The list of InternetDraft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. This InternetDraft will expire on June 21, 2010. Copyright Notice Copyright (c) 2009 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents in effect on the date of publication of this document (http://trustee.ietf.org/licenseinfo). Please review these documents carefully, as they describe your rights and restrictions with respect to this document. This document may not be modified, and derivative works of it may not be created, except to format it for publication as an RFC or to translate it into languages other than English. Abstract This document is intended to be a source of information about the Russian Federal standard for digital signatures (GOST R 34.102001), which is one of the Russian cryptographic standard algorithms (called GOST algorithms). Recently, Russian cryptography is being used in Internet applications, and this document has been created as as information for developers and users of GOST R 34.102001 for digital signature generation and verification. V.Dolmatov Expires June 21, 2010 [Page 1] Table of Contents 1. Introduction.....................................................2 1.1. General information.........................................2 1.2. The purpose of GOST R 34.102001............................3 2. Applicability....................................................3 3. Definitions and notations........................................3 3.1. Definitions.................................................3 3.2. Notations...................................................5 4. General statements...............................................6 5. Mathematical conventions.........................................7 5.1. Mathematical definitions....................................7 5.2. Digital signature parameters................................9 5.3. Binary vectors.............................................10 6. Main processes..................................................10 6.1. Digital signature generation process.......................11 6.2. Digital signature verification.............................11 7. Test examples (Appendix B to GOST R 34.102001).................13 7.1. The digital signature scheme parameters....................13 7.2. Digital signature process (Algorithm I)....................15 7.3. Verification process of digital signature (Algorithm II)...16 8. Security considerations.........................................17 9. IANA considerations.............................................17 10. Normative references...........................................18 11. Informative references.........................................18 1. Introduction 1.1. General information 1. GOST R 34.102001 was developed by the Federal Agency for Government Communication and Information under the President of Russian Federation with participation of the AllRussia Scientific and Research Institute of Standardization. GOST R 34.102001 was submitted by Federal Agency for Government Communication and Information at President of Russian Federation. 2. GOST R 34.102001 was accepted and activated by the Act 380st of 12.09.2001 issued by the Russian federal committee for standards. 3. GOST R 34.102001 was developed in accordance with terminology and concepts of international standards ISO 2382276. "Data processing. Dictionary. Part 2. Arithmetic and logic operations", ISO/IEC 979691 "Information technology. Secure methods. Digital signature scheme with message recovering", series ISO/ IEC 14888 "Information technology. Secure methods. Digital signatures and application" and series ISO/ IEC 10118 "Information technology. Secure methods. Hash functions" 4. GOST R 34.102001 replaces GOST R 34.1094. V.Dolmatov Expires June 21, 2010 [Page 2] 1.2. The purpose of GOST R 34.102001 GOST R 34.102001 describes generation and verification processes for digital signature, based on operations with elliptic curve points group, defined over prime finite field. GOST R 34.102001 is developed to replace GOST R 34.1094. Necessity for this development is caused by the need to increase the digital signature security against unauthorized modification. Digital signature security is based on complexity of discrete logarithm calculation in elliptic curve points group and also on the security of the hash function used (according to [GOST3411]). Terminologically and conceptually GOST R 34.102001 is in accord with international standards ISO 23822 [1], ISO/ IEC 9796 [2], series ISO/ IEC 14888 [3][5] and series ISO/ IEC 10118 [6][9]. Note: the main part of GOST R 34.102001 is supplemented with two appendixes: extra terms in digital signature area (Appendix A to this memo); test examples (section 7 of this memo); a bibliography in digital signature area (section 12 of this memo). 2. Applicability GOST R 34.102001 defines an electronic digital signature (or simply digital signature) scheme, digital signature generation and verification processes for a given message (document), meant for transmission via insecure public telecommunication channels in data processing systems of different purposes. Use of digital signature based on GOST R 34.102001 makes transmitted messages more resistant to forgery and loss of integrity, in comparison with digital signature scheme prescribed by the previous standard. GOST R 34.102001 is obligatory to use in Russian Federation in all data processing systems providing public services. 3. Definitions and notations 3.1. Definitions The following terms are used in the standard: 3.1.1 Appendix: Bit string, formed by digital signature and by arbitrary text field (ISO/IEC 1488811 [3]). 3.1.2 Signature key: Element of secret data, specific to the subject V.Dolmatov Expires June 21, 2010 [Page 3] and used only by this subject during the signature generation process (ISO/IEC 148881 [3]). 3.1.3 Verification key: Element of data mathematically linked to the signature key data element, used by the verifier during the digital signature verification process (ISO/IEC 148881 [3]). 3.1.4 Domain parameter: Element of data which is common for all the subjects of the digital signature scheme, known or accessible to all the subjects (ISO/IEC 148881 [3]). 3.1.5 Signed message: A set of data elements, that consists of the message and the appendix, which is a part of the message. 3.1.6 Pseudorandom number sequence: A sequence of numbers, which is obtained during some arithmetic (calculation) process, used in specific case instead of a true random number sequence (ISO 23822 [1]). 3.1.7 Random number sequence: A sequence of numbers none of which can be predicted (calculated) using only the preceding numbers of the same sequence (ISO 23822 [1]). 3.1.8 Verification process: A process using the signed message, the verification key and digital signature scheme parameters as initial data and giving the conclusion about digital signature validity or invalidity as a result. (ISO/IEC 148881 [3]). 3.1.9 Signature generation process: A process using the message, the signature key and digital signature scheme parameters as initial data and generating the digital signature as the result (ISO/IEC 148881 [3]). 3.1.10 Witness: Element of data (resulting from the verification process) which states to the verifier whether digital signature is valid or invalid (ISO/IEC 1488811 [3]). 3.1.11 Random number: A number chosen from the definite number set in such a way that every number from the set can be chosen with equal probability (ISO 23822 [1]). 3.1.12 Message: String of bits of a limited length (ISO/IEC 9796 [2]). 3.1.13 Hash code: String of bits that is a result of the hash function (ISO/IEC 1488811 [3]). 3.1.14 Hash function: The function, mapping bit strings onto bit strings of fixed length observing the following properties: 1) it is difficult to calculate the input data, that is the preimage of the given function value; 2) it is difficult to find another input data that is the preimage of the same function value as is the given input data; V.Dolmatov Expires June 21, 2010 [Page 4] 3) it is difficult to find a pair of different input data, producing the same hash function value. Note: The property 1 in the context of the digital signature area means that it is impossible to recover the initial message using the digital signature; property 2 means that it is difficult to find another (falsificated) message that produces the same digital signature as a given message; property 3 means that it is difficult to find some pair of different messages, that both produce the same signature. 3.1.15 [Electronic] Digital signature: String of bits obtained as a result of signature generation process. This string has an internal structure, depending on the specific signature generation mechanism. Note: In GOST R 34.102001 terms "Digital signature" and "Electronic sigital signature" are synonymous to save terminological succession to native legal documents currently in force and scientific publications. 3.2 Notations In GOST R 34.102001 the following notations are used: V256  set of all binary vectors of length 256 bit; V_all  set of all binary vectors of an arbitrary finite length; Z  set of all integers; p  prime number, p > 3; GF(p)  finite prime field represented by a set of integers {0, 1, ..., p  1}; b (mod p)  minimal nonnegative number, congruent to b modulo p; M  user's message, M belongs to V_all; (H1  H2 )  concatenation of two binary vectors; a,b  elliptic curve coefficients; m  points of the elliptic curve group order; q  subgroup order of group of points of the elliptic curve; O  zero point of the elliptic curve; P  elliptic curve point of order q; d  integer  a signature key; Q  elliptic curve point  a verification key; V.Dolmatov Expires June 21, 2010 [Page 5] ^  the power operator; /=  nonequality; sqrt  square root; zeta  digital signature for the message M. 4. GENERAL STATEMENTS A commonly accepted digital signature scheme (model) (see 6 ISO/IEC 148881 [3]) consists of three processes:  generation of a pair of keys (for signature generation and for signature verification);  signature generation;  signature verification. In GOST R 34.102001 a process for generating a pair of keys (for signature and verification) is not defined. Characteristics and ways of the process realization are defined by involved subjects, who determine corresponding parameters by their agreement. The digital signature mechanism is defined by realization of two main processes (see part 7):  signature generation (see. 6.1);  signature verification (see. 6.2). The digital signature is meant for authentication of the signatory of the electronic message. Besides, the digital signature usage gives an opportunity to provide the following properties during signed message transmission:  realization of control of the transmitted signed message integrity,  proof of the authorship of the signatory of the message,  protection of the message against possible forgery. A schematic representation of the signed message is shown in the figure 1. appendix  ++   ++ ++   +  message M  digital signature zeta  text  ++ ++   + Figure 1  Signed message scheme V.Dolmatov Expires June 21, 2010 [Page 6] The field "digital signature" is supplemented by the field "text" (see figure 1), that can contain for example identifiers of the signatory of the message, and/or time label. The digital signature scheme determined in GOST R 34.102001 must be implemented using operations of elliptic curve points group, defined over a finite prime field, and also with the use of hash function. The cryptographic security of the digital signature scheme is based on complexity of solving the problem of calculation the discrete logarithm in elliptic curve points group, and also on the security of the hash function used. The hash function calculation algorithm is determined in [GOST3411]. The digital signature scheme parameters needed for signature generation and verification are determined in 5.2. GOST R 34.102001 does not determine the process of generating parameters needed for digital signature scheme. Possible sets of these parameters are defined for example in [RFC4357]. The digital signature represented as a binary vector of length 512 bit, must be calculated using definite set of rules stated in 6.1. The digital signature of the received message is accepted or denied in accordance with the set of rules, stated in 6.2. 5. Mathematical conventions To define a digital signature scheme it is necessary to describe basic mathematical objects, used in the signature generation and verification processes. This section lays out basic mathematical definitions and requirements for the parameters of the digital signature scheme. 5.1 Mathematical definitions Suppose a prime number p > 3 is given. Then an elliptic curve E, defined over a finite prime field GF(p), is the set of number pairs (x,y), x, y belong to Fp , satisfying the identity y^2 = x^3 + a*x + b (mod p), (1) where a, b belong to GF(p) and 4*a^3 + 27*b^2 is not congruent to zero modulo p. An invariant of the elliptic curve is the value J(E) satisfying the equality 4*a^3 J(E) = 1728 *  (mod p) (2) 4*a^3+27*b^2 V.Dolmatov Expires June 21, 2010 [Page 7] Elliptic curve E coefficients a,b are defined in the following way using the invariant J(E):  a=3*k (mod p)  J(E)  b=2*k (mod p), where k =  (mod p), J(E) /= 0 or 1728 (3) 1728  J(E) The pairs (x,y) satisfying the identity (1) are called the elliptic curve E points, x and y are called x and ycoordinates of the point correspondingly. We will denote elliptic curve points as Q(x,y) or just Q. Two elliptic curve points are equal if their x and ycoordinates are equal. On the set of all elliptic curve E points we will define the addition operation, denoted by "+". For two arbitrary elliptic curve E points Q1 (x1, y1) and Q2 (x2, y2) we will consider several variants. Suppose coordinates of points Q1 and Q2 satisfy the condition x1 /= x2. In this case their sum is defined as a point Q3 (x3,y3) with coordinates defined by congruences  x3=lambda^2x1x2 (mod p), y1y2  where lambda=  (mod p). (4)  y3=lambda*(x1x3)y1 (mod p), x1x2 If x1 = x2 and y1 = y2 /= 0, then we will define point Q3 coordinates in a following way  x3=lambda^2x1*2 (mod p), 3*x1^2+a  where lambda=  (mod p) (5)  y3=lambda*(x1x3)y1 (mod p), y1*2 If x1 = x2 and y1 =  y2 (mod p), then the sum of points Q1 and Q2 is called a zero point O, without determination of its x and ycoordinates. In this case point Q2 is called a negative of point Q1. For the zero point the equalities hold O+Q=Q+O=Q, (6) V.Dolmatov Expires June 21, 2010 [Page 8] where Q is an arbitrary point of elliptic curve E. A set of all points of elliptic curve E including zero point forms a finite abelian (commutative) group of order m regarding introduced addition operation. For m the following unequalities hold: p + 1  2*sqrt(p) =< m =< p + 1 + 2*sqrt(p). (7) The point Q is called a point of multiplicity k, or just a multiple point of the elliptic curve E, if for some point P the following equality holds: Q = P + ... + P = k*P. (8) + k 5.2 Digital signature parameters The digital signature parameters are:  prime number p is an elliptic curve modulus, satisfying the inequality p > 2^255. The upper bound for this number must be determined for specific realization of digital signature scheme;  elliptic curve E, defined by its invariant J(E) or by coefficients a, b belonging to GF(p).  integer m is an elliptic curve E points group order;  prime number q is an order of a cyclic subgroup of the elliptic curve E points group, which satisfies the following conditions:  m = nq, n belongs to Z , n>=1  ; (9)  2^254 < q < 2^256  point P /= O of an elliptic curve E, with coordinates (x_p, y_p), satisfying the equality q*P=O.  hash function h(.):V_all > V256, which maps the messages represented as binary vectors of arbitrary finite length onto binary vectors of length 256 bit. The hash function is determined in [GOST3411]. Every user of the digital signature scheme must have its personal keys:  signature key, which is an integer d, satisfying the inequality 0 < d < q;  verification key, which is an elliptic curve point Q with coordinates (x_q, y_q), satisfying the equality d*P=Q. V.Dolmatov Expires June 21, 2010 [Page 9] The previously introduced digital signature parameters must satisfy the following requirements:  it is necessary that the condition p^t/= 1 (mod q ) holds for all integers t = 1, 2, ... B where B satisfies the inequality B >= 31;  it is necessary that the inequality m /= p holds;  the curve invariant must satisfy the condition J(E) /= 0, 1728. 5.3 Binary vectors To determine the digital signature generation and verification processes it is necessary to map the set of integers onto the set of binary vectors of length 256 bit. Consider the following binary vector of length 256 bit where loworder bits are placed on the right, and highorder ones are placed on the left H = (alpha[255], ... , alpha[0]), H belongs to V256 (10) where alpha[i], i = 0, ... , 255 are equal to 1 or to 0. We will say that the number alpha belonging to Z is mapped onto the binary vector h, if the equality holds alpha = alpha[0]*2^0 + alpha[1]*2^1 + ... + alpha[255]*2^255. (11) For two binary vectors H1 and H2 , which correspond to integers alpha and beta, we define a concatenation (union) operation in the following way. Let H1 = (alpha[255], ... , alpha[0]), (12) H2 = (beta[255], ..., beta[0]), then their union is H1H2 = (alpha[255], ... , alpha[0], beta[255], ..., beta[0]) (13) that is a binary vector of length 512 bit, consisting of coefficients of the vectors H1 and H2. On the other hand, the introduced formulae define a way to divide a binary vector H of length 512 bit into two binary vectors of length 256 bit, where H is the concatenation of the two. 6. Main processes In this section the digital signature generation and verification processes of user's message are defined. V.Dolmatov Expires June 21, 2010 [Page 10] For the realization of the processes it is necessary, that all users know the digital signature scheme parameters, which satisfy the requirements of section 5.2. Besides, every user must have the signature key d and the verification key Q(x[q], y[q]) , which also must satisfy the requirements of section 5.2. 6.1 Digital signature generation process It is necessary to perform the following actions (steps) according to Algorithm I to obtain the digital signature for the message M belonging to V_all: Step 1  calculate the message hash code M: H = h(M). (14) Step 2  calculate an integer alpha, binary representation of which is the vector H , and determine e = alpha (mod q ) . (15) If e = 0, then assign e = 1. Step 3  generate a random (pseudorandom) integer k, satisfying the inequality 0 < k < q. (16) Step 4  calculate the elliptic curve point C = k*P and determine r = x_C (mod q), (17) where x_C is xcoordinate of the point C. If r = 0, return to step 3. Step 5  calculate the value s = (r*d + k*e) (mod q). (18) If s = 0, return to step 3. Step 6  calculate the binary vectors R and S , corresponding to r and s, and determine the digital signature zeta = (R  S) as concatenation of these two binary vectors. The initial data of this process are the signature key d and the message M to be signed. The output result is the digital signature zeta. 6.2 Digital signature verification To verify digital signature for the received message M belonging to V_all it is necessary to perform the following actions (steps) according to Algorithm II: V.Dolmatov Expires June 21, 2010 [Page 11] Step 1  calculate the integers r and s using the received signature zeta. If the inequalities 0 < r < q, 0 < s < q hold, go to the next step. In the other case the signature is invalid. Step 2  calculate the hash code of the received message M H = h(M). (19) Step 3  calculate the integer alpha, the binary representation of which is the vector H , and determine e = alpha (mod q). (20) If e = 0, then assign e = 1. Step 4  calculate the value v = e^(1) (mod q) . (21) Step 5  calculate the values z1 = s*v (mod q), z2 = r*v (mod q). (22) Step 6  calculate the elliptic curve point C = z1*P + z2*Q and determine R = x_C (mod q), (23) where x_C is xcoordinate of the point . Step 7  if the equality R = r holds, than the signature is accepted, in the other case the signature is invalid. The input data of the process are the signed message M, the digital signature zeta and the verification key Q. The output result is the witness of the signature validity or invalidity. V.Dolmatov Expires June 21, 2010 [Page 12] 7. Test examples (Appendix to GOST R 34.102001) This sectin is included in GOST R 34.102001 as an appendix but is officially mentioned as not a part of the standard. This is a reference appendix and is not a part of the standard. The values given here for the parameters p, a, b, m, q, P, the signature key d and the verification key Q are recommended only for testing correctness of actual realizations of the algorithms described in GOST R 34.102001. All numerical values are introduced in decimal and hexadecimal notations. The numbers beginning with 0x are in hexadecimal notation. The symbol "\\" denotes a hyphenation of a number to the next line. For example, the notation 12345\\ 67890 0x499602D2 represents 1234567890 in decimal and hexadecimal number systems correspondingly. 7.1 The digital signature scheme parameters The following parameters must be used for the digital signature generation and verification (see section 5.2). 7.1.1 Elliptic curve modulus The following value is assigned to parameter p in this example p= 57896044618658097711785492504343953926\\ 634992332820282019728792003956564821041 p = 0x8000000000000000000000000000\\ 000000000000000000000000000000000431 V.Dolmatov Expires June 21, 2010 [Page 13] 7.1.2 Elliptic curve coefficients Parameters a and b take the following values in this example: a = 7 a = 0x7 b = 43308876546767276905765904595650931995\\ 942111794451039583252968842033849580414 b = 0x5FBFF498AA938CE739B8E022FBAFEF40563\\ F6E6A3472FC2A514C0CE9DAE23B7E 7.1.3 Elliptic curve points group order Parameter m takes the following value in this example: m = 5789604461865809771178549250434395392\\ 7082934583725450622380973592137631069619 m = 0x80000000000000000000000000000\\ 00150FE8A1892976154C59CFC193ACCF5B3 7.1.4 Order of cyclic subgroup of elliptic curve points group Parameter q takes the following value in this example: q = 5789604461865809771178549250434395392\\ 7082934583725450622380973592137631069619 q = 0x80000000000000000000000000000001\\ 50FE8A1892976154C59CFC193ACCF5B3 7.1.5 Elliptic curve point coordinates Point P coordinates take the following values in this example: x_p = 2 x_p = 0x2 y_p = 40189740565390375033354494229370597\\ 75635739389905545080690979365213431566280 y_p = 0x8E2A8A0E65147D4BD6316030E16D19\\ C85C97F0A9CA267122B96ABBCEA7E8FC8 7.1.6 Signature key It is supposed in this example that the user has the following signature key d: d = 554411960653632461263556241303241831\\ 96576709222340016572108097750006097525544 V.Dolmatov Expires June 21, 2010 [Page 14] d = 0x7A929ADE789BB9BE10ED359DD39A72C\\ 11B60961F49397EEE1D19CE9891EC3B28 7.1.7 Verification key It is supposed in this example that the user has the verification key Q with the following coordinate values: x_q = 57520216126176808443631405023338071\\ 176630104906313632182896741342206604859403 x_q = 0x7F2B49E270DB6D90D8595BEC458B5\\ 0C58585BA1D4E9B788F6689DBD8E56FD80B y_q = 17614944419213781543809391949654080\\ 031942662045363639260709847859438286763994 y_q = 0x26F1B489D6701DD185C8413A977B3\\ CBBAF64D1C593D26627DFFB101A87FF77DA 7.2 Digital signature process (Algorithm I) Suppose that after 13 steps according to the Algorithm I (6.1) are performed the following numerical values are obtained: e = 2079889367447645201713406156150827013\\ 0637142515379653289952617252661468872421 e = 0x2DFBC1B372D89A1188C09C52E0EE\\ C61FCE52032AB1022E8E67ECE6672B043EE5 k = 538541376773484637314038411479966192\\ 41504003434302020712960838528893196233395 k = 0x77105C9B20BCD3122823C8CF6FCC\\ 7B956DE33814E95B7FE64FED924594DCEAB3 And the multiple point C = k * P has the coordinates: x_C = 297009809158179528743712049839382569\\ 90422752107994319651632687982059210933395 x_C = 0x41AA28D2F1AB148280CD9ED56FED\\ A41974053554A42767B83AD043FD39DC0493 y[C] = 328425352786846634770946653225170845\\ 06804721032454543268132854556539274060910 y[C] = 0x489C375A9941A3049E33B34361DD\\ 204172AD98C3E5916DE27695D22A61FAE46E Parameter r = x_C(mod q) takes the value: V.Dolmatov Expires June 21, 2010 [Page 15] r = 297009809158179528743712049839382569\\ 90422752107994319651632687982059210933395 r = 0x41AA28D2F1AB148280CD9ED56FED\\ A41974053554A42767B83AD043FD39DC0493 Parameter s = (r*d + k*e)(mod q) takes the value: s = 57497340027008465417892531001914703\\ 8455227042649098563933718999175515839552 s = 0x1456C64BA4642A1653C235A98A602\\ 49BCD6D3F746B631DF928014F6C5BF9C40 7.3 Verification process of digital signature (Algorithm II) Suppose that after the steps 13 according to the Algorithm II (6.2) are performed the following numerical value is obtained: e = 2079889367447645201713406156150827013\\ 0637142515379653289952617252661468872421 e = 0x2DFBC1B372D89A1188C09C52E0EE\\ C61FCE52032AB1022E8E67ECE6672B043EE5 And the parameter v = e^(1) (mod q) takes the value: v = 176866836059344686773017138249002685\\ 62746883080675496715288036572431145718978 v = 0x271A4EE429F84EBC423E388964555BB\\ 29D3BA53C7BF945E5FAC8F381706354C2 The parameters z1 = s*v(mod q) and z2 = r*v(mod q) take the values: z1 = 376991675009019385568410572935126561\\ 08841345190491942619304532412743720999759 z1 = 0x5358F8FFB38F7C09ABC782A2DF2A\\ 3927DA4077D07205F763682F3A76C9019B4F z2 = 141719984273434721125159179695007657\\ 6924665583897286211449993265333367109221 z2 = 0x3221B4FBBF6D101074EC14AFAC2D4F7\\ EFAC4CF9FEC1ED11BAE336D27D527665 The point C = z1*P + z2*Q has the coordinates: x_C = 2970098091581795287437120498393825699\\ 0422752107994319651632687982059210933395 x_C = 0x41AA28D2F1AB148280CD9ED56FED\\ A41974053554A42767B83AD043FD39DC0493 V.Dolmatov Expires June 21, 2010 [Page 16] y[C] = 3284253527868466347709466532251708450\\ 6804721032454543268132854556539274060910 y[C] = 0x489C375A9941A3049E33B34361DD\\ 204172AD98C3E5916DE27695D22A61FAE46E Then the parameter R = x_C (mod q) takes the value: R = 2970098091581795287437120498393825699\\ 0422752107994319651632687982059210933395 R = 0x41AA28D2F1AB148280CD9ED56FED\\ A41974053554A42767B83AD043FD39DC0493 Since the equality R = r holds, the digital signature is accepted. Appendix A. Extra terms in digital signature area The appendix gives extra international terms applied in the considered and allied areas. 1. Padding: Extending of a data string with extra bits (ISO/IEC 101181 [6]). 2. Identification data: A list of data elements, including specific object identifier, that belongs to the object and is used for its denotation (ISO/IEC 1488811 [3]). 3. Signature equation: An equation, defined by the digital signature function (ISO/IEC 1488811 [3]). 4. Verification function: A verification process function, defined by the verification key, which outputs a witness of the signature authenticity (ISO/IEC 1488811 [3]). 5. Signature function: A function within a signature generation process, defined by the signature key and by the digital signature scheme parameters. This function inputs a part of initial data and, probably, a pseudorandom number sequence generator (randomizer), and outputs the second part of the digital signature. 8. Security considerations This entire document is about security considerations. Current cryptographic resistance of GOST R 34.102001 digital signature algorithm is estimated as 2**128 operations of multiple elliptic curve point computations on prime modulus of order 2**256. 9. IANA Considerations This document has no actions for IANA. V.Dolmatov Expires June 21, 2010 [Page 17] 10. Normative references [GOST3410] "Information technology. Cryptographic data security. Signature and verification processes of [electronic] digital signature. GOST R 34.102001, Gosudarstvennyi Standard of Russian Federation, Government Committee of the Russia for Standards, 2001. (In Russian) [GOST3411] "Information technology. Cryptographic Data Security. Hashing function.", GOST R 34.1094, Gosudarstvennyi Standard of Russian Federation, Government Committee of the Russia for Standards, 1994. (In Russian) [RFC4357] RFC 4357. V.Popov, I.Kurepkin, S.Leontiev. Additional Cryptographic Algorithms for Use with GOST 2814789, GOST R 34.1094, GOST R 34.102001, and GOST R 34.1194 Algorithms 11. Informative references [1] ISO 2382276 Data processing. Dictionary. Part 2. Arithmetic and logic operations [2] ISO/IEC 979691 Information technology. Secure methods. Digital signature scheme with message recovering [3] ISO/IEC 14888198 Information technology. Secure methods. Digital signatures and application. Part 1. General statements [4] ISO/IEC 14888299 Information technology. Secure methods. Digital signatures and application. Part 2. Mechanisms on authentication base [5] ISO/IEC 14888399 Information technology. Secure methods. Digital signatures and application. Part 3. Mechanisms on certificate base [6] ISO/IEC 10118194 Information technology. Secure methods. Hash functions Part 1. General statements. [7] ISO/IEC 10118294 Information technology. Secure methods. Hash functions Part 2. Hash functions using nbit block encryption algorithm [8] ISO/IEC 10118398 Information technology. Secure methods. Hash functions Part 3. Decimal hash functions [9] ISO/IEC 10118498 Information technology. Secure methods. Hash functions Part 4. Hash functions using modular arithmetic. V.Dolmatov Expires June 21, 2010 [Page 18] Authors' Addresses Vasily Dolmatov, Ed. Cryptocom Ltd. Kedrova st., 14, bld.2 Moscow, 117218, Russian Federation EMail: dol@cryptocom.ru Dmitry Kabelev Cryptocom Ltd. Kedrova st., 14, bld.2 Moscow, 117218, Russian Federation EMail: kdb@cryptocom.ru Igor Ustinov Cryptocom Ltd. Kedrova st., 14, bld.2 Moscow, 117218, Russian Federation EMail: igus@cryptocom.ru Sergey Vyshensky Moscow State University Leninskie gory, 1 Moscow, 119991, Russian Federation EMail: svysh@pn.sinp.msu.ru