aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/cli/speed.cpp4
-rw-r--r--src/lib/ffi/ffi_mp.cpp2
-rw-r--r--src/lib/math/bigint/big_ops3.cpp39
-rw-r--r--src/lib/math/bigint/bigint.h1
-rw-r--r--src/lib/math/bigint/divide.cpp2
-rw-r--r--src/lib/math/bigint/divide.h16
-rw-r--r--src/lib/math/numbertheory/monty.h1
-rw-r--r--src/lib/math/numbertheory/numthry.h59
-rw-r--r--src/lib/math/numbertheory/ressol.cpp16
-rw-r--r--src/lib/pubkey/dl_group/dl_group.cpp6
-rw-r--r--src/lib/utils/compiler.h17
11 files changed, 103 insertions, 60 deletions
diff --git a/src/cli/speed.cpp b/src/cli/speed.cpp
index 0ef453311..b8454d2a7 100644
--- a/src/cli/speed.cpp
+++ b/src/cli/speed.cpp
@@ -1356,7 +1356,7 @@ class Speed final : public Command
y.randomize(rng(), q_bits);
div_timer->start();
- Botan::divide(x, y, q1, r1);
+ Botan::vartime_divide(x, y, q1, r1);
div_timer->stop();
ct_div_timer->start();
@@ -1395,7 +1395,7 @@ class Speed final : public Command
x.randomize(rng(), n_bits);
div_timer->start();
- Botan::divide(x, ten, q1, r1);
+ Botan::vartime_divide(x, ten, q1, r1);
div_timer->stop();
ct_div_timer->start();
diff --git a/src/lib/ffi/ffi_mp.cpp b/src/lib/ffi/ffi_mp.cpp
index 513dbbb0c..68869e6ec 100644
--- a/src/lib/ffi/ffi_mp.cpp
+++ b/src/lib/ffi/ffi_mp.cpp
@@ -192,7 +192,7 @@ int botan_mp_div(botan_mp_t quotient,
{
return BOTAN_FFI_DO(Botan::BigInt, quotient, q, {
Botan::BigInt r;
- Botan::divide(safe_get(x), safe_get(y), q, r);
+ Botan::vartime_divide(safe_get(x), safe_get(y), q, r);
safe_get(remainder) = r;
});
}
diff --git a/src/lib/math/bigint/big_ops3.cpp b/src/lib/math/bigint/big_ops3.cpp
index 30b27c87b..11804762b 100644
--- a/src/lib/math/bigint/big_ops3.cpp
+++ b/src/lib/math/bigint/big_ops3.cpp
@@ -91,11 +91,37 @@ BigInt operator*(const BigInt& x, word y)
*/
BigInt operator/(const BigInt& x, const BigInt& y)
{
- if(y.sig_words() == 1 && is_power_of_2(y.word_at(0)))
- return (x >> (y.bits() - 1));
+ if(y.sig_words() == 1)
+ {
+ return x / y.word_at(0);
+ }
BigInt q, r;
- divide(x, y, q, r);
+ vartime_divide(x, y, q, r);
+ return q;
+ }
+
+/*
+* Division Operator
+*/
+BigInt operator/(const BigInt& x, word y)
+ {
+ if(y == 0)
+ throw BigInt::DivideByZero();
+ else if(y == 1)
+ return x;
+ else if(y == 2)
+ return (x >> 1);
+ else if(y <= 255)
+ {
+ BigInt q;
+ uint8_t r;
+ ct_divide_u8(x, static_cast<uint8_t>(y), q, r);
+ return q;
+ }
+
+ BigInt q, r;
+ vartime_divide(x, y, q, r);
return q;
}
@@ -111,8 +137,13 @@ BigInt operator%(const BigInt& n, const BigInt& mod)
if(n.is_positive() && mod.is_positive() && n < mod)
return n;
+ if(mod.sig_words() == 1)
+ {
+ return n % mod.word_at(0);
+ }
+
BigInt q, r;
- divide(n, mod, q, r);
+ vartime_divide(n, mod, q, r);
return r;
}
diff --git a/src/lib/math/bigint/bigint.h b/src/lib/math/bigint/bigint.h
index d04ac045c..33e79d012 100644
--- a/src/lib/math/bigint/bigint.h
+++ b/src/lib/math/bigint/bigint.h
@@ -1097,6 +1097,7 @@ BigInt BOTAN_PUBLIC_API(2,8) operator*(const BigInt& x, word y);
inline BigInt operator*(word x, const BigInt& y) { return y*x; }
BigInt BOTAN_PUBLIC_API(2,0) operator/(const BigInt& x, const BigInt& d);
+BigInt BOTAN_PUBLIC_API(2,0) operator/(const BigInt& x, word m);
BigInt BOTAN_PUBLIC_API(2,0) operator%(const BigInt& x, const BigInt& m);
word BOTAN_PUBLIC_API(2,0) operator%(const BigInt& x, word m);
BigInt BOTAN_PUBLIC_API(2,0) operator<<(const BigInt& x, size_t n);
diff --git a/src/lib/math/bigint/divide.cpp b/src/lib/math/bigint/divide.cpp
index fdb920241..0b23e2489 100644
--- a/src/lib/math/bigint/divide.cpp
+++ b/src/lib/math/bigint/divide.cpp
@@ -156,7 +156,7 @@ BigInt ct_modulo(const BigInt& x, const BigInt& y)
*
* See Handbook of Applied Cryptography section 14.2.5
*/
-void divide(const BigInt& x, const BigInt& y_arg, BigInt& q_out, BigInt& r_out)
+void vartime_divide(const BigInt& x, const BigInt& y_arg, BigInt& q_out, BigInt& r_out)
{
if(y_arg.is_zero())
throw BigInt::DivideByZero();
diff --git a/src/lib/math/bigint/divide.h b/src/lib/math/bigint/divide.h
index deb6ffdbb..47141b3e7 100644
--- a/src/lib/math/bigint/divide.h
+++ b/src/lib/math/bigint/divide.h
@@ -21,10 +21,10 @@ namespace Botan {
* @param q will be set to x / y
* @param r will be set to x % y
*/
-void BOTAN_PUBLIC_API(2,0) divide(const BigInt& x,
- const BigInt& y,
- BigInt& q,
- BigInt& r);
+void BOTAN_UNSTABLE_API vartime_divide(const BigInt& x,
+ const BigInt& y,
+ BigInt& q,
+ BigInt& r);
/**
* BigInt division, const time variant
@@ -42,6 +42,14 @@ void BOTAN_PUBLIC_API(2,9) ct_divide(const BigInt& x,
BigInt& q,
BigInt& r);
+inline void divide(const BigInt& x,
+ const BigInt& y,
+ BigInt& q,
+ BigInt& r)
+ {
+ ct_divide(x, y, q, r);
+ }
+
/**
* BigInt division, const time variant
*
diff --git a/src/lib/math/numbertheory/monty.h b/src/lib/math/numbertheory/monty.h
index e5ab2f9ad..8e0cd342f 100644
--- a/src/lib/math/numbertheory/monty.h
+++ b/src/lib/math/numbertheory/monty.h
@@ -8,6 +8,7 @@
#define BOTAN_MONTY_INT_H_
#include <botan/bigint.h>
+BOTAN_FUTURE_INTERNAL_HEADER(monty.h)
namespace Botan {
diff --git a/src/lib/math/numbertheory/numthry.h b/src/lib/math/numbertheory/numthry.h
index b7f87ee05..be9cd985e 100644
--- a/src/lib/math/numbertheory/numthry.h
+++ b/src/lib/math/numbertheory/numthry.h
@@ -21,9 +21,10 @@ class RandomNumberGenerator;
* @param c an integer
* @return (a*b)+c
*/
-BigInt BOTAN_PUBLIC_API(2,0) mul_add(const BigInt& a,
- const BigInt& b,
- const BigInt& c);
+BigInt BOTAN_PUBLIC_API(2,0) BOTAN_DEPRECATED("Just use (a*b)+c")
+ mul_add(const BigInt& a,
+ const BigInt& b,
+ const BigInt& c);
/**
* Fused subtract-multiply
@@ -32,9 +33,10 @@ BigInt BOTAN_PUBLIC_API(2,0) mul_add(const BigInt& a,
* @param c an integer
* @return (a-b)*c
*/
-BigInt BOTAN_PUBLIC_API(2,0) sub_mul(const BigInt& a,
- const BigInt& b,
- const BigInt& c);
+BigInt BOTAN_PUBLIC_API(2,0) BOTAN_DEPRECATED("Just use (a-b)*c")
+ sub_mul(const BigInt& a,
+ const BigInt& b,
+ const BigInt& c);
/**
* Fused multiply-subtract
@@ -43,9 +45,10 @@ BigInt BOTAN_PUBLIC_API(2,0) sub_mul(const BigInt& a,
* @param c an integer
* @return (a*b)-c
*/
-BigInt BOTAN_PUBLIC_API(2,0) mul_sub(const BigInt& a,
- const BigInt& b,
- const BigInt& c);
+BigInt BOTAN_PUBLIC_API(2,0) BOTAN_DEPRECATED("Just use (a*b)-c")
+ mul_sub(const BigInt& a,
+ const BigInt& b,
+ const BigInt& c);
/**
* Return the absolute value
@@ -109,14 +112,16 @@ BigInt BOTAN_DEPRECATED_API("Use inverse_mod") ct_inverse_mod_odd_modulus(const
* Returns k, between n and 2n
* Not const time
*/
-size_t BOTAN_PUBLIC_API(2,0) almost_montgomery_inverse(BigInt& result,
- const BigInt& a,
- const BigInt& b);
+size_t BOTAN_PUBLIC_API(2,0) BOTAN_DEPRECATED("Use inverse_mod")
+ almost_montgomery_inverse(BigInt& result,
+ const BigInt& a,
+ const BigInt& b);
/**
* Call almost_montgomery_inverse and correct the result to a^-1 mod b
*/
-BigInt BOTAN_PUBLIC_API(2,0) normalized_montgomery_inverse(const BigInt& a, const BigInt& b);
+BigInt BOTAN_PUBLIC_API(2,0) BOTAN_DEPRECATED("Use inverse_mod")
+ normalized_montgomery_inverse(const BigInt& a, const BigInt& b);
/**
@@ -143,7 +148,7 @@ BigInt BOTAN_PUBLIC_API(2,0) power_mod(const BigInt& b,
/**
* Compute the square root of x modulo a prime using the
-* Shanks-Tonnelli algorithm
+* Tonelli-Shanks algorithm
*
* @param x the input
* @param p the prime
@@ -156,13 +161,14 @@ BigInt BOTAN_PUBLIC_API(2,0) ressol(const BigInt& x, const BigInt& p);
* is even. If input is odd, then input and 2^n are relatively prime
* and an inverse exists.
*/
-word BOTAN_PUBLIC_API(2,0) monty_inverse(word input);
+word BOTAN_PUBLIC_API(2,0) BOTAN_DEPRECATED("Use inverse_mod")
+ monty_inverse(word input);
/**
-* @param x a positive integer
-* @return count of the zero bits in x, or, equivalently, the largest
-* value of n such that 2^n divides x evenly. Returns zero if
-* n is less than or equal to zero.
+* @param x an integer
+* @return count of the low zero bits in x, or, equivalently, the
+* largest value of n such that 2^n divides x evenly. Returns
+* zero if x is equal to zero.
*/
size_t BOTAN_PUBLIC_API(2,0) low_zero_bits(const BigInt& x);
@@ -188,13 +194,16 @@ bool BOTAN_PUBLIC_API(2,0) is_prime(const BigInt& n,
*/
BigInt BOTAN_PUBLIC_API(2,8) is_perfect_square(const BigInt& x);
-inline bool quick_check_prime(const BigInt& n, RandomNumberGenerator& rng)
+inline bool BOTAN_DEPRECATED("Use is_prime")
+ quick_check_prime(const BigInt& n, RandomNumberGenerator& rng)
{ return is_prime(n, rng, 32); }
-inline bool check_prime(const BigInt& n, RandomNumberGenerator& rng)
+inline bool BOTAN_DEPRECATED("Use is_prime")
+ check_prime(const BigInt& n, RandomNumberGenerator& rng)
{ return is_prime(n, rng, 56); }
-inline bool verify_prime(const BigInt& n, RandomNumberGenerator& rng)
+inline bool BOTAN_DEPRECATED("Use is_prime")
+ verify_prime(const BigInt& n, RandomNumberGenerator& rng)
{ return is_prime(n, rng, 80); }
/**
@@ -248,7 +257,7 @@ BigInt BOTAN_PUBLIC_API(2,0) random_safe_prime(RandomNumberGenerator& rng,
* @param qbits how long q will be in bits
* @return random seed used to generate this parameter set
*/
-std::vector<uint8_t> BOTAN_PUBLIC_API(2,0)
+std::vector<uint8_t> BOTAN_PUBLIC_API(2,0) BOTAN_DEPRECATED("Use DL_Group")
generate_dsa_primes(RandomNumberGenerator& rng,
BigInt& p_out, BigInt& q_out,
size_t pbits, size_t qbits);
@@ -265,7 +274,7 @@ generate_dsa_primes(RandomNumberGenerator& rng,
* @return true if seed generated a valid DSA parameter set, otherwise
false. p_out and q_out are only valid if true was returned.
*/
-bool BOTAN_PUBLIC_API(2,0)
+bool BOTAN_PUBLIC_API(2,0) BOTAN_DEPRECATED("Use DL_Group")
generate_dsa_primes(RandomNumberGenerator& rng,
BigInt& p_out, BigInt& q_out,
size_t pbits, size_t qbits,
@@ -278,7 +287,7 @@ generate_dsa_primes(RandomNumberGenerator& rng,
const size_t PRIME_TABLE_SIZE = 6541;
/**
-* A const array of all primes less than 65535
+* A const array of all odd primes less than 65535
*/
extern const uint16_t BOTAN_PUBLIC_API(2,0) PRIMES[];
diff --git a/src/lib/math/numbertheory/ressol.cpp b/src/lib/math/numbertheory/ressol.cpp
index 9d11ebbc4..de89e0384 100644
--- a/src/lib/math/numbertheory/ressol.cpp
+++ b/src/lib/math/numbertheory/ressol.cpp
@@ -1,6 +1,5 @@
/*
-* Shanks-Tonnelli (RESSOL)
-* (C) 2007-2008 Falko Strenzke, FlexSecure GmbH
+* (C) 2007,2008 Falko Strenzke, FlexSecure GmbH
* (C) 2008 Jack Lloyd
*
* Botan is released under the Simplified BSD License (see license.txt)
@@ -12,10 +11,13 @@
namespace Botan {
/*
-* Shanks-Tonnelli algorithm
+* Tonelli-Shanks algorithm
*/
BigInt ressol(const BigInt& a, const BigInt& p)
{
+ if(p <= 1 || p.is_even())
+ throw Invalid_Argument("ressol: invalid prime");
+
if(a == 0)
return 0;
else if(a < 0)
@@ -25,16 +27,14 @@ BigInt ressol(const BigInt& a, const BigInt& p)
if(p == 2)
return a;
- else if(p <= 1)
- throw Invalid_Argument("ressol: prime must be > 1 a");
- else if(p.is_even())
- throw Invalid_Argument("ressol: invalid prime");
if(jacobi(a, p) != 1) // not a quadratic residue
return -BigInt(1);
- if(p % 4 == 3)
+ if(p % 4 == 3) // The easy case
+ {
return power_mod(a, ((p+1) >> 2), p);
+ }
size_t s = low_zero_bits(p - 1);
BigInt q = p >> s;
diff --git a/src/lib/pubkey/dl_group/dl_group.cpp b/src/lib/pubkey/dl_group/dl_group.cpp
index b6b5d5f44..05f9640e3 100644
--- a/src/lib/pubkey/dl_group/dl_group.cpp
+++ b/src/lib/pubkey/dl_group/dl_group.cpp
@@ -9,6 +9,7 @@
#include <botan/numthry.h>
#include <botan/reducer.h>
#include <botan/monty.h>
+#include <botan/divide.h>
#include <botan/der_enc.h>
#include <botan/ber_dec.h>
#include <botan/pem.h>
@@ -214,9 +215,10 @@ namespace {
*/
BigInt make_dsa_generator(const BigInt& p, const BigInt& q)
{
- const BigInt e = (p - 1) / q;
+ BigInt e, r;
+ vartime_divide(p - 1, q, e, r);
- if(e == 0 || (p - 1) % q > 0)
+ if(e == 0 || r > 0)
throw Invalid_Argument("make_dsa_generator q does not divide p-1");
for(size_t i = 0; i != PRIME_TABLE_SIZE; ++i)
diff --git a/src/lib/utils/compiler.h b/src/lib/utils/compiler.h
index 22bd07426..832ab8f22 100644
--- a/src/lib/utils/compiler.h
+++ b/src/lib/utils/compiler.h
@@ -103,32 +103,23 @@
/*
* Define BOTAN_DEPRECATED
*/
-#if !defined(BOTAN_NO_DEPRECATED_WARNINGS)
+#if !defined(BOTAN_NO_DEPRECATED_WARNINGS) && !defined(BOTAN_IS_BEING_BUILT) && !defined(BOTAN_AMALGAMATION_H_)
#if defined(__clang__)
#define BOTAN_DEPRECATED(msg) __attribute__ ((deprecated(msg)))
#define BOTAN_DEPRECATED_HEADER(hdr) _Pragma("message \"this header is deprecated\"")
-
- #if !defined(BOTAN_IS_BEING_BUILT) && !defined(BOTAN_AMALGAMATION_H_)
- #define BOTAN_FUTURE_INTERNAL_HEADER(hdr) _Pragma("message \"this header will be made internal in the future\"")
- #endif
+ #define BOTAN_FUTURE_INTERNAL_HEADER(hdr) _Pragma("message \"this header will be made internal in the future\"")
#elif defined(_MSC_VER)
#define BOTAN_DEPRECATED(msg) __declspec(deprecated(msg))
#define BOTAN_DEPRECATED_HEADER(hdr) __pragma(message("this header is deprecated"))
-
- #if !defined(BOTAN_IS_BEING_BUILT) && !defined(BOTAN_AMALGAMATION_H_)
- #define BOTAN_FUTURE_INTERNAL_HEADER(hdr) __pragma(message("this header will be made internal in the future"))
- #endif
+ #define BOTAN_FUTURE_INTERNAL_HEADER(hdr) __pragma(message("this header will be made internal in the future"))
#elif defined(__GNUC__)
/* msg supported since GCC 4.5, earliest we support is 4.8 */
#define BOTAN_DEPRECATED(msg) __attribute__ ((deprecated(msg)))
#define BOTAN_DEPRECATED_HEADER(hdr) _Pragma("GCC warning \"this header is deprecated\"")
-
- #if !defined(BOTAN_IS_BEING_BUILT) && !defined(BOTAN_AMALGAMATION_H_)
- #define BOTAN_FUTURE_INTERNAL_HEADER(hdr) _Pragma("GCC warning \"this header will be made internal in the future\"")
- #endif
+ #define BOTAN_FUTURE_INTERNAL_HEADER(hdr) _Pragma("GCC warning \"this header will be made internal in the future\"")
#endif
#endif
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-02 07:17:47 +0000