John P Hurst's Introduction to PKI and GPG

This is by no means an exhaustive nor complete explanation of the subject. This introduction is intended for those who wish to understand the concepts of the Public Key Infrastructure well enough to determine whether its features are valuable to them and provide enough information that they can proceed.

PKI systems provide a means by which a message may be sent over eMail, or any other medium, in a manner that is believed to be readable only by the intended recipient. There are no known ways to break this encryption at this time and the math is well enough understood that it is likely to be impossible for the foreseeable future.

Traditionally, when two parties wanted to send messages that could not be read by others they agreed on a code. Messages between them were encoded using the code and it was assume that any would be eavesdropper would be unable to decode the messages since he did not have the code. This method of encryption remains valid and secret, s long as the chose code is good enough. As children many of us played with code where for example we replaced each letter with the next letter in the alphabet, so "Hello There" would be encoded as "Ifmmp Uifsf". For obvious reasons this code is relatively easy to break. The two parties have a shared secret, being that the next letter will be used and hope that others do not realize this.

Spies in the past used more complicated codes with "code books". A code book may be a list of words and for each word a random number. "Hello There" could not be "0213 7921" and as long as the would be listener did not have the code book it was relatively safe. But even this method has a two critical flaws: 1) if the code book is lost or copied the code becomes unusable or insecure; 2) frequency analysis may disclose the code book. ("the" is the most common word and if "6572" appears most often in messages then there is a good chance that 6572 is the code for the, et cetera.)

Both of the above code systems assume that the sender and receiver share a secret, being either the code book, or the coding system. PKI requires NO SUCH sharing of information.

In PKI systems I PUBLISH what is known as my Public Key, the world can and should know it. I keep my Private key secret. There is a relationship between my Public Key and My Private Key but there is no known way to generate one from the other.

If you want to send a message to me, you encode it with MY Public Key. This encoding is a mathematical operation that is simply performed by a computer. The encoded messages is then transmitted to me. I then use My Private Key to decrypt it. Since no one else has my Private Key, no one else can decode the message.

The mathematics of how and why the Public Key and Private key are related is beyond the scope of this discussion, but it is accepted mathematics at this time that there is no known method of generating a Private Key knowing the Public Key, nor the reverse operation. It is also proven that the encryption provided by the system is to all intents and purposes unbreakable.

With traditional encryption systems if I have the "plain text", that is the message before encryption, and the "cipher text", the encrypted message, I can determine the key that is needed for decryption. With PKI the mathematics ensure that this is not the case. This is why my Public Key can and should be published.

Feel free to skip this paragraph. The mathematics uses functions that are easy in one direction and hard in the other. In simple arithmetic we see such functions all the time. Consider the number 323. If asked to factorize this, even with a calculator it will take a number of attempts, whereas if I ask you to multiply 17 by 19 you can instantly generate 323. PKI uses this basic concept, take to a more extreme version.

For example, if you looked up my Public Key and then used GPG, one of the best PKI tools, to send the message to me, you would actually send:

-----BEGIN PGP MESSAGE-----
Version: GnuPG v1

hQIMA3SRd865atpYAQ//SzaeYESwQeV1Pf0fpP/svVpAhsj7EUJr17LUl3OHOT5Q
mzRdUhEZ/ZOIoN+Yevw71GZeEiYBI9+UzY36ktTdg9gKvHn0k+NWd3ChnG/eVgjB
pVzETIH8wVivlPL1U7hV43PDzciZxDRYpKe+JKCi7gmUF3E773NNmFLKpTWtKqzG
VOrq4MNTza3671KuoXNx18/mVgcVbIwhgZ8pWDswveUJlMKwJtJrAkYBx1S5xJAx
X1C0xVqceAfE2ZuUDuP5L54RJmHGoM3g0zzX6E+1AucwKmI9FN0DfMUaNtGAtGY/
CDBPNPcvIxDmlpdgT4ebWzWgD56go6NJt5xEyOg4Ls82Z9BwB68BUKY/oapD3nwp
m4Nwyt1z1YsSH+mQkB8rhHAmAYUmj5JRb4hJjAo6pKn6KpcHFMNgUeGtWFV/go/U
GDJu2exZZ6yQMajHPrIKTWPz3Q9pYqhMJieXdOtYHdJOZsbM+cW3Dsx5Zl2Enb73
6EgF0PKUuI/zZzmcVaQKrJFqZYEUJmcNj8TJBH2clNjzzol/xAEX+pFC1AQIh6Ef
epGr2Rq1KacnOaiOQ1WqDGQ9/rs7c2YWp9QfWaAav4WlKtsMcMTOm7RARakHizeS
ryVV1tFZanzetVTypclcN4nR0E4lsiTv4onwrXUikJKZgyAdCSIfy+f7A/PyskjS
RwF3whwaKOQ1wjIcSbXAJ7HmZZuTPFy65AWAOpv/Wn8Fdqu9VmlDus4m7b6k5OfH
+2NvatGiydammU2qYizFMawGOmqVBK8t
=xdX5
-----END PGP MESSAGE-----
over the Internet if the real message was "Hello There". There is no known way to reverse the encryption, to perform a decrypt without knowing my Private Key, which of course I do not disclose.

