1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201
// -*- mode: rust; -*-
//
// This file is part of curve25519-dalek.
// Copyright (c) 2016-2021 isis lovecruft
// Copyright (c) 2016-2019 Henry de Valence
// See LICENSE for licensing information.
//
// Authors:
// - isis agora lovecruft <isis@patternsinthevoid.net>
// - Henry de Valence <hdevalence@hdevalence.ca>
//! Implementation of the interleaved window method, also known as Straus' method.
#![allow(non_snake_case)]
use alloc::vec::Vec;
use core::borrow::Borrow;
use core::cmp::Ordering;
use crate::edwards::EdwardsPoint;
use crate::scalar::Scalar;
use crate::traits::MultiscalarMul;
use crate::traits::VartimeMultiscalarMul;
/// Perform multiscalar multiplication by the interleaved window
/// method, also known as Straus' method (since it was apparently
/// [first published][solution] by Straus in 1964, as a solution to [a
/// problem][problem] posted in the American Mathematical Monthly in
/// 1963).
///
/// It is easy enough to reinvent, and has been repeatedly. The basic
/// idea is that when computing
/// \\[
/// Q = s_1 P_1 + \cdots + s_n P_n
/// \\]
/// by means of additions and doublings, the doublings can be shared
/// across the \\( P_i \\\).
///
/// We implement two versions, a constant-time algorithm using fixed
/// windows and a variable-time algorithm using sliding windows. They
/// are slight variations on the same idea, and are described in more
/// detail in the respective implementations.
///
/// [solution]: https://www.jstor.org/stable/2310929
/// [problem]: https://www.jstor.org/stable/2312273
pub struct Straus {}
impl MultiscalarMul for Straus {
type Point = EdwardsPoint;
/// Constant-time Straus using a fixed window of size \\(4\\).
///
/// Our goal is to compute
/// \\[
/// Q = s_1 P_1 + \cdots + s_n P_n.
/// \\]
///
/// For each point \\( P_i \\), precompute a lookup table of
/// \\[
/// P_i, 2P_i, 3P_i, 4P_i, 5P_i, 6P_i, 7P_i, 8P_i.
/// \\]
///
/// For each scalar \\( s_i \\), compute its radix-\\(2^4\\)
/// signed digits \\( s_{i,j} \\), i.e.,
/// \\[
/// s_i = s_{i,0} + s_{i,1} 16^1 + ... + s_{i,63} 16^{63},
/// \\]
/// with \\( -8 \leq s_{i,j} < 8 \\). Since \\( 0 \leq |s_{i,j}|
/// \leq 8 \\), we can retrieve \\( s_{i,j} P_i \\) from the
/// lookup table with a conditional negation: using signed
/// digits halves the required table size.
///
/// Then as in the single-base fixed window case, we have
/// \\[
/// \begin{aligned}
/// s_i P_i &= P_i (s_{i,0} + s_{i,1} 16^1 + \cdots + s_{i,63} 16^{63}) \\\\
/// s_i P_i &= P_i s_{i,0} + P_i s_{i,1} 16^1 + \cdots + P_i s_{i,63} 16^{63} \\\\
/// s_i P_i &= P_i s_{i,0} + 16(P_i s_{i,1} + 16( \cdots +16P_i s_{i,63})\cdots )
/// \end{aligned}
/// \\]
/// so each \\( s_i P_i \\) can be computed by alternately adding
/// a precomputed multiple \\( P_i s_{i,j} \\) of \\( P_i \\) and
/// repeatedly doubling.
///
/// Now consider the two-dimensional sum
/// \\[
/// \begin{aligned}
/// s\_1 P\_1 &=& P\_1 s\_{1,0} &+& 16 (P\_1 s\_{1,1} &+& 16 ( \cdots &+& 16 P\_1 s\_{1,63}&) \cdots ) \\\\
/// + & & + & & + & & & & + & \\\\
/// s\_2 P\_2 &=& P\_2 s\_{2,0} &+& 16 (P\_2 s\_{2,1} &+& 16 ( \cdots &+& 16 P\_2 s\_{2,63}&) \cdots ) \\\\
/// + & & + & & + & & & & + & \\\\
/// \vdots & & \vdots & & \vdots & & & & \vdots & \\\\
/// + & & + & & + & & & & + & \\\\
/// s\_n P\_n &=& P\_n s\_{n,0} &+& 16 (P\_n s\_{n,1} &+& 16 ( \cdots &+& 16 P\_n s\_{n,63}&) \cdots )
/// \end{aligned}
/// \\]
/// The sum of the left-hand column is the result \\( Q \\); by
/// computing the two-dimensional sum on the right column-wise,
/// top-to-bottom, then right-to-left, we need to multiply by \\(
/// 16\\) only once per column, sharing the doublings across all
/// of the input points.
fn multiscalar_mul<I, J>(scalars: I, points: J) -> EdwardsPoint
where
I: IntoIterator,
I::Item: Borrow<Scalar>,
J: IntoIterator,
J::Item: Borrow<EdwardsPoint>,
{
use crate::backend::serial::curve_models::ProjectiveNielsPoint;
use crate::traits::Identity;
use crate::window::LookupTable;
let lookup_tables: Vec<_> = points
.into_iter()
.map(|point| LookupTable::<ProjectiveNielsPoint>::from(point.borrow()))
.collect();
// This puts the scalar digits into a heap-allocated Vec.
// To ensure that these are erased, pass ownership of the Vec into a
// Zeroizing wrapper.
#[cfg_attr(not(feature = "zeroize"), allow(unused_mut))]
let mut scalar_digits: Vec<_> = scalars
.into_iter()
.map(|s| s.borrow().as_radix_16())
.collect();
let mut Q = EdwardsPoint::identity();
for j in (0..64).rev() {
Q = Q.mul_by_pow_2(4);
let it = scalar_digits.iter().zip(lookup_tables.iter());
for (s_i, lookup_table_i) in it {
// R_i = s_{i,j} * P_i
let R_i = lookup_table_i.select(s_i[j]);
// Q = Q + R_i
Q = (&Q + &R_i).as_extended();
}
}
#[cfg(feature = "zeroize")]
zeroize::Zeroize::zeroize(&mut scalar_digits);
Q
}
}
impl VartimeMultiscalarMul for Straus {
type Point = EdwardsPoint;
/// Variable-time Straus using a non-adjacent form of width \\(5\\).
///
/// This is completely similar to the constant-time code, but we
/// use a non-adjacent form for the scalar, and do not do table
/// lookups in constant time.
///
/// The non-adjacent form has signed, odd digits. Using only odd
/// digits halves the table size (since we only need odd
/// multiples), or gives fewer additions for the same table size.
fn optional_multiscalar_mul<I, J>(scalars: I, points: J) -> Option<EdwardsPoint>
where
I: IntoIterator,
I::Item: Borrow<Scalar>,
J: IntoIterator<Item = Option<EdwardsPoint>>,
{
use crate::backend::serial::curve_models::{
CompletedPoint, ProjectiveNielsPoint, ProjectivePoint,
};
use crate::traits::Identity;
use crate::window::NafLookupTable5;
let nafs: Vec<_> = scalars
.into_iter()
.map(|c| c.borrow().non_adjacent_form(5))
.collect();
let lookup_tables = points
.into_iter()
.map(|P_opt| P_opt.map(|P| NafLookupTable5::<ProjectiveNielsPoint>::from(&P)))
.collect::<Option<Vec<_>>>()?;
let mut r = ProjectivePoint::identity();
for i in (0..256).rev() {
let mut t: CompletedPoint = r.double();
for (naf, lookup_table) in nafs.iter().zip(lookup_tables.iter()) {
match naf[i].cmp(&0) {
Ordering::Greater => {
t = &t.as_extended() + &lookup_table.select(naf[i] as usize)
}
Ordering::Less => t = &t.as_extended() - &lookup_table.select(-naf[i] as usize),
Ordering::Equal => {}
}
}
r = t.as_projective();
}
Some(r.as_extended())
}
}