#!/usr/bin/env python3
"""Verify a BlckRhino Send Forensic Delivery Record. Offline, and on its own.

USAGE
    python3 verify_delivery_record.py RECORD.json --keys KEYS.json
    python3 verify_delivery_record.py RECORD.json --keys KEYS.json --json
    python3 verify_delivery_record.py --help

    RECORD.json   the export downloaded from a Delivery Proof or a Receipt page
    KEYS.json     BlckRhino's published signing keys (linked from the export's
                  "key_history_url" field, and from every record page)

    Exit status   0  every check passed
                  1  at least one check failed
                  2  the arguments or the files could not be used at all

WHAT THIS TOOL IS
    docs/Send2.0_spec.md §3.4 requires that verifying a delivery record does not
    require trusting BlckRhino's website. This file is that requirement,
    implemented: **it is one file, it imports nothing but the Python standard
    library, and it talks to no network and no database.** There is no pip
    install, no BlckRhino code, no service to be reachable. Copy it to a machine
    with Python 3.9 or newer, copy the two JSON files next to it, and run it.

    That constraint is why the cryptography below is written out longhand rather
    than imported. Ed25519 verification is RFC 8032; the RFC 3161 timestamp token
    is parsed with a small DER reader and its signature checked with either
    RSASSA-PKCS1-v1_5 (RFC 8017) or ECDSA over the NIST prime curves
    (FIPS 186-4) — all of it verification-only, none of it handling a secret. A
    dependency would be less code and more trust, and trust is the thing being
    minimised.

WHAT IT CHECKS, AND WHAT EACH ANSWER MEANS
    1. canonical      the record bytes are the canonical form (see below). A
                      failure means the document was reformatted or edited.
    2. digest         SHA-256 of the record equals the hash the export claims.
    3. signature      the published BlckRhino key named in the export signed
                      exactly this digest. A failure means BlckRhino did not
                      issue this document — or one byte of it has changed.
    4. key in service the independent timestamp falls inside the published
                      validity window of that key. A failure means the record is
                      dated after the key was retired or declared compromised.
    5. timestamp      the RFC 3161 token verifies against the timestamp
                      authority's certificate, which travels inside the export.
    6. timestamp      …and the token is about *this* document. A genuine token
       binding        over a different document fails here and passes (5): that
                      is the substitution a forger reaches for.

WHAT A PASS DOES NOT MEAN
    That the files reached a named human. The record proves delivery to a party
    who demonstrated control of an email address (spec §3.1). It also does not
    make the timestamp authority trustworthy: this tool checks that the token was
    signed by the certificate stored with the record and attests to this digest.
    Whether that authority is one you accept is your decision, taken against your
    own trust store — the certificate is printed so you can look at it.

THE CANONICAL FORM (why re-serialising must reproduce the bytes)
    A signature is over bytes, so the bytes have to be reconstructible from the
    document by anyone. BlckRhino's rule, published in
    docs/DELIVERY-RECORD-SCHEMA.md, is exactly:

        json.dumps(obj, sort_keys=True, separators=(",", ":"),
                   ensure_ascii=False).encode("utf-8")

    keys sorted by code point, no insignificant whitespace, no trailing newline,
    integers only (never a float), timestamps to the second with a trailing "Z".
    This tool re-serialises the record it was given under that rule and hashes
    the result, so it never has to trust the export's own idea of its bytes.
"""

from __future__ import annotations

import argparse
import base64
import binascii
import hashlib
import json
import sys
from datetime import datetime, timedelta, timezone
from typing import Any

TOOL_VERSION = "1.0"

#: The domain separator BlckRhino signs under. Published in the key history file
#: as ``signed_payload`` so an independent implementer never has to read this
#: source: the signed bytes are this prefix, the purpose, a colon, and the
#: lowercase hex of the record digest.
PAYLOAD_PREFIX = b"blckrhino-send/v1:"
DEFAULT_PURPOSE = "delivery-record"
ALGORITHM_ED25519 = "Ed25519"

#: Object identifiers this tool needs to recognise. Written as dotted strings
#: because that is how a reader checks them against an RFC.
OID_SIGNED_DATA = "1.2.840.113549.1.7.2"
OID_TST_INFO = "1.2.840.113549.1.9.16.1.4"
OID_CONTENT_TYPE = "1.2.840.113549.1.9.3"
OID_MESSAGE_DIGEST = "1.2.840.113549.1.9.4"
OID_SHA256 = "2.16.840.1.101.3.4.2.1"
OID_SHA384 = "2.16.840.1.101.3.4.2.2"
OID_SHA512 = "2.16.840.1.101.3.4.2.3"
OID_RSA = "1.2.840.113549.1.1.1"
OID_SHA256_RSA = "1.2.840.113549.1.1.11"
OID_SHA384_RSA = "1.2.840.113549.1.1.12"
OID_SHA512_RSA = "1.2.840.113549.1.1.13"
OID_EC_PUBLIC_KEY = "1.2.840.10045.2.1"
OID_SHA256_ECDSA = "1.2.840.10045.4.3.2"
OID_SHA384_ECDSA = "1.2.840.10045.4.3.3"
OID_SHA512_ECDSA = "1.2.840.10045.4.3.4"
OID_P256 = "1.2.840.10045.3.1.7"
OID_P384 = "1.3.132.0.34"
OID_P521 = "1.3.132.0.35"
OID_ED25519 = "1.3.101.112"
OID_EXT_EKU = "2.5.29.37"
OID_KP_TIMESTAMPING = "1.3.6.1.5.5.7.3.8"

#: Hash OIDs → the hashlib name and the DigestInfo prefix PKCS#1 v1.5 expects.
#: SHA-1 and MD5 are deliberately absent: a timestamp token signed with either
#: is reported as an unsupported algorithm rather than quietly accepted.
_DIGESTS: dict[str, str] = {
    OID_SHA256: "sha256",
    OID_SHA384: "sha384",
    OID_SHA512: "sha512",
}
_RSA_SIGNATURES: dict[str, str] = {
    OID_SHA256_RSA: "sha256",
    OID_SHA384_RSA: "sha384",
    OID_SHA512_RSA: "sha512",
}
_ECDSA_SIGNATURES: dict[str, str] = {
    OID_SHA256_ECDSA: "sha256",
    OID_SHA384_ECDSA: "sha384",
    OID_SHA512_ECDSA: "sha512",
}

