rings-core 0.20.0

//! Elgamal Crypto Implementation
//! ----------------
//! Algorithm Description
//! # Encrypt
//! A second party, Bob, encrypts a message 𝑀 to Alice under her public key (𝐺,𝑞,𝑔,ℎ)
//! as follows:
//!    Map the message 𝑀 to an element 𝑚 of 𝐺 using a reversible mapping function.
//! Choose an integer 𝑦
//! randomly from {1,…,𝑞−1}
//! 1. Compute 𝑠:=ℎ𝑦 as the ElGamal masking element.
//! 2. Compute 𝑐1:=𝑔𝑦
//! 3. Compute 𝑐2:=𝑚⋅𝑠
//! 4. Bob sends the ciphertext (𝑐1,𝑐2) to Alice.
//!
//! # Decrypt
//! Alice decrypts a ciphertext 𝑐1,𝑐2 with her private key 𝑠𝑘 as follows:
//! 1. Compute 𝑠:=𝑐𝑥1
//! 2. Compute 𝑠−1, the inverse of 𝑠 in the group 𝐺
//! 3. Compute 𝑚:=𝑐2⋅𝑠−1
//!
//! ref:
//!    T. ElGamal. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Trans. Info. Theory, IT 31:469–472, 1985.
//!    ElGamal encryption <https://en.wikipedia.org/wiki/ElGamal_encryption>
//!    <http://www.docsdrive.com/pdfs/ansinet/itj/2005/299-306.pdf>
//!
//! # Abstract group implementation
//!
//! ElGamal is a public-key encryption algorithm over a finite cyclic group. It
//! is not tied to a particular elliptic curve; an elliptic curve point group is
//! one possible implementation of the carrier.
//!
//! In multiplicative notation, `c2 := m * s` and decryption computes
//! `m := c2 * s^{-1}`. The implementation below uses additive notation because
//! that is the natural convention for elliptic curve groups.
//!
//! With the group written additively, encryption of a group element `m` under
//! public key `h = xg` is:
//!
//! 1. choose fresh random scalar `r`
//! 2. compute `c1 = rg`
//! 3. compute masking element `s = rh`
//! 4. compute `c2 = m + s`
//!
//! Decryption computes `m = c2 - x c1`.
//!
//! The pure group operation is [`ElGamal::encrypt_block`]. Randomness is passed
//! into [`ElGamal::encrypt_with_rng`] explicitly; [`ElGamal::encrypt`] is only a
//! convenience shell around the default thread-local sampler.

use std::marker::PhantomData;

use rand::RngCore;

use crate::algebra::Module;
use crate::ecc::group::Bls12381G1;
use crate::ecc::group::CyclicModule;
use crate::ecc::group::Point;
#[cfg(feature = "curve-ristretto255")]
use crate::ecc::group::Ristretto255;
use crate::ecc::group::Secp256k1;
use crate::ecc::group::Secp256r1;

pub mod impls;

/// Ciphertext pairs over one cyclic module carrier.
pub type GroupCiphertext<Element> = Vec<(Element, Element)>;

/// ElGamal over secp256k1 group elements.
pub type Secp256k1ElGamal = ElGamal<Point<Secp256k1>>;

/// ElGamal over secp256r1/P-256 group elements.
pub type Secp256r1ElGamal = ElGamal<Point<Secp256r1>>;

/// ElGamal over BLS12-381 G1 group elements.
pub type Bls12381G1ElGamal = ElGamal<Point<Bls12381G1>>;

/// ElGamal over Ristretto255 group elements.
#[cfg(feature = "curve-ristretto255")]
pub type Ristretto255ElGamal = ElGamal<Point<Ristretto255>>;

/// ElGamal public key `h = xg` over one cyclic module carrier.
pub struct ElGamalPublicKey<Element: CyclicModule> {
    element: Element,
}

/// ElGamal secret scalar `x` over one cyclic module carrier.
pub struct ElGamalSecretKey<Element: CyclicModule> {
    scalar: Element::Scalar,
}

/// ElGamal key pair over one cyclic module carrier.
pub struct ElGamalKeyPair<Element: CyclicModule> {
    secret: ElGamalSecretKey<Element>,
    public: ElGamalPublicKey<Element>,
}

/// Generic ElGamal implementation parameterized only by the element carrier.
pub struct ElGamal<Element>(PhantomData<Element>);

impl<Element> ElGamalPublicKey<Element>
where Element: CyclicModule
{
    /// Build a public key from an existing group element.
    pub fn from_element(element: Element) -> Self {
        Self { element }
    }

    /// Borrow the public group element.
    pub fn as_element(&self) -> &Element {
        &self.element
    }

    /// Unwrap into the public group element.
    pub fn into_element(self) -> Element {
        self.element
    }
}

impl<Element> Clone for ElGamalPublicKey<Element>
where Element: CyclicModule + Clone
{
    fn clone(&self) -> Self {
        Self::from_element(self.element.clone())
    }
}

