zengo-x / curv

Rust language general purpose elliptic curve cryptography.

Curv

Curv contains an extremely simple interface to onboard new elliptic curves. Use this library for general purpose elliptic curve cryptography.

The library has a built in support for some useful operations/primitives such as verifiable secret sharing, commitment schemes, zero knowledge proofs, and simple two party protocols such as ECDH and coin flip. The library comes with serialize/deserialize support to be used in higher level code to implement networking.

Usage

To use curv crate, add the following to your Cargo.toml:

[dependencies]
curv-kzen = "0.9"

The crate will be available under curv name, e.g.:

use curv::elliptic::curves::*;

Currently Supported Elliptic Curves

Curve	low level library	curve description
Secp256k1	rust-secp256k1	bitcoin wiki
P-256	RustCrypto	NIST.FIPS.186.4
Ed25519	cryptoxide	BDLSY11
Ristretto	curve25519-dalek	ristretto group
BLS12-381	bls12-381	BLS12-381 For The Rest Of Us

Security

The library was audited by Kudelski security on Feb19. The report can be found here. No critical issue were found and all issues found were fixed.

The code was reviewed independently by few other cryptographers. Special thanks goes to Claudio Orlandi from Aarhus University.

In general security of the library is strongly dependent on the security of the low level libraries used. We chose only libraries that are used as part of other big projects and went through heavy audit/review.

The library is not immune to side channel attacks but considerable effort was given to try and catch as many such attacks as possible (see audit report).

Build

Use cargo build to build everything including curve implementations, cryptoprimitives, BigInt, etc.

Big integer implementation

The library supports a couple of bigint implementations and can easily switch between them. You can choose any one which you prefer by specifying a feature:

• rust-gmp-kzen, uses GMP bindings, requires GMP to be installed on a machine. Used by default.

• num-bigint, Rust's pure implementation of big integer. In order to use it, put in Cargo.toml:

  [dependencies.curv-kzen]
  version = "0.8"
  default-features = false
  features = ["num-bigint"]

  Warning: num-bigint support is experimental and should not be used in production. For this bigint implementation, we use prime numbers generator which is not considered secure.

Examples

The library includes some basic examples to get you going. To run them: cargo run --example EXAMPLE_NAME -- CURVE_NAME for example: cargo run --example proof_of_knowledge_of_dlog -- secp256k1

Docs

To build docs, use:

cargo doc
RUSTDOCFLAGS="--html-in-header katex-header.html" cargo doc --no-deps --open

License

Curv is released under the terms of the MIT license. See LICENSE for more information.

Development Process & Contact

This library is maintained by ZenGo-X. Contributions are highly welcomed! Besides GitHub issues and PRs, feel free to reach out by mail or join ZenGo X Telegram for discussions on code and research.

curv's Issues

Replace `from_coor` with `from_bytes`

We are currently using from_coor in most of the serialization function. This function is not supported for some of the curve and we are now using from_bytes. Before removing this method from the elliptic trait we need to replace all usages with the new from_bytes

Secp256k1Point bincode deserialization error

use bincode;
use curv::GE;

fn main() {
    let p = GE::random_point();
    let encoded = bincode::serialize(&p).unwrap();
    let decoded: GE = bincode::deserialize(encoded.as_slice()).unwrap();
}

thread 'main' panicked at 'called `Result::unwrap()` on an `Err` value: Custom("invalid type: sequence, expected Secp256k1Point")', src/libcore/result.rs:1084:5
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace.

[package]
name = "test"
version = "0.1.0"
edition = "2018"

[dependencies]
serde = "1.0"
bincode = "1.1"

[dependencies.curv]
git = "https://github.com/KZen-networks/curv"
tag = "v0.2.0"
features =  ["ec_secp256k1"]

Add commitments API that accept FE

Pedersen commitment currently accepts BigInt and convert it to FE. We want to have it accept directly FE. Same can be dome with hash based commitments

Cargo build fails

cargo build fails with error

error[E0432]: unresolved imports `FE`, `GE`                                                                                                                                                                         
  --> src/cryptographic_primitives/commitments/pedersen_commitment.rs:21:14                                                                                                                                         
   |                                                                                                                                                                                                                
21 | use {BigInt, FE, GE};                                                                                                                                                                                          
   |              ^^  ^^ no `GE` in the root                                                                                                                                                                        
   |              |                                                                                                                                                                                                 
   |              no `FE` in the root                                                                                                                                                                               
                                                                                                                                                                                                                    
error[E0432]: unresolved imports `FE`, `GE`                                                                                                                                                                         
  --> src/cryptographic_primitives/hashing/hash_sha256.rs:22:6                                                                                                                                                      
   |                                                                                                                                                                                                                
22 | use {FE, GE};                                                                                                                                                                                                  
   |      ^^  ^^ no `GE` in the root                                                                                                                                                                                
   |      |                                                                                                                                                                                                         
   |      no `FE` in the root                                                                                                                                                                                       
                                                                                                                                                                                                                    
