ubintntl.h

// @file ubintntl.h  This file contains the C++ code for implementing the main
// class for big integers: gmpint which replaces BBI and uses NTL
// @author TPOC: contact@palisade-crypto.org
//
// @copyright Copyright (c) 2019, New Jersey Institute of Technology (NJIT)
// All rights reserved.
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
// 1. Redistributions of source code must retain the above copyright notice,
// this list of conditions and the following disclaimer.
// 2. Redistributions in binary form must reproduce the above copyright notice,
// this list of conditions and the following disclaimer in the documentation
// and/or other materials provided with the distribution. THIS SOFTWARE IS
// PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR
// IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
// MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
// EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
// INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
// (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
// LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
// ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#ifndef LBCRYPTO_MATH_BIGINTNTL_UBINTNTL_H
#define LBCRYPTO_MATH_BIGINTNTL_UBINTNTL_H

#include "config_core.h"
#ifdef WITH_NTL

#include <NTL/ZZ.h>
#include <NTL/ZZ_limbs.h>

#include <exception>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <memory>
#include <string>
#include <type_traits>
#include <typeinfo>
#include <vector>

#include "utils/exception.h"
#include "utils/inttypes.h"
#include "utils/memory.h"

#include "utils/debug.h"

namespace NTL {
// log2 constants
template <usint N>
struct Log2 {
  static const usint value = 1 + Log2<N / 2>::value;
};

template <>
struct Log2<2> {
  static const usint value = 1;
};

class myZZ : public NTL::ZZ, public lbcrypto::BigIntegerInterface<myZZ> {
 public:
  // CONSTRUCTORS

  myZZ();

  myZZ(const NTL::ZZ &val);

  myZZ(NTL::ZZ &&val);

  // TODO: figure out how to do && for wrapper
  // myZZ(NTL::myZZ_p &&a);

  explicit myZZ(const std::string &strval);

  myZZ(uint64_t val);
#if defined(HAVE_INT128)
  myZZ(unsigned __int128 val);
#endif

  myZZ(int val) : myZZ(uint64_t(val)) {}
  myZZ(uint32_t val) : myZZ(uint64_t(val)) {}
  myZZ(long val) : myZZ(uint64_t(val)) {}
  myZZ(long long val) : myZZ(uint64_t(val)) {}

  template <typename T>
  myZZ(const bigintnat::NativeIntegerT<T> &val) : myZZ(val.ConvertToInt()) {}

  myZZ(double val)
      __attribute__((deprecated("Cannot construct from a double")));

  // ASSIGNMENT OPERATORS

  const myZZ &operator=(const myZZ &val);

  // TODO move assignment operator?

  inline const myZZ &operator=(std::string strval) {
    *this = myZZ(strval);
    return *this;
  }

  const myZZ &operator=(uint64_t val) {
    *this = myZZ(val);
    return *this;
  }

  // ACCESSORS

  void SetValue(const std::string &strval);

  void SetValue(const myZZ &val);

  void SetIdentity() { *this = 1; }

  // ARITHMETIC OPERATIONS

  myZZ Add(const myZZ &b) const {
    return *static_cast<const ZZ *>(this) + static_cast<const ZZ &>(b);
  }

  const myZZ &AddEq(const myZZ &b) {
    *static_cast<ZZ *>(this) += static_cast<const ZZ &>(b);
    return *this;
  }

  myZZ Sub(const myZZ &b) const {
    return (*this < b)
               ? ZZ(0)
               : (*static_cast<const ZZ *>(this) - static_cast<const ZZ &>(b));
  }

  const myZZ &SubEq(const myZZ &b) {
    if (*this < b) {
      *this = ZZ(0);
    } else {
      *static_cast<ZZ *>(this) -= static_cast<const ZZ &>(b);
    }
    return *this;
  }

  myZZ Mul(const myZZ &b) const {
    return *static_cast<const ZZ *>(this) * static_cast<const ZZ &>(b);
  }

  const myZZ &MulEq(const myZZ &b) {
    *static_cast<ZZ *>(this) *= static_cast<const ZZ &>(b);
    return *this;
  }

  myZZ DividedBy(const myZZ &b) const {
    return *static_cast<const ZZ *>(this) / static_cast<const ZZ &>(b);
  }

  const myZZ &DividedByEq(const myZZ &b) {
    *static_cast<ZZ *>(this) /= static_cast<const ZZ &>(b);
    return *this;
  }

  myZZ Exp(const usint p) const { return power(*this, p); }

