Re: [Cfrg] How to (pre-)compute a ladder [revised version]

Francisco Rodriguez- Henriquez <francisco@cs.cinvestav.mx> Fri, 14 July 2017 19:34 UTC

Return-Path: <francisco@cs.cinvestav.mx>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 04FE7129ADD for <cfrg@ietfa.amsl.com>; Fri, 14 Jul 2017 12:34:07 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.903
X-Spam-Level:
X-Spam-Status: No, score=-1.903 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_NONE=-0.0001, RP_MATCHES_RCVD=-0.001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=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 j87REikMw7Ux for <cfrg@ietfa.amsl.com>; Fri, 14 Jul 2017 12:34:05 -0700 (PDT)
Received: from delta.cs.cinvestav.mx (delta.cs.cinvestav.mx [148.247.102.21]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 5BA4B126BFD for <cfrg@irtf.org>; Fri, 14 Jul 2017 12:34:05 -0700 (PDT)
Received: from localhost (localhost [127.0.0.1]) by delta.cs.cinvestav.mx (Postfix) with ESMTP id 4ACDC5C1557; Fri, 14 Jul 2017 14:33:50 -0500 (CDT)
X-Virus-Scanned: amavisd-new at cs.cinvestav.mx
Received: from delta.cs.cinvestav.mx ([127.0.0.1]) by localhost (delta.cs.cinvestav.mx [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id Kf9MbDqbNpJb; Fri, 14 Jul 2017 14:33:48 -0500 (CDT)
Received: by delta.cs.cinvestav.mx (Postfix, from userid 1507) id BD0735C1577; Fri, 14 Jul 2017 14:33:48 -0500 (CDT)
Received: from localhost (localhost [127.0.0.1]) by delta.cs.cinvestav.mx (Postfix) with ESMTP id 93F8C5C1557; Fri, 14 Jul 2017 14:33:48 -0500 (CDT)
Date: Fri, 14 Jul 2017 14:33:48 -0500 (CDT)
From: Francisco Rodriguez- Henriquez <francisco@cs.cinvestav.mx>
To: Peter Dettman <peter.dettman@bouncycastle.org>
cc: "cfrg@irtf.org" <cfrg@irtf.org>, =?ISO-8859-15?Q?Julio_C=E9sar_Lopez?= <jlopez@ic.unicamp.br>, Thomaz Oliveira <thomaz.figueiredo@gmail.com>, huseyin.hisil@yasar.edu.tr, Armando Faz <armfazh@gmail.com>
In-Reply-To: <02899a12-8cf7-c318-32ea-9491ec2a22c2@bouncycastle.org>
Message-ID: <alpine.LFD.2.02.1707141329090.16576@delta.cs.cinvestav.mx>
References: <CAHOTMVKHA-yJR1oCyPtUp4-aJVc3dTdyxQHNo4xqnJt0hU6jVQ@mail.gmail.com> <CAMm+Lwgm8XzTBarZ1eFePTZGORorBJAeF7brDkhWGQKQVT0LPQ@mail.gmail.com> <CAMm+LwggT_AVv=KjzM1r=6UnkeK+g8zkticXFBDQ0cUXs_PP0A@mail.gmail.com> <CAHOTMVLHPFyi2VWpv85hrZ1MoXqeHYUv52wkMxjj3xp5B4V1cw@mail.gmail.com> <CAMm+Lwgfk1=yEJSbZbaZLvF5k5k66VVSx6MzKLM+DbUV7Ls6Xw@mail.gmail.com> <CAHOTMVK1gYrFiwd8f8zf2zPXYyCorp+jixkcY5FLhfHfv0NkWw@mail.gmail.com> <CAMm+LwjeZdR=ZGX0topN2w6P12jEmR-TQ8M9+anyETj43nbiqg@mail.gmail.com> <CAHOTMVL2e2UjVX6VKgHUbOHrb-gsU8kn_cxY1FdNrnj29cki9g@mail.gmail.com> <alpine.LFD.2.02.1703291804030.8996@delta.cs.cinvestav.mx> <alpine.LFD.2.02.1705111858040.25089@delta.cs.cinvestav.mx> <02899a12-8cf7-c318-32ea-9491ec2a22c2@bouncycastle.org>
User-Agent: Alpine 2.02 (LFD 1266 2009-07-14)
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; format=flowed; charset=US-ASCII
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/IvZzpVokzjyvBvOmdUCjAoeK7aU>
Subject: Re: [Cfrg] How to (pre-)compute a ladder [revised version]
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Fri, 14 Jul 2017 19:34:07 -0000

Hi Peter,

Please see my reply below.

Cheers,
Francisco
[on behalf of the authors]

On Fri, 16 Jun 2017, Peter Dettman wrote:

> Hi Francisco,
>
> I've updated my (java) implementations of X25519 and X448 in line with
> your revised paper. My rough benchmark results for a complete ECDH are
> -17.7% and -19.5% time required for X25519 and X448 respectively.

Great!
This is roughly in the same ballpark of what we are getting in our C 
implementation, which is available at,

https://github.com/armfazh/rfc7748_precomputed

[please check my previous email to this list]

> These are perhaps slightly more modest than the paper's estimates. Your
> paper already anticipates that (uncounted) field add/sub are significant
> in practice.

Right!

This effect appears to be more significant in the case of X25519 than in 
the case of X448.


> Part of the difference however is that my implementation of Algorithm 3
> handles the final 'q' bits using simple doublings, and removes redundant
> cswaps - just as Algorithm 5 does. Of course Alg. 3 is just as presented
> in RFC 7748, but it might be a fairer comparison to first apply to Alg.
> 3 those of your optimizations that are applicable.
>
> Also, my (32-bit) X448 implementation (Alg. 5) required a carry
> propagation for 'A' (line 10), due to tight bounds on limbs when
> squaring D, E. I did the same for (32-bit) X25519 although I haven't yet
> proved it necessary.

OK!
If you have time please compare against the C implementation mentioned 
above.

> An idea: for fixed-base X25519, why not precompute one doubling? i.e.
> just calculate (k/2) * 2P, needing only 2 final doublings (you even
> already have S of order 4). I am not sure whether this extends to
> precomputing (q-1) doublings.
>
> Another thought that occurred to me is that someone might get the idea
> to use your fixed-base ladder with some other point. Couldn't this go
> awry if that point were already "P + S" or similar? If so, a caution
> somewhere in the paper on preconditions for the fixed point might be
> advised.
>
> Regards,
> Pete Dettman

Thanks for both suggestions. We will carefully analyze both of them.


Cheers,
Francisco