Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-crypto

Source of release 0.6.0

0.6.0 / src / p256.lucb

## NIST P-256 (secp256r1): ECDH, ECDSA signing with RFC 6979 deterministic
## nonces, ECDSA verification and key generation. The point layer follows
## Thomas Pornin's BearSSL `ec_p256_m31` (MIT; see NOTICE.md): Jacobian
## coordinates, a 2-bit window with constant-time selection for a variable
## point, a 4-bit window over a fixed table of k*G with constant-time lookup
## for the generator, and Fermat inversion with a fixed exponent. Field and
## scalar arithmetic (p256_field) is branch-free, so secret scalars (private
## keys, nonces) never steer a branch or a memory index. Validity checks on
## public inputs, and RFC 6979's retry on an out-of-range candidate, do branch.
import os
import hmac
import p256_field as f
import p256_table as table
import secure
import sha2
import memory

let b_montgomery: u32[8] = [0x29c4bddf, 0xd89cdf62, 0x78843090, 0xacf005cd, 0xf7212ed6, 0xe5a220ab, 0x04874834, 0xdc30061d]

## A point in Jacobian coordinates (Montgomery form); z = 0 is infinity.
struct Point:
    var x: u32[8]
    var y: u32[8]
    var z: u32[8]

func copy_if(out: Point*, select: u32, value: const Point*):
    f.choose(out.x, select, value.x, out.x)
    f.choose(out.y, select, value.y, out.y)
    f.choose(out.z, select, value.z, out.z)

func eq32(a: u32, b: u32) -> u32:
    let d = a ^ b
    return ((d | (0 -% d)) >> 31) ^ 1

## Q = 2Q, valid for every point including infinity (formulas of BearSSL's
## p256_double, a = -3).
func double(q: Point*):
    var t1: u32[8]
    var t2: u32[8]
    var t3: u32[8]
    var t4: u32[8]
    f.square(t1, q.z, &f.field)
    f.add(t2, q.x, t1, &f.field)
    f.sub(t1, q.x, t1, &f.field)
    f.mul(t3, t1, t2, &f.field)
    f.add(t1, t3, t3, &f.field)
    f.add(t1, t3, t1, &f.field)
    f.square(t3, q.y, &f.field)
    f.add(t3, t3, t3, &f.field)
    f.mul(t2, q.x, t3, &f.field)
    f.add(t2, t2, t2, &f.field)
    f.square(q.x, t1, &f.field)
    f.sub(q.x, q.x, t2, &f.field)
    f.sub(q.x, q.x, t2, &f.field)
    f.mul(t4, q.y, q.z, &f.field)
    f.add(q.z, t4, t4, &f.field)
    f.sub(t2, t2, q.x, &f.field)
    f.mul(q.y, t1, t2, &f.field)
    f.square(t4, t3, &f.field)
    f.add(t4, t4, t4, &f.field)
    f.sub(q.y, q.y, t4, &f.field)

## P1 += P2 for P1, P2 not infinity and P1 != P2. Returns 1 when the Y
## coordinates differ (so an infinite result means P1 = -P2), else 0 (as
## BearSSL's p256_add). `mixed` takes P2 in affine form (z = 1).
func add(p1: Point*, p2: const Point*, mixed: bool) -> u32:
    var t1: u32[8]
    var t2: u32[8]
    var t3: u32[8]
    var t4: u32[8]
    var t5: u32[8]
    var t6: u32[8]
    var t7: u32[8]
    if mixed:
        t1 = p1.x
        t3 = p1.y
    else:
        f.square(t3, p2.z, &f.field)
        f.mul(t1, p1.x, t3, &f.field)
        f.mul(t4, p2.z, t3, &f.field)
        f.mul(t3, p1.y, t4, &f.field)
    f.square(t4, p1.z, &f.field)
    f.mul(t2, p2.x, t4, &f.field)
    f.mul(t5, p1.z, t4, &f.field)
    f.mul(t4, p2.y, t5, &f.field)
    f.sub(t2, t2, t1, &f.field)
    f.sub(t4, t4, t3, &f.field)
    let differ = f.is_zero(t4) ^ 1
    f.square(t7, t2, &f.field)
    f.mul(t6, t1, t7, &f.field)
    f.mul(t5, t7, t2, &f.field)
    f.square(p1.x, t4, &f.field)
    f.sub(p1.x, p1.x, t5, &f.field)
    f.sub(p1.x, p1.x, t6, &f.field)
    f.sub(p1.x, p1.x, t6, &f.field)
    f.sub(t6, t6, p1.x, &f.field)
    f.mul(p1.y, t4, t6, &f.field)
    f.mul(t1, t5, t3, &f.field)
    f.sub(p1.y, p1.y, t1, &f.field)
    if mixed:
        f.mul(p1.z, p1.z, t2, &f.field)
    else:
        f.mul(t1, p1.z, p2.z, &f.field)
        f.mul(p1.z, t1, t2, &f.field)
    return differ