#: NIST prime curves, as ``(p, b, Gx, Gy, n)``. ``a`` is ``-3 mod p`` for all
#: three, so it is not stored. These are the published FIPS 186-4 / SEC 2
#: parameters.
#:
#: Three deliberate choices about *how* they are written, because a mistyped
#: digit here gives a verifier that rejects good evidence — or, far worse, one
#: doing arithmetic in some other group where a forgery might pass:
#:
#: * each ``p`` is its Solinas form rather than a wall of hex, since
#:   ``2**521 - 1`` cannot be mistyped the way 131 hex digits can (it was);
#: * the remaining constants are grouped in eights, matching how FIPS prints
#:   them, so they can be checked against the standard by eye;
#: * and ``tests/test_offline_verifier.py`` proves each row internally
#:   consistent — G lies on the curve and n·G is the point at infinity — as well
#:   as cross-checking against a signature from ``cryptography``. The internal
#:   check is the one that matters, because it needs no library to be right.
_CURVES: dict[str, tuple[int, int, int, int, int]] = {
    OID_P256: (
        2**256 - 2**224 + 2**192 + 2**96 - 1,
        0x5AC635D8_AA3A93E7_B3EBBD55_769886BC_651D06B0_CC53B0F6_3BCE3C3E_27D2604B,
        0x6B17D1F2_E12C4247_F8BCE6E5_63A440F2_77037D81_2DEB33A0_F4A13945_D898C296,
        0x4FE342E2_FE1A7F9B_8EE7EB4A_7C0F9E16_2BCE3357_6B315ECE_CBB64068_37BF51F5,
        0xFFFFFFFF_00000000_FFFFFFFF_FFFFFFFF_BCE6FAAD_A7179E84_F3B9CAC2_FC632551,
    ),
    OID_P384: (
        2**384 - 2**128 - 2**96 + 2**32 - 1,
        0xB3312FA7_E23EE7E4_988E056B_E3F82D19_181D9C6E_FE814112_0314088F_5013875A_C656398D_8A2ED19D_2A85C8ED_D3EC2AEF,  # noqa: E501
        0xAA87CA22_BE8B0537_8EB1C71E_F320AD74_6E1D3B62_8BA79B98_59F741E0_82542A38_5502F25D_BF55296C_3A545E38_72760AB7,  # noqa: E501
        0x3617DE4A_96262C6F_5D9E98BF_9292DC29_F8F41DBD_289A147C_E9DA3113_B5F0B8C0_0A60B1CE_1D7E819D_7A431D7C_90EA0E5F,  # noqa: E501
        0xFFFFFFFF_FFFFFFFF_FFFFFFFF_FFFFFFFF_FFFFFFFF_FFFFFFFF_C7634D81_F4372DDF_581A0DB2_48B0A77A_ECEC196A_CCC52973,  # noqa: E501
    ),
    OID_P521: (
        2**521 - 1,
        0x0051_953EB961_8E1C9A1F_929A21A0_B68540EE_A2DA725B_99B315F3_B8B48991_8EF109E1_56193951_EC7E937B_1652C0BD_3BB1BF07_3573DF88_3D2C34F1_EF451FD4_6B503F00,  # noqa: E501
        0x00C6_858E06B7_0404E9CD_9E3ECB66_2395B442_9C648139_053FB521_F828AF60_6B4D3DBA_A14B5E77_EFE75928_FE1DC127_A2FFA8DE_3348B3C1_856A429B_F97E7E31_C2E5BD66,  # noqa: E501
        0x0118_39296A78_9A3BC004_5C8A5FB4_2C7D1BD9_98F54449_579B4468_17AFBD17_273E662C_97EE7299_5EF42640_C550B901_3FAD0761_353C7086_A272C240_88BE9476_9FD16650,  # noqa: E501
        0x01FF_FFFFFFFF_FFFFFFFF_FFFFFFFF_FFFFFFFF_FFFFFFFF_FFFFFFFF_FFFFFFFF_FFFFFFFA_51868783_BF2F966B_7FCC0148_F709A5D0_3BB5C9B8_899C47AE_BB6FB71E_91386409,  # noqa: E501
    ),
}
#: DER of ``DigestInfo`` minus the digest itself, per RFC 8017 §9.2 note 1.
_DIGEST_INFO_PREFIX: dict[str, bytes] = {
    "sha256": bytes.fromhex("3031300d060960864801650304020105000420"),
    "sha384": bytes.fromhex("3041300d060960864801650304020205000430"),
    "sha512": bytes.fromhex("3051300d060960864801650304020305000440"),
}

#: Common X.500 attribute types, for printing a certificate subject a person can
#: read. Anything not listed prints as its dotted OID, which is honest.
_NAME_ATTRS: dict[str, str] = {
    "2.5.4.3": "CN",
    "2.5.4.6": "C",
    "2.5.4.7": "L",
    "2.5.4.8": "ST",
    "2.5.4.10": "O",
    "2.5.4.11": "OU",
    "1.2.840.113549.1.9.1": "E",
}


# =========================================================================
# Canonical JSON (contract C1)
# =========================================================================


class RecordError(Exception):
    """The document handed over is not a well-formed delivery record."""


def _reject_floats(node: Any, path: str) -> None:
    """Refuse a float anywhere in the record.

    Not pedantry: floats do not round-trip identically between languages, so a
    record containing one would hash differently in a Python verifier and a Go
    one. BlckRhino's generator cannot emit a float, which means a record that
    contains one did not come out of it — worth saying plainly rather than
    reporting as a signature failure.
    """
    if isinstance(node, float):
        raise RecordError(f"floating-point number at {path or 'the top level'}")
    if isinstance(node, dict):
        for key, value in node.items():
            _reject_floats(value, f"{path}.{key}" if path else str(key))
    elif isinstance(node, (list, tuple)):
        for index, value in enumerate(node):
            _reject_floats(value, f"{path}[{index}]")


def canonical_bytes(record: Any) -> bytes:
    """The exact bytes the record digest is taken over (contract C1)."""
    if not isinstance(record, dict):
        raise RecordError("a delivery record is a JSON object")
    _reject_floats(record, "")
    return json.dumps(
        record, sort_keys=True, separators=(",", ":"), ensure_ascii=False
    ).encode("utf-8")


