// written by André Betz 
// http://www.andrebetz.de

#include <stdio.h>
#define LENGTH	60
#define SEED	27182

/*  
typedef unsigned long	ulong; //32Bit
typedef unsigned short	ushort;//16Bit

// a * b mod 65537
ushort mul(ushort a, ushort b)
{
	long	p;
	ulong	q;

  if (a==0)	return (ushort)(1 - b);
  if (b==0)	return (ushort)(1 - a);
  
  q = (ulong)a * (ulong)b;
  if((p = (q & 65535) - (q >> 16)) <= 0)	p++;
  
  return (ushort)p;
}

// a^-1 mod 65537
ushort inv(ushort ain)
{
  long a = ain, c = 65537, d, e = 0, f = 1, g;

  while ( a > 0 ) 
  {
	  d = c % a;
	  g = e - c / a * f;
	  c = a; 
	  a = d; 
  	  e = f; 
	  f = g;

  }

  if (e < 0)	e++;

  return (ushort)e;
}

// IDEA core function
void Idea(ushort *in, ushort *out, ushort *ks)
{
	ushort x0, x1, x2, x3, a, b, i;

	x0 = in[0];
	x1 = in[1];
	x2 = in[2];
	x3 = in[3];
	
	for(i=0;i<8;i++) 
	{
		x0	=	mul( ks[i*6+0], x0);
		x1	=	ks[i*6+1] + x1;
		x2	=	ks[i*6+2] + x2; 
		x3	=	mul( ks[i*6+3], x3);
		b	=	mul( ks[i*6+4], x0 ^ x2);
		a	=	mul( ks[i*6+5], b + (x1 ^ x3));
		b	=	b + a;
		x0	=	a ^ x0;
		x3	=	b ^ x3;
		b	=	b ^ x1;
		x1	=	a ^ x2;
		x2	=	b;
	}
	
	out[0] = mul(ks[i*6+0], x0);
	out[1] = ks[i*6+1] + x2;
	out[2] = ks[i*6+2] + x1;
	out[3] = mul(ks[i*6+3], x3);
}

// Expand 128-bit user key to 832-bit encrypt key
void ExpandUserKey(ushort *key, ushort *ks)
{
	ushort i;

	for (i=0;i<8;i++)	ks[i] = key[i];
	for (;i<52;i++) 
	{
		if ((i & 7) == 6) 
		{
			ks[i] = (ks[i - 7] << 9) ^ (ks[i - 14] >> 7);
		} 
		else if ((i & 7) == 7) 
		{
			ks[i] = (ks[i - 15] << 9) ^ (ks[i - 14] >> 7);
		} 
		else 
		{
			ks[i] = (ks[i - 7] << 9) ^ (ks[i - 6] >> 7);
		}
	}
}

// Invert encrypt key to decrypt key.
void InvertIdeaKey(ushort *ks, ushort *ik)
{
	ushort kb[52], i, j;

	for(i=0,j=48;i<52;i+=6,j-=6) 
	{
		kb[i + 0] = inv(ks[j + 0]);
		if ((i == 0) || (i == 48)) 
		{
			kb[i + 1] = -ks[j + 1];
			kb[i + 2] = -ks[j + 2];
		} 
		else 
		{
			kb[i + 1] = -ks[j + 2];
			kb[i + 2] = -ks[j + 1];
		}
		
		kb[i + 3] = inv(ks[j + 3]);
		if (i < 48) 
		{
			kb[i + 4] = ks[j - 2];
			kb[i + 5] = ks[j - 1];
		}
	}
	
	for (i = 0; i < 52; i++)	ik[i] = kb[i];
}

void main(int argc, char **argv)
{
	unsigned short key[8] = { 1, 2, 3, 4, 5, 6, 7, 8 };
	unsigned short ks[52], ik[52];
	unsigned short p[4] = {0, 1, 2, 3 }, c[4], d[4];
	int	i;

	ExpandUserKey(key, ks);
	InvertIdeaKey(ks, ik);
  
	for(i=0;i<4;i++)    printf("%5u",p[i]);
	printf("\n");
  
	Idea(p, c, ks);
	for(i=0;i<4;i++)    printf("%5u",c[i]);
	printf("\n");
 
	Idea(c, d, ik);
	for(i=0;i<4;i++)    printf("%5u",d[i]);
	printf("\n");
}
*/

