curve25519_dalek/backend/vector/scalar_mul/
precomputed_straus.rs

1// -*- mode: rust; -*-
2//
3// This file is part of curve25519-dalek.
4// Copyright (c) 2019 Henry de Valence.
5// See LICENSE for licensing information.
6//
7// Authors:
8// - Henry de Valence <[email protected]>
9
10//! Precomputation for Straus's method.
11
12#![allow(non_snake_case)]
13
14#[curve25519_dalek_derive::unsafe_target_feature_specialize(
15    "avx2",
16    conditional("avx512ifma,avx512vl", curve25519_dalek_backend = "avx512")
17)]
18pub mod spec {
19
20    use alloc::vec::Vec;
21
22    use core::borrow::Borrow;
23    use core::cmp::Ordering;
24
25    #[for_target_feature("avx2")]
26    use crate::backend::vector::avx2::{CachedPoint, ExtendedPoint};
27
28    #[for_target_feature("avx512ifma")]
29    use crate::backend::vector::ifma::{CachedPoint, ExtendedPoint};
30
31    use crate::edwards::EdwardsPoint;
32    use crate::scalar::Scalar;
33    use crate::traits::Identity;
34    use crate::traits::VartimePrecomputedMultiscalarMul;
35    use crate::window::{NafLookupTable5, NafLookupTable8};
36
37    pub struct VartimePrecomputedStraus {
38        static_lookup_tables: Vec<NafLookupTable8<CachedPoint>>,
39    }
40
41    impl VartimePrecomputedMultiscalarMul for VartimePrecomputedStraus {
42        type Point = EdwardsPoint;
43
44        fn new<I>(static_points: I) -> Self
45        where
46            I: IntoIterator,
47            I::Item: Borrow<EdwardsPoint>,
48        {
49            Self {
50                static_lookup_tables: static_points
51                    .into_iter()
52                    .map(|P| NafLookupTable8::<CachedPoint>::from(P.borrow()))
53                    .collect(),
54            }
55        }
56
57        fn len(&self) -> usize {
58            self.static_lookup_tables.len()
59        }
60
61        fn is_empty(&self) -> bool {
62            self.static_lookup_tables.is_empty()
63        }
64
65        fn optional_mixed_multiscalar_mul<I, J, K>(
66            &self,
67            static_scalars: I,
68            dynamic_scalars: J,
69            dynamic_points: K,
70        ) -> Option<EdwardsPoint>
71        where
72            I: IntoIterator,
73            I::Item: Borrow<Scalar>,
74            J: IntoIterator,
75            J::Item: Borrow<Scalar>,
76            K: IntoIterator<Item = Option<EdwardsPoint>>,
77        {
78            let static_nafs = static_scalars
79                .into_iter()
80                .map(|c| c.borrow().non_adjacent_form(8))
81                .collect::<Vec<_>>();
82            let dynamic_nafs: Vec<_> = dynamic_scalars
83                .into_iter()
84                .map(|c| c.borrow().non_adjacent_form(5))
85                .collect::<Vec<_>>();
86
87            let dynamic_lookup_tables = dynamic_points
88                .into_iter()
89                .map(|P_opt| P_opt.map(|P| NafLookupTable5::<CachedPoint>::from(&P)))
90                .collect::<Option<Vec<_>>>()?;
91
92            let sp = self.static_lookup_tables.len();
93            let dp = dynamic_lookup_tables.len();
94            assert!(sp >= static_nafs.len());
95            assert_eq!(dp, dynamic_nafs.len());
96
97            // We could save some doublings by looking for the highest
98            // nonzero NAF coefficient, but since we might have a lot of
99            // them to search, it's not clear it's worthwhile to check.
100            let mut R = ExtendedPoint::identity();
101            for j in (0..256).rev() {
102                R = R.double();
103
104                for i in 0..dp {
105                    let t_ij = dynamic_nafs[i][j];
106                    match t_ij.cmp(&0) {
107                        Ordering::Greater => {
108                            R = &R + &dynamic_lookup_tables[i].select(t_ij as usize);
109                        }
110                        Ordering::Less => {
111                            R = &R - &dynamic_lookup_tables[i].select(-t_ij as usize);
112                        }
113                        Ordering::Equal => {}
114                    }
115                }
116
117                #[allow(clippy::needless_range_loop)]
118                for i in 0..static_nafs.len() {
119                    let t_ij = static_nafs[i][j];
120                    match t_ij.cmp(&0) {
121                        Ordering::Greater => {
122                            R = &R + &self.static_lookup_tables[i].select(t_ij as usize);
123                        }
124                        Ordering::Less => {
125                            R = &R - &self.static_lookup_tables[i].select(-t_ij as usize);
126                        }
127                        Ordering::Equal => {}
128                    }
129                }
130            }
131
132            Some(R.into())
133        }
134    }
135}
curve25519_dalek/backend/vector/scalar_mul/precomputed_straus.rs

curve25519_dalek/backend/vector/scalar_mul/
precomputed_straus.rs