# =========================================================================
# DER: just enough of X.690 to read a certificate and a CMS token
# =========================================================================


class DerError(Exception):
    """The DER structure could not be read. Always a verdict, never a crash."""


class Elem:
    """One DER element: its tag, its value octets, and its complete encoding.

    ``raw`` is kept because two of the checks below hash or re-tag an element
    exactly as it appeared on the wire, and reconstructing an encoding is how a
    verifier ends up disagreeing with the signer over a length byte.
    """

    __slots__ = ("tag", "content", "raw")

    def __init__(self, tag: int, content: bytes, raw: bytes) -> None:
        self.tag = tag
        self.content = content
        self.raw = raw

    def __repr__(self) -> str:  # pragma: no cover - debugging aid
        return f"<Elem tag=0x{self.tag:02x} len={len(self.content)}>"


def der_read(data: bytes, offset: int = 0) -> tuple[Elem, int]:
    """Read one element at ``offset``. Returns the element and the next offset."""
    if offset >= len(data):
        raise DerError("truncated: no tag")
    tag = data[offset]
    if tag & 0x1F == 0x1F:
        # High-tag-number form. Nothing in a timestamp token or an X.509
        # certificate uses it, so refusing is more honest than half-supporting.
        raise DerError("high-tag-number form is not supported")
    position = offset + 1
    if position >= len(data):
        raise DerError("truncated: no length")
    first = data[position]
    position += 1
    if first < 0x80:
        length = first
    else:
        count = first & 0x7F
        if count == 0:
            raise DerError("indefinite length is not valid DER")
        if position + count > len(data):
            raise DerError("truncated length")
        length = int.from_bytes(data[position : position + count], "big")
        position += count
    end = position + length
    if end > len(data):
        raise DerError("truncated content")
    return Elem(tag, data[position:end], data[offset:end]), end


def der_children(element: Elem) -> list[Elem]:
    """Every element inside a constructed one, in order."""
    items: list[Elem] = []
    offset = 0
    while offset < len(element.content):
        child, offset = der_read(element.content, offset)
        items.append(child)
    return items


def der_parse(data: bytes) -> Elem:
    element, offset = der_read(data, 0)
    if offset != len(data):
        raise DerError("trailing bytes after the top-level element")
    return element


