1 /* 2 * Copyright 2019 Google LLC. 3 * Licensed under the Apache License, Version 2.0 (the "License"); 4 * you may not use this file except in compliance with the License. 5 * You may obtain a copy of the License at 6 * 7 * https://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software 10 * distributed under the License is distributed on an "AS IS" BASIS, 11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 * See the License for the specific language governing permissions and 13 * limitations under the License. 14 */ 15 16 // Implementation of discrete log algorithm. 17 // 18 // To solve discrete logarithms, we use the Baby Step, Giant Step algorithm 19 // (also known as Shanks algorithm). For a full description, see [1]. 20 // 21 // This class will construct a table of precomputed values, which depend 22 // on the generator and the percompute_bits argument. The precomputed table 23 // can be reused to perform multiple discrete logarithms for the same generator. 24 // 25 // [1] https://en.wikipedia.org/wiki/Baby-step_giant-step 26 27 #ifndef CRYPTO_SHANKS_DISCRETE_LOG_H_ 28 #define CRYPTO_SHANKS_DISCRETE_LOG_H_ 29 30 #include <map> 31 #include <memory> 32 #include <string> 33 34 #include "absl/status/statusor.h" 35 #include "private_join_and_compute/crypto/big_num.h" 36 #include "private_join_and_compute/crypto/ec_group.h" 37 #include "private_join_and_compute/crypto/ec_point.h" 38 #include "private_join_and_compute/crypto/elgamal.h" 39 40 namespace private_join_and_compute { 41 42 class ShanksDiscreteLog { 43 public: 44 // Constructs an object that can solve discrete logs with respect to the 45 // input generator. 46 // 47 // The max_message_bits parameter means the object can solve discrete logs for 48 // exponents with at most max_message_bits. 49 // 50 // The precompute_bits parameter means that a precomputed table will be 51 // constructed for the first precompute_bits. In particular, the precomputed 52 // table will hold O(2^(precompute_bits)) entries, which requires 53 // O(2^(precompute_bits)) elliptic curve additions to construct. 54 // 55 // Afterwards, discrete logarithm computation requires at most 56 // O(2^(max_message_bits - precompute_bits)) elliptic curve additions. 57 // 58 // Returns INVALID_ARGUMENT when max_message_bits is strictly greater than 40 59 // or precompute_bits is strictly greater than max_message_bits. 60 // Returns INTERNAL on internal cryptographic errors. 61 static absl::StatusOr<std::unique_ptr<ShanksDiscreteLog>> Create( 62 private_join_and_compute::Context* ctx, 63 const private_join_and_compute::ECGroup* group, 64 const private_join_and_compute::ECPoint* generator, int max_message_bits, 65 int precompute_bits); 66 67 // ShanksDiscreteLog is neither copyable nor copy assignable. 68 ShanksDiscreteLog(const ShanksDiscreteLog&) = delete; 69 ShanksDiscreteLog& operator=(const ShanksDiscreteLog&) = delete; 70 71 // GetDiscreteLog returns INVALID_ARGUMENT when point = g^x where x has 72 // strictly more than max_message_bits_ bits. Also, returns INTERNAL 73 // on internal cryptographic errors. 74 absl::StatusOr<int64_t> GetDiscreteLog( 75 const private_join_and_compute::ECPoint& point); 76 77 // Maxmium message size in bits. 78 static const int kMaxMessageSize; 79 80 private: 81 ShanksDiscreteLog( 82 private_join_and_compute::Context* ctx, 83 const private_join_and_compute::ECGroup* group, 84 std::unique_ptr<private_join_and_compute::ECPoint> generator, 85 int max_message_bits, int precompute_bits, 86 std::map<std::string, int> precomputed_table); 87 88 // Constructs a map such that the pair (g^i, i) appears 89 // for all i = 0, ..., 2^(precompute_bits). 90 static absl::StatusOr<std::map<std::string, int>> PrecomputeTable( 91 const private_join_and_compute::ECGroup* group, 92 const private_join_and_compute::ECPoint* generator, int precompute_bits); 93 94 private_join_and_compute::Context* const ctx_; 95 const std::unique_ptr<private_join_and_compute::ECPoint> generator_; 96 const int max_message_bits_; 97 const int precompute_bits_; 98 99 const std::map<std::string, int> precomputed_table_; 100 }; 101 102 } // namespace private_join_and_compute 103 104 #endif // CRYPTO_SHANKS_DISCRETE_LOG_H_ 105