[go] elliptic: assembly implementation of P256 for amd64

[Vlad Krasnov (Gerrit)]

Vlad Krasnov uploaded a change:
https://go-review.googlesource.com/8968

elliptic: assembly implementation of P256 for amd64

This is based on the implementation used in OpenSSL, from a
submission by Shay Gueron and myself. Besides using assembly,
this implementation employs several optimizations described in:

S.Gueron and V.Krasnov, "Fast prime field elliptic-curve
cryptography with 256-bit primes"

In addition a new and improved modular inverse modulo N is
implemented here. Also included performance tweaks by Andy
Polyakov from the OpenSSL team.

The performance measured on a Haswell based Macbook Pro shows 21X
speedup for the sign and 9X for the verify operations.
The operation BaseMult is 30X faster (and the Diffie-Hellman/ECDSA
key generation that use it are sped up as well).

The adaptation to Go with the help of Filippo Valsorda

Change-Id: I86a33636747d5c92f15e0c8344caa2e7e07e0028
---
M src/crypto/ecdsa/ecdsa.go
M src/crypto/ecdsa/ecdsa_test.go
M src/crypto/elliptic/elliptic.go
M src/crypto/elliptic/p256.go
A src/crypto/elliptic/p256_amd64.go
A src/crypto/elliptic/p256_math_amd64.s
6 files changed, 5,195 insertions(+), 2 deletions(-)




--
https://go-review.googlesource.com/8968

[Brad Fitzpatrick (Gerrit)]

Brad Fitzpatrick has posted comments on this change.

elliptic: assembly implementation of P256 for amd64

Patch Set 1:

R=agl

--
https://go-review.googlesource.com/8968
Gerrit-Reviewer: Adam Langley <a...@golang.org>
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>
Gerrit-HasComments: No

[Minux Ma (Gerrit)]

Minux Ma has posted comments on this change.

elliptic: assembly implementation of P256 for amd64

Patch Set 1:

(1 comment)

https://go-review.googlesource.com/#/c/8968/1/src/crypto/elliptic/p256_math_amd64.s
File src/crypto/elliptic/p256_math_amd64.s:

Line 5: // Copyright 2015 Intel Corporation
what's the copyright story for this file?

I don't remember any other Go package source file
to bear these kind of copyright notices without
any notices.

I don't know whether is ok, so I just bring up the
question.

--
https://go-review.googlesource.com/8968
Gerrit-Reviewer: Adam Langley <a...@golang.org>
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>

Gerrit-Reviewer: Minux Ma <mi...@golang.org>
Gerrit-HasComments: Yes

[Vlad Krasnov (Gerrit)]

Vlad Krasnov has posted comments on this change.

elliptic: assembly implementation of P256 for amd64

Patch Set 1:

> (1 comment)

The copyright is from submission to OpenSSL. I doubt I can remove it.
https://github.com/openssl/openssl/blob/master/crypto/ec/asm/ecp_nistz256-x86_64.pl
https://github.com/openssl/openssl/pull/263

--
https://go-review.googlesource.com/8968
Gerrit-Reviewer: Adam Langley <a...@golang.org>
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>
Gerrit-Reviewer: Minux Ma <mi...@golang.org>

Gerrit-Reviewer: Vlad Krasnov <vl...@cloudflare.com>
Gerrit-HasComments: No

[Adam Langley (Gerrit)]

Adam Langley has posted comments on this change.

elliptic: assembly implementation of P256 for amd64

Patch Set 1:

Typically we would have a corporate CLA from Intel for a submission like
this. I'll talk to counsel and see what they think.

[Adam Langley (Gerrit)]

Adam Langley has posted comments on this change.

elliptic: assembly implementation of P256 for amd64

Patch Set 1: Code-Review-2

> Typically we would have a corporate CLA from Intel for a submission
> like this. I'll talk to counsel and see what they think.

Word from counsel is that we can't accept this I'm afraid. Intel do have a
CLA on record, but Intel would need to submit it themselves in order for it
to apply.

Could you get Shay to submit it as an act of Intel under the already
executed CLA with Google?

[Adam Langley (Gerrit)]

Adam Langley has posted comments on this change.

elliptic: assembly implementation of P256 for amd64

Patch Set 1:

> The original code has been specifically released under the BSD.

The original code referenced above is Apache licensed, according to the
header.

--
https://go-review.googlesource.com/8968
Gerrit-Reviewer: Adam Langley <a...@golang.org>
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>

Gerrit-Reviewer: Filippo Valsorda <fil...@cloudflare.com>

[Filippo Valsorda (Gerrit)]

Filippo Valsorda has posted comments on this change.

elliptic: assembly implementation of P256 for amd64

Patch Set 1:

Mainly for my personal education: why wouldn't the "submit on behalf"
clause not apply?
https://groups.google.com/forum/#!topic/golang-dev/7pFzRRRDBW8

The original code has been specifically released under the BSD.

[Filippo Valsorda (Gerrit)]

Filippo Valsorda has posted comments on this change.

elliptic: assembly implementation of P256 for amd64

Patch Set 1:

Intel relicensed it in the latest revision:
https://rt.openssl.org/Ticket/Display.html?id=3810 Sorry for not making it
clear.

We would actually really appreciate directions on where to log the "paper
trail" and what copyright notices to retain in the code.

