"Fossies" - the Fresh Open Source Software Archive

Member "Atom/resources/app/apm/node_modules/jodid25519/lib/eddsa.js" (8 Mar 2017, 17062 Bytes) of archive /windows/misc/atom-windows.zip:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) Javascript source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file.

    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;