Return-Path: X-Original-To: cfrg@ietfa.amsl.com Delivered-To: cfrg@ietfa.amsl.com Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id D6E471A6EED for ; Wed, 28 Jan 2015 09:46:01 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: 1.19 X-Spam-Level: * X-Spam-Status: No, score=1.19 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, FR_TEST_BASE64_BAD=3.189, HTML_MESSAGE=0.001, SPF_PASS=-0.001] autolearn=no Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 1EV9xyHwra2V for ; Wed, 28 Jan 2015 09:45:59 -0800 (PST) Received: from mail-ob0-x22b.google.com (mail-ob0-x22b.google.com [IPv6:2607:f8b0:4003:c01::22b]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 399D41A1EF9 for ; Wed, 28 Jan 2015 09:45:59 -0800 (PST) Received: by mail-ob0-f171.google.com with SMTP id va2so20572841obc.2 for ; Wed, 28 Jan 2015 09:45:58 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=GPihtQ0OKhx3tFpCJojybwQEYw6hgElqpLW7HF+/SMY=; b=lv2AHCbPPbJ/GWFTPVqBejRm6UIEgTrdJy+wshVXss/Ve3ZfhFY+XOdyaldbADOzlN Nkcpc2zda1wAp16WdJEoWbTNKaRojNb6/fbpn8LdpgZ2KWef2kbZHq6SLuWGgxny3PZU V2OhbwNnFi9RRsrrfzJPz41LdpmKgcfPE39zrbwJn1DmgfkC++kRBL+2+avfeJB0oX9x JHD9BJ2G32TG+Slx3QbMFr/SeBZbsHW63eE7/35lP8OADuYeoPXzIxx8z8yDbtEYT+o7 MQPiEF1F/PCm78n2g2FLEf+mm5uIlCzoHgn1aDMCrEm17PW02NPvG4V7OIx8m52gRON7 j6Fg== MIME-Version: 1.0 X-Received: by 10.182.33.138 with SMTP id r10mr2894333obi.67.1422467158532; Wed, 28 Jan 2015 09:45:58 -0800 (PST) Received: by 10.182.5.103 with HTTP; Wed, 28 Jan 2015 09:45:58 -0800 (PST) In-Reply-To: References: Date: Wed, 28 Jan 2015 21:45:58 +0400 Message-ID: From: "Stanislav V. Smyshlyaev" To: Watson Ladd Content-Type: multipart/alternative; boundary=001a11c2cb9ab067ad050db9f197 Archived-At: Cc: "cfrg@irtf.org" Subject: Re: [Cfrg] 512-bit twisted Edwards curve and curve generation methods in Russian standardization X-BeenThere: cfrg@irtf.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 28 Jan 2015 17:46:02 -0000 --001a11c2cb9ab067ad050db9f197 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable For a very simple reason =E2=80=93 our Russian GOST signature standard has = a requirement for q: q must be either 2^254: > > On Jan 27, 2015 8:00 AM, "=D0=A1=D1=82=D0=B0=D0=BD=D0=B8=D1=81=D0=BB=D0= =B0=D0=B2 =D0=A1=D0=BC=D1=8B=D1=88=D0=BB=D1=8F=D0=B5=D0=B2" 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 =C2=ABCryptography and Security > Mechanisms=C2=BB (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 fiel= d > GF(p), where p is equal to 2^512 =E2=80=93 569, p =3D 3 (mod 4). > > > > p =3D > 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF= FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC7 > > This prime is not as fast on many platforms as p=3D2^521-1. Why was it > selected? > > > > > d =3D > 0x9E4F5D8C017D8D9F13A5CF3CDF5BFE4DAB402D54198E31EBDE28A0621050439CA6B39E0= A515C06B304E2CE43E79E369E91A0CFC2BC2A22B4CA302DBB33EE7550 > > > > e =3D 0x1 > > > > m =3D > 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF26336E9= 1941AAC0130CEA7FD451D40B323B6A79E9DA6849A5188F3BD1FC08FB4 > > > > q =3D > 0x3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC98CDBA= 46506AB004C33A9FF5147502CC8EDA9E7A769A12694623CEF47F023ED > > > > u(P) =3D 0x12 > > > > v(P) =3D > 0x469AF79D1FB1F5E16B99592B77A01E2A0FDFB0D01794368D9A56117F7B38669522DD4B6= 50CF789EEBF068C5D139732F0905622C04B2BAAE7600303EE73001A3D > > > > a =3D > 0xDC9203E514A721875485A529D2C722FB187BC8980EB866644DE41C68E143064546E861C= 0E2C9EDD92ADE71F46FCF50FF2AD97F951FDA9F2A2EB6546F39689BD3 > > > > b =3D > 0xB4C4EE28CEBC6C2C8AC12952CF37F16AC7EFB6A9F69F4B57FFDA2E4F0DE5ADE038CBC2F= FF719D2C18DE0284B8BFEF3B52B8CC7A5F5BF0A3C8D2319A5312557E1 > > > > x(P) =3D > 0xE2E31EDFC23DE7BDEBE241CE593EF5DE2295B7A9CBAEF021D385F7074CEA043AA27272A= 7AE602BF2A7B9033DB9ED3610C6FB85487EAE97AAC5BC7928C1950148 > > > > y(P) =3D > 0xF5CE40D95B5EB899ABBCCFF5911CB8577939804D6527378B8C108C3D2090FF9BE18E2D3= 3E3021ED2EF32D85822423B6304F726AA854BAE07D0396E9A9ADDC40F > > > > (The following notation is used for Edwards curve coefficients: eu^2 + > v^2 =3D 1 + du^2v^2, while the corresponding Weierstrass curve has form y= ^2 =3D > 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: > 0x40000000000000000000000000000000000000000000000000000000000000003673245= b9af954ffb3cc5600aeb8afd33712561858965ed96b9dc310b80fdaf7, > while the other factor is equal to 4. > > > > > > > > The curve can be used both for digital signatures and for Diffie-Hellma= n > key agreement. > > > > > > > > The curve parameters have been generated using random nonce W in such > way that e =3D 1, d =3D hash(W), where hash() is Russian national standar= d GOST > R 34.11-2012 hash function (also known as =E2=80=9CStreebog=E2=80=9D, > https://www.streebog.net/en/). The seed value W is equal to: > > > > W =3D 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 5= E > AF FE C6 67 76 70 2E E2 C7 AA 84 16 07 50 DA 1D D1 50 AE D2 8C 30 26 AC 7= E > 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 government= al > 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 > > > --001a11c2cb9ab067ad050db9f197 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
For a very simple reason =E2=80=93 our Russian GOST signat= ure 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, "=D0=A1=D1=82=D0=B0=D0=BD=D0=B8=D1=81=D0=BB= =D0=B0=D0=B2 =D0=A1=D0=BC=D1=8B=D1=88=D0=BB=D1=8F=D0=B5=D0=B2" <smyshsv@gmail.com&g= t; wrote:
>
> Good afternoon, dear colleagues,
>
> =C2=A0
>
> Currently the proposed draft on elliptic curves generation methods doe= s not explicitly consider curves with security more than 256 bits.
>
> =C2=A0
>
> In Russia we have had a similar lack of 512-bit curves (both twisted E= dwards ones and curves with groups of prime order), so we at CryptoPro (Rus= sian cryptographic software company) proposed three of them to our Technica= l Committee for Standardization =C2=ABCryptography and Security Mechanisms= =C2=BB (http://tc26.ru/en/= ).
>
> =C2=A0
>
> In 2014 after a deep discussion with colleagues these curves were stan= dardized for usage with Russian national digital signature standard (GOST R= 34.10-2012).
>
> =C2=A0
>
> For example, the twisted Edwards 512-bit curve is defined over the fie= ld GF(p), where p is equal to 2^512 =E2=80=93 569, p =3D 3 (mod 4).
>
> p =3D 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF= FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC7

This prime is not as fast on many platforms as p=3D2^= 521-1. Why was it selected?

>
> d =3D 0x9E4F5D8C017D8D9F13A5CF3CDF5BFE4DAB402D54198E31EBDE28A062105043= 9CA6B39E0A515C06B304E2CE43E79E369E91A0CFC2BC2A22B4CA302DBB33EE7550
>
> e =3D 0x1
>
> m =3D 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF= FF26336E91941AAC0130CEA7FD451D40B323B6A79E9DA6849A5188F3BD1FC08FB4
>
> q =3D 0x3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF= FFC98CDBA46506AB004C33A9FF5147502CC8EDA9E7A769A12694623CEF47F023ED
>
> u(P) =3D 0x12
>
> v(P) =3D 0x469AF79D1FB1F5E16B99592B77A01E2A0FDFB0D01794368D9A56117F7B3= 8669522DD4B650CF789EEBF068C5D139732F0905622C04B2BAAE7600303EE73001A3D
>
> a =3D 0xDC9203E514A721875485A529D2C722FB187BC8980EB866644DE41C68E14306= 4546E861C0E2C9EDD92ADE71F46FCF50FF2AD97F951FDA9F2A2EB6546F39689BD3
>
> b =3D 0xB4C4EE28CEBC6C2C8AC12952CF37F16AC7EFB6A9F69F4B57FFDA2E4F0DE5AD= E038CBC2FFF719D2C18DE0284B8BFEF3B52B8CC7A5F5BF0A3C8D2319A5312557E1
>
> x(P) =3D 0xE2E31EDFC23DE7BDEBE241CE593EF5DE2295B7A9CBAEF021D385F7074CE= A043AA27272A7AE602BF2A7B9033DB9ED3610C6FB85487EAE97AAC5BC7928C1950148
>
> y(P) =3D 0xF5CE40D95B5EB899ABBCCFF5911CB8577939804D6527378B8C108C3D209= 0FF9BE18E2D33E3021ED2EF32D85822423B6304F726AA854BAE07D0396E9A9ADDC40F
>
> (The following notation is used for Edwards curve coefficients: eu^2 += v^2 =3D 1 + du^2v^2, while the corresponding Weierstrass curve has form y^= 2 =3D x^3 + ax +b. We denote the total number of points on the curve as m a= nd 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.)
>
> =C2=A0
>
> p and q are prime. The curve has been examined to be secure against MO= V-attacks (thus it can be believed to be DDH-secure) and to satisfy CM-secu= rity requirements. Twisted curve security has also been studied: twisted cu= rve points group order has a prime factor of: 0x400000000000000000000000000= 00000000000000000000000000000000000003673245b9af954ffb3cc5600aeb8afd3371256= 1858965ed96b9dc310b80fdaf7, while the other factor is equal to 4.
>
> =C2=A0
>
> The curve can be used both for digital signatures and for Diffie-Hellm= an key agreement.
>
> =C2=A0
>
> The curve parameters have been generated using random nonce W in such = way that e =3D 1, d =3D hash(W), where hash() is Russian national standard = GOST R 34.11-2012 hash function (also known as =E2=80=9CStreebog=E2=80=9D, = https://www.stre= ebog.net/en/). The seed value W is equal to:
>
> W =3D 1F BB 79 69 B9 1B 3E A0 81 17 FB 10 74 BF BF 55 49 DD 66 07 63 F= 6 A5 AF 09 57 77 5B 66 4C B1 13 CF CB 91 C4 A7 7D 27 98 06 BC F2 4A 56 77 F= 2 5E AF FE C6 67 76 70 2E E2 C7 AA 84 16 07 50 DA 1D D1 50 AE D2 8C 30 26 A= C 7E D6 D1 9B 97 AC 2C B5 82 7C 00 03 18 47 13 53 5B FA 65 24 B3 E4 60 83,<= br> >
> =C2=A0
>
> GOST R 34.11-2012 (Streebog) implementation can be found at https://github.co= m/okazymyrov/stribog, for example.
>
> =C2=A0
>
> The base point has been selected as a point with the smallest u-coordi= nate, satisfying curve equation and having order equal to q.
>
> =C2=A0
>
> Also we have an agreed (with Russian cryptographic community, includin= g experts from other Russian companies, scientific community and government= al authorities) version of curve generation methods; if you consider it int= eresting, we could prepare an English translation in a couple of days.
>
> =C2=A0
>
> 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
>


--001a11c2cb9ab067ad050db9f197--