Page MenuHomePhabricator

Add CKey::SignSchnorr and CPubKey::VerifySchnorr

Authored by markblundeberg on Jan 19 2019, 20:10.



This is coded for 64-byte schnorr sigs (no flag byte).

Depends on D2345 and D2169 .

Test Plan
  • Tests added that mimic those used for SignECDSA/VerifyECDSA.
  • Test that nonce reuse does not occur for ECDSA and Schnorr.

Diff Detail

rABC Bitcoin ABC
Lint Not Applicable
Tests Not Applicable

Event Timeline

markblundeberg retitled this revision from WIP - add CKey::SignSchnorr and CPubKey::VerifySchnorr to Add CKey::SignSchnorr and CPubKey::VerifySchnorr.Jan 19 2019, 21:20
markblundeberg edited the test plan for this revision. (Show Details)
deadalnix requested changes to this revision.Jan 20 2019, 00:46
deadalnix added inline comments.
207 ↗(On Diff #6754)


219 ↗(On Diff #6754)

Is there a reason why the nonce generation function is passed explicitly ?

Reusing k between ECDSA and Schnorr would leak the private key, so we we should have a test case that sign with both ECDSA and schnorr and ensure they private key extraction fails.

220 ↗(On Diff #6754)

I'm not sure wy these assert rather than return false.

This revision now requires changes to proceed.Jan 20 2019, 00:46
207 ↗(On Diff #6754)

k :-)

219 ↗(On Diff #6754)

Just copying SignECDSA(). No other reason, indeed it doesn't seem necessary.

Yes, the reused-k check is indirectly done in the last two tests of deterministic signing. You can see that for the same key signing the same message, ECDSA deterministically produces r=c6ab5f8acfccc114da39dd5ad0b1ef4d39df6a721e824c22e00b7bc7944a1f78 and Schnorr produces r=e7167ae0afbba6019b4c7fcfe6de79165d555e8295bd72da1b8aa1a5b5430588. But this can definitely be tested more explicitly.

220 ↗(On Diff #6754)

Yep, I dunno, just copying SignECDSA() :-)

improve tests to check against ECDSA-Schnorr nonce reuse ; also fix braces

oops, messed that up. trying again...

markblundeberg added a task: Restricted Maniphest Task.Jan 20 2019, 07:31
deadalnix added inline comments.
46 ↗(On Diff #6756)

You should use .data() here rather than .begin() .

This revision is now accepted and ready to land.Jan 20 2019, 14:53

switched a few begin() to data(), strengthened internal sanity tests

oops, missed some .begin()s, now all changed to .data()

46 ↗(On Diff #6756)

OK, changed -- I'm curious what's the reasoning by the way? It sounds like most C++ people prefer iterators to pointers. e.g.

(My C++ is very rusty, I haven't used it in like 15 years.)

jasonbcox added a subscriber: jasonbcox.
jasonbcox added inline comments.
46 ↗(On Diff #6756)

Iterators have better null safety. "not found" situations tend to return container::end() rather than null.

46 ↗(On Diff #6756)

data provides you a pointer to the storage. begin provides you an iterator, that can anything.

For completeness, &sig[0] is undefined when sig.size() == 0 .

But actually in that case you aren't using memcpy or anything, so iterators are the way to go with std::copy.

OK so I was an idiot and begin is the way to go with std::copy. Most of the code use memcpy so I was confused. Either way it's fine as std::copy knows about pointers.

OK so I was an idiot and begin is the way to go with std::copy. Most of the code use memcpy so I was confused. Either way it's fine as std::copy knows about pointers.

Should I change them back to begin() ? Fine either way for me ...

rebase & fix

  • remove pubkey generation from SignSchnorr()
  • switch from data() to begin() in key_tests

Note: this python code reproduces the first Schnorr deterministic signature

#!/usr/bin/env python3
# Reproduce Bitcoin ABC's deterministic Schnorr signature near end of key_tests.cpp

from ecdsa.numbertheory import jacobi
from ecdsa import SECP256k1
import hashlib
import hmac

G = SECP256k1.generator
p = SECP256k1.curve.p()
n = SECP256k1.order

def sha(b):
    return hashlib.sha256(b).digest()

msg = b"Very deterministic message"
msghash = sha(sha(msg))
assert msghash == bytes.fromhex("5255683da567900bfd3e786ed8836a4e7763c221bf1ac20ece2a5171b9199e8a")
print("msg = "+repr(msg))
print("msghash = "+msghash.hex())

# 5HxWvvfubhXpYYpS3tJkw6fq9jE9j18THftkZjHHfmFiWtmAbrj
# Kwr371tjA9u2rFSMZjTNun2PXXP3WPZu2afRHTcta6KxEUdm1vEw
privkey = 0x12b004fff7f4b69ef8650e767f18f11ede158148b425660723b9f9a66e61f747
print("privkey = "+hex(privkey))
# pubkey point
P = privkey*G
comppub = (b'\x03' if (P.y()&1) else b'\x02') + P.x().to_bytes(32,'big')
assert comppub == bytes.fromhex("030b4c866585dd868a9d62348a9cd008d6a312937048fff31670e7e920cfc7a744")

### Validate the signature found in the code
sig = bytes.fromhex("2c56731ac2f7a7e7f11518fc7722a166b02438924ca9d8b4d1113"
r = int.from_bytes(sig[:32],'big')
s = int.from_bytes(sig[32:],'big')
print("sig.r = " + hex(r))
print("sig.s = " + hex(s))

e = int.from_bytes(sha(r.to_bytes(32, 'big') + comppub + msghash), 'big') % n
print("e = " + hex(e))

checkR = s*G + (n-e)*P
print("chk.rx = " + hex(checkR.x()))
print("chk.ry = " + hex(checkR.y()))
print("jacobi(chk.y) = %+d"%(jacobi(checkR.y(),p)))
assert checkR.x() == r

### Now try to reconstruct the deterministic nonce
# see secp256k1_schnorr_sig_generate_k() in schnorr_impl.h
# and nonce_function_rfc6979() in secp256k1.c
algo16 = b"Schnorr+SHA256  "
ndata = b''
V = b'\x01'*32
K = b'\x00'*32
buf = privkey.to_bytes(32,'big') + msghash + ndata + algo16
# initialize
K = hmac.HMAC(K, V+b'\x00'+buf, 'sha256').digest()
V = hmac.HMAC(K, V, 'sha256').digest()
K = hmac.HMAC(K, V+b'\x01'+buf, 'sha256').digest()
V = hmac.HMAC(K, V, 'sha256').digest()
# generate once
V = hmac.HMAC(K, V, 'sha256').digest()
T = b''

k = int.from_bytes(V, 'big')
print("nonce k = " + hex(k))
R = k*G
print(" (kG).x = " + hex(R.x()))
print("+(kG).y = " + hex(R.y()))
print("jacobi((kG).y) = %+d"%(jacobi(R.y(),p)))
print("-(kG).y = " + hex(p-R.y()))
This revision was automatically updated to reflect the committed changes.