#!/usr/bin/env python3
"""ed25519.py — pure-stdlib Ed25519 (RFC 8032), extended/projective coordinates.

Self-contained, no dependencies, no network. Slow (pure Python) but correct —
verified against RFC 8032 test vectors in demo.py.

API:
    publickey(seed_bytes)        -> 32-byte public key
    sign(msg, seed_bytes)        -> 64-byte signature
    verify(sig, msg, pk_bytes)   -> bool
"""
import hashlib

b = 256
q = 2 ** 255 - 19
L = 2 ** 252 + 27742317777372353535851937790883648493
d = (-121665 * pow(121666, q - 2, q)) % q
I = pow(2, (q - 1) // 4, q)


def _sha512(m):
    return hashlib.sha512(m).digest()


def _xrecover(y):
    xx = (y * y - 1) * pow(d * y * y + 1, q - 2, q) % q
    x = pow(xx, (q + 3) // 8, q)
    if (x * x - xx) % q != 0:
        x = (x * I) % q
    if x % 2 != 0:
        x = q - x
    return x


# Base point B (affine)
_By = (4 * pow(5, q - 2, q)) % q
_Bx = _xrecover(_By)
# Extended coordinates (X, Y, Z, T) with x=X/Z, y=Y/Z, T=XY/Z
B = (_Bx, _By, 1, (_Bx * _By) % q)
IDENTITY = (0, 1, 1, 0)


def _add(P, Q):
    X1, Y1, Z1, T1 = P
    X2, Y2, Z2, T2 = Q
    A = X1 * X2 % q
    Bv = Y1 * Y2 % q
    C = (d * T1 * T2) % q
    D = Z1 * Z2 % q
    E = ((X1 + Y1) * (X2 + Y2) - A - Bv) % q
    F = (D - C) % q
    G = (D + C) % q
    H = (Bv + A) % q  # a = -1  =>  H = B - a*A = B + A
    return (E * F % q, G * H % q, F * G % q, E * H % q)


def _double(P):
    X1, Y1, Z1, _ = P
    A = X1 * X1 % q
    Bv = Y1 * Y1 % q
    C = (2 * Z1 * Z1) % q
    D = (-A) % q  # a = -1
    E = ((X1 + Y1) * (X1 + Y1) - A - Bv) % q
    G = (D + Bv) % q
    F = (G - C) % q
    H = (D - Bv) % q
    return (E * F % q, G * H % q, F * G % q, E * H % q)


def _scalarmult(P, e):
    """Double-and-add, LSB-first: R += bit_i * [2^i]P."""
    R = IDENTITY
    Q = P
    while e:
        if e & 1:
            R = _add(R, Q)
        Q = _double(Q)
        e >>= 1
    return R


def _affine(P):
    X, Y, Z, _ = P
    zi = pow(Z, q - 2, q)
    return (X * zi % q, Y * zi % q)


def _eq(P, Q):
    X1, Y1, Z1, _ = P
    X2, Y2, Z2, _ = Q
    return (X1 * Z2 - X2 * Z1) % q == 0 and (Y1 * Z2 - Y2 * Z1) % q == 0


def _encodepoint(P):
    x, y = _affine(P)
    out = bytearray(y.to_bytes(32, "little"))
    out[31] |= (x & 1) << 7
    return bytes(out)


def _decodepoint(s):
    if len(s) != 32:
        raise ValueError("point must be 32 bytes")
    y = int.from_bytes(s, "little") & ((1 << 255) - 1)
    x = _xrecover(y)
    if (x & 1) != (s[31] >> 7):
        x = q - x
    # on-curve check: -x^2 + y^2 = 1 + d x^2 y^2
    if (-x * x + y * y - 1 - d * x * x * y * y) % q != 0:
        raise ValueError("point not on curve")
    return (x, y, 1, x * y % q)


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


def _hint(m):
    return int.from_bytes(_sha512(m), "little") % L


def publickey(seed):
    """32-byte public key from a 32-byte seed."""
    if len(seed) != 32:
        raise ValueError("seed must be 32 bytes")
    h = _sha512(seed)
    A = _scalarmult(B, _clamp(h))
    return _encodepoint(A)


def sign(msg, seed):
    """64-byte Ed25519 signature. msg: bytes, seed: 32 bytes."""
    h = _sha512(seed)
    a = _clamp(h)
    pk = _encodepoint(_scalarmult(B, a))
    r = _hint(h[32:] + msg)
    R = _scalarmult(B, r)
    k = _hint(_encodepoint(R) + pk + msg)
    S = (r + k * a) % L
    return _encodepoint(R) + S.to_bytes(32, "little")


def verify(sig, msg, pk):
    """RFC 8032 verification (permissive, no small-order cofactor checks —
    adequate for receipt binding; see SPEC.md)."""
    if len(sig) != 64 or len(pk) != 32:
        return False
    try:
        R = _decodepoint(sig[:32])
        A = _decodepoint(pk)
    except ValueError:
        return False
    S = int.from_bytes(sig[32:], "little")
    if S >= L:
        return False
    k = _hint(sig[:32] + pk + msg)
    return _eq(_scalarmult(B, S), _add(R, _scalarmult(A, k)))