179 lines
6.0 KiB
Rust
179 lines
6.0 KiB
Rust
//! This module implements "simplified SWU" hashing to short Weierstrass curves
|
|
//! with a = 0.
|
|
|
|
use ff::{Field, FromUniformBytes, PrimeField};
|
|
use static_assertions::const_assert;
|
|
use subtle::ConstantTimeEq;
|
|
|
|
use crate::arithmetic::CurveExt;
|
|
|
|
/// Hashes over a message and writes the output to all of `buf`.
|
|
pub fn hash_to_field<F: FromUniformBytes<64>>(
|
|
curve_id: &str,
|
|
domain_prefix: &str,
|
|
message: &[u8],
|
|
buf: &mut [F; 2],
|
|
) {
|
|
assert!(domain_prefix.len() < 256);
|
|
assert!((22 + curve_id.len() + domain_prefix.len()) < 256);
|
|
|
|
// Assume that the field size is 32 bytes and k is 256, where k is defined in
|
|
// <https://www.ietf.org/archive/id/draft-irtf-cfrg-hash-to-curve-10.html#name-security-considerations-3>.
|
|
const CHUNKLEN: usize = 64;
|
|
const_assert!(CHUNKLEN * 2 < 256);
|
|
|
|
// Input block size of BLAKE2b.
|
|
const R_IN_BYTES: usize = 128;
|
|
|
|
let personal = [0u8; 16];
|
|
let empty_hasher = blake2b_simd::Params::new()
|
|
.hash_length(CHUNKLEN)
|
|
.personal(&personal)
|
|
.to_state();
|
|
|
|
let b_0 = empty_hasher
|
|
.clone()
|
|
.update(&[0; R_IN_BYTES])
|
|
.update(message)
|
|
.update(&[0, (CHUNKLEN * 2) as u8, 0])
|
|
.update(domain_prefix.as_bytes())
|
|
.update(b"-")
|
|
.update(curve_id.as_bytes())
|
|
.update(b"_XMD:BLAKE2b_SSWU_RO_")
|
|
.update(&[(22 + curve_id.len() + domain_prefix.len()) as u8])
|
|
.finalize();
|
|
|
|
let b_1 = empty_hasher
|
|
.clone()
|
|
.update(b_0.as_array())
|
|
.update(&[1])
|
|
.update(domain_prefix.as_bytes())
|
|
.update(b"-")
|
|
.update(curve_id.as_bytes())
|
|
.update(b"_XMD:BLAKE2b_SSWU_RO_")
|
|
.update(&[(22 + curve_id.len() + domain_prefix.len()) as u8])
|
|
.finalize();
|
|
|
|
let b_2 = {
|
|
let mut empty_hasher = empty_hasher;
|
|
for (l, r) in b_0.as_array().iter().zip(b_1.as_array().iter()) {
|
|
empty_hasher.update(&[*l ^ *r]);
|
|
}
|
|
empty_hasher
|
|
.update(&[2])
|
|
.update(domain_prefix.as_bytes())
|
|
.update(b"-")
|
|
.update(curve_id.as_bytes())
|
|
.update(b"_XMD:BLAKE2b_SSWU_RO_")
|
|
.update(&[(22 + curve_id.len() + domain_prefix.len()) as u8])
|
|
.finalize()
|
|
};
|
|
|
|
for (big, buf) in [b_1, b_2].iter().zip(buf.iter_mut()) {
|
|
let mut little = [0u8; CHUNKLEN];
|
|
little.copy_from_slice(big.as_array());
|
|
little.reverse();
|
|
*buf = F::from_uniform_bytes(&little);
|
|
}
|
|
}
|
|
|
|
/// Implements a degree 3 isogeny map.
|
|
pub fn iso_map<F: Field, C: CurveExt<Base = F>, I: CurveExt<Base = F>>(
|
|
p: &I,
|
|
iso: &[C::Base; 13],
|
|
) -> C {
|
|
// The input and output are in Jacobian coordinates, using the method
|
|
// in "Avoiding inversions" [WB2019, section 4.3].
|
|
|
|
let (x, y, z) = p.jacobian_coordinates();
|
|
|
|
let z2 = z.square();
|
|
let z3 = z2 * z;
|
|
let z4 = z2.square();
|
|
let z6 = z3.square();
|
|
|
|
let num_x = ((iso[0] * x + iso[1] * z2) * x + iso[2] * z4) * x + iso[3] * z6;
|
|
let div_x = (z2 * x + iso[4] * z4) * x + iso[5] * z6;
|
|
|
|
let num_y = (((iso[6] * x + iso[7] * z2) * x + iso[8] * z4) * x + iso[9] * z6) * y;
|
|
let div_y = (((x + iso[10] * z2) * x + iso[11] * z4) * x + iso[12] * z6) * z3;
|
|
|
|
let zo = div_x * div_y;
|
|
let xo = num_x * div_y * zo;
|
|
let yo = num_y * div_x * zo.square();
|
|
|
|
C::new_jacobian(xo, yo, zo).unwrap()
|
|
}
|
|
|
|
#[allow(clippy::many_single_char_names)]
|
|
pub fn map_to_curve_simple_swu<F: PrimeField, C: CurveExt<Base = F>, I: CurveExt<Base = F>>(
|
|
u: &F,
|
|
theta: F,
|
|
z: F,
|
|
) -> I {
|
|
// 1. tv1 = inv0(Z^2 * u^4 + Z * u^2)
|
|
// 2. x1 = (-B / A) * (1 + tv1)
|
|
// 3. If tv1 == 0, set x1 = B / (Z * A)
|
|
// 4. gx1 = x1^3 + A * x1 + B
|
|
//
|
|
// We use the "Avoiding inversions" optimization in [WB2019, section 4.2]
|
|
// (not to be confused with section 4.3):
|
|
//
|
|
// here [WB2019]
|
|
// ------- ---------------------------------
|
|
// Z ξ
|
|
// u t
|
|
// Z * u^2 ξ * t^2 (called u, confusingly)
|
|
// x1 X_0(t)
|
|
// x2 X_1(t)
|
|
// gx1 g(X_0(t))
|
|
// gx2 g(X_1(t))
|
|
//
|
|
// Using the "here" names:
|
|
// x1 = num_x1/div = [B*(Z^2 * u^4 + Z * u^2 + 1)] / [-A*(Z^2 * u^4 + Z * u^2]
|
|
// gx1 = num_gx1/div_gx1 = [num_x1^3 + A * num_x1 * div^2 + B * div^3] / div^3
|
|
|
|
let a = I::a();
|
|
let b = I::b();
|
|
let z_u2 = z * u.square();
|
|
let ta = z_u2.square() + z_u2;
|
|
let num_x1 = b * (ta + F::ONE);
|
|
let div = a * F::conditional_select(&-ta, &z, ta.is_zero());
|
|
let num2_x1 = num_x1.square();
|
|
let div2 = div.square();
|
|
let div3 = div2 * div;
|
|
let num_gx1 = (num2_x1 + a * div2) * num_x1 + b * div3;
|
|
|
|
// 5. x2 = Z * u^2 * x1
|
|
let num_x2 = z_u2 * num_x1; // same div
|
|
|
|
// 6. gx2 = x2^3 + A * x2 + B [optimized out; see below]
|
|
// 7. If is_square(gx1), set x = x1 and y = sqrt(gx1)
|
|
// 8. Else set x = x2 and y = sqrt(gx2)
|
|
let (gx1_square, y1) = F::sqrt_ratio(&num_gx1, &div3);
|
|
|
|
// This magic also comes from a generalization of [WB2019, section 4.2].
|
|
//
|
|
// The Sarkar square root algorithm with input s gives us a square root of
|
|
// h * s for free when s is not square, where h is a fixed nonsquare.
|
|
// In our implementation, h = ROOT_OF_UNITY.
|
|
// We know that Z / h is a square since both Z and h are
|
|
// nonsquares. Precompute theta as a square root of Z / ROOT_OF_UNITY.
|
|
//
|
|
// We have gx2 = g(Z * u^2 * x1) = Z^3 * u^6 * gx1
|
|
// = (Z * u^3)^2 * (Z/h * h * gx1)
|
|
// = (Z * theta * u^3)^2 * (h * gx1)
|
|
//
|
|
// When gx1 is not square, y1 is a square root of h * gx1, and so Z * theta * u^3 * y1
|
|
// is a square root of gx2. Note that we don't actually need to compute gx2.
|
|
|
|
let y2 = theta * z_u2 * u * y1;
|
|
let num_x = F::conditional_select(&num_x2, &num_x1, gx1_square);
|
|
let y = F::conditional_select(&y2, &y1, gx1_square);
|
|
|
|
// 9. If sgn0(u) != sgn0(y), set y = -y
|
|
let y = F::conditional_select(&(-y), &y, u.is_odd().ct_eq(&y.is_odd()));
|
|
|
|
I::new_jacobian(num_x * div, y * div3, div).unwrap()
|
|
}
|