//Beipiel eines Austausches von Informationen mit 2 unterschieldichen privaten SChlüsseln
//A: verschlüsselt M mit seinem geheimen Schlüssel: M xor S1 = N und sendet N an B
//B: verschlüsselt N mit seinem geheimen Schlüssel: N xor S2 = O und sendet O an A 
//A: entschlüsselt O mit seinem geheimen Schlüssel: O xor S1 = P und sendet P an B
//b: entschlüsselt P mit seinem geheimen Schlüssel: P xor S2 = M und hat den Klartext


unsigned long	ZufSeed = SEED;

class BigNum
{
protected:
	unsigned char*	m_pucBigNum;
	unsigned long	m_ulVor;
	unsigned long	m_ulLen;
	unsigned long	m_ulSeed;
	void Zerro();
	void Add(BigNum& xBigNum1,BigNum& xBigNum2,BigNum& xErg);
	void Sub(BigNum& xBigNum1,BigNum& xBigNum2,BigNum& xErg);
	void Shr(BigNum& xBigNum,unsigned long ulWeit);
	void Shl(BigNum& xBigNum,unsigned long ulWeit);
	void Mul(BigNum& xBigNum,unsigned char ucFact);
	unsigned char BigNum::Kle(BigNum& xBigNum1,BigNum& xBigNum2);
	unsigned char BigNum::Gro(BigNum& xBigNum1,BigNum& xBigNum2);
	unsigned char BigNum::Div(BigNum& xBigNum1,BigNum& xBigNum2,BigNum& xRest);
	unsigned long Len(BigNum& xBigNum);
public:
	BigNum();
	BigNum(BigNum& xBigNum);
	BigNum(char* pcIn);
	~BigNum();
	void operator<<(char* pcIn);
	void operator>>(char* pcOut);
	BigNum& operator=(BigNum& xBigNum);
	BigNum operator+(BigNum& xBigNum);
	BigNum operator-(BigNum& xBigNum);
	BigNum operator*(BigNum& xBigNum);
	BigNum operator/(BigNum& xBigNum);
	BigNum operator%(BigNum& xBigNum);
	BigNum& operator=(char* pcIn);
	BigNum operator+(char* pcIn);
	BigNum operator-(char* pcIn);
	BigNum operator*(char* pcIn);
	BigNum operator/(char* pcIn);
	BigNum operator%(char* pcIn);
	void operator++(int);
	void operator--(int);
	unsigned char operator<(BigNum& xBigNum);
	unsigned char operator>(BigNum& xBigNum);
	unsigned char operator==(BigNum& xBigNum);
	unsigned char operator!=(BigNum& xBigNum);
	unsigned char operator<(char* pcIn);
	unsigned char operator>(char* pcIn);
	unsigned char operator==(char* pcIn);
	unsigned char operator!=(char* pcIn);
	void Random(unsigned long ulLen);
};

class RSA
{
protected:
	unsigned long	m_ulKeyLen;
	BigNum	m_xPrivat;
	BigNum	m_xPublic;
	BigNum	m_xModul;
	BigNum	m_xPhi;
	BigNum	m_xPrimP;
	BigNum	m_xPrimQ;
	BigNum	Gcd(BigNum& xBigNum1,BigNum &xBigNum2);
	BigNum	Egcd(BigNum& xBigNum1,BigNum &xBigNum2);
	BigNum	ModPow(BigNum& xBigNum1,BigNum& xBigNum2,BigNum& xBigNum3);
	BigNum	WordToNum(char* pcIn,unsigned long ulSize);
	void	NumToWord(BigNum& xBigNum,char* pcIn,unsigned long ulSize);
	unsigned long	IsPrim(BigNum& xBigNum);
public:
	RSA();
	void GenerateKey();
	void Encode(char* pcBigNum,char* pcIn);
	void Decode(char* pcBigNum,char* pcIn);
};


