Sign in

    moondsa

    moondsa is a MoonBit implementation of Dilithium, a post-quantum signature scheme.

    Dilithium
    Signature
    Cryptography
    Post-Quantum
    Download zip
    Author
    Version
    0.2.1
    License
    Apache-2.0
    Last updated
    last year
    Downloads
    37

    #ruifeng/dilithium

    A MoonBit implementation of the Dilithium post-quantum digital signature algorithm. This library provides key generation, signing, and verification functions for the Dilithium signature scheme, which is designed to be secure against attacks by quantum computers.

    #Features

    • Complete Dilithium Implementation: Full implementation of the Dilithium signature scheme as specified in the NIST post-quantum cryptography standard
    • Multiple Security Levels: Support for all three security levels:
      • Dilithium-2 (NIST security level 2)
      • Dilithium-3 (NIST security level 3)
      • Dilithium-5 (NIST security level 5)
    • Deterministic & Non-deterministic Signing: Support for both deterministic and randomized signature generation
    • Comprehensive Testing: Extensive Known Answer Tests (KAT) validation against official test vectors
    • Memory Safe: Written in MoonBit with memory safety guarantees

    #Security Warning

    ⚠️ Security Notice: This implementation has not undergone formal security analysis or side-channel resistance evaluation. While it implements the correct algorithms, it should not be used in production systems without additional security review and hardening.

    #Installation

    Add this package to your MoonBit project:

    moon add ruifeng/moondsa

    #Quick Start

    #Basic Usage

    // Import the package
    let @dilithium = @ruifeng/moondsa

    // Set security level (Dilithium3 is the default)
    @dilithium.dilithium_context.set_level(SecurityLevel::Dilithium3)

    // Generate key pair with random seed
    let (pk, sk) = @dilithium.crypto_sign_keypair(Err(@random.Rand::new()))

    // Sign a message
    let message = "Hello, post-quantum world!".to_bytes()
    let signature = @dilithium.crypto_sign_signature(message, sk)

    // Verify signature
    let result = @dilithium.crypto_sign_verify(signature, message, pk)
    match result {
    Ok(_) => println("Signature is valid!")
    Err(e) => println("Signature verification failed: \(e)")
    }

    #Deterministic Key Generation

    // Generate keys from a specific seed (deterministic)
    let seed = Array::make(32, 0x42) // 32-byte seed
    let (pk, sk) = @dilithium.crypto_sign_keypair(Ok(seed))

    #Security Level Selection

    // Available security levels
    @dilithium.dilithium_context.set_level(SecurityLevel::Dilithium2) // 128-bit security
    @dilithium.dilithium_context.set_level(SecurityLevel::Dilithium3) // 192-bit security
    @dilithium.dilithium_context.set_level(SecurityLevel::Dilithium5) // 256-bit security

    #API Reference

    #Core Functions

    • crypto_sign_keypair(seed): Generate public/private key pair
    • crypto_sign_signature(message, secret_key): Sign a message
    • crypto_sign_verify(signature, message, public_key): Verify a signature

    #Configuration

    • SecurityLevel: Enum with variants Dilithium2, Dilithium3, Dilithium5
    • dilithium_context: Global configuration context

    #Algorithm Details

    Dilithium is a lattice-based digital signature scheme based on the hardness of the Module Learning With Errors (MLWE) problem. The implementation follows the NIST FIPS 204 standard specification.

    #Key Sizes

    Security LevelPublic KeySecret KeySignature
    Dilithium-21312 bytes2528 bytes2420 bytes
    Dilithium-31952 bytes4016 bytes3293 bytes
    Dilithium-52592 bytes4864 bytes4595 bytes

    #Testing

    The implementation includes comprehensive Known Answer Tests (KAT) that validate against the official NIST test vectors:

    # Run all tests moon test # Run with verbose output moon test -v

    #Roadmap

    #References

    #License

    Licensed under the Apache License 2.0. See LICENSE for details.

    SignError

    type SignError

    Signature verification or validation error with descriptive message.

    This error type is returned when signature verification fails or when signature/key unpacking encounters invalid data. The error message provides specific information about what validation failed.

    BigRandom

    type BigRandom

    Composite random number generator that combines multiple random sources.

    This structure allows combining multiple random number generators to provide enhanced randomness quality and redundancy for cryptographic applications.

    BigRandom::get_random

    fn BigRandom::get_random(seed : Array[Byte], level : Int) ->
    Rand
    Crate a new BigRandom the length of the seed must be a multiple of 32(256 bits)

    DilithiumContext

    type DilithiumContext

    Global configuration context for the Dilithium signature scheme.

    This structure maintains the current security parameters and random number generator configuration for all cryptographic operations.

    DilithiumContext::get_params_set

    fn DilithiumContext::get_params_set(self : DilithiumContext) -> ParameterSet

    DilithiumContext::get_random

    DilithiumContext::set_level

    fn DilithiumContext::set_level(self : DilithiumContext, level : SecurityLevel) -> Unit

    DilithiumContext::set_random

    KeccakState

    pub struct KeccakState {
    s : FixedArray[UInt64]
    pos : UInt
    }

    Internal state structure for Keccak cryptographic hash functions.

    Fields:

    • s : 25-element flattened representation of the 5x5 Keccak state matrix, where each element is a 64-bit word.
    • pos : Current byte position within the rate block, used to track progress during incremental absorption and squeezing operations.
    impl Show for KeccakState

    KeccakState::init

    fn KeccakState::init(self : KeccakState) -> Unit

    Resets the Keccak state to its initial clean state with all fields zeroed.

    Parameters:

    • self : The KeccakState instance to be initialized.

    ParameterSet

    pub struct ParameterSet {
    k : Int
    l : Int
    eta : Int
    tau : Int
    beta : Int
    gamma1 : Int
    gamma2 : Int
    omega : Int
    publickey_bytes : Int
    polyeta_packedbytes : Int
    polyw1_packedbytes : Int
    polyz_packed_bytes : Int
    poly_uniform_gamma1_nblocks : UInt
    polyvech_packed_bytes : Int
    sign_bytes : Int
    level : SecurityLevel
    features : Map[String, String]
    }

    Configuration parameters for Dilithium digital signature scheme variants.

    Fields:

    • k : Dimension of the s_1 vector.
    • l : Dimension of the s_2 (error) vector.
    • eta : Coefficient range parameter for secret polynomials.
    • tau : Number of non-zero entries in the challenge polynomial.
    • beta : Maximum coefficient of the commitment randomness.
    • gamma1 : Parameter for decomposition, computed as (q - 1) / 16.
    • gamma2 : Half of gamma1, used for range checks.
    • omega : Maximum number of 1s in the hint polynomial.
    • publickey_bytes : Size of the public key in bytes (seedbytes + k * t1).
    • polyeta_packedbytes : Size of a packed eta polynomial in bytes.
    • polyw1_packedbytes : Size of a packed w1 polynomial in bytes.
    • polyz_packed_bytes : Size of a packed z polynomial in bytes.
    • poly_uniform_gamma1_nblocks : Number of SHAKE256 blocks needed for sampling gamma1.
    • polyvech_packed_bytes : Size of a packed hint vector in bytes.
    • sign_bytes : Size of the signature in bytes (seedbytes + l * polyz_packed_bytes + polyvech_packed_bytes).
    • level : Security level (Dilithium2, Dilithium3, or Dilithium5).
    • features : Additional features map (e.g., "aes" support, currently not supported).

    Poly

    pub struct Poly {
    coeffs : Array[Int]
    }

    Polynomial structure containing an array of coefficients for cryptographic operations.

    This structure represents a polynomial in the ring Z_q[X]/(X^N + 1) used in lattice-based cryptography, specifically in the Dilithium digital signature scheme. The polynomial has exactly N coefficients, where N is a compile-time constant representing the degree of the polynomial ring.

    Fields:

    • coeffs : Array of N integer coefficients representing the polynomial terms from degree 0 to N-1.

    Example:

    let p = @ruifeng/moondsa.Poly::new()
    p.coeffs[0] = 42 // Set constant term
    p.coeffs[1] = -17 // Set coefficient of x^1
    inspect(p.coeffs[0], content="42")
    inspect(p.coeffs[1], content="-17")

    impl Show for Poly

    Poly::add

    fn Poly::add(self : Poly, other : Poly) -> Unit
    Add polynomials. No modular reduction is performed. 多项式加法。不执行模约简。

    Arguments / 参数:
    • self: target polynomial (modified in place) / 目标多项式(原地修改)
    • other: polynomial to add / 要相加的多项式

    Poly::caddq

    fn Poly::caddq(self : Poly) -> Unit

    Conditionally adds the modulus Q to each coefficient of the polynomial if the coefficient is negative, ensuring all coefficients are in the range [0, 2*Q).

    Parameters:

    • self : The polynomial whose coefficients will be conditionally adjusted in place.

    Example:

    let poly = Poly::new()
    // Assume some coefficients are negative after operations
    poly.caddq() // All negative coefficients now have Q added to them

    Poly::challenge

    fn Poly::challenge(self : Poly, seed : Array[Byte]) -> Unit

    Generates a challenge polynomial using the SHAKE256 hash function, implementing the H function from the Dilithium signature scheme.

    This method samples a polynomial with exactly tau nonzero coefficients, each being either -1 or +1. The polynomial is used as part of the cryptographic challenge in the Dilithium digital signature algorithm. The sampling process uses rejection sampling on the SHAKE256 output stream to ensure uniform distribution.

    Parameters:

    • self : The polynomial to be filled with challenge coefficients. All coefficients will be set to 0 initially, then tau positions will be set to either -1 or +1.
    • seed : A byte array used as the seed for the SHAKE256 hash function. This seed determines the challenge polynomial generation.

    The method works by:

    1. Initializing all polynomial coefficients to zero
    2. Using SHAKE256 to generate pseudorandom bytes from the seed
    3. Extracting sign bits for the nonzero coefficients
    4. Using rejection sampling to select tau distinct positions
    5. Setting the selected positions to -1 or +1 based on the extracted sign bits

    The resulting polynomial will have exactly tau nonzero coefficients distributed uniformly at random positions, with each nonzero coefficient being either -1 or +1 with equal probability.

    Poly::chknorm

    fn Poly::chknorm(self : Poly, b : Int) -> Byte
    Check infinity norm of polynomial against given bound. Assumes input coefficients to be standard representatives. Returns 0 if norm is strictly smaller than B and 1 otherwise. 检查多项式的无穷范数是否超过给定界限。 假设输入系数为标准代表元。 如果范数严格小于 B 则返回 0,否则返回 1。

    Arguments / 参数:
    • self: polynomial to check / 要检查的多项式
    • b: bound to check against / 要检查的界限

    Returns / 返回: 0 if all coefficients have absolute value < b, 1 otherwise 0 如果所有系数的绝对值 < b,否则返回 1

    Poly::copy

    fn Poly::copy(self : Poly) -> Poly

    Creates a copy of the polynomial with independent coefficient storage.

    Parameters:

    • self : The polynomial to copy.

    Returns a new polynomial with the same coefficients as the original, but with independent storage that can be modified without affecting the original polynomial.

    Example:

    let poly1 = Poly::new()
    poly1.coeffs[0] = 42
    let poly2 = poly1.copy()
    poly2.coeffs[0] = 100
    // poly1.coeffs[0] is still 42, poly2.coeffs[0] is 100

    Poly::decompose

    fn Poly::decompose(self : Poly, low : Poly) -> Unit
    For all coefficients c of the input polynomial, compute high and low bits c0, c1 such c mod Q = c1ALPHA + c0 with -ALPHA/2 < c0 <= ALPHA/2 except c1 = (Q-1)/ALPHA where we set c1 = 0 and -ALPHA/2 <= c0 = c mod Q - Q < 0. Assumes coefficients to be standard representatives. 对于输入多项式的所有系数 c,计算高位和低位 c0, c1, 使得 c mod Q = c1ALPHA + c0,其中 -ALPHA/2 < c0 <= ALPHA/2, 除了当 c1 = (Q-1)/ALPHA 时,我们设置 c1 = 0 且 -ALPHA/2 <= c0 = c mod Q - Q < 0。 假设系数为标准代表元。

    Arguments / 参数:
    • self: input polynomial, gets high bits (modified in place) / 输入多项式,获得高位(原地修改)
    • other: output polynomial for low bits / 低位的输出多项式

    Poly::inv_ntt_to_mont

    fn Poly::inv_ntt_to_mont(self : Poly) -> Unit
    Inplace inverse NTT and multiplication by 2^{32}. Input coefficients need to be less than 2Q. Output coefficients are less than 2Q. 原地逆向 NTT 并乘以 2^{32}。 输入系数需要小于 2Q。 输出系数小于 2Q。

    Poly::make_hint

    fn Poly::make_hint(h : Poly, a0 : Poly, a1 : Poly) -> Int
    Compute hint polynomial. The coefficients of which indicate whether the low bits of the corresponding coefficient of the input polynomial overflow into the high bits. 计算提示多项式。其系数指示输入多项式对应系数的低位 是否溢出到高位。

    Arguments / 参数:
    • h: output hint polynomial / 输出提示多项式
    • a0: low bits polynomial / 低位多项式
    • a1: high bits polynomial / 高位多项式

    Returns / 返回: Number of 1's in hint polynomial / 提示多项式中 1 的数量

    Poly::new

    fn Poly::new() -> Poly

    Creates a new polynomial with all coefficients initialized to zero.

    Returns a new Poly instance with all coefficients set to zero.

    Poly::ntt

    fn Poly::ntt(self : Poly) -> Unit

    Performs an in-place forward Number Theoretic Transform (NTT) on the polynomial coefficients.

    Parameters:

    • self : The polynomial whose coefficients will be transformed in place.

    Example:

    let poly = Poly::new()
    // ... initialize polynomial coefficients ...
    poly.ntt() // Transform coefficients to NTT domain

    Poly::pack_eta

    fn Poly::pack_eta(self : Poly) -> Array[Byte]

    Encodes a polynomial with coefficients in the range [-ETA, ETA] into a compact byte array representation.

    This function performs bit-packing to efficiently store polynomial coefficients that are bounded by the ETA parameter. The packing strategy depends on the specific ETA value used in the current Dilithium parameter set. For ETA=2, coefficients are packed using 3 bits each with 8 coefficients packed into 3 bytes. For ETA=4, coefficients are packed using 4 bits each with 2 coefficients packed into 1 byte.

    Parameters:

    • self : The polynomial whose coefficients will be packed. Coefficients are assumed to lie in the range [Q-ETA, Q+ETA].

    Returns a byte array containing the bit-packed representation of the polynomial coefficients. The size of the returned array depends on the ETA parameter from the current Dilithium parameter set.

    Poly::pack_t0

    fn Poly::pack_t0(self : Poly) -> Array[Byte]

    Serializes polynomial coefficients with values in the range [-2^{D-1}, 2^{D-1}] into a compact byte array representation.

    This function performs bit-packing of polynomial coefficients by first transforming them to unsigned values using the formula D_SHL -coefficient, where D_SHL = 2^{D-1}. The transformed coefficients are then packed into bytes using a custom bit-packing scheme that processes 8 coefficients at a time and produces 13 bytes of output per group.

    Parameters:

    • self : The polynomial whose coefficients will be packed. Coefficients must be in the range [-2^{D-1}, 2^{D-1}].

    Returns a byte array containing the bit-packed representation of the polynomial coefficients. The output size is N / 8 * 13 bytes, where N is the number of coefficients in the polynomial.

    Poly::pack_t1

    fn Poly::pack_t1(self : Poly) -> Array[Byte]

    Bit-packs a polynomial t1 with coefficients that fit within 10 bits into a compact byte array representation.

    Parameters:

    • self : The polynomial containing coefficients to be packed. Input coefficients are assumed to be standard representatives fitting within 10 bits.

    Returns a byte array containing the bit-packed representation of the polynomial. The output array has length N / 4 * 5 bytes, where every group of 4 coefficients is packed into 5 bytes.

    Example:

    let poly = Poly::new()
    // Assume poly has been populated with valid coefficients
    let packed_bytes = poly.pack_t1()

    Poly::pack_w1

    fn Poly::pack_w1(self : Poly) -> Array[Byte]

    Bit-packs polynomial w1 coefficients into a compact byte array representation.

    Parameters:

    • self : The polynomial containing coefficients in the range [0, 15] that are assumed to be standard representatives.

    Returns a byte array containing the bit-packed representation of the polynomial coefficients. The size of the returned array depends on the gamma2 parameter: N/4 * 3 bytes when gamma2 equals (Q-1)/88, or N/2 bytes otherwise.

    Poly::pack_z

    fn Poly::pack_z(self : Poly) -> Array[Byte]
    Bit-pack polynomial z with coefficients in [-(GAMMA1 - 1), GAMMA1 - 1]. Input coefficients are assumed to be standard representatives.*

    Poly::pointwise_montgomery

    fn Poly::pointwise_montgomery(c : Poly, a : Poly, b : Poly) -> Unit
    Pointwise multiplication of polynomials in NTT domain representation and multiplication of resulting polynomial by 2^{-32}. Output coefficients are less than 2Q if input coefficient are less than 22Q. NTT 域内多项式的逐点乘法,并将结果多项式乘以 2^{-32}。 如果输入系数小于 22Q,则输出系数小于 2Q。

    Arguments / 参数:
    • self: result polynomial (modified in place) / 结果多项式(原地修改)
    • other: polynomial to multiply with / 要相乘的多项式

    Poly::poly_uniform_eta

    fn Poly::poly_uniform_eta(self : Poly, seed : Array[Byte], nonce : UInt16) -> Unit

    Samples uniformly random coefficients in the range [-η, η] for the polynomial using rejection sampling on a pseudo-random stream.

    This function uses the SHAKE256 extendable-output function to generate random bytes, then applies rejection sampling to obtain coefficients within the required range. The number of blocks to generate depends on the η parameter from the current Dilithium parameter set.

    Parameters:

    • self : The polynomial to fill with uniformly random coefficients in [-η, η].
    • seed : The seed bytes used to initialize the SHAKE256 pseudo-random stream.
    • nonce : A 16-bit nonce value used along with the seed for stream initialization to ensure different outputs for the same seed.

    Poly::power2round

    fn Poly::power2round(self : Poly, a0 : Poly) -> Unit
    For all coefficients c of the input polynomial, compute c0, c1 such that c mod Q = c1*2^D + c0 with -2^{D-1} < c0 <= 2^{D-1}. Assumes coefficients to be standard representatives.

    Poly::reduce

    fn Poly::reduce(self : Poly) -> Unit

    Performs in-place modular reduction of all polynomial coefficients to their canonical representatives in the range [0, 2*Q].

    Parameters:

    • self : The polynomial whose coefficients will be reduced in-place.

    Example:

    let poly = Poly::new()
    // ... populate polynomial with coefficients ...
    poly.reduce() // All coefficients are now in range [0, 2*Q]

    Poly::shiftl

    fn Poly::shiftl(self : Poly) -> Unit
    Multiply polynomial by 2^D without modular reduction. Assumes input coefficients to be less than 2^{32-D}. 将多项式乘以 2^D,不执行模约简。假设输入系数小于 2^{32-D}。

    Poly::sub

    fn Poly::sub(self : Poly, other : Poly) -> Unit
    Subtract polynomials. Assumes coefficients of second input polynomial to be less than 2Q. No modular reduction is performed. 多项式减法。假设第二个输入多项式的系数小于 2Q。 不执行模约简。

    Arguments / 参数:
    • self: target polynomial (modified in place) / 目标多项式(原地修改)
    • other: polynomial to subtract / 要减去的多项式

    Poly::uniform

    fn Poly::uniform(self : Poly, seed : Array[Byte], nonce : UInt16) -> Unit

    Samples uniformly random coefficients in [0, Q-1] for the polynomial using rejection sampling on a pseudo-random stream.

    Parameters:

    • self : The polynomial to fill with uniform random coefficients.
    • seed : The seed bytes used to initialize the pseudo-random stream.
    • nonce : A 16-bit nonce value used along with the seed for stream initialization.

    Panics if the rejection sampling fails to generate enough coefficients after multiple attempts (this should be extremely unlikely with proper randomness).

    Poly::uniform_gamma1

    fn Poly::uniform_gamma1(self : Poly, seed : Array[Byte], nonce : UInt16) -> Unit
    Sample polynomial with uniformly random coefficients in [-(GAMMA1 - 1), GAMMA1 - 1] by performing rejection sampling on output stream of SHAKE256(seed|nonce) or AES256CTR(seed,nonce).

    Poly::unpack_eta

    fn Poly::unpack_eta(self : Poly, a : Array[Byte]) -> Unit

    Unpacks a polynomial with small coefficients from a packed byte representation.

    Parameters:

    • self : The polynomial to store the unpacked coefficients. Its coefficients will be modified in place.
    • a : The packed byte array containing the encoded polynomial coefficients.

    Panics:

    • This function will panic if the length of the input byte array a doesn't match the expected size for the current eta parameter.

    The unpacking process depends on the eta value from the Dilithium parameter set:

    • For eta = 2: Each group of 3 bytes encodes 8 polynomial coefficients using 3-bit values
    • For eta = 4: Each byte encodes 2 polynomial coefficients using 4-bit values

    After extracting the raw values, the function transforms them from the range [0, 2*eta] back to the coefficient range [-eta, eta] by computing eta -extracted_value for each coefficient.

    This function is the inverse operation of Poly::pack_eta.

    Poly::unpack_t0

    fn Poly::unpack_t0(self : Poly, a : Array[Byte]) -> Unit

    Unpacks polynomial t0 from its byte array representation with coefficients in the range ]-2^{D-1}, 2^{D-1}].

    Performs the inverse operation of pack_t0, reconstructing polynomial coefficients from their bit-packed byte representation. Each group of 8 coefficients is packed into 13 bytes using a complex bit-packing scheme. The function extracts 13-bit values from the byte array, masks them to ensure they stay within the valid range, and then transforms them back to the signed coefficient representation by subtracting from D_SHL (2^{D-1}).

    Parameters:

    • self : The polynomial to be modified with the unpacked coefficients.
    • a : The byte array containing the packed polynomial data. Must have length N/8 * 13 bytes.

    Panics if the input byte array a does not have the expected length of N/8 * 13 bytes, which would cause an index out of bounds error during unpacking.

    Poly::unpack_t1

    fn Poly::unpack_t1(self : Poly, a : Array[Byte]) -> Unit

    Unpacks polynomial coefficients from a byte array, where each coefficient is stored using 10 bits.

    Parameters:

    • self : The polynomial to store the unpacked coefficients in.
    • a : The byte array containing the packed polynomial coefficients. Must contain at least 5 * (N / 4) bytes where every 5 consecutive bytes encode 4 coefficients.

    Panics:

    Panics if the byte array a does not contain enough bytes for the expected number of coefficients, or if array bounds are exceeded during the unpacking process.

    Poly::unpack_z

    fn Poly::unpack_z(self : Poly, a : Array[Byte]) -> Unit

    Unpacks a polynomial from its bit-packed byte array representation, restoring coefficients in the range [-(GAMMA1 - 1), GAMMA1 - 1].

    This function performs the inverse operation of pack_z, decoding a compressed polynomial representation back into standard coefficient form. The unpacking process depends on the GAMMA1 parameter from the Dilithium context, supporting both GAMMA1 = 2^17 (131072) and GAMMA1 = 2^19 (524288) parameter sets with different bit layouts.

    For GAMMA1 = 2^17:

    • Uses 18-bit representation per coefficient (mask 0x3FFFF)
    • Packs 4 coefficients into 9 bytes (4.5 bytes per coefficient)
    • Each group of 4 coefficients requires 72 bits total

    For GAMMA1 = 2^19:

    • Uses 20-bit representation per coefficient (mask 0xFFFFF)
    • Packs 2 coefficients into 5 bytes (2.5 bytes per coefficient)
    • Each group of 2 coefficients requires 40 bits total

    After bit extraction, coefficients are converted from their packed representation to standard form by computing GAMMA1 - packed_value, ensuring the result lies in the correct range.

    Parameters:

    • self : The polynomial whose coefficients will be modified in place with the unpacked values.
    • a : The byte array containing the bit-packed polynomial data.

    Poly::use_hint

    fn Poly::use_hint(self : Poly, h : Poly) -> Unit
    Use hint polynomial to correct the high bits of a polynomial. 使用提示多项式来修正多项式的高位。

    Arguments / 参数:
    • self: input/output polynomial with corrected high bits / 具有修正高位的输入/输出多项式
    • h: hint polynomial / 提示多项式

    Polyveck

    pub struct Polyveck {
    vec : Array[Poly]
    }

    Vector of polynomials with length k, where k is determined by the Dilithium parameter set.

    This structure represents one of the core data types in the Dilithium post-quantum cryptographic scheme. The length k corresponds to the security parameter that defines the dimensions of the underlying lattice problem. Each polynomial in the vector operates in the ring Z_q[X]/(X^256 + 1) where q is the modulus used in Dilithium.

    Fields:

    • vec : Array containing k polynomials, where each polynomial represents a vector component in the lattice-based operations.
    impl Default for Polyveck
    impl Show for Polyveck

    Polyveck::add

    fn Polyveck::add(w : Polyveck, v : Polyveck) -> Unit

    Adds two polynomial vectors of length K element-wise without modular reduction.

    Parameters:

    • w : The first polynomial vector that will store the result of the addition.
    • v : The second polynomial vector to be added to the first.

    Panics:

    • If either w or v has fewer than K polynomials, where K is determined by the current Dilithium parameter set.

    Polyveck::caddq

    fn Polyveck::caddq(v : Polyveck) -> Unit

    Converts all negative coefficients in the polynomial vector to their positive equivalent by adding Q (the modulus) to each negative coefficient.

    Parameters:

    • v : The polynomial vector of length K whose negative coefficients will be converted to positive form.

    Polyveck::chknorm

    fn Polyveck::chknorm(v : Polyveck, bound : Int) -> Byte
    Check infinity norm of polynomials in vector of length K. Assumes input coefficients to be standard representatives. Returns 0 if norm of all polynomials are strictly smaller than B and 1 otherwise.

    Polyveck::copy

    fn Polyveck::copy(self : Polyveck) -> Polyveck

    Creates a deep copy of the polynomial vector.

    Parameters:

    • self : The polynomial vector to copy.

    Returns a new Polyveck instance with deeply copied polynomials, ensuring that modifications to the returned vector or its polynomials do not affect the original.

    Polyveck::decompose

    fn Polyveck::decompose(v1 : Polyveck, v0 : Polyveck) -> Unit
    For all coefficients a of polynomials in vector of length K, compute high and low bits a0, a1 such a mod Q = a1*ALPHA + a0 with -ALPHA/2 < a0 <= ALPHA/2 except a1 = (Q-1)/ALPHA where we set a1 = 0 and -ALPHA/2 <= a0 = a mod Q - Q < 0. Assumes coefficients to be standard representatives.

    Polyveck::invntt_tomont

    fn Polyveck::invntt_tomont(v : Polyveck) -> Unit

    Applies inverse Number Theoretic Transform (NTT) and multiplies by 2^32 to all polynomials in a vector of length K.

    Parameters:

    • v : The polynomial vector of length K to transform. Input coefficients must be less than 2*Q.

    Panics if the dilithium context is not properly initialized or if the parameter set is invalid.

    Polyveck::make_hint

    fn Polyveck::make_hint(h : Polyveck, v0 : Polyveck, v1 : Polyveck) -> Int

    Computes hint vectors for polynomial coefficients in each polynomial of the vector.

    Parameters:

    • h : The output hint vector where computed hints will be stored.
    • v0 : The first input polynomial vector containing low bits from decomposition.
    • v1 : The second input polynomial vector containing high bits from decomposition.

    Returns the total number of 1 bits across all hint polynomials in the vector.

    Polyveck::ntt

    fn Polyveck::ntt(v : Polyveck) -> Unit

    Applies forward Number Theoretic Transform (NTT) to all polynomials in the vector of length K.

    Parameters:

    • v : The polynomial vector of length K to transform in-place.

    Panics if the vector length does not match the parameter K from the dilithium context.

    Example:

    let polyvec = Polyveck::default()
    // ... initialize polynomials in polyvec ...
    Polyveck::ntt(polyvec)
    // All polynomials in polyvec are now in NTT domain

    Polyveck::pack_w1

    fn Polyveck::pack_w1(self : Polyveck, r : Array[Byte]) -> Unit

    Packs the high bits (w1 components) of all polynomials in the vector into a byte array.

    Parameters:

    • self : The polynomial vector containing the polynomials whose w1 components will be packed.
    • r : The output byte array where the packed w1 data will be stored.

    Panics if the output array r is not large enough to hold all packed w1 data from the k polynomials in the vector.

    Polyveck::pointwise_poly_montgomery

    fn Polyveck::pointwise_poly_montgomery(r : Polyveck, a : Poly, v : Polyveck) -> Unit

    Performs pointwise multiplication of a polynomial with each polynomial in a vector, storing results in the output vector.

    Parameters:

    • r : The output vector where results are stored.
    • a : The polynomial to multiply with each element of the input vector.
    • v : The input vector of polynomials.

    Polyveck::power2round

    fn Polyveck::power2round(v1 : Polyveck, v0 : Polyveck) -> Unit
    For all coefficients a of polynomials in vector of length K, compute a0, a1 such that a mod Q = a1*2^D + a0 with -2^{D-1} < a0 <= 2^{D-1}. Assumes coefficients to be standard representatives.

    Polyveck::reduce

    fn Polyveck::reduce(v : Polyveck) -> Unit

    Reduces coefficients of all polynomials in the vector to representatives in the range [0, 2*Q].

    Parameters:

    • v : The polynomial vector of length K whose coefficients will be reduced.

    Panics if the dilithium context is not properly initialized or if the parameter set is invalid.

    Polyveck::shiftl

    fn Polyveck::shiftl(v : Polyveck) -> Unit
    Multiply vector of polynomials of Length K by 2^D without modular reduction. Assumes input coefficients to be less than 2^{32-D}.

    Polyveck::sub

    fn Polyveck::sub(w : Polyveck, v : Polyveck) -> Unit
    Subtract vectors of polynomials of length K. Assumes coefficients of polynomials in second input vector to be less than 2*Q. No modular reduction is performed.

    Polyveck::uniform_eta

    fn Polyveck::uniform_eta(v : Polyveck, seed : Array[Byte], nonce : UInt16) -> Unit

    Generates uniform random polynomials with coefficients in the range [-eta, eta] for all polynomials in the vector.

    Parameters:

    • v : The polynomial vector of length K to be filled with uniform random coefficients.
    • seed : The random seed bytes used for generating the uniform distribution.
    • nonce : The starting nonce value used for randomness generation, incremented for each polynomial.

    Polyveck::use_hint

    fn Polyveck::use_hint(w : Polyveck, h : Polyveck) -> Unit

    Uses a hint vector to correct the high bits of the input polynomial vector.

    Parameters:

    • w : The polynomial vector whose high bits will be corrected in-place.
    • h : The hint vector containing correction information for each polynomial.

    Example:

    let w = Polyveck::default()
    let h = Polyveck::default()
    // ... populate w and h with appropriate values ...
    w.use_hint(h)
    // w now has its high bits corrected based on the hint vector h

    Polyvecl

    pub struct Polyvecl {
    vec : Array[Poly]
    }

    Vector of polynomials of length L.

    Polyvecl is a fundamental data structure in the Dilithium post-quantum cryptographic scheme that holds an array of L polynomials, where L is determined by the current parameter set. This structure is used throughout the algorithm for operations like matrix expansion, pointwise multiplication, and various polynomial transformations in the NTT domain.
    impl Default for Polyvecl
    impl Show for Polyvecl

    Polyvecl::add

    fn Polyvecl::add(w : Polyvecl, v : Polyvecl) -> Unit

    Adds two polynomial vectors of length L element-wise without performing modular reduction.

    Parameters:

    • w : The first polynomial vector that will store the result of the addition.
    • v : The second polynomial vector to be added to the first vector.

    Panics if the length parameter l from the Dilithium context exceeds the actual length of either polynomial vector.

    Example:

    let w = Polyvecl::default()
    let v = Polyvecl::default()
    // Assume both vectors have been initialized with some polynomial values
    w.add(v) // w now contains the element-wise sum of the original w and v

    Polyvecl::chknorm

    fn Polyvecl::chknorm(v : Polyvecl, bound : Int) -> Byte
    Check infinity norm of polynomials in vector of length L. Assumes input coefficients to be standard representatives. Returns 0 if norm of all polynomials is strictly smaller than B and 1 otherwise.

    Polyvecl::copy

    fn Polyvecl::copy(self : Polyvecl) -> Polyvecl

    Creates a deep copy of the polynomial vector.

    Parameters:

    • self : The polynomial vector to copy.

    Returns a new Polyvecl instance that is an independent copy of the original, where each polynomial in the vector is also deeply copied.

    Polyvecl::invntt_tomont

    fn Polyvecl::invntt_tomont(v : Polyvecl) -> Unit

    Applies the inverse Number Theoretic Transform (NTT) to all polynomials in the vector and multiplies the result by the Montgomery constant 2^32.

    Parameters:

    • v : The vector of polynomials to transform. Each polynomial in the vector will be modified in-place.

    Panics if the vector length does not match the parameter l from the Dilithium context.

    Polyvecl::matrix_expand

    fn Polyvecl::matrix_expand(mat : Array[Polyvecl], rho : Array[Byte]) -> Unit
    Implementation of ExpandA. Generates matrix A with uniformly random coefficients a_{i,j} by performing rejection sampling on the output stream of SHAKE128(rho|j|i)

    Polyvecl::ntt

    fn Polyvecl::ntt(v : Polyvecl) -> Unit

    Applies the forward Number Theoretic Transform (NTT) to all polynomials in the vector of length L.

    Parameters:

    • v : The polynomial vector of length L whose polynomials will be transformed in-place.

    Panics if the polynomial vector length does not match the parameter set's L value.

    Example:

    let polyvec = Polyvecl::default()
    // ... initialize polynomials in polyvec ...
    polyvec.ntt() // Transform all polynomials to NTT domain

    Polyvecl::pointwise_acc_montgomery

    fn Polyvecl::pointwise_acc_montgomery(w : Poly, u : Polyvecl, v : Polyvecl) -> Unit
    Pointwise multiply vectors of polynomials of length L, multiply resulting vector by 2^{-32} and add (accumulate) polynomials in it. Input/output vectors are in NTT domain representation. Input coefficients are assumed to be less than 22Q. Output coefficient are less than 2L*Q.

    Polyvecl::pointwise_poly_montgomery

    fn Polyvecl::pointwise_poly_montgomery(r : Polyvecl, a : Poly, v : Polyvecl) -> Unit

    Multiplies each polynomial in a vector of polynomials by a single polynomial using Montgomery multiplication.

    Parameters:

    • result : The output vector of polynomials where the results will be stored.
    • polynomial : The single polynomial to multiply with each polynomial in the input vector.
    • input_vector : The input vector of polynomials to be multiplied.

    Panics if the length of result or input_vector differs from the parameter l in the current Dilithium context.

    Polyvecl::reduce

    fn Polyvecl::reduce(v : Polyvecl) -> Unit

    Reduces the coefficients of all polynomials in the vector to their canonical representatives.

    Parameters:

    • v : The polynomial vector of length L whose coefficients will be reduced.

    Example:

    let v : Polyvecl = Polyvecl::default()
    // ... populate v with polynomial data ...
    Polyvecl::reduce(v)
    // All polynomials in v now have reduced coefficients

    Polyvecl::uniform_eta

    fn Polyvecl::uniform_eta(v : Polyvecl, seed : Array[Byte], nonce : UInt16) -> Unit

    Generates uniform random polynomials with coefficients in the range determined by the eta parameter for all polynomials in the vector.

    Parameters:

    • v : The polynomial vector of length L to be filled with uniform random polynomials.
    • seed : The random seed bytes used for generating the uniform distribution.
    • nonce : The starting nonce value used to ensure different randomness for each polynomial in the vector.

    Polyvecl::uniform_gamma1

    fn Polyvecl::uniform_gamma1(v : Polyvecl, seed : Array[Byte], nonce : UInt16) -> Unit

    Generates uniform random coefficients for all polynomials in a vector using the gamma1 distribution.

    Parameters:

    • v : The polynomial vector of length L to populate with uniform gamma1 coefficients.
    • seed : The cryptographic seed used for random number generation.
    • nonce : The base nonce value used to ensure different randomness for each polynomial.

    Panics if the dilithium context is not properly initialized when accessing the parameter set.

    SecurityLevel

    pub(all) enum SecurityLevel {
    Dilithium2
    Dilithium3
    Dilithium5
    }

    Security levels supported by the Dilithium signature scheme.

    Each variant provides different security strengths and performance characteristics:
    • Dilithium2: 128-bit classical security, fastest performance
    • Dilithium3: 192-bit classical security, balanced performance
    • Dilithium5: 256-bit classical security, highest security

    CRHBYTES

    let CRHBYTES : Int

    Size in bytes for collision-resistant hash function outputs. This constant defines the output size for cryptographic hash functions, particularly for operations requiring 512-bit (64-byte) digests in the Dilithium signature scheme.

    This constant specifies the output size in bytes for cryptographic hash functions, particularly for operations that require 64-byte hash outputs. In the context of Dilithium, this is commonly used for collision-resistant hash functions and other cryptographic primitives that produce 512-bit (64-byte) digests.

    let D : Int

    The rounding parameter D used in power-of-2 rounding operations. This determines the precision of rounding in various cryptographic operations.
    let N : Int

    The dimension N of the polynomial ring Z_q[X]/(X^N + 1). This determines the degree of polynomials used in the scheme.

    POLYT0_PACKEDBYTES

    let POLYT0_PACKEDBYTES : Int

    Size in bytes for packed polynomial coefficients in the t0 representation. Used for efficient storage and transmission of polynomial data.

    POLYT1_PACKEDBYTES

    let POLYT1_PACKEDBYTES : Int

    Size in bytes for packed polynomial coefficients in the t1 representation. Used for efficient storage and transmission of polynomial data.

    POLY_UNIFORM_NBLOCKS

    let POLY_UNIFORM_NBLOCKS : UInt

    Defines the number of 128-byte blocks needed to generate sufficient random bytes for uniform polynomial sampling.

    This constant calculates the minimum number of SHAKE128 output blocks required to ensure that rejection sampling can successfully generate all N coefficients for a polynomial with high probability. The calculation accounts for the overhead in rejection sampling where not all random bytes result in valid coefficients in the range [0, Q-1].

    The value is computed as ⌈768 / STREAM128_BLOCKBYTES⌉, where 768 bytes provides enough random material for the rejection sampling algorithm to succeed with very high probability.

    let Q : Int

    The modulus q for the polynomial ring Z_q[X]/(X^N + 1). All polynomial coefficients are reduced modulo this prime value.

    SEEDBYTES

    let SEEDBYTES : Int

    Size in bytes for random seeds used in key generation and signature operations. This corresponds to 256-bit security strength for the seed material.

    SHAKE128_RATE

    let SHAKE128_RATE : UInt

    Rate (block size) in bytes for the SHAKE128 extendable-output function. This determines the input block size for the Keccak sponge construction.

    SHAKE256_RATE

    let SHAKE256_RATE : UInt

    Rate (block size) in bytes for the SHAKE256 extendable-output function. This determines the input block size for the Keccak sponge construction.

    STREAM128_BLOCKBYTES

    let STREAM128_BLOCKBYTES : UInt

    Block size in bytes for SHAKE128-based streaming operations. Alias for SHAKE128_RATE to maintain consistency with the reference implementation.

    STREAM256_BLOCKBYTES

    let STREAM256_BLOCKBYTES : UInt

    Block size in bytes for SHAKE256-based streaming operations. Alias for SHAKE256_RATE to maintain consistency with the reference implementation.

    caddq

    fn caddq(a : Int) -> Int
    如果输入为负数,则加上Q

    decompose

    fn decompose(a : Int) -> (Int, Int)

    Decomposes an integer into two components according to the Dilithium signature scheme's decomposition algorithm.

    This function implements the Decompose operation from the Dilithium post-quantum cryptographic signature scheme. It splits an input integer a into two parts a0 and a1 such that a = a0 + a1 * 2 * gamma2, where gamma2 is determined by the current Dilithium parameter set and can be either (Q-1)/32 or (Q-1)/88.

    Parameters:

    • a : The integer to be decomposed.

    Returns a tuple (a0, a1) where a0 is the low-order component and a1 is the high-order component of the decomposition.

    dilithium_context

    let dilithium_context : DilithiumContext
    default random is very dangerous, please use your own random source

    dilithium_shake128_stream_init

    fn dilithium_shake128_stream_init(state : KeccakState, seed : Array[Byte], nonce : UInt16) -> Unit

    Initializes a SHAKE128 stream for the CRYSTALS-Dilithium post-quantum cryptographic scheme.

    Parameters:

    • state : The Keccak state to be initialized for streaming.
    • seed : A byte array containing the seed data, expected to be of length SEEDBYTES.
    • nonce : A 16-bit unsigned integer used as a unique identifier for this stream instance.

    Example:

    let state = KeccakState::default()
    let seed: Array[Byte] = Array::make(SEEDBYTES, 0) // Create seed of appropriate size
    @ruifeng/moondsa.dilithium_shake128_stream_init(state, seed, (42: UInt16))

    dilithium_shake256_stream_init

    fn dilithium_shake256_stream_init(state : KeccakState, seed : Array[Byte], nonce : UInt16) -> Unit

    Initializes a SHAKE256 stream for Dilithium cryptographic operations with a seed and nonce.

    Parameters:

    • state : The Keccak state to initialize for SHAKE256 streaming.
    • seed : The cryptographic seed bytes used for initialization.
    • nonce : A 16-bit nonce value to ensure uniqueness of the stream.

    Example:

    let state = KeccakState::default()
    let seed : Array[Byte] = Array::make(CRHBYTES, 0) // 64-byte seed
    let nonce = (42: UInt16)
    dilithium_shake256_stream_init(state, seed, nonce)

    inv_ntt_to_mont

    fn inv_ntt_to_mont(a : Array[Int]) -> Unit
    Inverse Number Theoretic Transform (INTT) 逆向数论变换 (INTT)

    Performs in-place inverse NTT with Montgomery factor multiplication. 执行原地逆向 NTT 并乘以蒙哥马利因子。

    Algorithm details / 算法细节:
    • Decimation-in-time (DIT) butterfly operations / 时域抽取蝶形运算
    • Uses negative twiddle factors / 使用负旋转因子
    • Final multiplication by F = (R^2/N) mod Q / 最终乘以 F = (R^2/N) mod Q
    • No modular reduction during butterfly operations / 蝶形运算期间不进行模约简

    The factor F serves three purposes / 因子 F 有三个作用:
    1. Divide by N to normalize the transform / 除以 N 来归一化变换
    2. Multiply by R to keep result in Montgomery domain / 乘以 R 保持结果在蒙哥马利域
    3. Multiply by R again to compensate for Montgomery reduction / 再乘以 R 补偿蒙哥马利约简

    Complexity / 复杂度: O(N log N) where N = 256

    Arguments / 参数:
    • a: input/output coefficient array (length 256) / 输入/输出系数数组(长度256)

    Preconditions / 前置条件:
    • Input is in bit-reversed order (output of NTT) / 输入为比特翻转顺序(NTT的输出)
    • Input coefficients < Q in absolute value / 输入系数绝对值 < Q

    Postconditions / 后置条件:
    • Output is in standard order / 输出为标准顺序
    • Output coefficients < Q in absolute value / 输出系数绝对值 < Q
    • Result remains in Montgomery domain / 结果保持在蒙哥马利域中

    ite

    fn ite(cond : Bool, a : Int, b : Int) -> Int

    Implements constant-time conditional selection between two integer values.

    Parameters:

    • cond : The boolean condition that determines which value to select.
    • a : The integer value to return when the condition is true.
    • b : The integer value to return when the condition is false.

    Returns the value a if cond is true, otherwise returns b.

    Example:

    let result1 = @ruifeng/moondsa.ite(true, 10, 20) // returns 10
    let result2 = @ruifeng/moondsa.ite(false, 10, 20) // returns 20

    keccakf1600_statepermute

    fn keccakf1600_statepermute(state : FixedArray[UInt64]) -> Unit
    Keccak-f[1600] permutation function | Keccak-f[1600] 置换函数 Applies the complete Keccak permutation to the state 对状态应用完整的 Keccak 置换

    keypair_gen

    fn keypair_gen(seed : Result[Array[Byte],
    Rand
    ]) -> (Array[Byte], Array[Byte])

    Generates a cryptographic key pair for the Dilithium post-quantum signature scheme.

    This function implements the key generation algorithm from the NIST FIPS 204 standard. It constructs a Module-LWE (MLWE) key pair where the public key is derived from the secret key through matrix multiplication in the polynomial ring Z_q[X]/(X^N + 1).

    Algorithm Overview

    The key generation follows the MLWE construction:
    1. Generate random seed ρ for matrix expansion and seed κ for secret key derivation
    2. Expand ρ into matrix A ∈ R_q^{k×l} using SHAKE128 (deterministic expansion)
    3. Sample secret vectors s1 ∈ R_q^l and s2 ∈ R_q^k with coefficients in {-η, ..., η}
    4. Compute public vector t = A·s1 + s2 (matrix-vector multiplication)
    5. Compress t into t1 (high bits) and t0 (low bits) using power-of-2 rounding
    6. Pack (ρ, t1) as public key and (ρ, tr, κ, t0, s1, s2) as secret key

    Security Construction

    The security relies on the hardness of the Module Learning With Errors problem:
    • Given (A, t), it's computationally hard to recover (s1, s2)
    • The error term s2 provides the "learning with errors" hardness
    • The rounding of t provides compression while maintaining security

    Parameters

    • seed : Either:
      • Ok(seed_bytes): 32-byte seed for deterministic key generation (ρ = seed)
      • Err(rand): Random number generator for non-deterministic generation

    Returns

    A tuple (public_key, secret_key) where:
    • public_key: Packed (ρ, t1) - matrix seed + compressed public vector
    • secret_key: Packed (ρ, tr, κ, t0, s1, s2) - complete key material

    Key Sizes by Security Level

    LevelPublic KeySecret KeySecurity
    21312 bytes2528 bytes128-bit
    31952 bytes4016 bytes192-bit
    52592 bytes4864 bytes256-bit

    load64

    fn load64(x : Array[Byte]) -> UInt64

    Converts an 8-byte array into a 64-bit unsigned integer using little-endian byte ordering.

    Parameters:

    • x : An array of 8 bytes to be converted to a 64-bit integer.

    Returns a UInt64 value constructed from the input bytes in little-endian format.

    make_hint

    fn make_hint(a0 : Int, a1 : Int) -> Byte

    Generates a hint byte based on the decomposed polynomial coefficient components for use in the Dilithium signature scheme.

    Parameters:

    • a0 : The low-order component of the decomposed coefficient.
    • a1 : The high-order component of the decomposed coefficient.

    Returns a hint byte (0 or 1) indicating whether the coefficient requires adjustment during verification.

    montgomery_reduce

    fn montgomery_reduce(a : Int64) -> Int
    将 a 从蒙哥马利域转换到普通域 return a * R^-1 % Q

    ntt

    fn ntt(a : Array[Int]) -> Unit
    Forward Number Theoretic Transform (NTT) 正向数论变换 (NTT)

    Performs in-place Cooley-Tukey NTT using Montgomery arithmetic. 使用蒙哥马利算术执行原地 Cooley-Tukey NTT。

    Algorithm details / 算法细节:
    • Decimation-in-frequency (DIF) butterfly operations / 频域抽取蝶形运算
    • No modular reduction after additions/subtractions / 加减法后不进行模约简
    • Output is in bit-reversed order / 输出为比特翻转顺序
    • All coefficients remain in Montgomery domain / 所有系数保持在蒙哥马利域中

    Arguments / 参数:
    • a: input/output coefficient array (length 256) / 输入/输出系数数组(长度256)

    pack_pk

    fn pack_pk(rho : Array[Byte], t1 : Polyveck) -> Array[Byte]

    Serializes a public key into its binary representation by concatenating the seed rho and packed polynomial vector t1.

    Parameters:

    • rho : The random seed used in key generation, typically 32 bytes.
    • t1 : The polynomial vector representing the public component of the key.

    Returns a byte array containing the packed public key data.

    pack_sig

    fn pack_sig(sig : Array[Byte], c : Array[Byte]?, z : Polyvecl, h : Polyveck) -> Array[Byte]

    Bit-packs a Dilithium signature into a byte array format.

    Parameters:

    • sig : The output byte array to store the packed signature data.
    • c : The optional challenge hash bytes. If Some, the challenge is included in the packed signature; if None, the challenge portion is left uninitialized.
    • z : The polynomial vector z component of the signature.
    • h : The polynomial vector h component of the signature containing hint information.

    Returns the packed signature as a byte array.

    pack_sk

    fn pack_sk(rho : Array[Byte], tr : Array[Byte], key : Array[Byte], t0 : Polyveck, s1 : Polyvecl, s2 : Polyveck) -> Array[Byte]

    Serializes a Dilithium secret key into a compact byte array format.

    Parameters:

    • rho : A 32-byte seed used for generating the public matrix A.
    • tr : A 64-byte hash of the public key.
    • key : A 32-byte seed used for signing.
    • t0 : A polynomial vector containing the low-order bits of t.
    • s1 : A polynomial vector containing the first part of the secret key.
    • s2 : A polynomial vector containing the second part of the secret key.

    Returns a byte array containing the packed secret key in the format: rho || key || tr || s1 || s2 || t0.

    polyvec_matrix_pointwise_montgomery

    fn polyvec_matrix_pointwise_montgomery(t : Polyveck, mat : Array[Polyvecl], v : Polyvecl) -> Unit

    Performs matrix-vector multiplication using pointwise Montgomery multiplication in the NTT domain.

    Computes the result of multiplying a matrix of polynomial vectors by a single polynomial vector, where each row of the matrix is multiplied with the input vector and accumulated into the corresponding element of the result vector. This operation is performed in the NTT (Number Theoretic Transform) domain using Montgomery reduction for efficiency.

    Parameters:

    • t : The result polynomial vector of length k where the computed products will be stored.
    • mat : A matrix represented as an array of polynomial vectors, where each element is a row of the matrix.
    • v : The input polynomial vector of length l to be multiplied with each row of the matrix.

    Example:

    let t = Polyveck::default()
    let mat : Array[Polyvecl] = Array::new()
    let v = Polyvecl::default()

    // Initialize matrix with appropriate dimensions
    let k = dilithium_context.get_params_set().k
    for i in 0..<k {
    mat.push(Polyvecl::default())
    }

    polyvec_matrix_pointwise_montgomery(t, mat, v)

    power2round

    fn power2round(a : Int) -> (Int, Int)

    Decomposes an integer a into two components a0 and a1 such that a =a0 + a1 * 2^D, where D is a predefined constant.

    This function implements the power-of-2 rounding operation commonly used in lattice-based cryptography, particularly in the Dilithium digital signature scheme. The decomposition ensures that a0 is in the range [-2^(D-1),2^(D-1)) and a1 represents the higher-order bits.

    Parameters:

    • a : The integer value to be decomposed.

    Returns a tuple (a0, a1) where a0 is the low-order component and a1 is the high-order component such that a = a0 + a1 * 2^D.

    randombytes

    fn randombytes(rand :
    Rand
    , n : Int) -> Array[Byte]

    reduce32

    fn reduce32(a : Int) -> Int
    对于一个有限域元素a, a <= 2 ^ {31} - 2 ^ {22} - 1, 计算 r \equiv a (mod Q), 满足 -6283009 <= r <= 6283008

    rej_eta

    fn rej_eta(a : ArrayView[Int], len : Int, buf : Array[Byte], buflen : Int) -> UInt

    Performs rejection sampling on a buffer of random bytes to generate coefficients in the range [-eta, eta] for Dilithium polynomial operations.

    This function extracts 4-bit values from each byte in the input buffer and uses rejection sampling to convert them into coefficients within the valid range based on the eta parameter from the Dilithium context. For eta=2, it uses modular arithmetic to map values [0,14] to [-2,2]. For eta=4, it directly maps values [0,8] to [-4,4].

    Parameters:

    • a : The output array view where accepted coefficients will be stored.
    • len : The maximum number of coefficients to generate.
    • buf : The input buffer containing random bytes for sampling.
    • buflen : The length of the input buffer in bytes.

    Returns the number of coefficients successfully generated and stored in the output array.

    rej_uniform

    fn rej_uniform(a : ArrayView[Int], len : Int, buf : Array[Byte], buflen : Int) -> Int
    Sample uniformly random coefficients in [0, Q-1] by performing rejection sampling on array of random bytes. Returns number of sampled coefficients. Can be smaller than len if not enough random bytes were given. 通过对随机字节数组执行拒绝采样来采样 [0, Q-1] 范围内的均匀随机系数。 返回采样系数的数量。如果给定的随机字节不够,可能小于 len。

    Arguments / 参数:
    • a: output array for coefficients / 系数的输出数组
    • len: number of coefficients to sample / 要采样的系数数量
    • buf: input buffer of random bytes / 随机字节的输入缓冲区
    • buflen: length of input buffer / 输入缓冲区的长度

    Returns / 返回: number of coefficients successfully sampled / 成功采样的系数数量

    shake128_absorb

    fn shake128_absorb(state : KeccakState, input : Array[Byte], inlen : UInt) -> Unit

    Incrementally absorbs input data into a SHAKE128 state for cryptographic hashing.

    This function is part of the SHAKE128 extendable-output function (XOF) implementation. It processes input data in chunks, updating the internal Keccak state without finalizing the hash. Multiple calls to this function can be made to absorb data incrementally before calling the finalize function.

    Parameters:

    • state : The SHAKE128 state to absorb data into. The state maintains the current position and internal Keccak state array.
    • input : The byte array containing the data to be absorbed into the hash state.
    • inlen : The number of bytes from the input array to process. This allows processing only a portion of the input array if needed.

    Example:

    let state = KeccakState::default()
    let data : Array[Byte] = "Hello, World!".to_bytes().to_array()
    shake128_absorb(state, data, data.length().reinterpret_as_uint())
    // Continue absorbing more data if needed
    let more_data : Array[Byte] = " More data".to_bytes().to_array()
    shake128_absorb(state, more_data, more_data.length().reinterpret_as_uint())
    // Finally call shake128_finalize(state) to complete the absorption phase

    shake128_finalize

    fn shake128_finalize(state : KeccakState) -> Unit

    Finalizes the SHAKE128 absorbing phase by applying proper padding and transitions the state to the squeezing phase.

    Parameters:

    • state : The SHAKE128 state that has been absorbing input data and needs to be finalized.

    Example:

    let state = KeccakState::default()
    let input : Array[Byte] = "Hello, World!".to_bytes().to_array()
    shake128_absorb(state, input, input.length().reinterpret_as_uint())
    shake128_finalize(state)
    // State is now ready for squeezing output

    shake128_squeezeblocks

    fn shake128_squeezeblocks(output : ArrayView[Byte], nblocks : UInt, s : KeccakState) -> Unit

    Extracts full blocks of output data from a SHAKE128 state.

    Parameters:

    • output : The buffer to store the extracted output bytes.
    • nblocks : The number of complete blocks to extract from the state.
    • s : The SHAKE128 state to extract data from.

    Example:

    let state = KeccakState::default()
    // ... after initializing and finalizing the state ...
    let output: Array[Byte] = Array::make(336, 0) // 2 blocks * 168 bytes per block
    shake128_squeezeblocks(output, 2, state)

    shake256

    fn shake256(output~ : Array[Byte], outlen : UInt, input~ : Array[Byte], inlen : UInt) -> Unit
    SHAKE256 complete operation | SHAKE256 完整操作 Performs complete SHAKE256 hash: absorb input and squeeze output 执行完整的 SHAKE256 哈希:吸收输入并挤压输出

    shake256_absorb

    fn shake256_absorb(state : KeccakState, input : Array[Byte], inlen : UInt) -> Unit

    Incrementally absorbs input data into the SHAKE256 state during the absorbing phase.

    This function allows you to feed data to SHAKE256 in multiple chunks rather than all at once. The state maintains its position internally, so you can call this function multiple times with different input chunks before finalizing and squeezing output.

    Parameters:

    • state (KeccakState) : The SHAKE256 state object that maintains the internal hash state.
    • input (Array[Byte]) : The byte array containing the data to absorb.
    • inlen (UInt) : The number of bytes to absorb from the input array.

    Example:

    let state = @ruifeng/moondsa.KeccakState::default()
    let chunk1 : Array[Byte] = b"Hello, ".to_array()
    let chunk2 : Array[Byte] = b"World!".to_array()

    // Absorb data incrementally
    @ruifeng/moondsa.shake256_absorb(state, chunk1, 7U)
    @ruifeng/moondsa.shake256_absorb(state, chunk2, 6U)

    // Finalize before squeezing
    @ruifeng/moondsa.shake256_finalize(state)

    // Now squeeze output
    let output : Array[Byte] = Array::make(32, 0)
    @ruifeng/moondsa.shake256_squeeze(output, 32U, state)

    shake256_absorb_once

    fn shake256_absorb_once(state : KeccakState, input : Array[Byte], inlen : UInt) -> Unit

    Performs complete SHAKE256 absorption in a single operation, processing all input data and finalizing the state.

    Parameters:

    • state : The Keccak state to be initialized and used for absorption.
    • input : The byte array containing the data to be absorbed.
    • inlen : The number of bytes from the input array to process.

    Example:

    let state = @ruifeng/moondsa.KeccakState::default()
    let data : Array[Byte] = [0, 1, 2, 3]
    @ruifeng/moondsa.shake256_absorb_once(state, data, 4)
    // State is now ready for squeezing output

    shake256_finalize

    fn shake256_finalize(state : KeccakState) -> Unit

    Finalizes the SHAKE256 absorbing phase by applying proper padding and preparing the state for output extraction.

    Parameters:

    • state : The SHAKE256 Keccak state to finalize, which has been absorbing input data.

    Example:

    let state = @ruifeng/moondsa.KeccakState::default()
    let input : Array[Byte] = b"hello world".to_array()
    @ruifeng/moondsa.shake256_absorb(state, input, 11)
    @ruifeng/moondsa.shake256_finalize(state)
    // State is now ready for squeezing output

    shake256_squeeze

    fn shake256_squeeze(out : ArrayView[Byte], outlen : UInt, state : KeccakState) -> Unit

    Extracts output bytes from a SHAKE256 state in the squeezing phase.

    Parameters:

    • out : The output buffer to write the extracted bytes to.
    • outlen : The number of bytes to extract from the state.
    • state : The SHAKE256 state to squeeze from. The state's internal position will be updated to reflect the new position after squeezing.

    Example:

    // Initialize SHAKE256 state and absorb some data
    let state = KeccakState::default()
    let input : Array[Byte] = "Hello, World!".to_bytes().to_array()
    shake256_absorb(state, input, input.length().reinterpret_as_uint())
    shake256_finalize(state)

    // Squeeze 32 bytes of output
    let output : Array[Byte] = Array::make(32, 0)
    shake256_squeeze(output[:], 32, state)

    shake256_squeezeblocks

    fn shake256_squeezeblocks(out : Array[Byte], nblocks : UInt, state : KeccakState) -> Unit

    Extracts full blocks of output data from a SHAKE256 state.

    Parameters:

    • out : The output array to store the extracted bytes.
    • nblocks : The number of full blocks to extract from the state.
    • state : The SHAKE256 state to extract data from.

    Examples:

    // Initialize SHAKE256 state and absorb some input
    let state = KeccakState::default()
    shake256_absorb_once(state, [1, 2, 3, 4], 4)

    // Extract 2 full blocks (272 bytes total for SHAKE256)
    let output : Array[Byte] = Array::make(272, 0)
    shake256_squeezeblocks(output, 2, state)

    sign

    fn sign(m : Array[Byte], sk : Array[Byte]) -> Array[Byte]

    Creates a digital signature for a message using the Fiat-Shamir with Aborts signature scheme.

    This implements the Dilithium signature algorithm using rejection sampling to ensure signature security. The process follows the "Fiat-Shamir with Aborts" paradigm where the signer repeatedly samples randomness until obtaining a valid signature.

    Algorithm Overview

    The signing process implements the following steps:
    1. Derive deterministic randomness: μ = H(tr || m) where tr = H(pk)
    2. Sample masking vector y ∈ R_q^l with coefficients in [-γ1+β, γ1-β]
    3. Compute commitment w = A·y (matrix-vector multiplication)
    4. Decompose w = w1·2^D + w0 using power-of-2 rounding
    5. Compute challenge c = H(μ || w1) (hash-based challenge)
    6. Compute response z = y + c·s1
    7. Check rejection conditions: ||z||∞ < γ1-β and ||w0-c·s2||∞ < γ2-β
    8. If rejected, restart with fresh randomness
    9. Compute hints h for w1 reconstruction
    10. Pack signature as (c, z, h)

    Security Mechanism

    The rejection sampling ensures:
    • Signature distributions are independent of secret key
    • No information leakage through failed attempts
    • Valid signatures satisfy norm bounds for verification

    Parameters

    • message : Byte array containing the message to be signed
    • secret_key : Packed secret key containing (ρ, tr, κ, t0, s1, s2)

    Returns

    Byte array containing the signature σ = (c, z, h) where:
    • c: Challenge polynomial (seed for reconstruction)
    • z: Response vector with coefficients in [-γ1+β, γ1+β]
    • h: Hint vector for w1 reconstruction

    Signature Structure by Security Level

    LevelStructureSize
    2(c, z, h)2420 bytes
    3(c, z, h)3293 bytes
    5(c, z, h)4595 bytes

    Rejection Sampling

    The algorithm uses rejection sampling to ensure:
    • z has small coefficients (prevents key recovery)
    • w0-c·s2 has small coefficients (prevents forgery)
    • Expected number of iterations is small (≈ 2.2 for typical parameters)

    store64

    fn store64(x : Array[Byte], u : UInt64) -> Unit

    Stores a 64-bit unsigned integer into an 8-byte array using little-endian byte order.

    Parameters:

    • x : The 8-byte array where the integer will be stored.
    • u : The 64-bit unsigned integer to be stored.

    stream128_init

    fn stream128_init(state : KeccakState, seed : Array[Byte], nonce : UInt16) -> Unit

    Initializes a SHAKE128 stream for Dilithium cryptographic operations.

    Parameters:

    • state : The Keccak state to be initialized for streaming operations.
    • seed : The seed bytes used for initialization (expected to be SEEDBYTES length).
    • nonce : A 16-bit nonce value to ensure unique stream initialization.

    Example:

    let state = @ruifeng/moondsa.KeccakState::default()
    let seed: Array[Byte] = Array::make(32, 0) // SEEDBYTES length
    let nonce = (42: UInt16)
    @ruifeng/moondsa.stream128_init(state, seed, nonce)

    stream128_squeezeblocks

    fn stream128_squeezeblocks(out : ArrayView[Byte], outblocks : UInt64, state : KeccakState) -> Unit

    Squeezes multiple full blocks of output data from a SHAKE128 state.

    Parameters:

    • out : The output buffer where the squeezed data will be written.
    • outblocks : The number of full blocks to squeeze from the state.
    • state : The SHAKE128 state to squeeze data from.

    stream256_init

    fn stream256_init(state : KeccakState, seed : Array[Byte], nonce : UInt16) -> Unit

    Initializes a SHAKE256 stream state for cryptographic operations with a seed and nonce.

    Parameters:

    • state : The KeccakState object to be initialized for SHAKE256 streaming.
    • seed : The cryptographic seed bytes used to initialize the stream state.
    • nonce : A 16-bit nonce value to provide uniqueness for each stream initialization.

    Example:

    let state = KeccakState::default()
    let seed : Array[Byte] = Array::make(CRHBYTES, b'A') // 64-byte seed
    stream256_init(state, seed, (42: UInt16))

    stream256_squeezeblocks

    fn stream256_squeezeblocks(out : Array[Byte], outblocks : UInt64, state : KeccakState) -> Unit

    Extracts multiple full blocks of output from a SHAKE256 stream state.

    Parameters:

    • out : The output array where the extracted bytes will be stored.
    • outblocks : The number of blocks to extract from the stream.
    • state : The SHAKE256 stream state to extract blocks from.

    unpack_pk

    fn unpack_pk(pk : Array[Byte]) -> (Array[Byte], Polyveck)

    Unpacks a public key from its bit-packed representation into its constituent components.

    Parameters:

    • pk : The bit-packed public key as a byte array.

    Returns a tuple containing the seed rho and the polynomial vector t1.

    unpack_sig

    fn unpack_sig(sig : Array[Byte]) -> Result[(Polyvecl, Polyveck, Array[Byte]), SignError]

    Unpacks a Dilithium signature from its byte array representation into its constituent components.

    Parameters:

    • sig : The byte array containing the packed signature data.

    Returns a Result containing either:

    • Ok((z, h, c)) where z is the polynomial vector of length l, h is the hint polynomial vector of length k, and c is the challenge seed array
    • Err(SignError) if the signature format is invalid

    Throws an error of type SignError if:

    • The hint polynomial indices are not in ascending order (violates strong unforgeability)
    • The hint polynomial count exceeds the maximum allowed value omega
    • Extra hint indices contain non-zero values (violates strong unforgeability)
    • Any other signature format validation fails

    unpack_sk

    fn unpack_sk(sk : Array[Byte]) -> (Array[Byte], Array[Byte], Array[Byte], Polyveck, Polyvecl, Polyveck)

    Unpacks a Dilithium secret key from its binary representation into its constituent components.

    Parameters:

    • sk : The packed secret key as a byte array containing the serialized components in the specified order.

    Returns a tuple containing the unpacked secret key components: (rho, key,tr, t0, s1, s2) where:

    • rho : The random seed used for matrix generation (32 bytes)
    • key : The signing key seed (32 bytes)
    • tr : The hash of the public key (32 bytes)
    • t0 : The low-order bits of the NTT of the public key polynomial vector
    • s1 : The first secret polynomial vector with coefficients in the range [-eta, eta]
    • s2 : The second secret polynomial vector with coefficients in the range [-eta, eta]

    use_hint

    fn use_hint(a : Int, hint : Byte) -> Int

    Applies a hint to adjust the high-order bits of a polynomial coefficient in the Dilithium signature scheme.

    Parameters:

    • a : The polynomial coefficient to be adjusted.
    • hint : A hint byte that determines whether adjustment should be applied (0 = no adjustment, non-zero = apply adjustment).

    Returns the adjusted high-order bits a1 after applying the hint-based correction.

    verify

    fn verify(sig : Array[Byte], m : Array[Byte], pk : Array[Byte]) -> Result[Unit, SignError]

    Verifies a Dilithium signature using the Fiat-Shamir verification equation.

    This function implements the verification counterpart to the sign function, checking whether a signature σ = (c, z, h) is valid for message m under public key pk = (ρ, t1). It completes the signature lifecycle started by keypair_gen and sign.

    Relationship to Key Generation and Signing

    This verification function validates signatures created by the sign function using public keys generated by keypair_gen. The verification process reconstructs the cryptographic proof that the signer knew the secret key corresponding to the public key.

    Verification Equation

    The verifier checks the Fiat-Shamir equation: c = H(μ || w1) where:
    • μ = H(H(ρ, t1) || m) - message digest (same computation as in sign)
    • w1 = HighBits(A·z - c·t1) - reconstructed commitment using signature components
    • HighBits() extracts high-order bits after rounding (inverse of sign's decomposition)

    Algorithm Steps

    1. Parse signature: σ = (c, z, h) and public key: pk = (ρ, t1) (inverse of pack_sig)
    2. Verify signature format and component bounds (security check)
    3. Compute μ = H(H(ρ, t1) || m) - same message digest as used in sign
    4. Expand ρ into matrix A ∈ R_q^{k×l} using SHAKE128 (same expansion as keypair_gen)
    5. Reconstruct w1 = HighBits(A·z - c·t1) using hints h (inverse of sign's hint generation)
    6. Compute c' = H(μ || w1) - expected challenge (same computation as in sign)
    7. Verify c = c' - signature validity (final check)

    Security Properties

    The verification ensures the signature proves knowledge of the secret key without revealing it:
    • Signature components are within valid ranges (prevents forgery)
    • Response vector z has bounded coefficients (prevents key recovery)
    • Reconstructed commitment matches expected value (proves secret key knowledge)
    • No forgery attempts succeed (maintains unforgeability)

    Parameters

    • sig : Byte array containing signature σ = (c, z, h) from sign
    • m : Byte array containing the original message that was signed
    • pk : Byte array containing public key pk = (ρ, t1) from keypair_gen

    Returns

    • Ok(()): Signature is valid - verification equation holds, proving the signer knew the secret key
    • Err(SignError): Signature is invalid - specific failure reason indicating potential forgery or corruption

    Verification Failures

    Common failure modes indicate security violations:
    • Invalid signature format (wrong length or encoding) - malformed signature
    • Response vector z has coefficients outside bounds - potential key recovery attack
    • Reconstructed commitment doesn't match challenge - signature forgery attempt
    • Signature components don't satisfy norm constraints - malformed signature