[go] crypto/elliptic: add support for compressed point encoding

[Bryan Ford (Gerrit)]

Bryan Ford uploaded a change:
https://go-review.googlesource.com/1883

crypto/elliptic: add support for compressed point encoding

This change adds support for the ANSI X9.62 standard compressed point
encoding for all the NIST elliptic curves supported by crypto/elliptic.
To support this and other non-default encodings more cleanly,
I added an Encoding interface signature-compatible with
the existing point Marshal/Unmarshal functions, and two implementations -
Uncompressed and Compressed - representing the two standard encodings.
I also enhanced the test suite to exercise all encodings of all curves;
previously it would test marshaling on the p224 curve only.

Since compressed point unmarshaling depends on modular square-root,
which is a pretty common and standard operation for bignum libraries
but was missing from math/big, I added a ModSqrt function
to math/big based on the standard Tonelli-Shanks algorithm.
Since the square-rooot algorithm in turn depends on a Jacobi function,
which is also common and standard in most bignum libraries,
I added that to math/big as well. (Should these new math/big functions
be in a separate git-review change?)

The elliptic package internally allows individual Curve implementations
to provide a curve-specific, optimized square-root function,
in place of the generic Tonelli-Shanks algorithm I added to math/big.
This optimization is purely internal and does not affect the public API.
I implemented a curve-specific square-root function for the P256 curve,
though not (yet) for the other NIST curves in the package.
The square root implementation for P256 happens to be constant-time,
although this should not be a critical property for point unmarshaling
since marshaling/unmarshaling does not generally utilize any secrets.

Change-Id: I463eeefc1b6a274bf5651aeceef6b56d93d7d6bd
---
M src/crypto/elliptic/elliptic.go
M src/crypto/elliptic/elliptic_test.go
M src/crypto/elliptic/p256.go
M src/math/big/int.go
M src/math/big/int_test.go
5 files changed, 338 insertions(+), 21 deletions(-)



diff --git a/src/crypto/elliptic/elliptic.go
b/src/crypto/elliptic/elliptic.go
index ba673f8..2e0da8e 100644
--- a/src/crypto/elliptic/elliptic.go
+++ b/src/crypto/elliptic/elliptic.go
@@ -51,11 +51,10 @@
return curve
}

-func (curve *CurveParams) IsOnCurve(x, y *big.Int) bool {
- // y² = x³ - 3x + b
- y2 := new(big.Int).Mul(y, y)
- y2.Mod(y2, curve.P)
+// Use the curve equation to calculate y² given x
+func (curve *CurveParams) y2(x *big.Int) *big.Int {

+ // y² = x³ - 3x + b
x3 := new(big.Int).Mul(x, x)
x3.Mul(x3, x)

@@ -65,8 +64,15 @@
x3.Sub(x3, threeX)
x3.Add(x3, curve.B)
x3.Mod(x3, curve.P)
+ return x3
+}

- return x3.Cmp(y2) == 0
+func (curve *CurveParams) IsOnCurve(x, y *big.Int) bool {
+ // y² = x³ - 3x + b
+ y2 := new(big.Int).Mul(y, y)
+ y2.Mod(y2, curve.P)
+
+ return curve.y2(x).Cmp(y2) == 0
}

// zForAffine returns a Jacobian Z value for the affine point (x, y). If x
and
@@ -293,7 +299,33 @@
return
}

-// Marshal converts a point into the form specified in section 4.3.6 of
ANSI X9.62.
+// Encoding represents a method for marshaling and unmarshaling curve
points.
+type Encoding interface {
+
+ // Marshal serializes curve point into a binary string.
+ Marshal(curve Curve, x, y *big.Int) []byte
+
+ // Unmarshal deserializes a binary string into a curve point.
+ // On error, x = nil.
+ Unmarshal(curve Curve, data []byte) (x, y *big.Int)
+}
+
+// Uncompressed is a standard Encoding representing the uncompressed
+// point form specified in section 4.3.6 of ANSI X9.62.
+var Uncompressed Encoding = &compressed{}
+
+type uncompressed struct{}
+
+func (uncompressed) Marshal(curve Curve, x, y *big.Int) []byte {
+ return Marshal(curve, x, y)
+}
+
+func (uncompressed) Unmarshal(curve Curve, data []byte) (x, y *big.Int) {
+ return Unmarshal(curve, data)
+}
+
+// Marshal converts a point into the uncompressed form
+// specified in section 4.3.6 of ANSI X9.62.
func Marshal(curve Curve, x, y *big.Int) []byte {
byteLen := (curve.Params().BitSize + 7) >> 3

@@ -308,6 +340,8 @@
}