error[E0432]: unresolved imports `FE`, `GE`                                                                                                                                                                         
  --> src/cryptographic_primitives/hashing/hash_sha512.rs:22:6                                                                                                                                                      
   |                                                                                                                                                                                                                
22 | use {FE, GE};                                                                                                                                                                                                  
   |      ^^  ^^ no `GE` in the root                                                                                                                                                                                
   |      |                                                                                                                                                                                                         
   |      no `FE` in the root                                                                                                                                                                                       
                                                                                                                                                                                                                    
error[E0432]: unresolved import `GE`                                                                                                                                                                                
  --> src/cryptographic_primitives/hashing/merkle_tree.rs:18:5                                                                                                                                                      
   |                                                                                                                                                                                                                
18 | use GE;                                                                                                                                                                                                        
   |     ^^ no `GE` in the root                                                                                                                                                                                     
                                                                                                                                                                                                                    
error[E0432]: unresolved imports `FE`, `GE`                                                                                                                                                                         
  --> src/cryptographic_primitives/hashing/traits.rs:18:6                                                                                                                                                           
   |                                                                                                                                                                                                                
18 | use {FE, GE};                                                                                                                                                                                                  
   |      ^^  ^^ no `GE` in the root                                                                                                                                                                                
   |      |                                                                                                                                                                                                         
   |      no `FE` in the root                                                                                                                                                                                       
                                                                                                                                                                                                                    
error[E0432]: unresolved import `FE`                                                                                                                                                                                
  --> src/cryptographic_primitives/proofs/dlog_zk_protocol.rs:31:5                                                                                                                                                  
   |                                                                                                                                                                                                                
31 | use FE;                                                                                                                                                                                                        
   |     ^^ no `FE` in the root                                                                                                                                                                                     
                                                                                                                                                                                                                    
error[E0432]: unresolved import `GE`                                                                                                                                                                                
  --> src/cryptographic_primitives/proofs/dlog_zk_protocol.rs:32:5                                                                                                                                                  
   |                                                                                                                                                                                                                
32 | use GE;                                                                                                                                                                                                        
   |     ^^ no `GE` in the root                                                                                                                                                                                     
                                                                                                                                                                                                                    
error[E0432]: unresolved import `FE`                                                                                                                                                                                
  --> src/cryptographic_primitives/proofs/sigma_correct_homomorphic_elgamal_encryption_of_dlog.rs:27:5                                                                                                              
   |                                                                                                                                                                                                                
27 | use FE;                                                                                                                                                                                                        
   |     ^^ no `FE` in the root                                                                                                                                                                                     
                                                                                                                                                                                                                    
error[E0432]: unresolved import `GE`                                                                                                                                                                                
  --> src/cryptographic_primitives/proofs/sigma_correct_homomorphic_elgamal_encryption_of_dlog.rs:28:5                                                                                                              
   |                                                                                                                                                                                                                
28 | use GE;                                                                                                                                                                                                        
   |     ^^ no `GE` in the root                                                                                                                                                                                     
                                                                                                                                                                                                                    
error[E0432]: unresolved import `FE`                                                                                                                                                                                
  --> src/cryptographic_primitives/proofs/sigma_correct_homomrphic_elgamal_enc.rs:27:5                                                                                                                              
   |                                                                                                                                                                                                                
27 | use FE;                                                                                                                                                                                                        
   |     ^^ no `FE` in the root                                                                                                                                                                                     
                                                                                                                                                                                                                    
error[E0432]: unresolved import `GE`                                                                                                                                                                                
  --> src/cryptographic_primitives/proofs/sigma_correct_homomrphic_elgamal_enc.rs:28:5                                                                                                                              
   |                                                                                                                                                                                                                
28 | use GE;                                                                                                                                                                                                        
   |     ^^ no `GE` in the root                                                                                                                                                                                     
                                                                                                                                                                                                                    
error[E0432]: unresolved import `FE`                                                                                                                                                                                
  --> src/cryptographic_primitives/proofs/sigma_dlog.rs:27:5                                                                                                                                                        
   |                                                                                                                                                                                                                
27 | use FE;                                                                                                                                                                                                        
   |     ^^ no `FE` in the root                                                                                                                                                                                     
                                                                                                                                                                                                                    
error[E0432]: unresolved import `GE`                                                                                                                                                                                
  --> src/cryptographic_primitives/proofs/sigma_dlog.rs:28:5                                                                                                                                                        
   |                                                                                                                                                                                                                
28 | use GE;                                                                                                                                                                                                        
   |     ^^ no `GE` in the root                                                                                                                                                                                     
                                                                                                                                                                                                                    
error[E0432]: unresolved imports `FE`, `GE`                                                                                                                                                                         
  --> src/cryptographic_primitives/proofs/sigma_ec_ddh.rs:34:6                                                                                                                                                      
   |                                                                                                                                                                                                                
