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

For a very simple reason – our Russian GOST signature standard has a
requirement for q: q must be either 2^254<q<2^256 or 2^508<q<2^512, where q
is the order of a cyclic subgroup.

Best regards,

Stanislav

2015-01-28 20:36 GMT+03:00 Watson Ladd <watsonbladd@gmail.com>:

>
> On Jan 27, 2015 8:00 AM, "Станислав Смышляев" <smyshsv@gmail.com> wrote:
> >
> > 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
>
> This prime is not as fast on many platforms as p=2^521-1. Why was it
> selected?
>
> >
> > 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
> >
> >
> >
> > _______________________________________________
> > Cfrg mailing list
> > Cfrg@irtf.org
> > http://www.irtf.org/mailman/listinfo/cfrg
> >
>