← Back to branch summary

~ubuntu-branches/ubuntu/vivid/golang/vivid

« back to all changes in this revision

Viewing changes to src/pkg/crypto/elliptic/elliptic.go

  • Committer: Package Import Robot
  • Author(s): James Page
  • Date: 2013-08-20 14:06:23 UTC
  • mfrom: (14.1.23 saucy-proposed)
  • Revision ID: package-import@ubuntu.com-20130820140623-b414jfxi3m0qkmrq
Tags: 2:1.1.2-2ubuntu1
https://launchpad.net/bugs/1211749
https://launchpad.net/bugs/1202027
* Merge from Debian unstable (LP: #1211749, #1202027). Remaining changes:
  - 016-armhf-elf-header.patch: Use correct ELF header for armhf binaries.
  - d/control,control.cross: Update Breaks/Replaces for Ubuntu
    versions to ensure smooth upgrades, regenerate control file.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/pkg/crypto/elliptic/elliptic.go
31
31
        // Double returns 2*(x,y)
32
32
        Double(x1, y1 *big.Int) (x, y *big.Int)
33
33
        // ScalarMult returns k*(Bx,By) where k is a number in big-endian form.
34
 
        ScalarMult(x1, y1 *big.Int, scalar []byte) (x, y *big.Int)
35
 
        // ScalarBaseMult returns k*G, where G is the base point of the group and k
36
 
        // is an integer in big-endian form.
37
 
        ScalarBaseMult(scalar []byte) (x, y *big.Int)
 
34
        ScalarMult(x1, y1 *big.Int, k []byte) (x, y *big.Int)
 
35
        // ScalarBaseMult returns k*G, where G is the base point of the group
 
36
        // and k is an integer in big-endian form.
 
37
        ScalarBaseMult(k []byte) (x, y *big.Int)
38
38
}
39
39
 
40
40
// CurveParams contains the parameters of an elliptic curve and also provides
69
69
        return x3.Cmp(y2) == 0
70
70
}
71
71
 
 
72
// zForAffine returns a Jacobian Z value for the affine point (x, y). If x and
 
73
// y are zero, it assumes that they represent the point at infinity because (0,
 
74
// 0) is not on the any of the curves handled here.
 
75
func zForAffine(x, y *big.Int) *big.Int {
 
76
        z := new(big.Int)
 
77
        if x.Sign() != 0 || y.Sign() != 0 {
 
78
                z.SetInt64(1)
 
79
        }
 
80
        return z
 
81
}
 
82
 
72
83
// affineFromJacobian reverses the Jacobian transform. See the comment at the
73
 
// top of the file.
 
84
// top of the file. If the point is ∞ it returns 0, 0.
74
85
func (curve *CurveParams) affineFromJacobian(x, y, z *big.Int) (xOut, yOut *big.Int) {
 
86
        if z.Sign() == 0 {
 
87
                return new(big.Int), new(big.Int)
 
88
        }
 
89
 
75
90
        zinv := new(big.Int).ModInverse(z, curve.P)
76
91
        zinvsq := new(big.Int).Mul(zinv, zinv)
77
92
 
84
99
}
85
100
 
86
101
func (curve *CurveParams) Add(x1, y1, x2, y2 *big.Int) (*big.Int, *big.Int) {
87
 
        z := new(big.Int).SetInt64(1)
88
 
        return curve.affineFromJacobian(curve.addJacobian(x1, y1, z, x2, y2, z))
 
102
        z1 := zForAffine(x1, y1)
 
103
        z2 := zForAffine(x2, y2)
 
104
        return curve.affineFromJacobian(curve.addJacobian(x1, y1, z1, x2, y2, z2))
89
105
}
90
106
 
