curve25519_dalek/backend/vector/scalar_mul/
straus.rs

1// -*- mode: rust; -*-
2//
3// This file is part of curve25519-dalek.
4// Copyright (c) 2016-2021 isis lovecruft
5// Copyright (c) 2016-2019 Henry de Valence
6// See LICENSE for licensing information.
7//
8// Authors:
9// - isis agora lovecruft <[email protected]>
10// - Henry de Valence <[email protected]>
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    #[cfg(feature = "zeroize")]
29    use zeroize::Zeroizing;
30
31    #[for_target_feature("avx2")]
32    use crate::backend::vector::avx2::{CachedPoint, ExtendedPoint};
33
34    #[for_target_feature("avx512ifma")]
35    use crate::backend::vector::ifma::{CachedPoint, ExtendedPoint};
36
37    use crate::edwards::EdwardsPoint;
38    use crate::scalar::Scalar;
39    use crate::traits::{Identity, MultiscalarMul, VartimeMultiscalarMul};
40    use crate::window::{LookupTable, NafLookupTable5};
41
42    /// Multiscalar multiplication using interleaved window / Straus'
43    /// method.  See the `Straus` struct in the serial backend for more
44    /// details.
45    ///
46    /// This exists as a separate implementation from that one because the
47    /// AVX2 code uses different curve models (it does not pass between
48    /// multiple models during scalar mul), and it has to convert the
49    /// point representation on the fly.
50    pub struct Straus {}
51
52    impl MultiscalarMul for Straus {
53        type Point = EdwardsPoint;
54
55        fn multiscalar_mul<I, J>(scalars: I, points: J) -> EdwardsPoint
56        where
57            I: IntoIterator,
58            I::Item: Borrow<Scalar>,
59            J: IntoIterator,
60            J::Item: Borrow<EdwardsPoint>,
61        {
62            // Construct a lookup table of [P,2P,3P,4P,5P,6P,7P,8P]
63            // for each input point P
64            let lookup_tables: Vec<_> = points
65                .into_iter()
66                .map(|point| LookupTable::<CachedPoint>::from(point.borrow()))
67                .collect();
68
69            let scalar_digits_vec: Vec<_> = scalars
70                .into_iter()
71                .map(|s| s.borrow().as_radix_16())
72                .collect();
73            // Pass ownership to a `Zeroizing` wrapper
74            #[cfg(feature = "zeroize")]
75            let scalar_digits_vec = Zeroizing::new(scalar_digits_vec);
76
77            let mut Q = ExtendedPoint::identity();
78            for j in (0..64).rev() {
79                Q = Q.mul_by_pow_2(4);
80                let it = scalar_digits_vec.iter().zip(lookup_tables.iter());
81                for (s_i, lookup_table_i) in it {
82                    // Q = Q + s_{i,j} * P_i
83                    Q = &Q + &lookup_table_i.select(s_i[j]);
84                }
85            }
86            Q.into()
87        }
88    }
89
90    impl VartimeMultiscalarMul for Straus {
91        type Point = EdwardsPoint;
92
93        fn optional_multiscalar_mul<I, J>(scalars: I, points: J) -> Option<EdwardsPoint>
94        where
95            I: IntoIterator,
96            I::Item: Borrow<Scalar>,
97            J: IntoIterator<Item = Option<EdwardsPoint>>,
98        {
99            let nafs: Vec<_> = scalars
100                .into_iter()
101                .map(|c| c.borrow().non_adjacent_form(5))
102                .collect();
103            let lookup_tables: Vec<_> = points
104                .into_iter()
105                .map(|P_opt| P_opt.map(|P| NafLookupTable5::<CachedPoint>::from(&P)))
106                .collect::<Option<Vec<_>>>()?;
107
108            let mut Q = ExtendedPoint::identity();
109
110            for i in (0..256).rev() {
111                Q = Q.double();
112
113                for (naf, lookup_table) in nafs.iter().zip(lookup_tables.iter()) {
114                    match naf[i].cmp(&0) {
115                        Ordering::Greater => {
116                            Q = &Q + &lookup_table.select(naf[i] as usize);
117                        }
118                        Ordering::Less => {
119                            Q = &Q - &lookup_table.select(-naf[i] as usize);
120                        }
121                        Ordering::Equal => {}
122                    }
123                }
124            }
125
126            Some(Q.into())
127        }
128    }
129}
curve25519_dalek/backend/vector/scalar_mul/straus.rs

curve25519_dalek/backend/vector/scalar_mul/
straus.rs
