curve25519_dalek/backend/serial/scalar_mul/
variable_base.rs

1#![allow(non_snake_case)]
2
3use crate::backend::serial::curve_models::ProjectiveNielsPoint;
4use crate::edwards::EdwardsPoint;
5use crate::scalar::Scalar;
6use crate::traits::Identity;
7use crate::window::LookupTable;
8
9/// Perform constant-time, variable-base scalar multiplication.
10#[rustfmt::skip] // keep alignment of explanatory comments
11pub(crate) fn mul(point: &EdwardsPoint, scalar: &Scalar) -> EdwardsPoint {
12    // Construct a lookup table of [P,2P,3P,4P,5P,6P,7P,8P]
13    let lookup_table = LookupTable::<ProjectiveNielsPoint>::from(point);
14    // Setting s = scalar, compute
15    //
16    //    s = s_0 + s_1*16^1 + ... + s_63*16^63,
17    //
18    // with `-8 ≤ s_i < 8` for `0 ≤ i < 63` and `-8 ≤ s_63 ≤ 8`.
19    // This decomposition requires s < 2^255, which is guaranteed by Scalar invariant #1.
20    let scalar_digits = scalar.as_radix_16();
21    // Compute s*P as
22    //
23    //    s*P = P*(s_0 +   s_1*16^1 +   s_2*16^2 + ... +   s_63*16^63)
24    //    s*P =  P*s_0 + P*s_1*16^1 + P*s_2*16^2 + ... + P*s_63*16^63
25    //    s*P = P*s_0 + 16*(P*s_1 + 16*(P*s_2 + 16*( ... + P*s_63)...))
26    //
27    // We sum right-to-left.
28
29    // Unwrap first loop iteration to save computing 16*identity
30    let mut tmp2;
31    let mut tmp3 = EdwardsPoint::identity();
32    let mut tmp1 = &tmp3 + &lookup_table.select(scalar_digits[63]);
33    // Now tmp1 = s_63*P in P1xP1 coords
34    for i in (0..63).rev() {
35        tmp2 = tmp1.as_projective(); // tmp2 =    (prev) in P2 coords
36        tmp1 = tmp2.double();        // tmp1 =  2*(prev) in P1xP1 coords
37        tmp2 = tmp1.as_projective(); // tmp2 =  2*(prev) in P2 coords
38        tmp1 = tmp2.double();        // tmp1 =  4*(prev) in P1xP1 coords
39        tmp2 = tmp1.as_projective(); // tmp2 =  4*(prev) in P2 coords
40        tmp1 = tmp2.double();        // tmp1 =  8*(prev) in P1xP1 coords
41        tmp2 = tmp1.as_projective(); // tmp2 =  8*(prev) in P2 coords
42        tmp1 = tmp2.double();        // tmp1 = 16*(prev) in P1xP1 coords
43        tmp3 = tmp1.as_extended();   // tmp3 = 16*(prev) in P3 coords
44        tmp1 = &tmp3 + &lookup_table.select(scalar_digits[i]);
45        // Now tmp1 = s_i*P + 16*(prev) in P1xP1 coords
46    }
47    tmp1.as_extended()
48}
curve25519_dalek/backend/serial/scalar_mul/variable_base.rs

curve25519_dalek/backend/serial/scalar_mul/
variable_base.rs
