proofs/crypto/ed25519/scalar.bend checks
raw source on the hub · import bend-collections-laws-crypto@1.0.0.0/proofs/crypto/ed25519/scalar.bend as Scalar
25 imports
import Base import ../../../spec/lib/common.bend as C import ../../../spec/crypto/curve25519/field.bend as FS import ../../../spec/crypto/curve25519/x25519.bend as SX import ../../../src/crypto/curve25519/field.bend as F import ../../../src/crypto/curve25519/x25519.bend as X import ../../../src/crypto/ed25519/scalar.bend as ESC 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/u32.bend as U import ../../lib/lemmas/proofs/nat_algebra.bend as NA import ../../math/natural/arith.bend as NR import ../../math/typed/width.bend as WI import ../curve25519/num.bend as M import ../curve25519/limbs.bend as LM import ../curve25519/poly.bend as PL import ../curve25519/fold.bend as FD import ../curve25519/reduce.bend as RD import ../curve25519/consts.bend as K import ../curve25519/fieldops.bend as FO import ../curve25519/freeze.bend as FZ import ../curve25519/cong.bend as G import ../curve25519/xbits.bend as XB
Definitions
def v source · line 33 · raw
@+x:U32 -> Nat
def T source · line 36 · raw
@+one:Nat -> Nat
def ad_okb source · line 41 · raw
@+one:Nat -> @+h1:{one == 1n : Nat} -> @+x:List<&2, U32> -> @+cp:List<&2, U32> -> @+hx:{0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.okb(32n, x, 255n) == True{} : Bool} -> @+hk:{0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.okb(32n, cp, 255n) == True{} : Bool} -> {0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.okb(32n, 0xa7e654f9780078ca65bf9e187da99d3e/src/crypto/curve25519/field.addl(x, cp), 0xa7e654f9780078ca65bf9e187da99d3e/proofs/lib/word.sc(28n, one)) == True{} : Bool}
def cvx source · line 44 · raw
@+one:Nat -> @+h1:{one == 1n : Nat} -> @+mm:Nat -> @+x:List<&2, U32> -> @+cp:List<&2, U32> -> @+hx:{0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.okb(32n, x, 255n) == True{} : Bool} -> @+hk:{0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.okb(32n, cp, 255n) == True{} : Bool} -> {Nat.add(0xa7e654f9780078ca65bf9e187da99d3e/spec/crypto/curve25519/field.value(0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.cl(0xa7e654f9780078ca65bf9e187da99d3e/src/crypto/curve25519/field.carry(0xa7e654f9780078ca65bf9e187da99d3e/src/crypto/curve25519/field.addl(x, cp), 0))), 0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.shn(32n, v(0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.cc(0xa7e654f9780078ca65bf9e187da99d3e/src/crypto/curve25519/field.carry(0xa7e654f9780078ca65bf9e187da99d3e/src/crypto/curve25519/field.addl(x, cp), 0))))) == Nat.add(0xa7e654f9780078ca65bf9e187da99d3e/spec/crypto/curve25519/field.value(x), 0xa7e654f9780078ca65bf9e187da99d3e/spec/crypto/curve25519/field.value(cp)) : Nat}
def cp_val source · line 48 · raw
@+one:Nat -> @+h1:{one == 1n : Nat} -> @+mm:Nat -> @+cp:List<&2, U32> -> @+hv:{Nat.add(0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/consts.valo(one, cp), 1n+mm) == T(one) : Nat} -> {Nat.add(0xa7e654f9780078ca65bf9e187da99d3e/spec/crypto/curve25519/field.value(cp), 1n+mm) == T(one) : Nat}
def mz source · line 52 · raw
@+one:Nat -> @+h1:{one == 1n : Nat} -> @+mm:Nat -> @+x:List<&2, U32> -> @+cp:List<&2, U32> -> @+hx:{0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.okb(32n, x, 255n) == True{} : Bool} -> @+hk:{0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.okb(32n, cp, 255n) == True{} : Bool} -> @+hv:{Nat.add(0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/consts.valo(one, cp), 1n+mm) == T(one) : Nat} -> @+hc:{Nat.is_lt(v(0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.cc(0xa7e654f9780078ca65bf9e187da99d3e/src/crypto/curve25519/field.carry(0xa7e654f9780078ca65bf9e187da99d3e/src/crypto/curve25519/field.addl(x, cp), 0))), one) == True{} : Bool} -> {Nat.is_lt(0xa7e654f9780078ca65bf9e187da99d3e/spec/crypto/curve25519/field.value(x), 1n+mm) == True{} : Bool}case c < 1: x < M
def mo_c source · line 67 · raw
@+one:Nat -> @+h1:{one == 1n : Nat} -> @+mm:Nat -> @+x:List<&2, U32> -> @+cp:List<&2, U32> -> @+hx:{0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.okb(32n, x, 255n) == True{} : Bool} -> @+hk:{0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.okb(32n, cp, 255n) == True{} : Bool} -> @+hv:{Nat.add(0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/consts.valo(one, cp), 1n+mm) == T(one) : Nat} -> @+hc:{Nat.is_lt(v(0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.cc(0xa7e654f9780078ca65bf9e187da99d3e/src/crypto/curve25519/field.carry(0xa7e654f9780078ca65bf9e187da99d3e/src/crypto/curve25519/field.addl(x, cp), 0))), one) == False{} : Bool} -> {v(0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.cc(0xa7e654f9780078ca65bf9e187da99d3e/src/crypto/curve25519/field.carry(0xa7e654f9780078ca65bf9e187da99d3e/src/crypto/curve25519/field.addl(x, cp), 0))) == one : Nat}case c >= 1 (x < 2^256): c == 1
def mo source · line 85 · raw
@+one:Nat -> @+h1:{one == 1n : Nat} -> @+mm:Nat -> @+x:List<&2, U32> -> @+cp:List<&2, U32> -> @+hx:{0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.okb(32n, x, 255n) == True{} : Bool} -> @+hk:{0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.okb(32n, cp, 255n) == True{} : Bool} -> @+hv:{Nat.add(0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/consts.valo(one, cp), 1n+mm) == T(one) : Nat} -> @+hc:{Nat.is_lt(v(0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.cc(0xa7e654f9780078ca65bf9e187da99d3e/src/crypto/curve25519/field.carry(0xa7e654f9780078ca65bf9e187da99d3e/src/crypto/curve25519/field.addl(x, cp), 0))), one) == False{} : Bool} -> {Nat.add(0xa7e654f9780078ca65bf9e187da99d3e/spec/crypto/curve25519/field.value(0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.cl(0xa7e654f9780078ca65bf9e187da99d3e/src/crypto/curve25519/field.carry(0xa7e654f9780078ca65bf9e187da99d3e/src/crypto/curve25519/field.addl(x, cp), 0))), 1n+mm) == 0xa7e654f9780078ca65bf9e187da99d3e/spec/crypto/curve25519/field.value(x) : Nat}case c >= 1: value(s) + M == value(x)
def cs_mz source · line 95 · raw
@+one:Nat -> @+h1:{one == 1n : Nat} -> @+x:List<&2, U32> -> @+cp:List<&2, U32> -> @+hx:{0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.okb(32n, x, 255n) == True{} : Bool} -> @+hk:{0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.okb(32n, cp, 255n) == True{} : Bool} -> @+hc:{Nat.is_lt(v(0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.cc(0xa7e654f9780078ca65bf9e187da99d3e/src/crypto/curve25519/field.carry(0xa7e654f9780078ca65bf9e187da99d3e/src/crypto/curve25519/field.addl(x, cp), 0))), one) == True{} : Bool} -> {0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/freeze.csg(x, cp) == x : List<&2, U32>}
def cs_mo source · line 103 · raw
@+one:Nat -> @+h1:{one == 1n : Nat} -> @+mm:Nat -> @+x:List<&2, U32> -> @+cp:List<&2, U32> -> @+hx:{0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.okb(32n, x, 255n) == True{} : Bool} -> @+hk:{0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.okb(32n, cp, 255n) == True{} : Bool} -> @+hv:{Nat.add(0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/consts.valo(one, cp), 1n+mm) == T(one) : Nat} -> @+hc:{Nat.is_lt(v(0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.cc(0xa7e654f9780078ca65bf9e187da99d3e/src/crypto/curve25519/field.carry(0xa7e654f9780078ca65bf9e187da99d3e/src/crypto/curve25519/field.addl(x, cp), 0))), one) == False{} : Bool} -> {0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/freeze.csg(x, cp) == 0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.cl(0xa7e654f9780078ca65bf9e187da99d3e/src/crypto/curve25519/field.carry(0xa7e654f9780078ca65bf9e187da99d3e/src/crypto/curve25519/field.addl(x, cp), 0)) : List<&2, U32>}
def cs_okb_by source · line 112 · raw
@+one:Nat -> @+h1:{one == 1n : Nat} -> @+mm:Nat -> @+x:List<&2, U32> -> @+cp:List<&2, U32> -> @+hx:{0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.okb(32n, x, 255n) == True{} : Bool} -> @+hk:{0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.okb(32n, cp, 255n) == True{} : Bool} -> @+hv:{Nat.add(0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/consts.valo(one, cp), 1n+mm) == T(one) : Nat} -> @+b:Bool -> @+hb:{Nat.is_lt(v(0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.cc(0xa7e654f9780078ca65bf9e187da99d3e/src/crypto/curve25519/field.carry(0xa7e654f9780078ca65bf9e187da99d3e/src/crypto/curve25519/field.addl(x, cp), 0))), one) == b : Bool} -> {0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.okb(32n, 0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/freeze.csg(x, cp), 255n) == True{} : Bool}
def cs_val_by source · line 121 · raw
@+one:Nat -> @+h1:{one == 1n : Nat} -> @+mm:Nat -> @+x:List<&2, U32> -> @+cp:List<&2, U32> -> @+hx:{0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.okb(32n, x, 255n) == True{} : Bool} -> @+hk:{0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.okb(32n, cp, 255n) == True{} : Bool} -> @+hv:{Nat.add(0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/consts.valo(one, cp), 1n+mm) == T(one) : Nat} -> @+h2m:{Nat.is_lt(0xa7e654f9780078ca65bf9e187da99d3e/spec/crypto/curve25519/field.value(x), Nat.add(1n+mm, 1n+mm)) == True{} : Bool} -> @+b:Bool -> @+hb:{Nat.is_lt(v(0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.cc(0xa7e654f9780078ca65bf9e187da99d3e/src/crypto/curve25519/field.carry(0xa7e654f9780078ca65bf9e187da99d3e/src/crypto/curve25519/field.addl(x, cp), 0))), one) == b : Bool} -> {0xa7e654f9780078ca65bf9e187da99d3e/spec/crypto/curve25519/field.value(0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/freeze.csg(x, cp)) == Nat.mod(0xa7e654f9780078ca65bf9e187da99d3e/spec/crypto/curve25519/field.value(x), 1n+mm) : Nat}
def lt_by source · line 136 · raw
@+one:Nat -> @+h1:{one == 1n : Nat} -> @+mm:Nat -> @+x:List<&2, U32> -> @+cp:List<&2, U32> -> @+hx:{0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.okb(32n, x, 255n) == True{} : Bool} -> @+hk:{0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.okb(32n, cp, 255n) == True{} : Bool} -> @+hv:{Nat.add(0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/consts.valo(one, cp), 1n+mm) == T(one) : Nat} -> @+b:Bool -> @+hb:{Nat.is_lt(v(0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.cc(0xa7e654f9780078ca65bf9e187da99d3e/src/crypto/curve25519/field.carry(0xa7e654f9780078ca65bf9e187da99d3e/src/crypto/curve25519/field.addl(x, cp), 0))), one) == b : Bool} -> {U32.is_eq(0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.cc(0xa7e654f9780078ca65bf9e187da99d3e/src/crypto/curve25519/field.carry(0xa7e654f9780078ca65bf9e187da99d3e/src/crypto/curve25519/field.addl(x, cp), 0)), 0) == Nat.is_lt(0xa7e654f9780078ca65bf9e187da99d3e/spec/crypto/curve25519/field.value(x), 1n+mm) : Bool}x < M exactly when the carry is 0
def sum_okb source · line 154 · raw
@+one:Nat -> @+h1:{one == 1n : Nat} -> @+a:List<&2, U32> -> @+b:List<&2, U32> -> @+ha:{0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.okb(32n, a, 255n) == True{} : Bool} -> @+hb:{0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.okb(32n, b, 255n) == True{} : Bool} -> {0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.okb(32n, 0xa7e654f9780078ca65bf9e187da99d3e/src/crypto/curve25519/field.cr_limbs(0xa7e654f9780078ca65bf9e187da99d3e/src/crypto/curve25519/field.carry(0xa7e654f9780078ca65bf9e187da99d3e/src/crypto/curve25519/field.addl(a, b), 0)), 255n) == True{} : Bool}
def sum_val source · line 158 · raw
@+one:Nat -> @+h1:{one == 1n : Nat} -> @+mm:Nat -> @+h2:{Nat.is_le(Nat.add(1n+mm, 1n+mm), T(one)) == True{} : Bool} -> @+a:List<&2, U32> -> @+b:List<&2, U32> -> @+ha:{0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.okb(32n, a, 255n) == True{} : Bool} -> @+hb:{0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.okb(32n, b, 255n) == True{} : Bool} -> @+la:{Nat.is_lt(0xa7e654f9780078ca65bf9e187da99d3e/spec/crypto/curve25519/field.value(a), 1n+mm) == True{} : Bool} -> @+lb:{Nat.is_lt(0xa7e654f9780078ca65bf9e187da99d3e/spec/crypto/curve25519/field.value(b), 1n+mm) == True{} : Bool} -> {0xa7e654f9780078ca65bf9e187da99d3e/spec/crypto/curve25519/field.value(0xa7e654f9780078ca65bf9e187da99d3e/src/crypto/curve25519/field.cr_limbs(0xa7e654f9780078ca65bf9e187da99d3e/src/crypto/curve25519/field.carry(0xa7e654f9780078ca65bf9e187da99d3e/src/crypto/curve25519/field.addl(a, b), 0))) == Nat.add(0xa7e654f9780078ca65bf9e187da99d3e/spec/crypto/curve25519/field.value(a), 0xa7e654f9780078ca65bf9e187da99d3e/spec/crypto/curve25519/field.value(b)) : Nat}a + b < 2 M <= 2^256: no carry out, the limbs hold a + b
def addg source · line 170 · raw
@+a:List<&2, U32> -> @+b:List<&2, U32> -> @+cp:List<&2, U32> -> List<&2, U32>
addm with its constant as a parameter
def addg_okb source · line 173 · raw
@+one:Nat -> @+h1:{one == 1n : Nat} -> @+mm:Nat -> @+cp:List<&2, U32> -> @+hk:{0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.okb(32n, cp, 255n) == True{} : Bool} -> @+hv:{Nat.add(0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/consts.valo(one, cp), 1n+mm) == T(one) : Nat} -> @+a:List<&2, U32> -> @+b:List<&2, U32> -> @+ha:{0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.okb(32n, a, 255n) == True{} : Bool} -> @+hb:{0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.okb(32n, b, 255n) == True{} : Bool} -> {0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.okb(32n, addg(a, b, cp), 255n) == True{} : Bool}
def addg_val source · line 177 · raw
@+one:Nat -> @+h1:{one == 1n : Nat} -> @+mm:Nat -> @+h2:{Nat.is_le(Nat.add(1n+mm, 1n+mm), T(one)) == True{} : Bool} -> @+cp:List<&2, U32> -> @+hk:{0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.okb(32n, cp, 255n) == True{} : Bool} -> @+hv:{Nat.add(0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/consts.valo(one, cp), 1n+mm) == T(one) : Nat} -> @+a:List<&2, U32> -> @+b:List<&2, U32> -> @+ha:{0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.okb(32n, a, 255n) == True{} : Bool} -> @+hb:{0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.okb(32n, b, 255n) == True{} : Bool} -> @+la:{Nat.is_lt(0xa7e654f9780078ca65bf9e187da99d3e/spec/crypto/curve25519/field.value(a), 1n+mm) == True{} : Bool} -> @+lb:{Nat.is_lt(0xa7e654f9780078ca65bf9e187da99d3e/spec/crypto/curve25519/field.value(b), 1n+mm) == True{} : Bool} -> {0xa7e654f9780078ca65bf9e187da99d3e/spec/crypto/curve25519/field.value(addg(a, b, cp)) == Nat.mod(Nat.add(0xa7e654f9780078ca65bf9e187da99d3e/spec/crypto/curve25519/field.value(a), 0xa7e654f9780078ca65bf9e187da99d3e/spec/crypto/curve25519/field.value(b)), 1n+mm) : Nat}
def lt_mod source · line 184 · raw
@+mm:Nat -> @+x:Nat -> {Nat.is_lt(Nat.mod(x, 1n+mm), 1n+mm) == True{} : Bool}