gg.rs

//! Galindo-Garcia Identity-based signatures (GG-IBS).
//!
//! - From: "[A Schnorr-Like Lightweight Identity-Based Signature Scheme](https://link.springer.com/chapter/10.1007/978-3-642-02384-2_9)", AfricaCrypt, 2009.
//!
//! The scheme is built on Curve25519 Ristretto, using crate [`curve25519_dalek`].
//!
//! Hash functions G and H are instantiated as follows:
//! - G = `SHAKE128` (with a 64-byte output).
//! - H = `SHA3_512`,
//!
//! The constant [Ristretto basepoint][`curve25519_dalek::constants::RISTRETTO_BASEPOINT_POINT`] is used as a generator.
//!
//! # Example
//!
//! ```
//! use ibs::{
//!     gg,
//!     gg::{Identity, PublicKey, SecretKey, Signer, UserSecretKey, Verifier},
//! };
//! use rand::prelude::*;
//!
//! let mut rng = rand::rng();
//! let (pk, sk) = gg::setup(&mut rng);
//! let id = Identity::from("Johnny");
//!                                                                            
//! let usk_id = gg::keygen(&sk, &id, &mut rng);
//! let sig = Signer::new()
//!     .chain(b"The eagle has landed")
//!     .sign(&usk_id, &mut rng);
//!                                                                            
//! assert!(Verifier::new()
//!     .chain(b"The eagle ")
//!     .chain(b"has landed")
//!     .verify(&pk, &sig, &id));
//!                                                                            
//! assert!(!Verifier::new()
//!     .chain(b"The falcon has landed")
//!     .verify(&pk, &sig, &id));
//! ```

use curve25519_dalek::{
    constants::RISTRETTO_BASEPOINT_POINT, constants::RISTRETTO_BASEPOINT_TABLE,
    ristretto::CompressedRistretto, ristretto::RistrettoPoint, scalar::Scalar,
    traits::VartimeMultiscalarMul,
};
use rand_core::CryptoRng;
use sha3::digest::{ExtendableOutput, Update};
use sha3::{Digest, Sha3_256, Sha3_512};
use shake::Shake128;

#[cfg(feature = "serde")]
use serde::{Deserialize, Serialize};

#[cfg(feature = "zeroize")]
use zeroize::{Zeroize, ZeroizeOnDrop};

/// Size of a compressed public key.
pub const PK_BYTES: usize = 32;

/// Public key.
#[derive(Debug, Clone, PartialEq, Eq)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
pub struct PublicKey(RistrettoPoint);

/// Size of a compressed secret key.
pub const SK_BYTES: usize = 32;

/// Secret key.
#[derive(Debug, Clone, PartialEq, Eq)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
#[cfg_attr(feature = "zeroize", derive(Zeroize, ZeroizeOnDrop))]
pub struct SecretKey(Scalar);

/// Size of a compressed [`UserSecretKey`].
pub const USK_BYTES: usize = 96;

/// User secret key.
#[derive(Debug, Clone, PartialEq, Eq)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
#[cfg_attr(feature = "zeroize", derive(Zeroize, ZeroizeOnDrop))]
pub struct UserSecretKey {
    y: Scalar,
    gr: RistrettoPoint,
    id: Identity,
}

/// Size of a compressed [`Signature`].
pub const SIG_BYTES: usize = 96;

/// Signature.
#[derive(Debug, Clone, PartialEq, Eq)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
pub struct Signature {
    ga: RistrettoPoint,
    b: Scalar,
    gr: RistrettoPoint,
}

/// The size of the identity parameter.
pub const IDENTITY_BYTES: usize = 32;

/// Identity.
///
/// Uses a 32-byte internal representation.
#[derive(Debug, Clone, PartialEq, Eq)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
#[cfg_attr(feature = "zeroize", derive(Zeroize, ZeroizeOnDrop))]
pub struct Identity([u8; IDENTITY_BYTES]);

