Coverage Report

Created: 2022-06-23 06:44

/src/botan/src/fuzzer/invert.cpp
Line
Count
Source (jump to first uncovered line)
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
#include <botan/numthry.h>
8
9
namespace {
10
11
Botan::BigInt ref_inverse_mod(const Botan::BigInt& n, const Botan::BigInt& mod)
12
2.00k
   {
13
2.00k
   if(n == 0 || mod < 2)
14
15
      return 0;
15
1.98k
   if(n.is_even() && mod.is_even())
16
6
      return 0;
17
1.98k
   Botan::BigInt u = mod, v = n;
18
1.98k
   Botan::BigInt A = 1, B = 0, C = 0, D = 1;
19
20
537k
   while(u.is_nonzero())
21
535k
      {
22
535k
      const size_t u_zero_bits = Botan::low_zero_bits(u);
23
535k
      u >>= u_zero_bits;
24
1.31M
      for(size_t i = 0; i != u_zero_bits; ++i)
25
777k
         {
26
777k
         if(A.is_odd() || B.is_odd())
27
420k
            { A += n; B -= mod; }
28
777k
         A >>= 1; B >>= 1;
29
777k
         }
30
31
535k
      const size_t v_zero_bits = Botan::low_zero_bits(v);
32
535k
      v >>= v_zero_bits;
33
1.22M
      for(size_t i = 0; i != v_zero_bits; ++i)
34
689k
         {
35
689k
         if(C.is_odd() || D.is_odd())
36
309k
            { C += n; D -= mod; }
37
689k
         C >>= 1; D >>= 1;
38
689k
         }
39
40
535k
      if(u >= v) { u -= v; A -= C; B -= D; }
41
322k
      else       { v -= u; C -= A; D -= B; }
42
535k
      }
43
44
1.98k
   if(v != 1)
45
300
      return 0; // no modular inverse
46
47
3.16k
   while(D.is_negative()) D += mod;
48
3.09k
   while(D >= mod) D -= mod;
49
50
1.68k
   return D;
51
1.98k
   }
52
53
}
54
55
void fuzz(const uint8_t in[], size_t len)
56
2.02k
   {
57
2.02k
   static const size_t max_bits = 4096;
58
59
2.02k
   if(len > 2*max_bits/8)
60
17
      return;
61
62
2.00k
   const Botan::BigInt x = Botan::BigInt::decode(in, len / 2);
63
2.00k
   Botan::BigInt mod = Botan::BigInt::decode(in + len / 2, len - len / 2);
64
65
2.00k
   if(mod < 2)
66
2
      return;
67
68
2.00k
   const Botan::BigInt lib = Botan::inverse_mod(x, mod);
69
2.00k
   const Botan::BigInt ref = ref_inverse_mod(x, mod);
70
71
2.00k
   if(ref != lib)
72
0
      {
73
0
      FUZZER_WRITE_AND_CRASH("X = " << x << "\n"
74
0
                             << "Mod = " << mod << "\n"
75
0
                             << "GCD(X,Mod) = " << gcd(x, mod) << "\n"
76
0
                             << "RefInv(X,Mod) = " << ref << "\n"
77
0
                             << "LibInv(X,Mod)  = " << lib << "\n"
78
0
                             << "RefCheck = " << (x*ref)%mod << "\n"
79
0
                             << "LibCheck  = " << (x*lib)%mod << "\n");
80
0
      }
81
2.00k
   }
82