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

"Stanislav V. Smyshlyaev" <smyshsv@gmail.com> Wed, 28 January 2015 17:46 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 D6E471A6EED for <cfrg@ietfa.amsl.com>; 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 <cfrg@ietfa.amsl.com>; 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 <cfrg@irtf.org>; Wed, 28 Jan 2015 09:45:59 -0800 (PST)
Received: by mail-ob0-f171.google.com with SMTP id va2so20572841obc.2 for <cfrg@irtf.org>; 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: <CACsn0cm4wrhH8xgbA3SxbfpZHn1SKJJN+Ch7Out8WViZ7s2PYw@mail.gmail.com>
References: <CAMr0u6=prmjMv7e+S5UAGVw+uCQWPk-f86Koa04GVx8CZs4J4Q@mail.gmail.com> <CACsn0cm4wrhH8xgbA3SxbfpZHn1SKJJN+Ch7Out8WViZ7s2PYw@mail.gmail.com>
Date: Wed, 28 Jan 2015 21:45:58 +0400
Message-ID: <CAMr0u6=avxwgcLSNUQiOYwhjob7BUnjWdHucEchH5C6MN4Y8_A@mail.gmail.com>
From: "Stanislav V. Smyshlyaev" <smyshsv@gmail.com>
To: Watson Ladd <watsonbladd@gmail.com>
Content-Type: multipart/alternative; boundary="001a11c2cb9ab067ad050db9f197"
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/JZZi0iKy3N-nJqub4Z-DKJZwaI8>
Cc: "cfrg@irtf.org" <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 <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: Wed, 28 Jan 2015 17:46:02 -0000

For a very simple reason – our Russian GOST signature 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, "Станислав Смышляев" <smyshsv@gmail.com> 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 =
> 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC7
>
> This prime is not as fast on many platforms as p=2^521-1. Why was it
> selected?
>
> >
> > 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
> >
> >
> >
> > _______________________________________________
> > Cfrg mailing list
> > Cfrg@irtf.org
> > http://www.irtf.org/mailman/listinfo/cfrg
> >
>