Schnorr signature (Schnorr 签名)数学原理

来源

一、ECC public key & private key

On secp256k1, a private key is simply a scalar integer value between 0 and ~2256. That’s roughly how many atoms there are in the universe, so we have a big sandbox to play in. We have a special point on the secp256k1 curve called G, which acts as the “origin”. A public key is calculated by adding G on the curve to itself, k a k_a ka​ times. This is the definition of multiplication by a scalar, and is written as: P a = k a G P_a=k_aG Pa​=ka​G

二、Schnorr 签名

A valid digital signature is evidence that the person providing the signature knows the private key corresponding to the public key with which the message is associated, or that they have solved the Discrete Log Problem.

创建签名的流程通常为：

1. Generate a secret once-off number (called a nonce),r.
2. Create a public key, R from r (where R=r.G).
3. Send the following to Bob, your recipient - your message (m), R, and your public key (P=k.G).

The actual signature is created by hashing the combination of all the public information above to create a challenge, e:

e=H(R||P||m)

The hashing function is chosen so that e has the same range as your private keys. In our case, we want something that returns a 256-bit number, so SHA256 is a good choice.

Now the signature is constructed using your private information:

s=r+ke

Bob can now also calculate e(e值Bob也可以计算，因为m,R,P值Bob均已知，且H hash函数Bob也已知), since he already knows m,R,P. But he doesn’t know your private key k, or nonce r. 推理如下： sG=(r+ke)G Multiply out the right-hand side: sG=rG+(kG)e​ Substitute R=rG and P=kG and we have: sG=R+Pe​ Bob 已知s,G,R,P,e，所以可计算sG=R+Pe验证等式是否成立。​ So Bob must just calculate the public key corresponding to the signature (s.G) and check that it equals the right-hand side of the last equation above (R+P.e), all of which Bob already knows.

三、Schnorr 签名中为何要引入随机数r

若不引入随机数r，则 Naïvely sign a message m with

e=H(P||m)

and then the signature would be

s=ek

Now as before, we can check that the signature is valid:

sG=ekG=e(kG)=eP

So far so good. But anyone can read your private key now because s is a scalar, so k=s/e is not hard to do. With the nonce you have to solve k=(s−r)/e, but r is unknown, so this is not a feasible calculation as long as r has been chosen randomly.

Leaving off the nonce is indeed highly insecure.

The Schnorr signature is considered the simplest digital signature scheme to be provably secure in a random oracle model. It is efficient and generates short signatures. It was covered by U.S. Patent 4,995,082, which expired in February 2008.

In cryptography, a random oracle is an oracle (a theoretical black box) that responds to every unique query with a (truly) random response chosen uniformly from its output domain. If a query is repeated it responds the same way every time that query is submitted. Stated differently, a random oracle is a mathematical function chosen uniformly at random, that is, a function mapping each possible query to a (fixed) random response from its output domain.