// Build don't link: // Special g++ Options: -fexceptions // testcase to check obstack allocation for cleanups typedef unsigned char byte; typedef unsigned short word16; typedef unsigned long word32; typedef unsigned char boolean; enum {FALSE, TRUE}; extern "C" { extern void __eprintf (const char *, const char *, unsigned, const char *); } extern "C" { typedef unsigned int size_t; extern void *memccpy(void *, const void *, int, size_t); extern void *memchr(const void *, int, size_t); extern void *memset(void *, int, size_t); } template struct SecBlock { public: SecBlock(unsigned int size) : size(size), ptr((new T [( size )]) ) {} ~SecBlock() {(memset(( ptr ), 0, ( size )*sizeof(*( ptr ))), delete [] ( ptr )) ;} operator T *() const {return ptr;} T *operator +(unsigned int offset) {return ptr+offset;} T& operator[](int index) {((void) (( index SecByteBlock; void xorbuf(byte *buf, const byte *mask, unsigned int count); void byteReverse(word16 *out, const word16 *in, unsigned int byteCount); void byteReverse(word32 *out, const word32 *in, unsigned int byteCount); inline word16 Invert(const word16 value) { return (value << 8) | (value >> 8); } inline word32 Invert(const word32 value) { word32 work = ((value & 0xFF00FF00L) >> 8) | ((value & 0x00FF00FFL) << 8); return (work << 16) | (work >> 16); } template inline T min (const T t1, const T t2) { return (t1 < t2 ? t1 : t2); } template inline T max (const T t1, const T t2) { return (t1 > t2 ? t1 : t2); } template inline void swap (T &a, T &b) { T temp = a; a = b; b = temp; } template inline T rotl(T x, unsigned int y) { return ((x<>(sizeof(T)*8-y))); } template inline T rotr(T x, unsigned int y) { return ((x>>y) | (x<<(sizeof(T)*8-y))); } int BytePrecision(unsigned long); int BitPrecision(unsigned long); unsigned long Crop(unsigned long, int size); enum CipherDir {ENCRYPTION, DECRYPTION}; class BlockTransformation { public: virtual ~BlockTransformation() {} virtual void ProcessBlock(byte *inoutBlock) =0; virtual void ProcessBlock(const byte *inBlock, byte *outBlock) =0; virtual unsigned int BlockSize() const =0; }; class StreamCipher { public: virtual ~StreamCipher() {} virtual byte ProcessByte(byte input) =0; virtual void ProcessString(byte *outString, const byte *inString, unsigned int length); virtual void ProcessString(byte *inoutString, unsigned int length); }; class RandomAccessStreamCipher : public StreamCipher { public: virtual ~RandomAccessStreamCipher() {} virtual void Seek(unsigned long position) =0; }; class RandomNumberGenerator { public: virtual ~RandomNumberGenerator() {} virtual byte GetByte() =0; virtual int GetBit(); virtual word32 GetLong(word32 min=0, word32 max=0xffffffffL); virtual word16 GetShort(word16 min=0, word16 max=0xffff) {return (word16)GetLong(min, max);} virtual void GetBlock(byte *output, unsigned int size); }; template void Shuffle(RandomNumberGenerator &rng, T *array, unsigned int size) { while (--size) swap(array[size], array[(unsigned int)rng.GetLong(0, size)]); } class HashModule { public: virtual ~HashModule() {} virtual void Update(const byte *input, unsigned int length) =0; virtual void Final(byte *digest) =0; virtual int DigestSize() const =0; virtual void CalculateDigest(byte *digest, const byte *input, int length) {Update(input, length); Final(digest);} }; class BufferedTransformation { public: virtual ~BufferedTransformation() {} virtual unsigned long MaxRetrieveable() =0; virtual void TransferTo(BufferedTransformation &target); virtual boolean Attachable() {return FALSE;} virtual void Detach(BufferedTransformation *) {} virtual void Attach(BufferedTransformation *) {} virtual void Close() {InputFinished();} virtual void Put(byte inByte) =0; virtual void Put(const byte *inString, unsigned int length) =0; virtual void InputFinished() {} void PutShort(word16 value, boolean highFirst=TRUE); void PutLong(word32 value, boolean highFirst=TRUE); virtual int Get(byte &outByte) =0; virtual unsigned int Get(byte *outString, unsigned int getMax) =0; int GetShort(word16 &value, boolean highFirst=TRUE); int GetLong(word32 &value, boolean highFirst=TRUE); unsigned int Skip(unsigned int skipMax); }; class PK_CryptoSystem { public: virtual ~PK_CryptoSystem() {}; virtual unsigned int MaxPlainTextLength() const =0; virtual unsigned int CipherTextLength() const =0; }; class PK_Encryptor : public PK_CryptoSystem { public: virtual void Encrypt(RandomNumberGenerator &rng, const byte *plainText, unsigned int plainTextLength, byte *cipherText) =0; }; class PK_Decryptor : public PK_CryptoSystem { public: virtual unsigned int Decrypt(const byte *cipherText, byte *plainText) =0; }; class PK_SignatureSystem { public: virtual ~PK_SignatureSystem() {}; virtual unsigned int MaxMessageLength() const =0; virtual unsigned int SignatureLength() const =0; }; class PK_Signer : public PK_SignatureSystem { public: virtual void Sign(RandomNumberGenerator &rng, const byte *message, unsigned int messageLen, byte *signature) =0; }; class PK_Verifier : public PK_SignatureSystem { public: virtual boolean Verify(const byte *message, unsigned int messageLen, const byte *signature) =0; }; class ByteQueueNode; class ByteQueue : public BufferedTransformation { public: ByteQueue(); ~ByteQueue(); unsigned long CurrentSize() const; unsigned long MaxRetrieveable() {return CurrentSize();} void Put(byte inByte); void Put(const byte *inString, unsigned int length); int Get(byte &outByte); unsigned int Get(byte *outString, unsigned int getMax); private: ByteQueueNode *head, *tail; }; enum ASNTag {INTEGER=0x02, BIT_STRING=0x03, SEQUENCE=0x10}; enum ASNIdFlag {CONSTRUCTED = 0x20}; unsigned int DERLengthEncode(unsigned int length, byte *output); unsigned int DERLengthEncode(unsigned int length, BufferedTransformation &); class BERDecodeErr {}; boolean BERLengthDecode(BufferedTransformation &, unsigned int &); class BERSequenceDecoder : public BufferedTransformation { public: BERSequenceDecoder(BufferedTransformation &inQueue); ~BERSequenceDecoder(); void Put(byte inByte) {} void Put(const byte *, unsigned int) {} unsigned long MaxRetrieveable() {return inQueue.MaxRetrieveable();} int Get(byte &outByte) {return inQueue.Get(outByte);} unsigned int Get(byte *outString, unsigned int getMax) {return inQueue.Get(outString, getMax);} private: BufferedTransformation &inQueue; boolean definiteLength; unsigned int length; }; class DERSequenceEncoder : public ByteQueue { public: DERSequenceEncoder(BufferedTransformation &outQueue); ~DERSequenceEncoder(); private: BufferedTransformation &outQueue; }; extern "C" { } extern "C" { extern void *memmove(void *, const void *, size_t); extern char *strcpy(char *, const char *); extern char *strncpy(char *, const char *, size_t); extern char *strcat(char *, const char *); extern char *strncat(char *, const char *, size_t); extern int strcmp(const char *, const char *); extern int strcoll(const char *, const char *); extern int strncmp(const char *, const char *, size_t); extern size_t strxfrm(char *, const char *, size_t); extern void * __hide_memchr (const void *, int, size_t); extern char * __hide_strchr (const char *, int); extern size_t strcspn(const char *, const char *); extern char * __hide_strpbrk (const char *, const char *); extern char * __hide_strrchr (const char *, int); extern size_t strspn(const char *, const char *); extern char * __hide_strstr (const char *, const char *); extern char *strtok(char *, const char *); extern void *memset(void *, int, size_t); extern char *strerror(int); extern void *memccpy(void *, const void *, int, size_t); extern char *strdup(const char *); extern char *strsignal(int); extern int ffs(const int); extern int strcasecmp(const char *, const char *); extern int strncasecmp(const char *, const char *, size_t); } typedef int ptrdiff_t; extern "C" const char *strchr (const char *, int); inline char * strchr (char *s, int c) { return (char*) strchr ((const char *) s, c); } extern "C" const char *strpbrk (const char *, const char *); inline char * strpbrk (char *s1, const char *s2) { return (char *) strpbrk ((const char *) s1, s2); } extern "C" const char *strrchr (const char *, int); inline char * strrchr (char *s, int c) { return (char *) strrchr ((const char *) s, c); } extern "C" const char *strstr (const char *, const char *); inline char * strstr (char *s1, const char *s2) { return (char *) strstr ((const char *) s1, s2); } extern "C" void *memchr (const void *, int, size_t); inline void * memchr (void *s, int c, size_t n) { return (void *) memchr ((const void *) s, c, n); } typedef word16 unit; typedef short signedunit; typedef unit *unitptr; extern short global_precision; boolean mp_addc (register unitptr r1,const unit * r2,register boolean carry); boolean mp_subb (register unitptr r1,const unit * r2,register boolean borrow); boolean mp_rotate_left(register unitptr r1,register boolean carry); void mp_shift_right_bits(register unitptr r1,register short bits); short mp_compare(const unit * r1,const unit * r2); boolean mp_inc(register unitptr r); boolean mp_dec(register unitptr r); void mp_neg(register unitptr r); void mp_init(register unitptr r, word16 value); short significance(const unit * r); int mp_udiv(register unitptr remainder,register unitptr quotient, const unit * dividend,const unit * divisor); int mp_recip(register unitptr quotient,const unit * divisor); int mp_div(register unitptr remainder,register unitptr quotient, unit * dividend, unit * divisor); word16 mp_shortdiv(register unitptr quotient, const unit * dividend,register word16 divisor); int mp_mod(register unitptr remainder, const unit * dividend,const unit * divisor); word16 mp_shortmod(register unitptr dividend,register word16 divisor); int mp_mult(register unitptr prod, const unit * multiplicand,const unit * multiplier); int countbits(const unit * r); int stage_peasant_modulus(const unit * n); int stage_merritt_modulus(const unit * n); int stage_upton_modulus(const unit * n); int stage_smith_modulus(const unit * n); int peasant_modmult(register unitptr prod, const unit * multiplicand,const unit * multiplier); int merritt_modmult(register unitptr prod, const unit * multiplicand,const unit * multiplier); int upton_modmult(register unitptr prod, const unit * multiplicand,const unit * multiplier); int smith_modmult(register unitptr prod, const unit * multiplicand,const unit * multiplier); void peasant_burn(); void merritt_burn(); void upton_burn(); void smith_burn(); int mp_modexp(register unitptr expout,const unit * expin, const unit * exponent,const unit * modulus); int mp_modexp_crt(unitptr expout, const unit * expin, const unit * p, const unit * q, const unit * ep, const unit * eq, const unit * u); word16 fetch_word16(byte *buf); byte *put_word16(word16 w, byte *buf); word32 fetch_word32(byte *buf); byte *put_word32(word32 w, byte *buf); int string_length(const char *s); int str2reg(unit * reg,const char* digitstr); int reg2str(char * s,const unit * n,short radix); void mp_display(char * s,unitptr r); word16 checksum(register byte * buf, register word16 count); void cbc_xor(register unitptr dst, register unitptr src, word16 bytecount); void hiloswap(byte * r1,short numbytes); short mpi2reg(register unitptr r, register byte * buf); short reg2mpi(register byte * buf, register unitptr r); enum RandomNumberType {ANY, ODD, PRIME, BLUMINT}; class MPIRegister : public SecBlock { public: MPIRegister() : SecBlock((2048 / 16 ) ) {} }; class ostream; class bignum { public: bignum() {} bignum(unsigned long value); bignum(const char *str) {str2reg(reg, str);} enum Signedness{UNSIGNED, SIGNED}; bignum(const byte *encodedBignum, unsigned int byteCount, Signedness s=UNSIGNED) {Decode(encodedBignum, byteCount, s);} bignum(const byte *BEREncodedInteger) {BERDecode(BEREncodedInteger);} bignum(BufferedTransformation &bt) {BERDecode(bt);} bignum(RandomNumberGenerator &rng, unsigned int bitcount) {Randomize(rng, bitcount);} bignum(RandomNumberGenerator &rng, const bignum &min, const bignum &max, RandomNumberType rnType=ANY) {Randomize(rng, min, max, rnType);} bignum(const bignum& t) {memcpy(reg, t.reg, (2048 /8) );} unsigned int Encode(byte *output) const; unsigned int Encode(byte *output, unsigned int outputLen) const; void Decode(const byte *input, unsigned int inputLen, Signedness=UNSIGNED); unsigned int DEREncode(byte *output) const; unsigned int DEREncode(BufferedTransformation &bt) const; void BERDecode(const byte *input); void BERDecode(BufferedTransformation &bt); void Randomize(RandomNumberGenerator &rng, unsigned int bitcount); void Randomize(RandomNumberGenerator &rng, const bignum &min, const bignum &max); void Randomize(RandomNumberGenerator &rng, const bignum &min, const bignum &max, RandomNumberType rnType); unsigned int ByteCount() const { return ((countbits( reg )+7)>>3) ; } int BitCount() const { return countbits(reg); } bignum& operator++() { mp_inc(reg); return *this; } bignum& operator--() { mp_dec(reg); return *this; } int operator!() const { return ( ((* (( reg.ptr )+( global_precision )-1) ) ==( 0 )) && (significance( reg.ptr )<=1) ) ; } bignum& operator=(const bignum& t) { memcpy(reg, t.reg, (2048 /8) ); return *this; } bignum& operator+=(const bignum& t) { mp_addc( reg , t.reg ,(boolean)0) ; return *this; } bignum& operator-=(const bignum& t) { mp_subb( reg , t.reg ,(boolean)0) ; return *this; } bignum& operator*=(const bignum& t) { *this = (*this) * t; return *this; } bignum& operator/=(const bignum& t) { *this = (*this) / t; return *this; } bignum& operator%=(const bignum& t) { *this = (*this) % t; return *this; } bignum& operator<<=(unsigned int); bignum& operator>>=(unsigned int); unsigned MaxBitPrecision() const {return 2048 ;} int operator[](unsigned int n) const; friend bignum operator+(bignum a, const bignum &b) { return (a+=b); } friend bignum operator-(bignum a, const bignum &b) { return (a-=b); } friend bignum operator*(const bignum &a, const bignum &b); friend bignum operator/(const bignum &a, const bignum &b); friend bignum operator%(const bignum &a, const bignum &b); friend bignum operator/(const bignum &a, word16 b); friend word16 operator%(const bignum &a, word16 b); friend bignum operator>>(bignum a, unsigned int n) {return (a>>=n);} friend bignum operator<<(bignum a, unsigned int n) {return (a<<=n);} void Negate() {mp_neg(reg);} friend bignum operator-(bignum a) { a.Negate(); return a; } friend int operator==(const bignum &a, const bignum &b) { return (memcmp(a.reg.ptr, b.reg.ptr, (2048 /8) )==0); } friend int operator!=(const bignum& a, const bignum& b) { return (memcmp(a.reg.ptr, b.reg.ptr, (2048 /8) )!=0); } friend int operator>(const bignum& a, const bignum& b) { return (mp_compare(a.reg, b.reg)>0); } friend int operator>=(const bignum& a, const bignum& b) { return (mp_compare(a.reg, b.reg)>=0); } friend int operator<(const bignum& a, const bignum& b) { return (mp_compare(a.reg, b.reg)<0); } friend int operator<=(const bignum& a, const bignum& b) { return (mp_compare(a.reg, b.reg)<=0); } friend bignum a_times_b_mod_c(const bignum &x, const bignum& y, const bignum& m); friend bignum a_exp_b_mod_c(const bignum &x, const bignum& e, const bignum& m); class DivideErr {}; friend void Divide(bignum &r, bignum &q, const bignum &a, const bignum &d, Signedness s=SIGNED); friend boolean Negative(const bignum &a) { return ((signedunit) (* ( a.reg.ptr ) ) < 0) ; } friend bignum Abs(bignum a) { (((signedunit) (* ( a.reg.ptr ) ) < 0) ? (mp_neg( a.reg.ptr ),TRUE) : FALSE) ; return a; } friend ostream& operator<<(ostream& out, const bignum &a); unit lsUnit() {return (* (( reg.ptr )+( global_precision )-1) ) ;} private: MPIRegister reg; }; class RSAPublicKey : public PK_Encryptor, public PK_Decryptor, public PK_Verifier { public: RSAPublicKey(const bignum &n, const bignum &e); RSAPublicKey(BufferedTransformation &bt); void DEREncode(BufferedTransformation &bt) const; void Encrypt(RandomNumberGenerator &rng, const byte *plainText, unsigned int plainTextLength, byte *cipherText); unsigned int Decrypt(const byte *cipherText, byte *plainText); boolean Verify(const byte *message, unsigned int messageLen, const byte *signature); unsigned int MaxPlainTextLength() const {return modulusLen-11;} unsigned int CipherTextLength() const {return modulusLen;} unsigned int MaxMessageLength() const {return modulusLen-11;} unsigned int SignatureLength() const {return modulusLen;} const bignum& Exponent() const {return e;} const bignum& Modulus() const {return n;} protected: void RawEncrypt(const bignum &in, bignum &out) const; private: friend class RSAPrivateKey; RSAPublicKey() {} bignum n; bignum e; unsigned int modulusLen; }; class RSAPrivateKey : public RSAPublicKey, public PK_Signer { public: RSAPrivateKey(const bignum &n, const bignum &e, const bignum &d, const bignum &p, const bignum &q, const bignum &dp, const bignum &dq, const bignum &u); RSAPrivateKey(RandomNumberGenerator &rng, int keybits, bignum eStart=17); RSAPrivateKey(BufferedTransformation &bt); void DEREncode(BufferedTransformation &bt) const; void Encrypt(const byte *plainText, unsigned int plainTextLength, byte *cipherText); unsigned int Decrypt(const byte *cipherText, byte *plainText); void Encrypt(RandomNumberGenerator &, const byte *plainText, unsigned int plainTextLength, byte *cipherText) {Encrypt(plainText, plainTextLength, cipherText);} void Sign(const byte *message, unsigned int messageLen, byte *signature) {Encrypt(message, messageLen, signature);} void Sign(RandomNumberGenerator &, const byte *message, unsigned int messageLen, byte *signature) {Encrypt(message, messageLen, signature);} unsigned int MaxMessageLength() const {return modulusLen-11;} unsigned int SignatureLength() const {return modulusLen;} protected: void RawEncrypt(const bignum &in, bignum &out) const; private: bignum d; bignum p; bignum q; bignum dp; bignum dq; bignum u; }; bignum Gcd(const bignum &a, const bignum &b); bignum Inverse(const bignum &a, const bignum &m); boolean IsSmallPrime(const bignum &p); boolean SmallDivisorsTest(const bignum &p); boolean FermatTest(const bignum &p, unsigned int rounds); boolean RabinMillerTest(RandomNumberGenerator &rng, const bignum &w, unsigned int rounds); inline boolean IsPrime(const bignum &p) { return (IsSmallPrime(p) || (SmallDivisorsTest(p) && FermatTest(p, 2))); } boolean NextPrime(bignum &p, const bignum &max, boolean blumInt=FALSE); bignum a_exp_b_mod_pq(const bignum &a, const bignum &ep, const bignum &eq, const bignum &p, const bignum &q, const bignum &u); class PrimeAndGenerator { public: PrimeAndGenerator(RandomNumberGenerator &rng, unsigned int pbits); PrimeAndGenerator(RandomNumberGenerator &rng, unsigned int pbits, unsigned qbits); const bignum& Prime() const {return p;} const bignum& SubPrime() const {return q;} const bignum& Generator() const {return g;} private: bignum p, q, g; }; extern "C" { extern void __eprintf (const char *, const char *, unsigned, const char *); } RSAPublicKey::RSAPublicKey(const bignum &n, const bignum &e) : n(n), e(e), modulusLen(n.ByteCount()) { } RSAPublicKey::RSAPublicKey(BufferedTransformation &bt) { BERSequenceDecoder seq(bt); n.BERDecode(seq); modulusLen = n.ByteCount(); e.BERDecode(seq); } void RSAPublicKey::DEREncode(BufferedTransformation &bt) const { DERSequenceEncoder seq(bt); n.DEREncode(seq); e.DEREncode(seq); } void RSAPublicKey::Encrypt(RandomNumberGenerator &rng, const byte *input, unsigned int inputLen, byte *output) {unsigned int i; ((void) (( inputLen <= MaxPlainTextLength() ) ? 0 : (__eprintf ("%s:%u: failed assertion `%s'\n", "rsa.cpp" , 30 , "inputLen <= MaxPlainTextLength()" ), 0) )) ; SecByteBlock pkcsBlock(modulusLen); pkcsBlock[0] = 0; pkcsBlock[1] = 2; for (i = 2; i < modulusLen - inputLen - 1; i++) { do pkcsBlock[i] = rng.GetByte(); while (pkcsBlock[i] == 0); } pkcsBlock[i++] = 0; memcpy(pkcsBlock+i, input, inputLen); bignum c; RawEncrypt(bignum(pkcsBlock, modulusLen), c); c.Encode(output, modulusLen); } unsigned int RSAPublicKey::Decrypt(const byte *input, byte *output) {unsigned int i; bignum m; RawEncrypt(bignum(input, modulusLen), m); SecByteBlock pkcsBlock(modulusLen); m.Encode(pkcsBlock, modulusLen); if ((pkcsBlock[0] != 0) || (pkcsBlock[1] != 1)) return 0; for (i = 2; i < modulusLen-1; i++) if (pkcsBlock[i] != 0xff) break; if (pkcsBlock[i++] != 0) return 0; unsigned int outputLen = modulusLen - i; if (outputLen > MaxPlainTextLength()) return 0; memcpy (output, pkcsBlock+i, outputLen); return outputLen; } boolean RSAPublicKey::Verify(const byte *message, unsigned int messageLen, const byte *signature) { ((void) (( messageLen <= MaxMessageLength() ) ? 0 : (__eprintf ("%s:%u: failed assertion `%s'\n", "rsa.cpp" , 83 , "messageLen <= MaxMessageLength()" ), 0) )) ; SecByteBlock m(MaxMessageLength()); unsigned int mLen = RSAPublicKey::Decrypt(signature, m); return (mLen==messageLen && memcmp(message, m, mLen)==0); } void RSAPublicKey::RawEncrypt(const bignum &in, bignum &out) const { out = a_exp_b_mod_c(in, e, n); } RSAPrivateKey::RSAPrivateKey(const bignum &nIn, const bignum &eIn, const bignum &dIn, const bignum &pIn, const bignum &qIn, const bignum &dpIn, const bignum &dqIn, const bignum &uIn) : RSAPublicKey(nIn, eIn) { d=dIn; if (pIn < qIn) { p=pIn; q=qIn; dp=dpIn; dq=dqIn; } else { p=qIn; q=pIn; dp=dqIn; dq=dpIn; } u=uIn; } RSAPrivateKey::RSAPrivateKey(RandomNumberGenerator &rng, int keybits, bignum eStart) { p = bignum(rng, keybits/2, PRIME); const bignum minQ = ((bignum(1) << (keybits-1)) / p) + 1; const bignum maxQ = (bignum(1) << keybits) / p; do { bignum temp(rng, minQ, maxQ, PRIME); if (p>temp && p.BitCount()-(p-temp).BitCount() < 7) { q=p; p=temp; break; } if (pq) { swap(p, q); swap(dp, dq); } } void RSAPrivateKey::DEREncode(BufferedTransformation &bt) const { DERSequenceEncoder seq(bt); byte version[] = {INTEGER, 1, 0}; seq.Put(version, sizeof(version)); n.DEREncode(seq); e.DEREncode(seq); d.DEREncode(seq); q.DEREncode(seq); p.DEREncode(seq); dq.DEREncode(seq); dp.DEREncode(seq); u.DEREncode(seq); }