[Brad Fitzpatrick (Gerrit)]

Brad Fitzpatrick has posted comments on this change.

elliptic: assembly implementation of P256 for amd64

Patch Set 1:

https://rt.openssl.org/Ticket/Display.html?id=3810 is not a public URL.

[Filippo Valsorda (Gerrit)]

Filippo Valsorda has posted comments on this change.

elliptic: assembly implementation of P256 for amd64

Patch Set 1:

> https://rt.openssl.org/Ticket/Display.html?id=3810 is not a public URL.

I guess you mean for legal purposes, so neither is
https://github.com/openssl/openssl/pull/263/files (the associated PR)? Do
we have to wait for merge in OpenSSL?

Sorry for the hand-holding, I'm really out of my depth with Copyright
issues.

[Vlad Krasnov (Gerrit)]

Vlad Krasnov has posted comments on this change.

elliptic: assembly implementation of P256 for amd64

Patch Set 1:

https://rt.openssl.org/m/ticket/show?id=3149

Up to revision 7, the patch is licensed as BSD. Afterwards it was
relicensed to apache. But BSD still applies.

[Brad Fitzpatrick (Gerrit)]

Brad Fitzpatrick has posted comments on this change.

elliptic: assembly implementation of P256 for amd64

Patch Set 1:

No, I mean that URL requires some login username & password. I click it and
don't see any content except for an auth screen.

[Filippo Valsorda (Gerrit)]

Filippo Valsorda has posted comments on this change.

elliptic: assembly implementation of P256 for amd64

Patch Set 1:

> No, I mean that URL requires some login username & password. I
> click it and don't see any content except for an auth screen.

Wow. Google indexes the auth'd URLs which make a session:

https://rt.openssl.org/Ticket/Display.html?id=3810&user=guest&pass=guest

[Vlad Krasnov (Gerrit)]

Vlad Krasnov has posted comments on this change.

elliptic: assembly implementation of P256 for amd64

Patch Set 1:

Did you reach some kind of a decision?

Would a written consent from Intel help?

I don't think Intel will submit the code directly.

[Adam Langley (Gerrit)]

Adam Langley has posted comments on this change.

elliptic: assembly implementation of P256 for amd64

Patch Set 1:

> Did you reach some kind of a decision?
>
> Would a written consent from Intel help?
>
> I don't think Intel will submit the code directly.

I do see that the updated patch from Intel on the OpenSSL RT changes the
license to "This software is dual licensed under the Apache V.2.0 and BSD
licenses". I'll check again with counsel.

[Vlad Krasnov (Gerrit)]

Reviewers: Adam Langley

Vlad Krasnov uploaded a new patch set:

https://go-review.googlesource.com/8968

elliptic: assembly implementation of P256 for amd64

This is based on the implementation used in OpenSSL, from a
submission by Shay Gueron and myself. Besides using assembly,
this implementation employs several optimizations described in:

S.Gueron and V.Krasnov, "Fast prime field elliptic-curve
cryptography with 256-bit primes"

In addition a new and improved modular inverse modulo N is
implemented here. Also included performance tweaks by Andy
Polyakov from the OpenSSL team.

The performance measured on a Haswell based Macbook Pro shows 21X
speedup for the sign and 9X for the verify operations.
The operation BaseMult is 30X faster (and the Diffie-Hellman/ECDSA
key generation that use it are sped up as well).

The adaptation to Go with the help of Filippo Valsorda

Updated the submission for faster verify/ecdh, fixed some asm syntax and
API problems and added benchmarks.

Change-Id: I86a33636747d5c92f15e0c8344caa2e7e07e0028
---
M src/crypto/ecdsa/ecdsa.go
M src/crypto/ecdsa/ecdsa_test.go

M src/crypto/elliptic/elliptic_test.go
M src/crypto/elliptic/p256.go
A src/crypto/elliptic/p256_amd64.go
A src/crypto/elliptic/p256_asm_amd64.s
6 files changed, 5,231 insertions(+), 5 deletions(-)

[Adam Langley (Gerrit)]

Adam Langley has posted comments on this change.

elliptic: assembly implementation of P256 for amd64

Patch Set 2:

(This is still grinding through legal.)

--
https://go-review.googlesource.com/8968
Gerrit-Reviewer: Adam Langley <a...@golang.org>
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>
Gerrit-Reviewer: Filippo Valsorda <fil...@cloudflare.com>
Gerrit-Reviewer: Minux Ma <mi...@golang.org>
Gerrit-Reviewer: Vlad Krasnov <vl...@cloudflare.com>

Gerrit-HasComments: No

[Russ Cox (Gerrit)]

Russ Cox has posted comments on this change.

elliptic: assembly implementation of P256 for amd64

Patch Set 2: Code-Review-2

(2 comments)

I want both agl and me to verify the resolution of the copyright issues
here.

https://go-review.googlesource.com/#/c/8968/2/src/crypto/elliptic/p256_asm_amd64.s
File src/crypto/elliptic/p256_asm_amd64.s:

Line 5: // Copyright 2015 Intel Corporation

This is not okay. This is a copyright notice without a license giving the
terms of use. I know agl@ is working with you on resolving this, but the
final commit absolutely must make the situation in this file clearer than
these two lines.

