logo
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

//! Traits for handling hash to curve.

use super::MapToCurve;
use crate::{
    hash2field::{hash_to_field, ExpandMsg, FromOkm},
    ProjectiveArithmetic, Result,
};
use group::cofactor::CofactorGroup;

/// Adds hashing arbitrary byte sequences to a valid group element
pub trait GroupDigest: ProjectiveArithmetic<ProjectivePoint = Self::Output> {
    /// The field element representation for a group value with multiple elements
    type FieldElement: FromOkm + MapToCurve<Output = Self::Output> + Default + Copy;
    /// The resulting group element
    type Output: CofactorGroup<Subgroup = Self::Output>;

    /// Computes the hash to curve routine.
    ///
    /// From <https://www.ietf.org/archive/id/draft-irtf-cfrg-hash-to-curve-13.html>:
    ///
    /// > Uniform encoding from byte strings to points in G.
    /// > That is, the distribution of its output is statistically close
    /// > to uniform in G.
    /// > This function is suitable for most applications requiring a random
    /// > oracle returning points in G assuming a cryptographically secure
    /// > hash function is used.
    ///
    /// # Examples
    ///
    /// ## Using a fixed size hash function
    ///
    /// ```ignore
    /// let pt = ProjectivePoint::hash_from_bytes::<ExpandMsgXmd<sha2::Sha256>>(b"test data", b"CURVE_XMD:SHA-256_SSWU_RO_");
    /// ```
    ///
    /// ## Using an extendable output function
    ///
    /// ```ignore
    /// let pt = ProjectivePoint::hash_from_bytes::<ExpandMsgXof<sha3::Shake256>>(b"test data", b"CURVE_XOF:SHAKE-256_SSWU_RO_");
    /// ```
    ///
    /// # Errors
    /// See implementors of [`ExpandMsg`] for errors:
    /// - [`ExpandMsgXmd`]
    /// - [`ExpandMsgXof`]
    ///
    /// `len_in_bytes = <Self::FieldElement as FromOkm>::Length * 2`
    ///
    /// [`ExpandMsgXmd`]: crate::hash2field::ExpandMsgXmd
    /// [`ExpandMsgXof`]: crate::hash2field::ExpandMsgXof
    fn hash_from_bytes<'a, X: ExpandMsg<'a>>(
        msgs: &[&[u8]],
        dst: &'a [u8],
    ) -> Result<Self::Output> {
        let mut u = [Self::FieldElement::default(), Self::FieldElement::default()];
        hash_to_field::<X, _>(msgs, dst, &mut u)?;
        let q0 = u[0].map_to_curve();
        let q1 = u[1].map_to_curve();
        // Ideally we could add and then clear cofactor once
        // thus saving a call but the field elements may not
        // add properly due to the underlying implementation
        // which could result in an incorrect subgroup.
        // This is caused curve coefficients being different than
        // what is usually implemented.
        // FieldElement expects the `a` and `b` to be the original values
        // isogenies are different with curves like k256 and bls12-381.
        // This problem doesn't manifest for curves with no isogeny like p256.
        // For k256 and p256 clear_cofactor doesn't do anything anyway so it will be a no-op.
        Ok(q0.clear_cofactor() + q1.clear_cofactor())
    }

    /// Computes the encode to curve routine.
    ///
    /// From <https://www.ietf.org/archive/id/draft-irtf-cfrg-hash-to-curve-13.html>:
    ///
    /// > Nonuniform encoding from byte strings to
    /// > points in G. That is, the distribution of its output is not
    /// > uniformly random in G: the set of possible outputs of
    /// > encode_to_curve is only a fraction of the points in G, and some
    /// > points in this set are more likely to be output than others.
    ///
    /// # Errors
    /// See implementors of [`ExpandMsg`] for errors:
    /// - [`ExpandMsgXmd`]
    /// - [`ExpandMsgXof`]
    ///
    /// `len_in_bytes = <Self::FieldElement as FromOkm>::Length`
    ///
    /// [`ExpandMsgXmd`]: crate::hash2field::ExpandMsgXmd
    /// [`ExpandMsgXof`]: crate::hash2field::ExpandMsgXof
    fn encode_from_bytes<'a, X: ExpandMsg<'a>>(
        msgs: &[&[u8]],
        dst: &'a [u8],
    ) -> Result<Self::Output> {
        let mut u = [Self::FieldElement::default()];
        hash_to_field::<X, _>(msgs, dst, &mut u)?;
        let q0 = u[0].map_to_curve();
        Ok(q0.clear_cofactor())
    }

    /// Computes the hash to field routine according to
    /// <https://www.ietf.org/archive/id/draft-irtf-cfrg-hash-to-curve-13.html#section-5>
    /// and returns a scalar.
    ///
    /// # Errors
    /// See implementors of [`ExpandMsg`] for errors:
    /// - [`ExpandMsgXmd`]
    /// - [`ExpandMsgXof`]
    ///
    /// `len_in_bytes = <Self::Scalar as FromOkm>::Length`
    ///
    /// [`ExpandMsgXmd`]: crate::hash2field::ExpandMsgXmd
    /// [`ExpandMsgXof`]: crate::hash2field::ExpandMsgXof
    fn hash_to_scalar<'a, X: ExpandMsg<'a>>(msgs: &[&[u8]], dst: &'a [u8]) -> Result<Self::Scalar>
    where
        Self::Scalar: FromOkm,
    {
        let mut u = [Self::Scalar::default()];
        hash_to_field::<X, _>(msgs, dst, &mut u)?;
        Ok(u[0])
    }
}