34 | use {FE, GE};                                                                                                                                                                                                  
   |      ^^  ^^ no `GE` in the root                                                                                                                                                                                
   |      |                                                                                                                                                                                                         
   |      no `FE` in the root                                                                                                                                                                                       
                                                                                                                                                                                                                    
error[E0432]: unresolved imports `FE`, `GE`                                                                                                                                                                         
  --> src/cryptographic_primitives/proofs/sigma_valid_pedersen.rs:33:6                                                                                                                                              
   |                                                                                                                                                                                                                
33 | use {FE, GE};                                                                                                                                                                                                  
   |      ^^  ^^ no `GE` in the root                                                                                                                                                                                
   |      |                                                                                                                                                                                                         
   |      no `FE` in the root                                                                                                                                                                                       
                                                                                                                                                                                                                    
error[E0432]: unresolved imports `FE`, `GE`                                                                                                                                                                         
  --> src/cryptographic_primitives/proofs/sigma_valid_pedersen_blind.rs:37:6                                                                                                                                        
   |                                                                                                                                                                                                                
37 | use {FE, GE};                                                                                                                                                                                                  
   |      ^^  ^^ no `GE` in the root                                                                                                                                                                                
   |      |                                                                                                                                                                                                         
   |      no `FE` in the root                                                                                                                                                                                       
                                                                                                                                                                                                                    
error[E0432]: unresolved import `FE`                                                                                                                                                                                
  --> src/cryptographic_primitives/secret_sharing/feldman_vss.rs:24:5                                                                                                                                               
   |                                                                                                                                                                                                                
24 | use FE;                                                                                                                                                                                                        
   |     ^^ no `FE` in the root                                                                                                                                                                                     
                                                                                                                                                                                                                    
error[E0432]: unresolved import `GE`                                                                                                                                                                                
  --> src/cryptographic_primitives/secret_sharing/feldman_vss.rs:25:5                                                                                                                                               
   |                                                                                                                                                                                                                
25 | use GE;                                                                                                                                                                                                        
   |     ^^ no `GE` in the root                                                                                                                                                                                     
                                                                                                                                                                                                                    
error[E0432]: unresolved import `FE`                                                                                                                                                                                
  --> src/cryptographic_primitives/twoparty/dh_key_exchange.rs:35:5                                                                                                                                                 
   |                                                                                                                                                                                                                
35 | use FE;                                                                                                                                                                                                        
   |     ^^ no `FE` in the root                                                                                                                                                                                     
                                                                                                                                                                                                                    
error[E0432]: unresolved import `GE`                                                                                                                                                                                
  --> src/cryptographic_primitives/twoparty/dh_key_exchange.rs:36:5                                                                                                                                                 
   |                                                                                                                                                                                                                
36 | use GE;                                                                                                                                                                                                        
   |     ^^ no `GE` in the root                                                                                                                                                                                     
                                                                                                                                                                                                                    
warning: unused import: `ECPoint`                                                                                                                                                                                   
  --> src/cryptographic_primitives/hashing/hash_sha256.rs:19:32                                                                                                                                                     
   |                                                                                                                                                                                                                
19 | use elliptic::curves::traits::{ECPoint, ECScalar};                                                                                                                                                             
   |                                ^^^^^^^                                                                                                                                                                         
   |                                                                                                                                                                                                                
   = note: #[warn(unused_imports)] on by default                                                                                                                                                                    
                                                                                                                                                                                                                    
warning: unused import: `ECPoint`                                                                                                                                                                                   
  --> src/cryptographic_primitives/hashing/hash_sha512.rs:19:32                                                                                                                                                     
   |                                                                                                                                                                                                                
19 | use elliptic::curves::traits::{ECPoint, ECScalar};                                                                                                                                                             
   |                                ^^^^^^^                                                                                                                                                                         
                                                                                                                                                                                                                    
error: aborting due to 20 previous errors                                                                                                                                                                           
                                                                

method `sub_points` fails sometimes for curve25519

test_minus_point fails to generate valid public key once in a while.

Remove ristretto255 trait implementations

I noticed today that the curv traits are implemented for ristretto255.

ristretto255 is an abstract group, not an elliptic curve. See the ristretto255 RFC draft for more details. The curv traits provide APIs for elliptic curves, and thus it is a type error to implement them for ristretto255.

I briefly looked at the trait implementation, and found an example of where the type error manifests as an implementation error:

https://github.com/KZen-networks/curv/blob/b326b2708560eaa0e8fd86f2c2d7d20d6eafbdce/src/elliptic/curves/curve_ristretto.rs#L278-L289

Besides the fact that ristretto255 elements do not have coordinates, this code is parsing an encoded ristretto255 element (which includes the representation of a field element modulo p = 2²⁵⁵ - 19) as a ristretto255 scalar (which are field elements modulo ℓ = 2²⁵² + 27742317777372353535851937790883648493), which is a type error, and returns a scalar that has been reduced from a field element, losing information.

ristretto curve "from_bytes" is not rejecting

from bytes methods should accept only valid byte strings. Currently all strings are accepted (because of the underlining use of elligator in dalek-curve25519 lib)

