integer.h   [plain text]

/*
 * Copyright (c) 2002 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 * 
 * The contents of this file constitute Original Code as defined in and
 * are subject to the Apple Public Source License Version 1.1 (the
 * "License").  You may not use this file except in compliance with the
 * License.  Please obtain a copy of the License at
 * http://www.apple.com/publicsource and read it before using this file.
 * 
 * This Original Code and all software distributed under the License are
 * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the
 * License for the specific language governing rights and limitations
 * under the License.
 * 
 * @APPLE_LICENSE_HEADER_END@
 */
#ifndef CRYPTOPP_INTEGER_H
#define CRYPTOPP_INTEGER_H

/** \file */

#include "cryptopp.h"
#include "cryptopp_misc.h"

#include <iosfwd>

NAMESPACE_BEGIN(CryptoPP)

//! multiple precision integer and basic arithmetics
/*! This class can represent positive and negative integers
	with absolute value less than (256**sizeof(word)) ** (256**sizeof(int)).
	\nosubgrouping
*/
class Integer
{
public:
	//! \name ENUMS, EXCEPTIONS, and TYPEDEFS
	//@{
		//! division by zero exception
		class DivideByZero : public Exception
		{
		public:
			DivideByZero() : Exception("Integer: division by zero") {}
		};

		//!
		class RandomNumberNotFound : public Exception
		{
		public:
			RandomNumberNotFound() : Exception("Integer: random number not found") {}
		};

		//!
		enum Signedness {
		//!
			UNSIGNED,
		//!
			SIGNED};

		//!
		enum RandomNumberType {
		//!
			ANY,
		//!
			PRIME};
	//@}

	//! \name CREATORS
	//@{
		//! creates the zero integer
		Integer();

		//! copy constructor
		Integer(const Integer& t);

		//! convert from signed long
		Integer(signed long value);

		//! convert from string
		/*! str can be in base 2, 8, 10, or 16.  Base is determined by a
			case insensitive suffix of 'h', 'o', or 'b'.  No suffix means base 10.
		*/
		Integer(const char *str);

		//! convert from big-endian byte array
		Integer(const byte *encodedInteger, unsigned int byteCount, Signedness s=UNSIGNED);

		//! convert from big-endian form stored in a BufferedTransformation
		Integer(BufferedTransformation &bt, unsigned int byteCount, Signedness s=UNSIGNED);

		//! convert from BER encoded byte array stored in a BufferedTransformation object
		Integer(BufferedTransformation &bt);

		//! create a random integer
		/*! The random integer created is uniformly distributed over [0, 2**bitcount). */
		Integer(RandomNumberGenerator &rng, unsigned int bitcount);

		//! avoid calling constructors for these frequently used integers
		static const Integer &Zero();
		//! avoid calling constructors for these frequently used integers
		static const Integer &One();

		//! create a random integer of special type
		/*! Ideally, the random integer created should be uniformly distributed
			over {x | min <= x <= max and x is of rnType and x % mod == equiv}.
			However the actual distribution may not be uniform because sequential
			search is used to find an appropriate number from a random starting
			point.
			May return (with very small probability) a pseudoprime when a prime
			is requested and max > lastSmallPrime*lastSmallPrime (lastSmallPrime
			is declared in nbtheory.h).
			\throw RandomNumberNotFound if the set is empty.
		*/
		Integer(RandomNumberGenerator &rng, const Integer &min, const Integer &max, RandomNumberType rnType=ANY, const Integer &equiv=Zero(), const Integer &mod=One());

		//! return the integer 2**e
		static Integer Power2(unsigned int e);
	//@}

	//! \name ENCODE/DECODE
	//@{
		//! minimum number of bytes to encode this integer
		/*! MinEncodedSize of 0 is 1 */
		unsigned int MinEncodedSize(Signedness=UNSIGNED) const;
		//! encode in big-endian format
		/*! unsigned means encode absolute value, signed means encode two's complement if negative.
			if outputLen < MinEncodedSize, the most significant bytes will be dropped
			if outputLen > MinEncodedSize, the most significant bytes will be padded
		*/
		unsigned int Encode(byte *output, unsigned int outputLen, Signedness=UNSIGNED) const;
		//!
		unsigned int Encode(BufferedTransformation &bt, unsigned int outputLen, Signedness=UNSIGNED) const;

		//! encode using Distinguished Encoding Rules, put result into a BufferedTransformation object
		void DEREncode(BufferedTransformation &bt) const;

		//! encode absolute value as big-endian octet string
		void DEREncodeAsOctetString(BufferedTransformation &bt, unsigned int length) const;