Also, we try to avoid additional notice requirements. The best way to get
this code submitted would be to make it covered by the existing CLAs. In
particular, if you work for CloudFlare then the right thing to do for your
part of this code is to get CloudFlare to do a CLA and then remove the
Copyright CloudFlare line below.


Line 10: // S.Gueron and V.Krasnov, "Fast prime field elliptic-curve
cryptography with
Link please?

--
https://go-review.googlesource.com/8968
Gerrit-Reviewer: Adam Langley <a...@golang.org>
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>
Gerrit-Reviewer: Filippo Valsorda <fil...@cloudflare.com>
Gerrit-Reviewer: Minux Ma <mi...@golang.org>

Gerrit-Reviewer: Russ Cox <r...@golang.org>
Gerrit-Reviewer: Vlad Krasnov <vl...@cloudflare.com>
Gerrit-HasComments: Yes

[Vlad Krasnov (Gerrit)]

Vlad Krasnov has posted comments on this change.

elliptic: assembly implementation of P256 for amd64

Patch Set 2:

(2 comments)

https://go-review.googlesource.com/#/c/8968/2/src/crypto/elliptic/p256_asm_amd64.s
File src/crypto/elliptic/p256_asm_amd64.s:

Line 5: // Copyright 2015 Intel Corporation
> This is not okay. This is a copyright notice without a license giving the
> t

We at CloudFlare can remove anything, but I am afraid that the Intel notice
got to stay. It comes with BSD license.
I believe that is the showstopper here.


Line 10: // S.Gueron and V.Krasnov, "Fast prime field elliptic-curve
cryptography with
> Link please?
http://link.springer.com/article/10.1007%2Fs13389-014-0090-x

[Damian Gryski (Gerrit)]

Damian Gryski has posted comments on this change.

elliptic: assembly implementation of P256 for amd64

Patch Set 2:

(1 comment)

https://go-review.googlesource.com/#/c/8968/2/src/crypto/elliptic/p256_asm_amd64.s
File src/crypto/elliptic/p256_asm_amd64.s:

Line 10: // S.Gueron and V.Krasnov, "Fast prime field elliptic-curve
cryptography with
> http://link.springer.com/article/10.1007%2Fs13389-014-0090-x
Can we use https://eprint.iacr.org/2013/816.pdf which has no paywall?

--
https://go-review.googlesource.com/8968
Gerrit-Reviewer: Adam Langley <a...@golang.org>
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>

Gerrit-Reviewer: Damian Gryski <dgr...@gmail.com>

[Adam Langley (Gerrit)]

Adam Langley has posted comments on this change.

elliptic: assembly implementation of P256 for amd64

Patch Set 2:

I've consulted with our lawyers and with Intel. Intel do not wish to
publish this code under the Go license and having bits of the Go repo under
different licenses is sufficient unpleasant that counsel didn't want to
entertain the idea.

I'm afraid that, without Intel's permission, it doesn't appear that this
change can move forward.

--
https://go-review.googlesource.com/8968
Gerrit-Reviewer: Adam Langley <a...@golang.org>
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>
Gerrit-Reviewer: Damian Gryski <dgr...@gmail.com>
Gerrit-Reviewer: Filippo Valsorda <fil...@cloudflare.com>
Gerrit-Reviewer: Minux Ma <mi...@golang.org>
Gerrit-Reviewer: Russ Cox <r...@golang.org>
Gerrit-Reviewer: Vlad Krasnov <vl...@cloudflare.com>

Gerrit-HasComments: No

[adam...@gmail.com]

Not being able to deal with something licensed under Apache v2 seems like a major showstopper that will inevitably lead to more issues down the road guys. It doesn't get much less restrictive than Apache v2. I would either figure out a way to accept it or change dual license Go, although I realize I'm not the one meeting with legal here (thank some deity!).

-Adam

[Ian Lance Taylor (Gerrit)]

Ian Lance Taylor has posted comments on this change.

elliptic: assembly implementation of P256 for amd64

Patch Set 2:

(In reply to a mailing list message that was not attached here.)

From my point of view, the issue with multiple different licenses is not
the restrictions of the license (which I agree are minimal). It's the
requirements on the end user. As far as I can tell, using the Intel code
directly will require all people who distribute binaries written in Go to
include a copy of the Intel copyright notice in their documentation, along
with the Go copyright notice that they are already required to include.
That is not an imposition to add lightly.

We could avoid this if Intel were willing to sign a copyright disclaimer
for purposes of using this code in the Go distribution, but apparently (I
was not in the meeting) they are not.

This leaves us with only unpalatable choices. There is no obvious right
answer.

--
https://go-review.googlesource.com/8968
Gerrit-Reviewer: Adam Langley <a...@golang.org>
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>
Gerrit-Reviewer: Damian Gryski <dgr...@gmail.com>
Gerrit-Reviewer: Filippo Valsorda <fil...@cloudflare.com>

Gerrit-Reviewer: Ian Lance Taylor <ia...@golang.org>

[a...@develooper.com]

On Friday, May 22, 2015 at 11:54:59 AM UTC-7, adam...@gmail.com wrote:
> Not being able to deal with something licensed under Apache v2 seems like a major showstopper that will inevitably lead to more issues down the road guys. It doesn't get much less restrictive than Apache v2.

BSD and MIT are much less restrictive for contributors than Apache v2.


