Brau BärHinterlasse einen Kommentar auf Alter Code: RSA Verschlüsselung

Alter Code: RSA Verschlüsselung

RSA gehört zu den bekanntesten asymmetrischen Verschlüsselungsverafhren. EIngesetzt wird es unter anderem im Austausch von Schlüsseln für symmetrische Verschlüsselungen in zum Beispiel SSL. Die Sicherheit von RSA besteht darin, dass der Schlüssel aus zwei Primzahlen zusammengesetzt ist und deren Zerlegung sehr aufwendig ist (Primzahlzerlegung, Faktorisierung) und so lange es keine günstigen Quantencomputer gibt es auch so bleiben wird. Für die Implementierung benötigt man eine Zahlenklasse, die mit grossen Zahlen umgehen kann.


// 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");
}
*/

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);
}
Werbung

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

Gravatar
WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. ( Abmelden /  Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. ( Abmelden /  Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. ( Abmelden /  Ändern )

Abbrechen

Verbinde mit %s

Diese Seite verwendet Akismet, um Spam zu reduzieren. Erfahre, wie deine Kommentardaten verarbeitet werden..

%d Bloggern gefällt das:
search previous next tag category expand menu location phone mail time cart zoom edit close