Practical Public Key Cryptography

Encryption is one of the pillars of modern-day communications. You have devices that use encryption all the time, even if you are not aware of it. There are so many applications and systems using it that it’s hard to begin enumerating them. Ranging from satellite television to your mobile phone, from smart power meters to your car keys, from your wireless router to your browser, and from your Visa to your Bitcoins — the list is endless.

One of the great breakthroughs in the history of encryption was the invention of public key cryptography or asymmetrical cryptography in the 70’s. For centuries traditional cryptography methods were used, where some secret key or scheme had to be agreed and shared between the sender and the receiver of an encrypted message.

Asymmetric cryptography changed that. Today you can send an encrypted message to anyone. This is accomplished by the use of a pair of keys: one public key and one private key. The key properties are such that when something is encrypted with the public key, only the private key can decrypt it and vice-versa. In practice, this is usually implemented based on mathematical problems that admit no efficient solution like certain integer factorization, discrete logarithm and elliptic curve relationships.

But the game changer is that the public key doesn’t have to be kept secret. This allows cryptography to be used for authentication — proving who someone is — as well as for encryption, without requiring you to have previously exchanged secrets. In this article, I’ll get into the details of how to set yourself up so that anyone in the world is able to send you an e-mail that only you can read.

Public Key Cryptography in a Nutshell

But first, how does it work in theory? Let’s say that Alice wants to talk to Bob. (Yes, it’s Alice and Bob again.) Alice and Bob generate their respective pair of keys. They tell the whole world about their public keys, including one another. Alice can now use Bob’s public key to encrypt a message that only Bob can read — only Bob’s private key can decrypt the message and, as the name implies, it should be kept private and known only to Bob.

Imagine Alice wants to send the world (or Bob) an important message, and prove that it comes from her? In the times we live in, how could we make sure the message Alice claims to have sent is not a fake? Well, Alice uses her own private key to encrypt her important message. The world just has to use Alice public key to decrypt the message, since it is the only way to decrypt it and only the person with Alice private key could have encrypted it, hence proving that it was Alice that wrote that message.

Let’s Get Alice Started

So, assuming Alice has GPG installed, she would start by creating her own public/private key pair:


alice@wonderland ~ $ gpg --gen-key
gpg (GnuPG) 1.4.20; Copyright (C) 2015 Free Software Foundation, Inc.
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.

Please select what kind of key you want:
(1) RSA and RSA (default)
(2) DSA and Elgamal
(3) DSA (sign only)
(4) RSA (sign only)
Your selection? 1

RSA keys may be between 1024 and 4096 bits long.
What keysize do you want? (2048)

Requested keysize is 2048 bits
Please specify how long the key should be valid.
0 = key does not expire
<n> = key expires in n days
<n>w = key expires in n weeks
<n>m = key expires in n months
<n>y = key expires in n years
Key is valid for? (0)
Key does not expire at all
Is this correct? (y/N) Y

You need a user ID to identify your key; the software constructs the user ID
from the Real Name, Comment and Email Address in this form:
"Heinrich Heine (Der Dichter) <heinrichh@duesseldorf.de>"

Real name: Alice
Email address: alice@wonderland.xyz
Comment: Mushroom
You selected this USER-ID:
"Alice (Mushroom) <alice@wonderland.xyz>"

Change (N)ame, (C)omment, (E)mail or (O)kay/(Q)uit? O
You need a Passphrase to protect your secret key.
...
public and secret key created and signed.

pub 2048R/96FE8CE5 2017-10-13
Key fingerprint = B5FF 1BE3 4502 F425 A444 D6EC FBEC 78AE 96FE 8CE5
uid Alice (Mushroom) <alice@wonderland.xyz>
sub 2048R/76E5C437 2017-10-13

Depending on Alice’s needs, setting up key expiration might be a good idea. After this command, it is a good idea to export and store a copy of the keys somewhere safe, ideally with redundancy. She can, for example, store a copy in a USB drive and print a hardcopy and put it in a safe.


