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