1 | var assert = require('assert')
|
2 | var BigInteger = require('bigi')
|
3 |
|
4 | var THREE = BigInteger.valueOf(3)
|
5 |
|
6 | function Point(curve, x, y, z) {
|
7 | assert.notStrictEqual(z, undefined, 'Missing Z coordinate')
|
8 |
|
9 | this.curve = curve
|
10 | this.x = x
|
11 | this.y = y
|
12 | this.z = z
|
13 | this._zInv = null
|
14 |
|
15 | this.compressed = true
|
16 | }
|
17 |
|
18 | Object.defineProperty(Point.prototype, 'zInv', {
|
19 | get: function() {
|
20 | if (this._zInv === null) {
|
21 | this._zInv = this.z.modInverse(this.curve.p)
|
22 | }
|
23 |
|
24 | return this._zInv
|
25 | }
|
26 | })
|
27 |
|
28 | Object.defineProperty(Point.prototype, 'affineX', {
|
29 | get: function() {
|
30 | return this.x.multiply(this.zInv).mod(this.curve.p)
|
31 | }
|
32 | })
|
33 |
|
34 | Object.defineProperty(Point.prototype, 'affineY', {
|
35 | get: function() {
|
36 | return this.y.multiply(this.zInv).mod(this.curve.p)
|
37 | }
|
38 | })
|
39 |
|
40 | Point.fromAffine = function(curve, x, y) {
|
41 | return new Point(curve, x, y, BigInteger.ONE)
|
42 | }
|
43 |
|
44 | Point.prototype.equals = function(other) {
|
45 | if (other === this) return true
|
46 | if (this.curve.isInfinity(this)) return this.curve.isInfinity(other)
|
47 | if (this.curve.isInfinity(other)) return this.curve.isInfinity(this)
|
48 |
|
49 |
|
50 | var u = other.y.multiply(this.z).subtract(this.y.multiply(other.z)).mod(this.curve.p)
|
51 |
|
52 | if (u.signum() !== 0) return false
|
53 |
|
54 |
|
55 | var v = other.x.multiply(this.z).subtract(this.x.multiply(other.z)).mod(this.curve.p)
|
56 |
|
57 | return v.signum() === 0
|
58 | }
|
59 |
|
60 | Point.prototype.negate = function() {
|
61 | var y = this.curve.p.subtract(this.y)
|
62 |
|
63 | return new Point(this.curve, this.x, y, this.z)
|
64 | }
|
65 |
|
66 | Point.prototype.add = function(b) {
|
67 | if (this.curve.isInfinity(this)) return b
|
68 | if (this.curve.isInfinity(b)) return this
|
69 |
|
70 | var x1 = this.x
|
71 | var y1 = this.y
|
72 | var x2 = b.x
|
73 | var y2 = b.y
|
74 |
|
75 |
|
76 | var u = y2.multiply(this.z).subtract(y1.multiply(b.z)).mod(this.curve.p)
|
77 |
|
78 | var v = x2.multiply(this.z).subtract(x1.multiply(b.z)).mod(this.curve.p)
|
79 |
|
80 | if (v.signum() === 0) {
|
81 | if (u.signum() === 0) {
|
82 | return this.twice()
|
83 | }
|
84 |
|
85 | return this.curve.infinity
|
86 | }
|
87 |
|
88 | var v2 = v.square()
|
89 | var v3 = v2.multiply(v)
|
90 | var x1v2 = x1.multiply(v2)
|
91 | var zu2 = u.square().multiply(this.z)
|
92 |
|
93 |
|
94 | var x3 = zu2.subtract(x1v2.shiftLeft(1)).multiply(b.z).subtract(v3).multiply(v).mod(this.curve.p)
|
95 |
|
96 | var y3 = x1v2.multiply(THREE).multiply(u).subtract(y1.multiply(v3)).subtract(zu2.multiply(u)).multiply(b.z).add(u.multiply(v3)).mod(this.curve.p)
|
97 |
|
98 | var z3 = v3.multiply(this.z).multiply(b.z).mod(this.curve.p)
|
99 |
|
100 | return new Point(this.curve, x3, y3, z3)
|
101 | }
|
102 |
|
103 | Point.prototype.twice = function() {
|
104 | if (this.curve.isInfinity(this)) return this
|
105 | if (this.y.signum() === 0) return this.curve.infinity
|
106 |
|
107 | var x1 = this.x
|
108 | var y1 = this.y
|
109 |
|
110 | var y1z1 = y1.multiply(this.z)
|
111 | var y1sqz1 = y1z1.multiply(y1).mod(this.curve.p)
|
112 | var a = this.curve.a
|
113 |
|
114 |
|
115 | var w = x1.square().multiply(THREE)
|
116 |
|
117 | if (a.signum() !== 0) {
|
118 | w = w.add(this.z.square().multiply(a))
|
119 | }
|
120 |
|
121 | w = w.mod(this.curve.p)
|
122 |
|
123 | var x3 = w.square().subtract(x1.shiftLeft(3).multiply(y1sqz1)).shiftLeft(1).multiply(y1z1).mod(this.curve.p)
|
124 |
|
125 | var y3 = w.multiply(THREE).multiply(x1).subtract(y1sqz1.shiftLeft(1)).shiftLeft(2).multiply(y1sqz1).subtract(w.pow(3)).mod(this.curve.p)
|
126 |
|
127 | var z3 = y1z1.pow(3).shiftLeft(3).mod(this.curve.p)
|
128 |
|
129 | return new Point(this.curve, x3, y3, z3)
|
130 | }
|
131 |
|
132 |
|
133 |
|
134 | Point.prototype.multiply = function(k) {
|
135 | if (this.curve.isInfinity(this)) return this
|
136 | if (k.signum() === 0) return this.curve.infinity
|
137 |
|
138 | var e = k
|
139 | var h = e.multiply(THREE)
|
140 |
|
141 | var neg = this.negate()
|
142 | var R = this
|
143 |
|
144 | for (var i = h.bitLength() - 2; i > 0; --i) {
|
145 | R = R.twice()
|
146 |
|
147 | var hBit = h.testBit(i)
|
148 | var eBit = e.testBit(i)
|
149 |
|
150 | if (hBit != eBit) {
|
151 | R = R.add(hBit ? this : neg)
|
152 | }
|
153 | }
|
154 |
|
155 | return R
|
156 | }
|
157 |
|
158 |
|
159 | Point.prototype.multiplyTwo = function(j, x, k) {
|
160 | var i
|
161 |
|
162 | if (j.bitLength() > k.bitLength())
|
163 | i = j.bitLength() - 1
|
164 | else
|
165 | i = k.bitLength() - 1
|
166 |
|
167 | var R = this.curve.infinity
|
168 | var both = this.add(x)
|
169 |
|
170 | while (i >= 0) {
|
171 | R = R.twice()
|
172 |
|
173 | var jBit = j.testBit(i)
|
174 | var kBit = k.testBit(i)
|
175 |
|
176 | if (jBit) {
|
177 | if (kBit) {
|
178 | R = R.add(both)
|
179 |
|
180 | } else {
|
181 | R = R.add(this)
|
182 | }
|
183 |
|
184 | } else {
|
185 | if (kBit) {
|
186 | R = R.add(x)
|
187 | }
|
188 | }
|
189 | --i
|
190 | }
|
191 |
|
192 | return R
|
193 | }
|
194 |
|
195 | Point.prototype.getEncoded = function(compressed) {
|
196 | if (compressed == undefined) compressed = this.compressed
|
197 | if (this.curve.isInfinity(this)) return new Buffer('00', 'hex')
|
198 |
|
199 | var x = this.affineX
|
200 | var y = this.affineY
|
201 |
|
202 | var buffer
|
203 |
|
204 |
|
205 | var byteLength = Math.floor((this.curve.p.bitLength() + 7) / 8)
|
206 |
|
207 |
|
208 | if (compressed) {
|
209 | buffer = new Buffer(1 + byteLength)
|
210 | buffer.writeUInt8(y.isEven() ? 0x02 : 0x03, 0)
|
211 |
|
212 |
|
213 | } else {
|
214 | buffer = new Buffer(1 + byteLength + byteLength)
|
215 | buffer.writeUInt8(0x04, 0)
|
216 |
|
217 | y.toBuffer(byteLength).copy(buffer, 1 + byteLength)
|
218 | }
|
219 |
|
220 | x.toBuffer(byteLength).copy(buffer, 1)
|
221 |
|
222 | return buffer
|
223 | }
|
224 |
|
225 | Point.decodeFrom = function(curve, buffer) {
|
226 | var type = buffer.readUInt8(0)
|
227 | var compressed = (type !== 4)
|
228 |
|
229 | var byteLength = Math.floor((curve.p.bitLength() + 7) / 8)
|
230 | var x = BigInteger.fromBuffer(buffer.slice(1, 1 + byteLength))
|
231 |
|
232 | var Q
|
233 | if (compressed) {
|
234 | assert.equal(buffer.length, byteLength + 1, 'Invalid sequence length')
|
235 | assert(type === 0x02 || type === 0x03, 'Invalid sequence tag')
|
236 |
|
237 | var isOdd = (type === 0x03)
|
238 | Q = curve.pointFromX(isOdd, x)
|
239 |
|
240 | } else {
|
241 | assert.equal(buffer.length, 1 + byteLength + byteLength, 'Invalid sequence length')
|
242 |
|
243 | var y = BigInteger.fromBuffer(buffer.slice(1 + byteLength))
|
244 | Q = Point.fromAffine(curve, x, y)
|
245 | }
|
246 |
|
247 | Q.compressed = compressed
|
248 | return Q
|
249 | }
|
250 |
|
251 | Point.prototype.toString = function () {
|
252 | if (this.curve.isInfinity(this)) return '(INFINITY)'
|
253 |
|
254 | return '(' + this.affineX.toString() + ',' + this.affineY.toString() + ')'
|
255 | }
|
256 |
|
257 | module.exports = Point
|