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 <hdevalence@hdevalence.ca>
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", nightly)
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 optional_mixed_multiscalar_mul<I, J, K>(
58            &self,
59            static_scalars: I,
60            dynamic_scalars: J,
61            dynamic_points: K,
62        ) -> Option<EdwardsPoint>
63        where
64            I: IntoIterator,
65            I::Item: Borrow<Scalar>,
66            J: IntoIterator,
67            J::Item: Borrow<Scalar>,
68            K: IntoIterator<Item = Option<EdwardsPoint>>,
69        {
70            let static_nafs = static_scalars
71                .into_iter()
72                .map(|c| c.borrow().non_adjacent_form(5))
73                .collect::<Vec<_>>();
74            let dynamic_nafs: Vec<_> = dynamic_scalars
75                .into_iter()
76                .map(|c| c.borrow().non_adjacent_form(5))
77                .collect::<Vec<_>>();
78
79            let dynamic_lookup_tables = dynamic_points
80                .into_iter()
81                .map(|P_opt| P_opt.map(|P| NafLookupTable5::<CachedPoint>::from(&P)))
82                .collect::<Option<Vec<_>>>()?;
83
84            let sp = self.static_lookup_tables.len();
85            let dp = dynamic_lookup_tables.len();
86            assert_eq!(sp, static_nafs.len());
87            assert_eq!(dp, dynamic_nafs.len());
88
89            // We could save some doublings by looking for the highest
90            // nonzero NAF coefficient, but since we might have a lot of
91            // them to search, it's not clear it's worthwhile to check.
92            let mut R = ExtendedPoint::identity();
93            for j in (0..256).rev() {
94                R = R.double();
95
96                for i in 0..dp {
97                    let t_ij = dynamic_nafs[i][j];
98                    match t_ij.cmp(&0) {
99                        Ordering::Greater => {
100                            R = &R + &dynamic_lookup_tables[i].select(t_ij as usize);
101                        }
102                        Ordering::Less => {
103                            R = &R - &dynamic_lookup_tables[i].select(-t_ij as usize);
104                        }
105                        Ordering::Equal => {}
106                    }
107                }
108
109                #[allow(clippy::needless_range_loop)]
110                for i in 0..sp {
111                    let t_ij = static_nafs[i][j];
112                    match t_ij.cmp(&0) {
113                        Ordering::Greater => {
114                            R = &R + &self.static_lookup_tables[i].select(t_ij as usize);
115                        }
116                        Ordering::Less => {
117                            R = &R - &self.static_lookup_tables[i].select(-t_ij as usize);
118                        }
119                        Ordering::Equal => {}
120                    }
121                }
122            }
123
124            Some(R.into())
125        }
126    }
127}
curve25519_dalek/backend/vector/scalar_mul/precomputed_straus.rs

curve25519_dalek/backend/vector/scalar_mul/
precomputed_straus.rs