// Unmarshal converts a point, serialized by Marshal, into an x, y pair.
On error, x = nil.
+// Unmarshal converts a point, serialized by Marshal or MarshalCompressed,
+// into an x, y pair. On error, x = nil.
func Unmarshal(curve Curve, data []byte) (x, y *big.Int) {
byteLen := (curve.Params().BitSize + 7) >> 3
if len(data) != 1+2*byteLen {
@@ -321,6 +355,74 @@
return
}

+// Compressed is a standard Encoding representing the compressed
+// point form specified in section 4.3.6 of ANSI X9.62.
+var Compressed Encoding = &compressed{}
+
+type compressed struct{}
+
+func (compressed) Marshal(curve Curve, x, y *big.Int) []byte {
+ byteLen := (curve.Params().BitSize + 7) >> 3
+
+ ret := make([]byte, 1+byteLen)
+ ret[0] = 2 // compressed point
+
+ xBytes := x.Bytes()
+ copy(ret[1+byteLen-len(xBytes):], xBytes)
+ ret[0] += byte(y.Bit(0))
+ return ret
+}
+
+func (compressed) Unmarshal(curve Curve, data []byte) (x, y *big.Int) {
+ byteLen := (curve.Params().BitSize + 7) >> 3
+ if (data[0] &^ 1) != 2 {
+ return // unrecognized point encoding
+ }
+ if len(data) != 1+byteLen {
+ return
+ }
+
+ // Based on Routine 2.2.4 in NIST Mathematical routines paper
+ params := curve.Params()
+ tx := new(big.Int).SetBytes(data[1 : 1+byteLen])
+ y2 := params.y2(tx)
+ sqrt := defaultSqrt
+ if opt,ok := curve.(optimizedSqrt); ok {
+ sqrt = opt.sqrt // Curve has optimized sqrt func
+ }
+ ty := sqrt(y2, params.P)
+ if ty == nil {
+ return // "y^2" is not a square: invalid point
+ }
+ var y2c big.Int
+ y2c.Mul(ty, ty).Mod(&y2c, params.P)
+ if y2c.Cmp(y2) != 0 {
+ return // sqrt(y2)^2 != y2: invalid point
+ }
+ if ty.Bit(0) != uint(data[0] & 1) {
+ ty.Sub(params.P, ty)
+ }
+
+ x,y = tx,ty // valid point: return it
+ return
+}
+
+func defaultSqrt(x, p *big.Int) *big.Int {
+ var r big.Int
+ if !r.ModSqrt(x, p) {
+ return nil // x is not a square
+ }
+ return &r
+}
+
+// A Curve can optionally implement this internal interface
+// to provide a curve-specific optimized square-root implementation,
+// utilized in compressed point encoding/decoding.
+type optimizedSqrt interface {
+ sqrt(x, p *big.Int) *big.Int
+}
+
+
var initonce sync.Once
var p384 *CurveParams
var p521 *CurveParams
diff --git a/src/crypto/elliptic/elliptic_test.go
b/src/crypto/elliptic/elliptic_test.go
index 4dc27c9..95b2cd2 100644
--- a/src/crypto/elliptic/elliptic_test.go
+++ b/src/crypto/elliptic/elliptic_test.go
@@ -12,6 +12,8 @@
"testing"
)

+var testCurves = []Curve{P224(), P256(), P384(), P521()}
+
func TestOnCurve(t *testing.T) {
p224 := P224()
if !p224.IsOnCurve(p224.Params().Gx, p224.Params().Gy) {
@@ -428,22 +430,27 @@
}
}

+var testEncodings = []Encoding{ Uncompressed, Compressed }
+
func TestMarshal(t *testing.T) {
- p224 := P224()
- _, x, y, err := GenerateKey(p224, rand.Reader)
- if err != nil {
- t.Error(err)
- return
- }
- serialized := Marshal(p224, x, y)
- xx, yy := Unmarshal(p224, serialized)
- if xx == nil {
- t.Error("failed to unmarshal")
- return
- }
- if xx.Cmp(x) != 0 || yy.Cmp(y) != 0 {
- t.Error("unmarshal returned different values")
- return
+ for _,curve := range(testCurves) {
+ for _,enc := range(testEncodings) {
+ _, x, y, err := GenerateKey(curve, rand.Reader)
+ if err != nil {
+ t.Error(err)
+ return
+ }
+ serialized := enc.Marshal(curve, x, y)
+ xx, yy := enc.Unmarshal(curve, serialized)
+ if xx == nil {
+ t.Error("failed to unmarshal")
+ return
+ }
+ if xx.Cmp(x) != 0 || yy.Cmp(y) != 0 {
+ t.Error("unmarshal returned different values")
+ return
+ }
+ }
}
}

diff --git a/src/crypto/elliptic/p256.go b/src/crypto/elliptic/p256.go
index 82be51e..88e6167 100644
--- a/src/crypto/elliptic/p256.go
+++ b/src/crypto/elliptic/p256.go
@@ -77,6 +77,13 @@
return p256ToAffine(&x1, &y1, &z1)
}

