curve25519_dalek/backend/serial/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
14use alloc::vec::Vec;
15
16use core::borrow::Borrow;
17use core::cmp::Ordering;
18
19use crate::backend::serial::curve_models::{
20    AffineNielsPoint, CompletedPoint, ProjectiveNielsPoint, ProjectivePoint,
21};
22use crate::edwards::EdwardsPoint;
23use crate::scalar::Scalar;
24use crate::traits::Identity;
25use crate::traits::VartimePrecomputedMultiscalarMul;
26use crate::window::{NafLookupTable5, NafLookupTable8};
27
28#[allow(missing_docs)]
29pub struct VartimePrecomputedStraus {
30    static_lookup_tables: Vec<NafLookupTable8<AffineNielsPoint>>,
31}
32
33impl VartimePrecomputedMultiscalarMul for VartimePrecomputedStraus {
34    type Point = EdwardsPoint;
35
36    fn new<I>(static_points: I) -> Self
37    where
38        I: IntoIterator,
39        I::Item: Borrow<Self::Point>,
40    {
41        Self {
42            static_lookup_tables: static_points
43                .into_iter()
44                .map(|P| NafLookupTable8::<AffineNielsPoint>::from(P.borrow()))
45                .collect(),
46        }
47    }
48
49    fn len(&self) -> usize {
50        self.static_lookup_tables.len()
51    }
52
53    fn is_empty(&self) -> bool {
54        self.static_lookup_tables.is_empty()
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<Self::Point>
63    where
64        I: IntoIterator,
65        I::Item: Borrow<Scalar>,
66        J: IntoIterator,
67        J::Item: Borrow<Scalar>,
68        K: IntoIterator<Item = Option<Self::Point>>,
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::<ProjectiveNielsPoint>::from(&P)))
82            .collect::<Option<Vec<_>>>()?;
83
84        let sp = self.static_lookup_tables.len();
85        let dp = dynamic_lookup_tables.len();
86        assert!(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 S = ProjectivePoint::identity();
93        for j in (0..256).rev() {
94            let mut R: CompletedPoint = S.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.as_extended() + &dynamic_lookup_tables[i].select(t_ij as usize)
101                    }
102                    Ordering::Less => {
103                        R = &R.as_extended() - &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..static_nafs.len() {
111                let t_ij = static_nafs[i][j];
112                match t_ij.cmp(&0) {
113                    Ordering::Greater => {
114                        R = &R.as_extended() + &self.static_lookup_tables[i].select(t_ij as usize)
115                    }
116                    Ordering::Less => {
117                        R = &R.as_extended() - &self.static_lookup_tables[i].select(-t_ij as usize)
118                    }
119                    Ordering::Equal => {}
120                }
121            }
122
123            S = R.as_projective();
124        }
125
126        Some(S.as_extended())
127    }
128}
curve25519_dalek/backend/serial/scalar_mul/precomputed_straus.rs

curve25519_dalek/backend/serial/scalar_mul/
precomputed_straus.rs
