The Schnorr signature is used in Bitcoin, and allows an entity to sign for a message with their private key, but then for everyone involved to generate the public key from the signature, and also for it to be verified. In this case we will use the Ed25519 curve, and where Peggy generates a random private key (\(r\)) and a public key of \(rG\), and where \(G\) is the base point on the curve. Peggy takes a message (\(m\)) and generates a challenge based on the message and a random nonce value. From this she can provide proof to Victor (the verifier) that she has the required private key to match her public key. In Curve 25519, we typically do not represent a curve point with a \((u,v)\) value, and use only the \(u\) co-ordinate.
Schnorr Signatures in Rust |
Outline
Initially, Peggy (the prover) has a private key \(r\), and her public key will then be:
\(U = r \times G\)
To sign a new message, she then generates random nonce \(r_t\) and defines a commitment to this value:
\(U_t = r_t \times G\)
Next, with a message (\(m\)), she computes a challenge (\(c\)) with a hash function of:
\(c=H(m,U_t)\)
and where \(H()\) is a hashing function, such as with SHA-256. Next, Peggy computes:
\(r_z = r_t + c \times r\)
Peggy then sends \(U_t\) and \(r_z\) to Victor (the verifier). Victor then determines if:
\(r_z \times G = U_t + c \times U\)
If they are the same, Peggy has proven that she that the private key that has signed the message. This works because:
\(r_z \times G = (r_t + c \times r) \times G = r_t \times G + (c \times r) \times G = U_t + c \times U\)
In this case, we will use the Edwards curve (Ed25519) for our signature. In the following Rust code, 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:
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_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"); } }
Finally we simply build with:
cargo build
A sample run is:
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!!