+func (p256Curve) sqrt(x, p *big.Int) *big.Int {
+ var px, pr [p256Limbs]uint32
+ p256FromBig(&px, x)
+ p256Sqrt(&pr, &px)
+ return p256ToBig(&pr)
+}
+
// Field elements are represented as nine, unsigned 32-bit words.
//
// The value of an field element is:
@@ -803,6 +810,54 @@
p256ReduceCarry(out, carry)
}

+// p256Sqrt sets out=sqrt(in) if in is a square mod p
+//
+// On entry: in[0,2,...] < 2**30, in[1,3,...] < 2**29 and
+// On exit: out[0,2,...] < 2**30, out[1,3,...] < 2**29.
+// From "Mathematical routines for the NIST prime elliptic curves" (April
2010)
+func p256Sqrt(out, in *[p256Limbs]uint32) {
+ var t1, t2, t3, t4 [p256Limbs]uint32
+
+ p256Square(&t1,in)
+ p256Mul(&t1,&t1,in) // t1 = c^(2^2-1)
+
+ p256Square(&t2,&t1)
+ p256Square(&t2,&t2)
+ p256Mul(&t2,&t2,&t1) // t2 = c^(2^4-1)
+
+ p256Square(&t3,&t2)
+ for i := 1; i < 4; i++ {
+ p256Square(&t3,&t3)
+ }
+ p256Mul(&t3,&t3,&t2) // t3 = c^(2^8-1)
+
+ p256Square(&t4,&t3)
+ for i := 1; i < 8; i++ {
+ p256Square(&t4,&t4)
+ }
+ p256Mul(&t4,&t4,&t3) // t4 = c^(2^16-1)
+
+ p256Square(out,&t4)
+ for i := 1; i < 16; i++ {
+ p256Square(out,out)
+ }
+ p256Mul(out,out,&t4) // r = c^(2^32-1)
+
+ for i := 0; i < 32; i++ {
+ p256Square(out,out)
+ }
+ p256Mul(out,out,in) // r = c^(2^64-2^32+1)
+
+ for i := 0; i < 96; i++ {
+ p256Square(out,out)
+ }
+ p256Mul(out,out,in) // r = c^(2^160-2^128+2^96+1)
+
+ for i := 0; i < 94; i++ {
+ p256Square(out,out)
+ } // r = c^(2^254-2^222+2^190+2^94) = sqrt(c) mod p256
+}
+
// Group operations:
//
// Elements of the elliptic curve group are represented in Jacobian
diff --git a/src/math/big/int.go b/src/math/big/int.go
index d22e39e..5071d41 100644
--- a/src/math/big/int.go
+++ b/src/math/big/int.go
@@ -22,6 +22,7 @@
}

var intOne = &Int{false, natOne}
+var intTwo = &Int{false, natTwo}

// Sign returns:
//
@@ -766,6 +767,110 @@
return z
}