Ask

[Russ Cox (Gerrit)]

Russ Cox has posted comments on this change.

elliptic: assembly implementation of P256 for amd64

Patch Set 2:

R=close
To clear from dashboard.

[j.e....@gmail.com]

On Friday, May 15, 2015 at 9:32:12 AM UTC-7, Vlad Krasnov (Gerrit) wrote:
> Vlad Krasnov has posted comments on this change.
>
> elliptic: assembly implementation of P256 for amd64
>
> Patch Set 2:
>
> (2 comments)
>
> https://go-review.googlesource.com/#/c/8968/2/src/crypto/elliptic/p256_asm_amd64.s
> File src/crypto/elliptic/p256_asm_amd64.s:
>
> Line 5: // Copyright 2015 Intel Corporation
> > This is not okay. This is a copyright notice without a license giving the
> > t
> We at CloudFlare can remove anything, but I am afraid that the Intel notice
> got to stay. It comes with BSD license.

Vlad, it sounds like no matter what the disposition of this CL/code review, it would promote the reuse of this code to add the exact version of the BSD license (there are serveral variants) that Intel licensed the code under to the p256_asm_amd64.s file. It would be very wise and helpful to see the license right under the Intel copyright, so that the BSD license is clearly present after the copyright and there is no confusion about the license status of the file.

[Adam Langley (Gerrit)]

Adam Langley has posted comments on this change.

elliptic: assembly implementation of P256 for amd64

Patch Set 2: -Code-Review

Intel have submitted their underlying P-256 code under CLA now so I'm
reviving this change.

[Vlad Krasnov (Gerrit)]

Vlad Krasnov has posted comments on this change.

elliptic: assembly implementation of P256 for amd64

Patch Set 2:

Those are good news. Shall we attempt to make it for the freeze?

[Brad Fitzpatrick (Gerrit)]

Brad Fitzpatrick has posted comments on this change.

elliptic: assembly implementation of P256 for amd64

Patch Set 2:

Yes, please do. Upload a new version of the patch with the previous
comments addressed.

(Aside for Googlers doing CLA compliance verifications, see notes in:
http://go/p256intel)

[Vlad Krasnov (Gerrit)]

Reviewers: Russ Cox, Adam Langley

Vlad Krasnov uploaded a new patch set:
https://go-review.googlesource.com/8968

elliptic: assembly implementation of P256 for amd64

This is based on the implementation used in OpenSSL, from a
submission by Shay Gueron and myself. Besides using assembly,
this implementation employs several optimizations described in:

S.Gueron and V.Krasnov, "Fast prime field elliptic-curve

cryptography with 256-bit primes"

In addition a new and improved modular inverse modulo N is
implemented here. Also included performance tweaks by Andy
Polyakov from the OpenSSL team.

The performance measured on a Haswell based Macbook Pro shows 21X
speedup for the sign and 9X for the verify operations.
The operation BaseMult is 30X faster (and the Diffie-Hellman/ECDSA
key generation that use it are sped up as well).

The adaptation to Go with the help of Filippo Valsorda

Updated the submission for faster verify/ecdh, fixed some asm syntax and
API problems and added benchmarks.

Change-Id: I86a33636747d5c92f15e0c8344caa2e7e07e0028
---
M src/crypto/ecdsa/ecdsa.go
M src/crypto/ecdsa/ecdsa_test.go
M src/crypto/elliptic/elliptic_test.go
M src/crypto/elliptic/p256.go
A src/crypto/elliptic/p256_amd64.go
A src/crypto/elliptic/p256_asm_amd64.s

6 files changed, 5,229 insertions(+), 5 deletions(-)

[Klaus Post (Gerrit)]

Klaus Post has posted comments on this change.

elliptic: assembly implementation of P256 for amd64

Patch Set 3:

(9 comments)

Great to hear this is moving forward!

I am not an expert on the internals, but I did a superficial review.

I would really like if functions in "p256_amd64.go" had some descriptions.

https://go-review.googlesource.com/#/c/8968/3/src/crypto/elliptic/p256_amd64.go
File src/crypto/elliptic/p256_amd64.go:

Line 166: }
This drops values silently if len(Bits) > 4


