37879904758

Committed 09 Oct 2026 12:32AM UTC coverage: 92.188% (+2.3%) from 89.903%

Build # 37879904758

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #5964 from randombit/jack/ml-kem-avx2

Add AVX2 implementation of ML-KEM NTT, inverse NTT, and mul

Coverage Stats

134868 of 146297 relevant lines covered (92.19%)

8763146.96 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

94.64

/src/fuzzer/invert.cpp

/*
* (C) 2015,2016,2020 Jack Lloyd
*
* Botan is released under the Simplified BSD License (see license.txt)
*/
#include "fuzzers.h"

#include <botan/numthry.h>

namespace {

Botan::BigInt ref_inverse_mod(const Botan::BigInt& n, const Botan::BigInt& mod) {
   if(n == 0 || mod < 2) {
      return 0;
   }
   if(n.is_even() && mod.is_even()) {
      return 0;
   }
   Botan::BigInt u = mod;
   Botan::BigInt v = n;
   Botan::BigInt A = 1;
   Botan::BigInt B = 0;
   Botan::BigInt C = 0;
   Botan::BigInt D = 1;

   while(!u.is_zero()) {
      const size_t u_zero_bits = Botan::low_zero_bits(u);
      u >>= u_zero_bits;
      for(size_t i = 0; i != u_zero_bits; ++i) {
         if(A.is_odd() || B.is_odd()) {
            A += n;
            B -= mod;
         }
         A >>= 1;
         B >>= 1;
      }

      const size_t v_zero_bits = Botan::low_zero_bits(v);
      v >>= v_zero_bits;
      for(size_t i = 0; i != v_zero_bits; ++i) {
         if(C.is_odd() || D.is_odd()) {
            C += n;
            D -= mod;
         }
         C >>= 1;
         D >>= 1;
      }

      if(u >= v) {
         u -= v;
         A -= C;
         B -= D;
      } else {
         v -= u;
         C -= A;
         D -= B;
      }
   }

   if(v != 1) {
      return 0;  // no modular inverse
   }

   while(D.signum() < 0) {
      D += mod;
   }
   while(D >= mod) {
      D -= mod;
   }

   return D;
}

}  // namespace

void fuzz(std::span<const uint8_t> in) {
   static const size_t max_bits = 4096;

   if(in.size() > 2 * max_bits / 8) {
      return;
   }

   const Botan::BigInt x = Botan::BigInt::from_bytes(in.subspan(0, in.size() / 2));
   const Botan::BigInt mod = Botan::BigInt::from_bytes(in.subspan(in.size() / 2, in.size() - in.size() / 2));

   if(mod < 2) {
      return;
   }

   const Botan::BigInt lib = Botan::inverse_mod(x, mod);
   const Botan::BigInt ref = ref_inverse_mod(x, mod);

   if(ref != lib) {
      FUZZER_WRITE_AND_CRASH("X = " << x.to_hex_string() << "\n"
                                    << "Mod = " << mod.to_hex_string() << "\n"
                                    << "GCD(X,Mod) = " << gcd(x, mod).to_hex_string() << "\n"
                                    << "RefInv(X,Mod) = " << ref.to_hex_string() << "\n"
                                    << "LibInv(X,Mod)  = " << lib.to_hex_string() << "\n"
                                    << "RefCheck = " << ((x * ref) % mod).to_hex_string() << "\n"
                                    << "LibCheck  = " << ((x * lib) % mod).to_hex_string() << "\n");
   }
}

