Re: [Cfrg] How to (pre-)compute a ladder [full C implementation]

Francisco Rodriguez- Henriquez <francisco@cs.cinvestav.mx> Fri, 14 July 2017 19:29 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 5FF4013171B for <cfrg@ietfa.amsl.com>; Fri, 14 Jul 2017 12:29:16 -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 v73_VuGDZO_g for <cfrg@ietfa.amsl.com>; Fri, 14 Jul 2017 12:29:14 -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 2B1FA12EAB0 for <cfrg@irtf.org>; Fri, 14 Jul 2017 12:29:13 -0700 (PDT)
Received: from localhost (localhost [127.0.0.1]) by delta.cs.cinvestav.mx (Postfix) with ESMTP id B654B5C1462; Fri, 14 Jul 2017 14:28:57 -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 QX-SPrFBaQ-X; Fri, 14 Jul 2017 14:28:56 -0500 (CDT)
Received: by delta.cs.cinvestav.mx (Postfix, from userid 1507) id 38E385C1557; Fri, 14 Jul 2017 14:28:56 -0500 (CDT)
Received: from localhost (localhost [127.0.0.1]) by delta.cs.cinvestav.mx (Postfix) with ESMTP id 299945C1462; Fri, 14 Jul 2017 14:28:56 -0500 (CDT)
Date: Fri, 14 Jul 2017 14:28:56 -0500 (CDT)
From: Francisco Rodriguez- Henriquez <francisco@cs.cinvestav.mx>
To: "cfrg@irtf.org" <cfrg@irtf.org>
cc: Thomaz Oliveira <thomaz.figueiredo@gmail.com>, =?ISO-8859-15?Q?Julio_C=E9sar_Lopez?= <jlopez@ic.unicamp.br>, huseyin.hisil@yasar.edu.tr, Armando Faz <armfazh@gmail.com>
In-Reply-To: <alpine.LFD.2.02.1705111858040.25089@delta.cs.cinvestav.mx>
Message-ID: <alpine.LFD.2.02.1707141340500.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>
User-Agent: Alpine 2.02 (LFD 1266 2009-07-14)
MIME-Version: 1.0
Content-Type: MULTIPART/MIXED; BOUNDARY="-141290138-2002586352-1500058027=:16576"
Content-ID: <alpine.LFD.2.02.1707141347280.16576@delta.cs.cinvestav.mx>
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/mZ6apUEEuSnrfoJ5sr2vVbbIzdY>
Subject: Re: [Cfrg] How to (pre-)compute a ladder [full C implementation]
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:29:16 -0000

Dear CFRG community,

We would like to share with you a full C implementation of the 
ladder procedure described in the IACR pre-print 2017/264:

        "How to (pre-)compute a ladder"

The C code can be downloaded from,
https://github.com/armfazh/rfc7748_precomputed

We are reporting the following benchmarked timings for 64-bit Intel 
architectures (table entries are given in clock cycles),


X25519 				Haswell 	Skylake
proposed Keygen rtl ladder	 90,895 	 72,571
Shared secret 	 		138,962 	107,942
S.Secret/Keygen speedup		  1.529	          1.487
overall D-H speedup               1.209           1.196


X448				Haswell 	Skylake
Proposed Keygen rtl Ladder	401,902 	322,040
Shared Secret 			670,747 	528,470
S.Secret/Keygen speedup           1.668           1.641
overall D-H speedup               1.251           1.243

Notes:

+ The Key generation reported above was computed using the proposed
   right-to-left ladder
+ The Shared secret was computed using the procedure described in the RFC
   7748 memo
+ The D-H speedup is obtained as the ratio,
 		2*shared secret / (shared secret + key generation);
+ In the sense explained in our pre-print, our procedure fully complies
   with the RFC 7748 memo.

With best regards,
Thomaz Oliveira, Julio López, Hüseyin Hisil, Armando Faz-Hernández and 
Francisco Rodríguez-Henríquez


On Thu, 11 May 2017, Francisco Rodriguez- Henriquez wrote:

> Dear CFRG community,
>
> We would like to draw your attention to an improved version of our IACR 
> pre-print 2017/264 now entitled:
>
> 	"How to (pre-)compute a ladder"
>
> In this revised version, we present an improved differential addition formula 
> that uses pre-computation to match the computational cost of the classical 
> Montgomery differential addition.
>
> Accordingly, our estimates suggest that a full implementation of our 
> pre-computable ladder proposal should outperform state-of-the-art software 
> implementations of the X25519 and X448 functions by a 40% speedup when 
> working in the fixed-point scenario.
>
> We would be delighted to receive feedback (including sightings of typos) from 
> the CFRG community.
>
> With best regards,
>
> Thomaz Oliveira, Julio López, Hüseyin Hisil and Francisco Rodríguez-Henríquez