~/bend-docscommunity

proofs/crypto/curve25519/freeze.bend checks

raw source on the hub · import bend-collections-laws-crypto@1.0.0.0/proofs/crypto/curve25519/freeze.bend as Freeze

19 imports
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/u32.bend as U
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
import ./cong.bend as G

Definitions

def v source · line 25 · raw

@+x:U32 -> Nat

def comp_p_shape source · line 30 · raw

{0xa7e654f9780078ca65bf9e187da99d3e/src/crypto/curve25519/field.comp_p == 19 <> 0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/consts.rep(30n, 0, [128]) : List<&2, U32>}

def comp_p_val source · line 33 · raw

@+one:Nat -> @+h1:{one == 1n : Nat} -> @+pp:Nat -> @+hP:{Nat.add(1n+pp, 19n) == 0xa7e654f9780078ca65bf9e187da99d3e/proofs/lib/word.sc(255n, one) : Nat} -> {0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/consts.valo(one, 0xa7e654f9780078ca65bf9e187da99d3e/src/crypto/curve25519/field.comp_p) == Nat.add(1n+pp, 38n) : Nat}

def comp_p_okb source · line 44 · raw

{0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.okb(32n, 0xa7e654f9780078ca65bf9e187da99d3e/src/crypto/curve25519/field.comp_p, 128n) == True{} : Bool}

def t_val source · line 48 · raw

@+one:Nat -> @+h1:{one == 1n : Nat} -> @+pp:Nat -> @+hP:{Nat.add(1n+pp, 19n) == 0xa7e654f9780078ca65bf9e187da99d3e/proofs/lib/word.sc(255n, one) : Nat} -> {0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.shn(32n, one) == Nat.add(Nat.add(1n+pp, 1n+pp), 38n) : Nat}

2^256 == 2 p + 38

def p38 source · line 56 · raw

@+one:Nat -> @+h1:{one == 1n : Nat} -> @+pp:Nat -> @+hP:{Nat.add(1n+pp, 19n) == 0xa7e654f9780078ca65bf9e187da99d3e/proofs/lib/word.sc(255n, one) : Nat} -> {Nat.is_le(38n, 1n+pp) == True{} : Bool}

38 <= p

def csg source · line 68 · raw

@+x:List<&2, U32> -> @+cp:List<&2, U32> -> List<&2, U32>

def cs_eta source · line 71 · raw

@+r:0xa7e654f9780078ca65bf9e187da99d3e/src/crypto/curve25519/field.Cr -> @+x:List<&2, U32> -> {0xa7e654f9780078ca65bf9e187da99d3e/src/crypto/curve25519/field.csub_fin(r, x) == 0xa7e654f9780078ca65bf9e187da99d3e/src/crypto/curve25519/field.select(0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.cc(r), x, 0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/limbs.cl(r)) : List<&2, U32>}

def ad_okb source · line 76 · 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, 128n) == 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 cs_val source · line 81 · raw

@+one:Nat -> @+h1:{one == 1n : Nat} -> @+pp: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, 128n) == True{} : Bool} -> @+hv:{0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/consts.valo(one, cp) == Nat.add(1n+pp, 38n) : Nat} -> {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), Nat.add(1n+pp, 38n)) : Nat}

value(s) + 2^256 c == value(x) + (p + 38)

def z_case source · line 89 · raw

@+one:Nat -> @+h1:{one == 1n : Nat} -> @+pp:Nat -> @+hP:{Nat.add(1n+pp, 19n) == 0xa7e654f9780078ca65bf9e187da99d3e/proofs/lib/word.sc(255n, one) : 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, 128n) == True{} : Bool} -> @+hv:{0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/consts.valo(one, cp) == Nat.add(1n+pp, 38n) : 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+pp) == True{} : Bool}

case c == 0 (no carry out): x < p, the result is x

def o_c source · line 105 · raw

@+one:Nat -> @+h1:{one == 1n : Nat} -> @+pp:Nat -> @+hP:{Nat.add(1n+pp, 19n) == 0xa7e654f9780078ca65bf9e187da99d3e/proofs/lib/word.sc(255n, one) : 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, 128n) == True{} : Bool} -> @+hv:{0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/consts.valo(one, cp) == Nat.add(1n+pp, 38n) : 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: c == 1 and value(s) + p == value(x)

def o_case source · line 123 · raw

@+one:Nat -> @+h1:{one == 1n : Nat} -> @+pp:Nat -> @+hP:{Nat.add(1n+pp, 19n) == 0xa7e654f9780078ca65bf9e187da99d3e/proofs/lib/word.sc(255n, one) : 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, 128n) == True{} : Bool} -> @+hv:{0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/consts.valo(one, cp) == Nat.add(1n+pp, 38n) : 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+pp) == 0xa7e654f9780078ca65bf9e187da99d3e/spec/crypto/curve25519/field.value(x) : Nat}

def cs_zero source · line 135 · 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, 128n) == 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} -> {csg(x, cp) == x : List<&2, U32>}

csub gives x (c == 0) or its limbs s (c == 1)

def cs_one source · line 143 · raw

@+one:Nat -> @+h1:{one == 1n : Nat} -> @+pp:Nat -> @+hP:{Nat.add(1n+pp, 19n) == 0xa7e654f9780078ca65bf9e187da99d3e/proofs/lib/word.sc(255n, one) : 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, 128n) == True{} : Bool} -> @+hv:{0xa7e654f9780078ca65bf9e187da99d3e/proofs/crypto/curve25519/consts.valo(one, cp) == Nat.add(1n+pp, 38n) : 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} -> {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>}