Merge pull request #10 from trezor/master

Implementation of RFC 6979: Deterministic ECDSA

5 files changed, 293 insertions, 11 deletions

diff --git a/.gitignore b/.gitignore
index 57b3ce1..c686b2a 100644
--- a/.gitignore
+++ b/.gitignore
@@ -5,3 +5,4 @@
 /ecdsa/_version.py
 /MANIFEST
 /dist/
+*.pyc
diff --git a/ecdsa/keys.py b/ecdsa/keys.py
index 29a1cd7..3ea97c1 100644
--- a/ecdsa/keys.py
+++ b/ecdsa/keys.py
@@ -2,6 +2,7 @@ import binascii
 
 import ecdsa
 import der
+import rfc6979
 from curves import NIST192p, find_curve
 from util import string_to_number, number_to_string, randrange
 from util import sigencode_string, sigdecode_string
@@ -213,7 +214,24 @@ class SigningKey:
     def get_verifying_key(self):
         return self.verifying_key
 
-    def sign(self, data, entropy=None, hashfunc=None, sigencode=sigencode_string):
+    def sign_deterministic(self, data, hashfunc=None, sigencode=sigencode_string):
+        hashfunc = hashfunc or self.default_hashfunc
+        digest = hashfunc(data).digest()
+
+        return self.sign_digest_deterministic(digest, hashfunc=hashfunc, sigencode=sigencode)
+
+    def sign_digest_deterministic(self, digest, hashfunc=None, sigencode=sigencode_string):
+        """
+        Calculates 'k' from data itself, removing the need for strong
+        random generator and producing deterministic (reproducible) signatures.
+        See RFC 6979 for more details.
+        """
+        secexp = self.privkey.secret_multiplier
+        k = rfc6979.generate_k(self.curve.generator, secexp, hashfunc, digest)
+
+        return self.sign_digest(digest, sigencode=sigencode, k=k)
+
+    def sign(self, data, entropy=None, hashfunc=None, sigencode=sigencode_string, k=None):
         """
         hashfunc= should behave like hashlib.sha1 . The output length of the
         hash (in bytes) must not be longer than the length of the curve order
@@ -228,25 +246,32 @@ class SigningKey:
 
         hashfunc = hashfunc or self.default_hashfunc
         h = hashfunc(data).digest()
-        return self.sign_digest(h, entropy, sigencode)
+        return self.sign_digest(h, entropy, sigencode, k)
 
-    def sign_digest(self, digest, entropy=None, sigencode=sigencode_string):
+    def sign_digest(self, digest, entropy=None, sigencode=sigencode_string, k=None):
         if len(digest) > self.curve.baselen:
             raise BadDigestError("this curve (%s) is too short "
                                  "for your digest (%d)" % (self.curve.name,
                                                            8*len(digest)))
         number = string_to_number(digest)
-        r, s = self.sign_number(number, entropy)
+        r, s = self.sign_number(number, entropy, k)
         return sigencode(r, s, self.privkey.order)
 
-    def sign_number(self, number, entropy=None):
+    def sign_number(self, number, entropy=None, k=None):
         # returns a pair of numbers
         order = self.privkey.order
         # privkey.sign() may raise RuntimeError in the amazingly unlikely
         # (2**-192) event that r=0 or s=0, because that would leak the key.
         # We could re-try with a different 'k', but we couldn't test that
         # code, so I choose to allow the signature to fail instead.
-        k = randrange(order, entropy)
-        assert 1 <= k < order
-        sig = self.privkey.sign(number, k)
+
+        # If k is set, it is used directly. In other cases
+        # it is generated using entropy function
+        if k is not None:
+            _k = k
+        else:
+            _k = randrange(order, entropy)
+
+        assert 1 <= _k < order
+        sig = self.privkey.sign(number, _k)
         return sig.r, sig.s
diff --git a/ecdsa/rfc6979.py b/ecdsa/rfc6979.py
new file mode 100644
index 0000000..92509fd
--- /dev/null
+++ b/ecdsa/rfc6979.py
@@ -0,0 +1,91 @@
+'''
+           
+RFC 6979:
+    Deterministic Usage of the Digital Signature Algorithm (DSA) and
+    Elliptic Curve Digital Signature Algorithm (ECDSA)
+
+    http://tools.ietf.org/html/rfc6979
+    
+Many thanks to Coda Hale for his implementation in Go language:
+    https://github.com/codahale/rfc6979
+
+'''
+
+import hmac
+from binascii import hexlify
+from util import number_to_string, number_to_string_crop
+
+def bit_length(num):
+    # http://docs.python.org/dev/library/stdtypes.html#int.bit_length
+    s = bin(num)  # binary representation:  bin(-37) --> '-0b100101'
+    s = s.lstrip('-0b')  # remove leading zeros and minus sign
+    return len(s)  # len('100101') --> 6
+
+def bits2int(data, qlen):
+    x = int(hexlify(data), 16)
+    l = len(data) * 8
+    
+    if l > qlen:
+        return x >> (l-qlen)
+    return x    
+
+def bits2octets(data, order):
+    z1 = bits2int(data, bit_length(order))
+    z2 = z1 - order
+    
+    if z2 < 0:
+        z2 = z1
+        
+    return number_to_string_crop(z2, order)
+    
+# https://tools.ietf.org/html/rfc6979#section-3.2
+def generate_k(generator, secexp, hash_func, data):
+    '''
+        generator - ECDSA generator used in the signature
+        secexp - secure exponent (private key) in numeric form
+        hash_func - reference to the same hash function used for generating hash
+        data - hash in binary form of the signing data 
+    '''
+    
+    qlen = bit_length(generator.order())
+    holen = hash_func().digestsize
+    rolen = (qlen + 7) / 8
+    bx = number_to_string(secexp, generator.order()) + bits2octets(data, generator.order())
+    
+    # Step B
+    v = '\x01' * holen
+
+    # Step C
+    k = '\x00' * holen
+
+    # Step D
+
+    k = hmac.new(k, v+'\x00'+bx, hash_func).digest() 
+
+    # Step E
+    v = hmac.new(k, v, hash_func).digest()
+    
+    # Step F
+    k = hmac.new(k, v+'\x01'+bx, hash_func).digest()
+
+    # Step G
+    v = hmac.new(k, v, hash_func).digest()
+
+    # Step H
+    while True:
+        # Step H1
+        t = ''
+
+        # Step H2
+        while len(t) < rolen:
+            v = hmac.new(k, v, hash_func).digest()
+            t += v
+
+        # Step H3
+        secret = bits2int(t, qlen)
+
+        if secret >= 1 and secret < generator.order():
+            return secret
+
+        k = hmac.new(k, v+'\x00', hash_func).digest()
+        v = hmac.new(k, v, hash_func).digest()
diff --git a/ecdsa/test_pyecdsa.py b/ecdsa/test_pyecdsa.py
index 1f1a9bd..af27871 100644
--- a/ecdsa/test_pyecdsa.py
+++ b/ecdsa/test_pyecdsa.py
@@ -4,7 +4,7 @@ import time
 import shutil
 import subprocess
 from binascii import hexlify, unhexlify
-from hashlib import sha1, sha256
+from hashlib import sha1, sha256, sha512
 
 from keys import SigningKey, VerifyingKey
 from keys import BadSignatureError
@@ -12,8 +12,10 @@ import util
 from util import sigencode_der, sigencode_strings
 from util import sigdecode_der, sigdecode_strings
 from curves import Curve, UnknownCurveError
-from curves import NIST192p, NIST224p, NIST256p, NIST384p, NIST521p
+from curves import NIST192p, NIST224p, NIST256p, NIST384p, NIST521p, SECP256k1
+from ellipticcurve import Point
 import der
+import rfc6979
 
 class SubprocessError(Exception):
     pass
@@ -45,6 +47,27 @@ class ECDSA(unittest.TestCase):
         pub2 = VerifyingKey.from_string(pub.to_string())
         self.failUnless(pub2.verify(sig, data))
 
+    def test_deterministic(self):
+        data = "blahblah"
+        secexp = int("9d0219792467d7d37b4d43298a7d0c05", 16)
+
+        priv = SigningKey.from_secret_exponent(secexp, SECP256k1, sha256)
+        pub = priv.get_verifying_key()
+
+        k = rfc6979.generate_k(SECP256k1.generator, secexp, sha256, sha256(data).digest())
+
+        sig1 = priv.sign(data, k=k)
+        self.failUnless(pub.verify(sig1, data))
+
+        sig2 = priv.sign(data, k=k)
+        self.failUnless(pub.verify(sig2, data))
+
+        sig3 = priv.sign_deterministic(data, sha256)
+        self.failUnless(pub.verify(sig3, data))
+
+        self.failUnlessEqual(sig1, sig2)
+        self.failUnlessEqual(sig1, sig3)
+
     def test_bad_usage(self):
         # sk=SigningKey() is wrong
         self.failUnlessRaises(TypeError, SigningKey)
@@ -478,7 +501,143 @@ class Util(unittest.TestCase):
         self.failUnless(counts[order-1])
         for i in range(1, order):
             print "%3d: %s" % (i, "*"*(counts[i]//100))
-            
+
+class RFC6979(unittest.TestCase):
+    # https://tools.ietf.org/html/rfc6979#appendix-A.1
+    def _do(self, generator, secexp, hsh, hash_func, expected):
+        actual = rfc6979.generate_k(generator, secexp, hash_func, hsh)
+        self.failUnlessEqual(expected, actual)
+
+    def test_SECP256k1(self):
+        '''RFC doesn't contain test vectors for SECP256k1 used in bitcoin.
+        This vector has been computed by Golang reference implementation instead.'''
+        self._do(
+            generator = SECP256k1.generator,
+            secexp = int("9d0219792467d7d37b4d43298a7d0c05", 16),
+            hsh = sha256("sample").digest(),
+            hash_func = sha256,
+            expected = int("8fa1f95d514760e498f28957b824ee6ec39ed64826ff4fecc2b5739ec45b91cd", 16))
+
+    def test_SECP256k1_2(self):
+        self._do(
+            generator=SECP256k1.generator,
+            secexp=int("cca9fbcc1b41e5a95d369eaa6ddcff73b61a4efaa279cfc6567e8daa39cbaf50", 16),
+            hsh=sha256("sample").digest(),
+            hash_func=sha256,
+            expected=int("2df40ca70e639d89528a6b670d9d48d9165fdc0febc0974056bdce192b8e16a3", 16))
+
+    def test_SECP256k1_3(self):
+        self._do(
+            generator=SECP256k1.generator,
+            secexp=0x1,
+            hsh=sha256("Satoshi Nakamoto").digest(),
+            hash_func=sha256,
+            expected=0x8F8A276C19F4149656B280621E358CCE24F5F52542772691EE69063B74F15D15)
+
+    def test_SECP256k1_4(self):
+        self._do(
+            generator=SECP256k1.generator,
+            secexp=0x1,
+            hsh=sha256("All those moments will be lost in time, like tears in rain. Time to die...").digest(),
+            hash_func=sha256,
+            expected=0x38AA22D72376B4DBC472E06C3BA403EE0A394DA63FC58D88686C611ABA98D6B3)
+
+    def test_SECP256k1_5(self):
+        self._do(
+            generator=SECP256k1.generator,
+            secexp=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364140,
+            hsh=sha256("Satoshi Nakamoto").digest(),
+            hash_func=sha256,
+            expected=0x33A19B60E25FB6F4435AF53A3D42D493644827367E6453928554F43E49AA6F90)
+
+    def test_SECP256k1_6(self):
+        self._do(
+            generator=SECP256k1.generator,
+            secexp=0xf8b8af8ce3c7cca5e300d33939540c10d45ce001b8f252bfbc57ba0342904181,
+            hsh=sha256("Alan Turing").digest(),
+            hash_func=sha256,
+            expected=0x525A82B70E67874398067543FD84C83D30C175FDC45FDEEE082FE13B1D7CFDF1)
+
+    def test_1(self):
+        # Basic example of the RFC, it also tests 'try-try-again' from Step H of rfc6979
+        self._do(
+            generator = Point(None, 0, 0, int("4000000000000000000020108A2E0CC0D99F8A5EF", 16)),
+            secexp = int("09A4D6792295A7F730FC3F2B49CBC0F62E862272F", 16),
+            hsh = unhexlify("AF2BDBE1AA9B6EC1E2ADE1D694F41FC71A831D0268E9891562113D8A62ADD1BF"),
+            hash_func = sha256,
+            expected = int("23AF4074C90A02B3FE61D286D5C87F425E6BDD81B", 16))
+
+    def test_2(self):
+        self._do(
+            generator=NIST192p.generator,
+            secexp = int("6FAB034934E4C0FC9AE67F5B5659A9D7D1FEFD187EE09FD4", 16),
+            hsh = sha1("sample").digest(),
+            hash_func = sha1,
+            expected = int("37D7CA00D2C7B0E5E412AC03BD44BA837FDD5B28CD3B0021", 16))
+
+    def test_3(self):
+        self._do(
+            generator=NIST192p.generator,
+            secexp = int("6FAB034934E4C0FC9AE67F5B5659A9D7D1FEFD187EE09FD4", 16),
+            hsh = sha256("sample").digest(),
+            hash_func = sha256,
+            expected = int("32B1B6D7D42A05CB449065727A84804FB1A3E34D8F261496", 16))
+
+    def test_4(self):
+        self._do(
+            generator=NIST192p.generator,
+            secexp = int("6FAB034934E4C0FC9AE67F5B5659A9D7D1FEFD187EE09FD4", 16),
+            hsh = sha512("sample").digest(),
+            hash_func = sha512,
+            expected = int("A2AC7AB055E4F20692D49209544C203A7D1F2C0BFBC75DB1", 16))
+
+    def test_5(self):
+        self._do(
+            generator=NIST192p.generator,
+            secexp = int("6FAB034934E4C0FC9AE67F5B5659A9D7D1FEFD187EE09FD4", 16),
+            hsh = sha1("test").digest(),
+            hash_func = sha1,
+            expected = int("D9CF9C3D3297D3260773A1DA7418DB5537AB8DD93DE7FA25", 16))
+
+    def test_6(self):
+        self._do(
+            generator=NIST192p.generator,
+            secexp = int("6FAB034934E4C0FC9AE67F5B5659A9D7D1FEFD187EE09FD4", 16),
+            hsh = sha256("test").digest(),
+            hash_func = sha256,
+            expected = int("5C4CE89CF56D9E7C77C8585339B006B97B5F0680B4306C6C", 16))
+
+    def test_7(self):
+        self._do(
+            generator=NIST192p.generator,
+            secexp = int("6FAB034934E4C0FC9AE67F5B5659A9D7D1FEFD187EE09FD4", 16),
+            hsh = sha512("test").digest(),
+            hash_func = sha512,
+            expected = int("0758753A5254759C7CFBAD2E2D9B0792EEE44136C9480527", 16))
+
+    def test_8(self):
+        self._do(
+            generator=NIST521p.generator,
+            secexp = int("0FAD06DAA62BA3B25D2FB40133DA757205DE67F5BB0018FEE8C86E1B68C7E75CAA896EB32F1F47C70855836A6D16FCC1466F6D8FBEC67DB89EC0C08B0E996B83538", 16),
+            hsh = sha1("sample").digest(),
+            hash_func = sha1,
+            expected = int("089C071B419E1C2820962321787258469511958E80582E95D8378E0C2CCDB3CB42BEDE42F50E3FA3C71F5A76724281D31D9C89F0F91FC1BE4918DB1C03A5838D0F9", 16))
+
+    def test_9(self):
+        self._do(
+            generator=NIST521p.generator,
+            secexp = int("0FAD06DAA62BA3B25D2FB40133DA757205DE67F5BB0018FEE8C86E1B68C7E75CAA896EB32F1F47C70855836A6D16FCC1466F6D8FBEC67DB89EC0C08B0E996B83538", 16),
+            hsh = sha256("sample").digest(),
+            hash_func = sha256,
+            expected = int("0EDF38AFCAAECAB4383358B34D67C9F2216C8382AAEA44A3DAD5FDC9C32575761793FEF24EB0FC276DFC4F6E3EC476752F043CF01415387470BCBD8678ED2C7E1A0", 16))
+
+    def test_10(self):
+        self._do(
+            generator=NIST521p.generator,
+            secexp = int("0FAD06DAA62BA3B25D2FB40133DA757205DE67F5BB0018FEE8C86E1B68C7E75CAA896EB32F1F47C70855836A6D16FCC1466F6D8FBEC67DB89EC0C08B0E996B83538", 16),
+            hsh = sha512("test").digest(),
+            hash_func = sha512,
+            expected = int("16200813020EC986863BEDFC1B121F605C1215645018AEA1A7B215A564DE9EB1B38A67AA1128B80CE391C4FB71187654AAA3431027BFC7F395766CA988C964DC56D", 16))
 
 def __main__():
     unittest.main()
diff --git a/ecdsa/util.py b/ecdsa/util.py
index 6d37891..9531a3a 100644
--- a/ecdsa/util.py
+++ b/ecdsa/util.py
@@ -157,6 +157,12 @@ def number_to_string(num, order):
     assert len(string) == l, (len(string), l)
     return string
 
+def number_to_string_crop(num, order):
+    l = orderlen(order)
+    fmt_str = "%0" + str(2*l) + "x"
+    string = binascii.unhexlify(fmt_str % num)
+    return string[:l]
+
 def string_to_number(string):
     return int(binascii.hexlify(string), 16)