[Cfrg] A note on how to (pre-)compute a ladder

Francisco Rodriguez- Henriquez <francisco@cs.cinvestav.mx> Thu, 30 March 2017 01:00 UTC

Return-Path: <francisco@cs.cinvestav.mx>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id D7BB0126D73 for <cfrg@ietfa.amsl.com>; Wed, 29 Mar 2017 18:00:58 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.903
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 ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id u8Cok4t96ynC for <cfrg@ietfa.amsl.com>; Wed, 29 Mar 2017 18:00:56 -0700 (PDT)
Received: from delta.cs.cinvestav.mx (delta.cs.cinvestav.mx []) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 9B6AE126CE8 for <cfrg@irtf.org>; Wed, 29 Mar 2017 18:00:56 -0700 (PDT)
Received: from localhost (localhost []) by delta.cs.cinvestav.mx (Postfix) with ESMTP id 6CC135C0A86; Wed, 29 Mar 2017 19:00:42 -0600 (CST)
X-Virus-Scanned: amavisd-new at cs.cinvestav.mx
Received: from delta.cs.cinvestav.mx ([]) by localhost (delta.cs.cinvestav.mx []) (amavisd-new, port 10024) with ESMTP id YUlj8S+CCHLv; Wed, 29 Mar 2017 19:00:41 -0600 (CST)
Received: by delta.cs.cinvestav.mx (Postfix, from userid 1507) id 1C46B5C0AFA; Wed, 29 Mar 2017 19:00:40 -0600 (CST)
Received: from localhost (localhost []) by delta.cs.cinvestav.mx (Postfix) with ESMTP id EBCEA5C0A86; Wed, 29 Mar 2017 19:00:40 -0600 (CST)
Date: Wed, 29 Mar 2017 19:00:40 -0600
From: Francisco Rodriguez- Henriquez <francisco@cs.cinvestav.mx>
To: "cfrg@irtf.org" <cfrg@irtf.org>
cc: Thomaz Oliveira <thomaz.figueiredo@gmail.com>, Julio César Lopez <jlopez@ic.unicamp.br>
In-Reply-To: <CAHOTMVL2e2UjVX6VKgHUbOHrb-gsU8kn_cxY1FdNrnj29cki9g@mail.gmail.com>
Message-ID: <alpine.LFD.2.02.1703291804030.8996@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>
User-Agent: Alpine 2.02 (LFD 1266 2009-07-14)
MIME-Version: 1.0
Content-Type: MULTIPART/MIXED; BOUNDARY="-141290138-920918062-1490834242=:8996"
Content-ID: <alpine.LFD.2.02.1703291838010.8996@delta.cs.cinvestav.mx>
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/tWr1cOAgXjqT5uDp_bnMF2ULr7s>
Subject: [Cfrg] A note on how to (pre-)compute a ladder
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: Thu, 30 Mar 2017 01:00:59 -0000

Dear CFRG community,

We would like to draw your attention to our IACR pre-print entitled,

"A note on how to (pre-)compute a ladder
Improving the performance of X25519 and X448"


For the point multiplication computation Q = kP, this note describes a 
right-to-left version of the Montgomery ladder, which is amenable for 
pre-computing multiples of the base point P. By requiring very modest 
memory resources and a small implementation effort, it obtains noticeable
performance improvements with respect to the RFC 7748 classical ladder 

We stress that our proposal fully complies with the RFC 7748 
specification, in the sense that given any arbitrary secret keys of Alice 
and Bob, our ladder generates exactly the same public keys that an 
implementation of the RFC 7748 would output.

As a way of illustration, in Appendix B of our note, we include a magma 
script, which given Alice and Bob private keys of RFC7748 Sec. 6.2, it 
computes the same public keys as specified in that document.

We would be delighted to receive feedback (including sightings of typos) 
from the CFRG community.

With best regards,

Thomaz Oliveira, Julio López and Francisco Rodríguez-Henríquez