RSA  Encryption&Decryption

A.Second Edition

This is the second edition of RSA encryption and decryption program. and I find out and correct the mistakes 

of GCD.

B.Idea of program

1。 Basic idea: 

Last edition cannot find correct GCD if two number are divisible. Now I made it a special case among all others.

In this edition, I add a new function "linearCombination" which gives coefficients of these two numbers to

form a linear equations with their GCD.

2。 Program design: 

I made a internal method "internalCalculation" to split function "inverse".

4。 Further improvement：

I plan to find two very big prime number to use as "Public Key", so I write a simple program to search for 

such big primes. see here:

#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 main()
{
	int a, b, i=0;
	RSA R;
	while (i<5)
	{
		cin>>a;//>>b;
		cout<<R.decryption(a)<<endl;
		//cout<<R.decryption(R.encryption(a))<<endl;
		//R.linearCombination(a, b);
		//cout<<R.GCD(a, b)<<endl;
		//cout<<R.inverse(a, b)<<endl;
		i++;
	}
	return 0;
}

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 a small silly program to search for all prime numbers. It use the simplest algorithms, so

it runs hours to finish. I simply save every prime number I find in an array and future number just test

if it is divisable by the prime in array. And as the factor of a composite is less or equal to its square

root, so it can save some time.

#include <iostream>
#include <cmath>

using namespace std;

typedef unsigned long ulong;

const ulong MaxNum = 0xFFFFFFFE;

ulong array[59999999];

ulong counter =0;

bool test(ulong number)
{
	ulong temp;
	temp = sqrt(number);
	for (int i =0; i<counter; i++)
	{		
		if (array[i]>temp+1&&number%array[i]==0)
		{
			return false;
		}
	}
	array[counter] = number;
	counter++;
	return true;
}

void addPrime(ulong prime)
{
	array[counter] = prime;
	counter++;
}

void initialize()
{
	addPrime(2);
	//addPrime(3);
}

void display()
{
	for (int i=0; i<counter; i++)
	{
		cout<<"Prime no."<<i<<" is "<<array[i]<<endl;
	}
}
	


int main()
{
	ulong i =2;
	initialize();
	
	while (i<MaxNum)
	{
		test(i);
	
		i++;
	}
	display();

	return 0;
}