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

Crucial SSD BIOS update

Executive summary: If Crucial Storage Executive can't see your Crucial drive, you may be able to fix that by re-running as Administrator.  Windows 10 continues to be a nightmare. The latest update has caused my machine to go wonky and it was suggested that, for reasons unknown, my SSD boot drive needed a BIOS update.  The drive in question is a Crucial MX500 CT500MX500 S SD1 and the BIOS update is from M3CR020 to M3CR023.  I initially attempted to burn and boot from a DVD ROM, but that came back with an error:  "could not find kernel image boot/vmlinuz64" You would think that something whose sole purpose is to boot into one program could get that right. That is, you would think that this very basic thing would have been tested prior to release. Sigh. No doubt there is a tortured route to get that thing to boot, but for me there was an easier way. You would think that Crucial would have offered that up first rather than the burnable image, but not in my case.  I then insta

When code writes code, what do developers do?

When code writes code, what do developers do? As we head further into a future where things are automated, people’s last refuge will be curation in a bright future or serving others in a dark future. Curation devolves into saying what you want and iterating through a few rounds of “not that.” As a programmer, I always found automated programming tools laughable. We are still mostly there, but ML/AI is changing that. At one point, many people sagely nodded their heads and said computers would *never* beat a human at chess. Never. I disagreed. I thought that it was ***inevitable*** that they ***would*** beat humans ‘hands down.’ That is well behind us now. It is only a matter of time until all human ‘jobs’ will be doable by machines. Each one, including being a companion. As of now, the bottleneck is energy and knowledge. I think we will crack fusion, but if we do not, we can still harvest billions of times what we use now from the sun in space. The knowledge is increasing rapidly.