All artwork, design,
logo hacks, coding,
whining, painting and
Photoshop work by Thor.

Git yurself some!
Click the + sign
to use this card!

Thor’s PKI Primer - Public Key Encryption Made Easy!

I used to know absolutely nothing about how encryption REALLY worked or even what PKI stood for. But I saw a need for a powerful, feature-rich, easy to use, and free encryption tool for the masses so I dove headlong into encryption and wrote TGP, the only free encryption tool of it’s kind. As it turns out, there are LOTS of people who are like I used to be, so I thought I’d write up a wee explanation of what PKI is, what it does, and why it’s valuable. So here we go.

There are quite a few people in this industry who don’t have a very firm grip on encryption; there is little known as to what it is, what it does, and how it works.   It’s not because they aren’t intelligent or technical enough, it’s just because they either don’t have enough interest in finding out, or it wasn't explained to them in a way that made sense.   Well, OK…  Let's face it: in some cases it is because they aren’t intelligent, but thankfully there are auditor positions for those people.   It’s actually quite interesting how the ITSec industry has allowed people who don’t know anything about security to
report on the state of security for any given entity.

Aww, was that mean?  Well, often the truth is.  Had you seen what I’ve seen, you’d feel the same way.  Anyway, enough of my conceit…

Any time one tries to simplify something very complex, by the nature of the goal, certain elements will have to be merged into easier-to-handle components.  By way of example, if I wish to describe the purpose, usage, and control considerations while operating a bicycle,  I wouldn’t bother with describing how ball-bearings work, how the chain is constructed, or how I stole one from my friend Leon when I was 13.   There are also some things that just can’t be explained until one learns it oneself.  Consistent with the bicycle analogy, consider “balance.”  I can tell you what it is, what it does, and what happens when you don’t have it, but you’ll never really know until you bust your behind a few times and figure it out on your own.

