[Docs] [txt|pdf] [Tracker] [Email] [Nits]

Versions: 00 01 02 03 04 05 06 07 08 RFC 5832

Internet-Draft                                          V. Dolmatov, Ed.
Intended status: Informational                            Cryptocom Ltd.
Expires: December 17, 2009                                June 10, 2009


                        GOST R 34.10-2001
                   digital signature algorithm
              draft-dolmatov-cryptocom-gost34102001-00

Status of This Memo

   This Internet-Draft is submitted to IETF in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts 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.

   Internet-Drafts 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 Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt.

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.

   This Internet-Draft will expire on December 17, 2009.

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/license-info).
   Please review these documents carefully, as they describe your rights
   and restrictions with respect to this document.

Abstract

   This document is intended to be a source of information about the
   Russian Federal standard for for electronic digital signature
   generation and verification processes (GOST R 34.10-2001).
   GOST R 34.10-2001 is one of the official standards in the Russian
   cryptography, used in Russian algorithms (GOST algorithms).
   Recently, the Russian cryptography started to be used in
   different applications intended to work with the OpenSSL
   cryptographic library. Thus, this document has been created for the
   informational purposes for users of Russian cryptography.





V.Dolmatov              Expires December 17, 2009               [Page 1]

Internet-Draft                GOST R 3410-2001               10 June 2009

Table of Contents

   1. Introduction.....................................................2
      1.1. General information.........................................2
      1.2. The purpose of GOST R 34.10-2001............................3
      1.3. Terminology.................................................3
   2. Applicability....................................................3
   3. Legal references.................................................4
   4. Definitions and notations........................................4
      4.1. Definitions.................................................4
      4.2. Notations...................................................6
   5. General statements...............................................6
   6. Mathematical conventions.........................................8
      6.1. Mathematical definitions....................................8
      6.2. Digital signature parameters...............................10
      6.3. Binary vectors.............................................11
   7. Main processes..................................................11
      7.1. Digital signature generation process.......................12
      7.2. Digital signature verification.............................12
   Appendix A (for reference only) Extra terms in EDS area............13
   Appendix B (for reference only) Test example.......................14
      B.1. The digital signature scheme parameters....................14
      B.2. Digital signature process (Algorithm I)....................16
      B.3. Verification process of digital signature (Algorithm II)...17
   Appendix C (for reference only) The bibliography...................18
   Author's addresses ................................................19


1. Introduction

1.1. General information

   1. GOST 34.10-2001 was developed by the Federal Agency for Government
   Communication and Information at President of Russian Federation with
   participation of the All-Russia Scientific and Research Institute of
   Standardization.

   GOST 34.10-2001 was submitted by Federal Agency for Government
   Communication and Information at President of Russian Federation.

   2. GOST 34.11-94 was accepted and activated by the Act 380-st of
   12.09.2001 issued by the Russian federal committee for standards.

   3. GOST R 34.10-2001 was developed in accordance with terminology and
   concepts of international standards ISO 2382-2-76. "Data processing.
   Dictionary. Part 2. Arithmetic and logic operations", ISO/IEC 9796-91
   "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"


V.Dolmatov                Expires December 17, 2009             [Page 2]

Internet-Draft                GOST R 3410-2001              10 June 2009

4. GOST R 34.10-2001 replaces GOST R 34.10-94

1.2. The purpose of GOST R 34.10-2001

   GOST R 34.10-2001 describes generation and verification processes for
   electronic digital signature (EDS), based on operations with elliptic
   curve points group, defined over prime finite field.

   GOST R 34.10-2001 is developed to replace GOST R 34.10-94. Necessity
   for this development is caused by the need to increase the
   resistance of EDS against unauthorized modification. EDS resistance
   is based on complexity of discrete logarithm calculation in elliptic
   curve points group and also on resistance of hash function used
   (according to the GOST R 34.11).

   Terminologically and conceptually GOST R 34.10-2001 is in accord with
   international standards ISO 2382-2 [1], ISO/ IEC 9796 [2], series
   ISO/ IEC 14888 [3]-[5] and series ISO/ IEC 10118 [6]-[9].

   Note: the main part of the standard is supplemented with three
   appendixes:

   A - extra terms in EDS area;

   B - test example;

   C - a publications list (bibliography) in EDS area.

1.3.  Terminology

   In this document, the key words MUST, MUST NOT, REQUIRED, SHOULD,
   SHOULD NOT, RECOMMENDED, and MAY are to be interpreted as described
   in [RFC2119].