impl<T: AsRef<[u8]>> From<T> for Identity {
    fn from(b: T) -> Self {
        if b.as_ref().len() == IDENTITY_BYTES {
            Identity(b.as_ref().try_into().unwrap())
        } else {
            Identity(Sha3_256::digest(b.as_ref()).into())
        }
    }
}

// Helper: decode a 32-byte slice into a canonical `Scalar`.
fn scalar_from_canonical(bytes: [u8; 32]) -> Option<Scalar> {
    Scalar::from_canonical_bytes(bytes).into()
}

// Helper: decode a 32-byte slice into a `RistrettoPoint`.
fn point_from_bytes(bytes: [u8; 32]) -> Option<RistrettoPoint> {
    CompressedRistretto(bytes).decompress()
}

impl PublicKey {
    /// Serialize the public key to its compressed byte encoding.
    pub fn to_bytes(&self) -> [u8; PK_BYTES] {
        self.0.compress().to_bytes()
    }

    /// Deserialize a public key from its compressed byte encoding.
    ///
    /// Returns `None` if `bytes` is not a valid compressed Ristretto point.
    pub fn from_bytes(bytes: &[u8; PK_BYTES]) -> Option<Self> {
        point_from_bytes(*bytes).map(PublicKey)
    }
}

impl SecretKey {
    /// Serialize the secret key to its canonical byte encoding.
    pub fn to_bytes(&self) -> [u8; SK_BYTES] {
        self.0.to_bytes()
    }

    /// Deserialize a secret key from its canonical byte encoding.
    ///
    /// Returns `None` if `bytes` is not a canonical scalar encoding.
    pub fn from_bytes(bytes: &[u8; SK_BYTES]) -> Option<Self> {
        scalar_from_canonical(*bytes).map(SecretKey)
    }
}

impl UserSecretKey {
    /// Serialize the user secret key to a 96-byte encoding.
    ///
    /// Layout: `y (32 bytes) || gr (32 bytes, compressed) || id (32 bytes)`.
    pub fn to_bytes(&self) -> [u8; USK_BYTES] {
        let mut out = [0u8; USK_BYTES];
        out[..32].copy_from_slice(&self.y.to_bytes());
        out[32..64].copy_from_slice(&self.gr.compress().to_bytes());
        out[64..96].copy_from_slice(&self.id.0);
        out
    }

    /// Deserialize a user secret key from its 96-byte encoding.
    ///
    /// Returns `None` if `y` is not a canonical scalar or if `gr` is not a
    /// valid compressed Ristretto point. See [`UserSecretKey::to_bytes`] for
    /// the encoding layout.
    pub fn from_bytes(bytes: &[u8; USK_BYTES]) -> Option<Self> {
        let mut y_bytes = [0u8; 32];
        let mut gr_bytes = [0u8; 32];
        let mut id_bytes = [0u8; IDENTITY_BYTES];
        y_bytes.copy_from_slice(&bytes[..32]);
        gr_bytes.copy_from_slice(&bytes[32..64]);
        id_bytes.copy_from_slice(&bytes[64..96]);

        let y = scalar_from_canonical(y_bytes)?;
        let gr = point_from_bytes(gr_bytes)?;

        Some(UserSecretKey {
            y,
            gr,
            id: Identity(id_bytes),
        })
    }
}

impl Signature {
    /// Serialize the signature to a 96-byte encoding.
    ///
    /// Layout: `ga (32 bytes, compressed) || b (32 bytes) || gr (32 bytes, compressed)`.
    pub fn to_bytes(&self) -> [u8; SIG_BYTES] {
        let mut out = [0u8; SIG_BYTES];
        out[..32].copy_from_slice(&self.ga.compress().to_bytes());
        out[32..64].copy_from_slice(&self.b.to_bytes());
        out[64..96].copy_from_slice(&self.gr.compress().to_bytes());
        out
    }

