Repository: randombit/botan
Pull request #3912 (2024-02-20 11:24:55)

Backport 3909


Patch:
diff --git a/src/lib/math/bigint/bigint.cpp b/src/lib/math/bigint/bigint.cpp
index 7bcbaf37f..f3cd8ec79 100644
--- a/src/lib/math/bigint/bigint.cpp
+++ b/src/lib/math/bigint/bigint.cpp
@@ -45,6 +45,14 @@ BigInt::BigInt(Sign s, size_t size)
    m_signedness = s;
    }
 
+//static
+BigInt BigInt::with_capacity(size_t size)
+   {
+   BigInt bn;
+   bn.grow_to(size);
+   return bn;
+   }
+
 /*
 * Construct a BigInt from a string
 */
@@ -472,6 +480,40 @@ void BigInt::ct_cond_swap(bool predicate, BigInt& other)
    bigint_cnd_swap(predicate, this->mutable_data(), other.mutable_data(), max_words);
    }
 
+void BigInt::ct_shift_left(size_t shift) {
+   auto shl_bit = [](const BigInt& a, BigInt& result) {
+      BOTAN_DEBUG_ASSERT(a.size() + 1 == result.size());
+      bigint_shl2(result.mutable_data(), a.data(), a.size(), 0, 1);
+      // shl2 may have shifted a bit into the next word, which must be dropped
+      clear_mem(result.mutable_data() + result.size() - 1, 1);
+   };
+
+   auto shl_word = [](const BigInt& a, BigInt& result) {
+      // the most significant word is not copied, aka. shifted out
+      bigint_shl2(result.mutable_data(), a.data(), a.size() - 1 /* ignore msw */, 1, 0);
+      // we left-shifted by a full word, the least significant word must be zero'ed
+      clear_mem(result.mutable_data(), 1);
+   };
+
+   BOTAN_ASSERT_NOMSG(size() > 0);
+
+   constexpr size_t bits_in_word = sizeof(word) * 8;
+   const size_t word_shift = shift >> ceil_log2(bits_in_word);             // shift / bits_in_word
+   const size_t bit_shift = shift & ((1 << ceil_log2(bits_in_word)) - 1);  // shift % bits_in_word
+   const size_t iterations = std::max(size(), bits_in_word) - 1;           // uint64_t i; i << 64 is undefined behaviour
+
+   // In every iteration, shift one bit and one word to the left and use the
+   // shift results only when they are within the shift range.
+   BigInt tmp;
+   tmp.resize(size() + 1 /* to hold the shifted-out word */);
+   for(size_t i = 0; i < iterations; ++i) {
+      shl_bit(*this, tmp);
+      ct_cond_assign(i < bit_shift, tmp);
+      shl_word(*this, tmp);
+      ct_cond_assign(i < word_shift, tmp);
+   }
+}
+
 void BigInt::cond_flip_sign(bool predicate)
    {
    // This code is assuming Negative == 0, Positive == 1
diff --git a/src/lib/math/bigint/bigint.h b/src/lib/math/bigint/bigint.h
index 33e79d012..0aa401de1 100644
--- a/src/lib/math/bigint/bigint.h
+++ b/src/lib/math/bigint/bigint.h
@@ -57,6 +57,12 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
      */
      BigInt(uint64_t n);
 
+     /**
+     * Create BigInt of specified size, all zeros
+     * @param n size of the internal register in words
+     */
+     static BigInt with_capacity(size_t n);
+
      /**
      * Copy Constructor
      * @param other the BigInt to copy
@@ -727,6 +733,12 @@ class BOTAN_PUBLIC_API(2,0) BigInt final
      */
      void ct_cond_add(bool predicate, const BigInt& value);
 
+     /**
+     * Shift @p shift bits to the left, runtime is independent of
+     * the value of @p shift.
+     */
+     void ct_shift_left(size_t shift);
+
      /**
      * If predicate is true flip the sign of *this
      */
diff --git a/src/lib/math/numbertheory/numthry.cpp b/src/lib/math/numbertheory/numthry.cpp
index 51afa94c6..00049b714 100644
--- a/src/lib/math/numbertheory/numthry.cpp
+++ b/src/lib/math/numbertheory/numthry.cpp
@@ -18,21 +18,6 @@
 
 namespace Botan {
 
-namespace {
-
-void sub_abs(BigInt& z, const BigInt& x, const BigInt& y)
-   {
-   const size_t x_sw = x.sig_words();
-   const size_t y_sw = y.sig_words();
-   z.resize(std::max(x_sw, y_sw));
-
-   bigint_sub_abs(z.mutable_data(),
-                  x.data(), x_sw,
-                  y.data(), y_sw);
-   }
-
-}
-
 /*
 * Return the number of 0 bits at the end of n
 */
@@ -61,22 +46,8 @@ size_t low_zero_bits(const BigInt& n)
    return seen_nonempty_word.if_set_return(low_zero);
    }
 
-namespace {
-
-size_t safegcd_loop_bound(size_t f_bits, size_t g_bits)
-   {
-   const size_t d = std::max(f_bits, g_bits);
-
-   if(d < 46)
-      return (49*d + 80) / 17;
-   else
-      return (49*d + 57) / 17;
-   }
-
-}
-
 /*
-* Calculate the GCD
+* Calculate the GCD in constant time
 */
 BigInt gcd(const BigInt& a, const BigInt& b)
    {
@@ -84,58 +55,77 @@ BigInt gcd(const BigInt& a, const BigInt& b)
       return abs(b);
    if(b.is_zero())
       return abs(a);
+
    if(a == 1 || b == 1)
       return 1;
 
-   // See https://gcd.cr.yp.to/safegcd-20190413.pdf fig 1.2
-
-   BigInt f = a;
-   BigInt g = b;
-   f.const_time_poison();
-   g.const_time_poison();
-
-   f.set_sign(BigInt::Positive);
-   g.set_sign(BigInt::Positive);
-
-   const size_t common2s = std::min(low_zero_bits(f), low_zero_bits(g));
-   CT::unpoison(common2s);
-
-   f >>= common2s;
-   g >>= common2s;
-
-   f.ct_cond_swap(f.is_even(), g);
-
-   int32_t delta = 1;
-
-   const size_t loop_cnt = safegcd_loop_bound(f.bits(), g.bits());
-
-   BigInt newg, t;
-   for(size_t i = 0; i != loop_cnt; ++i)
-      {
-      sub_abs(newg, f, g);
-
-      const bool need_swap = (g.is_odd() && delta > 0);
-
-      // if(need_swap) { delta *= -1 } else { delta *= 1 }
-      delta *= CT::Mask<uint8_t>::expand(need_swap).if_not_set_return(2) - 1;
-      f.ct_cond_swap(need_swap, g);
-      g.ct_cond_swap(need_swap, newg);
-
-      delta += 1;
+   const size_t sz = std::max(a.sig_words(), b.sig_words());
+   auto u = BigInt::with_capacity(sz);
+   auto v = BigInt::with_capacity(sz);
+   u += a;
+   v += b;
+
+   u.const_time_poison();
+   v.const_time_poison();
+
+   u.set_sign(BigInt::Positive);
+   v.set_sign(BigInt::Positive);
+
+   // In the worst case we have two fully populated big ints. After right
+   // shifting so many times, we'll have reached the result for sure.
+   const size_t loop_cnt = u.bits() + v.bits();
+
+   using WordMask = CT::Mask<word>;
+
+   // This temporary is big enough to hold all intermediate results of the
+   // algorithm. No reallocation will happen during the loop.
+   // Note however, that `ct_cond_assign()` will invalidate the 'sig_words'
+   // cache, which _does not_ shrink the capacity of the underlying buffer.
+   auto tmp = BigInt::with_capacity(sz);
+   size_t factors_of_two = 0;
+   for(size_t i = 0; i != loop_cnt; ++i) {
+      auto both_odd = WordMask::expand(u.is_odd()) & WordMask::expand(v.is_odd());
+
+      // Subtract the smaller from the larger if both are odd
+      auto u_gt_v = WordMask::expand(bigint_cmp(u.data(), u.size(), v.data(), v.size()) > 0);
+      bigint_sub_abs(tmp.mutable_data(), u.data(), sz, v.data(), sz);
+      u.ct_cond_assign((u_gt_v & both_odd).is_set(), tmp);
+      v.ct_cond_assign((~u_gt_v & both_odd).is_set(), tmp);
+
+      const auto u_is_even = WordMask::expand(u.is_even());
+      const auto v_is_even = WordMask::expand(v.is_even());
+      BOTAN_DEBUG_ASSERT((u_is_even | v_is_even).is_set());
+
+      // When both are even, we're going to eliminate a factor of 2.
+      // We have to reapply this factor to the final result.
+      factors_of_two += (u_is_even & v_is_even).if_set_return(1);
+
+      // remove one factor of 2, if u is even
+      bigint_shr2(tmp.mutable_data(), u.data(), sz, 0, 1);
+      u.ct_cond_assign(u_is_even.is_set(), tmp);
+
+      // remove one factor of 2, if v is even
+      bigint_shr2(tmp.mutable_data(), v.data(), sz, 0, 1);
+      v.ct_cond_assign(v_is_even.is_set(), tmp);
+   }
 
-      g.ct_cond_add(g.is_odd(), f);
-      g >>= 1;
-      }
+   // The GCD (without factors of two) is either in u or v, the other one is
+   // zero. The non-zero variable _must_ be odd, because all factors of two were
+   // removed in the loop iterations above.
+   BOTAN_DEBUG_ASSERT(u.is_zero() || v.is_zero());
+   BOTAN_DEBUG_ASSERT(u.is_odd() || v.is_odd());
 
-   f <<= common2s;
+   // make sure that the GCD (without factors of two) is in u
+   u.ct_cond_assign(u.is_even() /* .is_zero() would not be constant time */, v);
 
-   f.const_time_unpoison();
-   g.const_time_unpoison();
+   // re-apply the factors of two
+   u.ct_shift_left(factors_of_two);
 
-   BOTAN_ASSERT_NOMSG(g.is_zero());
+   u.const_time_unpoison();
+   v.const_time_unpoison();
 
-   return f;
-   }
+   return u;
+}
 
 /*
 * Calculate the LCM


Test patch:
diff --git a/src/tests/data/bn/gcd.vec b/src/tests/data/bn/gcd.vec
index 4378c9534..333ec09de 100644
--- a/src/tests/data/bn/gcd.vec
+++ b/src/tests/data/bn/gcd.vec
@@ -10,3 +10,722 @@ GCD = 1
 X = 10022247630053045674847735694652
 Y = 25956
 GCD = 28
+
+# Generated by a fuzzer
+X = 50
+Y = 50
+GCD = 50
+
+X = 0
+Y = -50
+GCD = 50
+
+X = -10
+Y = 0
+GCD = 10
+
+X = 50
+Y = 25
+GCD = 25
+
+X = 245
+Y = 25
+GCD = 5
+
+X = 50
+Y = 10
+GCD = 10
+
+X = 10
+Y = 50
+GCD = 10
+
+X = 10
+Y = 12825
+GCD = 5
+
+X = 50
+Y = 12825
+GCD = 25
+
+X = 10240
+Y = 16450
+GCD = 10
+
+X = 10240
+Y = 47170
+GCD = 10
+
+X = 9984
+Y = 4260
+GCD = 12
+
+X = 40
+Y = 10290
+GCD = 10
+
+X = 1175
+Y = 94
+GCD = 47
+
+X = 35980
+Y = 53199
+GCD = 257
+
+X = 35847
+Y = 68096
+GCD = 7
+
+X = 458916
+Y = 2624598
+GCD = 6
+
+X = 3279408
+Y = 659760
+GCD = 48
+
+X = 16058112
+Y = 2700
+GCD = 12
+
+X = 36085
+Y = 12825
+GCD = 5
+
+X = 78337
+Y = 2160129
+GCD = 19
+
+X = 78430
+Y = 16056320
+GCD = 10
+
+X = 16776960
+Y = 1090
+GCD = 10
+
+X = 6396992
+Y = 722075655
+GCD = 7
+
+X = 5
+Y = 1059389735
+GCD = 5
+
+X = 150994738
+Y = 425888819
+GCD = 31
+
+X = 1242012672
+Y = 131082
+GCD = 6
+
+X = 4294967295
+Y = 738263040
+GCD = 15
+
+X = 408857345
+Y = 6438978
+GCD = 13
+
+X = 436207359
+Y = 140402178
+GCD = 21
+
+X = 1532952320
+Y = 4194400
+GCD = 160
+
+X = 271642542080
+Y = 271644042050
+GCD = 10
+
+X = 1099176033792
+Y = 63824831056434
+GCD = 6
+
+X = 201326976
+Y = 18906613940340
+GCD = 36
+
+X = 48382806589440
+Y = 273774117071615
+GCD = 5
+
+X = 1792968491011584
+Y = 458999933698965504
+GCD = 1792968491011584
+
+X = 1144597543780468
+Y = 18446744073709551615
+GCD = 17
+
+X = 1144597543780468
+Y = 4722366482869645213695
+GCD = 17
+
+X = 793209995169510720256
+Y = 393218
+GCD = 14
+
+X = 4703923224290950052352
+Y = 737873248443396401202
+GCD = 174
+
+X = 4722366482869645213695
+Y = 22067637293647090444
+GCD = 13
+
+X = 4703923164046856216064
+Y = 258254474215098561024
+GCD = 155136
+
+X = 797765102514435260416
+Y = 18447588507199864832
+GCD = 131072
+
+X = 903890459611768029184
+Y = 1807780919223536058368
+GCD = 903890459611768029184
+
+X = 4595903475389527228415
+Y = 4722312265951279579200
+GCD = 5
+
+X = 4722366482869645213695
+Y = 4722366482869645148160
+GCD = 255
+
+X = 480480039312998531072
+Y = 2141650212148595195904
+GCD = 65536
+
+X = 4722366482869645213695
+Y = 1208925754593909957197824
+GCD = 7
+
+X = 4722366482869645213695
+Y = 1208925819614629157928960
+GCD = 255
+
+X = 797765102514723686400
+Y = 188894665021251324477696
+GCD = 768
+
+X = 1204959715033735650869503
+Y = 136228393472650785280
+GCD = 13
+
+X = 942660822912753532928
+Y = 2141650212148595195904
+GCD = 65536
+
+X = 442721857769029238784
+Y = 2141650212148595195904
+GCD = 196608
+
+X = 303264472571785028567088
+Y = 516
+GCD = 12
+
+X = 747148475491232069452024
+Y = 1208925765339493900905763
+GCD = 23
+
+X = 170153343865918441783296
+Y = 48146007943356440641536
+GCD = 393216
+
+X = 1204959715032688404423390
+Y = 258254470916563677696
+GCD = 18
+
+X = 1204204345418645566925055
+Y = 74953629241549834414467122
+GCD = 7
+
+X = 1204959715032688404422754
+Y = 268381790208919692860076544
+GCD = 22
+
+X = 235692535821570555707392
+Y = 1208908107801354625679360
+GCD = 65536
+
+X = 228425443925444001792
+Y = 2419993289441406944608256
+GCD = 65536
+
+X = 231839255980392222556160
+Y = 3626777458843887530541056
+GCD = 131072
+
+X = 170153343968173022117888
+Y = 12325378033499248804233216
+GCD = 131072
+
+X = 460954170594259225267450
+Y = 190991380809640943687499784
+GCD = 22
+
+X = 102717755577535295809126400
+Y = 76258557204553309160996864
+GCD = 1099511627776
+
+X = 78879079857209709897575304235
+Y = 616826987596671034064896000
+GCD = 5
+
+X = 49130707534186789102904410112
+Y = 75513157013187737060741377315
+GCD = 7
+
+X = 3241353881420173612727533572
+Y = 243420769443702579199475796
+GCD = 12
+
+X = 48965141379259316382188709119
+Y = 79227255690700361606874801912
+GCD = 131
+
+X = 49130707533898558709572894720
+Y = 75513157013187824972490154800
+GCD = 80
+
+X = 26295745427849035727136358400
+Y = 6266316712697954317203668992
+GCD = 2199023255552
+
+X = 78879077562913050378480189452
+Y = 20193043856105740896890928499712
+GCD = 78879077562913050378480189452
+
+X = 16541354804929436240775120682911
+Y = 4436467613044451074029180174080
+GCD = 43
+
+X = 20282100128087474331341467287552
+Y = 14804600477052435834209280
+GCD = 3072
+
+X = 3426616473501470154388358040204
+Y = 811300217294875483658032846995456
+GCD = 12
+
+X = 1979783088584558316015909800496378
+Y = 3204303647565649377836686155582990
+GCD = 6
+
+X = 5192217815342704361436504779784204
+Y = 509048882746886449833877463025976320
+GCD = 12
+
+X = 306345514133557588452856797282868735
+Y = 73108820758812464596743413815553556735
+GCD = 5
+
+X = 1329227931720309912618700371287736320
+Y = 47857400145115505053127220974796079104
+GCD = 65536
+
+X = 184819773958316066324581304704805371903
+Y = 65274328389608743474021408575838784273835
+GCD = 11
+
+X = 124947766125005138789727305605075970088
+Y = 13664674708373325527021687322670232759040
+GCD = 24
+
+X = 53765944850796721205552073494172438364210
+Y = 17438543527387263594545220587919874457600
+GCD = 10
+
+X = 87112285708653741006455524839112898006880
+Y = 6908858316387243953660477516825431747133440
+GCD = 160
+
+X = 4276679421309531954424045504066924207603750
+Y = 14970090771917742400798760
+GCD = 10
+
+X = 5692439436496785127656169978005362407267880186
+Y = 3523168961246341099026895228700425015886348288
+GCD = 14
+
+X = 540008378638560841470062554657937819942518878
+Y = 3835694520731979079227933463325179017659678720
+GCD = 22
+
+X = 2176794525353287994057866548860824646756865530
+Y = 3523096940168748808865218389601781963264355080
+GCD = 130
+
+X = 1092736514728000533935250213806513787502592000
+Y = 16673835979125984709705355764156642361344
+GCD = 18446744073709551616
+
+X = 2176794525353287994057865295130745980848707066
+Y = 3523096940168748808864618659999724204647836424
+GCD = 6
+
+X = 374138710159133349757570722244018358724795979399284
+Y = 156713892929570061484699748181699212154666913628160
+GCD = 36
+
+X = 374138710159133349757570722244018358724795979399284
+Y = 40118756589969935740083135534514998311594729888808960
+GCD = 36
+
+X = 24331359867312863288178806485324207300903651618735573800
+Y = 5555389871922127531512992234290458197860109933360574720
+GCD = 120
+
+X = 2425751498259005642768313936505020065931630739229211754506
+Y = 1545914230665843215778896482126537958830148495309152960447
+GCD = 7
+
+X = 307577985033947357427953686929472512923843045309444524081152
+Y = 18446744073709551616
+GCD = 16777216
+
+X = 307577985033947357427953681737175654389015488836332551143424
+Y = 18446744073709551616
+GCD = 16777216
+
+X = 307577985033947357427953681737175654389015488836332551143424
+Y = 4722366482869645213696
+GCD = 16777216
+
+X = 307577985033947357427953686929472512923843045309444524081152
+Y = 4722366482869645213696
+GCD = 16777216
+
+X = 78739964168690523501556143853944963308503819599164119663509504
+Y = 4722366482869645213696
+GCD = 4294967296
+
+X = 78739964168690523501556142524716967523587965142101133092716544
+Y = 4722366482869645213696
+GCD = 4294967296
+
+X = 24768289145648317635589423814241117000881980746882242196598027553535
+Y = 26012136037358278543602333388999476469246802999199753743843516723025
+GCD = 15
+
+X = 5149981797533515283343742963724374606446469652965072943262919871430400
+Y = 100634002029312406256309105400787725740113724092516976497820
+GCD = 20
+
+X = 1321037386690381349938683739263961903008220076704488051574076902211584
+Y = 15164765481245908367514271744
+GCD = 15164765481245908367514271744
+
+X = 338185570992737625584303037251574247170104339636348941202963686966165504
+Y = 15164765481245908367514271744
+GCD = 15164765481245908367514271744
+
+X = 337509207083156457609252174647413332657279929155895836586315257914852321515
+Y = 183862752314623417506283538849296850517880288540684251333062945874556944895
+GCD = 5
+
+X = 86575506174140832149581577536403007275546710946905328947958703863338369024
+Y = 993838070578931850773415313014784
+GCD = 993838070578931850773415313014784
+
+X = 451228541390476007311714861022150931662474961929213031567292877630341120
+Y = 28497821422193158001834995761082810897171420688879198694774169491208898019700
+GCD = 20
+
+X = 22163329580580053030292883849319169862539958002407764210677428189014622470144
+Y = 993838070578931850773415313014784
+GCD = 993838070578931850773415313014784
+
+X = 22163329580580053030292883849319169862539958002407764210677428189014622470144
+Y = 993838070578931850773415313014784
+GCD = 993838070578931850773415313014784
+
+X = 5673812372628493575754978265425707484810229503038933706139975414382067779108864
+Y = 16673835979125984709705355764156642361344
+GCD = 4294967296
+
+X = 67748816296197
+Y = 18063636843423339079722091749027672109335822976424541404433076709396425681928202
+GCD = 9
+
+X = 7411128355566085319457338626786129046002747323297874334485280607558508373765130
+Y = 363037146019850891306148001123515022175314401015955244588895207922418343603077120
+GCD = 10
+
+X = 7262595629053709093161795750729914268464946708213641817118819126560319404146425856
+Y = 14589803243901840623369944111094676389512018067870711068971655584997054334631936
+GCD = 1042128803135845758812138865078191170679429861990765076355118256071218166759424
+
+X = 371838967652580954980678255602939165724523184037323580239604719051587148340059439104
+Y = 231395957660612615471104
+GCD = 231395957660612615471104
+
+X = 44402809341576954473801788584399829445476538567818211345965085950542927102022
+Y = 11367119191443700345293257877606356338041993873361462104567062003338989338117632
+GCD = 44402809341576954473801788584399829445476538567818211345965085950542927102022
+
+X = 95190775719060724475053633434352426425477935113554836541338808077206309975055216410624
+Y = 231395957660612615471104
+GCD = 231395957660612615471104
+
+X = 6238422677524363639197114920753720618220121955601929767573180126147792730525218662686654464
+Y = 993838070578931850773415313014784
+GCD = 993838070578931850773415313014784
+
+X = 408841268594236695458422123446515834435673912482328069247675932747221744387700730277832586952704
+Y = 993838070578931850773415313014784
+GCD = 993838070578931850773415313014784
+
+X = 408841268594236695458422123446515834435673912482328069247675932747221744387700730277832586952704
+Y = 993838070578931850773415313014784
+GCD = 993838070578931850773415313014784
+
+X = 198654714850752852592363122707663242051733816855458532862713726373719515326687166880656944993604360
+Y = 86599256666348587580503329953455095781939721929388613309198321077256291984619052067348523759043071
+GCD = 7
+
+X = 26793821378591896073563152282190861725576325528441852346215689928521924240192355059488036418532409344
+Y = 16673835979125984709705355764156642361344
+GCD = 16673835979125984709705355764156642361344
+
+X = 5192296858534827628530497151303680
+Y = 3766103215199622531020488704
+GCD = 16777216
+
+X = 50855607001792730263644959413161789965243857114997384412854713951672195923631914721448177918362716200
+Y = 19462156949119240227640167530869238428687774755474004687086012582757657528779782496685355629777466163200
+GCD = 200
+
+X = 4390453142593170309363265635381327121220423345634561843866236699607613995670929899628605142439752368128
+Y = 93522064638774249447776301990891455381258066287519450794260690484527632892296596759566194139285422080
+GCD = 786432
+
+X = 13019037486533195766829799640978001137664450949723837768963337919082957205986846261154033288307266488360
+Y = 19462156949119240227640167530869238428687774755474004687086012582757657528779782501426159849521566187520
+GCD = 40
+
+X = 4390453142593170309363265635381327122293332490483614587884613453663604407134860130361291060585539311873
+Y = 6999749148598229704746812131412457626739210509340432706826178845858494619235957338383668805336269062425
+GCD = 11
+
+X = 5669777658926189672943569867305179649574356876755444740948489583974038506846907871030547204609652109082623
+Y = 9173994463960286046443283581208347763186259956572673655155823296713211576176299233337151198935633932402467
+GCD = 13
+
+X = 95123020264944047966700135353315865954680594534614340988378094788420414699526866473363465939919657785382966157320
+Y = 94996208104613244195189838911222452851213994481177900332416597730828536263681970305024211239729721264311059349504
+GCD = 24
+
+X = 24351493187825676279475234650448860232011689670649706441969015219405369847827896511060340884550318956217718817185800
+Y = 94996703500314298509765795277736139558969785988557650099379290956644684024190012200649837659603085627522080047104
+GCD = 24
+
+X = 149323437019726910540195840569592375448924731136779111474316813891838465720455143161928677704750998590970289717248
+Y = 8469483861634652620682317165362880266526808259584364973179026472371958392199968100654574665265456117623535475621888
+GCD = 4294967296
+
+X = 2429850106321829637747161658815087375646557121712254810611796287163254521069457123635782064478328572582915443000016904
+Y = 315216049571191700026749714750673189937125585541579994787476383796725906199615814210146315734093853012193651760037888
+GCD = 24
+
+X = 185741808249886617612949114568838250946696831348240768581098401934275838253738570934613506997136157468313200749934259820171655976146960384
+Y = 17557697933765753949832252939792973391906666193305102298648092052771357222676265711277848982568472205770896447137835817699613722892321269
+GCD = 11
+
+X = 113832252960672093043177336145273032517527046282444394302063667262444254616149369120083453433201567454134615343414480692293737405292216320
+Y = 726838724295609472799297008929202347950830421821281247311683642474460130369651030412562910147871907063321995520089145250558542794981376
+GCD = 5192296858534827628530496329220096
+
+X = 119174205242975578406553365204248525682942899174860418749864895477087293740942722976957337053238901193205315992654863001649906341480759296
+Y = 139984046386113260483094870637401285033124859780250601317245593829672975558095346476454011284871970816
+GCD = 5708990770823839524233143877797980545530986496
+
+X = 25491687893765028392407019789442094962512508035749421337886807194868048938745925467926320301778056779793975243078670282232550853419424874495
+Y = 47559674350069023297869331109591321517873419921365893494881855906598127375965179410528616839104644928537901865352335920436657737774605688370
+GCD = 5
+
+X = 44285536747019986640223177352703732029765206417113941221954192268844621274915943678363659992223284850554793393708987972684042590578753372159
+Y = 47455371815155036853174613944824023845240349052349635257353336134342646433423212769927035131885402373599906839452732646994937992349721110568
+GCD = 7
+
+X = 14757231796860790312605598044536822272618662301747933489128465176126353599344099651287272935851986371120049059609397282674595456725750382592
+Y = 29661266221547676506128070165212416179773476434452875813311241034736131035592693522852299321630322358713643377988760131540243147077058560
+GCD = 131072
+
+X = 204586890682243650655710060648347275048307998118181832847223112172313155333402993147360082617796853721204345670713995530709406051888011514432119177216
+Y = 3147963050034366592815705643272567522280491949635552999881384163141354786381321642724819684217849896760732298330451712345811533744333389824
+GCD = 720896
+
+X = 780952437669429942780266969669539856717562738957591812803891008807045153158058742795133839238876008407666567831291927445858257817165886572217518850932998144
+Y = 504403158265511436
+GCD = 12
+
+X = 199923824043374065351748344235402203319696061173143504077796098254603559208463038155554262831620040049092373175638805611083702785842692887483532424625724063744
+Y = 504403158265511436
+GCD = 12
+
+X = 34982280245463394670609457579692929185443721170930743031741327140441958130773319576767495016711095182059469594800151886002830074247157977810501954179371828225
+Y = 34982280245463394670609457579692929185443721170932456410121470929926831540734185209652628374708872105702178134360854066463501710383165798940287649911473700864
+GCD = 7
+
+X = 878694100496718043517683302282418331810487718418192785677193797449164600716705457101935590301526715148342795763327063191246897382991985083216603962096249457665
+Y = 43969364306123046381956511696767704361262269092649482912391257072151681671305560049436536377059690931513127562699001851392833370855805178516047407033966087110655
+GCD = 15
+
+X = 722359995375998149452485056517285842402066952345334300743883237156388999832872241219610193491036248474734181158232142187846713464321542339826212024688289477104767074304
+Y = 3882179963198952542083653566464
+GCD = 3882179963198952542083653566464
+
+X = 52374249726338269194443774425091728217358108241299734432647981750858891655680924345063994400398162113835892614806287004877323591170548230038908752101376
+Y = 210265726817303378109970138950012831547339046258233416074451774499334824079559331987232133098737557454888223220234799156359904153661570213709387606041583842932214477094912
+GCD = 34359738368
+
+X = 237264110786113059287597060360971217820295734201329543203406214928585123660606883874524017374297879965166823063462155190474055541333260202958452865497459777760956809668148995948798814052108998716324291293983196317194135
+Y = 214049183505538932474636767459337440560215562385361923125807029489075083738122527867375416254885511299817701742552286611223076521995439143276788294859480451646321610711231658195238294213486990927936993797239561396212217600
+GCD = 5
+
+X = 1876879207201175057492789423877314215322424246124273896870746119483226976859199877194350199664905573345421779744860216842867027430639252976028516770546336337005568458497707911915485291288395026418956363130068715730985636454568832292022531662376191563661312
+Y = 5708990770823839524233143877797980545530986489
+GCD = 87
+
+X = 3363367539304505703027079442552507122706238400457443369245176791122514794639406448208954988501308221032146044411618007415565522845012431191879828925682092348594598068490632241848814700232176449061176441462518721293692255067829290957515767269880222157257965580
+Y = 1361814248756007200533168139845889408251142217611717175653659975577351848705785138602476176214007726323923770735401152485086859337546434285791192125908801955043446888948734166810831779557559296132508457382367647586533073003629384910505913215565085434033001944055825
+GCD = 5
+
+X = 12678109472213161401703438848791868216167793655255850598551177341659682857771272625612550510706188936452181169092059283552581314341902390680084213151227873955710459267650688968240636798789863358552942765269932433141366050248272244352050617332019950036016264831207730642943
+Y = 134845478592357541157566293117706725637394587431231839335331992855524373591354476025678346417912363996663099521848424500722273929166898542460768764255734440683183272037112665265878633463190025669514603243492092346274286626355517807168803021973022247459429695025836218908672
+GCD = 13
+
+X = 135243343542786727305418796631304605388582794212556168057882502451410729117628593218846680429940792678707573568123950847041618877615521458294043089389239881266154651220433127359406786735694503820660973954419629861656361978904452018851986932268485348203042364082876955230207
+Y = 33310135181696372139921906528350125226524900287668362295886420570329687806530399999415533137038875361825853395591655900400303707902706209190044809786503231266914425820271548614110409224049160286839516569368871407461659500788820820630471934000925653444182590104471184665600
+GCD = 17
+
+X = 2215827865120445285436125565036648969148792855456723372821991068916198703588887065116185201305308203107196095430332742070532641797438106858222281777895443600357105063040077502639318571449005406767096743780978646651379025340184632128851788352853550486187747427305824847603979002674
+Y = 416565862587258106453111968243765595200567114598511932122941350707696259133482593835765537607486930880074594511913079561845089085547380991590029881104408629401048208314254635112298059403160184650604748468779068541836121325038476716667853783318593594084688643635494233441539457024
+GCD = 14
+
+X = 38067632803851377644723601069695622654522250234718472043886004246542639109942188842572850188474014847493589682854680079209124766991310257951453896249547005494679473653969403765454676529792339023992983738796353079591318152225563916879649130726738090076785327664155405594427659035179220992
+Y = 19376425124231328118062655436325990964012306515288736815486364031503117411191149722688017059004921097711156200969399776405568620691513232993584793703800271763199073990809156305832298118900314870483505784879851011754418969310560036953681214463805023057298967656820912871872763936309671624717
+GCD = 59
+
+X = 122245218959001588463952828673506362171631389701671774417031018599279228376974049029329012807059471829805275905437405538025220405954614995919671470121686125412126680586247272481745019829681271369298598495825351381998153950179472676342568385456697115695273047400507577551061745792440647001785155
+Y = 167807122495781932399657376343175760221514333426416508587508285795505188084982704197762740314361205280402499732161411716709773057513862058339394752857055856940248189160532823690299195159119704681203604046535842844262361069507635748543749043776249631170872408689446756560839226898402940058337280
+GCD = 5
+
+X = 2494800386020829918222467977765624615221746130994983526475248193273100393791554515474032462773804430259686086041000293577524890952589256057203578585481900262756200266862196341924898293830316972643789814017571700871708957115737010655926624148325028026595582182659788564021205982273894684295176
+Y = 421454940789259495795256111430229273350011152351180327850997529961567917293056888234891165550570052180368066390565825695087791801561462751998308490587946260604451278389805009709823860714516476457343057128744104937078547109474923459916264428142272449661800532559792523035143747254390192340992
+GCD = 24
+
+X = 58206815071153024036311674235981655208600150932908250968023875369162384381955848483208129024983945969357554873865400877507205658490382493239432240097944207856659364012644411674928644269311309995031411138500636374938464683352472470290315251585405775102546100376071770046292271112813470075488043007
+Y = 163499238157084246970890052123683284196580360902532898925100485720359360229235781982089988404581326756820409334069376444260765475622917909637655170497159242908710009045866626823461452212060126470580043564995861900878159553289712399558293529812574219666096915236694430407300769271918989668235668480
+GCD = 9
+
+X = 22922588370333316881430253366508131451743354379072829866326982452703106633274800030719079341230928456007359073429001082348391435585414421706039920508952380312384446846962448598923124243168157351859118749463051962621818832272526883120870375185822891408916026287498783135046862091424299946093777386141
+Y = 41201169346686179126466659192833199132379059584855317847802894568950446975849390483031341790299031575598411718163868517140150253512249275818532126515548629103472617941609155222862989696719408112454711266628240269238297372353487915431721354068002935090383003459249878091217079995682714176669717576192
+GCD = 151
+
+X = 10673394352410707503628927353454958261246614200907378783582119880571015683552699636722430731336803551598707412685608263095009152984770551826751947383747725854090991756745367961468256374533473975653989555450095907310124772741650159183722187127284771532326749300815562811022782121318553856851969535115264
+Y = 5501836197888
+GCD = 131072
+
+X = 45841877162869861239249040245500787114088915313625578209875822348962763561438011463689563669832509531966818275743227429051574856811602808217130728862540292791166654575142479898360081105478161015027784469360774391960822319499157693659014968713275507892472315305173046071320579615930719714431992186299808898613248
+Y = 5501836197888
+GCD = 131072
+
+X = 11735520553694684477247754302848201501206762320288148021728210521334467471728130934704528299477122440183505478590266221837203163343770316877454817721137971930902011378286694086184168925875016643842537917967365383725177360969777586438763589522302025884227563951082036562167790419116358827084440361438807989000601600
+Y = 5501836197888
+GCD = 131072
+
+X = 9685264074275605761008078114479441450613550623479456835437662639984459608234152341509823048213299902601725405616722444978613894660062383170394195895601745103666361122609132526229373515002507422578856070551918465194861686218564396711217836354305486582714543719829667683656579410299115843825322312425443659084060233704669184
+Y = 3882179963198952542083653566464
+GCD = 3882179963198952542083653566464
+
+X = 13004339370268460133616414571621123902761181994968742785680443237879312379776629746132679421182002362987336697886525486884020067147614438624369680256652606648237071931125251027946628667333212342627889295190818593148126813009604585987153035103918036836139769063440760691928725245857912090211025899375479566099863871074101886976
+Y = 354279609555210558604710148568585177326814983332746428185135142550941980808729691687964087834293796715762367813496255455583019262446505929218716488066316617491845127026673354019551332256188054587633663653455125903701380160625973960719309131198646378397220569558799955563896094465870168940743363934293506518585341794651734016
+GCD = 4294967296
+
+X = 3631967693818796344388622788466903694961372340488471944860216614088969053134244850833644996538991173497670718646818120565969346913317674529160614453314552315257696487987514111996884798629983938827512693425670119076543569670123183524946882972201350429450453050878624020574601526164609079043474057300419996382484767330581303378892741985304576
+Y = 20203181441137406086353707335680
+GCD = 131072
+
+X = 3486906164855093402132295269158717942566975279436463909258497786794493929740097983047923969103201093740954635189469431178566391390118857701141180291807589848661241595106219332600122484419490366363228661167583461202459372115581895997582729601035378226784442398650982875312164286862754266978344493213057434559662979789541447415000627451692661728218186238
+Y = 908286955901919032661316939420652777406643027936798507085034277842856699555733131368108366941159898725752258384653277240314377557536757575321589026645538470780940441962870194874851487353046140359572654636523162180879990830802912342062370044470969582185487033643295652604714943742573504614009026544444276526262818642529090631534503300100698484140146688
+GCD = 6
+
+X = 1128430269653696552505663664688505519048577789599538365539622124238996200782519104763097842165142050162574185866196598853834822868366614849204705061545542573543394593165118178044669234153709272853780084054420025238502045013293149223615189108259682884834180066379082981015735633255565718487614148804739843611768135568282012321148042242594077250802202877118208167378944
+Y = 5708990770823839524233143877797980545530986489
+GCD = 29
+
+X = 71931783751688573561593065304303572791446413059397427216420833249708720173806415236252536670510042757933372965539093626484882876360573211769208774982004849741263453997537434379056854280023318338898939385221841091181302660216680169912627209083792257807856017126084808669109000030448103565719852082189862769560162268535136822958971155846232839537986610650112855196223944447
+Y = 6985101857537397370072970005252016084814218980265390429637289513586943158769573749949016815115129406528245358494919749794561954131056620498286119543517864438621657874648995697904201806628276059413231144821674516798707408068740079654571250600908006872443141383050144433990790994326750739942975055071508208546446310730368052718134713651140298936178054777251230662601163713465
+GCD = 7
+
+X = 11210665390637902553867733095687941573957466352879553085031644223463862408863392987917837312167474562749230450938427765815977203153874025891424282720901504852214379181073664695167124273441076136642981845607073260012419763269458459460006863533283637157852442106762068079980402111193946343488167155176025598830225847487779798341820219022548344721457026385778216963497294561280
+Y = 287754126692433455641163632071751943902388779097001464997912302762137967613696866454406589418751638945006146051548836140911665338924585639961442548081595158343330993937528850120114926051642103450469213642718453824925669580932736003855898369071061420588041856377289319563089568229166497331615218017455147152446348358467666171167165198073771583709307547017098279274938368
+GCD = 1099511627776
+
+X = 86960190628352373078181318531534076682483815341830191879467489496458683031737383192087221537406704769879022526987965995924553602917396607594914769936404358321022290207543748102771336931506640792003700745372484165427831807230827434724610521591456954986392866783183541270805258351929810348149329796893771836389620547572364051871227962043135902657718588695487786070908940315992638260115018505060413
+Y = 82315133424089161392941277050539233477694656017886073293320892676746686835260227003094277653546361968294518506220529991118259377219265928402677160946023053792440722514104313874387015723671522053068552691425635836483146406876738513177153280512879640234494275054613375251276219282042718071940519569659222830362443818821931138508122069512032498020013436493099439418331769304711746515192275416383695
+GCD = 11
+
+X = 13760451396890330453669230315025109614294534240060508373721193193072678786718899190949239158682716066778654757211949460319791133699370725926646424016334108613875638801255524335097952556506881123899189166219611364938828867245297083623518309980420166699835129273359797793707767305990812843407470020641895298602105631651250357383240989905555100040584999287385189163654438466807232250770248053401427264060137830407841582974141827052760171460358010984992264006525072161205415497751526138855090745337070607558246400
+Y = 31197101826193924802357548151897497122059925800562954364774960783244768307188881491432055976721319631178782923198279123525617022688747206769800213612644985409899488855548378261628722445478154644913665064706288577830879498972722464029843503279679584153310839575456592222454263530330948200721084492860758458553976025780503108714755304617811715622325157727125714310408585230398909153856742486529550727133818915755896580162267751190580949303149747150652102466301378063988172473431356868400617658729310977064960
+GCD = 327680
+
+X = 2085976507145258131303668551541188581622200472320643379967252402912542300716378091854726364863670533922307971460433320375368789172445718712461831379830730385975524903919836535585750454796529647920699160299071110323470327603877003543277826132969150523537535549256538649196488714308403209473002737156480181308725800481645186378035852252640284628105999795286145343783970967934701064819520810544499374744142303398420186939393433488498723219183870081216601575284857374283201623573155111539886750997767698858859560960
+Y = 249850811476614868626330058961501558684064217736265583221762255968344755288980536143378173682856225661512116820892348868678172006154240
+GCD = 5497558138880
+
+X = 18290777231384279903558776346397994961739796375193562395738421329709663988976079343344293719490151676427582502729335971519656008073025231711864900410814169820734251425574213950663493247870988870859557218402173375075931517335378418272431645649132682127024743288224296354152881815650381684588374306446825319641796967447884455518165427844914711609811489890733051347057573919908912974763695675095681970388154304172260273453639847612524537974593822708206313963565593255653977692946632133856237953435482633865687667158772275866851320180862820267589632
+Y = 53420548710018621169797907231411722985069363682265195386928370377269068340090509887045110726596137250217815879461250728444995662902110630717206316476813655610695190979142431492831898799908176139121955168491763167997111125978005425402736142862470643924468396469265966719871696882519326751646246469618232983451604126893336978682313582321638220706296425763278720837713969231423774835474903772684527164136983080022964862778006826337659540694866079142253708831195652879311236082594020742408831488773252321573264341424189959286870162455850450944
+GCD = 65536
+
+X = 86375753343124368752325271269789763165984441256087311882463472290020237150016099804111120755658302072845928745993007341476054020894366781581470616217561533108535624464589657656730162105411253690472818751181074526812690610830743019855294241109120600073515054074378955094453730513221182101432343448952305648312543440885808664477464591648226308162940165323288329387232324532417227657473491339313651860364031748252175463456530667167895622759772813154443275370190344158647070352073083194721826491890908471218427521748381245692758406306784940253001713788783903299543760896
+Y = 12833743307553955708072995426417214794689319784893085703413113163644086907773893156249273839051966301944907045737552805932228671761961284591295165080358639594570941606315255083715191478941479548056143225065115841756619935199409143037475295868922425594239277476612201880519702764335056071211712982900387911876399090529093646592421370837919968051858402914788742193980060088986254004356974523437655713225612717397091997660132455337836615707390637346198946717241958194571317609742197981705022557047339122546781825152271354311576156063155926024221775097017177566583251337216
+GCD = 65536
+
+X = 5660721371094998630552388977936941918845956342158938071529126119998766261863455116762226409842822484646030786297397729130974676313333221397723258304434112633800990684911347804191467903740231921858826649677402900189196491871403574549236563385327327646417880133295259645266024840801367732369351258605561030137336992067022215976117668901545227373750328004168642488142745520216397226259354611918842976540980591829601805122581187470751049442793603331972558299393970043449976554568493037154630363903683197609777400698775722507811192653717814409429667547359958889983064143822848
+Y = 12833743307553955708072995426417214794689319784893085703413113163644086907773893156249273839051966301944907045737552805932228671761961284591295165080358639594570941606315255083715191478941479548056143225065115841756619935199409143037475295868922425594239277476612201880519702764335056071211712982900387911876399090529093646592421370837919968051858402914788742193980060088986254004356974523437655713225612717397091997660132455337836615707390637346198946717241958194571317609742197981705022557047339122546781825152271354311576156063155926024221775097017177566583251337216
+GCD = 65536
+
+X = 1593351416094477439951653901101303797625314905385626832162449352088228505521468980858560435874851394151262739716930809136559078465205176543054974371502812400776359389698122021488804912745543905040065363266613700626228913445641138359924751172069747490582786652382905033572098894146140952500374355866243772460035785979256626067726277343962267348837441709485409642433030375930588884482722396389913551857438349438410067653692717222574208707099200663638426849466808923338922283095715806352693677780821490249151237707604248193257975910148716564504022228550693316708566413928197631839796474112
+Y = 12833743307553955708072995426417214794689319784893085703413113163644086907773893156249273839051966301944907045737552805932228671761961284591295165080358639594570941606315255083715191478941479548056143225065115841756619935199409143037475295868922425594239277476612201880519702764335056071211712982900387911876399090529093646592421370837919968051858402914788742193980060088986254004356974523437655713225612717397091997660132455337836615707390637346198946717241958194571317609742197981705022557047339122546781825152271354311576156063155926024221775097017177566583251337216
+GCD = 768
+
+X = 5386512581267998214128780883786501987512248398942980120858094526843667413651057296768456069275364577449693063027329013225314262801770523667628195798733908178303748041891484732511990463678507714564203931191378038015332841713411232329767064904663543935025150526589876314039767529286797859075102506298386770270116950763431820114472176260274607596499547327905073504856053770759768091324088158068080492002263055664059540297026753209388629752920548863688126639935095145172841418662177558444294594729362364931781144356151135711792680458369802649084540995691019905866070429588668735157811576896852804485544178838972032143145423445568782336
+Y = 18738350204025652696317952
+GCD = 1099511627776
+
+X = 5386512581267998214128780883786501987512248398942980120858043580351315696758776168077422767639985010766180403317535798279964846128245210941546701532038316380685132455056034396153252227586148009984974627405188612714570483915017462779289589582229087787940782263026104991846191073501301729657121137655617851790118560902918543917876582193164574163118089595167784948186069584437550595432380275820293430103557174779141313322065469395627928378232759348590889597278876862385215265104082707980092958424328692675026808389741932504155765655907914234901443888571228088208419912803915568468874085413119733475239819932088337372356738858224713728
+Y = 18738350204025652696317952
+GCD = 14293651161088
+
+X = 1741113273565387978206206465824512167165933266821688418201009227315116818099374224048161852958612887853536059174410378801855048850534273631735727594523168448083062686166239626780737234491740166584274375175920041002739305750530389724019421650714925420973308378261798213895736006933877533122229352906070369992465255349220109156911411351223575271030681420408813875825400782997312835085903182048684310432879709344815517763289012677104842974676560570888428789218611468379660759918544491747114274334358129326149904080083541512162378556324042696140478106384965630987278420001882294588652025525894275539629344151355995908137980733102751744
+Y = 3882179963198952542083653566464
+GCD = 3882179963198952542083653566464
+
+X = 445724998032739322420788855251075114794478916306352235059458362192669905433439801356329434357404899290505231148649056973274892505736774049724346264197931122709264047658557344455868732029885482645574240045035530496701262272135779769348971942583020907769166944835020342757308417775072648479290714343954014718071105369400347944169321305913235269383854443624656352211302600447312085781991214604463183470817205592272772547401987245338839801517199506147437770039964535905193154539147389887261254229595681107494375444501386627113568910418954930211962395234551201532743275520481867414694918534628934538145112102747134952483323067674304446464
+Y = 3882179963198952542083653566464
+GCD = 3882179963198952542083653566464
+
+X = 4965080241426511823742761047919256907470586719612049907946108314286704277269392273538205252564783513819764863729598144363960908994851029816471966175623861057872657971185199160867331227308217744028252747703518575741849183829185290642460608373849580946223072280466395046653906961777713133036855376251393425039861105360451375463740615418144975407672145358277822386831502891191199910259455517692635510959768319715228042129742650044391925909070746659917357232270514324576101384391574708774498205696
+Y = 8273153554255617868983008432299506358456048905475345746592664442180556895004577285342372917946942243236861132777299647224043638261433412700933335195788655713152711204629901803269789125469881603012719261621384401492183458537856606082487910022924790824190613904156473676491556263208619621104784431197818474446925122542033936848158391080975196545367305906755996147494234010365015083175767547831316888790368959665893677632964427744082847442260133048103280688334761601954994978159094554013244464016483595392559939945982123342790008178636386966365510836998304908949332952915650631073150530728572027015129217154873634686304256
+GCD = 65536
+
+X = 5922533216265880202513796871222528686746651461859445910493092723115557285461041931633327437300501431704477537743506001057788900656895599957604645807920680849417419961224706307587343094834033126347435589610207770530525298932899464474436914657592148575875518506819462680305263025852111495587514545401517643868197739207306901226775902666036575086806654839407364188756025954145260415206713308528177597672065561955181991159310437263161518315601452101357352673508583885181570971635890578790409008246589654139961660992637288806430101069922828322963627273211268662700246986712354925240176678804250397983415720741568548641976387788962261582004917108736
+Y = 18738350204025652696317952
+GCD = 1099511627776
+
+# OSS-Fuzz 31020
+X = 37
+Y = 65427
+GCD = 1
+
+# OSS-Fuzz 66162
+X = 289
+Y = 58403
+GCD = 1
diff --git a/src/tests/test_bigint.cpp b/src/tests/test_bigint.cpp
index 7d9407f32..fe80dd6ef 100644
--- a/src/tests/test_bigint.cpp
+++ b/src/tests/test_bigint.cpp
@@ -10,6 +10,7 @@
    #include <botan/bigint.h>
    #include <botan/numthry.h>
    #include <botan/divide.h>
+   #include <botan/reducer.h>
    #include <botan/internal/primality.h>
    #include <botan/reducer.h>
    #include <botan/pow_mod.h>
@@ -564,6 +565,30 @@ class BigInt_Rshift_Test final : public Text_Based_Test
 
 BOTAN_REGISTER_TEST("math", "bn_rshift", BigInt_Rshift_Test);
 
+Test::Result test_const_time_left_shift() {
+   Test::Result result("BigInt const time shift");
+   const size_t bits = Test::run_long_tests() ? 2 * 4096 : 2048;
+
+   Botan::BigInt a = Botan::BigInt(Botan::BigInt::Sign::Positive, bits / sizeof(Botan::word));
+   for(size_t i = 0; i < bits; ++i) {
+      a.set_bit(i);
+   }
+
+   for(size_t i = 0; i < bits; ++i) {
+      auto ct = a;
+      auto chk = a;
+      ct.const_time_poison();
+      ct.ct_shift_left(i);
+      ct.const_time_unpoison();
+      chk <<= i;
+      result.test_eq("ct_shift_left " + std::to_string(i), ct, chk);
+   }
+
+   return result;
+}
+
+BOTAN_REGISTER_TEST_FN("math", "bn_ct_lshift", test_const_time_left_shift);
+
 class BigInt_Powmod_Test final : public Text_Based_Test
    {
    public: