p2panda_encryption/crypto/
xeddsa.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2
3//! XEdDSA enables use of a single key pair format for both x25519 elliptic curve Diffie-Hellman
4//! and Ed25199 signatures.
5//!
6//! <https://signal.org/docs/specifications/xeddsa/>
7use std::fmt;
8
9use curve25519_dalek::constants::ED25519_BASEPOINT_TABLE;
10use curve25519_dalek::{EdwardsPoint, MontgomeryPoint, Scalar};
11use serde::{Deserialize, Serialize};
12use subtle::ConstantTimeEq;
13use thiserror::Error;
14
15use crate::crypto::sha2::sha2_512;
16use crate::crypto::x25519::{PublicKey, SecretKey};
17use crate::crypto::{Rng, RngError};
18
19/// 512-bit signature.
20pub const SIGNATURE_SIZE: usize = 64;
21
22/// Hash1 changes the first byte to 0xFE.
23const HASH_1_PREFIX: [u8; 32] = [
24    0xFEu8, 0xFFu8, 0xFFu8, 0xFFu8, 0xFFu8, 0xFFu8, 0xFFu8, 0xFFu8, 0xFFu8, 0xFFu8, 0xFFu8, 0xFFu8,
25    0xFFu8, 0xFFu8, 0xFFu8, 0xFFu8, 0xFFu8, 0xFFu8, 0xFFu8, 0xFFu8, 0xFFu8, 0xFFu8, 0xFFu8, 0xFFu8,
26    0xFFu8, 0xFFu8, 0xFFu8, 0xFFu8, 0xFFu8, 0xFFu8, 0xFFu8, 0xFFu8,
27];
28
29/// XEdDSA signature.
30#[derive(Copy, Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
31pub struct XSignature(#[serde(with = "serde_bytes")] [u8; SIGNATURE_SIZE]);
32
33impl XSignature {
34    pub fn from_bytes(bytes: [u8; SIGNATURE_SIZE]) -> Self {
35        Self(bytes)
36    }
37
38    pub fn as_bytes(&self) -> &[u8; SIGNATURE_SIZE] {
39        &self.0
40    }
41
42    pub fn to_bytes(self) -> [u8; SIGNATURE_SIZE] {
43        self.0
44    }
45
46    pub fn to_hex(self) -> String {
47        hex::encode(self.as_bytes())
48    }
49}
50
51impl fmt::Display for XSignature {
52    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
53        write!(f, "{}", self.to_hex())
54    }
55}
56
57/// Calculates an XEdDSA signature using the X25519 secret key directly.
58pub fn xeddsa_sign(
59    bytes: &[u8],
60    secret_key: &SecretKey,
61    rng: &Rng,
62) -> Result<XSignature, XEdDSAError> {
63    // M = Message to sign (byte sequence)
64    let cap_m = bytes;
65
66    // Z = 64 bytes secure random data (byte sequence)
67    let cap_z: [u8; SIGNATURE_SIZE] = rng.random_array()?;
68
69    // A, a = calculate_key_pair(k)
70    let (cap_a, a) = {
71        // k = Montgomery private key (integer mod q)
72        let k_bytes = secret_key.as_bytes();
73        let k = Scalar::from_bytes_mod_order(*k_bytes);
74
75        // calculate_key_pair(k)
76        let cap_e = &k * ED25519_BASEPOINT_TABLE; // E = kB
77        let mut cap_a = cap_e.compress(); // A.y = E.y
78        let sign_bit = cap_a.0[31] >> 7; // sign_bit = E.s
79        cap_a.0[31] &= 0b0111_1111_u8; // A.s = 0
80
81        // if E.s == 1:
82        //   a = -k (mod q)
83        // else:
84        //   a = k (mod q)
85        let a = if sign_bit == 1 { -k } else { k };
86
87        (cap_a, a)
88    };
89
90    // r = hash1(a || M || Z) (mod q)
91    let r = Scalar::from_bytes_mod_order_wide(&{
92        sha2_512(&[&HASH_1_PREFIX, a.as_bytes(), cap_m, &cap_z])
93    });
94
95    // R = rB
96    let cap_r = (&r * ED25519_BASEPOINT_TABLE).compress();
97
98    // h = hash(R || A || M) (mod q)
99    let h = Scalar::from_bytes_mod_order_wide(&{
100        sha2_512(&[cap_r.as_bytes(), cap_a.as_bytes(), cap_m])
101    });
102
103    // s = r + ha (mod q)
104    let s = r + (h * a);
105
106    // return R || s
107    let mut result = [0u8; SIGNATURE_SIZE];
108    result[..32].copy_from_slice(cap_r.as_bytes());
109    result[32..].copy_from_slice(s.as_bytes());
110    Ok(XSignature::from_bytes(result))
111}
112
113/// Verifies a XEdDSA signature on provided data using the X25519 public counter-part.
114pub fn xeddsa_verify(
115    bytes: &[u8],
116    their_public_key: &PublicKey,
117    signature: &XSignature,
118) -> Result<(), XEdDSAError> {
119    // M = Message to sign (byte sequence)
120    let cap_m = bytes;
121
122    // u = Montgomery public key (byte sequence of b bits).
123    let u = their_public_key;
124
125    // R || s = Signature to verify (byte sequence of 2b bits)
126    let mut cap_r = [0u8; 32];
127    cap_r.copy_from_slice(&signature.as_bytes()[..32]);
128    let mut s = [0u8; 32];
129    s.copy_from_slice(&signature.as_bytes()[32..]);
130    s[31] &= 0b0111_1111_u8;
131
132    // Reject s if it has excess bits.
133    if (s[31] & 0b1110_0000_u8) != 0 {
134        return Err(XEdDSAError::InvalidArgument);
135    }
136
137    // convert_mont(u):
138    //   umasked = u (mod 2|p|)
139    //   P.y = u_to_y(umasked)
140    //   P.s = 0
141    //   return P
142    let a = {
143        let mont_point = MontgomeryPoint(u.to_bytes());
144        match mont_point.to_edwards(0) {
145            Some(x) => x,
146            // if not on_curve(A):
147            //   return false
148            None => return Err(XEdDSAError::InvalidArgument),
149        }
150    };
151    let cap_a = a.compress();
152
153    // h = hash(R || A || M) (mod q)
154    let h = Scalar::from_bytes_mod_order_wide(&{ sha2_512(&[&cap_r, cap_a.as_bytes(), cap_m]) });
155
156    // Rcheck = sB - hA
157    let cap_r_check = {
158        let minus_cap_a = -a;
159        let cap_r_check_point = EdwardsPoint::vartime_double_scalar_mul_basepoint(
160            &h,
161            &minus_cap_a,
162            &Scalar::from_bytes_mod_order(s),
163        );
164        cap_r_check_point.compress()
165    };
166
167    // if bytes_equal(R, Rcheck):
168    //   return true
169    if bool::from(cap_r_check.as_bytes().ct_eq(&cap_r)) {
170        Ok(())
171    } else {
172        Err(XEdDSAError::VerificationFailed)
173    }
174}
175
176#[derive(Debug, Error)]
177pub enum XEdDSAError {
178    #[error(transparent)]
179    Rng(#[from] RngError),
180
181    #[error("invalid xeddsa public key or signature")]
182    InvalidArgument,
183
184    #[error("signature does not match public key and bytes")]
185    VerificationFailed,
186}
187
188#[cfg(test)]
189mod tests {
190    use crate::crypto::Rng;
191    use crate::crypto::x25519::SecretKey;
192
193    use super::{XEdDSAError, xeddsa_sign, xeddsa_verify};
194
195    #[test]
196    fn xeddsa_signatures() {
197        let rng = Rng::from_seed([1; 32]);
198
199        let secret_key = SecretKey::from_bytes(rng.random_array().unwrap());
200        let public_key = secret_key.public_key().unwrap();
201
202        let signature = xeddsa_sign(b"Hello, Panda!", &secret_key, &rng).unwrap();
203        assert!(xeddsa_verify(b"Hello, Panda!", &public_key, &signature).is_ok());
204    }
205
206    #[test]
207    fn failed_verify() {
208        let rng = Rng::from_seed([1; 32]);
209
210        let secret_key = SecretKey::from_bytes(rng.random_array().unwrap());
211        let public_key = secret_key.public_key().unwrap();
212        let signature = xeddsa_sign(b"Hello, Panda!", &secret_key, &rng).unwrap();
213
214        let invalid_secret_key = SecretKey::from_bytes(rng.random_array().unwrap());
215        let invalid_public_key = invalid_secret_key.public_key().unwrap();
216        let invalid_signature = xeddsa_sign(b"Hello, Panda!", &invalid_secret_key, &rng).unwrap();
217
218        assert_ne!(public_key, invalid_public_key);
219        assert_ne!(signature, invalid_signature);
220
221        assert!(matches!(
222            xeddsa_verify(b"Invalid Data", &public_key, &signature),
223            Err(XEdDSAError::VerificationFailed)
224        ));
225        assert!(matches!(
226            xeddsa_verify(b"Hello, Panda!", &invalid_public_key, &signature),
227            Err(XEdDSAError::VerificationFailed)
228        ));
229        assert!(matches!(
230            xeddsa_verify(b"Hello, Panda!", &public_key, &invalid_signature),
231            Err(XEdDSAError::VerificationFailed)
232        ));
233    }
234}
p2panda_encryption/crypto/xeddsa.rs

p2panda_encryption/crypto/
xeddsa.rs
