ec.js 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562
  1. // Basic Javascript Elliptic Curve implementation
  2. // Ported loosely from BouncyCastle's Java EC code
  3. // Only Fp curves implemented for now
  4. // Requires jsbn.js and jsbn2.js
  5. var BigInteger = require('jsbn').BigInteger
  6. var Barrett = BigInteger.prototype.Barrett
  7. // ----------------
  8. // ECFieldElementFp
  9. // constructor
  10. function ECFieldElementFp(q,x) {
  11. this.x = x;
  12. // TODO if(x.compareTo(q) >= 0) error
  13. this.q = q;
  14. }
  15. function feFpEquals(other) {
  16. if(other == this) return true;
  17. return (this.q.equals(other.q) && this.x.equals(other.x));
  18. }
  19. function feFpToBigInteger() {
  20. return this.x;
  21. }
  22. function feFpNegate() {
  23. return new ECFieldElementFp(this.q, this.x.negate().mod(this.q));
  24. }
  25. function feFpAdd(b) {
  26. return new ECFieldElementFp(this.q, this.x.add(b.toBigInteger()).mod(this.q));
  27. }
  28. function feFpSubtract(b) {
  29. return new ECFieldElementFp(this.q, this.x.subtract(b.toBigInteger()).mod(this.q));
  30. }
  31. function feFpMultiply(b) {
  32. return new ECFieldElementFp(this.q, this.x.multiply(b.toBigInteger()).mod(this.q));
  33. }
  34. function feFpSquare() {
  35. return new ECFieldElementFp(this.q, this.x.square().mod(this.q));
  36. }
  37. function feFpDivide(b) {
  38. return new ECFieldElementFp(this.q, this.x.multiply(b.toBigInteger().modInverse(this.q)).mod(this.q));
  39. }
  40. ECFieldElementFp.prototype.equals = feFpEquals;
  41. ECFieldElementFp.prototype.toBigInteger = feFpToBigInteger;
  42. ECFieldElementFp.prototype.negate = feFpNegate;
  43. ECFieldElementFp.prototype.add = feFpAdd;
  44. ECFieldElementFp.prototype.subtract = feFpSubtract;
  45. ECFieldElementFp.prototype.multiply = feFpMultiply;
  46. ECFieldElementFp.prototype.square = feFpSquare;
  47. ECFieldElementFp.prototype.divide = feFpDivide;
  48. // ----------------
  49. // ECPointFp
  50. // constructor
  51. function ECPointFp(curve,x,y,z) {
  52. this.curve = curve;
  53. this.x = x;
  54. this.y = y;
  55. // Projective coordinates: either zinv == null or z * zinv == 1
  56. // z and zinv are just BigIntegers, not fieldElements
  57. if(z == null) {
  58. this.z = BigInteger.ONE;
  59. }
  60. else {
  61. this.z = z;
  62. }
  63. this.zinv = null;
  64. //TODO: compression flag
  65. }
  66. function pointFpGetX() {
  67. if(this.zinv == null) {
  68. this.zinv = this.z.modInverse(this.curve.q);
  69. }
  70. var r = this.x.toBigInteger().multiply(this.zinv);
  71. this.curve.reduce(r);
  72. return this.curve.fromBigInteger(r);
  73. }
  74. function pointFpGetY() {
  75. if(this.zinv == null) {
  76. this.zinv = this.z.modInverse(this.curve.q);
  77. }
  78. var r = this.y.toBigInteger().multiply(this.zinv);
  79. this.curve.reduce(r);
  80. return this.curve.fromBigInteger(r);
  81. }
  82. function pointFpEquals(other) {
  83. if(other == this) return true;
  84. if(this.isInfinity()) return other.isInfinity();
  85. if(other.isInfinity()) return this.isInfinity();
  86. var u, v;
  87. // u = Y2 * Z1 - Y1 * Z2
  88. u = other.y.toBigInteger().multiply(this.z).subtract(this.y.toBigInteger().multiply(other.z)).mod(this.curve.q);
  89. if(!u.equals(BigInteger.ZERO)) return false;
  90. // v = X2 * Z1 - X1 * Z2
  91. v = other.x.toBigInteger().multiply(this.z).subtract(this.x.toBigInteger().multiply(other.z)).mod(this.curve.q);
  92. return v.equals(BigInteger.ZERO);
  93. }
  94. function pointFpIsInfinity() {
  95. if((this.x == null) && (this.y == null)) return true;
  96. return this.z.equals(BigInteger.ZERO) && !this.y.toBigInteger().equals(BigInteger.ZERO);
  97. }
  98. function pointFpNegate() {
  99. return new ECPointFp(this.curve, this.x, this.y.negate(), this.z);
  100. }
  101. function pointFpAdd(b) {
  102. if(this.isInfinity()) return b;
  103. if(b.isInfinity()) return this;
  104. // u = Y2 * Z1 - Y1 * Z2
  105. var u = b.y.toBigInteger().multiply(this.z).subtract(this.y.toBigInteger().multiply(b.z)).mod(this.curve.q);
  106. // v = X2 * Z1 - X1 * Z2
  107. var v = b.x.toBigInteger().multiply(this.z).subtract(this.x.toBigInteger().multiply(b.z)).mod(this.curve.q);
  108. if(BigInteger.ZERO.equals(v)) {
  109. if(BigInteger.ZERO.equals(u)) {
  110. return this.twice(); // this == b, so double
  111. }
  112. return this.curve.getInfinity(); // this = -b, so infinity
  113. }
  114. var THREE = new BigInteger("3");
  115. var x1 = this.x.toBigInteger();
  116. var y1 = this.y.toBigInteger();
  117. var x2 = b.x.toBigInteger();
  118. var y2 = b.y.toBigInteger();
  119. var v2 = v.square();
  120. var v3 = v2.multiply(v);
  121. var x1v2 = x1.multiply(v2);
  122. var zu2 = u.square().multiply(this.z);
  123. // x3 = v * (z2 * (z1 * u^2 - 2 * x1 * v^2) - v^3)
  124. var x3 = zu2.subtract(x1v2.shiftLeft(1)).multiply(b.z).subtract(v3).multiply(v).mod(this.curve.q);
  125. // y3 = z2 * (3 * x1 * u * v^2 - y1 * v^3 - z1 * u^3) + u * v^3
  126. var y3 = x1v2.multiply(THREE).multiply(u).subtract(y1.multiply(v3)).subtract(zu2.multiply(u)).multiply(b.z).add(u.multiply(v3)).mod(this.curve.q);
  127. // z3 = v^3 * z1 * z2
  128. var z3 = v3.multiply(this.z).multiply(b.z).mod(this.curve.q);
  129. return new ECPointFp(this.curve, this.curve.fromBigInteger(x3), this.curve.fromBigInteger(y3), z3);
  130. }
  131. function pointFpTwice() {
  132. if(this.isInfinity()) return this;
  133. if(this.y.toBigInteger().signum() == 0) return this.curve.getInfinity();
  134. // TODO: optimized handling of constants
  135. var THREE = new BigInteger("3");
  136. var x1 = this.x.toBigInteger();
  137. var y1 = this.y.toBigInteger();
  138. var y1z1 = y1.multiply(this.z);
  139. var y1sqz1 = y1z1.multiply(y1).mod(this.curve.q);
  140. var a = this.curve.a.toBigInteger();
  141. // w = 3 * x1^2 + a * z1^2
  142. var w = x1.square().multiply(THREE);
  143. if(!BigInteger.ZERO.equals(a)) {
  144. w = w.add(this.z.square().multiply(a));
  145. }
  146. w = w.mod(this.curve.q);
  147. //this.curve.reduce(w);
  148. // x3 = 2 * y1 * z1 * (w^2 - 8 * x1 * y1^2 * z1)
  149. var x3 = w.square().subtract(x1.shiftLeft(3).multiply(y1sqz1)).shiftLeft(1).multiply(y1z1).mod(this.curve.q);
  150. // y3 = 4 * y1^2 * z1 * (3 * w * x1 - 2 * y1^2 * z1) - w^3
  151. var y3 = w.multiply(THREE).multiply(x1).subtract(y1sqz1.shiftLeft(1)).shiftLeft(2).multiply(y1sqz1).subtract(w.square().multiply(w)).mod(this.curve.q);
  152. // z3 = 8 * (y1 * z1)^3
  153. var z3 = y1z1.square().multiply(y1z1).shiftLeft(3).mod(this.curve.q);
  154. return new ECPointFp(this.curve, this.curve.fromBigInteger(x3), this.curve.fromBigInteger(y3), z3);
  155. }
  156. // Simple NAF (Non-Adjacent Form) multiplication algorithm
  157. // TODO: modularize the multiplication algorithm
  158. function pointFpMultiply(k) {
  159. if(this.isInfinity()) return this;
  160. if(k.signum() == 0) return this.curve.getInfinity();
  161. var e = k;
  162. var h = e.multiply(new BigInteger("3"));
  163. var neg = this.negate();
  164. var R = this;
  165. var i;
  166. for(i = h.bitLength() - 2; i > 0; --i) {
  167. R = R.twice();
  168. var hBit = h.testBit(i);
  169. var eBit = e.testBit(i);
  170. if (hBit != eBit) {
  171. R = R.add(hBit ? this : neg);
  172. }
  173. }
  174. return R;
  175. }
  176. // Compute this*j + x*k (simultaneous multiplication)
  177. function pointFpMultiplyTwo(j,x,k) {
  178. var i;
  179. if(j.bitLength() > k.bitLength())
  180. i = j.bitLength() - 1;
  181. else
  182. i = k.bitLength() - 1;
  183. var R = this.curve.getInfinity();
  184. var both = this.add(x);
  185. while(i >= 0) {
  186. R = R.twice();
  187. if(j.testBit(i)) {
  188. if(k.testBit(i)) {
  189. R = R.add(both);
  190. }
  191. else {
  192. R = R.add(this);
  193. }
  194. }
  195. else {
  196. if(k.testBit(i)) {
  197. R = R.add(x);
  198. }
  199. }
  200. --i;
  201. }
  202. return R;
  203. }
  204. ECPointFp.prototype.getX = pointFpGetX;
  205. ECPointFp.prototype.getY = pointFpGetY;
  206. ECPointFp.prototype.equals = pointFpEquals;
  207. ECPointFp.prototype.isInfinity = pointFpIsInfinity;
  208. ECPointFp.prototype.negate = pointFpNegate;
  209. ECPointFp.prototype.add = pointFpAdd;
  210. ECPointFp.prototype.twice = pointFpTwice;
  211. ECPointFp.prototype.multiply = pointFpMultiply;
  212. ECPointFp.prototype.multiplyTwo = pointFpMultiplyTwo;
  213. // ----------------
  214. // ECCurveFp
  215. // constructor
  216. function ECCurveFp(q,a,b) {
  217. this.q = q;
  218. this.a = this.fromBigInteger(a);
  219. this.b = this.fromBigInteger(b);
  220. this.infinity = new ECPointFp(this, null, null);
  221. this.reducer = new Barrett(this.q);
  222. }
  223. function curveFpGetQ() {
  224. return this.q;
  225. }
  226. function curveFpGetA() {
  227. return this.a;
  228. }
  229. function curveFpGetB() {
  230. return this.b;
  231. }
  232. function curveFpEquals(other) {
  233. if(other == this) return true;
  234. return(this.q.equals(other.q) && this.a.equals(other.a) && this.b.equals(other.b));
  235. }
  236. function curveFpGetInfinity() {
  237. return this.infinity;
  238. }
  239. function curveFpFromBigInteger(x) {
  240. return new ECFieldElementFp(this.q, x);
  241. }
  242. function curveReduce(x) {
  243. this.reducer.reduce(x);
  244. }
  245. // for now, work with hex strings because they're easier in JS
  246. function curveFpDecodePointHex(s) {
  247. switch(parseInt(s.substr(0,2), 16)) { // first byte
  248. case 0:
  249. return this.infinity;
  250. case 2:
  251. case 3:
  252. // point compression not supported yet
  253. return null;
  254. case 4:
  255. case 6:
  256. case 7:
  257. var len = (s.length - 2) / 2;
  258. var xHex = s.substr(2, len);
  259. var yHex = s.substr(len+2, len);
  260. return new ECPointFp(this,
  261. this.fromBigInteger(new BigInteger(xHex, 16)),
  262. this.fromBigInteger(new BigInteger(yHex, 16)));
  263. default: // unsupported
  264. return null;
  265. }
  266. }
  267. function curveFpEncodePointHex(p) {
  268. if (p.isInfinity()) return "00";
  269. var xHex = p.getX().toBigInteger().toString(16);
  270. var yHex = p.getY().toBigInteger().toString(16);
  271. var oLen = this.getQ().toString(16).length;
  272. if ((oLen % 2) != 0) oLen++;
  273. while (xHex.length < oLen) {
  274. xHex = "0" + xHex;
  275. }
  276. while (yHex.length < oLen) {
  277. yHex = "0" + yHex;
  278. }
  279. return "04" + xHex + yHex;
  280. }
  281. ECCurveFp.prototype.getQ = curveFpGetQ;
  282. ECCurveFp.prototype.getA = curveFpGetA;
  283. ECCurveFp.prototype.getB = curveFpGetB;
  284. ECCurveFp.prototype.equals = curveFpEquals;
  285. ECCurveFp.prototype.getInfinity = curveFpGetInfinity;
  286. ECCurveFp.prototype.fromBigInteger = curveFpFromBigInteger;
  287. ECCurveFp.prototype.reduce = curveReduce;
  288. //ECCurveFp.prototype.decodePointHex = curveFpDecodePointHex;
  289. ECCurveFp.prototype.encodePointHex = curveFpEncodePointHex;
  290. // from: https://github.com/kaielvin/jsbn-ec-point-compression
  291. ECCurveFp.prototype.decodePointHex = function(s)
  292. {
  293. var yIsEven;
  294. switch(parseInt(s.substr(0,2), 16)) { // first byte
  295. case 0:
  296. return this.infinity;
  297. case 2:
  298. yIsEven = false;
  299. case 3:
  300. if(yIsEven == undefined) yIsEven = true;
  301. var len = s.length - 2;
  302. var xHex = s.substr(2, len);
  303. var x = this.fromBigInteger(new BigInteger(xHex,16));
  304. var alpha = x.multiply(x.square().add(this.getA())).add(this.getB());
  305. var beta = alpha.sqrt();
  306. if (beta == null) throw "Invalid point compression";
  307. var betaValue = beta.toBigInteger();
  308. if (betaValue.testBit(0) != yIsEven)
  309. {
  310. // Use the other root
  311. beta = this.fromBigInteger(this.getQ().subtract(betaValue));
  312. }
  313. return new ECPointFp(this,x,beta);
  314. case 4:
  315. case 6:
  316. case 7:
  317. var len = (s.length - 2) / 2;
  318. var xHex = s.substr(2, len);
  319. var yHex = s.substr(len+2, len);
  320. return new ECPointFp(this,
  321. this.fromBigInteger(new BigInteger(xHex, 16)),
  322. this.fromBigInteger(new BigInteger(yHex, 16)));
  323. default: // unsupported
  324. return null;
  325. }
  326. }
  327. ECCurveFp.prototype.encodeCompressedPointHex = function(p)
  328. {
  329. if (p.isInfinity()) return "00";
  330. var xHex = p.getX().toBigInteger().toString(16);
  331. var oLen = this.getQ().toString(16).length;
  332. if ((oLen % 2) != 0) oLen++;
  333. while (xHex.length < oLen)
  334. xHex = "0" + xHex;
  335. var yPrefix;
  336. if(p.getY().toBigInteger().isEven()) yPrefix = "02";
  337. else yPrefix = "03";
  338. return yPrefix + xHex;
  339. }
  340. ECFieldElementFp.prototype.getR = function()
  341. {
  342. if(this.r != undefined) return this.r;
  343. this.r = null;
  344. var bitLength = this.q.bitLength();
  345. if (bitLength > 128)
  346. {
  347. var firstWord = this.q.shiftRight(bitLength - 64);
  348. if (firstWord.intValue() == -1)
  349. {
  350. this.r = BigInteger.ONE.shiftLeft(bitLength).subtract(this.q);
  351. }
  352. }
  353. return this.r;
  354. }
  355. ECFieldElementFp.prototype.modMult = function(x1,x2)
  356. {
  357. return this.modReduce(x1.multiply(x2));
  358. }
  359. ECFieldElementFp.prototype.modReduce = function(x)
  360. {
  361. if (this.getR() != null)
  362. {
  363. var qLen = q.bitLength();
  364. while (x.bitLength() > (qLen + 1))
  365. {
  366. var u = x.shiftRight(qLen);
  367. var v = x.subtract(u.shiftLeft(qLen));
  368. if (!this.getR().equals(BigInteger.ONE))
  369. {
  370. u = u.multiply(this.getR());
  371. }
  372. x = u.add(v);
  373. }
  374. while (x.compareTo(q) >= 0)
  375. {
  376. x = x.subtract(q);
  377. }
  378. }
  379. else
  380. {
  381. x = x.mod(q);
  382. }
  383. return x;
  384. }
  385. ECFieldElementFp.prototype.sqrt = function()
  386. {
  387. if (!this.q.testBit(0)) throw "unsupported";
  388. // p mod 4 == 3
  389. if (this.q.testBit(1))
  390. {
  391. var z = new ECFieldElementFp(this.q,this.x.modPow(this.q.shiftRight(2).add(BigInteger.ONE),this.q));
  392. return z.square().equals(this) ? z : null;
  393. }
  394. // p mod 4 == 1
  395. var qMinusOne = this.q.subtract(BigInteger.ONE);
  396. var legendreExponent = qMinusOne.shiftRight(1);
  397. if (!(this.x.modPow(legendreExponent, this.q).equals(BigInteger.ONE)))
  398. {
  399. return null;
  400. }
  401. var u = qMinusOne.shiftRight(2);
  402. var k = u.shiftLeft(1).add(BigInteger.ONE);
  403. var Q = this.x;
  404. var fourQ = modDouble(modDouble(Q));
  405. var U, V;
  406. do
  407. {
  408. var P;
  409. do
  410. {
  411. P = new BigInteger(this.q.bitLength(), new SecureRandom());
  412. }
  413. while (P.compareTo(this.q) >= 0
  414. || !(P.multiply(P).subtract(fourQ).modPow(legendreExponent, this.q).equals(qMinusOne)));
  415. var result = this.lucasSequence(P, Q, k);
  416. U = result[0];
  417. V = result[1];
  418. if (this.modMult(V, V).equals(fourQ))
  419. {
  420. // Integer division by 2, mod q
  421. if (V.testBit(0))
  422. {
  423. V = V.add(q);
  424. }
  425. V = V.shiftRight(1);
  426. return new ECFieldElementFp(q,V);
  427. }
  428. }
  429. while (U.equals(BigInteger.ONE) || U.equals(qMinusOne));
  430. return null;
  431. }
  432. ECFieldElementFp.prototype.lucasSequence = function(P,Q,k)
  433. {
  434. var n = k.bitLength();
  435. var s = k.getLowestSetBit();
  436. var Uh = BigInteger.ONE;
  437. var Vl = BigInteger.TWO;
  438. var Vh = P;
  439. var Ql = BigInteger.ONE;
  440. var Qh = BigInteger.ONE;
  441. for (var j = n - 1; j >= s + 1; --j)
  442. {
  443. Ql = this.modMult(Ql, Qh);
  444. if (k.testBit(j))
  445. {
  446. Qh = this.modMult(Ql, Q);
  447. Uh = this.modMult(Uh, Vh);
  448. Vl = this.modReduce(Vh.multiply(Vl).subtract(P.multiply(Ql)));
  449. Vh = this.modReduce(Vh.multiply(Vh).subtract(Qh.shiftLeft(1)));
  450. }
  451. else
  452. {
  453. Qh = Ql;
  454. Uh = this.modReduce(Uh.multiply(Vl).subtract(Ql));
  455. Vh = this.modReduce(Vh.multiply(Vl).subtract(P.multiply(Ql)));
  456. Vl = this.modReduce(Vl.multiply(Vl).subtract(Ql.shiftLeft(1)));
  457. }
  458. }
  459. Ql = this.modMult(Ql, Qh);
  460. Qh = this.modMult(Ql, Q);
  461. Uh = this.modReduce(Uh.multiply(Vl).subtract(Ql));
  462. Vl = this.modReduce(Vh.multiply(Vl).subtract(P.multiply(Ql)));
  463. Ql = this.modMult(Ql, Qh);
  464. for (var j = 1; j <= s; ++j)
  465. {
  466. Uh = this.modMult(Uh, Vl);
  467. Vl = this.modReduce(Vl.multiply(Vl).subtract(Ql.shiftLeft(1)));
  468. Ql = this.modMult(Ql, Ql);
  469. }
  470. return [ Uh, Vl ];
  471. }
  472. var exports = {
  473. ECCurveFp: ECCurveFp,
  474. ECPointFp: ECPointFp,
  475. ECFieldElementFp: ECFieldElementFp
  476. }
  477. module.exports = exports