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

"Paterson, Kenny" <> Wed, 28 January 2015 10:32 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id AC8911A039A for <>; Wed, 28 Jan 2015 02:32:56 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -0.202
X-Spam-Status: No, score=-0.202 tagged_above=-999 required=5 tests=[BAYES_05=-0.5, MIME_8BIT_HEADER=0.3, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id KvBMp2HVMQ9h for <>; Wed, 28 Jan 2015 02:32:54 -0800 (PST)
Received: from ( [IPv6:2a01:111:f400:fe00::649]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-SHA384 (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id B87D51A0211 for <>; Wed, 28 Jan 2015 02:32:53 -0800 (PST)
Received: from ( by ( with Microsoft SMTP Server (TLS) id; Wed, 28 Jan 2015 10:32:29 +0000
Received: from ([]) by ([]) with mapi id 15.01.0065.013; Wed, 28 Jan 2015 10:32:29 +0000
From: "Paterson, Kenny" <>
To: Станислав Смышляев <>, "" <>
Thread-Topic: [Cfrg] 512-bit twisted Edwards curve and curve generation methods in Russian standardization
Thread-Index: AQHQOkpgQWElPvL0/EaQwowVk8M5cZzVVs2A
Date: Wed, 28 Jan 2015 10:32:29 +0000
Message-ID: <>
References: <>
In-Reply-To: <>
Accept-Language: en-GB, en-US
Content-Language: en-US
user-agent: Microsoft-MacOutlook/
x-originating-ip: []
authentication-results:; dkim=none (message not signed) header.d=none;; dmarc=none action=none;
x-dmarcaction-test: None
x-microsoft-antispam: BCL:0;PCL:0;RULEID:(3005004);SRVR:DBXPR03MB382;
x-exchange-antispam-report-test: UriScan:;
x-exchange-antispam-report-cfa-test: BCL:0;PCL:0;RULEID:;SRVR:DBXPR03MB382;
x-forefront-prvs: 047001DADA
x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(6009001)(24454002)(66654002)(479174004)(51704005)(52604005)(107886001)(106116001)(15975445007)(77096005)(102836002)(77156002)(62966003)(2900100001)(19580405001)(19580395003)(83506001)(2950100001)(40100003)(122556002)(575784001)(86362001)(15395725005)(87936001)(2656002)(4477795004)(66066001)(2501002)(74482002)(92566002)(46102003)(50986999)(54356999)(76176999)(36756003)(15198665003); DIR:OUT; SFP:1101; SCL:1; SRVR:DBXPR03MB382;; FPR:; SPF:None; MLV:sfv; LANG:en;
Content-Type: text/plain; charset="windows-1251"
Content-ID: <>
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-MS-Exchange-CrossTenant-originalarrivaltime: 28 Jan 2015 10:32:29.1822 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 2efd699a-1922-4e69-b601-108008d28a2e
X-MS-Exchange-Transport-CrossTenantHeadersStamped: DBXPR03MB382
Archived-At: <>
Subject: Re: [Cfrg] 512-bit twisted Edwards curve and curve generation methods in Russian standardization
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 10:32:56 -0000

Dear Stanislav,

Many thanks for sharing this detailed information.

In the current draft
(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.


Kenny (for the chairs)

On 27/01/2015 15:57, "Станислав Смышляев" <> 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
> Committee for Standardization «Cryptography and Security Mechanisms»
>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 = 
>d = 
>e = 0x1
>m = 
>q = 
>u(P) = 0x12
>v(P) = 
>a = 
>b = 
>x(P) = 
>y(P) = 
>(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:
> curve points group order has a prime factor of:
>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”,
> 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
>GOST R 34.11-2012 (Streebog) implementation can be found at
>, 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