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

["Stanislav V. Smyshlyaev" <[e-mail]>]

Dear Kenny,

Thank you very much for your letter. We'll prepare and send our comments
for the current draft as soon as possible.

Best regards,

Stanislav V. Smyshlyaev, Ph.D.,

Head of Information Security Department,

CryptoPro LLC


2015-01-28 13:32 GMT+03:00 Paterson, Kenny <[e-mail]>:

> Dear Stanislav,
>
> Many thanks for sharing this detailed information.
>
> In the current draft https://tools.ietf.org/html/draft-agl-cfrgcurve-00
> (which CFRG has just adopted), we have a specific curve generation method
> that is different from the one you outline below. It has taken the group
> quite a bit of discussion to get to the point of having a rough consensus
> that that method is one we want to use, and if we decide to produce a
> higher security level curve (which I personally hope we will), then it
> seems pretty likely that this method will be the one we select.
>
> Perhaps I could encourage you to look at the current draft and engage with
> the editors on it where you see fit? Note that the draft should be
> evolving fairly rapidly in response to others' inputs and as we further
> develop it to include signatures, higher security level curves, etc.
>
> Regards,
>
> Kenny (for the chairs)
>
>
>
> On 27/01/2015 15:57, "Станислав Смышляев" <[e-mail]> 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 =
> >0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
> >FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC7
> >d =
> >0x9E4F5D8C017D8D9F13A5CF3CDF5BFE4DAB402D54198E31EBDE28A0621050439CA6B39E0A
> >515C06B304E2CE43E79E369E91A0CFC2BC2A22B4CA302DBB33EE7550
> >e = 0x1
> >m =
> >0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF26336E91
> >941AAC0130CEA7FD451D40B323B6A79E9DA6849A5188F3BD1FC08FB4
> >q =
> >0x3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC98CDBA4
> >6506AB004C33A9FF5147502CC8EDA9E7A769A12694623CEF47F023ED
> >u(P) = 0x12
> >v(P) =
> >0x469AF79D1FB1F5E16B99592B77A01E2A0FDFB0D01794368D9A56117F7B38669522DD4B65
> >0CF789EEBF068C5D139732F0905622C04B2BAAE7600303EE73001A3D
> >a =
> >0xDC9203E514A721875485A529D2C722FB187BC8980EB866644DE41C68E143064546E861C0
> >E2C9EDD92ADE71F46FCF50FF2AD97F951FDA9F2A2EB6546F39689BD3
> >b =
> >0xB4C4EE28CEBC6C2C8AC12952CF37F16AC7EFB6A9F69F4B57FFDA2E4F0DE5ADE038CBC2FF
> >F719D2C18DE0284B8BFEF3B52B8CC7A5F5BF0A3C8D2319A5312557E1
> >x(P) =
> >0xE2E31EDFC23DE7BDEBE241CE593EF5DE2295B7A9CBAEF021D385F7074CEA043AA27272A7
> >AE602BF2A7B9033DB9ED3610C6FB85487EAE97AAC5BC7928C1950148
> >
> >y(P) =
> >0xF5CE40D95B5EB899ABBCCFF5911CB8577939804D6527378B8C108C3D2090FF9BE18E2D33
> >E3021ED2EF32D85822423B6304F726AA854BAE07D0396E9A9ADDC40F
> >(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:
> >0x40000000000000000000000000000000000000000000000000000000000000003673245b
> >9af954ffb3cc5600aeb8afd33712561858965ed96b9dc310b80fdaf7, 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
> >
> >
> >
> >
> >
> >
>
>