## k*P for a valid point P (not infinity) and a 32-byte big-endian scalar
## k < n: two bits at a time, the window entry and the accumulator update
## chosen by masks (BearSSL p256_mul).
func multiply_point(p: const Point*, k: const u8[]) -> Point:
    var p2 = *p
    double(&p2)
    var p3 = *p
    _ = add(&p3, &p2, false)
    var q = Point()
    var infinite: u32 = 0xffffffff
    for i in 0..<(usize)32:
        var shift: i32 = 6
        while shift >= 0:
            double(&q)
            double(&q)
            let bits = (u32)(k[i] >> (u8)shift) & 3
            var t = *p
            copy_if(&t, f.mask(eq32(bits, 2)), &p2)
            copy_if(&t, f.mask(eq32(bits, 3)), &p3)
            var u = q
            _ = add(&u, &t, false)
            let nonzero = f.mask(eq32(bits, 0) ^ 1)
            copy_if(&q, nonzero & infinite, &t)
            copy_if(&q, nonzero & ~infinite, &u)
            infinite &= ~nonzero
            shift -= 2
    return q

## k*G four bits at a time over the fixed table, with a constant-time scan
## of all fifteen entries (BearSSL p256_mulgen).
func multiply_generator_point(k: const u8[]) -> Point:
    var q = Point()
    var infinite: u32 = 0xffffffff
    for i in 0..<(usize)32:
        for half in 0..<(usize)2:
            double(&q)
            double(&q)
            double(&q)
            double(&q)
            let bits = (u32)(k[i] >> (u8)(4 - 4 * half)) & 15
            var t = Point()
            for entry in 0..<(usize)15:
                let select = f.mask(eq32(bits, (u32)entry + 1))
                for j in 0..<(usize)8:
                    t.x[j] |= select & table.generator_window[entry * 16 + j]
                    t.y[j] |= select & table.generator_window[entry * 16 + 8 + j]
            t.z = f.field.one
            var u = q
            _ = add(&u, &t, true)
            let nonzero = f.mask(eq32(bits, 0) ^ 1)
            copy_if(&q, nonzero & infinite, &t)
            copy_if(&q, nonzero & ~infinite, &u)
            infinite &= ~nonzero
    return q

## G itself: the first entry of the fixed window.
func generator_point() -> Point:
    var g = Point()
    for j in 0..<(usize)8:
        g.x[j] = table.generator_window[j]
        g.y[j] = table.generator_window[8 + j]
    g.z = f.field.one
    return g

## Affine coordinates in ordinary form; infinity becomes (0, 0).
func to_affine(p: const Point*, x: u32[], y: u32[]):
    var zi: u32[8]
    var zi2: u32[8]
    var t: u32[8]
    f.invert(zi, p.z, &f.field)
    f.square(zi2, zi, &f.field)
    f.mul(t, p.x, zi2, &f.field)
    f.from_montgomery(x, t, &f.field)
    f.mul(zi2, zi2, zi, &f.field)
    f.mul(t, p.y, zi2, &f.field)
    f.from_montgomery(y, t, &f.field)

func is_infinity(p: const Point*) -> bool:
    return f.is_zero(p.z) == 1

## Decode and validate a public point: coordinates below p, on the curve.
func decode_point(x_bytes: const u8[], y_bytes: const u8[], out: Point*) -> bool:
    if x_bytes.length != 32 or y_bytes.length != 32:
        return false
    var x: u32[8]
    var y: u32[8]
    f.decode(x, x_bytes)
    f.decode(y, y_bytes)
    if f.less(x, f.field.m) == 0 or f.less(y, f.field.m) == 0:
        return false
    f.to_montgomery(out.x, x, &f.field)
    f.to_montgomery(out.y, y, &f.field)
    out.z = f.field.one
    var left: u32[8]
    var right: u32[8]
    var three_x: u32[8]
    f.square(left, out.y, &f.field)
    f.square(right, out.x, &f.field)
    f.mul(right, right, out.x, &f.field)
    f.add(three_x, out.x, out.x, &f.field)
    f.add(three_x, three_x, out.x, &f.field)
    f.sub(right, right, three_x, &f.field)
    f.add(right, right, b_montgomery, &f.field)
    return f.equal(left, right) == 1

