schnorr_sign

Documentation

Index

• Variables
• func ComputeSByKEX(curve elliptic.Curve, k, e, x *big.Int) (*big.Int, error)
• func Sign(privateKey *ecdsa.PrivateKey, message []byte) (schnorrSignature []byte, err error)
• func Verify(publicKey *ecdsa.PublicKey, sig []byte, message []byte) (valid bool, err error)

Variables

var (
	GenerateSignatureError = errors.New("Failed to generate the schnorr signature, s = 0 happened.")
	EmptyMessageError      = errors.New("The message to be signed should not be empty")
)

Functions

func ComputeSByKEX

func ComputeSByKEX(curve elliptic.Curve, k, e, x *big.Int) (*big.Int, error)

Compute s = k - e*x

func Sign

func Sign(privateKey *ecdsa.PrivateKey, message []byte) (schnorrSignature []byte, err error)

Schnorr signatures use a particular function, defined as: H'(m, s, e) = H(m || s * G + e * P)

H is a hash function, for instance SHA256 or SM3. s and e are 2 numbers forming the signature itself. m is the message to sign. P is the public key.

To verify the signature, check that the result of H'(m, s, e) is equal to e. Which means that: H(m || s * G + e * P) = e

It's impossible for the others to find such a pair of (s, e) but the signer himself. This is because: P = x * G So the signer is able to get this equation: H(m || s * G + e * x * G) = e = H(m || (s + e * x) * G) It can be considered as: H(m || k * G) = e, where k = s + e * x

This is the original process: 1. Choose a random number k 2. Compute e = H(m || k * G) 3. Because k = s + e * x, k and x (the key factor of the private key) are already known, we can compute s 4. Now we get the SchnorrSignature (e, s)

Note that there is a potential risk for the private key, which also exists in the ECDSA algorithm: "The number k must be random enough." If not, say the same k has been used twice or the second k can be predicted by the first k, the attacker will be able to retrieve the private key (x) This is because:

1. If the same k has been used twice: k = s0 + e0 * x = s1 + e1 * x

The attacker knows: x = (s0 - s1) / (e1 - e0)

2. If the second k1 can be predicted by the first k0: k0 = s0 + e0 * x k1 = s1 + e1 * x

The attacker knows: x = (k1 - k0 + s0 - s1) / (e1 - e0)

So the final process is:

1. Compute k = H(m || x) This makes k unpredictable for anyone who do not know x, therefor it's impossible for the attacker to retrive x by breaking the random number generator of the system, which has happend in the Sony PlayStation 3 firmware attack.
2. Compute e = H(m || k * G)
3. Because k = s + e * x, k and x (the key factor of the private key) are already known, we can compute s = k - e * x Note that if k < e * x, S may be negative, but we need S to be positive. As when we compute e, e = H(m || s * G + e * P) and N * G = 0, and x < N We can change s = k - e * x + e * N, which will guarantee that s will be positive.
4. Now we get the SchnorrSignature (e, s)

func Verify

func Verify(publicKey *ecdsa.PublicKey, sig []byte, message []byte) (valid bool, err error)

In order to verify the signature, only need to check the equation: H'(m, s, e) = H(m || s * G + e * P) = e i.e. whether e is equal to H(m || s * G + e * P)