Content-Type: text/plain; charset=windows-1252
Mime-Version: 1.0 (Mac OS X Mail 8.0 \(1971.5\))
From: Michael Hamburg <mike@shiftleft.org>
In-Reply-To: <53F0010B.6080101@brainhub.org>
Date: Sun, 17 Aug 2014 10:09:44 -0700
Content-Transfer-Encoding: quoted-printable
Message-Id: <CD159876-F061-4EB8-B1DC-FAB8E4798E26@shiftleft.org>
References: <53F0010B.6080101@brainhub.org>
To: Andrey Jivsov <crypto@brainhub.org>
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/vfB5tqOvsajBnG37LdiSgP0mnao
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] Timing of libsodium, curve25519-donna, MSR ECCLib,
 and openssl-master
Precedence: list


> On Aug 16, 2014, at 6:10 PM, Andrey Jivsov <crypto@brainhub.org> =
wrote:
>=20
> I timed libsodium, curve25519-donna, MSR ECCLib, and openssl-master.

Thanks for the data!

> 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).
>=20
> Operations are reported as operations per second. I used default =
compile options.
>=20
> MSR ECCLib was slightly faster in variable base operations. It uses =
assembler code.
>=20
> Interestingly, MSR ECCLib Weierstrass a=3D-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)
>=20
> 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.

Precomputation on the curve=92s base point shouldn't be included in =
timing, because it will be hard-coded in a production version.  Handling =
it will be cheap, unless it=92s big enough to cause CPU cache thrashing.

> CPU: Intel(R) Core(TM) i5-3550 CPU @ 3.30GHz, no AVX2. Fedora Core 20 =
64 bit.

Do you know if TurboBoost was on?  That CPU can boost to 3.7 GHz, so the =
cycle counts could be 12% different one way or another.

> https://github.com/jedisct1/libsodium
> 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
>=20
> https://github.com/agl/curve25519-donna:
> 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)
>=20
> 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
>=20
> MSR ECCLib =
http://research.microsoft.com/en-us/downloads/149804d4-b5f5-496f-9a17-a013=
b242c02d/
>=20
> In the function that prints "Crypto operations: Weierstrass a=3D-3 =
over GF(2^256-189)":
> 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"
>=20
> In the function that prints "Crypto operations: twisted Edwards a=3D-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"
>=20
> memcpy of the 32 bytes: 595968511 op/sec, see attached code
> ( i.e. memcpy count / crypto_scalarmult_curve25519 count =3D 38042 )
> <memcpy-timing.c>_______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg