Subject: [Cfrg] Addition of elliptic curves that are compatible with Russian GOST

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Wed, 4 Feb 2015 10:57:19 +0300

Dear colleagues,

We kindly ask you to agree to add two Twisted Edwards curves with p =
2^{512}-d and p = 2^{256}-d to the proposed draft.

If you see it possible, we can generate these two curves ourselves –
completely with accordance to the method described in the current draft
(including deterministic "rigid" "non-random" method of curve search
process).

It can be done very quickly – we have a big interest in it, since only
curves with 2^{254}<q<2^{256} and 2^{508}<q<2^{512} are allowed with our
GOST and we want our Russian PKI standards to be as much connected with
international ones as possible.

P.S.: Description of our GOST can be found in ISO/IEC
14888-3:2006/Amd.1:2010(en) Information technology — Security techniques —
Digital signatures with appendix — Part 3: Discrete logarithm based
mechanisms AMENDMENT 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.

Best regards,
Stanislav V. Smyshlyaev, Ph.D.,
Head of Information Security Department,
CryptoPro LLC

---

From: Alyssa Rowan <[email-masked]>
Date: Wed, 04 Feb 2015 08:06:49 +0000

On 04/02/2015 07:57, Stanislav V. Smyshlyaev wrote:

> We kindly ask you to agree to add two Twisted Edwards curves with p
> = 2^{512}-d and p = 2^{256}-d to the proposed draft. […] It can be
> done very quickly – we have a big interest in it, since only curves
> with 2^{254}<q<2^{256} and 2^{508}<q<2^{512} are allowed with our
> GOST and we want our Russian PKI standards to be as much connected
> with international ones as possible.

Perhaps I'm confused. 2^255-19 is in that range, isn't it?

Do you have an issue with the curve we have generated?

- -- 
/akr

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Wed, 4 Feb 2015 12:00:03 +0300

Alyssa,

For the curve you generated:
order 2^252 + 0x14def9dea2f79cd65812631a5cf5d3ed

As I said earlier, we have a requirement of 2^{254}<q<2^{256} (where q is
the subgroup order).

Regards,

Stanislav

2015-02-04 11:06 GMT+03:00 Alyssa Rowan <[email-masked]>:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA512
>
> -----BEGIN PGP SIGNATURE-----
>
> iQIcBAEBCgAGBQJU0dMYAAoJEOyEjtkWi2t6UtwP+wei0KriODs+Stxn3qwG5mHC
> WC69j5u4zeOb7B/hcYWNVgYThaqQ26lzMF78/5YJo6b+UeyBkjVM6VJ7Tcpn3H9M
> ya/nD4mc6xm0JBpabGJaaD+J/hQ1W+NJ2fiMVKNurS4hhHVmXKBZOt51DryETXf8
> 5XYGxXckw7vMhda7c8EC3Jl/Rj+DPhYw5OVyHS1I83MQrPBs1Seki/tS70NSthih
> youuZ6O71FVtyBExkDFU38+/95BomAJwl2oX25dFomEqHJFI6fmf9MjGR6DnlSEX
> X7Jn8RzcbeC8OEk7zRFk2dBchdLD4RemQyRuu5VjzwjEIUt2ao6/sAV5+NSWAaN3
> PwLfbUIPO80JPbyueyiZ1Pr3KJXlBDvx0J8OONYvojQR2OPrg70fMoZv3IabcIZr
> IhTHlHYkz+CJaX8xDPiuoE1hsCg9U3sP29+qmWTRDsZWBeJ1oiJQoATEkwZGSGvZ
> vX+6OIVE08oaxEtgV8+JVuaTEJF0Ypxye+x/NQQGX71evCwTPQ6uOt/9/Mwg7ose
> toIPDHOmP7jzdt4Ctdwyhk3YRII4FWVJ9QtUVKX9SVJwnZLEukjLsefxe6bWIJca
> wcbaEyqWSPnGEuC2in1Fy/C8uOfb67KKIR44bqlsA4odTEP2q3QebCIPhLpEFr2O
> /GJCtfXttgoUyQRPXzRP
> =OfxW
> -----END PGP SIGNATURE-----
>

---

From: Alyssa Rowan <[email-masked]>
Date: Wed, 04 Feb 2015 09:06:37 +0000

>As I said earlier, we have a requirement of 2^{254}<q<2^{256} (where q

Oh, you meant the *order*, of course: sorry! I guess I was confused. :)

For my (small) part, I don't think I'd want to change the curve we have (international) consensus on to match a national standard, or really add more curves to this draft than are necessary.

If you want GOST primitives codified for your use, perhaps do an informational draft of your own?

- --
/akr

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 4 Feb 2015 12:15:39 +0200

> international ones as possible.

You mean applying the procedure described in the draft for 2^256-189
and 2^512-569?

Note that this has only 50/50 chances of working with lower-level
curve given the constraints on q (it will work on higher-level curve).

If it fails, then doing d'=1-d would give a curve with q>2^254 with
very high probability (AFAIK, the chance of failing is about 2^-120).

-Ilari