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