Implementation of `base_point2`

    // from https://github.com/KZen-networks/curv/pull/61/commits/3bd540e13a1152ccf51b7adf276887860482e44e
    pub fn base_point2() -> Self {
        let g = Self::generator();

        let hash = HSha256::create_hash(&[&g.bytes_compressed_to_big_int()]);
        let hash = HSha256::create_hash(&[&hash]);
        let hash = HSha256::create_hash(&[&hash]);

        let mut possible_pk = vec![2u8];
        possible_pk.append(&mut BigInt::to_vec(&hash));

        Self {
            purpose: "random",
            ge: PK::from_slice(possible_pk.as_slice()).unwrap(),
        }
    }

Is there a better way than generating another fixed (not random) base point by taking original base point's sha256 hash? The hash is not necessarily a valid x coordinate of a point on curve, so we take the hash over and over again until we find such a valid x.

The question is: why we use this method instead of picking a number k and multiply it with original base point to get another base point? Or is that because we want to get a valid base point without revealing the number k?

enable hash and hash based commitment for default feature

at the moment - hash and hash commitment are disabled for the default feature. In the hash function case there is also hash function from elliptic curve points that must be defined only with one of the elliptic curve features.

Refactor CurveConstCodec

The context struct Secp256k1 is unique to libsecp256k1 and does not generalize well to other elliptic curves.
Currently CurveConstCodec trait has two methods:
get_base_point -> needs to move to PublicKeyCodec
get_q -> needs to move to SecretKeyCodec
This makes much more sense and will allow to abstract for more elliptic curves

constant time comparisons

can be done using https://github.com/dalek-cryptography/subtle as one option.
Thanks to Jeremy Rubin.

curv exports only 1 curve implementation

curv exports only 1 curve implementation (secp256k1 / secp256r1 / ed25519 / etc). It may not be convenient in some cases, e.g. if I have to deal with both secp256k1 and secp256r1 simultaneously. With Rust's powerful type system, this limitation can be worked out.

Currently, to support multiple curve implementation, you define type aliases at the root of crate (FE, GE, PK, SK) which points to selected implementation based on features, and all other cryptographic code relies on those type aliases, e.g. that's the definition of VSS primitive:

#[derive(Clone, PartialEq, Debug, Serialize, Deserialize)]
pub struct VerifiableSS {
    pub parameters: ShamirSecretSharing,
    pub commitments: Vec<GE>,
}

I'd suggest using type generics here:

#[derive(Clone, PartialEq, Debug, Serialize, Deserialize)]
pub struct VerifiableSS<P> {
    pub parameters: ShamirSecretSharing,
    pub commitments: Vec<P>,
}

impl<P: ECPoint> VerifiableSS<P> {
  // ...
}

However, this is a big-scale refactoring as it will touch all dependent crates, like multi-party-ecdsa, which rely on those type synonyms too. But it will make code more flexible and Rust-ish.

constant time for scalar operations

Operations on scalars were never optimized for constant time.
example:
https://github.com/KZen-networks/curv/blob/master/src/elliptic/curves/secp256_k1.rs#L131 will leak the size of Secp256k1Scalar.

Code can be found here:
https://github.com/KZen-networks/curv/tree/master/src/elliptic/curves

implement proof of ec-ddh

statement = G1,H1,G2,H2
R=1 if H1 = xG1, H2 = xG2

• P choose alpha in random and sends a1 = alphaG1, a2 = alphaG2
• V sends a challenge
• P respond with r = alpha - xe
• V checks a1=rG1 + eH1, a_2 = rG2 + eH2

Enable default feature

We wish to allow compilation without flags by making a default feature.
Currently when we try to add a default feature it is compiled no matter what, including when we specifically choose another features (in that case both features are included).

update serialize for curve25519

https://github.com/KZen-networks/cryptography-utils/blob/master/src/elliptic/curves/curve25519.rs#L133

Currently curve25519 do not provide a method to print x coordinate of a point and our serialize method is using (x,y). Our current solution is to serielize (y,y) and derive x from y. We need to update the our serde such that it will support one coordinate . or to implement the coordinate derivation ourselves:

        //taken from https://doc-internal.dalek.rs/src/curve25519_dalek/edwards.rs.html#144
        let y = self.ge.as_bytes().clone();
        let Y = SK::from_bytes_mod_order(y);
        let Z = SK::one();
        let YY = Y*Y;
        let u = &YY - &Z;
        let v = &(&YY * &constants::EDWARDS_D) + &Z;
        let (is_nonzero_square, mut X) = sqrt_ratio(&u, &v);

Upgrade libsecp256k1

currently 0.9.0
need to update to 0.10.0

Non-additive feature flags are problematic

Currently you cannot compile curv with more than one of the specific curve features enabled due to the top-level FE, GE, PK, SK aliases. Please note that this is generally discouraged, because in a complex application there might be a dependency graph that wants to enable different curves, and this will result in compile failures in curv.

