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
123

//! Traits for handling hash to curve.

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

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

    /// 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::hash2curve::ExpandMsgXmd
    /// [`ExpandMsgXof`]: crate::hash2curve::ExpandMsgXof
    fn hash_from_bytes<'a, X: ExpandMsg<'a>>(
        msgs: &[&[u8]],
        dsts: &'a [&'a [u8]],
    ) -> Result<ProjectivePoint<Self>> {
        let mut u = [Self::FieldElement::default(), Self::FieldElement::default()];
        hash_to_field::<X, _>(msgs, dsts, &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().into() + 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::hash2curve::ExpandMsgXmd
    /// [`ExpandMsgXof`]: crate::hash2curve::ExpandMsgXof
    fn encode_from_bytes<'a, X: ExpandMsg<'a>>(
        msgs: &[&[u8]],
        dsts: &'a [&'a [u8]],
    ) -> Result<ProjectivePoint<Self>> {
        let mut u = [Self::FieldElement::default()];
        hash_to_field::<X, _>(msgs, dsts, &mut u)?;
        let q0 = u[0].map_to_curve();
        Ok(q0.clear_cofactor().into())
    }

    /// 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::hash2curve::ExpandMsgXmd
    /// [`ExpandMsgXof`]: crate::hash2curve::ExpandMsgXof
    fn hash_to_scalar<'a, X: ExpandMsg<'a>>(
        msgs: &[&[u8]],
        dsts: &'a [&'a [u8]],
    ) -> Result<Self::Scalar>
    where
        Self::Scalar: FromOkm,
    {
        let mut u = [Self::Scalar::default()];
        hash_to_field::<X, _>(msgs, dsts, &mut u)?;
        Ok(u[0])
    }
}