  const myZZ &ExpEq(const usint p) {
    *this = power(*this, p);
    return *this;
  }

  myZZ MultiplyAndRound(const myZZ &p, const myZZ &q) const;

  const myZZ &MultiplyAndRoundEq(const myZZ &p, const myZZ &q);

  myZZ DivideAndRound(const myZZ &q) const;

  const myZZ &DivideAndRoundEq(const myZZ &q);

  // MODULAR ARITHMETIC OPERATIONS

  myZZ Mod(const myZZ &modulus) const {
    return *static_cast<const ZZ *>(this) % static_cast<const ZZ &>(modulus);
  }

  const myZZ &ModEq(const myZZ &modulus) {
    *static_cast<ZZ *>(this) %= static_cast<const ZZ &>(modulus);
    return *this;
  }

  myZZ ComputeMu() const {
    myZZ temp(1);
    temp <<= (2 * this->GetMSB() + 3);
    return temp.DividedBy(*this);
    return temp;
  }

  myZZ Mod(const myZZ &modulus, const myZZ &mu) const {
    return *static_cast<const ZZ *>(this) % static_cast<const ZZ &>(modulus);
  }

  const myZZ &ModEq(const myZZ &modulus, const myZZ &mu) {
    *static_cast<ZZ *>(this) %= static_cast<const ZZ &>(modulus);
    return *this;
  }

  myZZ ModAdd(const myZZ &b, const myZZ &modulus) const {
    return AddMod(this->Mod(modulus), b.Mod(modulus), modulus);
  }

  const myZZ &ModAddEq(const myZZ &b, const myZZ &modulus) {
    AddMod(*this, this->Mod(modulus), b.Mod(modulus), modulus);
    return *this;
  }

  myZZ ModAddFast(const myZZ &b, const myZZ &modulus) const {
    return AddMod(*this, b, modulus);
  }

  const myZZ &ModAddFastEq(const myZZ &b, const myZZ &modulus) {
    *this = AddMod(*this, b, modulus);
    return *this;
  }

  myZZ ModAdd(const myZZ &b, const myZZ &modulus, const myZZ &mu) const {
    return AddMod(*this, b, modulus);
  }

  const myZZ &ModAddEq(const myZZ &b, const myZZ &modulus, const myZZ &mu) {
    *this = AddMod(*this, b, modulus);
    return *this;
  }

  myZZ ModSub(const myZZ &b, const myZZ &modulus) const {
    myZZ newthis(*this % modulus);
    myZZ newb(b % modulus);
    if (newthis >= newb) {
      myZZ tmp(SubMod(newthis, newb, modulus));  // normal mod sub
      return tmp;
    } else {
      myZZ tmp(newthis + modulus - newb);  // signed mod
      return tmp;
    }
  }

  const myZZ &ModSubEq(const myZZ &b, const myZZ &modulus) {
    this->ModEq(modulus);
    myZZ newb(b % modulus);
    if (*this >= newb) {
      SubMod(*this, *this, newb, modulus);  // normal mod sub
      return *this;
    } else {
      this->AddEq(modulus);
      this->SubEq(newb);  // signed mod
      return *this;
    }
  }

  myZZ ModSubFast(const myZZ &b, const myZZ &modulus) const {
    if (*this >= b) {
      return SubMod(*this, b, modulus);  // normal mod sub
    } else {
      return (*this + modulus - b);  // signed mod
    }
  }

  const myZZ &ModSubFastEq(const myZZ &b, const myZZ &modulus) {
    if (*this >= b) {
      return *this = SubMod(*this, b, modulus);  // normal mod sub
    } else {
      return *this = (*this + modulus - b);  // signed mod
    }
  }

  myZZ ModSub(const myZZ &b, const myZZ &modulus, const myZZ &mu) const {
    myZZ newthis(*this % modulus);
    myZZ newb(b % modulus);
    if (newthis >= newb) {
      myZZ tmp(SubMod(newthis, newb, modulus));  // normal mod sub
      return tmp;
    } else {
      myZZ tmp(newthis + modulus - newb);  // signed mod
      return tmp;
    }
  }

  const myZZ &ModSubEq(const myZZ &b, const myZZ &modulus, const myZZ &mu) {
    this->ModEq(modulus);
    myZZ newb(b % modulus);
    if (*this >= newb) {
      SubMod(*this, *this, newb, modulus);  // normal mod sub
      return *this;
    } else {
      this->AddEq(modulus);
      this->SubEq(newb);  // signed mod
      return *this;
    }
  }

