IETF Logo Mail Archive

Re: [Cfrg] On relative performance of Edwards v.s. Montgomery Curve25519, variable base

Watson Ladd <watsonbladd@gmail.com> Mon, 12 January 2015 19:30 UTC

Return-Path: <watsonbladd@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 9001D1ACD89 for <cfrg@ietfa.amsl.com>; Mon, 12 Jan 2015 11:30:39 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Level:
X-Spam-Status: No, score=-2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, SPF_PASS=-0.001] autolearn=ham
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 RLYNuzXrVz99 for <cfrg@ietfa.amsl.com>; Mon, 12 Jan 2015 11:30:38 -0800 (PST)
Received: from mail-yh0-x234.google.com (mail-yh0-x234.google.com [IPv6:2607:f8b0:4002:c01::234]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 061101ACD9A for <cfrg@irtf.org>; Mon, 12 Jan 2015 11:30:38 -0800 (PST)
Received: by mail-yh0-f52.google.com with SMTP id z6so10531608yhz.11 for <cfrg@irtf.org>; Mon, 12 Jan 2015 11:30:37 -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=hzLnSTd8IQ9aDsV1pF8xg/iZK8xuO/yQowbFs2HSm14=; b=sn3zo9uOnB+PmlCmceU/ZyZaW1aAGMWMT5W0ubcb9FGUtcpaew0u8mfYfuiESMNzgK FN8vEHgIWcKV4qkYodx7n1KE2v4bONTJ0lm9rN/Kombm9WgZeqrtVbamvvP4SSHeuXhx IGSMnqRbWVd36lOva5R2j9dpHerUXg60kcwDz0/ih3mBnNA4wGJR/bAdDfJQ8uSLCUrY X60z+IygNEcaWN8PL8l49lWmzT+Q4qC6d4sR4ZHsSjhD7MOo/rOPqGorUIDnTpl0QCxM 1TZnl7LeHupYWYmHgWnxPAj3KveY0fSzvfQVJ+lUYKy22NULGNQUYAMjZcMd1KdyW7EW ADyQ==
MIME-Version: 1.0
X-Received: by 10.236.30.168 with SMTP id k28mr23935553yha.163.1421091037319; Mon, 12 Jan 2015 11:30:37 -0800 (PST)
Received: by 10.170.207.6 with HTTP; Mon, 12 Jan 2015 11:30:37 -0800 (PST)
In-Reply-To: <3C94ED57-5089-4A6D-9CC6-2DCD452C7BCF@shiftleft.org>
References: <54AA4AB9.70505@brainhub.org> <54B315CA.6040900@brainhub.org> <88805D27-3B08-421D-B62A-2FC61AC5851A@shiftleft.org> <CACsn0c=qxBXCkr7hCtzgY9U+5_N8hY=jShU7g=hUbqkrUMYxNw@mail.gmail.com> <3C94ED57-5089-4A6D-9CC6-2DCD452C7BCF@shiftleft.org>
Date: Mon, 12 Jan 2015 11:30:37 -0800
Message-ID: <CACsn0ck6q9nxioS7q66MkB6M+YmaGj=Nmqop1LQ-DuG0q78GaQ@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: Michael Hamburg <mike@shiftleft.org>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/CoPdpUbtEUAGCHYYUbnCCW3DV84>
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] On relative performance of Edwards v.s. Montgomery Curve25519, variable base
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: Mon, 12 Jan 2015 19:30:39 -0000

On Mon, Jan 12, 2015 at 9:59 AM, Michael Hamburg <mike@shiftleft.org> wrote:
>
> On Jan 12, 2015, at 7:28 AM, Watson Ladd <watsonbladd@gmail.com> wrote:
> The table is filled with a cost of 8M for additions and 4M+4S for
> doublings so 2^(w-2)*8M+2^(w-2)*(4M+4S). Then we proceed for
> ceil(255/w)-1steps, each step consisting of (w-1) 3M+4S doublings, and
> 1 4M+4S doubling. Ergo the total cost becomes
> 2^(w-2)*(12M+4S)+(ceil(255/w)-1)*(w*(3M+4S)+1M).
>
>
> Don’t you need to do some additions at some point as well?  Or do the
> additions only cost 1M?

Doing the calculation correctly, it's effectively 9M for an addition
after a 3M+4S doubling. The best window is 5, with 1296*M + 1032*S,
and tossing in the inversion gives 1307*M + 1286*S, vs 1285*M + 1265*S
for Montgomery form. Note that here I'm neglecting the multiplications
by constants, which is why the speeds are coming out slightly
differently.

But the bottom line is that Montgomery ladder is competitive with the
best known alternative methods at 255 bits, in terms of operation
counts, and this difference can be wiped out by the need for side
channel protection: none of the various models are saying anything too
different.

Sincerely,
Watson Ladd


>
> — Mike



-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

v2.23.0 | Report a Bug | By Email