[openssl-dev] [openssl.org #3810] [PATCH] Improved P256 ECC performance by means of a dedicated function for modular inversion modulo the P256 group order

[Andy Polyakov via RT]

Hi,

> This patch is a contribution to OpenSSL.
> 
> It concerns the P256 ECC implementation.
> 
> The patch improves upon our previous submission, by providing a dedicated function to perform modular inversion modulo the P256 group order.
> 
> Results:
> The performance improvements, for single threaded applications, compared to the current (development) version of OpenSSL are as follows.
> 
> (measured by "openssl speed" utility)
> 
> 
> On Architecture Codename Haswell:
> ECDSA sign: 1.28X
> ECDSA verify: 1.10X
> 
> On Architecture  Broadwell:
> ECDSA sign: 1.42X
> ECDSA verify: 1.18X
> 
> We license the whole submission under BSD license.
> 
> Developers and authors:
> ***************************************************************************
> Shay Gueron (1, 2), and Vlad Krasnov (3)
> (1) University of Haifa, Israel
> (2) Intel Corporation, Israel Development Center, Haifa, Israel
> (3) CloudFlare, Inc.
> ***************************************************************************

Attached is version refactored for updated layout. It's few percent
faster than original (for several small reasons, e.g. avoiding excessive
%rip-relative addressing because it doesn't fuse, optimizing
back-to-back value passing through registers in squaring) and probably
more readable (for example squaring uses $acc6 and $acc7). Then I've got
nervous around possibility of unaccounted carry and rearranged reduction
step in manner that precludes it. To be more specific here is fragment
of original reduction step:

	mov	8*1+.Lord(%rip), $t4
	mul	$t0
	add	$t1, $acc1
	adc	\$0, $t3
	add	$t4, $acc1

	mov	$t0, $t1
	adc	$t3, $acc2
	adc	\$0, $t1
	sub	$t0, $acc2
	sbb	\$0, $t1

Concern was that if $t0 happens to be all-ones, then you risk
unaccounted carry in last adc above. Well, upon closer look concern
appears to be false, but as it's a bit counter-intuitive alternative is
provided anyway.


-------------- next part --------------
A non-text attachment was scrubbed...
Name: ecp_nistz256_inv_ord.diff
Type: text/x-patch
Size: 38647 bytes
Desc: not available
URL: <http://mta.openssl.org/pipermail/openssl-dev/attachments/20151221/56ed6df4/attachment-0001.bin>