5164070227

Committed 03 Jun 2023 02:38PM UTC coverage: 91.742% (+0.003%) from 91.739%

Build # 5164070227

Build Type

push

github

Committed by

randombit

Commit Message

Merge GH #3574 In run_clang_format prioritize os_utils.cpp

Run Details

76193 of 83051 relevant lines covered (91.74%)

11792659.86 hits per line

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

96.15

/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, v = n;
   Botan::BigInt A = 1, B = 0, C = 0, D = 1;

   while(u.is_nonzero()) {
      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.is_negative())
      D += mod;
   while(D >= mod)
      D -= mod;

   return D;
}

}  // namespace

void fuzz(const uint8_t in[], size_t len) {
   static const size_t max_bits = 4096;

   if(len > 2 * max_bits / 8)
      return;

   const Botan::BigInt x = Botan::BigInt::decode(in, len / 2);
   Botan::BigInt mod = Botan::BigInt::decode(in + len / 2, len - len / 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 << "\n"
                                    << "Mod = " << mod << "\n"
                                    << "GCD(X,Mod) = " << gcd(x, mod) << "\n"
                                    << "RefInv(X,Mod) = " << ref << "\n"
                                    << "LibInv(X,Mod)  = " << lib << "\n"
                                    << "RefCheck = " << (x * ref) % mod << "\n"
                                    << "LibCheck  = " << (x * lib) % mod << "\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	if(n.is_even() && mod.is_even())	235✔
16	return 0;	19✔
17	Botan::BigInt u = mod, v = n;	79✔
18	Botan::BigInt A = 1, B = 0, C = 0, D = 1;	79✔
19
20	while(u.is_nonzero()) {	43,473✔
21	const size_t u_zero_bits = Botan::low_zero_bits(u);	28,919✔
22	u >>= u_zero_bits;	28,919✔
23	for(size_t i = 0; i != u_zero_bits; ++i) {	57,893✔
24	if(A.is_odd() \|\| B.is_odd()) {	76,149✔
25	A += n;	14,458✔
26	B -= mod;	14,458✔
27	}
28	A >>= 1;	28,974✔
29	B >>= 1;	28,974✔
30	}
31
32	const size_t v_zero_bits = Botan::low_zero_bits(v);	28,919✔
33	v >>= v_zero_bits;	28,919✔
34	for(size_t i = 0; i != v_zero_bits; ++i) {	57,548✔
35	if(C.is_odd() \|\| D.is_odd()) {	75,182✔
36	C += n;	14,351✔
37	D -= mod;	14,351✔
38	}
39	C >>= 1;	28,629✔
40	D >>= 1;	28,629✔
41	}
42
43	if(u >= v) {	28,919✔
44	u -= v;	14,475✔
45	A -= C;	14,475✔
46	B -= D;	14,475✔
47	} else {
48	v -= u;	14,444✔
49	C -= A;	14,444✔
50	D -= B;	14,444✔
51	}
52	}
53
54	if(v != 1)	79✔
55	return 0; // no modular inverse	13✔
56
57	while(D.is_negative())	123✔
58	D += mod;	57✔
59	while(D >= mod)	66✔
60	D -= mod;	×
61
62	return D;	79✔
63	}	493✔
64
65	} // namespace
66
67	void fuzz(const uint8_t in[], size_t len) {	100✔
68	static const size_t max_bits = 4096;	100✔
69
70	if(len > 2 * max_bits / 8)	100✔
71	return;	2✔
72
73	const Botan::BigInt x = Botan::BigInt::decode(in, len / 2);	100✔
74	Botan::BigInt mod = Botan::BigInt::decode(in + len / 2, len - len / 2);	100✔
75
76	if(mod < 2)	100✔
77	return;	2✔
78
79	const Botan::BigInt lib = Botan::inverse_mod(x, mod);	98✔
80	const Botan::BigInt ref = ref_inverse_mod(x, mod);	98✔
81
82	if(ref != lib) {	98✔
83	FUZZER_WRITE_AND_CRASH("X = " << x << "\n"	98✔
84	<< "Mod = " << mod << "\n"
85	<< "GCD(X,Mod) = " << gcd(x, mod) << "\n"
86	<< "RefInv(X,Mod) = " << ref << "\n"
87	<< "LibInv(X,Mod) = " << lib << "\n"
88	<< "RefCheck = " << (x * ref) % mod << "\n"
89	<< "LibCheck = " << (x * lib) % mod << "\n");
90	}
91	}	374✔

randombit / botan / 5164070227

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