  myZZ ModMul(const myZZ &b, const myZZ &modulus) const {
    return MulMod(this->Mod(modulus), b.Mod(modulus), modulus);
  }

  const myZZ &ModMulEq(const myZZ &b, const myZZ &modulus) {
    MulMod(*this, this->Mod(modulus), b.Mod(modulus), modulus);
    return *this;
  }

  myZZ ModMul(const myZZ &b, const myZZ &modulus, const myZZ &mu) const {
    return MulMod(this->Mod(modulus), b.Mod(modulus), modulus);
  }

  const myZZ &ModMulEq(const myZZ &b, const myZZ &modulus, const myZZ &mu) {
    MulMod(*this, this->Mod(modulus), b.Mod(modulus), modulus);
    return *this;
  }

  inline myZZ ModMulFast(const myZZ &b, const myZZ &modulus) const {
    return MulMod(*this, b, modulus);
  }

  const myZZ &ModMulFastEq(const myZZ &b, const myZZ &modulus) {
    *this = MulMod(*this, b, modulus);
    return *this;
  }

  inline myZZ ModMulFast(const myZZ &b, const myZZ &modulus,
                         const myZZ &mu) const {
    return MulMod(*this, b, modulus);
  }

  const myZZ &ModMulFastEq(const myZZ &b, const myZZ &modulus, const myZZ &mu) {
    *this = MulMod(*this, b, modulus);
    return *this;
  }

  myZZ ModMulFastConst(const myZZ &b, const myZZ &modulus,
                       const myZZ &bInv) const {
    PALISADE_THROW(lbcrypto::not_implemented_error,
                   "ModMulFastConst is not implemented for backend 6");
  }

  const myZZ &ModMulFastConstEq(const myZZ &b, const myZZ &modulus,
                                const myZZ &bInv) {
    PALISADE_THROW(lbcrypto::not_implemented_error,
                   "ModMulFastConstEq is not implemented for backend 6");
  }

  inline myZZ ModExp(const myZZ &b, const myZZ &modulus) const {
    myZZ res;
    PowerMod(res, *this, b, modulus);
    return res;
  }

  const myZZ &ModExpEq(const myZZ &b, const myZZ &modulus) {
    PowerMod(*this, *this, b, modulus);
    return *this;
  }

  myZZ ModInverse(const myZZ &modulus) const {
    if (modulus == myZZ(0)) {
      PALISADE_THROW(lbcrypto::math_error, "zero has no inverse");
    }
    myZZ tmp(0);
    try {
      tmp = InvMod(*this % modulus, modulus);
    } catch (InvModErrorObject
                 &e) {  // note this code requires NTL Excptions coto be turned
                        // on. TODO: provide alternative when that is off.
      std::stringstream errmsg;
      errmsg << "ModInverse exception "
             << " this: " << *this << " modulus: " << modulus << "GCD("
             << e.get_a() << "," << e.get_n() << "!=1" << std::endl;
      PALISADE_THROW(lbcrypto::math_error, errmsg.str());
    }
    return tmp;
  }

  const myZZ &ModInverseEq(const myZZ &modulus) {
    if (modulus == myZZ(0)) {
      PALISADE_THROW(lbcrypto::math_error, "zero has no inverse");
    }
    try {
      *this = InvMod(*this % modulus, modulus);
    } catch (InvModErrorObject
                 &e) {  // note this code requires NTL Excptions coto be turned
                        // on. TODO: provide alternative when that is off.
      std::stringstream errmsg;
      errmsg << "ModInverse exception "
             << " this: " << *this << " modulus: " << modulus << "GCD("
             << e.get_a() << "," << e.get_n() << "!=1" << std::endl;
      PALISADE_THROW(lbcrypto::math_error, errmsg.str());
    }
    return *this;
  }

  myZZ LShift(usshort shift) const {
    return *static_cast<const ZZ *>(this) << shift;
  }

  const myZZ &LShiftEq(usshort shift) {
    *static_cast<ZZ *>(this) <<= shift;
    return *this;
  }

  myZZ RShift(usshort shift) const {
    return *static_cast<const ZZ *>(this) >> shift;
  }

  const myZZ &RShiftEq(usshort shift) {
    *static_cast<ZZ *>(this) >>= shift;
    return *this;
  }

  // COMPARE

  // comparison method inline for speed
  int Compare(const myZZ &a) const { return compare(*this, a); }

