Re: [Cfrg] Safecurves draft

Mike Hamburg <mike@shiftleft.org> Thu, 09 January 2014 18:07 UTC

Return-Path: <mike@shiftleft.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 9C08E1AE26E for <cfrg@ietfa.amsl.com>; Thu, 9 Jan 2014 10:07:37 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 1.557
X-Spam-Level: *
X-Spam-Status: No, score=1.557 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FH_HOST_EQ_D_D_D_D=0.765, FH_HOST_EQ_D_D_D_DB=0.888, HELO_MISMATCH_ORG=0.611, HOST_MISMATCH_NET=0.311, HTML_MESSAGE=0.001, RDNS_DYNAMIC=0.982, 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 KaL9INq5CJgL for <cfrg@ietfa.amsl.com>; Thu, 9 Jan 2014 10:07:36 -0800 (PST)
Received: from aspartame.shiftleft.org (199-116-74-157-v301.PUBLIC.monkeybrains.net [199.116.74.157]) by ietfa.amsl.com (Postfix) with ESMTP id 30E201AE04C for <cfrg@irtf.org>; Thu, 9 Jan 2014 10:07:36 -0800 (PST)
Received: from [192.168.1.129] (unknown [192.168.1.1]) by aspartame.shiftleft.org (Postfix) with ESMTPSA id B82F43AA04; Thu, 9 Jan 2014 10:06:05 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=shiftleft.org; s=sldo; t=1389290765; bh=SdpHQwKGMwdUJlPJp4qVkbO8hTLJUtBxMFwWol4S2X0=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=HPp8mTV+4pLznOj+lKilh9StQd3T2toXB+xqwlODyosk1qDBxPfwFOt1ai8JJ8Se5 HXnT+3kluR4a+BGfHf3uuZJQirPUfj93FzN/uPUk11SrG9aoMA9KJdc8m/8O0zd0Rr dWgU9fcc0rIziCgS1qL74tyZjbO/EFkVPy2gMUUA=
Content-Type: multipart/alternative; boundary="Apple-Mail=_71CF6819-6A8C-44BE-88D1-4DD86AFCA136"
Mime-Version: 1.0 (Mac OS X Mail 7.1 \(1827\))
From: Mike Hamburg <mike@shiftleft.org>
In-Reply-To: <CADMpkcKptQrtXyaarkXiMpRyGmobEcywbTeTkkcb6uWB-yttwg@mail.gmail.com>
Date: Thu, 9 Jan 2014 10:07:24 -0800
Message-Id: <B29AD107-69D0-4EF5-9D5B-137C1E333AEA@shiftleft.org>
References: <20140109031144.6111382.52184.8264@certicom.com> <20140109094731.GA12327@netbook.cypherspace.org> <CADMpkc+giuSZgrYmusRJmj5SyN9Dcu_Mdaqx5KQPyXGMmosFUw@mail.gmail.com> <CABqy+soXxjY+fEzpHP+_yn9Y1Xtapm_9OWbgDcA_J_Lukz_YLw@mail.gmail.com> <CADMpkcJFk2C5DPQX9RVWphUH25atsUX2vPA7RwNf8zbmR6dXJQ@mail.gmail.com> <CABqy+soX0xVWG0+vJs-_7O1Ur_hkDW0u0acCGZYrrtEci5QRXw@mail.gmail.com> <CADMpkcKptQrtXyaarkXiMpRyGmobEcywbTeTkkcb6uWB-yttwg@mail.gmail.com>
To: Bodo Moeller <bmoeller@acm.org>
X-Mailer: Apple Mail (2.1827)
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] Safecurves draft
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: Thu, 09 Jan 2014 18:07:37 -0000

On Jan 9, 2014, at 7:26 AM, Bodo Moeller <bmoeller@acm.org> wrote:

> Robert Ransom <rransom.8774@gmail.com>om>:
> 
> > So while the Montgomery-form Curve25519 certainly has its use, allowing
> > applications to negotiate a different form for ECDH would be beneficial.
> 
>  
> Even if the party which generates a public key uses Edwards-form
> points internally for that operation, whoever generates the key can
> put it into Montgomery form for free before scaling, whereas whoever
> receives it would need to perform an extra coordinate inversion in
> order to convert from Edwards form to affine Montgomery form.
> 
> That's a good point.  As I've pointed out (or tried to point out, anyway), the receiver might want to do the computations in Edwards form too, but there's not that much to be gained from that, so it may not be worth the extra complexity.
> 
> Bodo

I agree.  The sender might well use Edwards internally -- it's about 3x faster -- but the point should be sent in Montgomery form.

I wonder, though, if the standard encoding of the spec should have the sign of the y-coordinate.  That way if we want to use the format for something other than ECDH -- signatures or PAKE or whatever -- we won't have to specify a new encoding.

An overly-complicated but cute solution is 1/sqrt(x) chosen with the same sign as y.  (x is always square if you're in the q-torsion; 1/x works just as well as x in the ladder; 1/x lets you encode the identity.)  But we probably don't actually want to spec that.  Maybe just a bit for sign(y)?

-- Mike