Source: http://www.h-online.com/nettools/rfc/drafts/draft-dolmatov-gost34102012-00.shtml
Timestamp: 2013-12-19 00:36:08
Document Index: 188329411

Matched Legal Cases: ['art 2', 'art 2', 'art 3', 'art 1', 'art 3', 'art 3', 'art 1', 'art 2', 'art 3', 'art 4']

GOST R 34.10-2012: Digital Signature Algorithm - The H Security: News and features
draft-dolmatov-gost34102012-00:GOST R 34.10-2012: Digital Signature Algorithm
Author(s): Alexey Degtyarev, Vasily Dolmatov
This document is intended to be a source of information about the Russian Federal standard for digital signatures (GOST R 34.10-2012), which is one of the Russian cryptographic standard algorithms (called GOST algorithms). Recently, Russian cryptography is being...
INTERNET-DRAFT                                          V. Dolmatov, Ed.
Intended Status: Informational                           Cryptocom, Ltd.
Expires: November 21, 2013                                  A. Degtyarev
Cryptocom, Ltd.
May  21, 2013
GOST R 34.10-2012: Digital Signature Algorithm
draft-dolmatov-gost34102012-00
This document is intended to be a source of information about the
Russian Federal standard for digital signatures (GOST R 34.10-2012),
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-2012 for digital
signature generation and verification.
Dolmatov &amp; Degtyarev    Expires October 6, 2013                 [Page 1]
INTERNET DRAFT             GOST R 34.10-2012               May  21, 2013
1.1.  General Information  . . . . . . . . . . . . . . . . . . .  3
1.2.  The Purpose of GOST R 34.10-2012 . . . . . . . . . . . . .  3
2.  Scope  . . . . . . . . . . . . . . . . . . . . . . . . . . . .  3
3.  Terms, definitions and symbols . . . . . . . . . . . . . . . .  4
3.1.  Terms and definitions  . . . . . . . . . . . . . . . . . .  4
3.2.  Symbols  . . . . . . . . . . . . . . . . . . . . . . . . .  6
4.  General Statements . . . . . . . . . . . . . . . . . . . . . .  7
5.  Mathematical Conventions . . . . . . . . . . . . . . . . . . .  8
5.1.  Mathematical Definitions . . . . . . . . . . . . . . . . .  9
5.2.  Digital Signature Parameters . . . . . . . . . . . . . . . 11
5.3.  Binary Vectors . . . . . . . . . . . . . . . . . . . . . . 12
6.  Main Processes . . . . . . . . . . . . . . . . . . . . . . . . 12
6.1.  Digital Signature Generation Process . . . . . . . . . . . 13
6.2.  Digital Signature Verification . . . . . . . . . . . . . . 14
7.  Test Examples (Appendix to GOST R 34.10-2012)  . . . . . . . . 15
7.1.  The Digital Signature Scheme Parameters  . . . . . . . . . 15
7.2.  Digital Signature Process (Algorithm I)  . . . . . . . . . 17
7.3.  Verification Process of Digital Signature (Algorithm II) . 18
8.  Security Considerations  . . . . . . . . . . . . . . . . . . . 20
9.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 20
10.  References  . . . . . . . . . . . . . . . . . . . . . . . . . 20
10.1.  Normative References  . . . . . . . . . . . . . . . . . . 20
10.2.  Informative References  . . . . . . . . . . . . . . . . . 20
Author&#39;s Address . . . . . . . . . . . . . . . . . . . . . . . . . 22
Dolmatov &amp; Degtyarev    Expires October 6, 2013                 [Page 2]
1.1.  General Information
1. GOST R 34.10-2012 [GOST3410-2012] was developed by the Center for
Information Protection and Special Communications of the Federal
Security Service of the Russian Federation with participation of
the Open joint-stock company &quot;Information Technologies and
Communication Systems&quot; (InfoTeCS JSC).
2. GOST R 34.10-2012 was approved and introduced by Decree #215 of
the Federal Agency on Technical Regulating and Metrology on
3. GOST R 34.10-2012 intended to replace GOST R 34.10-2001
[GOST3410-2001] national standard of Russian Federation.
Terms and conceptions of this standard comply with International
standards ISO 2382-2 [ISO2382-2], ISO/IEC 9796 [ISO9796-2]
[ISO9796-3], series of standards ISO/IEC 14888 [ISO14888-1]
[ISO14888-2] [ISO14888-3] [ISO14888-4], and series of standards
ISO/IEC 10118 [ISO10118-1] [ISO10118-2] [ISO10118-3] [ISO10118-4].
1.2.  The Purpose of GOST R 34.10-2012
GOST R 34.10-2012 describes the generation and verification processes
for digital signatures, based on operations with an elliptic curve
points group, defined over a prime finite field.
Necessity for this standard development is caused by the need to
implement digital signature of varying resistance due to growth of
computer technology.  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 GOST R 34.11-2012 [GOST3411-2012]).
GOST R 34.10-2012 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-2012 makes
transmitted messages more resistant to forgery and loss of integrity,
in comparison with the digital signature scheme prescribed by the
previous standard.
Dolmatov &amp; Degtyarev    Expires October 6, 2013                 [Page 3]
GOST R 34.10-2012 is recommended to creation, operation and
modernization of data processing systems of various purpose.
3.  Terms, definitions and symbols
3.1.  Terms and definitions
The following terms are used in the standard:
3.1.1.  appendix: bit string, formed by a digital signature and by
the arbitrary text field. [ISO14888-1]
3.1.2.  signature key: element of secret data, specific to the
subject and used only by this subject during the signature
generation process. [ISO14888-1]
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. [ISO14888-1]
3.1.4.  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]
3.1.5.  signed message: a set of data elements, which consists of the
message and the appendix, which is a part of the message.
[ISO14888-1]
3.1.6.  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
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.
3.1.8.  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.
3.1.9.  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].
Dolmatov &amp; Degtyarev    Expires October 6, 2013                 [Page 4]
3.1.10.  witness: element of data that states to the verifier whether
the digital signature is valid or invalid.
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.
3.1.12.  message: string of bits of a limited length. [ISO14888-1]
3.1.13.  hash code: string of bits that is a result of the hash
function. [ISO14888-1]
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
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
3.  it is difficult to find a pair of different input data,
producing the same hash function value.
1.  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 as a given
message; property 3 means that it is difficult to find
some pair of different messages, which both produce the
same signature.
2.  in this standard terms &quot;hash function&quot;, &quot;cryptographic
hash function&quot;, &quot;hashing function&quot; and &quot;cryptographic
hashing function&quot; are synonymous to provide
terminological succession to native legal documents
currently in force and scientific publications.
3.1.15.  (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. [ISO14888-1]
Dolmatov &amp; Degtyarev    Expires October 6, 2013                 [Page 5]
1.  a string of bits that is signature may have internal
structure depending on specific mechanism of signature.
2.  In this standard terms &quot;electronic signature&quot;, &quot;digital
signature&quot; and &quot;electronic digital signature&quot; are
synonymous to provide terminological succession to
native legal documents currently in force and scientific
3.2.  Symbols
The following symbols are used in this standard:
V_l     set of all binary vectors of a l-bit length
V_all   set of all binary vectors of an arbitrary finite length
Z       set of all integers
p       prime number, p &gt; 3
GF(p)   finite prime field represented by a set of integers
{0, 1, ..., p - 1}
b (mod p)
minimal non-negative number, congruent to b modulo p
M       user&#39;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
Dolmatov &amp; Degtyarev    Expires October 6, 2013                 [Page 6]
zeta    digital signature for the message M
^       the power operator
/=      non-equality
sqrt    square root
4.  General Statements
A commonly accepted digital signature scheme (model) 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-2012, 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 (Section 6):
- signature generation (Section 6.1);
- signature verification (Section 6.2).
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
Dolmatov &amp; Degtyarev    Expires October 6, 2013                 [Page 7]
+-----------+   +------------------------+- - - +
| message M |---| digital signature zeta | text |
Figure 1: Signed message scheme
The field &quot;digital signature&quot; is supplemented by the field &quot;text&quot;,
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-2012 must be
implemented using operations of the elliptic curve points group,
defined over a finite prime field, and also with the use of hash
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 GOST R 34.11-2012 [GOST3411-2012].
The digital signature scheme parameters needed for signature
generation and verification are determined in Section 5.2.  This
standard provides the opportunity to select one of two options of
parameter requirements.
GOST R 34.10-2012 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 or
1024-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.
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.
Dolmatov &amp; Degtyarev    Expires October 6, 2013                 [Page 8]
5.1.  Mathematical Definitions
Suppose a prime number p &gt; 3 is given.  Then, an elliptic curve E,
defined over a finite prime field GF(p), is the set of number pairs
(x,y), where x and 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
4 * a^3
J(E) = 1728 * ------------------ (mod p)                          (2)
4 * a^3 + 27 * b^2
Elliptic curve E coefficients a, b are defined in the following way
using the invariant J(E):
| a = 3 * k (mod p),
|                                                                 (3)
| b = 2 * k (mod p),
where k = ----------- (mod p), J(E) /= 0 or 1728
1728 - J(E)
The pairs (x, y) satisfying the identity (1) are called &quot;the elliptic
curve E points&quot;; 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
On the set of all elliptic curve E points, we will define the
addition operation, denoted by &quot;+&quot;.  For two arbitrary elliptic curve
E points Q1 (x1, y1) and Q2 (x2, y2), we will consider several
Dolmatov &amp; Degtyarev    Expires October 6, 2013                 [Page 9]
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:
| x3 = lambda^2 - x1 - x2 (mod p),
|                                                                 (4)
| y3 = lambda * (x1 - x3) - y1 (mod p),
where lambda = -------- (mod p).
If x1 = x2 and y1 = y2 /= 0, then we will define point Q3 coordinates
| x3 = lambda^2 - x1 * 2 (mod p),
|                                                                 (5)
3 * x1^2 + a
where lambda = ------------ (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 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
p + 1 - 2 * sqrt(p) =&lt; m =&lt; p + 1 + 2 * sqrt(p)                   (7)
The point Q is called &quot;a point of multiplicity k&quot;, or just &quot;a
multiple point of the elliptic curve E&quot;, if for some point P the
following equality holds:
Q = P + ... + P = k * P                                           (8)
Dolmatov &amp; Degtyarev    Expires October 6, 2013                [Page 10]
5.2.  Digital Signature Parameters
The digital signature parameters are:
- prime number p is an elliptic curve modulus;
- 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 &gt;= 1
|                                                                 (9)
| 2^254 &lt; q &lt; 2^256 or 2^508 &lt; q &lt; 2^512
- 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 -&gt; V_l, which maps the messages
represented as binary vectors of arbitrary finite length onto
binary vectors of a l-bit length.  The hash function is
determined in GOST R 34.11-2012 [GOST3411-2012].
If 2^254 &lt; q &lt; 2^256 then l = 256.
If 2^508 &lt; q &lt; 2^512 then l = 512.
Every user of the digital signature scheme must have its personal
- signature key, which is an integer d, satisfying the inequality
0 &lt; d &lt; 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
- it is necessary that the condition p^t /= 1 (mod q) holds for
all integers t = 1, 2, ..., B, where
B = 31  if 2^254 &lt; q &lt; 2^256, or
B = 131 if 2^508 &lt; q &lt; 2^512;
- it is necessary that the inequality m /= p holds;
Dolmatov &amp; Degtyarev    Expires October 6, 2013                [Page 11]
- 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 a l-bit length.
Consider the following binary vector of a l-bit length where low-
order bits are placed on the right, and high-order ones are placed on
H = (alpha[l-1], ..., alpha[0]), H belongs to V_l                (10)
where alpha[i], i = 0, ..., l-1 are equal to 1 or to 0.  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[l-1]*2^(l-1)   (11)
For two binary vectors H1 and H2:
H1 = (alpha[l-1], ..., alpha[0]),
H2 = (beta[l-1], ..., beta[0]),
which correspond to integers alpha and beta, we define a
concatenation (union) operation in the following way:
H1||H2 = (alpha[l-1], ..., alpha[0], beta[l-1], ..., beta[0])    (13)
that is a binary vector of 2*l-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 2*l-bit length into two binary vectors of l-bit
length, where H is the concatenation of the two.
6.  Main Processes
In this section, the digital signature generation and verification
processes of user&#39;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.
Dolmatov &amp; Degtyarev    Expires October 6, 2013                [Page 12]
Besides, every user must have the signature key d and the
verification key Q(x_q, y_q), which also must satisfy the
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
0 &lt; k &lt; q.                                              (16)
Step 4.  Calculate the elliptic curve point C = k * P and determine:
r = x_C (mod q),                                        (17)
where x_C is x-coordinate of the point C.  If r = 0, return
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
Dolmatov &amp; Degtyarev    Expires October 6, 2013                [Page 13]
6.2.  Digital Signature Verification
To verify digital signature for the received message M, it is
necessary to perform the following actions (steps) according to
Step 1.  Calculate the integers r and s using the received signature
zeta.  If the inequalities 0 &lt; r &lt; q, 0 &lt; s &lt; 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)
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
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.
Dolmatov &amp; Degtyarev    Expires October 6, 2013                [Page 14]
7.  Test Examples (Appendix to GOST R 34.10-2012)
This section is included in GOST R 34.10-2012 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-2012.
All numerical values are introduced in decimal and hexadecimal
notations.  The numbers beginning with 0x are in hexadecimal
notation.  The symbol &quot;\\&quot; denotes a hyphenation of a number to the
next line.  For example, the notation:
represents 1234567890 in decimal and hexadecimal number systems,
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
7.1.2.  Elliptic Curve Coefficients
Parameters a and b take the following values in this example:
a = 0x7
b = 43308876546767276905765904595650931995\\
942111794451039583252968842033849580414
Dolmatov &amp; Degtyarev    Expires October 6, 2013                [Page 15]
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\\
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
d = 0x7A929ADE789BB9BE10ED359DD39A72C\\
11B60961F49397EEE1D19CE9891EC3B28
Dolmatov &amp; Degtyarev    Expires October 6, 2013                [Page 16]
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 steps 1-3, according to Algorithm I (Section 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
Dolmatov &amp; Degtyarev    Expires October 6, 2013                [Page 17]
Parameter r = x_C (mod q) takes the value:
r = 297009809158179528743712049839382569\\
r = 0x41AA28D2F1AB148280CD9ED56FED\\
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 steps 1-3, according to Algorithm II (Section
6.2), are performed, the following numerical value is obtained:
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
z1 = 376991675009019385568410572935126561\\
08841345190491942619304532412743720999759
z1 = 0x5358F8FFB38F7C09ABC782A2DF2A\\
3927DA4077D07205F763682F3A76C9019B4F
z2 = 141719984273434721125159179695007657\\
6924665583897286211449993265333367109221
Dolmatov &amp; Degtyarev    Expires October 6, 2013                [Page 18]
z2 = 0x3221B4FBBF6D101074EC14AFAC2D4F7\\
EFAC4CF9FEC1ED11BAE336D27D527665
The point C = z1 * P + z2 * Q has the coordinates:
x_C = 2970098091581795287437120498393825699\\
0422752107994319651632687982059210933395
y[C] = 3284253527868466347709466532251708450\\
6804721032454543268132854556539274060910
Then the parameter R = x_C (mod q) takes the value:
R = 2970098091581795287437120498393825699\\
Since the equality R = r holds, the digital signature is accepted.
Dolmatov &amp; Degtyarev    Expires October 6, 2013                [Page 19]
[GOST3410-2001]  &quot;Information technology.  Cryptographic data
security.  Signature and verification processes of
[electronic] digital signature.&quot;, GOST R 34.10-2001,
Gosudarstvennyi Standard of Russian Federation,
Government Committee of Russia for Standards, 2001.
[GOST3410-2012]  &quot;Information technology.  Cryptographic data
[electronic] digital signature.&quot;, GOST R 34.10-2012,
Federal Agency on Technical Regulating and
Metrology, 2012.
[GOST3411-2012]  &quot;Information technology.  Cryptographic Data
Security.  Hashing function.&quot;, GOST R 34.11-2012,
[RFC4357]        Popov, V., Kurepkin, I., and S. Leontiev,
&quot;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&quot;, RFC4357, January
[ISO2382-2]      ISO 2382-2:1976, &quot;Data processing - Vocabulary -
Part 2: Arithmetic and logic operations&quot;.
[ISO9796-2]      ISO/IEC 9796-2:2010, &quot;Information technology -
Security techniques - Digital signatures with
appendix - Part 2: Integer factorization based
mechanisms&quot;
Dolmatov &amp; Degtyarev    Expires October 6, 2013                [Page 20]
[ISO9796-3]      ISO/IEC 9796-3:2006, &quot;Information technology -
Security techniques - Digital signature schemes
giving message recovery - Part 3: Discrete logarithm
based mechanisms&quot;
[ISO14888-1]     ISO/IEC 14888-1:2008, &quot;Information technology -
appendix - Part 1: General&quot;.
[ISO14888-2]     ISO/IEC 14888-2:2008, &quot;Information technology -
mechanisms&quot;.
[ISO14888-3]     ISO/IEC 14888-3:2006, &quot;Information technology -
appendix - Part 3: Discrete logarithm based
[ISO14888-4]     ISO/IEC 14888-3:2006/Amd 1:2010, &quot;Information
technology - Security techniques - Digital
signatures with appendix - Part 3: Discrete
logarithm based mechanisms.  Ammendment 1.  Elliptic
Curve Russian Digital Signature Algorithm, Schnorr
Digital Signature Algorithm, Elliptic Curve Schnorr
Digital Signature Algorithm, and Elliptic Curve Full
Schnorr Digital Signature Algorithm&quot;
[ISO10118-1]     ISO/IEC 10118-1:2000, &quot;Information technology -
Security techniques - Hash-functions - Part 1:
General&quot;.
[ISO10118-2]     ISO/IEC 10118-2:2000, &quot;Information technology -
Security techniques - Hash-functions - Part 2: Hash-
functions using an n-bit block cipher algorithm&quot;.
[ISO10118-3]     ISO/IEC 10118-3:2004, &quot;Information technology -
Security techniques - Hash-functions - Part 3:
Dedicated hash-functions&quot;.
[ISO10118-4]     ISO/IEC 10118-4:1998, &quot;Information technology -
Security techniques - Hash-functions - Part 4: Hash-
functions using modular arithmetic&quot;.
Dolmatov &amp; Degtyarev    Expires October 6, 2013                [Page 21]
Vasily Dolmatov, Ed.
14 Kedrova St., Bldg. 2
EMail: dol@cryptocom.ru
EMail: degtyarev@cryptocom.ru
Dolmatov &amp; Degtyarev    Expires October 6, 2013                [Page 22]