← Back to branch summary

~nskaggs/+junk/xenial-test

« back to all changes in this revision

Viewing changes to src/golang.org/x/crypto/bn256/twist.go

  • Committer: Nicholas Skaggs
  • Date: 2016-10-24 20:56:05 UTC
  • Revision ID: nicholas.skaggs@canonical.com-20161024205605-z8lta0uvuhtxwzwl
Initi with beta15

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/golang.org/x/crypto/bn256/twist.go
 
1
// Copyright 2012 The Go Authors. All rights reserved.
 
2
// Use of this source code is governed by a BSD-style
 
3
// license that can be found in the LICENSE file.
 
4
 
 
5
package bn256
 
6
 
 
7
import (
 
8
        "math/big"
 
9
)
 
10
 
 
11
// twistPoint implements the elliptic curve y²=x³+3/ξ over GF(p²). Points are
 
12
// kept in Jacobian form and t=z² when valid. The group G₂ is the set of
 
13
// n-torsion points of this curve over GF(p²) (where n = Order)
 
14
type twistPoint struct {
 
15
        x, y, z, t *gfP2
 
16
}
 
17
 
 
18
var twistB = &gfP2{
 
19
        bigFromBase10("6500054969564660373279643874235990574282535810762300357187714502686418407178"),
 
20
        bigFromBase10("45500384786952622612957507119651934019977750675336102500314001518804928850249"),
 
21
}
 
22
 
 
23
// twistGen is the generator of group G₂.
 
24
var twistGen = &twistPoint{
 
25
        &gfP2{
 
26
                bigFromBase10("21167961636542580255011770066570541300993051739349375019639421053990175267184"),
 
27
                bigFromBase10("64746500191241794695844075326670126197795977525365406531717464316923369116492"),
 
28
        },
 
29
        &gfP2{
 
30
                bigFromBase10("20666913350058776956210519119118544732556678129809273996262322366050359951122"),
 
31
                bigFromBase10("17778617556404439934652658462602675281523610326338642107814333856843981424549"),
 
32
        },
 
33
        &gfP2{
 
34
                bigFromBase10("0"),
 
35
                bigFromBase10("1"),
 
36
        },
 
37
        &gfP2{
 
38
                bigFromBase10("0"),
 
39
                bigFromBase10("1"),
 
40
        },
 
41
}
 
42
 
 
43
func newTwistPoint(pool *bnPool) *twistPoint {
 
44
        return &twistPoint{
 
45
                newGFp2(pool),
 
46
                newGFp2(pool),
 
47
                newGFp2(pool),
 
48
                newGFp2(pool),
 
49
        }
 
50
}
 
51
 
 
52
func (c *twistPoint) String() string {
 
53
        return "(" + c.x.String() + ", " + c.y.String() + ", " + c.z.String() + ")"
 
54
}
 
55
 
 
56
func (c *twistPoint) Put(pool *bnPool) {
 
57
        c.x.Put(pool)
 
58
        c.y.Put(pool)
 
59
        c.z.Put(pool)
 
60
        c.t.Put(pool)
 
61
}
 
62
 
 
63
func (c *twistPoint) Set(a *twistPoint) {
 
64
        c.x.Set(a.x)
 
65
        c.y.Set(a.y)
 
66
        c.z.Set(a.z)
 
67
        c.t.Set(a.t)
 
68
}
 
69
 
 
70
// IsOnCurve returns true iff c is on the curve where c must be in affine form.
 
71
func (c *twistPoint) IsOnCurve() bool {
 
72
        pool := new(bnPool)
 
73
        yy := newGFp2(pool).Square(c.y, pool)
 
74
        xxx := newGFp2(pool).Square(c.x, pool)
 
75
        xxx.Mul(xxx, c.x, pool)
 
76
        yy.Sub(yy, xxx)
 
77
        yy.Sub(yy, twistB)
 
78
        yy.Minimal()
 
79
        return yy.x.Sign() == 0 && yy.y.Sign() == 0
 
80
}
 
81
 
 
82
func (c *twistPoint) SetInfinity() {
 
83
        c.z.SetZero()
 
84
}
 
85
 
 
86
func (c *twistPoint) IsInfinity() bool {
 
87
        return c.z.IsZero()
 
88
}
 
