1 // -*- mode: rust; -*- 2 // 3 // This file is part of curve25519-dalek. 4 // Copyright (c) 2016-2019 Isis Lovecruft, Henry de Valence 5 // See LICENSE for licensing information. 6 // 7 // Authors: 8 // - Isis Agora Lovecruft <isis@patternsinthevoid.net> 9 // - Henry de Valence <hdevalence@hdevalence.ca> 10 11 //! Group operations for Curve25519, in Edwards form. 12 //! 13 //! ## Encoding and Decoding 14 //! 15 //! Encoding is done by converting to and from a `CompressedEdwardsY` 16 //! struct, which is a typed wrapper around `[u8; 32]`. 17 //! 18 //! ## Equality Testing 19 //! 20 //! The `EdwardsPoint` struct implements the `subtle::ConstantTimeEq` 21 //! trait for constant-time equality checking, and the Rust `Eq` trait 22 //! for variable-time equality checking. 23 //! 24 //! ## Cofactor-related functions 25 //! 26 //! The order of the group of points on the curve \\(\mathcal E\\) 27 //! is \\(|\mathcal E| = 8\ell \\), so its structure is \\( \mathcal 28 //! E = \mathcal E[8] \times \mathcal E[\ell]\\). The torsion 29 //! subgroup \\( \mathcal E[8] \\) consists of eight points of small 30 //! order. Technically, all of \\(\mathcal E\\) is torsion, but we 31 //! use the word only to refer to the small \\(\mathcal E[8]\\) part, not 32 //! the large prime-order \\(\mathcal E[\ell]\\) part. 33 //! 34 //! To test if a point is in \\( \mathcal E[8] \\), use 35 //! `EdwardsPoint::is_small_order()`. 36 //! 37 //! To test if a point is in \\( \mathcal E[\ell] \\), use 38 //! `EdwardsPoint::is_torsion_free()`. 39 //! 40 //! To multiply by the cofactor, use `EdwardsPoint::mul_by_cofactor()`. 41 //! 42 //! To avoid dealing with cofactors entirely, consider using Ristretto. 43 //! 44 //! ## Scalars 45 //! 46 //! Scalars are represented by the `Scalar` struct. To construct a scalar with a specific bit 47 //! pattern, see `Scalar::from_bits()`. 48 //! 49 //! ## Scalar Multiplication 50 //! 51 //! Scalar multiplication on Edwards points is provided by: 52 //! 53 //! * the `*` operator between a `Scalar` and a `EdwardsPoint`, which 54 //! performs constant-time variable-base scalar multiplication; 55 //! 56 //! * the `*` operator between a `Scalar` and a 57 //! `EdwardsBasepointTable`, which performs constant-time fixed-base 58 //! scalar multiplication; 59 //! 60 //! * an implementation of the 61 //! [`MultiscalarMul`](../traits/trait.MultiscalarMul.html) trait for 62 //! constant-time variable-base multiscalar multiplication; 63 //! 64 //! * an implementation of the 65 //! [`VartimeMultiscalarMul`](../traits/trait.VartimeMultiscalarMul.html) 66 //! trait for variable-time variable-base multiscalar multiplication; 67 //! 68 //! ## Implementation 69 //! 70 //! The Edwards arithmetic is implemented using the “extended twisted 71 //! coordinates” of Hisil, Wong, Carter, and Dawson, and the 72 //! corresponding complete formulas. For more details, 73 //! see the [`curve_models` submodule][curve_models] 74 //! of the internal documentation. 75 //! 76 //! ## Validity Checking 77 //! 78 //! There is no function for checking whether a point is valid. 79 //! Instead, the `EdwardsPoint` struct is guaranteed to hold a valid 80 //! point on the curve. 81 //! 82 //! We use the Rust type system to make invalid points 83 //! unrepresentable: `EdwardsPoint` objects can only be created via 84 //! successful decompression of a compressed point, or else by 85 //! operations on other (valid) `EdwardsPoint`s. 86 //! 87 //! [curve_models]: https://doc-internal.dalek.rs/curve25519_dalek/backend/serial/curve_models/index.html 88 89 // We allow non snake_case names because coordinates in projective space are 90 // traditionally denoted by the capitalisation of their respective 91 // counterparts in affine space. Yeah, you heard me, rustc, I'm gonna have my 92 // affine and projective cakes and eat both of them too. 93 #![allow(non_snake_case)] 94 95 use core::borrow::Borrow; 96 use core::fmt::Debug; 97 use core::iter::Iterator; 98 use core::iter::Sum; 99 use core::ops::{Add, Neg, Sub}; 100 use core::ops::{AddAssign, SubAssign}; 101 use core::ops::{Mul, MulAssign}; 102 103 use subtle::Choice; 104 use subtle::ConditionallyNegatable; 105 use subtle::ConditionallySelectable; 106 use subtle::ConstantTimeEq; 107 108 use constants; 109 110 use field::FieldElement; 111 use scalar::Scalar; 112 113 use montgomery::MontgomeryPoint; 114 115 use backend::serial::curve_models::AffineNielsPoint; 116 use backend::serial::curve_models::CompletedPoint; 117 use backend::serial::curve_models::ProjectiveNielsPoint; 118 use backend::serial::curve_models::ProjectivePoint; 119 120 use window::LookupTable; 121 122 #[allow(unused_imports)] 123 use prelude::*; 124 125 use traits::ValidityCheck; 126 use traits::{Identity, IsIdentity}; 127 128 #[cfg(any(feature = "alloc", feature = "std"))] 129 use traits::MultiscalarMul; 130 #[cfg(any(feature = "alloc", feature = "std"))] 131 use traits::{VartimeMultiscalarMul, VartimePrecomputedMultiscalarMul}; 132 133 #[cfg(not(all( 134 feature = "simd_backend", 135 any(target_feature = "avx2", target_feature = "avx512ifma") 136 )))] 137 use backend::serial::scalar_mul; 138 #[cfg(all( 139 feature = "simd_backend", 140 any(target_feature = "avx2", target_feature = "avx512ifma") 141 ))] 142 use backend::vector::scalar_mul; 143 144 // ------------------------------------------------------------------------ 145 // Compressed points 146 // ------------------------------------------------------------------------ 147 148 /// In "Edwards y" / "Ed25519" format, the curve point \\((x,y)\\) is 149 /// determined by the \\(y\\)-coordinate and the sign of \\(x\\). 150 /// 151 /// The first 255 bits of a `CompressedEdwardsY` represent the 152 /// \\(y\\)-coordinate. The high bit of the 32nd byte gives the sign of \\(x\\). 153 #[derive(Copy, Clone, Eq, PartialEq, Hash)] 154 pub struct CompressedEdwardsY(pub [u8; 32]); 155 156 impl ConstantTimeEq for CompressedEdwardsY { ct_eq(&self, other: &CompressedEdwardsY) -> Choice157 fn ct_eq(&self, other: &CompressedEdwardsY) -> Choice { 158 self.as_bytes().ct_eq(other.as_bytes()) 159 } 160 } 161 162 impl Debug for CompressedEdwardsY { fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result163 fn fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result { 164 write!(f, "CompressedEdwardsY: {:?}", self.as_bytes()) 165 } 166 } 167 168 impl CompressedEdwardsY { 169 /// View this `CompressedEdwardsY` as an array of bytes. as_bytes(&self) -> &[u8; 32]170 pub fn as_bytes(&self) -> &[u8; 32] { 171 &self.0 172 } 173 174 /// Copy this `CompressedEdwardsY` to an array of bytes. to_bytes(&self) -> [u8; 32]175 pub fn to_bytes(&self) -> [u8; 32] { 176 self.0 177 } 178 179 /// Attempt to decompress to an `EdwardsPoint`. 180 /// 181 /// Returns `None` if the input is not the \\(y\\)-coordinate of a 182 /// curve point. decompress(&self) -> Option<EdwardsPoint>183 pub fn decompress(&self) -> Option<EdwardsPoint> { 184 let Y = FieldElement::from_bytes(self.as_bytes()); 185 let Z = FieldElement::one(); 186 let YY = Y.square(); 187 let u = &YY - &Z; // u = y²-1 188 let v = &(&YY * &constants::EDWARDS_D) + &Z; // v = dy²+1 189 let (is_valid_y_coord, mut X) = FieldElement::sqrt_ratio_i(&u, &v); 190 191 if is_valid_y_coord.unwrap_u8() != 1u8 { return None; } 192 193 // FieldElement::sqrt_ratio_i always returns the nonnegative square root, 194 // so we negate according to the supplied sign bit. 195 let compressed_sign_bit = Choice::from(self.as_bytes()[31] >> 7); 196 X.conditional_negate(compressed_sign_bit); 197 198 Some(EdwardsPoint{ X, Y, Z, T: &X * &Y }) 199 } 200 } 201 202 // ------------------------------------------------------------------------ 203 // Serde support 204 // ------------------------------------------------------------------------ 205 // Serializes to and from `EdwardsPoint` directly, doing compression 206 // and decompression internally. This means that users can create 207 // structs containing `EdwardsPoint`s and use Serde's derived 208 // serializers to serialize those structures. 209 210 #[cfg(feature = "serde")] 211 use serde::{self, Serialize, Deserialize, Serializer, Deserializer}; 212 #[cfg(feature = "serde")] 213 use serde::de::Visitor; 214 215 #[cfg(feature = "serde")] 216 impl Serialize for EdwardsPoint { serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> where S: Serializer217 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> 218 where S: Serializer 219 { 220 use serde::ser::SerializeTuple; 221 let mut tup = serializer.serialize_tuple(32)?; 222 for byte in self.compress().as_bytes().iter() { 223 tup.serialize_element(byte)?; 224 } 225 tup.end() 226 } 227 } 228 229 #[cfg(feature = "serde")] 230 impl Serialize for CompressedEdwardsY { serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> where S: Serializer231 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> 232 where S: Serializer 233 { 234 use serde::ser::SerializeTuple; 235 let mut tup = serializer.serialize_tuple(32)?; 236 for byte in self.as_bytes().iter() { 237 tup.serialize_element(byte)?; 238 } 239 tup.end() 240 } 241 } 242 243 #[cfg(feature = "serde")] 244 impl<'de> Deserialize<'de> for EdwardsPoint { deserialize<D>(deserializer: D) -> Result<Self, D::Error> where D: Deserializer<'de>245 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error> 246 where D: Deserializer<'de> 247 { 248 struct EdwardsPointVisitor; 249 250 impl<'de> Visitor<'de> for EdwardsPointVisitor { 251 type Value = EdwardsPoint; 252 253 fn expecting(&self, formatter: &mut ::core::fmt::Formatter) -> ::core::fmt::Result { 254 formatter.write_str("a valid point in Edwards y + sign format") 255 } 256 257 fn visit_seq<A>(self, mut seq: A) -> Result<EdwardsPoint, A::Error> 258 where A: serde::de::SeqAccess<'de> 259 { 260 let mut bytes = [0u8; 32]; 261 for i in 0..32 { 262 bytes[i] = seq.next_element()? 263 .ok_or(serde::de::Error::invalid_length(i, &"expected 32 bytes"))?; 264 } 265 CompressedEdwardsY(bytes) 266 .decompress() 267 .ok_or(serde::de::Error::custom("decompression failed")) 268 } 269 } 270 271 deserializer.deserialize_tuple(32, EdwardsPointVisitor) 272 } 273 } 274 275 #[cfg(feature = "serde")] 276 impl<'de> Deserialize<'de> for CompressedEdwardsY { deserialize<D>(deserializer: D) -> Result<Self, D::Error> where D: Deserializer<'de>277 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error> 278 where D: Deserializer<'de> 279 { 280 struct CompressedEdwardsYVisitor; 281 282 impl<'de> Visitor<'de> for CompressedEdwardsYVisitor { 283 type Value = CompressedEdwardsY; 284 285 fn expecting(&self, formatter: &mut ::core::fmt::Formatter) -> ::core::fmt::Result { 286 formatter.write_str("32 bytes of data") 287 } 288 289 fn visit_seq<A>(self, mut seq: A) -> Result<CompressedEdwardsY, A::Error> 290 where A: serde::de::SeqAccess<'de> 291 { 292 let mut bytes = [0u8; 32]; 293 for i in 0..32 { 294 bytes[i] = seq.next_element()? 295 .ok_or(serde::de::Error::invalid_length(i, &"expected 32 bytes"))?; 296 } 297 Ok(CompressedEdwardsY(bytes)) 298 } 299 } 300 301 deserializer.deserialize_tuple(32, CompressedEdwardsYVisitor) 302 } 303 } 304 305 // ------------------------------------------------------------------------ 306 // Internal point representations 307 // ------------------------------------------------------------------------ 308 309 /// An `EdwardsPoint` represents a point on the Edwards form of Curve25519. 310 #[derive(Copy, Clone)] 311 #[allow(missing_docs)] 312 pub struct EdwardsPoint { 313 pub(crate) X: FieldElement, 314 pub(crate) Y: FieldElement, 315 pub(crate) Z: FieldElement, 316 pub(crate) T: FieldElement, 317 } 318 319 // ------------------------------------------------------------------------ 320 // Constructors 321 // ------------------------------------------------------------------------ 322 323 impl Identity for CompressedEdwardsY { identity() -> CompressedEdwardsY324 fn identity() -> CompressedEdwardsY { 325 CompressedEdwardsY([1, 0, 0, 0, 0, 0, 0, 0, 326 0, 0, 0, 0, 0, 0, 0, 0, 327 0, 0, 0, 0, 0, 0, 0, 0, 328 0, 0, 0, 0, 0, 0, 0, 0]) 329 } 330 } 331 332 impl Default for CompressedEdwardsY { default() -> CompressedEdwardsY333 fn default() -> CompressedEdwardsY { 334 CompressedEdwardsY::identity() 335 } 336 } 337 338 impl CompressedEdwardsY { 339 /// Construct a `CompressedEdwardsY` from a slice of bytes. 340 /// 341 /// # Panics 342 /// 343 /// If the input `bytes` slice does not have a length of 32. from_slice(bytes: &[u8]) -> CompressedEdwardsY344 pub fn from_slice(bytes: &[u8]) -> CompressedEdwardsY { 345 let mut tmp = [0u8; 32]; 346 347 tmp.copy_from_slice(bytes); 348 349 CompressedEdwardsY(tmp) 350 } 351 } 352 353 impl Identity for EdwardsPoint { identity() -> EdwardsPoint354 fn identity() -> EdwardsPoint { 355 EdwardsPoint { 356 X: FieldElement::zero(), 357 Y: FieldElement::one(), 358 Z: FieldElement::one(), 359 T: FieldElement::zero(), 360 } 361 } 362 } 363 364 impl Default for EdwardsPoint { default() -> EdwardsPoint365 fn default() -> EdwardsPoint { 366 EdwardsPoint::identity() 367 } 368 } 369 370 // ------------------------------------------------------------------------ 371 // Validity checks (for debugging, not CT) 372 // ------------------------------------------------------------------------ 373 374 impl ValidityCheck for EdwardsPoint { is_valid(&self) -> bool375 fn is_valid(&self) -> bool { 376 let point_on_curve = self.to_projective().is_valid(); 377 let on_segre_image = (&self.X * &self.Y) == (&self.Z * &self.T); 378 379 point_on_curve && on_segre_image 380 } 381 } 382 383 // ------------------------------------------------------------------------ 384 // Constant-time assignment 385 // ------------------------------------------------------------------------ 386 387 impl ConditionallySelectable for EdwardsPoint { conditional_select(a: &EdwardsPoint, b: &EdwardsPoint, choice: Choice) -> EdwardsPoint388 fn conditional_select(a: &EdwardsPoint, b: &EdwardsPoint, choice: Choice) -> EdwardsPoint { 389 EdwardsPoint { 390 X: FieldElement::conditional_select(&a.X, &b.X, choice), 391 Y: FieldElement::conditional_select(&a.Y, &b.Y, choice), 392 Z: FieldElement::conditional_select(&a.Z, &b.Z, choice), 393 T: FieldElement::conditional_select(&a.T, &b.T, choice), 394 } 395 } 396 } 397 398 // ------------------------------------------------------------------------ 399 // Equality 400 // ------------------------------------------------------------------------ 401 402 impl ConstantTimeEq for EdwardsPoint { ct_eq(&self, other: &EdwardsPoint) -> Choice403 fn ct_eq(&self, other: &EdwardsPoint) -> Choice { 404 // We would like to check that the point (X/Z, Y/Z) is equal to 405 // the point (X'/Z', Y'/Z') without converting into affine 406 // coordinates (x, y) and (x', y'), which requires two inversions. 407 // We have that X = xZ and X' = x'Z'. Thus, x = x' is equivalent to 408 // (xZ)Z' = (x'Z')Z, and similarly for the y-coordinate. 409 410 (&self.X * &other.Z).ct_eq(&(&other.X * &self.Z)) 411 & (&self.Y * &other.Z).ct_eq(&(&other.Y * &self.Z)) 412 } 413 } 414 415 impl PartialEq for EdwardsPoint { eq(&self, other: &EdwardsPoint) -> bool416 fn eq(&self, other: &EdwardsPoint) -> bool { 417 self.ct_eq(other).unwrap_u8() == 1u8 418 } 419 } 420 421 impl Eq for EdwardsPoint {} 422 423 // ------------------------------------------------------------------------ 424 // Point conversions 425 // ------------------------------------------------------------------------ 426 427 impl EdwardsPoint { 428 /// Convert to a ProjectiveNielsPoint to_projective_niels(&self) -> ProjectiveNielsPoint429 pub(crate) fn to_projective_niels(&self) -> ProjectiveNielsPoint { 430 ProjectiveNielsPoint{ 431 Y_plus_X: &self.Y + &self.X, 432 Y_minus_X: &self.Y - &self.X, 433 Z: self.Z, 434 T2d: &self.T * &constants::EDWARDS_D2, 435 } 436 } 437 438 /// Convert the representation of this point from extended 439 /// coordinates to projective coordinates. 440 /// 441 /// Free. to_projective(&self) -> ProjectivePoint442 pub(crate) fn to_projective(&self) -> ProjectivePoint { 443 ProjectivePoint{ 444 X: self.X, 445 Y: self.Y, 446 Z: self.Z, 447 } 448 } 449 450 /// Dehomogenize to a AffineNielsPoint. 451 /// Mainly for testing. to_affine_niels(&self) -> AffineNielsPoint452 pub(crate) fn to_affine_niels(&self) -> AffineNielsPoint { 453 let recip = self.Z.invert(); 454 let x = &self.X * &recip; 455 let y = &self.Y * &recip; 456 let xy2d = &(&x * &y) * &constants::EDWARDS_D2; 457 AffineNielsPoint{ 458 y_plus_x: &y + &x, 459 y_minus_x: &y - &x, 460 xy2d 461 } 462 } 463 464 /// Convert this `EdwardsPoint` on the Edwards model to the 465 /// corresponding `MontgomeryPoint` on the Montgomery model. 466 /// 467 /// This function has one exceptional case; the identity point of 468 /// the Edwards curve is sent to the 2-torsion point \\((0,0)\\) 469 /// on the Montgomery curve. 470 /// 471 /// Note that this is a one-way conversion, since the Montgomery 472 /// model does not retain sign information. to_montgomery(&self) -> MontgomeryPoint473 pub fn to_montgomery(&self) -> MontgomeryPoint { 474 // We have u = (1+y)/(1-y) = (Z+Y)/(Z-Y). 475 // 476 // The denominator is zero only when y=1, the identity point of 477 // the Edwards curve. Since 0.invert() = 0, in this case we 478 // compute the 2-torsion point (0,0). 479 let U = &self.Z + &self.Y; 480 let W = &self.Z - &self.Y; 481 let u = &U * &W.invert(); 482 MontgomeryPoint(u.to_bytes()) 483 } 484 485 /// Compress this point to `CompressedEdwardsY` format. compress(&self) -> CompressedEdwardsY486 pub fn compress(&self) -> CompressedEdwardsY { 487 let recip = self.Z.invert(); 488 let x = &self.X * &recip; 489 let y = &self.Y * &recip; 490 let mut s: [u8; 32]; 491 492 s = y.to_bytes(); 493 s[31] ^= x.is_negative().unwrap_u8() << 7; 494 CompressedEdwardsY(s) 495 } 496 } 497 498 // ------------------------------------------------------------------------ 499 // Doubling 500 // ------------------------------------------------------------------------ 501 502 impl EdwardsPoint { 503 /// Add this point to itself. double(&self) -> EdwardsPoint504 pub(crate) fn double(&self) -> EdwardsPoint { 505 self.to_projective().double().to_extended() 506 } 507 } 508 509 // ------------------------------------------------------------------------ 510 // Addition and Subtraction 511 // ------------------------------------------------------------------------ 512 513 impl<'a, 'b> Add<&'b EdwardsPoint> for &'a EdwardsPoint { 514 type Output = EdwardsPoint; add(self, other: &'b EdwardsPoint) -> EdwardsPoint515 fn add(self, other: &'b EdwardsPoint) -> EdwardsPoint { 516 (self + &other.to_projective_niels()).to_extended() 517 } 518 } 519 520 define_add_variants!(LHS = EdwardsPoint, RHS = EdwardsPoint, Output = EdwardsPoint); 521 522 impl<'b> AddAssign<&'b EdwardsPoint> for EdwardsPoint { add_assign(&mut self, _rhs: &'b EdwardsPoint)523 fn add_assign(&mut self, _rhs: &'b EdwardsPoint) { 524 *self = (self as &EdwardsPoint) + _rhs; 525 } 526 } 527 528 define_add_assign_variants!(LHS = EdwardsPoint, RHS = EdwardsPoint); 529 530 impl<'a, 'b> Sub<&'b EdwardsPoint> for &'a EdwardsPoint { 531 type Output = EdwardsPoint; sub(self, other: &'b EdwardsPoint) -> EdwardsPoint532 fn sub(self, other: &'b EdwardsPoint) -> EdwardsPoint { 533 (self - &other.to_projective_niels()).to_extended() 534 } 535 } 536 537 define_sub_variants!(LHS = EdwardsPoint, RHS = EdwardsPoint, Output = EdwardsPoint); 538 539 impl<'b> SubAssign<&'b EdwardsPoint> for EdwardsPoint { sub_assign(&mut self, _rhs: &'b EdwardsPoint)540 fn sub_assign(&mut self, _rhs: &'b EdwardsPoint) { 541 *self = (self as &EdwardsPoint) - _rhs; 542 } 543 } 544 545 define_sub_assign_variants!(LHS = EdwardsPoint, RHS = EdwardsPoint); 546 547 impl<T> Sum<T> for EdwardsPoint 548 where 549 T: Borrow<EdwardsPoint> 550 { sum<I>(iter: I) -> Self where I: Iterator<Item = T>551 fn sum<I>(iter: I) -> Self 552 where 553 I: Iterator<Item = T> 554 { 555 iter.fold(EdwardsPoint::identity(), |acc, item| acc + item.borrow()) 556 } 557 } 558 559 560 // ------------------------------------------------------------------------ 561 // Negation 562 // ------------------------------------------------------------------------ 563 564 impl<'a> Neg for &'a EdwardsPoint { 565 type Output = EdwardsPoint; 566 neg(self) -> EdwardsPoint567 fn neg(self) -> EdwardsPoint { 568 EdwardsPoint{ 569 X: -(&self.X), 570 Y: self.Y, 571 Z: self.Z, 572 T: -(&self.T), 573 } 574 } 575 } 576 577 impl Neg for EdwardsPoint { 578 type Output = EdwardsPoint; 579 neg(self) -> EdwardsPoint580 fn neg(self) -> EdwardsPoint { 581 -&self 582 } 583 } 584 585 // ------------------------------------------------------------------------ 586 // Scalar multiplication 587 // ------------------------------------------------------------------------ 588 589 impl<'b> MulAssign<&'b Scalar> for EdwardsPoint { mul_assign(&mut self, scalar: &'b Scalar)590 fn mul_assign(&mut self, scalar: &'b Scalar) { 591 let result = (self as &EdwardsPoint) * scalar; 592 *self = result; 593 } 594 } 595 596 define_mul_assign_variants!(LHS = EdwardsPoint, RHS = Scalar); 597 598 define_mul_variants!(LHS = EdwardsPoint, RHS = Scalar, Output = EdwardsPoint); 599 define_mul_variants!(LHS = Scalar, RHS = EdwardsPoint, Output = EdwardsPoint); 600 601 impl<'a, 'b> Mul<&'b Scalar> for &'a EdwardsPoint { 602 type Output = EdwardsPoint; 603 /// Scalar multiplication: compute `scalar * self`. 604 /// 605 /// For scalar multiplication of a basepoint, 606 /// `EdwardsBasepointTable` is approximately 4x faster. mul(self, scalar: &'b Scalar) -> EdwardsPoint607 fn mul(self, scalar: &'b Scalar) -> EdwardsPoint { 608 scalar_mul::variable_base::mul(self, scalar) 609 } 610 } 611 612 impl<'a, 'b> Mul<&'b EdwardsPoint> for &'a Scalar { 613 type Output = EdwardsPoint; 614 615 /// Scalar multiplication: compute `scalar * self`. 616 /// 617 /// For scalar multiplication of a basepoint, 618 /// `EdwardsBasepointTable` is approximately 4x faster. mul(self, point: &'b EdwardsPoint) -> EdwardsPoint619 fn mul(self, point: &'b EdwardsPoint) -> EdwardsPoint { 620 point * self 621 } 622 } 623 624 // ------------------------------------------------------------------------ 625 // Multiscalar Multiplication impls 626 // ------------------------------------------------------------------------ 627 628 // These use the iterator's size hint and the target settings to 629 // forward to a specific backend implementation. 630 631 #[cfg(feature = "alloc")] 632 impl MultiscalarMul for EdwardsPoint { 633 type Point = EdwardsPoint; 634 multiscalar_mul<I, J>(scalars: I, points: J) -> EdwardsPoint where I: IntoIterator, I::Item: Borrow<Scalar>, J: IntoIterator, J::Item: Borrow<EdwardsPoint>,635 fn multiscalar_mul<I, J>(scalars: I, points: J) -> EdwardsPoint 636 where 637 I: IntoIterator, 638 I::Item: Borrow<Scalar>, 639 J: IntoIterator, 640 J::Item: Borrow<EdwardsPoint>, 641 { 642 // Sanity-check lengths of input iterators 643 let mut scalars = scalars.into_iter(); 644 let mut points = points.into_iter(); 645 646 // Lower and upper bounds on iterators 647 let (s_lo, s_hi) = scalars.by_ref().size_hint(); 648 let (p_lo, p_hi) = points.by_ref().size_hint(); 649 650 // They should all be equal 651 assert_eq!(s_lo, p_lo); 652 assert_eq!(s_hi, Some(s_lo)); 653 assert_eq!(p_hi, Some(p_lo)); 654 655 // Now we know there's a single size. When we do 656 // size-dependent algorithm dispatch, use this as the hint. 657 let _size = s_lo; 658 659 scalar_mul::straus::Straus::multiscalar_mul(scalars, points) 660 } 661 } 662 663 #[cfg(feature = "alloc")] 664 impl VartimeMultiscalarMul for EdwardsPoint { 665 type Point = EdwardsPoint; 666 optional_multiscalar_mul<I, J>(scalars: I, points: J) -> Option<EdwardsPoint> where I: IntoIterator, I::Item: Borrow<Scalar>, J: IntoIterator<Item = Option<EdwardsPoint>>,667 fn optional_multiscalar_mul<I, J>(scalars: I, points: J) -> Option<EdwardsPoint> 668 where 669 I: IntoIterator, 670 I::Item: Borrow<Scalar>, 671 J: IntoIterator<Item = Option<EdwardsPoint>>, 672 { 673 // Sanity-check lengths of input iterators 674 let mut scalars = scalars.into_iter(); 675 let mut points = points.into_iter(); 676 677 // Lower and upper bounds on iterators 678 let (s_lo, s_hi) = scalars.by_ref().size_hint(); 679 let (p_lo, p_hi) = points.by_ref().size_hint(); 680 681 // They should all be equal 682 assert_eq!(s_lo, p_lo); 683 assert_eq!(s_hi, Some(s_lo)); 684 assert_eq!(p_hi, Some(p_lo)); 685 686 // Now we know there's a single size. 687 // Use this as the hint to decide which algorithm to use. 688 let size = s_lo; 689 690 if size < 190 { 691 scalar_mul::straus::Straus::optional_multiscalar_mul(scalars, points) 692 } else { 693 scalar_mul::pippenger::Pippenger::optional_multiscalar_mul(scalars, points) 694 } 695 } 696 } 697 698 /// Precomputation for variable-time multiscalar multiplication with `EdwardsPoint`s. 699 // This wraps the inner implementation in a facade type so that we can 700 // decouple stability of the inner type from the stability of the 701 // outer type. 702 #[cfg(feature = "alloc")] 703 pub struct VartimeEdwardsPrecomputation(scalar_mul::precomputed_straus::VartimePrecomputedStraus); 704 705 #[cfg(feature = "alloc")] 706 impl VartimePrecomputedMultiscalarMul for VartimeEdwardsPrecomputation { 707 type Point = EdwardsPoint; 708 new<I>(static_points: I) -> Self where I: IntoIterator, I::Item: Borrow<Self::Point>,709 fn new<I>(static_points: I) -> Self 710 where 711 I: IntoIterator, 712 I::Item: Borrow<Self::Point>, 713 { 714 Self(scalar_mul::precomputed_straus::VartimePrecomputedStraus::new(static_points)) 715 } 716 optional_mixed_multiscalar_mul<I, J, K>( &self, static_scalars: I, dynamic_scalars: J, dynamic_points: K, ) -> Option<Self::Point> where I: IntoIterator, I::Item: Borrow<Scalar>, J: IntoIterator, J::Item: Borrow<Scalar>, K: IntoIterator<Item = Option<Self::Point>>,717 fn optional_mixed_multiscalar_mul<I, J, K>( 718 &self, 719 static_scalars: I, 720 dynamic_scalars: J, 721 dynamic_points: K, 722 ) -> Option<Self::Point> 723 where 724 I: IntoIterator, 725 I::Item: Borrow<Scalar>, 726 J: IntoIterator, 727 J::Item: Borrow<Scalar>, 728 K: IntoIterator<Item = Option<Self::Point>>, 729 { 730 self.0 731 .optional_mixed_multiscalar_mul(static_scalars, dynamic_scalars, dynamic_points) 732 } 733 } 734 735 impl EdwardsPoint { 736 /// Compute \\(aA + bB\\) in variable time, where \\(B\\) is the Ed25519 basepoint. vartime_double_scalar_mul_basepoint( a: &Scalar, A: &EdwardsPoint, b: &Scalar, ) -> EdwardsPoint737 pub fn vartime_double_scalar_mul_basepoint( 738 a: &Scalar, 739 A: &EdwardsPoint, 740 b: &Scalar, 741 ) -> EdwardsPoint { 742 scalar_mul::vartime_double_base::mul(a, A, b) 743 } 744 } 745 746 /// A precomputed table of multiples of a basepoint, for accelerating 747 /// fixed-base scalar multiplication. One table, for the Ed25519 748 /// basepoint, is provided in the `constants` module. 749 /// 750 /// The basepoint tables are reasonably large (30KB), so they should 751 /// probably be boxed. 752 #[derive(Clone)] 753 pub struct EdwardsBasepointTable(pub(crate) [LookupTable<AffineNielsPoint>; 32]); 754 755 impl EdwardsBasepointTable { 756 /// The computation uses Pippenger's algorithm, as described on 757 /// page 13 of the Ed25519 paper. Write the scalar \\(a\\) in radix \\(16\\) with 758 /// coefficients in \\([-8,8)\\), i.e., 759 /// $$ 760 /// a = a\_0 + a\_1 16\^1 + \cdots + a\_{63} 16\^{63}, 761 /// $$ 762 /// with \\(-8 \leq a_i < 8\\), \\(-8 \leq a\_{63} \leq 8\\). Then 763 /// $$ 764 /// a B = a\_0 B + a\_1 16\^1 B + \cdots + a\_{63} 16\^{63} B. 765 /// $$ 766 /// Grouping even and odd coefficients gives 767 /// $$ 768 /// \begin{aligned} 769 /// a B = \quad a\_0 16\^0 B +& a\_2 16\^2 B + \cdots + a\_{62} 16\^{62} B \\\\ 770 /// + a\_1 16\^1 B +& a\_3 16\^3 B + \cdots + a\_{63} 16\^{63} B \\\\ 771 /// = \quad(a\_0 16\^0 B +& a\_2 16\^2 B + \cdots + a\_{62} 16\^{62} B) \\\\ 772 /// + 16(a\_1 16\^0 B +& a\_3 16\^2 B + \cdots + a\_{63} 16\^{62} B). \\\\ 773 /// \end{aligned} 774 /// $$ 775 /// For each \\(i = 0 \ldots 31\\), we create a lookup table of 776 /// $$ 777 /// [16\^{2i} B, \ldots, 8\cdot16\^{2i} B], 778 /// $$ 779 /// and use it to select \\( x \cdot 16\^{2i} \cdot B \\) in constant time. 780 /// 781 /// The radix-\\(16\\) representation requires that the scalar is bounded 782 /// by \\(2\^{255}\\), which is always the case. basepoint_mul(&self, scalar: &Scalar) -> EdwardsPoint783 fn basepoint_mul(&self, scalar: &Scalar) -> EdwardsPoint { 784 let a = scalar.to_radix_16(); 785 786 let tables = &self.0; 787 let mut P = EdwardsPoint::identity(); 788 789 for i in (0..64).filter(|x| x % 2 == 1) { 790 P = (&P + &tables[i/2].select(a[i])).to_extended(); 791 } 792 793 P = P.mul_by_pow_2(4); 794 795 for i in (0..64).filter(|x| x % 2 == 0) { 796 P = (&P + &tables[i/2].select(a[i])).to_extended(); 797 } 798 799 P 800 } 801 } 802 803 impl<'a, 'b> Mul<&'b Scalar> for &'a EdwardsBasepointTable { 804 type Output = EdwardsPoint; 805 806 /// Construct an `EdwardsPoint` from a `Scalar` \\(a\\) by 807 /// computing the multiple \\(aB\\) of this basepoint \\(B\\). mul(self, scalar: &'b Scalar) -> EdwardsPoint808 fn mul(self, scalar: &'b Scalar) -> EdwardsPoint { 809 // delegate to a private function so that its documentation appears in internal docs 810 self.basepoint_mul(scalar) 811 } 812 } 813 814 impl<'a, 'b> Mul<&'a EdwardsBasepointTable> for &'b Scalar { 815 type Output = EdwardsPoint; 816 817 /// Construct an `EdwardsPoint` from a `Scalar` \\(a\\) by 818 /// computing the multiple \\(aB\\) of this basepoint \\(B\\). mul(self, basepoint_table: &'a EdwardsBasepointTable) -> EdwardsPoint819 fn mul(self, basepoint_table: &'a EdwardsBasepointTable) -> EdwardsPoint { 820 basepoint_table * self 821 } 822 } 823 824 impl EdwardsBasepointTable { 825 /// Create a table of precomputed multiples of `basepoint`. create(basepoint: &EdwardsPoint) -> EdwardsBasepointTable826 pub fn create(basepoint: &EdwardsPoint) -> EdwardsBasepointTable { 827 // XXX use init_with 828 let mut table = EdwardsBasepointTable([LookupTable::default(); 32]); 829 let mut P = *basepoint; 830 for i in 0..32 { 831 // P = (16^2)^i * B 832 table.0[i] = LookupTable::from(&P); 833 P = P.mul_by_pow_2(8); 834 } 835 table 836 } 837 838 /// Get the basepoint for this table as an `EdwardsPoint`. basepoint(&self) -> EdwardsPoint839 pub fn basepoint(&self) -> EdwardsPoint { 840 // self.0[0].select(1) = 1*(16^2)^0*B 841 // but as an `AffineNielsPoint`, so add identity to convert to extended. 842 (&EdwardsPoint::identity() + &self.0[0].select(1)).to_extended() 843 } 844 } 845 846 impl EdwardsPoint { 847 /// Multiply by the cofactor: return \\([8]P\\). mul_by_cofactor(&self) -> EdwardsPoint848 pub fn mul_by_cofactor(&self) -> EdwardsPoint { 849 self.mul_by_pow_2(3) 850 } 851 852 /// Compute \\([2\^k] P \\) by successive doublings. Requires \\( k > 0 \\). mul_by_pow_2(&self, k: u32) -> EdwardsPoint853 pub(crate) fn mul_by_pow_2(&self, k: u32) -> EdwardsPoint { 854 debug_assert!( k > 0 ); 855 let mut r: CompletedPoint; 856 let mut s = self.to_projective(); 857 for _ in 0..(k-1) { 858 r = s.double(); s = r.to_projective(); 859 } 860 // Unroll last iteration so we can go directly to_extended() 861 s.double().to_extended() 862 } 863 864 /// Determine if this point is of small order. 865 /// 866 /// # Return 867 /// 868 /// * `true` if `self` is in the torsion subgroup \\( \mathcal E[8] \\); 869 /// * `false` if `self` is not in the torsion subgroup \\( \mathcal E[8] \\). 870 /// 871 /// # Example 872 /// 873 /// ``` 874 /// use curve25519_dalek_ng::constants; 875 /// 876 /// // Generator of the prime-order subgroup 877 /// let P = constants::ED25519_BASEPOINT_POINT; 878 /// // Generator of the torsion subgroup 879 /// let Q = constants::EIGHT_TORSION[1]; 880 /// 881 /// // P has large order 882 /// assert_eq!(P.is_small_order(), false); 883 /// 884 /// // Q has small order 885 /// assert_eq!(Q.is_small_order(), true); 886 /// ``` is_small_order(&self) -> bool887 pub fn is_small_order(&self) -> bool { 888 self.mul_by_cofactor().is_identity() 889 } 890 891 /// Determine if this point is “torsion-free”, i.e., is contained in 892 /// the prime-order subgroup. 893 /// 894 /// # Return 895 /// 896 /// * `true` if `self` has zero torsion component and is in the 897 /// prime-order subgroup; 898 /// * `false` if `self` has a nonzero torsion component and is not 899 /// in the prime-order subgroup. 900 /// 901 /// # Example 902 /// 903 /// ``` 904 /// use curve25519_dalek_ng::constants; 905 /// 906 /// // Generator of the prime-order subgroup 907 /// let P = constants::ED25519_BASEPOINT_POINT; 908 /// // Generator of the torsion subgroup 909 /// let Q = constants::EIGHT_TORSION[1]; 910 /// 911 /// // P is torsion-free 912 /// assert_eq!(P.is_torsion_free(), true); 913 /// 914 /// // P + Q is not torsion-free 915 /// assert_eq!((P+Q).is_torsion_free(), false); 916 /// ``` is_torsion_free(&self) -> bool917 pub fn is_torsion_free(&self) -> bool { 918 (self * constants::BASEPOINT_ORDER).is_identity() 919 } 920 } 921 922 // ------------------------------------------------------------------------ 923 // Debug traits 924 // ------------------------------------------------------------------------ 925 926 impl Debug for EdwardsPoint { fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result927 fn fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result { 928 write!(f, "EdwardsPoint{{\n\tX: {:?},\n\tY: {:?},\n\tZ: {:?},\n\tT: {:?}\n}}", 929 &self.X, &self.Y, &self.Z, &self.T) 930 } 931 } 932 933 impl Debug for EdwardsBasepointTable { fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result934 fn fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result { 935 write!(f, "EdwardsBasepointTable([\n")?; 936 for i in 0..32 { 937 write!(f, "\t{:?},\n", &self.0[i])?; 938 } 939 write!(f, "])") 940 } 941 } 942 943 // ------------------------------------------------------------------------ 944 // Tests 945 // ------------------------------------------------------------------------ 946 947 #[cfg(test)] 948 mod test { 949 use field::FieldElement; 950 use scalar::Scalar; 951 use subtle::ConditionallySelectable; 952 use constants; 953 use super::*; 954 955 /// X coordinate of the basepoint. 956 /// = 15112221349535400772501151409588531511454012693041857206046113283949847762202 957 static BASE_X_COORD_BYTES: [u8; 32] = 958 [0x1a, 0xd5, 0x25, 0x8f, 0x60, 0x2d, 0x56, 0xc9, 0xb2, 0xa7, 0x25, 0x95, 0x60, 0xc7, 0x2c, 0x69, 959 0x5c, 0xdc, 0xd6, 0xfd, 0x31, 0xe2, 0xa4, 0xc0, 0xfe, 0x53, 0x6e, 0xcd, 0xd3, 0x36, 0x69, 0x21]; 960 961 /// Compressed Edwards Y form of 2*basepoint. 962 static BASE2_CMPRSSD: CompressedEdwardsY = 963 CompressedEdwardsY([0xc9, 0xa3, 0xf8, 0x6a, 0xae, 0x46, 0x5f, 0xe, 964 0x56, 0x51, 0x38, 0x64, 0x51, 0x0f, 0x39, 0x97, 965 0x56, 0x1f, 0xa2, 0xc9, 0xe8, 0x5e, 0xa2, 0x1d, 966 0xc2, 0x29, 0x23, 0x09, 0xf3, 0xcd, 0x60, 0x22]); 967 968 /// Compressed Edwards Y form of 16*basepoint. 969 static BASE16_CMPRSSD: CompressedEdwardsY = 970 CompressedEdwardsY([0xeb, 0x27, 0x67, 0xc1, 0x37, 0xab, 0x7a, 0xd8, 971 0x27, 0x9c, 0x07, 0x8e, 0xff, 0x11, 0x6a, 0xb0, 972 0x78, 0x6e, 0xad, 0x3a, 0x2e, 0x0f, 0x98, 0x9f, 973 0x72, 0xc3, 0x7f, 0x82, 0xf2, 0x96, 0x96, 0x70]); 974 975 /// 4493907448824000747700850167940867464579944529806937181821189941592931634714 976 pub static A_SCALAR: Scalar = Scalar{ 977 bytes: [ 978 0x1a, 0x0e, 0x97, 0x8a, 0x90, 0xf6, 0x62, 0x2d, 979 0x37, 0x47, 0x02, 0x3f, 0x8a, 0xd8, 0x26, 0x4d, 980 0xa7, 0x58, 0xaa, 0x1b, 0x88, 0xe0, 0x40, 0xd1, 981 0x58, 0x9e, 0x7b, 0x7f, 0x23, 0x76, 0xef, 0x09, 982 ], 983 }; 984 985 /// 2506056684125797857694181776241676200180934651973138769173342316833279714961 986 pub static B_SCALAR: Scalar = Scalar{ 987 bytes: [ 988 0x91, 0x26, 0x7a, 0xcf, 0x25, 0xc2, 0x09, 0x1b, 989 0xa2, 0x17, 0x74, 0x7b, 0x66, 0xf0, 0xb3, 0x2e, 990 0x9d, 0xf2, 0xa5, 0x67, 0x41, 0xcf, 0xda, 0xc4, 991 0x56, 0xa7, 0xd4, 0xaa, 0xb8, 0x60, 0x8a, 0x05, 992 ], 993 }; 994 995 /// A_SCALAR * basepoint, computed with ed25519.py 996 pub static A_TIMES_BASEPOINT: CompressedEdwardsY = CompressedEdwardsY([ 997 0xea, 0x27, 0xe2, 0x60, 0x53, 0xdf, 0x1b, 0x59, 998 0x56, 0xf1, 0x4d, 0x5d, 0xec, 0x3c, 0x34, 0xc3, 999 0x84, 0xa2, 0x69, 0xb7, 0x4c, 0xc3, 0x80, 0x3e, 1000 0xa8, 0xe2, 0xe7, 0xc9, 0x42, 0x5e, 0x40, 0xa5]); 1001 1002 /// A_SCALAR * (A_TIMES_BASEPOINT) + B_SCALAR * BASEPOINT 1003 /// computed with ed25519.py 1004 static DOUBLE_SCALAR_MULT_RESULT: CompressedEdwardsY = CompressedEdwardsY([ 1005 0x7d, 0xfd, 0x6c, 0x45, 0xaf, 0x6d, 0x6e, 0x0e, 1006 0xba, 0x20, 0x37, 0x1a, 0x23, 0x64, 0x59, 0xc4, 1007 0xc0, 0x46, 0x83, 0x43, 0xde, 0x70, 0x4b, 0x85, 1008 0x09, 0x6f, 0xfe, 0x35, 0x4f, 0x13, 0x2b, 0x42]); 1009 1010 /// Test round-trip decompression for the basepoint. 1011 #[test] basepoint_decompression_compression()1012 fn basepoint_decompression_compression() { 1013 let base_X = FieldElement::from_bytes(&BASE_X_COORD_BYTES); 1014 let bp = constants::ED25519_BASEPOINT_COMPRESSED.decompress().unwrap(); 1015 assert!(bp.is_valid()); 1016 // Check that decompression actually gives the correct X coordinate 1017 assert_eq!(base_X, bp.X); 1018 assert_eq!(bp.compress(), constants::ED25519_BASEPOINT_COMPRESSED); 1019 } 1020 1021 /// Test sign handling in decompression 1022 #[test] decompression_sign_handling()1023 fn decompression_sign_handling() { 1024 // Manually set the high bit of the last byte to flip the sign 1025 let mut minus_basepoint_bytes = constants::ED25519_BASEPOINT_COMPRESSED.as_bytes().clone(); 1026 minus_basepoint_bytes[31] |= 1 << 7; 1027 let minus_basepoint = CompressedEdwardsY(minus_basepoint_bytes) 1028 .decompress().unwrap(); 1029 // Test projective coordinates exactly since we know they should 1030 // only differ by a flipped sign. 1031 assert_eq!(minus_basepoint.X, -(&constants::ED25519_BASEPOINT_POINT.X)); 1032 assert_eq!(minus_basepoint.Y, constants::ED25519_BASEPOINT_POINT.Y); 1033 assert_eq!(minus_basepoint.Z, constants::ED25519_BASEPOINT_POINT.Z); 1034 assert_eq!(minus_basepoint.T, -(&constants::ED25519_BASEPOINT_POINT.T)); 1035 } 1036 1037 /// Test that computing 1*basepoint gives the correct basepoint. 1038 #[test] basepoint_mult_one_vs_basepoint()1039 fn basepoint_mult_one_vs_basepoint() { 1040 let bp = &constants::ED25519_BASEPOINT_TABLE * &Scalar::one(); 1041 let compressed = bp.compress(); 1042 assert_eq!(compressed, constants::ED25519_BASEPOINT_COMPRESSED); 1043 } 1044 1045 /// Test that `EdwardsBasepointTable::basepoint()` gives the correct basepoint. 1046 #[test] basepoint_table_basepoint_function_correct()1047 fn basepoint_table_basepoint_function_correct() { 1048 let bp = constants::ED25519_BASEPOINT_TABLE.basepoint(); 1049 assert_eq!(bp.compress(), constants::ED25519_BASEPOINT_COMPRESSED); 1050 } 1051 1052 /// Test `impl Add<EdwardsPoint> for EdwardsPoint` 1053 /// using basepoint + basepoint versus the 2*basepoint constant. 1054 #[test] basepoint_plus_basepoint_vs_basepoint2()1055 fn basepoint_plus_basepoint_vs_basepoint2() { 1056 let bp = constants::ED25519_BASEPOINT_POINT; 1057 let bp_added = &bp + &bp; 1058 assert_eq!(bp_added.compress(), BASE2_CMPRSSD); 1059 } 1060 1061 /// Test `impl Add<ProjectiveNielsPoint> for EdwardsPoint` 1062 /// using the basepoint, basepoint2 constants 1063 #[test] basepoint_plus_basepoint_projective_niels_vs_basepoint2()1064 fn basepoint_plus_basepoint_projective_niels_vs_basepoint2() { 1065 let bp = constants::ED25519_BASEPOINT_POINT; 1066 let bp_added = (&bp + &bp.to_projective_niels()).to_extended(); 1067 assert_eq!(bp_added.compress(), BASE2_CMPRSSD); 1068 } 1069 1070 /// Test `impl Add<AffineNielsPoint> for EdwardsPoint` 1071 /// using the basepoint, basepoint2 constants 1072 #[test] basepoint_plus_basepoint_affine_niels_vs_basepoint2()1073 fn basepoint_plus_basepoint_affine_niels_vs_basepoint2() { 1074 let bp = constants::ED25519_BASEPOINT_POINT; 1075 let bp_affine_niels = bp.to_affine_niels(); 1076 let bp_added = (&bp + &bp_affine_niels).to_extended(); 1077 assert_eq!(bp_added.compress(), BASE2_CMPRSSD); 1078 } 1079 1080 /// Check that equality of `EdwardsPoints` handles projective 1081 /// coordinates correctly. 1082 #[test] extended_point_equality_handles_scaling()1083 fn extended_point_equality_handles_scaling() { 1084 let mut two_bytes = [0u8; 32]; two_bytes[0] = 2; 1085 let id1 = EdwardsPoint::identity(); 1086 let id2 = EdwardsPoint{ 1087 X: FieldElement::zero(), 1088 Y: FieldElement::from_bytes(&two_bytes), 1089 Z: FieldElement::from_bytes(&two_bytes), 1090 T: FieldElement::zero() 1091 }; 1092 assert_eq!(id1.ct_eq(&id2).unwrap_u8(), 1u8); 1093 } 1094 1095 /// Sanity check for conversion to precomputed points 1096 #[test] to_affine_niels_clears_denominators()1097 fn to_affine_niels_clears_denominators() { 1098 // construct a point as aB so it has denominators (ie. Z != 1) 1099 let aB = &constants::ED25519_BASEPOINT_TABLE * &A_SCALAR; 1100 let aB_affine_niels = aB.to_affine_niels(); 1101 let also_aB = (&EdwardsPoint::identity() + &aB_affine_niels).to_extended(); 1102 assert_eq!( aB.compress(), 1103 also_aB.compress()); 1104 } 1105 1106 /// Test basepoint_mult versus a known scalar multiple from ed25519.py 1107 #[test] basepoint_mult_vs_ed25519py()1108 fn basepoint_mult_vs_ed25519py() { 1109 let aB = &constants::ED25519_BASEPOINT_TABLE * &A_SCALAR; 1110 assert_eq!(aB.compress(), A_TIMES_BASEPOINT); 1111 } 1112 1113 /// Test that multiplication by the basepoint order kills the basepoint 1114 #[test] basepoint_mult_by_basepoint_order()1115 fn basepoint_mult_by_basepoint_order() { 1116 let B = &constants::ED25519_BASEPOINT_TABLE; 1117 let should_be_id = B * &constants::BASEPOINT_ORDER; 1118 assert!(should_be_id.is_identity()); 1119 } 1120 1121 /// Test precomputed basepoint mult 1122 #[test] test_precomputed_basepoint_mult()1123 fn test_precomputed_basepoint_mult() { 1124 let aB_1 = &constants::ED25519_BASEPOINT_TABLE * &A_SCALAR; 1125 let aB_2 = &constants::ED25519_BASEPOINT_POINT * &A_SCALAR; 1126 assert_eq!(aB_1.compress(), aB_2.compress()); 1127 } 1128 1129 /// Test scalar_mul versus a known scalar multiple from ed25519.py 1130 #[test] scalar_mul_vs_ed25519py()1131 fn scalar_mul_vs_ed25519py() { 1132 let aB = &constants::ED25519_BASEPOINT_POINT * &A_SCALAR; 1133 assert_eq!(aB.compress(), A_TIMES_BASEPOINT); 1134 } 1135 1136 /// Test basepoint.double() versus the 2*basepoint constant. 1137 #[test] basepoint_double_vs_basepoint2()1138 fn basepoint_double_vs_basepoint2() { 1139 assert_eq!(constants::ED25519_BASEPOINT_POINT.double().compress(), 1140 BASE2_CMPRSSD); 1141 } 1142 1143 /// Test that computing 2*basepoint is the same as basepoint.double() 1144 #[test] basepoint_mult_two_vs_basepoint2()1145 fn basepoint_mult_two_vs_basepoint2() { 1146 let two = Scalar::from(2u64); 1147 let bp2 = &constants::ED25519_BASEPOINT_TABLE * &two; 1148 assert_eq!(bp2.compress(), BASE2_CMPRSSD); 1149 } 1150 1151 /// Check that converting to projective and then back to extended round-trips. 1152 #[test] basepoint_projective_extended_round_trip()1153 fn basepoint_projective_extended_round_trip() { 1154 assert_eq!(constants::ED25519_BASEPOINT_POINT 1155 .to_projective().to_extended().compress(), 1156 constants::ED25519_BASEPOINT_COMPRESSED); 1157 } 1158 1159 /// Test computing 16*basepoint vs mul_by_pow_2(4) 1160 #[test] basepoint16_vs_mul_by_pow_2_4()1161 fn basepoint16_vs_mul_by_pow_2_4() { 1162 let bp16 = constants::ED25519_BASEPOINT_POINT.mul_by_pow_2(4); 1163 assert_eq!(bp16.compress(), BASE16_CMPRSSD); 1164 } 1165 1166 #[test] impl_sum()1167 fn impl_sum() { 1168 1169 // Test that sum works for non-empty iterators 1170 let BASE = constants::ED25519_BASEPOINT_POINT; 1171 1172 let s1 = Scalar::from(999u64); 1173 let P1 = &BASE * &s1; 1174 1175 let s2 = Scalar::from(333u64); 1176 let P2 = &BASE * &s2; 1177 1178 let vec = vec![P1.clone(), P2.clone()]; 1179 let sum: EdwardsPoint = vec.iter().sum(); 1180 1181 assert_eq!(sum, P1 + P2); 1182 1183 // Test that sum works for the empty iterator 1184 let empty_vector: Vec<EdwardsPoint> = vec![]; 1185 let sum: EdwardsPoint = empty_vector.iter().sum(); 1186 1187 assert_eq!(sum, EdwardsPoint::identity()); 1188 1189 // Test that sum works on owning iterators 1190 let s = Scalar::from(2u64); 1191 let mapped = vec.iter().map(|x| x * s); 1192 let sum: EdwardsPoint = mapped.sum(); 1193 1194 assert_eq!(sum, &P1 * &s + &P2 * &s); 1195 } 1196 1197 1198 /// Test that the conditional assignment trait works for AffineNielsPoints. 1199 #[test] conditional_assign_for_affine_niels_point()1200 fn conditional_assign_for_affine_niels_point() { 1201 let id = AffineNielsPoint::identity(); 1202 let mut p1 = AffineNielsPoint::identity(); 1203 let bp = constants::ED25519_BASEPOINT_POINT.to_affine_niels(); 1204 1205 p1.conditional_assign(&bp, Choice::from(0)); 1206 assert_eq!(p1, id); 1207 p1.conditional_assign(&bp, Choice::from(1)); 1208 assert_eq!(p1, bp); 1209 } 1210 1211 #[test] is_small_order()1212 fn is_small_order() { 1213 // The basepoint has large prime order 1214 assert!(!constants::ED25519_BASEPOINT_POINT.is_small_order()); 1215 // constants::EIGHT_TORSION has all points of small order. 1216 for torsion_point in &constants::EIGHT_TORSION { 1217 assert!(torsion_point.is_small_order()); 1218 } 1219 } 1220 1221 #[test] compressed_identity()1222 fn compressed_identity() { 1223 assert_eq!(EdwardsPoint::identity().compress(), 1224 CompressedEdwardsY::identity()); 1225 } 1226 1227 #[test] is_identity()1228 fn is_identity() { 1229 assert!( EdwardsPoint::identity().is_identity()); 1230 assert!(!constants::ED25519_BASEPOINT_POINT.is_identity()); 1231 } 1232 1233 /// Rust's debug builds have overflow and underflow trapping, 1234 /// and enable `debug_assert!()`. This performs many scalar 1235 /// multiplications to attempt to trigger possible overflows etc. 1236 /// 1237 /// For instance, the `u64` `Mul` implementation for 1238 /// `FieldElements` requires the input `Limb`s to be bounded by 1239 /// 2^54, but we cannot enforce this dynamically at runtime, or 1240 /// statically at compile time (until Rust gets type-level 1241 /// integers, at which point we can encode "bits of headroom" into 1242 /// the type system and prove correctness). 1243 #[test] monte_carlo_overflow_underflow_debug_assert_test()1244 fn monte_carlo_overflow_underflow_debug_assert_test() { 1245 let mut P = constants::ED25519_BASEPOINT_POINT; 1246 // N.B. each scalar_mul does 1407 field mults, 1024 field squarings, 1247 // so this does ~ 1M of each operation. 1248 for _ in 0..1_000 { 1249 P *= &A_SCALAR; 1250 } 1251 } 1252 1253 #[test] scalarmult_extended_point_works_both_ways()1254 fn scalarmult_extended_point_works_both_ways() { 1255 let G: EdwardsPoint = constants::ED25519_BASEPOINT_POINT; 1256 let s: Scalar = A_SCALAR; 1257 1258 let P1 = &G * &s; 1259 let P2 = &s * &G; 1260 1261 assert!(P1.compress().to_bytes() == P2.compress().to_bytes()); 1262 } 1263 1264 // A single iteration of a consistency check for MSM. multiscalar_consistency_iter(n: usize)1265 fn multiscalar_consistency_iter(n: usize) { 1266 use core::iter; 1267 let mut rng = rand::thread_rng(); 1268 1269 // Construct random coefficients x0, ..., x_{n-1}, 1270 // followed by some extra hardcoded ones. 1271 let xs = (0..n) 1272 .map(|_| Scalar::random(&mut rng)) 1273 // The largest scalar allowed by the type system, 2^255-1 1274 .chain(iter::once(Scalar::from_bits([0xff; 32]))) 1275 .collect::<Vec<_>>(); 1276 let check = xs.iter() 1277 .map(|xi| xi * xi) 1278 .sum::<Scalar>(); 1279 1280 // Construct points G_i = x_i * B 1281 let Gs = xs.iter() 1282 .map(|xi| xi * &constants::ED25519_BASEPOINT_TABLE) 1283 .collect::<Vec<_>>(); 1284 1285 // Compute H1 = <xs, Gs> (consttime) 1286 let H1 = EdwardsPoint::multiscalar_mul(&xs, &Gs); 1287 // Compute H2 = <xs, Gs> (vartime) 1288 let H2 = EdwardsPoint::vartime_multiscalar_mul(&xs, &Gs); 1289 // Compute H3 = <xs, Gs> = sum(xi^2) * B 1290 let H3 = &check * &constants::ED25519_BASEPOINT_TABLE; 1291 1292 assert_eq!(H1, H3); 1293 assert_eq!(H2, H3); 1294 } 1295 1296 // Use different multiscalar sizes to hit different internal 1297 // parameters. 1298 1299 #[test] multiscalar_consistency_n_100()1300 fn multiscalar_consistency_n_100() { 1301 let iters = 50; 1302 for _ in 0..iters { 1303 multiscalar_consistency_iter(100); 1304 } 1305 } 1306 1307 #[test] multiscalar_consistency_n_250()1308 fn multiscalar_consistency_n_250() { 1309 let iters = 50; 1310 for _ in 0..iters { 1311 multiscalar_consistency_iter(250); 1312 } 1313 } 1314 1315 #[test] multiscalar_consistency_n_500()1316 fn multiscalar_consistency_n_500() { 1317 let iters = 50; 1318 for _ in 0..iters { 1319 multiscalar_consistency_iter(500); 1320 } 1321 } 1322 1323 #[test] multiscalar_consistency_n_1000()1324 fn multiscalar_consistency_n_1000() { 1325 let iters = 50; 1326 for _ in 0..iters { 1327 multiscalar_consistency_iter(1000); 1328 } 1329 } 1330 1331 #[test] vartime_precomputed_vs_nonprecomputed_multiscalar()1332 fn vartime_precomputed_vs_nonprecomputed_multiscalar() { 1333 let mut rng = rand::thread_rng(); 1334 1335 let B = &::constants::ED25519_BASEPOINT_TABLE; 1336 1337 let static_scalars = (0..128) 1338 .map(|_| Scalar::random(&mut rng)) 1339 .collect::<Vec<_>>(); 1340 1341 let dynamic_scalars = (0..128) 1342 .map(|_| Scalar::random(&mut rng)) 1343 .collect::<Vec<_>>(); 1344 1345 let check_scalar: Scalar = static_scalars 1346 .iter() 1347 .chain(dynamic_scalars.iter()) 1348 .map(|s| s * s) 1349 .sum(); 1350 1351 let static_points = static_scalars.iter().map(|s| s * B).collect::<Vec<_>>(); 1352 let dynamic_points = dynamic_scalars.iter().map(|s| s * B).collect::<Vec<_>>(); 1353 1354 let precomputation = VartimeEdwardsPrecomputation::new(static_points.iter()); 1355 1356 let P = precomputation.vartime_mixed_multiscalar_mul( 1357 &static_scalars, 1358 &dynamic_scalars, 1359 &dynamic_points, 1360 ); 1361 1362 use traits::VartimeMultiscalarMul; 1363 let Q = EdwardsPoint::vartime_multiscalar_mul( 1364 static_scalars.iter().chain(dynamic_scalars.iter()), 1365 static_points.iter().chain(dynamic_points.iter()), 1366 ); 1367 1368 let R = &check_scalar * B; 1369 1370 assert_eq!(P.compress(), R.compress()); 1371 assert_eq!(Q.compress(), R.compress()); 1372 } 1373 1374 mod vartime { 1375 use super::super::*; 1376 use super::{A_SCALAR, B_SCALAR, A_TIMES_BASEPOINT, DOUBLE_SCALAR_MULT_RESULT}; 1377 1378 /// Test double_scalar_mul_vartime vs ed25519.py 1379 #[test] double_scalar_mul_basepoint_vs_ed25519py()1380 fn double_scalar_mul_basepoint_vs_ed25519py() { 1381 let A = A_TIMES_BASEPOINT.decompress().unwrap(); 1382 let result = EdwardsPoint::vartime_double_scalar_mul_basepoint(&A_SCALAR, &A, &B_SCALAR); 1383 assert_eq!(result.compress(), DOUBLE_SCALAR_MULT_RESULT); 1384 } 1385 1386 #[test] multiscalar_mul_vs_ed25519py()1387 fn multiscalar_mul_vs_ed25519py() { 1388 let A = A_TIMES_BASEPOINT.decompress().unwrap(); 1389 let result = EdwardsPoint::vartime_multiscalar_mul( 1390 &[A_SCALAR, B_SCALAR], 1391 &[A, constants::ED25519_BASEPOINT_POINT] 1392 ); 1393 assert_eq!(result.compress(), DOUBLE_SCALAR_MULT_RESULT); 1394 } 1395 1396 #[test] multiscalar_mul_vartime_vs_consttime()1397 fn multiscalar_mul_vartime_vs_consttime() { 1398 let A = A_TIMES_BASEPOINT.decompress().unwrap(); 1399 let result_vartime = EdwardsPoint::vartime_multiscalar_mul( 1400 &[A_SCALAR, B_SCALAR], 1401 &[A, constants::ED25519_BASEPOINT_POINT] 1402 ); 1403 let result_consttime = EdwardsPoint::multiscalar_mul( 1404 &[A_SCALAR, B_SCALAR], 1405 &[A, constants::ED25519_BASEPOINT_POINT] 1406 ); 1407 1408 assert_eq!(result_vartime.compress(), result_consttime.compress()); 1409 } 1410 } 1411 1412 #[test] 1413 #[cfg(feature = "serde")] serde_bincode_basepoint_roundtrip()1414 fn serde_bincode_basepoint_roundtrip() { 1415 use bincode; 1416 1417 let encoded = bincode::serialize(&constants::ED25519_BASEPOINT_POINT).unwrap(); 1418 let enc_compressed = bincode::serialize(&constants::ED25519_BASEPOINT_COMPRESSED).unwrap(); 1419 assert_eq!(encoded, enc_compressed); 1420 1421 // Check that the encoding is 32 bytes exactly 1422 assert_eq!(encoded.len(), 32); 1423 1424 let dec_uncompressed: EdwardsPoint = bincode::deserialize(&encoded).unwrap(); 1425 let dec_compressed: CompressedEdwardsY = bincode::deserialize(&encoded).unwrap(); 1426 1427 assert_eq!(dec_uncompressed, constants::ED25519_BASEPOINT_POINT); 1428 assert_eq!(dec_compressed, constants::ED25519_BASEPOINT_COMPRESSED); 1429 1430 // Check that the encoding itself matches the usual one 1431 let raw_bytes = constants::ED25519_BASEPOINT_COMPRESSED.as_bytes(); 1432 let bp: EdwardsPoint = bincode::deserialize(raw_bytes).unwrap(); 1433 assert_eq!(bp, constants::ED25519_BASEPOINT_POINT); 1434 } 1435 } 1436