Botan 3.14.1
Crypto and TLS for C&
kyber_helpers.h
Go to the documentation of this file.
1/*
2 * Crystals Kyber Internal Helpers
3 *
4 * Further changes
5 * (C) 2024 Jack Lloyd
6 * (C) 2024 René Meusel, Rohde & Schwarz Cybersecurity
7 *
8 * Botan is released under the Simplified BSD License (see license.txt)
9 */
10
11#ifndef BOTAN_KYBER_HELPERS_H_
12#define BOTAN_KYBER_HELPERS_H_
13
14#include <botan/internal/ct_utils.h>
15#include <botan/internal/kyber_constants.h>
16#include <botan/internal/loadstor.h>
17
18namespace Botan::Kyber_Algos {
19
20/**
21 * Special load_le<> that takes 3 bytes and returns a 32-bit integer.
22 */
23inline uint32_t load_le3(std::span<const uint8_t, 3> in) {
24 return Botan::load_le(std::array<uint8_t, 4>{in[0], in[1], in[2], 0});
25}
26
27/**
28 * NIST FIPS 203, Formula 4.7 (Compress)
29 */
30template <size_t d>
31 requires(d > 0 && d < 12)
32constexpr std::make_unsigned_t<KyberConstants::T> compress(KyberConstants::T x) {
34 const uint32_t n = (static_cast<uint32_t>(x) << d) + KyberConstants::Q / 2;
35
36 // This is a mitigation for a potential side channel called "KyberSlash".
37 //
38 // It implements the division by Q using a multiplication and a shift. Most
39 // compilers would generate similar code for such a division by a constant.
40 // Though, in some cases, compilers might use a variable-time int division,
41 // resulting in a potential side channel.
42 //
43 // The constants below work for all values that appear in Kyber with the
44 // greatest being 3328 * 2^11 + Q // 2 = 6,817,408 < 2**23 = 8,388,608.
45 //
46 // See "Hacker's Delight" (Second Edition) by Henry S. Warren, Jr.
47 // Chapter 10-9 "Unsigned Division by Divisors >= 1"
48 BOTAN_DEBUG_ASSERT(n < (1 << 23));
49 static_assert(KyberConstants::Q == 3329);
50 using unsigned_T = std::make_unsigned_t<KyberConstants::T>;
51
52 constexpr uint64_t m = 2580335;
53 constexpr size_t p = 33;
54 constexpr unsigned_T mask = (1 << d) - 1;
55 return static_cast<unsigned_T>((n * m) >> p) & mask;
56}
57
58/**
59 * NIST FIPS 203, Formula 4.8 (Decompress)
60 */
61template <size_t d>
62 requires(d > 0 && d < 12)
63constexpr KyberConstants::T decompress(std::make_unsigned_t<KyberConstants::T> x) {
64 BOTAN_DEBUG_ASSERT(x >= 0 && x < (1 << d));
65
66 constexpr uint32_t offset = 1 << (d - 1);
67 constexpr uint32_t mask = (1 << d) - 1;
68
69 const uint32_t xq = CT::value_barrier(static_cast<uint32_t>(x) & mask) * KyberConstants::Q;
70 return static_cast<KyberConstants::T>((xq + offset) >> d);
71}
72
73} // namespace Botan::Kyber_Algos
74
75#endif
#define BOTAN_DEBUG_ASSERT(expr)
Definition assert.h:136
static constexpr T Q
modulus
int16_t T
base data type for most calculations
constexpr T value_barrier(T x)
constexpr std::make_unsigned_t< KyberConstants::T > compress(KyberConstants::T x)
constexpr KyberConstants::T decompress(std::make_unsigned_t< KyberConstants::T > x)
uint32_t load_le3(std::span< const uint8_t, 3 > in)
constexpr auto load_le(ParamTs &&... params)
Definition loadstor.h:495