BigNum::BigNum()
{
	m_ulLen		= LENGTH+1;
	m_ulSeed	= ZufSeed;
	m_ulVor		= 0;
	m_pucBigNum	= new unsigned char[m_ulLen];
	Zerro();
}		   

BigNum::BigNum(char* pcIn)
{
	m_ulLen		= LENGTH+1;
	m_ulSeed	= ZufSeed;
	m_pucBigNum	= new unsigned char[m_ulLen];
	*this << pcIn;
}

BigNum::BigNum(BigNum& xBigNum)
{
	unsigned long	ulCount;
	m_ulLen		= xBigNum.m_ulLen;
	m_ulSeed	= xBigNum.m_ulSeed;
	m_ulVor		= xBigNum.m_ulVor;
	m_pucBigNum	= new unsigned char[m_ulLen];
	for(ulCount=0;ulCount<xBigNum.m_ulLen;ulCount++)
	{
		m_pucBigNum[ulCount] = xBigNum.m_pucBigNum[ulCount];
	}
}

BigNum::~BigNum()
{
	delete m_pucBigNum;
}

void BigNum::Zerro()
{
	unsigned long	ulCount;
	for(ulCount=0;ulCount<m_ulLen;ulCount++)
	{
		m_pucBigNum[ulCount] = 0;
	}
}

unsigned long BigNum::Len(BigNum& xBigNum)
{
	unsigned long	ulCount	= 0;
	unsigned long	ulLen	= 0;
	unsigned long	ulFlag	= 0;

	for(ulCount=xBigNum.m_ulLen;ulCount>0;ulCount--)
	{
		if(xBigNum.m_pucBigNum[ulCount-1]!=0)	ulFlag = 1;
		if(ulFlag)
		{
			ulLen++;
		}
	}
	
	return ulLen;
}

void BigNum::operator<<(char* pcIn)
{
	unsigned long	ulCount = 0;
	unsigned long	ulLen	= 0;
	unsigned long	ulTill	= 0;

	Zerro();

	while(pcIn[ulLen])
	{
		ulLen++;
	}

	if(pcIn[0]=='-')	
	{
		m_ulVor = 1;
		ulCount++;
		ulTill++;
		ulLen--;
	}
	else				m_ulVor = 0;

	for(ulLen;ulLen>ulTill;ulLen--)
	{
		m_pucBigNum[ulCount] = (unsigned char)(pcIn[ulLen-1] - '0');
		ulCount++;
	}
}

void BigNum::operator>>(char* pcOut)
{
	unsigned long	ulCount = 0;
	unsigned long	ulLen;

	ulLen = Len(*this);

	if(m_ulVor)	
	{
		pcOut[0] = '-';
		ulCount++;
	}

	for(ulLen;ulLen>0;ulLen--)
	{
		pcOut[ulCount] = char(m_pucBigNum[ulLen-1] + '0'); 
		ulCount++;
	}
	pcOut[ulCount] = 0;
}

BigNum& BigNum::operator=(BigNum& xBigNum)
{
	unsigned long	ulCount;

	m_ulVor = xBigNum.m_ulVor;
	for(ulCount=0;ulCount<m_ulLen;ulCount++)
	{
		m_pucBigNum[ulCount] = xBigNum.m_pucBigNum[ulCount];	
	}

	return *this;
}

void BigNum::Add(BigNum& xBigNum1,BigNum& xBigNum2,BigNum& xErg)
{
	unsigned long	ulCount;
	unsigned char	ucCarry	= 0;

	for(ulCount=0;ulCount<m_ulLen;ulCount++)
	{
		ucCarry = xBigNum1.m_pucBigNum[ulCount] + xBigNum2.m_pucBigNum[ulCount] + ucCarry;
		if(ucCarry>9)	
		{
			xErg.m_pucBigNum[ulCount]	= ucCarry - 10;
			ucCarry						= 1;
		}
		else
		{
			xErg.m_pucBigNum[ulCount]	= ucCarry;
			ucCarry						= 0;
		}
	}
}