Line 232: func p256PointToAffine(in *p256Point) (xxOut, yyOut *big.Int) {
Is there any reason this isn't a method on p256Point called "Affine"?


Line 353: func p256BaseMult(r *p256Point, scalar []uint64) {
This writes to 'r', so it would be more clear if this was a method.


Line 389: func p256ScalarMult(r, p *p256Point, scalar []uint64) {
I cannot see from the code if this writes to 'p'. If it doesn't, it should
probably be a method with 'r'.


https://go-review.googlesource.com/#/c/8968/3/src/crypto/elliptic/p256_asm_amd64.s
File src/crypto/elliptic/p256_asm_amd64.s:

Line 81: PSHUFB X13, X12
SSSE3 instruction. I cannot see any check if the CPU supports this.


Line 411: MOVQ DX, t1
This move seems unnecesary. 'DX' doesn't appear to be overwritten
before 't1' is used. I don't really see any pipelining benefits. (+several
more below)


Line 837: MOVQ DX, t1
Again, it appears to have unneeded moved


Line 1363: MOVQ mul1, hlp
Unneeded move?


Line 1568: MOVQ DX, acc4
Unneeded move?

--
https://go-review.googlesource.com/8968
Gerrit-Reviewer: Adam Langley <a...@golang.org>
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>
Gerrit-Reviewer: Damian Gryski <dgr...@gmail.com>
Gerrit-Reviewer: Filippo Valsorda <fil...@cloudflare.com>
Gerrit-Reviewer: Ian Lance Taylor <ia...@golang.org>

Gerrit-Reviewer: Klaus Post <klau...@gmail.com>

Gerrit-Reviewer: Minux Ma <mi...@golang.org>
Gerrit-Reviewer: Russ Cox <r...@golang.org>
Gerrit-Reviewer: Vlad Krasnov <vl...@cloudflare.com>

Gerrit-HasComments: Yes

[Vlad Krasnov (Gerrit)]

Vlad Krasnov has posted comments on this change.

elliptic: assembly implementation of P256 for amd64

Patch Set 3:

(4 comments)

https://go-review.googlesource.com/#/c/8968/3/src/crypto/elliptic/p256_amd64.go
File src/crypto/elliptic/p256_amd64.go:

Line 166: }
> This drops values silently if len(Bits) > 4

It is only called from p256GetScalar, and can never have more than 256 bits

Line 232: func p256PointToAffine(in *p256Point) (xxOut, yyOut *big.Int) {
> Is there any reason this isn't a method on p256Point called "Affine"?

No reason, the two options are equivalent.

https://go-review.googlesource.com/#/c/8968/3/src/crypto/elliptic/p256_asm_amd64.s
File src/crypto/elliptic/p256_asm_amd64.s:

Line 81: PSHUFB X13, X12
> SSSE3 instruction. I cannot see any check if the CPU supports this.

Is there a single IA64 CPU that does not support SSSE3?

Line 411: MOVQ DX, t1
> This move seems unnecesary. 'DX' doesn't appear to be overwritten
> before 't

DX is overwritten by MULW

[Klaus Post (Gerrit)]

Klaus Post has posted comments on this change.

elliptic: assembly implementation of P256 for amd64

Patch Set 3:

(6 comments)

https://go-review.googlesource.com/#/c/8968/3/src/crypto/elliptic/p256_amd64.go
File src/crypto/elliptic/p256_amd64.go:

Line 232: func p256PointToAffine(in *p256Point) (xxOut, yyOut *big.Int) {

> No reason, the two options are equivalent.

IMO, it it "nicer" as a method, though no biggie.

https://go-review.googlesource.com/#/c/8968/3/src/crypto/elliptic/p256_asm_amd64.s
File src/crypto/elliptic/p256_asm_amd64.s:

Line 81: PSHUFB X13, X12

> Is there a single IA64 CPU that does not support SSSE3?

Yes, many. Especially AMD was slow to adopt SSSE3.

SSSE3 MUST be checked, otherwise another way of splatting should be used.

Line 411: MOVQ DX, t1

> DX is overwritten by MULW

Done

Line 837: MOVQ DX, t1
> Again, it appears to have unneeded moved

Done

Line 1363: MOVQ mul1, hlp
> Unneeded move?

Done

Line 1568: MOVQ DX, acc4
> Unneeded move?

Done

[Vlad Krasnov (Gerrit)]

Vlad Krasnov has posted comments on this change.

elliptic: assembly implementation of P256 for amd64

Patch Set 3:

(1 comment)

https://go-review.googlesource.com/#/c/8968/3/src/crypto/elliptic/p256_asm_amd64.s
File src/crypto/elliptic/p256_asm_amd64.s:

Line 81: PSHUFB X13, X12

> Yes, many. Especially AMD was slow to adopt SSSE3.

Indeed, Athlons and Phenoms ...
This instruction is not strictly required. Easier to replace than check
CPUID.

[Vlad Krasnov (Gerrit)]

Reviewers: Russ Cox, Adam Langley

Vlad Krasnov uploaded a new patch set:
https://go-review.googlesource.com/8968

elliptic: assembly implementation of P256 for amd64

This is based on the implementation used in OpenSSL, from a
submission by Shay Gueron and myself. Besides using assembly,
this implementation employs several optimizations described in:

S.Gueron and V.Krasnov, "Fast prime field elliptic-curve
cryptography with 256-bit primes"

In addition a new and improved modular inverse modulo N is
implemented here. Also included performance tweaks by Andy
Polyakov from the OpenSSL team.

The performance measured on a Haswell based Macbook Pro shows 21X
speedup for the sign and 9X for the verify operations.
The operation BaseMult is 30X faster (and the Diffie-Hellman/ECDSA
key generation that use it are sped up as well).

The adaptation to Go with the help of Filippo Valsorda

Updated the submission for faster verify/ecdh, fixed some asm syntax and
API problems and added benchmarks.

Change-Id: I86a33636747d5c92f15e0c8344caa2e7e07e0028
---
M src/crypto/ecdsa/ecdsa.go
M src/crypto/ecdsa/ecdsa_test.go
M src/crypto/elliptic/elliptic_test.go
M src/crypto/elliptic/p256.go
A src/crypto/elliptic/p256_amd64.go
A src/crypto/elliptic/p256_asm_amd64.s

6 files changed, 5,228 insertions(+), 5 deletions(-)

[Brad Fitzpatrick (Gerrit)]

Brad Fitzpatrick has posted comments on this change.

elliptic: assembly implementation of P256 for amd64

Patch Set 4:

(4 comments)

https://go-review.googlesource.com/#/c/8968/4//COMMIT_MSG
Commit Message:

Line 7: elliptic: assembly implementation of P256 for amd64
fix the part before the colon to be the packages this touches.

crypto/ecdsa, crypto/elliptic: assembly implementation of P256 for amd64


Line 17: implemented here. Also included performance tweaks by Andy
are those performance tweaks suitably licensed? do we need the OpenSSL
advertising?


Line 25: The adaptation to Go with the help of Filippo Valsorda
CLA on file for him?


Line 27: Updated the submission for faster verify/ecdh, fixed some asm

syntax and API problems and added benchmarks.

wrap this line

--
https://go-review.googlesource.com/8968
Gerrit-Reviewer: Adam Langley <a...@golang.org>
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>
Gerrit-Reviewer: Damian Gryski <dgr...@gmail.com>
Gerrit-Reviewer: Filippo Valsorda <fil...@cloudflare.com>
Gerrit-Reviewer: Ian Lance Taylor <ia...@golang.org>
Gerrit-Reviewer: Klaus Post <klau...@gmail.com>
Gerrit-Reviewer: Minux Ma <mi...@golang.org>
Gerrit-Reviewer: Russ Cox <r...@golang.org>
Gerrit-Reviewer: Vlad Krasnov <vl...@cloudflare.com>

Gerrit-HasComments: Yes

[Vlad Krasnov (Gerrit)]

Reviewers: Russ Cox, Adam Langley

Vlad Krasnov uploaded a new patch set:
https://go-review.googlesource.com/8968

crypto/elliptic,crypto/ecdsa: P256 amd64 assembly

This is based on the implementation used in OpenSSL, from a
submission by Shay Gueron and myself. Besides using assembly,
this implementation employs several optimizations described in:

S.Gueron and V.Krasnov, "Fast prime field elliptic-curve
cryptography with 256-bit primes"

In addition a new and improved modular inverse modulo N is
implemented here.

The performance measured on a Haswell based Macbook Pro shows 21X
speedup for the sign and 9X for the verify operations.
The operation BaseMult is 30X faster (and the Diffie-Hellman/ECDSA
key generation that use it are sped up as well).

The adaptation to Go with the help of Filippo Valsorda

Updated the submission for faster verify/ecdh, fixed some asm syntax
and API problems and added benchmarks.

Change-Id: I86a33636747d5c92f15e0c8344caa2e7e07e0028
---
M src/crypto/ecdsa/ecdsa.go
M src/crypto/ecdsa/ecdsa_test.go
M src/crypto/elliptic/elliptic_test.go
M src/crypto/elliptic/p256.go
A src/crypto/elliptic/p256_amd64.go
A src/crypto/elliptic/p256_asm_amd64.s
6 files changed, 5,228 insertions(+), 5 deletions(-)

[Vlad Krasnov (Gerrit)]

Vlad Krasnov has posted comments on this change.

crypto/elliptic,crypto/ecdsa: P256 amd64 assembly

Patch Set 5:

(4 comments)

https://go-review.googlesource.com/#/c/8968/4//COMMIT_MSG
Commit Message:

Line 7: crypto/elliptic,crypto/ecdsa: P256 amd64 assembly

> fix the part before the colon to be the packages this touches.

Done


Line 17: implemented here.

> are those performance tweaks suitably licensed? do we need the OpenSSL
> adve

They are very minor, I removed it


Line 25:

> CLA on file for him?

Yes there is


Line 27: and API problems and added benchmarks.
> wrap this line
Done

--
https://go-review.googlesource.com/8968
Gerrit-Reviewer: Adam Langley <a...@golang.org>
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>
Gerrit-Reviewer: Damian Gryski <dgr...@gmail.com>
Gerrit-Reviewer: Filippo Valsorda <fil...@cloudflare.com>
Gerrit-Reviewer: Ian Lance Taylor <ia...@golang.org>
Gerrit-Reviewer: Klaus Post <klau...@gmail.com>
Gerrit-Reviewer: Minux Ma <mi...@golang.org>
Gerrit-Reviewer: Russ Cox <r...@golang.org>
Gerrit-Reviewer: Vlad Krasnov <vl...@cloudflare.com>

Gerrit-HasComments: Yes

[Brad Fitzpatrick (Gerrit)]

Brad Fitzpatrick has posted comments on this change.

crypto/elliptic,crypto/ecdsa: P256 amd64 assembly

Patch Set 5:

(1 comment)

https://go-review.googlesource.com/#/c/8968/4//COMMIT_MSG
Commit Message:

Line 17: implemented here.

> They are very minor, I removed it

You only removed the attribution for him in the commit message from
patchset 4 to patchset 5. You didn't remove his code.

[Vlad Krasnov (Gerrit)]

Vlad Krasnov has posted comments on this change.

crypto/elliptic,crypto/ecdsa: P256 amd64 assembly

Patch Set 5:

(1 comment)

https://go-review.googlesource.com/#/c/8968/4//COMMIT_MSG
Commit Message:

Line 17: implemented here.

> You only removed the attribution for him in the commit message from
> patchse

There is no code per se ...

[Adam Langley (Gerrit)]

Reviewers: Russ Cox

Adam Langley uploaded a new patch set:

https://go-review.googlesource.com/8968

crypto/elliptic,crypto/ecdsa: P256 amd64 assembly

This is based on the implementation used in OpenSSL, from a
submission by Shay Gueron and myself. Besides using assembly,
this implementation employs several optimizations described in:

S.Gueron and V.Krasnov, "Fast prime field elliptic-curve
cryptography with 256-bit primes"

In addition a new and improved modular inverse modulo N is
implemented here.

The performance measured on a Haswell based Macbook Pro shows 21X
speedup for the sign and 9X for the verify operations.
The operation BaseMult is 30X faster (and the Diffie-Hellman/ECDSA
key generation that use it are sped up as well).

The adaptation to Go with the help of Filippo Valsorda

Updated the submission for faster verify/ecdh, fixed some asm syntax

and API problems and added benchmarks.

Change-Id: I86a33636747d5c92f15e0c8344caa2e7e07e0028
---
M src/crypto/ecdsa/ecdsa.go
M src/crypto/ecdsa/ecdsa_test.go
M src/crypto/elliptic/elliptic_test.go
M src/crypto/elliptic/p256.go
A src/crypto/elliptic/p256_amd64.go
A src/crypto/elliptic/p256_asm_amd64.s

6 files changed, 5,251 insertions(+), 5 deletions(-)

[Adam Langley (Gerrit)]

Adam Langley has posted comments on this change.

crypto/elliptic,crypto/ecdsa: P256 amd64 assembly

Patch Set 5:

Please check that the changes that I made in patch set six are ok with you.
There's nothing major in there.

I am still pondering whether the precomputed table should be generated with
a once rather than being 150KB of static data in the binary.

--
https://go-review.googlesource.com/8968
Gerrit-Reviewer: Adam Langley <a...@golang.org>
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>
Gerrit-Reviewer: Damian Gryski <dgr...@gmail.com>
Gerrit-Reviewer: Filippo Valsorda <fil...@cloudflare.com>
Gerrit-Reviewer: Ian Lance Taylor <ia...@golang.org>
Gerrit-Reviewer: Klaus Post <klau...@gmail.com>
Gerrit-Reviewer: Minux Ma <mi...@golang.org>
Gerrit-Reviewer: Russ Cox <r...@golang.org>
Gerrit-Reviewer: Vlad Krasnov <vl...@cloudflare.com>

Gerrit-HasComments: No

[Russ Cox (Gerrit)]

Russ Cox has posted comments on this change.

crypto/elliptic,crypto/ecdsa: P256 amd64 assembly

Patch Set 6: -Code-Review

Removing -2 since the copyright/CLA issues have been resolved per agl@.

[Vlad Krasnov (Gerrit)]

Vlad Krasnov has posted comments on this change.

crypto/elliptic,crypto/ecdsa: P256 amd64 assembly

Patch Set 6: Code-Review+1

LGTM. About the table: originally I intended the table in OpenSSL to be
generated with a call to a precompute function, the way elliptic curves
were designed assumed this function was called before repeated curve usage,
and if you needed the curve only once, you would not call it. In reality no
one ever called the precompute function, and as a hack I just bundled the
static table.
In Go we could use once or init() to generate a table, but the problem is
that it would needlessly (and visibly) slow down "only use once" operations
on P256.

[Klaus Post (Gerrit)]

Klaus Post has posted comments on this change.

crypto/elliptic,crypto/ecdsa: P256 amd64 assembly

Patch Set 6:

> I am still pondering whether the precomputed table should be generated
> with a once rather than being 150KB of static data in the binary.

Just wondering - how big is the calculation cost?

Could it be a calculated on first use, so it doesn't get a startup cost?

[Minux Ma (Gerrit)]

Minux Ma has posted comments on this change.

crypto/elliptic,crypto/ecdsa: P256 amd64 assembly

Patch Set 6:

> >I am still pondering whether the precomputed table should be
> generated with a once rather than being 150KB of static data in the
> binary.
>
> Just wondering - how big is the calculation cost?
>
> Could it be a calculated on first use, so it doesn't get a startup
> cost?

Yeah, it's better to not bloat every Go binary using crypto/tls.

[Vlad Krasnov (Gerrit)]

Reviewers: Russ Cox, Adam Langley

Vlad Krasnov uploaded a new patch set:

https://go-review.googlesource.com/8968

crypto/elliptic,crypto/ecdsa: P256 amd64 assembly

This is based on the implementation used in OpenSSL, from a
submission by Shay Gueron and myself. Besides using assembly,
this implementation employs several optimizations described in:

S.Gueron and V.Krasnov, "Fast prime field elliptic-curve
cryptography with 256-bit primes"

In addition a new and improved modular inverse modulo N is
implemented here.

The performance measured on a Haswell based Macbook Pro shows 21X
speedup for the sign and 9X for the verify operations.
The operation BaseMult is 30X faster (and the Diffie-Hellman/ECDSA
key generation that use it are sped up as well).

The adaptation to Go with the help of Filippo Valsorda

Updated the submission for faster verify/ecdh, fixed some asm syntax
and API problems and added benchmarks.

Change-Id: I86a33636747d5c92f15e0c8344caa2e7e07e0028
---
M src/crypto/ecdsa/ecdsa.go
M src/crypto/ecdsa/ecdsa_test.go
M src/crypto/elliptic/elliptic_test.go
M src/crypto/elliptic/p256.go
A src/crypto/elliptic/p256_amd64.go
A src/crypto/elliptic/p256_asm_amd64.s

6 files changed, 2,930 insertions(+), 5 deletions(-)

[Vlad Krasnov (Gerrit)]

Vlad Krasnov has posted comments on this change.

crypto/elliptic,crypto/ecdsa: P256 amd64 assembly

Patch Set 7:

I removed the precomputed table. The table is now generated on first use.
On my Has...@2.6GHz it takes about 17ms.

--
https://go-review.googlesource.com/8968
Gerrit-Reviewer: Adam Langley <a...@golang.org>
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>
Gerrit-Reviewer: Damian Gryski <dgr...@gmail.com>
Gerrit-Reviewer: Filippo Valsorda <fil...@cloudflare.com>
Gerrit-Reviewer: Ian Lance Taylor <ia...@golang.org>
Gerrit-Reviewer: Klaus Post <klau...@gmail.com>
Gerrit-Reviewer: Minux Ma <mi...@golang.org>
Gerrit-Reviewer: Russ Cox <r...@golang.org>
Gerrit-Reviewer: Vlad Krasnov <vl...@cloudflare.com>

Gerrit-HasComments: No

[Adam Langley (Gerrit)]

Reviewers: Russ Cox, Vlad Krasnov

Adam Langley uploaded a new patch set:

[Adam Langley (Gerrit)]

Adam Langley has posted comments on this change.

crypto/elliptic,crypto/ecdsa: P256 amd64 assembly

Patch Set 8: Run-TryBot+1

--
https://go-review.googlesource.com/8968
Gerrit-Reviewer: Adam Langley <a...@golang.org>
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>
Gerrit-Reviewer: Damian Gryski <dgr...@gmail.com>
Gerrit-Reviewer: Filippo Valsorda <fil...@cloudflare.com>
Gerrit-Reviewer: Ian Lance Taylor <ia...@golang.org>
Gerrit-Reviewer: Klaus Post <klau...@gmail.com>
Gerrit-Reviewer: Minux Ma <mi...@golang.org>
Gerrit-Reviewer: Russ Cox <r...@golang.org>
Gerrit-Reviewer: Vlad Krasnov <vl...@cloudflare.com>

Gerrit-HasComments: No

[Gobot Gobot (Gerrit)]

Gobot Gobot has posted comments on this change.

crypto/elliptic,crypto/ecdsa: P256 amd64 assembly

Patch Set 8:

TryBots beginning. Status page: http://farmer.golang.org/try?commit=7674a037

--
https://go-review.googlesource.com/8968
Gerrit-Reviewer: Adam Langley <a...@golang.org>
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>
Gerrit-Reviewer: Damian Gryski <dgr...@gmail.com>
Gerrit-Reviewer: Filippo Valsorda <fil...@cloudflare.com>

Gerrit-Reviewer: Gobot Gobot <go...@golang.org>

[Gobot Gobot (Gerrit)]

Gobot Gobot has posted comments on this change.

crypto/elliptic,crypto/ecdsa: P256 amd64 assembly

Patch Set 8: TryBot-Result+1

TryBots are happy.

[Adam Langley (Gerrit)]

Adam Langley has posted comments on this change.

crypto/elliptic,crypto/ecdsa: P256 amd64 assembly

Patch Set 8: Code-Review+2

[Adam Langley (Gerrit)]

Adam Langley has submitted this change and it was merged.

crypto/elliptic,crypto/ecdsa: P256 amd64 assembly

This is based on the implementation used in OpenSSL, from a
submission by Shay Gueron and myself. Besides using assembly,
this implementation employs several optimizations described in:

S.Gueron and V.Krasnov, "Fast prime field elliptic-curve
cryptography with 256-bit primes"

In addition a new and improved modular inverse modulo N is
implemented here.

The performance measured on a Haswell based Macbook Pro shows 21X
speedup for the sign and 9X for the verify operations.
The operation BaseMult is 30X faster (and the Diffie-Hellman/ECDSA
key generation that use it are sped up as well).

The adaptation to Go with the help of Filippo Valsorda

Updated the submission for faster verify/ecdh, fixed some asm syntax
and API problems and added benchmarks.

Change-Id: I86a33636747d5c92f15e0c8344caa2e7e07e0028

Reviewed-on: https://go-review.googlesource.com/8968
Run-TryBot: Adam Langley <a...@golang.org>
TryBot-Result: Gobot Gobot <go...@golang.org>
Reviewed-by: Adam Langley <a...@golang.org>

---
M src/crypto/ecdsa/ecdsa.go
M src/crypto/ecdsa/ecdsa_test.go
M src/crypto/elliptic/elliptic_test.go
M src/crypto/elliptic/p256.go
A src/crypto/elliptic/p256_amd64.go
A src/crypto/elliptic/p256_asm_amd64.s
6 files changed, 2,930 insertions(+), 5 deletions(-)

Approvals:
Adam Langley: Looks good to me, approved; Run TryBots
Gobot Gobot: TryBots succeeded