Public Key Encryption

Explaining Public Key Encryption

Many years ago, as a part of my company's research, I built a tool called 'DataHush'. It was a drag and drop encryption/decryption program. The tool, as I built it for original demonstration, did not include standard Public Key encryption. Patents encumbered well-known systems and I have always shied away from patents.

Despite not supporting it in the original tool, the design demanded Public Key encryption and supporting Infrastructure (PKI). It also had facilities that I felt improved upon the strength of PKI as generally practiced. I felt it necessary to explain to business partners just exactly HOW Public Key encryption worked and how, for banking and mission critical information PKI alone was (potentially) flawed.

I am currently working on a project where I have been asked to deliver some tools and protocols for an advanced secure infrastructure. First, though, it requires PKI and most people have such a hard time with the basics they have no hope of understanding the finer points of what my company has done to improve upon current PKI.

When I originally published information on our old system, I put together as simple an explanation as I could for PKI. This is still not entirely accessible to people without at least High School Math from the latter years. However, it does convey a concrete interpretation that should be meaningful to more people than typical discussions of this subject. So ... I dug up my old explanation (from the WayBack machine, bless them), formatted it for this environment and ... Here it is.

Here’s How it works

Public key encryption is based on a mathematical relationship between prime numbers, and the (presumed) computational difficulty of doing particular mathematical operations on large numbers( such as factoring (RSA) or discrete log (ElGamal)).

Here is an example of a particular public key system (RSA) whose strength depends upon the difficulty of factoring large numbers:

To start, we need to pick two prime numbers. In practice, these are very large multi-digit numbers. Here, we use small values to make it easier to understand.

Chose p1 and p2, say 3 and 11. We obtain an exponent value from the following equation:

(p1-1) * (p2-1) + 1 = x


For our numbers, this works out to be:

(3-1) * (11-1) + 1

= 2 * 10 + 1

and

x = 21


Now, multiply p1 by p2 to obtain a ‘modulus’ value (m). For our numbers, this equals:

3 * 11

and

m = 33


For any value (v) from 0 to (m-1), there is an equation that holds true:

v = vx mod m


Now we factor the exponent value such that factor 1 (f1) multiplied by factor 2 (f2) is equal to the exponent value. In our case:

f1 * f2 = x


3 * 7 = 21


So:

f1 = 3 and f2 = 7


One of the factors is chosen as our public key, the other our private key. We make life easier for the public by choosing the smaller of the two.

To encrypt a message, someone takes the (known) public key and uses that to encrypt the message using the following formula:

Encrypted = Plain ^ f1 mod m


For our example, let’s say the letter G is being encoded and (to make the math easier) it’s the 7th letter in our alphabet. We assign it a value of 7. So:

Encrypted = 7^3 mod 33


= 13

To decrypt, you use the formula ‘in reverse’:

Decrypted = Encrypted ^ f2 mod 33


In our case, this yields:

Decrypted = 13 ^ 7 mod 33


= 7


We have our original message back. Math weenies go nuts for this stuff!

It is important to understand, math aside, that the encryption is not symmetrical. This gives it important properties, which we exploit.

1) You can only read a message encrypted with one key if you hold the other key.

2) Anybody can send you a secure message by encrypting with your public key.

3) If we can decrypt with the public key, the sender encrypted with the private one.

It is essentially (with some optimizations) item three above that constitutes digital 'signing'. If we know you are the owner of a given public key and we can prove that a message decrypts with that public key and your private key is only under your control, then you must have 'signed' that message.

Here’s How it Fails

Public key encryption has a point of weakness in that two vital pieces of information are known by the attacker - the public key and the algorithm chosen for encryption. Although no civilian scientist has published an elegant method of attacking the algorithm mathematically, it has not been proved invulnerable to attack. It may already be the case that military or government scientists have discovered a computationally simple way of cracking this method of encryption. It is certainly a possibility. Meantime, a modified brute force method leaves public key encryption highly suspect. Here’s why:

Although it is computationally very difficult to examine and try all of the prime numbers in the ‘open’ range, in practice the method of generating keys is such that once one of the keys is chosen, the other may fall within a range that can be narrowed down using the public key. Once you have chosen a limited selection of numbers to try, you simply run the whole set through the known algorithm until you reveal the private key. Once a private key has been discovered, it is useless and all messages encoded with that key are open to examination.