const_crypto/ed25519/
mod.rs

1//! Magnetar Fields:
2//!
3//! Most of the code in here and the modules within were copied from
4//! curve curve25519-dalek and adapted to be const. Since the intended
5//! use case of is_on_curve is not intended to be used with any secrets,
6//! there were constant time operations that were replaced with unsafer
7//! counterparts. As such, this is not a cryptographically safe
8//! implementation. It is only intended to be used at compile time with
9//! public keys. For the sake of being as uninvasive as possible, there
10//! are some relic constant time implementations for some operations,
11//! and there may be some misnamed functions.
12//!
13//! There is a test in this module which checks that the is_on_curve
14//! evaluation agrees with a large batch of random keys.
15
16use sha2_const_stable::Sha256;
17
18mod choice;
19mod field_element;
20
21use choice::Choice;
22use field_element::FieldElement;
23
24// ------------------------------------------------------------------------
25// Compressed points
26// ------------------------------------------------------------------------
27
28/// In "Edwards y" / "Ed25519" format, the curve point \\((x,y)\\) is
29/// determined by the \\(y\\)-coordinate and the sign of \\(x\\).
30///
31/// The first 255 bits of a `CompressedEdwardsY` represent the
32/// \\(y\\)-coordinate.  The high bit of the 32nd byte gives the sign of
33/// \\(x\\).
34#[derive(Copy, Clone, Eq, PartialEq, Hash)]
35#[repr(C)]
36pub struct CompressedEdwardsY(pub [u8; 32]);
37
38#[derive(Copy, Clone)]
39#[repr(C)]
40#[allow(non_snake_case)]
41pub struct EdwardsPoint {
42    pub(crate) X: FieldElement,
43    pub(crate) Y: FieldElement,
44    pub(crate) Z: FieldElement,
45    pub(crate) T: FieldElement,
46}
47
48/// Do not use as part of a protocol that deals with secrets!
49/// Only use to evaluate if
50pub const fn crypto_unsafe_is_on_curve(key: &[u8; 32]) -> bool {
51    let (is_valid_y_coord, _, _, _) = decompress_step_1(key);
52
53    // don't need step 2 when checking on curve
54
55    is_valid_y_coord.into()
56}
57
58const PDA_MARKER: &[u8; 21] = b"ProgramDerivedAddress";
59
60pub const fn derive_program_address(seeds: &[&[u8]], program: &[u8; 32]) -> ([u8; 32], u8) {
61    let mut bump = u8::MAX;
62
63    loop {
64        let mut hasher = Sha256::new();
65
66        let mut i = 0;
67        while i < seeds.len() {
68            hasher = hasher.update(seeds[i]);
69            i += 1;
70        }
71        hasher = hasher.update(&[bump]);
72
73        // Solana PDAs also have program id and marker
74        hasher = hasher.update(program);
75        hasher = hasher.update(PDA_MARKER);
76
77        let candidate = hasher.finalize();
78
79        // If off curve, we're done
80        if !crypto_unsafe_is_on_curve(&candidate) {
81            return (candidate, bump);
82        }
83
84        // Otherwise, check next bump
85        bump -= 1;
86    }
87}
88
89#[derive(Clone)]
90pub struct PartialPda {
91    inner: Sha256,
92}
93
94impl PartialPda {
95    pub const fn from_partial_preimage(partial_preimage: &[&[u8]]) -> PartialPda {
96        let mut inner = Sha256::new();
97        let mut i = 0;
98
99        while i != partial_preimage.len() {
100            inner = inner.update(partial_preimage[i]);
101            i += 1
102        }
103
104        PartialPda { inner }
105    }
106
107    pub const fn finalize_with(
108        self,
109        remaining_seeds: &[&[u8]],
110        program: &[u8; 32],
111    ) -> ([u8; 32], u8) {
112        let mut bump = u8::MAX;
113
114        loop {
115            // Initialize with partial preimage
116            let mut hasher: Sha256 = unsafe { core::mem::transmute_copy(&self.inner) };
117
118            let mut i = 0;
119            while i < remaining_seeds.len() {
120                hasher = hasher.update(remaining_seeds[i]);
121                i += 1;
122            }
123            hasher = hasher.update(&[bump]);
124
125            // Solana PDAs also have program id and marker
126            hasher = hasher.update(program);
127            hasher = hasher.update(PDA_MARKER);
128
129            let candidate = hasher.finalize();
130
131            // If off curve, we're done
132            if !crypto_unsafe_is_on_curve(&candidate) {
133                return (candidate, bump);
134            }
135
136            // Otherwise, check next bump
137            bump -= 1;
138        }
139    }
140}
141#[rustfmt::skip] // keep alignment of explanatory comments
142pub(super) const fn decompress_step_1(
143    repr: &[u8; 32],
144) -> (Choice, FieldElement, FieldElement, FieldElement) {
145    let y = FieldElement::from_bytes(repr);
146    let z = FieldElement::ONE;
147    let yy = y.square();
148    let u = yy.sub(z);                              // u =  y²-1
149    let v = yy.mul(FieldElement::EDWARDS_D).add(z); // v = dy²+1
150    let (is_valid_y_coord, x) = FieldElement::sqrt_ratio_i(u, v);
151
152    (is_valid_y_coord, x, y, z)
153}
154
155#[test]
156fn test_on_curve() {
157    fn safe_is_on_curve(key: &[u8; 32]) -> bool {
158        curve25519_dalek::edwards::CompressedEdwardsY::from_slice(key.as_ref())
159            .unwrap()
160            .decompress()
161            .is_some()
162    }
163
164    for _ in 0..50_000 {
165        let bytes = rand::random::<[u8; 32]>();
166        assert_eq!(crypto_unsafe_is_on_curve(&bytes), safe_is_on_curve(&bytes));
167    }
168}
169
170#[test]
171fn test_with_partial_preimage() {
172    for _ in 0..50_000 {
173        let first = rand::random::<[u8; 32]>();
174        let second = rand::random::<[u8; 32]>();
175
176        let program = [0; 32];
177
178        let direct = derive_program_address(&[&first, &second], &program);
179        let via_parial =
180            PartialPda::from_partial_preimage(&[&first]).finalize_with(&[&second], &program);
181
182        assert_eq!(direct, via_parial)
183    }
184}
const_crypto/ed25519/mod.rs

const_crypto/ed25519/
mod.rs
