[Cfrg] Whether the performance advantage of small d needs to affect specifications.
Adam Langley <agl@imperialviolet.org> Wed, 31 December 2014 13:27 UTC
Return-Path: <alangley@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 A91471A8AE7 for <cfrg@ietfa.amsl.com>; Wed, 31 Dec 2014 05:27:39 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 2.544
X-Spam-Level: **
X-Spam-Status: No, score=2.544 tagged_above=-999 required=5 tests=[BAYES_50=0.8, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, FM_FORGED_GMAIL=0.622, FREEMAIL_FROM=0.001, SPF_PASS=-0.001, URI_HEX=1.122] 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 ujUgXgNO_hyA for <cfrg@ietfa.amsl.com>; Wed, 31 Dec 2014 05:27:37 -0800 (PST)
Received: from mail-lb0-x22b.google.com (mail-lb0-x22b.google.com [IPv6:2a00:1450:4010:c04::22b]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 8F1E21A8AE5 for <cfrg@irtf.org>; Wed, 31 Dec 2014 05:27:37 -0800 (PST)
Received: by mail-lb0-f171.google.com with SMTP id w7so13561250lbi.30 for <cfrg@irtf.org>; Wed, 31 Dec 2014 05:27:35 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:date:message-id:subject:from:to:content-type :content-transfer-encoding; bh=qNq1hOuWxTaOtyqHN6gkDXRy8jfLfk0aHvO46pk2+V8=; b=Ebzl/5KsrUBhTVjEtPW8flsj0a4ikLaH4O6keCo/8O6xzNcdSVht7jbutuHV36Tera uNOCp3q5tUAE1ZyVPEL/DQn48OqjvOnapWn1d/hM6pqE7JbSZstzVTVRCdob+CDT1Gx8 XQHSYic+H5qmHJ5ymfB5gFQZE3DE8Z0EMr05udMU7Hd4QKNjqCTqqBVvCiORq4Fdrjqa oulch4APgMYLbUJjyEPSNfkd/hl+k+G1uhT2qRORIb6c3bsI7onJjTohJwshVFwt/zTV yfMX2I7QhkhSd0K1UMxo6mPMydNjZnl1Cn+jAvCW+L8NnIdMwgqh7cqK9U6LGPlR0NTX R/SQ==
MIME-Version: 1.0
X-Received: by 10.112.163.167 with SMTP id yj7mr19480904lbb.96.1420032455746; Wed, 31 Dec 2014 05:27:35 -0800 (PST)
Sender: alangley@gmail.com
Received: by 10.112.114.225 with HTTP; Wed, 31 Dec 2014 05:27:35 -0800 (PST)
Date: Wed, 31 Dec 2014 13:27:35 +0000
X-Google-Sender-Auth: lVNEtypRVsdsrrytKlv-w1mvBaE
Message-ID: <CAMfhd9V4tnjQL-orjTjX3KS=-XZRn0snAPrVwmP6pZH_20Cfgg@mail.gmail.com>
From: Adam Langley <agl@imperialviolet.org>
To: "cfrg@irtf.org" <cfrg@irtf.org>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/Pdz-CY6azxJDgaSuc-EaAGdQlBg
Subject: [Cfrg] Whether the performance advantage of small d needs to affect specifications.
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: Wed, 31 Dec 2014 13:27:39 -0000
As I understand it, we have significant agreement at the ~128-bit level: Microsoft accepts curve25519 with a different base point and sending Montgomery-X for ECDH. Everyone else accepts curve25519 with Montgomery-X for ECDH. (I'm not considering those who want random primes as the chairs have said that's out of scope for now.) Since any base point (in the correct subgroup) is as good as any other, I'm going to make the assumption that significant existing practice will mean that we can we can all end up accepting x=9 as the base point. Where Microsoft still differ at ~128-bits is that they specify an isogenous twisted Edwards curve with small d, while existing practice uses an isomorphic twisted Edwards curve with d=-121665/121666. There is no security difference between these, but there is an argument that the small d brings a performance advantage—possibly leading to a tension between existing practice and performance. However, I think that tension can be resolved by considering a small d as an implementation strategy. That requires that implementations who wish to use the isogenous curve be able to convert inputs and outputs to/from the isomorphic curve very cheaply. 1) A "small d" implementation wishes to perform a scalarmult: This case is fairly easy I think. At the point that the implementation is doing the transformation to affine form, it holds extended coordinates (X, Y, Z, T) where x'=X/Z, y'=Y/Z and x'y' = T/Z. (I'll write (x', y') for the isogenous curve and (x, y) for the isomorphic one.) Rather than calculate 1/Z and then multiply that by X and Y, it can use different formulas to merge the transform to the isomorphic curve: x = TZ/(2Z^2 - X^2 - Y^2), y = (Y^2-X^2)/(Y^2+X^2). (I don't have Sage, Python or even enough paper with me, so I *probably* have the equations wrong, but the strategy should hold.) Since the inversions can be merged, the cost is essentially the same as outputting affine coordinates on the isogenous curve. For a modified ECDSA with Edward's curves (which Microsoft have suggested that they want to do), this is sufficient since the signature contains only scalars. For EdDSA, the paper[1] says that they skip the decompression of 'R' and check that the encoding of the other side of the verification equation matches 'R', thus this should be sufficient there too. However, let's assume that some protocol needs to decompress points: 2) A "small d" implementations wishes to use a compressed point on the isomorphic curve. The inverse transformation for the isogeny is more complex and results in 4 times the point. It also needs the decompressed point as an input to the map. As the Ed25519 paper shows, it's possible to merge an inversion and square root when decompressing Edwards points such that only a single field exponentiation is needed. I certainly won't get the equations for the inverse map correct here, but it appears that they'll end up needing an inversion and calculation of 'x', which needs a square root. (The value to invert needs to be independent of 'x', but that appears to be easy to arrange.) Call the value to be inverted 'a', and let b=uv^7, which is the value that we need to raise to (q-5)/8 in order to calculate 'x'. (I'm using the variable names 'u' and 'v' to match [1].) Calculate (a^8×b)^((q-5)/8) = c = a^(q-5)b^((q-5)/8). Multiplying by a^4 will eliminate the 'a' term leaving b^((q-5)/8), as needed for the 'x' calculation. Now c^8 = a^(7(q-1) + q - 33)b^q-5. Thus c^8×a^31×b^4 = a^(q-2), as needed for the inversion. So I think (albeit with the distinct possibility that I've missed something by not being able to confirm that it works) that a "small d" implementation can use compressed points from the isomorphic curve with only a single field exponentiation, which is the same cost as decompressing points is for implementations of the isomorphic curve anyway. It does result in 4R, but often that's not a problem, and could even be an advantage. (Consider ECDH with compressed points on the wire: since the private scalar is a multiple of 8, the two low-order bits can just be skipped.) So, hopefully, a performance advantage of small d, if any, can be realised even if the isomorphic curve is specified on the wire. Thus there need not be tension between performance and existing practice here. (Time to catch my flight.) [1] http://ed25519.cr.yp.to/ed25519-20110926.pdf, section 5. Cheers AGL -- Adam Langley agl@imperialviolet.org https://www.imperialviolet.org
- [Cfrg] Whether the performance advantage of small… Adam Langley
- [Cfrg] should the CFRG really strive for consensu… Christoph Anton Mitterer
- Re: [Cfrg] should the CFRG really strive for cons… Adam Langley
- Re: [Cfrg] should the CFRG really strive for cons… Christoph Anton Mitterer
- Re: [Cfrg] should the CFRG really strive for cons… Salz, Rich
- Re: [Cfrg] should the CFRG really strive for cons… Christoph Anton Mitterer
- Re: [Cfrg] should the CFRG really strive for cons… Yoav Nir
- Re: [Cfrg] should the CFRG really strive for cons… Watson Ladd
- Re: [Cfrg] should the CFRG really strive for cons… Nico Williams
- Re: [Cfrg] should the CFRG really strive for cons… Alexey Melnikov
- [Cfrg] Reconsider TLS/CFRG relationship (Re: shou… Nico Williams
- Re: [Cfrg] Reconsider TLS/CFRG relationship (Re: … Nex6|Bill