alice@wonderland ~ $ gpg --export-secret-key alice@wonderland.xyz > ./alice-gpg-backup.gpg

alice@wonderland ~ $ gpg --export-secret-key -a alice@wonderland.xyz
-----BEGIN PGP PRIVATE KEY BLOCK-----
Version: GnuPG v1

lQPGBFngvxUBCADNVg9j2iNv3FuzscUOe9oZqP0xCk8p9s+ApIDTqD6vZFkXLpYs...
-----END PGP PRIVATE KEY BLOCK-----

The above commands perform a backup and outputs an ASCII version of the private key, suitable for printing. The private key implementation of OpenPGP actually contains a complete copy of the public key, so this backup file is enough to recover the key pair. Restoring the backup is done with the --import flag.

Tell The World Who You Are

Now that Alice has her key, it’s time to tell the world about it. There are several ways to do it. On the command line:


alice@wonderland ~ $ gpg --list-public-keys
/home/alice/.gnupg/pubring.gpg
------------------------------
pub 2048R/96FE8CE5 2017-10-13
uid Alice (Mushroom) <alice@wonderland.xyz>
sub 2048R/76E5C437 2017-10-13

alice@wonderland ~ $ gpg --send-keys 96FE8CE5
gpg: sending key 96FE8CE5 to hkp server keys.gnupg.net

alice@wonderland ~ $ gpg --search-keys 96FE8CE5
gpg: searching for "0x96FE8CE5" from hkp server keys.gnupg.net
(1) Alice (Mushroom) <alice@wonderland.xyz>
2048 bit RSA key 96FE8CE5, created: 2017-10-13
Keys 1-1 of 1 for "0x96FE8CE5". Enter number(s), N)ext, or Q)uit > q

This way, Alice just published her key in a known OpenPGP Key server, accessible to anyone. (keys.gnupg.net is the default on my distro.) There are several key servers available to publish public keys, some of them are synchronized. I like to use pgp.mit.edu. Another option is to export the public key with the --export flag and sent it via email and/or manually publish it in several servers — the more the better. Now Alice can digitally sign her messages and receive encrypted messages directed to her. Lets see an example:


alice@wonderland ~ $ echo "This is a test file" > file.txt
alice@wonderland ~ $ gpg --detach-sign file.txt

You need a passphrase to unlock the secret key for
user: "Alice (Mushroom) <alice@wonderland.xyz>"
2048-bit RSA key, ID 96FE8CE5, created 2017-10-13

alice@wonderland ~ $ ls -l file*
-rw-rw-r-- 1 alice alice 37 Out 13 15:56 file.txt
-rw-rw-r-- 1 alice alice 287 Out 13 15:56 file.txt.sig

alice@wonderland ~ $ gpg --verify file.txt.sig
gpg: assuming signed data in `file.txt'
gpg: Signature made Sex 13 Out 2017 15:56:23 WEST using RSA key ID 96FE8CE5
gpg: Good signature from "Alice (Mushroom) <alice@wonderland.xyz>"

alice@wonderland ~ $ echo "The file contents have been tampered" > file.txt

alice@wonderland ~ $ gpg --verify file.txt.sig

gpg: assuming signed data in `file.txt'
gpg: Signature made 13 Out 2017 15:56:23 WEST using RSA key ID 96FE8CE5
gpg: BAD signature from "Alice (Mushroom) <alice@wonderland.xyz>"

When Alice wishes to shared file.txt she also shares file.txt.sig so that anyone can verify her signature. So Alice can sign but before she can send Bob a message, Bob must also have a key pair and publish his public key somewhere or sent it to Alice. Lets assume Bob already did it and Alice imported Bob’s public key into GPG, either with the --import flag or --recv-keys from a server. If Alice wants to send Bob a message she would issue the following commands:


alice@wonderland ~ $ gpg --import bob.asc
gpg: key 81DBD5F6: public key "Robert (Nope) <bob@whatdoesthebobsay.xyz>" imported
gpg: Total number processed: 1
gpg: imported: 1 (RSA: 1)

