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: BigInteger is inbuilt in C#.
You only need to use the System.Numerics
library.
You might have to add the above library in the reference
section - Project >> Add Reference...; tick off System.Numerics
- to be able to use it.
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.
C# Code for DualKeyEncryption Class
using System.Numerics;
using System.Globalization;
namespace Miscellaneous
{
class DualKeyEncryption
{
BigInteger semi_prime;
public DualKeyEncryption(BigInteger semi_prime)
{
this.semi_prime = semi_prime;
}
/*
* STEP VI:
*/
public string[] encodeWord(char[] msg, BigInteger key)
{
string[] encryption = new string[msg.Length];
int x;
for (int i = 0; i < msg.Length; i++)
{
// get unicode of this character as x
x = (int)msg[i];
// use RSA to encrypt & save in base 16
encryption[i] = BigInteger.ModPow(x, key, semi_prime).ToString("X");
}
return encryption;
}
/*
* STEP VII:
*/
public string decodeWord(string[] code, BigInteger key)
{
String decryption = "";
BigInteger c;
for (int i = 0; i < code.Length; i++)
{
// use RSA to decrypt
c = BigInteger.ModPow(BigInteger.Parse(code[i], NumberStyles.HexNumber), key, semi_prime);
decryption += (char)c;
}
return decryption;
}
}
}
Main Class
using System.Numerics;
using System.Collections.Generic;
namespace Miscellaneous
{
class Program
{
static void Main(string[] args)
{
/*
* STEP I:
*/
int p1 = 101; // 1st prime
int p2 = 401; // 2nd prime
/*
* STEP II:
*/
BigInteger semi_prime = new BigInteger(p1 * p2);
/*
* STEP III:
*/
LCM l_c_m = new LCM(new List<int>() { 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
BigInteger public_key = new BigInteger(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:
*/
BigInteger private_key = BigInteger.Divide(i * lcm + 1, public_key);
char[] message = "merry xmas".ToCharArray();
DualKeyEncryption go_secure = new DualKeyEncryption(semi_prime);
string[] encrypted = go_secure.encodeWord(message, public_key);
Console.WriteLine("Message is '" + String.Join("", message) +
"';\nEncrypted version is " + String.Join(", ", encrypted));
string decrypted = go_secure.decodeWord(encrypted, private_key);
Console.WriteLine("\n\nDecrypted version is '" + decrypted + "'.");
}
}
}