While I was doing-some-blockchain recently, I have found out that Elliptic Curve algebra does not seem to fit easily into u128, so this is a second attepmt, now done properly, using arkworks-rs.

TL/DR: code.

Note: this is a purely educational example, meant just to show how abstract math can be implemented in real world using propert tools & libraries. Do not use this implementation for anything beyound education. Consider yourself warned.

For a warmup let’s implement DHKE on a secp256k1 elliptic curve (the one used in Bitcoin):

// cargo add rand ark-std ark-ff ark-secp256k1
#[test]
fn test_dhke() {
    use ark_std::{rand, UniformRand};
    use ark_secp256k1::{Affine, Fr as F, G_GENERATOR_X, G_GENERATOR_Y};

    let mut rng = rand::thread_rng();
    let g = Affine::new(G_GENERATOR_X, G_GENERATOR_Y);

    let a = F::rand(&mut rng);
    let ga = g * a;

    let b = F::rand(&mut rng);
    let gb = g * b;

    let one = ga * b;
    let two = gb * a;

    // shared secrets must match
    assert_eq!(one, two);
}

$ cargo test
...
running 1 test
test tests::test_dhke ... ok

Now ECDSA: first add necessary dependencies:

cargo add sha2 hex
cargo add ark-serialize --features derive

So that final dependencies list looks like this:

[dependencies]
ark-ff = "0.4.2"
ark-secp256k1 = "0.4.0"
ark-serialize = { version = "0.4.2", features = ["derive"] }
ark-std = "0.4.0"
hex = "0.4.3"
rand = "0.8.5"
sha2 = "0.10.8"

First step is to derive a Public Key (PK) from a Secret Key (SK) - with SK being a scalar (just a regular number, not yet a point on the curve), it is enough to just multiply curve’s generator point (G) by the scalar to get a point on the curve. Thanks to the Discrete Logarithm problem, inversing this operation (and thus “cracking” a secret key from a public one) is considered extremely computationally intense (for the numbers of a certain size, say 256 bits).

For simplisity the API I’m presenting is going to use raw bytes slices and vectors to represent both public and secret keys.

pub fn get_pk(sk: &[u8]) -> Vec<u8> {
    // Derive Public Key from a Secret Key:
    // 
    // SK - secret key (scalar)
    // G - generator point
    // 
    // PK = G * SK

    let g = Affine::new(G_GENERATOR_X, G_GENERATOR_Y);
    let sk = F::from_be_bytes_mod_order(&sk);
    let pk = g * sk;

    into_bytes(&pk)
}

The signing part, pretty straightforward math:

pub fn sig(sk: &[u8], msg: &[u8]) -> (Vec<u8>, Vec<u8>) {
    // Signing:
    // 
    // SK - secret key
    // PK - public key (PK = SK * G)
    // m - message
    // H - sha256
    // (r, s) - signature
    // 
    // k = H(H(SK) || H(m))
    // R = k * G
    // r = R.x
    // s = k' * (h + r * SK)

    let k = hash(&[&hash(&[sk]), &hash(&[msg])]);
    let k = F::from_be_bytes_mod_order(&k);
    let ki = k.inverse().unwrap();

    let h = hash(&[msg]);
    let h = F::from_be_bytes_mod_order(&h);

    let sk = F::from_be_bytes_mod_order(&sk);

    let g = Affine::new(G_GENERATOR_X, G_GENERATOR_Y);
    let r = g * k;
    let r = Affine::from(r);
    let rx = F::from(r.x.into_bigint());

    let s = ki * (h + rx * sk);

    (into_bytes(&rx), into_bytes(&s))
}

The signature verification part: the whole “trick” is that (h + r * SK) and it’s modular inverse cancel each other out, so the original R is restored and compared to provided with the signature one (x coordinates really).

pub fn ver(pk: &[u8], msg: &[u8], sig: (&[u8], &[u8])) -> bool {
    // Verification
    // 
    // R = (h * s') * G + (r * s') * PK
    // For a valid signature: R.x == sig.r
    //
    // R = (h * s') * G + (r * s') * PK
    // R = (h * s') * G + (r * s') * SK * G
    // R = (h + r * SK) * s' * G
    // R = (h + r * SK) * (k' * (h + r * SK))' * G
    // R = (h + r * SK) * k * (h + r * SK)' * G
    // R = k * G

    let pk: Projective = from_bytes(&pk);

    let (rx, s) = sig;
    let rx: types::Number = from_bytes(rx);
    let s: types::Number = from_bytes(s);
    let si = s.inverse().unwrap();

    let h = hash(&[msg]);
    let h = F::from_be_bytes_mod_order(&h);

    let g = Affine::new(G_GENERATOR_X, G_GENERATOR_Y);
    let r = g * h * si + pk * rx * si;
    let r = Affine::from(r);

    rx == F::from(r.x.into_bigint())
}

Does it work? Checking:

#[test]
fn test_ecdsa() {
    use super::*;

    let sk = "43cdf7c47a34cac01e717ad098bde292c2b3972719da38b7d38706be25706d4f";
    let sk = hex::decode(sk).unwrap();
    let pk = get_pk(&sk);

    let msg = b"the quick brown fox jumps over the lazy dog";
    let (r, s) = sig(&sk, msg);
    assert!(ver(&pk, msg, (&r, &s)));
}

Seems like it does:

$ cargo test
...
running 2 tests
test tests::test_dhke ... ok
test tests::test_ecdsa ... ok
...

To test against random secret keys:

#[test]
fn test_ecdsa() {
    use super::*;
    
    use ark_std::{rand, UniformRand};
    let mut rng = rand::thread_rng();
    let a = F::rand(&mut rng);
    let sk = into_bytes(&a);

    // let sk = "43cdf7c47a34cac01e717ad098bde292c2b3972719da38b7d38706be25706d4f";
    // let sk = hex::decode(sk).unwrap();
    let pk = get_pk(&sk);

    let msg = b"the quick brown fox jumps over the lazy dog";
    let (r, s) = sig(&sk, msg);
    assert!(ver(&pk, msg, (&r, &s)));
}

Full code is on GitHub. Implementations of {from, into}_bytes and hash are pretty straightforward, so not providing them here for brevity. They are present in the repository of course.

ONE NOTE THOUGH:

There is one tricky moment in this implementation. Attentive reader might have noticed weird “flipping” (serializing to bytes and then deserializing back to point) of R happening in both signing and verification parts (let r: Projective = from_bytes(&into_bytes(&r));). The problem I had without such “flip”, was that the original point R was restored (byte representation did match the original one), but x coordinate did not match the original R’s x coordinate, for reasons I don’t quite understand. Pretty sure I must have misused arkworks-rs, and there is a proper way to express it, but I don’t know it yet! Leaving this as an excercise for a reader :) As long as tests pass, I think the educational purposes of this example implementation are achieved.

UPDATE: ‘ONE NOTE’ FIX

Affine::from was necessary to convert R from projective point to an affine one! Thank you Bayram!

References: