Re: [Cfrg] Curve selection revisited

Ilari Liusvaara <ilari.liusvaara@elisanet.fi> Sun, 27 July 2014 05:22 UTC

Return-Path: <ilari.liusvaara@elisanet.fi>
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 2018B1A0067 for <cfrg@ietfa.amsl.com>; Sat, 26 Jul 2014 22:22:24 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.901
X-Spam-Level:
X-Spam-Status: No, score=-1.901 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001] autolearn=ham
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 qbLY_HsAk248 for <cfrg@ietfa.amsl.com>; Sat, 26 Jul 2014 22:22:21 -0700 (PDT)
Received: from emh03.mail.saunalahti.fi (emh03.mail.saunalahti.fi [62.142.5.109]) (using TLSv1 with cipher ADH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id CE2731A0022 for <cfrg@irtf.org>; Sat, 26 Jul 2014 22:22:19 -0700 (PDT)
Received: from LK-Perkele-VII (a88-112-44-140.elisa-laajakaista.fi [88.112.44.140]) by emh03.mail.saunalahti.fi (Postfix) with ESMTP id 091C618876D; Sun, 27 Jul 2014 08:22:16 +0300 (EEST)
Date: Sun, 27 Jul 2014 08:22:16 +0300
From: Ilari Liusvaara <ilari.liusvaara@elisanet.fi>
To: Robert Ransom <rransom.8774@gmail.com>
Message-ID: <20140727052216.GA15012@LK-Perkele-VII>
References: <CA+Vbu7xroa68=HOZtbf=oz7kK2EeUv_z1okpnjxHPR0ZtHD5cA@mail.gmail.com> <CFF7E184.28E9F%kenny.paterson@rhul.ac.uk> <53D2781B.8030605@sbcglobal.net> <CACsn0ckqFigWoH2+OOEHSd2VWPp8y6=m8H5OsFRyjXmjK7+m4w@mail.gmail.com> <CABqy+srxMNuG0AaQd0SaegHvZWgbW762EQq+iAHL_fbu6sOJJQ@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
In-Reply-To: <CABqy+srxMNuG0AaQd0SaegHvZWgbW762EQq+iAHL_fbu6sOJJQ@mail.gmail.com>
User-Agent: Mutt/1.5.23 (2014-03-12)
Sender: Ilari Liusvaara <ilari.liusvaara@elisanet.fi>
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/U0MgnSTq5ZNo138Infidzx2vEMY
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] Curve selection revisited
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: Sun, 27 Jul 2014 05:22:24 -0000

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?

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).

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).

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?

> 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.


-Ilari