/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 | 857 | { |
13 | 857 | if(n == 0 || mod < 2) |
14 | 2 | return 0; |
15 | 855 | if(n.is_even() && mod.is_even()) |
16 | 5 | return 0; |
17 | 850 | Botan::BigInt u = mod, v = n; |
18 | 850 | Botan::BigInt A = 1, B = 0, C = 0, D = 1; |
19 | 850 | |
20 | 409k | while(u.is_nonzero()) |
21 | 408k | { |
22 | 408k | const size_t u_zero_bits = Botan::low_zero_bits(u); |
23 | 408k | u >>= u_zero_bits; |
24 | 994k | for(size_t i = 0; i != u_zero_bits; ++i) |
25 | 585k | { |
26 | 585k | if(A.is_odd() || B.is_odd()) |
27 | 266k | { A += n; B -= mod; } |
28 | 585k | A >>= 1; B >>= 1; |
29 | 585k | } |
30 | 408k | |
31 | 408k | const size_t v_zero_bits = Botan::low_zero_bits(v); |
32 | 408k | v >>= v_zero_bits; |
33 | 987k | for(size_t i = 0; i != v_zero_bits; ++i) |
34 | 578k | { |
35 | 578k | if(C.is_odd() || D.is_odd()) |
36 | 275k | { C += n; D -= mod; } |
37 | 578k | C >>= 1; D >>= 1; |
38 | 578k | } |
39 | 408k | |
40 | 408k | if(u >= v) { u -= v; A -= C; B -= D; } |
41 | 277k | else { v -= u; C -= A; D -= B; } |
42 | 408k | } |
43 | 850 | |
44 | 850 | if(v != 1) |
45 | 142 | return 0; // no modular inverse |
46 | 708 | |
47 | 1.45k | while(D.is_negative()) D += mod; |
48 | 922 | while(D >= mod) D -= mod; |
49 | 708 | |
50 | 708 | return D; |
51 | 708 | } |
52 | | |
53 | | } |
54 | | |
55 | | void fuzz(const uint8_t in[], size_t len) |
56 | 877 | { |
57 | 877 | static const size_t max_bits = 4096; |
58 | 877 | |
59 | 877 | if(len > 2*max_bits/8) |
60 | 17 | return; |
61 | 860 | |
62 | 860 | const Botan::BigInt x = Botan::BigInt::decode(in, len / 2); |
63 | 860 | Botan::BigInt mod = Botan::BigInt::decode(in + len / 2, len - len / 2); |
64 | 860 | |
65 | 860 | if(mod < 2) |
66 | 3 | return; |
67 | 857 | |
68 | 857 | const Botan::BigInt lib = Botan::inverse_mod(x, mod); |
69 | 857 | const Botan::BigInt ref = ref_inverse_mod(x, mod); |
70 | 857 | |
71 | 857 | 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 | 857 | } |
82 | | |