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 <isis@patternsinthevoid.net>
10 // - Henry de Valence <hdevalence@hdevalence.ca>
11
12 //! Scalar multiplication on the Montgomery form of Curve25519.
13 //!
14 //! To avoid notational confusion with the Edwards code, we use
15 //! variables \\( u, v \\) for the Montgomery curve, so that “Montgomery
16 //! \\(u\\)” here corresponds to “Montgomery \\(x\\)” elsewhere.
17 //!
18 //! Montgomery arithmetic works not on the curve itself, but on the
19 //! \\(u\\)-line, which discards sign information and unifies the curve
20 //! and its quadratic twist. See [_Montgomery curves and their
21 //! arithmetic_][costello-smith] by Costello and Smith for more details.
22 //!
23 //! The `MontgomeryPoint` struct contains the affine \\(u\\)-coordinate
24 //! \\(u\_0(P)\\) of a point \\(P\\) on either the curve or the twist.
25 //! Here the map \\(u\_0 : \mathcal M \rightarrow \mathbb F\_p \\) is
26 //! defined by \\(u\_0((u,v)) = u\\); \\(u\_0(\mathcal O) = 0\\). See
27 //! section 5.4 of Costello-Smith for more details.
28 //!
29 //! # Scalar Multiplication
30 //!
31 //! Scalar multiplication on `MontgomeryPoint`s is provided by the `*`
32 //! operator, which implements the Montgomery ladder.
33 //!
34 //! # Edwards Conversion
35 //!
36 //! The \\(2\\)-to-\\(1\\) map from the Edwards model to the Montgomery
37 //! \\(u\\)-line is provided by `EdwardsPoint::to_montgomery()`.
38 //!
39 //! To lift a `MontgomeryPoint` to an `EdwardsPoint`, use
40 //! `MontgomeryPoint::to_edwards()`, which takes a sign parameter.
41 //! This function rejects `MontgomeryPoints` which correspond to points
42 //! on the twist.
43 //!
44 //! [costello-smith]: https://eprint.iacr.org/2017/212.pdf
45
46 // We allow non snake_case names because coordinates in projective space are
47 // traditionally denoted by the capitalisation of their respective
48 // counterparts in affine space. Yeah, you heard me, rustc, I'm gonna have my
49 // affine and projective cakes and eat both of them too.
50 #![allow(non_snake_case)]
51
52 use core::ops::{Mul, MulAssign};
53
54 use constants::{APLUS2_OVER_FOUR, MONTGOMERY_A, MONTGOMERY_A_NEG};
55 use edwards::{CompressedEdwardsY, EdwardsPoint};
56 use field::FieldElement;
57 use scalar::Scalar;
58
59 use traits::Identity;
60
61 use subtle::Choice;
62 use subtle::ConstantTimeEq;
63 use subtle::{ConditionallyNegatable, ConditionallySelectable};
64
65 use zeroize::Zeroize;
66
67 /// Holds the \\(u\\)-coordinate of a point on the Montgomery form of
68 /// Curve25519 or its twist.
69 #[derive(Copy, Clone, Debug, Hash)]
70 #[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
71 pub struct MontgomeryPoint(pub [u8; 32]);
72
73 /// Equality of `MontgomeryPoint`s is defined mod p.
74 impl ConstantTimeEq for MontgomeryPoint {
ct_eq(&self, other: &MontgomeryPoint) -> Choice75 fn ct_eq(&self, other: &MontgomeryPoint) -> Choice {
76 let self_fe = FieldElement::from_bytes(&self.0);
77 let other_fe = FieldElement::from_bytes(&other.0);
78
79 self_fe.ct_eq(&other_fe)
80 }
81 }
82
83 impl Default for MontgomeryPoint {
default() -> MontgomeryPoint84 fn default() -> MontgomeryPoint {
85 MontgomeryPoint([0u8; 32])
86 }
87 }
88
89 impl PartialEq for MontgomeryPoint {
eq(&self, other: &MontgomeryPoint) -> bool90 fn eq(&self, other: &MontgomeryPoint) -> bool {
91 self.ct_eq(other).unwrap_u8() == 1u8
92 }
93 }
94
95 impl Eq for MontgomeryPoint {}
96
97 impl Identity for MontgomeryPoint {
98 /// Return the group identity element, which has order 4.
identity() -> MontgomeryPoint99 fn identity() -> MontgomeryPoint {
100 MontgomeryPoint([0u8; 32])
101 }
102 }
103
104 impl Zeroize for MontgomeryPoint {
zeroize(&mut self)105 fn zeroize(&mut self) {
106 self.0.zeroize();
107 }
108 }
109
110 impl MontgomeryPoint {
111 /// View this `MontgomeryPoint` as an array of bytes.
as_bytes<'a>(&'a self) -> &'a [u8; 32]112 pub fn as_bytes<'a>(&'a self) -> &'a [u8; 32] {
113 &self.0
114 }
115
116 /// Convert this `MontgomeryPoint` to an array of bytes.
to_bytes(&self) -> [u8; 32]117 pub fn to_bytes(&self) -> [u8; 32] {
118 self.0
119 }
120
121 /// Attempt to convert to an `EdwardsPoint`, using the supplied
122 /// choice of sign for the `EdwardsPoint`.
123 ///
124 /// # Inputs
125 ///
126 /// * `sign`: a `u8` donating the desired sign of the resulting
127 /// `EdwardsPoint`. `0` denotes positive and `1` negative.
128 ///
129 /// # Return
130 ///
131 /// * `Some(EdwardsPoint)` if `self` is the \\(u\\)-coordinate of a
132 /// point on (the Montgomery form of) Curve25519;
133 ///
134 /// * `None` if `self` is the \\(u\\)-coordinate of a point on the
135 /// twist of (the Montgomery form of) Curve25519;
136 ///
to_edwards(&self, sign: u8) -> Option<EdwardsPoint>137 pub fn to_edwards(&self, sign: u8) -> Option<EdwardsPoint> {
138 // To decompress the Montgomery u coordinate to an
139 // `EdwardsPoint`, we apply the birational map to obtain the
140 // Edwards y coordinate, then do Edwards decompression.
141 //
142 // The birational map is y = (u-1)/(u+1).
143 //
144 // The exceptional points are the zeros of the denominator,
145 // i.e., u = -1.
146 //
147 // But when u = -1, v^2 = u*(u^2+486662*u+1) = 486660.
148 //
149 // Since this is nonsquare mod p, u = -1 corresponds to a point
150 // on the twist, not the curve, so we can reject it early.
151
152 let u = FieldElement::from_bytes(&self.0);
153
154 if u == FieldElement::minus_one() { return None; }
155
156 let one = FieldElement::one();
157
158 let y = &(&u - &one) * &(&u + &one).invert();
159
160 let mut y_bytes = y.to_bytes();
161 y_bytes[31] ^= sign << 7;
162
163 CompressedEdwardsY(y_bytes).decompress()
164 }
165 }
166
167 /// Perform the Elligator2 mapping to a Montgomery point.
168 ///
169 /// See <https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-10#section-6.7.1>
170 //
171 // TODO Determine how much of the hash-to-group API should be exposed after the CFRG
172 // draft gets into a more polished/accepted state.
173 #[allow(unused)]
elligator_encode(r_0: &FieldElement) -> MontgomeryPoint174 pub(crate) fn elligator_encode(r_0: &FieldElement) -> MontgomeryPoint {
175 let one = FieldElement::one();
176 let d_1 = &one + &r_0.square2(); /* 2r^2 */
177
178 let d = &MONTGOMERY_A_NEG * &(d_1.invert()); /* A/(1+2r^2) */
179
180 let d_sq = &d.square();
181 let au = &MONTGOMERY_A * &d;
182
183 let inner = &(d_sq + &au) + &one;
184 let eps = &d * &inner; /* eps = d^3 + Ad^2 + d */
185
186 let (eps_is_sq, _eps) = FieldElement::sqrt_ratio_i(&eps, &one);
187
188 let zero = FieldElement::zero();
189 let Atemp = FieldElement::conditional_select(&MONTGOMERY_A, &zero, eps_is_sq); /* 0, or A if nonsquare*/
190 let mut u = &d + &Atemp; /* d, or d+A if nonsquare */
191 u.conditional_negate(!eps_is_sq); /* d, or -d-A if nonsquare */
192
193 MontgomeryPoint(u.to_bytes())
194 }
195
196 /// A `ProjectivePoint` holds a point on the projective line
197 /// \\( \mathbb P(\mathbb F\_p) \\), which we identify with the Kummer
198 /// line of the Montgomery curve.
199 #[derive(Copy, Clone, Debug)]
200 struct ProjectivePoint {
201 pub U: FieldElement,
202 pub W: FieldElement,
203 }
204
205 impl Identity for ProjectivePoint {
identity() -> ProjectivePoint206 fn identity() -> ProjectivePoint {
207 ProjectivePoint {
208 U: FieldElement::one(),
209 W: FieldElement::zero(),
210 }
211 }
212 }
213
214 impl Default for ProjectivePoint {
default() -> ProjectivePoint215 fn default() -> ProjectivePoint {
216 ProjectivePoint::identity()
217 }
218 }
219
220 impl ConditionallySelectable for ProjectivePoint {
conditional_select( a: &ProjectivePoint, b: &ProjectivePoint, choice: Choice, ) -> ProjectivePoint221 fn conditional_select(
222 a: &ProjectivePoint,
223 b: &ProjectivePoint,
224 choice: Choice,
225 ) -> ProjectivePoint {
226 ProjectivePoint {
227 U: FieldElement::conditional_select(&a.U, &b.U, choice),
228 W: FieldElement::conditional_select(&a.W, &b.W, choice),
229 }
230 }
231 }
232
233 impl ProjectivePoint {
234 /// Dehomogenize this point to affine coordinates.
235 ///
236 /// # Return
237 ///
238 /// * \\( u = U / W \\) if \\( W \neq 0 \\);
239 /// * \\( 0 \\) if \\( W \eq 0 \\);
to_affine(&self) -> MontgomeryPoint240 pub fn to_affine(&self) -> MontgomeryPoint {
241 let u = &self.U * &self.W.invert();
242 MontgomeryPoint(u.to_bytes())
243 }
244 }
245
246 /// Perform the double-and-add step of the Montgomery ladder.
247 ///
248 /// Given projective points
249 /// \\( (U\_P : W\_P) = u(P) \\),
250 /// \\( (U\_Q : W\_Q) = u(Q) \\),
251 /// and the affine difference
252 /// \\( u\_{P-Q} = u(P-Q) \\), set
253 /// $$
254 /// (U\_P : W\_P) \gets u([2]P)
255 /// $$
256 /// and
257 /// $$
258 /// (U\_Q : W\_Q) \gets u(P + Q).
259 /// $$
differential_add_and_double( P: &mut ProjectivePoint, Q: &mut ProjectivePoint, affine_PmQ: &FieldElement, )260 fn differential_add_and_double(
261 P: &mut ProjectivePoint,
262 Q: &mut ProjectivePoint,
263 affine_PmQ: &FieldElement,
264 ) {
265 let t0 = &P.U + &P.W;
266 let t1 = &P.U - &P.W;
267 let t2 = &Q.U + &Q.W;
268 let t3 = &Q.U - &Q.W;
269
270 let t4 = t0.square(); // (U_P + W_P)^2 = U_P^2 + 2 U_P W_P + W_P^2
271 let t5 = t1.square(); // (U_P - W_P)^2 = U_P^2 - 2 U_P W_P + W_P^2
272
273 let t6 = &t4 - &t5; // 4 U_P W_P
274
275 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
276 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
277
278 let t9 = &t7 + &t8; // 2 (U_P U_Q - W_P W_Q)
279 let t10 = &t7 - &t8; // 2 (W_P U_Q - U_P W_Q)
280
281 let t11 = t9.square(); // 4 (U_P U_Q - W_P W_Q)^2
282 let t12 = t10.square(); // 4 (W_P U_Q - U_P W_Q)^2
283
284 let t13 = &APLUS2_OVER_FOUR * &t6; // (A + 2) U_P U_Q
285
286 let t14 = &t4 * &t5; // ((U_P + W_P)(U_P - W_P))^2 = (U_P^2 - W_P^2)^2
287 let t15 = &t13 + &t5; // (U_P - W_P)^2 + (A + 2) U_P W_P
288
289 let t16 = &t6 * &t15; // 4 (U_P W_P) ((U_P - W_P)^2 + (A + 2) U_P W_P)
290
291 let t17 = affine_PmQ * &t12; // U_D * 4 (W_P U_Q - U_P W_Q)^2
292 let t18 = t11; // W_D * 4 (U_P U_Q - W_P W_Q)^2
293
294 P.U = t14; // U_{P'} = (U_P + W_P)^2 (U_P - W_P)^2
295 P.W = t16; // W_{P'} = (4 U_P W_P) ((U_P - W_P)^2 + ((A + 2)/4) 4 U_P W_P)
296 Q.U = t18; // U_{Q'} = W_D * 4 (U_P U_Q - W_P W_Q)^2
297 Q.W = t17; // W_{Q'} = U_D * 4 (W_P U_Q - U_P W_Q)^2
298 }
299
300 define_mul_assign_variants!(LHS = MontgomeryPoint, RHS = Scalar);
301
302 define_mul_variants!(LHS = MontgomeryPoint, RHS = Scalar, Output = MontgomeryPoint);
303 define_mul_variants!(LHS = Scalar, RHS = MontgomeryPoint, Output = MontgomeryPoint);
304
305 /// Multiply this `MontgomeryPoint` by a `Scalar`.
306 impl<'a, 'b> Mul<&'b Scalar> for &'a MontgomeryPoint {
307 type Output = MontgomeryPoint;
308
309 /// Given `self` \\( = u\_0(P) \\), and a `Scalar` \\(n\\), return \\( u\_0([n]P) \\).
mul(self, scalar: &'b Scalar) -> MontgomeryPoint310 fn mul(self, scalar: &'b Scalar) -> MontgomeryPoint {
311 // Algorithm 8 of Costello-Smith 2017
312 let affine_u = FieldElement::from_bytes(&self.0);
313 let mut x0 = ProjectivePoint::identity();
314 let mut x1 = ProjectivePoint {
315 U: affine_u,
316 W: FieldElement::one(),
317 };
318
319 let bits: [i8; 256] = scalar.bits();
320
321 for i in (0..255).rev() {
322 let choice: u8 = (bits[i + 1] ^ bits[i]) as u8;
323
324 debug_assert!(choice == 0 || choice == 1);
325
326 ProjectivePoint::conditional_swap(&mut x0, &mut x1, choice.into());
327 differential_add_and_double(&mut x0, &mut x1, &affine_u);
328 }
329 ProjectivePoint::conditional_swap(&mut x0, &mut x1, Choice::from(bits[0] as u8));
330
331 x0.to_affine()
332 }
333 }
334
335 impl<'b> MulAssign<&'b Scalar> for MontgomeryPoint {
mul_assign(&mut self, scalar: &'b Scalar)336 fn mul_assign(&mut self, scalar: &'b Scalar) {
337 *self = (self as &MontgomeryPoint) * scalar;
338 }
339 }
340
341 impl<'a, 'b> Mul<&'b MontgomeryPoint> for &'a Scalar {
342 type Output = MontgomeryPoint;
343
mul(self, point: &'b MontgomeryPoint) -> MontgomeryPoint344 fn mul(self, point: &'b MontgomeryPoint) -> MontgomeryPoint {
345 point * self
346 }
347 }
348
349 // ------------------------------------------------------------------------
350 // Tests
351 // ------------------------------------------------------------------------
352
353 #[cfg(test)]
354 mod test {
355 use super::*;
356 use constants;
357 use core::convert::TryInto;
358
359 use rand_core::OsRng;
360
361 #[test]
identity_in_different_coordinates()362 fn identity_in_different_coordinates() {
363 let id_projective = ProjectivePoint::identity();
364 let id_montgomery = id_projective.to_affine();
365
366 assert!(id_montgomery == MontgomeryPoint::identity());
367 }
368
369 #[test]
identity_in_different_models()370 fn identity_in_different_models() {
371 assert!(EdwardsPoint::identity().to_montgomery() == MontgomeryPoint::identity());
372 }
373
374 #[test]
375 #[cfg(feature = "serde")]
serde_bincode_basepoint_roundtrip()376 fn serde_bincode_basepoint_roundtrip() {
377 use bincode;
378
379 let encoded = bincode::serialize(&constants::X25519_BASEPOINT).unwrap();
380 let decoded: MontgomeryPoint = bincode::deserialize(&encoded).unwrap();
381
382 assert_eq!(encoded.len(), 32);
383 assert_eq!(decoded, constants::X25519_BASEPOINT);
384
385 let raw_bytes = constants::X25519_BASEPOINT.as_bytes();
386 let bp: MontgomeryPoint = bincode::deserialize(raw_bytes).unwrap();
387 assert_eq!(bp, constants::X25519_BASEPOINT);
388 }
389
390 /// Test Montgomery -> Edwards on the X/Ed25519 basepoint
391 #[test]
basepoint_montgomery_to_edwards()392 fn basepoint_montgomery_to_edwards() {
393 // sign bit = 0 => basepoint
394 assert_eq!(
395 constants::ED25519_BASEPOINT_POINT,
396 constants::X25519_BASEPOINT.to_edwards(0).unwrap()
397 );
398 // sign bit = 1 => minus basepoint
399 assert_eq!(
400 - constants::ED25519_BASEPOINT_POINT,
401 constants::X25519_BASEPOINT.to_edwards(1).unwrap()
402 );
403 }
404
405 /// Test Edwards -> Montgomery on the X/Ed25519 basepoint
406 #[test]
basepoint_edwards_to_montgomery()407 fn basepoint_edwards_to_montgomery() {
408 assert_eq!(
409 constants::ED25519_BASEPOINT_POINT.to_montgomery(),
410 constants::X25519_BASEPOINT
411 );
412 }
413
414 /// Check that Montgomery -> Edwards fails for points on the twist.
415 #[test]
montgomery_to_edwards_rejects_twist()416 fn montgomery_to_edwards_rejects_twist() {
417 let one = FieldElement::one();
418
419 // u = 2 corresponds to a point on the twist.
420 let two = MontgomeryPoint((&one+&one).to_bytes());
421
422 assert!(two.to_edwards(0).is_none());
423
424 // u = -1 corresponds to a point on the twist, but should be
425 // checked explicitly because it's an exceptional point for the
426 // birational map. For instance, libsignal will accept it.
427 let minus_one = MontgomeryPoint((-&one).to_bytes());
428
429 assert!(minus_one.to_edwards(0).is_none());
430 }
431
432 #[test]
eq_defined_mod_p()433 fn eq_defined_mod_p() {
434 let mut u18_bytes = [0u8; 32]; u18_bytes[0] = 18;
435 let u18 = MontgomeryPoint(u18_bytes);
436 let u18_unred = MontgomeryPoint([255; 32]);
437
438 assert_eq!(u18, u18_unred);
439 }
440
441 #[test]
montgomery_ladder_matches_edwards_scalarmult()442 fn montgomery_ladder_matches_edwards_scalarmult() {
443 let mut csprng: OsRng = OsRng;
444
445 let s: Scalar = Scalar::random(&mut csprng);
446 let p_edwards: EdwardsPoint = &constants::ED25519_BASEPOINT_TABLE * &s;
447 let p_montgomery: MontgomeryPoint = p_edwards.to_montgomery();
448
449 let expected = s * p_edwards;
450 let result = s * p_montgomery;
451
452 assert_eq!(result, expected.to_montgomery())
453 }
454
455 const ELLIGATOR_CORRECT_OUTPUT: [u8; 32] = [
456 0x5f, 0x35, 0x20, 0x00, 0x1c, 0x6c, 0x99, 0x36, 0xa3, 0x12, 0x06, 0xaf, 0xe7, 0xc7, 0xac,
457 0x22, 0x4e, 0x88, 0x61, 0x61, 0x9b, 0xf9, 0x88, 0x72, 0x44, 0x49, 0x15, 0x89, 0x9d, 0x95,
458 0xf4, 0x6e,
459 ];
460
461 #[test]
462 #[cfg(feature = "std")] // Vec
montgomery_elligator_correct()463 fn montgomery_elligator_correct() {
464 let bytes: std::vec::Vec<u8> = (0u8..32u8).collect();
465 let bits_in: [u8; 32] = (&bytes[..]).try_into().expect("Range invariant broken");
466
467 let fe = FieldElement::from_bytes(&bits_in);
468 let eg = elligator_encode(&fe);
469 assert_eq!(eg.to_bytes(), ELLIGATOR_CORRECT_OUTPUT);
470 }
471
472 #[test]
montgomery_elligator_zero_zero()473 fn montgomery_elligator_zero_zero() {
474 let zero = [0u8; 32];
475 let fe = FieldElement::from_bytes(&zero);
476 let eg = elligator_encode(&fe);
477 assert_eq!(eg.to_bytes(), zero);
478 }
479 }
480