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 // Classes for doing Montgomery modular multiplications using OpenSSL libraries. 17 // Using these classes for modular multiplications is faster than using the 18 // BigNum ModMul when same values are multiplied multiple times. 19 // NOTE: These classes are best suited for computing multiple exponentiations of 20 // a fixed based number ordered by exponents value. For instance computing g^n, 21 // g^(n+1),... in order. For all modular exponentiations with different bases, 22 // BigNum's ModExp using OpenSSL BN_mod_exp would probably be faster since it 23 // also uses Montgomery modular multiplication under the hood. 24 25 #ifndef PRIVATE_JOIN_AND_COMPUTE_CRYPTO_MONT_MUL_H_ 26 #define PRIVATE_JOIN_AND_COMPUTE_CRYPTO_MONT_MUL_H_ 27 28 #include <cstdint> 29 #include <memory> 30 #include <string> 31 32 #include "absl/strings/string_view.h" 33 #include "private_join_and_compute/crypto/big_num.h" 34 #include "private_join_and_compute/crypto/context.h" 35 #include "private_join_and_compute/crypto/openssl.inc" 36 37 namespace private_join_and_compute { 38 39 class MontBigNum { 40 public: 41 // Copies the given MontBigNum. 42 MontBigNum(const MontBigNum& other); 43 MontBigNum& operator=(const MontBigNum& other); 44 45 // Moves the given MontBigNum. 46 MontBigNum(MontBigNum&& other); 47 MontBigNum& operator=(MontBigNum&& other); 48 49 // Multiplies this and mont_big_num in Montgomery form and returns the 50 // resulting MontBigNum. 51 // Fails if mont_big_num is not created with the same MontContext used to 52 // create this MontBigNum. 53 MontBigNum Mul(const MontBigNum& mont_big_num) const; 54 55 // Multiplies this and mont_big_num in Montgomery form and puts the result 56 // into this MontBigNum. 57 // Fails if mont_big_num is not created with the same MontContext used to 58 // create this MontBigNum. 59 MontBigNum& MulInPlace(const MontBigNum& mont_big_num); 60 61 // Overloads *= operator to multiply this with another MontBigNum objects. 62 // Returns a MontBigNum whose value is (a * b). 63 inline MontBigNum& operator*=(const MontBigNum& other) { 64 return this->MulInPlace(other); 65 } 66 67 // Overloads == operator to check for equality. Note there is no CompareTo 68 // method in montgomery form. 69 // Fails if other is not created with the same MontContext used to create this 70 // MontBigNum. 71 bool operator==(const MontBigNum& other) const; 72 73 // Overloads inequality operator. Returns true if two MontBigNums differ. 74 // Fails if other is not created with the same MontContext used to create this 75 // MontBigNum. 76 inline bool operator!=(const MontBigNum& other) const { 77 return !(*this == other); 78 } 79 80 // Computes this^(2^exponent) in Montgomery form and returns the resulting 81 // MontBigNum. 82 MontBigNum PowTo2To(int64_t exponent) const; 83 84 // Serializes this without converting to BigNum. 85 std::string ToBytes() const; 86 87 // Converts this MontBigNum to its original BigNum value. 88 BigNum ToBigNum() const; 89 90 private: 91 // Creates a MontBigNum with the bn that is already in Montgomery form based 92 // on the mont_ctx. Takes the ownership of bn. 93 MontBigNum(Context* ctx, BN_MONT_CTX* mont_ctx, BigNum::BignumPtr bn); 94 95 // Creates a MontBigNum from a byte string. Assumes the serialized number is 96 // in montgomery form already. 97 MontBigNum(Context* ctx, BN_MONT_CTX* mont_ctx, absl::string_view bytes); 98 99 Context* ctx_; 100 BN_MONT_CTX* mont_ctx_; 101 BigNum::BignumPtr bn_; 102 friend class MontContext; 103 }; 104 105 // Overloads * operator to multiply two MontBigNum objects. 106 // Returns a MontBigNum whose value is (a * b). 107 inline MontBigNum operator*(const MontBigNum& a, const MontBigNum& b) { 108 return a.Mul(b); 109 } 110 111 // Factory class for MontBigNum having the BN_MONT_CTX that is used to convert 112 // BigNums into their Montgomery forms based on a fixed modulus. 113 class MontContext { 114 public: 115 // Deletes a BN_MONT_CTX when it goes out of scope. 116 class MontCtxDeleter { 117 public: operator()118 void operator()(BN_MONT_CTX* ctx) { BN_MONT_CTX_free(ctx); } 119 }; 120 typedef std::unique_ptr<BN_MONT_CTX, MontCtxDeleter> MontCtxPtr; 121 122 // Creates a MontBigNum based on the big_num after converting a copy of it. 123 MontBigNum CreateMontBigNum(const BigNum& big_num); 124 125 // Creates a MontBigNum from a byte string that was generated using ToBytes(). 126 // The original MontBigNum's context does not need to be the same as the 127 // current MontContext, as long as their moduli are equal. 128 MontBigNum CreateMontBigNum(absl::string_view bytes); 129 130 // Creates MontContext based on the given modulus. Every operation on the 131 // created MontBigNums using this MontContext will be done with this modulus. 132 MontContext(Context* ctx, const BigNum& modulus); 133 134 // MontContext is neither copyable nor movable. 135 MontContext(const MontContext&) = delete; 136 MontContext& operator=(const MontContext&) = delete; 137 138 private: 139 const BigNum modulus_; 140 Context* const ctx_; 141 MontCtxPtr mont_ctx_; 142 }; 143 144 } // namespace private_join_and_compute 145 146 #endif // PRIVATE_JOIN_AND_COMPUTE_CRYPTO_MONT_MUL_H_ 147