91
107
// addJacobian takes two points in Jacobian coordinates, (x1, y1, z1) and
92
108
// (x2, y2, z2) and returns their sum, also in Jacobian form.
93
109
func (curve *CurveParams) addJacobian(x1, y1, z1, x2, y2, z2 *big.Int) (*big.Int, *big.Int, *big.Int) {
94
110
        // See http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-2007-bl
 
111
        x3, y3, z3 := new(big.Int), new(big.Int), new(big.Int)
 
112
        if z1.Sign() == 0 {
 
113
                x3.Set(x2)
 
114
                y3.Set(y2)
 
115
                z3.Set(z2)
 
116
                return x3, y3, z3
 
117
        }
 
118
        if z2.Sign() == 0 {
 
119
                x3.Set(x1)
 
120
                y3.Set(y1)
 
121
                z3.Set(z1)
 
122
                return x3, y3, z3
 
123
        }
 
124
 
95
125
        z1z1 := new(big.Int).Mul(z1, z1)
96
126
        z1z1.Mod(z1z1, curve.P)
97
127
        z2z2 := new(big.Int).Mul(z2, z2)
102
132
        u2 := new(big.Int).Mul(x2, z1z1)
103
133
        u2.Mod(u2, curve.P)
104
134
        h := new(big.Int).Sub(u2, u1)
 
135
        xEqual := h.Sign() == 0
105
136
        if h.Sign() == -1 {
106
137
                h.Add(h, curve.P)
107
138
        }
119
150
        if r.Sign() == -1 {
120
151
                r.Add(r, curve.P)
121
152
        }
 
153
        yEqual := r.Sign() == 0
 
154
        if xEqual && yEqual {
 
155
                return curve.doubleJacobian(x1, y1, z1)
 
156
        }
122
157
        r.Lsh(r, 1)
123
158
        v := new(big.Int).Mul(u1, i)
124
159
 
125
 
        x3 := new(big.Int).Set(r)
 
160
        x3.Set(r)
126
161
        x3.Mul(x3, x3)
127
162
        x3.Sub(x3, j)
128
163
        x3.Sub(x3, v)
129
164
        x3.Sub(x3, v)
130
165
        x3.Mod(x3, curve.P)
131
166
 
132
 
        y3 := new(big.Int).Set(r)
 
167
        y3.Set(r)
133
168
        v.Sub(v, x3)
134
169
        y3.Mul(y3, v)
135
170
        s1.Mul(s1, j)
137
172
        y3.Sub(y3, s1)
138
173
        y3.Mod(y3, curve.P)
139
174
 
140
 
        z3 := new(big.Int).Add(z1, z2)
 
175
        z3.Add(z1, z2)
141
176
        z3.Mul(z3, z3)
142
177
        z3.Sub(z3, z1z1)
143
 
        if z3.Sign() == -1 {
144
 
                z3.Add(z3, curve.P)
145
 
        }
146
178
        z3.Sub(z3, z2z2)
147
 
        if z3.Sign() == -1 {
148
 
                z3.Add(z3, curve.P)
149
 
        }
150
179
        z3.Mul(z3, h)
151
180
        z3.Mod(z3, curve.P)
152
181
 
154
183
}
155
184
 
156
185
func (curve *CurveParams) Double(x1, y1 *big.Int) (*big.Int, *big.Int) {
157
 
        z1 := new(big.Int).SetInt64(1)
 
186
        z1 := zForAffine(x1, y1)
158
187
        return curve.affineFromJacobian(curve.doubleJacobian(x1, y1, z1))
159
188
}
160
189
 
219
248
}
220
249
 
221
250
func (curve *CurveParams) ScalarMult(Bx, By *big.Int, k []byte) (*big.Int, *big.Int) {
222
 
        // We have a slight problem in that the identity of the group (the
223
 
        // point at infinity) cannot be represented in (x, y) form on a finite
224
 
        // machine. Thus the standard add/double algorithm has to be tweaked
225
 
        // slightly: our initial state is not the identity, but x, and we
226
 
        // ignore the first true bit in |k|.  If we don't find any true bits in
227
 
        // |k|, then we return nil, nil, because we cannot return the identity
228
 
        // element.
229
 
 
230
251
        Bz := new(big.Int).SetInt64(1)
231
 
        x := Bx
232
 
        y := By
233
 
        z := Bz
 
252
        x, y, z := new(big.Int), new(big.Int), new(big.Int)
234
253
 
235
 
        seenFirstTrue := false
236
254
        for _, byte := range k {
237
255
                for bitNum := 0; bitNum < 8; bitNum++ {
238
 
                        if seenFirstTrue {
239
 
                                x, y, z = curve.doubleJacobian(x, y, z)
240
 
                        }
 
256
                        x, y, z = curve.doubleJacobian(x, y, z)
241
257
                        if byte&0x80 == 0x80 {
242
 
                                if !seenFirstTrue {
243
 
                                        seenFirstTrue = true
244
 
                                } else {
245
 
                                        x, y, z = curve.addJacobian(Bx, By, Bz, x, y, z)
246
 
                                }
 
258
                                x, y, z = curve.addJacobian(Bx, By, Bz, x, y, z)
247
259
                        }
248
260
                        byte <<= 1
249
261
                }
250
262
        }
251
263
 
252
 
        if !seenFirstTrue {
253
 
                return nil, nil
254
 
        }
255
 
 
256
264
        return curve.affineFromJacobian(x, y, z)
257
265
}
258
266
 
370
378
        return p384
371
379
}
372
380
 
373
 
// P256 returns a Curve which implements P-521 (see FIPS 186-3, section D.2.5)
 
381
// P521 returns a Curve which implements P-521 (see FIPS 186-3, section D.2.5)
374
382
func P521() Curve {
375
383
        initonce.Do(initAll)
376
384
        return p521