1	/*
2	* (C) 2015,2016,2020 Jack Lloyd
3	*
4	* Botan is released under the Simplified BSD License (see license.txt)
5	*/
6	#include "fuzzers.h"
7
8	#include <botan/numthry.h>
9
10	namespace {
11
12	Botan::BigInt ref_inverse_mod(const Botan::BigInt& n, const Botan::BigInt& mod) {	98 ✔
13	if(n == 0 \|\| mod < 2) {	196 ✔
14	return 0;	×
15	}
16	if(n.is_even() && mod.is_even()) {	246 ✔
17	return 0;	26 ✔
18	}
19	Botan::BigInt u = mod;	72 ✔
20	Botan::BigInt v = n;	72 ✔
21	Botan::BigInt A = 1;	72 ✔
22	Botan::BigInt B = 0;	72 ✔
23	Botan::BigInt C = 0;	72 ✔
24	Botan::BigInt D = 1;	72 ✔
25
26	while(!u.is_zero()) {	40,662 ✔
27	const size_t u_zero_bits = Botan::low_zero_bits(u);	26,975 ✔
28	u >>= u_zero_bits;	26,975 ✔
29	for(size_t i = 0; i != u_zero_bits; ++i) {	54,046 ✔
30	if(A.is_odd() \|\| B.is_odd()) {	27,071 ✔
31	A += n;	13,606 ✔
32	B -= mod;	13,606 ✔
33	}
34	A >>= 1;	27,071 ✔
35	B >>= 1;	27,071 ✔
36	}
37
38	const size_t v_zero_bits = Botan::low_zero_bits(v);	26,975 ✔
39	v >>= v_zero_bits;	26,975 ✔
40	for(size_t i = 0; i != v_zero_bits; ++i) {	53,700 ✔
41	if(C.is_odd() \|\| D.is_odd()) {	26,725 ✔
42	C += n;	13,456 ✔
43	D -= mod;	13,456 ✔
44	}
45	C >>= 1;	26,725 ✔
46	D >>= 1;	26,725 ✔
47	}
48
49	if(u >= v) {	26,975 ✔
50	u -= v;	13,615 ✔
51	A -= C;	13,615 ✔
52	B -= D;	13,615 ✔
53	} else {
54	v -= u;	13,360 ✔
55	C -= A;	13,360 ✔
56	D -= B;	13,360 ✔
57	}
58	}
59
60	if(v != 1) {	72 ✔
61	return 0; // no modular inverse	12 ✔
62	}
63
64	while(D.signum() < 0) {	109 ✔
65	D += mod;	49 ✔
66	}
67	while(D >= mod) {	60 ✔
68	D -= mod;	×
69	}
70
71	return D;	60 ✔
72	}	72 ✔
73
74	} // namespace
75
76	void fuzz(std::span<const uint8_t> in) {	100 ✔
77	static const size_t max_bits = 4096;	100 ✔
78
79	if(in.size() > 2 * max_bits / 8) {	100 ✔
80	return;	2 ✔
81	}
82
83	const Botan::BigInt x = Botan::BigInt::from_bytes(in.subspan(0, in.size() / 2));	100 ✔
84	const Botan::BigInt mod = Botan::BigInt::from_bytes(in.subspan(in.size() / 2, in.size() - in.size() / 2));	100 ✔
85
86	if(mod < 2) {	100 ✔
87	return;	2 ✔
88	}
89
90	const Botan::BigInt lib = Botan::inverse_mod(x, mod);	98 ✔
91	const Botan::BigInt ref = ref_inverse_mod(x, mod);	98 ✔
92
93	if(ref != lib) {	98 ✔
94	FUZZER_WRITE_AND_CRASH("X = " << x.to_hex_string() << "\n"	×
95	<< "Mod = " << mod.to_hex_string() << "\n"
96	<< "GCD(X,Mod) = " << gcd(x, mod).to_hex_string() << "\n"
97	<< "RefInv(X,Mod) = " << ref.to_hex_string() << "\n"
98	<< "LibInv(X,Mod) = " << lib.to_hex_string() << "\n"
99	<< "RefCheck = " << ((x * ref) % mod).to_hex_string() << "\n"
100	<< "LibCheck = " << ((x * lib) % mod).to_hex_string() << "\n");
101	}
102	}	100 ✔

randombit / botan / 37879904758

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous