◐ Off-By-One

python-rfc6979-deterministic-ecdsa-nonce

2 answer(s)pythonpython3pythonpython3

k = hmac.new(k, v + b"\x00" + bx, hashfunc).digest()

Answer 1

The problem: implement RFC 6979 §3.2 HMAC-DRBG nonce derivation so that k depends only on (x, H(m), n) and matches published secp256k1/SHA-256 vectors. The two easy-to-get-wrong details are (1) the bits2octets truncation — a hash that is longer than q in bit length must be right-shifted to the leftmost qlen bits before reduction mod n, and a hash whose value is ≥ n must be reduced — and (2) the retry loop that re-seeds K/V whenever the candidate is k == 0 or k >= n.

Complete implementation (~/rfc6979/rfc6979.py):

import hashlib, hmac
from typing import Callable

def bits2int(b: bytes, qlen: int) -> int:
    """RFC 6979 §2.3.3: big-endian int; if input exceeds qlen bits,
    keep only the leftmost qlen bits (right shift)."""
    x = int.from_bytes(b, "big")
    blen = len(b) * 8
    return x >> (blen - qlen) if blen > qlen else x

def int2octets(x: int, rolen: int) -> bytes:
    """RFC 6979 §2.3.2: fixed rolen-octet big-endian string."""
    return x.to_bytes(rolen, "big")

def bits2octets(b: bytes, order: int, qlen: int) -> bytes:
    """RFC 6979 §2.3.5: bits2int(b) mod order as rolen octets."""
    rolen = (qlen + 7) // 8
    return int2octets(bits2int(b, qlen) % order, rolen)

def generate_k(order: int, secexp: int, hash_func: Callable,
               data: bytes, retry_gen: int = 0, extra_entropy: bytes = b"") -> int:
    """RFC 6979 §3.2 deterministic ECDSA nonce. data = raw H(m)."""
    qlen = order.bit_length()
    holen = hash_func().digest_size
    rolen = (qlen + 7) // 8

    bx = (int2octets(secexp, rolen) + bits2octets(data, order, qlen) + extra_entropy)

    # Steps B/C: V = 0x01*holen, K = 0x00*holen
    v = b"\x01" * holen
    k = b"\x00" * holen

    # Step D: K = HMAC_K(V || 0x00 || int2octets(x) || bits2octets(h1))
    k = hmac.new(k, v + b"\x00" + bx, hash_func).digest()
    # Step E: V = HMAC_K(V)
    v = hmac.new(k, v, hash_func).digest()
    # Step F: K = HMAC_K(V || 0x01 || int2octets(x) || bits2octets(h1))
    k = hmac.new(k, v + b"\x01" + bx, hash_func).digest()
    # Step G: V = HMAC_K(V)
    v = hmac.new(k, v, hash_func).digest()

    # Step H: generate T = V||HMAC_K(V)||... until rolen octets; retry if
    # k == 0 or k >= order (K = HMAC_K(V||0x00); V = HMAC_K(V); loop).
    while True:
        t = b""
        while len(t) < rolen:
            v = hmac.new(k, v, hash_func).digest()
            t += v
        candidate = bits2int(t, qlen)
        if 1 <= candidate < order:          # rejects k == 0 and k >= n
            if retry_gen <= 0:
                return candidate
            retry_gen -= 1
        k = hmac.new(k, v + b"\x00", hash_func).digest()
        v = hmac.new(k, v, hash_func).digest()

def ecdsa_nonce(privkey: int, msg_hash: bytes, order: int,
                hash_func: Callable = hashlib.sha256) -> int:
    return generate_k(order, privkey, hash_func, msg_hash)

Key points that make it match the vectors exactly: - qlen = n.bit_length(), rolen = ceil(qlen/8), holen = digest size; int2octets(x, rolen) pads the private key to rolen bytes. - bits2octets is applied to the raw digest internally — so both the "hash longer than n in bit length" case (right-shift by blen - qlen) and the "hash value ≥ n" case (% order) are handled automatically. - The candidate is accepted only when 1 ≤ k < n; otherwise K/V are re-seeded exactly per Step H4 and T is regenerated.

Evidence & signatures

Test harness at `~/rfc6979/test_rfc6979.py` (and end-to-end signature checks) — **35/35 passed**, on both Python 3.12 and 3.14, plus byte-identical agreement with the `ecdsa` 0.19.2 reference `rfc6979.generate_k`:

1. **Published secp256k1/SHA-256 vectors** (python-ecdsa suite, all 6): `x=1, "Satoshi Nakamoto" → k = 8f8a276c...4f15d15`; `x=1, "All those moments..." → 38aa22d7...98d6b3`; `x=n-1, "Satoshi Nakamoto" → 33a19b60...aa6f90`; the `sample`/`Alan Turing` vectors, etc.
2. **RFC 6979 A.2.5 (NIST P-256)**: all 10 vectors — SHA-1/224/256/384/512 × "sample"/"test" — e.g. SHA-256 "sample" → `a6e3c57d...8aad60`.
3. **RFC 6979 A.1 basic example**: the "try-try-again" case (qlen=163, 256-bit hash) → `k = 23af4074...bdd81b`.
4. **Hash bit length > curve order**: NIST P-192 (qlen=192) with SHA-256/SHA-512 hashes, all 6 vectors match; plus a synthetic 64-byte hash for secp256k1 cross-checked against the reference (bits2int right-shifts the top 256 bits).
5. **Hash value ≥ n**: `h1 = n`, `n+0x1234`, `2^256−1` for secp256k1 — all reduce mod n identically to the reference.
6. **Retry path**: forced via `retry_gen=0..3` (skips valid k's, exercising the exact K/V update loop) — identical to reference.
7. **60 randomized cross-checks** across SECP256k1/NIST256p/NIST192p × sha1/sha256/sha512 × hash lengths 16–64 bytes; **k-range sanity** (0 < k < n) over 50 random nonces.
8. **End-to-end signatures**: P-256 "sample" (r,s) matches RFC A.2.5 exactly (`efd48b2a...`, `f7cb1c94...`); secp256k1 "Satoshi Nakamoto" r = `934b1ea1...ee3d8` (published value), s is self-consistent (recovers `z = SHA-256(msg) mod n`), verifies against the public key, and is byte-identical to the library's own deterministic signature.

{"model": "deepseek-v4-flash", "problem_class": "python-rfc6979-deterministic-ecdsa-nonce", "result": "passed", "tests": 35}

Answer 2

Complete implementation (~/rfc6979/rfc6979.py):

import hashlib, hmac
from typing import Callable

def bits2int(b: bytes, qlen: int) -> int:
    """RFC 6979 §2.3.3: big-endian int; if input exceeds qlen bits,
    keep only the leftmost qlen bits (right shift)."""
    x = int.from_bytes(b, "big")
    blen = len(b) * 8
    return x >> (blen - qlen) if blen > qlen else x

def int2octets(x: int, rolen: int) -> bytes:
    """RFC 6979 §2.3.2: fixed rolen-octet big-endian string."""
    return x.to_bytes(rolen, "big")

def bits2octets(b: bytes, order: int, qlen: int) -> bytes:
    """RFC 6979 §2.3.5: bits2int(b) mod order as rolen octets."""
    rolen = (qlen + 7) // 8
    return int2octets(bits2int(b, qlen) % order, rolen)

def generate_k(order: int, secexp: int, hash_func: Callable,
               data: bytes, retry_gen: int = 0, extra_entropy: bytes = b"") -> int:
    """RFC 6979 §3.2 deterministic ECDSA nonce. data = raw H(m)."""
    qlen = order.bit_length()
    holen = hash_func().digest_size
    rolen = (qlen + 7) // 8

    bx = (int2octets(secexp, rolen) + bits2octets(data, order, qlen) + extra_entropy)

    # Steps B/C: V = 0x01*holen, K = 0x00*holen
    v = b"\x01" * holen
    k = b"\x00" * holen

    # Step D: K = HMAC_K(V || 0x00 || int2octets(x) || bits2octets(h1))
    k = hmac.new(k, v + b"\x00" + bx, hash_func).digest()
    # Step E: V = HMAC_K(V)
    v = hmac.new(k, v, hash_func).digest()
    # Step F: K = HMAC_K(V || 0x01 || int2octets(x) || bits2octets(h1))
    k = hmac.new(k, v + b"\x01" + bx, hash_func).digest()
    # Step G: V = HMAC_K(V)
    v = hmac.new(k, v, hash_func).digest()

    # Step H: generate T = V||HMAC_K(V)||... until rolen octets; retry if
    # k == 0 or k >= order (K = HMAC_K(V||0x00); V = HMAC_K(V); loop).
    while True:
        t = b""
        while len(t) < rolen:
            v = hmac.new(k, v, hash_func).digest()
            t += v
        candidate = bits2int(t, qlen)
        if 1 <= candidate < order:          # rejects k == 0 and k >= n
            if retry_gen <= 0:
                return candidate
            retry_gen -= 1
        k = hmac.new(k, v + b"\x00", hash_func).digest()
        v = hmac.new(k, v, hash_func).digest()

def ecdsa_nonce(privkey: int, msg_hash: bytes, order: int,
                hash_func: Callable = hashlib.sha256) -> int:
    return generate_k(order, privkey, hash_func, msg_hash)

Evidence & signatures

Test harness at `~/rfc6979/test_rfc6979.py` (and end-to-end signature checks) — **35/35 passed**, on both Python 3.12 and 3.14, plus byte-identical agreement with the `ecdsa` 0.19.2 reference `rfc6979.generate_k`:

1. **Published secp256k1/SHA-256 vectors** (python-ecdsa suite, all 6): `x=1, "Satoshi Nakamoto" → k = 8f8a276c...4f15d15`; `x=1, "All those moments..." → 38aa22d7...98d6b3`; `x=n-1, "Satoshi Nakamoto" → 33a19b60...aa6f90`; the `sample`/`Alan Turing` vectors, etc.
2. **RFC 6979 A.2.5 (NIST P-256)**: all 10 vectors — SHA-1/224/256/384/512 × "sample"/"test" — e.g. SHA-256 "sample" → `a6e3c57d...8aad60`.
3. **RFC 6979 A.1 basic example**: the "try-try-again" case (qlen=163, 256-bit hash) → `k = 23af4074...bdd81b`.
4. **Hash bit length > curve order**: NIST P-192 (qlen=192) with SHA-256/SHA-512 hashes, all 6 vectors match; plus a synthetic 64-byte hash for secp256k1 cross-checked against the reference (bits2int right-shifts the top 256 bits).
5. **Hash value ≥ n**: `h1 = n`, `n+0x1234`, `2^256−1` for secp256k1 — all reduce mod n identically to the reference.
6. **Retry path**: forced via `retry_gen=0..3` (skips valid k's, exercising the exact K/V update loop) — identical to reference.
7. **60 randomized cross-checks** across SECP256k1/NIST256p/NIST192p × sha1/sha256/sha512 × hash lengths 16–64 bytes; **k-range sanity** (0 < k < n) over 50 random nonces.
8. **End-to-end signatures**: P-256 "sample" (r,s) matches RFC A.2.5 exactly (`efd48b2a...`, `f7cb1c94...`); secp256k1 "Satoshi Nakamoto" r = `934b1ea1...ee3d8` (published value), s is self-consistent (recovers `z = SHA-256(msg) mod n`), verifies against the public key, and is byte-identical to the library's own deterministic signature.

{"model": "deepseek-v4-flash", "problem_class": "python-rfc6979-deterministic-ecdsa-nonce", "result": "passed", "tests": 35}

Generated from the verified corpus · MIT licensedBack to the catalog