RSA  Encryption&Decryption

A.2.5 Edition

This is the second edition of RSA encryption and decryption program only with a slight difference.

I only add Chinese remainder method.

B.Idea of program

1。 Basic idea: 

Chinese remainder method takes two int array plus its size as params. The algorithms is very simple and it is in text. First

you calculate the total product of all modulos, then for each mod, you simply exclude it and then calculate the inverse of that 

modulos. I don't know how to express it. But it is simple when you see it.

2。 Program design: 

I only want to make a demo how to use the functions.

#include <iostream>

using namespace std;

typedef unsigned long ulong;

const ulong Prime1 = 43;
const ulong Prime2 = 59;
const ulong DefaultExp = 13;


enum DivName
{Quotient, Remainder};

class RSA
{
private:
	int counter;
	int exp;
	long divident;
	long divisor;
	ulong enModular;
	ulong deModular;
	ulong deExp;
	ulong gcd;
	long temp[100][2];
	bool testExp(ulong e);
	void initialize(ulong e= DefaultExp);
	void internalCalculate(long number, long mod);
public:
	RSA();
	RSA(ulong e);
	void setExp(ulong e);
	void linearCombination(long number, long mod);
	long inverse(long number, long mod);
	ulong GCD(long number, long mod);
	ulong modularExp(ulong base, ulong exp, ulong mod);
	ulong encryption(ulong input);
	ulong decryption(ulong input);
	int chineseRemainder(int size, int* number, int* mod);
};

int main()
{
	
	int num1[3] ={2,3,4};
	int mod1[3] ={3,5,11};
	int num2[3]={5,6,7};
	int mod2[3]={45,49,52};
	
	RSA R;
	

	cout<<"\nQ1 is:";
	R.linearCombination(3457, 4669);
	cout<<"\nQ2 is "<<R.inverse(144, 233);
	cout<<"\nQ10a is"<<R.chineseRemainder(3, num1, mod1);
	cout<<"\nQ10b is"<<R.chineseRemainder(3, num2, mod2);
	cout<<"\nQ11 is"<<R.modularExp(17, 23, 131);
	cout<<"\nDecrpt\n";
	cout<<"0667 = "<<R.decryption(667);
	cout<<"\t 1947 = "<<R.decryption(1947);
	cout<<"\t 0671 = "<<R.decryption(671);

	
	return 0;
}

int RSA::chineseRemainder(int size, int * number, int* mod)
{
	int M =1;
	int result =0;
	for (int i=0; i< size; i++)
	{
		M *= mod[i]; //M is the product of all mod
	}
	for (i=0; i< size; i++)
	{
		result += number[i] * M / mod[i] * inverse(M/mod[i], mod[i]);
	}
	return result;
}





void RSA::linearCombination(long number, long mod)
{

	internalCalculate(number, mod);
	cout<<"\nThe linear combination is: "<<number<<" x "<<divident<<" - ";
	cout<<" "<<divisor<<" x "<<mod<<" = "<<gcd<<endl; 
}

void RSA::setExp(ulong e)
{
	if (!testExp(e))
	{
		cout<<"Input exponent is not relative prime to modular!\n";
		cout<<"Default exponent is used!\n";
		exp = DefaultExp;
	}
	else
	{
		exp = e;	
	}
	deExp = inverse(exp, deModular);
}

ulong RSA::encryption(ulong input)
{
	return modularExp(input, exp, enModular);
}

ulong RSA::decryption(ulong input)
{
	return modularExp(input, deExp, enModular);
}

void RSA::initialize(ulong e)
{
	counter =0;
	enModular = Prime1* Prime2;
	deModular = (Prime1 -1)*(Prime2 -1);
	setExp(e);	
}

RSA::RSA(ulong e)
{
	initialize(e);
}


bool RSA::testExp(ulong e)
{
	return GCD(e, deModular)==1;
}

RSA::RSA()
{
	initialize();
}


ulong RSA::modularExp(ulong base, ulong exp, ulong mod)
{
	ulong shifts = exp; //in order to shift to test each bit
	ulong test;   //mask and also temp result to see bit value
	ulong power; //the base modular 
	ulong result =1;  //final result
	power = base % mod;

	for (int i=0; i< 32; i++)
	{
		test =1;
		test &= shifts;  //bit-and assignment
		if (test)  //if it is 1, then result times power
		{
			result *= power;
			result %= mod;
		}
		power *= power;
		power %= mod;
		shifts>>= 1;
		if (shifts==0)
		{
			break;
		}
	}
	return result;
}




ulong RSA::GCD(long number, long mod)
{
	div_t result;
	long tempDivident, tempDivisor;
	tempDivident = number;
	tempDivisor = mod;
	counter = 0;

	result = div(tempDivident, tempDivisor);
	
	//if they are not relative prime
	if (result.rem == 0)
	{
		temp[counter][Quotient] = result.quot;
		temp[counter][Remainder] = result.rem;
		counter++;
		gcd = mod;
		return gcd;
	}
	
	while (result.rem != 0)
	{			
		temp[counter][Quotient] = result.quot;
		temp[counter][Remainder] = result.rem;
		counter++;
		tempDivident = tempDivisor;
		tempDivisor = result.rem;	
		result = div(tempDivident, tempDivisor);
	}
	gcd = temp[counter-1][Remainder];
	return gcd;

}

void RSA::internalCalculate(long number, long mod)
{
	long scale =0;
	GCD(number, mod);
	//these are quotient for 
	counter--;
	if (counter ==0&&temp[counter][Remainder] ==0)//this is mod|number!!!
	{
		divident = 1;
		divisor = divisor =temp[counter][Quotient] -1;
		return;
	}
	divident = 1;
	divisor = temp[counter][Quotient];
	
	while (counter>0)
	{
		scale = -1 * divisor;
		divisor = temp[counter-1][Quotient]* scale - divident;
		divident = scale;
		counter--;
	}
}


long RSA::inverse(long number, long mod)
{
	//counter =0; //initialize 

	internalCalculate(number, mod);
	if (gcd == 1)
	{
		

		return divident;
	}
	else
	{
		cout<<"\nThese two number are not relative prime!"<<endl;
		return 0;
	}
}


			

The following is result of program:

 (I found out the reason why Decryption outcome is different from solution:  the "0" in 0667

means number 667 in base of "8"!!! and it is by chance that the two number 0667 and 0671 are all

digits under 8!!! otherwise I will find out this mistake earlier!)		

Q1 is:
The linear combination is: 3457 x 1252 - 927 x 4669 = 1

Q2 is 89
Q10a is488
Q10b is31415
Q11 is122
Decrpt
0667 = 1808 1947 = 1121 0671 = 417