## Whether a 32-byte big-endian scalar lies in [1, n - 1].
func scalar_in_range(k: const u8[]) -> bool:
    var v: u32[8]
    f.decode(v, k)
    return f.is_zero(v) == 0 and f.less(v, f.order.m) == 1

func write_point(p: const Point*, x_out: u8[], y_out: u8[]):
    var x: u32[8]
    var y: u32[8]
    to_affine(p, x, y)
    f.encode(x_out, x)
    f.encode(y_out, y)

## P1 + P2 for points that may be infinite or equal (public data only).
func combine(a: const Point*, b: const Point*) -> Point:
    if is_infinity(a): return *b
    if is_infinity(b): return *a
    var sum = *a
    let differ = add(&sum, b, false)
    if is_infinity(&sum) and differ == 0:
        sum = *a
        double(&sum)
    return sum

## u*A + v*B for public scalars (32 big-endian bytes) with a joint two-bit
## window (Straus): a table of i*A + j*B for i, j in 0..3, then two doublings
## and one addition per bit pair. Variable time; verification only.
func joint_multiply(u: const u8[], a: const Point*, v: const u8[], b: const Point*) -> Point:
    var window: Point[16]
    window[1] = *b
    window[2] = *b
    double(&window[2])
    window[3] = combine(&window[2], b)
    window[4] = *a
    window[8] = *a
    double(&window[8])
    window[12] = combine(&window[8], a)
    for i in 1..<(usize)4:
        for j in 1..<(usize)4:
            window[i * 4 + j] = combine(&window[i * 4], &window[j])
    var q = Point()
    for i in 0..<(usize)32:
        var shift: i32 = 6
        while shift >= 0:
            double(&q)
            double(&q)
            let index = (usize)((u[i] >> (u8)shift) & 3) * 4 + (usize)((v[i] >> (u8)shift) & 3)
            if index != 0:
                q = combine(&q, &window[index])
            shift -= 2
    return q

## k*(x, y) for a valid point and 0 <= k < n; writes the affine result and
## returns false when it is the point at infinity (as BearSSL's `mul`).
pub func multiply(k: const u8[], x: const u8[], y: const u8[], out_x: u8[], out_y: u8[]) -> bool!:
    var p = Point()
    if not decode_point(x, y, &p):
        error(sha2.invalid, "P-256 point is not on the curve")
    if k.length != 32 or (not scalar_in_range(k) and not all_zero(k)):
        error(sha2.invalid, "P-256 scalar must be 32 bytes below the group order")
    let q = multiply_point(&p, k)
    write_point(&q, out_x, out_y)
    return not is_infinity(&q)

## k*G for 0 <= k < n; false for the point at infinity.
pub func multiply_generator(k: const u8[], out_x: u8[], out_y: u8[]) -> bool!:
    if k.length != 32 or (not scalar_in_range(k) and not all_zero(k)):
        error(sha2.invalid, "P-256 scalar must be 32 bytes below the group order")
    let q = multiply_generator_point(k)
    write_point(&q, out_x, out_y)
    return not is_infinity(&q)

## u*A + v*B for valid points and scalars below n (public data); false for
## the point at infinity (as BearSSL's `muladd`).
pub func multiply_add(ax: const u8[], ay: const u8[], u: const u8[], bx: const u8[], by: const u8[], v: const u8[],
                      out_x: u8[], out_y: u8[]) -> bool!:
    var a = Point()
    var b = Point()
    if not decode_point(ax, ay, &a) or not decode_point(bx, by, &b):
        error(sha2.invalid, "P-256 point is not on the curve")
    let sum = joint_multiply(u, &a, v, &b)
    write_point(&sum, out_x, out_y)
    return not is_infinity(&sum)

func all_zero(k: const u8[]) -> bool:
    var acc: u8 = 0
    for i in 0..<k.length: acc |= k[i]
    return acc == 0

## Q = d*G. `d`, `qx` and `qy` are 32 big-endian bytes.
pub func public_from_private(d: const u8[], qx: u8[], qy: u8[]) -> !:
    if d.length != 32 or qx.length < 32 or qy.length < 32 or not scalar_in_range(d):
        error(sha2.invalid, "P-256 private key must be 32 bytes in [1, n - 1]")
    let q = multiply_generator_point(d)
    write_point(&q, qx[..<32], qy[..<32])

