Public and Private keys

The first thing we'll do is create a public and private key from an elliptic curve.

On secp256k1, a private key is simply a scalar integer value between 0 and ~2256. That's roughly how many atoms there are in the universe, so we have a big sandbox to play in.

We have a special point on the secp256k1 curve called G, that acts as the 'origin'. A public key is calculated by adding G on the curve to itself, \( k_a \) times. This is the definition of multiplication by a scalar and is written as such:

$$ P_a = k_a G $$

Let's take an example from this post, where it is known that the public key for 1, when written in uncompressed format is 0479BE667...C47D08FFB10D4B8. The following code snippet demonstrates this:

extern crate libsecp256k1_rs;

use libsecp256k1_rs::{ SecretKey, PublicKey };

#[allow(non_snake_case)]
fn main() {
    // Create the secret key "1"
    let k = SecretKey::from_hex("0000000000000000000000000000000000000000000000000000000000000001").unwrap();
    // Generate the public key, P = k.G
    let pub_from_k = PublicKey::from_secret_key(&k);
    let known_pub = PublicKey::from_hex("0479BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8").unwrap();
    // Compare it to the known value
    assert_eq!(pub_from_k, known_pub);
    println!("Ok")
}

Creating a signature

Reversing ECC math multiplication (i.e. division) is pretty much infeasible when using properly chosen random values for your scalars [4, 5]. This property is called the Discrete Log Problem and is used as the principle behind a lot of cryptography and digital signatures. A valid digital signature is evidence that the person providing the signature knows the private key corresponding to the public key the message is associated with, or that they have solved the Discrete Log Problem.

The approach to creating signatures always follows this recipe:

  1. Generate a secret once-off number (called a nonce), r
  2. Create a public key, R from r (where R = r.G)
  3. Send the following to Bob, your recipient: your message (m), R, and your public key (P = k.G)

The actual signature is created by hashing the combination of all the public information above to create a challenge, e:

$$ e = H(R || P || m) $$

The hashing function is chosen so that e has the same range as your private keys. In our case, we want something that returns a 256 bit number, so SHA256 is a good choice.

Now the signature is constructed using your private information:

$$ s = r + ke $$

Now Bob can also calculate e, since he already knows m, R, P. But he doesn't know your private key, or nonce.

Note: When you construct the signature like this, it's known as a Schnorr signature, which we'll discuss in more detail in the next section. There are other ways of constructing s, such as ECDSA [1], which is used in Bitcoin.

But see this:

$$ sG = (r + ke)G $$

Multiply out the RHS:

$$ sG = rG + (kG)e $$

Substitute \(R = rG \) and \(P = kG \) and we have: $$ sG = R + Pe $$

So Bob must just calculate the public key corresponding to the signature (s.G) and check that it equals the RHS of the last equation above (R + P.e), all of which Bob already knows.

Why do we need the nonce?

Why do we need a nonce in the standard signature?

Let's say we naïvely sign a message m with

$$ e = H(R || m) $$

and then the signature would be \(s = ek \).

Now as before, we can check that the signature is valid:

$$ \begin{align} sG &= ekG \\ &= e(kG) = eP \end{align} $$

So far so good. But anyone can read your private key now because s is a scalar, so \(k = \frac{s}{e} \) is not hard to do. With the nonce you have to solve \( k = (s - r)/e \), but r is unknown, so this is not a feasible calculation as long as r has been chosen randomly.

We can show that leaving off the nonce is indeed highly insecure:

extern crate libsecp256k1_rs as secp256k1;

use secp256k1::{SecretKey, PublicKey, thread_rng, Message};
use secp256k1::schnorr::{ Challenge};

#[allow(non_snake_case)]
fn main() {
    // Create a random private key
    let mut rng = thread_rng();
    let k = SecretKey::random(&mut rng);
    println!("My private key: {}", k);
    let P = PublicKey::from_secret_key(&k);
    let m = Message::hash(b"Meet me at 12").unwrap();
    // Challenge, e = H(P || m)
    let e = Challenge::new(&[&P, &m]).as_scalar().unwrap();

    // Signature
    let s = e * k;

    // Verify the signature
    assert_eq!(PublicKey::from_secret_key(&s), e*P);
    println!("Signature is valid!");
    // But let's try calculate the private key from known information
    let hacked = s * e.inv();
    assert_eq!(k, hacked);
    println!("Hacked key:     {}", k)
}

ECDH

How do parties that want to communicate securely generate a shared secret for encrypting messages? One way is called the Elliptic Curve Diffie-Hellmam exchange (ECDH) which is a simple method for doing just this.

ECDH is used in many places, including the Lightning Network during channel negotiation [2].

Here's how it works. Alice and Bob want to communicate securely. A simple way to do this is to use each other's public keys and calculate

$$ \begin{align} S_a &= k_a P_b \tag{Alice} \\ S_b &= k_b P_a \tag{Bob} \\ \implies S_a = k_a k_b G &\equiv S_b = k_b k_a G \end{align} $$

extern crate libsecp256k1_rs as secp256k1;

use secp256k1::{ SecretKey, PublicKey, thread_rng, Message };

#[allow(non_snake_case)]
fn main() {
    let mut rng = thread_rng();
    // Alice creates a public-private keypair
    let k_a = SecretKey::random(&mut rng);
    let P_a = PublicKey::from_secret_key(&k_a);
    // Bob creates a public-private keypair
    let k_b = SecretKey::random(&mut rng);
    let P_b = PublicKey::from_secret_key(&k_b);
    // They each calculate the shared secret based only on the other party's public information
    // Alice's version:
    let S_a = k_a * P_b;
    // Bob's version:
    let S_b = k_b * P_a;

    assert_eq!(S_a, S_b, "The shared secret is not the same!");
    println!("The shared secret is identical")
}

For security reasons, the private keys are usually chosen at random for each session (you'll see the term ephemeral keys being used), but then we have the problem of not being sure the other party is who they say they are (perhaps due to a man-in-the-middle attack [3]).

Various additional authentication steps can be employed to resolve this problem, which we won't get into here.

References

  • [1] Elliptic Curve Digital Signature Algorithm, Wikipedia, https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm. Accessed 11/10/18.
  • [2] BOLT #8: Encrypted and Authenticated Transport, Lightning RFC, Github. https://github.com/lightningnetwork/lightning-rfc/blob/master/08-transport.md. Accessed 11/10/18.
  • [3] Man in the Middle Attack, Wikipedia, https://en.wikipedia.org/wiki/Man-in-the-middle_attack. Accessed 11/10/18.
  • [4] How does a cryptographically secure random number generator work?, StackOverflow, https://stackoverflow.com/questions/2449594/how-does-a-cryptographically-secure-random-number-generator-work. Accessed 11/10/18.
  • [5] Cryptographically secure pseudorandom number generator, Wikipedia, https://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator. Accessed 11/10/18.