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

Robert Ransom <> Fri, 24 January 2014 03:17 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 699BB1A012A for <>; Thu, 23 Jan 2014 19:17:15 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.75
X-Spam-Status: No, score=-1.75 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, SPF_PASS=-0.001] autolearn=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id nTpne7qNzF67 for <>; Thu, 23 Jan 2014 19:17:14 -0800 (PST)
Received: from ( [IPv6:2607:f8b0:400d:c00::233]) by (Postfix) with ESMTP id DD9F11A0141 for <>; Thu, 23 Jan 2014 19:17:13 -0800 (PST)
Received: by with SMTP id f11so3253827qae.24 for <>; Thu, 23 Jan 2014 19:17:12 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; bh=fYLiJm/Yv5dJAOe6JPEUkRRz3k0/ZHJCns2bn4BapX0=; b=q5kbDuQ2Txb+xPWVhVBj+p+qbqvIMIZYhiHZwRyKiYWNmPlcEtKF9Bs913Uq8pbZp7 fSZ0sKSdO72mDc+MPMuGljmvLz2eXjGZCEKKUojtgWQLn8Yv1hCY1UktvcZ7tnm4eoza 7SZ2xNeJ2V+hb95vxbAhzrWfEwVYqY4ODdFedIfLCrbs8BvI7sqEUq1fDEQN6EDoxtQ8 JDggFhZoDNtzz6laLhsr7Oa14a3Ud/wA057QJe6l63xN1srTn4evViItKV+uyr+JHy1V tuI56Q1nYkGyKvC4XB4nWk3r7w7cRoX8XGbTO0wusUtNZN1TKFzeOlbiOfIqBzSthfgM 1zQg==
MIME-Version: 1.0
X-Received: by with SMTP id m78mr15972582qga.21.1390533432694; Thu, 23 Jan 2014 19:17:12 -0800 (PST)
Received: by with HTTP; Thu, 23 Jan 2014 19:17:12 -0800 (PST)
In-Reply-To: <>
References: <> <> <> <> <> <> <> <> <> <>
Date: Thu, 23 Jan 2014 19:17:12 -0800
Message-ID: <>
From: Robert Ransom <>
To: Michael Hamburg <>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
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 03:17:15 -0000

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

Robert Ransom