Quote from: adam3us on February 23, 2015, 08:12:31 AM

Quote from: bitpop on February 22, 2015, 04:21:57 PM

Quote from: Carlton Banks on February 22, 2015, 04:04:55 PM

Quote from: bitpop on February 22, 2015, 04:00:44 PM

What do you mean by deterministic signing?

It takes the random number generator out of the process for generating a signed transaction. Somehow (I do not know the details). It makes it safer, as the signatures can't leak any information (i.e. something to help calculate the private key...) when using weak RNG implementations, plus some other benefits I expect. Also, it's last on the changelog list for 0.93

Oh so instead of random it uses a rolling nonce

Idk, personally I think a bad write can make you reuse an increment and boom you're done. But what do I know.

If it adds a random number, it sounds very good.

No thats not how it works. Deterministic DSA is to use k=H(d,m) as the nonce. In that way if you sign the same message m=H(transaction), you'll get the same signature, so its also stateless.

And this is important because if you reuse k with different messages you reveal a simultaneous equation allowing the private key to be computed. private key is d, public key is Q=dG, address is a=H(Q), signature is (s,r) where s=(h(m)+rd)/k, r=[kG].x, n is the order of the curve.

s=(h(m)+rd)/k mod n
s2=(h(m2)+rd)/k mod n

=> sk = h(m)+rd, s2k = h(m2)+rd
=> (s-s2)k = h(m)-h(m2)
=> k=(h(m)-h(m2))/(s-s2).

now we know k and substituting:

sk=h(m)+rd
=> d=(sk-h(m))/r

There are worse attacks where even knowing a bias of a few bits eg http://www.irisa.fr/celtique/zapalowicz/papers/asiacrypt2014.pdf can result in d being recovered over a modest number of signatures, or that the NIST original DSA standard was partly broken due to a small bias in k generation algorithm by Bleichenbacher, see section 2.2 http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.122.3190&rep=rep1&type=pdf

Avoiding reuse of k is also tricky because that implies log transactional storage in the RNG state. What if the RNG is in a VM, and the VM snapshotted and rolled back? What if the RNG is poorly seeded (eg in a server environment).

The lesson for bitcoin is dont reuse addresses but as there are usability difficulties with that also dont have biases in k, and dont rely on transactional, non-rollbackable storage: hence deterministic DSA.

Adam