alice@wonderland ~ $ gpg --list-public-keys
/home/alice/.gnupg/pubring.gpg
------------------------------
pub 2048R/96FE8CE5 2017-10-13
uid Alice (Mushroom) <alice@wonderland.xyz>
sub 2048R/76E5C437 2017-10-13

pub 2048R/81DBD5F6 2017-10-13
uid Robert (Nope) <bob@whatdoesthebobsay.xyz>
sub 2048R/21B662BE 2017-10-13

alice@wonderland ~ $ echo "This is a secret message to Bob" > message.txt
alice@wonderland ~ $ ls -l message*
-rw-rw-r-- 1 alice alice 32 Out 13 16:25 message.txt
alice@wonderland ~ $ gpg -r bob@whatdoesthebobsay.xyz --sign --encrypt message.txt

You need a passphrase to unlock the secret key for
user: "Alice (Mushroom) <alice@wonderland.xyz>"
2048-bit RSA key, ID 96FE8CE5, created 2017-10-13

gpg: gpg-agent is not available in this session
gpg: 21B662BE: There is no assurance this key belongs to the named user

pub 2048R/21B662BE 2017-10-13 Robert (Nope) <bob@whatdoesthebobsay.xyz>
Primary key fingerprint: 1558 11B0 C87D 0E02 1C8B 304F 4982 D1D3 81DB D5F6
Subkey fingerprint: 6CC7 BC9C D69E 9465 78E4 53E3 A931 7A64 21B6 62BE

It is NOT certain that the key belongs to the person named
in the user ID. If you *really* know what you are doing,
you may answer the next question with yes.

Use this key anyway? (y/N) y
alice@wonderland ~ $ ls -l message*
-rw-rw-r-- 1 alice alice 32 Out 13 16:25 message.txt
-rw-rw-r-- 1 alice alice 678 Out 13 16:25 message.txt.gpg

This would encrypt message.txt with Bob’s public key and sign the file using Alice private key. Now Alice can send Bob the file message.txt.gpg and not only is Bob the only person able to decrypt it, he can also verify that it came from Alice as long as he has Alice’s public key. Let’s see what Bob would have to do:


bob@whatdoesthebobsay ~ $ gpg --import alice-public-key.asc
gpg: key 96FE8CE5: public key "Alice (Mushroom) <alice@wonderland.xyz>" imported
gpg: Total number processed: 1
gpg: imported: 1 (RSA: 1)

bob@whatdoesthebobsay ~ $ gpg --decrypt message.txt.gpg

You need a passphrase to unlock the secret key for
user: "Robert (Nope) <bob@whatdoesthebobsay.xyz>"
2048-bit RSA key, ID 21B662BE, created 2017-10-13 (main key ID 81DBD5F6)

gpg: encrypted with 2048-bit RSA key, ID 21B662BE, created 2017-10-13
"Robert (Nope) <bob@whatdoesthebobsay.xyz>"

This is a secret message to Bob

gpg: Signature made Sex 13 Out 2017 16:19:51 WEST using RSA key ID 96FE8CE5
gpg: Good signature from "Alice (Mushroom) <alice@wonderland.xyz>"
gpg: WARNING: This key is not certified with a trusted signature!
gpg: There is no indication that the signature belongs to the owner.
Primary key fingerprint: B5FF 1BE3 4502 F425 A444 D6EC FBEC 78AE 96FE 8CE5

Who Can You Trust?

You might have notice the WARNING message saying that Alice key is not certified with a trusted signature and there is no indication that the signature belongs to her. If Bob knows for sure that Alice key is from Alice, he can sign it and GPG will see it as trusted.


bob@whatdoesthebobsay ~ $ gpg --edit-key alice@wonderland.xyz sign

pub 2048R/96FE8CE5 created: 2017-10-13 expires: never usage: SC
trust: undefined validity: unknown
sub 2048R/76E5C437 created: 2017-10-13 expires: never usage: E
[ unknown] (1). Alice (Mushroom) <alice@wonderland.xyz>

