www.aleph1.co.uk Git - yaffs-website/blob - node_modules/jodid25519/lib/eddsa.js

   1 "use strict";
   2 /**
   3  * @fileOverview
   4  * Digital signature scheme based on Curve25519 (Ed25519 or EdDSA).
   5  */
   6
   7 /*
   8  * Copyright (c) 2011, 2012, 2014 Ron Garret
   9  * Copyright (c) 2014 Mega Limited
  10  * under the MIT License.
  11  *
  12  * Authors: Guy K. Kloss, Ron Garret
  13  *
  14  * You should have received a copy of the license along with this program.
  15  */
  16
  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');
  22
  23     /**
  24      * @exports jodid25519/eddsa
  25      * Digital signature scheme based on Curve25519 (Ed25519 or EdDSA).
  26      *
  27      * @description
  28      * Digital signature scheme based on Curve25519 (Ed25519 or EdDSA).
  29      *
  30      * <p>
  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>
  38     */
  39     var ns = {};
  40
  41     function _bi255(value) {
  42         if (!(this instanceof _bi255)) {
  43             return new _bi255(value);
  44         }
  45         if (typeof value === 'undefined') {
  46             return _ZERO;
  47         }
  48         var c = value.constructor;
  49         if ((c === Array || c === Uint16Array || c === Uint32Array) && (value.length === 16)) {
  50             this.n = value;
  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
  60         } else {
  61             throw "Bad argument for bignum: " + value;
  62         }
  63     }
  64
  65    _bi255.prototype = {
  66         'toString' : function() {
  67             return utils.hexEncode(this.n);
  68         },
  69         'toSource' : function() {
  70             return '_' + utils.hexEncode(this.n);
  71         },
  72         'plus' : function(n1) {
  73             return _bi255(core.bigintadd(this.n, n1.n));
  74         },
  75         'minus' : function(n1) {
  76             return _bi255(core.bigintsub(this.n, n1.n)).modq();
  77         },
  78         'times' : function(n1) {
  79             return _bi255(core.mulmodp(this.n, n1.n));
  80         },
  81         'divide' : function(n1) {
  82             return this.times(n1.inv());
  83         },
  84         'sqr' : function() {
  85             return _bi255(core.sqrmodp(this.n));
  86         },
  87         'cmp' : function(n1) {
  88             return core.bigintcmp(this.n, n1.n);
  89         },
  90         'equals' : function(n1) {
  91             return this.cmp(n1) === 0;
  92         },
  93         'isOdd' : function() {
  94             return (this.n[0] & 1) === 1;
  95         },
  96         'shiftLeft' : function(cnt) {
  97             _shiftL(this.n, cnt);
  98             return this;
  99         },
 100         'shiftRight' : function(cnt) {
 101             _shiftR(this.n, cnt);
 102             return this;
 103         },
 104         'inv' : function() {
 105             return _bi255(core.invmodp(this.n));
 106         },
 107         'pow' : function(e) {
 108             return _bi255(_pow(this.n, e.n));
 109         },
 110         'modq' : function() {
 111             return _modq(this);
 112         },
 113         'bytes' : function() {
 114             return _bi255_bytes(this);
 115         }
 116     };
 117
 118     function _shiftL(n, cnt) {
 119         var lastcarry = 0;
 120         for (var i = 0; i < 16; i++) {
 121             var carry = n[i] >> (16 - cnt);
 122             n[i] = (n[i] << cnt) & 0xffff | lastcarry;
 123             lastcarry = carry;
 124         }
 125         return n;
 126     }
 127
 128     function _shiftR(n, cnt) {
 129         var lastcarry = 0;
 130         for (var i = 15; i >= 0; i--) {
 131             var carry = n[i] << (16 - cnt) & 0xffff;
 132             n[i] = (n[i] >> cnt) | lastcarry;
 133             lastcarry = carry;
 134         }
 135         return n;
 136     }
 137
 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;
 143             n.shiftRight(8);
 144         }
 145         return a;
 146     }
 147
 148     function _bytes2bi255(a) {
 149         var n = _ZERO;
 150         for (var i = 0; i < 32; i++) {
 151             n.shiftLeft(8);
 152             n = n.plus(_bi255(a[i]));
 153         }
 154         return n;
 155     }
 156
 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);
 162             }
 163             n = core.sqrmodp(n);
 164         }
 165         return result;
 166     }
 167
 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]);
 175
 176     function _modq(n) {
 177         core.reduce(n.n);
 178         if (n.cmp(_Q) >= 0) {
 179             return _modq(n.minus(_Q));
 180         }
 181         if (n.cmp(_ZERO) === -1) {
 182             return _modq(n.plus(_Q));
 183         } else {
 184             return n;
 185         }
 186     }
 187
 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);
 197
 198
 199     // ////////////////////////////////////////////////////////////
 200
 201     function _isoncurve(p) {
 202         var x = p[0];
 203         var y = p[1];
 204         var xsqr = x.sqr();
 205         var ysqr = y.sqr();
 206         var v = _D.times(xsqr).times(ysqr);
 207         return ysqr.minus(xsqr).minus(_ONE).minus(v).modq().equals(_ZERO);
 208     }
 209
 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))) {
 215             x = x.times(_I);
 216         }
 217         if (x.isOdd()) {
 218             x = _Q.minus(x);
 219         }
 220         return x;
 221     }
 222
 223     function _x_pt_add(pt1, pt2) {
 224         var x1 = pt1[0];
 225         var y1 = pt1[1];
 226         var z1 = pt1[2];
 227         var t1 = pt1[3];
 228         var x2 = pt2[0];
 229         var y2 = pt2[1];
 230         var z2 = pt2[2];
 231         var t2 = pt2[3];
 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);
 236         var E = D.plus(C);
 237         var F = B.minus(A);
 238         var G = B.plus(A);
 239         var H = D.minus(C);
 240         return [E.times(F), G.times(H), F.times(G), E.times(H)];
 241     }
 242
 243     function _xpt_double(pt1) {
 244         var x1 = pt1[0];
 245         var y1 = pt1[1];
 246         var z1 = pt1[2];
 247         var A = x1.times(x1);
 248         var B = y1.times(y1);
 249         var C = _TWO.times(z1).times(z1);
 250         var D = _Q.minus(A);
 251         var J = x1.plus(y1);
 252         var E = J.times(J).minus(A).minus(B);
 253         var G = D.plus(B);
 254         var F = G.minus(C);
 255         var H = D.minus(B);
 256         return [E.times(F), G.times(H), F.times(G), E.times(H)];
 257     }
 258
 259     function _xpt_mult(pt, n) {
 260         if (n.equals(_ZERO)) {
 261             return [_ZERO, _ONE, _ONE, _ZERO];
 262         }
 263         var odd = n.isOdd();
 264         n.shiftRight(1);
 265         var value = _xpt_double(_xpt_mult(pt, n));
 266         return odd ? _x_pt_add(value, pt) : value;
 267     }
 268
 269     function _pt_xform(pt) {
 270         var x = pt[0];
 271         var y = pt[1];
 272         return [x, y, _ONE, x.times(y)];
 273     }
 274
 275     function _pt_unxform(pt) {
 276         var x = pt[0];
 277         var y = pt[1];
 278         var z = pt[2];
 279         var invz = z.inv();
 280         return [x.times(invz), y.times(invz)];
 281     }
 282
 283     function _scalarmult(pt, n) {
 284         return _pt_unxform(_xpt_mult(_pt_xform(pt), n));
 285     }
 286
 287     function _bytesgetbit(bytes, n) {
 288         return (bytes[bytes.length - (n >>> 3) - 1] >> (n & 7)) & 1;
 289     }
 290
 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--) {
 294             r = _xpt_double(r);
 295             if (_bytesgetbit(bytes, i) === 1) {
 296                 r = _x_pt_add(r, pt);
 297             }
 298         }
 299         return r;
 300     }
 301
 302     function _scalarmultBytes(pt, bytes) {
 303         return _pt_unxform(_xpt_mult_bytes(_pt_xform(pt), bytes));
 304     }
 305
 306     var _by = _bi255(4).divide(_bi255(5));
 307     var _bx = _xrecover(_by);
 308     var _bp = [_bx, _by];
 309
 310     function _encodeint(n) {
 311         return n.bytes(32).reverse();
 312     }
 313     function _decodeint(b) {
 314         return _bi255(b.slice(0).reverse());
 315     }
 316
 317     function _encodepoint(p) {
 318         var v = _encodeint(p[1]);
 319         if (p[0].isOdd()) {
 320             v[31] |= 0x80;
 321         }
 322         return v;
 323     }
 324
 325     function _decodepoint(v) {
 326         v = v.slice(0);
 327         var signbit = v[31] >> 7;
 328         v[31] &= 127;
 329         var y = _decodeint(v);
 330         var x = _xrecover(y);
 331         if ((x.n[0] & 1) !== signbit) {
 332             x = _Q.minus(x);
 333         }
 334         var p = [x, y];
 335         if (!_isoncurve(p)) {
 336             throw ('Point is not on curve');
 337         }
 338         return p;
 339     }
 340
 341     // //////////////////////////////////////////////////
 342
 343     /**
 344      * Factory function to create a suitable BigInteger.
 345      *
 346      * @param value
 347      *     The value for the big integer.
 348      * @param base {integer}
 349      *     Base of the conversion of elements in ``value``.
 350      * @returns
 351      *     A BigInteger object.
 352      */
 353     function _bi(value, base) {
 354         if (base !== undefined) {
 355             if (base === 256) {
 356                 return _bi(utils.string2bytes(value));
 357             }
 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);
 366         } else {
 367             throw "Can't convert " + value + " to BigInteger";
 368         }
 369     }
 370
 371     function _bi2bytes(n, cnt) {
 372         if (cnt === undefined) {
 373             cnt = (n.bitLength() + 7) >>> 3;
 374         }
 375         var bytes = new Array(cnt);
 376         for (var i = cnt - 1; i >= 0; i--) {
 377             bytes[i] = n[0] & 255; // n.and(0xff);
 378             n = n.shiftRight(8);
 379         }
 380         return bytes;
 381     }
 382
 383     BigInteger.prototype.bytes = function(n) {
 384         return _bi2bytes(this, n);
 385     };
 386
 387     // /////////////////////////////////////////////////////////
 388
 389     function _bytehash(s) {
 390         var sha = crypto.createHash('sha512').update(s).digest();
 391         return _bi2bytes(_bi(sha), 64).reverse();
 392     }
 393
 394     function _stringhash(s) {
 395         var sha = crypto.createHash('sha512').update(s).digest();
 396         return _map(_chr, _bi2bytes(_bi(sha), 64)).join('');
 397     }
 398
 399     function _inthash(s) {
 400         // Need a leading 0 to prevent sign extension
 401         return _bi([0].concat(_bytehash(s)));
 402     }
 403
 404     function _inthash_lo(s) {
 405         return _bi255(_bytehash(s).slice(32, 64));
 406     }
 407
 408     function _inthash_mod_l(s) {
 409         return _inthash(s).mod(_L_BI);
 410     }
 411
 412     function _get_a(sk) {
 413         var a = _inthash_lo(sk);
 414         a.n[0] &= 0xfff8;
 415         a.n[15] &= 0x3fff;
 416         a.n[15] |= 0x4000;
 417         return a;
 418     }
 419
 420     function _publickey(sk) {
 421         return _encodepoint(_scalarmult(_bp, _get_a(sk)));
 422     }
 423
 424     function _map(f, l) {
 425         var result = new Array(l.length);
 426         for (var i = 0; i < l.length; i++) {
 427             result[i] = f(l[i]);
 428         }
 429         return result;
 430     }
 431
 432     function _chr(n) {
 433         return String.fromCharCode(n);
 434     }
 435
 436     function _ord(c) {
 437         return c.charCodeAt(0);
 438     }
 439
 440     function _pt_add(p1, p2) {
 441         return _pt_unxform(_x_pt_add(_pt_xform(p1), _pt_xform(p2)));
 442     }
 443
 444
 445     // Exports for the API.
 446
 447     /**
 448      * Checks whether a point is on the curve.
 449      *
 450      * @function
 451      * @param point {string}
 452      *     The point to check for in a byte string representation.
 453      * @returns {boolean}
 454      *     true if the point is on the curve, false otherwise.
 455      */
 456     ns.isOnCurve = function(point) {
 457         try {
 458             _isoncurve(_decodepoint(utils.string2bytes(point)));
 459         } catch(e) {
 460             if (e === 'Point is not on curve') {
 461                 return false;
 462             } else {
 463                 throw e;
 464             }
 465         }
 466         return true;
 467     };
 468
 469
 470     /**
 471      * Computes the EdDSA public key.
 472      *
 473      * <p>Note: Seeds should be a byte string, not a unicode string containing
 474      * multi-byte characters.</p>
 475      *
 476      * @function
 477      * @param keySeed {string}
 478      *     Private key seed in the form of a byte string.
 479      * @returns {string}
 480      *     Public key as byte string computed from the private key seed
 481      *     (32 bytes).
 482      */
 483     ns.publicKey = function(keySeed) {
 484         return utils.bytes2string(_publickey(keySeed));
 485     };
 486
 487
 488     /**
 489      * Computes an EdDSA signature of a message.
 490      *
 491      * <p>Notes:</p>
 492      *
 493      * <ul>
 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>
 498      * </ul>
 499      *
 500      * @function
 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).
 508      * @returns {string}
 509      *     Detached message signature in the form of a byte string (64 bytes).
 510      */
 511     ns.sign = function(message, keySeed, publicKey) {
 512         if (publicKey === undefined) {
 513             publicKey = _publickey(keySeed);
 514         } else {
 515             publicKey = utils.string2bytes(publicKey);
 516         }
 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)));
 526     };
 527
 528
 529     /**
 530      * Verifies an EdDSA signature of a message with the public key.
 531      *
 532      * <p>Note: Unicode messages need to be converted to a byte representation
 533      * (e. g. UTF-8).</p>
 534      *
 535      * @function
 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).
 544      * @returns {boolean}
 545      *     true, if the signature verifies.
 546      */
 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]);
 559     };
 560
 561
 562     /**
 563      * Generates a new random private key seed of 32 bytes length (256 bit).
 564      *
 565      * @function
 566      * @returns {string}
 567      *     Byte string containing a new random private key seed.
 568      */
 569     ns.generateKeySeed = function() {
 570         return core.generateKey(false);
 571     };
 572
 573 module.exports = ns;