~/jendhub

proofs/crypto/secp256k1/fwrap.bend

bend-collections-laws-crypto@1.0.0.0 · 119 lines · 11 definitions

1# GENERATED by tools/generators/rw.py from ../../../tools/generators/secp256k1_hand/fwrap.src; edit the .src
2import Base
3import bend-collections-laws-crypto@1.0.0.0/spec/lib/common.bend as C
4import bend-collections-laws-crypto@1.0.0.0/spec/crypto/secp256k1/field.bend as FS
5import bend-collections-laws-crypto@1.0.0.0/src/crypto/secp256k1/limbs.bend as L
6import bend-collections-laws-crypto@1.0.0.0/src/crypto/secp256k1/field.bend as F
7import bend-collections-laws-crypto@1.0.0.0/src/crypto/secp256k1/scalar.bend as S
8import bend-collections-laws-crypto@1.0.0.0/proofs/lib/nat.bend as N
9import bend-collections-laws-crypto@1.0.0.0/proofs/lib/lemmas/proofs/nat_algebra.bend as NA
10import bend-collections-laws-crypto@1.0.0.0/proofs/math/typed/width.bend as WW
11import bend-collections-laws-crypto@1.0.0.0/proofs/crypto/secp256k1/semiring.bend as SR
12import bend-collections-laws-crypto@1.0.0.0/proofs/crypto/secp256k1/limbs.bend as LV
13import bend-collections-laws-crypto@1.0.0.0/proofs/crypto/secp256k1/fprot.bend as FR
14import bend-collections-laws-crypto@1.0.0.0/proofs/crypto/secp256k1/consts.bend as K
15import bend-collections-laws-crypto@1.0.0.0/proofs/crypto/secp256k1/listops.bend as LO
16
17# The tests of src/crypto/secp256k1/field.bend and scalar.bend (zero,
18# equality, parity, a < p, a < n, a > n / 2) are the specification's tests
19# on the values.
20
21# ---- GF(p) ----
22
23def is_zero_f(+one: Nat, +h1: {one == 1n : Nat}, +a: List<&2, Nat>) -> {F.is_zero(a) == Nat.is_eq(FS.value(one, a), 0n) : Bool}:
24  %Equal.sym(Bool, L.is_zero(a), Nat.is_eq(LV.ev(a), 0n), LO.is_zero_v(a)) : {_ == Nat.is_eq(FS.value(one, a), 0n) : Bool}
25  %Equal.sym(Nat, FS.value(one, a), LV.ev(a), LV.ev_value(one, h1, a)) : {Nat.is_eq(LV.ev(a), 0n) == Nat.is_eq(_, 0n) : Bool}
26  {==}
27
28def eq_f(+one: Nat, +h1: {one == 1n : Nat}, +a: List<&2, Nat>, +b: List<&2, Nat>, +ha: {FS.limbs16(one, 16n, a) == True{} : Bool}, +hb: {FS.limbs16(one, 16n, b) == True{} : Bool}) -> {F.eq(a, b) == Nat.is_eq(FS.value(one, a), FS.value(one, b)) : Bool}:
29  %Equal.sym(Bool, F.eq(a, b), L.eq(a, b), FR.f_eq(a, b)) : {_ == Nat.is_eq(FS.value(one, a), FS.value(one, b)) : Bool}
30  %Equal.sym(Bool, L.eq(a, b), Nat.is_eq(LV.ev(a), LV.ev(b)), LO.eq_v(one, h1, a, b, ha, hb)) : {_ == Nat.is_eq(FS.value(one, a), FS.value(one, b)) : Bool}
31  %Equal.sym(Nat, FS.value(one, a), LV.ev(a), LV.ev_value(one, h1, a)) : {Nat.is_eq(LV.ev(a), LV.ev(b)) == Nat.is_eq(_, FS.value(one, b)) : Bool}
32  %Equal.sym(Nat, FS.value(one, b), LV.ev(b), LV.ev_value(one, h1, b)) : {Nat.is_eq(LV.ev(a), LV.ev(b)) == Nat.is_eq(LV.ev(a), _) : Bool}
33  {==}
34
35def parity_f(+one: Nat, +h1: {one == 1n : Nat}, +a: List<&2, Nat>) -> {F.parity(a) == Nat.mod(FS.value(one, a), 2n) : Nat}:
36  %Equal.sym(Nat, Nat.mod(L.hd0(a), 2n), Nat.mod(LV.ev(a), 2n), LO.parity_v(a)) : {_ == Nat.mod(FS.value(one, a), 2n) : Nat}
37  %Equal.sym(Nat, FS.value(one, a), LV.ev(a), LV.ev_value(one, h1, a)) : {Nat.mod(LV.ev(a), 2n) == Nat.mod(_, 2n) : Nat}
38  {==}
39
40def lt_p_f(+one: Nat, +h1: {one == 1n : Nat}, +a: List<&2, Nat>) -> {F.lt_p(a) == Nat.is_lt(FS.value(one, a), FS.prime(one)) : Bool}:
41  %Equal.sym(Bool, L.ltm(F.c(), a), Nat.is_lt(LV.ev(a), 1n+K.pp(one)), LO.ltm_vv(one, h1, K.pp(one), F.c(), K.hm_p(one, h1), a)) : {_ == Nat.is_lt(FS.value(one, a), FS.prime(one)) : Bool}
42  %Equal.sym(Nat, FS.value(one, a), LV.ev(a), LV.ev_value(one, h1, a)) : {Nat.is_lt(LV.ev(a), 1n+K.pp(one)) == Nat.is_lt(_, FS.prime(one)) : Bool}
43  %Equal.sym(Nat, FS.prime(one), 1n+K.pp(one), K.prime_eq(one, h1)) : {Nat.is_lt(LV.ev(a), 1n+K.pp(one)) == Nat.is_lt(LV.ev(a), _) : Bool}
44  {==}
45
46# ---- Z / n ----
47
48def is_zero_s(+one: Nat, +h1: {one == 1n : Nat}, +a: List<&2, Nat>) -> {S.is_zero(a) == Nat.is_eq(FS.value(one, a), 0n) : Bool}:
49  %Equal.sym(Bool, L.is_zero(a), Nat.is_eq(LV.ev(a), 0n), LO.is_zero_v(a)) : {_ == Nat.is_eq(FS.value(one, a), 0n) : Bool}
50  %Equal.sym(Nat, FS.value(one, a), LV.ev(a), LV.ev_value(one, h1, a)) : {Nat.is_eq(LV.ev(a), 0n) == Nat.is_eq(_, 0n) : Bool}
51  {==}
52
53def eq_s(+one: Nat, +h1: {one == 1n : Nat}, +a: List<&2, Nat>, +b: List<&2, Nat>, +ha: {FS.limbs16(one, 16n, a) == True{} : Bool}, +hb: {FS.limbs16(one, 16n, b) == True{} : Bool}) -> {S.eq(a, b) == Nat.is_eq(FS.value(one, a), FS.value(one, b)) : Bool}:
54  %Equal.sym(Bool, S.eq(a, b), L.eq(a, b), FR.s_eq(a, b)) : {_ == Nat.is_eq(FS.value(one, a), FS.value(one, b)) : Bool}
55  %Equal.sym(Bool, L.eq(a, b), Nat.is_eq(LV.ev(a), LV.ev(b)), LO.eq_v(one, h1, a, b, ha, hb)) : {_ == Nat.is_eq(FS.value(one, a), FS.value(one, b)) : Bool}
56  %Equal.sym(Nat, FS.value(one, a), LV.ev(a), LV.ev_value(one, h1, a)) : {Nat.is_eq(LV.ev(a), LV.ev(b)) == Nat.is_eq(_, FS.value(one, b)) : Bool}
57  %Equal.sym(Nat, FS.value(one, b), LV.ev(b), LV.ev_value(one, h1, b)) : {Nat.is_eq(LV.ev(a), LV.ev(b)) == Nat.is_eq(LV.ev(a), _) : Bool}
58  {==}
59
60def lt_n_s(+one: Nat, +h1: {one == 1n : Nat}, +a: List<&2, Nat>) -> {S.lt_n(a) == Nat.is_lt(FS.value(one, a), FS.order(one)) : Bool}:
61  %Equal.sym(Bool, L.ltm(S.c(), a), Nat.is_lt(LV.ev(a), 1n+K.np(one)), LO.ltm_vv(one, h1, K.np(one), S.c(), K.hm_n(one, h1), a)) : {_ == Nat.is_lt(FS.value(one, a), FS.order(one)) : Bool}
62  %Equal.sym(Nat, FS.value(one, a), LV.ev(a), LV.ev_value(one, h1, a)) : {Nat.is_lt(LV.ev(a), 1n+K.np(one)) == Nat.is_lt(_, FS.order(one)) : Bool}
63  %Equal.sym(Nat, FS.order(one), 1n+K.np(one), K.order_eq(one, h1)) : {Nat.is_lt(LV.ev(a), 1n+K.np(one)) == Nat.is_lt(LV.ev(a), _) : Bool}
64  {==}
65
66# a leading digit one larger
67def dig1(+one: Nat, +h1: {one == 1n : Nat}, +d: Nat, +r: Nat) -> {Nat.add(Nat.mul(one, 1n+d), r) == 1n+Nat.add(Nat.mul(one, d), r) : Nat}:
68  %Equal.sym(Nat, one, 1n, h1) : {Nat.add(Nat.mul(_, 1n+d), r) == 1n+Nat.add(Nat.mul(one, d), r) : Nat}
69  %Equal.sym(Nat, one, 1n, h1) : {Nat.add(Nat.mul(1n, 1n+d), r) == 1n+Nat.add(Nat.mul(_, d), r) : Nat}
70  %Equal.sym(Nat, 1n+d, Nat.add(d, 1n), SR.succ_add(1n, d)) : {Nat.add(Nat.mul(1n, _), r) == 1n+Nat.add(Nat.mul(1n, d), r) : Nat}
71  %Equal.sym(Nat, Nat.mul(1n, Nat.add(d, 1n)), Nat.add(d, 1n), SR.one_mul(Nat.add(d, 1n))) : {Nat.add(_, r) == 1n+Nat.add(Nat.mul(1n, d), r) : Nat}
72  %Equal.sym(Nat, Nat.add(Nat.add(d, 1n), r), Nat.add(d, Nat.add(1n, r)), NA.add_assoc(d, 1n, r)) : {_ == 1n+Nat.add(Nat.mul(1n, d), r) : Nat}
73  %Equal.sym(Nat, Nat.add(1n, r), Nat.add(r, 1n), NA.add_comm(1n, r)) : {Nat.add(d, _) == 1n+Nat.add(Nat.mul(1n, d), r) : Nat}
74  %Equal.sym(Nat, Nat.mul(1n, d), d, SR.one_mul(d)) : {Nat.add(d, Nat.add(r, 1n)) == 1n+Nat.add(_, r) : Nat}
75  %Equal.sym(Nat, 1n+Nat.add(d, r), Nat.add(Nat.add(d, r), 1n), SR.succ_add(1n, Nat.add(d, r))) : {Nat.add(d, Nat.add(r, 1n)) == _ : Nat}
76  %Equal.sym(Nat, Nat.add(Nat.add(d, r), 1n), Nat.add(d, Nat.add(r, 1n)), NA.add_assoc(d, r, 1n)) : {Nat.add(d, Nat.add(r, 1n)) == _ : Nat}
77  {==}
78
79# n + 1 + (2^256 - n - 1) = 2^256
80def hm_n1(+one: Nat, +h1: {one == 1n : Nat}) -> {Nat.add(1n+(1n+K.np(one)), FS.value(one, S.cm1())) == C.shift(256n, one) : Nat}:
81  +r = C.shift(16n, FS.digits(one, [12233n, 41331n, 16429n, 24516n, 20663n, 8985n, 17745n, 1n]))
82  %Equal.sym(Nat, C.shift(256n, one), Nat.add(1n+K.np(one), FS.cn(one)), Equal.sym(Nat, Nat.add(1n+K.np(one), FS.cn(one)), C.shift(256n, one), K.hm_n(one, h1))) : {Nat.add(1n+1n+K.np(one), Nat.add(Nat.mul(one, 48830n), r)) == _ : Nat}
83  %Equal.sym(Nat, Nat.add(Nat.mul(one, 48831n), r), 1n+Nat.add(Nat.mul(one, 48830n), r), dig1(one, h1, 48830n, r)) : {Nat.add(1n+1n+K.np(one), Nat.add(Nat.mul(one, 48830n), r)) == Nat.add(1n+K.np(one), _) : Nat}
84  %Equal.sym(Nat, 1n+K.np(one), Nat.add(K.np(one), 1n), SR.succ_add(1n, K.np(one))) : {Nat.add(1n+_, Nat.add(Nat.mul(one, 48830n), r)) == Nat.add(1n+K.np(one), 1n+Nat.add(Nat.mul(one, 48830n), r)) : Nat}
85  %Equal.sym(Nat, 1n+Nat.add(K.np(one), 1n), Nat.add(Nat.add(K.np(one), 1n), 1n), SR.succ_add(1n, Nat.add(K.np(one), 1n))) : {Nat.add(_, Nat.add(Nat.mul(one, 48830n), r)) == Nat.add(1n+K.np(one), 1n+Nat.add(Nat.mul(one, 48830n), r)) : Nat}
86  %Equal.sym(Nat, Nat.add(Nat.add(K.np(one), 1n), 1n), Nat.add(K.np(one), Nat.add(1n, 1n)), NA.add_assoc(K.np(one), 1n, 1n)) : {Nat.add(_, Nat.add(Nat.mul(one, 48830n), r)) == Nat.add(1n+K.np(one), 1n+Nat.add(Nat.mul(one, 48830n), r)) : Nat}
87  %Equal.sym(Nat, Nat.add(1n, 1n), 2n, {==}) : {Nat.add(Nat.add(K.np(one), _), Nat.add(Nat.mul(one, 48830n), r)) == Nat.add(1n+K.np(one), 1n+Nat.add(Nat.mul(one, 48830n), r)) : Nat}
88  %Equal.sym(Nat, Nat.add(Nat.add(K.np(one), 2n), Nat.add(Nat.mul(one, 48830n), r)), Nat.add(K.np(one), Nat.add(2n, Nat.add(Nat.mul(one, 48830n), r))), NA.add_assoc(K.np(one), 2n, Nat.add(Nat.mul(one, 48830n), r))) : {_ == Nat.add(1n+K.np(one), 1n+Nat.add(Nat.mul(one, 48830n), r)) : Nat}
89  %Equal.sym(Nat, Nat.add(2n, Nat.add(Nat.mul(one, 48830n), r)), Nat.add(Nat.mul(one, 48830n), Nat.add(2n, r)), NA.add_swap(2n, Nat.mul(one, 48830n), r)) : {Nat.add(K.np(one), _) == Nat.add(1n+K.np(one), 1n+Nat.add(Nat.mul(one, 48830n), r)) : Nat}
90  %Equal.sym(Nat, Nat.add(2n, r), Nat.add(r, 2n), NA.add_comm(2n, r)) : {Nat.add(K.np(one), Nat.add(Nat.mul(one, 48830n), _)) == Nat.add(1n+K.np(one), 1n+Nat.add(Nat.mul(one, 48830n), r)) : Nat}
91  %Equal.sym(Nat, 1n+K.np(one), Nat.add(K.np(one), 1n), SR.succ_add(1n, K.np(one))) : {Nat.add(K.np(one), Nat.add(Nat.mul(one, 48830n), Nat.add(r, 2n))) == Nat.add(_, 1n+Nat.add(Nat.mul(one, 48830n), r)) : Nat}
92  %Equal.sym(Nat, 1n+Nat.add(Nat.mul(one, 48830n), r), Nat.add(Nat.add(Nat.mul(one, 48830n), r), 1n), SR.succ_add(1n, Nat.add(Nat.mul(one, 48830n), r))) : {Nat.add(K.np(one), Nat.add(Nat.mul(one, 48830n), Nat.add(r, 2n))) == Nat.add(Nat.add(K.np(one), 1n), _) : Nat}
93  %Equal.sym(Nat, Nat.add(Nat.add(Nat.mul(one, 48830n), r), 1n), Nat.add(Nat.mul(one, 48830n), Nat.add(r, 1n)), NA.add_assoc(Nat.mul(one, 48830n), r, 1n)) : {Nat.add(K.np(one), Nat.add(Nat.mul(one, 48830n), Nat.add(r, 2n))) == Nat.add(Nat.add(K.np(one), 1n), _) : Nat}
94  %Equal.sym(Nat, Nat.add(Nat.add(K.np(one), 1n), Nat.add(Nat.mul(one, 48830n), Nat.add(r, 1n))), Nat.add(K.np(one), Nat.add(1n, Nat.add(Nat.mul(one, 48830n), Nat.add(r, 1n)))), NA.add_assoc(K.np(one), 1n, Nat.add(Nat.mul(one, 48830n), Nat.add(r, 1n)))) : {Nat.add(K.np(one), Nat.add(Nat.mul(one, 48830n), Nat.add(r, 2n))) == _ : Nat}
95  %Equal.sym(Nat, Nat.add(1n, Nat.add(Nat.mul(one, 48830n), Nat.add(r, 1n))), Nat.add(Nat.mul(one, 48830n), Nat.add(1n, Nat.add(r, 1n))), NA.add_swap(1n, Nat.mul(one, 48830n), Nat.add(r, 1n))) : {Nat.add(K.np(one), Nat.add(Nat.mul(one, 48830n), Nat.add(r, 2n))) == Nat.add(K.np(one), _) : Nat}
96  %Equal.sym(Nat, Nat.add(1n, Nat.add(r, 1n)), Nat.add(r, Nat.add(1n, 1n)), NA.add_swap(1n, r, 1n)) : {Nat.add(K.np(one), Nat.add(Nat.mul(one, 48830n), Nat.add(r, 2n))) == Nat.add(K.np(one), Nat.add(Nat.mul(one, 48830n), _)) : Nat}
97  %Equal.sym(Nat, Nat.add(1n, 1n), 2n, {==}) : {Nat.add(K.np(one), Nat.add(Nat.mul(one, 48830n), Nat.add(r, 2n))) == Nat.add(K.np(one), Nat.add(Nat.mul(one, 48830n), Nat.add(r, _))) : Nat}
98  {==}
99
100# not (x < m + 1) is m < x
101def nlt(x: Nat, m: Nat) -> {Bool.not(Nat.is_lt(x, 1n+m)) == Nat.is_lt(m, x) : Bool}:
102  match x m:
103    case 0n _:
104      Equal.sym(Bool, Nat.is_lt(m, 0n), False{}, N.not_lt_zero(m))
105    case 1n+y 0n:
106      %Equal.sym(Bool, Nat.is_lt(y, 0n), False{}, N.not_lt_zero(y)) : {Bool.not(_) == True{} : Bool}
107      {==}
108    case 1n+y 1n+k:
109      nlt(y, k)
110
111def is_high_s(+one: Nat, +h1: {one == 1n : Nat}, +a: List<&2, Nat>) -> {S.is_high(a) == Nat.is_lt(FS.order(one), Nat.double(FS.value(one, a))) : Bool}:
112  %Equal.sym(Bool, L.ltm(S.cm1(), L.scal(2n, a)), Nat.is_lt(LV.ev(L.scal(2n, a)), 1n+1n+K.np(one)), LO.ltm_vv(one, h1, 1n+K.np(one), S.cm1(), hm_n1(one, h1), L.scal(2n, a))) : {Bool.not(_) == Nat.is_lt(FS.order(one), Nat.double(FS.value(one, a))) : Bool}
113  %Equal.sym(Nat, LV.ev(L.scal(2n, a)), Nat.mul(LV.ev(a), 2n), LV.scal_v(2n, a)) : {Bool.not(Nat.is_lt(_, 1n+1n+K.np(one))) == Nat.is_lt(FS.order(one), Nat.double(FS.value(one, a))) : Bool}
114  %Equal.sym(Nat, FS.value(one, a), LV.ev(a), LV.ev_value(one, h1, a)) : {Bool.not(Nat.is_lt(Nat.mul(LV.ev(a), 2n), 1n+1n+K.np(one))) == Nat.is_lt(FS.order(one), Nat.double(_)) : Bool}
115  %Equal.sym(Bool, Bool.not(Nat.is_lt(Nat.mul(LV.ev(a), 2n), 1n+1n+K.np(one))), Nat.is_lt(1n+K.np(one), Nat.mul(LV.ev(a), 2n)), nlt(Nat.mul(LV.ev(a), 2n), 1n+K.np(one))) : {_ == Nat.is_lt(FS.order(one), Nat.double(LV.ev(a))) : Bool}
116  %Equal.sym(Nat, FS.order(one), 1n+K.np(one), K.order_eq(one, h1)) : {Nat.is_lt(1n+K.np(one), Nat.mul(LV.ev(a), 2n)) == Nat.is_lt(_, Nat.double(LV.ev(a))) : Bool}
117  %Equal.sym(Nat, Nat.double(LV.ev(a)), Nat.mul(2n, LV.ev(a)), NA.double_mul(LV.ev(a))) : {Nat.is_lt(1n+K.np(one), Nat.mul(LV.ev(a), 2n)) == Nat.is_lt(1n+K.np(one), _) : Bool}
118  %Equal.sym(Nat, Nat.mul(2n, LV.ev(a)), Nat.mul(LV.ev(a), 2n), NA.mul_comm(2n, LV.ev(a))) : {Nat.is_lt(1n+K.np(one), Nat.mul(LV.ev(a), 2n)) == Nat.is_lt(1n+K.np(one), _) : Bool}
119  {==}