schnorr_sign

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) / (e0 - e1)

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) / (e0 - e1)

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
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)