proofs/crypto/curve25519/rel.bend

bend-collections-laws-crypto@1.0.0.0 · 87 lines · 16 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/lemmas/proofs/nat_algebra.bend as NA
9import bend-collections-laws-crypto@1.0.0.0/proofs/math/natural/arith.bend as NR
10import bend-collections-laws-crypto@1.0.0.0/proofs/crypto/curve25519/limbs.bend as LM
11import bend-collections-laws-crypto@1.0.0.0/proofs/crypto/curve25519/fieldops.bend as FO
12import bend-collections-laws-crypto@1.0.0.0/proofs/crypto/curve25519/mulw.bend as MW
13import bend-collections-laws-crypto@1.0.0.0/proofs/crypto/curve25519/pow.bend as PW
14import bend-collections-laws-crypto@1.0.0.0/proofs/crypto/curve25519/canon.bend as CN
15import bend-collections-laws-crypto@1.0.0.0/proofs/crypto/curve25519/cong.bend as G
16
17# The representation relation of the curve proofs: R(pp, x, a) is "x is a
18# tight element whose value is a mod p". Every field operation maps related
19# arguments to a result related to the specification's operation
20# (spec/crypto/curve25519/field.bend: fadd, fsub, fmul, finv).
21
22def R(+pp: Nat, +x: List<&2, U32>, +a: Nat) -> Data:
23  Sigma<&2, &2, {LM.okb(32n, x, 255n) == True{} : Bool}, _ => G.ceq(pp, FS.value(x), a)>
24
25def rc_add(+one: Nat, +h1: {one == 1n : Nat}, +pp: Nat, +hP: {Nat.add(1n+pp, 19n) == WD.sc(255n, one) : Nat}, +x: List<&2, U32>, +y: List<&2, U32>, +a: Nat, +b: Nat, +ox: {LM.okb(32n, x, 255n) == True{} : Bool}, +cx: G.ceq(pp, FS.value(x), a), +oy: {LM.okb(32n, y, 255n) == True{} : Bool}, +cy: G.ceq(pp, FS.value(y), b)) -> G.ceq(pp, FS.value(F.add(x, y)), FS.fadd(1n+pp, a, b)):
26  +e = G.c_trans(pp, FS.value(F.add(x, y)), Nat.add(FS.value(x), FS.value(y)), FS.fadd(1n+pp, a, b), FO.add_mod(one, h1, pp, hP, x, y, ox, oy), G.c_trans(pp, Nat.add(FS.value(x), FS.value(y)), Nat.add(a, b), FS.fadd(1n+pp, a, b), G.c_add(pp, FS.value(x), a, FS.value(y), b, cx, cy), G.c_sym(pp, Nat.mod(Nat.add(a, b), 1n+pp), Nat.add(a, b), G.c_mod(pp, Nat.add(a, b)))))
27  e
28
29def r_add(+one: Nat, +h1: {one == 1n : Nat}, +pp: Nat, +hP: {Nat.add(1n+pp, 19n) == WD.sc(255n, one) : Nat}, +x: List<&2, U32>, +y: List<&2, U32>, +a: Nat, +b: Nat, +ox: {LM.okb(32n, x, 255n) == True{} : Bool}, +cx: G.ceq(pp, FS.value(x), a), +oy: {LM.okb(32n, y, 255n) == True{} : Bool}, +cy: G.ceq(pp, FS.value(y), b)) -> R(pp, F.add(x, y), FS.fadd(1n+pp, a, b)):
30  (FO.add_okb(one, h1, x, y, ox, oy), rc_add(one, h1, pp, hP, x, y, a, b, ox, cx, oy, cy))
31
32def rc_sub(+one: Nat, +h1: {one == 1n : Nat}, +pp: Nat, +hP: {Nat.add(1n+pp, 19n) == WD.sc(255n, one) : Nat}, +x: List<&2, U32>, +y: List<&2, U32>, +a: Nat, +b: Nat, +ox: {LM.okb(32n, x, 255n) == True{} : Bool}, +cx: G.ceq(pp, FS.value(x), a), +oy: {LM.okb(32n, y, 255n) == True{} : Bool}, +cy: G.ceq(pp, FS.value(y), b)) -> G.ceq(pp, FS.value(F.sub(x, y)), FS.fsub(1n+pp, a, b)):
33  +P = {1n+pp : Nat}
34  +mb = Nat.mod(b, P)
35  +e1 = FO.sub_mod(one, h1, pp, hP, x, y, ox, oy)
36  +e2 = G.c_eq(pp, Nat.sub(Nat.add(FS.value(x), P), Nat.mod(FS.value(y), P)), Nat.sub(Nat.add(FS.value(x), P), mb), Equal.cong(Nat, Nat, z => Nat.sub(Nat.add(FS.value(x), P), z), Nat.mod(FS.value(y), P), mb, cy))
37  +e3 = G.c_subm(pp, FS.value(x), a, mb, cx, N.lt_le(mb, P, NR.dm_lt(pp, b)))
38  +e4 = G.c_sym(pp, Nat.mod(Nat.sub(Nat.add(a, P), mb), P), Nat.sub(Nat.add(a, P), mb), G.c_mod(pp, Nat.sub(Nat.add(a, P), mb)))
39  +e = G.c_trans(pp, FS.value(F.sub(x, y)), Nat.sub(Nat.add(FS.value(x), P), Nat.mod(FS.value(y), P)), FS.fsub(P, a, b), e1, G.c_trans(pp, Nat.sub(Nat.add(FS.value(x), P), Nat.mod(FS.value(y), P)), Nat.sub(Nat.add(FS.value(x), P), mb), FS.fsub(P, a, b), e2, G.c_trans(pp, Nat.sub(Nat.add(FS.value(x), P), mb), Nat.sub(Nat.add(a, P), mb), FS.fsub(P, a, b), e3, e4)))
40  e
41
42def r_sub(+one: Nat, +h1: {one == 1n : Nat}, +pp: Nat, +hP: {Nat.add(1n+pp, 19n) == WD.sc(255n, one) : Nat}, +x: List<&2, U32>, +y: List<&2, U32>, +a: Nat, +b: Nat, +ox: {LM.okb(32n, x, 255n) == True{} : Bool}, +cx: G.ceq(pp, FS.value(x), a), +oy: {LM.okb(32n, y, 255n) == True{} : Bool}, +cy: G.ceq(pp, FS.value(y), b)) -> R(pp, F.sub(x, y), FS.fsub(1n+pp, a, b)):
43  (FO.sub_okb(one, h1, x, y, ox, oy), rc_sub(one, h1, pp, hP, x, y, a, b, ox, cx, oy, cy))
44
45def rc_mul(+one: Nat, +h1: {one == 1n : Nat}, +pp: Nat, +hP: {Nat.add(1n+pp, 19n) == WD.sc(255n, one) : Nat}, +x: List<&2, U32>, +y: List<&2, U32>, +a: Nat, +b: Nat, +ox: {LM.okb(32n, x, 255n) == True{} : Bool}, +cx: G.ceq(pp, FS.value(x), a), +oy: {LM.okb(32n, y, 255n) == True{} : Bool}, +cy: G.ceq(pp, FS.value(y), b)) -> G.ceq(pp, FS.value(F.mul(x, y)), FS.fmul(1n+pp, a, b)):
46  +e = G.c_trans(pp, FS.value(F.mul(x, y)), Nat.mul(FS.value(x), FS.value(y)), FS.fmul(1n+pp, a, b), MW.mul_mod(one, h1, pp, hP, x, y, ox, oy), G.c_trans(pp, Nat.mul(FS.value(x), FS.value(y)), Nat.mul(a, b), FS.fmul(1n+pp, a, b), G.c_mul(pp, FS.value(x), a, FS.value(y), b, cx, cy), G.c_sym(pp, Nat.mod(Nat.mul(a, b), 1n+pp), Nat.mul(a, b), G.c_mod(pp, Nat.mul(a, b)))))
47  e
48
49def r_mul(+one: Nat, +h1: {one == 1n : Nat}, +pp: Nat, +hP: {Nat.add(1n+pp, 19n) == WD.sc(255n, one) : Nat}, +x: List<&2, U32>, +y: List<&2, U32>, +a: Nat, +b: Nat, +ox: {LM.okb(32n, x, 255n) == True{} : Bool}, +cx: G.ceq(pp, FS.value(x), a), +oy: {LM.okb(32n, y, 255n) == True{} : Bool}, +cy: G.ceq(pp, FS.value(y), b)) -> R(pp, F.mul(x, y), FS.fmul(1n+pp, a, b)):
50  (MW.mul_okb(one, h1, x, y, ox, oy), rc_mul(one, h1, pp, hP, x, y, a, b, ox, cx, oy, cy))
51
52def rc_sq(+one: Nat, +h1: {one == 1n : Nat}, +pp: Nat, +hP: {Nat.add(1n+pp, 19n) == WD.sc(255n, one) : Nat}, +x: List<&2, U32>, +a: Nat, +ox: {LM.okb(32n, x, 255n) == True{} : Bool}, +cx: G.ceq(pp, FS.value(x), a)) -> G.ceq(pp, FS.value(F.sq(x)), FS.fmul(1n+pp, a, a)):
53  rc_mul(one, h1, pp, hP, x, x, a, a, ox, cx, ox, cx)
54
55def r_sq(+one: Nat, +h1: {one == 1n : Nat}, +pp: Nat, +hP: {Nat.add(1n+pp, 19n) == WD.sc(255n, one) : Nat}, +x: List<&2, U32>, +a: Nat, +ox: {LM.okb(32n, x, 255n) == True{} : Bool}, +cx: G.ceq(pp, FS.value(x), a)) -> R(pp, F.sq(x), FS.fmul(1n+pp, a, a)):
56  r_mul(one, h1, pp, hP, x, x, a, a, ox, cx, ox, cx)
57
58def rc_inv(+one: Nat, +h1: {one == 1n : Nat}, +pp: Nat, +hP: {Nat.add(1n+pp, 19n) == WD.sc(255n, one) : Nat}, +x: List<&2, U32>, +a: Nat, +ox: {LM.okb(32n, x, 255n) == True{} : Bool}, +cx: G.ceq(pp, FS.value(x), a)) -> G.ceq(pp, FS.value(F.inv(x)), FS.finv(1n+pp, a)):
59  +P = {1n+pp : Nat}
60  +k = Nat.sub(P, 2n)
61  +e = G.c_trans(pp, FS.value(F.inv(x)), Nat.pow(FS.value(x), k), FS.finv(P, a), PW.inv_val(one, h1, pp, hP, x, ox), G.c_trans(pp, Nat.pow(FS.value(x), k), Nat.pow(a, k), FS.finv(P, a), G.c_pow(pp, FS.value(x), a, k, cx), G.c_sym(pp, Nat.mod(Nat.pow(a, k), P), Nat.pow(a, k), G.c_mod(pp, Nat.pow(a, k)))))
62  e
63
64def r_inv(+one: Nat, +h1: {one == 1n : Nat}, +pp: Nat, +hP: {Nat.add(1n+pp, 19n) == WD.sc(255n, one) : Nat}, +x: List<&2, U32>, +a: Nat, +ox: {LM.okb(32n, x, 255n) == True{} : Bool}, +cx: G.ceq(pp, FS.value(x), a)) -> R(pp, F.inv(x), FS.finv(1n+pp, a)):
65  (PW.inv_okb(one, h1, x, ox), rc_inv(one, h1, pp, hP, x, a, ox, cx))
66
67def rc_p58(+one: Nat, +h1: {one == 1n : Nat}, +pp: Nat, +hP: {Nat.add(1n+pp, 19n) == WD.sc(255n, one) : Nat}, +x: List<&2, U32>, +a: Nat, +ox: {LM.okb(32n, x, 255n) == True{} : Bool}, +cx: G.ceq(pp, FS.value(x), a)) -> G.ceq(pp, FS.value(F.pow_p58(x)), FS.fpow(1n+pp, a, Nat.div(Nat.sub(1n+pp, 5n), 8n))):
68  +P = {1n+pp : Nat}
69  +k = Nat.div(Nat.sub(P, 5n), 8n)
70  +e = G.c_trans(pp, FS.value(F.pow_p58(x)), Nat.pow(FS.value(x), k), FS.fpow(P, a, k), PW.p58_val(one, h1, pp, hP, x, ox), G.c_trans(pp, Nat.pow(FS.value(x), k), Nat.pow(a, k), FS.fpow(P, a, k), G.c_pow(pp, FS.value(x), a, k, cx), G.c_sym(pp, Nat.mod(Nat.pow(a, k), P), Nat.pow(a, k), G.c_mod(pp, Nat.pow(a, k)))))
71  e
72
73def r_p58(+one: Nat, +h1: {one == 1n : Nat}, +pp: Nat, +hP: {Nat.add(1n+pp, 19n) == WD.sc(255n, one) : Nat}, +x: List<&2, U32>, +a: Nat, +ox: {LM.okb(32n, x, 255n) == True{} : Bool}, +cx: G.ceq(pp, FS.value(x), a)) -> R(pp, F.pow_p58(x), FS.fpow(1n+pp, a, Nat.div(Nat.sub(1n+pp, 5n), 8n))):
74  (PW.p58_okb(one, h1, x, ox), rc_p58(one, h1, pp, hP, x, a, ox, cx))
75
76def r_o(+pp: Nat, +x: List<&2, U32>, +a: Nat, +r: R(pp, x, a)) -> {LM.okb(32n, x, 255n) == True{} : Bool}:
77  match r:
78    case (o, c):
79      o
80
81def r_c(+pp: Nat, +x: List<&2, U32>, +a: Nat, +r: R(pp, x, a)) -> G.ceq(pp, FS.value(x), a):
82  match r:
83    case (o, c):
84      c
85
86def mkR(+pp: Nat, +x: List<&2, U32>, +a: Nat, +o: {LM.okb(32n, x, 255n) == True{} : Bool}, +c: G.ceq(pp, FS.value(x), a)) -> R(pp, x, a):
87  (o, c)