  // CONVERTING

  // palisade conversion methods
  uint64_t ConvertToInt() const;

  uint64_t ConvertToUint64() const;

  double ConvertToDouble() const;

  static myZZ FromBinaryString(const std::string &bitString);

  // OTHER FUNCTIONS

  // adapter kit that wraps ZZ with BACKEND 2 functionality

  static const myZZ &zero();

  usint GetMSB() const;

  usint GetLengthForBase(usint base) const { return GetMSB(); }

  usint GetDigitAtIndexForBase(usint index, usint base) const;

  // variable to store the log(base 2) of the number of bits in the
  // limb data type.
  static const usint m_log2LimbBitLength;

  usint GetBitRangeAtIndex(usint index, usint length) const;

  uschar GetBitAtIndex(usint index) const;

  static myZZ Allocator() { return 0; }

  // STRINGS & STREAMS

  // palisade string conversion
  const std::string ToString() const;

  static const std::string IntegerTypeName() { return "UBNTLINT"; }

  // big integer stream output
  friend std::ostream &operator<<(std::ostream &os, const myZZ &ptr_obj);

  std::string GetInternalRepresentation(void) const {
    std::string ret("");
    const ZZ_limb_t *zlp = ZZ_limbs_get(*this);

    for (size_t i = 0; i < (size_t)this->size(); i++) {
      ret += std::to_string(zlp[i]);
      if (i < ((size_t)this->size() - 1)) {
        ret += " ";
      }
    }
    return ret;
  }


  template <class Archive>
  typename std::enable_if<!cereal::traits::is_text_archive<Archive>::value,
                          void>::type
  save(Archive &ar, std::uint32_t const version) const {
    void *data = this->rep.rep;
    ::cereal::size_type len = 0;
    if (data == nullptr) {
      ar(::cereal::binary_data(&len, sizeof(len)));
    } else {
      len = _ntl_ALLOC(this->rep.rep);

      ar(::cereal::binary_data(&len, sizeof(len)));
      ar(::cereal::binary_data(data, len * sizeof(_ntl_gbigint)));
      ar(::cereal::make_nvp("mb", m_MSB));
    }
  }

  template <class Archive>
  typename std::enable_if<cereal::traits::is_text_archive<Archive>::value,
                          void>::type
  save(Archive &ar, std::uint32_t const version) const {
    ar(::cereal::make_nvp("v", ToString()));
  }

  template <class Archive>
  typename std::enable_if<!cereal::traits::is_text_archive<Archive>::value,
                          void>::type
  load(Archive &ar, std::uint32_t const version) {
    if (version > SerializedVersion()) {
      PALISADE_THROW(lbcrypto::deserialize_error,
                     "serialized object version " + std::to_string(version) +
                         " is from a later version of the library");
    }
    ::cereal::size_type len;
    ar(::cereal::binary_data(&len, sizeof(len)));
    if (len == 0) {
      *this = 0;
      return;
    }

    void *mem = malloc(len * sizeof(_ntl_gbigint));
    ar(::cereal::binary_data(mem, len * sizeof(_ntl_gbigint)));
    WrappedPtr<_ntl_gbigint_body, Deleter> newrep;
    newrep.rep = reinterpret_cast<_ntl_gbigint_body *>(mem);
    _ntl_gswap(&this->rep, &newrep);

    ar(::cereal::make_nvp("mb", m_MSB));
  }

  template <class Archive>
  typename std::enable_if<cereal::traits::is_text_archive<Archive>::value,
                          void>::type
  load(Archive &ar, std::uint32_t const version) {
    if (version > SerializedVersion()) {
      PALISADE_THROW(lbcrypto::deserialize_error,
                     "serialized object version " + std::to_string(version) +
                         " is from a later version of the library");
    }
    std::string s;
    ar(::cereal::make_nvp("v", s));
    *this = s;
  }

  std::string SerializedObjectName() const { return "NTLInteger"; }

  static uint32_t SerializedVersion() { return 1; }

 private:
  // adapter kits
  void SetMSB();

  // todo: rename to MSB2NLimbs()
  static usint ceilIntByUInt(const ZZ_limb_t Number);

  mutable uint32_t m_MSB;
  usint GetMSBLimb_t(ZZ_limb_t x) const;
};
// class ends

NTL_DECLARE_RELOCATABLE((myZZ *))
}  // namespace NTL

#endif

#endif  // LBCRYPTO_MATH_BIGINTNTL_UBINTNTL_H