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