Independent Submission V. Dolmatov, Ed. Request for Comments: 5832 Cryptocom, Ltd. Category: Informational March 2010 ISSN: 2070-1721
GOST R 34.10-2001: Digital Signature Algorithm
Abstract
This document is intended to be a source of information about the Russian Federal standard for digital signatures (GOST R 34.10-2001), 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 information for developers and users of GOST R 34.10-2001 for digital signature generation and verification.
Status of This Memo
This document is not an Internet Standards Track specification; it is published for informational purposes.
This is a contribution to the RFC Series, independently of any other RFC stream. The RFC Editor has chosen to publish this document at its discretion and makes no statement about its value for implementation or deployment. Documents approved for publication by the RFC Editor are not a candidate for any level of Internet Standard; see Section 2 of RFC 5741.
Information about the current status of this document, any errata, and how to provide feedback on it may be obtained at http://www.rfc-editor.org/info/rfc5832.
Dolmatov Informational [Page 1]
RFC 5832 GOST R 34.10-2001 March 2010
Copyright Notice
Copyright (c) 2010 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 (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. 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.
Table of Contents
1. Introduction ....................................................3 1.1. General Information ........................................3 1.2. The Purpose of GOST R 34.10-2001 ...........................3 2. Applicability ...................................................4 3. Definitions and Notations .......................................4 3.1. Definitions ................................................4 3.2. Notations ..................................................6 4. General Statements ..............................................7 5. Mathematical Conventions ........................................8 5.1. Mathematical Definitions ...................................9 5.2. Digital Signature Parameters ..............................10 5.3. Binary Vectors ............................................11 6. Main Processes .................................................12 6.1. Digital Signature Generation Process ......................12 6.2. Digital Signature Verification ............................13 7. Test Examples (Appendix to GOST R 34.10-2001) ..................14 7.1. The Digital Signature Scheme Parameters ...................14 7.2. Digital Signature Process (Algorithm I) ...................16 7.3. Verification Process of Digital Signature (Algorithm II) ..17 8. Security Considerations ........................................19 9. References .....................................................19 9.1. Normative References ......................................19 9.2. Informative References ....................................19 Appendix A. Extra Terms in the Digital Signature Area .............21 Appendix B. Contributors ..........................................22
1. GOST R 34.10-2001 [GOST3410] was developed by the Federal Agency for Government Communication and Information under the President of the Russian Federation with the participation of the All-Russia Scientific and Research Institute of Standardization.
GOST R 34.10-2001 was submitted by Federal Agency for Government Communication and Information at President of the Russian Federation.
2. GOST R 34.10-2001 was accepted and activated by the Act 380-st of 12.09.2001 issued by the Government Committee of Russia for Standards.
3. GOST R 34.10-2001 was developed in accordance with the terminology and concepts of international standards ISO 2382-2:1976 "Data processing - Vocabulary - Part 2: Arithmetic and logic operations"; ISO/IEC 9796:1991 "Information technology -- Security techniques -- Digital signature schemes giving message recovery"; ISO/IEC 14888 "Information technology - Security techniques - Digital signatures with appendix"; and ISO/IEC 10118 "Information technology - Security techniques - Hash-functions".
GOST R 34.10-2001 describes the generation and verification processes for digital signatures, based on operations with an elliptic curve points group, defined over a prime finite field.
GOST R 34.10-2001 has been developed to replace GOST R 34.10-94. Necessity for this development is caused by the need to increase digital signature security against unauthorized modification. Digital signature security is based on the complexity of discrete logarithm calculation in an elliptic curve points group and also on the security of the hash function used (according to [GOST3411]).
Terminologically and conceptually, GOST R 34.10-2001 is in accordance with international standards ISO 2382-2 [ISO2382-2], ISO/IEC 9796 [ISO9796-1991], ISO/IEC 14888 Parts 1-3 [ISO14888-1]-[ISO14888-3], and ISO/IEC 10118 Parts 1-4 [ISO10118-1]-[ISO10118-4].
Note: the main part of GOST R 34.10-2001 is supplemented with three appendixes:
Dolmatov Informational [Page 3]
RFC 5832 GOST R 34.10-2001 March 2010
"Extra Terms in the Digital Signature Area" (Appendix A of this memo);
GOST R 34.10-2001 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 a digital signature based on GOST R 34.10-2001 makes transmitted messages more resistant to forgery and loss of integrity, in comparison with the digital signature scheme prescribed by the previous standard.
GOST R 34.10-2001 is obligatory to use in the Russian Federation in all data processing systems providing public services.
Appendix: Bit string, formed by a digital signature and by the arbitrary text field [ISO14888-1].
Signature key: Element of secret data, specific to the subject and used only by this subject during the signature generation process [ISO14888-1].
Verification key: Element of data mathematically linked to the signature key data element, used by the verifier during the digital signature verification process [ISO14888-1].
Domain parameter: Element of data that is common for all the subjects of the digital signature scheme, known or accessible to all the subjects [ISO14888-1].
Signed message: A set of data elements, which consists of the message and the appendix, which is a part of the message.
Dolmatov Informational [Page 4]
RFC 5832 GOST R 34.10-2001 March 2010
Pseudo-random number sequence: A sequence of numbers, which is obtained during some arithmetic (calculation) process, used in a specific case instead of a true random number sequence [ISO2382-2].
Random number sequence: A sequence of numbers none of which can be predicted (calculated) using only the preceding numbers of the same sequence [ISO2382-2].
Verification process: A process that uses the signed message, the verification key, and the digital signature scheme parameters as initial data and that gives the conclusion about digital signature validity or invalidity as a result [ISO14888-1].
Signature generation process: A process that uses the message, the signature key, and the digital signature scheme parameters as initial data and that generates the digital signature as the result [ISO14888-1].
Witness: Element of data (resulting from the verification process) that states to the verifier whether the digital signature is valid or invalid [ISO148881-1]).
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 [ISO2382-2].
Message: String of bits of a limited length [ISO9796-1991].
Hash code: String of bits that is a result of the hash function [ISO148881-1].
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 pre- image of the given function value;
2) it is difficult to find another input data that is the pre- image of the same function value as is the given input data;
3) it is difficult to find a pair of different input data, producing the same hash function value.
Note: 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 (falsified) message that produces the same digital signature
Dolmatov Informational [Page 5]
RFC 5832 GOST R 34.10-2001 March 2010
as a given message; property 3 means that it is difficult to find some pair of different messages, which both produce the same signature.
(Electronic) Digital signature: String of bits obtained as a result of the signature generation process. This string has an internal structure, depending on the specific signature generation mechanism.
Note: In GOST R 34.10-2001 terms, "Digital signature" and "Electronic digital signature" are synonymous to save terminological succession to native legal documents currently in force and scientific publications.
A commonly accepted digital signature scheme (model) (see Section 6 of [ISO/IEC14888-1]) 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.10-2001, 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 the realization of two main processes (see Section 7):
The digital signature is meant for the authentication of the signatory of the electronic message. Besides, 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 Figure 1.
Dolmatov Informational [Page 7]
RFC 5832 GOST R 34.10-2001 March 2010
appendix | +-------------------------------+ | | +-----------+ +------------------------+- - - + | message M |---| digital signature zeta | text | +-----------+ +------------------------+- - - +
Figure 1: Signed message scheme
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.10-2001 must be implemented using operations of the 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 the complexity of solving the problem of the calculation of the discrete logarithm in the 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 Section 5.2.
GOST R 34.10-2001 does not determine the process of generating parameters needed for the digital signature scheme. Possible sets of these parameters are defined, for example, in [RFC4357].
The digital signature represented as a binary vector of a 512-bit length must be calculated using a definite set of rules, as stated in Section 6.1.
The digital signature of the received message is accepted or denied in accordance with the set of rules, as stated in Section 6.2.
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.
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:
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 y-coordinates 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 y-coordinates 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 congruencies:
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 y- coordinates. 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)
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 the introduced addition operation. For m, the following inequalities 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:
- prime number p is an elliptic curve modulus, satisfying the inequality p > 2^255. The upper bound for this number must be determined for the specific realization of the 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:
Dolmatov Informational [Page 10]
RFC 5832 GOST R 34.10-2001 March 2010
| 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 a 256-bit length. 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.
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.
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 a 256-bit length.
Consider the following binary vector of a 256-bit length where low- order bits are placed on the right, and high-order 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:
H1||H2 = (alpha[255], ... , alpha[0], beta[255], ..., beta[0]) (13) that is a binary vector of 512-bit length, 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 512-bit length into two binary vectors of 256-bit length, where H is the concatenation of the two.
In this section, the digital signature generation and verification processes of user's message are defined.
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.
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.
Dolmatov Informational [Page 12]
RFC 5832 GOST R 34.10-2001 March 2010
Step 3 - generate a random (pseudorandom) integer k, satisfying the inequality:
Step 4 - calculate the elliptic curve point C = k*P and determine if:
r = x_C (mod q), (17)
where x_C is x-coordinate 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 a 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.
To verify digital signatures for the received message M belonging to V_all, it is necessary to perform the following actions (steps) according to Algorithm II:
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. Otherwise, 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 if:
e = alpha (mod q). (20)
If e = 0, then assign e = 1.
Step 4 - calculate the value v = e^(-1) (mod q). (21)
Dolmatov Informational [Page 13]
RFC 5832 GOST R 34.10-2001 March 2010
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 if:
R = x_C (mod q), (23)
where x_C is x-coordinate of the point.
Step 7 - if the equality R = r holds, then the signature is accepted. Otherwise, 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.
This section is included in GOST R 34.10-2001 as a reference appendix but is not officially mentioned as 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 the correctness of actual realizations of the algorithms described in GOST R 34.10-2001.
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, respectively.
This entire document is about security considerations.
Current cryptographic resistance of GOST R 34.10-2001 digital signature algorithm is estimated as 2^128 operations of multiple elliptic curve point computations on prime modulus of order 2^256.
[GOST3410] "Information technology. Cryptographic data security. Signature and verification processes of [electronic] digital signature.", GOST R 34.10-2001, Gosudarstvennyi Standard of Russian Federation, Government Committee of Russia for Standards, 2001. (In Russian)
[GOST3411] "Information technology. Cryptographic Data Security. Hashing function.", GOST R 34.10-94, Gosudarstvennyi Standard of Russian Federation, Government Committee of Russia for Standards, 1994. (In Russian)
[RFC4357] Popov, V., Kurepkin, I., and S. Leontiev, "Additional Cryptographic Algorithms for Use with GOST 28147-89, GOST R 34.10-94, GOST R 34.10-2001, and GOST R 34.11-94 Algorithms", RFC 4357, January 2006.
[ISO10118-4] ISO/IEC 10118-4 (1998), "Information technology - Security techniques - Hash-functions - Part 4: Hash- functions using modular arithmetic".
Dolmatov Informational [Page 20]
RFC 5832 GOST R 34.10-2001 March 2010
Appendix A. Extra Terms in the Digital Signature Area
The appendix gives extra international terms applied in the considered and allied areas.
1. Padding: Extending a data string with extra bits [ISO10118-1].
2. Identification data: A list of data elements, including specific object identifier, that belongs to the object and is used for its denotation [ISO14888-1].
3. Signature equation: An equation, defined by the digital signature function [ISO14888-1].
4. Verification function: A verification process function, defined by the verification key, which outputs a witness of the signature authenticity [ISO14888-1].
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 pseudo-random number sequence generator (randomizer), and outputs the second part of the digital signature.