pub 2048R/96FE8CE5 created: 2017-10-13 expires: never usage: SC
trust: undefined validity: unknown
Primary key fingerprint: B5FF 1BE3 4502 F425 A444 D6EC FBEC 78AE 96FE 8CE5

Alice (Mushroom) <alice@wonderland.xyz>

Are you sure that you want to sign this key with your
key "Robert (Nope) <bob@whatdoesthebobsay.xyz>" (81DBD5F6)

Really sign? (y/N) y

You need a passphrase to unlock the secret key for
user: "Robert (Nope) <bob@whatdoesthebobsay.xyz>"
2048-bit RSA key, ID 81DBD5F6, created 2017-10-13

gpg> save
bob@whatdoesthebobsay ~ $ gpg --decrypt message.txt.gpg

You need a passphrase to unlock the secret key for
user: "Robert (Nope) <bob@whatdoesthebobsay.xyz>"
2048-bit RSA key, ID 21B662BE, created 2017-10-13 (main key ID 81DBD5F6)

gpg: encrypted with 2048-bit RSA key, ID 21B662BE, created 2017-10-13
"Robert (Nope) <bob@whatdoesthebobsay.xyz>"
This is a secret message to Bob
gpg: Signature made Sex 13 Out 2017 16:19:51 WEST using RSA key ID 96FE8CE5
gpg: checking the trustdb
gpg: 3 marginal(s) needed, 1 complete(s) needed, PGP trust model
gpg: depth: 0 valid: 8 signed: 2 trust: 0-, 0q, 0n, 0m, 0f, 8u
gpg: depth: 1 valid: 2 signed: 0 trust: 1-, 1q, 0n, 0m, 0f, 0u
gpg: next trustdb check due at 2019-03-19
gpg: Good signature from "Alice (Mushroom) <alice@wonderland.xyz>"

The warning will disappear. But why was there a warning? So far, someone sent an email claiming to have Alice’s public key, but how does Bob know it is the Alice that he knows? Or that the initial public key exchange was not intercepted? Even though public key cryptography eliminated the need to distribute secret keys, public keys have to be distributed to others with whom they want to communicate, and if the encryption is also used for authentication, the provenance of the public keys is important.

So what are Bob’s options? Bob can meet Alice face to face where she guarantees him that her key (or her key fingerprint) is correct, and Bob can mark it as trusted by signing it as in the above example. Sometimes it is impossible to meet face to face or you are talking with someone you don’t actually know. Bob can alternately choose to trust a particular key server, which is usually quite secure. If Bob does not want to choose to trust any key server, there is another way.

The Web of Trust

GnuPG addresses this problem with a mechanism known as the web of trust. In the web of trust model, responsibility for validating public keys is delegated to people you trust. This is different from normal public key infrastructure (PKI) approach since PKI permits each certificate to be signed only by a single party: a certificate authority (CA). By contrast, OpenPGP identity certificates (which include public key(s) and owner information) can be digitally signed by other users who, by signing, acknowledge the association of that public key with the person listed in the certificate.

There are even events, known as key signing parties, where users gather with their keys and identity documents and sign each other keys. Basically, as more people sign a key, the more sure you can be that the key is from who it claims to be.

I Take It All Back

On a last note, it might be a good idea for Alice to create a revocation certificate. A revocation certificate can be used if and when Alice loses her key or she believes the key was compromised. It is published to notify others that the public key should no longer be used. A revoked public key can still be used to verify signatures made by Alice in the past, but it cannot be used to encrypt future messages to Alice. It also does not affect the ability to decrypt messages sent to Alice in the past if she still has the key.


alice@wonderland ~ $ gpg -a --gen-revoke alice@wonderland.xyz

sec 2048R/96FE8CE5 2017-10-13 Alice (Mushroom) <alice@wonderland.xyz>

