| 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360 |
1x
1x
1x
1x
1x
150x
150x
150x
150x
150x
1x
2x
1x
1x
1x
1x
1x
19x
1x
18x
1x
17x
1x
1x
1x
1x
1x
1x
1x
3x
3x
1x
4x
4x
4x
1x
11x
1x
9x
1x
8x
8x
8x
1x
7x
6x
7x
7x
20x
20x
20x
20x
20x
20x
20x
10x
10x
20x
20x
20x
20x
20x
20x
20x
20x
6x
20x
20x
7x
1x
2x
2x
1x
1x
1x
1x
5x
5x
5x
1x
1x
1x
1x
1x
2x
2x
1x
39x
39x
39x
39x
39x
1x
5x
1x
1x
1x
10x
10x
10x
10x
10x
10x
10x
10x
1x
10x
1x
9x
9x
9x
1x
8x
8x
8x
1x
1x
7x
7x
1x
| "use strict";
const BN = require("bn.js");
const crypto = require("crypto");
const Scalar = require("./scalar");
const constants = require("../../constants");
module.exports = Point;
/**
* @module group/nist/point
*/
/**
* Represents a Point on the nist curve
*
* The value of the parameters is expected in little endian form if being
* passed as a Uint8Array
* @constructor
*
* @param {module:group/nist~Weierstrass} curve - Weierstrass curve
* @param {(number|Uint8Array|BN.jsObject)} x
* @param {(number|Uint8Array|BN.jsObject)} y
*/
function Point(curve, x, y) {
let _x = x || null;
let _y = y || null;
Iif (x !== undefined && x.constructor === Uint8Array) {
_x = new BN(x, 16, "le");
}
Iif (y !== undefined && y.constructor === Uint8Array) {
_y = new BN(y, 16, "le");
}
// the point reference is stored in an object to make set()
// consistent.
this.ref = {
curve: curve,
point: curve.curve.point(_x, _y)
};
}
/**
* Returns the little endian representation of the y coordinate of
* the Point
*
* @return {string}
*/
Point.prototype.toString = function() {
if (this.ref.point.inf) {
return "(0,0)";
}
return (
"(" +
this.ref.point.x.fromRed().toString(10) +
"," +
this.ref.point.y.fromRed().toString(10) +
")"
);
};
Point.prototype.string = Point.prototype.toString;
Point.prototype.inspect = Point.prototype.toString;
/**
* Tests for equality between two Points derived from the same group
*
* @param {module:group/nist~Point} p2 Point object to compare
* @return {boolean}
*/
Point.prototype.equal = function(p2) {
if (this.ref.point.isInfinity() ^ p2.ref.point.isInfinity()) {
return false;
}
if (this.ref.point.isInfinity() & p2.ref.point.isInfinity()) {
return true;
}
return (
this.ref.point.x.cmp(p2.ref.point.x) === 0 &&
this.ref.point.y.cmp(p2.ref.point.y) === 0
);
};
// Set point to be equal to p2
/**
* set Set the current point to be equal to p2
*
* @param {module:group/nist~Point} p2 Point object
* @return {module:group/nist~Point}
*/
Point.prototype.set = function(p2) {
this.ref = p2.ref;
return this;
};
/**
* Creates a copy of the current point
*
* @return {module:group/nist~Point} new Point object
*/
Point.prototype.clone = function() {
const point = this.ref.point;
return new Point(this.ref.curve, point.x, point.y);
};
/**
* Set to the neutral element for the curve
* Modifies the receiver
*
* @return {module:group/nist~Point}
*/
Point.prototype.null = function() {
this.ref.point = this.ref.curve.curve.point(null, null);
return this;
};
/**
* Set to the standard base point for this curve
* Modifies the receiver
*
* @return {module:group/nist~Point}
*/
Point.prototype.base = function() {
const g = this.ref.curve.curve.g;
this.ref.point = this.ref.curve.curve.point(g.x, g.y);
return this;
};
/**
* Returns the length (in bytes) of the embedded data
*
* @return {number}
*/
Point.prototype.embedLen = function() {
// Reserve the most-significant 8 bits for pseudo-randomness.
// Reserve the least-significant 8 bits for embedded data length.
// (Hopefully it's unlikely we'll need >=2048-bit curves soon.)
return (this.ref.curve.curve.p.bitLength() - 8 - 8) >> 3;
};
/**
* Returns a Point with data embedded in the y coordinate
*
* @param {Uint8Array} data - data to embed with length <= embedLen
* @param {function} [callback] - to generate a random byte array of given length
*
* @throws {TypeError} if data is not Uint8Array
* @throws {Error} if data.length > embedLen
* @return {module:group/nist~Point}
*/
Point.prototype.embed = function(data, callback) {
if (data.constructor !== Uint8Array) {
throw new TypeError("data should be Uint8Array");
}
let l = this.ref.curve._coordLen();
let dl = this.embedLen();
if (data.length > dl) {
throw new Error("data.length > dl");
}
if (dl > data.length) {
dl = data.length;
}
callback = callback || crypto.randomBytes;
while (true) {
const bitLen = this.ref.curve.curve.p.bitLength();
const buffLen = bitLen >> 3;
let buff = callback(buffLen);
let bytes = Uint8Array.from(buff);
let highbits = bitLen & 7;
Iif (highbits != 0) {
bytes[0] &= ~(0xff << highbits);
}
if (dl > 0) {
bytes[l - 1] = dl; // encode length in lower 8 bits
bytes.set(data, l - dl - 1); // copy in data to embed
}
//console.log(bytes);
let x = new BN(bytes, 16, "be");
Iif (x.cmp(this.ref.curve.curve.p) > 0) {
continue;
}
let xRed = x.toRed(this.ref.curve.curve.red);
let aX = xRed.redMul(this.ref.curve.curve.a);
// y^2 = x^3 + ax + b
let y2 = xRed
.redSqr()
.redMul(xRed)
.redAdd(aX)
.redAdd(this.ref.curve.curve.b);
let y = y2.redSqrt();
let b = callback(1);
if ((b[0] & 0x80) !== 0) {
y = this.ref.curve.curve.p.sub(y).toRed(this.ref.curve.curve.red);
}
// check if it is a valid point
let y2t = y.redSqr();
if (y2t.cmp(y2) === 0) {
return new Point(this.ref.curve, xRed, y);
}
}
};
/**
* Extract embedded data from a point
*
* @throws {Error} when length of embedded data > embedLen
* @return {Uint8Array}
*/
Point.prototype.data = function() {
const l = this.ref.curve._coordLen();
let b = Uint8Array.from(this.ref.point.x.fromRed().toArray("be", l));
const dl = b[l - 1];
Iif (dl > this.embedLen()) {
throw new Error("invalid embed data length");
}
return b.slice(l - dl - 1, l - 1);
};
/**
* Returns the sum of two points on the curve
* Modifies the receiver
*
* @param {module:group/nist~Point} p1 Point object, addend
* @param {module:group/nist~Point} p2 Point object, addend
* @return {module:group/nist~Point} p1 + p2
*/
Point.prototype.add = function(p1, p2) {
const point = p1.ref.point;
this.ref.point = this.ref.curve.curve
.point(point.x, point.y)
.add(p2.ref.point);
return this;
};
/**
* Subtract two points
* Modifies the receiver
*
* @param {module:group/nist~Point} p1 Point object
* @param {module:group/nist~Point} p2 Point object
* @return {module:group/nist~Point} p1 - p2
*/
Point.prototype.sub = function(p1, p2) {
const point = p1.ref.point;
this.ref.point = this.ref.curve.curve
.point(point.x, point.y)
.add(p2.ref.point.neg());
return this;
};
/**
* Finds the negative of a point p
* Modifies the receiver
*
* @param {module:group/nist~Point} p Point to negate
* @return {module:group/nist~Point} -p
*/
Point.prototype.neg = function(p) {
this.ref.point = p.ref.point.neg();
return this;
};
/**
* Multiply point p by scalar s.
* If p is not passed then multiplies the base point of the curve with
* scalar s
* Modifies the receiver
*
* @param {module:group/nist~Scalar} s Scalar
* @param {module:group/nist~Point} [p=null] Point
* @return {module:group/nist~Point}
*/
Point.prototype.mul = function(s, p) {
Iif (s.constructor !== Scalar) {
throw new TypeError("s should be a Scalar");
}
p = p || null;
const arr = s.ref.arr.fromRed();
this.ref.point =
p !== null ? p.ref.point.mul(arr) : this.ref.curve.curve.g.mul(arr);
return this;
};
/**
* Selects a random point
*
* @param {function} [callback] - to generate a random byte array of given length
* @return {module:group/nist~Point}
*/
Point.prototype.pick = function(callback) {
return this.embed(new Uint8Array(), callback);
};
Point.prototype.marshalSize = function() {
// uncompressed ANSI X9.62 representation
return this.ref.curve.pointLen();
};
/**
* converts a point into the form specified in section 4.3.6 of ANSI X9.62.
*
* @return {Uint8Array} byte representation
*/
Point.prototype.marshalBinary = function() {
const byteLen = this.ref.curve._coordLen();
let buf = new Uint8Array(this.ref.curve.pointLen());
buf[0] = 4; // uncompressed point
let xBytes = this.ref.point.x.fromRed().toArray("be");
buf.set(xBytes, 1 + byteLen - xBytes.length);
let yBytes = this.ref.point.y.fromRed().toArray("be");
buf.set(yBytes, 1 + 2 * byteLen - yBytes.length);
return buf;
};
/**
* Convert a Uint8Array back to a curve point.
* Accepts only uncompressed point as specified in section 4.3.6 of ANSI X9.62
* @param {Uint8Array} bytes
*
* @throws {TypeError} when bytes is not Uint8Array
* @throws {Error} when bytes does not correspond to a valid point
*/
Point.prototype.unmarshalBinary = function(bytes) {
if (bytes.constructor !== Uint8Array) {
throw new TypeError("bytes should be a Uint8Array");
}
const byteLen = this.ref.curve._coordLen();
Iif (bytes.length != 1 + 2 * byteLen) {
throw new Error();
}
// not an uncompressed point
if (bytes[0] != 4) {
throw new Error("unmarshalBinary only accepts uncompressed point");
}
let x = new BN(bytes.slice(1, 1 + byteLen), 16);
let y = new BN(bytes.slice(1 + byteLen), 16);
if (x.cmp(constants.zeroBN) === 0 && y.cmp(constants.zeroBN) === 0) {
this.ref.point = this.ref.curve.curve.point(null, null);
return this;
}
this.ref.point = this.ref.curve.curve.point(x, y);
if (!this.ref.curve.curve.validate(this.ref.point)) {
throw new Error("point is not on curve");
}
};
|