code review 6402052: bn256: add package

bn256: add package

Package bn256 implements a particular bilinear group at the 128-bit
security level.

[agl1, 2012-07-16 19:08:08]

Hello golang-dev@googlegroups.com (cc: golang-dev@googlegroups.com),

I'd like you to review this change to
https://code.google.com/p/go.crypto

[remyoudompheng, 2012-07-16 19:42:04]

I have some stupid grammar remarks. What is the "Jacobian form"?

http://codereview.appspot.com/6402052/diff/5001/bn256/constants.go
File bn256/constants.go (right):

http://codereview.appspot.com/6402052/diff/5001/bn256/constants.go#newcode25
bn256/constants.go:25: // xiToPMinus1Over3 is ξ^((p-1)/6) where ξ = i+3.
s/Over3/Over6

http://codereview.appspot.com/6402052/diff/5001/bn256/gfp6.go
File bn256/gfp6.go (right):

http://codereview.appspot.com/6402052/diff/5001/bn256/gfp6.go#newcode120
bn256/gfp6.go:120: // Section 4, Katasuba method.
s/Katasuba/Karatsuba

http://codereview.appspot.com/6402052/diff/5001/bn256/optate.go
File bn256/optate.go (right):

http://codereview.appspot.com/6402052/diff/5001/bn256/optate.go#newcode263
bn256/optate.go:263: // For Q2 we are applying the p² Forbenius. The two
conjuctions cancel
Frobenius?
conjugations?

[r2, 2012-07-16 19:45:39]

This is crypto code so cryptic comments are appropriate.

-rob



On Mon, Jul 16, 2012 at 12:42 PM, <remyoudompheng@gmail.com> wrote:

> I have some stupid grammar remarks. What is the "Jacobian form"?
>
>
>
http://codereview.appspot.com/**6402052/diff/5001/bn256/**constants.go<http:/...
> File bn256/constants.go (right):
>
> http://codereview.appspot.com/**6402052/diff/5001/bn256/**
>
constants.go#newcode25<http://codereview.appspot.com/6402052/diff/5001/bn256/constants.go#newcode25>
> bn256/constants.go:25: // xiToPMinus1Over3 is ξ^((p-1)/6) where ξ = i+3.
> s/Over3/Over6
>
>
http://codereview.appspot.com/**6402052/diff/5001/bn256/gfp6.**go<http://code...
> File bn256/gfp6.go (right):
>
> http://codereview.appspot.com/**6402052/diff/5001/bn256/gfp6.**
>
go#newcode120<http://codereview.appspot.com/6402052/diff/5001/bn256/gfp6.go#newcode120>
> bn256/gfp6.go:120: // Section 4, Katasuba method.
> s/Katasuba/Karatsuba
>
>
http://codereview.appspot.com/**6402052/diff/5001/bn256/**optate.go<http://co...
> File bn256/optate.go (right):
>
> http://codereview.appspot.com/**6402052/diff/5001/bn256/**
>
optate.go#newcode263<http://codereview.appspot.com/6402052/diff/5001/bn256/optate.go#newcode263>
> bn256/optate.go:263: // For Q2 we are applying the p² Forbenius. The two
> conjuctions cancel
> Frobenius?
> conjugations?
>
>
http://codereview.appspot.com/**6402052/<http://codereview.appspot.com/6402052/>
>

[agl1, 2012-07-16 19:51:25]

Thanks. I just did a pass adding all the comments and typoed a few it seems :)

Jacobian form is a representation of points in an elliptic curve group. For a
point (x,y) the Jacobian form is (x',y',z) where x = x' * z^2 and y = y' * z^3.
The advantage of holding it in this form is that the group operations are
faster. Generally the faster group operations more than make up for the cost of
converting back to affine form at the end.

http://codereview.appspot.com/6402052/diff/5001/bn256/constants.go
File bn256/constants.go (right):

http://codereview.appspot.com/6402052/diff/5001/bn256/constants.go#newcode25
bn256/constants.go:25: // xiToPMinus1Over3 is ξ^((p-1)/6) where ξ = i+3.
On 2012/07/16 19:42:04, remyoudompheng wrote:
> s/Over3/Over6

Done.

http://codereview.appspot.com/6402052/diff/5001/bn256/gfp6.go
File bn256/gfp6.go (right):

http://codereview.appspot.com/6402052/diff/5001/bn256/gfp6.go#newcode120
bn256/gfp6.go:120: // Section 4, Katasuba method.
On 2012/07/16 19:42:04, remyoudompheng wrote:
> s/Katasuba/Karatsuba

Done.

http://codereview.appspot.com/6402052/diff/5001/bn256/optate.go
File bn256/optate.go (right):