Create a revocation certificate for this key? (y/N) y
Please select the reason for the revocation:
0 = No reason specified
1 = Key has been compromised
2 = Key is superseded
3 = Key is no longer used
Q = Cancel
(Probably you want to select 1 here)
Your decision? 0
Enter an optional description; end it with an empty line:
> revoke!
>
Reason for revocation: No reason specified
revoke!
Is this okay? (y/N) y

You need a passphrase to unlock the secret key for
user: "Alice (Mushroom) <alice@wonderland.xyz>"
2048-bit RSA key, ID 96FE8CE5, created 2017-10-13

Revocation certificate created.

Please move it to a medium which you can hide away; if Mallory gets
access to this certificate he can use it to make your key unusable.
As with the private key, it is smart to print this certificate and store it away, just in case
your media become unreadable. But have some caution: the print system of
your machine might store the data and make it available to others!

-----BEGIN PGP PUBLIC KEY BLOCK-----
Version: GnuPG v1
Comment: A revocation certificate should follow

iQEmBCABAgAQBQJZ5N6XCR0AcmV2b2tlIQAKCRD77Hiulv6M5XnuB/41jjJCVx/S
...
-----END PGP PUBLIC KEY BLOCK-----

The above code demonstrates how to generate a revocation certificate.

“This is too confusing!”

I get that. I do. Users don’t want to be encrypting stuff via the command line and worry about certificates and trust models. It might seem a bit overwhelming at first but luckily there are easy to use software solutions available to the end-user that solve your basic public key cryptography needs. It’s an extensive list and I’m pretty sure our readers have plenty of suggestions depending on your internet use and operating system. Let’s hear them in the comments!

For example, to secure emails, there are several options. If you use Thunderbird, you can install Enigmail. It should work on Linux, Windows, Mac and SunOS/Solaris. For Outlook users, look for gpg4o or gpg4win. Apple Mail has GPGTools. Android has K9 and R2Mail2 while iOS has iPGMail. If you don’t use a specific email client but use webmail instead, you are not left out, you can try Mailvelope. Mailvelope is an extension for Chrome and Firefox that implements OpenPGP and works over your regular webmail client.

Regarding email encryption, you can see that there is a lot to choose from. There is probably a OpenPGP implementation available to your email client of choice, it’s a matter of choosing a solution for a software that you are already accustomed and start from there. So if you don’t use encryption yet, what is your excuse now?

Go and create your key pair, share it with the world! And do it now, before the next revolution in cryptography, quantum computing, kills it all.

