monero_generators/
hash_to_point.rs

1use subtle::ConditionallySelectable;
2
3use group::ff::{Field, PrimeField};
4use curve25519_dalek::edwards::EdwardsPoint;
5use dalek_ff_group::FieldElement;
6
7use crate::keccak256;
8
9/// Monero's `hash_to_ec` function.
10///
11/// This achieves parity with https://github.com/monero-project/monero
12///   /blob/389e3ba1df4a6df4c8f9d116aa239d4c00f5bc78/src/crypto/crypto.cpp#L611, inlining the
13/// `ge_fromfe_frombytes_vartime` function (https://github.com/monero-project/monero
14///   /blob/389e3ba1df4a6df4c8f9d116aa239d4c00f5bc78/src/crypto/crypto-ops.c#L2309). This
15/// implementation runs in constant time.
16///
17/// According to the original authors
18/// (https://web.archive.org/web/20201028121818/https://cryptonote.org/whitepaper.pdf), this would
19/// implement https://arxiv.org/abs/0706.1448. Shen Noether also describes the algorithm
20/// (https://web.getmonero.org/resources/research-lab/pubs/ge_fromfe.pdf), yet without reviewing
21/// its security and in a very straight-forward fashion.
22///
23/// In reality, this implements Elligator 2 as detailed in
24/// "Elligator: Elliptic-curve points indistinguishable from uniform random strings"
25/// (https://eprint.iacr.org/2013/325). Specifically, Section 5.5 details the application of
26/// Elligator 2 to Curve25519, after which the result is mapped to Ed25519.
27///
28/// As this only applies Elligator 2 once, it's limited to a subset of points where a certain
29/// derivative of their `u` coordinates (in Montgomery form) are quadratic residues. It's biased
30/// accordingly.
31pub fn biased_hash_to_point(bytes: [u8; 32]) -> EdwardsPoint {
32  /*
33    Curve25519 is a Montgomery curve with equation `v^2 = u^3 + 486662 u^2 + u`.
34
35    A Curve25519 point `(u, v)` may be mapped to an Ed25519 point `(x, y)` with the map
36    `(sqrt(-(A + 2)) u / v, (u - 1) / (u + 1))`.
37  */
38  use crypto_bigint::U256;
39  const A_U256: U256 = U256::from_u64(486662);
40  const A: FieldElement = FieldElement::from_u256(&A_U256);
41  const MODULUS: U256 = U256::ONE.shl_vartime(255).wrapping_sub(&U256::from_u64(19));
42  const NEGATIVE_A: FieldElement = FieldElement::from_u256(&MODULUS.wrapping_sub(&A_U256));
43
44  // Sample a FieldElement
45  let r = {
46    use crypto_bigint::Encoding;
47    /*
48      This isn't a wide reduction, implying it'd be biased, yet the bias should only be negligible
49      due to the shape of the prime number. All elements within the prime field field have a
50      `2 / 2^{256}` chance of being selected, except for the first 19 which have a `3 / 2^256`
51      chance of being selected. In order for this 'third chance' (the bias) to be relevant, the
52      hash function would have to output a number greater than or equal to:
53
54        0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffda
55
56      which is of negligible probability.
57    */
58    FieldElement::from_u256(&U256::from_le_bytes(keccak256(&bytes)))
59  };
60
61  // Per Section 5.5, take `u = 2`. This is the smallest quadratic non-residue in the field
62  let ur_square = r.square().double();
63
64  /*
65    We know this is non-zero as:
66
67    ```sage
68    p = 2**255 - 19
69    Mod((p - 1) * inverse_mod(2, p), p).is_square() == False
70    ```
71  */
72  let one_plus_ur_square = FieldElement::ONE + ur_square;
73  let one_plus_ur_square_inv = one_plus_ur_square
74    .invert()
75    .expect("unreachable modulo 2^{255} - 19 due to how `ur_square` was chosen");
76  let upsilon = NEGATIVE_A * one_plus_ur_square_inv;
77  /*
78    Quoting section 5.5,
79    "then \epsilon = 1 and x = \upsilon. Otherwise \epsilon = -1, x = \upsilon u r^2"
80
81    Whereas in the specification present in Section 5.2, the expansion of the `u` coordinate when
82    `\epsilon = -1` is `-\upsilon - A`. Per Section 5.2, in the "Second case",
83    `= -\upsilon - A = \upsilon u r^2`. These two values are equivalent, yet the negation and
84    subtract outperform a multiplication.
85  */
86  let other_candidate = -upsilon - A;
87
88  /*
89    Check if `\upsilon` is a valid `u` coordinate by checking for a solution for the square root
90    of `\upsilon^3 + A \upsilon^2 + \upsilon`.
91  */
92  let epsilon = (((upsilon + A) * upsilon.square()) + upsilon).sqrt().is_some();
93  let u = <FieldElement>::conditional_select(&other_candidate, &upsilon, epsilon);
94
95  // Map from Curve25519 to Ed25519
96  /*
97    Elligator 2's specification in section 5.2 says to choose the negative square root as the
98    `v` coordinate if `\upsilon` was chosen (as signaled by `\epsilon = 1`). The following
99    chooses the odd `y` coordinate if `\upsilon` was chosen, which is functionally equivalent.
100  */
101  let res = curve25519_dalek::MontgomeryPoint(u.to_repr())
102    .to_edwards(epsilon.unwrap_u8())
103    .expect("neither Elligator 2 candidate was a square");
104
105  // Ensure this point lies within the prime-order subgroup
106  res.mul_by_cofactor()
107}
monero_generators/hash_to_point.rs

monero_generators/
hash_to_point.rs