void BigNum::Sub(BigNum& xBigNum1,BigNum& xBigNum2,BigNum& xErg)
{
	unsigned long	ulCount;
	unsigned char	ucCarry	= 0;

	for(ulCount=0;ulCount<m_ulLen;ulCount++)
	{
		ucCarry = (xBigNum1.m_pucBigNum[ulCount] + 10) - (xBigNum2.m_pucBigNum[ulCount] + ucCarry);
		if(ucCarry>9)
		{
			xErg.m_pucBigNum[ulCount]	= ucCarry - 10;
			ucCarry						= 0;
		}
		else
		{
			xErg.m_pucBigNum[ulCount]	= ucCarry;
			ucCarry						= 1;
		}
	}
}

BigNum BigNum::operator+(BigNum& xBigNum)
{
	BigNum	xHelp;
	
	if(((*this).m_ulVor==0)&&(xBigNum.m_ulVor==0)) 
	{
		Add(*this,xBigNum,xHelp);
		xHelp.m_ulVor = 0;
	}

	if(((*this).m_ulVor==1)&&(xBigNum.m_ulVor==1)) 
	{
		Add(*this,xBigNum,xHelp);
		xHelp.m_ulVor = 1;
	}

	if(((*this).m_ulVor==0)&&(xBigNum.m_ulVor==1)) 
	{
		if(Kle(*this,xBigNum))
		{
			Sub(xBigNum,*this,xHelp);
			xHelp.m_ulVor = 1;
		}
		else
		{
			Sub(*this,xBigNum,xHelp);
			xHelp.m_ulVor = 0;
		}
	}

	if(((*this).m_ulVor==1)&&(xBigNum.m_ulVor==0)) 
	{
		if(Kle(*this,xBigNum))
		{
			Sub(xBigNum,*this,xHelp);
			xHelp.m_ulVor = 0;
		}
		else
		{
			Sub(*this,xBigNum,xHelp);
			xHelp.m_ulVor = 1;
		}
	}

	return xHelp;
}

BigNum BigNum::operator-(BigNum& xBigNum)
{
	BigNum	xHelp;

	if(((*this).m_ulVor==0)&&(xBigNum.m_ulVor==0)) 
	{
		if(Kle(*this,xBigNum))
		{
			Sub(xBigNum,*this,xHelp);
			xHelp.m_ulVor = 1;
		}
		else
		{
			Sub(*this,xBigNum,xHelp);
			xHelp.m_ulVor = 0;
		}
	}
	if(((*this).m_ulVor==0)&&(xBigNum.m_ulVor==1)) 
	{
		Add(*this,xBigNum,xHelp);
		xHelp.m_ulVor = 0;
	}
	if(((*this).m_ulVor==1)&&(xBigNum.m_ulVor==0)) 
	{
		Add(*this,xBigNum,xHelp);
		xHelp.m_ulVor = 1;
	}
	if(((*this).m_ulVor==1)&&(xBigNum.m_ulVor==1))
	{
		if(Kle(*this,xBigNum))
		{
			Sub(xBigNum,*this,xHelp);
			xHelp.m_ulVor = 0;
		}
		else
		{
			Sub(*this,xBigNum,xHelp);
			xHelp.m_ulVor = 1;
		}
	}

	return xHelp;
}

void BigNum::operator++(int)
{
	*this = *this + "1";
}

void BigNum::operator--(int)
{
	*this = *this - "1";
}

unsigned char BigNum::Kle(BigNum& xBigNum1,BigNum& xBigNum2)
{
  	unsigned char	ucKleiner	= 0;
	unsigned long	ulCount;

	for(ulCount=m_ulLen;ulCount>0;ulCount--)
	{
		if(xBigNum1.m_pucBigNum[ulCount-1] > xBigNum2.m_pucBigNum[ulCount-1]) 
		{
			ucKleiner	= 0;
			ulCount		= 1;
		}
		else if(xBigNum1.m_pucBigNum[ulCount-1] < xBigNum2.m_pucBigNum[ulCount-1]) 
		{
			ucKleiner	= 1;
			ulCount		= 1;
		}
	}

	return ucKleiner;
}

