proofs/crypto/secp256k1/sel.bend

bend-collections-laws-crypto@1.0.0.0 · 127 lines · 15 definitions

1# GENERATED by tools/generators/rw.py from ../../../tools/generators/secp256k1_hand/sel.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/spec/crypto/secp256k1/curve.bend as CV
6import bend-collections-laws-crypto@1.0.0.0/src/crypto/secp256k1/limbs.bend as L
7import bend-collections-laws-crypto@1.0.0.0/src/crypto/secp256k1/point.bend as P
8import bend-collections-laws-crypto@1.0.0.0/proofs/lib/logic.bend as Lg
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/crypto/secp256k1/fieldops.bend as FO
11import bend-collections-laws-crypto@1.0.0.0/proofs/crypto/secp256k1/bitsv.bend as BV
12import bend-collections-laws-crypto@1.0.0.0/proofs/crypto/secp256k1/bitsrel.bend as BR
13import bend-collections-laws-crypto@1.0.0.0/proofs/crypto/secp256k1/point.bend as PT
14
15# Selection (b ? p : q, b in {0, 1}) and small facts for the point proofs.
16def bit01(n: Nat) -> {Nat.is_lt(C.bit(n), 2n) == True{} : Bool}:
17  match n:
18    case 0n:
19      {==}
20    case 1n:
21      {==}
22    case 2n+m:
23      bit01(m)
24
25def sb01(i: Nat, +off: Nat, +k: Nat) -> {BV.all01(BR.sb(i, off, k)) == True{} : Bool}:
26  match i:
27    case 0n:
28      {==}
29    case 1n+ +j:
30      Lg.and_intro(Nat.is_lt(CV.bit(Nat.add(off, j), k), 2n), BV.all01(BR.sb(j, off, k)), bit01(C.high(Nat.add(off, j), k)), sb01(j, off, k))
31
32def sel0(+one: Nat, n: Nat, xs: List<&2, Nat>, ys: List<&2, Nat>, +hx: {FS.limbs16(one, n, xs) == True{} : Bool}, +hy: {FS.limbs16(one, n, ys) == True{} : Bool}) -> {L.select(0n, xs, ys) == ys : List<&2, Nat>}:
33  match n xs:
34    case 0n Nil{}:
35      match ys:
36        case Nil{}:
37          {==}
38        case y <> t:
39          Empty.absurd({L.select(0n, [], y <> t) == y <> t : List<&2, Nat>}, Lg.false_true(hy))
40    case 0n x <> t:
41      Empty.absurd({L.select(0n, x <> t, ys) == ys : List<&2, Nat>}, Lg.false_true(hx))
42    case 1n+k Nil{}:
43      Empty.absurd({L.select(0n, [], ys) == ys : List<&2, Nat>}, Lg.false_true(hx))
44    case 1n+ +k +x <> +xt:
45      match ys:
46        case Nil{}:
47          Empty.absurd({L.select(0n, x <> xt, []) == [] : List<&2, Nat>}, Lg.false_true(hy))
48        case +y <> +yt:
49          +hxt = Lg.and_right(Nat.is_lt(x, C.shift(16n, one)), FS.limbs16(one, k, xt), hx)
50          +hyt = Lg.and_right(Nat.is_lt(y, C.shift(16n, one)), FS.limbs16(one, k, yt), hy)
51          %Equal.sym(List<&2, Nat>, L.select(0n, xt, yt), yt, sel0(one, k, xt, yt, hxt, hyt)) : {Nat.add(Nat.mul(x, 0n), Nat.mul(y, 1n)) <> _ == y <> yt : List<&2, Nat>}
52          %Equal.sym(Nat, Nat.mul(x, 0n), 0n, NA.mul_zero(x)) : {Nat.add(_, Nat.mul(y, 1n)) <> yt == y <> yt : List<&2, Nat>}
53          %Equal.sym(Nat, Nat.mul(y, 1n), y, NA.mul_one(y)) : {Nat.add(0n, _) <> yt == y <> yt : List<&2, Nat>}
54          {==}
55
56def sel1(+one: Nat, n: Nat, xs: List<&2, Nat>, ys: List<&2, Nat>, +hx: {FS.limbs16(one, n, xs) == True{} : Bool}, +hy: {FS.limbs16(one, n, ys) == True{} : Bool}) -> {L.select(1n, xs, ys) == xs : List<&2, Nat>}:
57  match n xs:
58    case 0n Nil{}:
59      match ys:
60        case Nil{}:
61          {==}
62        case y <> t:
63          Empty.absurd({L.select(1n, [], y <> t) == [] : List<&2, Nat>}, Lg.false_true(hy))
64    case 0n x <> t:
65      Empty.absurd({L.select(1n, x <> t, ys) == x <> t : List<&2, Nat>}, Lg.false_true(hx))
66    case 1n+k Nil{}:
67      Empty.absurd({L.select(1n, [], ys) == [] : List<&2, Nat>}, Lg.false_true(hx))
68    case 1n+ +k +x <> +xt:
69      match ys:
70        case Nil{}:
71          Empty.absurd({L.select(1n, x <> xt, []) == x <> xt : List<&2, Nat>}, Lg.false_true(hy))
72        case +y <> +yt:
73          +hxt = Lg.and_right(Nat.is_lt(x, C.shift(16n, one)), FS.limbs16(one, k, xt), hx)
74          +hyt = Lg.and_right(Nat.is_lt(y, C.shift(16n, one)), FS.limbs16(one, k, yt), hy)
75          %Equal.sym(List<&2, Nat>, L.select(1n, xt, yt), xt, sel1(one, k, xt, yt, hxt, hyt)) : {Nat.add(Nat.mul(x, 1n), Nat.mul(y, 0n)) <> _ == x <> xt : List<&2, Nat>}
76          %Equal.sym(Nat, Nat.mul(y, 0n), 0n, NA.mul_zero(y)) : {Nat.add(Nat.mul(x, 1n), _) <> xt == x <> xt : List<&2, Nat>}
77          %Equal.sym(Nat, Nat.mul(x, 1n), x, NA.mul_one(x)) : {Nat.add(_, 0n) <> xt == x <> xt : List<&2, Nat>}
78          %Equal.sym(Nat, Nat.add(x, 0n), x, NA.add_zero(x)) : {_ <> xt == x <> xt : List<&2, Nat>}
79          {==}
80
81def l16(+one: Nat, +x: List<&2, Nat>, +h: {PT.red(one, x) == True{} : Bool}) -> {FS.limbs16(one, 16n, x) == True{} : Bool}:
82  Lg.and_left(FS.limbs16(one, 16n, x), Nat.is_lt(FS.value(one, x), FS.prime(one)), h)
83
84def rx(+one: Nat, +x: List<&2, Nat>, +y: List<&2, Nat>, +z: List<&2, Nat>, +h: {PT.pred(one, P.Point{x, y, z}) == True{} : Bool}) -> {FS.limbs16(one, 16n, x) == True{} : Bool}:
85  l16(one, x, Lg.and_left(PT.red(one, x), Bool.and(PT.red(one, y), PT.red(one, z)), h))
86
87def ry(+one: Nat, +x: List<&2, Nat>, +y: List<&2, Nat>, +z: List<&2, Nat>, +h: {PT.pred(one, P.Point{x, y, z}) == True{} : Bool}) -> {FS.limbs16(one, 16n, y) == True{} : Bool}:
88  l16(one, y, Lg.and_left(PT.red(one, y), PT.red(one, z), Lg.and_right(PT.red(one, x), Bool.and(PT.red(one, y), PT.red(one, z)), h)))
89
90def rz(+one: Nat, +x: List<&2, Nat>, +y: List<&2, Nat>, +z: List<&2, Nat>, +h: {PT.pred(one, P.Point{x, y, z}) == True{} : Bool}) -> {FS.limbs16(one, 16n, z) == True{} : Bool}:
91  l16(one, z, Lg.and_right(PT.red(one, y), PT.red(one, z), Lg.and_right(PT.red(one, x), Bool.and(PT.red(one, y), PT.red(one, z)), h)))
92
93# b = 0 picks the second point, b = 1 the first
94def psel0(+one: Nat, a: P.Point, b: P.Point, +ha: {PT.pred(one, a) == True{} : Bool}, +hb: {PT.pred(one, b) == True{} : Bool}) -> {P.select(0n, a, b) == b : P.Point}:
95  match a b:
96    case P.Point{+x1, +y1, +z1} P.Point{+x2, +y2, +z2}:
97      %Equal.sym(List<&2, Nat>, L.select(0n, x1, x2), x2, sel0(one, 16n, x1, x2, rx(one, x1, y1, z1, ha), rx(one, x2, y2, z2, hb))) : {P.Point{_, L.select(0n, y1, y2), L.select(0n, z1, z2)} == P.Point{x2, y2, z2} : P.Point}
98      %Equal.sym(List<&2, Nat>, L.select(0n, y1, y2), y2, sel0(one, 16n, y1, y2, ry(one, x1, y1, z1, ha), ry(one, x2, y2, z2, hb))) : {P.Point{x2, _, L.select(0n, z1, z2)} == P.Point{x2, y2, z2} : P.Point}
99      %Equal.sym(List<&2, Nat>, L.select(0n, z1, z2), z2, sel0(one, 16n, z1, z2, rz(one, x1, y1, z1, ha), rz(one, x2, y2, z2, hb))) : {P.Point{x2, y2, _} == P.Point{x2, y2, z2} : P.Point}
100      {==}
101
102def psel1(+one: Nat, a: P.Point, b: P.Point, +ha: {PT.pred(one, a) == True{} : Bool}, +hb: {PT.pred(one, b) == True{} : Bool}) -> {P.select(1n, a, b) == a : P.Point}:
103  match a b:
104    case P.Point{+x1, +y1, +z1} P.Point{+x2, +y2, +z2}:
105      %Equal.sym(List<&2, Nat>, L.select(1n, x1, x2), x1, sel1(one, 16n, x1, x2, rx(one, x1, y1, z1, ha), rx(one, x2, y2, z2, hb))) : {P.Point{_, L.select(1n, y1, y2), L.select(1n, z1, z2)} == P.Point{x1, y1, z1} : P.Point}
106      %Equal.sym(List<&2, Nat>, L.select(1n, y1, y2), y1, sel1(one, 16n, y1, y2, ry(one, x1, y1, z1, ha), ry(one, x2, y2, z2, hb))) : {P.Point{x1, _, L.select(1n, z1, z2)} == P.Point{x1, y1, z1} : P.Point}
107      %Equal.sym(List<&2, Nat>, L.select(1n, z1, z2), z1, sel1(one, 16n, z1, z2, rz(one, x1, y1, z1, ha), rz(one, x2, y2, z2, hb))) : {P.Point{x1, y1, _} == P.Point{x1, y1, z1} : P.Point}
108      {==}
109
110def one_lt(+one: Nat, +h1: {one == 1n : Nat}) -> {Nat.is_lt(1n, FS.prime(one)) == True{} : Bool}:
111  FO.small_lt_p(one, h1, 1n, {==})
112
113def lt2(c: Nat) -> {Nat.is_lt(2n+c, 2n) == False{} : Bool}:
114  match c:
115    case 0n:
116      {==}
117    case 1n+d:
118      {==}
119
120def not01(+c: Nat, +h: {Nat.is_lt(2n+c, 2n) == True{} : Bool}) -> Empty:
121  Lg.false_true(Equal.trans(Bool, False{}, Nat.is_lt(2n+c, 2n), True{}, Equal.sym(Bool, Nat.is_lt(2n+c, 2n), False{}, lt2(c)), h))
122
123def red_of(+one: Nat, +x: List<&2, Nat>, +hl: {FS.limbs16(one, 16n, x) == True{} : Bool}, +hb: {Nat.is_lt(FS.value(one, x), FS.prime(one)) == True{} : Bool}) -> {PT.red(one, x) == True{} : Bool}:
124  Lg.and_intro(FS.limbs16(one, 16n, x), Nat.is_lt(FS.value(one, x), FS.prime(one)), hl, hb)
125
126def sl16(+one: Nat, +x: List<&2, Nat>, +h: {FS.reduced(one, FS.order(one), x) == True{} : Bool}) -> {FS.limbs16(one, 16n, x) == True{} : Bool}:
127  Lg.and_left(FS.limbs16(one, 16n, x), Nat.is_lt(FS.value(one, x), FS.order(one)), h)