1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
/*
* (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;
}
}
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");
}
}
|
