Sign Schnorr

[LSantos06]

[1] https://en.bitcoin.it/wiki/Schnorr

Schnorr signatures are a proposed future extension that give a new way to generate signatures (R, s) on a hash h.

Given a hash value h, hash function f(), private key x, group generator G, and public key P=xG, we can generate a Schnorr signature on h as follows:

Choose a random nonce k. Let R=Gk, and let s = k - f(h . R . P)x. The Schnorr signature is the pair (R, s). Note that R is a public key, so would require 33 bytes to represent (32 bytes + 1 bit indicating "even" vs "odd").

[2] https://github.com/bitcoin-core/secp256k1/blob/04c8ef36ad35e846ac27157021a78f79465f2a22/src/modules/schnorr/schnorr_impl.h

Signing:

Inputs: 32-byte message m, 32-byte scalar key x (!=0), 32-byte scalar nonce k (!=0)

Compute point R = k * G. Reject nonce if R's y coordinate is odd (or negate nonce).
Compute 32-byte r, the serialization of R's x coordinate.
Compute scalar h = Hash(r || m). Reject nonce if h == 0 or h >= order.
Compute scalar s = k - h * x.
The signature is (r, s).

[3] https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki

Input:

- The secret key d: an integer in the range 1..n-1.
- The message m: a 32-byte array

To sign m for public key dG:

- Let k' = int(hash(bytes(d) || m)) mod n[8].
- Fail if k' = 0.
- Let R = k'G.
- Let k = k' if jacobi(y(R)) = 1, otherwise let k = n - k' .
- Let e = int(hash(bytes(x(R)) || bytes(dG) || m)) mod n.
- The signature is bytes(x(R)) || bytes(k + ed mod n).

[LSantos06]

- Let k' = int(hash(bytes(d) || m)) mod n.
- Fail if k' = 0.
- Let R = k'G.

[1] https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki#cite_note-8
[2] https://github.com/bitcoin-core/secp256k1/blob/aa15154a4882a40227a238edef830b85a4942d4f/src/scalar_4x64.h#L12
[3] https://github.com/bitcoin-core/secp256k1/blob/master/src/scalar.h#L35
[4] https://github.com/bitcoin-core/secp256k1/blob/1e6f1f5ad5e7f1e3ef79313ec02023902bf8175c/src/ecmult_gen.h#L39
[5] https://github.com/bitcoin-core/secp256k1/blob/e34ceb333b1c0e6f4115ecbb80c632ac1042fa49/src/ecmult_gen_impl.h#L124
[6] https://github.com/bitcoin-core/secp256k1/blob/e34ceb333b1c0e6f4115ecbb80c632ac1042fa49/src/group.h#L13
[7] https://github.com/bitcoin-core/secp256k1/blob/ba698f883b7de4f89be073aa8713ae736f5e770d/src/field_5x52.h#L12
[8] https://github.com/bitcoin-core/secp256k1/blob/1e6f1f5ad5e7f1e3ef79313ec02023902bf8175c/src/field.h#L10

- Let k = k' if jacobi(y(R)) = 1, otherwise let k = n - k'.
- Let e = int(hash(bytes(x(R)) || bytes(dG) || m)) mod n.
- The signature is bytes(x(R)) || bytes(k + ed mod n).

[1] https://github.com/bitcoin-core/secp256k1/blob/master/src/field.h#L76
[2] https://github.com/bitcoin-core/secp256k1/blob/1e6f1f5ad5e7f1e3ef79313ec02023902bf8175c/src/num_gmp.h#L14
[3] https://github.com/bitcoin-core/secp256k1/blob/master/src/scalar.h#L89
[4] https://github.com/bitcoin-core/secp256k1/blob/1e6f1f5ad5e7f1e3ef79313ec02023902bf8175c/src/num.h#L25
[5] https://github.com/bitcoin-core/secp256k1/blob/master/src/scalar.h#L35
[6] https://github.com/bitcoin-core/secp256k1/blob/1e6f1f5ad5e7f1e3ef79313ec02023902bf8175c/src/num.h#L35
[7] https://github.com/bitcoin-core/secp256k1/blob/master/src/scalar.h#L66
[8] https://github.com/bitcoin-core/secp256k1/blob/master/src/scalar.h#L50
[9] https://github.com/bitcoin-core/secp256k1/blob/master/src/scalar.h#L44
[10] https://github.com/bitcoin-core/secp256k1/blob/master/src/scalar.h#L41