curve.js 6.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156
  1. /*! noble-curves - MIT License (c) 2022 Paul Miller (paulmillr.com) */
  2. // Abelian group utilities
  3. import { validateField, nLength } from './modular.js';
  4. import { validateObject } from './utils.js';
  5. const _0n = BigInt(0);
  6. const _1n = BigInt(1);
  7. // Elliptic curve multiplication of Point by scalar. Fragile.
  8. // Scalars should always be less than curve order: this should be checked inside of a curve itself.
  9. // Creates precomputation tables for fast multiplication:
  10. // - private scalar is split by fixed size windows of W bits
  11. // - every window point is collected from window's table & added to accumulator
  12. // - since windows are different, same point inside tables won't be accessed more than once per calc
  13. // - each multiplication is 'Math.ceil(CURVE_ORDER / 𝑊) + 1' point additions (fixed for any scalar)
  14. // - +1 window is neccessary for wNAF
  15. // - wNAF reduces table size: 2x less memory + 2x faster generation, but 10% slower multiplication
  16. // TODO: Research returning 2d JS array of windows, instead of a single window. This would allow
  17. // windows to be in different memory locations
  18. export function wNAF(c, bits) {
  19. const constTimeNegate = (condition, item) => {
  20. const neg = item.negate();
  21. return condition ? neg : item;
  22. };
  23. const opts = (W) => {
  24. const windows = Math.ceil(bits / W) + 1; // +1, because
  25. const windowSize = 2 ** (W - 1); // -1 because we skip zero
  26. return { windows, windowSize };
  27. };
  28. return {
  29. constTimeNegate,
  30. // non-const time multiplication ladder
  31. unsafeLadder(elm, n) {
  32. let p = c.ZERO;
  33. let d = elm;
  34. while (n > _0n) {
  35. if (n & _1n)
  36. p = p.add(d);
  37. d = d.double();
  38. n >>= _1n;
  39. }
  40. return p;
  41. },
  42. /**
  43. * Creates a wNAF precomputation window. Used for caching.
  44. * Default window size is set by `utils.precompute()` and is equal to 8.
  45. * Number of precomputed points depends on the curve size:
  46. * 2^(𝑊−1) * (Math.ceil(𝑛 / 𝑊) + 1), where:
  47. * - 𝑊 is the window size
  48. * - 𝑛 is the bitlength of the curve order.
  49. * For a 256-bit curve and window size 8, the number of precomputed points is 128 * 33 = 4224.
  50. * @returns precomputed point tables flattened to a single array
  51. */
  52. precomputeWindow(elm, W) {
  53. const { windows, windowSize } = opts(W);
  54. const points = [];
  55. let p = elm;
  56. let base = p;
  57. for (let window = 0; window < windows; window++) {
  58. base = p;
  59. points.push(base);
  60. // =1, because we skip zero
  61. for (let i = 1; i < windowSize; i++) {
  62. base = base.add(p);
  63. points.push(base);
  64. }
  65. p = base.double();
  66. }
  67. return points;
  68. },
  69. /**
  70. * Implements ec multiplication using precomputed tables and w-ary non-adjacent form.
  71. * @param W window size
  72. * @param precomputes precomputed tables
  73. * @param n scalar (we don't check here, but should be less than curve order)
  74. * @returns real and fake (for const-time) points
  75. */
  76. wNAF(W, precomputes, n) {
  77. // TODO: maybe check that scalar is less than group order? wNAF behavious is undefined otherwise
  78. // But need to carefully remove other checks before wNAF. ORDER == bits here
  79. const { windows, windowSize } = opts(W);
  80. let p = c.ZERO;
  81. let f = c.BASE;
  82. const mask = BigInt(2 ** W - 1); // Create mask with W ones: 0b1111 for W=4 etc.
  83. const maxNumber = 2 ** W;
  84. const shiftBy = BigInt(W);
  85. for (let window = 0; window < windows; window++) {
  86. const offset = window * windowSize;
  87. // Extract W bits.
  88. let wbits = Number(n & mask);
  89. // Shift number by W bits.
  90. n >>= shiftBy;
  91. // If the bits are bigger than max size, we'll split those.
  92. // +224 => 256 - 32
  93. if (wbits > windowSize) {
  94. wbits -= maxNumber;
  95. n += _1n;
  96. }
  97. // This code was first written with assumption that 'f' and 'p' will never be infinity point:
  98. // since each addition is multiplied by 2 ** W, it cannot cancel each other. However,
  99. // there is negate now: it is possible that negated element from low value
  100. // would be the same as high element, which will create carry into next window.
  101. // It's not obvious how this can fail, but still worth investigating later.
  102. // Check if we're onto Zero point.
  103. // Add random point inside current window to f.
  104. const offset1 = offset;
  105. const offset2 = offset + Math.abs(wbits) - 1; // -1 because we skip zero
  106. const cond1 = window % 2 !== 0;
  107. const cond2 = wbits < 0;
  108. if (wbits === 0) {
  109. // The most important part for const-time getPublicKey
  110. f = f.add(constTimeNegate(cond1, precomputes[offset1]));
  111. }
  112. else {
  113. p = p.add(constTimeNegate(cond2, precomputes[offset2]));
  114. }
  115. }
  116. // JIT-compiler should not eliminate f here, since it will later be used in normalizeZ()
  117. // Even if the variable is still unused, there are some checks which will
  118. // throw an exception, so compiler needs to prove they won't happen, which is hard.
  119. // At this point there is a way to F be infinity-point even if p is not,
  120. // which makes it less const-time: around 1 bigint multiply.
  121. return { p, f };
  122. },
  123. wNAFCached(P, precomputesMap, n, transform) {
  124. // @ts-ignore
  125. const W = P._WINDOW_SIZE || 1;
  126. // Calculate precomputes on a first run, reuse them after
  127. let comp = precomputesMap.get(P);
  128. if (!comp) {
  129. comp = this.precomputeWindow(P, W);
  130. if (W !== 1) {
  131. precomputesMap.set(P, transform(comp));
  132. }
  133. }
  134. return this.wNAF(W, comp, n);
  135. },
  136. };
  137. }
  138. export function validateBasic(curve) {
  139. validateField(curve.Fp);
  140. validateObject(curve, {
  141. n: 'bigint',
  142. h: 'bigint',
  143. Gx: 'field',
  144. Gy: 'field',
  145. }, {
  146. nBitLength: 'isSafeInteger',
  147. nByteLength: 'isSafeInteger',
  148. });
  149. // Set defaults
  150. return Object.freeze({
  151. ...nLength(curve.n, curve.nBitLength),
  152. ...curve,
  153. ...{ p: curve.Fp.ORDER },
  154. });
  155. }
  156. //# sourceMappingURL=curve.js.map