diff options
Diffstat (limited to 'protocols/Telegram/tdlib/td/tdutils/test/pq.cpp')
| -rw-r--r-- | protocols/Telegram/tdlib/td/tdutils/test/pq.cpp | 138 |
1 files changed, 91 insertions, 47 deletions
diff --git a/protocols/Telegram/tdlib/td/tdutils/test/pq.cpp b/protocols/Telegram/tdlib/td/tdutils/test/pq.cpp index 5210cc2638..d919d661b5 100644 --- a/protocols/Telegram/tdlib/td/tdutils/test/pq.cpp +++ b/protocols/Telegram/tdlib/td/tdutils/test/pq.cpp @@ -1,29 +1,24 @@ // -// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2018 +// Copyright Aliaksei Levin (levlam@telegram.org), Arseny Smirnov (arseny30@gmail.com) 2014-2022 // // Distributed under the Boost Software License, Version 1.0. (See accompanying // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) // #include "td/utils/tests.h" +#include "td/utils/algorithm.h" #include "td/utils/BigNum.h" #include "td/utils/common.h" #include "td/utils/crypto.h" #include "td/utils/format.h" #include "td/utils/logging.h" -#include "td/utils/misc.h" +#include "td/utils/SliceBuilder.h" -#include <algorithm> #include <limits> #include <utility> -REGISTER_TESTS(pq) - -using namespace td; - -#if TD_HAVE_OPENSSL -static bool is_prime(uint64 x) { - for (uint64 d = 2; d < x && d * d <= x; d++) { +static bool is_prime(td::uint64 x) { + for (td::uint64 d = 2; d < x && d * d <= x; d++) { if (x % d == 0) { return false; } @@ -31,9 +26,9 @@ static bool is_prime(uint64 x) { return true; } -static std::vector<uint64> gen_primes(uint64 L, uint64 R, int limit = 0) { - std::vector<uint64> res; - for (auto x = L; x <= R && (limit <= 0 || res.size() < static_cast<std::size_t>(limit)); x++) { +static td::vector<td::uint64> gen_primes(td::uint64 L, td::uint64 R, std::size_t limit = 0) { + td::vector<td::uint64> res; + for (auto x = L; x <= R && (limit <= 0 || res.size() < limit); x++) { if (is_prime(x)) { res.push_back(x); } @@ -41,22 +36,26 @@ static std::vector<uint64> gen_primes(uint64 L, uint64 R, int limit = 0) { return res; } -static std::vector<uint64> gen_primes() { - std::vector<uint64> result; - append(result, gen_primes(1, 100)); - append(result, gen_primes((1ull << 31) - 500000, std::numeric_limits<uint64>::max(), 5)); - append(result, gen_primes((1ull << 32) - 500000, std::numeric_limits<uint64>::max(), 5)); - append(result, gen_primes((1ull << 39) - 500000, std::numeric_limits<uint64>::max(), 1)); +static td::vector<td::uint64> gen_primes(int mode) { + td::vector<td::uint64> result; + if (mode == 1) { + for (size_t i = 10; i <= 19; i++) { + td::append(result, gen_primes(i * 100000000, (i + 1) * 100000000, 1)); + } + } else { + td::append(result, gen_primes(1, 100)); + td::append(result, gen_primes((1ull << 31) - 500000, std::numeric_limits<td::uint64>::max(), 5)); + td::append(result, gen_primes((1ull << 32) - 500000, std::numeric_limits<td::uint64>::max(), 2)); + td::append(result, gen_primes((1ull << 39) - 500000, std::numeric_limits<td::uint64>::max(), 1)); + } return result; } -using PqQuery = std::pair<uint64, uint64>; -static bool cmp(const PqQuery &a, const PqQuery &b) { - return a.first * a.second < b.first * b.second; -} -static std::vector<PqQuery> gen_pq_queries() { - std::vector<PqQuery> res; - auto primes = gen_primes(); +using PqQuery = std::pair<td::uint64, td::uint64>; + +static td::vector<PqQuery> gen_pq_queries(int mode = 0) { + td::vector<PqQuery> res; + auto primes = gen_primes(mode); for (auto q : primes) { for (auto p : primes) { if (p > q) { @@ -65,28 +64,56 @@ static std::vector<PqQuery> gen_pq_queries() { res.emplace_back(p, q); } } - std::sort(res.begin(), res.end(), cmp); return res; } -static void test_pq(uint64 first, uint64 second) { - BigNum p = BigNum::from_decimal(PSLICE() << first); - BigNum q = BigNum::from_decimal(PSLICE() << second); +static td::string to_binary(td::uint64 x) { + td::string result; + do { + result = static_cast<char>(x & 255) + result; + x >>= 8; + } while (x > 0); + return result; +} + +static void test_pq_fast(td::uint64 first, td::uint64 second) { + if ((static_cast<td::uint64>(1) << 63) / first <= second) { + return; + } + + td::string p_str; + td::string q_str; + int err = td::pq_factorize(to_binary(first * second), &p_str, &q_str); + ASSERT_EQ(err, 0); + + ASSERT_STREQ(p_str, to_binary(first)); + ASSERT_STREQ(q_str, to_binary(second)); +} + +#if TD_HAVE_OPENSSL +static void test_pq_slow(td::uint64 first, td::uint64 second) { + if ((static_cast<td::uint64>(1) << 63) / first > second) { + return; + } + + td::BigNum p = td::BigNum::from_decimal(PSLICE() << first).move_as_ok(); + td::BigNum q = td::BigNum::from_decimal(PSLICE() << second).move_as_ok(); - BigNum pq; - BigNumContext context; - BigNum::mul(pq, p, q, context); - std::string pq_str = pq.to_binary(); + td::BigNum pq; + td::BigNumContext context; + td::BigNum::mul(pq, p, q, context); + td::string pq_str = pq.to_binary(); - std::string p_str, q_str; + td::string p_str; + td::string q_str; int err = td::pq_factorize(pq_str, &p_str, &q_str); - CHECK(err == 0) << first << " * " << second; + LOG_CHECK(err == 0) << first << " * " << second; - BigNum p_res = BigNum::from_binary(p_str); - BigNum q_res = BigNum::from_binary(q_str); + td::BigNum p_res = td::BigNum::from_binary(p_str); + td::BigNum q_res = td::BigNum::from_binary(q_str); - CHECK(p_str == p.to_binary()) << td::tag("got", p_res.to_decimal()) << td::tag("expected", first); - CHECK(q_str == q.to_binary()) << td::tag("got", q_res.to_decimal()) << td::tag("expected", second); + LOG_CHECK(p_str == p.to_binary()) << td::tag("got", p_res.to_decimal()) << td::tag("expected", first); + LOG_CHECK(q_str == q.to_binary()) << td::tag("got", q_res.to_decimal()) << td::tag("expected", second); } #endif @@ -101,18 +128,35 @@ TEST(CryptoPQ, hands) { ASSERT_EQ(179424611ull, td::pq_factorize(179424611ull * 179424673ull)); #if TD_HAVE_OPENSSL - test_pq(4294467311, 4294467449); + test_pq_slow(4294467311, 4294467449); #endif } -#if TD_HAVE_OPENSSL -TEST(CryptoPQ, generated_slow) { +TEST(CryptoPQ, four) { for (int i = 0; i < 100000; i++) { - test_pq(2, 2); + test_pq_fast(2, 2); + } +} + +TEST(CryptoPQ, generated_fast) { + auto queries = gen_pq_queries(); + for (const auto &query : queries) { + test_pq_fast(query.first, query.second); } +} + +TEST(CryptoPQ, generated_server) { + auto queries = gen_pq_queries(1); + for (const auto &query : queries) { + test_pq_fast(query.first, query.second); + } +} + +#if TD_HAVE_OPENSSL +TEST(CryptoPQ, generated_slow) { auto queries = gen_pq_queries(); - for (auto query : queries) { - test_pq(query.first, query.second); + for (const auto &query : queries) { + test_pq_slow(query.first, query.second); } } -#endif
\ No newline at end of file +#endif |