+// Jacobi returns the Jacobi symbol of (x/y), between -1 and 1.
+func Jacobi(x,y *Int) int {
+
+ // We use the formulation described in chapter 2, section 2.4,
+ // "The Yacas Book of Algorithms":
+ // http://yacas.sourceforge.net/Algo.book.pdf
+
+ var a,b,c Int
+ a.Set(x)
+ b.Set(y)
+ j := 1
+ for {
+ if a.Sign() == 0 {
+ return 0
+ }
+ if b.Cmp(intOne) == 0 {
+ return j
+ }
+ a.Mod(&a,&b)
+
+ // Handle factors of 2 in a
+ s := 0
+ for a.Bit(s) == 0 {
+ s++
+ }
+ if s & 1 != 0 {
+ bmod8 := b.Bits()[0] & 7
+ if bmod8 == 3 || bmod8 == 5 {
+ j = -j
+ }
+ }
+ c.Rsh(&a,uint(s)) // a = 2^s*c
+
+ // Swap numerator and denominator
+ if b.Bits()[0] & 3 == 3 && c.Bits()[0] & 3 == 3 {
+ j = -j
+ }
+ a.Set(&b)
+ b.Set(&c)
+ }
+}
+
+// SquareRoot sets z to one of the square roots of a modulo an odd prime p,
+// if a square root exists.
+// Returns true on success, false if input a is not a square modulo p.
+func (z *Int) ModSqrt(a, p *Int) bool {
+
+ if a.Sign() == 0 {
+ z.SetInt64(0) // sqrt(0) = 0
+ return true
+ }
+ if Jacobi(a,p) != 1 {
+ return false // a is not a square mod M
+ }
+
+ // Break p-1 into s*2^e such that s is odd.
+ var s Int
+ var e int
+ s.Sub(p,intOne)
+ for s.Bit(0) == 0 {
+ s.Div(&s,intTwo)
+ e++
+ }
+
+ // Find some non-square n
+ var n Int
+ n.SetInt64(2)
+ for Jacobi(&n,p) != -1 {
+ n.Add(&n,intOne)
+ }
+
+ // Heart of the Tonelli-Shanks algorithm.
+ // Follows the description in
+ // "Square roots from 1; 24, 51, 10 to Dan Shanks" by Ezra Brown.
+ var x,b,g,t Int
+ x.Add(&s,intOne).Div(&x,intTwo).Exp(a,&x,p)
+ b.Exp(a,&s,p)
+ g.Exp(&n,&s,p)
+ r := e
+ for {
+ // Find the least m such that ord_p(b) = 2^m
+ var m int
+ t.Set(&b)
+ for t.Cmp(intOne) != 0 {
+ t.Exp(&t,intTwo,p)
+ m++
+ }
+
+ if m == 0 {
+ z.Set(&x)
+ return true
+ }
+
+ t.SetInt64(0).SetBit(&t,r-m-1,1).Exp(&g,&t,p)
+ // t = g^(2^(r-m-1)) mod p
+ g.Mul(&t,&t).Mod(&g,p) // g = g^(2^(r-m)) mod p
+ x.Mul(&x,&t).Mod(&x,p)
+ b.Mul(&b,&g).Mod(&b,p)
+ r = m
+ }
+}
+
+
+
// Lsh sets z = x << n and returns z.
func (z *Int) Lsh(x *Int, n uint) *Int {
z.abs = z.abs.shl(x.abs, n)
diff --git a/src/math/big/int_test.go b/src/math/big/int_test.go
index 6070cf3..3d9e0cd 100644
--- a/src/math/big/int_test.go
+++ b/src/math/big/int_test.go
@@ -1486,6 +1486,54 @@
}
}