89
 
 
90
func (c *twistPoint) Add(a, b *twistPoint, pool *bnPool) {
 
91
        // For additional comments, see the same function in curve.go.
 
92
 
 
93
        if a.IsInfinity() {
 
94
                c.Set(b)
 
95
                return
 
96
        }
 
97
        if b.IsInfinity() {
 
98
                c.Set(a)
 
99
                return
 
100
        }
 
101
 
 
102
        // See http://hyperelliptic.org/EFD/g1p/auto-code/shortw/jacobian-0/addition/add-2007-bl.op3
 
103
        z1z1 := newGFp2(pool).Square(a.z, pool)
 
104
        z2z2 := newGFp2(pool).Square(b.z, pool)
 
105
        u1 := newGFp2(pool).Mul(a.x, z2z2, pool)
 
106
        u2 := newGFp2(pool).Mul(b.x, z1z1, pool)
 
107
 
 
108
        t := newGFp2(pool).Mul(b.z, z2z2, pool)
 
109
        s1 := newGFp2(pool).Mul(a.y, t, pool)
 
110
 
 
111
        t.Mul(a.z, z1z1, pool)
 
112
        s2 := newGFp2(pool).Mul(b.y, t, pool)
 
113
 
 
114
        h := newGFp2(pool).Sub(u2, u1)
 
115
        xEqual := h.IsZero()
 
116
 
 
117
        t.Add(h, h)
 
118
        i := newGFp2(pool).Square(t, pool)
 
119
        j := newGFp2(pool).Mul(h, i, pool)
 
120
 
 
121
        t.Sub(s2, s1)
 
122
        yEqual := t.IsZero()
 
123
        if xEqual && yEqual {
 
124
                c.Double(a, pool)
 
125
                return
 
126
        }
 
127
        r := newGFp2(pool).Add(t, t)
 
128
 
 
129
        v := newGFp2(pool).Mul(u1, i, pool)
 
130
 
 
131
        t4 := newGFp2(pool).Square(r, pool)
 
132
        t.Add(v, v)
 
133
        t6 := newGFp2(pool).Sub(t4, j)
 
134
        c.x.Sub(t6, t)
 
135
 
 
136
        t.Sub(v, c.x)       // t7
 
137
        t4.Mul(s1, j, pool) // t8
 
138
        t6.Add(t4, t4)      // t9
 
139
        t4.Mul(r, t, pool)  // t10
 
140
        c.y.Sub(t4, t6)
 
141
 
 
142
        t.Add(a.z, b.z)    // t11
 
143
        t4.Square(t, pool) // t12
 
144
        t.Sub(t4, z1z1)    // t13
 
145
        t4.Sub(t, z2z2)    // t14
 
146
        c.z.Mul(t4, h, pool)
 
147
 
 
148
        z1z1.Put(pool)
 
149
        z2z2.Put(pool)
 
150
        u1.Put(pool)
 
151
        u2.Put(pool)
 
152
        t.Put(pool)
 
153
        s1.Put(pool)
 
154
        s2.Put(pool)
 
155
        h.Put(pool)
 
156
        i.Put(pool)
 
157
        j.Put(pool)
 
158
        r.Put(pool)
 
159
        v.Put(pool)
 
160
        t4.Put(pool)
 
161
        t6.Put(pool)
 
162
}
 
163
 
 
164
func (c *twistPoint) Double(a *twistPoint, pool *bnPool) {
 
165
        // See http://hyperelliptic.org/EFD/g1p/auto-code/shortw/jacobian-0/doubling/dbl-2009-l.op3
 
166
        A := newGFp2(pool).Square(a.x, pool)
 
167
        B := newGFp2(pool).Square(a.y, pool)
 
168
        C := newGFp2(pool).Square(B, pool)
 
169
 
 
170
        t := newGFp2(pool).Add(a.x, B)
 
171
        t2 := newGFp2(pool).Square(t, pool)
 
172
        t.Sub(t2, A)
 
173
        t2.Sub(t, C)
 
174
        d := newGFp2(pool).Add(t2, t2)
 
175
        t.Add(A, A)
 
176
        e := newGFp2(pool).Add(t, A)
 
177
        f := newGFp2(pool).Square(e, pool)
 
178
 
 
179
        t.Add(d, d)
 
180
        c.x.Sub(f, t)
 
181
 
 
182
        t.Add(C, C)
 
183
        t2.Add(t, t)
 
184
        t.Add(t2, t2)
 
185
        c.y.Sub(d, c.x)
 
186
        t2.Mul(e, c.y, pool)
 
187
        c.y.Sub(t2, t)
 
188
 
 
189
        t.Mul(a.y, a.z, pool)
 
190
        c.z.Add(t, t)
 
191
 
 
192
        A.Put(pool)
 
193
        B.Put(pool)
 
194
        C.Put(pool)
 
195
        t.Put(pool)
 
196
        t2.Put(pool)
 
197
        d.Put(pool)
 
198
        e.Put(pool)
 
199
        f.Put(pool)
 
200
}
 
201
 
 
202
func (c *twistPoint) Mul(a *twistPoint, scalar *big.Int, pool *bnPool) *twistPoint {
 
203
        sum := newTwistPoint(pool)
 
204
        sum.SetInfinity()
 
205
        t := newTwistPoint(pool)
 
206
 
 
207
        for i := scalar.BitLen(); i >= 0; i-- {
 
208
                t.Double(sum, pool)
 
209
                if scalar.Bit(i) != 0 {
 
210
                        sum.Add(t, a, pool)
 
211
                } else {
 
212
                        sum.Set(t)
 
213
                }
 
214
        }
 
215
 
 
216
        c.Set(sum)
 
217
        sum.Put(pool)
 
218
        t.Put(pool)
 
219
        return c
 
220
}
 
221
 
 
222
func (c *twistPoint) MakeAffine(pool *bnPool) *twistPoint {
 
223
        if c.z.IsOne() {
 
224
                return c
 
225
        }
 
226
 
 
227
        zInv := newGFp2(pool).Invert(c.z, pool)
 
228
        t := newGFp2(pool).Mul(c.y, zInv, pool)
 
229
        zInv2 := newGFp2(pool).Square(zInv, pool)
 
230
        c.y.Mul(t, zInv2, pool)
 
231
        t.Mul(c.x, zInv2, pool)
 
232
        c.x.Set(t)
 
233
        c.z.SetOne()
 
234
        c.t.SetOne()
 
235
 
 
236
        zInv.Put(pool)
 
237
        t.Put(pool)
 
238
        zInv2.Put(pool)
 
239
 
 
240
        return c
 
241
}
 
242
 
 
243
func (c *twistPoint) Negative(a *twistPoint, pool *bnPool) {
 
244
        c.x.Set(a.x)
 
245
        c.y.SetZero()
 
246
        c.y.Sub(c.y, a.y)
 
247
        c.z.Set(a.z)
 
248
        c.t.SetZero()
 
249
}