4 * Digital signature scheme based on Curve25519 (Ed25519 or EdDSA).
8 * Copyright (c) 2011, 2012, 2014 Ron Garret
9 * Copyright (c) 2014 Mega Limited
10 * under the MIT License.
12 * Authors: Guy K. Kloss, Ron Garret
14 * You should have received a copy of the license along with this program.
17 var core = require('./core');
18 var curve255 = require('./curve255');
19 var utils = require('./utils');
20 var BigInteger = require('jsbn').BigInteger;
21 var crypto = require('crypto');
24 * @exports jodid25519/eddsa
25 * Digital signature scheme based on Curve25519 (Ed25519 or EdDSA).
28 * Digital signature scheme based on Curve25519 (Ed25519 or EdDSA).
31 * This code is adapted from fast-djbec.js, a faster but more complicated
32 * version of the Ed25519 encryption scheme (as compared to djbec.js).
33 * It uses two different representations for big integers: The jsbn
34 * BigInteger class, which can represent arbitrary-length numbers, and a
35 * special fixed-length representation optimised for 256-bit integers.
36 * The reason both are needed is that the Ed25519 algorithm requires some
37 * 512-bit numbers.</p>
41 function _bi255(value) {
42 if (!(this instanceof _bi255)) {
43 return new _bi255(value);
45 if (typeof value === 'undefined') {
48 var c = value.constructor;
49 if ((c === Array || c === Uint16Array || c === Uint32Array) && (value.length === 16)) {
51 } else if ((c === Array) && (value.length === 32)) {
52 this.n = _bytes2bi255(value).n;
53 } else if (c === String) {
54 this.n = utils.hexDecode(value);
55 } else if (c === Number) {
56 this.n = [value & 0xffff,
57 value >> 16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
58 } else if (value instanceof _bi255) {
59 this.n = value.n.slice(0); // Copy constructor
61 throw "Bad argument for bignum: " + value;
66 'toString' : function() {
67 return utils.hexEncode(this.n);
69 'toSource' : function() {
70 return '_' + utils.hexEncode(this.n);
72 'plus' : function(n1) {
73 return _bi255(core.bigintadd(this.n, n1.n));
75 'minus' : function(n1) {
76 return _bi255(core.bigintsub(this.n, n1.n)).modq();
78 'times' : function(n1) {
79 return _bi255(core.mulmodp(this.n, n1.n));
81 'divide' : function(n1) {
82 return this.times(n1.inv());
85 return _bi255(core.sqrmodp(this.n));
87 'cmp' : function(n1) {
88 return core.bigintcmp(this.n, n1.n);
90 'equals' : function(n1) {
91 return this.cmp(n1) === 0;
93 'isOdd' : function() {
94 return (this.n[0] & 1) === 1;
96 'shiftLeft' : function(cnt) {
100 'shiftRight' : function(cnt) {
101 _shiftR(this.n, cnt);
105 return _bi255(core.invmodp(this.n));
107 'pow' : function(e) {
108 return _bi255(_pow(this.n, e.n));
110 'modq' : function() {
113 'bytes' : function() {
114 return _bi255_bytes(this);
118 function _shiftL(n, cnt) {
120 for (var i = 0; i < 16; i++) {
121 var carry = n[i] >> (16 - cnt);
122 n[i] = (n[i] << cnt) & 0xffff | lastcarry;
128 function _shiftR(n, cnt) {
130 for (var i = 15; i >= 0; i--) {
131 var carry = n[i] << (16 - cnt) & 0xffff;
132 n[i] = (n[i] >> cnt) | lastcarry;
138 function _bi255_bytes(n) {
139 n = _bi255(n); // Make a copy because shiftRight is destructive
140 var a = new Array(32);
141 for (var i = 31; i >= 0; i--) {
142 a[i] = n.n[0] & 0xff;
148 function _bytes2bi255(a) {
150 for (var i = 0; i < 32; i++) {
152 n = n.plus(_bi255(a[i]));
157 function _pow(n, e) {
158 var result = core.ONE();
159 for (var i = 0; i < 256; i++) {
160 if (core.getbit(e, i) === 1) {
161 result = core.mulmodp(result, n);
168 var _ZERO = _bi255(0);
169 var _ONE = _bi255(1);
170 var _TWO = _bi255(2);
171 // This is the core prime.
172 var _Q = _bi255([0xffff - 18, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff,
173 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff, 0xffff,
174 0xffff, 0xffff, 0x7fff]);
178 if (n.cmp(_Q) >= 0) {
179 return _modq(n.minus(_Q));
181 if (n.cmp(_ZERO) === -1) {
182 return _modq(n.plus(_Q));
188 // _RECOVERY_EXPONENT = _Q.plus(_bi255(3)).divide(_bi255(8));
189 var _RECOVERY_EXPONENT = _bi255('0ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe');
190 // _D = _Q.minus(_bi255(121665)).divide(_bi255(121666));
191 var _D = _bi255('52036cee2b6ffe738cc740797779e89800700a4d4141d8ab75eb4dca135978a3');
192 // _I = _TWO.pow(_Q.minus(_ONE).divide(_bi255(4)));
193 var _I = _bi255('2b8324804fc1df0b2b4d00993dfbd7a72f431806ad2fe478c4ee1b274a0ea0b0');
194 // _L = _TWO.pow(_bi255(252)).plus(_bi255('14def9dea2f79cd65812631a5cf5d3ed'));
195 var _L = _bi255('1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3ed');
196 var _L_BI = _bi('1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3ed', 16);
199 // ////////////////////////////////////////////////////////////
201 function _isoncurve(p) {
206 var v = _D.times(xsqr).times(ysqr);
207 return ysqr.minus(xsqr).minus(_ONE).minus(v).modq().equals(_ZERO);
210 function _xrecover(y) {
211 var ysquared = y.sqr();
212 var xx = ysquared.minus(_ONE).divide(_ONE.plus(_D.times(ysquared)));
213 var x = xx.pow(_RECOVERY_EXPONENT);
214 if (!(x.times(x).minus(xx).equals(_ZERO))) {
223 function _x_pt_add(pt1, pt2) {
232 var A = y1.minus(x1).times(y2.plus(x2));
233 var B = y1.plus(x1).times(y2.minus(x2));
234 var C = z1.times(_TWO).times(t2);
235 var D = t1.times(_TWO).times(z2);
240 return [E.times(F), G.times(H), F.times(G), E.times(H)];
243 function _xpt_double(pt1) {
247 var A = x1.times(x1);
248 var B = y1.times(y1);
249 var C = _TWO.times(z1).times(z1);
252 var E = J.times(J).minus(A).minus(B);
256 return [E.times(F), G.times(H), F.times(G), E.times(H)];
259 function _xpt_mult(pt, n) {
260 if (n.equals(_ZERO)) {
261 return [_ZERO, _ONE, _ONE, _ZERO];
265 var value = _xpt_double(_xpt_mult(pt, n));
266 return odd ? _x_pt_add(value, pt) : value;
269 function _pt_xform(pt) {
272 return [x, y, _ONE, x.times(y)];
275 function _pt_unxform(pt) {
280 return [x.times(invz), y.times(invz)];
283 function _scalarmult(pt, n) {
284 return _pt_unxform(_xpt_mult(_pt_xform(pt), n));
287 function _bytesgetbit(bytes, n) {
288 return (bytes[bytes.length - (n >>> 3) - 1] >> (n & 7)) & 1;
291 function _xpt_mult_bytes(pt, bytes) {
292 var r = [_ZERO, _ONE, _ONE, _ZERO];
293 for (var i = (bytes.length << 3) - 1; i >= 0; i--) {
295 if (_bytesgetbit(bytes, i) === 1) {
296 r = _x_pt_add(r, pt);
302 function _scalarmultBytes(pt, bytes) {
303 return _pt_unxform(_xpt_mult_bytes(_pt_xform(pt), bytes));
306 var _by = _bi255(4).divide(_bi255(5));
307 var _bx = _xrecover(_by);
308 var _bp = [_bx, _by];
310 function _encodeint(n) {
311 return n.bytes(32).reverse();
313 function _decodeint(b) {
314 return _bi255(b.slice(0).reverse());
317 function _encodepoint(p) {
318 var v = _encodeint(p[1]);
325 function _decodepoint(v) {
327 var signbit = v[31] >> 7;
329 var y = _decodeint(v);
330 var x = _xrecover(y);
331 if ((x.n[0] & 1) !== signbit) {
335 if (!_isoncurve(p)) {
336 throw ('Point is not on curve');
341 // //////////////////////////////////////////////////
344 * Factory function to create a suitable BigInteger.
347 * The value for the big integer.
348 * @param base {integer}
349 * Base of the conversion of elements in ``value``.
351 * A BigInteger object.
353 function _bi(value, base) {
354 if (base !== undefined) {
356 return _bi(utils.string2bytes(value));
358 return new BigInteger(value, base);
359 } else if (typeof value === 'string') {
360 return new BigInteger(value, 10);
361 } else if ((value instanceof Array) || (value instanceof Uint8Array)
362 || Buffer.isBuffer(value)) {
363 return new BigInteger(value);
364 } else if (typeof value === 'number') {
365 return new BigInteger(value.toString(), 10);
367 throw "Can't convert " + value + " to BigInteger";
371 function _bi2bytes(n, cnt) {
372 if (cnt === undefined) {
373 cnt = (n.bitLength() + 7) >>> 3;
375 var bytes = new Array(cnt);
376 for (var i = cnt - 1; i >= 0; i--) {
377 bytes[i] = n[0] & 255; // n.and(0xff);
383 BigInteger.prototype.bytes = function(n) {
384 return _bi2bytes(this, n);
387 // /////////////////////////////////////////////////////////
389 function _bytehash(s) {
390 var sha = crypto.createHash('sha512').update(s).digest();
391 return _bi2bytes(_bi(sha), 64).reverse();
394 function _stringhash(s) {
395 var sha = crypto.createHash('sha512').update(s).digest();
396 return _map(_chr, _bi2bytes(_bi(sha), 64)).join('');
399 function _inthash(s) {
400 // Need a leading 0 to prevent sign extension
401 return _bi([0].concat(_bytehash(s)));
404 function _inthash_lo(s) {
405 return _bi255(_bytehash(s).slice(32, 64));
408 function _inthash_mod_l(s) {
409 return _inthash(s).mod(_L_BI);
412 function _get_a(sk) {
413 var a = _inthash_lo(sk);
420 function _publickey(sk) {
421 return _encodepoint(_scalarmult(_bp, _get_a(sk)));
424 function _map(f, l) {
425 var result = new Array(l.length);
426 for (var i = 0; i < l.length; i++) {
433 return String.fromCharCode(n);
437 return c.charCodeAt(0);
440 function _pt_add(p1, p2) {
441 return _pt_unxform(_x_pt_add(_pt_xform(p1), _pt_xform(p2)));
445 // Exports for the API.
448 * Checks whether a point is on the curve.
451 * @param point {string}
452 * The point to check for in a byte string representation.
454 * true if the point is on the curve, false otherwise.
456 ns.isOnCurve = function(point) {
458 _isoncurve(_decodepoint(utils.string2bytes(point)));
460 if (e === 'Point is not on curve') {
471 * Computes the EdDSA public key.
473 * <p>Note: Seeds should be a byte string, not a unicode string containing
474 * multi-byte characters.</p>
477 * @param keySeed {string}
478 * Private key seed in the form of a byte string.
480 * Public key as byte string computed from the private key seed
483 ns.publicKey = function(keySeed) {
484 return utils.bytes2string(_publickey(keySeed));
489 * Computes an EdDSA signature of a message.
494 * <li>Unicode messages need to be converted to a byte representation
495 * (e. g. UTF-8).</li>
496 * <li>If `publicKey` is given, and it is *not* a point of the curve,
497 * the signature will be faulty, but no error will be thrown.</li>
501 * @param message {string}
502 * Message in the form of a byte string.
503 * @param keySeed {string}
504 * Private key seed in the form of a byte string.
505 * @param publicKey {string}
506 * Public key as byte string (if not present, it will be computed from
507 * the private key seed).
509 * Detached message signature in the form of a byte string (64 bytes).
511 ns.sign = function(message, keySeed, publicKey) {
512 if (publicKey === undefined) {
513 publicKey = _publickey(keySeed);
515 publicKey = utils.string2bytes(publicKey);
517 var a = _bi(_get_a(keySeed).toString(), 16);
518 var hs = _stringhash(keySeed);
519 var r = _bytehash(hs.slice(32, 64) + message);
520 var rp = _scalarmultBytes(_bp, r);
521 var erp = _encodepoint(rp);
522 r = _bi(r).mod(_bi(1, 10).shiftLeft(512));
523 var s = _map(_chr, erp).join('') + _map(_chr, publicKey).join('') + message;
524 s = _inthash_mod_l(s).multiply(a).add(r).mod(_L_BI);
525 return utils.bytes2string(erp.concat(_encodeint(s)));
530 * Verifies an EdDSA signature of a message with the public key.
532 * <p>Note: Unicode messages need to be converted to a byte representation
536 * @param signature {string}
537 * Message signature in the form of a byte string. Can be detached
538 * (64 bytes), or attached to be sliced off.
539 * @param message {string}
540 * Message in the form of a byte string.
541 * @param publicKey {string}
542 * Public key as byte string (if not present, it will be computed from
543 * the private key seed).
545 * true, if the signature verifies.
547 ns.verify = function(signature, message, publicKey) {
548 signature = utils.string2bytes(signature.slice(0, 64));
549 publicKey = utils.string2bytes(publicKey);
550 var rpe = signature.slice(0, 32);
551 var rp = _decodepoint(rpe);
552 var a = _decodepoint(publicKey);
553 var s = _decodeint(signature.slice(32, 64));
554 var h = _inthash(utils.bytes2string(rpe.concat(publicKey)) + message);
555 var v1 = _scalarmult(_bp, s);
556 var value = _scalarmultBytes(a, _bi2bytes(h));
557 var v2 = _pt_add(rp, value);
558 return v1[0].equals(v2[0]) && v1[1].equals(v2[1]);
563 * Generates a new random private key seed of 32 bytes length (256 bit).
567 * Byte string containing a new random private key seed.
569 ns.generateKeySeed = function() {
570 return core.generateKey(false);