| // Copyright 2016 Brian Smith. |
| // |
| // Permission to use, copy, modify, and/or distribute this software for any |
| // purpose with or without fee is hereby granted, provided that the above |
| // copyright notice and this permission notice appear in all copies. |
| // |
| // THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHORS DISCLAIM ALL WARRANTIES |
| // WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF |
| // MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY |
| // SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES |
| // WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION |
| // OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN |
| // CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. |
| |
| //! Elliptic curve operations on P-256 & P-384. |
| |
| use arithmetic::montgomery::*; |
| use {der, ec, error, pkcs8}; |
| use self::ops::*; |
| use untrusted; |
| |
| |
| // NIST SP 800-56A Step 3: "If q is an odd prime p, verify that |
| // yQ**2 = xQ**3 + axQ + b in GF(p), where the arithmetic is performed modulo |
| // p." |
| // |
| // That is, verify that (x, y) is on the curve, which is true iif: |
| // |
| // y**2 == x**3 + a*x + b (mod q) |
| // |
| // Or, equivalently, but more efficiently: |
| // |
| // y**2 == (x**2 + a)*x + b (mod q) |
| // |
| fn verify_affine_point_is_on_the_curve( |
| ops: &CommonOps, (x, y): (&Elem<R>, &Elem<R>)) |
| -> Result<(), error::Unspecified> { |
| verify_affine_point_is_on_the_curve_scaled(ops, (x, y), &ops.a, &ops.b) |
| } |
| |
| |
| // Use `verify_affine_point_is_on_the_curve` instead of this function whenever |
| // the affine coordinates are available or will become available. This function |
| // should only be used then the affine coordinates are never calculated. See |
| // the notes for `verify_affine_point_is_on_the_curve_scaled`. |
| // |
| // The value `z**2` is returned on success because it is useful for ECDSA |
| // verification. |
| // |
| // This function also verifies that the point is not at infinity. |
| fn verify_jacobian_point_is_on_the_curve(ops: &CommonOps, p: &Point) |
| -> Result<Elem<R>, error::Unspecified> { |
| let z = ops.point_z(p); |
| |
| // Verify that the point is not at infinity. |
| ops.elem_verify_is_not_zero(&z)?; |
| |
| let x = ops.point_x(p); |
| let y = ops.point_y(p); |
| |
| // We are given Jacobian coordinates (x, y, z). So, we have: |
| // |
| // (x/z**2, y/z**3) == (x', y'), |
| // |
| // where (x', y') are the affine coordinates. The curve equation is: |
| // |
| // y'**2 == x'**3 + a*x' + b == (x'**2 + a)*x' + b |
| // |
| // Substituting our Jacobian coordinates, we get: |
| // |
| // / y \**2 / / x \**2 \ / x \ |
| // | ---- | == | | ---- | + a | * | ---- | + b |
| // \ z**3 / \ \ z**2 / / \ z**2 / |
| // |
| // Simplify: |
| // |
| // y**2 / x**2 \ x |
| // ---- == | ---- + a | * ---- + b |
| // z**6 \ z**4 / z**2 |
| // |
| // Multiply both sides by z**6: |
| // |
| // z**6 / x**2 \ z**6 |
| // ---- * y**2 == | ---- + a | * ---- * x + (z**6) * b |
| // z**6 \ z**4 / z**2 |
| // |
| // Simplify: |
| // |
| // / x**2 \ |
| // y**2 == | ---- + a | * z**4 * x + (z**6) * b |
| // \ z**4 / |
| // |
| // Distribute z**4: |
| // |
| // / z**4 \ |
| // y**2 == | ---- * x**2 + z**4 * a | * x + (z**6) * b |
| // \ z**4 / |
| // |
| // Simplify: |
| // |
| // y**2 == (x**2 + z**4 * a) * x + (z**6) * b |
| // |
| let z2 = ops.elem_squared(&z); |
| let z4 = ops.elem_squared(&z2); |
| let z4_a = ops.elem_product(&z4, &ops.a); |
| let z6 = ops.elem_product(&z4, &z2); |
| let z6_b = ops.elem_product(&z6, &ops.b); |
| verify_affine_point_is_on_the_curve_scaled(ops, (&x, &y), &z4_a, &z6_b)?; |
| Ok(z2) |
| } |
| |
| |
| // Handles the common logic of point-is-on-the-curve checks for both affine and |
| // Jacobian cases. |
| // |
| // When doing the check that the point is on the curve after a computation, |
| // to avoid fault attacks or mitigate potential bugs, it is better for security |
| // to use `verify_affine_point_is_on_the_curve` on the affine coordinates, |
| // because it provides some protection against faults that occur in the |
| // computation of the inverse of `z`. See the paper and presentation "Fault |
| // Attacks on Projective-to-Affine Coordinates Conversion" by Diana Maimuţ, |
| // Cédric Murdica, David Naccache, Mehdi Tibouchi. That presentation concluded |
| // simply "Check the validity of the result after conversion to affine |
| // coordinates." (It seems like a good idea to verify that |
| // z_inv * z == 1 mod q too). |
| // |
| // In the case of affine coordinates (x, y), `a_scaled` and `b_scaled` are |
| // `a` and `b`, respectively. In the case of Jacobian coordinates (x, y, z), |
| // the computation and comparison is the same, except `a_scaled` and `b_scaled` |
| // are (z**4 * a) and (z**6 * b), respectively. Thus, performance is another |
| // reason to prefer doing the check on the affine coordinates, as Jacobian |
| // computation requires 3 extra multiplications and 2 extra squarings. |
| // |
| // An example of a fault attack that isn't mitigated by a point-on-the-curve |
| // check after multiplication is given in "Sign Change Fault Attacks On |
| // Elliptic Curve Cryptosystems" by Johannes Blömer, Martin Otto, and |
| // Jean-Pierre Seifert. |
| fn verify_affine_point_is_on_the_curve_scaled( |
| ops: &CommonOps, (x, y): (&Elem<R>, &Elem<R>), a_scaled: &Elem<R>, |
| b_scaled: &Elem<R>) -> Result<(), error::Unspecified> { |
| let lhs = ops.elem_squared(y); |
| |
| let mut rhs = ops.elem_squared(x); |
| ops.elem_add(&mut rhs, a_scaled); |
| ops.elem_mul(&mut rhs, x); |
| ops.elem_add(&mut rhs, b_scaled); |
| |
| if !ops.elems_are_equal(&lhs, &rhs) { |
| return Err(error::Unspecified); |
| } |
| |
| Ok(()) |
| } |
| |
| pub fn key_pair_from_pkcs8(curve: &ec::Curve, template: &pkcs8::Template, |
| input: untrusted::Input) |
| -> Result<ec::KeyPair, error::Unspecified> { |
| let (ec_private_key, _) = |
| pkcs8::unwrap_key(template, pkcs8::Version::V1Only, input)?; |
| let (private_key, public_key) = ec_private_key.read_all( |
| error::Unspecified, |input| { |
| // https://tools.ietf.org/html/rfc5915#section-3 |
| der::nested(input, der::Tag::Sequence, error::Unspecified, |input| { |
| let version = der::small_nonnegative_integer(input)?; |
| if version != 1 { |
| return Err(error::Unspecified); |
| } |
| |
| let private_key = |
| der::expect_tag_and_get_value(input, der::Tag::OctetString)?; |
| |
| // [0] parameters (optional). |
| if input.peek(der::Tag::ContextSpecificConstructed0 as u8) { |
| let actual_alg_id = der::expect_tag_and_get_value( |
| input, der::Tag::ContextSpecificConstructed0)?; |
| if actual_alg_id != template.curve_oid() { |
| return Err(error::Unspecified); |
| } |
| } |
| |
| // [1] publicKey. The RFC says it is optional, but we require it |
| // to be present. |
| let public_key = der::nested( |
| input, der::Tag::ContextSpecificConstructed1, |
| error::Unspecified, der::bit_string_with_no_unused_bits)?; |
| |
| Ok((private_key, public_key)) |
| }) |
| })?; |
| key_pair_from_bytes(curve, private_key, public_key) |
| } |
| |
| pub fn key_pair_from_bytes(curve: &ec::Curve, |
| private_key_bytes: untrusted::Input, |
| public_key_bytes: untrusted::Input) |
| -> Result<ec::KeyPair, error::Unspecified> { |
| let private_key = ec::PrivateKey::from_bytes(curve, private_key_bytes)?; |
| |
| let mut public_key_check = [0; ec::PUBLIC_KEY_MAX_LEN]; |
| { // Borrow `public_key_check`. |
| let public_key_check = &mut public_key_check[..curve.public_key_len]; |
| (curve.public_from_private)(public_key_check, &private_key)?; |
| if public_key_bytes != &*public_key_check { |
| return Err(error::Unspecified); |
| } |
| } |
| |
| Ok(ec::KeyPair { |
| private_key: private_key, |
| public_key: public_key_check, |
| }) |
| } |
| |
| pub mod curve; |
| pub mod ecdsa; |
| pub mod ecdh; |
| |
| #[macro_use] |
| #[path = "ops/ops.rs"] |
| mod ops; |
| |
| mod private_key; |
| mod public_key; |