My mail reader is "intelligent enough" to recognize that this message needs to be decode and would apply my Private key and I would see the correct message. Good PKI tools make this almost transparent. (In this case a rather short message has become rather large. This occurs with small messages since there is some overhead and some padding so that the lengths of the messages do not disclose information.)

I have said previously that the "magic of PKI" is that ONLY MY Private Key can decode messages encrypted using My Public Key. Interestingly enough a feature of the mathematics ensure an additional feature, being that any message encoded with My Private Key can only be decrypted with My Public Key. So, if I used my Private key to encode the message and you are able to decode it with my Public Key, then you could be certain that it was from me, a form of very secure "signing". Actually, since the entire message is signed this is better that an traditional signature since the signature is specific to the message. If you can decrypt it with my Public Key you know not only that I sent it, but that I sent THIS message.

My Public Key is published not only on my own site but also at all of the major Public Key Servers, such as pgp.mit.edu. Thus if you want to send a secret message to me then you collect a copy of my Public Key, use it to encrypt the message and send the encrypted message to me. If you receive a message claiming to be from me you can ensure it is really from me by ensuring that it can be decrypted using my Public Key. While this sounds a lot of work, good Mail Clients such as Thunderbird and even Gmail will handle this for you, virtually transparently.

When you are ready to use PKI you generate a Key Pair, the Public and Private Keys. You publish your public key, or send it to those you wish to communicate with and keep your Private Key VERY SECURE. No one else should ever know or have access to your Private Key.

Each Kay Pair is unique, and is identified by a Fingerprint. My key has the fingerprint: 839D 23C2 F61F D3BB 5F92 B6CF 3F6E 1AE7 2A44 EB84 The number of possible keys exceeds 1.4 followed by 48 zeros, an extremely large number. In fact the number of potential keys exceeds the number of of atoms in the universe multiplied by the age of the universe multiplied by almost any other number we could think of. Basically it is unique. In practice one often checks only the last 8 characters of the fingerprint, in my case 2A44 EB84 since even this matches only one in every 4 billion keys and the chance of a clash is small enough that it can generally be ignored. There is NO known way that a key can be generated to match a fingerprint, so if a message is signed by me with my fingerprint you can be relatively certain it is from me. If it is encrypted to my key, as identified by my fingerprint you can be certain that no one else can read it, unless I disclose my key or decrypt it for them.

As discussed above the 8 character version of the fingerprint uniquely identifies over 4 billion key pairs. If PKI ever caught on as it should then this would not be enough since there are more than 4 billion people in the world. Therefore, there are some paranoid or optimistic people who identify their key with a 16 character sequence, mine being: 3F6E 1AE7 2A44 EB84 which identifies uniquely more than more than 1.8 followed by 19 zeros key pairs. This would allow for one for every person on every planet in the universe, even assuming that every star had as many planets with populations as does our sun. Essentially this is unique.

We can be relatively certain, especially since the Snowden revelations that even the governments of the world can not break this encryption and signing system.

We have considered both encryption and signing. PKI allows a single message to be encoded twice, therefore I could encode the message with my Public Key and your Private Key. I would be then certain that ONLY you could read it since only you have the required Private Key and you could be certain that it was from me since my Public Key would decrypt the signature.

PKI is wonderful but has gained very little acceptance because it is an "add on" to eMail and many mail clients do not make it easy to add. For those using Gmail on the Chrome Browser there is a wonderful and simple extension providing GPG, a great version of PKI. The source code of the add-on is published and is secure and can be trusted, at least at the time of this writing. If you are interested in GPG for Gmail, click the link and learn more.

Return to my Home Page


© 2016 John P Hurst - All Rights Reserved