(Also, I really dislike these two-letter type names and the fact that there are two sets of aliases for each curve. IMO, using PublicKey and SecretKey consistently instead would make code using curv much more readable.)

More curves please

Hi there,
It would be good if you implement more curves. Mainly, I'm speaking about secp521r1 as almost all SSL libraries have implemented it..
I wish I was not so new to Rust and ECC and I could contribute to this project. Nevertheless, I like the Gotham city project and I would appreciate a lot if some more trusted curves are implemented here.

test_bit_length_create_commitment_with_user_defined_randomness fails occasionally

Once in every few attempts, test fails (I would assume every 16 attempts on average):

$ cargo test --features=ec_secp256k1
---- cryptographic_primitives::commitments::hash_commitment::tests::test_bit_length_create_commitment_with_user_defined_randomness stdout ----
thread 'cryptographic_primitives::commitments::hash_commitment::tests::test_bit_length_create_commitment_with_user_defined_randomness' panicked at 'assertion failed: `(left == right)`
  left: `63`,
 right: `64`', src/cryptographic_primitives/commitments/hash_commitment.rs:83:9

Generating random secret key for secp256k1 is not correct

impl ECScalar<SK> for Secp256k1Scalar {
    fn new_random() -> Self {
        let mut arr = [0u8; 32];
        thread_rng().fill(&mut arr[..]);
        Self {
            purpose: "random",
            fe: SK::from_slice(&arr[0..arr.len()]).unwrap(),
        }
    }
   // ...
}

This is not enough, a valid secret key should be [1, Group order), and group order is fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

How to serialize/deserialize PublicKey?

I want to recover from bytes.

fn main() {
    let ec_point: GE = ECPoint::generator();
    let secret: FE = ECScalar::new_random();
    let public: GE = ec_point.scalar_mul(&secret.get_element());
    let compressed_key = public.get_element().serialize();
    let new_public: GE = ECPoint::from_bytes(&compressed_key).expect("THIS");
    // let uncompressed_key = public.get_element().serialize_uncompressed();
    // let new_public: GE = ECPoint::from_bytes(&uncompressed_key).expect("THIS");
    assert_eq!(public, new_public);
}

It looks work, but paniced 'THIS: InvalidPublicKey.
I cannot find correct way to serialize/deserialize except this.
What's wrong is this way?

Deterministic / regression unit testing for elliptic curves

Motivation

Curv is used as a low level library for crypto-currency wallets impacting the following critical features: address creation / derivation, master-key generation, signature.
A framework for unit testing a curve should be defined and used.

Proposal

As a starting point, my proposal is to start with secp256 and add basic unit testing which make sure of basic features. Test output against previously verified hardcoded set of values.

Wrap mul_assign and handle error within the wrapper

Suggested by @romanz here: ZenGo-X/multi-party-ecdsa#39.

Refactor GE to take &self instead of mut self

for backward compatibility we need to support both

transform coin flip protocol to support abstract elliptic curves

related also to #25

point and scalar validation

Thanks to @ra-- who raised this issue:

I noticed that there were some unsafe unwrap calls/missing checks. E.g. https://github.com/ZenGo-X/curv/blob/master/src/elliptic/curves/secp256_k1.rs#L148 the scalar may be 0. Or here https://github.com/ZenGo-X/curv/blob/master/src/elliptic/curves/secp256_k1.rs#L160. Basically add, sub, mul, and invert should check whether the result is 0. For points, there are unsafe unwraps as well. Here for example: https://github.com/ZenGo-X/curv/blob/master/src/elliptic/curves/secp256_k1.rs#L414.

Error handling should be added as part of the point and scalar traits by way of returning Result. Here is an example:
nash-io/nash-rust@0910eb7#diff-bf4822a262bb2d66887c738137845d7b

How to install on Windows env?

Link error,

note: Non-UTF-8 output: LINK : fatal error LNK1181: \x93\xfc\x97\xcd\x83t\x83@\x83C\x83\x8b \'gmp.lib\' \x82\xf0\x8aJ\x82\xaf\x82\xdc\x82\xb9\x82\xf1\x81B\r\n

I find rack of gmp.lib, download from gmp-static-vc-4.1.2.zip and move to C:\Users\home\.rustup\toolchains\nightly-x86_64-pc-windows-msvc\lib\rustlib\x86_64-pc-windows-msvc\lib

fatal error LNK1120: 108 \x8c\x8f\x82\xcc\x96\xa2\x89\xf0\x8c\x88\x82\xcc\x8aO\x95\x94\x8eQ\x8f\xc6\r\n

how to solve it?

Refactor elliptic curve abstraction

Opening this issue for discussion:
Currently we are using our own struct called Point which is a non-native representation of the EC point as x and y coordinates. This struct is being used to easily extract the x coordinate (when used to hash a publicKey).
EC computations on the other hand are done using a native PublicKey struct in an efficient way.
few suggestions:

