crsa.cpp

rsa加密算法很好的例子

// CRSA.cpp: implementation of the CRSA class.
//
//////////////////////////////////////////////////////////////////////

#include <iostream.h>
#include <string.h>

#include "CRSA.h"
#include "LLrsa.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CRSA::CRSA()
{
	nums = new char[27]; // initialize the alphabet list
	char ch = 'A';

	for (int i = 1 ; i < 27 ; i++)
	{
		nums[i] = ch++;
	}

}

CRSA::~CRSA()
{
	delete[] nums;
}

//function to encrypt the data
char* CRSA::Encrypt(char* data,long e,long p,long q)
{
	int m;
	char c1,c2;
	unsigned int i = 0;
	long cipher_part;
	char* ccipherp = new char[5];
	char* cipher = new char[2*strlen(data)];
	memset(cipher,0,sizeof(cipher));
	
	int ndigits = getNumLength(p*q); // number of digits in n

	char *ccipherp2;
	
	while(i < strlen(data))
	{
		c1 = data[i++];

		if (i != strlen(data))
			c2 = data[i++];
		else
			c2 = '-';

		m = convDataToNum(c1,c2); // convert the first two characters to number

		cipher_part = process(m,e,p,q);
		ltoa(cipher_part,ccipherp,10); // convert the cipher to string

		ccipherp2 = compFour(cipher_part,ndigits); // complete four digits

		cipher = strcat(cipher,ccipherp2);
		cipher = strcat(cipher,ccipherp); // add this string to the overall cipher

//		break;
	}

	return cipher;
}

//function to decrypt the data
char* CRSA::Decrypt(char* data,long e,long p,long q)
{
	long d = calcDecExp(e,p,q);

	int nData = strlen(data); // length of the data

	int ndigit = getNumLength(p*q);

	int i = 0; // index to traverse the data array

	long c; // numerical cipher to be converted back
	long m; // the converted data

	int mlen; // length of the decrypted message

	char* dec = new char[strlen(data)/2];
	int j = 0;

	while(i < nData) // the string is still remaining to decrypt
	{
		c = getNextToDec(i,nData,data);

		m = process(c,d,p,q);

//		cout << endl << m << endl;

		mlen = getNumLength(m);

		if (mlen <= 2)
		{
			dec[j++] = nums[m];
		}
		else if (mlen == 3)
		{
			dec[j++] = nums[(m/100)];
			dec[j++] = nums[(m%100)];
		}
		else
		{
			dec[j++] = nums[(((m/1000)*10)+((m%1000)/100))];
			dec[j++] = nums[((m%1000)%100)];
		}
	}

	dec[j] = '\0';

	return dec; // return dectrypted message
}

// convert the string to numeric equivalents
int CRSA::convDataToNum(char c1,char c2)
{
	int num1,num2,num;
	char cn1[2],cn2[2],*cn;

	for (num1 = 1 ; num1 < 27 ; num1++) // find the index of the first number
	{
		if (nums[num1] == c1)
			break;
	}

	for (num2 = 1 ; num2 < 27 ; num2++) // find index of the second number
	{
		if (nums[num2] == c2)
			break;
	}

	cn1[0] = '0'; // make the number two digits
	if (num1 < 10)
	{
		itoa(num1,&cn1[1],10);
	}
	else
	{
		itoa(num1,cn1,10);
	}

	cn2[0] = '0'; // make the number two digits
	if (num2 < 10)
	{
		itoa(num2,&cn2[1],10);
	}
	else
	{
		itoa(num2,cn2,10);
	}

	if (num2 == 27)
	{
		cn = cn1;
	}
	else
	{
		cn = strcat(cn1,cn2);
	}

	num = atoi(cn);

	return num; // return complete number
}

//function to take the square
long CRSA::square(long m, long p, long q)
{
	long n = p*q;
	
	int sn = m*m; // take the square

	return sn%n;
}

//function to add the two exponents
long CRSA::add(long v1,long v2,long p,long q) {

	long n = p*q;
	long v = v1*v2;

	return v%n;
}

// function to process the logic
long CRSA::process(long m, long e, long p, long q)
{
	long value;
	long mye = 1;
	long mye_add = 1;

	CLLrsa* list = new CLLrsa();

	list->insert(1,m);

	while (mye < e)
	{ // go upto the encryption exponent

		if (mye+mye_add < e)
		{
			mye += mye_add;
			value = square(m,p,q);
			mye_add = mye;
		}
		else
		{
			value = list->getNextToAdd(mye_add,mye,e);
			mye += mye_add;
			value = add(m,value,p,q);
		}

		list->insert(mye,value);

		m = value;
	}

	delete list;

	return m;
}

// get number of digits in a number
int CRSA::getNumLength(long n)
{
	char cn[10];
	ltoa(n,cn,10);

	return strlen(cn);
}

// the number of zeroes leading to make 4 digitd
char* CRSA::compFour(long m,int ndigits) {

	long cipher_part = m;

	int ccpn = getNumLength(cipher_part); // get length of the returned value
	char* ccipherp2 = new char[5];
	memset(ccipherp2,0,sizeof(ccipherp2));

	char* zero = "0";

	while(ccpn < ndigits) // the number is less in digits with the n
	{
		ccipherp2 = strcat(ccipherp2,zero); // insert some zeroes in front
		ccpn++;
	}

	return ccipherp2;
}

// calculate the decryption exponent
long CRSA::calcDecExp(long e, long p, long q)
{
	long n = (p-1)*(q-1);

	long value = 1;

	while( value%e != 0 ) // still d is not found
	{
		value += n;
	}

	return (value/e); // return the decryption exponent
}

// get the next number to decrypt
long CRSA::getNextToDec(int& i,const int nData,char* data)
{
	int j = 0;
	char c1,c2,c3,c4;
	char cipher[4];

	c1 = data[i++];

	if (i != nData)
		c2 = data[i++];
	else
		c2 = '-';

	if (i != nData)
		c3 = data[i++];
	else
		c3 = '-';

	if (i != nData)
		c4 = data[i++];
	else
		c4 = '-';

	cipher[j++] = c1;

	if (c2 != '-') // there is second character
		cipher[j++] = c2;

	if (c3 != '-') // there is third character
		cipher[j++] = c3;

	if (c4 != '-') // there is fourth character
		cipher[j++] = c4;

	cipher[j] = '\0';

	return atol(cipher);
}

// verify the validity of e,p,q and relative primes
bool CRSA::verify(long e, long p, long q)
{
	if (!isPrime(e)) // e is not prime
		return false;

	if (!isPrime(p)) // p is not prime
		return false;

	if (!isPrime(q)) // q is not prime
		return false;

	if (e%(p*q) == 0)
		return false;

	return true;
}

// function to check whether a given number is prime or not
bool CRSA::isPrime(long p)
{
	int i;

	for (i = 2 ; i < p/2 ; i++) // divide the number with all the numbers less than its half
	{
		if (p%i == 0) // number divided
			return false;
	}

	return true;
}