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

crypto/curve25519/
ed25519.rs