2. Applicability

   GOST R 34.10-2001 defines an electronic digital signature (EDS, 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.10-2001 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.10-2001 is obligatory to use in Russian Federation in all
   data processing systems providing public services.

V.Dolmatov                Expires December 17, 2009             [Page 3]

Internet-Draft                GOST R 3410-2001              10 June 2009

3. Legal references

   A reference to the following draft is used in this draft:

   GOST R 34.11-94 hash function algorithm

4. Definitions and notations

4.1. Definitions

   The following terms are used in the standard:

   4.1.1 appendix: Bit string, formed by digital signature and by
   arbitrary text field (ISO/IEC 148881-1 [3]).

   4.1.2 signature key: Element of secret data, specific to the subject
   and used only by this subject during the signature generation process
   (ISO/IEC 14888-1 [3]).

   4.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 14888-1 [3]).

   4.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 14888-1 [3]).

   4.1.5 signed message: A set of data elements, that consists of the
   message and the appendix, which is a part of the message.

   4.1.6 pseudo-random 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 2382-2
   [1]).

   4.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 2382-2 [1]).


   4.1.8 verification process: A process using the signed message, the
   verification key and EDS scheme parameters as initial data and giving
   the conclusion about digital signature validity or invalidity as a
   result. (ISO/IEC 14888-1 [3]).

   4.1.9 signature generation process: A process using the message, the
   signature key and EDS scheme parameters as initial data and
   generating the digital signature as the result (ISO/IEC 14888-1 [3]).

   4.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 148881-1 [3]).

V.Dolmatov                Expires December 17, 2009             [Page 4]

Internet-Draft                GOST R 3410-2001              10 June 2009

   4.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 2382-2 [1]).

   4.1.12 message: String of bits of a limited length (ISO/IEC 9796
   [2]).

   4.1.13 hash code: String of bits that is a result of the hash
   function (ISO/IEC 148881-1 [3]).

   4.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 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: The property 1 in the context of the EDS area means that it is
   impossible to recover the initial message using the EDS; property 2
   means that it is difficult to find another (falsificated) message
   that produces the same EDS; property 3 means that it is difficult to
   find some pair of different messages, that both produce the same
   signature.

   4.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.10-2001 terms "digital signature" and "electronic
   digital signature (EDS)" are synonymous to save terminological
   succession to native legal documents currently in force and
   scientific-technical publications.

4.2 Notations

   In GOST R 34.10-2001 the following notations are used:

V.Dolmatov                Expires December 17, 2009             [Page 5]

Internet-Draft                GOST R 3410-2001              10 June 2009

   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;

   ^ - the power operator;

   /= - non-equality;

   sqrt - square root;

   zeta - digital signature for the message M.

5 GENERAL STATEMENTS

   A commonly accepted digital signature scheme (model) (see 6 ISO/IEC
   14888-1 [3]) consists of three processes:

   - generation of a pair of keys (for signature generation and for
   signature verification);

   - signature generation;

   - signature verification.

V.Dolmatov                Expires December 17, 2009             [Page 6]

Internet-Draft                GOST R 3410-2001              10 June 2009


   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 realization of two main
   processes (see part 7):

   - signature generation (see. 7.1);

   - signature verification (see. 7.2).

   The digital signature is meant for authentication of the signatory of
   the electronic message. Besides, the EDS 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

   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 elliptic curve points group, defined
   over a finite prime field, and also with the use of hash function.

   The cryptographic resistance 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
   resistance of hash function used. The hash function calculation
   algorithm is determined in GOST R 34.11.

   The digital signature scheme parameters needed for signature
   generation and verification are determined in 6.2.

V.Dolmatov                Expires December 17, 2009             [Page 7]

Internet-Draft                GOST R 3410-2001              10 June 2009


   GOST R 34.10-2001 does not determine the process of generating
   parameters needed for digital signature scheme. The sets of these
   parameters are defined in RFC 4357.

   The digital signature represented as a binary vector of length 512
   bit, must be calculated using definite set of rules stated in 7.1.

   The digital signature of the received message is accepted or denied
   in accordance with the set of rules, stated in 7.2.

6. 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.

