/* Copyright (c) 2023, Google LLC * * Permission to use, copy, modify, and/or distribute this software for any * purpose with or without fee is hereby granted, provided that the above * copyright notice and this permission notice appear in all copies. * * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ #define OPENSSL_UNSTABLE_EXPERIMENTAL_DILITHIUM #include <openssl/experimental/dilithium.h> #include <assert.h> #include <stdlib.h> #include <openssl/bytestring.h> #include <openssl/rand.h> #include "../internal.h" #include "../keccak/internal.h" #include "./internal.h" #define DEGREE … #define K … #define L … #define ETA … #define TAU … #define BETA … #define OMEGA … #define RHO_BYTES … #define SIGMA_BYTES … #define K_BYTES … #define TR_BYTES … #define MU_BYTES … #define RHO_PRIME_BYTES … #define LAMBDA_BITS … #define LAMBDA_BYTES … // 2^23 - 2^13 + 1 static const uint32_t kPrime = …; // Inverse of -kPrime modulo 2^32 static const uint32_t kPrimeNegInverse = …; static const int kDroppedBits = …; static const uint32_t kHalfPrime = …; static const uint32_t kGamma1 = …; static const uint32_t kGamma2 = …; // 256^-1 mod kPrime, in Montgomery form. static const uint32_t kInverseDegreeMontgomery = …; scalar; vectork; vectorl; matrix; /* Arithmetic */ // This bit of Python will be referenced in some of the following comments: // // q = 8380417 // # Inverse of -q modulo 2^32 // q_neg_inverse = 4236238847 // # 2^64 modulo q // montgomery_square = 2365951 // // def bitreverse(i): // ret = 0 // for n in range(8): // bit = i & 1 // ret <<= 1 // ret |= bit // i >>= 1 // return ret // // def montgomery_reduce(x): // a = (x * q_neg_inverse) % 2**32 // b = x + a * q // assert b & 0xFFFF_FFFF == 0 // c = b >> 32 // assert c < q // return c // // def montgomery_transform(x): // return montgomery_reduce(x * montgomery_square) // kNTTRootsMontgomery = [ // montgomery_transform(pow(1753, bitreverse(i), q)) for i in range(256) // ] static const uint32_t kNTTRootsMontgomery[256] = …; // Reduces x mod kPrime in constant time, where 0 <= x < 2*kPrime. static uint32_t reduce_once(uint32_t x) { … } // Returns the absolute value in constant time. static uint32_t abs_signed(uint32_t x) { … } // Returns the absolute value modulo kPrime. static uint32_t abs_mod_prime(uint32_t x) { … } // Returns the maximum of two values in constant time. static uint32_t maximum(uint32_t x, uint32_t y) { … } static void scalar_add(scalar *out, const scalar *lhs, const scalar *rhs) { … } static void scalar_sub(scalar *out, const scalar *lhs, const scalar *rhs) { … } static uint32_t reduce_montgomery(uint64_t x) { … } // Multiply two scalars in the number theoretically transformed state. static void scalar_mult(scalar *out, const scalar *lhs, const scalar *rhs) { … } // In place number theoretic transform of a given scalar. // // FIPS 204, Algorithm 35 (`NTT`). static void scalar_ntt(scalar *s) { … } // In place inverse number theoretic transform of a given scalar. // // FIPS 204, Algorithm 36 (`NTT^-1`). static void scalar_inverse_ntt(scalar *s) { … } static void vectork_zero(vectork *out) { … } static void vectork_add(vectork *out, const vectork *lhs, const vectork *rhs) { … } static void vectork_sub(vectork *out, const vectork *lhs, const vectork *rhs) { … } static void vectork_mult_scalar(vectork *out, const vectork *lhs, const scalar *rhs) { … } static void vectork_ntt(vectork *a) { … } static void vectork_inverse_ntt(vectork *a) { … } static void vectorl_add(vectorl *out, const vectorl *lhs, const vectorl *rhs) { … } static void vectorl_mult_scalar(vectorl *out, const vectorl *lhs, const scalar *rhs) { … } static void vectorl_ntt(vectorl *a) { … } static void vectorl_inverse_ntt(vectorl *a) { … } static void matrix_mult(vectork *out, const matrix *m, const vectorl *a) { … } /* Rounding & hints */ // FIPS 204, Algorithm 29 (`Power2Round`). static void power2_round(uint32_t *r1, uint32_t *r0, uint32_t r) { … } // Scale back previously rounded value. static void scale_power2_round(uint32_t *out, uint32_t r1) { … } // FIPS 204, Algorithm 31 (`HighBits`). static uint32_t high_bits(uint32_t x) { … } // FIPS 204, Algorithm 30 (`Decompose`). static void decompose(uint32_t *r1, int32_t *r0, uint32_t r) { … } // FIPS 204, Algorithm 32 (`LowBits`). static int32_t low_bits(uint32_t x) { … } // FIPS 204, Algorithm 33 (`MakeHint`). static int32_t make_hint(uint32_t ct0, uint32_t cs2, uint32_t w) { … } // FIPS 204, Algorithm 34 (`UseHint`). static uint32_t use_hint_vartime(uint32_t h, uint32_t r) { … } static void scalar_power2_round(scalar *s1, scalar *s0, const scalar *s) { … } static void scalar_scale_power2_round(scalar *out, const scalar *in) { … } static void scalar_high_bits(scalar *out, const scalar *in) { … } static void scalar_low_bits(scalar *out, const scalar *in) { … } static void scalar_max(uint32_t *max, const scalar *s) { … } static void scalar_max_signed(uint32_t *max, const scalar *s) { … } static void scalar_make_hint(scalar *out, const scalar *ct0, const scalar *cs2, const scalar *w) { … } static void scalar_use_hint_vartime(scalar *out, const scalar *h, const scalar *r) { … } static void vectork_power2_round(vectork *t1, vectork *t0, const vectork *t) { … } static void vectork_scale_power2_round(vectork *out, const vectork *in) { … } static void vectork_high_bits(vectork *out, const vectork *in) { … } static void vectork_low_bits(vectork *out, const vectork *in) { … } static uint32_t vectork_max(const vectork *a) { … } static uint32_t vectork_max_signed(const vectork *a) { … } // The input vector contains only zeroes and ones. static size_t vectork_count_ones(const vectork *a) { … } static void vectork_make_hint(vectork *out, const vectork *ct0, const vectork *cs2, const vectork *w) { … } static void vectork_use_hint_vartime(vectork *out, const vectork *h, const vectork *r) { … } static uint32_t vectorl_max(const vectorl *a) { … } /* Bit packing */ static const uint8_t kMasks[8] = …; // FIPS 204, Algorithm 10 (`SimpleBitPack`). static void scalar_encode(uint8_t *out, const scalar *s, int bits) { … } // FIPS 204, Algorithm 11 (`BitPack`). static void scalar_encode_signed(uint8_t *out, const scalar *s, int bits, uint32_t max) { … } // FIPS 204, Algorithm 12 (`SimpleBitUnpack`). static void scalar_decode(scalar *out, const uint8_t *in, int bits) { … } // FIPS 204, Algorithm 13 (`BitUnpack`). static int scalar_decode_signed(scalar *out, const uint8_t *in, int bits, uint32_t max) { … } /* Expansion functions */ // FIPS 204, Algorithm 24 (`RejNTTPoly`). // // Rejection samples a Keccak stream to get uniformly distributed elements. This // is used for matrix expansion and only operates on public inputs. static void scalar_from_keccak_vartime( scalar *out, const uint8_t derived_seed[RHO_BYTES + 2]) { … } // FIPS 204, Algorithm 25 (`RejBoundedPoly`). static void scalar_uniform_eta_4(scalar *out, const uint8_t derived_seed[SIGMA_BYTES + 2]) { … } // FIPS 204, Algorithm 28 (`ExpandMask`). static void scalar_sample_mask( scalar *out, const uint8_t derived_seed[RHO_PRIME_BYTES + 2]) { … } // FIPS 204, Algorithm 23 (`SampleInBall`). static void scalar_sample_in_ball_vartime(scalar *out, const uint8_t *seed, int len) { … } // FIPS 204, Algorithm 26 (`ExpandA`). static void matrix_expand(matrix *out, const uint8_t rho[RHO_BYTES]) { … } // FIPS 204, Algorithm 27 (`ExpandS`). static void vector_expand_short(vectorl *s1, vectork *s2, const uint8_t sigma[SIGMA_BYTES]) { … } // FIPS 204, Algorithm 28 (`ExpandMask`). static void vectorl_expand_mask(vectorl *out, const uint8_t seed[RHO_PRIME_BYTES], size_t kappa) { … } /* Encoding */ // FIPS 204, Algorithm 10 (`SimpleBitPack`). // // Encodes an entire vector into 32*K*|bits| bytes. Note that since 256 (DEGREE) // is divisible by 8, the individual vector entries will always fill a whole // number of bytes, so we do not need to worry about bit packing here. static void vectork_encode(uint8_t *out, const vectork *a, int bits) { … } // FIPS 204, Algorithm 12 (`SimpleBitUnpack`). static void vectork_decode(vectork *out, const uint8_t *in, int bits) { … } static void vectork_encode_signed(uint8_t *out, const vectork *a, int bits, uint32_t max) { … } static int vectork_decode_signed(vectork *out, const uint8_t *in, int bits, uint32_t max) { … } // FIPS 204, Algorithm 11 (`BitPack`). // // Encodes an entire vector into 32*L*|bits| bytes. Note that since 256 (DEGREE) // is divisible by 8, the individual vector entries will always fill a whole // number of bytes, so we do not need to worry about bit packing here. static void vectorl_encode_signed(uint8_t *out, const vectorl *a, int bits, uint32_t max) { … } static int vectorl_decode_signed(vectorl *out, const uint8_t *in, int bits, uint32_t max) { … } // FIPS 204, Algorithm 22 (`w1Encode`). // // The output must point to an array of 128*K bytes. static void w1_encode(uint8_t *out, const vectork *w1) { … } // FIPS 204, Algorithm 14 (`HintBitPack`). static void hint_bit_pack(uint8_t *out, const vectork *h) { … } // FIPS 204, Algorithm 15 (`HintBitUnpack`). static int hint_bit_unpack(vectork *h, const uint8_t *in) { … } struct public_key { … }; struct private_key { … }; struct signature { … }; // FIPS 204, Algorithm 16 (`pkEncode`). static int dilithium_marshal_public_key(CBB *out, const struct public_key *pub) { … } // FIPS 204, Algorithm 17 (`pkDecode`). static int dilithium_parse_public_key(struct public_key *pub, CBS *in) { … } // FIPS 204, Algorithm 18 (`skEncode`). static int dilithium_marshal_private_key(CBB *out, const struct private_key *priv) { … } // FIPS 204, Algorithm 19 (`skDecode`). static int dilithium_parse_private_key(struct private_key *priv, CBS *in) { … } // FIPS 204, Algorithm 20 (`sigEncode`). static int dilithium_marshal_signature(CBB *out, const struct signature *sign) { … } // FIPS 204, Algorithm 21 (`sigDecode`). static int dilithium_parse_signature(struct signature *sign, CBS *in) { … } static struct private_key *private_key_from_external( const struct DILITHIUM_private_key *external) { … } static struct public_key *public_key_from_external( const struct DILITHIUM_public_key *external) { … } /* API */ // Calls |DILITHIUM_generate_key_external_entropy| with random bytes from // |RAND_bytes|. Returns 1 on success and 0 on failure. int DILITHIUM_generate_key( uint8_t out_encoded_public_key[DILITHIUM_PUBLIC_KEY_BYTES], struct DILITHIUM_private_key *out_private_key) { … } // FIPS 204, Algorithm 1 (`ML-DSA.KeyGen`). Returns 1 on success and 0 on // failure. int DILITHIUM_generate_key_external_entropy( uint8_t out_encoded_public_key[DILITHIUM_PUBLIC_KEY_BYTES], struct DILITHIUM_private_key *out_private_key, const uint8_t entropy[DILITHIUM_GENERATE_KEY_ENTROPY]) { … } int DILITHIUM_public_from_private( struct DILITHIUM_public_key *out_public_key, const struct DILITHIUM_private_key *private_key) { … } // FIPS 204, Algorithm 2 (`ML-DSA.Sign`). Returns 1 on success and 0 on failure. static int dilithium_sign_with_randomizer( uint8_t out_encoded_signature[DILITHIUM_SIGNATURE_BYTES], const struct DILITHIUM_private_key *private_key, const uint8_t *msg, size_t msg_len, const uint8_t randomizer[DILITHIUM_SIGNATURE_RANDOMIZER_BYTES]) { … } // Dilithium signature in deterministic mode. Returns 1 on success and 0 on // failure. int DILITHIUM_sign_deterministic( uint8_t out_encoded_signature[DILITHIUM_SIGNATURE_BYTES], const struct DILITHIUM_private_key *private_key, const uint8_t *msg, size_t msg_len) { … } // Dilithium signature in randomized mode, filling the random bytes with // |RAND_bytes|. Returns 1 on success and 0 on failure. int DILITHIUM_sign(uint8_t out_encoded_signature[DILITHIUM_SIGNATURE_BYTES], const struct DILITHIUM_private_key *private_key, const uint8_t *msg, size_t msg_len) { … } // FIPS 204, Algorithm 3 (`ML-DSA.Verify`). int DILITHIUM_verify(const struct DILITHIUM_public_key *public_key, const uint8_t encoded_signature[DILITHIUM_SIGNATURE_BYTES], const uint8_t *msg, size_t msg_len) { … } /* Serialization of keys. */ int DILITHIUM_marshal_public_key( CBB *out, const struct DILITHIUM_public_key *public_key) { … } int DILITHIUM_parse_public_key(struct DILITHIUM_public_key *public_key, CBS *in) { … } int DILITHIUM_marshal_private_key( CBB *out, const struct DILITHIUM_private_key *private_key) { … } int DILITHIUM_parse_private_key(struct DILITHIUM_private_key *private_key, CBS *in) { … }
Codebase Browser
chromium