`bignp256`: SWU

[makavity]

Hello.
I'm implementing the ⁠bake-swu protocol according to STB 34.101.66-2014
The algorithm uses ⁠belt-kwp (Belt Key Wrap) as the expand function instead of a traditional hash function. This means I cannot use ⁠OsswuMap directly, but the algorithm itself is compatible with the ⁠map2curve interface.

pub struct BeltKwpExpander {
    /// Output buffer containing the 48-byte result of belt-keywrap
    buf: [u8; 48],
    /// Current position in the buffer for reading
    offset: usize,
}

impl Expander for BeltKwpExpander { ... }
impl ExpandMsg<'_> for BeltKwpExpander { ... }

impl FieldElement {
    /// Reduces a 384-bit (48-byte) value to a field element modulo p.
    pub(crate) fn reduce_bytes_to_field(bytes: &GenericArray<u8, U48>) -> Self {
        let value = U384::from_le_slice(bytes);

        let modulus = {
            let mut modulus_bytes = [0u8; 48];
            modulus_bytes[..32].copy_from_slice(&MODULUS.to_le_bytes());
            U384::from_le_bytes(modulus_bytes)
        };

        let reduced = value.const_rem(&modulus).0;
        let reduced_bytes = reduced.to_le_bytes();
        let result = U256::from_le_slice(&reduced_bytes[..32]);

        Self::from_uint_unchecked(result)
    }

    /// Simplified SWU map from field element to curve point.
    ///
    /// Implements the bake-swu algorithm from STB 34.101.66-2014, section 6.2.3.
    /// Input `self` is the field element s obtained after belt-keywrap preprocessing.
    #[allow(clippy::arithmetic_side_effects)]
    pub(crate) fn swu(&self) -> AffinePoint {
        // Step 3: t ← -s² mod p
        let t = self.square().neg();
        let t_squared = t.square();

        // Step 4: Compute numerator = (1 + t + t²) and denominator = a(t + t²)
        let num = FieldElement::ONE + t + t_squared;
        let den = BignP256::EQUATION_A * (t + t_squared);

        // Step 4: x₁ ← -b(1 + t + t²)(a(t + t²))^(-1) mod p
        let x1 = -BignP256::EQUATION_B * num * den.invert().unwrap();

        // Step 5: x₂ ← t·x₁ mod p
        let x2 = t * x1;

        // Step 6: y ← (x₁³ + a·x₁ + b) mod p
        let gx1 = x1.cube() + BignP256::EQUATION_A * x1 + BignP256::EQUATION_B;

        // Steps 7-8: Compute square root and check if gx1 is a quadratic residue
        let (is_square, y1) = gx1.sqrt_alt();

        // Step 7: s³·y mod p (for alternative case)
        let y2 = self.cube() * y1;

        // Step 9: Constant-time selection of final coordinates
        let x = FieldElement::conditional_select(&x2, &x1, is_square);
        let y = FieldElement::conditional_select(&y2, &y1, is_square);

        // Step 10: Return W as AffinePoint
        let point = EncodedPoint::from_affine_coordinates(&x.to_bytes(), &y.to_bytes(), false);
        AffinePoint::from_encoded_point(&point).unwrap()
    }
}

impl MapToCurve for FieldElement {
    type Output = ProjectivePoint;

    fn map_to_curve(&self) -> Self::Output {
        self.swu().into()
    }
}

impl FromOkm for FieldElement {
    type Length = U48;

    fn from_okm(data: &GenericArray<u8, Self::Length>) -> Self {
        Self::reduce_bytes_to_field(data)
    }
}

impl GroupDigest for BignP256 {
    type FieldElement = FieldElement;
}

impl BignP256 {
    pub fn hash_secret_to_curve(secret: &[u8]) -> elliptic_curve::Result<ProjectivePoint> {
        use crate::arithmetic::expand::BeltKwpExpander;
        use elliptic_curve::{hash2curve::ExpandMsg, hash2curve::Expander};

        // 1. H ← belt-keywrap(X, 0^128, 0^256)
        // Expand input secret to 48 bytes (384 bits) using Belt-KWP
        let mut expander = BeltKwpExpander::expand_message(&[secret], &[], 48)?;

        // 2. s ← H mod p
        // Extract 48-byte output and reduce modulo field prime
        let mut okm = GenericArray::<u8, U48>::default();
        expander.fill_bytes(&mut okm);
        let field_elem = FieldElement::from_okm(&okm);

        // 3-10. Apply simplified SWU mapping
        let point = field_elem.map_to_curve();

        Ok(point)
    }
}

It is the backport on 0.13 version, for example.

[tarcieri]

cc @daxpedda

@makavity did you have a question? This seems fine to me at a high level. It's just incompatible with OsswuMap and I don't think there's anything we can really do about that.

[makavity]

I just wanted to check if this is correct before the PR. If the approach is ok, I'll prepare and create the PR. Thanks for the feedback, @tarcieri :)