Skip to main content

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.

Comments

Popular posts from this blog

The system cannot execute the specified program

It always annoys me no end when I get messages like the following: "The system cannot execute the specified program." I got the above error from Windows XP when I tried to execute a program I use all the time. The message is hugely aggravating because it says the obvious without giving any actionable information. If you have such a problem and you are executing from a deep directory structure that may be your problem. It was in my case. Looking on the web with that phrase brought up a bunch of arcane stuff that did not apply to me. It mostly brought up long threads (as these things tend to do) which follow this pattern: 'Q' is the guy with the problem asking for help 'A' can be any number of people who jump in to 'help'. Q: I got this error "The system cannot execute the specified program." when I tried to ... [long list of things tried] A: What program were you running, what operating system, where is the program? What type of

The JWST did not take resources away from the poor.

The JWST project employed many people for a long time. It helped them and their communities. Like other NASA projects, it has funded technology breakthroughs that will pay back the investment. Right now, mathematical physicists are working on a new theory that combines quantum physics and relativity and explains how the two emerge from a common root structure. This will be aided by knowledge of the early universe we get from JWST. A breakthrough there could lead to essentially limitless low-cost energy. It could possibly lead to crazy stuff like anti-gravity and magnetic monopoles. It could extend the periodic table, and allow us to create exotic substances, it could allow us to create room temperature superconductors, and it could conceivably allow us to figure out how to explore the galaxy. Our understanding of electromagnetism since the 19th century has allowed us to do miraculous things that people in earlier centuries would simply think of as pure magic. Reaching for the stars is

Coming Soon: General Artificial Intelligence

The closer you get to experts who understand the nuts and bolts and history of AI, the more you find them saying that what we have is not nearly General Artificial Intelligence (GAI), and that GAI seems far away. I think we already have the roots in place with Neural Networks (NN), Deep Learning (DL), Machine Learning (ML), and primitive domain limited Artificial Intelligence (AI). Things like computer vision, voice recognition, and language translation are already in production. These are tough problems, but in some ways, machines are already better than humans are. I expect GAI to be an emergent property as systems mature, join, and augment one another. I was around during the 70s AI winter, and was involved in the 80s AI winter as one of the naysayers. I built a demonstration system with a Sperry voice recognition card in 1984. I could demonstrate it in a quiet room, but as a practical matter, it was not production ready at all. Around 1988 we built demonstration expert systems usin