From 9835e2ae736235810b4ea1c162ca5e65c547e770 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sat, 18 May 2024 04:49:50 +0200 Subject: Merging upstream version 1.71.1+dfsg1. Signed-off-by: Daniel Baumann --- vendor/primeorder/.cargo-checksum.json | 1 + vendor/primeorder/CHANGELOG.md | 55 +++ vendor/primeorder/Cargo.toml | 62 +++ vendor/primeorder/LICENSE-APACHE | 201 +++++++++ vendor/primeorder/LICENSE-MIT | 25 ++ vendor/primeorder/README.md | 88 ++++ vendor/primeorder/src/affine.rs | 485 +++++++++++++++++++++ vendor/primeorder/src/dev.rs | 152 +++++++ vendor/primeorder/src/field.rs | 641 +++++++++++++++++++++++++++ vendor/primeorder/src/lib.rs | 46 ++ vendor/primeorder/src/point_arithmetic.rs | 318 ++++++++++++++ vendor/primeorder/src/projective.rs | 696 ++++++++++++++++++++++++++++++ 12 files changed, 2770 insertions(+) create mode 100644 vendor/primeorder/.cargo-checksum.json create mode 100644 vendor/primeorder/CHANGELOG.md create mode 100644 vendor/primeorder/Cargo.toml create mode 100644 vendor/primeorder/LICENSE-APACHE create mode 100644 vendor/primeorder/LICENSE-MIT create mode 100644 vendor/primeorder/README.md create mode 100644 vendor/primeorder/src/affine.rs create mode 100644 vendor/primeorder/src/dev.rs create mode 100644 vendor/primeorder/src/field.rs create mode 100644 vendor/primeorder/src/lib.rs create mode 100644 vendor/primeorder/src/point_arithmetic.rs create mode 100644 vendor/primeorder/src/projective.rs (limited to 'vendor/primeorder') diff --git a/vendor/primeorder/.cargo-checksum.json b/vendor/primeorder/.cargo-checksum.json new file mode 100644 index 000000000..cfa328a00 --- /dev/null +++ b/vendor/primeorder/.cargo-checksum.json @@ -0,0 +1 @@ +{"files":{"CHANGELOG.md":"fc693b1a8146817a57357c4889266ea268d349c3348dadd566f165a375d4a36e","Cargo.toml":"27184fca63239e9d189981e3d3bd473431e927a30ddcdc1e7877dbb3ef9411ec","LICENSE-APACHE":"a9040321c3712d8fd0b09cf52b17445de04a23a10165049ae187cd39e5c86be5","LICENSE-MIT":"233b95ccbf90dc67e32f3e8995c489f6312d9191ebd141a931c3b684f1e3be6d","README.md":"e5ca721a4b1fb470d68a5fd9f7e9d6631e70ae9c4fbfa1fcf0b9a44b52cb612c","src/affine.rs":"8729eb99754c4cb379fde743a41b7e9fa6dde73b2f01b04f191cb23fc24bb6e2","src/dev.rs":"1ee156b18a6f42246cb2d02a13aa8068c7783d050d32987ae36596232c22312e","src/field.rs":"bfc19ceb9e8cd6725e84253188e82d684d05bc55bf619386726080b81adbed7b","src/lib.rs":"4b26e5a38f30ad77cd47f7c7b56492716d6fe70b5e483daa93bc6d79711f6694","src/point_arithmetic.rs":"7b65088237a263f7972cf59f88e7f761513d3a0ed9e687d6d429d70fa8974398","src/projective.rs":"a2a47adeeae9beeaccfb40a2746543c2db280ff47be038c39338437826f6762c"},"package":"cf8d3875361e28f7753baefef104386e7aa47642c93023356d97fdef4003bfb5"} \ No newline at end of file diff --git a/vendor/primeorder/CHANGELOG.md b/vendor/primeorder/CHANGELOG.md new file mode 100644 index 000000000..22693bea1 --- /dev/null +++ b/vendor/primeorder/CHANGELOG.md @@ -0,0 +1,55 @@ +# Changelog +All notable changes to this project will be documented in this file. + +The format is based on [Keep a Changelog](https://keepachangelog.com/en/1.0.0/), +and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0.html). + +## 0.13.1 (2023-04-09) +### Added +- `impl_bernstein_yang_invert!` macro ([#786]) +- `impl_field_invert_tests!` macro ([#786]) +- `impl_field_identity_tests!` macro ([#790]) +- `impl_field_sqrt_tests!` macro ([#790], [#800]) + +### Fixed +- Correct product definition for empty iterators ([#802]) + +[#786]: https://github.com/RustCrypto/elliptic-curves/pull/786 +[#790]: https://github.com/RustCrypto/elliptic-curves/pull/790 +[#800]: https://github.com/RustCrypto/elliptic-curves/pull/800 +[#802]: https://github.com/RustCrypto/elliptic-curves/pull/802 + +## 0.13.0 (2023-03-03) +### Added +- Support curves with any `a`-coefficient ([#728], [#729]) +- `impl_primefield_tests!` macro ([#739]) + +### Changed +- Use `AffineCoordinates` trait ([#734]) +- Rename `impl_field_element!` to `impl_mont_field_element!` ([#762]) +- Bump `elliptic-curve` dependency to v0.13 ([#770]) +- Bump `ecdsa` to v0.16 ([#770]) + +[#728]: https://github.com/RustCrypto/elliptic-curves/pull/728 +[#729]: https://github.com/RustCrypto/elliptic-curves/pull/729 +[#734]: https://github.com/RustCrypto/elliptic-curves/pull/734 +[#739]: https://github.com/RustCrypto/elliptic-curves/pull/739 +[#762]: https://github.com/RustCrypto/elliptic-curves/pull/762 +[#770]: https://github.com/RustCrypto/elliptic-curves/pull/770 + +## 0.12.1 (2023-01-22) +### Added +- Impl `From/ToEncodedPoint` for `ProjectivePoint` ([#722]) + +[#722]: https://github.com/RustCrypto/elliptic-curves/pull/722 + +## 0.12.0 (2023-01-16) + +Initial stable release. + +NOTE: other versions skipped to synchronize version numbers with +`elliptic-curve`, `k256`, `p256`, and `p384`. + +## 0.0.2 (2022-12-29) + +## 0.0.1 (2022-11-06) diff --git a/vendor/primeorder/Cargo.toml b/vendor/primeorder/Cargo.toml new file mode 100644 index 000000000..00deb8671 --- /dev/null +++ b/vendor/primeorder/Cargo.toml @@ -0,0 +1,62 @@ +# THIS FILE IS AUTOMATICALLY GENERATED BY CARGO +# +# When uploading crates to the registry Cargo will automatically +# "normalize" Cargo.toml files for maximal compatibility +# with all versions of Cargo and also rewrite `path` dependencies +# to registry (e.g., crates.io) dependencies. +# +# If you are reading this file be aware that the original Cargo.toml +# will likely look very different (and much more reasonable). +# See Cargo.toml.orig for the original contents. + +[package] +edition = "2021" +rust-version = "1.65" +name = "primeorder" +version = "0.13.1" +authors = ["RustCrypto Developers"] +description = """ +Pure Rust implementation of complete addition formulas for prime order elliptic +curves (Renes-Costello-Batina 2015). Generic over field elements and curve +equation coefficients +""" +documentation = "https://docs.rs/primeorder" +readme = "README.md" +keywords = [ + "crypto", + "ecc", +] +categories = [ + "cryptography", + "no-std", +] +license = "Apache-2.0 OR MIT" +repository = "https://github.com/RustCrypto/elliptic-curves/tree/master/primeorder" + +[package.metadata.docs.rs] +all-features = true +rustdoc-args = [ + "--cfg", + "docsrs", +] + +[dependencies.elliptic-curve] +version = "0.13" +features = [ + "arithmetic", + "sec1", +] +default-features = false + +[dependencies.serdect] +version = "0.2" +optional = true +default-features = false + +[features] +dev = [] +serde = [ + "elliptic-curve/serde", + "serdect", +] +std = ["elliptic-curve/std"] diff --git a/vendor/primeorder/LICENSE-APACHE b/vendor/primeorder/LICENSE-APACHE new file mode 100644 index 000000000..78173fa2e --- /dev/null +++ b/vendor/primeorder/LICENSE-APACHE @@ -0,0 +1,201 @@ + Apache License + Version 2.0, January 2004 + http://www.apache.org/licenses/ + +TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION + +1. Definitions. + + "License" shall mean the terms and conditions for use, reproduction, + and distribution as defined by Sections 1 through 9 of this document. + + "Licensor" shall mean the copyright owner or entity authorized by + the copyright owner that is granting the License. + + "Legal Entity" shall mean the union of the acting entity and all + other entities that control, are controlled by, or are under common + control with that entity. For the purposes of this definition, + "control" means (i) the power, direct or indirect, to cause the + direction or management of such entity, whether by contract or + otherwise, or (ii) ownership of fifty percent (50%) or more of the + outstanding shares, or (iii) beneficial ownership of such entity. + + "You" (or "Your") shall mean an individual or Legal Entity + exercising permissions granted by this License. + + "Source" form shall mean the preferred form for making modifications, + including but not limited to software source code, documentation + source, and configuration files. + + "Object" form shall mean any form resulting from mechanical + transformation or translation of a Source form, including but + not limited to compiled object code, generated documentation, + and conversions to other media types. + + "Work" shall mean the work of authorship, whether in Source or + Object form, made available under the License, as indicated by a + copyright notice that is included in or attached to the work + (an example is provided in the Appendix below). + + "Derivative Works" shall mean any work, whether in Source or Object + form, that is based on (or derived from) the Work and for which the + editorial revisions, annotations, elaborations, or other modifications + represent, as a whole, an original work of authorship. For the purposes + of this License, Derivative Works shall not include works that remain + separable from, or merely link (or bind by name) to the interfaces of, + the Work and Derivative Works thereof. + + "Contribution" shall mean any work of authorship, including + the original version of the Work and any modifications or additions + to that Work or Derivative Works thereof, that is intentionally + submitted to Licensor for inclusion in the Work by the copyright owner + or by an individual or Legal Entity authorized to submit on behalf of + the copyright owner. For the purposes of this definition, "submitted" + means any form of electronic, verbal, or written communication sent + to the Licensor or its representatives, including but not limited to + communication on electronic mailing lists, source code control systems, + and issue tracking systems that are managed by, or on behalf of, the + Licensor for the purpose of discussing and improving the Work, but + excluding communication that is conspicuously marked or otherwise + designated in writing by the copyright owner as "Not a Contribution." + + "Contributor" shall mean Licensor and any individual or Legal Entity + on behalf of whom a Contribution has been received by Licensor and + subsequently incorporated within the Work. + +2. Grant of Copyright License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + copyright license to reproduce, prepare Derivative Works of, + publicly display, publicly perform, sublicense, and distribute the + Work and such Derivative Works in Source or Object form. + +3. Grant of Patent License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + (except as stated in this section) patent license to make, have made, + use, offer to sell, sell, import, and otherwise transfer the Work, + where such license applies only to those patent claims licensable + by such Contributor that are necessarily infringed by their + Contribution(s) alone or by combination of their Contribution(s) + with the Work to which such Contribution(s) was submitted. If You + institute patent litigation against any entity (including a + cross-claim or counterclaim in a lawsuit) alleging that the Work + or a Contribution incorporated within the Work constitutes direct + or contributory patent infringement, then any patent licenses + granted to You under this License for that Work shall terminate + as of the date such litigation is filed. + +4. Redistribution. You may reproduce and distribute copies of the + Work or Derivative Works thereof in any medium, with or without + modifications, and in Source or Object form, provided that You + meet the following conditions: + + (a) You must give any other recipients of the Work or + Derivative Works a copy of this License; and + + (b) You must cause any modified files to carry prominent notices + stating that You changed the files; and + + (c) You must retain, in the Source form of any Derivative Works + that You distribute, all copyright, patent, trademark, and + attribution notices from the Source form of the Work, + excluding those notices that do not pertain to any part of + the Derivative Works; and + + (d) If the Work includes a "NOTICE" text file as part of its + distribution, then any Derivative Works that You distribute must + include a readable copy of the attribution notices contained + within such NOTICE file, excluding those notices that do not + pertain to any part of the Derivative Works, in at least one + of the following places: within a NOTICE text file distributed + as part of the Derivative Works; within the Source form or + documentation, if provided along with the Derivative Works; or, + within a display generated by the Derivative Works, if and + wherever such third-party notices normally appear. The contents + of the NOTICE file are for informational purposes only and + do not modify the License. You may add Your own attribution + notices within Derivative Works that You distribute, alongside + or as an addendum to the NOTICE text from the Work, provided + that such additional attribution notices cannot be construed + as modifying the License. + + You may add Your own copyright statement to Your modifications and + may provide additional or different license terms and conditions + for use, reproduction, or distribution of Your modifications, or + for any such Derivative Works as a whole, provided Your use, + reproduction, and distribution of the Work otherwise complies with + the conditions stated in this License. + +5. Submission of Contributions. Unless You explicitly state otherwise, + any Contribution intentionally submitted for inclusion in the Work + by You to the Licensor shall be under the terms and conditions of + this License, without any additional terms or conditions. + Notwithstanding the above, nothing herein shall supersede or modify + the terms of any separate license agreement you may have executed + with Licensor regarding such Contributions. + +6. Trademarks. This License does not grant permission to use the trade + names, trademarks, service marks, or product names of the Licensor, + except as required for reasonable and customary use in describing the + origin of the Work and reproducing the content of the NOTICE file. + +7. Disclaimer of Warranty. Unless required by applicable law or + agreed to in writing, Licensor provides the Work (and each + Contributor provides its Contributions) on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or + implied, including, without limitation, any warranties or conditions + of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A + PARTICULAR PURPOSE. You are solely responsible for determining the + appropriateness of using or redistributing the Work and assume any + risks associated with Your exercise of permissions under this License. + +8. Limitation of Liability. In no event and under no legal theory, + whether in tort (including negligence), contract, or otherwise, + unless required by applicable law (such as deliberate and grossly + negligent acts) or agreed to in writing, shall any Contributor be + liable to You for damages, including any direct, indirect, special, + incidental, or consequential damages of any character arising as a + result of this License or out of the use or inability to use the + Work (including but not limited to damages for loss of goodwill, + work stoppage, computer failure or malfunction, or any and all + other commercial damages or losses), even if such Contributor + has been advised of the possibility of such damages. + +9. Accepting Warranty or Additional Liability. While redistributing + the Work or Derivative Works thereof, You may choose to offer, + and charge a fee for, acceptance of support, warranty, indemnity, + or other liability obligations and/or rights consistent with this + License. However, in accepting such obligations, You may act only + on Your own behalf and on Your sole responsibility, not on behalf + of any other Contributor, and only if You agree to indemnify, + defend, and hold each Contributor harmless for any liability + incurred by, or claims asserted against, such Contributor by reason + of your accepting any such warranty or additional liability. + +END OF TERMS AND CONDITIONS + +APPENDIX: How to apply the Apache License to your work. + + To apply the Apache License to your work, attach the following + boilerplate notice, with the fields enclosed by brackets "[]" + replaced with your own identifying information. (Don't include + the brackets!) The text should be enclosed in the appropriate + comment syntax for the file format. We also recommend that a + file or class name and description of purpose be included on the + same "printed page" as the copyright notice for easier + identification within third-party archives. + +Copyright [yyyy] [name of copyright owner] + +Licensed under the Apache License, Version 2.0 (the "License"); +you may not use this file except in compliance with the License. +You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + +Unless required by applicable law or agreed to in writing, software +distributed under the License is distributed on an "AS IS" BASIS, +WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +See the License for the specific language governing permissions and +limitations under the License. diff --git a/vendor/primeorder/LICENSE-MIT b/vendor/primeorder/LICENSE-MIT new file mode 100644 index 000000000..50b1254c1 --- /dev/null +++ b/vendor/primeorder/LICENSE-MIT @@ -0,0 +1,25 @@ +Copyright (c) 2020-2023 RustCrypto Developers + +Permission is hereby granted, free of charge, to any +person obtaining a copy of this software and associated +documentation files (the "Software"), to deal in the +Software without restriction, including without +limitation the rights to use, copy, modify, merge, +publish, distribute, sublicense, and/or sell copies of +the Software, and to permit persons to whom the Software +is furnished to do so, subject to the following +conditions: + +The above copyright notice and this permission notice +shall be included in all copies or substantial portions +of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF +ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED +TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A +PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT +SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY +CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION +OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR +IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER +DEALINGS IN THE SOFTWARE. diff --git a/vendor/primeorder/README.md b/vendor/primeorder/README.md new file mode 100644 index 000000000..0c30c7bb5 --- /dev/null +++ b/vendor/primeorder/README.md @@ -0,0 +1,88 @@ +# [RustCrypto]: Prime Order Elliptic Curve Formulas + +[![crate][crate-image]][crate-link] +[![Docs][docs-image]][docs-link] +[![Build Status][build-image]][build-link] +![Apache2/MIT licensed][license-image] +![Rust Version][rustc-image] +[![Project Chat][chat-image]][chat-link] + +Pure Rust implementation of complete addition formulas for prime order elliptic +curves ([Renes-Costello-Batina 2015]). Generic over field elements and curve +equation coefficients. + +[Documentation][docs-link] + +## About + +This crate provides a generic implementation of complete formulas for prime +order elliptic curves which are defined by the short [Weierstrass equation]: + +```text +y² = x³ + ax + b +``` + +It's used to implement the following elliptic curves: + +- [`p256`]: NIST P-256 +- [`p384`]: NIST P-384 + +## ⚠️ Security Warning + +The elliptic curve arithmetic contained in this crate has never been +independently audited! + +This crate has been designed with the goal of ensuring that secret-dependent +operations are performed in constant time (using the `subtle` crate and +constant-time formulas). However, it has not been thoroughly assessed to ensure +that generated assembly is constant time on common CPU architectures. + +USE AT YOUR OWN RISK! + +## Minimum Supported Rust Version + +Rust **1.65** or higher. + +Minimum supported Rust version can be changed in the future, but it will be +done with a minor version bump. + +## SemVer Policy + +- All on-by-default features of this library are covered by SemVer +- MSRV is considered exempt from SemVer as noted above + +## License + +All crates licensed under either of: + +- [Apache License, Version 2.0](http://www.apache.org/licenses/LICENSE-2.0) +- [MIT license](http://opensource.org/licenses/MIT) + +at your option. + +### Contribution + +Unless you explicitly state otherwise, any contribution intentionally submitted +for inclusion in the work by you, as defined in the Apache-2.0 license, shall be +dual licensed as above, without any additional terms or conditions. + +[//]: # (badges) + +[crate-image]: https://buildstats.info/crate/primeorder +[crate-link]: https://crates.io/crates/primeorder +[docs-image]: https://docs.rs/primeorder/badge.svg +[docs-link]: https://docs.rs/primeorder/ +[build-image]: https://github.com/RustCrypto/elliptic-curves/actions/workflows/primeorder.yml/badge.svg +[build-link]: https://github.com/RustCrypto/elliptic-curves/actions/workflows/primeorder.yml +[license-image]: https://img.shields.io/badge/license-Apache2.0/MIT-blue.svg +[rustc-image]: https://img.shields.io/badge/rustc-1.65+-blue.svg +[chat-image]: https://img.shields.io/badge/zulip-join_chat-blue.svg +[chat-link]: https://rustcrypto.zulipchat.com/#narrow/stream/260040-elliptic-curves + +[//]: # (links) + +[RustCrypto]: https://github.com/rustcrypto/ +[Renes-Costello-Batina 2015]: https://eprint.iacr.org/2015/1060 +[Weierstrass equation]: https://crypto.stanford.edu/pbc/notes/elliptic/weier.html +[`p256`]: https://github.com/RustCrypto/elliptic-curves/tree/master/p256 +[`p384`]: https://github.com/RustCrypto/elliptic-curves/tree/master/p256 diff --git a/vendor/primeorder/src/affine.rs b/vendor/primeorder/src/affine.rs new file mode 100644 index 000000000..e7f2feccd --- /dev/null +++ b/vendor/primeorder/src/affine.rs @@ -0,0 +1,485 @@ +//! Affine curve points. + +#![allow(clippy::op_ref)] + +use crate::{PrimeCurveParams, ProjectivePoint}; +use core::{ + borrow::Borrow, + ops::{Mul, Neg}, +}; +use elliptic_curve::{ + ff::{Field, PrimeField}, + generic_array::ArrayLength, + group::{prime::PrimeCurveAffine, GroupEncoding}, + point::{AffineCoordinates, DecompactPoint, DecompressPoint, Double}, + sec1::{ + self, CompressedPoint, EncodedPoint, FromEncodedPoint, ModulusSize, ToCompactEncodedPoint, + ToEncodedPoint, UncompressedPointSize, + }, + subtle::{Choice, ConditionallySelectable, ConstantTimeEq, ConstantTimeGreater, CtOption}, + zeroize::DefaultIsZeroes, + Error, FieldBytes, FieldBytesEncoding, FieldBytesSize, PublicKey, Result, Scalar, +}; + +#[cfg(feature = "serde")] +use serdect::serde::{de, ser, Deserialize, Serialize}; + +/// Point on a Weierstrass curve in affine coordinates. +#[derive(Clone, Copy, Debug)] +pub struct AffinePoint { + /// x-coordinate + pub(crate) x: C::FieldElement, + + /// y-coordinate + pub(crate) y: C::FieldElement, + + /// Is this point the point at infinity? 0 = no, 1 = yes + /// + /// This is a proxy for [`Choice`], but uses `u8` instead to permit `const` + /// constructors for `IDENTITY` and `GENERATOR`. + pub(crate) infinity: u8, +} + +impl AffinePoint +where + C: PrimeCurveParams, +{ + /// Additive identity of the group a.k.a. the point at infinity. + pub const IDENTITY: Self = Self { + x: C::FieldElement::ZERO, + y: C::FieldElement::ZERO, + infinity: 1, + }; + + /// Base point of the curve. + pub const GENERATOR: Self = Self { + x: C::GENERATOR.0, + y: C::GENERATOR.1, + infinity: 0, + }; + + /// Is this point the point at infinity? + pub fn is_identity(&self) -> Choice { + Choice::from(self.infinity) + } + + /// Conditionally negate [`AffinePoint`] for use with point compaction. + fn to_compact(self) -> Self { + let neg_self = -self; + let choice = C::Uint::decode_field_bytes(&self.y.to_repr()) + .ct_gt(&C::Uint::decode_field_bytes(&neg_self.y.to_repr())); + + Self { + x: self.x, + y: C::FieldElement::conditional_select(&self.y, &neg_self.y, choice), + infinity: self.infinity, + } + } +} + +impl AffineCoordinates for AffinePoint +where + C: PrimeCurveParams, +{ + type FieldRepr = FieldBytes; + + fn x(&self) -> FieldBytes { + self.x.to_repr() + } + + fn y_is_odd(&self) -> Choice { + self.y.is_odd() + } +} + +impl ConditionallySelectable for AffinePoint +where + C: PrimeCurveParams, +{ + fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self { + Self { + x: C::FieldElement::conditional_select(&a.x, &b.x, choice), + y: C::FieldElement::conditional_select(&a.y, &b.y, choice), + infinity: u8::conditional_select(&a.infinity, &b.infinity, choice), + } + } +} + +impl ConstantTimeEq for AffinePoint +where + C: PrimeCurveParams, +{ + fn ct_eq(&self, other: &Self) -> Choice { + self.x.ct_eq(&other.x) & self.y.ct_eq(&other.y) & self.infinity.ct_eq(&other.infinity) + } +} + +impl Default for AffinePoint +where + C: PrimeCurveParams, +{ + fn default() -> Self { + Self::IDENTITY + } +} + +impl DefaultIsZeroes for AffinePoint where C: PrimeCurveParams {} + +impl DecompressPoint for AffinePoint +where + C: PrimeCurveParams, + FieldBytes: Copy, +{ + fn decompress(x_bytes: &FieldBytes, y_is_odd: Choice) -> CtOption { + C::FieldElement::from_repr(*x_bytes).and_then(|x| { + let alpha = x * &x * &x + &(C::EQUATION_A * &x) + &C::EQUATION_B; + let beta = alpha.sqrt(); + + beta.map(|beta| { + let y = C::FieldElement::conditional_select( + &-beta, + &beta, + beta.is_odd().ct_eq(&y_is_odd), + ); + + Self { x, y, infinity: 0 } + }) + }) + } +} + +impl DecompactPoint for AffinePoint +where + C: PrimeCurveParams, + FieldBytes: Copy, +{ + fn decompact(x_bytes: &FieldBytes) -> CtOption { + Self::decompress(x_bytes, Choice::from(0)).map(|point| point.to_compact()) + } +} + +impl Eq for AffinePoint where C: PrimeCurveParams {} + +impl FromEncodedPoint for AffinePoint +where + C: PrimeCurveParams, + FieldBytes: Copy, + FieldBytesSize: ModulusSize, + CompressedPoint: Copy, +{ + /// Attempts to parse the given [`EncodedPoint`] as an SEC1-encoded + /// [`AffinePoint`]. + /// + /// # Returns + /// + /// `None` value if `encoded_point` is not on the secp384r1 curve. + fn from_encoded_point(encoded_point: &EncodedPoint) -> CtOption { + match encoded_point.coordinates() { + sec1::Coordinates::Identity => CtOption::new(Self::IDENTITY, 1.into()), + sec1::Coordinates::Compact { x } => Self::decompact(x), + sec1::Coordinates::Compressed { x, y_is_odd } => { + Self::decompress(x, Choice::from(y_is_odd as u8)) + } + sec1::Coordinates::Uncompressed { x, y } => { + C::FieldElement::from_repr(*y).and_then(|y| { + Self::decompress(x, y.is_odd()) + .and_then(|point| CtOption::new(point, point.y.ct_eq(&y))) + }) + } + } + } +} + +impl From> for AffinePoint +where + C: PrimeCurveParams, +{ + fn from(p: ProjectivePoint) -> AffinePoint { + p.to_affine() + } +} + +impl From<&ProjectivePoint> for AffinePoint +where + C: PrimeCurveParams, +{ + fn from(p: &ProjectivePoint) -> AffinePoint { + p.to_affine() + } +} + +impl From> for AffinePoint +where + C: PrimeCurveParams, +{ + fn from(public_key: PublicKey) -> AffinePoint { + *public_key.as_affine() + } +} + +impl From<&PublicKey> for AffinePoint +where + C: PrimeCurveParams, +{ + fn from(public_key: &PublicKey) -> AffinePoint { + AffinePoint::from(*public_key) + } +} + +impl From> for EncodedPoint +where + C: PrimeCurveParams, + FieldBytesSize: ModulusSize, + CompressedPoint: Copy, + as ArrayLength>::ArrayType: Copy, +{ + fn from(affine: AffinePoint) -> EncodedPoint { + affine.to_encoded_point(false) + } +} + +impl GroupEncoding for AffinePoint +where + C: PrimeCurveParams, + FieldBytes: Copy, + FieldBytesSize: ModulusSize, + CompressedPoint: Copy, + as ArrayLength>::ArrayType: Copy, +{ + type Repr = CompressedPoint; + + /// NOTE: not constant-time with respect to identity point + fn from_bytes(bytes: &Self::Repr) -> CtOption { + EncodedPoint::::from_bytes(bytes) + .map(|point| CtOption::new(point, Choice::from(1))) + .unwrap_or_else(|_| { + // SEC1 identity encoding is technically 1-byte 0x00, but the + // `GroupEncoding` API requires a fixed-width `Repr` + let is_identity = bytes.ct_eq(&Self::Repr::default()); + CtOption::new(EncodedPoint::::identity(), is_identity) + }) + .and_then(|point| Self::from_encoded_point(&point)) + } + + fn from_bytes_unchecked(bytes: &Self::Repr) -> CtOption { + // No unchecked conversion possible for compressed points + Self::from_bytes(bytes) + } + + fn to_bytes(&self) -> Self::Repr { + let encoded = self.to_encoded_point(true); + let mut result = CompressedPoint::::default(); + result[..encoded.len()].copy_from_slice(encoded.as_bytes()); + result + } +} + +impl PartialEq for AffinePoint +where + C: PrimeCurveParams, +{ + fn eq(&self, other: &Self) -> bool { + self.ct_eq(other).into() + } +} + +impl PrimeCurveAffine for AffinePoint +where + C: PrimeCurveParams, + FieldBytes: Copy, + FieldBytesSize: ModulusSize, + ProjectivePoint: Double, + CompressedPoint: Copy, + as ArrayLength>::ArrayType: Copy, +{ + type Curve = ProjectivePoint; + type Scalar = Scalar; + + fn identity() -> AffinePoint { + Self::IDENTITY + } + + fn generator() -> AffinePoint { + Self::GENERATOR + } + + fn is_identity(&self) -> Choice { + self.is_identity() + } + + fn to_curve(&self) -> ProjectivePoint { + ProjectivePoint::from(*self) + } +} + +impl ToCompactEncodedPoint for AffinePoint +where + C: PrimeCurveParams, + FieldBytesSize: ModulusSize, + CompressedPoint: Copy, + as ArrayLength>::ArrayType: Copy, +{ + /// Serialize this value as a SEC1 compact [`EncodedPoint`] + fn to_compact_encoded_point(&self) -> CtOption> { + let point = self.to_compact(); + + let mut bytes = CompressedPoint::::default(); + bytes[0] = sec1::Tag::Compact.into(); + bytes[1..].copy_from_slice(&point.x.to_repr()); + + let encoded = EncodedPoint::::from_bytes(bytes); + let is_some = point.y.ct_eq(&self.y); + CtOption::new(encoded.unwrap_or_default(), is_some) + } +} + +impl ToEncodedPoint for AffinePoint +where + C: PrimeCurveParams, + FieldBytesSize: ModulusSize, + CompressedPoint: Copy, + as ArrayLength>::ArrayType: Copy, +{ + fn to_encoded_point(&self, compress: bool) -> EncodedPoint { + EncodedPoint::::conditional_select( + &EncodedPoint::::from_affine_coordinates( + &self.x.to_repr(), + &self.y.to_repr(), + compress, + ), + &EncodedPoint::::identity(), + self.is_identity(), + ) + } +} + +impl TryFrom> for AffinePoint +where + C: PrimeCurveParams, + FieldBytes: Copy, + FieldBytesSize: ModulusSize, + CompressedPoint: Copy, +{ + type Error = Error; + + fn try_from(point: EncodedPoint) -> Result> { + AffinePoint::try_from(&point) + } +} + +impl TryFrom<&EncodedPoint> for AffinePoint +where + C: PrimeCurveParams, + FieldBytes: Copy, + FieldBytesSize: ModulusSize, + CompressedPoint: Copy, +{ + type Error = Error; + + fn try_from(point: &EncodedPoint) -> Result> { + Option::from(AffinePoint::::from_encoded_point(point)).ok_or(Error) + } +} + +impl TryFrom> for PublicKey +where + C: PrimeCurveParams, +{ + type Error = Error; + + fn try_from(affine_point: AffinePoint) -> Result> { + PublicKey::from_affine(affine_point) + } +} + +impl TryFrom<&AffinePoint> for PublicKey +where + C: PrimeCurveParams, +{ + type Error = Error; + + fn try_from(affine_point: &AffinePoint) -> Result> { + PublicKey::::try_from(*affine_point) + } +} + +// +// Arithmetic trait impls +// + +impl Mul for AffinePoint +where + C: PrimeCurveParams, + S: Borrow>, + ProjectivePoint: Double, +{ + type Output = ProjectivePoint; + + fn mul(self, scalar: S) -> ProjectivePoint { + ProjectivePoint::::from(self) * scalar + } +} + +impl Neg for AffinePoint +where + C: PrimeCurveParams, +{ + type Output = Self; + + fn neg(self) -> Self { + AffinePoint { + x: self.x, + y: -self.y, + infinity: self.infinity, + } + } +} + +impl Neg for &AffinePoint +where + C: PrimeCurveParams, +{ + type Output = AffinePoint; + + fn neg(self) -> AffinePoint { + -(*self) + } +} + +// +// serde support +// + +#[cfg(feature = "serde")] +impl Serialize for AffinePoint +where + C: PrimeCurveParams, + FieldBytesSize: ModulusSize, + CompressedPoint: Copy, + as ArrayLength>::ArrayType: Copy, +{ + fn serialize(&self, serializer: S) -> core::result::Result + where + S: ser::Serializer, + { + self.to_encoded_point(true).serialize(serializer) + } +} + +#[cfg(feature = "serde")] +impl<'de, C> Deserialize<'de> for AffinePoint +where + C: PrimeCurveParams, + FieldBytes: Copy, + FieldBytesSize: ModulusSize, + CompressedPoint: Copy, +{ + fn deserialize(deserializer: D) -> core::result::Result + where + D: de::Deserializer<'de>, + { + EncodedPoint::::deserialize(deserializer)? + .try_into() + .map_err(de::Error::custom) + } +} diff --git a/vendor/primeorder/src/dev.rs b/vendor/primeorder/src/dev.rs new file mode 100644 index 000000000..67877aa74 --- /dev/null +++ b/vendor/primeorder/src/dev.rs @@ -0,0 +1,152 @@ +//! Development-related functionality. + +/// Implement projective arithmetic tests. +#[macro_export] +macro_rules! impl_projective_arithmetic_tests { + ( + $affine:tt, + $projective:tt, + $scalar:ty, + $add_vectors:expr, + $mul_vectors:expr + ) => { + /// Assert that the provided projective point matches the given test vector. + // TODO(tarcieri): use coordinate APIs. See zkcrypto/group#30 + macro_rules! assert_point_eq { + ($actual:expr, $expected:expr) => { + let (expected_x, expected_y) = $expected; + + let point = $actual.to_affine().to_encoded_point(false); + let (actual_x, actual_y) = match point.coordinates() { + sec1::Coordinates::Uncompressed { x, y } => (x, y), + _ => unreachable!(), + }; + + assert_eq!(&expected_x, actual_x.as_slice()); + assert_eq!(&expected_y, actual_y.as_slice()); + }; + } + + #[test] + fn affine_to_projective() { + let basepoint_affine = $affine::GENERATOR; + let basepoint_projective = $projective::GENERATOR; + + assert_eq!($projective::from(basepoint_affine), basepoint_projective,); + assert_eq!(basepoint_projective.to_affine(), basepoint_affine); + assert!(!bool::from(basepoint_projective.to_affine().is_identity())); + + assert!(bool::from($projective::IDENTITY.to_affine().is_identity())); + } + + #[test] + fn projective_identity_addition() { + let identity = $projective::IDENTITY; + let generator = $projective::GENERATOR; + + assert_eq!(identity + &generator, generator); + assert_eq!(generator + &identity, generator); + } + + #[test] + fn projective_mixed_addition() { + let identity = $projective::IDENTITY; + let basepoint_affine = $affine::GENERATOR; + let basepoint_projective = $projective::GENERATOR; + + assert_eq!(identity + &basepoint_affine, basepoint_projective); + assert_eq!( + basepoint_projective + &basepoint_affine, + basepoint_projective + &basepoint_projective + ); + } + + #[test] + fn test_vector_repeated_add() { + let generator = $projective::GENERATOR; + let mut p = generator; + + for i in 0..$add_vectors.len() { + assert_point_eq!(p, $add_vectors[i]); + p += &generator; + } + } + + #[test] + fn test_vector_repeated_add_mixed() { + let generator = $affine::GENERATOR; + let mut p = $projective::GENERATOR; + + for i in 0..$add_vectors.len() { + assert_point_eq!(p, $add_vectors[i]); + p += &generator; + } + } + + #[test] + fn test_vector_add_mixed_identity() { + let generator = $projective::GENERATOR; + let p0 = generator + $projective::IDENTITY; + let p1 = generator + $affine::IDENTITY; + assert_eq!(p0, p1); + } + + #[test] + fn test_vector_double_generator() { + let generator = $projective::GENERATOR; + let mut p = generator; + + for i in 0..2 { + assert_point_eq!(p, $add_vectors[i]); + p = p.double(); + } + } + + #[test] + fn projective_add_vs_double() { + let generator = $projective::GENERATOR; + assert_eq!(generator + &generator, generator.double()); + } + + #[test] + fn projective_add_and_sub() { + let basepoint_affine = $affine::GENERATOR; + let basepoint_projective = $projective::GENERATOR; + + assert_eq!( + (basepoint_projective + &basepoint_projective) - &basepoint_projective, + basepoint_projective + ); + assert_eq!( + (basepoint_projective + &basepoint_affine) - &basepoint_affine, + basepoint_projective + ); + } + + #[test] + fn projective_double_and_sub() { + let generator = $projective::GENERATOR; + assert_eq!(generator.double() - &generator, generator); + } + + #[test] + fn test_vector_scalar_mult() { + let generator = $projective::GENERATOR; + + for (k, coords) in $add_vectors + .iter() + .enumerate() + .map(|(k, coords)| (<$scalar>::from(k as u64 + 1), *coords)) + .chain( + $mul_vectors + .iter() + .cloned() + .map(|(k, x, y)| (<$scalar>::from_repr(k.into()).unwrap(), (x, y))), + ) + { + let p = generator * &k; + assert_point_eq!(p, coords); + } + } + }; +} diff --git a/vendor/primeorder/src/field.rs b/vendor/primeorder/src/field.rs new file mode 100644 index 000000000..a347f0bb1 --- /dev/null +++ b/vendor/primeorder/src/field.rs @@ -0,0 +1,641 @@ +/// Implements a field element type whose internal representation is in +/// Montgomery form, providing a combination of trait impls and inherent impls +/// which are `const fn` where possible. +/// +/// Accepts a set of `const fn` arithmetic operation functions as arguments. +/// +/// # Inherent impls +/// - `const ZERO: Self` +/// - `const ONE: Self` (multiplicative identity) +/// - `pub fn from_bytes` +/// - `pub fn from_slice` +/// - `pub fn from_uint` +/// - `fn from_uint_unchecked` +/// - `pub fn to_bytes` +/// - `pub fn to_canonical` +/// - `pub fn is_odd` +/// - `pub fn is_zero` +/// - `pub fn double` +/// +/// NOTE: field implementations must provide their own inherent impls of +/// the following methods in order for the code generated by this macro to +/// compile: +/// +/// - `pub fn invert` +/// - `pub fn sqrt` +/// +/// # Trait impls +/// - `AsRef<$arr>` +/// - `ConditionallySelectable` +/// - `ConstantTimeEq` +/// - `ConstantTimeGreater` +/// - `ConstantTimeLess` +/// - `Default` +/// - `DefaultIsZeroes` +/// - `Eq` +/// - `Field` +/// - `PartialEq` +/// +/// ## Ops +/// - `Add` +/// - `AddAssign` +/// - `Sub` +/// - `SubAssign` +/// - `Mul` +/// - `MulAssign` +/// - `Neg` +#[macro_export] +macro_rules! impl_mont_field_element { + ( + $curve:tt, + $fe:tt, + $bytes:ty, + $uint:ty, + $modulus:expr, + $arr:ty, + $from_mont:ident, + $to_mont:ident, + $add:ident, + $sub:ident, + $mul:ident, + $neg:ident, + $square:ident + ) => { + impl $fe { + /// Zero element. + pub const ZERO: Self = Self(<$uint>::ZERO); + + /// Multiplicative identity. + pub const ONE: Self = Self::from_uint_unchecked(<$uint>::ONE); + + /// Create a [` + #[doc = stringify!($fe)] + /// `] from a canonical big-endian representation. + pub fn from_bytes(repr: &$bytes) -> $crate::elliptic_curve::subtle::CtOption { + use $crate::elliptic_curve::FieldBytesEncoding; + Self::from_uint(FieldBytesEncoding::<$curve>::decode_field_bytes(repr)) + } + + /// Decode [` + #[doc = stringify!($fe)] + /// `] from a big endian byte slice. + pub fn from_slice(slice: &[u8]) -> $crate::elliptic_curve::Result { + use $crate::elliptic_curve::generic_array::{typenum::Unsigned, GenericArray}; + + if slice.len() != <$curve as $crate::elliptic_curve::Curve>::FieldBytesSize::USIZE { + return Err($crate::elliptic_curve::Error); + } + + Option::from(Self::from_bytes(GenericArray::from_slice(slice))) + .ok_or($crate::elliptic_curve::Error) + } + + /// Decode [` + #[doc = stringify!($fe)] + /// `] + /// from [` + #[doc = stringify!($uint)] + /// `] converting it into Montgomery form: + /// + /// ```text + /// w * R^2 * R^-1 mod p = wR mod p + /// ``` + pub fn from_uint(uint: $uint) -> $crate::elliptic_curve::subtle::CtOption { + use $crate::elliptic_curve::subtle::ConstantTimeLess as _; + let is_some = uint.ct_lt(&$modulus); + $crate::elliptic_curve::subtle::CtOption::new( + Self::from_uint_unchecked(uint), + is_some, + ) + } + + /// Parse a [` + #[doc = stringify!($fe)] + /// `] from big endian hex-encoded bytes. + /// + /// Does *not* perform a check that the field element does not overflow the order. + /// + /// This method is primarily intended for defining internal constants. + #[allow(dead_code)] + pub(crate) const fn from_hex(hex: &str) -> Self { + Self::from_uint_unchecked(<$uint>::from_be_hex(hex)) + } + + /// Convert a `u64` into a [` + #[doc = stringify!($fe)] + /// `]. + pub const fn from_u64(w: u64) -> Self { + Self::from_uint_unchecked(<$uint>::from_u64(w)) + } + + /// Decode [` + #[doc = stringify!($fe)] + /// `] from [` + #[doc = stringify!($uint)] + /// `] converting it into Montgomery form. + /// + /// Does *not* perform a check that the field element does not overflow the order. + /// + /// Used incorrectly this can lead to invalid results! + pub(crate) const fn from_uint_unchecked(w: $uint) -> Self { + Self(<$uint>::from_words($to_mont(w.as_words()))) + } + + /// Returns the big-endian encoding of this [` + #[doc = stringify!($fe)] + /// `]. + pub fn to_bytes(self) -> $bytes { + use $crate::elliptic_curve::FieldBytesEncoding; + FieldBytesEncoding::<$curve>::encode_field_bytes(&self.to_canonical()) + } + + /// Translate [` + #[doc = stringify!($fe)] + /// `] out of the Montgomery domain, returning a [` + #[doc = stringify!($uint)] + /// `] in canonical form. + #[inline] + pub const fn to_canonical(self) -> $uint { + <$uint>::from_words($from_mont(self.0.as_words())) + } + + /// Determine if this [` + #[doc = stringify!($fe)] + /// `] is odd in the SEC1 sense: `self mod 2 == 1`. + /// + /// # Returns + /// + /// If odd, return `Choice(1)`. Otherwise, return `Choice(0)`. + pub fn is_odd(&self) -> Choice { + use $crate::elliptic_curve::bigint::Integer; + self.to_canonical().is_odd() + } + + /// Determine if this [` + #[doc = stringify!($fe)] + /// `] is even in the SEC1 sense: `self mod 2 == 0`. + /// + /// # Returns + /// + /// If even, return `Choice(1)`. Otherwise, return `Choice(0)`. + pub fn is_even(&self) -> Choice { + !self.is_odd() + } + + /// Determine if this [` + #[doc = stringify!($fe)] + /// `] is zero. + /// + /// # Returns + /// + /// If zero, return `Choice(1)`. Otherwise, return `Choice(0)`. + pub fn is_zero(&self) -> Choice { + self.ct_eq(&Self::ZERO) + } + + /// Add elements. + pub const fn add(&self, rhs: &Self) -> Self { + Self(<$uint>::from_words($add( + self.0.as_words(), + rhs.0.as_words(), + ))) + } + + /// Double element (add it to itself). + #[must_use] + pub const fn double(&self) -> Self { + self.add(self) + } + + /// Subtract elements. + pub const fn sub(&self, rhs: &Self) -> Self { + Self(<$uint>::from_words($sub( + self.0.as_words(), + rhs.0.as_words(), + ))) + } + + /// Multiply elements. + pub const fn multiply(&self, rhs: &Self) -> Self { + Self(<$uint>::from_words($mul( + self.0.as_words(), + rhs.0.as_words(), + ))) + } + + /// Negate element. + pub const fn neg(&self) -> Self { + Self(<$uint>::from_words($neg(self.0.as_words()))) + } + + /// Compute modular square. + #[must_use] + pub const fn square(&self) -> Self { + Self(<$uint>::from_words($square(self.0.as_words()))) + } + + /// Returns `self^exp`, where `exp` is a little-endian integer exponent. + /// + /// **This operation is variable time with respect to the exponent.** + /// + /// If the exponent is fixed, this operation is effectively constant time. + pub const fn pow_vartime(&self, exp: &[u64]) -> Self { + let mut res = Self::ONE; + let mut i = exp.len(); + + while i > 0 { + i -= 1; + + let mut j = 64; + while j > 0 { + j -= 1; + res = res.square(); + + if ((exp[i] >> j) & 1) == 1 { + res = res.multiply(self); + } + } + } + + res + } + } + + impl AsRef<$arr> for $fe { + fn as_ref(&self) -> &$arr { + self.0.as_ref() + } + } + + impl Default for $fe { + fn default() -> Self { + Self::ZERO + } + } + + impl Eq for $fe {} + impl PartialEq for $fe { + fn eq(&self, rhs: &Self) -> bool { + self.0.ct_eq(&(rhs.0)).into() + } + } + + impl From for $fe { + fn from(n: u32) -> $fe { + Self::from_uint_unchecked(<$uint>::from(n)) + } + } + + impl From for $fe { + fn from(n: u64) -> $fe { + Self::from_uint_unchecked(<$uint>::from(n)) + } + } + + impl From for $fe { + fn from(n: u128) -> $fe { + Self::from_uint_unchecked(<$uint>::from(n)) + } + } + + impl $crate::elliptic_curve::subtle::ConditionallySelectable for $fe { + fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self { + Self(<$uint>::conditional_select(&a.0, &b.0, choice)) + } + } + + impl $crate::elliptic_curve::subtle::ConstantTimeEq for $fe { + fn ct_eq(&self, other: &Self) -> $crate::elliptic_curve::subtle::Choice { + self.0.ct_eq(&other.0) + } + } + + impl $crate::elliptic_curve::subtle::ConstantTimeGreater for $fe { + fn ct_gt(&self, other: &Self) -> $crate::elliptic_curve::subtle::Choice { + self.0.ct_gt(&other.0) + } + } + + impl $crate::elliptic_curve::subtle::ConstantTimeLess for $fe { + fn ct_lt(&self, other: &Self) -> $crate::elliptic_curve::subtle::Choice { + self.0.ct_lt(&other.0) + } + } + + impl $crate::elliptic_curve::zeroize::DefaultIsZeroes for $fe {} + + impl $crate::elliptic_curve::ff::Field for $fe { + const ZERO: Self = Self::ZERO; + const ONE: Self = Self::ONE; + + fn random(mut rng: impl $crate::elliptic_curve::rand_core::RngCore) -> Self { + // NOTE: can't use ScalarPrimitive::random due to CryptoRng bound + let mut bytes = <$bytes>::default(); + + loop { + rng.fill_bytes(&mut bytes); + if let Some(fe) = Self::from_bytes(&bytes).into() { + return fe; + } + } + } + + fn is_zero(&self) -> Choice { + Self::ZERO.ct_eq(self) + } + + #[must_use] + fn square(&self) -> Self { + self.square() + } + + #[must_use] + fn double(&self) -> Self { + self.double() + } + + fn invert(&self) -> CtOption { + self.invert() + } + + fn sqrt(&self) -> CtOption { + self.sqrt() + } + + fn sqrt_ratio(num: &Self, div: &Self) -> (Choice, Self) { + $crate::elliptic_curve::ff::helpers::sqrt_ratio_generic(num, div) + } + } + + $crate::impl_field_op!($fe, Add, add, $add); + $crate::impl_field_op!($fe, Sub, sub, $sub); + $crate::impl_field_op!($fe, Mul, mul, $mul); + + impl AddAssign<$fe> for $fe { + #[inline] + fn add_assign(&mut self, other: $fe) { + *self = *self + other; + } + } + + impl AddAssign<&$fe> for $fe { + #[inline] + fn add_assign(&mut self, other: &$fe) { + *self = *self + other; + } + } + + impl SubAssign<$fe> for $fe { + #[inline] + fn sub_assign(&mut self, other: $fe) { + *self = *self - other; + } + } + + impl SubAssign<&$fe> for $fe { + #[inline] + fn sub_assign(&mut self, other: &$fe) { + *self = *self - other; + } + } + + impl MulAssign<&$fe> for $fe { + #[inline] + fn mul_assign(&mut self, other: &$fe) { + *self = *self * other; + } + } + + impl MulAssign for $fe { + #[inline] + fn mul_assign(&mut self, other: $fe) { + *self = *self * other; + } + } + + impl Neg for $fe { + type Output = $fe; + + #[inline] + fn neg(self) -> $fe { + Self($neg(self.as_ref()).into()) + } + } + + impl Sum for $fe { + fn sum>(iter: I) -> Self { + iter.reduce(core::ops::Add::add).unwrap_or(Self::ZERO) + } + } + + impl<'a> Sum<&'a $fe> for $fe { + fn sum>(iter: I) -> Self { + iter.copied().sum() + } + } + + impl Product for $fe { + fn product>(iter: I) -> Self { + iter.reduce(core::ops::Mul::mul).unwrap_or(Self::ONE) + } + } + + impl<'a> Product<&'a $fe> for $fe { + fn product>(iter: I) -> Self { + iter.copied().product() + } + } + }; +} + +/// Emit impls for a `core::ops` trait for all combinations of reference types, +/// which thunk to the given function. +#[macro_export] +macro_rules! impl_field_op { + ($fe:tt, $op:tt, $op_fn:ident, $func:ident) => { + impl ::core::ops::$op for $fe { + type Output = $fe; + + #[inline] + fn $op_fn(self, rhs: $fe) -> $fe { + $fe($func(self.as_ref(), rhs.as_ref()).into()) + } + } + + impl ::core::ops::$op<&$fe> for $fe { + type Output = $fe; + + #[inline] + fn $op_fn(self, rhs: &$fe) -> $fe { + $fe($func(self.as_ref(), rhs.as_ref()).into()) + } + } + + impl ::core::ops::$op<&$fe> for &$fe { + type Output = $fe; + + #[inline] + fn $op_fn(self, rhs: &$fe) -> $fe { + $fe($func(self.as_ref(), rhs.as_ref()).into()) + } + } + }; +} + +/// Implement Bernstein-Yang field element inversion. +#[macro_export] +macro_rules! impl_bernstein_yang_invert { + ( + $a:expr, + $one:expr, + $d:expr, + $nlimbs:expr, + $word:ty, + $from_montgomery:ident, + $mul:ident, + $neg:ident, + $divstep_precomp:ident, + $divstep:ident, + $msat:ident, + $selectznz:ident, + ) => {{ + // See Bernstein-Yang 2019 p.366 + const ITERATIONS: usize = (49 * $d + 57) / 17; + + let a = $from_montgomery($a); + let mut d = 1; + let mut f = $msat(); + let mut g = [0; $nlimbs + 1]; + let mut v = [0; $nlimbs]; + let mut r = $one; + let mut i = 0; + let mut j = 0; + + while j < $nlimbs { + g[j] = a[j]; + j += 1; + } + + while i < ITERATIONS - ITERATIONS % 2 { + let (out1, out2, out3, out4, out5) = $divstep(d, &f, &g, &v, &r); + let (out1, out2, out3, out4, out5) = $divstep(out1, &out2, &out3, &out4, &out5); + d = out1; + f = out2; + g = out3; + v = out4; + r = out5; + i += 2; + } + + if ITERATIONS % 2 != 0 { + let (_out1, out2, _out3, out4, _out5) = $divstep(d, &f, &g, &v, &r); + v = out4; + f = out2; + } + + let s = ((f[f.len() - 1] >> <$word>::BITS - 1) & 1) as u8; + let v = $selectznz(s, &v, &$neg(&v)); + $mul(&v, &$divstep_precomp()) + }}; +} + +/// Implement field element identity tests. +#[macro_export] +macro_rules! impl_field_identity_tests { + ($fe:tt) => { + #[test] + fn zero_is_additive_identity() { + let zero = $fe::ZERO; + let one = $fe::ONE; + assert_eq!(zero.add(&zero), zero); + assert_eq!(one.add(&zero), one); + } + + #[test] + fn one_is_multiplicative_identity() { + let one = $fe::ONE; + assert_eq!(one.multiply(&one), one); + } + }; +} + +/// Implement field element inversion tests. +#[macro_export] +macro_rules! impl_field_invert_tests { + ($fe:tt) => { + #[test] + fn invert() { + let one = $fe::ONE; + assert_eq!(one.invert().unwrap(), one); + + let three = one + &one + &one; + let inv_three = three.invert().unwrap(); + assert_eq!(three * &inv_three, one); + + let minus_three = -three; + let inv_minus_three = minus_three.invert().unwrap(); + assert_eq!(inv_minus_three, -inv_three); + assert_eq!(three * &inv_minus_three, -one); + } + }; +} + +/// Implement field element square root tests. +#[macro_export] +macro_rules! impl_field_sqrt_tests { + ($fe:tt) => { + #[test] + fn sqrt() { + for &n in &[1u64, 4, 9, 16, 25, 36, 49, 64] { + let fe = $fe::from(n); + let sqrt = fe.sqrt().unwrap(); + assert_eq!(sqrt.square(), fe); + } + } + }; +} + +/// Implement tests for the `PrimeField` trait. +#[macro_export] +macro_rules! impl_primefield_tests { + ($fe:tt, $t:expr) => { + #[test] + fn two_inv_constant() { + assert_eq!($fe::from(2u32) * $fe::TWO_INV, $fe::ONE); + } + + #[test] + fn root_of_unity_constant() { + assert!($fe::S < 128); + let two_to_s = 1u128 << $fe::S; + + // ROOT_OF_UNITY^{2^s} mod m == 1 + assert_eq!( + $fe::ROOT_OF_UNITY.pow_vartime(&[ + (two_to_s & 0xFFFFFFFFFFFFFFFF) as u64, + (two_to_s >> 64) as u64, + 0, + 0 + ]), + $fe::ONE + ); + + // MULTIPLICATIVE_GENERATOR^{t} mod m == ROOT_OF_UNITY + assert_eq!( + $fe::MULTIPLICATIVE_GENERATOR.pow_vartime(&$t), + $fe::ROOT_OF_UNITY + ) + } + + #[test] + fn root_of_unity_inv_constant() { + assert_eq!($fe::ROOT_OF_UNITY * $fe::ROOT_OF_UNITY_INV, $fe::ONE); + } + + #[test] + fn delta_constant() { + // DELTA^{t} mod m == 1 + assert_eq!($fe::DELTA.pow_vartime(&$t), $fe::ONE); + } + }; +} diff --git a/vendor/primeorder/src/lib.rs b/vendor/primeorder/src/lib.rs new file mode 100644 index 000000000..0847a995a --- /dev/null +++ b/vendor/primeorder/src/lib.rs @@ -0,0 +1,46 @@ +#![no_std] +#![cfg_attr(docsrs, feature(doc_auto_cfg))] +#![doc( + html_logo_url = "https://raw.githubusercontent.com/RustCrypto/meta/master/logo.svg", + html_favicon_url = "https://raw.githubusercontent.com/RustCrypto/meta/master/logo.svg" +)] +#![forbid(unsafe_code)] +#![warn(missing_docs, rust_2018_idioms, unused_qualifications)] +#![doc = include_str!("../README.md")] + +#[cfg(feature = "dev")] +pub mod dev; +pub mod point_arithmetic; + +mod affine; +mod field; +mod projective; + +pub use crate::{affine::AffinePoint, projective::ProjectivePoint}; +pub use elliptic_curve::{self, point::Double, Field, FieldBytes, PrimeCurve, PrimeField}; + +use elliptic_curve::CurveArithmetic; + +/// Parameters for elliptic curves of prime order which can be described by the +/// short Weierstrass equation. +pub trait PrimeCurveParams: + PrimeCurve + + CurveArithmetic + + CurveArithmetic> + + CurveArithmetic> +{ + /// Base field element type. + type FieldElement: PrimeField>; + + /// [Point arithmetic](point_arithmetic) implementation, might be optimized for this specific curve + type PointArithmetic: point_arithmetic::PointArithmetic; + + /// Coefficient `a` in the curve equation. + const EQUATION_A: Self::FieldElement; + + /// Coefficient `b` in the curve equation. + const EQUATION_B: Self::FieldElement; + + /// Generator point's affine coordinates: (x, y). + const GENERATOR: (Self::FieldElement, Self::FieldElement); +} diff --git a/vendor/primeorder/src/point_arithmetic.rs b/vendor/primeorder/src/point_arithmetic.rs new file mode 100644 index 000000000..b41308992 --- /dev/null +++ b/vendor/primeorder/src/point_arithmetic.rs @@ -0,0 +1,318 @@ +//! Point arithmetic implementation optimised for different curve equations +//! +//! Support for formulas specialized to the short Weierstrass equation's +//! 𝒂-coefficient. + +use elliptic_curve::{subtle::ConditionallySelectable, Field}; + +use crate::{AffinePoint, PrimeCurveParams, ProjectivePoint}; + +mod sealed { + use crate::{AffinePoint, PrimeCurveParams, ProjectivePoint}; + + /// Elliptic point arithmetic implementation + /// + /// Provides implementation of point arithmetic (point addition, point doubling) which + /// might be optimized for the curve. + pub trait PointArithmetic { + /// Returns `lhs + rhs` + fn add(lhs: &ProjectivePoint, rhs: &ProjectivePoint) -> ProjectivePoint; + + /// Returns `lhs + rhs` + fn add_mixed(lhs: &ProjectivePoint, rhs: &AffinePoint) -> ProjectivePoint; + + /// Returns `point + point` + fn double(point: &ProjectivePoint) -> ProjectivePoint; + } +} + +/// Allow crate-local visibility +pub(crate) use sealed::PointArithmetic; + +/// The 𝒂-coefficient of the short Weierstrass equation does not have specific +/// properties which allow for an optimized implementation. +pub struct EquationAIsGeneric {} + +impl PointArithmetic for EquationAIsGeneric { + /// Implements complete addition for any curve + /// + /// Implements the complete addition formula from [Renes-Costello-Batina 2015] + /// (Algorithm 1). The comments after each line indicate which algorithm steps + /// are being performed. + /// + /// [Renes-Costello-Batina 2015]: https://eprint.iacr.org/2015/1060 + fn add(lhs: &ProjectivePoint, rhs: &ProjectivePoint) -> ProjectivePoint { + let b3 = C::FieldElement::from(3) * C::EQUATION_B; + + let t0 = lhs.x * rhs.x; // 1 + let t1 = lhs.y * rhs.y; // 2 + let t2 = lhs.z * rhs.z; // 3 + let t3 = lhs.x + lhs.y; // 4 + let t4 = rhs.x + rhs.y; // 5 + let t3 = t3 * t4; // 6 + let t4 = t0 + t1; // 7 + let t3 = t3 - t4; // 8 + let t4 = lhs.x + lhs.z; // 9 + let t5 = rhs.x + rhs.z; // 10 + let t4 = t4 * t5; // 11 + let t5 = t0 + t2; // 12 + let t4 = t4 - t5; // 13 + let t5 = lhs.y + lhs.z; // 14 + let x3 = rhs.y + rhs.z; // 15 + let t5 = t5 * x3; // 16 + let x3 = t1 + t2; // 17 + let t5 = t5 - x3; // 18 + let z3 = C::EQUATION_A * t4; // 19 + let x3 = b3 * t2; // 20 + let z3 = x3 + z3; // 21 + let x3 = t1 - z3; // 22 + let z3 = t1 + z3; // 23 + let y3 = x3 * z3; // 24 + let t1 = t0 + t0; // 25 + let t1 = t1 + t0; // 26 + let t2 = C::EQUATION_A * t2; // 27 + let t4 = b3 * t4; // 28 + let t1 = t1 + t2; // 29 + let t2 = t0 - t2; // 30 + let t2 = C::EQUATION_A * t2; // 31 + let t4 = t4 + t2; // 32 + let t0 = t1 * t4; // 33 + let y3 = y3 + t0; // 34 + let t0 = t5 * t4; // 35 + let x3 = t3 * x3; // 36 + let x3 = x3 - t0; // 37 + let t0 = t3 * t1; // 38 + let z3 = t5 * z3; // 39 + let z3 = z3 + t0; // 40 + + ProjectivePoint { + x: x3, + y: y3, + z: z3, + } + } + + /// Implements complete mixed addition for curves with any `a` + /// + /// Implements the complete mixed addition formula from [Renes-Costello-Batina 2015] + /// (Algorithm 2). The comments after each line indicate which algorithm + /// steps are being performed. + /// + /// [Renes-Costello-Batina 2015]: https://eprint.iacr.org/2015/1060 + fn add_mixed(lhs: &ProjectivePoint, rhs: &AffinePoint) -> ProjectivePoint { + let b3 = C::EQUATION_B * C::FieldElement::from(3); + + let t0 = lhs.x * rhs.x; // 1 + let t1 = lhs.y * rhs.y; // 2 + let t3 = rhs.x + rhs.y; // 3 + let t4 = lhs.x + lhs.y; // 4 + let t3 = t3 * t4; // 5 + let t4 = t0 + t1; // 6 + let t3 = t3 - t4; // 7 + let t4 = rhs.x * lhs.z; // 8 + let t4 = t4 + lhs.x; // 9 + let t5 = rhs.y * lhs.z; // 10 + let t5 = t5 + lhs.y; // 11 + let z3 = C::EQUATION_A * t4; // 12 + let x3 = b3 * lhs.z; // 13 + let z3 = x3 + z3; // 14 + let x3 = t1 - z3; // 15 + let z3 = t1 + z3; // 16 + let y3 = x3 * z3; // 17 + let t1 = t0 + t0; // 18 + let t1 = t1 + t0; // 19 + let t2 = C::EQUATION_A * lhs.z; // 20 + let t4 = b3 * t4; // 21 + let t1 = t1 + t2; // 22 + let t2 = t0 - t2; // 23 + let t2 = C::EQUATION_A * t2; // 24 + let t4 = t4 + t2; // 25 + let t0 = t1 * t4; // 26 + let y3 = y3 + t0; // 27 + let t0 = t5 * t4; // 28 + let x3 = t3 * x3; // 29 + let x3 = x3 - t0; // 30 + let t0 = t3 * t1; // 31 + let z3 = t5 * z3; // 32 + let z3 = z3 + t0; // 33 + + let mut ret = ProjectivePoint { + x: x3, + y: y3, + z: z3, + }; + ret.conditional_assign(lhs, rhs.is_identity()); + ret + } + + /// Implements point doubling for curves with any `a` + /// + /// Implements the exception-free point doubling formula from [Renes-Costello-Batina 2015] + /// (Algorithm 3). The comments after each line indicate which algorithm + /// steps are being performed. + /// + /// [Renes-Costello-Batina 2015]: https://eprint.iacr.org/2015/1060 + fn double(point: &ProjectivePoint) -> ProjectivePoint { + let b3 = C::EQUATION_B * C::FieldElement::from(3); + + let t0 = point.x * point.x; // 1 + let t1 = point.y * point.y; // 2 + let t2 = point.z * point.z; // 3 + let t3 = point.x * point.y; // 4 + let t3 = t3 + t3; // 5 + let z3 = point.x * point.z; // 6 + let z3 = z3 + z3; // 7 + let x3 = C::EQUATION_A * z3; // 8 + let y3 = b3 * t2; // 9 + let y3 = x3 + y3; // 10 + let x3 = t1 - y3; // 11 + let y3 = t1 + y3; // 12 + let y3 = x3 * y3; // 13 + let x3 = t3 * x3; // 14 + let z3 = b3 * z3; // 15 + let t2 = C::EQUATION_A * t2; // 16 + let t3 = t0 - t2; // 17 + let t3 = C::EQUATION_A * t3; // 18 + let t3 = t3 + z3; // 19 + let z3 = t0 + t0; // 20 + let t0 = z3 + t0; // 21 + let t0 = t0 + t2; // 22 + let t0 = t0 * t3; // 23 + let y3 = y3 + t0; // 24 + let t2 = point.y * point.z; // 25 + let t2 = t2 + t2; // 26 + let t0 = t2 * t3; // 27 + let x3 = x3 - t0; // 28 + let z3 = t2 * t1; // 29 + let z3 = z3 + z3; // 30 + let z3 = z3 + z3; // 31 + + ProjectivePoint { + x: x3, + y: y3, + z: z3, + } + } +} + +/// The 𝒂-coefficient of the short Weierstrass equation is -3. +pub struct EquationAIsMinusThree {} + +impl PointArithmetic for EquationAIsMinusThree { + /// Implements complete addition for curves with `a = -3` + /// + /// Implements the complete addition formula from [Renes-Costello-Batina 2015] + /// (Algorithm 4). The comments after each line indicate which algorithm steps + /// are being performed. + /// + /// [Renes-Costello-Batina 2015]: https://eprint.iacr.org/2015/1060 + fn add(lhs: &ProjectivePoint, rhs: &ProjectivePoint) -> ProjectivePoint { + debug_assert_eq!( + C::EQUATION_A, + -C::FieldElement::from(3), + "this implementation is only valid for C::EQUATION_A = -3" + ); + + let xx = lhs.x * rhs.x; // 1 + let yy = lhs.y * rhs.y; // 2 + let zz = lhs.z * rhs.z; // 3 + let xy_pairs = ((lhs.x + lhs.y) * (rhs.x + rhs.y)) - (xx + yy); // 4, 5, 6, 7, 8 + let yz_pairs = ((lhs.y + lhs.z) * (rhs.y + rhs.z)) - (yy + zz); // 9, 10, 11, 12, 13 + let xz_pairs = ((lhs.x + lhs.z) * (rhs.x + rhs.z)) - (xx + zz); // 14, 15, 16, 17, 18 + + let bzz_part = xz_pairs - (C::EQUATION_B * zz); // 19, 20 + let bzz3_part = bzz_part.double() + bzz_part; // 21, 22 + let yy_m_bzz3 = yy - bzz3_part; // 23 + let yy_p_bzz3 = yy + bzz3_part; // 24 + + let zz3 = zz.double() + zz; // 26, 27 + let bxz_part = (C::EQUATION_B * xz_pairs) - (zz3 + xx); // 25, 28, 29 + let bxz3_part = bxz_part.double() + bxz_part; // 30, 31 + let xx3_m_zz3 = xx.double() + xx - zz3; // 32, 33, 34 + + ProjectivePoint { + x: (yy_p_bzz3 * xy_pairs) - (yz_pairs * bxz3_part), // 35, 39, 40 + y: (yy_p_bzz3 * yy_m_bzz3) + (xx3_m_zz3 * bxz3_part), // 36, 37, 38 + z: (yy_m_bzz3 * yz_pairs) + (xy_pairs * xx3_m_zz3), // 41, 42, 43 + } + } + + /// Implements complete mixed addition for curves with `a = -3` + /// + /// Implements the complete mixed addition formula from [Renes-Costello-Batina 2015] + /// (Algorithm 5). The comments after each line indicate which algorithm + /// steps are being performed. + /// + /// [Renes-Costello-Batina 2015]: https://eprint.iacr.org/2015/1060 + fn add_mixed(lhs: &ProjectivePoint, rhs: &AffinePoint) -> ProjectivePoint { + debug_assert_eq!( + C::EQUATION_A, + -C::FieldElement::from(3), + "this implementation is only valid for C::EQUATION_A = -3" + ); + + let xx = lhs.x * rhs.x; // 1 + let yy = lhs.y * rhs.y; // 2 + let xy_pairs = ((lhs.x + lhs.y) * (rhs.x + rhs.y)) - (xx + yy); // 3, 4, 5, 6, 7 + let yz_pairs = (rhs.y * lhs.z) + lhs.y; // 8, 9 (t4) + let xz_pairs = (rhs.x * lhs.z) + lhs.x; // 10, 11 (y3) + + let bz_part = xz_pairs - (C::EQUATION_B * lhs.z); // 12, 13 + let bz3_part = bz_part.double() + bz_part; // 14, 15 + let yy_m_bzz3 = yy - bz3_part; // 16 + let yy_p_bzz3 = yy + bz3_part; // 17 + + let z3 = lhs.z.double() + lhs.z; // 19, 20 + let bxz_part = (C::EQUATION_B * xz_pairs) - (z3 + xx); // 18, 21, 22 + let bxz3_part = bxz_part.double() + bxz_part; // 23, 24 + let xx3_m_zz3 = xx.double() + xx - z3; // 25, 26, 27 + + let mut ret = ProjectivePoint { + x: (yy_p_bzz3 * xy_pairs) - (yz_pairs * bxz3_part), // 28, 32, 33 + y: (yy_p_bzz3 * yy_m_bzz3) + (xx3_m_zz3 * bxz3_part), // 29, 30, 31 + z: (yy_m_bzz3 * yz_pairs) + (xy_pairs * xx3_m_zz3), // 34, 35, 36 + }; + ret.conditional_assign(lhs, rhs.is_identity()); + ret + } + + /// Implements point doubling for curves with `a = -3` + /// + /// Implements the exception-free point doubling formula from [Renes-Costello-Batina 2015] + /// (Algorithm 6). The comments after each line indicate which algorithm + /// steps are being performed. + /// + /// [Renes-Costello-Batina 2015]: https://eprint.iacr.org/2015/1060 + fn double(point: &ProjectivePoint) -> ProjectivePoint { + debug_assert_eq!( + C::EQUATION_A, + -C::FieldElement::from(3), + "this implementation is only valid for C::EQUATION_A = -3" + ); + + let xx = point.x.square(); // 1 + let yy = point.y.square(); // 2 + let zz = point.z.square(); // 3 + let xy2 = (point.x * point.y).double(); // 4, 5 + let xz2 = (point.x * point.z).double(); // 6, 7 + + let bzz_part = (C::EQUATION_B * zz) - xz2; // 8, 9 + let bzz3_part = bzz_part.double() + bzz_part; // 10, 11 + let yy_m_bzz3 = yy - bzz3_part; // 12 + let yy_p_bzz3 = yy + bzz3_part; // 13 + let y_frag = yy_p_bzz3 * yy_m_bzz3; // 14 + let x_frag = yy_m_bzz3 * xy2; // 15 + + let zz3 = zz.double() + zz; // 16, 17 + let bxz2_part = (C::EQUATION_B * xz2) - (zz3 + xx); // 18, 19, 20 + let bxz6_part = bxz2_part.double() + bxz2_part; // 21, 22 + let xx3_m_zz3 = xx.double() + xx - zz3; // 23, 24, 25 + + let y = y_frag + (xx3_m_zz3 * bxz6_part); // 26, 27 + let yz2 = (point.y * point.z).double(); // 28, 29 + let x = x_frag - (bxz6_part * yz2); // 30, 31 + let z = (yz2 * yy).double().double(); // 32, 33, 34 + + ProjectivePoint { x, y, z } + } +} diff --git a/vendor/primeorder/src/projective.rs b/vendor/primeorder/src/projective.rs new file mode 100644 index 000000000..5549543fc --- /dev/null +++ b/vendor/primeorder/src/projective.rs @@ -0,0 +1,696 @@ +//! Projective curve points. + +#![allow(clippy::needless_range_loop, clippy::op_ref)] + +use crate::{point_arithmetic::PointArithmetic, AffinePoint, Field, PrimeCurveParams}; +use core::{ + borrow::Borrow, + iter::Sum, + ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign}, +}; +use elliptic_curve::{ + bigint::{ArrayEncoding, Integer}, + generic_array::ArrayLength, + group::{ + self, + cofactor::CofactorGroup, + prime::{PrimeCurve, PrimeGroup}, + Group, GroupEncoding, + }, + ops::{LinearCombination, MulByGenerator}, + point::Double, + rand_core::RngCore, + sec1::{ + CompressedPoint, EncodedPoint, FromEncodedPoint, ModulusSize, ToEncodedPoint, + UncompressedPointSize, + }, + subtle::{Choice, ConditionallySelectable, ConstantTimeEq, CtOption}, + zeroize::DefaultIsZeroes, + Error, FieldBytes, FieldBytesSize, PublicKey, Result, Scalar, +}; + +/// Point on a Weierstrass curve in projective coordinates. +#[derive(Clone, Copy, Debug)] +pub struct ProjectivePoint { + pub(crate) x: C::FieldElement, + pub(crate) y: C::FieldElement, + pub(crate) z: C::FieldElement, +} + +impl ProjectivePoint +where + C: PrimeCurveParams, +{ + /// Additive identity of the group a.k.a. the point at infinity. + pub const IDENTITY: Self = Self { + x: C::FieldElement::ZERO, + y: C::FieldElement::ONE, + z: C::FieldElement::ZERO, + }; + + /// Base point of the curve. + pub const GENERATOR: Self = Self { + x: C::GENERATOR.0, + y: C::GENERATOR.1, + z: C::FieldElement::ONE, + }; + + /// Returns the affine representation of this point, or `None` if it is the identity. + pub fn to_affine(&self) -> AffinePoint { + self.z + .invert() + .map(|zinv| AffinePoint { + x: self.x * &zinv, + y: self.y * &zinv, + infinity: 0, + }) + .unwrap_or(AffinePoint::IDENTITY) + } + + /// Returns `-self`. + pub fn neg(&self) -> Self { + Self { + x: self.x, + y: -self.y, + z: self.z, + } + } + + /// Returns `self + other`. + pub fn add(&self, other: &Self) -> Self { + C::PointArithmetic::add(self, other) + } + + /// Returns `self + other`. + fn add_mixed(&self, other: &AffinePoint) -> Self { + C::PointArithmetic::add_mixed(self, other) + } + + /// Returns `self - other`. + pub fn sub(&self, other: &Self) -> Self { + self.add(&other.neg()) + } + + /// Returns `self - other`. + fn sub_mixed(&self, other: &AffinePoint) -> Self { + self.add_mixed(&other.neg()) + } + + /// Returns `[k] self`. + fn mul(&self, k: &Scalar) -> Self + where + Self: Double, + { + let k = Into::::into(*k).to_le_byte_array(); + + let mut pc = [Self::default(); 16]; + pc[0] = Self::IDENTITY; + pc[1] = *self; + + for i in 2..16 { + pc[i] = if i % 2 == 0 { + Double::double(&pc[i / 2]) + } else { + pc[i - 1].add(self) + }; + } + + let mut q = Self::IDENTITY; + let mut pos = C::Uint::BITS - 4; + + loop { + let slot = (k[pos >> 3] >> (pos & 7)) & 0xf; + + let mut t = ProjectivePoint::IDENTITY; + + for i in 1..16 { + t.conditional_assign( + &pc[i], + Choice::from(((slot as usize ^ i).wrapping_sub(1) >> 8) as u8 & 1), + ); + } + + q = q.add(&t); + + if pos == 0 { + break; + } + + q = Double::double(&Double::double(&Double::double(&Double::double(&q)))); + pos -= 4; + } + + q + } +} + +impl CofactorGroup for ProjectivePoint +where + Self: Double, + C: PrimeCurveParams, + FieldBytes: Copy, + FieldBytesSize: ModulusSize, + CompressedPoint: Copy, + as ArrayLength>::ArrayType: Copy, +{ + type Subgroup = Self; + + fn clear_cofactor(&self) -> Self::Subgroup { + *self + } + + fn into_subgroup(self) -> CtOption { + CtOption::new(self, 1.into()) + } + + fn is_torsion_free(&self) -> Choice { + 1.into() + } +} + +impl ConditionallySelectable for ProjectivePoint +where + C: PrimeCurveParams, +{ + fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self { + Self { + x: C::FieldElement::conditional_select(&a.x, &b.x, choice), + y: C::FieldElement::conditional_select(&a.y, &b.y, choice), + z: C::FieldElement::conditional_select(&a.z, &b.z, choice), + } + } +} + +impl ConstantTimeEq for ProjectivePoint +where + C: PrimeCurveParams, +{ + fn ct_eq(&self, other: &Self) -> Choice { + self.to_affine().ct_eq(&other.to_affine()) + } +} + +impl Default for ProjectivePoint +where + C: PrimeCurveParams, +{ + fn default() -> Self { + Self::IDENTITY + } +} + +impl DefaultIsZeroes for ProjectivePoint where C: PrimeCurveParams {} + +impl Double for ProjectivePoint { + fn double(&self) -> Self { + C::PointArithmetic::double(self) + } +} + +impl Eq for ProjectivePoint where C: PrimeCurveParams {} + +impl From> for ProjectivePoint +where + C: PrimeCurveParams, +{ + fn from(p: AffinePoint) -> Self { + let projective = ProjectivePoint { + x: p.x, + y: p.y, + z: C::FieldElement::ONE, + }; + Self::conditional_select(&projective, &Self::IDENTITY, p.is_identity()) + } +} + +impl From<&AffinePoint> for ProjectivePoint +where + C: PrimeCurveParams, +{ + fn from(p: &AffinePoint) -> Self { + Self::from(*p) + } +} + +impl From> for ProjectivePoint +where + C: PrimeCurveParams, +{ + fn from(public_key: PublicKey) -> ProjectivePoint { + AffinePoint::from(public_key).into() + } +} + +impl From<&PublicKey> for ProjectivePoint +where + C: PrimeCurveParams, +{ + fn from(public_key: &PublicKey) -> ProjectivePoint { + AffinePoint::::from(public_key).into() + } +} + +impl FromEncodedPoint for ProjectivePoint +where + C: PrimeCurveParams, + FieldBytes: Copy, + FieldBytesSize: ModulusSize, + CompressedPoint: Copy, +{ + fn from_encoded_point(p: &EncodedPoint) -> CtOption { + AffinePoint::::from_encoded_point(p).map(Self::from) + } +} + +impl Group for ProjectivePoint +where + Self: Double, + C: PrimeCurveParams, +{ + type Scalar = Scalar; + + fn random(mut rng: impl RngCore) -> Self { + Self::GENERATOR * as Field>::random(&mut rng) + } + + fn identity() -> Self { + Self::IDENTITY + } + + fn generator() -> Self { + Self::GENERATOR + } + + fn is_identity(&self) -> Choice { + self.ct_eq(&Self::IDENTITY) + } + + #[must_use] + fn double(&self) -> Self { + Double::double(self) + } +} + +impl GroupEncoding for ProjectivePoint +where + C: PrimeCurveParams, + FieldBytes: Copy, + FieldBytesSize: ModulusSize, + CompressedPoint: Copy, + as ArrayLength>::ArrayType: Copy, +{ + type Repr = CompressedPoint; + + fn from_bytes(bytes: &Self::Repr) -> CtOption { + as GroupEncoding>::from_bytes(bytes).map(Into::into) + } + + fn from_bytes_unchecked(bytes: &Self::Repr) -> CtOption { + // No unchecked conversion possible for compressed points + Self::from_bytes(bytes) + } + + fn to_bytes(&self) -> Self::Repr { + self.to_affine().to_bytes() + } +} + +impl group::Curve for ProjectivePoint +where + Self: Double, + C: PrimeCurveParams, +{ + type AffineRepr = AffinePoint; + + fn to_affine(&self) -> AffinePoint { + ProjectivePoint::to_affine(self) + } +} + +impl LinearCombination for ProjectivePoint +where + Self: Double, + C: PrimeCurveParams, +{ +} + +impl MulByGenerator for ProjectivePoint +where + Self: Double, + C: PrimeCurveParams, +{ + fn mul_by_generator(scalar: &Self::Scalar) -> Self { + // TODO(tarcieri): precomputed basepoint tables + Self::generator() * scalar + } +} + +impl PrimeGroup for ProjectivePoint +where + Self: Double, + C: PrimeCurveParams, + FieldBytes: Copy, + FieldBytesSize: ModulusSize, + CompressedPoint: Copy, + as ArrayLength>::ArrayType: Copy, +{ +} + +impl PrimeCurve for ProjectivePoint +where + Self: Double, + C: PrimeCurveParams, + FieldBytes: Copy, + FieldBytesSize: ModulusSize, + CompressedPoint: Copy, + as ArrayLength>::ArrayType: Copy, +{ + type Affine = AffinePoint; +} + +impl PartialEq for ProjectivePoint +where + C: PrimeCurveParams, +{ + fn eq(&self, other: &Self) -> bool { + self.ct_eq(other).into() + } +} + +impl ToEncodedPoint for ProjectivePoint +where + C: PrimeCurveParams, + FieldBytesSize: ModulusSize, + CompressedPoint: Copy, + as ArrayLength>::ArrayType: Copy, +{ + fn to_encoded_point(&self, compress: bool) -> EncodedPoint { + self.to_affine().to_encoded_point(compress) + } +} + +impl TryFrom> for PublicKey +where + C: PrimeCurveParams, +{ + type Error = Error; + + fn try_from(point: ProjectivePoint) -> Result> { + AffinePoint::::from(point).try_into() + } +} + +impl TryFrom<&ProjectivePoint> for PublicKey +where + C: PrimeCurveParams, +{ + type Error = Error; + + fn try_from(point: &ProjectivePoint) -> Result> { + AffinePoint::::from(point).try_into() + } +} + +// +// Arithmetic trait impls +// + +impl Add> for ProjectivePoint +where + C: PrimeCurveParams, +{ + type Output = ProjectivePoint; + + fn add(self, other: ProjectivePoint) -> ProjectivePoint { + ProjectivePoint::add(&self, &other) + } +} + +impl Add<&ProjectivePoint> for &ProjectivePoint +where + C: PrimeCurveParams, +{ + type Output = ProjectivePoint; + + fn add(self, other: &ProjectivePoint) -> ProjectivePoint { + ProjectivePoint::add(self, other) + } +} + +impl Add<&ProjectivePoint> for ProjectivePoint +where + C: PrimeCurveParams, +{ + type Output = ProjectivePoint; + + fn add(self, other: &ProjectivePoint) -> ProjectivePoint { + ProjectivePoint::add(&self, other) + } +} + +impl AddAssign> for ProjectivePoint +where + C: PrimeCurveParams, +{ + fn add_assign(&mut self, rhs: ProjectivePoint) { + *self = ProjectivePoint::add(self, &rhs); + } +} + +impl AddAssign<&ProjectivePoint> for ProjectivePoint +where + C: PrimeCurveParams, +{ + fn add_assign(&mut self, rhs: &ProjectivePoint) { + *self = ProjectivePoint::add(self, rhs); + } +} + +impl Add> for ProjectivePoint +where + C: PrimeCurveParams, +{ + type Output = ProjectivePoint; + + fn add(self, other: AffinePoint) -> ProjectivePoint { + ProjectivePoint::add_mixed(&self, &other) + } +} + +impl Add<&AffinePoint> for &ProjectivePoint +where + C: PrimeCurveParams, +{ + type Output = ProjectivePoint; + + fn add(self, other: &AffinePoint) -> ProjectivePoint { + ProjectivePoint::add_mixed(self, other) + } +} + +impl Add<&AffinePoint> for ProjectivePoint +where + C: PrimeCurveParams, +{ + type Output = ProjectivePoint; + + fn add(self, other: &AffinePoint) -> ProjectivePoint { + ProjectivePoint::add_mixed(&self, other) + } +} + +impl AddAssign> for ProjectivePoint +where + C: PrimeCurveParams, +{ + fn add_assign(&mut self, rhs: AffinePoint) { + *self = ProjectivePoint::add_mixed(self, &rhs); + } +} + +impl AddAssign<&AffinePoint> for ProjectivePoint +where + C: PrimeCurveParams, +{ + fn add_assign(&mut self, rhs: &AffinePoint) { + *self = ProjectivePoint::add_mixed(self, rhs); + } +} + +impl Sum for ProjectivePoint +where + C: PrimeCurveParams, +{ + fn sum>(iter: I) -> Self { + iter.fold(ProjectivePoint::IDENTITY, |a, b| a + b) + } +} + +impl<'a, C> Sum<&'a ProjectivePoint> for ProjectivePoint +where + C: PrimeCurveParams, +{ + fn sum>>(iter: I) -> Self { + iter.cloned().sum() + } +} + +impl Sub> for ProjectivePoint +where + C: PrimeCurveParams, +{ + type Output = ProjectivePoint; + + fn sub(self, other: ProjectivePoint) -> ProjectivePoint { + ProjectivePoint::sub(&self, &other) + } +} + +impl Sub<&ProjectivePoint> for &ProjectivePoint +where + C: PrimeCurveParams, +{ + type Output = ProjectivePoint; + + fn sub(self, other: &ProjectivePoint) -> ProjectivePoint { + ProjectivePoint::sub(self, other) + } +} + +impl Sub<&ProjectivePoint> for ProjectivePoint +where + C: PrimeCurveParams, +{ + type Output = ProjectivePoint; + + fn sub(self, other: &ProjectivePoint) -> ProjectivePoint { + ProjectivePoint::sub(&self, other) + } +} + +impl SubAssign> for ProjectivePoint +where + C: PrimeCurveParams, +{ + fn sub_assign(&mut self, rhs: ProjectivePoint) { + *self = ProjectivePoint::sub(self, &rhs); + } +} + +impl SubAssign<&ProjectivePoint> for ProjectivePoint +where + C: PrimeCurveParams, +{ + fn sub_assign(&mut self, rhs: &ProjectivePoint) { + *self = ProjectivePoint::sub(self, rhs); + } +} + +impl Sub> for ProjectivePoint +where + C: PrimeCurveParams, +{ + type Output = ProjectivePoint; + + fn sub(self, other: AffinePoint) -> ProjectivePoint { + ProjectivePoint::sub_mixed(&self, &other) + } +} + +impl Sub<&AffinePoint> for &ProjectivePoint +where + C: PrimeCurveParams, +{ + type Output = ProjectivePoint; + + fn sub(self, other: &AffinePoint) -> ProjectivePoint { + ProjectivePoint::sub_mixed(self, other) + } +} + +impl Sub<&AffinePoint> for ProjectivePoint +where + C: PrimeCurveParams, +{ + type Output = ProjectivePoint; + + fn sub(self, other: &AffinePoint) -> ProjectivePoint { + ProjectivePoint::sub_mixed(&self, other) + } +} + +impl SubAssign> for ProjectivePoint +where + C: PrimeCurveParams, +{ + fn sub_assign(&mut self, rhs: AffinePoint) { + *self = ProjectivePoint::sub_mixed(self, &rhs); + } +} + +impl SubAssign<&AffinePoint> for ProjectivePoint +where + C: PrimeCurveParams, +{ + fn sub_assign(&mut self, rhs: &AffinePoint) { + *self = ProjectivePoint::sub_mixed(self, rhs); + } +} + +impl Mul for ProjectivePoint +where + Self: Double, + C: PrimeCurveParams, + S: Borrow>, +{ + type Output = Self; + + fn mul(self, scalar: S) -> Self { + ProjectivePoint::mul(&self, scalar.borrow()) + } +} + +impl Mul<&Scalar> for &ProjectivePoint +where + C: PrimeCurveParams, + ProjectivePoint: Double, +{ + type Output = ProjectivePoint; + + fn mul(self, scalar: &Scalar) -> ProjectivePoint { + ProjectivePoint::mul(self, scalar) + } +} + +impl MulAssign for ProjectivePoint +where + Self: Double, + C: PrimeCurveParams, + S: Borrow>, +{ + fn mul_assign(&mut self, scalar: S) { + *self = ProjectivePoint::mul(self, scalar.borrow()); + } +} + +impl Neg for ProjectivePoint +where + C: PrimeCurveParams, +{ + type Output = ProjectivePoint; + + fn neg(self) -> ProjectivePoint { + ProjectivePoint::neg(&self) + } +} + +impl<'a, C> Neg for &'a ProjectivePoint +where + C: PrimeCurveParams, +{ + type Output = ProjectivePoint; + + fn neg(self) -> ProjectivePoint { + ProjectivePoint::neg(self) + } +} -- cgit v1.2.3