"""Ed25519 verification as WAI verifies every signature (SPEC §7 *Signatures*), written
from RFC 8032's definitions with Python's integers and nothing beyond the standard
library: the one routine the Python verifiers of WAI's corpora share. It shares no code
with wai-rs (`wai::sig`).

The rule, in order:

1. the key A decodes, and is the one canonical encoding of its point: y < p, and x = 0
   never carries the sign bit (RFC 8032 §5.1.3);
2. A is not of small order (its order divides 8): under such a key the equation can
   hold for a signature made without any private key;
3. S < L (RFC 8032 §5.1.7);
4. R decodes, is not of small order, and [S]B = R + [k]A holds with [S]B - [k]A encoded
   and compared with R byte for byte (the cofactorless equation), k = SHA-512(R || A ||
   M) mod L over the bytes of R and A as given.

`verify` returns None when every step holds, "bad_key" when step 1 or 2 fails and
"bad_signature" otherwise, so a verifier names the two outcomes with its own reasons.

The OER/2 reference verifier does not use this: oer-receipts §5 settles its own rule,
which refuses the same keys and leaves R to RFC 8032.
"""
import hashlib

P = 2 ** 255 - 19
L = 2 ** 252 + 27742317777372353535851937790883648493
D = -121665 * pow(121666, P - 2, P) % P
_SQRT_M1 = pow(2, (P - 1) // 4, P)

# The checks a verifier's own self-test may leave out, by name, to show its corpus
# catches the defect; never left out otherwise.
SKIPPABLE = ("small-order-key", "small-order-r")


def _recover_x(y, sign):
    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:
        x = x * _SQRT_M1 % P
    if (x * x - x2) % P:
        return None
    return P - x if (x & 1) != sign else x


def decode(b):
    """RFC 8032 §5.1.3: the point `b` encodes, in extended coordinates (X, Y, Z, T), or
    None when it is not the canonical encoding of a point (y >= p, x = 0 with the sign
    bit set, or no x)."""
    if len(b) != 32:
        return None
    y = int.from_bytes(b, "little")
    sign, y = y >> 255, y & ((1 << 255) - 1)
    x = _recover_x(y, sign)
    return None if x is None else (x, y, 1, x * y % P)


def _add(p, q):
    """Twisted Edwards addition (a = -1) in extended coordinates; complete on this curve."""
    a = (p[1] - p[0]) * (q[1] - q[0]) % P
    b = (p[1] + p[0]) * (q[1] + q[0]) % P
    c = 2 * p[3] * q[3] * D % P
    d = 2 * p[2] * q[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 _neg(p):
    return (P - p[0], p[1], p[2], P - p[3])


def _identity(p):
    return p[0] % P == 0 and (p[1] - p[2]) % P == 0


def encode(p):
    zi = pow(p[2], P - 2, P)
    x, y = p[0] * zi % P, p[1] * zi % P
    return (y | ((x & 1) << 255)).to_bytes(32, "little")


_BY = 4 * pow(5, P - 2, P) % P
B = (_recover_x(_BY, 0), _BY, 1, _recover_x(_BY, 0) * _BY % P)
IDENTITY = (0, 1, 1, 0)


def small_order(p):
    """Whether [8]p is the identity: p's order divides 8."""
    for _ in range(3):
        p = _add(p, p)
    return _identity(p)


def strict_key(pk):
    """Steps 1 and 2: whether `pk` is the canonical encoding of a point of large order."""
    a = decode(pk)
    return a is not None and not small_order(a)


def _double_mul(s, p, k, q):
    """[s]p + [k]q, one doubling per bit (Shamir's trick)."""
    pq = _add(p, q)
    acc = IDENTITY
    for i in range(max(s.bit_length(), k.bit_length()) - 1, -1, -1):
        acc = _add(acc, acc)
        bs, bk = (s >> i) & 1, (k >> i) & 1
        if bs and bk:
            acc = _add(acc, pq)
        elif bs:
            acc = _add(acc, p)
        elif bk:
            acc = _add(acc, q)
    return acc


def verify(pk, msg, sig, skip=()):
    """The whole rule over `msg`: None when every step holds, else "bad_key" (steps 1
    and 2) or "bad_signature" (steps 3 and 4). `skip` names checks of SKIPPABLE to leave
    out, for a verifier's self-test only."""
    if len(pk) != 32:
        return "bad_key"
    a = decode(pk)
    if a is None or (small_order(a) and "small-order-key" not in skip):
        return "bad_key"
    if len(sig) != 64:
        return "bad_signature"
    s = int.from_bytes(sig[32:], "little")
    if s >= L:
        return "bad_signature"
    r = decode(sig[:32])
    if r is None or (small_order(r) and "small-order-r" not in skip):
        return "bad_signature"
    k = int.from_bytes(hashlib.sha512(sig[:32] + pk + msg).digest(), "little") % L
    if encode(_double_mul(s, B, k, _neg(a))) != sig[:32]:
        return "bad_signature"
    return None


def verifies(pk, msg, sig, skip=()):
    return verify(pk, msg, sig, skip) is None


def _self_test():
    """RFC 8032 §7.1 TEST 1 and TEST 2, and the three signatures a lenient verifier
    accepts and this rule refuses; a list of the checks that fail."""
    fails = []
    t1_pk = bytes.fromhex("d75a980182b10ab7d54bfed3c964073a0ee172f3daa62325af021a68f707511a")
    t1_sig = bytes.fromhex("e5564300c360ac729086e2cc806e828a84877f1eb8e5d974d873e06522490155"
                           "5fb8821590a33bacc61e39701cf9b46bd25bf5f0595bbe24655141438e7a100b")
    t2_pk = bytes.fromhex("3d4017c3e843895a92b70aa74d1b7ebc9c982ccf2ec4968cc0cd55f12af4660c")
    t2_sig = bytes.fromhex("92a009a9f0d4cab8720e820b5f642540a2b27b5416503f8fb3762223ebdb69da"
                           "085ac1e43e15996e458f3613d0f11d8c387b2eaeb4302aeeb00d291612bb0c00")
    if verify(t1_pk, b"", t1_sig) is not None or verify(t2_pk, b"\x72", t2_sig) is not None:
        fails.append("rfc8032-vectors")
    if verify(t2_pk, b"\x73", t2_sig) != "bad_signature":
        fails.append("rfc8032-wrong-message")
    one = (1).to_bytes(32, "little")
    b_enc = encode(B)
    long_identity = (P + 1).to_bytes(32, "little")
    forged = b_enc + one  # (R, S) = (B, 1): [1]B = B + [k]O under the identity
    if verify(one, b"any", forged) != "bad_key" or verify(long_identity, b"any", forged) != "bad_key":
        fails.append("identity-key")
    if verify(one, b"any", forged, skip=("small-order-key",)) is not None:
        fails.append("identity-key-is-a-forgery")
    k = int.from_bytes(hashlib.sha512(one + b_enc + b"m").digest(), "little") % L
    r_small = one + k.to_bytes(32, "little")  # under B (scalar 1): [k]B = O + [k]B
    if verify(b_enc, b"m", r_small) != "bad_signature" or verify(b_enc, b"m", r_small, skip=("small-order-r",)) is not None:
        fails.append("small-order-r")
    s_plus_l = t1_sig[:32] + (int.from_bytes(t1_sig[32:], "little") + L).to_bytes(32, "little")
    if verify(t1_pk, b"", s_plus_l) != "bad_signature":
        fails.append("s-not-reduced")
    return fails


if __name__ == "__main__":
    import sys
    f = _self_test()
    print(("PASS" if not f else "FAIL") + " Ed25519 strict rule self-test " + ",".join(f))
    sys.exit(1 if f else 0)