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

Mike Hamburg <mike@shiftleft.org> Tue, 21 January 2014 04:38 UTC

Return-Path: <mike@shiftleft.org>
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 AB7861A0035 for <cfrg@ietfa.amsl.com>; Mon, 20 Jan 2014 20:38:58 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 1.556
X-Spam-Level: *
X-Spam-Status: No, score=1.556 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FH_HOST_EQ_D_D_D_D=0.765, FH_HOST_EQ_D_D_D_DB=0.888, HELO_MISMATCH_ORG=0.611, HOST_MISMATCH_NET=0.311, RDNS_DYNAMIC=0.982, 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 XQaWMmndzK1E for <cfrg@ietfa.amsl.com>; Mon, 20 Jan 2014 20:38:57 -0800 (PST)
Received: from aspartame.shiftleft.org (199-116-74-157-v301.PUBLIC.monkeybrains.net [199.116.74.157]) by ietfa.amsl.com (Postfix) with ESMTP id B788C1A002F for <cfrg@irtf.org>; Mon, 20 Jan 2014 20:38:57 -0800 (PST)
Received: from [192.168.1.129] (unknown [192.168.1.1]) by aspartame.shiftleft.org (Postfix) with ESMTPSA id AF1093AA04; Mon, 20 Jan 2014 20:36:51 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=shiftleft.org; s=sldo; t=1390279011; bh=+4yKHIp6OsgmphNo3LOQWgcYx+HDweMJ0SRvlX6ZGak=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=IO6uQgYVO57fumJSl4MWaqOSOIKfs0VMBy2jq7EicibLMZ/eL4+9h+Z6a8AD4BNwb gyaY5kYp+pdgNndhHyJ3LWxB6Ga57VDvejfO3E6PaTf8i+hBi0TaumjxlgrVuUS85e eOa6ZcbrsiYLhQd8RORtI8fmBbIu7J7ZiHai1YMM=
Content-Type: text/plain; charset=us-ascii
Mime-Version: 1.0 (Mac OS X Mail 7.1 \(1827\))
From: Mike Hamburg <mike@shiftleft.org>
In-Reply-To: <CABqy+sr1zc-T-F3D_VOoz2B9GNZPsAxi=HeMoe=DwG5EJq8AuA@mail.gmail.com>
Date: Mon, 20 Jan 2014 20:38:56 -0800
Content-Transfer-Encoding: quoted-printable
Message-Id: <972ED43E-96A5-4B4B-A117-3DC88D00B778@shiftleft.org>
References: <CACsn0ck02mnETBUfuyJjLV9K8Yuiki8_-RG0tVszL8BDhkK27w@mail.gmail.com> <6489F7D3-BF54-416F-94BE-64FD1CFCCB1E@callas.org> <CACsn0cn0938BHMs7uFJYeB_q2VcGQULcF8fzc7KR67A_+mqzLw@mail.gmail.com> <264676DC-14DA-432E-81AB-CD0D852307A4@shiftleft.org> <CABqy+sr1zc-T-F3D_VOoz2B9GNZPsAxi=HeMoe=DwG5EJq8AuA@mail.gmail.com>
To: Robert Ransom <rransom.8774@gmail.com>
X-Mailer: Apple Mail (2.1827)
Cc: "cfrg@irtf.org" <cfrg@irtf.org>, Jon Callas <jon@callas.org>
Subject: Re: [Cfrg] New names for draft-ladd-safecurves
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, 21 Jan 2014 04:38:58 -0000

On Jan 20, 2014, at 8:25 PM, Robert Ransom <rransom.8774@gmail.com> wrote:

> On 1/20/14, Mike Hamburg <mike@shiftleft.org> 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).
> 
> 
> Robert Ransom

So it is.  Do you have a reference for that, BTW?  I derived it as:

x' = (x^2-z^2)^2
z' = 4xz(x^2 + Axz + z^2)

These are typically computed from (x+z)^2 and (x-z)^2, with 4xz being the difference between the two.

Substituting A = 2(1+d)/(1-d) = 4/(1-d)-2, we have

z' = 4xz(x^2 - 2xz + z^2 + 4xz/(1-d))

Scaling both x' and z' by (1-d) gives

x' = (x+z)^2 (x-z)^2 (1-d)
z' = 4xz(4xz + (1-d)(x-z)^2)

requiring the same 2 bigmuls, one smallmul and one add that the standard formula requires.

-- Mike