unsigned char BigNum::operator<(BigNum& xBigNum)
{
	unsigned char	ucKleiner	= 0;
	ucKleiner = Kle(*this,xBigNum);

	if(ucKleiner)
	{
		if((m_ulVor==0)&&(xBigNum.m_ulVor==0))	ucKleiner = 1;
		if((m_ulVor==1)&&(xBigNum.m_ulVor==0))	ucKleiner = 1;
		if((m_ulVor==0)&&(xBigNum.m_ulVor==1))	ucKleiner = 0;
		if((m_ulVor==1)&&(xBigNum.m_ulVor==1))	ucKleiner = 0;
	}
	else
	{
		if((m_ulVor==0)&&(xBigNum.m_ulVor==0))	ucKleiner = 0;
		if((m_ulVor==1)&&(xBigNum.m_ulVor==0))	ucKleiner = 1;
		if((m_ulVor==0)&&(xBigNum.m_ulVor==1))	ucKleiner = 0;
		if((m_ulVor==1)&&(xBigNum.m_ulVor==1))	ucKleiner = 1;
	}

	return ucKleiner;
}

unsigned char BigNum::Gro(BigNum& xBigNum1,BigNum& xBigNum2)
{
	unsigned char	ucKleiner	= 0;
	unsigned long	ulCount;

	for(ulCount=m_ulLen;ulCount>0;ulCount--)
	{
		if(xBigNum1.m_pucBigNum[ulCount-1] < xBigNum2.m_pucBigNum[ulCount-1]) 
		{
			ucKleiner	= 0;
			ulCount		= 1;
		}
		else if(xBigNum1.m_pucBigNum[ulCount-1] > xBigNum2.m_pucBigNum[ulCount-1]) 
		{
			ucKleiner	= 1;
			ulCount		= 1;
		}
	}

	return ucKleiner;
}

unsigned char BigNum::operator>(BigNum& xBigNum)
{
	unsigned char	ucKleiner	= 0;
	ucKleiner = Gro(*this,xBigNum);

	if(ucKleiner)
	{
		if((m_ulVor==0)&&(xBigNum.m_ulVor==0))	ucKleiner = 1;
		if((m_ulVor==1)&&(xBigNum.m_ulVor==0))	ucKleiner = 0;
		if((m_ulVor==0)&&(xBigNum.m_ulVor==1))	ucKleiner = 1;
		if((m_ulVor==1)&&(xBigNum.m_ulVor==1))	ucKleiner = 0;
	}
	else
	{
		if((m_ulVor==0)&&(xBigNum.m_ulVor==0))	ucKleiner = 0;
		if((m_ulVor==1)&&(xBigNum.m_ulVor==0))	ucKleiner = 0;
		if((m_ulVor==0)&&(xBigNum.m_ulVor==1))	ucKleiner = 1;
		if((m_ulVor==1)&&(xBigNum.m_ulVor==1))	ucKleiner = 1;
	}

	return ucKleiner;
}

unsigned char BigNum::operator==(BigNum& xBigNum)
{
	unsigned char	ucKleiner	= 1;
	unsigned long	ulCount;

	for(ulCount=m_ulLen;ulCount>0;ulCount--)
	{
		if(m_pucBigNum[ulCount-1] != xBigNum.m_pucBigNum[ulCount-1]) ucKleiner = 0;
	}

	if(ucKleiner)
	{
		if(m_ulVor==xBigNum.m_ulVor)	ucKleiner = 1;
		else							ucKleiner = 0;
	}

	return ucKleiner;
}

unsigned char BigNum::operator<(char* pcIn)
{
	BigNum	xHelp;
	xHelp << pcIn;
	return (*this<xHelp);
}
	
