index.js 6.1 KB

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