Re: [Cfrg] [TLS] Curve25519 in TLS and Additional Curves in TLS
Robert Ransom <rransom.8774@gmail.com> Fri, 24 January 2014 03:17 UTC
Return-Path: <rransom.8774@gmail.com>
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 699BB1A012A for <cfrg@ietfa.amsl.com>; Thu, 23 Jan 2014 19:17:15 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.75
X-Spam-Level:
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 mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id nTpne7qNzF67 for <cfrg@ietfa.amsl.com>; Thu, 23 Jan 2014 19:17:14 -0800 (PST)
Received: from mail-qa0-x233.google.com (mail-qa0-x233.google.com [IPv6:2607:f8b0:400d:c00::233]) by ietfa.amsl.com (Postfix) with ESMTP id DD9F11A0141 for <cfrg@irtf.org>; Thu, 23 Jan 2014 19:17:13 -0800 (PST)
Received: by mail-qa0-f51.google.com with SMTP id f11so3253827qae.24 for <cfrg@irtf.org>; Thu, 23 Jan 2014 19:17:12 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; 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 10.140.47.212 with SMTP id m78mr15972582qga.21.1390533432694; Thu, 23 Jan 2014 19:17:12 -0800 (PST)
Received: by 10.229.181.132 with HTTP; Thu, 23 Jan 2014 19:17:12 -0800 (PST)
In-Reply-To: <2311ADE0-B85D-4EEA-A675-03ED3735DE1D@shiftleft.org>
References: <87ob3456s1.fsf@latte.josefsson.org> <CABqy+spt7BYqjsqLAkZssGp3aY9M+iLqV+pmyr7ZN-TXmJJpVg@mail.gmail.com> <52E060D0.9030801@polarssl.org> <CABqy+spJoswrPovxf18QS1SGdk6K=mfny6joJm3X24Vh65oagQ@mail.gmail.com> <52E0E241.40406@polarssl.org> <CABqy+sqs31ATDWJSum55m1o5pRvw8Wq5GtB-mF-hgP2emB5eFQ@mail.gmail.com> <CABqy+sozYSOTh7pbUS2GXf=4kYV3zgztXZBa10Bx=s-N8zHHyA@mail.gmail.com> <CABqy+soSojSMfx=yU9eFhmAeuJaJ_r=4h=RDR6JtOchYZ9zsQA@mail.gmail.com> <52E1BAE0.8060809@brainhub.org> <2311ADE0-B85D-4EEA-A675-03ED3735DE1D@shiftleft.org>
Date: Thu, 23 Jan 2014 19:17:12 -0800
Message-ID: <CABqy+souWU30JvfzE61GY11gZLevL+Ru50GHkxJDfCkLMuRYqg@mail.gmail.com>
From: Robert Ransom <rransom.8774@gmail.com>
To: Michael Hamburg <mike@shiftleft.org>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Cc: cfrg@irtf.org
Subject: Re: [Cfrg] [TLS] Curve25519 in TLS and Additional Curves in TLS
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: Fri, 24 Jan 2014 03:17:15 -0000
On 1/23/14, Michael Hamburg <mike@shiftleft.org> wrote: > On Jan 23, 2014, at 4:59 PM, Andrey Jivsov <crypto@brainhub.org> wrote: >> >> Wouldn't http://tools.ietf.org/html/draft-jivsov-ecc-compact 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
- [Cfrg] Fwd: [TLS] Curve25519 in TLS and Additiona… Robert Ransom
- Re: [Cfrg] Fwd: [TLS] Curve25519 in TLS and Addit… Andrey Jivsov
- Re: [Cfrg] [TLS] Curve25519 in TLS and Additional… Michael Hamburg
- Re: [Cfrg] Fwd: [TLS] Curve25519 in TLS and Addit… Robert Ransom
- Re: [Cfrg] [TLS] Curve25519 in TLS and Additional… Robert Ransom
- Re: [Cfrg] [TLS] Curve25519 in TLS and Additional… Mike Hamburg
- Re: [Cfrg] [TLS] Curve25519 in TLS and Additional… Andrey Jivsov
- Re: [Cfrg] [TLS] Curve25519 in TLS and Additional… Michael Hamburg
- Re: [Cfrg] [TLS] Curve25519 in TLS and Additional… Andrey Jivsov
- Re: [Cfrg] [TLS] Curve25519 in TLS and Additional… Michael Hamburg
- Re: [Cfrg] [TLS] Curve25519 in TLS and Additional… Andrey Jivsov
- Re: [Cfrg] [TLS] Curve25519 in TLS and Additional… Robert Ransom
- Re: [Cfrg] [TLS] Curve25519 in TLS and Additional… Andrey Jivsov
- Re: [Cfrg] [TLS] Curve25519 in TLS and Additional… Watson Ladd
- Re: [Cfrg] [TLS] Curve25519 in TLS and Additional… Dan Harkins
- Re: [Cfrg] Fwd: [TLS] Curve25519 in TLS and Addit… Andrey Jivsov
- Re: [Cfrg] Fwd: [TLS] Curve25519 in TLS and Addit… Robert Ransom
- Re: [Cfrg] Fwd: [TLS] Curve25519 in TLS and Addit… Andrey Jivsov