unsigned char BigNum::operator>(char* pcIn)
{
	BigNum	xHelp;
	xHelp << pcIn;
	return (*this>xHelp);
}

unsigned char BigNum::operator==(char* pcIn)
{
	BigNum	xHelp;
	xHelp << pcIn;
	return (*this==xHelp);
}

void BigNum::Shr(BigNum& xBigNum,unsigned long ulWeit)
{
	unsigned long	ulCount;
	for(ulCount=1;ulCount<m_ulLen;ulCount++)
	{
		xBigNum.m_pucBigNum[ulCount-ulWeit] = xBigNum.m_pucBigNum[ulCount];
	}
	xBigNum.m_pucBigNum[ulCount] = 0;
}

void BigNum::Shl(BigNum& xBigNum,unsigned long ulWeit)
{
	unsigned long	ulCount;
	for(ulCount=m_ulLen-ulWeit;ulCount>0;ulCount--)
	{
		xBigNum.m_pucBigNum[ulCount+ulWeit-1] = xBigNum.m_pucBigNum[ulCount-1];
	}

	for(ulCount=0;ulCount<ulWeit;ulCount++)
	{
		xBigNum.m_pucBigNum[ulCount] = 0;
	}
}

void BigNum::Mul(BigNum& xBigNum,unsigned char ucFact)
{
	BigNum			xHelp;
	unsigned long	ulCount;

	for(ulCount=0;ulCount<ucFact;ulCount++)
	{
		xHelp = xHelp + xBigNum;
	}
	xBigNum = xHelp;
}

unsigned char BigNum::Div(BigNum& xBigNum1,BigNum& xBigNum2,BigNum& xRest)
{
	BigNum			xHelp1;
	BigNum			xHelp2;
	unsigned char	ucCount	= 0;

	xHelp1 = xBigNum1;

	while(!(xBigNum1<xHelp2))
	{
		xHelp2 = xHelp2 + xBigNum2;
		ucCount++;
	}

	xHelp2 = xHelp2 - xBigNum2;
	xRest = xHelp1 - xHelp2;

	return --ucCount;
}

BigNum BigNum::operator*(BigNum& xBigNum)
{
	BigNum			xHelp1;
	BigNum			xHelp2;
	unsigned long	ulCount;
	unsigned long	ulLen;

	ulLen = Len(xBigNum);

	for(ulCount=0;ulCount<ulLen;ulCount++)
	{
		xHelp1 = *this;
		Mul(xHelp1,xBigNum.m_pucBigNum[ulCount]);
		Shl(xHelp1,ulCount);
		xHelp2 = xHelp2 + xHelp1;
	}

	return xHelp2;
}

BigNum BigNum::operator/(BigNum& xBigNum)
{					  
	BigNum			xHelp1;
	BigNum			xHelp2;
	unsigned long	ulLen1;
	unsigned long	ulLen2;

	ulLen1 = Len(xBigNum);
	ulLen2 = Len(*this);

	while(ulLen2>0)
	{

		while((Gro(xBigNum,xHelp2))&&(ulLen2>0))
		{
			Shl(xHelp2,1);
			Shl(xHelp1,1);
			xHelp2.m_pucBigNum[0] = (*this).m_pucBigNum[ulLen2-1];
			ulLen2--;
		}

		if(!(Gro(xBigNum,xHelp2)))
		{
			xHelp1.m_pucBigNum[0] = Div(xHelp2,xBigNum,xHelp2);
		}
	}

	return xHelp1;
}

BigNum BigNum::operator%(BigNum& xBigNum)
{
	BigNum	xHelp1;
	BigNum	xHelp2;

	xHelp1	= *this;
	xHelp2	= *this;

	xHelp1 = xHelp1 / xBigNum;
	xHelp1 = xHelp1 * xBigNum;
	xHelp2 = xHelp2 - xHelp1;

	return xHelp2;
}

BigNum& BigNum::operator=(char* pcIn)
{
	BigNum	xHelp;
	xHelp << pcIn;
	*this = xHelp;
	return *this;
}