    /// Deserialize a signature from its 96-byte encoding.
    ///
    /// Returns `None` if `ga` or `gr` is not a valid compressed Ristretto
    /// point or if `b` is not a canonical scalar encoding. See
    /// [`Signature::to_bytes`] for the encoding layout.
    pub fn from_bytes(bytes: &[u8; SIG_BYTES]) -> Option<Self> {
        let mut ga_bytes = [0u8; 32];
        let mut b_bytes = [0u8; 32];
        let mut gr_bytes = [0u8; 32];
        ga_bytes.copy_from_slice(&bytes[..32]);
        b_bytes.copy_from_slice(&bytes[32..64]);
        gr_bytes.copy_from_slice(&bytes[64..96]);

        let ga = point_from_bytes(ga_bytes)?;
        let b = scalar_from_canonical(b_bytes)?;
        let gr = point_from_bytes(gr_bytes)?;

        Some(Signature { ga, b, gr })
    }
}

// Helper function to compute H(g^r || id).
fn h_helper(gr: &RistrettoPoint, id: &Identity) -> Scalar {
    let mut h = Sha3_512::new();

    Digest::update(&mut h, gr.compress().as_bytes());
    Digest::update(&mut h, id.0);

    Scalar::from_hash(h)
}

/// Create a master key pair.
pub fn setup<R: CryptoRng>(r: &mut R) -> (PublicKey, SecretKey) {
    let z = Scalar::random(r);
    let gz = RISTRETTO_BASEPOINT_TABLE * &z;

    (PublicKey(gz), SecretKey(z))
}

/// Extract a signing key from the master secret key for a given identity.
pub fn keygen<R: CryptoRng>(sk: &SecretKey, id: &Identity, r: &mut R) -> UserSecretKey {
    let r = Scalar::random(r);
    let gr = RISTRETTO_BASEPOINT_TABLE * &r;
    let y = r + sk.0 * h_helper(&gr, id);

    UserSecretKey {
        y,
        gr,
        id: id.clone(),
    }
}

/// Signer.
#[derive(Debug, Clone)]
pub struct Signer {
    g: Shake128,
}

impl Default for Signer {
    fn default() -> Self {
        Signer::new()
    }
}

impl Signer {
    /// Create a new signer.
    pub fn new() -> Self {
        Self {
            g: Shake128::default(),
        }
    }

    /// Sign additional message data.
    pub fn update(&mut self, m: impl AsRef<[u8]>) {
        self.g.update(m.as_ref());
    }

    /// Sign additional message data, in a chained manner.
    #[must_use]
    pub fn chain(mut self, m: impl AsRef<[u8]>) -> Self {
        self.g.update(m.as_ref());
        self
    }

    /// Create the signature. Call this after the message has been processed.
    pub fn sign<R: CryptoRng>(mut self, usk: &UserSecretKey, r: &mut R) -> Signature {
        let a = Scalar::random(r);
        let ga = RISTRETTO_BASEPOINT_TABLE * &a;

        self.g.update(&usk.id.0);
        self.g.update(ga.compress().as_bytes());

        let mut out = [0u8; 64];
        self.g.finalize_xof_into(&mut out);

        let b = a + usk.y * Scalar::from_bytes_mod_order_wide(&out);

        Signature { ga, b, gr: usk.gr }
    }
}

/// Verifier.
#[derive(Debug, Clone)]
pub struct Verifier {
    g: Shake128,
}

impl Default for Verifier {
    fn default() -> Self {
        Verifier::new()
    }
}

impl Verifier {
    /// Create a new verifier instance.
    pub fn new() -> Self {
        Self {
            g: Shake128::default(),
        }
    }

    /// Verify additional message data.
    pub fn update(&mut self, m: impl AsRef<[u8]>) {
        self.g.update(m.as_ref());
    }

    /// Verify additional message data, in a chained manner.
    #[must_use]
    pub fn chain(mut self, m: impl AsRef<[u8]>) -> Self {
        self.g.update(m.as_ref());
        self
    }

