proofs/crypto/curve25519/freeze.bend

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

1import Base
2import bend-collections-laws-crypto@1.0.0.0/spec/lib/common.bend as C
3import bend-collections-laws-crypto@1.0.0.0/spec/crypto/curve25519/field.bend as FS
4import bend-collections-laws-crypto@1.0.0.0/src/crypto/curve25519/field.bend as F
5import bend-collections-laws-crypto@1.0.0.0/proofs/lib/nat.bend as N
6import bend-collections-laws-crypto@1.0.0.0/proofs/lib/logic.bend as L
7import bend-collections-laws-crypto@1.0.0.0/proofs/lib/word.bend as WD
8import bend-collections-laws-crypto@1.0.0.0/proofs/lib/arith.bend as AR
9import bend-collections-laws-crypto@1.0.0.0/proofs/lib/u32.bend as U
10import bend-collections-laws-crypto@1.0.0.0/proofs/lib/lemmas/proofs/nat_algebra.bend as NA
11import bend-collections-laws-crypto@1.0.0.0/proofs/math/natural/arith.bend as NR
12import bend-collections-laws-crypto@1.0.0.0/proofs/crypto/curve25519/num.bend as M
13import bend-collections-laws-crypto@1.0.0.0/proofs/crypto/curve25519/limbs.bend as LM
14import bend-collections-laws-crypto@1.0.0.0/proofs/crypto/curve25519/poly.bend as PL
15import bend-collections-laws-crypto@1.0.0.0/proofs/crypto/curve25519/fold.bend as FD
16import bend-collections-laws-crypto@1.0.0.0/proofs/crypto/curve25519/reduce.bend as RD
17import bend-collections-laws-crypto@1.0.0.0/proofs/crypto/curve25519/consts.bend as K
18import bend-collections-laws-crypto@1.0.0.0/proofs/crypto/curve25519/fieldops.bend as FO
19import bend-collections-laws-crypto@1.0.0.0/proofs/crypto/curve25519/cong.bend as G
20
21# freeze (the canonical representative, below p) of a tight element: csub
22# adds 2^256 - p = 2^255 + 19 and keeps the sum when it carries out (x >= p,
23# the sum is x - p), else keeps x; twice suffices since 2^256 < 3 p.
24
25def v(+x: U32) -> Nat:
26  U32.to_nat(x)
27
28# ---- constants ----
29
30def comp_p_shape() -> {F.comp_p() == Con{19, K.rep(30n, 0, Con{128, Nil{}})} : List<&2, U32>}:
31  {==}
32
33def comp_p_val(+one: Nat, +h1: {one == 1n : Nat}, +pp: Nat, +hP: {Nat.add(1n+pp, 19n) == WD.sc(255n, one) : Nat}) -> {K.valo(one, F.comp_p()) == Nat.add(1n+pp, 38n) : Nat}:
34  +P = {1n+pp : Nat}
35  +R = K.rep(30n, 0, Con{128, Nil{}})
36  %Equal.sym(List<&2, U32>, F.comp_p(), Con{19, R}, comp_p_shape()) : {K.valo(one, _) == Nat.add(P, 38n) : Nat}
37  +e1 = K.run0(one, 30n, Con{128, Nil{}})
38  +e2 = L.subst(Nat, o => {K.valo(o, Con{128, Nil{}}) == WD.sc(7n, o) : Nat}, 1n, one, Equal.sym(Nat, one, 1n, h1), {==})
39  +e3 = Equal.trans(Nat, K.valo(one, R), LM.shn(30n, K.valo(one, Con{128, Nil{}})), LM.shn(30n, WD.sc(7n, one)), e1, Equal.cong(Nat, Nat, t => LM.shn(30n, t), K.valo(one, Con{128, Nil{}}), WD.sc(7n, one), e2))
40  +e4 = M.cong_add(Nat.mul(one, v(19)), 19n, C.shift(8n, K.valo(one, R)), WD.sc(255n, one), K.one_k(one, h1, v(19)), M.cong_sc(8n, K.valo(one, R), LM.shn(30n, WD.sc(7n, one)), e3))
41  +e5 = M.cong_r(19n, WD.sc(255n, one), Nat.add(P, 19n), Equal.sym(Nat, Nat.add(P, 19n), WD.sc(255n, one), hP))
42  Equal.trans(Nat, Nat.add(Nat.mul(one, v(19)), C.shift(8n, K.valo(one, R))), Nat.add(19n, WD.sc(255n, one)), Nat.add(P, 38n), e4, Equal.trans(Nat, Nat.add(19n, WD.sc(255n, one)), Nat.add(19n, Nat.add(P, 19n)), Nat.add(P, 38n), e5, NA.add_swap(19n, P, 19n)))
43
44def comp_p_okb() -> {LM.okb(32n, F.comp_p(), 128n) == True{} : Bool}:
45  {==}
46
47# 2^256 == 2 p + 38
48def t_val(+one: Nat, +h1: {one == 1n : Nat}, +pp: Nat, +hP: {Nat.add(1n+pp, 19n) == WD.sc(255n, one) : Nat}) -> {LM.shn(32n, one) == Nat.add(Nat.add(1n+pp, 1n+pp), 38n) : Nat}:
49  +P = {1n+pp : Nat}
50  +X = WD.sc(255n, one)
51  +e1 = Equal.sym(Nat, Nat.add(X, X), WD.sc(256n, one), M.sc_dbl(255n, one))
52  +e2 = M.cong_add(X, Nat.add(P, 19n), X, Nat.add(P, 19n), Equal.sym(Nat, Nat.add(P, 19n), X, hP), Equal.sym(Nat, Nat.add(P, 19n), X, hP))
53  Equal.trans(Nat, WD.sc(256n, one), Nat.add(X, X), Nat.add(Nat.add(P, P), 38n), e1, Equal.trans(Nat, Nat.add(X, X), Nat.add(Nat.add(P, 19n), Nat.add(P, 19n)), Nat.add(Nat.add(P, P), 38n), e2, M.add4(P, 19n, P, 19n)))
54
55# 38 <= p
56def p38(+one: Nat, +h1: {one == 1n : Nat}, +pp: Nat, +hP: {Nat.add(1n+pp, 19n) == WD.sc(255n, one) : Nat}) -> {Nat.is_le(38n, 1n+pp) == True{} : Bool}:
57  +P = {1n+pp : Nat}
58  +a = L.subst(Nat, o => {Nat.is_le(64n, WD.sc(6n, o)) == True{} : Bool}, 1n, one, Equal.sym(Nat, one, 1n, h1), {==})
59  +b = N.le_trans(64n, WD.sc(6n, one), WD.sc(255n, one), a, M.sc_mono(249n, 6n, one))
60  +c = L.subst(Nat, z => {Nat.is_le(64n, z) == True{} : Bool}, WD.sc(255n, one), Nat.add(P, 19n), Equal.sym(Nat, Nat.add(P, 19n), WD.sc(255n, one), hP), b)
61  +c2 = L.subst(Nat, z => {Nat.is_le(64n, z) == True{} : Bool}, Nat.add(P, 19n), Nat.add(19n, P), NA.add_comm(P, 19n), c)
62  +d = L.subst(Nat, z => {Nat.is_le(z, Nat.add(19n, P)) == True{} : Bool}, 64n, Nat.add(19n, 45n), {==}, c2)
63  +e = L.subst(Bool, z => {z == True{} : Bool}, Nat.is_le(Nat.add(19n, 45n), Nat.add(19n, P)), Nat.is_le(45n, P), NR.le_add_cancel(19n, 45n, P), d)
64  N.le_trans(38n, 45n, P, {==}, e)
65
66# ---- one conditional subtraction, with the constant as a parameter ----
67
68def csg(+x: List<&2, U32>, +cp: List<&2, U32>) -> List<&2, U32>:
69  F.csub_fin(F.carry(F.addl(x, cp), 0), x)
70
71def cs_eta(+r: F.Cr, +x: List<&2, U32>) -> {F.csub_fin(r, x) == F.select(LM.cc(r), x, LM.cl(r)) : List<&2, U32>}:
72  match r:
73    case F.Cr{a, c}:
74      {==}
75
76def ad_okb(+one: Nat, +h1: {one == 1n : Nat}, +x: List<&2, U32>, +cp: List<&2, U32>, +hx: {LM.okb(32n, x, 255n) == True{} : Bool}, +hk: {LM.okb(32n, cp, 128n) == True{} : Bool}) -> {LM.okb(32n, F.addl(x, cp), WD.sc(28n, one)) == True{} : Bool}:
77  +e = PL.addl_okb(one, h1, 32n, x, cp, 255n, 128n, hx, LM.okb_lea(32n, cp, 128n, hk), PL.okb_len_le(32n, cp, 128n, hk), FO.lt32_small(one, h1, Nat.add(255n, 128n), {==}))
78  PL.okb_mono(32n, F.addl(x, cp), Nat.add(255n, 128n), WD.sc(28n, one), FO.le_small(one, h1, Nat.add(255n, 128n), {==}), e)
79
80# value(s) + 2^256 c == value(x) + (p + 38)
81def cs_val(+one: Nat, +h1: {one == 1n : Nat}, +pp: Nat, +x: List<&2, U32>, +cp: List<&2, U32>, +hx: {LM.okb(32n, x, 255n) == True{} : Bool}, +hk: {LM.okb(32n, cp, 128n) == True{} : Bool}, +hv: {K.valo(one, cp) == Nat.add(1n+pp, 38n) : Nat}) -> {Nat.add(FS.value(LM.cl(F.carry(F.addl(x, cp), 0))), LM.shn(32n, v(LM.cc(F.carry(F.addl(x, cp), 0))))) == Nat.add(FS.value(x), Nat.add(1n+pp, 38n)) : Nat}:
82  +ys = F.addl(x, cp)
83  +e1 = FD.cr_val(one, h1, ys, ad_okb(one, h1, x, cp, hx, hk))
84  +e2 = PL.addl_val(one, h1, x, cp, 255n, 128n, LM.okb_lea(32n, x, 255n, hx), LM.okb_lea(32n, cp, 128n, hk), FO.lt32_small(one, h1, Nat.add(255n, 128n), {==}))
85  +e3 = Equal.trans(Nat, FS.value(cp), K.valo(one, cp), Nat.add(1n+pp, 38n), Equal.sym(Nat, K.valo(one, cp), FS.value(cp), K.valo_value(one, h1, cp)), hv)
86  Equal.trans(Nat, Nat.add(FS.value(LM.cl(F.carry(ys, 0))), LM.shn(32n, v(LM.cc(F.carry(ys, 0))))), FS.value(ys), Nat.add(FS.value(x), Nat.add(1n+pp, 38n)), e1, Equal.trans(Nat, FS.value(ys), Nat.add(FS.value(x), FS.value(cp)), Nat.add(FS.value(x), Nat.add(1n+pp, 38n)), e2, M.cong_r(FS.value(x), FS.value(cp), Nat.add(1n+pp, 38n), e3)))
87
88# case c == 0 (no carry out): x < p, the result is x
89def z_case(+one: Nat, +h1: {one == 1n : Nat}, +pp: Nat, +hP: {Nat.add(1n+pp, 19n) == WD.sc(255n, one) : Nat}, +x: List<&2, U32>, +cp: List<&2, U32>, +hx: {LM.okb(32n, x, 255n) == True{} : Bool}, +hk: {LM.okb(32n, cp, 128n) == True{} : Bool}, +hv: {K.valo(one, cp) == Nat.add(1n+pp, 38n) : Nat}, +hc: {Nat.is_lt(v(LM.cc(F.carry(F.addl(x, cp), 0))), one) == True{} : Bool}) -> {Nat.is_lt(FS.value(x), 1n+pp) == True{} : Bool}:
90  +P = {1n+pp : Nat}
91  +r = F.carry(F.addl(x, cp), 0)
92  +c = v(LM.cc(r))
93  +vs = FS.value(LM.cl(r))
94  +c0 = U.lt_one_zero(c, L.subst(Nat, o => {Nat.is_lt(c, o) == True{} : Bool}, one, 1n, h1, hc))
95  +ev = cs_val(one, h1, pp, x, cp, hx, hk, hv)
96  +ev0 = L.subst(Nat, z => {Nat.add(vs, LM.shn(32n, z)) == Nat.add(FS.value(x), Nat.add(P, 38n)) : Nat}, c, 0n, c0, ev)
97  +ev1 = Equal.trans(Nat, vs, Nat.add(vs, 0n), Nat.add(FS.value(x), Nat.add(P, 38n)), Equal.sym(Nat, Nat.add(vs, 0n), vs, N.add_zero(vs)), ev0)
98  +lt = RD.val_lt(one, h1, 32n, LM.cl(r), FD.cr_okb(one, h1, F.addl(x, cp), ad_okb(one, h1, x, cp, hx, hk)))
99  +lt2 = L.subst(Nat, z => {Nat.is_lt(vs, z) == True{} : Bool}, LM.shn(32n, one), Nat.add(Nat.add(P, P), 38n), t_val(one, h1, pp, hP), lt)
100  +lt3 = L.subst(Nat, z => {Nat.is_lt(z, Nat.add(Nat.add(P, P), 38n)) == True{} : Bool}, vs, Nat.add(FS.value(x), Nat.add(P, 38n)), ev1, lt2)
101  +lt4 = L.subst(Nat, z => {Nat.is_lt(Nat.add(FS.value(x), Nat.add(P, 38n)), z) == True{} : Bool}, Nat.add(Nat.add(P, P), 38n), Nat.add(P, Nat.add(P, 38n)), NA.add_assoc(P, P, 38n), lt3)
102  RD.lt_cancel_r(FS.value(x), P, Nat.add(P, 38n), lt4)
103
104# case c >= 1: c == 1 and value(s) + p == value(x)
105def o_c(+one: Nat, +h1: {one == 1n : Nat}, +pp: Nat, +hP: {Nat.add(1n+pp, 19n) == WD.sc(255n, one) : Nat}, +x: List<&2, U32>, +cp: List<&2, U32>, +hx: {LM.okb(32n, x, 255n) == True{} : Bool}, +hk: {LM.okb(32n, cp, 128n) == True{} : Bool}, +hv: {K.valo(one, cp) == Nat.add(1n+pp, 38n) : Nat}, +hc: {Nat.is_lt(v(LM.cc(F.carry(F.addl(x, cp), 0))), one) == False{} : Bool}) -> {v(LM.cc(F.carry(F.addl(x, cp), 0))) == one : Nat}:
106  +P = {1n+pp : Nat}
107  +r = F.carry(F.addl(x, cp), 0)
108  +c = v(LM.cc(r))
109  +vs = FS.value(LM.cl(r))
110  +T = LM.shn(32n, one)
111  +ev = cs_val(one, h1, pp, x, cp, hx, hk, hv)
112  +a = N.le_trans(LM.shn(32n, c), Nat.add(vs, LM.shn(32n, c)), Nat.add(FS.value(x), Nat.add(P, 38n)), PL.le_add_l(vs, LM.shn(32n, c)), N.eq_le(Nat.add(vs, LM.shn(32n, c)), Nat.add(FS.value(x), Nat.add(P, 38n)), ev))
113  +tv = t_val(one, h1, pp, hP)
114  +k1 = L.subst(Nat, z => {Nat.is_le(Nat.add(P, 38n), z) == True{} : Bool}, Nat.add(Nat.add(P, P), 38n), T, Equal.sym(Nat, T, Nat.add(Nat.add(P, P), 38n), tv), M.le_add_r(P, Nat.add(P, P), 38n, N.le_add_right(P, P)))
115  +b = N.lt_le_trans(Nat.add(FS.value(x), Nat.add(P, 38n)), Nat.add(T, Nat.add(P, 38n)), Nat.add(T, T), N.lt_add_r2(FS.value(x), T, Nat.add(P, 38n), RD.val_lt(one, h1, 32n, x, hx)), N.le_add_left(Nat.add(P, 38n), T, T, k1))
116  +d = N.le_lt_trans(LM.shn(32n, c), Nat.add(FS.value(x), Nat.add(P, 38n)), Nat.add(T, T), a, b)
117  +d2 = L.subst(Nat, z => {Nat.is_lt(LM.shn(32n, c), z) == True{} : Bool}, Nat.add(T, T), LM.shn(32n, Nat.add(one, one)), M.sc_add(256n, one, one), d)
118  +c2 = RD.shn_lt_cancel(c, Nat.add(one, one), d2)
119  +c2b = L.subst(Nat, o => {Nat.is_lt(c, Nat.add(o, o)) == True{} : Bool}, one, 1n, h1, c2)
120  +cle = L.subst(Nat, o => {Nat.is_le(c, o) == True{} : Bool}, 1n, one, Equal.sym(Nat, one, 1n, h1), N.lt_succ_le(c, 1n, c2b))
121  N.le_antisym(c, one, cle, N.not_lt_le(c, one, hc))
122
123def o_case(+one: Nat, +h1: {one == 1n : Nat}, +pp: Nat, +hP: {Nat.add(1n+pp, 19n) == WD.sc(255n, one) : Nat}, +x: List<&2, U32>, +cp: List<&2, U32>, +hx: {LM.okb(32n, x, 255n) == True{} : Bool}, +hk: {LM.okb(32n, cp, 128n) == True{} : Bool}, +hv: {K.valo(one, cp) == Nat.add(1n+pp, 38n) : Nat}, +hc: {Nat.is_lt(v(LM.cc(F.carry(F.addl(x, cp), 0))), one) == False{} : Bool}) -> {Nat.add(FS.value(LM.cl(F.carry(F.addl(x, cp), 0))), 1n+pp) == FS.value(x) : Nat}:
124  +P = {1n+pp : Nat}
125  +r = F.carry(F.addl(x, cp), 0)
126  +c = v(LM.cc(r))
127  +vs = FS.value(LM.cl(r))
128  +ev = cs_val(one, h1, pp, x, cp, hx, hk, hv)
129  +ev1 = L.subst(Nat, z => {Nat.add(vs, LM.shn(32n, z)) == Nat.add(FS.value(x), Nat.add(P, 38n)) : Nat}, c, one, o_c(one, h1, pp, hP, x, cp, hx, hk, hv, hc), ev)
130  +ev2 = L.subst(Nat, z => {Nat.add(vs, z) == Nat.add(FS.value(x), Nat.add(P, 38n)) : Nat}, LM.shn(32n, one), Nat.add(Nat.add(P, P), 38n), t_val(one, h1, pp, hP), ev1)
131  +ev3 = Equal.trans(Nat, Nat.add(Nat.add(vs, P), Nat.add(P, 38n)), Nat.add(vs, Nat.add(P, Nat.add(P, 38n))), Nat.add(FS.value(x), Nat.add(P, 38n)), NA.add_assoc(vs, P, Nat.add(P, 38n)), Equal.trans(Nat, Nat.add(vs, Nat.add(P, Nat.add(P, 38n))), Nat.add(vs, Nat.add(Nat.add(P, P), 38n)), Nat.add(FS.value(x), Nat.add(P, 38n)), M.cong_r(vs, Nat.add(P, Nat.add(P, 38n)), Nat.add(Nat.add(P, P), 38n), Equal.sym(Nat, Nat.add(Nat.add(P, P), 38n), Nat.add(P, Nat.add(P, 38n)), NA.add_assoc(P, P, 38n))), ev2))
132  G.cancel_r(Nat.add(vs, P), FS.value(x), Nat.add(P, 38n), ev3)
133
134# csub gives x (c == 0) or its limbs s (c == 1)
135def cs_zero(+one: Nat, +h1: {one == 1n : Nat}, +x: List<&2, U32>, +cp: List<&2, U32>, +hx: {LM.okb(32n, x, 255n) == True{} : Bool}, +hk: {LM.okb(32n, cp, 128n) == True{} : Bool}, +hc: {Nat.is_lt(v(LM.cc(F.carry(F.addl(x, cp), 0))), one) == True{} : Bool}) -> {csg(x, cp) == x : List<&2, U32>}:
136  +r = F.carry(F.addl(x, cp), 0)
137  +c0 = U.lt_one_zero(v(LM.cc(r)), L.subst(Nat, o => {Nat.is_lt(v(LM.cc(r)), o) == True{} : Bool}, one, 1n, h1, hc))
138  +cz = U.injective(LM.cc(r), 0, c0)
139  %Equal.sym(List<&2, U32>, F.csub_fin(r, x), F.select(LM.cc(r), x, LM.cl(r)), cs_eta(r, x)) : {_ == x : List<&2, U32>}
140  %Equal.cong(U32, List<&2, U32>, z => F.select(z, x, LM.cl(r)), 0, LM.cc(r), Equal.sym(U32, LM.cc(r), 0, cz)) : {_ == x : List<&2, U32>}
141  FO.select0(one, h1, 32n, x, LM.cl(r), hx, FD.cr_okb(one, h1, F.addl(x, cp), ad_okb(one, h1, x, cp, hx, hk)))
142
143def cs_one(+one: Nat, +h1: {one == 1n : Nat}, +pp: Nat, +hP: {Nat.add(1n+pp, 19n) == WD.sc(255n, one) : Nat}, +x: List<&2, U32>, +cp: List<&2, U32>, +hx: {LM.okb(32n, x, 255n) == True{} : Bool}, +hk: {LM.okb(32n, cp, 128n) == True{} : Bool}, +hv: {K.valo(one, cp) == Nat.add(1n+pp, 38n) : Nat}, +hc: {Nat.is_lt(v(LM.cc(F.carry(F.addl(x, cp), 0))), one) == False{} : Bool}) -> {csg(x, cp) == LM.cl(F.carry(F.addl(x, cp), 0)) : List<&2, U32>}:
144  +r = F.carry(F.addl(x, cp), 0)
145  +c1 = Equal.trans(Nat, v(LM.cc(r)), one, 1n, o_c(one, h1, pp, hP, x, cp, hx, hk, hv, hc), h1)
146  +co = U.injective(LM.cc(r), 1, c1)
147  %Equal.sym(List<&2, U32>, F.csub_fin(r, x), F.select(LM.cc(r), x, LM.cl(r)), cs_eta(r, x)) : {_ == LM.cl(r) : List<&2, U32>}
148  %Equal.cong(U32, List<&2, U32>, z => F.select(z, x, LM.cl(r)), 1, LM.cc(r), Equal.sym(U32, LM.cc(r), 1, co)) : {_ == LM.cl(r) : List<&2, U32>}
149  FO.select1(one, h1, 32n, x, LM.cl(r), hx, FD.cr_okb(one, h1, F.addl(x, cp), ad_okb(one, h1, x, cp, hx, hk)))