pasta_curves/
hashtocurve.rs

Help
1//! This module implements "simplified SWU" hashing to short Weierstrass curves
2//! with a = 0.
3
4use ff::{Field, FromUniformBytes, PrimeField};
5use static_assertions::const_assert;
6use subtle::ConstantTimeEq;
7
8use crate::arithmetic::CurveExt;
9
10/// Hashes over a message and writes the output to all of `buf`.
11pub fn hash_to_field<F: FromUniformBytes<64>>(
12    curve_id: &str,
13    domain_prefix: &str,
14    message: &[u8],
15    buf: &mut [F; 2],
16) {
17    assert!(domain_prefix.len() < 256);
18    assert!((22 + curve_id.len() + domain_prefix.len()) < 256);
19
20    // Assume that the field size is 32 bytes and k is 256, where k is defined in
21    // <https://www.ietf.org/archive/id/draft-irtf-cfrg-hash-to-curve-10.html#name-security-considerations-3>.
22    const CHUNKLEN: usize = 64;
23    const_assert!(CHUNKLEN * 2 < 256);
24
25    // Input block size of BLAKE2b.
26    const R_IN_BYTES: usize = 128;
27
28    let personal = [0u8; 16];
29    let empty_hasher = blake2b_simd::Params::new()
30        .hash_length(CHUNKLEN)
31        .personal(&personal)
32        .to_state();
33
34    let b_0 = empty_hasher
35        .clone()
36        .update(&[0; R_IN_BYTES])
37        .update(message)
38        .update(&[0, (CHUNKLEN * 2) as u8, 0])
39        .update(domain_prefix.as_bytes())
40        .update(b"-")
41        .update(curve_id.as_bytes())
42        .update(b"_XMD:BLAKE2b_SSWU_RO_")
43        .update(&[(22 + curve_id.len() + domain_prefix.len()) as u8])
44        .finalize();
45
46    let b_1 = empty_hasher
47        .clone()
48        .update(b_0.as_array())
49        .update(&[1])
50        .update(domain_prefix.as_bytes())
51        .update(b"-")
52        .update(curve_id.as_bytes())
53        .update(b"_XMD:BLAKE2b_SSWU_RO_")
54        .update(&[(22 + curve_id.len() + domain_prefix.len()) as u8])
55        .finalize();
56
57    let b_2 = {
58        let mut empty_hasher = empty_hasher;
59        for (l, r) in b_0.as_array().iter().zip(b_1.as_array().iter()) {
60            empty_hasher.update(&[*l ^ *r]);
61        }
62        empty_hasher
63            .update(&[2])
64            .update(domain_prefix.as_bytes())
65            .update(b"-")
66            .update(curve_id.as_bytes())
67            .update(b"_XMD:BLAKE2b_SSWU_RO_")
68            .update(&[(22 + curve_id.len() + domain_prefix.len()) as u8])
69            .finalize()
70    };
71
72    for (big, buf) in [b_1, b_2].iter().zip(buf.iter_mut()) {
73        let mut little = [0u8; CHUNKLEN];
74        little.copy_from_slice(big.as_array());
75        little.reverse();
76        *buf = F::from_uniform_bytes(&little);
77    }
78}
79
80/// Implements a degree 3 isogeny map.
81pub fn iso_map<F: Field, C: CurveExt<Base = F>, I: CurveExt<Base = F>>(
82    p: &I,
83    iso: &[C::Base; 13],
84) -> C {
85    // The input and output are in Jacobian coordinates, using the method
86    // in "Avoiding inversions" [WB2019, section 4.3].
87
88    let (x, y, z) = p.jacobian_coordinates();
89
90    let z2 = z.square();
91    let z3 = z2 * z;
92    let z4 = z2.square();
93    let z6 = z3.square();
94
95    let num_x = ((iso[0] * x + iso[1] * z2) * x + iso[2] * z4) * x + iso[3] * z6;
96    let div_x = (z2 * x + iso[4] * z4) * x + iso[5] * z6;
97
98    let num_y = (((iso[6] * x + iso[7] * z2) * x + iso[8] * z4) * x + iso[9] * z6) * y;
99    let div_y = (((x + iso[10] * z2) * x + iso[11] * z4) * x + iso[12] * z6) * z3;
100
101    let zo = div_x * div_y;
102    let xo = num_x * div_y * zo;
103    let yo = num_y * div_x * zo.square();
104
105    C::new_jacobian(xo, yo, zo).unwrap()
106}
107
108#[allow(clippy::many_single_char_names)]
109pub fn map_to_curve_simple_swu<F: PrimeField, C: CurveExt<Base = F>, I: CurveExt<Base = F>>(
110    u: &F,
111    theta: F,
112    z: F,
113) -> I {
114    // 1. tv1 = inv0(Z^2 * u^4 + Z * u^2)
115    // 2. x1 = (-B / A) * (1 + tv1)
116    // 3. If tv1 == 0, set x1 = B / (Z * A)
117    // 4. gx1 = x1^3 + A * x1 + B
118    //
119    // We use the "Avoiding inversions" optimization in [WB2019, section 4.2]
120    // (not to be confused with section 4.3):
121    //
122    //   here       [WB2019]
123    //   -------    ---------------------------------
124    //   Z          ξ
125    //   u          t
126    //   Z * u^2    ξ * t^2 (called u, confusingly)
127    //   x1         X_0(t)
128    //   x2         X_1(t)
129    //   gx1        g(X_0(t))
130    //   gx2        g(X_1(t))
131    //
132    // Using the "here" names:
133    //    x1 = num_x1/div      = [B*(Z^2 * u^4 + Z * u^2 + 1)] / [-A*(Z^2 * u^4 + Z * u^2]
134    //   gx1 = num_gx1/div_gx1 = [num_x1^3 + A * num_x1 * div^2 + B * div^3] / div^3
135
136    let a = I::a();
137    let b = I::b();
138    let z_u2 = z * u.square();
139    let ta = z_u2.square() + z_u2;
140    let num_x1 = b * (ta + F::ONE);
141    let div = a * F::conditional_select(&-ta, &z, ta.is_zero());
142    let num2_x1 = num_x1.square();
143    let div2 = div.square();
144    let div3 = div2 * div;
145    let num_gx1 = (num2_x1 + a * div2) * num_x1 + b * div3;
146
147    // 5. x2 = Z * u^2 * x1
148    let num_x2 = z_u2 * num_x1; // same div
149
150    // 6. gx2 = x2^3 + A * x2 + B  [optimized out; see below]
151    // 7. If is_square(gx1), set x = x1 and y = sqrt(gx1)
152    // 8. Else set x = x2 and y = sqrt(gx2)
153    let (gx1_square, y1) = F::sqrt_ratio(&num_gx1, &div3);
154
155    // This magic also comes from a generalization of [WB2019, section 4.2].
156    //
157    // The Sarkar square root algorithm with input s gives us a square root of
158    // h * s for free when s is not square, where h is a fixed nonsquare.
159    // In our implementation, h = ROOT_OF_UNITY.
160    // We know that Z / h is a square since both Z and h are
161    // nonsquares. Precompute theta as a square root of Z / ROOT_OF_UNITY.
162    //
163    // We have gx2 = g(Z * u^2 * x1) = Z^3 * u^6 * gx1
164    //                               = (Z * u^3)^2 * (Z/h * h * gx1)
165    //                               = (Z * theta * u^3)^2 * (h * gx1)
166    //
167    // When gx1 is not square, y1 is a square root of h * gx1, and so Z * theta * u^3 * y1
168    // is a square root of gx2. Note that we don't actually need to compute gx2.
169
170    let y2 = theta * z_u2 * u * y1;
171    let num_x = F::conditional_select(&num_x2, &num_x1, gx1_square);
172    let y = F::conditional_select(&y2, &y1, gx1_square);
173
174    // 9. If sgn0(u) != sgn0(y), set y = -y
175    let y = F::conditional_select(&(-y), &y, u.is_odd().ct_eq(&y.is_odd()));
176
177    I::new_jacobian(num_x * div, y * div3, div).unwrap()
178}
pasta_curves/hashtocurve.rs

pasta_curves/
hashtocurve.rs