6.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 belongs to Fp , satisfying the identity

   y^2 = x^3 + ax + b(mod p),                                        (1)

   where a, b belong to GF(p) and 4a^3 + 27b^2 is not congruent to zero
   modulo p.

   An invariant of the elliptic curve is the quantity J(E) , satisfying
   the identity

                4a^3
   J(E)=1728------------(mod p)                                      (2)
             4a^3+27b^2

   Elliptic curve E coefficients a,b are defined in the following way
   using the invariant J(E):

   | a=3k(mod p)
   |                           J(E)
   | b=2k(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 or x- and y-coordinates of the point
   correspondingly.

V.Dolmatov                Expires December 17, 2009             [Page 8]

Internet-Draft                GOST R 3410-2001              10 June 2009


   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 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^2-x1-x2 (mod p),                  y1-y2
   |                              where lambda= ------- (mod p).     (4)
   | y3=lambda*(x1-x3)-y1 (mod p),               x1-x2


   If x1 = x2 and y1 = y2 /= 0, then we will define point Q3
   coordinates in a following way

   | x3=lambda^2-x1*2 (mod p),                    3x1^2+a
   |                               where lambda= --------- (mod p)   (5)
   | y3=lambda*(x1-x3)-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
   y-coordinates. In this case point Q2 is called a denial 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 introduced
   addition operation. The number m must satisfy the inequality

   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

V.Dolmatov                Expires December 17, 2009             [Page 9]

Internet-Draft                GOST R 3410-2001              10 June 2009

6.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 the GOST R 34.11.

   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.

   There are the following requirements for the previously introduced
   digital signature parameters:

   - 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.

6.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

V.Dolmatov                Expires December 17, 2009            [Page 10]

Internet-Draft                GOST R 3410-2001              10 June 2009


   binary vectors of length 256 bit.

   Consider the following binary vector of length 256 bit 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

   alpha = alpha[0]*2^0 + alpha[1]*2^1 + ... + alpha[256]*2^256.    (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
   _   _
   h1||h2 = (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.

7. Main processes

   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.



V.Dolmatov                Expires December 17, 2009            [Page 11]

Internet-Draft                GOST R 3410-2001              10 June 2009


7.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 - x-coordinate of the point C. If r = 0, return to step 3.

   Step 5 - calculate the quantity

   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.

7.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:

   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.


V.Dolmatov                Expires December 17, 2009            [Page 12]

Internet-Draft                GOST R 3410-2001              10 June 2009

   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 = 0, then assign = 1.

   Step 4 - calculate the quantity v = e^-1(mod q) .                (21)

   Step 5 - calculate the quantities

   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 - x-coordinate 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.

Appendix A (for reference only) Extra terms in EDS 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
   10118-1 [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 148881-1 [3]).

   3. signature equation: An equation, defined by the digital signature
   function (ISO/IEC 148881-1 [3]).

   4. verification function: A verification process function, defined by
   the verification key, which outputs a witness of the signature
   authenticity (ISO/IEC 148881-1 [3]).


V.Dolmatov                Expires December 17, 2009            [Page 13]

Internet-Draft                GOST R 3410-2001              10 June 2009

   5. signature function: A function within a signature generation
   process,defined by the signature key and by the EDS scheme
   parameters. This function inputs is a part of initial data and,
   probably, a pseudorandom number sequence generator (randomizer), and
   outputs the second part of the digital signature.

Appendix B (for reference only) Test example

   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 for testing the
   correctness of only the specific realization of the algorithms,
   described in GOST R 34.10-2001.

   All numerical values are introduced in decimal and hexadecimal
   notations. Lower index in number notation denotes a number system
   base. 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.

B.1 The digital signature scheme parameters

   The following parameters must be used for the digital signature
   generation and verification (see section 6.2).

B.1.1 Elliptic curve modulus

   The following value is assigned to parameter p in this example

   p= 57896044618658097711785492504343953926\\
   634992332820282019728792003956564821041

   p = 0x8000000000000000000000000000\\
   000000000000000000000000000000000431

B.1.2 Elliptic curve coefficients

   Parameters a and b take the following values in this example:

   a = 7

   a = 0x7


V.Dolmatov                Expires December 17, 2009            [Page 14]

Internet-Draft                GOST R 3410-2001              10 June 2009


   b = 43308876546767276905765904595650931995\\
   942111794451039583252968842033849580414

   b = 0x5FBFF498AA938CE739B8E022FBAFEF40563\\
   F6E6A3472FC2A514C0CE9DAE23B7E

B.1.3 Elliptic curve points group order

   Parameter m takes the following value in this example:

   m = 5789604461865809771178549250434395392\\
   7082934583725450622380973592137631069619

   m = 0x80000000000000000000000000000\\
   00150FE8A1892976154C59CFC193ACCF5B3

B.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

B.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

B.1.6 Signature key

   It is supposed in this example that the user has the following
   signature key d:

   d = 554411960653632461263556241303241831\\
   96576709222340016572108097750006097525544

   d = 0x7A929ADE789BB9BE10ED359DD39A72C\\
   11B60961F49397EEE1D19CE9891EC3B28

V.Dolmatov                Expires December 17, 2009            [Page 15]

Internet-Draft                GOST R 3410-2001              10 June 2009



B.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

B.2 Digital signature process (Algorithm I)

   Suppose that after 1-3 steps according to the Algorithm I (7.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



V.Dolmatov                Expires December 17, 2009            [Page 16]

Internet-Draft                GOST R 3410-2001              10 June 2009



   Parameter r = x_C(mod q) takes the value:

   r = 297009809158179528743712049839382569\\
   90422752107994319651632687982059210933395

   r = 0x41AA28D2F1AB148280CD9ED56FED\\
   A41974053554A42767B83AD043FD39DC0493

   Parameter s = (r*d + k*e)(mod q) takes the value:

   s = 57497340027008465417892531001914703\\
   8455227042649098563933718999175515839552

   s = 0x1456C64BA4642A1653C235A98A602\\
   49BCD6D3F746B631DF928014F6C5BF9C40

B.3 Verification process of digital signature (Algorithm II)

   Suppose that after the steps 1-3 according to the Algorithm II (7.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

   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\\
   EFAC4CF9FEC1ED11BAE336D27D52766516


V.Dolmatov                Expires December 17, 2009            [Page 17]

Internet-Draft                GOST R 3410-2001              10 June 2009


   The point C = z1*P + z2*Q has the coordinates:

   x_C = 2970098091581795287437120498393825699\\
   0422752107994319651632687982059210933395

   x_C = 0x41AA28D2F1AB148280CD9ED56FED\\
   A41974053554A42767B83AD043FD39DC0493

   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 C (for reference only) The bibliography

   [1] ISO 2382-2-76 Data processing. Dictionary. Part 2. Arithmetic and
   logic operations

   [2] ISO/IEC 9796-91 Information technology. Secure methods. Digital
   signature scheme with message recovering

   [3] ISO/IEC 14888-1-98 Information technology. Secure methods.
   Digital signatures and application. Part 1. General statements

   [4] ISO/IEC 14888-2-99 Information technology. Secure methods.
   Digital signatures and application. Part 2. Mechanisms on
   authentication base

   [5] ISO/IEC 14888-3-99 Information technology. Secure methods.
   Digital signatures and application. Part 3. Mechanisms on certificate
   base

   [6] ISO/IEC 10118-1-94 Information technology. Secure methods. Hash
   functions Part 1. General statements.

   [7] ISO/IEC 10118-2-94 Information technology. Secure methods. Hash
   functions Part 2. Hash functions using n-bit block encryption
   algorithm


V.Dolmatov                Expires December 17, 2009            [Page 18]
Internet-Draft                GOST R 3410-2001              10 June 2009


   [8] ISO/IEC 10118-3-98 Information technology. Secure methods. Hash
   functions Part 3. Decimal hash functions

   [9] ISO/IEC 10118-4-98 Information technology. Secure methods. Hash
   functions Part 4. Hash functions using modular arithmetic

   [10]Russian federal standard. Information technology. Cryptographic
   data security. Electronic digital signature generation and
   verification processes (in Russian)

Authors' Addresses

Vasily Dolmatov, Ed.
Cryptocom Ltd.
Bolotnikovskaya, 23
Moscow, 117303, Russian Federation

EMail: dol@cryptocom.ru

Dmitry Kabelev
Cryptocom Ltd.
Bolotnikovskaya, 23
Moscow, 117303, Russian Federation

EMail: kdb@cryptocom.ru

Igor Ustinov
Cryptocom Ltd.
Bolotnikovskaya, 23
Moscow, 117303, Russian Federation

EMail: igus@cryptocom.ru

Sergey Vyshensky
Moscow State University
Leninskie gory, 1
Moscow, 119991, Russian Federation

EMail: svysh@pn.sinp.msu.ru


Acknowledgement

   Funding for the RFC Editor function is provided by the IETF
   Administrative Support Activity (IASA).


Html markup produced by rfcmarkup 1.108, available from http://tools.ietf.org/tools/rfcmarkup/