+var modSqrtTests = []struct {
+ element string
+ modulus string
+}{
+
{"239487239847", "3618502788666131106986593281521497120414687020801267626233049500247285301239"},
+
{"17093281290581290823908023482908", "57896044618658097711785492504343953926634992332820282019728792003956564819949L"},
+
{"7917902318412094812390857981620481290623", "9850501549098619803069760025035903451269934817616361666987073351061430442874302652853566563721228910201656997576599"},
+
{"1758927132094812309581209482340981249018234901238509321756017820", "42307582002575910332922579714097346549017899709713998034217522897561970639123926132812109468141778230245837569601494931472367"},
+}
+
+func testModSqrt(t *testing.T, element, modulus, sqrt *Int) bool {
+ var sq, sqrtsq Int
+ (&sq).Mul(element, element)
+ (&sq).Mod(&sq, modulus)
+ sqrt.ModSqrt(&sq, modulus)
+ if sqrt.Cmp(element) == 0 {
+ return true
+ }
+ (&sqrtsq).Mul(sqrt, sqrt)
+ (&sqrtsq).Mod(&sqrtsq, modulus)
+ return (&sq).Cmp(&sqrtsq) == 0
+}
+
+func TestModSqrt(t *testing.T) {
+ var element, modulus, sqrt Int
+ for i, test := range modSqrtTests {
+ (&element).SetString(test.element, 10)
+ (&modulus).SetString(test.modulus, 10)
+ if !testModSqrt(t, &element, &modulus, &sqrt) {
+ t.Errorf("#%d: failed (sqrt(e)=%s)", i, &sqrt)
+ }
+ }
+ // exhaustive test for small values
+ for n := 3; n < 100; n++ {
+ (&modulus).SetInt64(int64(n))
+ if !(&modulus).ProbablyPrime(10) {
+ continue
+ }
+ for x := 1; x < n; x++ {
+ (&element).SetInt64(int64(x))
+ if !testModSqrt(t, &element, &modulus, &sqrt) {
+ t.Errorf("#%d: failed (sqrt(%d,%d)=%s)",
+ &element, &modulus, &sqrt)
+ }
+ }
+ }
+}
+
var encodingTests = []string{
"-539345864568634858364538753846587364875430589374589",
"-678645873",

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

[Minux Ma (Gerrit)]

Minux Ma has posted comments on this change.

crypto/elliptic: add support for compressed point encoding

Patch Set 1:

the math/big change should be sent as another CL.

--
https://go-review.googlesource.com/1883
Gerrit-Reviewer: Minux Ma <mi...@golang.org>
Gerrit-HasComments: No

[Bryan Ford (Gerrit)]

Bryan Ford uploaded a new patch set:

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

crypto/elliptic: add support for compressed point encoding

This change adds support for the ANSI X9.62 standard compressed point
encoding for all the NIST elliptic curves supported by crypto/elliptic.
To support this and other non-default encodings more cleanly,
I added an Encoding interface signature-compatible with
the existing point Marshal/Unmarshal functions, and two implementations -
Uncompressed and Compressed - representing the two standard encodings.
I also enhanced the test suite to exercise all encodings of all curves;
previously it would test marshaling on the p224 curve only.

The elliptic package internally allows individual Curve implementations
to provide a curve-specific, optimized square-root function,
in place of the generic Tonelli-Shanks algorithm I added to math/big.
This optimization is purely internal and does not affect the public API.
I implemented a curve-specific square-root function for the P256 curve,
though not (yet) for the other NIST curves in the package.
The square root implementation for P256 happens to be constant-time,
although this should not be a critical property for point unmarshaling
since marshaling/unmarshaling does not generally utilize any secrets.

This CL depends on the modular square-root function in the math/big package,
proposed in change 1886 (https://go-review.googlesource.com/#/c/1886/).

Change-Id: I463eeefc1b6a274bf5651aeceef6b56d93d7d6bd
---
M src/crypto/elliptic/elliptic.go
M src/crypto/elliptic/elliptic_test.go
M src/crypto/elliptic/p256.go

3 files changed, 184 insertions(+), 21 deletions(-)

[Bryan Ford (Gerrit)]

Bryan Ford has posted comments on this change.

crypto/elliptic: add support for compressed point encoding

Patch Set 2:

No problem, done.

--
https://go-review.googlesource.com/1883
Gerrit-Reviewer: Bryan Ford <bryno...@gmail.com>

[Bryan Ford (Gerrit)]

Bryan Ford has posted comments on this change.

crypto/elliptic: add support for compressed point encoding

Patch Set 2:

Q: is the proposed Encoding interface useful or overkill? The advantages
are that it binds together the marshal/unmarshal methods for a given
encoding, makes it easy to parameterize encodings in other code, and
requires adding only one new symbol per (future) encoding.

But I'm by no means wedded to this approach. The obvious alternative is
simply to add two new plain functions, e.g., Compress() and Decompress(),
corresponding to the existing Marshal() and Unmarshal() functions and with
identical signatures.

[Adam Langley (Gerrit)]

Adam Langley has posted comments on this change.

crypto/elliptic: add support for compressed point encoding

Patch Set 2: Code-Review-1

The math/big change looks useful, thanks. gri appears to have that in hand.

But I don't think that we want to support compressed points in the standard
library. Go doesn't try to support absolutely everything and compressed
points (at least over the generic curves implemented in crypto/elliptic)
are very obscure.

--
https://go-review.googlesource.com/1883
Gerrit-Reviewer: Adam Langley <a...@golang.org>

[Bryan Ford (Gerrit)]

Bryan Ford has posted comments on this change.

crypto/elliptic: add support for compressed point encoding

Patch Set 2:

> The math/big change looks useful, thanks. gri appears to have that
> in hand.
>
> But I don't think that we want to support compressed points in the
> standard library. Go doesn't try to support absolutely everything
> and compressed points (at least over the generic curves implemented
> in crypto/elliptic) are very obscure.

Thanks for the review. I guess my reasons for thinking compressed-point
encoding would be good to support in the standard library (besides the fact
that I need it :) ) would be: (a) they're just as "standard" as
uncompressed encoding at least in that they are defined in the same ANSI
standard; (b) they're obviously a bit more storage-efficient; but probably
most importantly, (c) they're safer to use in new applications or protocols
than uncompressed-point encodings, because an on-curve check basically
comes "for free" with point decompression, whereas applications using
uncompressed points can silently become insecure if the developer forgets
the on-curve check (depending on what it's used for of course). If the Go
library supports only the uncompressed and not the compressed encoding, the
library is basically incentivizing developers to use the less-safe encoding
(or else code up their own compressed point conversion code).

But if you don't agree with these reasons or don't think they are
sufficient, no worries, I'll go ahead with the math/big part but keep the
compressed-point parts in my own crypto library.

[Minux Ma (Gerrit)]

Minux Ma has posted comments on this change.

crypto/elliptic: add support for compressed point encoding

Patch Set 2:

could we add this functionality to x/crypto/elliptic?
i missed this feature at least once.

I also miss GF(2^m) curves (the sect curves), but it seems they're pretty
unpopular these days. Even most ECC libraries in C don't support them.
(BoringSSL go so far as to delete their support.)
Adam, do you accept GF(2^m) curves in x/crypto sub-repo?

[David Leon Gil (Gerrit)]

David Leon Gil has posted comments on this change.

crypto/elliptic: add support for compressed point encoding

Patch Set 2:

I'd second Minux and Bryan on the utility of the compressed point format;
although it isn't typically used in open-standard internet protocols, it is
not uncommon in other applications.

--
https://go-review.googlesource.com/1883
Gerrit-Reviewer: Adam Langley <a...@golang.org>
Gerrit-Reviewer: Bryan Ford <bryno...@gmail.com>

Gerrit-Reviewer: David Leon Gil <cor...@gmail.com>

[Bryan Ford (Gerrit)]

Bryan Ford has posted comments on this change.

crypto/elliptic: add support for compressed point encoding

Patch Set 2:

Should I continue with this CL on compressed-point encoding or abandon it?
Currently I hear three voices at least mildly in favor of incorporating it
and only one opposed. Thanks.

[Bryan Ford (Gerrit)]

Bryan Ford has abandoned this change.

Change subject: crypto/elliptic: add support for compressed point encoding
......................................................................


Abandoned

Never mind, not worth the t ime.

[Russ Cox (Gerrit)]

Russ Cox has posted comments on this change.

crypto/elliptic: add support for compressed point encoding

Patch Set 2:

Adam owns the crypto package tree, and what's here in the standard library
is really just to support TLS. So if compressed points are obscure in the
sense that we don't need them for TLS interop, that's a good reason not to
include them. The rest of useful crypto is expected to be in the
golang.org/x/crypto repo instead. I heard a few people suggest they'd be
interested in that.

If Bryan doesn't have time, maybe Minux or David can pick up the change for
x/crypto?

--
https://go-review.googlesource.com/1883
Gerrit-Reviewer: Adam Langley <a...@golang.org>
Gerrit-Reviewer: Bryan Ford <bryno...@gmail.com>
Gerrit-Reviewer: David Leon Gil <cor...@gmail.com>
Gerrit-Reviewer: Minux Ma <mi...@golang.org>

Gerrit-Reviewer: Russ Cox <r...@golang.org>
Gerrit-HasComments: No

[Bryan Ford]

> On Jan 19, 2015, at 1:55 PM, Russ Cox (Gerrit) <noreply-gerritcoderevie...@google.com> wrote:
> Adam owns the crypto package tree, and what's here in the standard library is really just to support TLS. So if compressed points are obscure in the sense that we don't need them for TLS interop, that's a good reason not to include them. The rest of useful crypto is expected to be in the golang.org/x/crypto repo instead. I heard a few people suggest they'd be interested in that.

I have to say that I for one find “what TLS wants” to be a most truly bizarre basis for defining what crypto functionality belongs in a language’s standard library.

If those crypto packages are really meant for internal use within other standard-library packages, then perhaps this points towards a larger language issue: if the standard library isn’t supposed to include crypto APIs “in general”, perhaps those packages that are only there to support TLS don’t really belong in the public API either? Have you thought about or discussed some kind of “private packages” mechanism for Go, e.g., packages that are only visible and accessible from their immediate parent packages or from a defined scope?

> If Bryan doesn't have time, maybe Minux or David can pick up the change for x/crypto?

I have time to work on a change if it’s wanted; I just don’t have time to spend in endless arguments on exactly how widely useful a given API function is and whether it serves the 90% or 10% use case, etc.

B

[Brad Fitzpatrick]

Please reply on Gerrit. Gerrit doesn't yet have an email gateway, and we're still working on figure out configuration for all this after our recent migration.

These emails should really be bouncing instead.

--
You received this message because you are subscribed to the Google Groups "golang-codereviews" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-coderevi...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Brad Fitzpatrick (Gerrit)]

Brad Fitzpatrick has posted comments on this change.

crypto/elliptic: add support for compressed point encoding

Patch Set 2:

Bryan Ford wrote:

> I have to say that I for one find "what TLS wants" to be a most truly
> bizarre basis for defining what crypto functionality belongs in a
> language's standard library.

> If those crypto packages are really meant for internal use within other
> standard-library packages, then perhaps this points towards a larger
> language issue: if the standard library isn't supposed to include crypto
> APIs "in general", perhaps those packages that are only there to support
> TLS don't really belong in the public API either? Have you thought about
> or discussed some kind of "private packages" mechanism for Go, e.g.,
> packages that are only visible and accessible from their immediate parent
> packages or from a defined scope?

There is an internal mechanism, since Go 1.4:
https://golang.org/wiki/DesignDocuments links to Go 1.4 "Internal"
Packages:
https://docs.google.com/a/golang.org/document/d/1e8kOo3r51b2BWtTs_1uADIA5djfXhPT36s6eHVRIvaU/edit

--
https://go-review.googlesource.com/1883
Gerrit-Reviewer: Adam Langley <a...@golang.org>

Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>

[Russ Cox (Gerrit)]

Russ Cox has posted comments on this change.

crypto/elliptic: add support for compressed point encoding

Patch Set 2:

> Bryan Ford wrote:
>
> > I have to say that I for one find "what TLS wants" to be a most
> truly bizarre basis for defining what crypto functionality belongs
> in a language's standard library.

I agree about "what TLS wants" being a strange bar. We decided we wanted
HTTPS support in the standard library, and that meant pulling in TLS. We
didn't at the time have a way to have internal-only packages. Now we do,
but I still think that having basic crypto we do have in the standard
library is a good thing. If we'd hidden it, code using HTTPS and importing
the same crypto from golang.org/x/crypto would be getting two copies. Also,
the standard library has been able to define some very useful general
interfaces that defined a framework for the rest of the crypto additions,
both in the standard library and in the x/crypto repo. On balance, I might
tweak a function here or there but I don't think I'd end up with too much
of a different split. If "needed for TLS" seems too specific, subsitute "in
widespread use in common protocols" for the bar I personally think we are
using.

I do think that support for compressed points should go into x/crypto if
possible, so that there will be a good implementation for others to use, in
a curated, standard place.

[Bryan Ford (Gerrit)]

Bryan Ford has posted comments on this change.

crypto/elliptic: add support for compressed point encoding

Patch Set 2:

I'm happy to work this code into a CL for x/crypto, if someone can offer
guidance as to exactly where and how. x/crypto doesn't currently have
an "elliptic-curve" package that I can see. Should the compressed-point
functionality be a completely separate package that builds on the
crypto/elliptic in the standard library? It seems like a pretty small
piece of functionality (two functions basically) to justify a completely
separate package in x/crypto - but I can do that if that's what you want.

Another technical difficulty arises as well: my proposed change adds
internal support for square-root implementations optimized for particular
curves, including an optimized square-root for the common p256 curve. This
functionality hooks pretty deeply into the internal implementation of
curve/elliptic. If the compressed-point functionality is to be separated
into a separate package in x/crypto, then it will need to either (a) just
give up the curve-specific sqrt optimization and just always use the
generic big.Int implementation, (b) add some kind of hack to detect which
curve is being used outside of the elliptic/curve package and pick the
appropriate sort implementation based on that, or (c) put the
compressed-point functions in the separate package but keep the
optimized-sort functionality in the standard library and externally expose
at least that one added method.

[Bryan Ford (Gerrit)]

Bryan Ford has posted comments on this change.

crypto/elliptic: add support for compressed point encoding

Patch Set 2:

Alternatively, as an obviously much more major venture, you could consider
whether you'd like to review and eventually adopt portions of my dedis
crypto library, which presents a more powerful and generic abstract
interface to many types of elliptic curves with different available
encodings (https://github.com/DeDiS/crypto/blob/master/abstract/group.go) -
not just the NIST curves but various Edwards curves as well, and not just
compressed and uncompressed encodings, but also for example the
Elligator-style uniformly-random encodings that steganography and
anti-censorship code needs. A much larger task obviously that probably no
one should jump into lightly, but at least the functionality increment
would be much larger and would probably better justify adding complete
additional packages to x/crypto.

[Adam Langley (Gerrit)]

Adam Langley has posted comments on this change.

crypto/elliptic: add support for compressed point encoding

Patch Set 2:

> I'm happy to work this code into a CL for x/crypto, if someone can
> offer guidance as to exactly where and how.

Adding a Sqrt member to the P-256 implementation is reasonable, although I
think the 'p' parameter is implicit and shouldn't be an argument to Sqrt.

Then a package in x/crypto can try to type assert an interface with Sqrt in
order to use the optimised routines. The question is what the name of the
x/crypto package should be and, although I don't think it's very
good, 'ellipticutil' is the best that comes to mind at the moment.

[Adam Langley (Gerrit)]

Adam Langley has posted comments on this change.

crypto/elliptic: add support for compressed point encoding

Patch Set 2:

> "ellutil", perhaps? "ellipticutil" would be longer than any package
> name in the stdlib, at least.

What it does should be roughly obvious from the name and I'm not sure
that's true of "ellutil".

--
https://go-review.googlesource.com/1883
Gerrit-Reviewer: Adam Langley <a...@golang.org>
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>
Gerrit-Reviewer: Bryan Ford <bryno...@gmail.com>

Gerrit-Reviewer: David Gil <dg...@yahoo-inc.com>

[Minux Ma (Gerrit)]

Minux Ma has posted comments on this change.

crypto/elliptic: add support for compressed point encoding

Patch Set 2:

How about ecutil?

elliptic curve util.

And I also suggest x/crypto/elliptic/ecutil as the import path,
in case we will add a full elliptic package to x/crypto.
(I still want to support GF(2^m) curves, although probably no
others want them.)

[Bryan Ford (Gerrit)]

Bryan Ford has posted comments on this change.

crypto/elliptic: add support for compressed point encoding

Patch Set 2:

> How about ecutil?
>

> And I also suggest x/crypto/elliptic/ecutil as the import path,
> in case we will add a full elliptic package to x/crypto.
> (I still want to support GF(2^m) curves, although probably no
> others want them.)

Taking that approach further, if it seems likely that you'll eventually
want an 'elliptic' package in x/crypto, how about just creating
x/crypto/elliptic now, and initially just populate it with mirrors of the
functions and types in crypto/elliptic? (e.g., GenerateKey etc in
x/crypto/elliptic simply calls the same function in crypto/elliptic; Curve
in x/crypto/elliptic is defined as 'type Curve elliptic.Curve' imported
from crypto/elliptic.) And then we could just add the compressed-point
encoding/decoding to that (e.g., 'Compress' and 'Decompress'
or 'CompressedMarshall' and 'CompressedUnmarshall'). Code that wants the
expanded elliptic package would simply need to change the 'import
crypto/elliptic' to 'import x/crypto/elliptic'.

[David Gil (Gerrit)]

David Gil has posted comments on this change.

crypto/elliptic: add support for compressed point encoding

Patch Set 2:

True enough.

(Though is people who {know acronyms under x/crypto} ∩ {not able to infer
ellutil ≝ ellipticutil} != ∅? ;)

[David Gil (Gerrit)]

David Gil has posted comments on this change.

crypto/elliptic: add support for compressed point encoding

Patch Set 2:

"ellutil", perhaps? "ellipticutil" would be longer than any package name in
the stdlib, at least.

[Adam Langley (Gerrit)]

Adam Langley has posted comments on this change.

crypto/elliptic: add support for compressed point encoding

Patch Set 2:

> > How about ecutil?
> >
> > And I also suggest x/crypto/elliptic/ecutil as the import path,
> > in case we will add a full elliptic package to x/crypto.
> > (I still want to support GF(2^m) curves, although probably no
> > others want them.)
>
> Taking that approach further, if it seems likely that you'll
> eventually want an 'elliptic' package in x/crypto, how about just
> creating x/crypto/elliptic now, and initially just populate it with
> mirrors of the functions and types in crypto/elliptic? (e.g.,
> GenerateKey etc in x/crypto/elliptic simply calls the same function
> in crypto/elliptic; Curve in x/crypto/elliptic is defined as 'type
> Curve elliptic.Curve' imported from crypto/elliptic.) And then we
> could just add the compressed-point encoding/decoding to that
> (e.g., 'Compress' and 'Decompress' or 'CompressedMarshall' and
> 'CompressedUnmarshall'). Code that wants the expanded elliptic
> package would simply need to change the 'import crypto/elliptic' to
> 'import x/crypto/elliptic'.

ecutil sounds fine but I don't expect to mirror elliptic in x/crypto. The
elliptic package is a traditional design which makes sense for TLS but, in
the future, I rather feel that things will do the direction of ed25519,
which expose higher-level concepts and take care of all the problems that
can arise from the integration.