Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Consensus and a way forward]

Ilari Liusvaara <ilari.liusvaara@elisanet.fi> Mon, 01 December 2014 17:53 UTC

Return-Path: <ilari.liusvaara@elisanet.fi>
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 9F84A1A8722 for <cfrg@ietfa.amsl.com>; Mon, 1 Dec 2014 09:53:56 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.901
X-Spam-Level:
X-Spam-Status: No, score=-1.901 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_NONE=-0.0001, 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 QbnndwkocOwD for <cfrg@ietfa.amsl.com>; Mon, 1 Dec 2014 09:53:48 -0800 (PST)
Received: from emh01.mail.saunalahti.fi (emh01.mail.saunalahti.fi [62.142.5.107]) (using TLSv1 with cipher ADH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id DBB041A1A7E for <cfrg@irtf.org>; Mon, 1 Dec 2014 09:53:47 -0800 (PST)
Received: from LK-Perkele-VII (a88-112-44-140.elisa-laajakaista.fi [88.112.44.140]) by emh01.mail.saunalahti.fi (Postfix) with ESMTP id E71BA9005B; Mon, 1 Dec 2014 19:53:44 +0200 (EET)
Date: Mon, 1 Dec 2014 19:53:44 +0200
From: Ilari Liusvaara <ilari.liusvaara@elisanet.fi>
To: Adam Langley <agl@imperialviolet.org>
Message-ID: <20141201175344.GA21285@LK-Perkele-VII>
References: <CA+Vbu7xvvfRWyqyE9sqU7VbjzNQZp+DwRWjaV3Lw0hjLr8ye1A@mail.gmail.com> <5476CB73.7090206@akr.io> <CAMfhd9XxkZsVPMcevWOgvvqbBK0JqLVCGBYfwWu0QFO5rsfbJQ@mail.gmail.com> <CABqy+sodVBbwNrA28AFxYMiw5rJxtUX3cbYCjtrYxK-48Ocd6A@mail.gmail.com> <CAMfhd9VF784rJ5gXiLkB6DdwS+zAi=GDgT=792jQ=+oqcK_F3Q@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
In-Reply-To: <CAMfhd9VF784rJ5gXiLkB6DdwS+zAi=GDgT=792jQ=+oqcK_F3Q@mail.gmail.com>
User-Agent: Mutt/1.5.23 (2014-03-12)
Sender: Ilari Liusvaara <ilari.liusvaara@elisanet.fi>
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/24H6_oVS6VezTOsuq1Ca_cmzAOU
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] draft-black-rpgecc-00-.txt [was: Consensus and a way forward]
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, 01 Dec 2014 17:53:57 -0000

On Mon, Dec 01, 2014 at 06:17:07AM -0800, Adam Langley wrote:
> On Sun, Nov 30, 2014 at 7:33 PM, Robert Ransom <rransom.8774@gmail.com>; wrote:
> 
> > Interesting suggestion.
> >
> > Both 89747 and 121665 are 17 bits long (they are between 2^17 and 2^18
> > - 1), and 89747 has a slightly greater Hamming weight than 121665 (10
> > rather than 9); I would expect any performance improvement on due to
> > that change in curve parameter to be quite small and only applicable
> > to a very few implementation strategies.  Have you done any
> > benchmarking to quantify the performance improvement that you are
> > claiming as a technical benefit of PinkBikeShed?
> 
> I've not done any benchmarking, it's just a guess. But the Edward's d
> parameter for the curve isomorphic to Curve25519 isn't 121665, it's
> +/- 121665/121666 [http://eprint.iacr.org/2007/286.pdf, section 2].
> That value doesn't have a small representation so I think that the
> PinkBikeShed curve does get to use a multiplication by a small
> constant in place of a multiplication by a large constant. That might
> be a small help.

The isogeny that lets one in effect have small d and a24 at the same time
also exists for Curve25519.


AFAICT:

Complete Twisted Edwards curve:

-x^2+y^2=1+121665x^2*y^2 (mod 2^255-19)

With base point:

x=8343919484931660353238246604028044872330114539683257561218125599081866236258
y=10591048728587107161910258178281284043396286849160988064050992288107790236293

Mapped by:
u = -y^2/x^2
v = y*(-x^2+y^2-2)/(i*x^3)

Where (square root of -1):
i=38214883241950591754978413199355411911188925816896391856984770930832735035197

Maps to complete Montgomery curve:

v^2 = u^3 + 486662 * u^2 + u  (mod 2^255-19)

With base point:

u=9
v=14781619447589544791020593568409986887264606134616475288964881837755586237401


Mapped by:
w=u+19298681539552699237261830834781317975544997444273427339909597334652188435537

Maps to Weierstrass curve v^2=w^3+a*w+b:
a=19298681539552699237261830834781317975544997444273427339909597334573241639236
b=55751746669818908907645289078257140818241103727901012315294400837956729358436

With base point:
w=19298681539552699237261830834781317975544997444273427339909597334652188435546
v=14781619447589544791020593568409986887264606134616475288964881837755586237401


All the curves have base order of:
7237005577332262213973186563042994240857116359379907606001950938285454250989



The middle curve and base point match Curve25519 data from Safecurves after
changing variable names (x,y)->(u,v).


The v(x,y) formula looks messy, but for single-coordinate Montgomery, one only
needs u(x,y), which is reasonably fast. And looks like one can compute v(x,y)
together with u(x,y) pretty cheaply (few extra multiplications and additions).

The reverse maps x(u,v) and y(u,v) are more annoying, seemingly containing
two square roots and an inversion (among with few other ops).


-Ilari