		//! encode absolute value in OpenPGP format, return length of output
		unsigned int OpenPGPEncode(byte *output, unsigned int bufferSize) const;
		//! encode absolute value in OpenPGP format, put result into a BufferedTransformation object
		unsigned int OpenPGPEncode(BufferedTransformation &bt) const;

		//!
		void Decode(const byte *input, unsigned int inputLen, Signedness=UNSIGNED);
		//! 
		//* Precondition: bt.MaxRetrievable() >= inputLen
		void Decode(BufferedTransformation &bt, unsigned int inputLen, Signedness=UNSIGNED);

		//!
		void BERDecode(const byte *input, unsigned int inputLen);
		//!
		void BERDecode(BufferedTransformation &bt);

		//! decode nonnegative value as big-endian octet string
		void BERDecodeAsOctetString(BufferedTransformation &bt, unsigned int length);

		class OpenPGPDecodeErr : public Exception
		{
		public: 
			OpenPGPDecodeErr() : Exception("OpenPGP decode error") {}
		};

		//!
		void OpenPGPDecode(const byte *input, unsigned int inputLen);
		//!
		void OpenPGPDecode(BufferedTransformation &bt);
	//@}

	//! \name ACCESSORS
	//@{
		//! return true if *this can be represented as a signed long
		bool IsConvertableToLong() const;
		//! return equivalent signed long if possible, otherwise undefined
		signed long ConvertToLong() const;

		//! number of significant bits = floor(log2(abs(*this))) + 1
		unsigned int BitCount() const;
		//! number of significant bytes = ceiling(BitCount()/8)
		unsigned int ByteCount() const;
		//! number of significant words = ceiling(ByteCount()/sizeof(word))
		unsigned int WordCount() const;

		//! return the i-th bit, i=0 being the least significant bit
		bool GetBit(unsigned int i) const;
		//! return the i-th byte
		byte GetByte(unsigned int i) const;
		//! return n lowest bits of *this >> i
		unsigned long GetBits(unsigned int i, unsigned int n) const;

		//!
		bool IsZero() const {return !*this;}
		//!
		bool NotZero() const {return !IsZero();}
		//!
		bool IsNegative() const {return sign == NEGATIVE;}
		//!
		bool NotNegative() const {return !IsNegative();}
		//!
		bool IsPositive() const {return NotNegative() && NotZero();}
		//!
		bool NotPositive() const {return !IsPositive();}
		//!
		bool IsEven() const {return GetBit(0) == 0;}
		//!
		bool IsOdd() const	{return GetBit(0) == 1;}
	//@}

	//! \name MANIPULATORS
	//@{
		//!
		Integer&  operator=(const Integer& t);

		//!
		Integer&  operator+=(const Integer& t);
		//!
		Integer&  operator-=(const Integer& t);
		//!
		Integer&  operator*=(const Integer& t)	{return *this = Times(t);}
		//!
		Integer&  operator/=(const Integer& t)	{return *this = DividedBy(t);}
		//!
		Integer&  operator%=(const Integer& t)	{return *this = Modulo(t);}
		//!
		Integer&  operator/=(word t)  {return *this = DividedBy(t);}
		//!
		Integer&  operator%=(word t)  {return *this = Modulo(t);}

		//!
		Integer&  operator<<=(unsigned int);
		//!
		Integer&  operator>>=(unsigned int);

		//!
		void Randomize(RandomNumberGenerator &rng, unsigned int bitcount);
		//!
		void Randomize(RandomNumberGenerator &rng, const Integer &min, const Integer &max);
		//! set this Integer to a random element of {x | min <= x <= max and x is of rnType and x % mod == equiv}
		/*! returns false if the set is empty */
		bool Randomize(RandomNumberGenerator &rng, const Integer &min, const Integer &max, RandomNumberType rnType, const Integer &equiv=Zero(), const Integer &mod=One());

		//! set the n-th bit to value
		void SetBit(unsigned int n, bool value=1);
		//! set the n-th byte to value
		void SetByte(unsigned int n, byte value);

		//!
		void Negate();
		//!
		void SetPositive() {sign = POSITIVE;}
		//!
		void SetNegative() {if (!!(*this)) sign = NEGATIVE;}

		//!
		void swap(Integer &a);
	//@}

	//! \name UNARY OPERATORS
	//@{
		//!
		bool		operator!() const;
		//!
		Integer 	operator+() const {return *this;}
		//!
		Integer 	operator-() const;
		//!
		Integer&	operator++();
		//!
		Integer&	operator--();
		//!
		Integer 	operator++(int) {Integer temp = *this; ++*this; return temp;}
		//!
		Integer 	operator--(int) {Integer temp = *this; --*this; return temp;}
	//@}