The following overview is something like the bicycle analogy - there will be simplification, but you’ll hopefully end up understanding things much better.  I’ll break it down into little pieces, but let me iterate, these examples are generalized.  (I only say that to appease the know-it-all's who always end up commenting on these things :) Anyway, I still think they'll deliver.    I'm verbose in sections as to make sure there is no room for error.  So when I repeat myself a couple of times you'll know why.  There will be repetition in this article to ensure you understand the right bits.  You can also expect some iterations, and reiterations.  See what I did there?

Introducing PKI
PKI is “Public Key Infrastructure.”  Here’s what that means, by way of another analogy:

As it relates to encryption, it can almost always be thought of in the terms of a “conversation” that two parties want to have in private.  So private, in fact, no one should ever, ever, ever be able to figure out what was said during that conversation - even if it was recorded.  How long that “ever, ever, ever” is depends on how strong the encryption is.  For the purposes of this article, let's assume it is long enough not to matter - meaning, time-bound entropy has rendered the data's value null.  That's a nice way of saying "by the time it's cracked, it will have turned into thermodynamic poo."  Now, the “two” entities can actually be any number of people exchanging data, or even encryption for one’s self.  I’m sure there are quite a few of you who cypher with your own bits all the time.   

Something bold should be here
Here's a "for instance":   As some of you may know, the "players" in PKI examples are always "Bob" and "Alice."  They are the quintessential couple we regard insofar as encrypted conversations are concerned.  I, however, will not perpetuate this precedent.  Why?  Because Bob and Alice are obviously up to something sketchy or they wouldn't always be the ones we talk about.  I'm not sure if they're doing that spouse-swapping thing or planning an attack against the International House of Pancakes, but I'm not supporting it.  One shudders.  So we'll make this personal, between you and me, because I know you trust me.

So - Let’s say I want to send you an encrypted message in the mail.  If I encrypt it and mail it to you, no one will ever know what it is.  That includes you until I can somehow get you the passcode to decrypt it.  In some manner, I need to get you this “key” - the code you’ll need to have in order to read my message. It's similar to having to know what number (key) to use on your Captain Crunch Decoder Ring to decode the cypher-text into the plaintext of “S.S. Guppy."  The PKI scheme is a way that I can get you the secret key so you can decrypt the message I will send you -
AND do it in a way so that no one can eavesdrop and steal it.  To be precise, they can eavesdrop, they just won't be able to anything useful with it as we shall soon see.  

So let’s say I want to call and give you the password (that decrypts the letter), but we both know the FBI is listening in to our calls (in addition to reading our mail).   Before I send the letter, I’m going to encrypt it with a passcode that is difficult (impossible in the real world) to guess or otherwise compromise. That way I won’t be worried about the FBI seeing it as it goes by - or if they capture it and mack on it for years - because it’s encrypted.  That part's easy.  But as I said, somehow I have to get the letter's password to you so you can open it.  That's the tricky part.  How do we do that with the FBI listening?   Well, in today’s world, I could just FedEx it to you because they are too busy being clever and watching Facebook, Twitter, and disrupting elections to remember that people can still send parcels. But let’s get back to our example.  For the sake of argument, let’s say the password to decrypt the letter itself is “ShammaLammaDingDong.”  Remember that.   Here's how we are going to exchange it:

PKI is a function where a person, entity, or process makes 2 keys.  One is a public key which anyone can have, and the other is a private key which only the owner has.  All data, when encrypted, is encrypted with a public key of some sort. 
Public keys only encrypt - they never decrypt.  They can’t, mathematically. In kind, private keys are only used to decrypt data.  They never encrypt.   So far you probably know all or some of this.  Some of you may be thinking, "why is it that you can share the public key?" That’s a great question, and I cover it below. 

A common mistake people make regarding encryption is they think public and private keys are used to encrypt the
entire contents of "the letter" and then decrypt the entire contents of the letter.  This is not true.  PKI is only used to encrypt the secret password itself, in this case, ShammaLammaDingDong.  PKI is how I tell you that the letter I’m about to send needs ShammaLammaDingDong to be decrypted without the fuzz intercepting it.  ShammaLammaDingDong is the key that actually encrypts the letter's contents.  Now we need to encrypt the word “ShammaLammaDingDong” so I can tell you what it is securely, all the while knowing the fuzz is listening to our phone call, just waiting for me to tell you the code.  At the risk of being redundant, we have to encrypt the key we used to encrypt the data.  To do this, we have to use yet another key, right?  - the one to encrypt the key which is then used to encrypt/decrypt the letter!

To do this, you will create a key-pair:  a public and a private key.  This particular implementation of PKI is called "RSA."  The acronym RSA is simply the initials of the guys who came up with the paradigm. On a side note, and this is true, another guy named Clifford Cocks actually came up with it first.  But the RSA guys were first to publish it.  I think it was a good thing, too - going to California for the RSA Conference is one thing, but taking a buddy to the California Cocks Conference could be something completely different.   No one remembers the names of the other guys, so we just use “RSA.”  Anyway, like I said, YOU create the key pair. YOU then tell ME the public key over the phone.  The FBI is listening, but we don’t care.  All the public key can do is encrypt data. 
It can’t decrypt.  If the FBI used it to encrypt data, you would still be the only one who could decrypt it.   So you tell me your public key.  I take that public key, and use it to encrypt the word “ShammaLammaDingDong.”  Once it is encrypted with your public key, even I can’t decrypt it.  That's why no one cares about the public key.  Now that I've encrypted ShammaLammaDingDong with your public key, I "read off" the encrypted password to you over the phone.  The format of the data will all be binary, so when I read it to you, it will sound like Klingon.  Anyway, you get the encrypted data, and use your private key which only you have to decrypt it.  Now you know the password for the letter itself!!  You know it'ss ShammaLammaDingDong!  I can now send you the encrypted letter and you can decrypt it because you have the password.  And that password was encrypted with a key exchanged “publicly” so that no one but us knows what it is.  If the FBI Xerox's the letter to keep, it will never be decrypted.  Not in a billion years, or until Keith Richards dies - whichever comes first. 

Let's review.  In this scenario, there were actually 2 different types of encryption used.  One is
asynchronous, and the other is synchronous.   When I encrypted ShammaLammaDing for you, I used one particular key: your public key.  When you decrypted it, you used another, different key: your private key  That’s called asynchronous - one key encrypts, and a different key decrypts.   The encryption of the letter itself was different.  When I encrypted the letter with the key ShammaLammaDingDong, you used the same key to decrypt it.  That’s call synchronous: the same key encrypts and decrypts.   Now at this point you may be saying to yourself, “self, why didn’t they just use the one key they got the first time and encrypt the letter with that?”  Well, your self has asked you a good question.   When you consider how it can be that one password encrypts and another password decrypts, you might say “WTF?  How could that possibly work?”  Well, it’s magic.  No one knows that, but it is.  OK, it’s a tiny bit of math too.   I’ll make this simple.  Figuring out how to encrypt with one password and decrypt with another is a super hard thing to do.  As such, the actual amount of data you can encrypt is super small.  It could be bigger, but it would take ages to encrypt.  To be specific, an RSA 1024 bit key (the public and private key lengths) can only hold 116 bytes.  Maybe it’s 117.  Whatever - it’s small.   A RSA 2048 bit key length can encrypt about 245 bytes.   That would be a 245 letter letter.  Sorry, a 245 “character” letter.  You know what I mean.  Now, you could certainly encrypt “Hey baby, what you wearin'?” and be done with it, but obviously we need to be able to encrypt WAY more than that. 

That’s where the “symmetric” encryption comes in.  You send me the public key, but before I encrypt the letter itself, I have to choose a big random key to encrypt it with.  This will depend on the cypher of course, but let’s say AES256.  AES is the algorithm, and 256 is the key length.  That’s really big for a symmetric key.  So, I get that really big AES number and use that to encrypt the letter (this time it’s not ShammaLammaDingDong, it’s the big random one I was just talking about)). I then use your public key to encrypt the AES key, send it to you, you decrypt the AES key and subsequently, as a different operation, you use the now-decrypted AES key to decrypt the letter.  See, symmetric encryption, since it's pretty straight-forward, can encrypt as much data as you want.  More specifically, the encryption process reads in a block of data, encrypts it, writes it back out, and then keeps doing that until all the data is encrypted. You get the key, and it encrypts little bits at a time and sticks it all together on the other side.   By the way, this is also the way your SSL connection works when you do whatever it is that your are doing that requires SSL.

