From 1670af4bdf6b5139fa218377fa8761e2c4ea0e4a Mon Sep 17 00:00:00 2001 From: Jack Lloyd Date: Sun, 2 Dec 2018 18:16:40 -0500 Subject: Add a constant time divide variant for dividing by uint8_t Originally wrote it for div-by-word but that ends up requiring a dword type which we don't always have. And uint8_t covers the most important cases of n = 10 and n = 58 (whenever I get around to writing base58). We could portably support up to div-by-uint32, but I don't think we need it. Nicely for n = 10, this is actually faster than the variable time division. --- src/tests/data/bn/divide.vec | 4 ++++ src/tests/test_bigint.cpp | 18 ++++++++++++++++++ 2 files changed, 22 insertions(+) (limited to 'src/tests') diff --git a/src/tests/data/bn/divide.vec b/src/tests/data/bn/divide.vec index f1220561e..0a6dd2423 100644 --- a/src/tests/data/bn/divide.vec +++ b/src/tests/data/bn/divide.vec @@ -159,3 +159,7 @@ In1 = 0x123F71E77499975C79EE4C4F7B275A4410863CEDC3E244724D5AF83A8A2DD73C5D5913E9 In2 = 0x78B294AD98589FDCC2D53FCB0FC9F0E70E4E30323832D5669F66E15 Output = 0x26B426C03F76F97048D5DE0B8D9DBD02F4DC +In1 = 1996953214196350189568 +In2 = 13331618315827609940 +Output = 149 + diff --git a/src/tests/test_bigint.cpp b/src/tests/test_bigint.cpp index 9d8a88497..d85115e03 100644 --- a/src/tests/test_bigint.cpp +++ b/src/tests/test_bigint.cpp @@ -405,6 +405,16 @@ class BigInt_Div_Test final : public Text_Based_Test e /= b; result.test_eq("a /= b", e, c); + if(b.bytes() == 1) + { + const uint8_t b8 = b.byte_at(0); + + Botan::BigInt ct_q; + uint8_t ct_r; + Botan::ct_divide_u8(a, b8, ct_q, ct_r); + result.test_eq("ct_divide_u8 q", ct_q, c); + } + Botan::BigInt ct_q, ct_r; Botan::ct_divide(a, b, ct_q, ct_r); result.test_eq("ct_divide q", ct_q, c); @@ -449,6 +459,14 @@ class BigInt_Mod_Test final : public Text_Based_Test result.test_eq("a % b (as word)", a % b_word, expected); } + if(b.bytes() == 1) + { + Botan::BigInt ct_q; + Botan::uint8_t ct_r; + Botan::ct_divide_u8(a, b.byte_at(0), ct_q, ct_r); + result.test_eq("ct_divide_u8 r", ct_r, expected); + } + Botan::BigInt ct_q, ct_r; Botan::ct_divide(a, b, ct_q, ct_r); result.test_eq("ct_divide r", ct_r, expected); -- cgit v1.2.3