Re: [Cfrg] Timing of libsodium, curve25519-donna, MSR ECCLib, and openssl-master

Andrey Jivsov <crypto@brainhub.org> Wed, 03 September 2014 07:25 UTC

Return-Path: <crypto@brainhub.org>
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 CA4521A004E for <cfrg@ietfa.amsl.com>; Wed, 3 Sep 2014 00:25:30 -0700 (PDT)
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, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, 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 7xXEtvyWDt1q for <cfrg@ietfa.amsl.com>; Wed, 3 Sep 2014 00:25:29 -0700 (PDT)
Received: from qmta01.emeryville.ca.mail.comcast.net (qmta01.emeryville.ca.mail.comcast.net [IPv6:2001:558:fe2d:43:76:96:30:16]) by ietfa.amsl.com (Postfix) with ESMTP id 1652A1A8701 for <cfrg@irtf.org>; Wed, 3 Sep 2014 00:24:48 -0700 (PDT)
Received: from omta02.emeryville.ca.mail.comcast.net ([76.96.30.19]) by qmta01.emeryville.ca.mail.comcast.net with comcast id mXFk1o0020QkzPwA1XQnhD; Wed, 03 Sep 2014 07:24:47 +0000
Received: from [192.168.1.2] ([71.202.164.227]) by omta02.emeryville.ca.mail.comcast.net with comcast id mXQm1o0044uhcbK8NXQns8; Wed, 03 Sep 2014 07:24:47 +0000
Message-ID: <5406C23E.80205@brainhub.org>
Date: Wed, 03 Sep 2014 00:24:46 -0700
From: Andrey Jivsov <crypto@brainhub.org>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.7.0
MIME-Version: 1.0
To: cfrg@irtf.org
X-Priority: 5 (Lowest)
References: <53F0010B.6080101@brainhub.org> <CD159876-F061-4EB8-B1DC-FAB8E4798E26@shiftleft.org> <53F108CF.4040704@brainhub.org> <53F18607.3000005@brainhub.org>
In-Reply-To: <53F18607.3000005@brainhub.org>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=comcast.net; s=q20140121; t=1409729087; bh=vkGvGliSE/hz9vNPV5ucq7yXHOOTtf8H+Q4wFVhHOcw=; h=Received:Received:Message-ID:Date:From:MIME-Version:To:Subject: Content-Type; b=E5zmRu61KOcvnuLtPAL5zPEsQUeWBcC7OWzB0AXVFj5wtlFlwUPkarEb3XaBR2QPe b2Jap4D0z5Yi/bdrM0SzJM72xRYOKoPXAc0MttZgJsbWB2VvZ50yeorCGuAUsJhZ05 PjZMcFrKaOmBo5R7wZmkxWv6wRmhH8KnrW3WqWciKzPWqKULFsDGo/gwoVUaMtbC3C osJa2azCRtlfnxrWqUQpeiL7DVsW3fXRfNf+7Nsk4a7SjgoY6lZhdtRbDNRvk6SnKC TaWiMqC1xDW0GdZBdyTz865I5TVuEuDtKN2a5jx4BmgvjQICmIAJcQDc0CYjoKhQp5 gGyWdNPOEPPCg==
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/e8xYp-oSakkECSkdY5G94E1RS5U
Subject: Re: [Cfrg] Timing of libsodium, curve25519-donna, MSR ECCLib, and openssl-master
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: Wed, 03 Sep 2014 07:25:30 -0000

In my previous message I missed that the openssl has a (non-default) 
configuration option that enables special handling of NIST primes with 
64 bit code that relies on the existence of a 128 bit integer.

On the same non-AVX2 machine this increases performance from ~ 3K to 5K 
op/s. This configuration of openssl code uses the same features (C only, 
64/128 bit) as curve25519-donna. Here is the updated number for the 
openssl along with the previously reported one for curve25519-donna for 
fair comparison:

./speed-curve25519-donna-c64:
70 us, 14131.5 op/s	

[andrey@ivy openssl-master]$ apps/openssl speed ecdhp256
                               op      op/s
  256 bit ecdh (nistp256)   0.0002s   5231.7

14131.5/5231.7=2.7

Intel(R) Core(TM) i5-3550 CPU @ 3.30GHz
cpu MHz		: 3281.308
No SpeedStep, Turboboost


Counting F(p) multiplies and squares as equal, OpenSSL's implementation 
of the P-256 uses a bit more than 11M, while X25519 (Curve25519) uses 
9M. This leaves with the observation that the 2^s-C prime contributes 
about a factor of 2 to the performance advantage of 2^255-19 v.s. 2^256 
- 2^224 + 2^192 + 2^96 - 1 in F(p).