[Cfrg] 512-bit twisted Edwards curve and curve generation methods in Russian standardization

[Станислав Смышляев <[e-mail]>]

Good afternoon, dear colleagues,



Currently the proposed draft on elliptic curves generation methods does not
explicitly consider curves with security more than 256 bits.



In Russia we have had a similar lack of 512-bit curves (both twisted
Edwards ones and curves with groups of prime order), so we at CryptoPro
(Russian cryptographic software company) proposed three of them to our
Technical Committee for Standardization «Cryptography and Security
Mechanisms» (http://tc26.ru/en/).



In 2014 after a deep discussion with colleagues these curves were
standardized for usage with Russian national digital signature standard
(GOST R 34.10-2012).



For example, the twisted Edwards 512-bit curve is defined over the field
GF(p), where p is equal to 2^512 – 569, p = 3 (mod 4).

p =
0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC7

d =
0x9E4F5D8C017D8D9F13A5CF3CDF5BFE4DAB402D54198E31EBDE28A0621050439CA6B39E0A515C06B304E2CE43E79E369E91A0CFC2BC2A22B4CA302DBB33EE7550

e = 0x1

m =
0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF26336E91941AAC0130CEA7FD451D40B323B6A79E9DA6849A5188F3BD1FC08FB4

q =
0x3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC98CDBA46506AB004C33A9FF5147502CC8EDA9E7A769A12694623CEF47F023ED

u(P) = 0x12

v(P) =
0x469AF79D1FB1F5E16B99592B77A01E2A0FDFB0D01794368D9A56117F7B38669522DD4B650CF789EEBF068C5D139732F0905622C04B2BAAE7600303EE73001A3D

a =
0xDC9203E514A721875485A529D2C722FB187BC8980EB866644DE41C68E143064546E861C0E2C9EDD92ADE71F46FCF50FF2AD97F951FDA9F2A2EB6546F39689BD3

b =
0xB4C4EE28CEBC6C2C8AC12952CF37F16AC7EFB6A9F69F4B57FFDA2E4F0DE5ADE038CBC2FFF719D2C18DE0284B8BFEF3B52B8CC7A5F5BF0A3C8D2319A5312557E1

x(P) =
0xE2E31EDFC23DE7BDEBE241CE593EF5DE2295B7A9CBAEF021D385F7074CEA043AA27272A7AE602BF2A7B9033DB9ED3610C6FB85487EAE97AAC5BC7928C1950148


y(P) =
0xF5CE40D95B5EB899ABBCCFF5911CB8577939804D6527378B8C108C3D2090FF9BE18E2D33E3021ED2EF32D85822423B6304F726AA854BAE07D0396E9A9ADDC40F

(The following notation is used for Edwards curve coefficients: eu^2 + v^2
= 1 + du^2v^2, while the corresponding Weierstrass curve has form y^2 = x^3
+ ax +b. We denote the total number of points on the curve as m and prime
subgroup order as q. We denote base point as P; x(P), y(P) and u(P), v(P)
are respectively base point coordinates in Weierstrass and twisted Edwards
form.)



p and q are prime. The curve has been examined to be secure against
MOV-attacks (thus it can be believed to be DDH-secure) and to satisfy
CM-security requirements. Twisted curve security has also been studied:
twisted curve points group order has a prime factor of:
0x40000000000000000000000000000000000000000000000000000000000000003673245b9af954ffb3cc5600aeb8afd33712561858965ed96b9dc310b80fdaf7,
while the other factor is equal to 4.



The curve can be used both for digital signatures and for Diffie-Hellman
key agreement.



The curve parameters have been generated using random nonce W in such way
that e = 1, d = hash(W), where hash() is Russian national standard GOST R
34.11-2012 hash function (also known as “Streebog”,
https://www.streebog.net/en/). The seed value W is equal to:

W = 1F BB 79 69 B9 1B 3E A0 81 17 FB 10 74 BF BF 55 49 DD 66 07 63 F6 A5 AF
09 57 77 5B 66 4C B1 13 CF CB 91 C4 A7 7D 27 98 06 BC F2 4A 56 77 F2 5E AF
FE C6 67 76 70 2E E2 C7 AA 84 16 07 50 DA 1D D1 50 AE D2 8C 30 26 AC 7E D6
D1 9B 97 AC 2C B5 82 7C 00 03 18 47 13 53 5B FA 65 24 B3 E4 60 83,



GOST R 34.11-2012 (Streebog) implementation can be found at
https://github.com/okazymyrov/stribog, for example.



The base point has been selected as a point with the smallest u-coordinate,
satisfying curve equation and having order equal to q.



Also we have an agreed (with Russian cryptographic community, including
experts from other Russian companies, scientific community and governmental
authorities) version of curve generation methods; if you consider it
interesting, we could prepare an English translation in a couple of days.



Best regards,

Stanislav V. Smyshlyaev, Ph.D.,

Head of Information Security Department,

CryptoPro LLC