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

From: Robert Ransom <[email-masked]>
Date: Tue, 29 Jul 2014 06:52:33 -0700

On 7/26/14, Ilari Liusvaara <[email-masked]> wrote:
> On Fri, Jul 25, 2014 at 07:25:54PM -0700, Robert Ransom wrote:
>> On 7/25/14, Watson Ladd <[email-masked]> 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