crypto/curve25519/
ed25519.rs

1use constant_time_eq::constant_time_eq;
2
3use super::curve25519::{FieldElement, U256};
4use crate::{EllipticCurveError, Hasher, sha2::Sha512};
5
6pub const SECRET_KEY_SIZE: usize = 32;
7pub const PUBLIC_KEY_SIZE: usize = 32;
8pub const SIGNATURE_SIZE: usize = 64;
9
10const MODULUS_L: U256 = U256::from_limbs([
11    0x5812_631a_5cf5_d3ed,
12    0x14de_f9de_a2f7_9cd6,
13    0x0000_0000_0000_0000,
14    0x1000_0000_0000_0000,
15]);
16
17// const P_PLUS_THREE_OVER_EIGHT: U256 = U256::from_limbs([
18//     0xffff_ffff_ffff_fffe,
19//     0xffff_ffff_ffff_ffff,
20//     0xffff_ffff_ffff_ffff,
21//     0x0fff_ffff_ffff_ffff,
22// ]);
23
24const EDWARDS_D: FieldElement = FieldElement(U256::from_limbs([
25    0x75eb_4dca_1359_78a3,
26    0x0070_0a4d_4141_d8ab,
27    0x8cc7_4079_7779_e898,
28    0x5203_6cee_2b6f_fe73,
29]));
30
31/// R = 2^256 mod L, used for fast scalar reduction.
32const R: U256 = U256::from_limbs([
33    0xd6ec_3174_8d98_951d,
34    0xc6ef_5bf4_737d_cf70,
35    0xffff_ffff_ffff_fffe,
36    0x0fff_ffff_ffff_ffff,
37]);
38
39/// Barrett µ = floor(2^512 / L), used for fast wide reduction modulo L.
40const BAR_MU: [u64; 5] = [
41    0xed9c_e5a3_0a2c_131b,
42    0x2106_215d_0863_29a7,
43    0xffff_ffff_ffff_ffeb,
44    0xffff_ffff_ffff_ffff,
45    0x0000_0000_0000_000f,
46];
47
48const EDWARDS_2D: FieldElement = FieldElement(U256::from_limbs([
49    0xebd6_9b94_26b2_f159,
50    0x00e0_149a_8283_b156,
51    0x198e_80f2_eef3_d130,
52    0x2406_d9dc_56df_fce7,
53]));
54
55const SQRT_M1: FieldElement = FieldElement(U256::from_limbs([
56    0xc4ee_1b27_4a0e_a0b0,
57    0x2f43_1806_ad2f_e478,
58    0x2b4d_0099_3dfb_d7a7,
59    0x2b83_2480_4fc1_df0b,
60]));
61
62const BASEPOINT: EdwardsPoint = EdwardsPoint {
63    x: FieldElement(U256::from_limbs([
64        0xc9562d608f25d51a,
65        0x692cc7609525a7b2,
66        0xc0a4e231fdd6dc5c,
67        0x216936d3cd6e53fe,
68    ])),
69    y: FieldElement(U256::from_limbs([
70        0x6666666666666658,
71        0x6666666666666666,
72        0x6666666666666666,
73        0x6666666666666666,
74    ])),
75    z: FieldElement(U256::from_limbs([
76        0x0000000000000001,
77        0x0000000000000000,
78        0x0000000000000000,
79        0x0000000000000000,
80    ])),
81    t: FieldElement(U256::from_limbs([
82        0x6dde8ab3a5b7dda3,
83        0x20f09f80775152f5,
84        0x66ea4e8e64abe37d,
85        0x67875f0fd78b7665,
86    ])),
87};
88
89/// Ed25519 signing key (RFC 8032).
90///
91/// # Generating a key
92///
93/// ```ignore
94/// use crypto::curve25519::ed25519::SecretKey;
95///
96/// let priv_key = SecretKey::generate();
97/// let pub_key = priv_key.public_key();
98/// ```
99///
100/// # Signing and verification
101///
102/// ```ignore
103/// use crypto::curve25519::ed25519::SecretKey;
104///
105/// let priv_key = SecretKey::generate();
106/// let pub_key = priv_key.public_key();
107/// let sig = priv_key.sign(b"message");
108/// assert!(pub_key.verify(b"message", &sig).is_ok());
109/// ```
110// TODO: zeroize
111#[derive(Clone, Debug, PartialEq, Eq)]
112pub struct SecretKey {
113    seed: [u8; SECRET_KEY_SIZE],
114    scalar: Scalar,
115    prefix: [u8; 32],
116    public_point: EdwardsPoint,
117    public_bytes: [u8; PUBLIC_KEY_SIZE],
118}
119
120impl SecretKey {
121    #[cfg(feature = "random")]
122    pub fn generate() -> SecretKey {
123        let seed: [u8; SECRET_KEY_SIZE] = crate::random::random_bytes();
124        SecretKey::from_bytes(&seed)
125    }
126
127    pub fn from_bytes(seed: &[u8; SECRET_KEY_SIZE]) -> SecretKey {
128        let (scalar, prefix) = expand_secret(seed);
129        let public_point = scalar_mul_base(&scalar);
130        let public_bytes = public_point
131            .to_bytes()
132            .expect("basepoint multiplication must produce a valid point");
133        SecretKey {
134            seed: *seed,
135            scalar,
136            prefix,
137            public_point,
138            public_bytes,
139        }
140    }
141
142    // pub fn from_seed_unchecked(seed: &[u8; PRIVATE_KEY_SIZE]) -> SecretKey {
143    //     SecretKey::from_bytes(seed)
144    // }
145
146    pub fn sign(&self, message: &[u8]) -> [u8; SIGNATURE_SIZE] {
147        let r = hash_to_scalar(&[&self.prefix, message]);
148        let r_point = scalar_mul_base(&r)
149            .to_bytes()
150            .expect("basepoint multiplication must produce a valid point");
151
152        let k = hash_to_scalar(&[&r_point, &self.public_bytes, message]);
153        let s = r.add(k.mul(self.scalar));
154
155        let mut signature = [0u8; SIGNATURE_SIZE];
156        signature[..32].copy_from_slice(&r_point);
157        signature[32..].copy_from_slice(&s.to_bytes());
158        signature
159    }
160
161    #[inline]
162    pub fn to_bytes(&self) -> [u8; SECRET_KEY_SIZE] {
163        self.seed
164    }
165
166    #[inline]
167    pub fn public_key(&self) -> PublicKey {
168        PublicKey {
169            point: self.public_point,
170            bytes: self.public_bytes,
171        }
172    }
173}
174
175impl From<&[u8; SECRET_KEY_SIZE]> for SecretKey {
176    fn from(bytes: &[u8; SECRET_KEY_SIZE]) -> Self {
177        Self::from_bytes(bytes)
178    }
179}
180
181impl TryFrom<&[u8]> for SecretKey {
182    type Error = EllipticCurveError;
183
184    fn try_from(bytes: &[u8]) -> Result<Self, Self::Error> {
185        Ok(Self::from_bytes(bytes.try_into().map_err(|_| EllipticCurveError::InvalidKey)?))
186    }
187}
188
189/// Ed25519 public key for signature verification (RFC 8032).
190///
191/// # Verifying a signature
192///
193/// ```ignore
194/// use crypto::curve25519::ed25519::{PublicKey, SecretKey};
195///
196/// let priv_key = SecretKey::generate();
197/// let pub_key = priv_key.public_key();
198/// let sig = priv_key.sign(b"message");
199/// assert!(pub_key.verify(b"message", &sig).is_ok());
200/// ```
201///
202/// # Deserializing from bytes
203///
204/// ```ignore
205/// use crypto::curve25519::ed25519::PublicKey;
206///
207/// let bytes = [0u8; 32]; // replace with a real public key
208/// let pub_key = PublicKey::from_bytes(&bytes);
209/// ```
210#[derive(Clone, Debug, PartialEq, Eq)]
211pub struct PublicKey {
212    point: EdwardsPoint,
213    bytes: [u8; PUBLIC_KEY_SIZE],
214}
215
216impl PublicKey {
217    pub fn from_bytes(key: &[u8; PUBLIC_KEY_SIZE]) -> Result<PublicKey, EllipticCurveError> {
218        let point = EdwardsPoint::from_bytes(key.try_into().unwrap()).ok_or(EllipticCurveError::InvalidKey)?;
219        Ok(PublicKey {
220            point,
221            bytes: *key,
222        })
223    }
224
225    pub fn verify(&self, message: &[u8], signature: &[u8; SIGNATURE_SIZE]) -> Result<(), EllipticCurveError> {
226        ed25519_verify(&self.point, message, signature)
227    }
228
229    #[inline]
230    pub fn to_bytes(&self) -> [u8; PUBLIC_KEY_SIZE] {
231        self.bytes
232    }
233
234    pub fn to_montgomery_u(&self) -> Option<FieldElement> {
235        let inv_z = self.point.z.invert()?;
236        let y = self.point.y.mul(inv_z);
237        let one = FieldElement::ONE;
238        let u = (one.add(y)).mul((one.sub(y)).invert()?);
239        Some(u)
240    }
241}
242
243impl TryFrom<&[u8]> for PublicKey {
244    type Error = EllipticCurveError;
245
246    fn try_from(bytes: &[u8]) -> Result<Self, Self::Error> {
247        Self::from_bytes(bytes.try_into().map_err(|_| EllipticCurveError::InvalidKey)?)
248    }
249}
250
251#[derive(Clone, Copy, Debug, PartialEq, Eq)]
252struct Scalar(U256);
253
254impl Scalar {
255    fn from_canonical_bytes(bytes: &[u8; 32]) -> Option<Self> {
256        let value = U256::from_le_slice(bytes);
257        if value.ct_ge(&MODULUS_L) {
258            None
259        } else {
260            Some(Self(value))
261        }
262    }
263
264    /// Reduce an arbitrary-length byte sequence modulo L (the ed25519 subgroup order).
265    ///
266    /// Two fast paths:
267    /// - <= 32 bytes: parse as U256 and repeatedly conditionally subtract L (at most 16 times,
268    ///   since a 256-bit value is < 16·L). Constant-time via ct_select.
269    /// - > 32 bytes: Horner evaluation in base 2^256. Split into 32-byte chunks processed
270    ///   from most significant to least, using the precomputed R = 2^256 mod L for shifting
271    ///   and the Barrett constant µ for fast modular multiplication of the accumulator by R.
272    fn reduce_bytes_mod_l(bytes: &[u8]) -> Self {
273        let len = bytes.len();
274        if len <= 32 {
275            let mut padded = [0u8; 32];
276            padded[..len].copy_from_slice(bytes);
277            let val = U256::from_le_slice(&padded);
278            let mut result = val;
279            let mut i = 16;
280            while i > 0 {
281                let (diff, borrow) = result.sub_raw(&MODULUS_L);
282                result = U256::ct_select(&diff, &result, borrow == 0);
283                i -= 1;
284            }
285            Self(result)
286        } else {
287            let chunk_count = (len + 31) / 32;
288            let mut acc = U256::ZERO;
289            let mut chunk_idx = chunk_count;
290            while chunk_idx > 0 {
291                chunk_idx -= 1;
292                let chunk_start = chunk_idx * 32;
293                let chunk_end = usize::min(chunk_start + 32, len);
294                let chunk_len = chunk_end - chunk_start;
295
296                if !acc.is_zero() {
297                    acc = acc.mul_mod_barrett(&R, &MODULUS_L, &BAR_MU);
298                }
299
300                let mut padded = [0u8; 32];
301                padded[..chunk_len].copy_from_slice(&bytes[chunk_start..chunk_end]);
302                let mut chunk_reduced = U256::from_le_slice(&padded);
303                let mut j = 16;
304                while j > 0 {
305                    let (diff, borrow) = chunk_reduced.sub_raw(&MODULUS_L);
306                    chunk_reduced = U256::ct_select(&diff, &chunk_reduced, borrow == 0);
307                    j -= 1;
308                }
309
310                acc = acc.add_mod(&chunk_reduced, &MODULUS_L);
311            }
312            Self(acc)
313        }
314    }
315
316    #[inline]
317    fn to_bytes(self) -> [u8; 32] {
318        self.0.to_le_bytes_fixed::<32>()
319    }
320
321    #[inline]
322    fn add(self, rhs: Self) -> Self {
323        Self(self.0.add_mod(&rhs.0, &MODULUS_L))
324    }
325
326    #[inline]
327    fn mul(self, rhs: Self) -> Self {
328        Self(self.0.mul_mod_barrett(&rhs.0, &MODULUS_L, &BAR_MU))
329    }
330}
331
332#[derive(Clone, Copy, Debug, PartialEq, Eq)]
333struct EdwardsPoint {
334    x: FieldElement,
335    y: FieldElement,
336    z: FieldElement,
337    t: FieldElement,
338}
339
340impl EdwardsPoint {
341    #[inline]
342    fn identity() -> Self {
343        Self {
344            x: FieldElement::ZERO,
345            y: FieldElement::ONE,
346            z: FieldElement::ONE,
347            t: FieldElement::ZERO,
348        }
349    }
350
351    #[inline]
352    fn from_affine(x: FieldElement, y: FieldElement) -> Self {
353        Self {
354            x,
355            y,
356            z: FieldElement::ONE,
357            t: x.mul(y),
358        }
359    }
360
361    fn from_bytes(bytes: &[u8; 32]) -> Option<Self> {
362        let sign = (bytes[31] >> 7) == 1;
363        let mut y_bytes = *bytes;
364        y_bytes[31] &= 0x7f;
365        let y = FieldElement::from_canonical_bytes(&y_bytes)?;
366        let y2 = y.square();
367        let u = y2.sub(FieldElement::ONE);
368        let v = EDWARDS_D.mul(y2).add(FieldElement::ONE);
369        let x2 = u.mul(v.invert()?);
370        let mut x = sqrt(&x2)?;
371        if x.is_zero() && sign {
372            return None;
373        }
374        if x.is_odd() != sign {
375            x = x.negate();
376        }
377        Some(Self::from_affine(x, y))
378    }
379
380    fn to_bytes(self) -> Option<[u8; 32]> {
381        let inv_z = self.z.invert()?;
382        let x = self.x.mul(inv_z);
383        let y = self.y.mul(inv_z);
384        let mut out = y.to_bytes();
385        if x.is_odd() {
386            out[31] |= 0x80;
387        }
388        Some(out)
389    }
390
391    #[inline]
392    fn add(&self, rhs: &Self) -> Self {
393        let a = self.y.sub(self.x).mul(rhs.y.sub(rhs.x));
394        let b = self.y.add(self.x).mul(rhs.y.add(rhs.x));
395        let c = self.t.mul(rhs.t).mul(EDWARDS_2D);
396        let z1z2 = self.z.mul(rhs.z);
397        let d = z1z2.add(z1z2);
398        let e = b.sub(a);
399        let f = d.sub(c);
400        let g = d.add(c);
401        let h = b.add(a);
402        Self {
403            x: e.mul(f),
404            y: g.mul(h),
405            t: e.mul(h),
406            z: f.mul(g),
407        }
408    }
409
410    #[inline]
411    fn double(&self) -> Self {
412        let a = self.x.square();
413        let b = self.y.square();
414        let z2 = self.z.square();
415        let c = z2.add(z2);
416        let d = a.negate();
417        let e = self.x.add(self.y).square().sub(a).sub(b);
418        let g = d.add(b);
419        let f = g.sub(c);
420        let h = d.sub(b);
421        Self {
422            x: e.mul(f),
423            y: g.mul(h),
424            t: e.mul(h),
425            z: f.mul(g),
426        }
427    }
428
429    #[inline]
430    fn select(a: &Self, b: &Self, choice: bool) -> Self {
431        Self {
432            x: FieldElement::select(&a.x, &b.x, choice),
433            y: FieldElement::select(&a.y, &b.y, choice),
434            z: FieldElement::select(&a.z, &b.z, choice),
435            t: FieldElement::select(&a.t, &b.t, choice),
436        }
437    }
438
439    #[inline]
440    fn mul_by_cofactor(&self) -> Self {
441        self.double().double().double()
442    }
443}
444
445#[inline]
446fn sqrt(a: &FieldElement) -> Option<FieldElement> {
447    let mut candidate = a.pow_sqrt_exponent();
448    if !candidate.square().ct_eq(a) {
449        candidate = candidate.mul(SQRT_M1);
450    }
451    if candidate.square().ct_eq(a) {
452        Some(candidate)
453    } else {
454        None
455    }
456}
457
458fn scalar_mul(point: &EdwardsPoint, scalar: &Scalar) -> EdwardsPoint {
459    let mut table = [EdwardsPoint::identity(); 16];
460    table[1] = *point;
461    let mut i = 2;
462    while i < 16 {
463        table[i] = table[i - 1].add(point);
464        i += 1;
465    }
466
467    scalar_mul_table(&table, scalar)
468}
469
470/// Optimized version of `scalar_mul` for `BASEPOINT` using a pre-computed table.
471#[cfg(feature = "std")]
472fn scalar_mul_base(scalar: &Scalar) -> EdwardsPoint {
473    use std::sync::LazyLock;
474    static TABLE: LazyLock<[EdwardsPoint; 16]> = LazyLock::new(|| {
475        let mut t = [EdwardsPoint::identity(); 16];
476        t[1] = BASEPOINT;
477        let mut i = 2;
478        while i < 16 {
479            t[i] = t[i - 1].add(&BASEPOINT);
480            i += 1;
481        }
482        t
483    });
484
485    scalar_mul_table(&TABLE, scalar)
486}
487
488#[cfg(not(feature = "std"))]
489#[inline]
490fn scalar_mul_base(scalar: &Scalar) -> EdwardsPoint {
491    scalar_mul(&BASEPOINT, scalar)
492}
493
494#[inline]
495fn scalar_mul_table(table: &[EdwardsPoint; 16], scalar: &Scalar) -> EdwardsPoint {
496    let mut result = EdwardsPoint::identity();
497    let mut win = 63;
498    loop {
499        let idx = scalar_window(scalar, win);
500        let selected = ct_select_from_table(&table, idx);
501        result = result.add(&selected);
502        if win == 0 {
503            break;
504        }
505        result = result.double().double().double().double();
506        win -= 1;
507    }
508    result
509}
510
511#[inline]
512fn ct_select_from_table(table: &[EdwardsPoint; 16], index: usize) -> EdwardsPoint {
513    let mut result = table[0];
514    let mut i = 1;
515    while i < 16 {
516        let diff = i ^ index;
517        let choice = ((diff.wrapping_sub(1) >> (usize::BITS - 1)) & 1) != 0;
518        result = EdwardsPoint::select(&table[i], &result, choice);
519        i += 1;
520    }
521    result
522}
523
524#[inline]
525fn scalar_window(scalar: &Scalar, window: usize) -> usize {
526    let bit_pos = window * 4;
527    let limb_idx = bit_pos / 64;
528    let limb = scalar.0.limbs[limb_idx];
529    ((limb >> (bit_pos % 64)) & 0xf) as usize
530}
531
532fn hash_to_scalar(parts: &[&[u8]]) -> Scalar {
533    let mut hasher = Sha512::new();
534    let mut i = 0usize;
535    while i < parts.len() {
536        hasher.update(parts[i]);
537        i += 1;
538    }
539    let digest = hasher.sum();
540    Scalar::reduce_bytes_mod_l(digest.as_ref())
541}
542
543fn expand_secret(private_key: &[u8; SECRET_KEY_SIZE]) -> (Scalar, [u8; 32]) {
544    let mut digest = Sha512::hash(private_key);
545    let digest: &mut [u8; 64] = digest.as_mut().try_into().unwrap();
546
547    digest[0] &= 248;
548    digest[31] &= 63;
549    digest[31] |= 64;
550
551    let scalar = Scalar::reduce_bytes_mod_l(&digest[..32]);
552    let mut prefix = [0u8; 32];
553    prefix.copy_from_slice(&digest[32..]);
554    (scalar, prefix)
555}
556
557fn ed25519_verify(
558    point: &EdwardsPoint,
559    message: &[u8],
560    signature: &[u8; SIGNATURE_SIZE],
561) -> Result<(), EllipticCurveError> {
562    let r_bytes: &[u8; 32] = &signature[..32].try_into().unwrap();
563    let r = EdwardsPoint::from_bytes(r_bytes).ok_or(EllipticCurveError::InvalidSignature)?;
564
565    let s =
566        Scalar::from_canonical_bytes(&signature[32..].try_into().unwrap()).ok_or(EllipticCurveError::Unspecified)?;
567
568    let k = hash_to_scalar(&[
569        r_bytes,
570        &point.to_bytes().ok_or(EllipticCurveError::Unspecified)?,
571        message,
572    ]);
573
574    let lhs = scalar_mul_base(&s).mul_by_cofactor();
575    let rhs = r.add(&scalar_mul(point, &k)).mul_by_cofactor();
576
577    // SAFETY: this is okay to use non-contant time compare because
578    match (lhs.to_bytes(), rhs.to_bytes()) {
579        (Some(lhs), Some(rhs)) if constant_time_eq(&lhs, &rhs) => Ok(()),
580        _ => Err(EllipticCurveError::InvalidSignature),
581    }
582}
583
584#[cfg(test)]
585mod tests {
586    use super::*;
587    use crate::curve25519::x25519;
588
589    const BASEPOINT_COMPRESSED: [u8; 32] = [
590        0x58, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
591        0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
592    ];
593
594    fn decode_hex<const N: usize>(hex_bytes: &str) -> [u8; N] {
595        let bytes = hex::decode(hex_bytes).unwrap();
596        assert_eq!(bytes.len(), N);
597        let mut out = [0u8; N];
598        out.copy_from_slice(&bytes);
599        out
600    }
601
602    fn decode_hex_vec(hex_bytes: &str) -> Vec<u8> {
603        hex::decode(hex_bytes).unwrap()
604    }
605
606    #[test]
607    fn sign_verify_roundtrip() {
608        let seed = decode_hex::<32>("9d61b19deffd5a60ba844af492ec2cc44449c5697b326919703bac031cae7f60");
609        let priv_key = SecretKey::from_bytes(&seed);
610        let pub_key = priv_key.public_key();
611
612        let messages: [&[u8]; 4] = [b"", b"hello", b"test message", &[0xffu8; 256]];
613        for msg in &messages {
614            let sig = priv_key.sign(msg);
615            assert!(pub_key.verify(msg, &sig).is_ok());
616            assert!(pub_key.verify(b"wrong", &sig).is_err());
617        }
618    }
619
620    #[test]
621    fn public_key_bytes_roundtrip() {
622        let seed = decode_hex::<32>("9d61b19deffd5a60ba844af492ec2cc44449c5697b326919703bac031cae7f60");
623        let priv_key = SecretKey::from_bytes(&seed);
624        let pub_key = priv_key.public_key();
625        let pub_bytes = pub_key.to_bytes();
626        let restored = PublicKey::from_bytes(&pub_bytes).unwrap();
627        assert_eq!(pub_bytes, restored.to_bytes());
628    }
629
630    #[test]
631    fn private_key_bytes_roundtrip() {
632        let seed = decode_hex::<32>("9d61b19deffd5a60ba844af492ec2cc44449c5697b326919703bac031cae7f60");
633        let priv_key = SecretKey::from_bytes(&seed);
634        assert_eq!(priv_key.to_bytes(), seed);
635    }
636
637    #[test]
638    fn generate_produces_valid_keys() {
639        let priv_key = SecretKey::generate();
640        let pub_key = priv_key.public_key();
641        let sig = priv_key.sign(b"hello");
642        assert!(pub_key.verify(b"hello", &sig).is_ok());
643    }
644
645    #[test]
646    fn rejects_invalid_public_key() {
647        assert!(PublicKey::from_bytes(&[0xffu8; 32]).is_err());
648        let p_enc = decode_hex::<32>("edffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f");
649        assert!(PublicKey::from_bytes(&p_enc).is_err());
650    }
651
652    fn check_vector(
653        seed_hex: &'static str,
654        public_key_hex: &'static str,
655        message_hex: &'static str,
656        signature_hex: &'static str,
657    ) {
658        let seed = decode_hex::<32>(seed_hex);
659        let pk_expected = decode_hex::<32>(public_key_hex);
660        let sig_expected = decode_hex::<64>(signature_hex);
661        let msg = decode_hex_vec(message_hex);
662
663        let priv_key = SecretKey::from_bytes(&seed);
664        assert_eq!(priv_key.public_key().to_bytes(), pk_expected);
665        assert_eq!(priv_key.sign(&msg), sig_expected);
666        assert!(priv_key.public_key().verify(&msg, &sig_expected).is_ok());
667    }
668
669    #[test]
670    fn rfc8032_vectors() {
671        check_vector(
672            "9d61b19deffd5a60ba844af492ec2cc44449c5697b326919703bac031cae7f60",
673            "d75a980182b10ab7d54bfed3c964073a0ee172f3daa62325af021a68f707511a",
674            "",
675            "e5564300c360ac729086e2cc806e828a84877f1eb8e5d974d873e065224901555fb8821590a33bacc61e39701cf9b46bd25bf5f0595bbe24655141438e7a100b",
676        );
677        check_vector(
678            "4ccd089b28ff96da9db6c346ec114e0f5b8a319f35aba624da8cf6ed4fb8a6fb",
679            "3d4017c3e843895a92b70aa74d1b7ebc9c982ccf2ec4968cc0cd55f12af4660c",
680            "72",
681            "92a009a9f0d4cab8720e820b5f642540a2b27b5416503f8fb3762223ebdb69da085ac1e43e15996e458f3613d0f11d8c387b2eaeb4302aeeb00d291612bb0c00",
682        );
683        check_vector(
684            "c5aa8df43f9f837bedb7442f31dcb7b166d38535076f094b85ce3a2e0b4458f7",
685            "fc51cd8e6218a1a38da47ed00230f0580816ed13ba3303ac5deb911548908025",
686            "af82",
687            "6291d657deec24024827e69c3abe01a30ce548a284743a445e3680d7db5ac3ac18ff9b538d16f290ae67f760984dc6594a7c15e9716ed28dc027beceea1ec40a",
688        );
689    }
690
691    #[test]
692    fn go_golden_vectors() {
693        let data = include_str!("../../testdata/ed25519/sign.input");
694
695        for line in data.lines() {
696            let mut parts = line.split(':');
697            let private_and_public = parts.next().unwrap();
698            let public_key = parts.next().unwrap();
699            let message = parts.next().unwrap();
700            let signature_with_message = parts.next().unwrap();
701            assert!(parts.next().is_some());
702            assert!(parts.next().is_none());
703
704            check_vector(&private_and_public[..64], public_key, message, &signature_with_message[..128]);
705        }
706    }
707
708    #[test]
709    fn verify_rejects_tampering_and_non_canonical_s() {
710        let seed = decode_hex::<32>("9d61b19deffd5a60ba844af492ec2cc44449c5697b326919703bac031cae7f60");
711        let pub_key = SecretKey::from_bytes(&seed).public_key();
712        let signature = SecretKey::from_bytes(&seed).sign(b"message");
713
714        assert!(pub_key.verify(b"message", &signature).is_ok());
715        assert!(pub_key.verify(b"tampered", &signature).is_err());
716
717        let mut bad_signature = signature;
718        bad_signature[0] ^= 0x80;
719        assert!(pub_key.verify(b"message", &bad_signature).is_err());
720
721        let mut non_canonical_s = signature;
722        non_canonical_s[32..].copy_from_slice(&[
723            0xed, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58, 0xd6, 0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde, 0x14, 0x00, 0x00,
724            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10,
725        ]);
726        assert!(pub_key.verify(b"message", &non_canonical_s).is_err());
727    }
728
729    #[test]
730    fn public_key_validation_rejects_invalid_encodings() {
731        let valid = decode_hex::<32>("d75a980182b10ab7d54bfed3c964073a0ee172f3daa62325af021a68f707511a");
732        assert!(PublicKey::from_bytes(&valid).is_ok());
733
734        let mut invalid = [0xffu8; 32];
735        assert!(PublicKey::from_bytes(&invalid).is_err());
736
737        invalid = valid;
738        invalid[31] |= 0x80;
739        invalid[..31].fill(0);
740        assert!(PublicKey::from_bytes(&invalid).is_err());
741    }
742
743    #[test]
744    fn cctv_ed25519_vectors() {
745        let data = include_str!("../../testdata/ed25519/cctv_vectors.txt");
746
747        for line in data.lines() {
748            let parts: Vec<&str> = line.split(':').collect();
749            assert_eq!(parts.len(), 5, "malformed line: {line}");
750            let number = parts[0];
751            let key_hex = parts[1];
752            let sig_hex = parts[2];
753            let msg_hex = parts[3];
754            let flags_str = parts[4];
755
756            let flags: Vec<&str> = if flags_str.is_empty() {
757                vec![]
758            } else {
759                flags_str.split(',').collect()
760            };
761
762            let has_non_canonical_a = flags.contains(&"non_canonical_A");
763            let has_non_canonical_r = flags.contains(&"non_canonical_R");
764            let should_reject = has_non_canonical_a || has_non_canonical_r;
765
766            let public_key = decode_hex::<32>(key_hex);
767            let signature = decode_hex::<64>(sig_hex);
768            let message = decode_hex_vec(msg_hex);
769
770            let pub_key = PublicKey::from_bytes(&public_key);
771            let result = pub_key.and_then(|pk| pk.verify(&message, &signature));
772
773            if should_reject {
774                assert!(
775                    result.is_err(),
776                    "vector #{number} should be rejected (flags: {flags_str}) but was accepted",
777                );
778            } else {
779                assert!(
780                    result.is_ok(),
781                    "vector #{number} should be accepted (flags: {flags_str}) but was rejected",
782                );
783            }
784        }
785    }
786
787    #[test]
788    fn rfc8032_extended_vectors() {
789        check_vector(
790            "833fe62409237b9d62ec77587520911e9a759cec1d19755b7da901b96dca3d42",
791            "ec172b93ad5e563bf4932c70e1245034c35467ef2efd4d64ebf819683467e2bf",
792            "ddaf35a193617abacc417349ae20413112e6fa4e89a97ea20a9eeee64b55d39a2192992a274fc1a836ba3c23a3feebbd454d4423643ce80e2a9ac94fa54ca49f",
793            "dc2a4459e7369633a52b1bf277839a00201009a3efbf3ecb69bea2186c26b58909351fc9ac90b3ecfdfbc7c66431e0303dca179c138ac17ad9bef1177331a704",
794        );
795    }
796
797    #[test]
798    fn verify_rejects_all_zero_signature() {
799        let public_key = decode_hex::<32>("d75a980182b10ab7d54bfed3c964073a0ee172f3daa62325af021a68f707511a");
800        let signature = [0u8; 64];
801        let pk = PublicKey::from_bytes(&public_key).unwrap();
802        let result = pk.verify(b"test", &signature);
803        assert!(result.is_err());
804    }
805
806    #[test]
807    fn verify_rejects_s_equals_l() {
808        let seed = decode_hex::<32>("9d61b19deffd5a60ba844af492ec2cc44449c5697b326919703bac031cae7f60");
809        let pub_key = SecretKey::from_bytes(&seed).public_key();
810        let signature = SecretKey::from_bytes(&seed).sign(b"test");
811
812        let mut bad_sig = signature;
813        bad_sig[32..].copy_from_slice(&[
814            0xed, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58, 0xd6, 0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde, 0x14, 0x00, 0x00,
815            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10,
816        ]);
817        assert!(pub_key.verify(b"test", &bad_sig).is_err());
818    }
819
820    #[test]
821    fn verify_rejects_non_canonical_point_encodings() {
822        let non_canonical_key = decode_hex::<32>("edffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f");
823        assert!(PublicKey::from_bytes(&non_canonical_key).is_err());
824
825        let seed = decode_hex::<32>("9d61b19deffd5a60ba844af492ec2cc44449c5697b326919703bac031cae7f60");
826        let pub_key = SecretKey::from_bytes(&seed).public_key();
827        let mut bad_sig = SecretKey::from_bytes(&seed).sign(b"test");
828        bad_sig[..32].copy_from_slice(&[
829            0xed, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
830            0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f,
831        ]);
832        assert!(pub_key.verify(b"test", &bad_sig).is_err());
833    }
834
835    #[test]
836    fn edwards_identity_point_roundtrip() {
837        let id_bytes = [
838            0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
839            0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
840        ];
841        let point = EdwardsPoint::from_bytes(&id_bytes).unwrap();
842        let roundtripped = point.to_bytes().unwrap();
843        assert_eq!(roundtripped, id_bytes);
844    }
845
846    #[test]
847    fn ed25519_to_montgomery_u_conversion() {
848        let seed = decode_hex::<32>("9d61b19deffd5a60ba844af492ec2cc44449c5697b326919703bac031cae7f60");
849        let priv_key = SecretKey::from_bytes(&seed);
850        let ed_pub = priv_key.public_key();
851
852        let u = ed_pub
853            .to_montgomery_u()
854            .expect("valid ed point must convert to montgomery u");
855        let u_bytes = u.to_bytes();
856
857        let x_pub_from_ed = x25519::PublicKey::try_from(&ed_pub).unwrap();
858        assert_eq!(u_bytes, x_pub_from_ed.to_bytes());
859
860        assert_ne!(u_bytes, [0u8; 32], "montgomery u must be non-zero for non-identity point");
861    }
862
863    #[test]
864    fn rfc8032_test_1024() {
865        check_vector(
866            "f5e5767cf153319517630f226876b86c8160cc583bc013744c6bf255f5cc0ee5",
867            "278117fc144c72340f67d0f2316e8386ceffbf2b2428c9c51fef7c597f1d426e",
868            "08b8b2b733424243760fe426a4b54908632110a66c2f6591eabd3345e3e4eb98fa6e264bf09efe12ee50f8f54e9f77b1e355f6c50544e23fb1433ddf73be84d879de7c0046dc4996d9e773f4bc9efe5738829adb26c81b37c93a1b270b20329d658675fc6ea534e0810a4432826bf58c941efb65d57a338bbd2e26640f89ffbc1a858efcb8550ee3a5e1998bd177e93a7363c344fe6b199ee5d02e82d522c4feba15452f80288a821a579116ec6dad2b3b310da903401aa62100ab5d1a36553e06203b33890cc9b832f79ef80560ccb9a39ce767967ed628c6ad573cb116dbefefd75499da96bd68a8a97b928a8bbc103b6621fcde2beca1231d206be6cd9ec7aff6f6c94fcd7204ed3455c68c83f4a41da4af2b74ef5c53f1d8ac70bdcb7ed185ce81bd84359d44254d95629e9855a94a7c1958d1f8ada5d0532ed8a5aa3fb2d17ba70eb6248e594e1a2297acbbb39d502f1a8c6eb6f1ce22b3de1a1f40cc24554119a831a9aad6079cad88425de6bde1a9187ebb6092cf67bf2b13fd65f27088d78b7e883c8759d2c4f5c65adb7553878ad575f9fad878e80a0c9ba63bcbcc2732e69485bbc9c90bfbd62481d9089beccf80cfe2df16a2cf65bd92dd597b0707e0917af48bbb75fed413d238f5555a7a569d80c3414a8d0859dc65a46128bab27af87a71314f318c782b23ebfe808b82b0ce26401d2e22f04d83d1255dc51addd3b75a2b1ae0784504df543af8969be3ea7082ff7fc9888c144da2af58429ec96031dbcad3dad9af0dcbaaaf268cb8fcffead94f3c7ca495e056a9b47acdb751fb73e666c6c655ade8297297d07ad1ba5e43f1bca32301651339e22904cc8c42f58c30c04aafdb038dda0847dd988dcda6f3bfd15c4b4c4525004aa06eeff8ca61783aacec57fb3d1f92b0fe2fd1a85f6724517b65e614ad6808d6f6ee34dff7310fdc82aebfd904b01e1dc54b2927094b2db68d6f903b68401adebf5a7e08d78ff4ef5d63653a65040cf9bfd4aca7984a74d37145986780fc0b16ac451649de6188a7dbdf191f64b5fc5e2ab47b57f7f7276cd419c17a3ca8e1b939ae49e488acba6b965610b5480109c8b17b80e1b7b750dfc7598d5d5011fd2dcc5600a32ef5b52a1ecc820e308aa342721aac0943bf6686b64b2579376504ccc493d97e6aed3fb0f9cd71a43dd497f01f17c0e2cb3797aa2a2f256656168e6c496afc5fb93246f6b1116398a346f1a641f3b041e989f7914f90cc2c7fff357876e506b50d334ba77c225bc307ba537152f3f1610e4eafe595f6d9d90d11faa933a15ef1369546868a7f3a45a96768d40fd9d03412c091c6315cf4fde7cb68606937380db2eaaa707b4c4185c32eddcdd306705e4dc1ffc872eeee475a64dfac86aba41c0618983f8741c5ef68d3a101e8a3b8cac60c905c15fc910840b94c00a0b9d0",
869            "0aab4c900501b3e24d7cdf4663326a3a87df5e4843b2cbdb67cbf6e460fec350aa5371b1508f9f4528ecea23c436d94b5e8fcd4f681e30a6ac00a9704a188a03",
870        );
871    }
872
873    #[test]
874    fn wycheproof_ed25519_vectors() {
875        #[derive(serde::Deserialize)]
876        struct TestJson {
877            #[serde(rename = "testGroups")]
878            test_groups: Vec<TestGroup>,
879        }
880
881        #[derive(serde::Deserialize)]
882        struct TestGroup {
883            #[serde(rename = "publicKey")]
884            public_key: PublicKeyJson,
885            tests: Vec<TestCase>,
886        }
887
888        #[derive(serde::Deserialize)]
889        struct PublicKeyJson {
890            pk: String,
891        }
892
893        #[derive(serde::Deserialize)]
894        struct TestCase {
895            #[serde(rename = "tcId")]
896            tc_id: u32,
897            // #[allow(dead_code)]
898            // comment: String,
899            msg: String,
900            sig: String,
901            result: String,
902        }
903
904        let data = include_str!("../../testdata/wycheproof/testvectors_v1/ed25519_test.json");
905        let parsed: TestJson = serde_json::from_str(data).unwrap();
906
907        let mut valid_tested = 0usize;
908        let mut invalid_tested = 0usize;
909        let mut skipped = 0usize;
910
911        for group in &parsed.test_groups {
912            let public_key = decode_hex::<32>(&group.public_key.pk);
913            let pk = PublicKey::from_bytes(&public_key).unwrap();
914
915            for test in &group.tests {
916                let msg = decode_hex_vec(&test.msg);
917                let sig_hex = &test.sig;
918                if sig_hex.len() != 128 {
919                    skipped += 1;
920                    continue;
921                }
922                let signature = decode_hex::<64>(sig_hex);
923                let should_be_valid = test.result == "valid";
924
925                let result = pk.verify(&msg, &signature);
926                if should_be_valid {
927                    assert!(
928                        result.is_ok(),
929                        "Wycheproof test #{}: expected valid but got {:?}",
930                        test.tc_id,
931                        result,
932                    );
933                    valid_tested += 1;
934                } else {
935                    assert!(result.is_err(), "Wycheproof test #{}: expected invalid but got ok", test.tc_id,);
936                    invalid_tested += 1;
937                }
938            }
939        }
940
941        assert!(valid_tested > 0, "must test at least one valid Wycheproof vector");
942        assert!(invalid_tested > 0, "must test at least one invalid Wycheproof vector");
943        assert!(skipped > 0, "some truncated signatures should be skipped");
944
945        eprintln!("Wycheproof ed25519: {valid_tested} valid, {invalid_tested} invalid, {skipped} skipped");
946    }
947
948    #[test]
949    fn sign_verify_roundtrip_various_lengths() {
950        let seed = decode_hex::<32>("9d61b19deffd5a60ba844af492ec2cc44449c5697b326919703bac031cae7f60");
951        let priv_key = SecretKey::from_bytes(&seed);
952        let pub_key = priv_key.public_key();
953
954        for len in [0, 1, 2, 16, 32, 64, 128, 255, 256, 1024] {
955            let message: Vec<u8> = (0..len).map(|i| (i & 0xff) as u8).collect();
956            let signature = priv_key.sign(&message);
957            assert!(
958                pub_key.verify(&message, &signature).is_ok(),
959                "roundtrip failed for message length {len}"
960            );
961        }
962    }
963
964    #[test]
965    fn fixed_window_matches_scalar_mul() {
966        for _ in 0..100 {
967            let s = Scalar(U256::from_limbs([
968                rand::random::<u64>(),
969                rand::random::<u64>(),
970                rand::random::<u64>(),
971                rand::random::<u64>(),
972            ]));
973            let s = Scalar(s.0.add_mod(&U256::ZERO, &MODULUS_L));
974            let old_result = scalar_mul(&BASEPOINT, &s);
975            let new_result = scalar_mul_base(&s);
976            assert_eq!(old_result.to_bytes(), new_result.to_bytes(), "mismatch for scalar={:x}", s.0,);
977        }
978    }
979
980    #[test]
981    fn mul_mod_barrett_agrees_with_mul_mod() {
982        for _ in 0..100 {
983            let a = U256::from_limbs([
984                rand::random::<u64>(),
985                rand::random::<u64>(),
986                rand::random::<u64>(),
987                rand::random::<u64>(),
988            ]);
989            let b = U256::from_limbs([
990                rand::random::<u64>(),
991                rand::random::<u64>(),
992                rand::random::<u64>(),
993                rand::random::<u64>(),
994            ]);
995            let slow = a.mul_mod(&b, &MODULUS_L);
996            let fast = a.mul_mod_barrett(&b, &MODULUS_L, &BAR_MU);
997            assert_eq!(slow, fast, "mismatch for a={a:x}, b={b:x}");
998        }
999    }
1000
1001    #[test]
1002    fn basepoint() {
1003        assert_eq!(BASEPOINT, EdwardsPoint::from_bytes(&BASEPOINT_COMPRESSED).unwrap())
1004    }
1005}
crypto/curve25519/ed25519.rs

crypto/curve25519/
ed25519.rs
