632f8cf394
wai-rs gains the feature floor (the mandatory floor of SPEC 5: PNG, FLAC and zstd, decoded with no system codec library) and quickstart (the floor, and the receipt checks hello and verify run). The wai command line gains four verbs, one module each, named in one table (dx::VERBS): - hello: name, dispatch, rebuild and receipt on a picture made here, the receipt laid out as http-delivery 8 lays receipts beside an object; - create: a new project from one of the examples, whose files the binary holds; tests/cli_dx.rs holds them to wai/examples/ byte for byte; - dev: the relay, the room service and the room page on one loopback origin, as a production front serves them; --check checks each piece through it; - verify: the receipt indexes under a directory, checked offline. The project file a template writes, wai.json, is read in one place (dx/project.rs). wai/examples/ holds video-room, watch-together, messaging, encoder-ingest, package-and-deliver, verify-receipts, apple-app, android-app and remote-desktop, each with a README and a test that runs it through wai create and wai dev. wai/quickstart/ builds the room client and the archive that holds wai, the relay, the room service, the remote host and the packager. Co-Authored-By: Claude Opus 5.5 <[email protected]>
182 lines
6.8 KiB
Python
182 lines
6.8 KiB
Python
"""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)
|