## A fresh key pair from the OS random generator.
pub func keygen(d: u8[], qx: u8[], qy: u8[]) -> !:
    if d.length < 32 or qx.length < 32 or qy.length < 32:
        error(sha2.invalid, "P-256 key buffers must be 32 bytes")
    for _ in 0..<(usize)64:
        try os.random_bytes(d[..<32])
        if scalar_in_range(d[..<32]):
            try public_from_private(d[..<32], qx, qy)
            return
    error(sha2.invalid, "could not sample a P-256 private key")

## ECDH (SEC 1 §3.3.1): the 32-byte x-coordinate of d*Q for a valid peer
## point Q.
pub func ecdh(d: const u8[], qx: const u8[], qy: const u8[], shared: u8[]) -> !:
    if d.length != 32 or shared.length < 32 or not scalar_in_range(d):
        error(sha2.invalid, "P-256 private key must be 32 bytes in [1, n - 1]")
    var p = Point()
    if not decode_point(qx, qy, &p):
        error(sha2.invalid, "P-256 ECDH peer key is not a curve point")
    var q = multiply_point(&p, d)
    defer secure.wipe(u8[]((u8*)&q, memory.size_of(Point)))
    if is_infinity(&q):
        error(sha2.invalid, "P-256 ECDH produced the point at infinity")
    var x: u32[8]
    var y: u32[8]
    to_affine(&q, x, y)
    f.encode(shared[..<32], x)

## The digest as an integer modulo n (SEC 1 §4.1.3 step 5: the leftmost 256
## bits when longer).
func digest_scalar(digest: const u8[], out: u32[]):
    var bytes: u8[32]
    if digest.length >= 32:
        for i in 0..<(usize)32: bytes[i] = digest[i]
    else:
        for i in 0..<digest.length: bytes[32 - digest.length + i] = digest[i]
    var v: u32[8]
    f.decode(v, bytes)
    reduce_order(v, out)

func hash_for(digest: const u8[]) -> str!:
    if digest.length == 28: return "sha224"
    if digest.length == 32: return "sha256"
    if digest.length == 48: return "sha384"
    if digest.length == 64: return "sha512"
    error(sha2.invalid, "P-256 signing needs a SHA-224/256/384/512 digest")

## RFC 6979 §3.2 nonce generation with HMAC over the digest's hash.
struct Nonces:
    var key: u8[64]
    var value: u8[64]
    var size: usize
    var algorithm: str

    static func start(d: const u8[], digest: const u8[]) -> Nonces!:
        var state = Nonces(algorithm = try hash_for(digest))
        state.size = digest.length
        for i in 0..<state.size: state.value[i] = 1
        var h: u32[8]
        digest_scalar(digest, h)
        var h_bytes: u8[32]
        f.encode(h_bytes, h)
        for separator in [(u8)0, 1]:
            var context = hmac.Context()
            defer context.close()
            try context.start(state.key[..<state.size], state.algorithm)
            try context.update(state.value[..<state.size])
            var sep: u8[1]
            sep[0] = separator
            try context.update(sep)
            try context.update(d)
            try context.update(h_bytes)
            _ = try context.finish(state.key)
            _ = try hmac.authenticate(state.key[..<state.size], state.value[..<state.size], state.value, state.algorithm)
        return state

    ## The next candidate k (RFC 6979 step h).
    func next(out: u8[]) -> !:
        var produced: usize = 0
        var t: u8[64]
        while produced < 32:
            _ = try hmac.authenticate(self.key[..<self.size], self.value[..<self.size], self.value, self.algorithm)
            for i in 0..<self.size:
                t[produced + i] = self.value[i]
            produced += self.size
        for i in 0..<(usize)32: out[i] = t[i]

    ## Step h.3 after a rejected candidate.
    func reseed() -> !:
        var zero: u8[1]
        var input: u8[65]
        for i in 0..<self.size: input[i] = self.value[i]
        input[self.size] = zero[0]
        _ = try hmac.authenticate(self.key[..<self.size], input[..<self.size + 1], self.key, self.algorithm)
        _ = try hmac.authenticate(self.key[..<self.size], self.value[..<self.size], self.value, self.algorithm)

    func wipe():
        secure.wipe(self.key)
        secure.wipe(self.value)

