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

crypto/curve25519/
ed25519.rs