• eliminate Point struct and instead add methods in PublicKeyCodec for get_x_coor, get_y_coor
• write abstract PublicKey struct that will be implemented for every EC we add and will represent the chosen EC native publicKey struct.
• Do the same for SecretKey struct (the current SecretKeyCodec is actually good for now, just renaming)
• abstract (add to PublicKeyCodec ) the nG and nG + mH operations (mul_asign and combine for secp256k1)

Generalize Pederson sigma proofs to work with all elliptic curves

Scalar zero

While implementing proactive secret sharing protocols, we have come across an issue in that the secp256k1 curve library is very reluctant to let us have a scalar zero or the identity point. This makes proactive secret sharing protocols a bit tricky to implement.

Is this a fundamental limitation, or is it just needed for safe ECDSA implementation?

Constant time implementation for Modulo trait

to get better chances against side channels

Replace rust-crypto with RustCrypto

rust-crypto is used for hash and for mac in curv. We wish to replace it with RustCrypto based crates which are actively supported.

Test `test_bit_length_create_commitment_with_user_defined_randomness` sometimes fails

Related to #54, it seems that the test that fails once in 16 runs (in expectation) is:
https://github.com/KZen-networks/curv/blob/7f0586fd543f81f5202da766cd7c382e07876a04/src/cryptographic_primitives/commitments/hash_commitment.rs#L78
Because leading zeros are not translated into a string.

Possible fix suggestions:

• Check not_zero
• Check no error is returned from string conversion
• Check length > (some number less than 64) (This is will still be probabilistic but with lower probability)
• Ignore test

Replace secp256k1 library

move to https://crates.io/crates/libsecp256k1:

• no std
• pure rust
• based on ZenGo-X/emerald-city#8 we get serious performance boost. (see also this repo for how to implement)

Security of the new library should be checked more thoroughly

Consider migrating to Rust 2018

Mainly removing extern crate, which is no longer necessary

#51

implement Sum trait for FE and GE

https://doc.rust-lang.org/std/iter/trait.Sum.html

Write smart tests for hash functions

unit test for hash functions should use test vectors and compare results. Right not we are just doing sanity checking.

panicked at 'assertion failed: ctr_blind_len / sample_size > 0.4

Run with seq 50 | xargs -Iz cargo test -- --nocapture

    Finished dev [unoptimized + debuginfo] target(s) in 0.07s                                                                                     
     Running target/debug/deps/cryptography_utils-e955308f74f59d5e

running 26 tests
test arithmetic::big_gmp::tests::sample_below_test ... ok
test arithmetic::big_gmp::tests::sample_range_test ... ok
test arithmetic::big_gmp::tests::strict_sample_test ... ok
test arithmetic::big_gmp::tests::test_from_hex ... ok
test arithmetic::big_gmp::tests::test_mod_mul ... ok
test arithmetic::big_gmp::tests::test_mod_pow ... ok
test arithmetic::big_gmp::tests::test_mod_sub_modulo ... ok
test arithmetic::big_gmp::tests::strict_sample_range_test ... ok
test arithmetic::big_gmp::tests::test_mod_sub_negative_modulo ... ok
test arithmetic::big_gmp::tests::test_to_hex ... ok
test cryptographic_primitives::commitments::hash_commitment::tests::test_bit_length_create_commitment_with_user_defined_randomness ... ok
test cryptographic_primitives::commitments::hash_commitment::tests::test_hashing_create_commitment_with_user_defined_randomness ... ok
test cryptographic_primitives::commitments::hash_commitment::tests::test_random_num_generation_create_commitment_with_user_defined_randomness ... ok
test cryptographic_primitives::hashing::hash_sha256::tests::create_hash_test ... ok
test arithmetic::big_gmp::tests::sample_below_zero_test ... ok
test arithmetic::big_gmp::tests::invalid_range_test ... ok
test cryptographic_primitives::commitments::hash_commitment::tests::test_bit_length_create_commitment ... FAILED
test elliptic::curves::secp256_k1::tests::from_invalid_header_key_slice_test ... ok
test elliptic::curves::secp256_k1::tests::from_valid_uncompressed_key_slice_to_key_test ... ok
test elliptic::curves::secp256_k1::tests::get_base_point_test ... ok
test elliptic::curves::secp256_k1::tests::get_q_test ... ok
test elliptic::point::tests::equality_test ... ok
test elliptic::point::tests::test_serialization ... ok
test cryptographic_primitives::proofs::dlog_zk_protocol::tests::test_serialization ... ok
test elliptic::curves::secp256_k1::tests::from_public_key_to_point_to_slice_to_key ... ok
test elliptic::curves::secp256_k1::tests::from_secret_key_to_big_int ... ok

failures:

