### [Cfrg] Montgomery-form point formats for Edwards-form software

Robert Ransom <rransom.8774@gmail.com> Tue, 29 July 2014 13:52 UTC

Return-Path: <rransom.8774@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 48D6A1B2793
for <cfrg@ietfa.amsl.com>; Tue, 29 Jul 2014 06:52:38 -0700 (PDT)

X-Virus-Scanned: amavisd-new at amsl.com

X-Spam-Flag: NO

X-Spam-Score: -0.55

X-Spam-Level:

X-Spam-Status: No, score=-0.55 tagged_above=-999 required=5
tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
DKIM_VALID_AU=-0.1, FREEMAIL_ENVFROM_END_DIGIT=0.25,
FREEMAIL_FROM=0.001, J_CHICKENPOX_14=0.6, J_CHICKENPOX_15=0.6,
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 ZDFiHfXskmng for <cfrg@ietfa.amsl.com>;
Tue, 29 Jul 2014 06:52:34 -0700 (PDT)

Received: from mail-qg0-x233.google.com (mail-qg0-x233.google.com
[IPv6:2607:f8b0:400d:c04::233])
(using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits))
(No client certificate requested)
by ietfa.amsl.com (Postfix) with ESMTPS id 027541B2884
for <cfrg@irtf.org>; Tue, 29 Jul 2014 06:52:33 -0700 (PDT)

Received: by mail-qg0-f51.google.com with SMTP id a108so10535806qge.10
for <cfrg@irtf.org>; Tue, 29 Jul 2014 06:52:33 -0700 (PDT)

DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
h=mime-version:date:message-id:subject:from:to:cc:content-type
:content-transfer-encoding;
bh=bBpJDa1V6YxeNCUIX/SeMst3ueeeZsHsemWoQhNCIJg=;
b=PxP80vBVimaMLigLK5LdrvoN8zb4SVMlNFwLbIruog8+CS1dkvToRA/r/BMfpEXwWa
jhIJSnnK/hZzf1h9l6o9TMSChSCI6wn5+uL5H3hQK3QLRuZTqB9RJAP+TRwS4sPRVx05
5ONc/YU/4sNFzP9Pc+wECDY6wKxRY3VsYdNI4PNJlTD2LujtBbbJSE1szS52vNoXuFYD
b/jm0J/A8IGMQB2+LmX8DvtRxgGEoIlES2nkHJHWf05fSREguSP8fX0Id9p8q6LzR5WM
oFEWDonfihs70gHTbi/yMK3T5z1s37Dnf3V6ywBWCj1djuJmuNzZ6LUdPrUGUdNDTZQC
oYaA==

MIME-Version: 1.0

X-Received: by 10.229.67.69 with SMTP id q5mr3727051qci.25.1406641953227; Tue,
29 Jul 2014 06:52:33 -0700 (PDT)

Received: by 10.140.86.135 with HTTP; Tue, 29 Jul 2014 06:52:33 -0700 (PDT)

Date: Tue, 29 Jul 2014 06:52:33 -0700

Message-ID: <CABqy+sqKg=9UTYZdZM+Ac9wznUHUGzV1zB+RUrrjRU1+e3VJKg@mail.gmail.com>

From: Robert Ransom <rransom.8774@gmail.com>

To: Ilari Liusvaara <ilari.liusvaara@elisanet.fi>

Content-Type: text/plain; charset=UTF-8

Content-Transfer-Encoding: quoted-printable

Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/Cko4mRR94X0IrqpmYLG9jLAkVGM

Cc: "cfrg@irtf.org" <cfrg@irtf.org>

Subject: [Cfrg] Montgomery-form point formats for Edwards-form software

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, 29 Jul 2014 13:52:38 -0000

