index.js 6.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243
  1. 'use strict';
  2. var BN = require('bn.js');
  3. var HmacDRBG = require('hmac-drbg');
  4. var utils = require('../utils');
  5. var curves = require('../curves');
  6. var rand = require('brorand');
  7. var assert = utils.assert;
  8. var KeyPair = require('./key');
  9. var Signature = require('./signature');
  10. function EC(options) {
  11. if (!(this instanceof EC))
  12. return new EC(options);
  13. // Shortcut `elliptic.ec(curve-name)`
  14. if (typeof options === 'string') {
  15. assert(Object.prototype.hasOwnProperty.call(curves, options),
  16. 'Unknown curve ' + options);
  17. options = curves[options];
  18. }
  19. // Shortcut for `elliptic.ec(elliptic.curves.curveName)`
  20. if (options instanceof curves.PresetCurve)
  21. options = { curve: options };
  22. this.curve = options.curve.curve;
  23. this.n = this.curve.n;
  24. this.nh = this.n.ushrn(1);
  25. this.g = this.curve.g;
  26. // Point on curve
  27. this.g = options.curve.g;
  28. this.g.precompute(options.curve.n.bitLength() + 1);
  29. // Hash for function for DRBG
  30. this.hash = options.hash || options.curve.hash;
  31. }
  32. module.exports = EC;
  33. EC.prototype.keyPair = function keyPair(options) {
  34. return new KeyPair(this, options);
  35. };
  36. EC.prototype.keyFromPrivate = function keyFromPrivate(priv, enc) {
  37. return KeyPair.fromPrivate(this, priv, enc);
  38. };
  39. EC.prototype.keyFromPublic = function keyFromPublic(pub, enc) {
  40. return KeyPair.fromPublic(this, pub, enc);
  41. };
  42. EC.prototype.genKeyPair = function genKeyPair(options) {
  43. if (!options)
  44. options = {};
  45. // Instantiate Hmac_DRBG
  46. var drbg = new HmacDRBG({
  47. hash: this.hash,
  48. pers: options.pers,
  49. persEnc: options.persEnc || 'utf8',
  50. entropy: options.entropy || rand(this.hash.hmacStrength),
  51. entropyEnc: options.entropy && options.entropyEnc || 'utf8',
  52. nonce: this.n.toArray(),
  53. });
  54. var bytes = this.n.byteLength();
  55. var ns2 = this.n.sub(new BN(2));
  56. for (;;) {
  57. var priv = new BN(drbg.generate(bytes));
  58. if (priv.cmp(ns2) > 0)
  59. continue;
  60. priv.iaddn(1);
  61. return this.keyFromPrivate(priv);
  62. }
  63. };
  64. EC.prototype._truncateToN = function _truncateToN(msg, truncOnly) {
  65. var delta = msg.byteLength() * 8 - this.n.bitLength();
  66. if (delta > 0)
  67. msg = msg.ushrn(delta);
  68. if (!truncOnly && msg.cmp(this.n) >= 0)
  69. return msg.sub(this.n);
  70. else
  71. return msg;
  72. };
  73. EC.prototype.sign = function sign(msg, key, enc, options) {
  74. if (typeof enc === 'object') {
  75. options = enc;
  76. enc = null;
  77. }
  78. if (!options)
  79. options = {};
  80. key = this.keyFromPrivate(key, enc);
  81. msg = this._truncateToN(new BN(msg, 16));
  82. // Zero-extend key to provide enough entropy
  83. var bytes = this.n.byteLength();
  84. var bkey = key.getPrivate().toArray('be', bytes);
  85. // Zero-extend nonce to have the same byte size as N
  86. var nonce = msg.toArray('be', bytes);
  87. // Instantiate Hmac_DRBG
  88. var drbg = new HmacDRBG({
  89. hash: this.hash,
  90. entropy: bkey,
  91. nonce: nonce,
  92. pers: options.pers,
  93. persEnc: options.persEnc || 'utf8',
  94. });
  95. // Number of bytes to generate
  96. var ns1 = this.n.sub(new BN(1));
  97. for (var iter = 0; ; iter++) {
  98. var k = options.k ?
  99. options.k(iter) :
  100. new BN(drbg.generate(this.n.byteLength()));
  101. k = this._truncateToN(k, true);
  102. if (k.cmpn(1) <= 0 || k.cmp(ns1) >= 0)
  103. continue;
  104. var kp = this.g.mul(k);
  105. if (kp.isInfinity())
  106. continue;
  107. var kpX = kp.getX();
  108. var r = kpX.umod(this.n);
  109. if (r.cmpn(0) === 0)
  110. continue;
  111. var s = k.invm(this.n).mul(r.mul(key.getPrivate()).iadd(msg));
  112. s = s.umod(this.n);
  113. if (s.cmpn(0) === 0)
  114. continue;
  115. var recoveryParam = (kp.getY().isOdd() ? 1 : 0) |
  116. (kpX.cmp(r) !== 0 ? 2 : 0);
  117. // Use complement of `s`, if it is > `n / 2`
  118. if (options.canonical && s.cmp(this.nh) > 0) {
  119. s = this.n.sub(s);
  120. recoveryParam ^= 1;
  121. }
  122. return new Signature({ r: r, s: s, recoveryParam: recoveryParam });
  123. }
  124. };
  125. EC.prototype.verify = function verify(msg, signature, key, enc) {
  126. msg = this._truncateToN(new BN(msg, 16));
  127. key = this.keyFromPublic(key, enc);
  128. signature = new Signature(signature, 'hex');
  129. // Perform primitive values validation
  130. var r = signature.r;
  131. var s = signature.s;
  132. if (r.cmpn(1) < 0 || r.cmp(this.n) >= 0)
  133. return false;
  134. if (s.cmpn(1) < 0 || s.cmp(this.n) >= 0)
  135. return false;
  136. // Validate signature
  137. var sinv = s.invm(this.n);
  138. var u1 = sinv.mul(msg).umod(this.n);
  139. var u2 = sinv.mul(r).umod(this.n);
  140. var p;
  141. if (!this.curve._maxwellTrick) {
  142. p = this.g.mulAdd(u1, key.getPublic(), u2);
  143. if (p.isInfinity())
  144. return false;
  145. return p.getX().umod(this.n).cmp(r) === 0;
  146. }
  147. // NOTE: Greg Maxwell's trick, inspired by:
  148. // https://git.io/vad3K
  149. p = this.g.jmulAdd(u1, key.getPublic(), u2);
  150. if (p.isInfinity())
  151. return false;
  152. // Compare `p.x` of Jacobian point with `r`,
  153. // this will do `p.x == r * p.z^2` instead of multiplying `p.x` by the
  154. // inverse of `p.z^2`
  155. return p.eqXToP(r);
  156. };
  157. EC.prototype.recoverPubKey = function(msg, signature, j, enc) {
  158. assert((3 & j) === j, 'The recovery param is more than two bits');
  159. signature = new Signature(signature, enc);
  160. var n = this.n;
  161. var e = new BN(msg);
  162. var r = signature.r;
  163. var s = signature.s;
  164. // A set LSB signifies that the y-coordinate is odd
  165. var isYOdd = j & 1;
  166. var isSecondKey = j >> 1;
  167. if (r.cmp(this.curve.p.umod(this.curve.n)) >= 0 && isSecondKey)
  168. throw new Error('Unable to find sencond key candinate');
  169. // 1.1. Let x = r + jn.
  170. if (isSecondKey)
  171. r = this.curve.pointFromX(r.add(this.curve.n), isYOdd);
  172. else
  173. r = this.curve.pointFromX(r, isYOdd);
  174. var rInv = signature.r.invm(n);
  175. var s1 = n.sub(e).mul(rInv).umod(n);
  176. var s2 = s.mul(rInv).umod(n);
  177. // 1.6.1 Compute Q = r^-1 (sR - eG)
  178. // Q = r^-1 (sR + -eG)
  179. return this.g.mulAdd(s1, r, s2);
  180. };
  181. EC.prototype.getKeyRecoveryParam = function(e, signature, Q, enc) {
  182. signature = new Signature(signature, enc);
  183. if (signature.recoveryParam !== null)
  184. return signature.recoveryParam;
  185. for (var i = 0; i < 4; i++) {
  186. var Qprime;
  187. try {
  188. Qprime = this.recoverPubKey(e, signature, i);
  189. } catch (e) {
  190. continue;
  191. }
  192. if (Qprime.eq(Q))
  193. return i;
  194. }
  195. throw new Error('Unable to find valid recovery factor');
  196. };