---- cryptographic_primitives::commitments::hash_commitment::tests::test_bit_length_create_commitment stdout ----
thread 'cryptographic_primitives::commitments::hash_commitment::tests::test_bit_length_create_commitment' panicked at 'assertion failed: ctr_blind_len / sample_size > 0.4', src/cryptographic_primitives/commitments/hash_commitment.rs:86:9
stack backtrace:
   0:        0x10e225a1f - std::sys::unix::backtrace::tracing::imp::unwind_backtrace::hf54cb26e9988c378
                               at libstd/sys/unix/backtrace/tracing/gcc_s.rs:49
   1:        0x10e216fea - std::sys_common::backtrace::print::hcf3280d66bce889a
                               at libstd/sys_common/backtrace.rs:71
                               at libstd/sys_common/backtrace.rs:59
   2:        0x10e228d43 - std::panicking::default_hook::{{closure}}::h5389dd597603d3e2
                               at libstd/panicking.rs:211
   3:        0x10e228a6e - std::panicking::default_hook::ha03261d956257219
                               at libstd/panicking.rs:221
   4:        0x10e229437 - <std::panicking::begin_panic::PanicPayload<A> as core::panic::BoxMeUp>::get::h92afdb80a2b4c720
                               at libstd/panicking.rs:475
   5:        0x10e1cc287 - <i32 as core::iter::range::Step>::add_usize::h061baae0da0bfc60
                               at /Users/travis/build/rust-lang/rust/src/libstd/panicking.rs:409
   6:        0x10e180b96 - cryptography_utils::cryptographic_primitives::commitments::hash_commitment::tests::test_bit_length_create_commitment::h107dfac42b916d22
                               at src/cryptographic_primitives/commitments/hash_commitment.rs:86
   7:        0x10e17e4f0 - cryptography_utils::__test::TESTS::{{closure}}::hc8eedea2334dfa47
                               at src/cryptographic_primitives/commitments/hash_commitment.rs:65
   8:        0x10e17f240 - core::ops::function::FnOnce::call_once::hcfd92abca524ad85
                               at /Users/travis/build/rust-lang/rust/src/libcore/ops/function.rs:223
   9:        0x10e18c8b1 - <F as alloc::boxed::FnBox<A>>::call_box::h6afbc84c11a5f3a1
                               at libtest/lib.rs:1451
                               at /Users/travis/build/rust-lang/rust/src/libcore/ops/function.rs:223
                               at /Users/travis/build/rust-lang/rust/src/liballoc/boxed.rs:642
  10:        0x10e234d1e - panic_unwind::dwarf::eh::read_encoded_pointer::h079a09b4aa438388
                               at libpanic_unwind/lib.rs:105
  11:        0x10e1ad94c - std::sys_common::backtrace::__rust_begin_short_backtrace::h17861fece576b515
                               at /Users/travis/build/rust-lang/rust/src/libstd/panicking.rs:289
                               at /Users/travis/build/rust-lang/rust/src/libstd/panic.rs:392
                               at libtest/lib.rs:1406
                               at /Users/travis/build/rust-lang/rust/src/libstd/sys_common/backtrace.rs:136
  12:        0x10e1ae277 - std::panicking::try::do_call::h4ec3fd68253c3d49
                               at /Users/travis/build/rust-lang/rust/src/libstd/thread/mod.rs:409
                               at /Users/travis/build/rust-lang/rust/src/libstd/panic.rs:313
                               at /Users/travis/build/rust-lang/rust/src/libstd/panicking.rs:310
  13:        0x10e234d1e - panic_unwind::dwarf::eh::read_encoded_pointer::h079a09b4aa438388
                               at libpanic_unwind/lib.rs:105
  14:        0x10e1a35f4 - <F as alloc::boxed::FnBox<A>>::call_box::h0474f3b7214db9a4
                               at /Users/travis/build/rust-lang/rust/src/libstd/panicking.rs:289
                               at /Users/travis/build/rust-lang/rust/src/libstd/panic.rs:392
                               at /Users/travis/build/rust-lang/rust/src/libstd/thread/mod.rs:408
                               at /Users/travis/build/rust-lang/rust/src/liballoc/boxed.rs:642
  15:        0x10e228587 - std::sys_common::thread::start_thread::h5d813c910f870c79
                               at /Users/travis/build/rust-lang/rust/src/liballoc/boxed.rs:652
                               at libstd/sys_common/thread.rs:24
  16:        0x10e2160b8 - std::sys::unix::thread::Thread::new::thread_start::hb499b7779e2b1e18
                               at libstd/sys/unix/thread.rs:90
  17:     0x7fff87657059 - _pthread_body
  18:     0x7fff87656fd6 - _pthread_start


failures:
    cryptographic_primitives::commitments::hash_commitment::tests::test_bit_length_create_commitment

test result: FAILED. 25 passed; 1 failed; 0 ignored; 0 measured; 0 filtered out

error: test failed, to rerun pass '--lib'

Implement elliptic curve trait for P-256

Basically - we need to find a good library that implement P-256 elliptic curve and implement with it the trait:

pub trait ECScalar<SK> {
    fn new_random() -> Self;
    fn get_element(&self) -> SK;
    fn set_element(&mut self, element: SK);
    fn from(n: &BigInt) -> Self;
    fn to_big_int(&self) -> BigInt;
    fn q(&self) -> BigInt;
    fn add(&self, other: &SK) -> Self;
    fn mul(&self, other: &SK) -> Self;
    fn sub(&self, other: &SK) -> Self;
    fn invert(&self) -> Self;
}

