Re: [Cfrg] Curve manipulation, revisited

Adam Langley <agl@imperialviolet.org> Tue, 30 December 2014 10:28 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 009D21A005F for <cfrg@ietfa.amsl.com>; Tue, 30 Dec 2014 02:28:41 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 1.422
X-Spam-Level: *
X-Spam-Status: No, score=1.422 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] 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 u_Oa2u4ATRmU for <cfrg@ietfa.amsl.com>; Tue, 30 Dec 2014 02:28:39 -0800 (PST)
Received: from mail-la0-x22d.google.com (mail-la0-x22d.google.com [IPv6:2a00:1450:4010:c03::22d]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 5C4391A005D for <cfrg@irtf.org>; Tue, 30 Dec 2014 02:28:39 -0800 (PST)
Received: by mail-la0-f45.google.com with SMTP id gq15so12319944lab.4 for <cfrg@irtf.org>; Tue, 30 Dec 2014 02:28:37 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:in-reply-to:references:date:message-id:subject :from:to:cc:content-type; bh=DgpznrT1jU8nW6HZKjgIu0sIy2/4ZtrET8sgHm2pnyI=; b=EbTBTcBB4m9Cw0zhsmog0H8xqQMjnz2UxirWM510VUuMaUQrPZSaIl9AeMqTU7pddD hr0EWHlUVUm0JM4UOZTaScET7HimSOt5CqzkfQTfuCYbhVYNHOtHwrg+JI3X2I/ETdBZ L2ZtFc3S7ec3rRTuYiLhD8zUXx8TulajHzc60lBLCM+yApOHbk58+QYKSbnrigkALwVo GG6Q4ppgsIh8g/gQV/q84JACK3KVs3IniS0f+xnQ6uhEtzr5/Z098VIbE5eRDhXwHXYA xWV22snluz2iJGw35B/NvXh9f+9kvfFa3adtK3pkv5HZrYcJ49Px3eyXht3DB9GXkDO+ QW8w==
MIME-Version: 1.0
X-Received: by 10.152.30.6 with SMTP id o6mr62073511lah.64.1419935317689; Tue, 30 Dec 2014 02:28:37 -0800 (PST)
Sender: alangley@gmail.com
Received: by 10.112.114.225 with HTTP; Tue, 30 Dec 2014 02:28:37 -0800 (PST)
In-Reply-To: <CA+Vbu7zO3OatbC+cXiV58hvJCuqiTYvnsSuyopDXum4qBX54fw@mail.gmail.com>
References: <CAMfhd9W684XMmXn3ueDmwrsQ_ZdiFG+VqYLxkvs7qDwiJdpk6w@mail.gmail.com> <1725646678.805875.1419539885135.JavaMail.yahoo@jws100115.mail.ne1.yahoo.com> <CAMfhd9Ua5fFZk46Xx1AN2VgyJ=Yng6fnO8aN-_ZfzXQn0Xbxhg@mail.gmail.com> <CA+Vbu7zqFcu8d1053mZ_eEm0q=np6T3snSQ4rfY0k1-4hBVDsA@mail.gmail.com> <CAMfhd9XEqMwFzJ4sK4aHGbke6REZb26uaEEv9gbM5v_goDzwUA@mail.gmail.com> <CA+Vbu7zO3OatbC+cXiV58hvJCuqiTYvnsSuyopDXum4qBX54fw@mail.gmail.com>
Date: Tue, 30 Dec 2014 11:28:37 +0100
X-Google-Sender-Auth: i6fR1Mr75MmCZZRezyUfdsK4OfM
Message-ID: <CAMfhd9UWPF=m_UoYVRDmaxrGbzyhNfAGz-Zmqi6jxTaKhBHADw@mail.gmail.com>
From: Adam Langley <agl@imperialviolet.org>
To: Benjamin Black <b@b3k.us>
Content-Type: text/plain; charset=UTF-8
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/XfSyhemh5dCcsZwDWhGhmFkQ0xU
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] Curve manipulation, revisited
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: Tue, 30 Dec 2014 10:28:41 -0000

On Mon, Dec 29, 2014 at 6:14 PM, Benjamin Black <b@b3k.us>; wrote:
> After Yarov and Benger I don't know how robust anyone should assume ladders
> are, though that might be beside the point. Had Dan been insisting that
> ladders be _allowed_ then I would agree with you, as I have said the same
> (in the line just before the part you quoted, even). What Dan said is that
> single-coordinate ladders are _required_. They are not (or, to quote Dan
> again, "False."). X-only on the wire has clear advantages and I support that
> recommendation, but that does not force use of ladders.

I don't see quite how you're understanding Dan's quoted message to
mean that, but I think that everyone would be happy with any technique
that eliminated possible problems.

But, since a working with a windowed multiplication on the Edwards
curve is faster with Curve41417, that opens the question of whether it
would be better to transmit compressed Edwards points for ECDH at that
size.

Tanja did some calculations and the answer appears to be "no": for
41417, it's better to work with Montgomery-X for ECDH rather than do
the square-root to uncompress the point and then use the (slightly
faster) windowed method. So a general rule of "send Montgomery-X on
the wire" appears to be optimal in the cases under consideration,
which is nice.

(The limiting factor for the windowed method is reading from the L1.
The size of the window, and thus the speedup, is limited by the
requirement to read the whole table each step in order that the code
be constant-time. That means that a windowed method with 41417 is only
very slightly faster and thus the square-root cost is sufficient to
tip the balance. Of course, that also assumes that cache-pressure is
free, which it isn't in reality, so the Montgomery ladder is actually
even better than the estimates would suggest.)


Cheers

AGL