Re: [Cfrg] On the use of Montgomery form curves for key agreement

Andrey Jivsov <crypto@brainhub.org> Fri, 12 September 2014 08:06 UTC

Return-Path: <crypto@brainhub.org>
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 B60BC1A0665 for <cfrg@ietfa.amsl.com>; Fri, 12 Sep 2014 01:06:41 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 1.12
X-Spam-Level: *
X-Spam-Status: No, score=1.12 tagged_above=-999 required=5 tests=[BAYES_40=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, SPF_PASS=-0.001, URI_HEX=1.122] 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 oZw30-wbbyEs for <cfrg@ietfa.amsl.com>; Fri, 12 Sep 2014 01:06:37 -0700 (PDT)
Received: from resqmta-po-07v.sys.comcast.net (resqmta-po-07v.sys.comcast.net [IPv6:2001:558:fe16:19:96:114:154:166]) (using TLSv1 with cipher DHE-RSA-AES128-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id C7B051A0676 for <cfrg@irtf.org>; Fri, 12 Sep 2014 01:06:37 -0700 (PDT)
Received: from omta10.emeryville.ca.mail.comcast.net ([76.96.30.28]) by resqmta-po-07v.sys.comcast.net with comcast id q86c1o0010cQ2SL0186dQ5; Fri, 12 Sep 2014 08:06:37 +0000
Received: from [192.168.1.2] ([71.202.164.227]) by omta10.emeryville.ca.mail.comcast.net with comcast id q86b1o0084uhcbK8W86bCu; Fri, 12 Sep 2014 08:06:36 +0000
Message-ID: <5412A98B.4020103@brainhub.org>
Date: Fri, 12 Sep 2014 01:06:35 -0700
From: Andrey Jivsov <crypto@brainhub.org>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.7.0
MIME-Version: 1.0
To: cfrg@irtf.org
References: <e16ac4926a934565a65456058e50b68e@BL2PR03MB242.namprd03.prod.outlook.com> <CALCETrUby2o5O3=tMkv20JTVkahSo5Wan4oSCPOspRnXhFCg+g@mail.gmail.com> <b53e2c5417d247199f4496e0c0d5c29c@BL2PR03MB242.namprd03.prod.outlook.com> <CACsn0cktxTyPpeaqKU-oL+DiP4Fu0risHB1Wx8-by+94s30h=g@mail.gmail.com> <CA+Vbu7yMvyPzRAGrtVH38mzaYy3XQ1wswEUQisqbwpT10JfQVg@mail.gmail.com> <54058021.9040801@cs.tcd.ie> <CACsn0c=XV4bQSa7Oh3=s+JvFpJdT3Lm16wQHRG2ACEjxuU-dvg@mail.gmail.com> <5405E343.7010302@cs.tcd.ie> <5406387E.4060507@brainhub.org> <54063AEA.7060903@cs.tcd.ie> <54063D8B.7020302@brainhub.org> <CAK3OfOgJWkYS5NkO2ffJQshE8sO1hFu0UJGZ-akSs93PxSbTBw@mail.gmail.com> <5406584E.3060000@brainhub.org> <7B0EC922-D82E-441A-AC3C-B62C6A22ABC1@shiftleft.org>
In-Reply-To: <7B0EC922-D82E-441A-AC3C-B62C6A22ABC1@shiftleft.org>
Content-Type: text/plain; charset="UTF-8"; format="flowed"
Content-Transfer-Encoding: 8bit
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=comcast.net; s=q20140121; t=1410509197; bh=90x6ZZ/qMjMGiLigyz+KNxD+BXQtlt0j/yMjWUJGmls=; h=Received:Received:Message-ID:Date:From:MIME-Version:To:Subject: Content-Type; b=F9hm/K4MS9gor9P+pkVu8zxUPY1vYs3hvLSpkGAfnN6x11hOTp5Lku7JFp/f3P89P b3K0HwKDdxe7K0rdUxBc3Wa//k8ObPteYoNN+yst/G2aY6Zo9lsZe1y6UVlBdQTvYp 17kG8wWdsxuOMjoTiz0Gh/6pitJ+/Pk1M9IrNkA3gh+4NFiZr3uZlbIyY3MK+t2v81 RKjlBaOI6gUCUcnF4dhjNu7fTe+gN4WYXIJy6CjHjV7KFLRXRGfOZyJHEE4F0LPL7E SczDueAwVi3nTKE8T2LUM+G99ijmikh+3eGF5yhxWXd6ecZQNQzP4svz4HJtB7Gymh UIagDYmdoYXig==
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/bNHOiq6aZKBSsAuhaaMPO1h6oZ8
Subject: Re: [Cfrg] On the use of Montgomery form curves for key agreement
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: Fri, 12 Sep 2014 08:06:42 -0000

On 09/02/2014 05:20 PM, Michael Hamburg wrote:
> There isn’t actually a 10% penalty for switching forms unless you are
> translating between two different wire formats.  If one side or the
> other is internal to the application, it will be projective, which makes
> translation free unless the format is compressed.

[ http://www.ietf.org/mail-archive/web/cfrg/current/msg05045.html ]

I followed up on the idea that one can convert between Montgomery 
canonical compressed representation to Edwards projective coordinates 
without extra one or two inverses. Here are my notes, confirming the above.

To convert from Montgomery M(x,y): y^2 = x^3 + A*x^2 + x to -1 twisted 
Edwards coordinate (x_e,y_e) on the curve E(x,y): -x^2+y^2 = 1 + 
d*x^2*y^2 the following formula is used:

x_e = sqrt( -(A+2) ) * x / y
y_e = (x-1)/(x+1)

O = (0,0) for M
O = (0,1) for E, (0,-1) is exceptional

d = -(A-2)/(A+2)

y is not sent and we calculate it based on y_e and E(x,y) equation as 
follows:

x_e = sqrt( (y_e^2-1) / (d*y_e^2+1) )

The numerator and denominator in the above formula are:

y_e^2-1 = -4x = Y^2 - T^2
d*y_e^2+1 = d*Y^2+T^2

Y = x - 1
T = x + 1

This is x_e = sqrt( (T^2-Y^2)/(-dY^2-T^2) ) and this can be calculated 
in terms of Montgomery x at no additional cost, but this is not enough 
because y_e = Y/T would require an additional inverse. In addition, 
there may be a second extra inverse corresponding to the conversion back 
to the canonical representation.  These two inverses would have added 
20% performance penalty, a significant hit in some instances. For 
example, Curve25519 is 50% faster than NIST P-256 between openssl 
optimized for AVX2 v.s. curve25519-donna on the same modern x86_64 CPUs.

Fortunately, it is possible to avoid the overhead of conversion both ways:
* from affine Montgomery compressed coordinates (x only) to affine -1 
twisted Edwards  coordinates (from which one can use projective coordinates)
* from projective -1 twisted Endwards coordinates to Montgomery

First, let's look at conversion to Edwards affine coordinates. This 
conversion has a nice property that it's affine-to-affine.

The following 3 "tricks" will be used to accomplish this.

The simultaneous square root and inversion are explained in section 5 of 
http://ed25519.cr.yp.to/ed25519-20110705.pdf )

The "Montgomery trick" is easily generalized to any number of inverses 
as follows, shown for 3. To calculate 1/a, 1/b, 1/c, we do

t = 1/(abc), 1/a = bct, 1/b = act,  1/c = abt.

Also, sqrt(zz) = zz/sqrt(zz).

( See also http://moderncrypto.org/mail-archive/curves/2014/000064.html, 
http://www.ietf.org/mail-archive/web/cfrg/current/msg04800.html )

x_e = sqrt(T^2-Y^2) / sqrt(-dY^2-T^2) =
(T^2-Y^2) / sqrt( (T^2-Y^2)(-dY^2-T^2) )

With this in mind, here is the algorithm:

1. t = (T^2-Y^2)*(-d*Y^2-T^2) * T^2

2. tt = sqrt(1/t) ( paying the cost close to 1 inverse )

3. x_e = tt * (T^2-Y^2) * T

4. y_e = tt^2 * (T^2-Y^2)*(-d*Y^2-T^2) * T ( this is 1 / T )
    y_e = Y * y_e

5. Test that E(x_e,y_e)==0 (otherwise more thoughts are needed for point 
x validation and handling of O)

The sign of x_e will need to be adjusted, not discussed here.

Finally, the conversion back to Montgomery representation is simpler.

Let's assume that there is a projective (x/z, y/z) representation. 
(Other internal representations should work as well, as long as there is 
an inverse calculation to piggy-back on)

We know that Montgomery x is obtained from Edwards y_e as follows:

x = -(y_e+1)/(y_e-1).

To calculate affine y_e = y_e'/z_e' we calculate x directly from 
projective y_e' as follows:

x = - (y_e'+z_e')/(y_e'-z_e').

Thank you.