src/crypto/secp256k1/schnorr.bend

bend-collections-laws-crypto@1.0.0.0 · 159 lines · 30 definitions

1import Base
2import bend-collections-laws-crypto@1.0.0.0/src/crypto/sha/sha256.bend as SHA
3import bend-collections-laws-crypto@1.0.0.0/src/crypto/secp256k1/limbs.bend as L
4import bend-collections-laws-crypto@1.0.0.0/src/crypto/secp256k1/field.bend as F
5import bend-collections-laws-crypto@1.0.0.0/src/crypto/secp256k1/scalar.bend as S
6import bend-collections-laws-crypto@1.0.0.0/src/crypto/secp256k1/point.bend as P
7import bend-collections-laws-crypto@1.0.0.0/src/crypto/secp256k1/bytes.bend as B
8
9# BIP-340 Schnorr signatures over secp256k1: x-only public keys (the point
10# with even y), tagged SHA-256 hashes, the default signing algorithm (with
11# its final verification) and verification. Messages may have any length
12# (BIP-340 as revised in 2022). The contract is
13# spec/crypto/secp256k1/schnorr.bend.
14
15def cat(xs: List<&2, U32>, ys: List<&2, U32>) -> List<&2, U32>:
16  List.append(&2, U32, xs, ys)
17
18# "BIP0340/aux", "BIP0340/nonce", "BIP0340/challenge" in ASCII
19def tag_prefix(rest: List<&2, U32>) -> List<&2, U32>:
20  66 <> 73 <> 80 <> 48 <> 51 <> 52 <> 48 <> 47 <> rest
21
22def tag_aux() -> List<&2, U32>:
23  tag_prefix([97, 117, 120])
24
25def tag_nonce() -> List<&2, U32>:
26  tag_prefix([110, 111, 110, 99, 101])
27
28def tag_challenge() -> List<&2, U32>:
29  tag_prefix([99, 104, 97, 108, 108, 101, 110, 103, 101])
30
31# hash_tag(x) = SHA256(SHA256(tag) || SHA256(tag) || x)
32def tagged_h(+th: List<&2, U32>, x: List<&2, U32>) -> List<&2, U32>:
33  SHA.sha256_bytes(cat(th, cat(th, x)))
34
35def tagged(tag: List<&2, U32>, x: List<&2, U32>) -> List<&2, U32>:
36  tagged_h(SHA.sha256_bytes(tag), x)
37
38def xor_bytes(xs: List<&2, U32>, ys: List<&2, U32>) -> List<&2, U32>:
39  match xs ys:
40    case x <> xt y <> yt: U32.xor(x, y) <> xor_bytes(xt, yt)
41    case _ _: Nil{}
42
43def is_odd(+y: List<&2, Nat>) -> Nat:
44  F.parity(y)
45
46def verify_aff(+r: List<&2, Nat>, inf: Bool, a: P.Affine) -> Bool:
47  match a:
48    case P.Affine{x, +y}: Bool.and(Bool.not(inf), Bool.and(Nat.is_eq(is_odd(y), 0n), F.eq(x, r)))
49
50# ---- verification ----
51
52# R = [s] G - [e] P must be finite, with even y and x(R) = r
53def verify_r(+r: List<&2, Nat>, +rr: P.Point) -> Bool:
54  verify_aff(r, P.is_inf(rr), P.to_affine(rr))
55
56def verify_ok(+r: List<&2, Nat>, +s: List<&2, Nat>, +e: List<&2, Nat>, +pp: P.Point, ok: Bool) -> Bool:
57  match ok:
58    case True{}: verify_r(r, P.add(P.mul(s, P.g()), P.mul(S.neg(e), pp)))
59    case False{}: False{}
60
61def verify_p(+pk: List<&2, U32>, +m: List<&2, U32>, +sig: List<&2, U32>, mp: Maybe<&2, P.Point>) -> Bool:
62  match mp:
63    case None{}: False{}
64    case Some{+pp}:
65      +rb = B.prefix(32n, sig)
66      +r = B.of_be(rb)
67      +s = B.of_be(B.suffix(32n, sig))
68      +e = S.reduce(B.of_be(tagged(tag_challenge(), cat(rb, cat(pk, m)))))
69      verify_ok(r, s, e, pp, Bool.and(F.lt_p(r), S.lt_n(s)))
70
71def lift_if(+x: List<&2, Nat>, ok: Bool) -> Maybe<&2, P.Point>:
72  match ok:
73    case True{}: P.decompress(x, 0n)
74    case False{}: None{}
75
76# lift_x: the point with x-coordinate x and even y, if any
77def lift_x(+x: List<&2, Nat>) -> Maybe<&2, P.Point>:
78  lift_if(x, F.lt_p(x))
79
80def verify_len(+pk: List<&2, U32>, +m: List<&2, U32>, +sig: List<&2, U32>, ok: Bool) -> Bool:
81  match ok:
82    case True{}: verify_p(pk, m, sig, lift_x(B.of_be(pk)))
83    case False{}: False{}
84
85# BIP-340 Verify(pk, m, sig) for a 32-byte x-only key and a 64-byte signature
86def verify(+pk: List<&2, U32>, +m: List<&2, U32>, +sig: List<&2, U32>) -> Bool:
87  verify_len(pk, m, sig, Bool.and(B.has_len(32n, pk), B.has_len(64n, sig)))
88
89# ---- signing ----
90
91# the secret key d', when 1 <= d' < n
92def secret_if(+d: List<&2, Nat>, ok: Bool) -> Maybe<&2, List<&2, Nat>>:
93  match ok:
94    case True{}: Some{d}
95    case False{}: None{}
96
97def secret(+sk: List<&2, U32>) -> Maybe<&2, List<&2, Nat>>:
98  +d = B.of_be(sk)
99  secret_if(d, Bool.and(B.has_len(32n, sk), Bool.and(Bool.not(S.is_zero(d)), S.lt_n(d))))
100
101def pubkey_aff(a: P.Affine) -> List<&2, U32>:
102  match a:
103    case P.Affine{x, y}: B.to_be(x)
104
105def pubkey_d(m: Maybe<&2, List<&2, Nat>>) -> Maybe<&2, List<&2, U32>>:
106  match m:
107    case None{}: None{}
108    case Some{d}: Some{pubkey_aff(P.to_affine(P.mul(d, P.g())))}
109
110# PubKey(sk) = bytes(d' G), the 32-byte x-only public key
111def pubkey(+sk: List<&2, U32>) -> Maybe<&2, List<&2, U32>>:
112  pubkey_d(secret(sk))
113
114# sig = bytes(R) || bytes((k + e d) mod n), then Verify(bytes(P), m, sig)
115def sign_ok(+sig: List<&2, U32>, ok: Bool) -> Maybe<&2, List<&2, U32>>:
116  match ok:
117    case True{}: Some{sig}
118    case False{}: None{}
119
120def sign_fin(+pb: List<&2, U32>, +m: List<&2, U32>, +sig: List<&2, U32>) -> Maybe<&2, List<&2, U32>>:
121  sign_ok(sig, verify(pb, m, sig))
122
123def sign_k(+d: List<&2, Nat>, +pb: List<&2, U32>, +m: List<&2, U32>, +k0: List<&2, Nat>, ra: P.Affine) -> Maybe<&2, List<&2, U32>>:
124  match ra:
125    case P.Affine{rx, +ry}:
126      +k = S.select(is_odd(ry), S.neg(k0), k0)
127      +rb = B.to_be(rx)
128      +e = S.reduce(B.of_be(tagged(tag_challenge(), cat(rb, cat(pb, m)))))
129      sign_fin(pb, m, cat(rb, B.to_be(S.add(k, S.mul(e, d)))))
130
131def sign_nz(+d: List<&2, Nat>, +pb: List<&2, U32>, +m: List<&2, U32>, +k0: List<&2, Nat>, ok: Bool) -> Maybe<&2, List<&2, U32>>:
132  match ok:
133    case True{}: sign_k(d, pb, m, k0, P.to_affine(P.mul(k0, P.g())))
134    case False{}: None{}
135
136def sign_p(+d0: List<&2, Nat>, +m: List<&2, U32>, +aux: List<&2, U32>, pa: P.Affine) -> Maybe<&2, List<&2, U32>>:
137  match pa:
138    case P.Affine{px, +py}:
139      +d = S.select(is_odd(py), S.neg(d0), d0)
140      +pb = B.to_be(px)
141      +t = xor_bytes(B.to_be(d), tagged(tag_aux(), aux))
142      +k0 = S.reduce(B.of_be(tagged(tag_nonce(), cat(t, cat(pb, m)))))
143      sign_nz(d, pb, m, k0, Bool.not(S.is_zero(k0)))
144
145def sign_d(+m: List<&2, U32>, +aux: List<&2, U32>, md: Maybe<&2, List<&2, Nat>>) -> Maybe<&2, List<&2, U32>>:
146  match md:
147    case None{}: None{}
148    case Some{+d0}: sign_p(d0, m, aux, P.to_affine(P.mul(d0, P.g())))
149
150def sign_len(+sk: List<&2, U32>, +m: List<&2, U32>, +aux: List<&2, U32>, ok: Bool) -> Maybe<&2, List<&2, U32>>:
151  match ok:
152    case True{}: sign_d(m, aux, secret(sk))
153    case False{}: None{}
154
155# BIP-340 Sign(sk, m, a) for a 32-byte secret key and 32 bytes of auxiliary
156# randomness; None for an invalid key (or, with negligible probability, a
157# zero nonce or a failed self-check)
158def sign(+sk: List<&2, U32>, +m: List<&2, U32>, +aux: List<&2, U32>) -> Maybe<&2, List<&2, U32>>:
159  sign_len(sk, m, aux, B.has_len(32n, aux))