elastic_elgamal/group/
mod.rs

1//! Traits and implementations for prime-order groups in which
2//! the [decisional Diffie–Hellman][DDH] (DDH), [computational Diffie–Hellman][CDH] (CDH)
3//! and [discrete log][DLP] (DL) problems are believed to be hard.
4//!
5//! (Decisional Diffie–Hellman assumption is considered stronger than both CDH and DL,
6//! so if DDH is believed to hold for a certain group, it should be good to go.)
7//!
8//! Such groups can be applied for ElGamal encryption and other cryptographic protocols
9//! from this crate.
10//!
11//! [DDH]: https://en.wikipedia.org/wiki/Decisional_Diffie%E2%80%93Hellman_assumption
12//! [CDH]: https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_problem
13//! [DLP]: https://en.wikipedia.org/wiki/Discrete_logarithm
14
15use core::{fmt, ops, str};
16
17use elliptic_curve::{
18    rand_core::{CryptoRng, RngCore, SeedableRng},
19    zeroize::Zeroize,
20};
21use merlin::Transcript;
22use rand_chacha::ChaChaRng;
23
24#[cfg(any(feature = "curve25519-dalek", feature = "curve25519-dalek-ng"))]
25mod curve25519;
26mod generic;
27#[cfg(any(feature = "curve25519-dalek", feature = "curve25519-dalek-ng"))]
28mod ristretto;
29
30pub use self::generic::Generic;
31#[cfg(any(feature = "curve25519-dalek", feature = "curve25519-dalek-ng"))]
32pub use self::{curve25519::Curve25519Subgroup, ristretto::Ristretto};
33
34/// Provides an arbitrary number of random bytes.
35///
36/// Unlike [`RngCore::fill_bytes()`], a single provider can only be used once.
37pub struct RandomBytesProvider<'a> {
38    transcript: &'a mut Transcript,
39    label: &'static [u8],
40}
41
42impl fmt::Debug for RandomBytesProvider<'_> {
43    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
44        let label = str::from_utf8(self.label).unwrap_or("(non-utf8 label)");
45        formatter
46            .debug_struct("RandomBytesProvider")
47            .field("label", &label)
48            .finish()
49    }
50}
51
52impl<'a> RandomBytesProvider<'a> {
53    pub(crate) fn new(transcript: &'a mut Transcript, label: &'static [u8]) -> Self {
54        Self { transcript, label }
55    }
56
57    /// Writes random bytes into the specified buffer. As follows from the signature, this method
58    /// can only be called once for a provider instance.
59    pub fn fill_bytes(self, dest: &mut [u8]) {
60        self.transcript.challenge_bytes(self.label, dest);
61    }
62}
63
64/// Helper trait for [`Group`] that describes operations on group scalars.
65pub trait ScalarOps {
66    /// Scalar type. As per [`Group`] contract, scalars must form a prime field.
67    /// Arithmetic operations on scalars requested here must be constant-time.
68    type Scalar: Copy
69        + Default
70        + From<u64>
71        + From<Self::Scalar> // `PublicKey::encrypt()` doesn't work without this
72        + ops::Neg<Output = Self::Scalar>
73        + ops::Add<Output = Self::Scalar>
74        + for<'a> ops::Add<&'a Self::Scalar, Output = Self::Scalar>
75        + ops::Sub<Output = Self::Scalar>
76        + ops::Mul<Output = Self::Scalar>
77        + for<'a> ops::Mul<&'a Self::Scalar, Output = Self::Scalar>
78        + PartialEq
79        + Zeroize
80        + fmt::Debug;
81
82    /// Byte size of a serialized [`Self::Scalar`].
83    const SCALAR_SIZE: usize;
84
85    /// Generates a random scalar based on the provided CSPRNG. This operation
86    /// must be constant-time.
87    fn generate_scalar<R: CryptoRng + RngCore>(rng: &mut R) -> Self::Scalar;
88
89    /// Generates a scalar from a `source` of random bytes. This operation must be constant-time.
90    /// The `source` is guaranteed to return any necessary number of bytes.
91    ///
92    /// # Default implementation
93    ///
94    /// 1. Create a [ChaCha RNG] using 32 bytes read from `source` as the seed.
95    /// 2. Call [`Self::generate_scalar()`] with the created RNG.
96    ///
97    /// [ChaCha RNG]: https://docs.rs/rand_chacha/
98    fn scalar_from_random_bytes(source: RandomBytesProvider<'_>) -> Self::Scalar {
99        let mut rng_seed = <ChaChaRng as SeedableRng>::Seed::default();
100        source.fill_bytes(&mut rng_seed);
101        let mut rng = ChaChaRng::from_seed(rng_seed);
102        Self::generate_scalar(&mut rng)
103    }
104
105    /// Inverts the `scalar`, which is guaranteed to be non-zero. This operation does not
106    /// need to be constant-time.
107    fn invert_scalar(scalar: Self::Scalar) -> Self::Scalar;
108
109    /// Inverts scalars in a batch. This operation does not need to be constant-time.
110    ///
111    /// # Default implementation
112    ///
113    /// Inverts every scalar successively.
114    fn invert_scalars(scalars: &mut [Self::Scalar]) {
115        for scalar in scalars {
116            *scalar = Self::invert_scalar(*scalar);
117        }
118    }
119
120    /// Serializes the scalar into the provided `buffer`, which is guaranteed to have length
121    /// [`Self::SCALAR_SIZE`].
122    fn serialize_scalar(scalar: &Self::Scalar, buffer: &mut [u8]);
123
124    /// Deserializes the scalar from `buffer`, which is guaranteed to have length
125    /// [`Self::SCALAR_SIZE`]. This method returns `None` if the buffer
126    /// does not correspond to a representation of a valid scalar.
127    fn deserialize_scalar(buffer: &[u8]) -> Option<Self::Scalar>;
128}
129
130/// Helper trait for [`Group`] that describes operations on group elements (i.e., EC points
131/// for elliptic curve groups).
132pub trait ElementOps: ScalarOps {
133    /// Element of the group. Arithmetic operations requested here (addition among
134    /// elements and multiplication by a `Scalar`) must be constant-time.
135    type Element: Copy
136        + ops::Add<Output = Self::Element>
137        + ops::Sub<Output = Self::Element>
138        + ops::Neg<Output = Self::Element>
139        + for<'a> ops::Mul<&'a Self::Scalar, Output = Self::Element>
140        + PartialEq
141        + fmt::Debug;
142
143    /// Byte size of a serialized [`Self::Element`].
144    const ELEMENT_SIZE: usize;
145
146    /// Returns the identity of the group (aka point at infinity for EC groups).
147    fn identity() -> Self::Element;
148
149    /// Checks if the specified element is the identity.
150    fn is_identity(element: &Self::Element) -> bool;
151
152    /// Returns the agreed-upon generator of the group.
153    fn generator() -> Self::Element;
154
155    /// Serializes `element` into the provided `buffer`, which is guaranteed to have length
156    /// [`Self::ELEMENT_SIZE`].
157    fn serialize_element(element: &Self::Element, output: &mut [u8]);
158
159    /// Deserializes an element from `buffer`, which is guaranteed to have length
160    /// [`Self::ELEMENT_SIZE`]. This method returns `None` if the buffer
161    /// does not correspond to a representation of a valid scalar.
162    fn deserialize_element(buffer: &[u8]) -> Option<Self::Element>;
163}
164
165/// Prime-order group in which the discrete log problem and decisional / computational
166/// Diffie–Hellman problems are believed to be hard.
167///
168/// Groups conforming to this trait can be used for ElGamal encryption and other
169/// cryptographic protocols defined in this crate.
170///
171/// This crate provides the following implementations of this trait:
172///
173/// - [`Curve25519Subgroup`], representation of a prime-order subgroup of Curve25519
174///   with the conventionally chosen generator.
175/// - [`Ristretto`], a transform of Curve25519 which eliminates its co-factor 8 with the help
176///   of the [eponymous technique][ristretto].
177/// - [`Generic`] implementation defined in terms of traits from the [`elliptic-curve`] crate.
178///   (For example, this means secp256k1 support via the [`k256`] crate.)
179///
180/// [ristretto]: https://ristretto.group/
181/// [`elliptic-curve`]: https://docs.rs/elliptic-curve/
182/// [`k256`]: https://docs.rs/k256/
183pub trait Group: Copy + ScalarOps + ElementOps + 'static {
184    /// Multiplies the provided scalar by [`ElementOps::generator()`]. This operation must be
185    /// constant-time.
186    ///
187    /// # Default implementation
188    ///
189    /// Implemented using [`Mul`](ops::Mul) (which is constant-time as per the [`ElementOps`]
190    /// contract).
191    fn mul_generator(k: &Self::Scalar) -> Self::Element {
192        Self::generator() * k
193    }
194
195    /// Multiplies the provided scalar by [`ElementOps::generator()`].
196    /// Unlike [`Self::mul_generator()`], this operation does not need to be constant-time;
197    /// thus, it may employ additional optimizations.
198    ///
199    /// # Default implementation
200    ///
201    /// Implemented by calling [`Self::mul_generator()`].
202    #[inline]
203    fn vartime_mul_generator(k: &Self::Scalar) -> Self::Element {
204        Self::mul_generator(k)
205    }
206
207    /// Multiplies provided `scalars` by `elements`. This operation must be constant-time
208    /// w.r.t. the given length of elements.
209    ///
210    /// # Default implementation
211    ///
212    /// Implemented by straightforward computations, which are constant-time as per
213    /// the [`ElementOps`] contract.
214    fn multi_mul<'a, I, J>(scalars: I, elements: J) -> Self::Element
215    where
216        I: IntoIterator<Item = &'a Self::Scalar>,
217        J: IntoIterator<Item = Self::Element>,
218    {
219        let mut output = Self::identity();
220        for (scalar, element) in scalars.into_iter().zip(elements) {
221            output = output + element * scalar;
222        }
223        output
224    }
225
226    /// Calculates `k * k_element + r * G`, where `G` is the group generator. This operation
227    /// does not need to be constant-time.
228    ///
229    /// # Default implementation
230    ///
231    /// Implemented by straightforward arithmetic.
232    fn vartime_double_mul_generator(
233        k: &Self::Scalar,
234        k_element: Self::Element,
235        r: &Self::Scalar,
236    ) -> Self::Element {
237        k_element * k + Self::generator() * r
238    }
239
240    /// Multiplies provided `scalars` by `elements`. Unlike [`Self::multi_mul()`],
241    /// this operation does not need to be constant-time; thus, it may employ
242    /// additional optimizations.
243    ///
244    /// # Default implementation
245    ///
246    /// Implemented by calling [`Self::multi_mul()`].
247    #[inline]
248    fn vartime_multi_mul<'a, I, J>(scalars: I, elements: J) -> Self::Element
249    where
250        I: IntoIterator<Item = &'a Self::Scalar>,
251        J: IntoIterator<Item = Self::Element>,
252    {
253        Self::multi_mul(scalars, elements)
254    }
255}
elastic_elgamal/group/mod.rs

elastic_elgamal/group/
mod.rs
