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