import Base import ../../../spec/lib/common.bend as C import ../../../spec/crypto/curve25519/field.bend as FS import ../../../src/crypto/curve25519/field.bend as F import ../../lib/nat.bend as N import ../../lib/logic.bend as L import ../../lib/word.bend as WD import ../../lib/arith.bend as AR import ../../lib/lemmas/proofs/nat_algebra.bend as NA import ../../math/natural/arith.bend as NR import ./num.bend as M import ./limbs.bend as LM import ./poly.bend as PL import ./fold.bend as FD import ./reduce.bend as RD import ./consts.bend as K import ./fieldops.bend as FO # mul, sq and mul_small of src/crypto/curve25519/field.bend: the schoolbook # product of two tight elements has 63 limbs below 32 * 2^16 = 2^21; `wide` # folds limbs 32.. down by 38 (2^256 == 2 p + 38) into 32 limbs below 2^28; # `reduce` makes them tight. The value is the product mod p. def v(+x: U32) -> Nat: U32.to_nat(x) # ---- the product's limb bound: 32 * 2^8 * 2^8 ---- def cbn_add(+a: Nat, +b: Nat, +k: Nat) -> {PL.cbn(Nat.add(a, b), k) == Nat.add(PL.cbn(a, k), PL.cbn(b, k)) : Nat}: match a: case 0n: {==} case 1n+ +q: Equal.trans(Nat, Nat.add(k, PL.cbn(Nat.add(q, b), k)), Nat.add(k, Nat.add(PL.cbn(q, k), PL.cbn(b, k))), Nat.add(Nat.add(k, PL.cbn(q, k)), PL.cbn(b, k)), M.cong_r(k, PL.cbn(Nat.add(q, b), k), Nat.add(PL.cbn(q, k), PL.cbn(b, k)), cbn_add(q, b, k)), Equal.sym(Nat, Nat.add(Nat.add(k, PL.cbn(q, k)), PL.cbn(b, k)), Nat.add(k, Nat.add(PL.cbn(q, k), PL.cbn(b, k))), NA.add_assoc(k, PL.cbn(q, k), PL.cbn(b, k)))) def cbn_pow(+j: Nat, +k: Nat) -> {PL.cbn(WD.sc(j, 1n), k) == WD.sc(j, k) : Nat}: match j: case 0n: N.add_zero(k) case 1n+ +q: +n = WD.sc(q, 1n) +e1 = Equal.cong(Nat, Nat, t => PL.cbn(t, k), Nat.double(n), Nat.add(n, n), NA.double_self(n)) +e2 = cbn_add(n, n, k) +e3 = M.cong_add(PL.cbn(n, k), WD.sc(q, k), PL.cbn(n, k), WD.sc(q, k), cbn_pow(q, k), cbn_pow(q, k)) Equal.trans(Nat, PL.cbn(Nat.double(n), k), Nat.add(PL.cbn(n, k), PL.cbn(n, k)), WD.sc(1n+q, k), Equal.trans(Nat, PL.cbn(Nat.double(n), k), PL.cbn(Nat.add(n, n), k), Nat.add(PL.cbn(n, k), PL.cbn(n, k)), e1, e2), Equal.trans(Nat, Nat.add(PL.cbn(n, k), PL.cbn(n, k)), Nat.add(WD.sc(q, k), WD.sc(q, k)), WD.sc(1n+q, k), e3, M.sc_dbl(q, k))) def cb_okb(+n: Nat, +xs: List<&2, U32>, +b: Nat, +k: Nat, +e: {LM.okb(n, xs, b) == True{} : Bool}) -> {PL.cb(xs, k) == PL.cbn(n, k) : Nat}: match n xs: case 0n Nil{}: {==} case 0n Con{y, yt}: Empty.absurd({PL.cb(Con{y, yt}, k) == 0n : Nat}, L.false_true(e)) case 1n+m Nil{}: Empty.absurd({0n == PL.cbn(1n+m, k) : Nat}, L.false_true(e)) case 1n+ +m Con{+y, +yt}: M.cong_r(k, PL.cb(yt, k), PL.cbn(m, k), cb_okb(m, yt, b, k, LM.okb_tail(m, y, yt, b, e))) def mm8(+one: Nat, +h1: {one == 1n : Nat}) -> {Nat.mul(WD.sc(8n, one), WD.sc(8n, one)) == WD.sc(16n, one) : Nat}: Equal.trans(Nat, Nat.mul(WD.sc(8n, one), WD.sc(8n, one)), WD.sc(16n, Nat.mul(one, one)), WD.sc(16n, one), M.mul_sc2(8n, 8n, one, one), M.cong_sc(16n, Nat.mul(one, one), one, K.one_k(one, h1, one))) def cb32(+one: Nat, +h1: {one == 1n : Nat}, +a: List<&2, U32>, +b: Nat, +ha: {LM.okb(32n, a, b) == True{} : Bool}) -> {PL.cb(a, Nat.mul(WD.sc(8n, one), WD.sc(8n, one))) == WD.sc(21n, one) : Nat}: +mm = Nat.mul(WD.sc(8n, one), WD.sc(8n, one)) +e1 = cb_okb(32n, a, b, mm, ha) +e2 = cbn_pow(5n, mm) +e3 = M.cong_sc(5n, mm, WD.sc(16n, one), mm8(one, h1)) Equal.trans(Nat, PL.cb(a, mm), PL.cbn(32n, mm), WD.sc(21n, one), e1, Equal.trans(Nat, PL.cbn(32n, mm), WD.sc(5n, mm), WD.sc(21n, one), e2, e3)) def lea8(+one: Nat, +h1: {one == 1n : Nat}, +a: List<&2, U32>, +ha: {LM.okb(32n, a, 255n) == True{} : Bool}) -> {LM.lea(a, WD.sc(8n, one)) == True{} : Bool}: LM.lea_mono(a, 255n, WD.sc(8n, one), FD.le255(one, h1, 0n), LM.okb_lea(32n, a, 255n, ha)) def conv_ge(+m: Nat, +xs: List<&2, U32>, +ys: List<&2, U32>, +n: Nat, +b: Nat, +hx: {LM.okb(1n+m, xs, b) == True{} : Bool}, +hy: {PL.len_ge(n, ys) == True{} : Bool}) -> {PL.len_ge(n, F.conv(xs, ys)) == True{} : Bool}: match xs: case Nil{}: Empty.absurd({PL.len_ge(n, Nil{}) == True{} : Bool}, L.false_true(hx)) case Con{+x, +xt}: PL.conv_len_ge(n, x, xt, ys, hy) def conv_hc(+one: Nat, +h1: {one == 1n : Nat}, +a: List<&2, U32>, +ha: {LM.okb(32n, a, 255n) == True{} : Bool}) -> {Nat.is_lt(PL.cb(a, Nat.mul(WD.sc(8n, one), WD.sc(8n, one))), WD.sc(32n, one)) == True{} : Bool}: L.subst(Nat, z => {Nat.is_lt(z, WD.sc(32n, one)) == True{} : Bool}, WD.sc(21n, one), PL.cb(a, Nat.mul(WD.sc(8n, one), WD.sc(8n, one))), Equal.sym(Nat, PL.cb(a, Nat.mul(WD.sc(8n, one), WD.sc(8n, one))), WD.sc(21n, one), cb32(one, h1, a, 255n, ha)), LM.sc_lt(10n, 21n, one, h1)) def conv_lea21(+one: Nat, +h1: {one == 1n : Nat}, +a: List<&2, U32>, +b: List<&2, U32>, +ha: {LM.okb(32n, a, 255n) == True{} : Bool}, +hb: {LM.okb(32n, b, 255n) == True{} : Bool}) -> {LM.lea(F.conv(a, b), WD.sc(21n, one)) == True{} : Bool}: +s8 = WD.sc(8n, one) +e = PL.conv_lea(one, h1, a, b, s8, s8, lea8(one, h1, a, ha), lea8(one, h1, b, hb), conv_hc(one, h1, a, ha)) L.subst(Nat, z => {LM.lea(F.conv(a, b), z) == True{} : Bool}, PL.cb(a, Nat.mul(s8, s8)), WD.sc(21n, one), cb32(one, h1, a, 255n, ha), e) def conv_val(+one: Nat, +h1: {one == 1n : Nat}, +a: List<&2, U32>, +b: List<&2, U32>, +ha: {LM.okb(32n, a, 255n) == True{} : Bool}, +hb: {LM.okb(32n, b, 255n) == True{} : Bool}) -> {FS.value(F.conv(a, b)) == Nat.mul(FS.value(a), FS.value(b)) : Nat}: +s8 = WD.sc(8n, one) PL.conv_val(one, h1, a, b, s8, s8, lea8(one, h1, a, ha), lea8(one, h1, b, hb), conv_hc(one, h1, a, ha)) # ---- wide ---- def m38_27(+one: Nat, +h1: {one == 1n : Nat}) -> {Nat.is_le(Nat.mul(38n, WD.sc(21n, one)), WD.sc(27n, one)) == True{} : Bool}: FD.m38(WD.sc(21n, one)) def wsum_le(+one: Nat, +h1: {one == 1n : Nat}) -> {Nat.is_le(Nat.add(WD.sc(21n, one), Nat.mul(38n, WD.sc(21n, one))), WD.sc(28n, one)) == True{} : Bool}: +a = M.le_add2(WD.sc(21n, one), Nat.mul(38n, WD.sc(21n, one)), WD.sc(27n, one), WD.sc(27n, one), M.sc_mono(6n, 21n, one), m38_27(one, h1)) L.subst(Nat, z => {Nat.is_le(Nat.add(WD.sc(21n, one), Nat.mul(38n, WD.sc(21n, one))), z) == True{} : Bool}, Nat.add(WD.sc(27n, one), WD.sc(27n, one)), WD.sc(28n, one), M.sc_dbl(27n, one), a) def wsum_lt(+one: Nat, +h1: {one == 1n : Nat}) -> {Nat.is_lt(Nat.add(WD.sc(21n, one), Nat.mul(38n, WD.sc(21n, one))), WD.sc(32n, one)) == True{} : Bool}: N.le_lt_trans(Nat.add(WD.sc(21n, one), Nat.mul(38n, WD.sc(21n, one))), WD.sc(28n, one), WD.sc(32n, one), wsum_le(one, h1), LM.sc_lt(3n, 28n, one, h1)) def m38_lt(+one: Nat, +h1: {one == 1n : Nat}) -> {Nat.is_lt(Nat.mul(38n, WD.sc(21n, one)), WD.sc(32n, one)) == True{} : Bool}: N.le_lt_trans(Nat.mul(38n, WD.sc(21n, one)), WD.sc(27n, one), WD.sc(32n, one), m38_27(one, h1), LM.sc_lt(4n, 27n, one, h1)) def wide_okb(+one: Nat, +h1: {one == 1n : Nat}, +zs: List<&2, U32>, +hl: {LM.lea(zs, WD.sc(21n, one)) == True{} : Bool}, +hge: {PL.len_ge(32n, zs) == True{} : Bool}, +hle: {PL.len_le(64n, zs) == True{} : Bool}) -> {LM.okb(32n, F.wide(zs), WD.sc(28n, one)) == True{} : Bool}: +k21 = WD.sc(21n, one) +T = F.take(32n, zs) +D = F.drop(32n, zs) +okT = PL.take_okb(32n, zs, k21, hge, hl) +leD = PL.drop_lea(32n, zs, k21, hl) +lnD = PL.drop_len_le(32n, 32n, zs, hle) +leS = PL.scal_lea(one, h1, 38, D, 38n, k21, N.le_refl(38n), leD, m38_lt(one, h1)) +lnS = PL.scal_len_le(32n, 38, D, lnD) +e = PL.addl_okb(one, h1, 32n, T, F.scal(38, D), k21, Nat.mul(38n, k21), okT, leS, lnS, wsum_lt(one, h1)) PL.okb_mono(32n, F.addl(T, F.scal(38, D)), Nat.add(k21, Nat.mul(38n, k21)), WD.sc(28n, one), wsum_le(one, h1), e) def wide_mod(+one: Nat, +h1: {one == 1n : Nat}, +pp: Nat, +hP: {Nat.add(1n+pp, 19n) == WD.sc(255n, one) : Nat}, +zs: List<&2, U32>, +hl: {LM.lea(zs, WD.sc(21n, one)) == True{} : Bool}, +hge: {PL.len_ge(32n, zs) == True{} : Bool}) -> {Nat.mod(FS.value(F.wide(zs)), 1n+pp) == Nat.mod(FS.value(zs), 1n+pp) : Nat}: +k21 = WD.sc(21n, one) +T = F.take(32n, zs) +D = F.drop(32n, zs) +okT = PL.take_okb(32n, zs, k21, hge, hl) +leD = PL.drop_lea(32n, zs, k21, hl) +leS = PL.scal_lea(one, h1, 38, D, 38n, k21, N.le_refl(38n), leD, m38_lt(one, h1)) +VT = FS.value(T) +VD = FS.value(D) +ew = PL.addl_val(one, h1, T, F.scal(38, D), k21, Nat.mul(38n, k21), LM.okb_lea(32n, T, k21, okT), leS, wsum_lt(one, h1)) +es = PL.scal_val(one, h1, 38, D, 38n, k21, N.le_refl(38n), leD, m38_lt(one, h1)) +ew2 = Equal.trans(Nat, FS.value(F.wide(zs)), Nat.add(VT, FS.value(F.scal(38, D))), Nat.add(VT, Nat.mul(38n, VD)), ew, M.cong_r(VT, FS.value(F.scal(38, D)), Nat.mul(38n, VD), es)) +ez = Equal.trans(Nat, FS.value(zs), Nat.add(VT, LM.sh(T, VD)), Nat.add(VT, LM.shn(32n, VD)), PL.take_drop_val(32n, zs), M.cong_r(VT, LM.sh(T, VD), LM.shn(32n, VD), LM.sh_okb(32n, T, k21, VD, okT))) +ef = FD.fold_id(one, h1, pp, hP, VT, VD) +q = Nat.add(VD, VD) +ez2 = Equal.trans(Nat, FS.value(zs), Nat.add(VT, LM.shn(32n, VD)), Nat.add(Nat.mul(q, 1n+pp), FS.value(F.wide(zs))), ez, Equal.trans(Nat, Nat.add(VT, LM.shn(32n, VD)), Nat.add(Nat.mul(q, 1n+pp), Nat.add(VT, Nat.mul(38n, VD))), Nat.add(Nat.mul(q, 1n+pp), FS.value(F.wide(zs))), ef, M.cong_r(Nat.mul(q, 1n+pp), Nat.add(VT, Nat.mul(38n, VD)), FS.value(F.wide(zs)), Equal.sym(Nat, FS.value(F.wide(zs)), Nat.add(VT, Nat.mul(38n, VD)), ew2)))) Equal.trans(Nat, Nat.mod(FS.value(F.wide(zs)), 1n+pp), Nat.mod(Nat.add(Nat.mul(q, 1n+pp), FS.value(F.wide(zs))), 1n+pp), Nat.mod(FS.value(zs), 1n+pp), Equal.sym(Nat, Nat.mod(Nat.add(Nat.mul(q, 1n+pp), FS.value(F.wide(zs))), 1n+pp), Nat.mod(FS.value(F.wide(zs)), 1n+pp), NR.absorb(pp, q, FS.value(F.wide(zs)))), M.cong_mod(1n+pp, Nat.add(Nat.mul(q, 1n+pp), FS.value(F.wide(zs))), FS.value(zs), Equal.sym(Nat, FS.value(zs), Nat.add(Nat.mul(q, 1n+pp), FS.value(F.wide(zs))), ez2))) # ---- mul, sq ---- def wide_in(+one: Nat, +h1: {one == 1n : Nat}, +a: List<&2, U32>, +b: List<&2, U32>, +ha: {LM.okb(32n, a, 255n) == True{} : Bool}, +hb: {LM.okb(32n, b, 255n) == True{} : Bool}) -> {LM.okb(32n, F.wide(F.conv(a, b)), WD.sc(28n, one)) == True{} : Bool}: +zs = F.conv(a, b) +hge = conv_ge(31n, a, b, 32n, 255n, ha, PL.okb_len_ge(32n, b, 255n, hb)) +hle = PL.conv_len_le(32n, 32n, a, b, PL.okb_len_le(32n, a, 255n, ha), PL.okb_len_le(32n, b, 255n, hb)) wide_okb(one, h1, zs, conv_lea21(one, h1, a, b, ha, hb), hge, hle) def mul_okb(+one: Nat, +h1: {one == 1n : Nat}, +a: List<&2, U32>, +b: List<&2, U32>, +ha: {LM.okb(32n, a, 255n) == True{} : Bool}, +hb: {LM.okb(32n, b, 255n) == True{} : Bool}) -> {LM.okb(32n, F.mul(a, b), 255n) == True{} : Bool}: RD.reduce_okb(one, h1, F.wide(F.conv(a, b)), wide_in(one, h1, a, b, ha, hb)) def mul_mod(+one: Nat, +h1: {one == 1n : Nat}, +pp: Nat, +hP: {Nat.add(1n+pp, 19n) == WD.sc(255n, one) : Nat}, +a: List<&2, U32>, +b: List<&2, U32>, +ha: {LM.okb(32n, a, 255n) == True{} : Bool}, +hb: {LM.okb(32n, b, 255n) == True{} : Bool}) -> {Nat.mod(FS.value(F.mul(a, b)), 1n+pp) == Nat.mod(Nat.mul(FS.value(a), FS.value(b)), 1n+pp) : Nat}: +zs = F.conv(a, b) +hge = conv_ge(31n, a, b, 32n, 255n, ha, PL.okb_len_ge(32n, b, 255n, hb)) +e1 = RD.reduce_mod(one, h1, pp, hP, F.wide(zs), wide_in(one, h1, a, b, ha, hb)) +e2 = wide_mod(one, h1, pp, hP, zs, conv_lea21(one, h1, a, b, ha, hb), hge) +e3 = M.cong_mod(1n+pp, FS.value(zs), Nat.mul(FS.value(a), FS.value(b)), conv_val(one, h1, a, b, ha, hb)) Equal.trans(Nat, Nat.mod(FS.value(F.mul(a, b)), 1n+pp), Nat.mod(FS.value(F.wide(zs)), 1n+pp), Nat.mod(Nat.mul(FS.value(a), FS.value(b)), 1n+pp), e1, Equal.trans(Nat, Nat.mod(FS.value(F.wide(zs)), 1n+pp), Nat.mod(FS.value(zs), 1n+pp), Nat.mod(Nat.mul(FS.value(a), FS.value(b)), 1n+pp), e2, e3)) def sq_okb(+one: Nat, +h1: {one == 1n : Nat}, +a: List<&2, U32>, +ha: {LM.okb(32n, a, 255n) == True{} : Bool}) -> {LM.okb(32n, F.sq(a), 255n) == True{} : Bool}: mul_okb(one, h1, a, a, ha, ha) def sq_mod(+one: Nat, +h1: {one == 1n : Nat}, +pp: Nat, +hP: {Nat.add(1n+pp, 19n) == WD.sc(255n, one) : Nat}, +a: List<&2, U32>, +ha: {LM.okb(32n, a, 255n) == True{} : Bool}) -> {Nat.mod(FS.value(F.sq(a)), 1n+pp) == Nat.mod(Nat.mul(FS.value(a), FS.value(a)), 1n+pp) : Nat}: mul_mod(one, h1, pp, hP, a, a, ha, ha) # ---- mul_small (k at most 2^17) ---- def ms_lt(+one: Nat, +h1: {one == 1n : Nat}) -> {Nat.is_lt(Nat.mul(WD.sc(17n, one), 255n), WD.sc(32n, one)) == True{} : Bool}: +a = M.le_mul2(WD.sc(17n, one), 255n, WD.sc(17n, one), WD.sc(8n, one), N.le_refl(WD.sc(17n, one)), FD.le255(one, h1, 0n)) +b = L.subst(Nat, z => {Nat.is_le(Nat.mul(WD.sc(17n, one), 255n), z) == True{} : Bool}, Nat.mul(WD.sc(17n, one), WD.sc(8n, one)), WD.sc(25n, one), Equal.trans(Nat, Nat.mul(WD.sc(17n, one), WD.sc(8n, one)), WD.sc(25n, Nat.mul(one, one)), WD.sc(25n, one), M.mul_sc2(17n, 8n, one, one), M.cong_sc(25n, Nat.mul(one, one), one, K.one_k(one, h1, one))), a) N.le_lt_trans(Nat.mul(WD.sc(17n, one), 255n), WD.sc(25n, one), WD.sc(32n, one), b, LM.sc_lt(6n, 25n, one, h1)) def ms_le(+one: Nat, +h1: {one == 1n : Nat}) -> {Nat.is_le(Nat.mul(WD.sc(17n, one), 255n), WD.sc(28n, one)) == True{} : Bool}: +a = M.le_mul2(WD.sc(17n, one), 255n, WD.sc(17n, one), WD.sc(8n, one), N.le_refl(WD.sc(17n, one)), FD.le255(one, h1, 0n)) +b = L.subst(Nat, z => {Nat.is_le(Nat.mul(WD.sc(17n, one), 255n), z) == True{} : Bool}, Nat.mul(WD.sc(17n, one), WD.sc(8n, one)), WD.sc(25n, one), Equal.trans(Nat, Nat.mul(WD.sc(17n, one), WD.sc(8n, one)), WD.sc(25n, Nat.mul(one, one)), WD.sc(25n, one), M.mul_sc2(17n, 8n, one, one), M.cong_sc(25n, Nat.mul(one, one), one, K.one_k(one, h1, one))), a) N.le_trans(Nat.mul(WD.sc(17n, one), 255n), WD.sc(25n, one), WD.sc(28n, one), b, M.sc_mono(3n, 25n, one)) def scal_in(+one: Nat, +h1: {one == 1n : Nat}, +a: List<&2, U32>, +k: U32, +ha: {LM.okb(32n, a, 255n) == True{} : Bool}, +hk: {Nat.is_le(v(k), WD.sc(17n, one)) == True{} : Bool}) -> {LM.okb(32n, F.scal(k, a), WD.sc(28n, one)) == True{} : Bool}: +e = PL.scal_okb(one, h1, 32n, k, a, WD.sc(17n, one), 255n, hk, ha, ms_lt(one, h1)) PL.okb_mono(32n, F.scal(k, a), Nat.mul(WD.sc(17n, one), 255n), WD.sc(28n, one), ms_le(one, h1), e) def mul_small_okb(+one: Nat, +h1: {one == 1n : Nat}, +a: List<&2, U32>, +k: U32, +ha: {LM.okb(32n, a, 255n) == True{} : Bool}, +hk: {Nat.is_le(v(k), WD.sc(17n, one)) == True{} : Bool}) -> {LM.okb(32n, F.mul_small(a, k), 255n) == True{} : Bool}: RD.reduce_okb(one, h1, F.scal(k, a), scal_in(one, h1, a, k, ha, hk)) def mul_small_mod(+one: Nat, +h1: {one == 1n : Nat}, +pp: Nat, +hP: {Nat.add(1n+pp, 19n) == WD.sc(255n, one) : Nat}, +a: List<&2, U32>, +k: U32, +ha: {LM.okb(32n, a, 255n) == True{} : Bool}, +hk: {Nat.is_le(v(k), WD.sc(17n, one)) == True{} : Bool}) -> {Nat.mod(FS.value(F.mul_small(a, k)), 1n+pp) == Nat.mod(Nat.mul(FS.value(a), v(k)), 1n+pp) : Nat}: +e1 = RD.reduce_mod(one, h1, pp, hP, F.scal(k, a), scal_in(one, h1, a, k, ha, hk)) +e2 = PL.scal_val(one, h1, k, a, WD.sc(17n, one), 255n, hk, LM.okb_lea(32n, a, 255n, ha), ms_lt(one, h1)) +e3 = Equal.trans(Nat, FS.value(F.scal(k, a)), Nat.mul(v(k), FS.value(a)), Nat.mul(FS.value(a), v(k)), e2, NA.mul_comm(v(k), FS.value(a))) Equal.trans(Nat, Nat.mod(FS.value(F.mul_small(a, k)), 1n+pp), Nat.mod(FS.value(F.scal(k, a)), 1n+pp), Nat.mod(Nat.mul(FS.value(a), v(k)), 1n+pp), e1, M.cong_mod(1n+pp, FS.value(F.scal(k, a)), Nat.mul(FS.value(a), v(k)), e3))