Deeper Explanation
Ready for more?  Of course you are!  This is the real meat and whatever you want to go with your meat, unless you don't eat meat and you can just eat the whatever it was.   Everyone seems to like to dance over this asymmetric magic.  They all tell you "your public key is public! And your private key is private!" But they don't explain HOW! I mean, how can that work?  How can  you send me a number (key) out in front of God and everybody that I use to encrypt  but when I send the encrypted data back, only you can decrypt it?? “How do it know?”  Do the keys know each other?  Was there something sketchy going on in the back alley?  Did they use protection?  Is that what "protecting your keys" means?  There’s got to be some sort of relationship between the two, right?  Yup.

The first thing towards realizing how this can possibly work is to understand that a public key is not really “a key.”  A private key is not really “a key.”  Rather, they are both units of data comprised of several mathematical elements.   I’ve heard many folks describe the a key as, well, as a key - or better stated, a singe unit of mathematical significance.   This simple distinction may already be giving you clues on how this works.  You may be thinking, “why the hell don’t they just say that?”  For the same reason engineers call a guitar pickup a piezoelectric transducer, and why doctors call dust in your lungs Pneumonoultramicroscopicsilicovolcanoconiosis; they can charge you more money for knowing the same things you do.  

So here’s what happens.  When you go to create your keys, several processes are executed.   First we generate two very large prime numbers.  You know, like Optimus Prime.  Except he wasn't really prime because he got divided by 2 in the end.  Ba dum. Anyway, large numbers...  And I mean large, like, even bigger than 29.  We’ll keep these two big prime numbers and call one p and one q.  I wanted to call them Meryl and Streep, but she is way out of her prime.  Anyway, we then multiply p and q together, getting the product of the two large primes which is a huge number.  That would obviously be pq=(p*q).  Again, the product of the two is
pq. At this point, we need to generate a number which creates a relationship to pq called a “relatively prime” number (to be pedantic, the term "relatively prime refers to both numbers).  The two numbers are “relatively prime” when they don’t share a common factor; meaning any common number where different integers could form the product).   This new number is also called the “Stranger.”  I'm not being a smart ass this time, that's really what we old-school math people call it.  I like “Stranger” because it was one of Billy Joel’s better albums.  But I like it better because I get to call the “new” number (not pq) the Stranger in my examples.   

On a side note, (don’t let this confuse you) the Stranger is not really a Stranger to the product pq as one may be led to believe.  It is a Stranger to the product of (p-1)*(q-1).  See, all prime number are odd.  Not “odd” like “strange,” and not “strange” like Stranger, but odd like ending in a 1, 3, 5 ,7, 9.  Finding a Stranger to pq could be a very long process.  To help with that, we create an even number, (p-1)*(q-1), and solve for its stranger.  So we subtract 1 from each of the two large prime numbers p and q.  Two even numbers multiplied together is always an even number.  This reduces the number of possible factors required to iterate through before finding a Stranger.  It's faster to find the Stranger if one number is odd and the other even.   As you can imagine, some of the formulas for this stuff are pretty complex.  They’ve got lots of parentheses, squiggly lines, and one even has that big, backwards "E" that some dyslexic Greek came up with, but that’s why I went ahead and wrote all the code for you.

Anyway, we find a Stranger to the product of (p-1)*(q-1).  We’re going to call the Stranger “d.” (By the way, I’m not just making up the letters.  They are standard for RSA algorithms - I am bound by Geek Guild Law to preserve them).  Now, this is going to sound way more complicated than it is, but we now have to get the “multiplicative inverse” of d.  Ooooh.  That sounds hard!  Nope, just stick a 1 over it and make it a fraction.  But now we need to get the modulus of (p-1)*(q-1)!  Modulus?? Wasn't he the ET looking dude on that Star Trek episode?  Oh, back to modulus...  It's easy.  Divide them and whatever is left over is the modulus.  I don’t know why they just don't say that, but whatever.  We then call that number “e.”

So where are we?  We’ve got p,q,pq,(p-1)*(q-1),d, and e.  That spells PqpqDE, or “Pi'quiddy.”  And that's how you get the key! "Pi'quiddy" is always the key for any RSA key!  That’s it!  Oh, there’s another way, too.  We now have everything we need to ‘cipher up some figga’s.  To create the private key, we’ll take p and q, which then allows us to make qp,  We then take d, (the Stranger) and package that up with p & q.  That it - that's the private key.  It is now a data unit containing q,p, and d.  The public key however, is only given pq - that is, the
product of p * q, but not p and q individually.  We then package up pq with e.  That’s the public key.   The public key only has the product pq and the multiplicative identity of the Stranger.   I had the multiplicative identity of a stranger once.  It was hot.  But we now have our "keys."  The product pq can be given to everyone because the algorithm to decrypt the data requires p and q.   People in the public, if snooping, would only have pq.   It’s like this:  To make it simple, let say I use the large prime number 5,816,267,416,546,567,109 as the basis for my public key..  I put it on a bulletin board.  You can do that with your public key.  Anyway, you now have it.  If someone overheard that huge key, and wanted to "crack" it, they would have to figure out which 2 numbers I multiplied together to get that number.  Here, you try.  It’s OK, I’ll wait.  hmm hmm...  la la la...  See?  You'd be at your TI-30 for a very long time factoring prime numbers.  But you can encrypt something for me with the huge key (and a bit of math) and when I get that encrypted data, I can decrypt it because my private keys knows the two primes are: (32,416,188,271) and (179,424,779).  And that's the skinny on that.

That’s it!  Now have a gander at TGP -
Thor’s Godly Privacy!