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

Станислав Смышляев <smyshsv@gmail.com> Tue, 27 January 2015 15:59 UTC

Return-Path: <smyshsv@gmail.com>
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 E5F5A1A1B35 for <cfrg@ietfa.amsl.com>; Tue, 27 Jan 2015 07:59:52 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.2
X-Spam-Level:
X-Spam-Status: No, score=0.2 tagged_above=-999 required=5 tests=[BAYES_40=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, MIME_8BIT_HEADER=0.3, 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 7m0F8Svos2fg for <cfrg@ietfa.amsl.com>; Tue, 27 Jan 2015 07:59:50 -0800 (PST)
Received: from mail-oi0-x235.google.com (mail-oi0-x235.google.com [IPv6:2607:f8b0:4003:c06::235]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 24A531A887A for <cfrg@irtf.org>; Tue, 27 Jan 2015 07:57:41 -0800 (PST)
Received: by mail-oi0-f53.google.com with SMTP id i138so12972264oig.12 for <cfrg@irtf.org>; Tue, 27 Jan 2015 07:57:40 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:date:message-id:subject:from:to:content-type; bh=Jp0aGeRpYZmcHoPOGYshUDckIkutvV6blsgjoRuKKsA=; b=0k0Q4dqy3B6Q/8mGra++9EndXby53nb+wiKq881gn5rKbTPsmFUWVB670+eCbda1dZ 1hHEDf4ulZGPT6s0k+2ugqWjbulvWsMAujiqsbV2XUBs/VzReTdZcupADhbykh9BXu91 DEBoJNpJfMwOk3edtHPXKBDonYyuXDTBkNo72itvp80Rjs232t3paATBqLVdrzekJZnF fsf9kRmEbLkleyl/q9iTVNHtowghqps364L9A4uF1EZ//Yf255oWFFmvplVvFfKqefA3 PtfXfkI9dxpMX33dPbCaFdGrXPnKNMBwlk79uTZecdhaMlYQLPP7OeaSY3zGy0qaERaH xVUA==
MIME-Version: 1.0
X-Received: by 10.60.123.14 with SMTP id lw14mr1210758oeb.31.1422374260414; Tue, 27 Jan 2015 07:57:40 -0800 (PST)
Received: by 10.182.5.103 with HTTP; Tue, 27 Jan 2015 07:57:40 -0800 (PST)
Date: Tue, 27 Jan 2015 18:57:40 +0300
Message-ID: <CAMr0u6=prmjMv7e+S5UAGVw+uCQWPk-f86Koa04GVx8CZs4J4Q@mail.gmail.com>
From: =?UTF-8?B?0KHRgtCw0L3QuNGB0LvQsNCyINCh0LzRi9GI0LvRj9C10LI=?= <smyshsv@gmail.com>
To: cfrg@irtf.org
Content-Type: multipart/alternative; boundary=047d7b5d47d8879ca4050da4500f
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/1L7W2lPu4MtcHOfjoTFn_mmGPG4>
Subject: [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 <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Tue, 27 Jan 2015 15:59:53 -0000

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

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