Re: [Cfrg] E-521 vs. numsp512t1

Ilari Liusvaara <ilari.liusvaara@elisanet.fi> Wed, 22 October 2014 23:43 UTC

Date: Thu, 23 Oct 2014 02:42:58 +0300
From: Ilari Liusvaara <ilari.liusvaara@elisanet.fi>
To: David Leon Gil <coruus@gmail.com>
Message-ID: <20141022234258.GA29823@LK-Perkele-VII>
References: <20141022213447.20218.qmail@cr.yp.to> <CAA7UWsXmo_H4vYVzfPdjP3xzgyHvCcwvQfP==OZi1P5Wvn-Qvw@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset="utf-8"
Content-Disposition: inline
In-Reply-To: <CAA7UWsXmo_H4vYVzfPdjP3xzgyHvCcwvQfP==OZi1P5Wvn-Qvw@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/EPmidSzE0F-HRpRg3xP86Kocvxc
Cc: "cfrg@irtf.org" <cfrg@irtf.org>, "D. J. Bernstein" <djb@cr.yp.to>
Subject: Re: [Cfrg] E-521 vs. numsp512t1
Precedence: list

On Wed, Oct 22, 2014 at 07:19:44PM -0400, David Leon Gil wrote:
> On Wed, Oct 22, 2014 at 5:34 PM, D. J. Bernstein <djb@cr.yp.to> wrote:
> > Rob Granger and Mike Scott have posted a new paper "Faster ECC over
> > \F_{2^521-1}" (https://eprint.iacr.org/2014/852) reporting ECC speeds
> > mod 2^521-1, and in particular the first (as far as I know) serious
> > implementation of E-521.
> 
> The implementation djb mentions is available on their website:
> 
> http://indigo.ie/~mscott/{ed521,ws521}.cpp
> 


Watch out (from ed521.cpp):


void mul(int *w,ECp *P)
{
	ECp W[33],Q;
	precomp(P,W);

	copy(&W[w[86]],P);  
	for (int i=85;i>=0;i--)
	{
		if (w[i]>=0) copy(&W[w[i]],&Q);
		else         neg(&W[-w[i]],&Q);
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
		window(&Q,P);
	}
	norm(P); 
}


That does not look constant-time...


-Ilari

[Cfrg] E-521 vs. numsp512t1 D. J. Bernstein
Re: [Cfrg] E-521 vs. numsp512t1 David Leon Gil
Re: [Cfrg] E-521 vs. numsp512t1 Ilari Liusvaara
Re: [Cfrg] E-521 vs. numsp512t1 Mike Hamburg
Re: [Cfrg] E-521 vs. numsp512t1 Andy Lutomirski