Re: [Cfrg] [TLS] Curve25519 in TLS and Additional Curves in TLS

Mike Hamburg <> Fri, 24 January 2014 06:07 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 216BC1A0208 for <>; Thu, 23 Jan 2014 22:07:59 -0800 (PST)
X-Virus-Scanned: amavisd-new at
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 ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id v9po__Io-JVu for <>; Thu, 23 Jan 2014 22:07:56 -0800 (PST)
Received: from ( []) by (Postfix) with ESMTP id 9C7D51A01BB for <>; Thu, 23 Jan 2014 22:07:56 -0800 (PST)
Received: from [] (unknown []) by (Postfix) with ESMTPSA id 990733AA04; Thu, 23 Jan 2014 22:05:37 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple;; s=sldo; t=1390543537; bh=fc9UzJyCUvIBHZOtk2yaOSuo7flzaRwm4RQw+iFK8Rg=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=EQx3fmUjxsTk9kMre3R3fUBCL/VVC75SLaKz2wlSCkSyxj/zG0tLD2fNbt0nexh2z rlHHOmSTb3shzAAJGlASI8F1bJraxuQP/MVO5vaM84r1oKITNgRBvELhOG7uJE86CQ +cxOzq7by8to6Q0vh0eVZUAHkyFteyIjDpZ6OIkU=
Content-Type: multipart/alternative; boundary="Apple-Mail=_0E29B95A-AF6E-4EF4-97CE-0E3AA4474C51"
Mime-Version: 1.0 (Mac OS X Mail 7.1 \(1827\))
From: Mike Hamburg <>
In-Reply-To: <>
Date: Thu, 23 Jan 2014 22:07:55 -0800
Message-Id: <>
References: <> <> <> <> <> <> <> <> <> <> <>
To: Robert Ransom <>
X-Mailer: Apple Mail (2.1827)
Subject: Re: [Cfrg] [TLS] Curve25519 in TLS and Additional Curves in TLS
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Fri, 24 Jan 2014 06:07:59 -0000

On Jan 23, 2014, at 7:17 PM, Robert Ransom <> wrote:

> On 1/23/14, Michael Hamburg <> wrote:
>> On Jan 23, 2014, at 4:59 PM, Andrey Jivsov <> wrote:
>>> Wouldn't be another
>>> method?
>>> Traditionally the problem was solved by carrying 1 bit and then finding a
>>> place to fit it in and defining what it means, etc. There is another way.
>>> One can adjust the private key to make the coordinate that we drop, x in
>>> this case, be the smallest of the two possibilities.
>>> The nice feature of my proposal is that you can still also encode the bit
>>> if you wish so, as you proposed.
>> This is interesting, but I think it works better with the Edwards
>> x-coordinate instead of the Montgomery y-coordinate.  That is, it applies
>> well to Watson’s (Montgomery x, Edwards x) representation.  This is because
>> not every point you might want to transmit is a public key; it might be the
>> product of something which does not support an easy negation, such as PAKE.
>> In this case, with your proposal, implementers have to send the sign bit,
>> and we have two wire formats again.  But if the Edwards x-coordinate is
>> used, you can also fast-adjust by adding the point of order 2, which maps
>> EdX to -EdX.  (It maps EdY to -EdY and MontX to 1/MontX.)  If the protocol
>> wipes out the cofactor (almost every protocol does for security reasons),
>> then this is more likely to be acceptable than negating the point.
> This makes point encoding to Montgomery-form x slightly less efficient
> and more complex -- instead of computing (for the main coordinate)
> Zinv=1/Z, then x=X*Zinv, this requires XZinv=1/(X*Z), then either
> x=X^2*XZinv or xinv=Z^2*XZinv (conditional on the sign bit of the
> Edwards-form x coordinate).  (I'm omitting the part where Zinv or
> XZinv must be batched with the inversion to compute the Edwards-form x
> coordinate and its sign bit.)
> (It may still be worthwhile; I'm just pointing out exactly what effect
> this would have on implementations.  I should also point out that the
> Montgomery-form x coordinate can't distinguish the identity element
> from the point of order 2.)

You're right.

The part that counts is complexity, though, not speed.  Adding a dozen muls to a 2500-mul computation is less than half a percent.  The bigger the curve, the smaller the fraction.

Furthermore, to be a truly uniform point-encoding format (including for hashes and stuff), you'd have to modify your ladder to figure out which y is correct at the end.  And that's going to be complicated.  Or you could not do that, but then again you'd have to figure out which encoding to use where.  I should probably go work out the formulas and post them at some point...

So yeah.  Upside.  Downside.

-- Mike