pub trait ECPoint<PK, SK>
    where Self: Sized{
    fn generator() -> Self;
    fn get_element(&self) -> PK;
    fn x_coor(&self) -> BigInt;
    fn y_coor(&self) -> BigInt;
    fn bytes_compressed_to_big_int(&self) -> BigInt;
    fn from_bytes(bytes: &[u8]) ->  Result<Self, ErrorKey>;
    fn pk_to_key_slice(&self) -> Vec<u8>;
    fn scalar_mul(self, fe: &SK) -> Self;
    fn add_point(&self, other: &PK) -> Self;
    fn sub_point(&self, other: &PK) -> Self;
    fn from_coor(x: &BigInt, y: &BigInt) -> Self;
}

Add "power" functionality to elliptic curve implementation

Implement PartialOrd trait for all elliptic curves FE structs

For some curves PartialOrd cannot be derived and need to be implemented

Prototypes the use of ff crate for dlog zk proof.

For more information see here: ZenGo-X/multi-party-ecdsa#18 (comment).

Use https://github.com/zkcrypto/ff for https://github.com/KZen-networks/cryptography-utils/blob/master/src/cryptographic_primitives/proofs/dlog_zk_protocol.rs and keep the code in a new branch.

This will help us evaluate the impact of this crate before a full migration.

add sha3 support

should be based on sha3 crate already used for hash based commitment

Clear all warnings

ECPoint improvement

I propose the following changes in ECPoint & ECScalar traits aimed at better user experience, reducing unsafe unwrap()s in curve implementations, based on feedback from people who built their solution on top of curv crate.

1. from_coor(x, y) method should return Result<Self, ErrorKey>.
   Currently it returns Self and panics if point is not on the curve.
2. Add is_on_curve(x, y) -> bool method.
   It might be helpful for early point validation.
3. 1. Add is_at_infinity(&self) -> bool method.
      Currently, the only way to check if the point is at infinity (as I understood) - call x_coor()/y_coor(). If any of them are None, then it's a point at infinity. It works, but it looks unclear in the code.
   2. Another way is to restrict ECPoint to never be at infinity. Then we should add methods add_point_checked, sub_point_checked and scalar_mul_checked which should return Option<Self> (as any of them may produce a point at infinity). Also add_point, sub_point and scalar_mulshould be explicitly marked that they will panic if point at infinity occurs.
      x_coor and y_coor methods will return BigInt instead of Option<BigInt> as they are always present (am I right?).
4. pk_to_key_slice and bytes_compressed_to_big_int methods are a bit confusing.
   They both do the same thing - marshal point to bytes. But the first marshals in uncompressed form (which is unclear until you look at implementation). Also confusing thing is that one method returns Vec<u8>, another returns BigInt. I suggest making both methods to return Vec<u8>. The caller will have to convert to BigInt if it's necessary by calling BigInt::from(...).
   So I suggest to replace both methods with a single one:

   fn to_encoded_point(&self, compressed: bool) -> Vec<u8>

5. Also we should probably restrict ECScalar not to ever be zero. In such a way, the following changes are required:
   1. from(bytes) -> Self method should return Result<Self>
   2. set_element(&self, ...) method should probably also return Result<()> (as we cannot generally guarantee that every PK is proven to be non-zero)
   3. zero() -> Self method should be removed
   4. Add add_checked, mul_checked, sub_checked methods which return Option<Self>. add, mul, sub methods should be explicitly marked that they will panic if zero scalar occurs.
6. Should ECScalar trait leak more info about a curve? Currently, it exposes only the order of G (ECScalar::q()). I would add such enum:

   #[non_exhaustive]
   enum CurveParams {
     Weierstrass {
       a: BigInt, b: BigInt, q: BigInt, p: BigInt, ...
     },
     Montgomery {
       a: BigInt, ...
     }
   }

   And then add method to ECScalar:

   fn params() -> &'static CurveParams

It's a big list of suggestions, but every one may be considered independently.

Delete proofs/dlog_zk_protocol

dlog_zk_protocol.rs was replaced with sigma_dlog.rs. It is maintained for backward compatibility until multi-party-ecdsa will switch.

Test zeroize operations for scalars, points and bigint

In the lib we needed to implement our own Zeroize traits.
It is required to write tests for all zeroize methods.

zeroize bigint: https://github.com/KZen-networks/curv/blob/master/src/arithmetic/big_gmp.rs#L33

zeroize for secp256k1 ECScalar: https://github.com/KZen-networks/curv/blob/master/src/elliptic/curves/secp256_k1.rs#L90

zeroize for secp256k1 ECPoint: https://github.com/KZen-networks/curv/blob/master/src/elliptic/curves/secp256_k1.rs#L271

Same goes for scalars and points of other curves

Review elliptic curve abstraction

review #17

Enforce git-flow, PR and squash commit

Enforce git-flow, PR and squash commit