#!/usr/bin/env python3
"""wdy_ed25519.py — Pure-Python Ed25519 (RFC 8032), stdlib only.

Public-domain reference implementation (ed25519crp style), adapted.
Used by wdy_certify.py / wdy_verify.py so that anyone can re-verify
WDY provenance records without installing third-party packages.
"""
import hashlib

_p = 2**255 - 19
_l = 2**252 + 27742317777372353535851937790883648493
_d = -121665 * pow(121666, _p - 2, _p) % _p
_I = pow(2, (_p - 1) // 4, _p)


def _inv(x):
    return pow(x, _p - 2, _p)


def _xrecover(y):
    xx = (y * y - 1) * _inv(_d * y * y + 1)
    x = pow(xx, (_p + 3) // 8, _p)
    if (x * x - xx) % _p != 0:
        x = (x * _I) % _p
    if (x * x - xx) % _p != 0:
        raise ValueError("point not on curve")
    if x % 2 != 0:
        x = _p - x
    return x


_By = 4 * _inv(5) % _p
_Bx = _xrecover(_By)
_B = (_Bx % _p, _By % _p, 1, (_Bx * _By) % _p)


def _edwards_add(P, Q):
    (x1, y1, z1, t1), (x2, y2, z2, t2) = P, Q
    a = (y1 - x1) * (y2 - x2) % _p
    b = (y1 + x1) * (y2 + x2) % _p
    c = t1 * 2 * _d * t2 % _p
    dd = z1 * 2 * z2 % _p
    e, f, g, h = b - a, dd - c, dd + c, b + a
    return (e * f % _p, g * h % _p, f * g % _p, e * h % _p)


def _scalarmult(P, e):
    Q = (0, 1, 1, 0)
    while e > 0:
        if e & 1:
            Q = _edwards_add(Q, P)
        P = _edwards_add(P, P)
        e >>= 1
    return Q


def _compress(P):
    (x, y, z, t) = P
    zi = _inv(z)
    x, y = x * zi % _p, y * zi % _p
    return int.to_bytes(y | ((x & 1) << 255), 32, "little")


def _decompress(s):
    y = int.from_bytes(s, "little")
    sign = y >> 255
    y &= (1 << 255) - 1
    x = _xrecover(y)
    if x & 1 != sign:
        x = _p - x
    return (x, y, 1, x * y % _p)


def _secret_expand(seed):
    h = hashlib.sha512(seed).digest()
    a = int.from_bytes(h[:32], "little")
    a &= (1 << 254) - 8
    a |= (1 << 254)
    return a, h[32:]


def ed25519_pub(seed: bytes) -> bytes:
    a, _ = _secret_expand(seed)
    return _compress(_scalarmult(_B, a))


def ed25519_sign(seed: bytes, msg: bytes) -> bytes:
    a, prefix = _secret_expand(seed)
    A = _compress(_scalarmult(_B, a))
    r = int.from_bytes(hashlib.sha512(prefix + msg).digest(), "little") % _l
    R = _compress(_scalarmult(_B, r))
    h = int.from_bytes(hashlib.sha512(R + A + msg).digest(), "little") % _l
    s = (r + h * a) % _l
    return R + int.to_bytes(s, 32, "little")


def ed25519_verify(pub: bytes, msg: bytes, sig: bytes) -> bool:
    if len(pub) != 32 or len(sig) != 64:
        return False
    try:
        A = _decompress(pub)
        Rs = sig[:32]
        R = _decompress(Rs)
        s = int.from_bytes(sig[32:], "little")
        if s >= _l:
            return False
        h = int.from_bytes(hashlib.sha512(Rs + pub + msg).digest(), "little") % _l
        sB = _scalarmult(_B, s)
        hA = _scalarmult(A, h)
        RhA = _edwards_add(R, hA)
        return _compress(sB) == _compress(RhA)
    except (ValueError, IndexError):
        return False


def canonical_bytes(obj) -> bytes:
    """Canonical form: sorted keys, compact separators, UTF-8, no extra whitespace."""
    import json
    return json.dumps(obj, sort_keys=True, separators=(",", ":"), ensure_ascii=False).encode("utf-8")