GOST R 34.10-2012

The GOST R is a set of standards of the Russian Federation (not to be confused with the GOST standards maintained by the Euro-Asian Council for Standardization). The name is an acronym for gosudarstvennyy standard, which means state standard [1]. The GOST R standards have employed elliptic curve cryptography since GOST R 34.10-2001 [2]. This standard doesn't specify any elliptic curve parameters or elliptic curve generation but describes the following security conditions for elliptic curves over 256-bit prime field used in ECC.

Security - 2001 version

• The order $n$ of the prime subgroup must satisfy $2^{254} \leq n \leq 2^{256}$.
• The embedding degree must be at least 32.
• The curve can't be anomalous.
• The $j$-invariant can't be 0 or 1728.

Since no curves were recommended, curves were then provided in 2006 in RFC [3], each of 256-bit length (CryptoPro-A, CryptoPro-B, CryptoPro-C). Although no method of generation was specified, these curves satisfy the recommended security conditions. In 2012 an updated standard GOST R 34.10-2012 was released [4]. The only notable difference from the previous version concerning elliptic curves was the introduction of 512-bit protocols. The security conditions were extended to:

Security - 2012 version

• The order $n$ of the prime subgroup must satisfy $2^{254} \leq n \leq 2^{256}$ for 256-bit curve and $2^{508} \leq n \leq 2^{512}$ for 512-bit curve.
• The embedding degree must be at least 32 for 256-bit curve and at least 132 for 512-bit curve.
• The curve can't be anomalous
• The $j$-invariant can't be 0 or 1728.

Finally, two 512-bit Weierstrass curves (512-paramSetA, 512-paramSetB), one 256-bit (256-paramSetA) and one 512-bit Edwards curve (512-paramSetC), were then adopted in [5] in 2016. Again, no method of generation was specified.

In [6], authors investigate russian standardized elliptic curves and show that all of the standardized curves were generated in the following way:

• Select $p$ that allows fast arithmetic
• Value h was acquired by hashing a random seed with the Streebog hash function [7].
• For the generation of twisted Edwards curve $eu^2+v^2=1+du^2v^2$ we put $e=1, d=h$. For the generation of Weierstrass curve $y^2=x^3+ax+b$, we put $a=-3$ and $b$ equal to any value such that $hb^2=a^3$.
• Check the security conditions (mentioned above)
• Basepoint is selected by iterating $x$ for Weierstrass and $u$ for twisted Edwards form from 0 until the point $(x,y)$ (or $(u,v)$) has order $n$.

The authors provide the seeds to support the claimed generation method but only for the twisted Edwards curves. As the authors do not consider the RFC document [3] as a standard (based on a private discussion with the authors), they did not claim anything about the generation method of the first three CryptoPro curves specified by the RFC. You can read our hypothesis about the generation method of these curves in our paper.