Deterministic signatures as specified by RFC 6979

[gitzhou]

Hi Ofek, this might be not an issue, just wanna get a confirmation.

As described in features, coincurve supports RFC6979 Deterministic signatures.

I've read the document, and following section 3.2, implemented a python demo to generate the "random" k. (tested with the most cases in RFC)

then I use coincurve to sign some message, use the signature to recover the ephemeral key - k coincurve used when signing, and make a comparison (code below) with the k value generated from rfc6979.

The result confused me, some of the cases get the same k, but others are not. Any thoughts about this, did I miss anything?

Thanks!

import hashlib
import random
import string
from random import choices
from typing import Tuple

from coincurve import PrivateKey

from rfc6979 import Rfc6979

# curve order
q = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141


def extended_euclid_gcd(a: int, b: int) -> Tuple[int, int, int]:
    """
    :returns: [gcd(a, b), x, y] where ax + by = gcd(a, b)
    """
    s, old_s = 0, 1
    t, old_t = 1, 0
    r, old_r = b, a
    while r != 0:
        quotient = old_r // r
        old_r, r = r, old_r - quotient * r
        old_s, s = s, old_s - quotient * s
        old_t, t = t, old_t - quotient * t
    return old_r, old_s, old_t


def modular_inverse(num: int, n: int) -> int:
    """
    require num and n are co-prime
    :returns: modular multiplicative inverse of num under n
    """
    # find gcd using Extended Euclid's Algorithm
    gcd, x, y = extended_euclid_gcd(num, n)
    # in case x is negative, we handle it by adding extra n
    # because we know that modular multiplicative inverse of num in range n lies in the range [0, n-1]
    if x < 0:
        x += n
    return x


def deserialize_ecdsa_der(signature: bytes) -> Tuple[int, int]:
    """
    deserialize ECDSA signature from bitcoin strict DER to (r, s)
    """
    try:
        assert signature[0] == 0x30
        assert int(signature[1]) == len(signature) - 2
        # r
        assert signature[2] == 0x02
        r_len = int(signature[3])
        r = int.from_bytes(signature[4: 4 + r_len], 'big')
        # s
        assert signature[4 + r_len] == 0x02
        s_len = int(signature[5 + r_len])
        s = int.from_bytes(signature[-s_len:], 'big')
        return r, s
    except Exception:
        raise ValueError(f'invalid DER encoded {signature.hex()}')


def test(test_count: int):
    failure = 0
    for _ in range(test_count):
        # random a private key
        x = PrivateKey()
        # random a string with digits and ascii letters, with length from 1 to 1024
        # this is the message to sign
        m: bytes = ''.join(choices(string.digits + string.ascii_letters, k=random.randint(1, 1024))).encode()

        e = int.from_bytes(hashlib.sha256(m).digest(), 'big')
        r, s = deserialize_ecdsa_der(x.sign(m))
        # recover the ephemeral key - k used by coincurve sign
        # k = [ (e + rx) / s ] mod q
        mod_inv_s = modular_inverse(s, q)
        k1: int = (mod_inv_s * (e + r * x.to_int())) % q

        # calculate "random" k with rfc6979
        k2 = Rfc6979(q).generate_k(x.to_int(), m)

        if k1 != k2:
            failure += 1
            print(x.to_int(), m.decode())

    print(f'failure: {failure}/{test_count}')


if __name__ == '__main__':
    test(100)

Output:

....

failure: 52/100