hash-to-curve.js 6.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173
  1. import { mod } from './modular.js';
  2. import { abytes, bytesToNumberBE, concatBytes, utf8ToBytes, validateObject } from './utils.js';
  3. // Octet Stream to Integer. "spec" implementation of os2ip is 2.5x slower vs bytesToNumberBE.
  4. const os2ip = bytesToNumberBE;
  5. // Integer to Octet Stream (numberToBytesBE)
  6. function i2osp(value, length) {
  7. if (value < 0 || value >= 1 << (8 * length)) {
  8. throw new Error(`bad I2OSP call: value=${value} length=${length}`);
  9. }
  10. const res = Array.from({ length }).fill(0);
  11. for (let i = length - 1; i >= 0; i--) {
  12. res[i] = value & 0xff;
  13. value >>>= 8;
  14. }
  15. return new Uint8Array(res);
  16. }
  17. function strxor(a, b) {
  18. const arr = new Uint8Array(a.length);
  19. for (let i = 0; i < a.length; i++) {
  20. arr[i] = a[i] ^ b[i];
  21. }
  22. return arr;
  23. }
  24. function anum(item) {
  25. if (!Number.isSafeInteger(item))
  26. throw new Error('number expected');
  27. }
  28. // Produces a uniformly random byte string using a cryptographic hash function H that outputs b bits
  29. // https://www.rfc-editor.org/rfc/rfc9380#section-5.3.1
  30. export function expand_message_xmd(msg, DST, lenInBytes, H) {
  31. abytes(msg);
  32. abytes(DST);
  33. anum(lenInBytes);
  34. // https://www.rfc-editor.org/rfc/rfc9380#section-5.3.3
  35. if (DST.length > 255)
  36. DST = H(concatBytes(utf8ToBytes('H2C-OVERSIZE-DST-'), DST));
  37. const { outputLen: b_in_bytes, blockLen: r_in_bytes } = H;
  38. const ell = Math.ceil(lenInBytes / b_in_bytes);
  39. if (ell > 255)
  40. throw new Error('Invalid xmd length');
  41. const DST_prime = concatBytes(DST, i2osp(DST.length, 1));
  42. const Z_pad = i2osp(0, r_in_bytes);
  43. const l_i_b_str = i2osp(lenInBytes, 2); // len_in_bytes_str
  44. const b = new Array(ell);
  45. const b_0 = H(concatBytes(Z_pad, msg, l_i_b_str, i2osp(0, 1), DST_prime));
  46. b[0] = H(concatBytes(b_0, i2osp(1, 1), DST_prime));
  47. for (let i = 1; i <= ell; i++) {
  48. const args = [strxor(b_0, b[i - 1]), i2osp(i + 1, 1), DST_prime];
  49. b[i] = H(concatBytes(...args));
  50. }
  51. const pseudo_random_bytes = concatBytes(...b);
  52. return pseudo_random_bytes.slice(0, lenInBytes);
  53. }
  54. // Produces a uniformly random byte string using an extendable-output function (XOF) H.
  55. // 1. The collision resistance of H MUST be at least k bits.
  56. // 2. H MUST be an XOF that has been proved indifferentiable from
  57. // a random oracle under a reasonable cryptographic assumption.
  58. // https://www.rfc-editor.org/rfc/rfc9380#section-5.3.2
  59. export function expand_message_xof(msg, DST, lenInBytes, k, H) {
  60. abytes(msg);
  61. abytes(DST);
  62. anum(lenInBytes);
  63. // https://www.rfc-editor.org/rfc/rfc9380#section-5.3.3
  64. // DST = H('H2C-OVERSIZE-DST-' || a_very_long_DST, Math.ceil((lenInBytes * k) / 8));
  65. if (DST.length > 255) {
  66. const dkLen = Math.ceil((2 * k) / 8);
  67. DST = H.create({ dkLen }).update(utf8ToBytes('H2C-OVERSIZE-DST-')).update(DST).digest();
  68. }
  69. if (lenInBytes > 65535 || DST.length > 255)
  70. throw new Error('expand_message_xof: invalid lenInBytes');
  71. return (H.create({ dkLen: lenInBytes })
  72. .update(msg)
  73. .update(i2osp(lenInBytes, 2))
  74. // 2. DST_prime = DST || I2OSP(len(DST), 1)
  75. .update(DST)
  76. .update(i2osp(DST.length, 1))
  77. .digest());
  78. }
  79. /**
  80. * Hashes arbitrary-length byte strings to a list of one or more elements of a finite field F
  81. * https://www.rfc-editor.org/rfc/rfc9380#section-5.2
  82. * @param msg a byte string containing the message to hash
  83. * @param count the number of elements of F to output
  84. * @param options `{DST: string, p: bigint, m: number, k: number, expand: 'xmd' | 'xof', hash: H}`, see above
  85. * @returns [u_0, ..., u_(count - 1)], a list of field elements.
  86. */
  87. export function hash_to_field(msg, count, options) {
  88. validateObject(options, {
  89. DST: 'stringOrUint8Array',
  90. p: 'bigint',
  91. m: 'isSafeInteger',
  92. k: 'isSafeInteger',
  93. hash: 'hash',
  94. });
  95. const { p, k, m, hash, expand, DST: _DST } = options;
  96. abytes(msg);
  97. anum(count);
  98. const DST = typeof _DST === 'string' ? utf8ToBytes(_DST) : _DST;
  99. const log2p = p.toString(2).length;
  100. const L = Math.ceil((log2p + k) / 8); // section 5.1 of ietf draft link above
  101. const len_in_bytes = count * m * L;
  102. let prb; // pseudo_random_bytes
  103. if (expand === 'xmd') {
  104. prb = expand_message_xmd(msg, DST, len_in_bytes, hash);
  105. }
  106. else if (expand === 'xof') {
  107. prb = expand_message_xof(msg, DST, len_in_bytes, k, hash);
  108. }
  109. else if (expand === '_internal_pass') {
  110. // for internal tests only
  111. prb = msg;
  112. }
  113. else {
  114. throw new Error('expand must be "xmd" or "xof"');
  115. }
  116. const u = new Array(count);
  117. for (let i = 0; i < count; i++) {
  118. const e = new Array(m);
  119. for (let j = 0; j < m; j++) {
  120. const elm_offset = L * (j + i * m);
  121. const tv = prb.subarray(elm_offset, elm_offset + L);
  122. e[j] = mod(os2ip(tv), p);
  123. }
  124. u[i] = e;
  125. }
  126. return u;
  127. }
  128. export function isogenyMap(field, map) {
  129. // Make same order as in spec
  130. const COEFF = map.map((i) => Array.from(i).reverse());
  131. return (x, y) => {
  132. const [xNum, xDen, yNum, yDen] = COEFF.map((val) => val.reduce((acc, i) => field.add(field.mul(acc, x), i)));
  133. x = field.div(xNum, xDen); // xNum / xDen
  134. y = field.mul(y, field.div(yNum, yDen)); // y * (yNum / yDev)
  135. return { x, y };
  136. };
  137. }
  138. export function createHasher(Point, mapToCurve, def) {
  139. if (typeof mapToCurve !== 'function')
  140. throw new Error('mapToCurve() must be defined');
  141. return {
  142. // Encodes byte string to elliptic curve.
  143. // hash_to_curve from https://www.rfc-editor.org/rfc/rfc9380#section-3
  144. hashToCurve(msg, options) {
  145. const u = hash_to_field(msg, 2, { ...def, DST: def.DST, ...options });
  146. const u0 = Point.fromAffine(mapToCurve(u[0]));
  147. const u1 = Point.fromAffine(mapToCurve(u[1]));
  148. const P = u0.add(u1).clearCofactor();
  149. P.assertValidity();
  150. return P;
  151. },
  152. // Encodes byte string to elliptic curve.
  153. // encode_to_curve from https://www.rfc-editor.org/rfc/rfc9380#section-3
  154. encodeToCurve(msg, options) {
  155. const u = hash_to_field(msg, 1, { ...def, DST: def.encodeDST, ...options });
  156. const P = Point.fromAffine(mapToCurve(u[0])).clearCofactor();
  157. P.assertValidity();
  158. return P;
  159. },
  160. // Same as encodeToCurve, but without hash
  161. mapToCurve(scalars) {
  162. if (!Array.isArray(scalars))
  163. throw new Error('mapToCurve: expected array of bigints');
  164. for (const i of scalars)
  165. if (typeof i !== 'bigint')
  166. throw new Error(`mapToCurve: expected array of bigints, got ${i} in array`);
  167. const P = Point.fromAffine(mapToCurve(scalars)).clearCofactor();
  168. P.assertValidity();
  169. return P;
  170. },
  171. };
  172. }
  173. //# sourceMappingURL=hash-to-curve.js.map