BigNum BigNum::operator+(char* pcIn)
{
	BigNum	xHelp1;
	BigNum	xHelp2;

	xHelp1 = pcIn;
	xHelp2 = *this;
	xHelp2 = xHelp2 + xHelp1;
	
	return xHelp2;
}

BigNum BigNum::operator-(char* pcIn)
{
	BigNum	xHelp1;
	BigNum	xHelp2;

	xHelp1 = pcIn;
	xHelp2 = *this;
	xHelp2 = xHelp2 - xHelp1;

	return xHelp2;
}

BigNum BigNum::operator*(char* pcIn)
{
	BigNum	xHelp1;
	BigNum	xHelp2;

	xHelp1 = pcIn;
	xHelp2 = *this;
	xHelp2 = xHelp2 * xHelp1;

	return xHelp2;
}

BigNum BigNum::operator/(char* pcIn)
{
	BigNum	xHelp1;
	BigNum	xHelp2;

	xHelp1 = pcIn;
	xHelp2 = *this;
	xHelp2 = xHelp2 / xHelp1;
	
	return xHelp2;
}

BigNum BigNum::operator%(char* pcIn)
{
	BigNum	xHelp1;
	BigNum	xHelp2;

	xHelp1 = pcIn;
	xHelp2 = *this;
	xHelp2 = xHelp2 % xHelp1;
	
	return xHelp2;
}

unsigned char BigNum::operator!=(BigNum& xBigNum)
{
	return !(*this==xBigNum);
}

unsigned char BigNum::operator!=(char* pcIn)
{
	BigNum	xHelp;
	xHelp << pcIn;
	return !(*this==pcIn);
}

void BigNum::Random(unsigned long ulLen)
{
	BigNum	xHelp;
	unsigned long	ulCount;

	for(ulCount=0;ulCount<ulLen;ulCount++)
	{
		ZufSeed = (ZufSeed * 31421 + 6927) & 0xffff;
		xHelp.m_pucBigNum[ulCount] = (unsigned char)(ZufSeed % 10);
	}
	*this = xHelp;
}

RSA::RSA()
{
	m_ulKeyLen = LENGTH/2;
}

BigNum RSA::ModPow(BigNum& m,BigNum& a,BigNum& n)
{
	BigNum w,x,y,z;
	w = m % n;
	x = a;
	y = "1";
	z = "1";

	while(x!="1")
	{
		y = y * "2";
		x = x / "2";
	}
	x = a;
	while(y!="0")
	{
		z = z % n;
		z = z * z;
		z = z % n;
		if((x/y)=="1")
		{
			z = z * w;
			z = z % n;
		}
		x = x % y;
		y = y / "2";
	}
	return z;
}

BigNum RSA::Gcd(BigNum& xBigNum1,BigNum& xBigNum2)
{
	BigNum a,b,c;
	a = xBigNum1;
	b = xBigNum2;
	c = "1";

	if(a<b)
	{
		c = b;
		b = a;
		a = c;
	}
	while(c!="0")
	{
		c = a % b;
		a = b;
		b = c;
	}
	return a;
}

BigNum	RSA::Egcd(BigNum& xBigNum1,BigNum &xBigNum2)
{
	BigNum	q,c,d,e,w,x,y;

	c = xBigNum2;
	d = xBigNum1;
	x = "0";
	y = "1";

	while(d!="1")
	{
		q = c / d;
		e = c - d * q;
		c = d;
		d = e;

		w = x - y * q;
		x = y;
		y = w;
	}

	if(y<"0")	y = y + xBigNum2;

	return y;
}

unsigned long	RSA::IsPrim(BigNum& xBigNum)
{
   BigNum m,n,o;
   unsigned long	prim = 0;

   o = "2";
   m = xBigNum - "1";
   n = ModPow(o,m,xBigNum);
   if(n=="1") prim = 1;

   return prim;
}

