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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
//! Traits and implementations for prime-order groups in which
//! the [decisional Diffie–Hellman][DDH] (DDH), [computational Diffie–Hellman][CDH] (CDH)
//! and [discrete log][DLP] (DL) problems are believed to be hard.
//!
//! (Decisional Diffie–Hellman assumption is considered stronger than both CDH and DL,
//! so if DDH is believed to hold for a certain group, it should be good to go.)
//!
//! Such groups can be applied for ElGamal encryption and other cryptographic protocols
//! from this crate.
//!
//! [DDH]: https://en.wikipedia.org/wiki/Decisional_Diffie%E2%80%93Hellman_assumption
//! [CDH]: https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_problem
//! [DLP]: https://en.wikipedia.org/wiki/Discrete_logarithm

use merlin::Transcript;
use rand_chacha::ChaChaRng;
use rand_core::{CryptoRng, RngCore, SeedableRng};
use zeroize::Zeroize;

use core::{fmt, ops, str};

#[cfg(any(feature = "curve25519-dalek", feature = "curve25519-dalek-ng"))]
mod curve25519;
mod generic;
#[cfg(any(feature = "curve25519-dalek", feature = "curve25519-dalek-ng"))]
mod ristretto;

pub use self::generic::Generic;
#[cfg(any(feature = "curve25519-dalek", feature = "curve25519-dalek-ng"))]
pub use self::{curve25519::Curve25519Subgroup, ristretto::Ristretto};

/// Provides an arbitrary number of random bytes.
///
/// Unlike [`RngCore::fill_bytes()`], a single provider can only be used once.
pub struct RandomBytesProvider<'a> {
    transcript: &'a mut Transcript,
    label: &'static [u8],
}

impl fmt::Debug for RandomBytesProvider<'_> {
    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
        let label = str::from_utf8(self.label).unwrap_or("(non-utf8 label)");
        formatter
            .debug_struct("RandomBytesProvider")
            .field("label", &label)
            .finish()
    }
}

impl<'a> RandomBytesProvider<'a> {
    pub(crate) fn new(transcript: &'a mut Transcript, label: &'static [u8]) -> Self {
        Self { transcript, label }
    }

    /// Writes random bytes into the specified buffer. As follows from the signature, this method
    /// can only be called once for a provider instance.
    pub fn fill_bytes(self, dest: &mut [u8]) {
        self.transcript.challenge_bytes(self.label, dest);
    }
}

/// Helper trait for [`Group`] that describes operations on group scalars.
pub trait ScalarOps {
    /// Scalar type. As per [`Group`] contract, scalars must form a prime field.
    /// Arithmetic operations on scalars requested here must be constant-time.
    type Scalar: Copy
        + Default
        + From<u64>
        + From<Self::Scalar> // `PublicKey::encrypt()` doesn't work without this
        + ops::Neg<Output = Self::Scalar>
        + ops::Add<Output = Self::Scalar>
        + for<'a> ops::Add<&'a Self::Scalar, Output = Self::Scalar>
        + ops::Sub<Output = Self::Scalar>
        + ops::Mul<Output = Self::Scalar>
        + for<'a> ops::Mul<&'a Self::Scalar, Output = Self::Scalar>
        + PartialEq
        + Zeroize
        + fmt::Debug;

    /// Byte size of a serialized [`Self::Scalar`].
    const SCALAR_SIZE: usize;

    /// Generates a random scalar based on the provided CSPRNG. This operation
    /// must be constant-time.
    fn generate_scalar<R: CryptoRng + RngCore>(rng: &mut R) -> Self::Scalar;

    /// Generates a scalar from a `source` of random bytes. This operation must be constant-time.
    /// The `source` is guaranteed to return any necessary number of bytes.
    ///
    /// # Default implementation
    ///
    /// 1. Create a [ChaCha RNG] using 32 bytes read from `source` as the seed.
    /// 2. Call [`Self::generate_scalar()`] with the created RNG.
    ///
    /// [ChaCha RNG]: https://docs.rs/rand_chacha/
    fn scalar_from_random_bytes(source: RandomBytesProvider<'_>) -> Self::Scalar {
        let mut rng_seed = <ChaChaRng as SeedableRng>::Seed::default();
        source.fill_bytes(&mut rng_seed);
        let mut rng = ChaChaRng::from_seed(rng_seed);
        Self::generate_scalar(&mut rng)
    }

    /// Inverts the `scalar`, which is guaranteed to be non-zero. This operation does not
    /// need to be constant-time.
    fn invert_scalar(scalar: Self::Scalar) -> Self::Scalar;

    /// Inverts scalars in a batch. This operation does not need to be constant-time.
    ///
    /// # Default implementation
    ///
    /// Inverts every scalar successively.
    fn invert_scalars(scalars: &mut [Self::Scalar]) {
        for scalar in scalars {
            *scalar = Self::invert_scalar(*scalar);
        }
    }

    /// Serializes the scalar into the provided `buffer`, which is guaranteed to have length
    /// [`Self::SCALAR_SIZE`].
    fn serialize_scalar(scalar: &Self::Scalar, buffer: &mut [u8]);