    /// Verifies the signature.
    #[must_use]
    pub fn verify(mut self, pk: &PublicKey, sig: &Signature, id: &Identity) -> bool {
        self.g.update(&id.0);
        self.g.update(&sig.ga.compress().to_bytes());

        let c = h_helper(&sig.gr, id);

        let mut out = [0u8; 64];
        self.g.finalize_xof_into(&mut out);
        let d = Scalar::from_bytes_mod_order_wide(&out);

        let lhs = -sig.ga;
        let rhs = RistrettoPoint::vartime_multiscalar_mul(
            &[-sig.b, c * d, d],
            &[RISTRETTO_BASEPOINT_POINT, pk.0, sig.gr],
        );

        lhs.eq(&rhs)
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use rand::Rng;

    fn default_setup() -> (PublicKey, UserSecretKey, Identity) {
        let (pk, sk) = setup(&mut rand::rng());
        let mut rand_bytes = [0u8; 32];
        rand::rng().fill_bytes(&mut rand_bytes);
        let id = rand_bytes.into();
        let usk = keygen(&sk, &id, &mut rand::rng());

        (pk, usk, id)
    }

    #[test]
    fn test_sign_verify() {
        let (pk, usk, id) = default_setup();

        let message = b"some identical message";
        let sig = Signer::new().chain(message).sign(&usk, &mut rand::rng());

        assert!(Verifier::new().chain(message).verify(&pk, &sig, &id));
    }

    #[test]
    fn test_sign_wrong_message() {
        let (pk, usk, id) = default_setup();

        let sig = Signer::new()
            .chain(b"some message")
            .sign(&usk, &mut rand::rng());
        assert!(!Verifier::new()
            .chain(b"some other message")
            .verify(&pk, &sig, &id));
    }

    #[test]
    fn test_sign_wrong_public_key() {
        let (_, usk1, id1) = default_setup();
        let (pk2, _, _) = default_setup();

        let message = b"some identical message";
        let sig = Signer::new().chain(message).sign(&usk1, &mut rand::rng());

        assert!(!Verifier::new().chain(message).verify(&pk2, &sig, &id1));
    }

    #[test]
    fn test_sign_wrong_identity() {
        let (pk1, usk1, _) = default_setup();
        let (_, _, id2) = default_setup();

        let message = b"some identical message";
        let sig = Signer::new().chain(message).sign(&usk1, &mut rand::rng());

        assert!(!Verifier::new().chain(message).verify(&pk1, &sig, &id2));
    }

    #[test]
    #[cfg(feature = "serde")]
    fn test_round() {
        // This test simulates a real-world scenario,
        // where all communicated messages are serialized/deserialized.

        let (pk, usk, id) = default_setup();
        let cfg = bincode_next::config::standard();

        // 1. PKG creates key pair and publishes the public key.
        let pk_serialized = bincode_next::serde::encode_to_vec(&pk, cfg).unwrap();
        let usk_serialized = bincode_next::serde::encode_to_vec(&usk, cfg).unwrap();

        // 2. A signer retrieves the public key and signs some message,
        // after which it sends the signature to the verifier.
        let (pk_recovered, _): (PublicKey, usize) =
            bincode_next::serde::decode_from_slice(&pk_serialized, cfg).unwrap();
        let (usk_recovered, _): (UserSecretKey, usize) =
            bincode_next::serde::decode_from_slice(&usk_serialized, cfg).unwrap();
        let sig = Signer::new()
            .chain(b"some message")
            .sign(&usk_recovered, &mut rand::rng());
        let sig_serialized = bincode_next::serde::encode_to_vec(&sig, cfg).unwrap();

        // 3. A verifier retrieves the signature from the signer and verifies it.
        let (sig_recovered, _): (Signature, usize) =
            bincode_next::serde::decode_from_slice(&sig_serialized, cfg).unwrap();

        assert!(Verifier::new()
            .chain(b"some message")
            .verify(&pk_recovered, &sig_recovered, &id));
    }

    #[test]
    fn test_signature_eq() {
        let (_, usk, _) = default_setup();
        let message = b"message under test";

        let sig = Signer::new().chain(message).sign(&usk, &mut rand::rng());
        let sig_clone = sig.clone();
        assert_eq!(sig, sig_clone);

        let sig_other = Signer::new().chain(message).sign(&usk, &mut rand::rng());
        assert_ne!(sig, sig_other);
    }

    #[test]
    fn test_byte_roundtrip_public_key() {
        let (pk, _) = setup(&mut rand::rng());
        let bytes = pk.to_bytes();
        let recovered = PublicKey::from_bytes(&bytes).expect("valid pk bytes");
        assert_eq!(pk, recovered);
        assert_eq!(bytes, recovered.to_bytes());
    }

    #[test]
    fn test_byte_roundtrip_secret_key() {
        let (_, sk) = setup(&mut rand::rng());
        let bytes = sk.to_bytes();
        let recovered = SecretKey::from_bytes(&bytes).expect("valid sk bytes");
        assert_eq!(sk, recovered);
        assert_eq!(bytes, recovered.to_bytes());
    }

    #[test]
    fn test_byte_roundtrip_user_secret_key() {
        let (_, usk, _) = default_setup();
        let bytes = usk.to_bytes();
        let recovered = UserSecretKey::from_bytes(&bytes).expect("valid usk bytes");
        assert_eq!(usk, recovered);
        assert_eq!(bytes, recovered.to_bytes());
    }

    #[test]
    fn test_byte_roundtrip_signature() {
        let (_, usk, _) = default_setup();
        let sig = Signer::new().chain(b"msg").sign(&usk, &mut rand::rng());
        let bytes = sig.to_bytes();
        let recovered = Signature::from_bytes(&bytes).expect("valid sig bytes");
        assert_eq!(sig, recovered);
        assert_eq!(bytes, recovered.to_bytes());
    }

    #[test]
    fn test_byte_roundtrip_end_to_end() {
        // Full sign/verify across to_bytes/from_bytes on every type.
        let (pk, sk) = setup(&mut rand::rng());
        let mut id_bytes = [0u8; 32];
        rand::rng().fill_bytes(&mut id_bytes);
        let id: Identity = id_bytes.into();
        let usk = keygen(&sk, &id, &mut rand::rng());

        let pk = PublicKey::from_bytes(&pk.to_bytes()).unwrap();
        let usk = UserSecretKey::from_bytes(&usk.to_bytes()).unwrap();

        let message = b"the eagle has landed";
        let sig = Signer::new().chain(message).sign(&usk, &mut rand::rng());
        let sig = Signature::from_bytes(&sig.to_bytes()).unwrap();

        assert!(Verifier::new().chain(message).verify(&pk, &sig, &id));
    }

    #[test]
    fn test_from_bytes_rejects_invalid_point() {
        // 0xFF... is not a canonical compressed Ristretto encoding.
        let bad = [0xFFu8; PK_BYTES];
        assert!(PublicKey::from_bytes(&bad).is_none());
    }

    #[test]
    fn test_from_bytes_rejects_non_canonical_scalar() {
        // The all-ones byte string exceeds the curve25519 scalar order.
        let bad = [0xFFu8; SK_BYTES];
        assert!(SecretKey::from_bytes(&bad).is_none());
    }

    #[test]
    fn test_signature_from_bytes_rejects_bad_point() {
        let (_, usk, _) = default_setup();
        let sig = Signer::new().chain(b"msg").sign(&usk, &mut rand::rng());
        let mut bytes = sig.to_bytes();
        // Corrupt the `ga` point to an invalid encoding.
        bytes[..32].copy_from_slice(&[0xFFu8; 32]);
        assert!(Signature::from_bytes(&bytes).is_none());
    }

    #[test]
    fn test_clone_state() {
        let (pk, usk, id) = default_setup();

        let signer = Signer::new().chain(b"a");
        let sig2 = signer.clone().chain(b"b").sign(&usk, &mut rand::rng());
        let sig1 = signer.sign(&usk, &mut rand::rng());
        let verifier = Verifier::new().chain(b"a");
        assert!(verifier.clone().chain(b"b").verify(&pk, &sig2, &id));
        assert!(verifier.verify(&pk, &sig1, &id));
    }
}