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

Andrey Jivsov <crypto@brainhub.org> Sun, 17 August 2014 01:10 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 []) by ietfa.amsl.com (Postfix) with ESMTP id 2F6BA1A05F5 for <cfrg@ietfa.amsl.com>; Sat, 16 Aug 2014 18:10:40 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.799
X-Spam-Status: No, score=0.799 tagged_above=-999 required=5 tests=[BAYES_50=0.8, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, SPF_PASS=-0.001] autolearn=ham
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id MCSUqYPwu0Ej for <cfrg@ietfa.amsl.com>; Sat, 16 Aug 2014 18:10:37 -0700 (PDT)
Received: from qmta03.emeryville.ca.mail.comcast.net (qmta03.emeryville.ca.mail.comcast.net [IPv6:2001:558:fe2d:43:76:96:30:32]) by ietfa.amsl.com (Postfix) with ESMTP id 994B71A0584 for <cfrg@irtf.org>; Sat, 16 Aug 2014 18:10:37 -0700 (PDT)
Received: from omta22.emeryville.ca.mail.comcast.net ([]) by qmta03.emeryville.ca.mail.comcast.net with comcast id fd4K1o0011vN32cA3dAcEp; Sun, 17 Aug 2014 01:10:36 +0000
Received: from [] ([]) by omta22.emeryville.ca.mail.comcast.net with comcast id fdAb1o00C4uhcbK8idAbDr; Sun, 17 Aug 2014 01:10:36 +0000
Message-ID: <53F0010B.6080101@brainhub.org>
Date: Sat, 16 Aug 2014 18:10:35 -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" <cfrg@irtf.org>
Content-Type: multipart/mixed; boundary="------------020204080901010206010108"
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=comcast.net; s=q20140121; t=1408237836; bh=CXBIXSGTP6b23eHl53SwPXq5+HVYKbxxCQT3Tibqg/A=; h=Received:Received:Message-ID:Date:From:MIME-Version:To:Subject: Content-Type; b=t3bKITGuSxatcciElz+10aw+qeN2NJpyHcoLLF+0ceXDsnWryfvTdes7LMl3foa0W prwaOi/nfet7sEhrGsLDhPMB2EAVZM/jjNI2ntdhmwmP5TX9xfd1h/oJnu5odvtX0z 5t9CVMa2s+rLVqSe0GgZ8/3Z9XQjkEOVJz0G8fi5Q/dXD7xDWySx2hU4Kk2g8s+ATO xyGcBKxj+UHjSkbLFAWiQW5qdAyowoaI2uY7K3wWYSwRjZKfrQ5uiZ3wt8AD3v0QR5 n0jGDAHNINCtX7etJvhxt6nFrOGVyPn+AjJmKnSVdst9FshBDZPXqELD/HQHo2RLFg J0K4LDhMYb6yg==
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/QQ8m2LFI6HHTiQ_X4RGzMLalg2w
Subject: [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: Sun, 17 Aug 2014 01:10:40 -0000

I timed libsodium, curve25519-donna, MSR ECCLib, and openssl-master.

In all cases minor tweaks to the source code were added to measure and 
report the timing. I made sure to time the variable base scalar 
multiplication. I also timed the fixed base multiplication and 
precomputation (only needed for MSR ECCLib).

Operations are reported as operations per second. I used default compile 

MSR ECCLib was slightly faster in variable base operations. It uses 
assembler code.

Interestingly, MSR ECCLib Weierstrass a=-3 curves are only 10% slower 
than curve25519-donna. At the same time all pseudo-Mersenne prime curves 
are ~5 times faster than NIST P-256 (this is better than factor of 2 
back-of-envelope difference in modp multiplication performance)

The factor of 2+ improvement for fixed base calculation in MSR ECCLib is 
impressive. Note, however, the significant penalty that precalculation 
step adds. If the pre-calculation is included in timing, we could do 
~50% more EDH agreements with NIST P-256.

CPU: Intel(R) Core(TM) i5-3550 CPU @ 3.30GHz, no AVX2. Fedora Core 20 64 

modified tests in libsodium/test/default to take the timing:
crypto_scalarmult_curve25519_base: 15620.2 op/s
crypto_scalarmult_curve25519: 15602.8 op/s

make ./speed-curve25519-donna-c64 && ./speed-curve25519-donna-c64
63 us, 15722.1 op/s
(also modified to check variable base v.s. generator 9 -- no difference)

OpenSSL 1.0.1e-fips 11 Feb 2013:
openssl speed ecdhp256 (ECDH_compute_key)
  256 bit ecdh (nistp256)   0.0003s   3245.4  op      op/s
and from git://git.openssl.org/openssl.git:
  256 bit ecdh (nistp256)   0.0003s   3406.7  op      op/s


In the function that prints "Crypto operations: Weierstrass a=-3 over 
with variable base (baseecdh_secret_agreement_Jac256) 14047.9 op/sec
with fixed base (ecdh_keygen_Jac256) 35370 op/sec
table precomp (ecdh_generator_table_Jac256) 1284.03 op/sec
table precomp+keygen+variable base 1056.86 op/sec
"ECDH(E) runs in [...] 328926 cycles"

In the function that prints "Crypto operations: twisted Edwards a=-1 
over GF(2^256-189)"
with variable base (ecdh_secret_agreement_Ted256): 17482 op/sec
with fixed base (ecdh_keygen_Ted256) 35370 op/sec: 45762.9 op/sec
table precomp (ecdh_generator_table_Ted256) 1346.98 op/sec
table precomp+keygen+variable base 1195.89 op/sec
"ECDH(E) runs in [...] 261385 cycles"

memcpy of the 32 bytes: 595968511 op/sec, see attached code
( i.e. memcpy count / crypto_scalarmult_curve25519 count = 38042 )