arcis_compiler/utils/crypto/
key.rs

1use crate::{
2    core::{
3        actually_used_field::ActuallyUsedField,
4        circuits::{
5            boolean::{
6                boolean_value::{Boolean, BooleanValue},
7                byte::Byte,
8            },
9            x25519::get_shared_secret,
10        },
11        expressions::{expr::Expr, other_expr::OtherExpr},
12        global_value::value::FieldValue,
13    },
14    traits::{
15        FromF25519,
16        FromLeBits,
17        FromLeBytes,
18        GetSharedRescueKey,
19        MxeRescueKey,
20        MxeX25519PrivateKey,
21        Random,
22        Reveal,
23        ToMontgomery,
24    },
25    utils::{
26        crypto::{
27            key::get_shared_secret::get_shared_secret,
28            rescue_desc::RescueArg,
29            rescue_prime_hash::RescuePrimeHash,
30        },
31        curve_point::{Curve, CurvePoint},
32        elliptic_curve::{
33            decompress_montgomery_u,
34            is_valid_x25519_public_key,
35            AffineEdwardsPoint,
36            F25519,
37        },
38        field::{BaseField, ScalarField},
39        matrix::Matrix,
40    },
41    MxeBitInput,
42    MxeInput,
43};
44use std::ops::Mul;
45
46pub const X25519_PRIVATE_KEY_COUNT: usize = 1;
47pub const X25519_PUBLIC_KEY_COUNT: usize = 1;
48pub const X25519_PUBLIC_KEY_BYTES_COUNT: usize = 32;
49pub const RESCUE_KEY_COUNT: usize = 5;
50pub const AES_128_KEY_COUNT: usize = 128;
51pub const AES_192_KEY_COUNT: usize = 192;
52pub const AES_256_KEY_COUNT: usize = 256;
53pub const ED25519_SECRET_KEY_COUNT: usize = 256;
54pub const ED25519_SIGNING_KEY_S_COUNT: usize = 1;
55pub const ED25519_SIGNING_KEY_HASH_PREFIX_COUNT: usize = 256;
56pub const ED25519_VERIFYING_KEY_COUNT: usize = 32;
57pub const ELGAMAL_SECRET_KEY_COUNT: usize = 1;
58pub const ELGAMAL_PUBKEY_COUNT: usize = 1;
59pub const ELGAMAL_PUBKEY_BYTES_COUNT: usize = 32;
60
61/// The Arcis Rescue key type. A key is an array of length 5 of secret-shared
62/// elements over a finite field. The client rescue key is obtained as
63/// key = rescue_prime_hash(get_shared_secret(mxe_x25519_private_key, pubkey)),
64/// while the mxe rescue key corresponds to 5 randomly generated secret-shared
65/// elements of the finite field.
66#[derive(Copy, Clone)]
67pub struct RescueKey<T: Clone + Copy + Random>([T; RESCUE_KEY_COUNT]);
68
69impl<T: Clone + Copy + Random> RescueKey<T> {
70    pub fn new_from_inner(a: [T; RESCUE_KEY_COUNT]) -> Self {
71        Self(a)
72    }
73
74    pub fn inner(&self) -> [T; RESCUE_KEY_COUNT] {
75        self.0
76    }
77
78    /// Given a client x25519 pubkey, load the cached shared Rescue key if the pubkey is a public
79    /// circuit input and compute the Rescue key otherwise.
80    /// The Rescue key is computed as follows:
81    /// - perform the x25519 key exchange with the MXE private key
82    /// - convert the output to `Vec<T>`
83    /// - perform a key derivation, following [Section 4, Option 1.](https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Cr2.pdf),
84    ///   with the Arcis Rescue-Prime hash function.
85    pub fn new_with_client<
86        Base: F25519,
87        S: Clone + Copy + MxeX25519PrivateKey + Mul<C, Output = C>,
88        C: Curve + ToMontgomery<Output = Base>,
89    >(
90        pubkey: X25519PublicKey<C>,
91    ) -> Self
92    where
93        T: FromF25519<Base> + GetSharedRescueKey<C>,
94    {
95        Self::new_from_inner(
96            (0..RESCUE_KEY_COUNT)
97                .map(|i| T::get_shared_rescue_key(pubkey, i))
98                .collect::<Vec<T>>()
99                .try_into()
100                .unwrap_or_else(|v: Vec<T>| {
101                    panic!(
102                        "Expected a Vec of length {} (found {})",
103                        RESCUE_KEY_COUNT,
104                        v.len()
105                    )
106                }),
107        )
108    }
109
110    /// Given a x25519 private key and a client x25519 pubkey:
111    /// - perform the x25519 key exchange
112    /// - convert the output to `Vec<T>`
113    /// - perform a key derivation, following [Section 4, Option 1.](https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Cr2.pdf),
114    ///   with the Arcis Rescue-Prime hash function.
115    pub fn new_with_client_from_keys<
116        F: ActuallyUsedField,
117        Base: F25519,
118        S: Clone + Copy + Mul<C, Output = C>,
119        C: Curve + ToMontgomery<Output = Base>,
120    >(
121        private_key: X25519PrivateKey<S>,
122        client_pubkey: X25519PublicKey<C>,
123    ) -> Self
124    where
125        T: RescueArg<F> + FromF25519<Base>,
126    {
127        let shared_secret = get_shared_secret(private_key, client_pubkey);
128        let converted = T::from_F25519(shared_secret);
129        let hasher = RescuePrimeHash::new();
130        // We follow [Section 4, Option 1.](https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Cr2.pdf).
131        // For our choice of hash function, we have:
132        // - H_outputBits = hasher.digest_len = RESCUE_KEY_COUNT
133        // - max_H_inputBits = arbitrarily long, as the Rescue-Prime hash function is built upon the
134        //   sponge construction
135        // - L = RESCUE_KEY_COUNT.
136
137        // Build the vector `counter || Z || FixedInfo` (we only have i = 1, since reps = 1).
138        let mut counter = vec![T::from(F::from(1))];
139        counter.extend(converted);
140        // For the FixedInfo we simply take L.
141        counter.push(T::from(F::from(RESCUE_KEY_COUNT as u64)));
142        Self::new_from_inner(hasher.digest(counter))
143    }
144
145    /// Loads the MXE Rescue key.
146    pub fn mxe_rescue_key() -> Self
147    where
148        T: MxeRescueKey,
149    {
150        Self(
151            (0..RESCUE_KEY_COUNT)
152                .map(|i| T::mxe_rescue_key(i))
153                .collect::<Vec<T>>()
154                .try_into()
155                .unwrap_or_else(|v: Vec<T>| {
156                    panic!(
157                        "Expected a Vec of length {} (found {})",
158                        RESCUE_KEY_COUNT,
159                        v.len()
160                    )
161                }),
162        )
163    }
164}
165
166impl<T: Clone + Copy + Random> Random for RescueKey<T> {
167    fn random() -> Self {
168        Self(
169            (0..RESCUE_KEY_COUNT)
170                .map(|_| T::random())
171                .collect::<Vec<T>>()
172                .try_into()
173                .unwrap_or_else(|v: Vec<T>| {
174                    panic!(
175                        "Expected a Vec of length {} (found {})",
176                        RESCUE_KEY_COUNT,
177                        v.len()
178                    )
179                }),
180        )
181    }
182}
183
184impl<T: Clone + Copy + Random> From<RescueKey<T>> for Matrix<T> {
185    fn from(key: RescueKey<T>) -> Self {
186        Matrix::from(key.0.to_vec())
187    }
188}
189
190macro_rules! impl_aes_key {
191    ($t: ident, $byte_len:expr, $key_func_trait: ident, $key_func:ident, $mxe_key: ident) => {
192        pub trait $key_func_trait {
193            fn $key_func(i: usize) -> Self;
194        }
195
196        impl $key_func_trait for BooleanValue {
197            fn $key_func(i: usize) -> Self {
198                assert!(i < 8 * $byte_len);
199                Self::from_expr(Expr::Other(OtherExpr::MxeKey(MxeInput::Bit(
200                    MxeBitInput::$t(i),
201                ))))
202            }
203        }
204
205        impl $key_func_trait for bool {
206            fn $key_func(i: usize) -> Self {
207                debug_assert!(i < 8 * $byte_len);
208                ($mxe_key[i / 8] >> (i % 8)) & 1u8 == 1u8
209            }
210        }
211
212        /// The Arcis AES key type.
213        #[derive(Clone, Copy)]
214        pub struct $t<B: Boolean>([Byte<B>; $byte_len]);
215
216        impl<B: Boolean> $t<B> {
217            pub fn new_from_inner(a: [Byte<B>; $byte_len]) -> Self {
218                Self(a)
219            }
220
221            pub fn inner(&self) -> [Byte<B>; $byte_len] {
222                self.0
223            }
224
225            /// Loads the MXE AES key.
226            pub fn mxe_aes_key() -> Self
227            where
228                B: $key_func_trait,
229            {
230                Self(
231                    (0..8 * $byte_len)
232                        .map(|i| B::$key_func(i))
233                        .collect::<Vec<B>>()
234                        .chunks(8)
235                        .map(|chunk| {
236                            Byte::new(chunk.to_vec().try_into().unwrap_or_else(|v: Vec<B>| {
237                                panic!("Expected a Vec of length 8 (found {})", v.len())
238                            }))
239                        })
240                        .collect::<Vec<Byte<B>>>()
241                        .try_into()
242                        .unwrap_or_else(|v: Vec<Byte<B>>| {
243                            panic!("Expected a Vec of length {} (found {})", $byte_len, v.len())
244                        }),
245                )
246            }
247        }
248
249        impl<B: Boolean> Random for $t<B> {
250            fn random() -> Self {
251                Self(
252                    (0..$byte_len)
253                        .map(|_| Byte::<B>::random())
254                        .collect::<Vec<Byte<B>>>()
255                        .try_into()
256                        .unwrap_or_else(|v: Vec<Byte<B>>| {
257                            panic!("Expected a Vec of length {} (found {})", $byte_len, v.len())
258                        }),
259                )
260            }
261        }
262
263        impl $t<BooleanValue> {
264            pub fn compress(&self) -> [FieldValue<BaseField>; ($byte_len as usize).div_ceil(16)] {
265                self.0
266                    .chunks(16)
267                    .map(|bytes| {
268                        FieldValue::<BaseField>::from_le_bits(
269                            bytes
270                                .into_iter()
271                                .flat_map(|byte| byte.to_vec())
272                                .collect::<Vec<BooleanValue>>(),
273                            false,
274                        )
275                    })
276                    .collect::<Vec<FieldValue<BaseField>>>()
277                    .try_into()
278                    .unwrap_or_else(|v: Vec<FieldValue<BaseField>>| {
279                        panic!(
280                            "Expected a Vec of length {} (found {})",
281                            ($byte_len + 15) / 16,
282                            v.len()
283                        )
284                    })
285            }
286        }
287    };
288}
289
290impl_aes_key!(AES128Key, 16, MxeAES128Key, mxe_aes_128_key, MXE_AES128_KEY);
291impl_aes_key!(AES192Key, 24, MxeAES192Key, mxe_aes_192_key, MXE_AES192_KEY);
292impl_aes_key!(AES256Key, 32, MxeAES256Key, mxe_aes_256_key, MXE_AES256_KEY);
293
294/// The Arcis x25519 private key type. A private key is a random element of the
295/// finite field with ell = 2^252 + 27742317777372353535851937790883648493 elements.
296#[derive(Copy, Clone)]
297pub struct X25519PrivateKey<S: Clone + Copy> {
298    key: S,
299    pub is_expected_non_zero: bool,
300}
301
302impl<S: Clone + Copy> X25519PrivateKey<S> {
303    pub fn new(value: S, is_expected_non_zero: bool) -> Self {
304        Self {
305            key: value,
306            is_expected_non_zero,
307        }
308    }
309
310    pub fn inner(&self) -> S {
311        self.key
312    }
313
314    /// Generate a random x25519 private key.
315    /// We generate private keys similar to the standard way of generating a x25519 private key:
316    /// generate 32 random bytes and perform clamped multiplication with the generator/the client's
317    /// pubkey. The reason for doing so is that one generally wants to avoid the expensive check if
318    /// the client pubkey is a valid point of order \ell, and the clamped multiplication
319    /// naturally prevents from small-subgroup attacks. Since we do check on the node that the
320    /// client pubkey is a valid point of order \ell, and input it as a CurveValue, this comes
321    /// down to generating 251 random bits and return \sum_{i=3}^{253} b_i*2^i + 2^254 mod \ell.
322    /// Note: this is by no means better or worse than generating a random ScalarField element,
323    /// it just has become a convention.
324    pub fn random<B: Boolean>() -> Self
325    where
326        S: FromLeBits<B>,
327    {
328        let mut bits = vec![B::from(false); 3];
329        for _ in 0..251 {
330            bits.push(B::random());
331        }
332        bits.push(B::from(true));
333        Self {
334            key: S::from_le_bits(bits, false),
335            is_expected_non_zero: true,
336        }
337    }
338
339    /// Loads the MXE x25519 private key.
340    pub fn mxe_private_key() -> Self
341    where
342        S: MxeX25519PrivateKey,
343    {
344        Self {
345            key: S::mxe_x25519_private_key(),
346            is_expected_non_zero: true,
347        }
348    }
349}
350
351impl<S: Clone + Copy + From<ScalarField>> FromLeBytes for X25519PrivateKey<S> {
352    fn from_le_bytes(bytes: [u8; 32]) -> Self {
353        // clamp the bytes
354        let mut key_bytes = bytes;
355        key_bytes[0] &= 0b1111_1000;
356        key_bytes[31] &= 0b0111_1111;
357        key_bytes[31] |= 0b0100_0000;
358        // Note that the key cannot be zero since the clamped bytes represent a 255-bit
359        // multiple of 8 and the lcm of 8 and \ell is 8 * \ell, which is 256 bits long.
360        X25519PrivateKey::new(
361            S::from(ScalarField::from_le_bits(
362                key_bytes
363                    .into_iter()
364                    .flat_map(|byte| Byte::from(byte).to_vec())
365                    .collect::<Vec<bool>>(),
366                false,
367            )),
368            true,
369        )
370    }
371}
372
373impl Default for X25519PrivateKey<ScalarField> {
374    fn default() -> Self {
375        Self::from_le_bytes([0u8; 32])
376    }
377}
378
379/// The Arcis x25519 public key type.
380/// A public key is not necessarily public.
381#[derive(Copy, Clone)]
382pub struct X25519PublicKey<C: Curve> {
383    point: C,
384    pub is_expected_non_identity: bool,
385}
386
387impl<C: Curve> X25519PublicKey<C> {
388    pub fn new(value: C, is_expected_non_identity: bool) -> Self {
389        Self {
390            point: value,
391            is_expected_non_identity,
392        }
393    }
394
395    pub fn new_from_private_key<S: Clone + Copy + Mul<C, Output = C>>(
396        private_key: X25519PrivateKey<S>,
397    ) -> Self {
398        Self {
399            point: private_key.inner() * C::generator(),
400            is_expected_non_identity: private_key.is_expected_non_zero,
401        }
402    }
403
404    pub fn inner(&self) -> C {
405        self.point
406    }
407
408    pub fn to_montgomery<Base: F25519>(self) -> (Base, Base)
409    where
410        C: ToMontgomery<Output = Base>,
411    {
412        self.point.to_montgomery(self.is_expected_non_identity)
413    }
414}
415
416impl X25519PublicKey<CurvePoint> {
417    /// A X25519PublicKey is serialized by converting the inner CurvePoint to Montgomery coordinates
418    /// and then serializing the u-coordinate (a BaseField element).
419    pub fn to_le_bytes(&self) -> [u8; 32] {
420        self.to_montgomery().0.to_le_bytes()
421    }
422
423    /// Given the serialized Montgomery u-coordinate of a x25519 pubkey, checks the validity of the
424    /// bytes and constructs a X25519PublicKey.
425    pub fn from_le_bytes(bytes: [u8; 32]) -> Option<Self> {
426        is_valid_x25519_public_key(bytes).map(|montgomery_point| {
427            // convert the affine Montgomery point to a CurvePoint
428            let edwards_point = AffineEdwardsPoint::from_montgomery(montgomery_point);
429            Self {
430                point: CurvePoint::from(edwards_point),
431                is_expected_non_identity: true,
432            }
433        })
434    }
435
436    /// Constructs a X25519PublicKey from the serialized Montgomery u-coordinate of a x25519 pubkey.
437    /// Does not check the validity of the pubkey.
438    pub fn from_le_bytes_unchecked(bytes: [u8; 32]) -> Self {
439        let u = BaseField::from_le_bytes(bytes);
440        let (_, montgomery_point) = decompress_montgomery_u(u);
441        // convert the affine Montgomery point to a CurvePoint
442        let edwards_point = AffineEdwardsPoint::from_montgomery(montgomery_point);
443        Self {
444            point: CurvePoint::from(edwards_point),
445            is_expected_non_identity: false,
446        }
447    }
448}
449
450impl<C: Curve> Reveal for X25519PublicKey<C> {
451    fn reveal(self) -> Self {
452        Self {
453            point: self.point.reveal(),
454            is_expected_non_identity: self.is_expected_non_identity,
455        }
456    }
457}
458
459impl Default for X25519PublicKey<CurvePoint> {
460    fn default() -> Self {
461        Self::new_from_private_key(X25519PrivateKey::<ScalarField>::default())
462    }
463}
464
465// Randomly generated element of the scalar field.
466pub(crate) const MXE_X25519_PRIVATE_KEY: [u8; 32] = [
467    207, 40, 181, 230, 45, 204, 46, 17, 8, 19, 251, 241, 43, 129, 216, 23, 86, 169, 218, 248, 95,
468    114, 111, 9, 188, 159, 223, 16, 124, 98, 41, 1,
469];
470
471// Five randomly generated elements of the base field.
472pub(crate) const MXE_RESCUE_BASE_FIELD_KEY: [[u8; 32]; 5] = [
473    [
474        124, 219, 118, 100, 151, 174, 173, 201, 180, 159, 95, 202, 109, 154, 90, 104, 99, 221, 206,
475        79, 44, 221, 182, 198, 143, 180, 180, 121, 78, 223, 238, 12,
476    ],
477    [
478        158, 10, 32, 122, 234, 85, 113, 2, 69, 115, 151, 149, 163, 189, 216, 108, 160, 21, 118,
479        154, 185, 199, 198, 251, 142, 193, 168, 98, 218, 59, 20, 9,
480    ],
481    [
482        45, 115, 67, 23, 196, 46, 150, 202, 33, 22, 44, 144, 204, 34, 166, 30, 183, 63, 38, 213,
483        166, 150, 234, 191, 201, 13, 79, 86, 171, 100, 140, 15,
484    ],
485    [
486        209, 1, 108, 251, 175, 105, 199, 246, 83, 186, 72, 0, 15, 236, 105, 110, 5, 109, 41, 216,
487        148, 98, 208, 128, 32, 47, 224, 93, 90, 176, 33, 2,
488    ],
489    [
490        179, 142, 132, 221, 113, 147, 206, 83, 22, 121, 245, 155, 239, 204, 18, 158, 119, 190, 54,
491        17, 28, 17, 247, 191, 151, 147, 118, 151, 38, 169, 21, 4,
492    ],
493];
494
495// Five randomly generated elements of the scalar field.
496pub(crate) const MXE_RESCUE_SCALAR_FIELD_KEY: [[u8; 32]; 5] = [
497    [
498        72, 239, 104, 144, 184, 215, 25, 76, 171, 209, 107, 34, 146, 39, 35, 134, 103, 10, 38, 148,
499        251, 155, 69, 207, 216, 234, 104, 220, 253, 63, 217, 14,
500    ],
501    [
502        11, 232, 48, 222, 61, 142, 29, 189, 73, 204, 120, 1, 111, 20, 233, 1, 101, 49, 169, 220,
503        66, 250, 21, 125, 132, 247, 11, 21, 128, 217, 231, 12,
504    ],
505    [
506        33, 164, 174, 155, 214, 77, 209, 93, 24, 230, 196, 38, 29, 5, 89, 76, 52, 85, 219, 66, 90,
507        7, 190, 27, 181, 51, 206, 187, 99, 72, 251, 2,
508    ],
509    [
510        7, 178, 214, 42, 8, 10, 134, 249, 244, 69, 192, 63, 96, 204, 229, 10, 126, 3, 33, 49, 174,
511        26, 149, 5, 254, 118, 230, 75, 149, 105, 145, 5,
512    ],
513    [
514        22, 94, 36, 119, 174, 65, 70, 75, 230, 11, 102, 41, 31, 194, 55, 255, 24, 25, 113, 181,
515        206, 213, 243, 203, 115, 152, 90, 177, 232, 228, 145, 3,
516    ],
517];
518
519// 16 randomly generated bytes.
520pub(crate) const MXE_AES128_KEY: [u8; 16] = [
521    124, 219, 118, 100, 151, 174, 173, 201, 180, 159, 95, 202, 109, 154, 90, 104,
522];
523
524// 24 randomly generated bytes.
525pub(crate) const MXE_AES192_KEY: [u8; 24] = [
526    159, 234, 203, 164, 191, 151, 2, 150, 165, 97, 217, 48, 4, 227, 91, 13, 244, 2, 222, 234, 226,
527    187, 253, 127,
528];
529
530// 32 randomly generated bytes.
531pub(crate) const MXE_AES256_KEY: [u8; 32] = [
532    196, 120, 191, 34, 144, 89, 36, 185, 242, 159, 162, 158, 170, 37, 234, 191, 33, 141, 52, 147,
533    253, 3, 58, 49, 169, 146, 53, 185, 1, 55, 60, 87,
534];
535
536// 32 randomly generated bytes.
537pub(crate) const MXE_ED25519_SECRET_KEY: [u8; 32] = [
538    13, 192, 52, 244, 242, 224, 239, 161, 194, 4, 155, 74, 60, 148, 207, 43, 188, 194, 251, 154,
539    142, 189, 227, 93, 25, 249, 65, 205, 121, 53, 203, 22,
540];
541
542// Signing key s derived from MXE_ED25519_SECRET_KEY.
543pub(crate) const MXE_ED25519_SIGNING_KEY_S: [u8; 32] = [
544    60, 248, 182, 157, 91, 202, 9, 247, 187, 176, 179, 140, 115, 51, 98, 253, 44, 82, 56, 212, 19,
545    155, 154, 68, 254, 17, 132, 223, 74, 130, 165, 12,
546];
547
548// Signing key hash-prefix derived from MXE_ED25519_SECRET_KEY.
549pub(crate) const MXE_ED25519_SIGNING_KEY_HASH_PREFIX: [u8; 32] = [
550    217, 141, 36, 192, 41, 135, 248, 83, 212, 208, 84, 27, 188, 50, 69, 245, 68, 207, 121, 207, 6,
551    115, 30, 27, 94, 187, 91, 113, 18, 219, 27, 64,
552];
553
554// Verifying key derived from MXE_ED25519_SECRET_KEY.
555pub(crate) const MXE_ED25519_VERIFYING_KEY: [u8; 32] = [
556    14, 32, 126, 133, 202, 216, 28, 182, 228, 95, 141, 94, 34, 155, 36, 238, 53, 102, 82, 241, 81,
557    180, 136, 239, 169, 22, 226, 133, 195, 171, 252, 7,
558];
559
560// Randomly generated element of the scalar field.
561pub(crate) const MXE_ELGAMAL_SECRET_KEY: [u8; 32] = [
562    57, 71, 187, 92, 7, 239, 222, 40, 252, 52, 135, 191, 198, 199, 173, 77, 31, 119, 254, 244, 152,
563    71, 131, 255, 183, 183, 182, 191, 87, 99, 182, 3,
564];
565
566// Public key derived from MXE_ELGAMAL_SECRET_KEY, stored as CompressedRistretto.
567pub(crate) const MXE_ELGAMAL_PUBKEY: [u8; 32] = [
568    168, 163, 137, 87, 0, 80, 192, 23, 16, 133, 172, 238, 187, 164, 133, 148, 115, 126, 183, 16,
569    220, 95, 125, 82, 16, 175, 99, 114, 226, 131, 197, 111,
570];
arcis_compiler/utils/crypto/key.rs

arcis_compiler/utils/crypto/
key.rs
