proofs/crypto/curve25519/prime.bend source

proofs/crypto/curve25519/prime.bend on the hub · documented module

import Baseimport ../../../spec/lib/common.bend as Cimport ../../../spec/crypto/curve25519/field.bend as FSimport ../../lib/nat.bend as Nimport ../../lib/logic.bend as Limport ../../lib/word.bend as WDimport ../../lib/lemmas/proofs/nat_algebra.bend as NAimport ./num.bend as M# p = FS.prime(one) = 2^255 - 19 as 1 + pp, the form of the modular lemmas# (proofs/math/natural/arith.bend), with (1 + pp) + 19 == 2^255.def pp_of(+one: Nat) -> Nat:  Nat.sub(C.shift(255n, one), 20n)def p20(+one: Nat, +h1: {one == 1n : Nat}) -> {Nat.is_le(20n, WD.sc(255n, one)) == True{} : Bool}:  +a = L.subst(Nat, o => {Nat.is_le(20n, WD.sc(5n, o)) == True{} : Bool}, 1n, one, Equal.sym(Nat, one, 1n, h1), {==})  N.le_trans(20n, WD.sc(5n, one), WD.sc(255n, one), a, M.sc_mono(250n, 5n, one))# 20 + pp == 2^255def pp_sum(+one: Nat, +h1: {one == 1n : Nat}) -> {Nat.add(20n, pp_of(one)) == WD.sc(255n, one) : Nat}:  N.sub_add(WD.sc(255n, one), 20n, p20(one, h1))def hP(+one: Nat, +h1: {one == 1n : Nat}) -> {Nat.add(1n+pp_of(one), 19n) == WD.sc(255n, one) : Nat}:  +pp = pp_of(one)  +e = Equal.cong(Nat, Nat, t => 1n+t, Nat.add(pp, 19n), Nat.add(19n, pp), NA.add_comm(pp, 19n))  Equal.trans(Nat, Nat.add(1n+pp, 19n), Nat.add(20n, pp), WD.sc(255n, one), e, pp_sum(one, h1))def prime_eq(+one: Nat, +h1: {one == 1n : Nat}) -> {FS.prime(one) == 1n+pp_of(one) : Nat}:  +pp = pp_of(one)  +e = Equal.cong(Nat, Nat, t => Nat.sub(t, 19n), WD.sc(255n, one), Nat.add(20n, pp), Equal.sym(Nat, Nat.add(20n, pp), WD.sc(255n, one), pp_sum(one, h1)))  Equal.trans(Nat, Nat.sub(WD.sc(255n, one), 19n), Nat.sub(Nat.add(20n, pp), 19n), 1n+pp, e, N.add_sub_cancel(19n, 1n+pp))