On 7/26/14, Ilari Liusvaara <ilari.liusvaara@elisanet.fi>; wrote: > On Fri, Jul 25, 2014 at 07:25:54PM -0700, Robert Ransom wrote: >> On 7/25/14, Watson Ladd <watsonbladd@gmail.com>; wrote: >> >> Affine Montgomery-form points can be unpacked to and packed from >> projective (optionally twisted) Edwards-form points at a trivial extra >> cost over unpacking from or packing to a compressed affine >> Edwards-form point. > > Do you mean Montgomery_x-only, or that (Montgomery_x, Edwards_x_sign) > representation? Yes. (Either representation -- one can trivially interpret the former as the latter and convert the latter to the former.) > If the latter, it is not at all obvious how to get both in just > one inversion (either can obviously be gotten in just one inversion, > as can full edwards affine form). First: * I'm going to state the unpacking and packing routines in terms of the P^1 * P^1 form of Edwards coordinates, in which Edwards x is represented as (X : Z) and Edwards y is represented as (Y : T). NOTE that the Hisil et al. ‘extended’ coordinates used in fast implementations use the same variable names with different meanings; those extended coordinates are what mathematicians call the ‘Segre embedding’ of the P^1 * P^1 form. Converting from P^1 * P^1 to Segre coordinates when one of X, Z and one of Y, T are each known to equal 1 costs 1M; converting to Segre when only one of X, Z, Y, T is known to be 1 costs 2M. Converting from P^1 * P^1 to Segre coordinates in general costs 3M, and this routine can be reused internally by the addition and doubling formulas. * I'm assuming a square-root-of-fraction routine (as described in the Ed25519 paper and used in Edwards-form point decompression) as a primitive, as well as a simultaneous-inversion routine (which computes the reciprocals of two coordinates at once, using ‘Montgomery's trick’). I assume that, as happens naturally in practice, both routines produce zero as their output(s) when either of their inputs is zero. If you haven't seen it before, Montgomery's simultaneous-inversion trick to invert e.g. a and b, assuming they are both non-zero, is as follows: ab := a*b abinv := 1/ab ainv := b*abinv binv := a*abinv * I'm assuming that points are encoded on a ‘complete’ Edwards curve, i.e. one which has no points at infinity over the base field (so that Z and T are non-zero when packing a point, and when unpacking a valid point). This is a good idea, for multiple reasons, even if the most efficient implementations will map points onto an incomplete Edwards curve internally before operating on them. Now, the routines: * Unpacking affine Montgomery form to projective Edwards form: u := Montgomery_x sx := Edwards_x_sign Y := u - 1 T := u + 1 f := T^2 - Y^2 g := a*T^2 - d*Y^2 X' := sqrt(f/g) if (X')^2*g != f, abort (Note: In practice, some Edwards-form implementations must decompress and operate on points on the twist as well; I'll post more details soon-ish.) X := adjust_sign(X', sx) Z := 1 * Packing projective Edwards form to affine Montgomery form: U := T + Y W := T - Y Winv, Zinv := 1/W, 1/Z u := U*Winv x := X*Zinv sx := sign(x) Montgomery_x := u Edwards_x_sign := sx Some notes: * If the input to the packing routine is ‘undefined’ (i.e. X = Z = 0 or Y = T = 0), then W or Z will be zero, so Winv = Zinv = 0, so u = x = 0 and sx = sign(0); this is the same output as is used to represent the identity element. Note that packing an undefined point to Edwards form in the natural way results in either a distinct undefined-point encoding or a point with y=0, of order 4. This routine handles the undefined point in a safer way, when used as part of an algorithm which can produce it under controlled, predictable conditions. So, assume that the point being packed is not undefined. * Since the Edwards curve is assumed to be complete, in any valid input to the packing routine, Z != 0. Thus, the only way that Winv or Zinv can be set to zero is if W = 0. If W = 0, then T = Y, so y = 1, so the input is the identity element. * As with implementations which use Montgomery form internally, the Montgomery_x=0 input is unpacked to the point of order 2, even though it was most likely packed from the identity element. This issue could be avoided (as suggested by Mike Hamburg) by using the reciprocal of Montgomery_x instead of Montgomery_x itself as the point format's main coordinate, so that the zero encoding would naturally be unpacked to the identity element. However, the standard point format for Curve25519 uses Montgomery_x, and I don't think avoiding the benefit of this change is important enough to outweigh the cost of changing (or discarding) every current Curve25519 implementation. > Also, looks like the representation hits special case if Edwards-x is > 0 (both points map into Montgomery_x=0, and sign bit needs to tell > apart Edwards_y values, instead of Edwards_x values as usual). I don't see enough of a benefit to distinguishing the point of order 2 from the identity element, at least in protocols which should be standardized, to justify requiring the added complexity of changing the meaning of the sign bit when Montgomery_x = 0. > So yes, easy conversion to Montgomery form is useful for DH, but > is it useful for when the other side will do things like additions? Yes. Constrained implementations are likely to use the Montgomery ladder for all scalar multiplications, and using a Montgomery-form point format benefits those implementations greatly at very low cost to implementations which use Edwards form internally. >> Variable-base scalar-multiplication operations >> which use Edwards form internally are not slowed significantly by >> having a projective rather than affine input (if any operations rely >> on their input being affine, they must occur during table setup), and >> they are not slowed at all if they double and/or apply isogenies to >> clear the cofactor group before operating on an ‘incomplete’ curve >> (e.g. a=-1 in a field in which -1 is a non-square). > > At least some protocols that do seem to cope with h>1 (as in having > checks for low-order points and no direct coupling between subgroups) > don't clear cofactors in points sent by the peer, but proceed to > directly calculate with those. I know, but some scalar multiplication algorithms can't tolerate points of even order internally. For example, the variable-base scalar multiplication algorithm for incomplete Edwards curves specified by Microsoft Research assumes that its input has odd order, and might otherwise trigger exceptional cases in formulas under uncontrolled conditions on the curves they use, so that algorithm doubles its input to clear the cofactor before performing any further processing. Robert Ransom

- [Cfrg] Montgomery-form point formats for Edward... Robert Ransom