PALISADE Lattice Crypto Library  1.11.9
A lattice crypto library for software engineers by software engineers.
ubintfxd.h
1 // @file ubintfxd.h This file contains the vector manipulation functionality.
2 // @author TPOC: contact@palisade-crypto.org
3 //
4 // @copyright Copyright (c) 2019, New Jersey Institute of Technology (NJIT)
5 // All rights reserved.
6 // Redistribution and use in source and binary forms, with or without
7 // modification, are permitted provided that the following conditions are met:
8 // 1. Redistributions of source code must retain the above copyright notice,
9 // this list of conditions and the following disclaimer.
10 // 2. Redistributions in binary form must reproduce the above copyright notice,
11 // this list of conditions and the following disclaimer in the documentation
12 // and/or other materials provided with the distribution. THIS SOFTWARE IS
13 // PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR
14 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
15 // MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
16 // EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
17 // INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
18 // (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
19 // LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
20 // ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
21 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
22 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
23 /*
24  * This file contains the main class for big integers: BigInteger. Big integers
25  * are represented as arrays of native usigned integers. The native integer type
26  * is supplied as a template parameter. Currently implementations based on
27  * uint8_t, uint16_t, and uint32_t are supported. The second template parameter
28  * is the maximum bitwidth for the big integer.
29  */
30 
31 #ifndef LBCRYPTO_MATH_BIGINTFXD_UBINTFXD_H
32 #define LBCRYPTO_MATH_BIGINTFXD_UBINTFXD_H
33 
34 #include <cstdlib>
35 #include <cstring>
36 #include <fstream>
37 #include <functional>
38 #include <iostream>
39 #include <limits>
40 #include <memory>
41 #include <string>
42 #include <type_traits>
43 #include <typeinfo>
44 #include <vector>
45 #include "utils/exception.h"
46 #include "utils/inttypes.h"
47 #include "utils/memory.h"
48 #include "utils/palisadebase64.h"
49 #include "utils/serializable.h"
50 #include "math/backend.h"
51 
56 namespace bigintfxd {
57 
58 using U64BITS = uint64_t;
59 #if defined(HAVE_INT128)
60 using U128BITS = unsigned __int128;
61 #endif
62 
74 template <usint N>
75 struct Log2 {
76  static const usint value = 1 + Log2<N / 2>::value;
77 };
78 
84 template <>
85 struct Log2<2> {
86  static const usint value = 1;
87 };
88 
95 template <typename U>
96 struct LogDtype {
97  static const usint value = Log2<8 * sizeof(U)>::value;
98 };
99 
106 template <typename Dtype>
108  static const bool value = false;
109 };
110 
115 template <>
116 struct DataTypeChecker<uint8_t> {
117  static const bool value = true;
118 };
119 
124 template <>
125 struct DataTypeChecker<uint16_t> {
126  static const bool value = true;
127 };
128 
133 template <>
134 struct DataTypeChecker<uint32_t> {
135  static const bool value = true;
136 };
137 
142 template <>
143 struct DataTypeChecker<uint64_t> {
144  static const bool value = true;
145 };
146 
153 template <typename uint_type>
154 struct UIntBitWidth {
155  static const int value = 8 * sizeof(uint_type);
156 };
157 
164 template <typename utype>
166  typedef void T;
167 };
168 
173 template <>
174 struct DoubleDataType<uint8_t> {
175  typedef uint16_t T;
176 };
177 
182 template <>
183 struct DoubleDataType<uint16_t> {
184  typedef uint32_t T;
185 };
186 
191 template <>
192 struct DoubleDataType<uint32_t> {
193  typedef uint64_t T;
194 };
195 
200 template <>
201 struct DoubleDataType<uint64_t> {
202 #if defined(HAVE_INT128)
203  typedef __uint128_t T;
204 #else
205  typedef uint64_t T;
206 #endif
207 };
208 
209 const double LOG2_10 =
210  3.32192809;
211 
218 template <typename uint_type, usint BITLENGTH>
220  : public lbcrypto::BigIntegerInterface<BigInteger<uint_type, BITLENGTH>> {
221  public:
222  // CONSTRUCTORS
223 
227  BigInteger();
228 
234  BigInteger(const BigInteger &val);
235 
241  BigInteger(BigInteger &&val);
242 
248  explicit BigInteger(const std::string &strval);
249 
255  BigInteger(uint64_t val);
256 #if defined(HAVE_INT128)
257  BigInteger(U128BITS val);
258 #endif
259 
265  BigInteger(int val) : BigInteger(uint64_t(val)) {}
266  BigInteger(uint32_t val) : BigInteger(uint64_t(val)) {}
267  BigInteger(long val) : BigInteger(uint64_t(val)) {}
268  BigInteger(long long val) : BigInteger(uint64_t(val)) {}
269 
275  template <typename T>
277  : BigInteger(val.ConvertToInt()) {}
278 
284  BigInteger(double val)
285  __attribute__((deprecated("Cannot construct from a double")));
286 
287  ~BigInteger() {}
288 
289  // ASSIGNMENT OPERATORS
290 
297  const BigInteger &operator=(const BigInteger &val);
298 
305  const BigInteger &operator=(BigInteger &&val);
306 
313  const BigInteger &operator=(const std::string strval) {
314  *this = BigInteger(strval);
315  return *this;
316  }
317 
324  const BigInteger &operator=(uint64_t val) {
325  *this = BigInteger(val);
326  return *this;
327  }
328 
336  *this = BigInteger(val);
337  return *this;
338  }
339 
340  // ACCESSORS
341 
348  void SetValue(const std::string &strval);
349 
356  void SetValue(const BigInteger &val);
357 
361  void SetIdentity() { *this = 1; }
362 
368  void SetIntAtIndex(usint idx, uint_type value);
369 
370  // ARITHMETIC OPERATIONS
371 
378  BigInteger Add(const BigInteger &b) const;
379 
386  const BigInteger &AddEq(const BigInteger &b);
387 
394  BigInteger Sub(const BigInteger &b) const;
395 
402  const BigInteger &SubEq(const BigInteger &b);
403 
408  BigInteger operator-() const { return BigInteger(0).Sub(*this); }
409 
416  BigInteger Mul(const BigInteger &b) const;
417 
424  const BigInteger &MulEq(const BigInteger &b);
425 
432  BigInteger DividedBy(const BigInteger &b) const;
433 
440  const BigInteger &DividedByEq(const BigInteger &b);
441 
448  BigInteger Exp(usint p) const;
449 
456  const BigInteger &ExpEq(usint p);
457 
466  BigInteger MultiplyAndRound(const BigInteger &p, const BigInteger &q) const;
467 
476  const BigInteger &MultiplyAndRoundEq(const BigInteger &p,
477  const BigInteger &q);
478 
486  BigInteger DivideAndRound(const BigInteger &q) const;
487 
495  const BigInteger &DivideAndRoundEq(const BigInteger &q);
496 
497  // MODULAR ARITHMETIC OPERATIONS
498 
505  BigInteger Mod(const BigInteger &modulus) const;
506 
513  const BigInteger &ModEq(const BigInteger &modulus);
514 
520  BigInteger ComputeMu() const;
521 
531  BigInteger Mod(const BigInteger &modulus, const BigInteger &mu) const;
532 
542  const BigInteger &ModEq(const BigInteger &modulus, const BigInteger &mu);
543 
551  BigInteger ModAdd(const BigInteger &b, const BigInteger &modulus) const;
552 
560  const BigInteger &ModAddEq(const BigInteger &b, const BigInteger &modulus);
561 
569  BigInteger ModAddFast(const BigInteger &b, const BigInteger &modulus) const;
570 
578  const BigInteger &ModAddFastEq(const BigInteger &b,
579  const BigInteger &modulus);
580 
589  BigInteger ModAdd(const BigInteger &b, const BigInteger &modulus,
590  const BigInteger &mu) const;
591 
600  const BigInteger &ModAddEq(const BigInteger &b, const BigInteger &modulus,
601  const BigInteger &mu);
602 
610  BigInteger ModSub(const BigInteger &b, const BigInteger &modulus) const;
611 
619  const BigInteger &ModSubEq(const BigInteger &b, const BigInteger &modulus);
620 
628  BigInteger ModSubFast(const BigInteger &b, const BigInteger &modulus) const;
629 
637  const BigInteger &ModSubFastEq(const BigInteger &b,
638  const BigInteger &modulus);
639 
648  BigInteger ModSub(const BigInteger &b, const BigInteger &modulus,
649  const BigInteger &mu) const;
650 
659  const BigInteger &ModSubEq(const BigInteger &b, const BigInteger &modulus,
660  const BigInteger &mu);
661 
669  BigInteger ModMul(const BigInteger &b, const BigInteger &modulus) const;
670 
678  const BigInteger &ModMulEq(const BigInteger &b, const BigInteger &modulus);
679 
688  BigInteger ModMul(const BigInteger &b, const BigInteger &modulus,
689  const BigInteger &mu) const;
690 
699  const BigInteger &ModMulEq(const BigInteger &b, const BigInteger &modulus,
700  const BigInteger &mu);
701 
709  BigInteger ModMulFast(const BigInteger &b, const BigInteger &modulus) const;
710 
719  const BigInteger &ModMulFastEq(const BigInteger &b,
720  const BigInteger &modulus);
721 
730  BigInteger ModMulFast(const BigInteger &b, const BigInteger &modulus,
731  const BigInteger &mu) const;
732 
742  const BigInteger &ModMulFastEq(const BigInteger &b, const BigInteger &modulus,
743  const BigInteger &mu);
744 
745  BigInteger ModMulFastConst(const BigInteger &b, const BigInteger &modulus,
746  const BigInteger &bInv) const {
747  PALISADE_THROW(lbcrypto::not_implemented_error,
748  "ModMulFastConst is not implemented for backend 2");
749  }
750 
751  const BigInteger &ModMulFastConstEq(const BigInteger &b,
752  const BigInteger &modulus,
753  const BigInteger &bInv) {
754  PALISADE_THROW(lbcrypto::not_implemented_error,
755  "ModMulFastConstEq is not implemented for backend 2");
756  }
757 
765  BigInteger ModExp(const BigInteger &b, const BigInteger &modulus) const;
766 
775  const BigInteger &ModExpEq(const BigInteger &b, const BigInteger &modulus);
776 
783  BigInteger ModInverse(const BigInteger &modulus) const;
784 
791  const BigInteger &ModInverseEq(const BigInteger &modulus);
792 
793  // SHIFT OPERATIONS
794 
801  BigInteger LShift(usshort shift) const;
802 
809  const BigInteger &LShiftEq(usshort shift);
810 
817  BigInteger RShift(usshort shift) const;
818 
825  const BigInteger &RShiftEq(usshort shift);
826 
827  // COMPARE
828 
836  int Compare(const BigInteger &a) const;
837 
838  // CONVERTERS
839 
845  template <typename T = bigintnat::BasicInteger>
846  T ConvertToInt() const {
847  T result = 0;
848  // set num to number of equisized chunks
849  // usint num = bigintnat::NativeIntegerT<T>::MaxBits() / m_uintBitLength;
850  usint num = bigintnat::NativeIntegerT<T>().MaxBits() / m_uintBitLength;
851  usint ceilInt = m_nSize - ceilIntByUInt(m_MSB);
852  // copy the values by shift and add
853  for (usint i = 0; i < num && (m_nSize - i - 1) >= ceilInt; i++) {
854  result += ((T)this->m_value[m_nSize - i - 1] << (m_uintBitLength * i));
855  }
856  if (this->m_MSB > bigintnat::NativeIntegerT<T>::MaxBits()) {
857  PALISADE_THROW(
859  std::string("MSB cannot be bigger than ") +
860  std::to_string(bigintnat::NativeIntegerT<T>::MaxBits()));
861  }
862  return result;
863  }
864 
870  double ConvertToDouble() const;
871 
878  static BigInteger intToBigInteger(usint m);
879 
886  static BigInteger FromBinaryString(const std::string &bitString);
887 
888  // OTHER FUNCTIONS
889 
895  usint GetMSB() const;
896 
904  usint GetLengthForBase(usint base) const { return GetMSB(); }
905 
920  usint GetDigitAtIndexForBase(usint index, usint base) const;
921 
928  bool CheckIfPowerOfTwo(const BigInteger &m_numToCheck);
929 
936  uschar GetBitAtIndex(usint index) const;
937 
942  static BigInteger Allocator() { return 0; }
943 
944  // STRINGS & STREAMS
945 
952  const std::string ToString() const;
953 
954  static const std::string IntegerTypeName() { return "UBFIXINT"; }
955 
961  std::string GetInternalRepresentation(void) const {
962  std::string ret("");
963  size_t ceilInt = ceilIntByUInt(this->m_MSB); // max limb used
964 
965  for (size_t i = m_nSize - 1; i >= (size_t)(m_nSize - ceilInt); i--) {
966  ret += std::to_string(m_value[i]);
967  if (i != (size_t)(m_nSize - ceilInt)) ret += " ";
968  }
969  return ret;
970  }
971 
979  template <typename uint_type_c, usint BITLENGTH_c>
980  friend std::ostream &operator<<(
981  std::ostream &os, const BigInteger<uint_type_c, BITLENGTH_c> &ptr_obj) {
982  usint counter;
983  // initiate to object to be printed
984  auto print_obj = new BigInteger<uint_type_c, BITLENGTH_c>(ptr_obj);
985  // print_VALUE array stores the decimal value in the array
986  uschar *print_VALUE = new uschar[ptr_obj.m_numDigitInPrintval];
987  for (size_t i = 0; i < ptr_obj.m_numDigitInPrintval; i++) {
988  // reset to zero
989  *(print_VALUE + i) = 0;
990  }
991  // starts the conversion from base r to decimal value
992  for (size_t i = print_obj->m_MSB; i > 0; i--) {
993  // print_VALUE = print_VALUE*2
995  // adds the bit value to the print_VALUE
997  print_VALUE, print_obj->GetBitAtIndex(i));
998  }
999  // find the first occurence of non-zero value in print_VALUE
1000  for (counter = 0; counter < ptr_obj.m_numDigitInPrintval - 1; counter++) {
1001  if (static_cast<int>(print_VALUE[counter]) != 0) {
1002  break;
1003  }
1004  }
1005  // start inserting values into the ostream object
1006  for (; counter < ptr_obj.m_numDigitInPrintval; counter++) {
1007  os << static_cast<int>(print_VALUE[counter]);
1008  }
1009  // deallocate the memory since values are inserted into the ostream object
1010  delete[] print_VALUE;
1011  delete print_obj;
1012  return os;
1013  }
1014 
1015  // SERIALIZATION
1016 
1017  template <class Archive>
1018  typename std::enable_if<!cereal::traits::is_text_archive<Archive>::value,
1019  void>::type
1020  save(Archive &ar, std::uint32_t const version) const {
1021  ar(::cereal::binary_data(m_value, sizeof(m_value)));
1022  ar(::cereal::binary_data(&m_MSB, sizeof(m_MSB)));
1023  }
1024 
1025  template <class Archive>
1026  typename std::enable_if<cereal::traits::is_text_archive<Archive>::value,
1027  void>::type
1028  save(Archive &ar, std::uint32_t const version) const {
1029  ar(::cereal::make_nvp("v", m_value));
1030  ar(::cereal::make_nvp("m", m_MSB));
1031  }
1032 
1033  template <class Archive>
1034  typename std::enable_if<!cereal::traits::is_text_archive<Archive>::value,
1035  void>::type
1036  load(Archive &ar, std::uint32_t const version) {
1037  if (version > SerializedVersion()) {
1038  PALISADE_THROW(lbcrypto::deserialize_error,
1039  "serialized object version " + std::to_string(version) +
1040  " is from a later version of the library");
1041  }
1042  ar(::cereal::binary_data(m_value, sizeof(m_value)));
1043  ar(::cereal::binary_data(&m_MSB, sizeof(m_MSB)));
1044  }
1045 
1046  template <class Archive>
1047  typename std::enable_if<cereal::traits::is_text_archive<Archive>::value,
1048  void>::type
1049  load(Archive &ar, std::uint32_t const version) {
1050  if (version > SerializedVersion()) {
1051  PALISADE_THROW(lbcrypto::deserialize_error,
1052  "serialized object version " + std::to_string(version) +
1053  " is from a later version of the library");
1054  }
1055  ar(::cereal::make_nvp("v", m_value));
1056  ar(::cereal::make_nvp("m", m_MSB));
1057  }
1058 
1059  std::string SerializedObjectName() const { return "FXDInteger"; }
1060 
1061  static uint32_t SerializedVersion() { return 1; }
1062 
1063  protected:
1070  void AssignVal(const std::string &v);
1071 
1075  void SetMSB();
1076 
1081  void SetMSB(usint guessIdxChar);
1082 
1083  private:
1084  // array storing the native integers.
1085  // array size is the ceiling of BITLENGTH/(bits in the integral data type)
1086  uint_type m_value[(BITLENGTH + 8 * sizeof(uint_type) - 1) /
1087  (8 * sizeof(uint_type))];
1088 
1089  // variable that stores the MOST SIGNIFICANT BIT position in the number.
1090  usshort m_MSB;
1091 
1092  // variable to store the bit width of the integral data type.
1093  static const uschar m_uintBitLength;
1094 
1095  // variable to store the maximum value of the integral data type.
1096  static const uint_type m_uintMax;
1097 
1098  // variable to store the log(base 2) of the number of bits in the integral
1099  // data type.
1100  static const uschar m_logUintBitLength;
1101 
1102  // variable to store the size of the data array.
1103  static const usint m_nSize;
1104 
1105  // The maximum number of digits in BigInteger. It is used by the cout(ostream)
1106  // function for printing the bigbinarynumber.
1107  static const usint m_numDigitInPrintval;
1108 
1115  static uint_type ceilIntByUInt(const uint_type Number);
1116 
1117  // currently unused array
1118  static const BigInteger *m_modChain;
1119 
1126  static usint GetMSBUint_type(uint_type x);
1127 
1128  // Duint_type is the data type that has twice as many bits in the integral
1129  // data type.
1130  typedef typename DoubleDataType<uint_type>::T Duint_type;
1131 
1137  static usint GetMSBDUint_type(Duint_type x);
1138 
1144  BigInteger MulByUint(const uint_type b) const;
1145 
1151  void MulByUintToInt(const uint_type b, BigInteger *ans) const;
1152 
1158  static uint_type UintInBinaryToDecimal(uschar *a);
1159 
1164  static void double_bitVal(uschar *a);
1165 
1171  static void add_bitVal(uschar *a, uschar b);
1172 };
1173 
1175 
1176 } // namespace bigintfxd
1177 
1178 #endif // LBCRYPTO_MATH_BIGINTFXD_UBINTFXD_H
const BigInteger & operator=(uint64_t val)
Definition: ubintfxd.h:324
std::string GetInternalRepresentation(void) const
Definition: ubintfxd.h:961
static BigInteger Allocator()
Definition: ubintfxd.h:942
BigInteger(int val)
Definition: ubintfxd.h:265
Definition: exception.h:119
friend std::ostream & operator<<(std::ostream &os, const BigInteger< uint_type_c, BITLENGTH_c > &ptr_obj)
Definition: ubintfxd.h:980
Definition: exception.h:147
const BigInteger & operator=(const std::string strval)
Definition: ubintfxd.h:313
Definition: exception.h:113
const double LOG2_10
A pre-computed constant of Log base 2 of 10.
Definition: ubintfxd.h:209
T ConvertToInt() const
Definition: ubintfxd.h:846
uschar GetBitAtIndex(usint index) const
Definition: ubintfxd.cpp:1671
Struct for validating if Dtype is amongst {uint8_t, uint16_t, uint32_t}.
Definition: ubintfxd.h:107
Main class for big integers represented as an array of native (primitive) unsigned integers...
Definition: ubintfxd.h:219
Struct for calculating bit width from data type. Sets value to the bitwidth of uint_type.
Definition: ubintfxd.h:154
void SetIdentity()
Definition: ubintfxd.h:361
Struct to find log value of U where U is a primitive datatype. Needed in the preprocessing step of Bi...
Definition: ubintfxd.h:96
const BigInteger & operator=(const bigintnat::NativeInteger &val)
Definition: ubintfxd.h:335
Struct to determine a datatype that is twice as big(bitwise) as utype. sets T as of type void for def...
Definition: ubintfxd.h:165
usint GetLengthForBase(usint base) const
Definition: ubintfxd.h:904
BigInteger(const bigintnat::NativeIntegerT< T > &val)
Definition: ubintfxd.h:276
Struct to find log value of N. Needed in the preprocessing step of BigInteger to determine bitwidth...
Definition: ubintfxd.h:75
Definition: interface.h:33
BigInteger operator-() const
Definition: ubintfxd.h:408
Main class for big integers represented as an array of native (primitive) unsigned integers...
Definition: backend.h:60
BigInteger Sub(const BigInteger &b) const
Definition: ubintfxd.cpp:320