Re: [Cfrg] New names for draft-ladd-safecurves

Watson Ladd <> Tue, 21 January 2014 04:36 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id DDE0C1A002F for <>; Mon, 20 Jan 2014 20:36:57 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2
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 ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id JxGHE3lHEddy for <>; Mon, 20 Jan 2014 20:36:56 -0800 (PST)
Received: from ( [IPv6:2a00:1450:400c:c05::231]) by (Postfix) with ESMTP id 0C9551A002A for <>; Mon, 20 Jan 2014 20:36:55 -0800 (PST)
Received: by with SMTP id m19so1604051wiv.10 for <>; Mon, 20 Jan 2014 20:36:55 -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; bh=/HjSjDgOhAMlgwyhzddcrB6PbTpRN5g6PRZ+zdtdamw=; b=tPH4vFiLqJxQS4sZuMs05js2VC4JrYb4hpVUlJ7p7CBzCOoHFgnqL7PlVLtc9bJNrZ mKx4qJDB5Rd06C/p6hcuCOHacnQVkhCmOu/NJDduP8MFTfAuLWmc1kDwYvMo2+dZKdBs SXjQ8SN2TIj5cWAWdXrsjLSJtxjYHHMwHaiTMMKiXAeXDEAYgqMdbF4/tlVTPpMaSA36 LhurjmbvRbL8bsnCQ9o14x6WurUBAS8ecULL++7PlKGES3cRp9mmuOr4nBJbfhzmE5Yk 3laaYHZg7BRwOuNQ640KGJ4ONZ7MlCcIao2uP1kK71Er72vR84yLu194i61S0rsi+xj3 49YA==
MIME-Version: 1.0
X-Received: by with SMTP id ck4mr245694wjb.53.1390279015568; Mon, 20 Jan 2014 20:36:55 -0800 (PST)
Received: by with HTTP; Mon, 20 Jan 2014 20:36:55 -0800 (PST)
In-Reply-To: <>
References: <> <> <> <> <>
Date: Mon, 20 Jan 2014 20:36:55 -0800
Message-ID: <>
From: Watson Ladd <>
To: Robert Ransom <>
Content-Type: text/plain; charset=UTF-8
Cc: "" <>, Jon Callas <>
Subject: Re: [Cfrg] New names for draft-ladd-safecurves
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: Tue, 21 Jan 2014 04:36:58 -0000

On Mon, Jan 20, 2014 at 8:25 PM, Robert Ransom <> wrote:
> On 1/20/14, Mike Hamburg <> wrote:
>> I suppose in that case we should be using curves with a small A or (A-2)/4
>> in Montgomery form instead of small d in Edwards form, because you need to
>> multiply by A more often: Edwards representations are probably fastest with
>> Niels+Extended coordinates at that size so they almost never multiply by d.
> The Montgomery-form ladder is as efficient for small-integer
> Edwards-form d as it is for small-integer Montgomery-form parameter
> ((A-2)/4 or (A+2)/4).

Maybe it's because it's late, but I don't immediately see why
A=2(1+d)/(1-d) for a small integer d leads
to a fast multiplication in the Montgomery-form ladder. The best
solution I could come up with involves
multiplications by 3 small integers instead of 1. So maybe the
efficiency loss is small, but it still exists.

I also don't see why if you are going to toss in the y coordinate into
Montgomery form to disambiguate addition you
would use the Montgomery form as a wire format instead of Edwards
form. I'm aware you can recalculate the y coordinate
given the original one after a Montgomery ladder, but with radix-k
addition algorithms on Edwards this doesn't seem to be a win.

Maybe Montgomery form is just a red herring, but when I think about
the consequences of a missing square root check in an Edwards
form implementation for ECDH, I feel Montgomery form has a place here.

> Robert Ransom

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