1 // Copyright 2016 Brian Smith. 2 // 3 // Permission to use, copy, modify, and/or distribute this software for any 4 // purpose with or without fee is hereby granted, provided that the above 5 // copyright notice and this permission notice appear in all copies. 6 // 7 // THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHORS DISCLAIM ALL WARRANTIES 8 // WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 9 // MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY 10 // SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 11 // WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION 12 // OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN 13 // CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 14 15 use crate::{arithmetic::montgomery::*, c, error, limb::*}; 16 use core::marker::PhantomData; 17 18 pub use self::elem::*; 19 20 /// A field element, i.e. an element of ℤ/qℤ for the curve's field modulus 21 /// *q*. 22 pub type Elem<E> = elem::Elem<Q, E>; 23 24 /// Represents the (prime) order *q* of the curve's prime field. 25 #[derive(Clone, Copy)] 26 pub enum Q {} 27 28 /// A scalar. Its value is in [0, n). Zero-valued scalars are forbidden in most 29 /// contexts. 30 pub type Scalar<E = Unencoded> = elem::Elem<N, E>; 31 32 /// Represents the prime order *n* of the curve's group. 33 #[derive(Clone, Copy)] 34 pub enum N {} 35 36 pub struct Point { 37 // The coordinates are stored in a contiguous array, where the first 38 // `ops.num_limbs` elements are the X coordinate, the next 39 // `ops.num_limbs` elements are the Y coordinate, and the next 40 // `ops.num_limbs` elements are the Z coordinate. This layout is dictated 41 // by the requirements of the GFp_nistz256 code. 42 xyz: [Limb; 3 * MAX_LIMBS], 43 } 44 45 impl Point { 46 pub fn new_at_infinity() -> Point { 47 Point { 48 xyz: [0; 3 * MAX_LIMBS], 49 } 50 } 51 } 52 53 static ONE: Elem<Unencoded> = Elem { 54 limbs: limbs![1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 55 m: PhantomData, 56 encoding: PhantomData, 57 }; 58 59 /// Operations and values needed by all curve operations. 60 pub struct CommonOps { 61 pub num_limbs: usize, 62 q: Modulus, 63 pub n: Elem<Unencoded>, 64 65 pub a: Elem<R>, // Must be -3 mod q 66 pub b: Elem<R>, 67 68 // In all cases, `r`, `a`, and `b` may all alias each other. 69 elem_add_impl: unsafe extern "C" fn(r: *mut Limb, a: *const Limb, b: *const Limb), 70 elem_mul_mont: unsafe extern "C" fn(r: *mut Limb, a: *const Limb, b: *const Limb), 71 elem_sqr_mont: unsafe extern "C" fn(r: *mut Limb, a: *const Limb), 72 73 point_add_jacobian_impl: unsafe extern "C" fn(r: *mut Limb, a: *const Limb, b: *const Limb), 74 } 75 76 impl CommonOps { 77 #[inline] 78 pub fn elem_add<E: Encoding>(&self, a: &mut Elem<E>, b: &Elem<E>) { 79 binary_op_assign(self.elem_add_impl, a, b) 80 } 81 82 #[inline] 83 pub fn elems_are_equal(&self, a: &Elem<R>, b: &Elem<R>) -> LimbMask { 84 limbs_equal_limbs_consttime(&a.limbs[..self.num_limbs], &b.limbs[..self.num_limbs]) 85 } 86 87 #[inline] 88 pub fn elem_unencoded(&self, a: &Elem<R>) -> Elem<Unencoded> { 89 self.elem_product(a, &ONE) 90 } 91 92 #[inline] 93 pub fn elem_mul(&self, a: &mut Elem<R>, b: &Elem<R>) { 94 binary_op_assign(self.elem_mul_mont, a, b) 95 } 96 97 #[inline] 98 pub fn elem_product<EA: Encoding, EB: Encoding>( 99 &self, 100 a: &Elem<EA>, 101 b: &Elem<EB>, 102 ) -> Elem<<(EA, EB) as ProductEncoding>::Output> 103 where 104 (EA, EB): ProductEncoding, 105 { 106 mul_mont(self.elem_mul_mont, a, b) 107 } 108 109 #[inline] 110 pub fn elem_square(&self, a: &mut Elem<R>) { 111 unary_op_assign(self.elem_sqr_mont, a); 112 } 113 114 #[inline] 115 pub fn elem_squared(&self, a: &Elem<R>) -> Elem<R> { 116 unary_op(self.elem_sqr_mont, a) 117 } 118 119 #[inline] 120 pub fn is_zero<M, E: Encoding>(&self, a: &elem::Elem<M, E>) -> bool { 121 limbs_are_zero_constant_time(&a.limbs[..self.num_limbs]) == LimbMask::True 122 } 123 124 pub fn elem_verify_is_not_zero(&self, a: &Elem<R>) -> Result<(), error::Unspecified> { 125 if self.is_zero(a) { 126 Err(error::Unspecified) 127 } else { 128 Ok(()) 129 } 130 } 131 132 pub fn point_sum(&self, a: &Point, b: &Point) -> Point { 133 let mut r = Point::new_at_infinity(); 134 unsafe { 135 (self.point_add_jacobian_impl)(r.xyz.as_mut_ptr(), a.xyz.as_ptr(), b.xyz.as_ptr()) 136 } 137 r 138 } 139 140 pub fn point_x(&self, p: &Point) -> Elem<R> { 141 let mut r = Elem::zero(); 142 r.limbs[..self.num_limbs].copy_from_slice(&p.xyz[0..self.num_limbs]); 143 r 144 } 145 146 pub fn point_y(&self, p: &Point) -> Elem<R> { 147 let mut r = Elem::zero(); 148 r.limbs[..self.num_limbs].copy_from_slice(&p.xyz[self.num_limbs..(2 * self.num_limbs)]); 149 r 150 } 151 152 pub fn point_z(&self, p: &Point) -> Elem<R> { 153 let mut r = Elem::zero(); 154 r.limbs[..self.num_limbs] 155 .copy_from_slice(&p.xyz[(2 * self.num_limbs)..(3 * self.num_limbs)]); 156 r 157 } 158 } 159 160 struct Modulus { 161 p: [Limb; MAX_LIMBS], 162 rr: [Limb; MAX_LIMBS], 163 } 164 165 /// Operations on private keys, for ECDH and ECDSA signing. 166 pub struct PrivateKeyOps { 167 pub common: &'static CommonOps, 168 elem_inv_squared: fn(a: &Elem<R>) -> Elem<R>, 169 point_mul_base_impl: fn(a: &Scalar) -> Point, 170 point_mul_impl: unsafe extern "C" fn( 171 r: *mut Limb, // [3][num_limbs] 172 p_scalar: *const Limb, // [num_limbs] 173 p_x: *const Limb, // [num_limbs] 174 p_y: *const Limb, // [num_limbs] 175 ), 176 } 177 178 impl PrivateKeyOps { 179 #[inline(always)] 180 pub fn point_mul_base(&self, a: &Scalar) -> Point { 181 (self.point_mul_base_impl)(a) 182 } 183 184 #[inline(always)] 185 pub fn point_mul(&self, p_scalar: &Scalar, (p_x, p_y): &(Elem<R>, Elem<R>)) -> Point { 186 let mut r = Point::new_at_infinity(); 187 unsafe { 188 (self.point_mul_impl)( 189 r.xyz.as_mut_ptr(), 190 p_scalar.limbs.as_ptr(), 191 p_x.limbs.as_ptr(), 192 p_y.limbs.as_ptr(), 193 ); 194 } 195 r 196 } 197 198 #[inline] 199 pub fn elem_inverse_squared(&self, a: &Elem<R>) -> Elem<R> { 200 (self.elem_inv_squared)(a) 201 } 202 } 203 204 /// Operations and values needed by all operations on public keys (ECDH 205 /// agreement and ECDSA verification). 206 pub struct PublicKeyOps { 207 pub common: &'static CommonOps, 208 } 209 210 impl PublicKeyOps { 211 // The serialized bytes are in big-endian order, zero-padded. The limbs 212 // of `Elem` are in the native endianness, least significant limb to 213 // most significant limb. Besides the parsing, conversion, this also 214 // implements NIST SP 800-56A Step 2: "Verify that xQ and yQ are integers 215 // in the interval [0, p-1] in the case that q is an odd prime p[.]" 216 pub fn elem_parse(&self, input: &mut untrusted::Reader) -> Result<Elem<R>, error::Unspecified> { 217 let encoded_value = input.read_bytes(self.common.num_limbs * LIMB_BYTES)?; 218 let parsed = elem_parse_big_endian_fixed_consttime(self.common, encoded_value)?; 219 let mut r = Elem::zero(); 220 // Montgomery encode (elem_to_mont). 221 // TODO: do something about this. 222 unsafe { 223 (self.common.elem_mul_mont)( 224 r.limbs.as_mut_ptr(), 225 parsed.limbs.as_ptr(), 226 self.common.q.rr.as_ptr(), 227 ) 228 } 229 Ok(r) 230 } 231 } 232 233 // Operations used by both ECDSA signing and ECDSA verification. In general 234 // these must be side-channel resistant. 235 pub struct ScalarOps { 236 pub common: &'static CommonOps, 237 238 scalar_inv_to_mont_impl: fn(a: &Scalar) -> Scalar<R>, 239 scalar_mul_mont: unsafe extern "C" fn(r: *mut Limb, a: *const Limb, b: *const Limb), 240 } 241 242 impl ScalarOps { 243 // The (maximum) length of a scalar, not including any padding. 244 pub fn scalar_bytes_len(&self) -> usize { 245 self.common.num_limbs * LIMB_BYTES 246 } 247 248 /// Returns the modular inverse of `a` (mod `n`). Panics of `a` is zero, 249 /// because zero isn't invertible. 250 pub fn scalar_inv_to_mont(&self, a: &Scalar) -> Scalar<R> { 251 assert!(!self.common.is_zero(a)); 252 (self.scalar_inv_to_mont_impl)(a) 253 } 254 255 #[inline] 256 pub fn scalar_product<EA: Encoding, EB: Encoding>( 257 &self, 258 a: &Scalar<EA>, 259 b: &Scalar<EB>, 260 ) -> Scalar<<(EA, EB) as ProductEncoding>::Output> 261 where 262 (EA, EB): ProductEncoding, 263 { 264 mul_mont(self.scalar_mul_mont, a, b) 265 } 266 } 267 268 /// Operations on public scalars needed by ECDSA signature verification. 269 pub struct PublicScalarOps { 270 pub scalar_ops: &'static ScalarOps, 271 pub public_key_ops: &'static PublicKeyOps, 272 273 // XXX: `PublicScalarOps` shouldn't depend on `PrivateKeyOps`, but it does 274 // temporarily until `twin_mul` is rewritten. 275 pub private_key_ops: &'static PrivateKeyOps, 276 277 pub q_minus_n: Elem<Unencoded>, 278 } 279 280 impl PublicScalarOps { 281 #[inline] 282 pub fn scalar_as_elem(&self, a: &Scalar) -> Elem<Unencoded> { 283 Elem { 284 limbs: a.limbs, 285 m: PhantomData, 286 encoding: PhantomData, 287 } 288 } 289 290 pub fn elem_equals(&self, a: &Elem<Unencoded>, b: &Elem<Unencoded>) -> bool { 291 for i in 0..self.public_key_ops.common.num_limbs { 292 if a.limbs[i] != b.limbs[i] { 293 return false; 294 } 295 } 296 true 297 } 298 299 pub fn elem_less_than(&self, a: &Elem<Unencoded>, b: &Elem<Unencoded>) -> bool { 300 let num_limbs = self.public_key_ops.common.num_limbs; 301 limbs_less_than_limbs_vartime(&a.limbs[..num_limbs], &b.limbs[..num_limbs]) 302 } 303 304 #[inline] 305 pub fn elem_sum(&self, a: &Elem<Unencoded>, b: &Elem<Unencoded>) -> Elem<Unencoded> { 306 binary_op(self.public_key_ops.common.elem_add_impl, a, b) 307 } 308 } 309 310 #[allow(non_snake_case)] 311 pub struct PrivateScalarOps { 312 pub scalar_ops: &'static ScalarOps, 313 314 pub oneRR_mod_n: Scalar<RR>, // 1 * R**2 (mod n). TOOD: Use One<RR>. 315 } 316 317 // This assumes n < q < 2*n. 318 pub fn elem_reduced_to_scalar(ops: &CommonOps, elem: &Elem<Unencoded>) -> Scalar<Unencoded> { 319 let num_limbs = ops.num_limbs; 320 let mut r_limbs = elem.limbs; 321 limbs_reduce_once_constant_time(&mut r_limbs[..num_limbs], &ops.n.limbs[..num_limbs]); 322 Scalar { 323 limbs: r_limbs, 324 m: PhantomData, 325 encoding: PhantomData, 326 } 327 } 328 329 pub fn scalar_sum(ops: &CommonOps, a: &Scalar, b: &Scalar) -> Scalar { 330 let mut r = Scalar::zero(); 331 unsafe { 332 LIMBS_add_mod( 333 r.limbs.as_mut_ptr(), 334 a.limbs.as_ptr(), 335 b.limbs.as_ptr(), 336 ops.n.limbs.as_ptr(), 337 ops.num_limbs, 338 ) 339 } 340 r 341 } 342 343 // Returns (`a` squared `squarings` times) * `b`. 344 fn elem_sqr_mul(ops: &CommonOps, a: &Elem<R>, squarings: usize, b: &Elem<R>) -> Elem<R> { 345 debug_assert!(squarings >= 1); 346 let mut tmp = ops.elem_squared(a); 347 for _ in 1..squarings { 348 ops.elem_square(&mut tmp); 349 } 350 ops.elem_product(&tmp, b) 351 } 352 353 // Sets `acc` = (`acc` squared `squarings` times) * `b`. 354 fn elem_sqr_mul_acc(ops: &CommonOps, acc: &mut Elem<R>, squarings: usize, b: &Elem<R>) { 355 debug_assert!(squarings >= 1); 356 for _ in 0..squarings { 357 ops.elem_square(acc); 358 } 359 ops.elem_mul(acc, b) 360 } 361 362 #[inline] 363 pub fn elem_parse_big_endian_fixed_consttime( 364 ops: &CommonOps, 365 bytes: untrusted::Input, 366 ) -> Result<Elem<Unencoded>, error::Unspecified> { 367 parse_big_endian_fixed_consttime(ops, bytes, AllowZero::Yes, &ops.q.p[..ops.num_limbs]) 368 } 369 370 #[inline] 371 pub fn scalar_parse_big_endian_fixed_consttime( 372 ops: &CommonOps, 373 bytes: untrusted::Input, 374 ) -> Result<Scalar, error::Unspecified> { 375 parse_big_endian_fixed_consttime(ops, bytes, AllowZero::No, &ops.n.limbs[..ops.num_limbs]) 376 } 377 378 #[inline] 379 pub fn scalar_parse_big_endian_variable( 380 ops: &CommonOps, 381 allow_zero: AllowZero, 382 bytes: untrusted::Input, 383 ) -> Result<Scalar, error::Unspecified> { 384 let mut r = Scalar::zero(); 385 parse_big_endian_in_range_and_pad_consttime( 386 bytes, 387 allow_zero, 388 &ops.n.limbs[..ops.num_limbs], 389 &mut r.limbs[..ops.num_limbs], 390 )?; 391 Ok(r) 392 } 393 394 pub fn scalar_parse_big_endian_partially_reduced_variable_consttime( 395 ops: &CommonOps, 396 allow_zero: AllowZero, 397 bytes: untrusted::Input, 398 ) -> Result<Scalar, error::Unspecified> { 399 let mut r = Scalar::zero(); 400 parse_big_endian_in_range_partially_reduced_and_pad_consttime( 401 bytes, 402 allow_zero, 403 &ops.n.limbs[..ops.num_limbs], 404 &mut r.limbs[..ops.num_limbs], 405 )?; 406 Ok(r) 407 } 408 409 fn parse_big_endian_fixed_consttime<M>( 410 ops: &CommonOps, 411 bytes: untrusted::Input, 412 allow_zero: AllowZero, 413 max_exclusive: &[Limb], 414 ) -> Result<elem::Elem<M, Unencoded>, error::Unspecified> { 415 if bytes.len() != ops.num_limbs * LIMB_BYTES { 416 return Err(error::Unspecified); 417 } 418 let mut r = elem::Elem::zero(); 419 parse_big_endian_in_range_and_pad_consttime( 420 bytes, 421 allow_zero, 422 max_exclusive, 423 &mut r.limbs[..ops.num_limbs], 424 )?; 425 Ok(r) 426 } 427 428 extern "C" { 429 fn LIMBS_add_mod( 430 r: *mut Limb, 431 a: *const Limb, 432 b: *const Limb, 433 m: *const Limb, 434 num_limbs: c::size_t, 435 ); 436 } 437 438 #[cfg(test)] 439 mod tests { 440 use super::*; 441 use crate::test; 442 use alloc::{format, vec, vec::Vec}; 443 444 const ZERO_SCALAR: Scalar = Scalar { 445 limbs: [0; MAX_LIMBS], 446 m: PhantomData, 447 encoding: PhantomData, 448 }; 449 450 fn q_minus_n_plus_n_equals_0_test(ops: &PublicScalarOps) { 451 let cops = ops.scalar_ops.common; 452 let mut x = ops.q_minus_n; 453 cops.elem_add(&mut x, &cops.n); 454 assert!(cops.is_zero(&x)); 455 } 456 457 #[test] 458 fn p256_q_minus_n_plus_n_equals_0_test() { 459 q_minus_n_plus_n_equals_0_test(&p256::PUBLIC_SCALAR_OPS); 460 } 461 462 #[test] 463 fn p384_q_minus_n_plus_n_equals_0_test() { 464 q_minus_n_plus_n_equals_0_test(&p384::PUBLIC_SCALAR_OPS); 465 } 466 467 #[test] 468 fn p256_elem_add_test() { 469 elem_add_test( 470 &p256::PUBLIC_SCALAR_OPS, 471 test_file!("ops/p256_elem_sum_tests.txt"), 472 ); 473 } 474 475 #[test] 476 fn p384_elem_add_test() { 477 elem_add_test( 478 &p384::PUBLIC_SCALAR_OPS, 479 test_file!("ops/p384_elem_sum_tests.txt"), 480 ); 481 } 482 483 fn elem_add_test(ops: &PublicScalarOps, test_file: test::File) { 484 test::run(test_file, |section, test_case| { 485 assert_eq!(section, ""); 486 487 let cops = ops.public_key_ops.common; 488 let a = consume_elem(cops, test_case, "a"); 489 let b = consume_elem(cops, test_case, "b"); 490 let expected_sum = consume_elem(cops, test_case, "r"); 491 492 let mut actual_sum = a; 493 ops.public_key_ops.common.elem_add(&mut actual_sum, &b); 494 assert_limbs_are_equal(cops, &actual_sum.limbs, &expected_sum.limbs); 495 496 let mut actual_sum = b; 497 ops.public_key_ops.common.elem_add(&mut actual_sum, &a); 498 assert_limbs_are_equal(cops, &actual_sum.limbs, &expected_sum.limbs); 499 500 Ok(()) 501 }) 502 } 503 504 // XXX: There's no `GFp_nistz256_sub` in *ring*; it's logic is inlined into 505 // the point arithmetic functions. Thus, we can't test it. 506 507 #[test] 508 fn p384_elem_sub_test() { 509 extern "C" { 510 fn GFp_p384_elem_sub(r: *mut Limb, a: *const Limb, b: *const Limb); 511 } 512 elem_sub_test( 513 &p384::COMMON_OPS, 514 GFp_p384_elem_sub, 515 test_file!("ops/p384_elem_sum_tests.txt"), 516 ); 517 } 518 519 fn elem_sub_test( 520 ops: &CommonOps, 521 elem_sub: unsafe extern "C" fn(r: *mut Limb, a: *const Limb, b: *const Limb), 522 test_file: test::File, 523 ) { 524 test::run(test_file, |section, test_case| { 525 assert_eq!(section, ""); 526 527 let a = consume_elem(ops, test_case, "a"); 528 let b = consume_elem(ops, test_case, "b"); 529 let r = consume_elem(ops, test_case, "r"); 530 531 let mut actual_difference = Elem::<R>::zero(); 532 unsafe { 533 elem_sub( 534 actual_difference.limbs.as_mut_ptr(), 535 r.limbs.as_ptr(), 536 b.limbs.as_ptr(), 537 ); 538 } 539 assert_limbs_are_equal(ops, &actual_difference.limbs, &a.limbs); 540 541 let mut actual_difference = Elem::<R>::zero(); 542 unsafe { 543 elem_sub( 544 actual_difference.limbs.as_mut_ptr(), 545 r.limbs.as_ptr(), 546 a.limbs.as_ptr(), 547 ); 548 } 549 assert_limbs_are_equal(ops, &actual_difference.limbs, &b.limbs); 550 551 Ok(()) 552 }) 553 } 554 555 // XXX: There's no `GFp_nistz256_div_by_2` in *ring*; it's logic is inlined 556 // into the point arithmetic functions. Thus, we can't test it. 557 558 #[test] 559 fn p384_elem_div_by_2_test() { 560 extern "C" { 561 fn GFp_p384_elem_div_by_2(r: *mut Limb, a: *const Limb); 562 } 563 elem_div_by_2_test( 564 &p384::COMMON_OPS, 565 GFp_p384_elem_div_by_2, 566 test_file!("ops/p384_elem_div_by_2_tests.txt"), 567 ); 568 } 569 570 fn elem_div_by_2_test( 571 ops: &CommonOps, 572 elem_div_by_2: unsafe extern "C" fn(r: *mut Limb, a: *const Limb), 573 test_file: test::File, 574 ) { 575 test::run(test_file, |section, test_case| { 576 assert_eq!(section, ""); 577 578 let a = consume_elem(ops, test_case, "a"); 579 let r = consume_elem(ops, test_case, "r"); 580 581 let mut actual_result = Elem::<R>::zero(); 582 unsafe { 583 elem_div_by_2(actual_result.limbs.as_mut_ptr(), a.limbs.as_ptr()); 584 } 585 assert_limbs_are_equal(ops, &actual_result.limbs, &r.limbs); 586 587 Ok(()) 588 }) 589 } 590 591 // TODO: Add test vectors that test the range of values above `q`. 592 #[test] 593 fn p256_elem_neg_test() { 594 extern "C" { 595 fn GFp_nistz256_neg(r: *mut Limb, a: *const Limb); 596 } 597 elem_neg_test( 598 &p256::COMMON_OPS, 599 GFp_nistz256_neg, 600 test_file!("ops/p256_elem_neg_tests.txt"), 601 ); 602 } 603 604 #[test] 605 fn p384_elem_neg_test() { 606 extern "C" { 607 fn GFp_p384_elem_neg(r: *mut Limb, a: *const Limb); 608 } 609 elem_neg_test( 610 &p384::COMMON_OPS, 611 GFp_p384_elem_neg, 612 test_file!("ops/p384_elem_neg_tests.txt"), 613 ); 614 } 615 616 fn elem_neg_test( 617 ops: &CommonOps, 618 elem_neg: unsafe extern "C" fn(r: *mut Limb, a: *const Limb), 619 test_file: test::File, 620 ) { 621 test::run(test_file, |section, test_case| { 622 assert_eq!(section, ""); 623 624 let a = consume_elem(ops, test_case, "a"); 625 let b = consume_elem(ops, test_case, "b"); 626 627 // Verify -a == b. 628 { 629 let mut actual_result = Elem::<R>::zero(); 630 unsafe { 631 elem_neg(actual_result.limbs.as_mut_ptr(), a.limbs.as_ptr()); 632 } 633 assert_limbs_are_equal(ops, &actual_result.limbs, &b.limbs); 634 } 635 636 // Verify -b == a. 637 { 638 let mut actual_result = Elem::<R>::zero(); 639 unsafe { 640 elem_neg(actual_result.limbs.as_mut_ptr(), b.limbs.as_ptr()); 641 } 642 assert_limbs_are_equal(ops, &actual_result.limbs, &a.limbs); 643 } 644 645 Ok(()) 646 }) 647 } 648 649 #[test] 650 fn p256_elem_mul_test() { 651 elem_mul_test(&p256::COMMON_OPS, test_file!("ops/p256_elem_mul_tests.txt")); 652 } 653 654 #[test] 655 fn p384_elem_mul_test() { 656 elem_mul_test(&p384::COMMON_OPS, test_file!("ops/p384_elem_mul_tests.txt")); 657 } 658 659 fn elem_mul_test(ops: &CommonOps, test_file: test::File) { 660 test::run(test_file, |section, test_case| { 661 assert_eq!(section, ""); 662 663 let mut a = consume_elem(ops, test_case, "a"); 664 let b = consume_elem(ops, test_case, "b"); 665 let r = consume_elem(ops, test_case, "r"); 666 ops.elem_mul(&mut a, &b); 667 assert_limbs_are_equal(ops, &a.limbs, &r.limbs); 668 669 Ok(()) 670 }) 671 } 672 673 #[test] 674 fn p256_scalar_mul_test() { 675 scalar_mul_test( 676 &p256::SCALAR_OPS, 677 test_file!("ops/p256_scalar_mul_tests.txt"), 678 ); 679 } 680 681 #[test] 682 fn p384_scalar_mul_test() { 683 scalar_mul_test( 684 &p384::SCALAR_OPS, 685 test_file!("ops/p384_scalar_mul_tests.txt"), 686 ); 687 } 688 689 fn scalar_mul_test(ops: &ScalarOps, test_file: test::File) { 690 test::run(test_file, |section, test_case| { 691 assert_eq!(section, ""); 692 let cops = ops.common; 693 let a = consume_scalar(cops, test_case, "a"); 694 let b = consume_scalar_mont(cops, test_case, "b"); 695 let expected_result = consume_scalar(cops, test_case, "r"); 696 let actual_result = ops.scalar_product(&a, &b); 697 assert_limbs_are_equal(cops, &actual_result.limbs, &expected_result.limbs); 698 699 Ok(()) 700 }) 701 } 702 703 #[test] 704 fn p256_scalar_square_test() { 705 extern "C" { 706 fn GFp_p256_scalar_sqr_rep_mont(r: *mut Limb, a: *const Limb, rep: Limb); 707 } 708 scalar_square_test( 709 &p256::SCALAR_OPS, 710 GFp_p256_scalar_sqr_rep_mont, 711 test_file!("ops/p256_scalar_square_tests.txt"), 712 ); 713 } 714 715 // XXX: There's no `p384_scalar_square_test()` because there's no dedicated 716 // `GFp_p384_scalar_sqr_rep_mont()`. 717 718 fn scalar_square_test( 719 ops: &ScalarOps, 720 sqr_rep: unsafe extern "C" fn(r: *mut Limb, a: *const Limb, rep: Limb), 721 test_file: test::File, 722 ) { 723 test::run(test_file, |section, test_case| { 724 assert_eq!(section, ""); 725 let cops = &ops.common; 726 let a = consume_scalar(cops, test_case, "a"); 727 let expected_result = consume_scalar(cops, test_case, "r"); 728 729 { 730 let mut actual_result: Scalar<R> = Scalar { 731 limbs: [0; MAX_LIMBS], 732 m: PhantomData, 733 encoding: PhantomData, 734 }; 735 unsafe { 736 sqr_rep(actual_result.limbs.as_mut_ptr(), a.limbs.as_ptr(), 1); 737 } 738 assert_limbs_are_equal(cops, &actual_result.limbs, &expected_result.limbs); 739 } 740 741 { 742 let actual_result = ops.scalar_product(&a, &a); 743 assert_limbs_are_equal(cops, &actual_result.limbs, &expected_result.limbs); 744 } 745 746 Ok(()) 747 }) 748 } 749 750 #[test] 751 #[should_panic(expected = "!self.common.is_zero(a)")] 752 fn p256_scalar_inv_to_mont_zero_panic_test() { 753 let _ = p256::SCALAR_OPS.scalar_inv_to_mont(&ZERO_SCALAR); 754 } 755 756 #[test] 757 #[should_panic(expected = "!self.common.is_zero(a)")] 758 fn p384_scalar_inv_to_mont_zero_panic_test() { 759 let _ = p384::SCALAR_OPS.scalar_inv_to_mont(&ZERO_SCALAR); 760 } 761 762 #[test] 763 fn p256_point_sum_test() { 764 point_sum_test( 765 &p256::PRIVATE_KEY_OPS, 766 test_file!("ops/p256_point_sum_tests.txt"), 767 ); 768 } 769 770 #[test] 771 fn p384_point_sum_test() { 772 point_sum_test( 773 &p384::PRIVATE_KEY_OPS, 774 test_file!("ops/p384_point_sum_tests.txt"), 775 ); 776 } 777 778 fn point_sum_test(ops: &PrivateKeyOps, test_file: test::File) { 779 test::run(test_file, |section, test_case| { 780 assert_eq!(section, ""); 781 782 let a = consume_jacobian_point(ops, test_case, "a"); 783 let b = consume_jacobian_point(ops, test_case, "b"); 784 let r_expected = consume_point(ops, test_case, "r"); 785 786 let r_actual = ops.common.point_sum(&a, &b); 787 assert_point_actual_equals_expected(ops, &r_actual, &r_expected); 788 789 Ok(()) 790 }); 791 } 792 793 // Keep this in sync with the logic for defining `GFp_USE_LARGE_TABLE` and 794 // with the corresponding code in p256.rs that decides which base point 795 // multiplication to use. 796 #[cfg(any(target_arch = "aarch64", target_arch = "x86", target_arch = "x86_64"))] 797 #[test] 798 fn p256_point_sum_mixed_test() { 799 extern "C" { 800 fn GFp_nistz256_point_add_affine( 801 r: *mut Limb, // [p256::COMMON_OPS.num_limbs*3] 802 a: *const Limb, // [p256::COMMON_OPS.num_limbs*3] 803 b: *const Limb, // [p256::COMMON_OPS.num_limbs*2] 804 ); 805 } 806 point_sum_mixed_test( 807 &p256::PRIVATE_KEY_OPS, 808 GFp_nistz256_point_add_affine, 809 test_file!("ops/p256_point_sum_mixed_tests.txt"), 810 ); 811 } 812 813 // XXX: There is no `GFp_nistz384_point_add_affine()`. 814 815 #[cfg(any(target_arch = "aarch64", target_arch = "x86", target_arch = "x86_64"))] 816 fn point_sum_mixed_test( 817 ops: &PrivateKeyOps, 818 point_add_affine: unsafe extern "C" fn( 819 r: *mut Limb, // [ops.num_limbs*3] 820 a: *const Limb, // [ops.num_limbs*3] 821 b: *const Limb, // [ops.num_limbs*2] 822 ), 823 test_file: test::File, 824 ) { 825 test::run(test_file, |section, test_case| { 826 assert_eq!(section, ""); 827 828 let a = consume_jacobian_point(ops, test_case, "a"); 829 let b = consume_affine_point(ops, test_case, "b"); 830 let r_expected = consume_point(ops, test_case, "r"); 831 832 let mut r_actual = Point::new_at_infinity(); 833 unsafe { 834 point_add_affine(r_actual.xyz.as_mut_ptr(), a.xyz.as_ptr(), b.xy.as_ptr()); 835 } 836 837 assert_point_actual_equals_expected(ops, &r_actual, &r_expected); 838 839 Ok(()) 840 }); 841 } 842 843 #[test] 844 fn p256_point_double_test() { 845 extern "C" { 846 fn GFp_nistz256_point_double( 847 r: *mut Limb, // [p256::COMMON_OPS.num_limbs*3] 848 a: *const Limb, // [p256::COMMON_OPS.num_limbs*3] 849 ); 850 } 851 point_double_test( 852 &p256::PRIVATE_KEY_OPS, 853 GFp_nistz256_point_double, 854 test_file!("ops/p256_point_double_tests.txt"), 855 ); 856 } 857 858 #[test] 859 fn p384_point_double_test() { 860 extern "C" { 861 fn GFp_nistz384_point_double( 862 r: *mut Limb, // [p384::COMMON_OPS.num_limbs*3] 863 a: *const Limb, // [p384::COMMON_OPS.num_limbs*3] 864 ); 865 } 866 point_double_test( 867 &p384::PRIVATE_KEY_OPS, 868 GFp_nistz384_point_double, 869 test_file!("ops/p384_point_double_tests.txt"), 870 ); 871 } 872 873 fn point_double_test( 874 ops: &PrivateKeyOps, 875 point_double: unsafe extern "C" fn( 876 r: *mut Limb, // [ops.num_limbs*3] 877 a: *const Limb, // [ops.num_limbs*3] 878 ), 879 test_file: test::File, 880 ) { 881 test::run(test_file, |section, test_case| { 882 assert_eq!(section, ""); 883 884 let a = consume_jacobian_point(ops, test_case, "a"); 885 let r_expected = consume_point(ops, test_case, "r"); 886 887 let mut r_actual = Point::new_at_infinity(); 888 unsafe { 889 point_double(r_actual.xyz.as_mut_ptr(), a.xyz.as_ptr()); 890 } 891 892 assert_point_actual_equals_expected(ops, &r_actual, &r_expected); 893 894 Ok(()) 895 }); 896 } 897 898 #[test] 899 fn p256_point_mul_test() { 900 point_mul_tests( 901 &p256::PRIVATE_KEY_OPS, 902 test_file!("ops/p256_point_mul_tests.txt"), 903 ); 904 } 905 906 #[test] 907 fn p384_point_mul_test() { 908 point_mul_tests( 909 &p384::PRIVATE_KEY_OPS, 910 test_file!("ops/p384_point_mul_tests.txt"), 911 ); 912 } 913 914 fn point_mul_tests(ops: &PrivateKeyOps, test_file: test::File) { 915 test::run(test_file, |section, test_case| { 916 assert_eq!(section, ""); 917 let p_scalar = consume_scalar(ops.common, test_case, "p_scalar"); 918 let (x, y) = match consume_point(ops, test_case, "p") { 919 TestPoint::Infinity => { 920 panic!("can't be inf."); 921 } 922 TestPoint::Affine(x, y) => (x, y), 923 }; 924 let expected_result = consume_point(ops, test_case, "r"); 925 let actual_result = ops.point_mul(&p_scalar, &(x, y)); 926 assert_point_actual_equals_expected(ops, &actual_result, &expected_result); 927 Ok(()) 928 }) 929 } 930 931 #[test] 932 fn p256_point_mul_serialized_test() { 933 point_mul_serialized_test( 934 &p256::PRIVATE_KEY_OPS, 935 &p256::PUBLIC_KEY_OPS, 936 test_file!("ops/p256_point_mul_serialized_tests.txt"), 937 ); 938 } 939 940 fn point_mul_serialized_test( 941 priv_ops: &PrivateKeyOps, 942 pub_ops: &PublicKeyOps, 943 test_file: test::File, 944 ) { 945 let cops = pub_ops.common; 946 947 test::run(test_file, |section, test_case| { 948 assert_eq!(section, ""); 949 let p_scalar = consume_scalar(cops, test_case, "p_scalar"); 950 951 let p = test_case.consume_bytes("p"); 952 let p = super::super::public_key::parse_uncompressed_point( 953 pub_ops, 954 untrusted::Input::from(&p), 955 ) 956 .expect("valid point"); 957 958 let expected_result = test_case.consume_bytes("r"); 959 960 let product = priv_ops.point_mul(&p_scalar, &p); 961 962 let mut actual_result = vec![4u8; 1 + (2 * (cops.num_limbs * LIMB_BYTES))]; 963 { 964 let (x, y) = actual_result[1..].split_at_mut(cops.num_limbs * LIMB_BYTES); 965 super::super::private_key::big_endian_affine_from_jacobian( 966 priv_ops, 967 Some(x), 968 Some(y), 969 &product, 970 ) 971 .expect("successful encoding"); 972 } 973 974 assert_eq!(expected_result, actual_result); 975 976 Ok(()) 977 }) 978 } 979 980 #[test] 981 fn p256_point_mul_base_test() { 982 point_mul_base_tests( 983 &p256::PRIVATE_KEY_OPS, 984 test_file!("ops/p256_point_mul_base_tests.txt"), 985 ); 986 } 987 988 #[test] 989 fn p384_point_mul_base_test() { 990 point_mul_base_tests( 991 &p384::PRIVATE_KEY_OPS, 992 test_file!("ops/p384_point_mul_base_tests.txt"), 993 ); 994 } 995 996 fn point_mul_base_tests(ops: &PrivateKeyOps, test_file: test::File) { 997 test::run(test_file, |section, test_case| { 998 assert_eq!(section, ""); 999 let g_scalar = consume_scalar(ops.common, test_case, "g_scalar"); 1000 let expected_result = consume_point(ops, test_case, "r"); 1001 let actual_result = ops.point_mul_base(&g_scalar); 1002 assert_point_actual_equals_expected(ops, &actual_result, &expected_result); 1003 Ok(()) 1004 }) 1005 } 1006 1007 fn assert_point_actual_equals_expected( 1008 ops: &PrivateKeyOps, 1009 actual_point: &Point, 1010 expected_point: &TestPoint, 1011 ) { 1012 let cops = ops.common; 1013 let actual_x = &cops.point_x(&actual_point); 1014 let actual_y = &cops.point_y(&actual_point); 1015 let actual_z = &cops.point_z(&actual_point); 1016 match expected_point { 1017 TestPoint::Infinity => { 1018 let zero = Elem::zero(); 1019 assert_elems_are_equal(cops, &actual_z, &zero); 1020 } 1021 TestPoint::Affine(expected_x, expected_y) => { 1022 let zz_inv = ops.elem_inverse_squared(&actual_z); 1023 let x_aff = cops.elem_product(&actual_x, &zz_inv); 1024 let y_aff = { 1025 let zzzz_inv = cops.elem_squared(&zz_inv); 1026 let zzz_inv = cops.elem_product(&actual_z, &zzzz_inv); 1027 cops.elem_product(&actual_y, &zzz_inv) 1028 }; 1029 1030 assert_elems_are_equal(cops, &x_aff, &expected_x); 1031 assert_elems_are_equal(cops, &y_aff, &expected_y); 1032 } 1033 } 1034 } 1035 1036 fn consume_jacobian_point( 1037 ops: &PrivateKeyOps, 1038 test_case: &mut test::TestCase, 1039 name: &str, 1040 ) -> Point { 1041 let input = test_case.consume_string(name); 1042 let elems = input.split(", ").collect::<Vec<&str>>(); 1043 assert_eq!(elems.len(), 3); 1044 let mut p = Point::new_at_infinity(); 1045 consume_point_elem(ops.common, &mut p.xyz, &elems, 0); 1046 consume_point_elem(ops.common, &mut p.xyz, &elems, 1); 1047 consume_point_elem(ops.common, &mut p.xyz, &elems, 2); 1048 p 1049 } 1050 1051 #[cfg(any(target_arch = "aarch64", target_arch = "x86", target_arch = "x86_64"))] 1052 struct AffinePoint { 1053 xy: [Limb; 2 * MAX_LIMBS], 1054 } 1055 1056 #[cfg(any(target_arch = "aarch64", target_arch = "x86", target_arch = "x86_64"))] 1057 fn consume_affine_point( 1058 ops: &PrivateKeyOps, 1059 test_case: &mut test::TestCase, 1060 name: &str, 1061 ) -> AffinePoint { 1062 let input = test_case.consume_string(name); 1063 let elems = input.split(", ").collect::<Vec<&str>>(); 1064 assert_eq!(elems.len(), 2); 1065 let mut p = AffinePoint { 1066 xy: [0; 2 * MAX_LIMBS], 1067 }; 1068 consume_point_elem(ops.common, &mut p.xy, &elems, 0); 1069 consume_point_elem(ops.common, &mut p.xy, &elems, 1); 1070 p 1071 } 1072 1073 fn consume_point_elem(ops: &CommonOps, limbs_out: &mut [Limb], elems: &[&str], i: usize) { 1074 let bytes = test::from_hex(elems[i]).unwrap(); 1075 let bytes = untrusted::Input::from(&bytes); 1076 let r: Elem<Unencoded> = elem_parse_big_endian_fixed_consttime(ops, bytes).unwrap(); 1077 // XXX: “Transmute” this to `Elem<R>` limbs. 1078 limbs_out[(i * ops.num_limbs)..((i + 1) * ops.num_limbs)] 1079 .copy_from_slice(&r.limbs[..ops.num_limbs]); 1080 } 1081 1082 enum TestPoint { 1083 Infinity, 1084 Affine(Elem<R>, Elem<R>), 1085 } 1086 1087 fn consume_point(ops: &PrivateKeyOps, test_case: &mut test::TestCase, name: &str) -> TestPoint { 1088 fn consume_point_elem(ops: &CommonOps, elems: &[&str], i: usize) -> Elem<R> { 1089 let bytes = test::from_hex(elems[i]).unwrap(); 1090 let bytes = untrusted::Input::from(&bytes); 1091 let unencoded: Elem<Unencoded> = 1092 elem_parse_big_endian_fixed_consttime(ops, bytes).unwrap(); 1093 // XXX: “Transmute” this to `Elem<R>` limbs. 1094 Elem { 1095 limbs: unencoded.limbs, 1096 m: PhantomData, 1097 encoding: PhantomData, 1098 } 1099 } 1100 1101 let input = test_case.consume_string(name); 1102 if input == "inf" { 1103 return TestPoint::Infinity; 1104 } 1105 let elems = input.split(", ").collect::<Vec<&str>>(); 1106 assert_eq!(elems.len(), 2); 1107 let x = consume_point_elem(ops.common, &elems, 0); 1108 let y = consume_point_elem(ops.common, &elems, 1); 1109 TestPoint::Affine(x, y) 1110 } 1111 1112 fn assert_elems_are_equal(ops: &CommonOps, a: &Elem<R>, b: &Elem<R>) { 1113 assert_limbs_are_equal(ops, &a.limbs, &b.limbs) 1114 } 1115 1116 fn assert_limbs_are_equal( 1117 ops: &CommonOps, 1118 actual: &[Limb; MAX_LIMBS], 1119 expected: &[Limb; MAX_LIMBS], 1120 ) { 1121 for i in 0..ops.num_limbs { 1122 if actual[i] != expected[i] { 1123 let mut s = alloc::string::String::new(); 1124 for j in 0..ops.num_limbs { 1125 let formatted = format!("{:016x}", actual[ops.num_limbs - j - 1]); 1126 s.push_str(&formatted); 1127 } 1128 panic!("Actual != Expected,\nActual = {}", s); 1129 } 1130 } 1131 } 1132 1133 fn consume_elem(ops: &CommonOps, test_case: &mut test::TestCase, name: &str) -> Elem<R> { 1134 let bytes = consume_padded_bytes(ops, test_case, name); 1135 let bytes = untrusted::Input::from(&bytes); 1136 let r: Elem<Unencoded> = elem_parse_big_endian_fixed_consttime(ops, bytes).unwrap(); 1137 // XXX: “Transmute” this to an `Elem<R>`. 1138 Elem { 1139 limbs: r.limbs, 1140 m: PhantomData, 1141 encoding: PhantomData, 1142 } 1143 } 1144 1145 fn consume_scalar(ops: &CommonOps, test_case: &mut test::TestCase, name: &str) -> Scalar { 1146 let bytes = test_case.consume_bytes(name); 1147 let bytes = untrusted::Input::from(&bytes); 1148 scalar_parse_big_endian_variable(ops, AllowZero::Yes, bytes).unwrap() 1149 } 1150 1151 fn consume_scalar_mont( 1152 ops: &CommonOps, 1153 test_case: &mut test::TestCase, 1154 name: &str, 1155 ) -> Scalar<R> { 1156 let bytes = test_case.consume_bytes(name); 1157 let bytes = untrusted::Input::from(&bytes); 1158 let s = scalar_parse_big_endian_variable(ops, AllowZero::Yes, bytes).unwrap(); 1159 // “Transmute” it to a `Scalar<R>`. 1160 Scalar { 1161 limbs: s.limbs, 1162 m: PhantomData, 1163 encoding: PhantomData, 1164 } 1165 } 1166 1167 fn consume_padded_bytes( 1168 ops: &CommonOps, 1169 test_case: &mut test::TestCase, 1170 name: &str, 1171 ) -> Vec<u8> { 1172 let unpadded_bytes = test_case.consume_bytes(name); 1173 let mut bytes = vec![0; (ops.num_limbs * LIMB_BYTES) - unpadded_bytes.len()]; 1174 bytes.extend(&unpadded_bytes); 1175 bytes 1176 } 1177 } 1178 1179 mod elem; 1180 pub mod p256; 1181 pub mod p384; 1182