1 files changed, 87 insertions, 0 deletions
diff --git a/src/fuzzer/invert.cpp b/src/fuzzer/invert.cpp
new file mode 100644
index 000000000..08e8229b8
--- /dev/null
+++ b/src/fuzzer/invert.cpp
@@ -0,0 +1,87 @@
+/*
+* (C) 2015,2016 Jack Lloyd
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+#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);
+
+   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);
+   //Botan::BigInt mon = Botan::normalized_montgomery_inverse(x, mod);
+
+   if(ref != ct)
+      {
+      std::cout << "X = " << x << "\n";
+      std::cout << "P = " << mod << "\n";
+      std::cout << "GCD = " << gcd(x, mod) << "\n";
+      std::cout << "Ref = " << ref << "\n";
+      std::cout << "CT  = " << ct << "\n";
+      //std::cout << "Mon = " << mon << "\n";
+
+      std::cout << "RefCheck = " << (ref*ref)%mod << "\n";
+      std::cout << "CTCheck  = " << (ct*ct)%mod << "\n";
+      //std::cout << "MonCheck = " << (mon*mon)%mod << "\n";
+      abort();
+      }
+   }
+