dymokomi/luce-crypto
Source of release 0.6.0
## FIPS 204 ML-DSA-65 key generation, signing and verification.
import shake
import mldsa_ntt as ntt
import sha2
import secure
import memory
pub let invalid = sha2.invalid
pub let k: usize = 6
pub let l: usize = 5
pub let eta: i32 = 4
pub let d_bits: u32 = 13
pub let pk_bytes: usize = 1952
pub let sk_bytes: usize = 4032
pub let sig_bytes: usize = 3309
func put16(out: u8[], at: usize, value: u16):
out[at] = (u8)value
out[at + 1] = (u8)(value >> 8)
func sample_uniform(seed: const u8[], nonce: u16, out: i32[]) -> !:
var ext: u8[34]
for i in 0..<(usize)32: ext[i] = seed[i]
put16(ext, 32, nonce)
var state = try shake.make(128)
defer state.close()
try state.update(ext)
var ctr: usize
var tmp: u8[3]
while ctr < ntt.n:
try state.squeeze(tmp)
let t = ((u32)tmp[0] | ((u32)tmp[1] << 8) | ((u32)tmp[2] << 16)) & 0x7fffff
if t < (u32)ntt.q:
out[ctr] = (i32)t
ctr += 1
func sample_eta(seed: const u8[], nonce: u16, out: i32[]) -> !:
var ext: u8[66]
for i in 0..<(usize)64: ext[i] = seed[i]
put16(ext, 64, nonce)
var state = try shake.make(256)
defer state.close()
try state.update(ext)
var ctr: usize
var tmp: u8[1]
while ctr < ntt.n:
try state.squeeze(tmp)
let t0 = tmp[0] & 15
let t1 = tmp[0] >> 4
if t0 < 9:
out[ctr] = eta - (i32)t0
ctr += 1
if ctr == ntt.n: return
if t1 < 9:
out[ctr] = eta - (i32)t1
ctr += 1
func pack_t1(a: const i32[], out: u8[]):
for i in 0..<(ntt.n // 4):
let a0 = a[4 * i]
let a1 = a[4 * i + 1]
let a2 = a[4 * i + 2]
let a3 = a[4 * i + 3]
out[5 * i] = (u8)a0
out[5 * i + 1] = (u8)((a0 >> 8) | (a1 << 2))
out[5 * i + 2] = (u8)((a1 >> 6) | (a2 << 4))
out[5 * i + 3] = (u8)((a2 >> 4) | (a3 << 6))
out[5 * i + 4] = (u8)(a3 >> 2)
func power2round(a: i32, a0: i32*) -> i32:
let a1 = (a + (1 << 12) - 1) >> 13
*a0 = a - (a1 << 13)
return a1
func pack_eta(a: const i32[], out: u8[]):
for i in 0..<(ntt.n // 2):
let t0 = eta - a[2 * i]
let t1 = eta - a[2 * i + 1]
out[i] = (u8)t0 | (u8)(t1 << 4)
func pack_t0(a: const i32[], out: u8[]):
for i in 0..<(ntt.n // 8):
var t: i32[8]
for j in 0..<(usize)8: t[j] = (1 << 12) - a[8 * i + j]
out[13 * i] = (u8)t[0]
out[13 * i + 1] = (u8)((t[0] >> 8) | (t[1] << 5))
out[13 * i + 2] = (u8)(t[1] >> 3)
out[13 * i + 3] = (u8)((t[1] >> 11) | (t[2] << 2))
out[13 * i + 4] = (u8)((t[2] >> 6) | (t[3] << 7))
out[13 * i + 5] = (u8)(t[3] >> 1)
out[13 * i + 6] = (u8)((t[3] >> 9) | (t[4] << 4))
out[13 * i + 7] = (u8)(t[4] >> 4)
out[13 * i + 8] = (u8)((t[4] >> 12) | (t[5] << 1))
out[13 * i + 9] = (u8)((t[5] >> 7) | (t[6] << 6))
out[13 * i + 10] = (u8)(t[6] >> 2)
out[13 * i + 11] = (u8)((t[6] >> 10) | (t[7] << 3))
out[13 * i + 12] = (u8)(t[7] >> 5)
pub func keygen(seed: const u8[], pk: u8[], sk: u8[]) -> !:
if seed.length != 32 or pk.length < pk_bytes or sk.length < sk_bytes:
error(invalid, "ML-DSA-65 key buffers")
var seed_ext: u8[34]
for i in 0..<(usize)32: seed_ext[i] = seed[i]
seed_ext[32] = (u8)k
seed_ext[33] = (u8)l
var expanded: u8[128]
try shake.shake256(seed_ext, expanded)
var rho: u8[32]
var rhoprime: u8[64]
var key: u8[32]
for i in 0..<(usize)32: rho[i] = expanded[i]
for i in 0..<(usize)64: rhoprime[i] = expanded[32 + i]
for i in 0..<(usize)32: key[i] = expanded[96 + i]
var s1: i32[1280]
var s1hat: i32[1280]
var s2: i32[1536]
for j in 0..<l:
try sample_eta(rhoprime, (u16)j, s1[j * ntt.n..<(j + 1) * ntt.n])
for n in 0..<ntt.n: s1hat[j * ntt.n + n] = s1[j * ntt.n + n]
ntt.ntt(s1hat[j * ntt.n..<(j + 1) * ntt.n])
for i in 0..<k:
try sample_eta(rhoprime, (u16)(l + i), s2[i * ntt.n..<(i + 1) * ntt.n])
var t0: i32[1536]
for i in 0..<(usize)32: pk[i] = rho[i]
for i in 0..<k:
var acc: i32[256]
for j in 0..<l:
var row: i32[256]
try sample_uniform(rho, (u16)((i << 8) + j), row)
for n in 0..<ntt.n:
acc[n] +%= ntt.mont((i64)row[n] * (i64)s1hat[j * ntt.n + n])
for n in 0..<ntt.n: acc[n] = ntt.reduce32(acc[n])
ntt.invntt(acc)
for n in 0..<ntt.n:
acc[n] +%= s2[i * ntt.n + n]
acc[n] = ntt.caddq(acc[n])
var high: i32[256]
for n in 0..<ntt.n:
high[n] = power2round(acc[n], &t0[i * ntt.n + n])
pack_t1(high, pk[32 + i * 320..<32 + (i + 1) * 320])
try shake.shake256(pk[..<pk_bytes], sk[64..<128])
for i in 0..<(usize)32:
sk[i] = rho[i]
sk[32 + i] = key[i]
for j in 0..<l:
pack_eta(s1[j * ntt.n..<(j + 1) * ntt.n], sk[128 + j * 128..<128 + (j + 1) * 128])
let s2_at = 128 + l * 128
for i in 0..<k:
pack_eta(s2[i * ntt.n..<(i + 1) * ntt.n], sk[s2_at + i * 128..<s2_at + (i + 1) * 128])
let t0_at = s2_at + k * 128
for i in 0..<k:
pack_t0(t0[i * ntt.n..<(i + 1) * ntt.n], sk[t0_at + i * 416..<t0_at + (i + 1) * 416])
secure.wipe(u8[]((u8*)&s1[0], memory.size_of(s1)))
secure.wipe(u8[]((u8*)&s1hat[0], memory.size_of(s1hat)))
secure.wipe(u8[]((u8*)&s2[0], memory.size_of(s2)))
secure.wipe(expanded)
secure.wipe(key)
secure.wipe(rhoprime)
pub let gamma1: i32 = 524288
pub let gamma2: i32 = 261888
pub let beta: i32 = 196
pub let tau: usize = 49
pub let omega: usize = 55
pub let ctilde: usize = 48
func unpack_eta(a: const u8[], out: i32[]):
for i in 0..<(ntt.n // 2):
out[2 * i] = eta - (i32)(a[i] & 15)
out[2 * i + 1] = eta - (i32)(a[i] >> 4)
func unpack_t0(a: const u8[], out: i32[]):
for i in 0..<(ntt.n // 8):
var c: i32[8]
c[0] = (i32)a[13 * i] | ((i32)a[13 * i + 1] << 8)
c[0] &= 0x1fff
c[1] = (i32)(a[13 * i + 1] >> 5) | ((i32)a[13 * i + 2] << 3) | ((i32)a[13 * i + 3] << 11)
c[1] &= 0x1fff
c[2] = (i32)(a[13 * i + 3] >> 2) | ((i32)a[13 * i + 4] << 6)
c[2] &= 0x1fff
c[3] = (i32)(a[13 * i + 4] >> 7) | ((i32)a[13 * i + 5] << 1) | ((i32)a[13 * i + 6] << 9)
c[3] &= 0x1fff
c[4] = (i32)(a[13 * i + 6] >> 4) | ((i32)a[13 * i + 7] << 4) | ((i32)a[13 * i + 8] << 12)
c[4] &= 0x1fff
c[5] = (i32)(a[13 * i + 8] >> 1) | ((i32)a[13 * i + 9] << 7)
c[5] &= 0x1fff
c[6] = (i32)(a[13 * i + 9] >> 6) | ((i32)a[13 * i + 10] << 2) | ((i32)a[13 * i + 11] << 10)
c[6] &= 0x1fff
c[7] = (i32)(a[13 * i + 11] >> 3) | ((i32)a[13 * i + 12] << 5)
c[7] &= 0x1fff
for j in 0..<(usize)8: out[8 * i + j] = (1 << 12) - c[j]
func unpack_t1(a: const u8[], out: i32[]):
for i in 0..<(ntt.n // 4):
out[4 * i] = ((i32)a[5 * i] | ((i32)a[5 * i + 1] << 8)) & 0x3ff
out[4 * i + 1] = ((i32)(a[5 * i + 1] >> 2) | ((i32)a[5 * i + 2] << 6)) & 0x3ff
out[4 * i + 2] = ((i32)(a[5 * i + 2] >> 4) | ((i32)a[5 * i + 3] << 4)) & 0x3ff
out[4 * i + 3] = ((i32)(a[5 * i + 3] >> 6) | ((i32)a[5 * i + 4] << 2)) & 0x3ff
func pack_z(a: const i32[], out: u8[]):
for i in 0..<(ntt.n // 2):
let t0 = gamma1 - a[2 * i]
let t1 = gamma1 - a[2 * i + 1]
out[5 * i] = (u8)t0
out[5 * i + 1] = (u8)(t0 >> 8)
out[5 * i + 2] = (u8)((t0 >> 16) | (t1 << 4))
out[5 * i + 3] = (u8)(t1 >> 4)
out[5 * i + 4] = (u8)(t1 >> 12)
func unpack_z(a: const u8[], out: i32[]):
for i in 0..<(ntt.n // 2):
var z0 = (i32)a[5 * i] | ((i32)a[5 * i + 1] << 8) | ((i32)a[5 * i + 2] << 16)
z0 &= 0xfffff
var z1 = (i32)(a[5 * i + 2] >> 4) | ((i32)a[5 * i + 3] << 4) | ((i32)a[5 * i + 4] << 12)
out[2 * i] = gamma1 - z0
out[2 * i + 1] = gamma1 - z1
func pack_w1(a: const i32[], out: u8[]):
for i in 0..<(ntt.n // 2):
out[i] = (u8)a[2 * i] | (u8)(a[2 * i + 1] << 4)
func sample_gamma1(seed: const u8[], nonce: u16, out: i32[]) -> !:
var ext: u8[66]
for i in 0..<(usize)64: ext[i] = seed[i]
put16(ext, 64, nonce)
var packed: u8[640]
try shake.shake256(ext, packed)
unpack_z(packed, out)
func decompose(a: i32, a0: i32*) -> i32:
var a1 = (a + 127) >> 7
a1 = (a1 * 1025 + (1 << 21)) >> 22
a1 &= 15
*a0 = a - a1 * 2 * gamma2
if *a0 > (ntt.q - 1) // 2: *a0 -= ntt.q
return a1
func make_hint(a0: i32, a1: i32) -> i32:
if a0 > gamma2 or a0 < -gamma2 or (a0 == -gamma2 and a1 != 0): return 1
return 0
func use_hint(a: i32, hint: i32) -> i32:
var a0: i32
let a1 = decompose(a, &a0)
if hint == 0: return a1
if a0 > 0: return (a1 + 1) & 15
return (a1 - 1) & 15
func chknorm(a: const i32[], bound: i32) -> bool:
if bound > (ntt.q - 1) // 8: return true
for i in 0..<ntt.n:
var t = a[i]
if t < 0: t = -t
if t >= bound: return true
return false
func challenge(seed: const u8[], out: i32[]) -> !:
var state = try shake.make(256)
defer state.close()
try state.update(seed)
var buf: u8[136]
try state.squeeze(buf)
var signs: u64
for i in 0..<(usize)8: signs |= (u64)buf[i] << (i * 8)
var pos: usize = 8
for i in 0..<ntt.n: out[i] = 0
var i = ntt.n - tau
while i < ntt.n:
var b: usize
while true:
if pos >= 136:
try state.squeeze(buf)
pos = 0
b = (usize)buf[pos]
pos += 1
if b <= i: break
out[i] = out[b]
out[b] = 1 - 2 * (i32)(signs & 1)
signs >>= 1
i += 1
func absorb_mu(tr: const u8[], msg: const u8[], mu: u8[]) -> !:
var state = try shake.make(256)
defer state.close()
try state.update(tr)
var pre: u8[2]
try state.update(pre)
try state.update(msg)
try state.squeeze(mu)
pub func sign(sk: const u8[], msg: const u8[], rnd: const u8[], sig: u8[]) -> !:
if sk.length < sk_bytes or sig.length < sig_bytes or rnd.length != 32:
error(invalid, "ML-DSA-65 signature buffers")
var rho: u8[32]
var key: u8[32]
var tr: u8[64]
for i in 0..<(usize)32:
rho[i] = sk[i]
key[i] = sk[32 + i]
for i in 0..<(usize)64: tr[i] = sk[64 + i]
var s1: i32[1280]
var s2: i32[1536]
var t0: i32[1536]
for j in 0..<l: unpack_eta(sk[128 + j * 128..<128 + (j + 1) * 128], s1[j * ntt.n..<(j + 1) * ntt.n])
let s2_at = 128 + l * 128
for i in 0..<k: unpack_eta(sk[s2_at + i * 128..<s2_at + (i + 1) * 128], s2[i * ntt.n..<(i + 1) * ntt.n])
let t0_at = s2_at + k * 128
for i in 0..<k: unpack_t0(sk[t0_at + i * 416..<t0_at + (i + 1) * 416], t0[i * ntt.n..<(i + 1) * ntt.n])
var mu: u8[64]
try absorb_mu(tr, msg, mu)
var rhoprime: u8[64]
var state = try shake.make(256)
try state.update(key)
try state.update(rnd)
try state.update(mu)
try state.squeeze(rhoprime)
state.close()
for j in 0..<l: ntt.ntt(s1[j * ntt.n..<(j + 1) * ntt.n])
for i in 0..<k:
ntt.ntt(s2[i * ntt.n..<(i + 1) * ntt.n])
ntt.ntt(t0[i * ntt.n..<(i + 1) * ntt.n])
var nonce: u16
var attempts: usize
while attempts < 10000:
attempts += 1
var y: i32[1280]
var z: i32[1280]
for j in 0..<l:
try sample_gamma1(rhoprime, nonce, y[j * ntt.n..<(j + 1) * ntt.n])
nonce += 1
for n in 0..<ntt.n: z[j * ntt.n + n] = y[j * ntt.n + n]
ntt.ntt(z[j * ntt.n..<(j + 1) * ntt.n])
var w1: i32[1536]
var w0: i32[1536]
var packed_w1: u8[768]
for i in 0..<k:
var acc: i32[256]
for j in 0..<l:
var row: i32[256]
try sample_uniform(rho, (u16)((i << 8) + j), row)
for n in 0..<ntt.n:
acc[n] +%= ntt.mont((i64)row[n] * (i64)z[j * ntt.n + n])
for n in 0..<ntt.n: acc[n] = ntt.reduce32(acc[n])
ntt.invntt(acc)
for n in 0..<ntt.n: acc[n] = ntt.caddq(acc[n])
for n in 0..<ntt.n:
w1[i * ntt.n + n] = decompose(acc[n], &w0[i * ntt.n + n])
pack_w1(w1[i * ntt.n..<(i + 1) * ntt.n], packed_w1[i * 128..<(i + 1) * 128])
var cseed = try shake.make(256)
try cseed.update(mu)
try cseed.update(packed_w1)
try cseed.squeeze(sig[..<ctilde])
cseed.close()
var cp: i32[256]
try challenge(sig[..<ctilde], cp)
ntt.ntt(cp)
var reject = false
for j in 0..<l:
var cs1: i32[256]
for n in 0..<ntt.n:
cs1[n] = ntt.mont((i64)cp[n] * (i64)s1[j * ntt.n + n])
ntt.invntt(cs1)
for n in 0..<ntt.n:
z[j * ntt.n + n] = cs1[n] +% y[j * ntt.n + n]
for n in 0..<ntt.n: z[j * ntt.n + n] = ntt.reduce32(z[j * ntt.n + n])
if chknorm(z[j * ntt.n..<(j + 1) * ntt.n], gamma1 - beta):
reject = true
break
if reject: continue
var h: i32[1536]
var hints: usize
for i in 0..<k:
var cs2: i32[256]
for n in 0..<ntt.n:
cs2[n] = ntt.mont((i64)cp[n] * (i64)s2[i * ntt.n + n])
ntt.invntt(cs2)
for n in 0..<ntt.n:
w0[i * ntt.n + n] -%= cs2[n]
w0[i * ntt.n + n] = ntt.reduce32(w0[i * ntt.n + n])
if chknorm(w0[i * ntt.n..<(i + 1) * ntt.n], gamma2 - beta):
reject = true
break
var ct0: i32[256]
for n in 0..<ntt.n:
ct0[n] = ntt.mont((i64)cp[n] * (i64)t0[i * ntt.n + n])
ntt.invntt(ct0)
for n in 0..<ntt.n: ct0[n] = ntt.reduce32(ct0[n])
if chknorm(ct0, gamma2):
reject = true
break
for n in 0..<ntt.n:
w0[i * ntt.n + n] +%= ct0[n]
h[i * ntt.n + n] = make_hint(w0[i * ntt.n + n], w1[i * ntt.n + n])
hints += (usize)h[i * ntt.n + n]
if reject or hints > omega: continue
for j in 0..<l:
pack_z(z[j * ntt.n..<(j + 1) * ntt.n], sig[ctilde + j * 640..<ctilde + (j + 1) * 640])
let hint_at = ctilde + l * 640
for i in 0..<(omega + k): sig[hint_at + i] = 0
var at: usize
for i in 0..<k:
for n in 0..<ntt.n:
if h[i * ntt.n + n] != 0:
sig[hint_at + at] = (u8)n
at += 1
sig[hint_at + omega + i] = (u8)at
secure.wipe(key)
secure.wipe(rhoprime)
return
error(invalid, "ML-DSA-65 signing rejected too many times")
pub func verify(pk: const u8[], msg: const u8[], sig: const u8[]) -> bool!:
if pk.length < pk_bytes or sig.length != sig_bytes: return false
var rho: u8[32]
for i in 0..<(usize)32: rho[i] = pk[i]
var t1: i32[1536]
for i in 0..<k: unpack_t1(pk[32 + i * 320..<32 + (i + 1) * 320], t1[i * ntt.n..<(i + 1) * ntt.n])
var z: i32[1280]
for j in 0..<l: unpack_z(sig[ctilde + j * 640..<ctilde + (j + 1) * 640], z[j * ntt.n..<(j + 1) * ntt.n])
for j in 0..<l:
if chknorm(z[j * ntt.n..<(j + 1) * ntt.n], gamma1 - beta): return false
var h: i32[1536]
let hint_at = ctilde + l * 640
var pos: usize
for i in 0..<k:
for n in 0..<ntt.n: h[i * ntt.n + n] = 0
let next = (usize)sig[hint_at + omega + i]
if next < pos or next > omega: return false
var j = pos
while j < next:
if j > pos and sig[hint_at + j] <= sig[hint_at + j - 1]: return false
h[i * ntt.n + (usize)sig[hint_at + j]] = 1
j += 1
pos = next
for j in pos..<omega:
if sig[hint_at + j] != 0: return false
var tr: u8[64]
try shake.shake256(pk[..<pk_bytes], tr)
var mu: u8[64]
try absorb_mu(tr, msg, mu)
var cp: i32[256]
try challenge(sig[..<ctilde], cp)
ntt.ntt(cp)
for j in 0..<l: ntt.ntt(z[j * ntt.n..<(j + 1) * ntt.n])
var packed_w1: u8[768]
for i in 0..<k:
var acc: i32[256]
for j in 0..<l:
var row: i32[256]
try sample_uniform(rho, (u16)((i << 8) + j), row)
for n in 0..<ntt.n:
acc[n] +%= ntt.mont((i64)row[n] * (i64)z[j * ntt.n + n])
for n in 0..<ntt.n: t1[i * ntt.n + n] <<= 13
ntt.ntt(t1[i * ntt.n..<(i + 1) * ntt.n])
var ct1: i32[256]
for n in 0..<ntt.n:
ct1[n] = ntt.mont((i64)cp[n] * (i64)t1[i * ntt.n + n])
for n in 0..<ntt.n:
acc[n] -%= ct1[n]
acc[n] = ntt.reduce32(acc[n])
ntt.invntt(acc)
for n in 0..<ntt.n: acc[n] = ntt.caddq(acc[n])
var high: i32[256]
for n in 0..<ntt.n: high[n] = use_hint(acc[n], h[i * ntt.n + n])
pack_w1(high, packed_w1[i * 128..<(i + 1) * 128])
var c2: u8[48]
var check = try shake.make(256)
defer check.close()
try check.update(mu)
try check.update(packed_w1)
try check.squeeze(c2)
for i in 0..<ctilde:
if sig[i] != c2[i]: return false
return true