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

curve25519_dalek/backend/vector/scalar_mul/
precomputed_straus.rs