	//! \name BINARY OPERATORS
	//@{
		//! signed comparison
		/*! \retval -1 if *this < a
			\retval  0 if *this = a
			\retval  1 if *this > a
		*/
		int Compare(const Integer& a) const;

		//!
		Integer Plus(const Integer &b) const;
		//!
		Integer Minus(const Integer &b) const;
		//!
		Integer Times(const Integer &b) const;
		//!
		Integer DividedBy(const Integer &b) const;
		//!
		Integer Modulo(const Integer &b) const;
		//!
		Integer DividedBy(word b) const;
		//!
		word Modulo(word b) const;

		//!
		Integer operator>>(unsigned int n) const	{return Integer(*this)>>=n;}
		//!
		Integer operator<<(unsigned int n) const	{return Integer(*this)<<=n;}
	//@}

	//! \name OTHER ARITHMETIC FUNCTIONS
	//@{
		//!
		Integer AbsoluteValue() const;
		//!
		Integer Doubled() const {return Plus(*this);}
		//!
		Integer Squared() const {return Times(*this);}
		//! extract square root, if negative return 0, else return floor of square root
		Integer SquareRoot() const;
		//! return whether this integer is a perfect square
		bool IsSquare() const;

		//! is 1 or -1
		bool IsUnit() const;
		//! return inverse if 1 or -1, otherwise return 0
		Integer MultiplicativeInverse() const;

		//! modular multiplication
		friend Integer a_times_b_mod_c(const Integer &x, const Integer& y, const Integer& m);
		//! modular exponentiation
		friend Integer a_exp_b_mod_c(const Integer &x, const Integer& e, const Integer& m);

		//! calculate r and q such that (a == d*q + r) && (0 <= r < abs(d))
		static void Divide(Integer &r, Integer &q, const Integer &a, const Integer &d);
		//! use a faster division algorithm when divisor is short
		static void Divide(word &r, Integer &q, const Integer &a, word d);

		//! returns same result as Divide(r, q, a, Power2(n)), but faster
		static void DivideByPowerOf2(Integer &r, Integer &q, const Integer &a, unsigned int n);

		//! greatest common divisor
		static Integer Gcd(const Integer &a, const Integer &n);
		//! calculate multiplicative inverse of *this mod n
		Integer InverseMod(const Integer &n) const;
		//!
		word InverseMod(word n) const;
	//@}

	//! \name INPUT/OUTPUT
	//@{
		//!
		friend std::istream& operator>>(std::istream& in, Integer &a);
		//!
		friend std::ostream& operator<<(std::ostream& out, const Integer &a);
	//@}

private:
	friend class ModularArithmetic;
	friend class MontgomeryRepresentation;
	friend class HalfMontgomeryRepresentation;

	Integer(word value, unsigned int length);

	int PositiveCompare(const Integer &t) const;
	friend void PositiveAdd(Integer &sum, const Integer &a, const Integer &b);
	friend void PositiveSubtract(Integer &diff, const Integer &a, const Integer &b);
	friend void PositiveMultiply(Integer &product, const Integer &a, const Integer &b);
	friend void PositiveDivide(Integer &remainder, Integer &quotient, const Integer &dividend, const Integer &divisor);

	enum Sign {POSITIVE=0, NEGATIVE=1};

	SecWordBlock reg;
	Sign sign;
};

NAMESPACE_END

// declaring these overloaded operators inside the CryptoPP namespace
// causes problems with GCC 2.95.2

//!
inline bool operator==(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)==0;}
//!
inline bool operator!=(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)!=0;}
//!
inline bool operator> (const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)> 0;}
//!
inline bool operator>=(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)>=0;}
//!
inline bool operator< (const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)< 0;}
//!
inline bool operator<=(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)<=0;}
//!
inline CryptoPP::Integer operator+(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Plus(b);}
//!
inline CryptoPP::Integer operator-(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Minus(b);}
//!
inline CryptoPP::Integer operator*(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Times(b);}
//!
inline CryptoPP::Integer operator/(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.DividedBy(b);}
//!
inline CryptoPP::Integer operator%(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Modulo(b);}
//!
inline CryptoPP::Integer operator/(const CryptoPP::Integer &a, CryptoPP::word b) {return a.DividedBy(b);}
//!
inline CryptoPP::word    operator%(const CryptoPP::Integer &a, CryptoPP::word b) {return a.Modulo(b);}

NAMESPACE_BEGIN(std)
template<> inline void swap(CryptoPP::Integer &a, CryptoPP::Integer &b)
{
	a.swap(b);
}
NAMESPACE_END

#endif