impl<Element> ElGamalSecretKey<Element>
where Element: CyclicModule
{
    /// Build a secret key from an existing scalar.
    pub fn from_scalar(scalar: Element::Scalar) -> Self {
        Self { scalar }
    }

    /// Borrow the secret scalar.
    pub fn as_scalar(&self) -> &Element::Scalar {
        &self.scalar
    }

    /// Unwrap into the secret scalar.
    pub fn into_scalar(self) -> Element::Scalar {
        self.scalar
    }

    /// Derive the public key `h = xg`.
    pub fn public_key(&self) -> ElGamalPublicKey<Element> {
        ElGamalPublicKey::from_element(Element::generator_mul(&self.scalar))
    }
}

impl<Element> Clone for ElGamalSecretKey<Element>
where
    Element: CyclicModule,
    Element::Scalar: Clone,
{
    fn clone(&self) -> Self {
        Self::from_scalar(self.scalar.clone())
    }
}

impl<Element> ElGamalKeyPair<Element>
where Element: CyclicModule
{
    /// Borrow the public key.
    pub fn public_key(&self) -> &ElGamalPublicKey<Element> {
        &self.public
    }

    /// Borrow the secret key.
    pub fn secret_key(&self) -> &ElGamalSecretKey<Element> {
        &self.secret
    }
}

impl<Element> ElGamalSecretKey<Element>
where Element: CyclicModule
{
    /// Generate a fresh non-zero ElGamal secret scalar from an explicit RNG.
    pub fn random_with_rng(rng: &mut impl RngCore) -> Self {
        Self::from_scalar(Element::random_scalar_with_rng(rng))
    }

    /// Generate a fresh non-zero ElGamal secret scalar.
    pub fn random() -> Self {
        Self::from_scalar(Element::random_scalar())
    }
}

impl<Element> ElGamalKeyPair<Element>
where Element: CyclicModule
{
    /// Generate a fresh ElGamal key pair from an explicit RNG.
    pub fn random_with_rng(rng: &mut impl RngCore) -> Self {
        let secret = ElGamalSecretKey::<Element>::random_with_rng(rng);
        let public = secret.public_key();
        Self { secret, public }
    }

    /// Generate a fresh ElGamal key pair.
    pub fn random() -> Self {
        let secret = ElGamalSecretKey::<Element>::random();
        let public = secret.public_key();
        Self { secret, public }
    }
}

impl<Element> ElGamal<Element>
where
    Element: CyclicModule + Module<Element::Scalar> + Clone,
    Element::Scalar: Clone,
{
    /// Decrypt ciphertext pairs into group elements with the given scalar.
    pub fn decrypt(
        ciphertext: &[(Element, Element)],
        secret_key: &ElGamalSecretKey<Element>,
    ) -> Vec<Element> {
        ciphertext
            .iter()
            .map(|(c1, c2)| {
                let mask = c1.clone() * secret_key.as_scalar().clone();
                c2.clone() - mask
            })
            .collect()
    }

    /// Encrypt one group element using caller-supplied randomness.
    ///
    /// This is the pure ElGamal kernel over additive group notation:
    /// `(c1, c2) = (rg, m + rh)` where `h` is the public key and `r` is the
    /// ephemeral scalar. It performs no sampling and has no hidden side effects.
    pub fn encrypt_block(
        message_element: Element,
        public_key: &ElGamalPublicKey<Element>,
        ephemeral_scalar: Element::Scalar,
    ) -> (Element, Element) {
        let c1 = Element::generator_mul(&ephemeral_scalar);
        let mask = public_key.as_element().clone() * ephemeral_scalar;
        let c2 = message_element + mask;
        (c1, c2)
    }

    /// Encrypt group elements under the given public group element using an
    /// explicit RNG for ephemeral scalars.
    pub fn encrypt_with_rng<I>(
        message: I,
        public_key: &ElGamalPublicKey<Element>,
        rng: &mut impl RngCore,
    ) -> GroupCiphertext<Element>
    where
        I: IntoIterator<Item = Element>,
    {
        message
            .into_iter()
            .map(|message_element| {
                let ephemeral_scalar = Element::random_scalar_with_rng(rng);
                Self::encrypt_block(message_element, public_key, ephemeral_scalar)
            })
            .collect()
    }

    /// Encrypt group elements under the given public group element.
    pub fn encrypt<I>(
        message: I,
        public_key: &ElGamalPublicKey<Element>,
    ) -> GroupCiphertext<Element>
    where
        I: IntoIterator<Item = Element>,
    {
        message
            .into_iter()
            .map(|message_element| {
                let ephemeral_scalar = Element::random_scalar();
                Self::encrypt_block(message_element, public_key, ephemeral_scalar)
            })
            .collect()
    }
}

#[cfg(test)]
mod test_elgamal;