This PR implements "lazy reduction" arithmetic for SECP256k1, based on libsecp256k1.

(Disclaimer: this is my first non-trivial piece of Rust code. Don't hesitate to point out my mistakes).

• adds 5x52bit and 10x26bit arithmetic for the internal field (the old Montgomery one is preserved)
• adds 4x64bit and 8x32bit arithmetic for scalars
• adds more tests for fields and scalars (using num-bigint as a reference)
• adds a fixed window point-scalar multiplication

More advanced multiplication routines (wNAF, endomorphism, batch multiplication) will not be included in this PR — it has too much stuff already. Even the windowed multiplication already gives a good performance boost. As compared to the baseline performance, I currently see an almost 3x speedup (300us vs 106us per mul).

The old Montgomery field can be enabled with field-montgomery, 32-bit fields & scalars on a 64-bit target can be enabled with force-32-bit.

I'd like to cut releases of the following crates relatively soon (next few days / week):

• elliptic-curve v0.5.0
• ecdsa v0.7.0
• k256 v0.4.0
• p256 v0.4.0
• p384 v0.3.0

These will be the first releases supporting an integrated ECDSA implementation as well as initial (and rather rudimentary) support for implementing algorithms generically over elliptic curve groups.

If there's anything else you'd like to get into these releases, let me know, otherwise I plan on doing it soon.

When I say that, I'm also looking for small items rather than more significant changes. There's plenty of bigger issues to address (e.g. eliminating fallible APIs via eliminating the invalid representations that cause them in PublicKey/SecretKey) but I'd rather not make any bigger items release blockers at this point and we can continue making large and breaking changes in the next release.

cc @str4d @tuxxy @fjarri @nickray

The goal of this PR is to optimize a commonly used operation (x * k + y * l) where x and y are curve points, and k and l are scalars. It is currently used in verify.rs and recoverable.rs.

On my machine it speeds up ECDSA verification from 176us to 145us (and the newly added benchmark shows speed-up from 157us to 124us for linear combination alone).

Currently there PR contains a lincomb_generic() that takes arrays, and it has two aliases: mul() (internal, used in operator traits) and lincomb() (public, for two-point linear combinations).

This is a "spitballing" PR, intended primarily for illustration of required API and discussion.

There are two things I'm missing from the current Scalar API:

• an ability to generate random NonZeroScalars (without unwrapping)
• an ability to generate a Scalar/NonZeroScalar from a digest safely according to hash-to-curve standard

The latter needs the scalar to be reduced from L = ceil((ceil(log2(p)) + k) / 8) bytes (Section 5.3), where p is the order, and k is the security parameter. For k = 256 this gives 64 bytes, for k = 128 it's 48 bytes. I went with 64 for simplicity.

The public methods added to Scalar:

• pub fn random_nonzero(rng: impl RngCore) -> NonZeroScalar
• pub fn from_digest_safe<D>(digest: D) -> Self where D: Digest<OutputSize = U64>
• pub fn from_digest_safe_nonzero<D>(digest: D) -> NonZeroScalar where D: Digest<OutputSize = U64>

Now for the problems:

• random() is a part of the Field trait. If NonZeroScalar implemented Field, the code from random_nonzero() could go there.
• FromDigest requires OutputSize = FieldSize, so it can't be changed to 64 bytes output. The ways to deal with it include:
  • adding a SafeExpansionSize (or whatever) type and locking FromDigest to it
  • adding a FromDigestSafe trait
• from_digest_safe_nonzero() can be an impl of FromDigest for NonZeroScalar (but again there's the size problem)
• The added internal function Scalar::from_wide_bytes_reduced() assumes that WideScalar::reduce() can reduce any 512 bit, and not just anything below order^2. I'm 99.9% certain that's true, but I can't present a formal proof right now. I did test it for 0xfff...fff, and it works.
• WideScalar::reduce_nonzero() assumes that reduce() works just as well for the modulus decreased by one. See the comment above about being 99.9% sure.
• WideScalar::reduce_nonzero() contains an unwrap(). Ideally I'd prefer to have something like NonZeroScalar::from_bytes_unchecked() to avoid it.

Hi,

Is there a way to compute and verify p384 signatures yet?

p384 has an ecdsa feature, but I couldn't get anything done with it. ProjectiveArithmetic is not implemented for NistP384. The arithmetic feature of the elliptic_curve crate isn't set, so I wasn't even able to manually compute a public key.

Is it possible to use it in a similar way as p256 and k256? Or to use it for ECDSA at all? Or is it still a work in progress?

Thanks for your help :)

Hi,

Since version 0.5, Secp256k1 signatures cannot be created nor verified due to DigestPrimitive not being implemented.

The example code from the documentation fails:

   | let signature: Signature = signing_key.sign(message);
   |                                        ^^^^ the trait `ecdsa::hazmat::DigestPrimitive` is not implemented for `Secp256k1`
   |
   = note: required because of the requirements on the impl of `PrehashSignature` for `ecdsa::Signature<Secp256k1>`
   = note: required because of the requirements on the impl of `Signer<ecdsa::Signature<Secp256k1>>` for `SigningKey`

One of the goals of the elliptic-curve crate is to be able to write code that's generic over (at least Weierstrass) elliptic curve types.

Now that the p256 and k256 crates have arithmetic implementations (thanks @str4d and @tuxxy!), an open question is how to write code that's generic over the underlying AffinePoint and/or ProjectivePoint types.

It seems like AffinePoint and ProjectivePoint could benefit from having traits which at the very least are bounded by the point arithmetic they must support.

It also seems like there needs to be some trait connecting the two of them which can be used to access the From impls and arithmetic (e.g. Add) between the two different point types.

Finally, it seems like there needs to be a trait a weierstrass::Curve type can impl which provides that curve's AffinePoint and ProjectivePoint types as associated types.

Curious if people think this is a good idea and what those traits might look like.

cc @tuxxy

Currently using the arithmetic feature requires atomics. Compilling on a platform without atomics (such as RV32IMC) results in this error:

error[E0432]: unresolved imports `core::sync::atomic::AtomicBool`, `core::sync::atomic::AtomicI16`, `core::sync::atomic::AtomicI32`, `core::sync::atomic::AtomicI8`, `core::sync::atomic::AtomicIsize`, `core::sync::atomic::AtomicPtr`, `core::sync::atomic::AtomicU16`, `core::sync::atomic::AtomicU32`, `core::sync::atomic::AtomicU8`, `core::sync::atomic::AtomicUsize`
  --> /home/alistair/.cargo/registry/src/github.com-1ecc6299db9ec823/radium-0.3.0/src/lib.rs:29:11
   |
29 |     self, AtomicBool, AtomicI16, AtomicI32, AtomicI8, AtomicIsize, AtomicPtr, AtomicU16, AtomicU32,
   |           ^^^^^^^^^^  ^^^^^^^^^  ^^^^^^^^^  ^^^^^^^^  ^^^^^^^^^^^  ^^^^^^^^^  ^^^^^^^^^  ^^^^^^^^^ no `AtomicU32` in `sync::atomic`
   |           |           |          |          |         |            |          |
   |           |           |          |          |         |            |          no `AtomicU16` in `sync::atomic`
   |           |           |          |          |         |            no `AtomicPtr` in `sync::atomic`
   |           |           |          |          |         no `AtomicIsize` in `sync::atomic`
   |           |           |          |          no `AtomicI8` in `sync::atomic`
   |           |           |          no `AtomicI32` in `sync::atomic`
   |           |           no `AtomicI16` in `sync::atomic`
   |           no `AtomicBool` in `sync::atomic`
30 |     AtomicU8, AtomicUsize, Ordering,
   |     ^^^^^^^^  ^^^^^^^^^^^ no `AtomicUsize` in `sync::atomic`
   |     |
   |     no `AtomicU8` in `sync::atomic`

error: aborting due to previous error

For more information about this error, try `rustc --explain E0432`.
error: could not compile `radium`.

To learn more, run the command again with --verbose.
make: *** [Makefile:141: flash-opentitan] Error 101

cargo tree reports that Radium comes from:

├── ecdsa v0.8.0
│   ├── elliptic-curve v0.6.0
│   │   ├── bitvec v0.18.3
│   │   │   ├── funty v1.0.1
│   │   │   ├── radium v0.3.0
│   │   │   └── wyz v0.2.0

I have opened an issue for Radium: https://github.com/mystor/radium/issues/3 but it would also be great if these libraries could stop depending on it.

TBH I'm not sure if this is a bug in k256 or a Rust miscompilation bug.

We've found that in certain cases k256 compressed point serialization and deserialization do not round trip correctly. In particular the sign of y will for certain rare points, be flipped.

This is using k256 0.10.2, rustc 1.58.1

use k256::elliptic_curve::group::GroupEncoding;
use k256::elliptic_curve::sec1::FromEncodedPoint;

pub fn deserialize(bytes: &[u8]) -> Option<k256::ProjectivePoint> {
    match k256::EncodedPoint::from_bytes(bytes) {
        Ok(ept) => {
            let apt = k256::AffinePoint::from_encoded_point(&ept);

            if bool::from(apt.is_some()) {
                Some(k256::ProjectivePoint::from(apt.unwrap()))
            } else {
                None
            }
        }
        Err(_) => None,
    }
}

pub fn serialize(pt: k256::ProjectivePoint) -> Vec<u8> {
    pt.to_affine().to_bytes().to_vec()
}

fn main() {
    let bits =
        hex::decode("024b395881d9965c4621459ad2ec12716fa7f669b6108ad3b8b82b91644fb44808").unwrap();

    let pt = deserialize(&bits).unwrap();

    let pt_bytes = serialize(pt);

    assert_eq!(bits, pt_bytes);
}

In release mode (only), this fails:

$ cargo run --release
   Compiling k256-bug v0.1.0 (/home/jack/sw/k256-bug)
    Finished release [optimized] target(s) in 0.58s
     Running `target/release/k256-bug`
thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `[2, 75, 57, 88, 129, 217, 150, 92, 70, 33, 69, 154, 210, 236, 18, 113, 111, 167, 246, 105, 182, 16, 138, 211, 184, 184, 43, 145, 100, 79, 180, 72, 8]`,
 right: `[3, 75, 57, 88, 129, 217, 150, 92, 70, 33, 69, 154, 210, 236, 18, 113, 111, 167, 246, 105, 182, 16, 138, 211, 184, 184, 43, 145, 100, 79, 180, 72, 8]`', src/main.rs:31:5

So far we have not been able to reproduce this in either debug mode or with coverage guided fuzzing enabled.

It seems that some Serde serializers have issues when serializing VerifyingKeys and Signatures. They all serialize fine, but Serde returns an error for certain serializers when deserializing back to the original type.

I've tested it with three serializers, and it seems to be a bit of a hit or miss if it works. It's a bit verbose, but I've included tests that reproduce the issue. I would normally just include a Rust Playground link, but they don't support k256.

#[cfg(test)]
mod test {
    use k256::ecdsa::{Signature, SigningKey, signature::Signer};
    use rand::rngs::OsRng;
    use serde::{Deserialize, Serialize};
    use std::fmt::Debug;

    fn ser_deser_test<'a, D, S, T, U>(ser: S, deser: D, val: T)
    where
        D: Fn(&U) -> Result<T, String>,
        S: Fn(&T) -> Result<U, String>,
        T: Debug + Deserialize<'a> + PartialEq + Serialize,
    {
        let ser = ser(&val).unwrap();
        let deser = deser(&ser).expect("Deserialization failure");

        assert_eq!(val, deser);
    }

    fn create_fake_sig() -> Signature {
        let k = SigningKey::random(&mut OsRng);
        let msg: Vec<_> = (0..100).collect();

        k.sign(&msg)
    }

    #[test]
    fn json_signing_key() {
        ser_deser_test(
            |val| serde_json::to_string(val).map_err(|err| err.to_string()),
            |str| serde_json::from_str(str).map_err(|err| err.to_string()),
            SigningKey::random(&mut OsRng).verifying_key(),
        );
    }

    #[test]
    fn json_signature() {
        ser_deser_test(
            |val| serde_json::to_string(val).map_err(|err| err.to_string()),
            |str| serde_json::from_str(str).map_err(|err| err.to_string()),
            create_fake_sig(),
        );
    }

    #[test]
    fn toml_signing_key() {
        ser_deser_test(
            |val| toml::to_string(val).map_err(|err| err.to_string()),
            |str| toml::from_str(str).map_err(|err| err.to_string()),
            SigningKey::random(&mut OsRng).verifying_key(),
        );
    }

    #[test]
    fn toml_signature() {
        ser_deser_test(
            |val| toml::to_string(val).map_err(|err| err.to_string()),
            |str| toml::from_str(str).map_err(|err| err.to_string()),
            create_fake_sig(),
        );
    }

    #[test]
    fn bincode_signing_key() {
        ser_deser_test(
            |val| bincode::serialize(val).map_err(|err| err.to_string()),
            |bytes| bincode::deserialize(bytes).map_err(|err| err.to_string()),
            SigningKey::random(&mut OsRng).verifying_key(),
        );
    }

    #[test]
    fn bincode_signature() {
        ser_deser_test(
            |val| bincode::serialize(val).map_err(|err| err.to_string()),
            |bytes| bincode::deserialize(bytes).map_err(|err| err.to_string()),
            create_fake_sig(),
        );
    }
}

Dependencies:

[dependencies]
k256 = {version = "0.10.4", features = ["serde", "pem"] }
bincode = "1.3.3"
serde_json = "1.0.59"
rand = {version = "0.8.5", features = ["getrandom"] }
toml = "0.5.8"
serde = "1.0"
serde_yaml = "0.8"

With results:

test test::bincode_signing_key ... ok
test test::json_signature ... ok
test test::bincode_signature ... ok
test test::json_signing_key ... FAILED ("panicked at 'Deserialization failure: invalid type: sequence, expected a borrowed byte array at line 1 column 1")
test test::toml_signing_key ... FAILED ("panicked at 'Deserialization failure: "expected a right bracket, found a comma at line 1 column 4")
test test::toml_signature ... FAILED ("panicked at 'Deserialization failure: "expected an equals, found eof at line 1 column 131")

I'm not very experienced with cryptography, so let me know if I'm doing something that I shouldn't be. :slightly_smiling_face:

This is a tracking ticket for work items it would be nice to have before cutting a final v0.11 release which includes an initial arithmetic implementation.

NOTE: not all of these need to be completed prior to a release and they can be added after-the-fact.

• [x] #573
• [x] Test vectors
  • [x] #567
  • [x] #570
  • [x] #569
  • [x] #574

cc @brycx @jedisct1

This PR introduces a way to multiply a scalar by the generator by keeping precomputed lookup tables. Speeds up signing by about 6% according to benchmarks; I was hoping for more, but it does only get rid of 7 point additions (creation of the lookup table), so, I guess, it was expected. Up to you if you think that the measly speed-up justifies the increase in complexity.

Currently it is exposed just as a mul_by_generator() function; ideally we should probably add a MulByGenerator trait in elliptic-curve alongside LinearCombination and expose the functionality through that. I can do that if we decide to proceed with it.

I assume these are missing since nobody needed them so far, or is there a concern?

Doing a bunch of iterator.fold(Scalar::ZERO, |acc, summand| acc + summand) where I'd like to just write iterator.sum().

Would also be nice to have Sum for AffinePoint.

This is in big need of more scrutiny, documenting, and refactoring, but I wanted to push early and allow for input.

Elligator Squared is obviously not a standard anything, nor is the simplified Shallue-van de Woestijne-Ulas encoding, so I’m pretty open to this being a bad fit for inclusion in this crate. This is well into “science project” territory and really not something I’d responsibly recommend to anyone.

Buuut it’s neat and I’ve got a hobby project which might could use it and it seems like a decent focal point for conversations about what an EC API looks like which would allow me to ~commit these sorts of crimes~ implement this sort of functionality without having to maintain my own fork. At a minimum, that’d probably be access to FieldElement, curve constants, and point construction.

Ostensibly this could also be implemented for k256, but it’d need a similar degree of specialization.

Absolutely no hurry on this, BTW.

The k256 crate uses lazy normalization of field elements. While not a user-facing concern as we deliberately encapsulate FieldElement, there is a potential for bugs in code in k256 itself in the event one "forgets" to normalize a field element prior to returning it as the result of some computation. See #530 as an example (although there have been others).

One potential way to eliminate this class of bugs is to use separate types for normalized vs non-normalized field elements. For example, we could introduce something like LazyFieldElement on which all of the arithmetic operations are defined, while retaining FieldElement for the normalized form and defining all serialization operations on that.

LazyFieldElement::normalize could return FieldElement, and we could additionally have bidirectional From conversions between the two.

Things would be a bit tricky in regard to the the ff::Field traits. I imagine for compatibility reasons they would need to be impl'd on FieldElement, converting to a LazyFieldElement to perform the arithmetic, and then calling normalize() to get a FieldElement again as a result, which would mean that the performance benefits of lazy normalization wouldn't be available under such an API. However, that is the only safe usage pattern since the traits are designed to abstract over different fields/field implementations, and not all of them have lazy normalization.

cc @fjarri

While working on voprf and opaque-ke I noticed that a lot of implementations and traits could be removed if curve25519-dalek would support necessary traits from elliptic-curves, like Curve and ProjectiveArithmetic. Using some of these already uncovered serious bugs and other issues.

It might be possible to implement some of it through PR's or wrappers for ed25519 and x25519, but it will be much harder for ristretto255. Among other problems in the library, the dependency maintenance story isn't ideal, as seen by the many PR's to update rand.

Specifically, voprf is interested in support for ristretto255 arithmetic, including hash2curve. For opaque-ke x25519 and ristretto255 support for DH is a requirement.

I am myself no cryptographer and sadly can only contribute, but not actually implement something like it.