void RSA::GenerateKey()
{
	m_xPrimP.Random(m_ulKeyLen/2);
	m_xPrimQ.Random(m_ulKeyLen/2);
	m_xPrivat.Random((m_ulKeyLen/3)*2);

	if((m_xPrimP % "2")=="0")	m_xPrimP++;
	while(IsPrim(m_xPrimP)==0)
	{
		m_xPrimP = m_xPrimP + "2";
	}

	if((m_xPrimQ % "2")=="0")	m_xPrimQ++;
	while(IsPrim(m_xPrimQ)==0)
	{
		m_xPrimQ = m_xPrimQ + "2";
	}

	m_xModul	= m_xPrimP * m_xPrimQ;
	m_xPhi		= (m_xPrimP - "1") * (m_xPrimQ - "1");

	while(Gcd(m_xPrivat,m_xPhi)!="1")
	{
		m_xPrivat++;
	}

	m_xPublic = Egcd(m_xPrivat,m_xPhi);
}

BigNum RSA::WordToNum(char* pcIn,unsigned long ulSize)
{
	BigNum			xSum;
	BigNum			xHelp;
	BigNum			xBas		= "256";
	BigNum			xExp		= "1";
	char			pcZahl[]	= "000";
	unsigned long	cHelp0;
	unsigned long	cHelp1;
	unsigned long	cHelp2;
	unsigned long	cHelp3;
	unsigned long	ulCount;

	for(ulCount=0;ulCount<ulSize;ulCount++)
	{
		cHelp1 = pcIn[ulCount] / 100;
		cHelp0 = pcIn[ulCount] % 100;
		cHelp2 = cHelp0 / 10;
		cHelp3 = cHelp0 % 10;

		pcZahl[0] = (unsigned char)cHelp1 + '0';
		pcZahl[1] = (unsigned char)cHelp2 + '0';
		pcZahl[2] = (unsigned char)cHelp3 + '0';

		xHelp << pcZahl;

		xSum = xSum + xExp * xHelp;
		xExp = xExp * xBas;
	}

	return xSum;
}

void RSA::NumToWord(BigNum& xBigNum,char* pcIn,unsigned long ulSize)
{
	BigNum			xHelp;
	BigNum			xRest		= xBigNum;
	BigNum			xBas		= "256";
	BigNum			xExp		= "1";
	unsigned long	ulCount;
	char			pcZahl[]	= "000";
	char			cHelp;

	for(ulCount=1;ulCount<ulSize;ulCount++)
	{
		xExp = xExp * xBas;
	}

	for(ulCount=0;ulCount<ulSize;ulCount++)
	{
		xHelp	= xRest / xExp; 
		xRest	= xRest % xExp;
		xExp	= xExp / xBas;
		xHelp >> pcZahl;

		cHelp = 0;

		if(pcZahl[0]!=0)
		{
			cHelp = pcZahl[0] - '0';
		}
		
		if((pcZahl[1]!=0)&&(pcZahl[0]!=0))
		{
			cHelp = cHelp * 10;
			cHelp = cHelp + pcZahl[1] - '0';
		}

		if((pcZahl[2]!=0)&&(pcZahl[1]!=0)&&(pcZahl[0]!=0))
		{
			cHelp = cHelp * 10;
			cHelp = cHelp + pcZahl[2] - '0';
		}

		pcIn[ulSize-(ulCount+1)] = cHelp;
	}
}

void RSA::Encode(char* pcBigNum,char* pcIn)
{
	BigNum xHelp;
	xHelp = WordToNum(pcIn,m_ulKeyLen/3);
	xHelp = ModPow(xHelp,m_xPrivat,m_xModul);
	xHelp >> pcBigNum;
}

void RSA::Decode(char* pcBigNum,char* pcIn)
{
	BigNum xHelp;
	xHelp << pcBigNum;
	xHelp = ModPow(xHelp,m_xPublic,m_xModul);
	NumToWord(xHelp,pcIn,m_ulKeyLen/3);
}


void main()
{
	RSA test;
	char txt[LENGTH/3] = "testext";
	char get[LENGTH/3];
	char Num[LENGTH];

	test.GenerateKey();
	test.Encode(Num,txt);
	test.Decode(Num,get);

	printf("%s\n",get);
}