In Rust, We Trust: The Mighty Schnorr Signature

In Rust, We Trust: The Mighty Schnorr Signature

I have been learning Rust, and it is rock solid when it comes to producing cryptography-related code. So, let’s cut our teeth on the mighty Schnorr signature. This method has the great advantage that we can have multiple signers to a message or a transaction, and end up with a single signature for all the signers. It is now being used in Bitcoin transactions so that we have an efficient signature for a transaction that involves multiple entities.

The patent

In Feb 1989, Claus Schnorr submitted a patent which was assigned to no one. It has 11 claims, and allowed digital signatures to be merged for multiple signers [here]:

The signature

With the Schnorr signature, we create a signature (R,s) for a hash of the message (m). Initially, Peggy (the prover) has a private key r, and her public key will then be:

U=r×G

and where G is the base point on the curve. She then generates random nonce (rt) for the signing of a message and defines a commitment to this value:

Ut=rt×G

Next, with a message (m), she computes a challenge (c) with a hash function of:

c=H(m,Ut)

Next, Peggy computes:

rz=rt+c×r

Peggy then sends Ut (R) and rz (s) to Victor (the verifier). Victor then determines if:

rz×G=Ut+c×U

If they are the same, Peggy has proven that she that the private key that has signed the message. This works because:

rz×G=(rt+c×r)×G=rt×G+(c×r)×G = Ut+c×U

In Rust, We Trust

In this case, we will use the Edwards curve (Ed25519) for our signature. In the following, we use a base point on the curve (G), and generate a random private key for Peggy (the prover) of r. Her public key becomes another point on the curve represented by rG. An outline of the Rust code is [here]:

extern crate curve25519_dalek;
extern crate rand_core;
extern crate sha2;

use curve25519_dalek::constants;

use curve25519_dalek::scalar::Scalar;

use sha2::{Sha256, Digest};

//use rand::thread_rng;
use rand_core::OsRng;
use std::env;

fn main() {

    let mut message="password";
    let args: Vec = env::args().collect();
  
    if args.len() >1 { message = args[1].as_str();}

    // Base point
    let G = &constants::ED25519_BASEPOINT_POINT;

    //Private key (r)
    let r = Scalar::random(&mut OsRng);

    //Public key (rG)
    let U = r*G;

    //Create a random nonce (rt) for each proof
    let rt = Scalar::random(&mut OsRng);

    let Ut = rt*G;

    // Challenge generation
    let mut temp: [u8;32] = [0u8;32];
    let mut hasher = Sha256::new();
    hasher.update(message.as_bytes());
    hasher.update(Ut.compress().to_bytes());
    temp.copy_from_slice(hasher.finalize().as_slice());

    let c = Scalar::from_bytes_mod_order(temp);

    let rz = rt + c*r;

    println!("Message:={:}",message);

    println!("\nG={:}",hex::encode(G.compress().as_bytes()));

    println!("-- Let's pick the private key (r) -- ");
    println!("r= {:}",hex::encode(r.as_bytes()));
    println!("-- Let's generate the public key (rG) -- ");
    println!("\nU=rG= {:}",hex::encode(U.compress().as_bytes()));

    println!("\n-- Let's pick a random value (rt) -- ");
    println!("rt= {:}",hex::encode(rt.as_bytes()));

    println!("Ut=rtG= {:}",hex::encode(Ut.compress().as_bytes()));

    println!("\n-- Let's generate the challenge (c) and response (rz) -- ");
    println!("c= {:}",hex::encode(c.as_bytes()));
    println!("rz=rt+c*r {:}",hex::encode(rz.as_bytes()));

    let p1=rz*G;
    let p2=Ut+c*U;
    println!("\n-- Computing the proof -- ");
    println!("\nrz*G={:}",hex::encode(p1.compress().as_bytes()));
    println!("Ut+c*U{:}",hex::encode(p2.compress().as_bytes()));

    if (p1==p2) {
        println!("Proven!!");   
    }
    else {
        println!("Not proven");
    }

}

A sample run is [here]:

Message:=hello

G=5866666666666666666666666666666666666666666666666666666666666666
-- Let's pick the private key (r) -- 
r= 02bcf35c87b4c3e1d329702efc748691346e9e100c28a02d36d681992db77300
-- Let's generate the public key (rG) -- 

U=rG= 247d8ed740a20fdd8f3d0e462c0ec1b4f6e3758fc421a493f73fb04556cf1960

-- Let's pick a random value (rt) -- 
rt= d951491abb5e6e89378b2ca87273c15635d5391f64f574171a958fe69f0d6a00
Ut=rtG= 4092352a3f1a418cdae8e1e37142a89e60c3da6a96bca5d8e7a8c06e0dfbbdd4

-- Let's generate the challenge (c) and response (rz) -- 
c= 9c26b1852c12ff3be62f70c04f94669955d9043bd9fbc7a87049aff36303e108
rz=rt+c*r a2d9d0efcf58506f3ddfec823d7e79821d3552d1e48bc814720aba7968e1c60d

-- Computing the proof -- 

rz*G=57dea6d0a80aba602903020f3c82813af385340161b62ade9a73a34f1721f11e
Ut+c*U57dea6d0a80aba602903020f3c82813af385340161b62ade9a73a34f1721f11e
Proven!!

Here is the final running code:

https://asecuritysite.com/rust/rust_schnorr

Conclusions

I think the Schnorr signature method is just beautiful … it is mathematical beauty at its best. Something that is so useful, and so trustworthy. If you are interested in Ed25519, try here:

https://asecuritysite.com/golang/ed