Private Key - Public Key Encryption Mechanism
A Private Key - Public Key Encryption works much like a padlock
that is operated with two different keys: one key for the sole purpose
of locking the padlock, and the other to open it only; just as was
illustrated in our introduction to data security section.
In a Public Key - Private Key encryption system, one key is open to
the public - rightly called the Public Key; which can only be used to
encrypt data or file to be transferred say over the Internet.
The other key is kept secret - obviously called the Private Key; Its main
function is to decrypt any encrypted data or file sent to it over a
transfer medium - usually the Internet.
The beauty of the Public Key - Private Key Encryption System is that data
encrypted with the Public Key cannot be decrypted with the same Public Key.
A ready scenario to the apt use of this could be a situation where a subject Teacher
in class poses a question and every student is to attempt an answer.
The students submit their answers in encrypted form with a public key given by the
Teacher and the Teacher displays each answer as they come on a projector.
After every student has submitted an answer, the Teacher shows the correct
answer on the projector, then decrypts every students answer to reveal which student(s)
may have gotten the correct answer to the posed question.
Done this way, no students can take clues from other students' answers for their own answers.
This set-up can also be used in a live hosted (Quiz) Programme if all viewers can have
access to the encryption algorithm to be used.
This way, not even behind-the-scene Technicians or even the Producer can see (and leak)
the entries or answers viewers have submitted until the Show Host is ready to reveal them.
The Open-Lock-Only Conundrum
The above hypothesis sounds like the perfect theory until it has to be
implemented.
The big question then is just how do you design an encryption algorithm
that a user can encode data with given the set of parameters available to
him/her, but cannot decode the obfuscated data using the same parameters?
This is what we call the Open-Lock-Only Conundrum.
Going down the time-line of Mathematics, much help is not found.
This is because almost every single Binary Operation in Mathematics has
a complementary opposite.
Addition is reversed with Subtraction; Multiplication is reversed with
Division; Even Unary Operations like Sine, Cosine and Tangent are reversed
with their Arc counterparts.
The only binary operation close to one without an opposite is the Modulus (not Young's).
Modulus is even more interesting when you consider the fact that working out 12 % 5 yields 2;
but so also does 22 % 5 and 37 % 5 and so on and so forth; making it almost impossible to tell
exactly [what number] % 2 yielded 2 in a posteriori.
This provides a nice cover for any Open-Lock-Only encryption since there is
always an infinite number of correct solutions to any modulus operation.
This cover however is only adequate with humans since computers can proffer these answers
in virtually no time; Reverse Engineers can tell the likely solution simply by inspecting
all available answers.
To further spice things up though, moduli of data to be encrypted are carried out with
prime numbers since computer algorithms known so far take too long - exponential
time - to factor semi primes or list prime numbers.
Hence if parameters can be chosen in a doctored fashion, an Open-Lock-Only algorithm
becomes achievable.
To carry out an Open-Lock-Only algorithm in C++ however, the
following steps are carried out with precision, viz:
- Two (large) prime numbers are chosen, we will call them p1 and p2.
-
The prime numbers are multiplied to produce a semi-prime.
Semi-prime will go hand in hand with the Public Key and Private Key so it is also a public knowledge. -
The Lowest Common Factor (L.C.M.) of p1 - 1 and p2 - 1 is calculated.
We will simply call it lcm. -
A (prime) number that lies between the range of 1 to lcm is chosen;
this will be the Public Key.
One condition in picking the Public Key is that it must have no common factors with the lcm.
Or put differently, the Highest Common Factor (H.C.F.) of Public Key and lcm must be 1; Picking a prime number as the Public Key almost guarantees this. -
Finally, the Private Key is calculated as the
Modular Multiplicative Inverse of the Public Key.
I.e.,(public_key * private_key) % lcm = 1. -
To encrypt data using the Public Key, you do:
[Unicode(data)]public_key % semi_prime = encoded_data; -
To decrypt coded data using the Private Key, you do:
[encoded_data)]private_key % semi_prime = original data;
moduli of data to be encrypted are carried out
In answer to speed of computers problem, real Public Key - Private Key algorithms use very
large prime numbers that are almost impossible to factor in linear time for the current prime
number algorithms that are known to the programming community...
By The Way: The encryption algorithm described in the above steps is called
R.S.A. algorithm; and coming up with an algorithm that can factor very large semi primes
into their prime factors in linear time is called the R.S.A. problem.
You can try your hands on it and see whether you can solve this problem!
Also noteworthy is the fact that there are other ways of implementing an
open-lock-only encryption algorithm; like the Logarithm Encryption, e.t.c.
If you interested in knowing more, an Internet search for Public Key - Private Key Encryption
should bring up some relevant results - Wikipedia especially has some
very fine articles on Public Key - Private Key Encryptions.
Create a new C++ class file;
Call it DualKeyEncryption
.
Type out the adjoining C++ code for encrypting and decrypting a chunk of data
using a Public Key - Private Key pair.
Important: We obligatorily wrote a BigInteger class
for use with this section.
It is freely available on Github
or you can download it as a zip file here.
The algorithm class for finding LCM
has been explained in the Primary Category.
Create a new C++ class file called LCM in your current
project and copy the L.C.M. code into it.
DualKeyEncryption Header File
#include "BigInteger.h"
#include <string>
#include <vector>
using namespace std;
class DualKeyEncryption
{
public:
DualKeyEncryption(int);
virtual ~DualKeyEncryption();
vector<string> encodeWord(vector<char>, int);
string decodeWord(vector<string>, int);
private:
string semi_prime;
};
C++ Code for DualKeyEncryption Class File
#include "DualKeyEncryption.h"
DualKeyEncryption::DualKeyEncryption(int semi_p)
{
semi_prime = to_string(semi_p);
}
/*
* STEP VI:
*/
vector<string> DualKeyEncryption::encodeWord(vector<char> msg, int key) {
vector<string> encryption = {};
string x;
for (size_t i = 0; i < msg.size(); i++) {
// get unicode of this character as x
x = to_string((int)msg[i]);
// use RSA to encrypt & save in base 16
encryption.push_back(BigInteger::decToHex(BigInteger::powerModulus(x, key, semi_prime)));
}
return encryption;
}
/*
* STEP VII:
*/
string DualKeyEncryption::decodeWord(vector<string> code, int key) {
string decryption = "";
string char_string;
int c;
for (size_t i = 0; i < code.size(); i++) {
char_string = "";
// use RSA to decrypt
c = stoi(BigInteger::powerModulus(BigInteger::hexToDec(code[i]), key, semi_prime));
char_string += (char)c;
decryption += char_string;
}
return decryption;
}
DualKeyEncryption::~DualKeyEncryption()
{
}
Main Class
#include "LCM.h"
#include "DualKeyEncryption.h"
#include <iostream>
using namespace std;
int main() {
/*
* STEP I:
*/
unsigned p1 = 101; // 1st prime
unsigned p2 = 401; // 2nd prime
/*
* STEP II:
*/
int semi_prime = p1 * p2;
/*
* STEP III:
*/
// get L.C.M. of p1-1 and p2-1
LCM l_c_m({ p1 - 1, p2 - 1 });
int lcm = l_c_m.getLCM();
/*
* STEP IV:
*/
// pick a random prime (public_key) that lies
// between 1 and LCM but not a factor of LCM
int public_key = 313;
// find 'public_key' complement - private_key - such that
// (public_key * private_key) % LCM = 1
//this involves some measure of trial and error
int i = 1;
while ((lcm * i + 1) % public_key != 0) {
i++;
}
/*
* STEP V:
*/
int private_key = (i * lcm + 1) / public_key;
vector<char> message = { 'm', 'e', 'r', 'r', 'y', ' ', 'x', 'm', 'a', 's' };
DualKeyEncryption go_secure(semi_prime);
vector<string> encrypted = go_secure.encodeWord(message, public_key);
string disp = "", msg = "";
for (size_t i = 0; i < encrypted.size(); i++) {
disp += encrypted[i] + "; ";
msg += message[i];
}
cout << "Message is '" << msg << "';\nEncrypted version is " << disp << endl;
string decrypted = go_secure.decodeWord(encrypted, private_key);
cout << "\n\nDecrypted version is '" << decrypted << "'.";
return 0;
}