23 thoughts on “Practical Public Key Cryptography

  1. “One of the great breakthroughs in the history of encryption was the invention of public key cryptography or asymmetrical cryptography in the 70’s.”

    The other was the NSA taking their fingers out of export control. Remember when Netscape use to come in a “home” version and an export version.

    As for PGP the hardest thing about it is “ease of use” not the technology itself.

  2. Hmmm…. Have I just also spotted an unintended 64-character password generator?

    Take the private key, tweak it a little to invalidate it as a key and use that as the pass phrase to generate another private key…

    Though that idea is probably flawed also… currently I’m using a 32-character base passcode that I remember off the hat when I need it or bits of it and another 32 character passcode for logging into my laptop.

    The look on peoples’ faces when they see me type seemingly random keys at a fast-ish pace with the passcodes being subsequently accepted by my laptop for the power-on, OS-login and the mobile-modem activation passcodes.

    1. A better option is to hash your public key using sha256 or some other hash algorithm. If you need to generate multiple passwords, concatenate a nonce to the public key before hashing. A nonce is just a number that you increment for each iteration. This is also essentially how bitcoin addresses are generated.

      1. Actually don’t do that with your public key, sorry for the confusion. If the public key is actually shared publicly and someone guesses you are using this method, then they could also generate your passwords. Instead, use some other string of text as the input that is secret.

    1. Screen output is indeed very hard to decipher for the novice cryptographer, a clue here is that it’s written left to right and top to bottom in a challenge/response format.

    2. What is it that you are trying to understand? Do you want to know the basic principle of asymmetric encryption (“what’s a private key and a public key, what’s encryption and decryption, what does signing mean, etc.”)? Or do you know that stuff already and now want to understand how it is possible that asymmetric encryption works the way it does?

      In the first case, there are _a lot_ of (both good and bad) explanations of that on the internet. If you want, I’ll see if I can pick out one that I think explains the concept well.

      In the second case, things may get a little more involved. Asymmetric encryption is usually built using a certain kind of mathematics, so understanding more deeply how it works usually involves a bit more effort. If there’s a way you can hear course on the subject (if you’re enrolled in university, for example, or if you find an online course), that’s probably not the worst idea. However, if you just want a quicker overview of the maths, maybe take a look at this article I just found: https://arstechnica.com/information-technology/2013/10/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/ . It has got a small example that shows how you can encrypt a message using RSA.

      In both cases, knowing all this command line stuff is not necessary. That is something you only need when you actually want to encrypt or decrypt something.

    3. I thought this page explains it quite well. Not sure what you mean by “noobs”… perhaps you could be more clear?

      I would agree there are better ways to present the terminal output to make user input clearer from machine output, but the above isn’t too bad to understand.

      The command line stuff, the author shows a typical Unix shell prompt here, so alice@wonderland ~ $ denotes the shell that Alice sees when she opens her terminal. Likewise for Bob, bob@whatdoesthebobsay ~ $ is what he sees as the prompt on his computer. A Raspberry Pi running stock Raspbian with the pi user would see something like pi@raspberry ~ $. The form shown is ${USER}@${HOSTNAME} ${CURRENT_DIRECTORY} ${SHELL_MODE} where ${USER} is the user’s login name, ${HOSTNAME} is the name of the computer being used, ${CURRENT_DIRECTORY} is the current working directory (~ means the user’s home directory, typically /home/${USER} on Linux, /Users/${USER} on MacOS X, historically might’ve been /usr/${USER} on earlier Unix platforms), and ${SHELL_MODE} indicates whether the shell is running as a standard user ($ prompt), or as an administrator (# prompt).

      Everything typed after that prompt is the user input. Everything seen there between the end of that command and the next prompt is the application, with input from the user and output from the program. So in the first example, alice@wonderland ~ $ gpg --gen-key, gpg --gen-key was the command entered, and everything that followed is user-entered input to, or output generated from, the gpg command.

      Asymmetric crypto comes in many forms. OpenPGP is just one application of it (and GnuPG being one implementation of OpenPGP). The underlying algorithm used will likely be RSA (there is DSA and ECC too), combined with a hashing algorithm (when signing; such as SHA256) or symmetric encryption algorithm (when encrypting; such as AES) and Wikipedia have an explanation of RSA here.

      Perhaps it’s worth taking a step back and explaining what you don’t understand about the above? As I do not understand your lack of understanding.

  3. Great article, thanks!

    A question and two minor nits :)

    Q: Why does it say “Signature made Sex 13 Out 2017”, curious which language is associated with that date formatting!

    N1: s/looses/loses

    N2: “Go and create your key pair, share it with the world! ” Don’t share the pair with the world, only share the public with the world and keep your private stuff private!

    1. Q: Never realized how strange that may sound in English. It is indeed portuguese and it is short for Sexta (Friday)
      N1: Thanks, fixed.
      N2: Aha! Glad you were paying attention. :)

        1. I hear the EU now reiterated that the ‘privacy shield’ agreement is sound, for now, surely, sorta, oh-OK not – but let’s pretend.
          Not that it matters if all EU spook (or ‘security’) services are all subservient to the US and even proactively help them destroy EU citizen’s privacy and steal industrial secrets to give to the US, with approval of EU governments.

  4. Question: Is public key cryptography possible on hardcopy (paper)? I’ve often thought it would be cool to print out a bunch of gibberish either in text or in a giant QR code, and mail it to somebody. They would scan it in, and use their private key to decrypt it. It would just be fun for games or scavenger hunts, etc. So far I haven’t found any cryptography software for use on paper, but maybe I’m just looking in the wrong place.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s