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 #include "private_join_and_compute/crypto/shanks_discrete_log.h"
17
18 #include <map>
19 #include <memory>
20 #include <string>
21 #include <utility>
22
23 #include "absl/status/statusor.h"
24 #include "absl/strings/str_cat.h"
25 #include "private_join_and_compute/util/status.inc"
26
27 namespace private_join_and_compute {
28
29 // The maximum number of bits in the message (exponent).
30 const int ShanksDiscreteLog::kMaxMessageSize = 40;
31
ShanksDiscreteLog(private_join_and_compute::Context * ctx,const private_join_and_compute::ECGroup * group,std::unique_ptr<private_join_and_compute::ECPoint> generator,int max_message_bits,int precompute_bits,std::map<std::string,int> precomputed_table)32 ShanksDiscreteLog::ShanksDiscreteLog(
33 private_join_and_compute::Context* ctx,
34 const private_join_and_compute::ECGroup* group,
35 std::unique_ptr<private_join_and_compute::ECPoint> generator,
36 int max_message_bits, int precompute_bits,
37 std::map<std::string, int> precomputed_table)
38 : ctx_(ctx),
39 generator_(std::move(generator)),
40 max_message_bits_(max_message_bits),
41 precompute_bits_(precompute_bits),
42 precomputed_table_(std::move(precomputed_table)) {}
43
PrecomputeTable(const private_join_and_compute::ECGroup * group,const private_join_and_compute::ECPoint * generator,int precompute_bits)44 absl::StatusOr<std::map<std::string, int>> ShanksDiscreteLog::PrecomputeTable(
45 const private_join_and_compute::ECGroup* group,
46 const private_join_and_compute::ECPoint* generator, int precompute_bits) {
47 std::map<std::string, int> table;
48 ASSIGN_OR_RETURN(auto point, group->GetPointAtInfinity());
49 // Cannot encode point at infinity to bytes.
50 for (int i = 1; i < (1 << precompute_bits); ++i) {
51 ASSIGN_OR_RETURN(point, generator->Add(point));
52 ASSIGN_OR_RETURN(auto bytes, point.ToBytesCompressed());
53 table.insert(std::pair<std::string, int>(bytes, i));
54 }
55 return table;
56 }
57
Create(private_join_and_compute::Context * ctx,const private_join_and_compute::ECGroup * group,const private_join_and_compute::ECPoint * generator,int max_message_bits,int precompute_bits)58 absl::StatusOr<std::unique_ptr<ShanksDiscreteLog>> ShanksDiscreteLog::Create(
59 private_join_and_compute::Context* ctx,
60 const private_join_and_compute::ECGroup* group,
61 const private_join_and_compute::ECPoint* generator, int max_message_bits,
62 int precompute_bits) {
63 if (max_message_bits <= precompute_bits) {
64 return absl::InvalidArgumentError(
65 "Precompute bits should be at most the maximum message size.");
66 }
67 if (max_message_bits > kMaxMessageSize) {
68 return absl::InvalidArgumentError(
69 absl::StrCat("Maximum number of message bits should be at most ",
70 kMaxMessageSize, "."));
71 }
72 ASSIGN_OR_RETURN(auto generator_clone, generator->Clone());
73 auto generator_ptr = std::make_unique<private_join_and_compute::ECPoint>(
74 std::move(generator_clone));
75 ASSIGN_OR_RETURN(auto table,
76 PrecomputeTable(group, generator, precompute_bits));
77 return absl::WrapUnique<ShanksDiscreteLog>(new ShanksDiscreteLog(
78 ctx, group, std::move(generator_ptr), max_message_bits, precompute_bits,
79 std::move(table)));
80 }
81
GetDiscreteLog(const private_join_and_compute::ECPoint & point)82 absl::StatusOr<int64_t> ShanksDiscreteLog::GetDiscreteLog(
83 const private_join_and_compute::ECPoint& point) {
84 ASSIGN_OR_RETURN(auto inverse, generator_->Inverse());
85 ASSIGN_OR_RETURN(auto baby_step,
86 inverse.Mul(ctx_->CreateBigNum(1 << precompute_bits_)));
87 ASSIGN_OR_RETURN(auto current_state, point.Clone());
88 // Create guarantees that max_message_bits_ >= precompute_bits_.
89 for (int i = 0; i < (1 << (max_message_bits_ - precompute_bits_)); ++i) {
90 // Infinity cannot be encoded as bytes, so we explcitly check for infinity
91 // in precomputed table.
92 if (current_state.IsPointAtInfinity()) {
93 int64_t shift = 1;
94 shift <<= precompute_bits_;
95 return shift * i;
96 }
97 ASSIGN_OR_RETURN(auto bytes, current_state.ToBytesCompressed());
98 auto iter = precomputed_table_.find(bytes);
99 if (iter != precomputed_table_.end()) {
100 int64_t shift = 1;
101 shift <<= precompute_bits_;
102 shift *= i;
103 return shift + iter->second;
104 }
105 ASSIGN_OR_RETURN(current_state, current_state.Add(baby_step));
106 }
107 return absl::InvalidArgumentError(
108 "Could not find discrete log. Exponent larger than specified max size.");
109 }
110
111 } // namespace private_join_and_compute
112