def der_oid(element: Elem) -> str:
    """Decode an OBJECT IDENTIFIER to its dotted form."""
    if element.tag != 0x06 or not element.content:
        raise DerError("not an object identifier")
    body = element.content
    first = body[0]
    parts = [str(first // 40), str(first % 40)]
    value = 0
    for byte in body[1:]:
        value = (value << 7) | (byte & 0x7F)
        if not byte & 0x80:
            parts.append(str(value))
            value = 0
    return ".".join(parts)


def der_int(element: Elem) -> int:
    if element.tag != 0x02:
        raise DerError("not an integer")
    return int.from_bytes(element.content, "big", signed=True)


def der_bitstring(element: Elem) -> bytes:
    """The payload of a BIT STRING, which must be a whole number of octets."""
    if element.tag != 0x03 or not element.content:
        raise DerError("not a bit string")
    if element.content[0] != 0:
        raise DerError("bit string is not octet-aligned")
    return element.content[1:]


def der_time(element: Elem) -> datetime:
    """A UTCTime or GeneralizedTime as an aware UTC datetime.

    Sub-second precision is truncated rather than refused: a real timestamp
    authority is entitled to emit it, and the record's own timestamps are
    second-precision by contract, so keeping the extra digits would only invite
    a comparison that fails for no reason.
    """
    text = element.content.decode("ascii", "replace")
    if element.tag == 0x17:  # UTCTime: YYMMDDhhmmssZ
        if len(text) < 13 or not text.endswith("Z"):
            raise DerError(f"unsupported UTCTime {text!r}")
        year = int(text[0:2])
        year += 2000 if year < 50 else 1900
        stem = f"{year:04d}{text[2:12]}"
    elif element.tag == 0x18:  # GeneralizedTime: YYYYMMDDhhmmss[.f]Z
        if len(text) < 15 or not text.endswith("Z"):
            raise DerError(f"unsupported GeneralizedTime {text!r}")
        stem = text[0:14]
    else:
        raise DerError("not a time")
    try:
        return datetime.strptime(stem, "%Y%m%d%H%M%S").replace(tzinfo=timezone.utc)
    except ValueError as error:
        raise DerError(f"unreadable time {text!r}") from error


# =========================================================================
# Ed25519 verification (RFC 8032), written out so there is no dependency
# =========================================================================

_P = 2**255 - 19
_L = 2**252 + 27742317777372353535851937790883648493
_D = -121665 * pow(121666, _P - 2, _P) % _P
_SQRT_M1 = pow(2, (_P - 1) // 4, _P)


def _recover_x(y: int, sign: int) -> int | None:
    """The curve point's x for a given y and sign bit, or ``None`` if there is none."""
    if y >= _P:
        return None
    x2 = (y * y - 1) * pow(_D * y * y + 1, _P - 2, _P) % _P
    if x2 == 0:
        return None if sign else 0
    x = pow(x2, (_P + 3) // 8, _P)
    if (x * x - x2) % _P != 0:
        x = x * _SQRT_M1 % _P
    if (x * x - x2) % _P != 0:
        return None
    if (x & 1) != sign:
        x = _P - x
    return x


def _point_add(point: tuple[int, int, int, int], other: tuple[int, int, int, int]):
    """Addition in extended twisted-Edwards coordinates (RFC 8032 §5.1.4)."""
    a = (point[1] - point[0]) * (other[1] - other[0]) % _P
    b = (point[1] + point[0]) * (other[1] + other[0]) % _P
    c = 2 * point[3] * other[3] * _D % _P
    d = 2 * point[2] * other[2] % _P
    e, f, g, h = b - a, d - c, d + c, b + a
    return (e * f % _P, g * h % _P, f * g % _P, e * h % _P)


def _point_mul(scalar: int, point: tuple[int, int, int, int]):
    result = (0, 1, 1, 0)
    while scalar > 0:
        if scalar & 1:
            result = _point_add(result, point)
        point = _point_add(point, point)
        scalar >>= 1
    return result


def _point_equal(point: tuple[int, int, int, int], other: tuple[int, int, int, int]) -> bool:
    if (point[0] * other[2] - other[0] * point[2]) % _P != 0:
        return False
    return (point[1] * other[2] - other[1] * point[2]) % _P == 0


_G_Y = 4 * pow(5, _P - 2, _P) % _P
_G_X = _recover_x(_G_Y, 0)
assert _G_X is not None  # the curve's base point is not optional
_G = (_G_X, _G_Y, 1, _G_X * _G_Y % _P)


def _point_decompress(data: bytes) -> tuple[int, int, int, int] | None:
    if len(data) != 32:
        return None
    y = int.from_bytes(data, "little")
    sign = y >> 255
    y &= (1 << 255) - 1
    x = _recover_x(y, sign)
    if x is None:
        return None
    return (x, y, 1, x * y % _P)


def ed25519_verify(public_key: bytes, signature: bytes, message: bytes) -> bool:
    """Verify an Ed25519 signature. Returns a boolean; never raises."""
    if len(public_key) != 32 or len(signature) != 64:
        return False
    point_a = _point_decompress(public_key)
    if point_a is None:
        return False
    encoded_r = signature[:32]
    point_r = _point_decompress(encoded_r)
    if point_r is None:
        return False
    scalar = int.from_bytes(signature[32:], "little")
    if scalar >= _L:
        # A non-canonical S is rejected, as RFC 8032 §5.1.7 requires: accepting
        # it would make signatures malleable.
        return False
    challenge = (
        int.from_bytes(
            hashlib.sha512(encoded_r + public_key + message).digest(), "little"
        )
        % _L
    )
    return _point_equal(
        _point_mul(scalar, _G), _point_add(point_r, _point_mul(challenge, point_a))
    )


def ed25519_public_key_from_pem(pem: str) -> bytes:
    """The 32 raw key bytes inside a PEM SubjectPublicKeyInfo."""
    der = pem_block(pem, "PUBLIC KEY")
    if der is None:
        raise DerError("not a PEM public key")
    spki = der_parse(der)
    children = der_children(spki)
    if len(children) != 2:
        raise DerError("malformed SubjectPublicKeyInfo")
    algorithm = der_children(children[0])
    if not algorithm or der_oid(algorithm[0]) != OID_ED25519:
        raise DerError("public key is not Ed25519")
    key = der_bitstring(children[1])
    if len(key) != 32:
        raise DerError("Ed25519 public key is not 32 bytes")
    return key


def signed_payload(digest: bytes, purpose: str) -> bytes:
    """The exact bytes BlckRhino's signing service is asked to sign.

    Domain-separated on purpose: a signature over a bare hash could be replayed
    as a signature over anything else that happened to hash the same way in some
    other protocol. The construction is published, so this line is a
    reimplementation of a specification rather than a copy of an implementation.
    """
    return PAYLOAD_PREFIX + purpose.encode("ascii") + b":" + digest.hex().encode("ascii")


# =========================================================================
# PEM, RSA and X.509 — only what a timestamp token needs
# =========================================================================


def pem_blocks(text: str, label: str) -> list[bytes]:
    """Every ``-----BEGIN <label>-----`` block in a PEM bundle, as DER."""
    marker_begin = f"-----BEGIN {label}-----"
    marker_end = f"-----END {label}-----"
    blocks: list[bytes] = []
    remainder = text or ""
    while marker_begin in remainder:
        _, _, rest = remainder.partition(marker_begin)
        body, found, remainder = rest.partition(marker_end)
        if not found:
            break
        try:
            blocks.append(base64.b64decode("".join(body.split())))
        except (binascii.Error, ValueError):
            continue
    return blocks


def pem_block(text: str, label: str) -> bytes | None:
    blocks = pem_blocks(text, label)
    return blocks[0] if blocks else None


class Certificate:
    """The handful of certificate fields a timestamp check actually needs."""

    __slots__ = ("der", "subject", "issuer", "serial", "public_key", "eku", "not_before", "not_after")

    def __init__(self, der: bytes) -> None:
        self.der = der
        certificate = der_parse(der)
        tbs = der_children(certificate)[0]
        fields = der_children(tbs)
        index = 1 if fields and fields[0].tag == 0xA0 else 0
        self.serial = der_int(fields[index])
        self.issuer = _name_text(fields[index + 2])
        validity = der_children(fields[index + 3])
        self.not_before = der_time(validity[0])
        self.not_after = der_time(validity[1])
        self.subject = _name_text(fields[index + 4])
        self.public_key = fields[index + 5]
        self.eku = _extended_key_usage(fields[index + 6 :])

    @property
    def permits_timestamping(self) -> bool:
        """RFC 3161 §2.3: the signing certificate must carry this EKU and only it.

        A certificate with *no* EKU extension is treated as not permitted here.
        That is stricter than some verifiers and deliberately so: this is the
        control that stops a token being accepted from a certificate its owner
        issued for something else entirely.
        """
        return OID_KP_TIMESTAMPING in self.eku


def _name_text(element: Elem) -> str:
    """An X.500 name as ``CN=…, O=…`` — for display, never for a decision."""
    parts: list[str] = []
    try:
        for rdn in der_children(element):
            for attribute in der_children(rdn):
                pair = der_children(attribute)
                if len(pair) != 2:
                    continue
                oid = der_oid(pair[0])
                label = _NAME_ATTRS.get(oid, oid)
                parts.append(f"{label}={pair[1].content.decode('utf-8', 'replace')}")
    except DerError:
        return "(unreadable)"
    return ", ".join(parts)


def _extended_key_usage(extension_fields: list[Elem]) -> list[str]:
    """The EKU OIDs, or an empty list when the extension is absent."""
    for field in extension_fields:
        if field.tag != 0xA3:
            continue
        try:
            for extension in der_children(der_children(field)[0]):
                items = der_children(extension)
                if not items or der_oid(items[0]) != OID_EXT_EKU:
                    continue
                value = items[-1]
                return [
                    der_oid(oid) for oid in der_children(der_parse(value.content))
                ]
        except (DerError, IndexError):
            return []
    return []


def rsa_verify(certificate: Certificate, signature: bytes, message: bytes, algorithm: str) -> bool:
    """RSASSA-PKCS1-v1_5 verification (RFC 8017 §8.2.2). Never raises.

    Written out rather than imported for the reason in the module docstring.
    Verification touches no secret: it is one modular exponentiation with a
    public exponent, followed by a byte-for-byte comparison of the padding and
    the DigestInfo — which is why doing it by hand here is safe in a way that
    hand-rolling a *signature* never would be.
    """
    hash_name = _RSA_SIGNATURES.get(algorithm)
    if hash_name is None:
        return False
    try:
        spki = der_children(certificate.public_key)
        if der_oid(der_children(spki[0])[0]) != OID_RSA:
            return False
        key = der_children(der_parse(der_bitstring(spki[1])))
        modulus = der_int(key[0])
        exponent = der_int(key[1])
    except (DerError, IndexError):
        return False
    if modulus <= 0 or exponent <= 0:
        return False

    size = (modulus.bit_length() + 7) // 8
    if len(signature) != size:
        return False
    recovered = pow(int.from_bytes(signature, "big"), exponent, modulus)
    block = recovered.to_bytes(size, "big")

    digest = hashlib.new(hash_name, message).digest()
    expected = (
        b"\x00\x01"
        + b"\xff" * (size - len(_DIGEST_INFO_PREFIX[hash_name]) - len(digest) - 3)
        + b"\x00"
        + _DIGEST_INFO_PREFIX[hash_name]
        + digest
    )
    # Length equality is implied by the construction above, but a malformed key
    # size would make the padding run negative; guard rather than trust it.
    return len(expected) == size and block == expected


# -------------------------------------------------------------------------
# ECDSA over the NIST prime curves
#
# Needed because timestamp authorities are moving off RSA: freetsa.org, the
# authority recorded in docs/SIGNING.md §4, switched to ECDSA P-384 on
# 2026-03-16. A verifier that only spoke RSA would reject every token issued
# after that date — the single check the whole product claim rests on, failing
# on good evidence.
#
# Short-Weierstrass arithmetic in affine coordinates, which costs one modular
# inverse per step. Measured on a 2026 laptop: ~0.2 s for P-256, ~0.5 s for
# P-384 (the curve actually in use), ~1.8 s for P-521. Jacobian coordinates
# would be several times faster by deferring the inversion to the end.
#
# That trade is refused deliberately. This file exists to be *read* by someone
# deciding whether to believe it — often an opponent's expert — and it verifies
# one record per invocation, so a second of arithmetic costs nothing that
# matters while the clarity buys something that does. There is also no secret
# here to leak through timing: verification recomputes a public point.
#
# If this ever runs in a loop over thousands of records, revisit it then, and
# measure rather than assume.
# -------------------------------------------------------------------------


def _inverse(value: int, modulus: int) -> int:
    """Modular inverse by Fermat — the modulus is prime for every curve here."""
    return pow(value, modulus - 2, modulus)


def _ec_add(
    point: tuple[int, int] | None, other: tuple[int, int] | None, p: int
) -> tuple[int, int] | None:
    """Point addition on ``y² = x³ - 3x + b``. ``None`` is the point at infinity."""
    if point is None:
        return other
    if other is None:
        return point
    x1, y1 = point
    x2, y2 = other
    if x1 == x2:
        if (y1 + y2) % p == 0:
            return None  # P + (-P)
        # Doubling: a = -3, so the numerator is 3(x² - 1).
        slope = (3 * (x1 * x1 - 1) * _inverse(2 * y1 % p, p)) % p
    else:
        slope = ((y2 - y1) * _inverse((x2 - x1) % p, p)) % p
    x3 = (slope * slope - x1 - x2) % p
    return x3, (slope * (x1 - x3) - y1) % p


def _ec_mul(scalar: int, point: tuple[int, int] | None, p: int) -> tuple[int, int] | None:
    """Double-and-add. Constant time is irrelevant: the scalar is public."""
    result: tuple[int, int] | None = None
    addend = point
    while scalar:
        if scalar & 1:
            result = _ec_add(result, addend, p)
        addend = _ec_add(addend, addend, p)
        scalar >>= 1
    return result


def _ec_public_point(
    certificate: Certificate,
) -> tuple[tuple[int, int, int, int, int], tuple[int, int]] | None:
    """The curve parameters and public point from a certificate's SPKI.

    Only the uncompressed point form (``0x04 || X || Y``) is accepted. Point
    compression is legal in X.509 and vanishingly rare in TSA certificates;
    guessing at a form we cannot test against is worse than reporting that we do
    not support it.
    """
    try:
        spki = der_children(certificate.public_key)
        algorithm = der_children(spki[0])
        if der_oid(algorithm[0]) != OID_EC_PUBLIC_KEY or len(algorithm) < 2:
            return None
        curve = _CURVES.get(der_oid(algorithm[1]))
        if curve is None:
            return None
        encoded = der_bitstring(spki[1])
    except (DerError, IndexError):
        return None

    p, b, _gx, _gy, _n = curve
    width = (p.bit_length() + 7) // 8
    if len(encoded) != 1 + 2 * width or encoded[0] != 0x04:
        return None
    x = int.from_bytes(encoded[1 : 1 + width], "big")
    y = int.from_bytes(encoded[1 + width :], "big")

    # A point off the curve is either corruption or an attack; either way it
    # cannot be allowed to reach the arithmetic below.
    if (y * y - x * x * x + 3 * x - b) % p != 0:
        return None
    return curve, (x, y)


def ecdsa_verify(
    certificate: Certificate, signature: bytes, message: bytes, algorithm: str
) -> bool:
    """ECDSA verification (FIPS 186-4 §6.4.2). Never raises.

    As with :func:`rsa_verify`, this handles no secret — it recomputes a public
    point and compares one coordinate.
    """
    hash_name = _ECDSA_SIGNATURES.get(algorithm)
    if hash_name is None:
        return False
    parsed = _ec_public_point(certificate)
    if parsed is None:
        return False
    (p, _b, gx, gy, n), public_point = parsed

    try:
        parts = der_children(der_parse(signature))
        r = der_int(parts[0])
        s = der_int(parts[1])
    except (DerError, IndexError):
        return False
    if not (1 <= r < n and 1 <= s < n):
        return False

    digest = hashlib.new(hash_name, message).digest()
    # FIPS 186-4 §6.4: use the leftmost min(N, outlen) bits of the hash. With
    # P-521 and SHA-384 the hash is *shorter* than n, so the shift must not go
    # negative — hence the max().
    shift = max(0, len(digest) * 8 - n.bit_length())
    e = int.from_bytes(digest, "big") >> shift

    w = _inverse(s, n)
    point = _ec_add(
        _ec_mul(e * w % n, (gx, gy), p),
        _ec_mul(r * w % n, public_point, p),
        p,
    )
    if point is None:
        return False
    return point[0] % n == r


def token_signature_verify(
    certificate: Certificate, signature: bytes, message: bytes, algorithm: str
) -> bool:
    """Verify a token signature with whichever algorithm the token declares.

    Unknown algorithms return False rather than raising, so the caller can go on
    to report the OID it could not handle — far more useful to whoever is
    holding the record than a traceback.
    """
    if algorithm in _RSA_SIGNATURES:
        return rsa_verify(certificate, signature, message, algorithm)
    if algorithm in _ECDSA_SIGNATURES:
        return ecdsa_verify(certificate, signature, message, algorithm)
    return False


# =========================================================================
# RFC 3161 timestamp tokens
# =========================================================================


class TimestampFacts:
    """What a token says and whether it holds up."""

    __slots__ = ("valid", "reason", "gen_time", "imprint", "tsa_name", "policy_oid", "serial")

    def __init__(
        self,
        *,
        valid: bool,
        reason: str,
        gen_time: datetime | None = None,
        imprint: bytes | None = None,
        tsa_name: str | None = None,
        policy_oid: str | None = None,
        serial: int | None = None,
    ) -> None:
        self.valid = valid
        self.reason = reason
        self.gen_time = gen_time
        self.imprint = imprint
        self.tsa_name = tsa_name
        self.policy_oid = policy_oid
        self.serial = serial


def _signed_attribute(signed_attrs: Elem, oid: str) -> Elem | None:
    for attribute in der_children(signed_attrs):
        pair = der_children(attribute)
        if len(pair) < 2:
            continue
        try:
            if der_oid(pair[0]) == oid:
                values = der_children(pair[1])
                return values[0] if values else None
        except DerError:
            continue
    return None


def verify_timestamp(token_der: bytes, chain_pem: str) -> TimestampFacts:
    """Read an RFC 3161 token and check it against its own certificate.

    Returns facts and a verdict; **never raises**, because a tampered token is a
    deliberately corrupt ASN.1 structure and "your file is broken" is an answer
    a person needs rather than a traceback.

    What is checked:

    * the token is a CMS ``SignedData`` wrapping a ``TSTInfo``;
    * the signed attributes contain a ``message-digest`` equal to SHA-256 of the
      ``TSTInfo`` — this is what binds the signature to the timestamp's content;
    * the signature over the DER ``SET OF`` signed attributes verifies under a
      certificate that carries the timestamping extended key usage.

    The certificate is taken from the token itself or from the chain stored with
    the record, whichever verifies. Both are tried because the two are meant to
    be the same certificate: BlckRhino stores the chain precisely so that a
    token stripped of its certificates is still checkable years later.

    What is deliberately **not** checked: whether the certificate chains to a
    trusted root. That is a policy decision about which authorities you accept,
    it needs a trust store this tool does not carry, and pretending to make it
    would be the most misleading thing this file could do. The certificate's
    subject and validity are printed instead, so the decision is yours to take.
    """
    try:
        info = der_children(der_parse(token_der))
        if der_oid(info[0]) != OID_SIGNED_DATA:
            return TimestampFacts(valid=False, reason="token is not CMS SignedData")
        signed_data = der_children(der_children(info[1])[0])

        encap = der_children(signed_data[2])
        if der_oid(encap[0]) != OID_TST_INFO:
            return TimestampFacts(valid=False, reason="token does not wrap a TSTInfo")
        tst_der = der_children(encap[1])[0].content

        certificates: list[Certificate] = []
        signer_infos: Elem | None = None
        for field in signed_data[3:]:
            if field.tag == 0xA0:  # [0] IMPLICIT certificates
                for candidate in der_children(field):
                    try:
                        certificates.append(Certificate(candidate.raw))
                    except (DerError, IndexError):
                        continue
            elif field.tag == 0x31:  # SET OF SignerInfo
                signer_infos = field
        if signer_infos is None:
            return TimestampFacts(valid=False, reason="token carries no signer")

        facts = _tst_info_facts(tst_der)
        signer = der_children(der_children(signer_infos)[0])
        # A SignerInfo may end with [1] IMPLICIT unsignedAttrs, and several real
        # authorities do attach one. Dropping it first means "the last two
        # elements are the algorithm and the signature" stays true, instead of
        # being true only for the tokens this was first tested against.
        while signer and signer[-1].tag == 0xA1:
            signer.pop()
        signed_attrs = next((item for item in signer if item.tag == 0xA0), None)
        if signed_attrs is None:
            return TimestampFacts(
                valid=False,
                reason="token has no signed attributes",
                **facts,
            )

        # RFC 5652 §5.3: SignerInfo declares the digest algorithm, and the
        # messageDigest attribute is that digest of the content. Assuming
        # SHA-256 works right up until an authority signs with SHA-384 — which
        # is what freetsa.org does since moving to P-384 — and then reports a
        # *good* token as one whose "signature does not cover this content",
        # which is about the most misleading answer this tool could give.
        signer_digest = _DIGESTS.get(der_oid(der_children(signer[2])[0]))
        if signer_digest is None:
            return TimestampFacts(
                valid=False,
                reason=(
                    "the token declares a digest algorithm this tool does not "
                    f"support ({der_oid(der_children(signer[2])[0])})"
                ),
                **facts,
            )

        digest_attr = _signed_attribute(signed_attrs, OID_MESSAGE_DIGEST)
        if (
            digest_attr is None
            or digest_attr.content != hashlib.new(signer_digest, tst_der).digest()
        ):
            return TimestampFacts(
                valid=False,
                reason="the signature does not cover this timestamp's content",
                **facts,
            )
        content_attr = _signed_attribute(signed_attrs, OID_CONTENT_TYPE)
        if content_attr is None or der_oid(content_attr) != OID_TST_INFO:
            return TimestampFacts(
                valid=False,
                reason="signed attributes do not declare a timestamp",
                **facts,
            )

        # RFC 5652 §5.4: the signature is over the DER SET OF encoding, not over
        # the [0] IMPLICIT form that appears in the message. Re-tagging the byte
        # is the whole of the difference and getting it wrong fails every token.
        to_verify = b"\x31" + signed_attrs.raw[1:]
        signature_algorithm = der_oid(der_children(signer[-2])[0])
        signature = signer[-1].content

        for certificate in certificates + _chain_certificates(chain_pem):
            if not certificate.permits_timestamping:
                continue
            if token_signature_verify(
                certificate, signature, to_verify, signature_algorithm
            ):
                return TimestampFacts(
                    valid=True,
                    reason=f"signed by {certificate.subject}",
                    tsa_name=certificate.subject,
                    **{key: value for key, value in facts.items() if key != "tsa_name"},
                )
        if not certificates and not _chain_certificates(chain_pem):
            return TimestampFacts(
                valid=False,
                reason="no certificate travels with this token",
                **facts,
            )
        return TimestampFacts(
            valid=False,
            reason=(
                "no timestamping certificate verifies this token "
                f"(signature algorithm {signature_algorithm})"
            ),
            **facts,
        )
    except (DerError, IndexError, ValueError) as error:
        return TimestampFacts(
            valid=False, reason=f"the timestamp token could not be read ({error})"
        )


def _tst_info_facts(tst_der: bytes) -> dict[str, Any]:
    """Policy, imprint, serial and generation time out of a ``TSTInfo``."""
    fields = der_children(der_parse(tst_der))
    imprint = der_children(fields[2])
    algorithm = der_oid(der_children(imprint[0])[0])
    return {
        "policy_oid": der_oid(fields[1]),
        "imprint": imprint[1].content if _DIGESTS.get(algorithm) == "sha256" else None,
        "serial": der_int(fields[3]),
        "gen_time": der_time(fields[4]),
        "tsa_name": None,
    }


def _chain_certificates(chain_pem: str) -> list[Certificate]:
    found: list[Certificate] = []
    for der in pem_blocks(chain_pem or "", "CERTIFICATE"):
        try:
            found.append(Certificate(der))
        except (DerError, IndexError, ValueError):
            continue
    return found


# =========================================================================
# The verification itself
# =========================================================================


class Check:
    """One question, its answer, and one line explaining what the answer means."""

    __slots__ = ("name", "ok", "detail")

    def __init__(self, name: str, ok: bool, detail: str) -> None:
        self.name = name
        self.ok = ok
        self.detail = detail


def _parse_time(value: Any) -> datetime | None:
    if not isinstance(value, str) or not value:
        return None
    text = value.strip()
    if text.endswith("Z"):
        text = text[:-1] + "+00:00"
    try:
        moment = datetime.fromisoformat(text)
    except ValueError:
        return None
    return moment if moment.tzinfo else moment.replace(tzinfo=timezone.utc)


def _load_keys(payload: Any) -> list[dict[str, Any]]:
    """The published key history, from either shape the endpoint may serve."""
    if isinstance(payload, dict):
        keys = payload.get("keys")
    else:
        keys = payload
    if not isinstance(keys, list):
        raise RecordError("the key history file has no \"keys\" list")
    return [item for item in keys if isinstance(item, dict)]


def verify_export(
    export: Any,
    keys: list[dict[str, Any]],
    *,
    form_ok: bool = True,
    form_note: str = "",
) -> tuple[list[Check], dict[str, Any]]:
    """Check one export against one key history. Returns the checks and the facts.

    ``form_ok``/``form_note`` come from :func:`read_export`, which reads the file
    a second time with duplicate object keys refused. That check cannot be made
    here: by the time JSON has been parsed into a dict, a duplicate key has
    already silently become whichever copy came last — which is precisely the
    edit that would otherwise slip past a canonical-form test.
    """
    if not isinstance(export, dict):
        raise RecordError("a delivery record export is a JSON object")
    record = export.get("record")
    signature_block = export.get("signature")
    timestamp_block = export.get("timestamp")
    if not isinstance(record, dict):
        raise RecordError("the export has no \"record\" object")
    if not isinstance(signature_block, dict) or not isinstance(timestamp_block, dict):
        raise RecordError("the export is missing its signature or timestamp block")

    canonical = canonical_bytes(record)
    digest = hashlib.sha256(canonical).digest()
    facts: dict[str, Any] = {
        "record_id": record.get("record_id"),
        "record_version": record.get("record_version"),
        "record_sha256": digest.hex(),
        "recomputed_from": "the record object in this file, re-serialised canonically",
    }
    checks: list[Check] = []

    # 1. Canonical form. The claim is not that the file is pretty — it is that
    # the bytes hashed below are reconstructible by anyone from what is on the
    # page: no duplicate keys hiding a second value, no float that would hash
    # differently in another language, and a serialisation that is fixed by rule
    # rather than by whatever wrote the file.
    checks.append(
        Check(
            "canonical form",
            form_ok,
            "the record has no duplicate keys and no floating-point numbers, so "
            "its canonical bytes are reproducible"
            if form_ok
            else f"the file cannot be canonicalised unambiguously ({form_note})",
        )
    )

    # 2. The export's own two halves agree.
    claimed = export.get("record_sha256")
    checks.append(
        Check(
            "record hash",
            isinstance(claimed, str) and claimed.strip().lower() == digest.hex(),
            f"SHA-256 of the record is {digest.hex()}",
        )
    )

    # 3. The signature, under the published key.
    key_id = str(signature_block.get("key_id", ""))
    algorithm = str(signature_block.get("algorithm", ""))
    purpose = str(signature_block.get("purpose") or DEFAULT_PURPOSE)
    facts["key_id"] = key_id
    facts["algorithm"] = algorithm
    entry = next((item for item in keys if item.get("key_id") == key_id), None)
    signature_ok = False
    signature_detail = ""
    if algorithm != ALGORITHM_ED25519:
        signature_detail = f"unsupported signature algorithm {algorithm!r}"
    elif entry is None:
        signature_detail = f"key {key_id!r} is not in the published key history"
    else:
        try:
            public_key = ed25519_public_key_from_pem(str(entry.get("public_key_pem", "")))
            raw_signature = base64.b64decode(
                str(signature_block.get("value", "")), validate=True
            )
        except (DerError, binascii.Error, ValueError) as error:
            signature_detail = f"the key or the signature could not be read ({error})"
        else:
            signature_ok = ed25519_verify(
                public_key, raw_signature, signed_payload(digest, purpose)
            )
            signature_detail = (
                f"Ed25519 signature by {key_id} over the {purpose} payload"
                if signature_ok
                else f"key {key_id} did not sign this digest"
            )
    checks.append(Check("signature", signature_ok, signature_detail))

    # 5/6. The timestamp, read before the key window because the window is
    # measured against the time the authority asserts.
    try:
        token = base64.b64decode(str(timestamp_block.get("token", "")), validate=True)
    except (binascii.Error, ValueError):
        token = b""
    stamp = verify_timestamp(token, str(timestamp_block.get("chain_pem", "")))
    facts["timestamp_authority"] = stamp.tsa_name or timestamp_block.get("tsa_name")
    facts["timestamped_at"] = stamp.gen_time.isoformat() if stamp.gen_time else None
    facts["timestamp_policy"] = stamp.policy_oid
    facts["timestamp_serial"] = stamp.serial
    checks.append(Check("timestamp token", stamp.valid, stamp.reason))
    checks.append(
        Check(
            "timestamp covers this record",
            stamp.imprint is not None and stamp.imprint == digest,
            "the token's message imprint is this record's SHA-256"
            if stamp.imprint == digest
            else "the token attests to a different document",
        )
    )

    # 4. Was the signing key in service when the authority saw the digest?
    valid_from = _parse_time(entry.get("valid_from")) if entry else None
    valid_to = _parse_time(entry.get("valid_to")) if entry else None
    in_service = True
    window_detail = "the key history publishes no validity window for this key"
    if stamp.gen_time is not None and (valid_from or valid_to):
        # A minute of slack in each direction, because the signing service and
        # the authority are two clocks and a record signed in the first second of
        # a key's life is not evidence of anything wrong.
        slack = timedelta(minutes=1)
        if valid_from and stamp.gen_time < valid_from - slack:
            in_service = False
            window_detail = f"the record predates key {key_id} entering service"
        elif valid_to and stamp.gen_time > valid_to + slack:
            in_service = False
            window_detail = f"the record postdates key {key_id} being retired"
        else:
            window_detail = (
                f"the timestamp falls inside {key_id}'s published validity window"
            )
    checks.append(Check("signing key in service", in_service, window_detail))
    return checks, facts


# =========================================================================
# Command line
# =========================================================================


def _read_json(path: str) -> Any:
    with open(path, "r", encoding="utf-8") as handle:
        return json.load(handle)


def _reject_duplicates(pairs: list[tuple[str, Any]]) -> dict[str, Any]:
    """``object_pairs_hook`` that refuses a JSON object with a repeated key.

    ``{"a":1,"a":2}`` is valid JSON that every parser silently reduces to one
    value, which makes it the one edit a naive canonical-form check misses: the
    document a reader sees and the document that gets hashed are different.
    """
    seen: dict[str, Any] = {}
    for key, value in pairs:
        if key in seen:
            raise ValueError(f"duplicate object key {key!r}")
        seen[key] = value
    return seen


def read_export(path: str) -> tuple[Any, bool, str]:
    """The export, plus whether its JSON is unambiguous and why not if it is not."""
    with open(path, "r", encoding="utf-8") as handle:
        text = handle.read()
    document = json.loads(text)
    try:
        json.loads(text, object_pairs_hook=_reject_duplicates)
    except ValueError as error:
        return document, False, str(error)
    return document, True, ""


def build_parser() -> argparse.ArgumentParser:
    parser = argparse.ArgumentParser(
        prog="verify_delivery_record.py",
        description=(
            "Verify a BlckRhino Send Forensic Delivery Record offline. Needs "
            "nothing but Python: no network, no database, no BlckRhino code."
        ),
        epilog=(
            "Exit status: 0 every check passed, 1 a check failed, 2 the files "
            "could not be used. A pass means the record has not been altered and "
            "was not created later than it claims; it does not identify the human "
            "who received the files."
        ),
        formatter_class=argparse.RawDescriptionHelpFormatter,
    )
    parser.add_argument("record", help="the exported record JSON file")
    parser.add_argument(
        "--keys",
        required=True,
        metavar="KEYS.json",
        help="the published signing key history (see the export's key_history_url)",
    )
    parser.add_argument(
        "--json",
        action="store_true",
        dest="as_json",
        help="print the verdict as JSON instead of prose",
    )
    parser.add_argument("--version", action="version", version=f"%(prog)s {TOOL_VERSION}")
    return parser


def main(argv: list[str] | None = None) -> int:
    parser = build_parser()
    arguments = parser.parse_args(argv)

    try:
        export, form_ok, form_note = read_export(arguments.record)
        keys = _load_keys(_read_json(arguments.keys))
    except (OSError, ValueError, RecordError) as error:
        print(f"cannot verify: {error}", file=sys.stderr)
        return 2

    try:
        checks, facts = verify_export(export, keys, form_ok=form_ok, form_note=form_note)
    except RecordError as error:
        print(f"cannot verify: {error}", file=sys.stderr)
        return 2

    passed = all(check.ok for check in checks)
    if arguments.as_json:
        print(
            json.dumps(
                {
                    "valid": passed,
                    "checks": [
                        {"name": check.name, "ok": check.ok, "detail": check.detail}
                        for check in checks
                    ],
                    **facts,
                },
                indent=2,
                sort_keys=True,
            )
        )
        return 0 if passed else 1

    print(f"Record   {facts.get('record_id') or '(unnamed)'}")
    print(f"Schema   {facts.get('record_version') or '(unknown)'}")
    print(f"SHA-256  {facts['record_sha256']}")
    print(f"Key      {facts.get('key_id') or '(unnamed)'}")
    print(f"Stamped  {facts.get('timestamped_at') or '(unreadable)'}")
    print(f"By       {facts.get('timestamp_authority') or '(unreadable)'}")
    print("")
    for check in checks:
        print(f"[{'PASS' if check.ok else 'FAIL'}] {check.name}: {check.detail}")
    print("")
    if passed:
        print("VERIFIED — this record is authentic, unaltered, and independently dated.")
        print(
            "It proves what was delivered and when. It does not prove the identity "
            "of the person who received it."
        )
    else:
        print("NOT VERIFIED — at least one check failed. See the FAIL lines above.")
    return 0 if passed else 1


if __name__ == "__main__":
    raise SystemExit(main())