Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-crypto

Source of release 0.6.1

0.6.1 / src / mldsa.lucb

## 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