dymokomi/luce-crypto
Source of release 0.6.0
## 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