## Sign a SHA-224/256/384/512 digest with private key `d` (deterministic
## RFC 6979 nonces, as BearSSL). `r` and `s` are 32 big-endian bytes.
pub func sign(d: const u8[], digest: const u8[], r_out: u8[], s_out: u8[]) -> !:
    if d.length != 32 or r_out.length < 32 or s_out.length < 32 or not scalar_in_range(d):
        error(sha2.invalid, "P-256 private key must be 32 bytes in [1, n - 1]")
    var nonces = try Nonces.start(d, digest)
    defer nonces.wipe()
    var e: u32[8]
    digest_scalar(digest, e)
    var k_bytes: u8[32]
    defer secure.wipe(k_bytes)
    for _ in 0..<(usize)64:
        try nonces.next(k_bytes)
        if not scalar_in_range(k_bytes):
            try nonces.reseed()
            continue
        let point = multiply_generator_point(k_bytes)
        var x: u32[8]
        var y: u32[8]
        to_affine(&point, x, y)
        var r: u32[8]
        reduce_order(x, r)
        var k: u32[8]
        var dv: u32[8]
        f.decode(k, k_bytes)
        f.decode(dv, d)
        var km: u32[8]
        var dm: u32[8]
        var rm: u32[8]
        var em: u32[8]
        f.to_montgomery(km, k, &f.order)
        f.to_montgomery(dm, dv, &f.order)
        f.to_montgomery(rm, r, &f.order)
        f.to_montgomery(em, e, &f.order)
        var kinv: u32[8]
        f.invert(kinv, km, &f.order)
        var t: u32[8]
        f.mul(t, rm, dm, &f.order)
        f.add(t, t, em, &f.order)
        f.mul(t, kinv, t, &f.order)
        var s: u32[8]
        f.from_montgomery(s, t, &f.order)
        secure.wipe(u8[]((u8*)&km[0], memory.size_of(km)))
        secure.wipe(u8[]((u8*)&kinv[0], memory.size_of(kinv)))
        secure.wipe(u8[]((u8*)&dm[0], memory.size_of(dm)))
        if f.is_zero(r) == 1 or f.is_zero(s) == 1:
            try nonces.reseed()
            continue
        f.encode(r_out[..<32], r)
        f.encode(s_out[..<32], s)
        return
    error(sha2.invalid, "could not form an ECDSA-P256 signature")

## v mod n for any v < 2^256 (< 2n): subtract n once unless v < n, without
## branching (p256_field.sub adds n back on a borrow).
func reduce_order(v: const u32[], out: u32[]):
    f.sub(out, v, f.order.m, &f.order)

## Verify an ECDSA-P256 signature: Q = (qx, qy) and r, s are 32 big-endian
## bytes; the digest is any length (the leftmost 256 bits are used).
pub func verify(qx: const u8[], qy: const u8[], digest: const u8[], r_bytes: const u8[], s_bytes: const u8[]) -> bool!:
    if qx.length != 32 or qy.length != 32 or r_bytes.length != 32 or s_bytes.length != 32 or digest.length == 0:
        error(sha2.invalid, "ECDSA-P256 key and signature values must be 32 bytes each")
    var q = Point()
    if not decode_point(qx, qy, &q) or not scalar_in_range(r_bytes) or not scalar_in_range(s_bytes):
        return false
    var r: u32[8]
    var s: u32[8]
    var e: u32[8]
    f.decode(r, r_bytes)
    f.decode(s, s_bytes)
    digest_scalar(digest, e)
    var sm: u32[8]
    var w: u32[8]
    f.to_montgomery(sm, s, &f.order)
    f.invert(w, sm, &f.order)
    var t: u32[8]
    var u1: u32[8]
    var u2: u32[8]
    f.to_montgomery(t, e, &f.order)
    f.mul(t, t, w, &f.order)
    f.from_montgomery(u1, t, &f.order)
    f.to_montgomery(t, r, &f.order)
    f.mul(t, t, w, &f.order)
    f.from_montgomery(u2, t, &f.order)
    var u1_bytes: u8[32]
    var u2_bytes: u8[32]
    f.encode(u1_bytes, u1)
    f.encode(u2_bytes, u2)
    let g = generator_point()
    let sum = joint_multiply(u1_bytes, &g, u2_bytes, &q)
    if is_infinity(&sum):
        return false
    var x: u32[8]
    var y: u32[8]
    to_affine(&sum, x, y)
    var v: u32[8]
    reduce_order(x, v)
    return f.equal(v, r) == 1