http://codereview.appspot.com/6402052/diff/5001/bn256/optate.go#newcode263
bn256/optate.go:263: // For Q2 we are applying the p² Forbenius. The two
conjuctions cancel
On 2012/07/16 19:42:04, remyoudompheng wrote:
> Frobenius?
> conjugations?

Done.

[r, 2012-07-17 00:06:54]

this is a pretty big blodge of inscrutableness. is there an itch it scratches?

i've only looked quickly at the first file. i'll look at more later.

http://codereview.appspot.com/6402052/diff/2003/bn256/bn256.go
File bn256/bn256.go (right):

http://codereview.appspot.com/6402052/diff/2003/bn256/bn256.go#newcode13
bn256/bn256.go:13: // bn256 specifically implements the Optimal Ate pairing over
a 256-bit
s/b/B/ English sentences start with capital letters. If you don't like that,
please rephrase.

http://codereview.appspot.com/6402052/diff/2003/bn256/bn256.go#newcode29
bn256/bn256.go:29: // G1 is an abstract cyclic group. The zero value is suitable
for using as the
s/using/use/

http://codereview.appspot.com/6402052/diff/2003/bn256/bn256.go#newcode111
bn256/bn256.go:111: func (out *G1) Unmarshal(m []byte) (*G1, bool) {
// doc comment?

http://codereview.appspot.com/6402052/diff/2003/bn256/bn256.go#newcode162
bn256/bn256.go:162: // ScalarBaseMult sets out to g*k where g is the generator
of the group and
the use of 'out' as a receiver name is unidiomatic and renders these comments
hard to parse.

today i set out to do the following: to set out to g*k.

http://codereview.appspot.com/6402052/diff/2003/bn256/bn256.go#newcode211
bn256/bn256.go:211: func (out *G2) Unmarshal(m []byte) (*G2, bool) {
// doc comment

http://codereview.appspot.com/6402052/diff/2003/bn256/bn256.go#newcode248
bn256/bn256.go:248: func (out *GT) ScalarMult(a *GT, k *big.Int) *GT {
ditto about 'out'

[agl1, 2012-07-18 15:00:28]

This is indeed pretty obscure. I'm afraid that I'm not going to make bilinear
groups and field extensions easy to understand in this code, although I've tried
to make them easy to use.

This package is also pretty obscure. It allows one to write lots of neat
cryptosystems (identity based encryption, group signatures, proxy re-signatures
etc), but those aren't in common use. It's certain sub-repository material and
possibly not even that interesting. I can certainly put it in github if you
would prefer.

http://codereview.appspot.com/6402052/diff/2003/bn256/bn256.go
File bn256/bn256.go (right):

http://codereview.appspot.com/6402052/diff/2003/bn256/bn256.go#newcode13
bn256/bn256.go:13: // bn256 specifically implements the Optimal Ate pairing over
a 256-bit
On 2012/07/17 00:06:54, r wrote:
> s/b/B/ English sentences start with capital letters. If you don't like that,
> please rephrase.

Done.

http://codereview.appspot.com/6402052/diff/2003/bn256/bn256.go#newcode29
bn256/bn256.go:29: // G1 is an abstract cyclic group. The zero value is suitable
for using as the
On 2012/07/17 00:06:54, r wrote:
> s/using/use/

Done.

http://codereview.appspot.com/6402052/diff/2003/bn256/bn256.go#newcode111
bn256/bn256.go:111: func (out *G1) Unmarshal(m []byte) (*G1, bool) {
On 2012/07/17 00:06:54, r wrote:
> // doc comment?

Done.

http://codereview.appspot.com/6402052/diff/2003/bn256/bn256.go#newcode162
bn256/bn256.go:162: // ScalarBaseMult sets out to g*k where g is the generator
of the group and
On 2012/07/17 00:06:54, r wrote:
> the use of 'out' as a receiver name is unidiomatic and renders these comments
> hard to parse.
> 
> today i set out to do the following: to set out to g*k.

I've changed all the uses of |out| as a receiver to |e| and updated the comments
accordingly. ('e' for 'element' since they're elements of the group.)

http://codereview.appspot.com/6402052/diff/2003/bn256/bn256.go#newcode211
bn256/bn256.go:211: func (out *G2) Unmarshal(m []byte) (*G2, bool) {
On 2012/07/17 00:06:54, r wrote:
> // doc comment

Done.

http://codereview.appspot.com/6402052/diff/2003/bn256/bn256.go#newcode248
bn256/bn256.go:248: func (out *GT) ScalarMult(a *GT, k *big.Int) *GT {
On 2012/07/17 00:06:54, r wrote:
> ditto about 'out'

Done.

[r, 2012-07-18 15:17:00]

I don't mind it being in the subrepo. That's what the subrepo is for.

The package doc is a little odd - it reads almost like an apology. Can
you rephrase it to a 'just the facts ma'am', put in a more general
citation, and then add a separate comment with more detail along the
lines of (but more expansive than) what you wrote here? So someone
interested enough to read the code can see more about it? That general
approach keeps godoc output clean but gives context for the dedicated
user.

I'll do a proper review later in the week.

-rob

[akumar_mail.nanosouffle.net, 2012-07-18 17:02:08]

On 18 July 2012 08:00,  <agl@golang.org> wrote:
> http://codereview.appspot.com/6402052/diff/2003/bn256/bn256.go#newcode162
> bn256/bn256.go:162: // ScalarBaseMult sets out to g*k where g is the
> generator of the group and
> On 2012/07/17 00:06:54, r wrote:
>>
>> the use of 'out' as a receiver name is unidiomatic and renders these
>
> comments
>>
>> hard to parse.
>
>
>> today i set out to do the following: to set out to g*k.
>
>
> I've changed all the uses of |out| as a receiver to |e| and updated the
> comments accordingly. ('e' for 'element' since they're elements of the
> group.)

`e' is usually the identity element when talking about abstract groups. :-P


ak

[remyoudompheng, 2012-07-21 06:41:54]

A first round of comments or possible suggestions. I didn't look at the elliptic
curve part yet.

http://codereview.appspot.com/6402052/diff/10002/bn256/bn256_test.go
File bn256/bn256_test.go (right):

http://codereview.appspot.com/6402052/diff/10002/bn256/bn256_test.go#newcode160
bn256/bn256_test.go:160: 
I suggest adding a stupid test like:

func TestGenG2(t *testing.T) {
      g := new(G2).ScalarBaseMult(Order)
      if !g.p.IsInfinity() {
            t.Error("twistPoint does have order n in G₂")
      }
}

http://codereview.appspot.com/6402052/diff/10002/bn256/bn256_test.go#newcode196
bn256/bn256_test.go:196: }
Marshal/Unmarshal round trip fails for infinity points:

func TestG2MarshalInfinity(t *testing.T) {
      g := new(G2).ScalarBaseMult(Order)
      if !g.p.IsInfinity() {
            t.Error("not infinity")
      }
      form := g.Marshal()
      t.Logf("%+v", form)
      _, ok := new(G2).Unmarshal(form)
      if !ok {
            t.Fatalf("failed to unmarshal")
      }
}

http://codereview.appspot.com/6402052/diff/10002/bn256/bn256_test.go#newcode197
bn256/bn256_test.go:197: 
the following test fails, why?

func TestG2Identity(t *testing.T) {
      g := new(G2).ScalarBaseMult(new(big.Int).SetInt64(0))
      if !g.p.IsInfinity() {
            t.Error("failure")
      }
}

http://codereview.appspot.com/6402052/diff/10002/bn256/constants.go
File bn256/constants.go (right):

http://codereview.appspot.com/6402052/diff/10002/bn256/constants.go#newcode16
bn256/constants.go:16: // u is the BN parameter that determines the prime
since u is not written explicit in the reference paper, I suggest mentioning
that u = 1868033³

http://codereview.appspot.com/6402052/diff/10002/bn256/constants.go#newcode19
bn256/constants.go:19: // p is a prime over which we form a basic field.
similarly, mention that p = 36u⁴+36u³+24u³+6u+1 ?

http://codereview.appspot.com/6402052/diff/10002/bn256/constants.go#newcode37
bn256/constants.go:37: // xiToPSquaredMinus1Over6 is ξ^((p²-1)/6) where ξ = i+3.
(a cubic root of unity modulo p).

http://codereview.appspot.com/6402052/diff/10002/bn256/curve.go
File bn256/curve.go (right):

http://codereview.appspot.com/6402052/diff/10002/bn256/curve.go#newcode12
bn256/curve.go:12: // Jacobian form and t=z² when valid.
// G₁ is the set of points of this curve on GF(p).

(or a similar sentence)

http://codereview.appspot.com/6402052/diff/10002/bn256/curve.go#newcode55
bn256/curve.go:55: func (c *curvePoint) IsOnCurve() bool {
this function only works for points in affine form.

http://codereview.appspot.com/6402052/diff/10002/bn256/gfp12.go
File bn256/gfp12.go (right):

http://codereview.appspot.com/6402052/diff/10002/bn256/gfp12.go#newcode79
bn256/gfp12.go:79: func (e *gfP12) Frobenius(a *gfP12, pool *bnPool) *gfP12 {
Computes (xω+y)^p = x^p ω·ξ^((p-1)/6) + y^p

http://codereview.appspot.com/6402052/diff/10002/bn256/gfp12.go#newcode86
bn256/gfp12.go:86: func (e *gfP12) FrobeniusP2(a *gfP12, pool *bnPool) *gfP12 {
F(aω+b) = F(a)·ω^p² + F(b) = F(a)·ω·ξ^(p²-1/6) + F(b)
where does the negative come from?

http://codereview.appspot.com/6402052/diff/10002/bn256/gfp2.go
File bn256/gfp2.go (right):

http://codereview.appspot.com/6402052/diff/10002/bn256/gfp2.go#newcode126
bn256/gfp2.go:126: func (e *gfP2) MulElements(a *gfP2, b *big.Int) *gfP2 {
MulElements looks weird to me. MulScalar or MulInt maybe?

http://codereview.appspot.com/6402052/diff/10002/bn256/gfp2.go#newcode173
bn256/gfp2.go:173: func (e *gfP2) Invert(a *gfP2, pool *bnPool) *gfP2 {
mention that you are computing 1/(ai+b) = (-ai+b)/(a²+b²) ?

http://codereview.appspot.com/6402052/diff/10002/bn256/gfp6.go
File bn256/gfp6.go (right):

http://codereview.appspot.com/6402052/diff/10002/bn256/gfp6.go#newcode86
bn256/gfp6.go:86: func (e *gfP6) FrobeniusP2(a *gfP6) *gfP6 {
Computes (xτ²+yτ+z)^(p²) = xτ^(2p²) + yτ^(p²) + z
so y gets multiplied by τ^(p²-1) = ξ^(p²-1/3) = z²
   x gets multiplied by τ^2(p²-1) = z⁴
(where z = xiToPSquaredMinus1Over6)

Oh, wait, it's worth mentioning that z is a cubic root of unity.

http://codereview.appspot.com/6402052/diff/10002/bn256/gfp6.go#newcode184
bn256/gfp6.go:184: func (e *gfP6) MulTau(a *gfP6, pool *bnPool) {
seems obvious but it computes
τ·(aτ²+bτ+c) = bτ²+cτ+aξ

http://codereview.appspot.com/6402052/diff/10002/bn256/twist.go
File bn256/twist.go (right):

http://codereview.appspot.com/6402052/diff/10002/bn256/twist.go#newcode12
bn256/twist.go:12: // kept in Jacobian form and t=z² when valid.
// The group G₂ is the set of n-torsion points of this curve over GF(p²) (where
n = Order)

http://codereview.appspot.com/6402052/diff/10002/bn256/twist.go#newcode22
bn256/twist.go:22: // twistGen is the generator of group G₁.
s/G₁/G₂/

[r, 2012-07-21 16:26:44]

remy's comments seem spot-on. otherwise LGTM

[agl1, 2012-07-21 18:26:00]

http://codereview.appspot.com/6402052/diff/10002/bn256/bn256_test.go
File bn256/bn256_test.go (right):

http://codereview.appspot.com/6402052/diff/10002/bn256/bn256_test.go#newcode160
bn256/bn256_test.go:160: 
On 2012/07/21 06:41:55, remyoudompheng wrote:
> I suggest adding a stupid test like:
> 
> func TestGenG2(t *testing.T) {
>       g := new(G2).ScalarBaseMult(Order)
>       if !g.p.IsInfinity() {
>             t.Error("twistPoint does have order n in G₂")
>       }
> }

Done (for G1, G2 and GT. I don't specify the order of GT, but it's the same.)

http://codereview.appspot.com/6402052/diff/10002/bn256/bn256_test.go#newcode196
bn256/bn256_test.go:196: }
On 2012/07/21 06:41:55, remyoudompheng wrote:
> Marshal/Unmarshal round trip fails for infinity points:

This was deliberate because I wanted to avoid people having to worry about zero
in TDH. (Tor, previously, has been broken by failing to check for zero in a DH
exchange.)

However, having checked a few other pairing based protocols it seems that they
will need zero to marshal/unmarshal correctly so I've done that.

http://codereview.appspot.com/6402052/diff/10002/bn256/bn256_test.go#newcode197
bn256/bn256_test.go:197: 
On 2012/07/21 06:41:55, remyoudompheng wrote:
> the following test fails, why?
> 
> func TestG2Identity(t *testing.T) {
>       g := new(G2).ScalarBaseMult(new(big.Int).SetInt64(0))
>       if !g.p.IsInfinity() {
>             t.Error("failure")
>       }
> }

That's a good catch. The code that the paper is based on is broken in the same
way and it seems it's because their elliptic addition formula aren't complete.
This is doubly unfortunately because I thought that the Bernstein-Lange formulas
*were* complete so I'll have to check crypto/elliptic on that point.

http://codereview.appspot.com/6402052/diff/10002/bn256/constants.go
File bn256/constants.go (right):

http://codereview.appspot.com/6402052/diff/10002/bn256/constants.go#newcode16
bn256/constants.go:16: // u is the BN parameter that determines the prime
On 2012/07/21 06:41:55, remyoudompheng wrote:
> since u is not written explicit in the reference paper, I suggest mentioning
> that u = 1868033³

Done.

http://codereview.appspot.com/6402052/diff/10002/bn256/constants.go#newcode19
bn256/constants.go:19: // p is a prime over which we form a basic field.
On 2012/07/21 06:41:55, remyoudompheng wrote:
> similarly, mention that p = 36u⁴+36u³+24u³+6u+1 ?

Done (and for Order)

http://codereview.appspot.com/6402052/diff/10002/bn256/constants.go#newcode37
bn256/constants.go:37: // xiToPSquaredMinus1Over6 is ξ^((p²-1)/6) where ξ = i+3.
On 2012/07/21 06:41:55, remyoudompheng wrote:
> (a cubic root of unity modulo p).

Done (and above).

http://codereview.appspot.com/6402052/diff/10002/bn256/curve.go
File bn256/curve.go (right):

http://codereview.appspot.com/6402052/diff/10002/bn256/curve.go#newcode12
bn256/curve.go:12: // Jacobian form and t=z² when valid.
On 2012/07/21 06:41:55, remyoudompheng wrote:
> // G₁ is the set of points of this curve on GF(p).
> 
> (or a similar sentence)

Done.

http://codereview.appspot.com/6402052/diff/10002/bn256/curve.go#newcode55
bn256/curve.go:55: func (c *curvePoint) IsOnCurve() bool {
On 2012/07/21 06:41:55, remyoudompheng wrote:
> this function only works for points in affine form.

Yep. Added comment to that effect.

http://codereview.appspot.com/6402052/diff/10002/bn256/gfp12.go
File bn256/gfp12.go (right):

http://codereview.appspot.com/6402052/diff/10002/bn256/gfp12.go#newcode79
bn256/gfp12.go:79: func (e *gfP12) Frobenius(a *gfP12, pool *bnPool) *gfP12 {
On 2012/07/21 06:41:55, remyoudompheng wrote:
> Computes (xω+y)^p = x^p ω·ξ^((p-1)/6) + y^p

Done.

http://codereview.appspot.com/6402052/diff/10002/bn256/gfp12.go#newcode86
bn256/gfp12.go:86: func (e *gfP12) FrobeniusP2(a *gfP12, pool *bnPool) *gfP12 {
On 2012/07/21 06:41:55, remyoudompheng wrote:
> F(aω+b) = F(a)·ω^p² + F(b) = F(a)·ω·ξ^(p²-1/6) + F(b)
> where does the negative come from? 

Sorry, this was a (very minor) speed up that I forgot about and then got tangled
in when cleaning up the code. The old value of xiToPSquaredMinus1Over6 was
actually the forth power of that value and, since it's a cube root of -1, the
negative made it work. It was slightly faster because the forth power is a small
number but it's probably too subtle to be worth it so I dropped it.

http://codereview.appspot.com/6402052/diff/10002/bn256/gfp2.go
File bn256/gfp2.go (right):

http://codereview.appspot.com/6402052/diff/10002/bn256/gfp2.go#newcode126
bn256/gfp2.go:126: func (e *gfP2) MulElements(a *gfP2, b *big.Int) *gfP2 {
On 2012/07/21 06:41:55, remyoudompheng wrote:
> MulElements looks weird to me. MulScalar or MulInt maybe? 

Done.

http://codereview.appspot.com/6402052/diff/10002/bn256/gfp2.go#newcode173
bn256/gfp2.go:173: func (e *gfP2) Invert(a *gfP2, pool *bnPool) *gfP2 {
On 2012/07/21 06:41:55, remyoudompheng wrote:
> mention that you are computing 1/(ai+b) = (-ai+b)/(a²+b²) ?

In other cases I referenced the paper in question, so I've added that here. (I
might be able to derive quadratic field extension inversion, but I'd probably be
stuck on cubic inversion without a reference :) )

http://codereview.appspot.com/6402052/diff/10002/bn256/gfp6.go
File bn256/gfp6.go (right):

http://codereview.appspot.com/6402052/diff/10002/bn256/gfp6.go#newcode86
bn256/gfp6.go:86: func (e *gfP6) FrobeniusP2(a *gfP6) *gfP6 {
On 2012/07/21 06:41:55, remyoudompheng wrote:
> Computes (xτ²+yτ+z)^(p²) = xτ^(2p²) + yτ^(p²) + z
> so y gets multiplied by τ^(p²-1) = ξ^(p²-1/3) = z²
>    x gets multiplied by τ^2(p²-1) = z⁴
> (where z = xiToPSquaredMinus1Over6)

I'm afraid that I've lead you astray with by mistake of misnaming the constant
in GF(p12)'s FrobeniusP2. The factor applied to x should be 
ξ^((2p²-2)/3) and, in fact it was, but I had it named wrong.

> Oh, wait, it's worth mentioning that z is a cubic root of unity.

(z is a cube root of -1, rather than 1.)

http://codereview.appspot.com/6402052/diff/10002/bn256/gfp6.go#newcode184
bn256/gfp6.go:184: func (e *gfP6) MulTau(a *gfP6, pool *bnPool) {
On 2012/07/21 06:41:55, remyoudompheng wrote:
> seems obvious but it computes
> τ·(aτ²+bτ+c) = bτ²+cτ+aξ

Done.

http://codereview.appspot.com/6402052/diff/10002/bn256/twist.go
File bn256/twist.go (right):

http://codereview.appspot.com/6402052/diff/10002/bn256/twist.go#newcode12
bn256/twist.go:12: // kept in Jacobian form and t=z² when valid.
On 2012/07/21 06:41:55, remyoudompheng wrote:
> // The group G₂ is the set of n-torsion points of this curve over GF(p²)
(where
> n = Order)

Done.

http://codereview.appspot.com/6402052/diff/10002/bn256/twist.go#newcode22
bn256/twist.go:22: // twistGen is the generator of group G₁.
On 2012/07/21 06:41:55, remyoudompheng wrote:
> s/G₁/G₂/

Done.

[remyoudompheng, 2012-07-21 19:42:00]

Comments about the elliptic curve group law implementation. I have not reviewed
the Tate pairing computation because I have not yet an idea of what it is
computing.

http://codereview.appspot.com/6402052/diff/10002/bn256/curve.go
File bn256/curve.go (right):

http://codereview.appspot.com/6402052/diff/10002/bn256/curve.go#newcode238
bn256/curve.go:238: c.t.SetInt64(0)
why violate the assumption that t=z² ? actually it doesn't seem to be used (nor
true) outside of the pairing computation anyway

http://codereview.appspot.com/6402052/diff/23001/bn256/curve.go
File bn256/curve.go (right):

http://codereview.appspot.com/6402052/diff/23001/bn256/curve.go#newcode77
bn256/curve.go:77: func (c *curvePoint) Add(a, b *curvePoint, pool *bnPool) {
The Add function is not suitable for a == b and will return zero coordinates if
it happens. This means that the following test (possible using public API
functions) will fail (so the fact should be documented or correctly handled by
redirecting to the Double function):

func TestG1AddSelf(t *testing.T) {
  a := new(G1).ScalarBaseMult(new(big.Int).SetInt64(64))
  b := new(G1).Add(a, a)
  s := b.Marshal()
  _, ok := new(G1).Unmarshal(s)
  if !ok {
    t.Fatal("marshal of a·a failed")
  }               
}

http://codereview.appspot.com/6402052/diff/23001/bn256/curve.go#newcode88
bn256/curve.go:88: z1z1 := pool.Get().Mul(a.z, a.z)
I personnally prefer formulas over assembly-like programs so I try to suggest
comments that make it easier to digest (feel free to choose classical notations
for coordinates over mine): 

// Normalize the points by replacing a = [x1:y1:z1] and b = [x2:y2:z2]
// by [u1:s1:z1·z2] and [u2:s2:z1·z2]
// where u1 = x1·z2², s1 = y1·z2³ and u1 = x2·z1², s2 = y2·z1³

http://codereview.appspot.com/6402052/diff/23001/bn256/curve.go#newcode107
bn256/curve.go:107: h := pool.Get().Sub(u2, u1)
// Compute x = (2h)²(s²-u1-u2)
// where s = (s2-s1)/(u2-u1) is the slope of the line through
// (u1,s1) and (u2,s2). The extra factor 2h = 2(u2-u1) comes from the value of z
below.
// This is also:
// 4(s2-s1)² - 4h²(u1+u2) = 4(s2-s1)² - 4h³ - 4h²(2u1)
//                        = r² - j - 2v
// with the notations below.

http://codereview.appspot.com/6402052/diff/23001/bn256/curve.go#newcode110
bn256/curve.go:110: i := pool.Get().Mul(t, t)
// i = 4h²

http://codereview.appspot.com/6402052/diff/23001/bn256/curve.go#newcode112
bn256/curve.go:112: j := pool.Get().Mul(h, i)
// j = 4h³

http://codereview.appspot.com/6402052/diff/23001/bn256/curve.go#newcode121
bn256/curve.go:121: t4 := pool.Get().Mul(r, r)
// t4 = 4(s2-s1)²

http://codereview.appspot.com/6402052/diff/23001/bn256/curve.go#newcode127
bn256/curve.go:127: t.Sub(v, c.x) // t7
// Set y = -(2h)³(s1 + s*(x/4h²-u1))
// This is also
// y = - 2·s1·j - (s2-s1)(2x - 2i·u1) = r(v-x) - 2·s1·j

http://codereview.appspot.com/6402052/diff/23001/bn256/curve.go#newcode135
bn256/curve.go:135: t.Add(a.z, b.z) // t11
// Set z = 2(u2-u1)·z1·z2 = 2h·z1·z2

Seems like 2z1·z2 is computed as (z1+z2)²-z1²-z2². Weird.
I would have said (it seems to have similar performance):

t.Add(h, h)
t.Mul(t, a.z)
t.Mul(t, b.z)
c.z.Mod(t, p)

http://codereview.appspot.com/6402052/diff/23001/bn256/twist.go
File bn256/twist.go (right):

http://codereview.appspot.com/6402052/diff/23001/bn256/twist.go#newcode100
bn256/twist.go:100: // See
http://hyperelliptic.org/EFD/g1p/auto-code/shortw/jacobian-0/addition/add-200...
it seems the code is identical to the non-twisted curve so no need for extra
comments here.

[remyoudompheng, 2012-07-21 20:23:34]

http://codereview.appspot.com/6402052/diff/23001/bn256/curve.go
File bn256/curve.go (right):

http://codereview.appspot.com/6402052/diff/23001/bn256/curve.go#newcode77
bn256/curve.go:77: func (c *curvePoint) Add(a, b *curvePoint, pool *bnPool) {
Oh if a+b = infinity, h=0 too and the same problem occurs.

http://codereview.appspot.com/6402052/diff/23001/bn256/gfp6.go
File bn256/gfp6.go (right):

http://codereview.appspot.com/6402052/diff/23001/bn256/gfp6.go#newcode243
bn256/gfp6.go:243: // ftp://136.206.11.249/pub/crypto/pairings.pdf
is that URL really persistent?

Here we can give a short explanation of how it works: let j be a cubic root of
unity in GF(p²) so that 1+j+j²=0.
Then (xτ² + yτ + z)(xj²τ² + yjτ + z)(xjτ² + yj²τ + z)
= (xτ² + yτ + z)(Cτ²+Bτ+A)
= (x³ξ²+y³ξ+z³-3ξxyz) = F is an element of the base field (the norm).

On the other hand (xj²τ² + yjτ + z)(xjτ² + yj²τ + z)
= τ²(y²-ξxz) + τ(ξx²-yz) + (z²-ξxy)

So that's why A = (z²-ξxy), B = (ξx²-yz), C = (y²-ξxz)

[remyoudompheng, 2012-07-21 22:58:57]

http://codereview.appspot.com/6402052/diff/23001/bn256/optate.go
File bn256/optate.go (right):

http://codereview.appspot.com/6402052/diff/23001/bn256/optate.go#newcode302
bn256/optate.go:302: // finalExponentiation compuates the steps 13-15 of
algorithm 1 from
I would say that since GT is the group of Order-th roots of unity in GF(p^12):

finalExponentiation computes the (p¹²-1)/Order-th power of an element of GF(p¹²)
to obtain an element of GT (steps 13-15 of...)

[agl1, 2012-07-24 23:18:45]

http://codereview.appspot.com/6402052/diff/10002/bn256/curve.go
File bn256/curve.go (right):

http://codereview.appspot.com/6402052/diff/10002/bn256/curve.go#newcode238
bn256/curve.go:238: c.t.SetInt64(0)
On 2012/07/21 19:42:00, remyoudompheng wrote:
> why violate the assumption that t=z² ? actually it doesn't seem to be used
(nor
> true) outside of the pairing computation anyway

It's used to save computation in the Tate function, but not otherwise. It's not
worth maintaining it outside of that function and |t| is mostly a suitable place
for the Tate function to store this value.

http://codereview.appspot.com/6402052/diff/23001/bn256/curve.go
File bn256/curve.go (right):

http://codereview.appspot.com/6402052/diff/23001/bn256/curve.go#newcode77
bn256/curve.go:77: func (c *curvePoint) Add(a, b *curvePoint, pool *bnPool) {
On 2012/07/21 19:42:00, remyoudompheng wrote:
> The Add function is not suitable for a == b and will return zero coordinates
if
> it happens. This means that the following test (possible using public API
> functions) will fail (so the fact should be documented or correctly handled by
> redirecting to the Double function):
> 
> func TestG1AddSelf(t *testing.T) {
>   a := new(G1).ScalarBaseMult(new(big.Int).SetInt64(64))
>   b := new(G1).Add(a, a)
>   s := b.Marshal()
>   _, ok := new(G1).Unmarshal(s)
>   if !ok {
>     t.Fatal("marshal of a·a failed")
>   }               
> }

I think the a+b=infinity case works fine, but you are correct that a+a doesn't.
That's not usually a problem because we don't hit that case in the
double-and-add loop for multiplication but, by exposing it to the world, we
might.

I think I'll land this code as is, but with a BUG marker for now. I want to
investigate whether it's better to add a test in this code, or to try and find a
complete function for addition on this curve. (I'm not aware if there is a
complete function for a=0 curves, but I believe that there is for a=-3.)

http://codereview.appspot.com/6402052/diff/23001/bn256/curve.go#newcode88
bn256/curve.go:88: z1z1 := pool.Get().Mul(a.z, a.z)
On 2012/07/21 19:42:00, remyoudompheng wrote:
> I personnally prefer formulas over assembly-like programs so I try to suggest
> comments that make it easier to digest (feel free to choose classical
notations
> for coordinates over mine): 
> 
> // Normalize the points by replacing a = [x1:y1:z1] and b = [x2:y2:z2]
> // by [u1:s1:z1·z2] and [u2:s2:z1·z2]
> // where u1 = x1·z2², s1 = y1·z2³ and u1 = x2·z1², s2 = y2·z1³

Happy to import your comments wholesale. I'll add a pointer to twist.go rather
than duplicating them there.

http://codereview.appspot.com/6402052/diff/23001/bn256/gfp6.go
File bn256/gfp6.go (right):

http://codereview.appspot.com/6402052/diff/23001/bn256/gfp6.go#newcode243
bn256/gfp6.go:243: // ftp://136.206.11.249/pub/crypto/pairings.pdf
On 2012/07/21 20:23:34, remyoudompheng wrote:
> is that URL really persistent?

It's the only location that I (or Google) could find.

> 
> Here we can give a short explanation of how it works: let j be a cubic root of
> unity in GF(p²) so that 1+j+j²=0.
> Then (xτ² + yτ + z)(xj²τ² + yjτ + z)(xjτ² + yj²τ + z)
> = (xτ² + yτ + z)(Cτ²+Bτ+A)
> = (x³ξ²+y³ξ+z³-3ξxyz) = F is an element of the base field (the norm).
> 
> On the other hand (xj²τ² + yjτ + z)(xjτ² + yj²τ + z)
> = τ²(y²-ξxz) + τ(ξx²-yz) + (z²-ξxy)
> 
> So that's why A = (z²-ξxy), B = (ξx²-yz), C = (y²-ξxz)

Thanks! Have copied that in.

http://codereview.appspot.com/6402052/diff/23001/bn256/optate.go
File bn256/optate.go (right):

http://codereview.appspot.com/6402052/diff/23001/bn256/optate.go#newcode302
bn256/optate.go:302: // finalExponentiation compuates the steps 13-15 of
algorithm 1 from
On 2012/07/21 22:58:57, remyoudompheng wrote:
> I would say that since GT is the group of Order-th roots of unity in GF(p^12):
> 
> finalExponentiation computes the (p¹²-1)/Order-th power of an element of
GF(p¹²)
> to obtain an element of GT (steps 13-15 of...)

Done.

http://codereview.appspot.com/6402052/diff/23001/bn256/twist.go
File bn256/twist.go (right):

http://codereview.appspot.com/6402052/diff/23001/bn256/twist.go#newcode100
bn256/twist.go:100: // See
http://hyperelliptic.org/EFD/g1p/auto-code/shortw/jacobian-0/addition/add-200...
On 2012/07/21 19:42:00, remyoudompheng wrote:
> it seems the code is identical to the non-twisted curve so no need for extra
> comments here.

Yes. I did originally use interfaces to eliminate this code duplication, but it
made a mess and, in the end, I decided that duplicating the code was the lesser
of the two evils.

[agl1, 2012-07-24 23:20:32]

http://codereview.appspot.com/6402052/diff/23001/bn256/curve.go
File bn256/curve.go (right):

http://codereview.appspot.com/6402052/diff/23001/bn256/curve.go#newcode77
bn256/curve.go:77: func (c *curvePoint) Add(a, b *curvePoint, pool *bnPool) {
On 2012/07/24 23:18:45, agl1 wrote:
> I think I'll land this code as is, but with a BUG marker for now. I want to
> investigate whether it's better to add a test in this code, or to try and find
a
> complete function for addition on this curve. (I'm not aware if there is a
> complete function for a=0 curves, but I believe that there is for a=-3.)

I forgot to hit `send' on the previous set of comments, but I've checked into
complete formulas and they're more trouble than they're worth for these curves.
So I've added a test that, if the x and y values are equal, we call Double. The
formula does work for P+(-P).

[remyoudompheng, 2012-07-25 04:27:22]

LGTM

[agl1, 2012-07-27 16:55:13]

*** Submitted as
http://code.google.com/p/go/source/detail?r=c349712b1885&repo=crypto ***

bn256: add package

Package bn256 implements a particular bilinear group at the 128-bit
security level.

R=golang-dev, remyoudompheng, r, r, akumar
CC=golang-dev
http://codereview.appspot.com/6402052