    /// Deserializes the scalar from `buffer`, which is guaranteed to have length
    /// [`Self::SCALAR_SIZE`]. This method returns `None` if the buffer
    /// does not correspond to a representation of a valid scalar.
    fn deserialize_scalar(buffer: &[u8]) -> Option<Self::Scalar>;
}

/// Helper trait for [`Group`] that describes operations on group elements (i.e., EC points
/// for elliptic curve groups).
pub trait ElementOps: ScalarOps {
    /// Element of the group. Arithmetic operations requested here (addition among
    /// elements and multiplication by a `Scalar`) must be constant-time.
    type Element: Copy
        + ops::Add<Output = Self::Element>
        + ops::Sub<Output = Self::Element>
        + ops::Neg<Output = Self::Element>
        + for<'a> ops::Mul<&'a Self::Scalar, Output = Self::Element>
        + PartialEq
        + fmt::Debug;

    /// Byte size of a serialized [`Self::Element`].
    const ELEMENT_SIZE: usize;

    /// Returns the identity of the group (aka point at infinity for EC groups).
    fn identity() -> Self::Element;

    /// Checks if the specified element is the identity.
    fn is_identity(element: &Self::Element) -> bool;

    /// Returns the agreed-upon generator of the group.
    fn generator() -> Self::Element;

    /// Serializes `element` into the provided `buffer`, which is guaranteed to have length
    /// [`Self::ELEMENT_SIZE`].
    fn serialize_element(element: &Self::Element, output: &mut [u8]);

    /// Deserializes an element from `buffer`, which is guaranteed to have length
    /// [`Self::ELEMENT_SIZE`]. This method returns `None` if the buffer
    /// does not correspond to a representation of a valid scalar.
    fn deserialize_element(buffer: &[u8]) -> Option<Self::Element>;
}

/// Prime-order group in which the discrete log problem and decisional / computational
/// Diffie–Hellman problems are believed to be hard.
///
/// Groups conforming to this trait can be used for ElGamal encryption and other
/// cryptographic protocols defined in this crate.
///
/// This crate provides the following implementations of this trait:
///
/// - [`Curve25519Subgroup`], representation of a prime-order subgroup of Curve25519
///   with the conventionally chosen generator.
/// - [`Ristretto`], a transform of Curve25519 which eliminates its co-factor 8 with the help
///   of the [eponymous technique][ristretto].
/// - [`Generic`] implementation defined in terms of traits from the [`elliptic-curve`] crate.
///   (For example, this means secp256k1 support via the [`k256`] crate.)
///
/// [ristretto]: https://ristretto.group/
/// [`elliptic-curve`]: https://docs.rs/elliptic-curve/
/// [`k256`]: https://docs.rs/k256/
pub trait Group: Copy + ScalarOps + ElementOps + 'static {
    /// Multiplies the provided scalar by [`ElementOps::generator()`]. This operation must be
    /// constant-time.
    ///
    /// # Default implementation
    ///
    /// Implemented using [`Mul`](ops::Mul) (which is constant-time as per the [`ElementOps`]
    /// contract).
    fn mul_generator(k: &Self::Scalar) -> Self::Element {
        Self::generator() * k
    }

    /// Multiplies the provided scalar by [`ElementOps::generator()`].
    /// Unlike [`Self::mul_generator()`], this operation does not need to be constant-time;
    /// thus, it may employ additional optimizations.
    ///
    /// # Default implementation
    ///
    /// Implemented by calling [`Self::mul_generator()`].
    #[inline]
    fn vartime_mul_generator(k: &Self::Scalar) -> Self::Element {
        Self::mul_generator(k)
    }

    /// Multiplies provided `scalars` by `elements`. This operation must be constant-time
    /// w.r.t. the given length of elements.
    ///
    /// # Default implementation
    ///
    /// Implemented by straightforward computations, which are constant-time as per
    /// the [`ElementOps`] contract.
    fn multi_mul<'a, I, J>(scalars: I, elements: J) -> Self::Element
    where
        I: IntoIterator<Item = &'a Self::Scalar>,
        J: IntoIterator<Item = Self::Element>,
    {
        let mut output = Self::identity();
        for (scalar, element) in scalars.into_iter().zip(elements) {
            output = output + element * scalar;
        }
        output
    }

    /// Calculates `k * k_element + r * G`, where `G` is the group generator. This operation
    /// does not need to be constant-time.
    ///
    /// # Default implementation
    ///
    /// Implemented by straightforward arithmetic.
    fn vartime_double_mul_generator(
        k: &Self::Scalar,
        k_element: Self::Element,
        r: &Self::Scalar,
    ) -> Self::Element {
        k_element * k + Self::generator() * r
    }

    /// Multiplies provided `scalars` by `elements`. Unlike [`Self::multi_mul()`],
    /// this operation does not need to be constant-time; thus, it may employ
    /// additional optimizations.
    ///
    /// # Default implementation
    ///
    /// Implemented by calling [`Self::multi_mul()`].
    #[inline]
    fn vartime_multi_mul<'a, I, J>(scalars: I, elements: J) -> Self::Element
    where
        I: IntoIterator<Item = &'a Self::Scalar>,
        J: IntoIterator<Item = Self::Element>,
    {
        Self::multi_mul(scalars, elements)
    }
}