aboutsummaryrefslogtreecommitdiffstats
path: root/src/fuzzer/invert.cpp
diff options
context:
space:
mode:
authorJack Lloyd <[email protected]>2018-03-01 10:30:47 -0500
committerJack Lloyd <[email protected]>2018-03-01 10:30:47 -0500
commit45eea5c4f3d5a582940cb488d660f3cb8ce189dc (patch)
tree40dbbb3a75d99882591d214c845a6b1333074039 /src/fuzzer/invert.cpp
parentb02b5aae2ae9f687c28af29014c12da9c37347a7 (diff)
Simplify modular inversion fuzzer
Now binary ext gcd algorithm has an exposed API so no need to duplicate the code here.
Diffstat (limited to 'src/fuzzer/invert.cpp')
-rw-r--r--src/fuzzer/invert.cpp56
1 files changed, 6 insertions, 50 deletions
diff --git a/src/fuzzer/invert.cpp b/src/fuzzer/invert.cpp
index dd91fe83f..81923b07e 100644
--- a/src/fuzzer/invert.cpp
+++ b/src/fuzzer/invert.cpp
@@ -6,67 +6,23 @@
#include "fuzzers.h"
#include <botan/numthry.h>
-namespace {
-
-Botan::BigInt inverse_mod_ref(const Botan::BigInt& n, const Botan::BigInt& mod)
- {
- if(n == 0)
- return 0;
-
- Botan::BigInt u = mod, v = n;
- Botan::BigInt B = 0, D = 1;
-
- while(u.is_nonzero())
- {
- const size_t u_zero_bits = low_zero_bits(u);
- u >>= u_zero_bits;
- for(size_t i = 0; i != u_zero_bits; ++i)
- {
- //B.cond_sub(B.is_odd(), mod);
- if(B.is_odd())
- { B -= mod; }
- B >>= 1;
- }
-
- const size_t v_zero_bits = low_zero_bits(v);
- v >>= v_zero_bits;
- for(size_t i = 0; i != v_zero_bits; ++i)
- {
- if(D.is_odd())
- { D -= mod; }
- D >>= 1;
- }
-
- if(u >= v) { u -= v; B -= D; }
- else { v -= u; 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)
{
if(len % 2 == 1 || len > 2*4096/8)
return;
- const Botan::BigInt x = Botan::BigInt::decode(in, len / 2);
- Botan::BigInt mod = Botan::BigInt::decode(in + len / 2, len / 2);
+ const size_t part_len = len / 2;
+
+ const Botan::BigInt x = Botan::BigInt::decode(in, part_len);
+ Botan::BigInt mod = Botan::BigInt::decode(in + part_len, part_len);
mod.set_bit(0);
if(mod < 3 || x >= mod)
return;
- Botan::BigInt ref = inverse_mod_ref(x, mod);
- Botan::BigInt ct = Botan::ct_inverse_mod_odd_modulus(x, mod);
+ const Botan::BigInt ref = Botan::inverse_euclid(x, mod);
+ const Botan::BigInt ct = Botan::ct_inverse_mod_odd_modulus(x, mod);
//Botan::BigInt mon = Botan::normalized_montgomery_inverse(x, mod);
if(ref != ct)