RSA  Encryption&Decryption

A.First Edition

This is the  first edition of RSA encryption and decryption program. and most code are from text of 

discrete mathematics.

B.Idea of program

1。 Basic idea: 

Encryption is actually using modular theory and the theory is very profound though the algorithm is comparatively

simple. The only function by me is "inverse" which derives from Euclidean Algorithms. 

2。 Program design: 

There are some basic algorithm related with modular, such as inverse, GCD, exponent modular etc. 

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;
	ulong enModular;
	ulong deModular;
	ulong deExp;
	ulong temp[100][2];
	bool testExp(ulong e);
	void initialize(ulong e= DefaultExp);
public:
	RSA();
	RSA(ulong e);
	void setExp(ulong e);
	ulong inverse(ulong number, ulong mod);
	ulong GCD(ulong number, ulong mod);
	ulong modularExp(ulong base, ulong exp, ulong mod);
	ulong encryption(ulong input);
	ulong decryption(ulong input);
};

int main()
{
	int a, i=0;
	RSA R;
	while (i<5)
	{
		cout<<endl;
		cin>>a;
		//cout<<modularExp(2, a, b);
		cout<<R.decryption(a)<<endl;
		i++;
	}
	return 0;
}

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(ulong number, ulong mod)
{
	div_t result;
	result = div(number, mod);
	if (result.rem != 0)
	{
		temp[counter][Quotient] = result.quot;
		temp[counter][Remainder] = result.rem;
		counter++;
		return GCD(mod, result.rem);
	}
	else
	{
		return temp[counter-1][Remainder];
	}
}

ulong RSA::inverse(ulong number, ulong mod)
{
	counter =0; //initialize 
	if (GCD(number, mod)!=1)
	{
		cout<<"The two number are not relatively prime!";
	}
	else
	{
		//don't call GCD as it is already done in "if", this is really a nasty way!!!
		counter--;
		ulong scale =0;
		ulong divident, divisor;//these are quotient for 
		divident = 1;
		divisor = temp[counter][Quotient];
		
		while (counter>0)
		{
			scale = -1 * divisor;
			divisor = temp[counter-1][Quotient]* scale - divident;
			divident = scale;
			counter--;
		}
		return divident;
	}
	return -1;
}

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