ed448_goldilocks/
montgomery.rs

1// The original file was a part of curve25519-dalek.
2// Copyright (c) 2016-2019 Isis Lovecruft, Henry de Valence
3// Copyright (c) 2020 Kevaundray Wedderburn
4// See LICENSE for licensing information.
5//
6// Authors:
7// - Isis Agora Lovecruft <[email protected]>
8// - Henry de Valence <[email protected]>
9// - Kevaundray Wedderburn <[email protected]>
10
11#![allow(non_snake_case)]
12
13// use crate::constants::A_PLUS_TWO_OVER_FOUR;
14use crate::EdwardsScalar;
15use crate::edwards::extended::EdwardsPoint;
16use crate::field::FieldElement;
17use core::fmt;
18use core::ops::Mul;
19use subtle::{Choice, ConditionallySelectable, ConstantTimeEq};
20
21impl MontgomeryPoint {
22    /// First low order point on Curve448 and it's twist
23    pub const LOW_A: MontgomeryPoint = MontgomeryPoint([
24        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
25        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
26        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
27        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
28    ]);
29    /// Second low order point on Curve448 and it's twist
30    pub const LOW_B: MontgomeryPoint = MontgomeryPoint([
31        0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
32        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
33        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
34        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
35    ]);
36    /// Third low order point on Curve448 and it's twist
37    pub const LOW_C: MontgomeryPoint = MontgomeryPoint([
38        0xfe, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
39        0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe, 0xff,
40        0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
41        0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
42    ]);
43}
44
45/// A point in Montgomery form
46#[derive(Copy, Clone)]
47pub struct MontgomeryPoint(pub [u8; 56]);
48
49impl Default for MontgomeryPoint {
50    fn default() -> MontgomeryPoint {
51        Self([0u8; 56])
52    }
53}
54
55impl elliptic_curve::zeroize::DefaultIsZeroes for MontgomeryPoint {}
56
57impl fmt::Debug for MontgomeryPoint {
58    fn fmt(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
59        self.0[..].fmt(formatter)
60    }
61}
62
63impl ConstantTimeEq for MontgomeryPoint {
64    fn ct_eq(&self, other: &MontgomeryPoint) -> Choice {
65        self.0.ct_eq(&other.0)
66    }
67}
68
69impl PartialEq for MontgomeryPoint {
70    fn eq(&self, other: &MontgomeryPoint) -> bool {
71        self.ct_eq(other).into()
72    }
73}
74impl Eq for MontgomeryPoint {}
75
76/// A Projective point in Montgomery form
77#[derive(Copy, Clone, Debug)]
78pub struct ProjectiveMontgomeryPoint {
79    U: FieldElement,
80    W: FieldElement,
81}
82
83impl Mul<&EdwardsScalar> for &MontgomeryPoint {
84    type Output = MontgomeryPoint;
85
86    #[allow(clippy::suspicious_arithmetic_impl)]
87    fn mul(self, scalar: &EdwardsScalar) -> MontgomeryPoint {
88        // Algorithm 8 of Costello-Smith 2017
89        let affine_u = FieldElement::from_bytes(&self.0);
90        let mut x0 = ProjectiveMontgomeryPoint::identity();
91        let mut x1 = ProjectiveMontgomeryPoint {
92            U: affine_u,
93            W: FieldElement::ONE,
94        };
95
96        let bits = scalar.bits();
97        let mut swap = 0;
98        for s in (0..448).rev() {
99            let bit = bits[s] as u8;
100            let choice: u8 = swap ^ bit;
101
102            ProjectiveMontgomeryPoint::conditional_swap(&mut x0, &mut x1, Choice::from(choice));
103            differential_add_and_double(&mut x0, &mut x1, &affine_u);
104
105            swap = bit;
106        }
107
108        x0.to_affine()
109    }
110}
111
112impl Mul<&MontgomeryPoint> for &EdwardsScalar {
113    type Output = MontgomeryPoint;
114
115    fn mul(self, point: &MontgomeryPoint) -> MontgomeryPoint {
116        point * self
117    }
118}
119
120impl MontgomeryPoint {
121    /// Returns the generator specified in RFC7748
122    pub const GENERATOR: Self = Self([
123        0x05, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
124        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
125        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
126        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
127    ]);
128
129    /// Convert this point to an [`EdwardsPoint`]
130    pub fn to_edwards(&self, _sign: u8) -> Option<EdwardsPoint> {
131        // We use the 4-isogeny to map to the Ed448.
132        // This is different to Curve25519, where we use a birational map.
133        todo!()
134    }
135
136    /// Returns true if the point is one of the low order points
137    pub fn is_low_order(&self) -> bool {
138        (*self == Self::LOW_A) || (*self == Self::LOW_B) || (*self == Self::LOW_C)
139    }
140
141    /// View the point as a byte slice
142    pub fn as_bytes(&self) -> &[u8; 56] {
143        &self.0
144    }
145
146    /// Convert the point to a ProjectiveMontgomeryPoint
147    pub fn to_projective(&self) -> ProjectiveMontgomeryPoint {
148        ProjectiveMontgomeryPoint {
149            U: FieldElement::from_bytes(&self.0),
150            W: FieldElement::ONE,
151        }
152    }
153}
154
155impl ConditionallySelectable for ProjectiveMontgomeryPoint {
156    fn conditional_select(
157        a: &ProjectiveMontgomeryPoint,
158        b: &ProjectiveMontgomeryPoint,
159        choice: Choice,
160    ) -> ProjectiveMontgomeryPoint {
161        ProjectiveMontgomeryPoint {
162            U: FieldElement::conditional_select(&a.U, &b.U, choice),
163            W: FieldElement::conditional_select(&a.W, &b.W, choice),
164        }
165    }
166}
167
168fn differential_add_and_double(
169    P: &mut ProjectiveMontgomeryPoint,
170    Q: &mut ProjectiveMontgomeryPoint,
171    affine_PmQ: &FieldElement,
172) {
173    let t0 = P.U + P.W;
174    let t1 = P.U - P.W;
175    let t2 = Q.U + Q.W;
176    let t3 = Q.U - Q.W;
177
178    let t4 = t0.square(); // (U_P + W_P)^2 = U_P^2 + 2 U_P W_P + W_P^2
179    let t5 = t1.square(); // (U_P - W_P)^2 = U_P^2 - 2 U_P W_P + W_P^2
180
181    let t6 = t4 - t5; // 4 U_P W_P
182
183    let t7 = t0 * t3; // (U_P + W_P) (U_Q - W_Q) = U_P U_Q + W_P U_Q - U_P W_Q - W_P W_Q
184    let t8 = t1 * t2; // (U_P - W_P) (U_Q + W_Q) = U_P U_Q - W_P U_Q + U_P W_Q - W_P W_Q
185
186    let t9 = t7 + t8; // 2 (U_P U_Q - W_P W_Q)
187    let t10 = t7 - t8; // 2 (W_P U_Q - U_P W_Q)
188
189    let t11 = t9.square(); // 4 (U_P U_Q - W_P W_Q)^2
190    let t12 = t10.square(); // 4 (W_P U_Q - U_P W_Q)^2
191    let t13 = FieldElement::A_PLUS_TWO_OVER_FOUR * t6; // (A + 2) U_P U_Q
192
193    let t14 = t4 * t5; // ((U_P + W_P)(U_P - W_P))^2 = (U_P^2 - W_P^2)^2
194    let t15 = t13 + t5; // (U_P - W_P)^2 + (A + 2) U_P W_P
195
196    let t16 = t6 * t15; // 4 (U_P W_P) ((U_P - W_P)^2 + (A + 2) U_P W_P)
197    let t17 = *affine_PmQ * t12; // U_D * 4 (W_P U_Q - U_P W_Q)^2
198    let t18 = t11; // W_D * 4 (U_P U_Q - W_P W_Q)^2
199
200    P.U = t14; // U_{P'} = (U_P + W_P)^2 (U_P - W_P)^2
201    P.W = t16; // W_{P'} = (4 U_P W_P) ((U_P - W_P)^2 + ((A + 2)/4) 4 U_P W_P)
202    Q.U = t18; // U_{Q'} = W_D * 4 (U_P U_Q - W_P W_Q)^2
203    Q.W = t17; // W_{Q'} = U_D * 4 (W_P U_Q - U_P W_Q)^2
204}
205
206impl ProjectiveMontgomeryPoint {
207    /// The identity element of the group: the point at infinity.
208    pub fn identity() -> ProjectiveMontgomeryPoint {
209        ProjectiveMontgomeryPoint {
210            U: FieldElement::ONE,
211            W: FieldElement::ZERO,
212        }
213    }
214
215    /// Convert the point to affine form
216    pub fn to_affine(&self) -> MontgomeryPoint {
217        let x = self.U * self.W.invert();
218        MontgomeryPoint(x.to_bytes())
219    }
220}
221
222#[cfg(test)]
223mod tests {
224
225    use super::*;
226
227    #[test]
228    fn test_montgomery_edwards() {
229        let scalar = EdwardsScalar::from(200u32);
230        use crate::GOLDILOCKS_BASE_POINT as bp;
231
232        // Montgomery scalar mul
233        let montgomery_bp = bp.to_montgomery();
234        let montgomery_res = &montgomery_bp * &scalar;
235
236        // Goldilocks scalar mul
237        let goldilocks_point = bp.scalar_mul(&scalar);
238        assert_eq!(goldilocks_point.to_montgomery(), montgomery_res);
239    }
240}
ed448_goldilocks/montgomery.rs

ed448_goldilocks/
montgomery.rs
