~/bend-docscommunity

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}