Welcome to part two in the series from Jason Wallace on Public Key Infrastructure. If you didn't read Jason's first article explaining PKI I suggest you nip back down the post list of The Manageability Guys to get up to speed. Over to you again Jason...


This is the second in a series of blog posts aimed at introducing PKI so that we can hopefully gain an understanding of the core concepts involved in a PKI.

We left off having considered that information can be encrypted using a protocol and a key, but considering the implications of needing to exchange keys.  This is a problem that perplexed many people for many years - how do I successfully ensure that a short-term key can be securely exchanged.

For many years, people would be issued with some form of code book.  People would have the code of the day and use that code to exchange messages.  Later, they realised that if all messages were exchanged using that key and the key for the day was compromised then all communications for that day would also be compromised.  This is when procedures changed and people would first of all invent their own, new key and send that key encrypted by the day key to the recipient.  Now, we had the concept of the session key.  We also had the idea of in-band key exchange.

All of this, however still relied on us having some form of code book.  That code book would have to have enough pages to cover for long enough to span a replacement of a code book.  If, for example we were supplying code books to infantrymen then a short code book would suffice as it would be possible to replace, say monthly.  But how about a submarine on patrol for many months at a time, for example?

So enters in Public Key Cryptography otherwise known as Asymmetric cryptography.

All history is stories, and there are many stories surrounding the inception of Public Key cryptography - whether it was some clever people in Langley, USA or some clever people in Cheltenham, UK, or some clever university professors.  Sitting here in my study in Cheltenham I can tell you that we know the real story!

The idea of public key cryptography is really quite simple - the idea is that you and I agree a protocol and then within that protocol I construct two keys: the private key, which I will always protect and NEVER allow anybody to access, and a public key which I'll allow anybody to have access to.  These two keys will be mathematically related somehow but the public key will not give any clue as to the content of the private key.

Easy?  Kind of

So, let's look at our protocol.  Let's say the following:

  • A private key will be the sum of two randomly selected prime numbers
  • A public key will be the multiplication of these two randomly selected prime numbers

So, if I were to choose, say 3359 and 1249 as my primes, my private key would be 4608 and the public key 4195391.

What's so cool about that?  Well, pretty much the fact that in order to determine which primes went to make up 4195391 the attacker would need to try each set of prime numbers in sequence to see whether the result was a prime number - something called factoring.

It's all way more complicated than that, and the numbers which we are using are way way larger than two numbers selected from Wikipedia's table of the first 500 primes (remember that we don't know how much time or CPU time the attacker has), but the key point (sorry for the pun) [RY: No he isn't] is that the actual PRIVATE key NEVER goes across the wire in band.  In fact, pretty much anything that involves the private key going anywhere is a concern!

Given this, if you know that my PUBLIC key is 4195391 then you can encrypt some data with this key and I can use my PRIVATE key to decrypt the data.  Hey presto!  I cannot send you anything back though - for that, I'd need your PUBLIC key!

Equally, If I were to encrypt a piece of data with my PRIVATE KEY, then assuming that my private key is indeed private then the only person who could have encrypted that piece of data was me!  That's a big assumption there, though - the assumption that private keys are indeed always kept private.

So, we have started to achieve two of our goals - those of CONFIDENTIALITY and AUTHENTICITY.  More on those later.

There are a couple of major issues which we encounter with Public / Private Key cryptography:

  • We know that there is a distinct possibility that the private key could be mathematically calculated by an attacker from the public key - it's just going to take an attacker with a huge amount of time and/or processing power. Or an attacker who is much more clever than the person who invented the encryption protocol and has spotted a weakness. To mitigate this, we tend to revert to very long key lengths and to complex mathematics, which can make these kinds of protocols slow to use
  • The more data which we send across the wire which is encrypted with any given key then potentially the bigger pool of data which the attacker can use to attack our key there is.

So, what we will tend to do is to use a public key protocol to encrypt a session key for communications and exchange this key with the recipient and then revert to a much simpler, but faster symmetric key for the actual data encryption.  That's why, for example you will see DH/3DES combinations in, say your IPSEC rules, where Diffie Hellman is the public key protocol and 3DES is the symmetric one.

As a side note, all of our assumptions over the mathematics involved are being challenged by products such as Elliptical Curve Diffie Hellman which allow for very fast, very efficient public key cryptography. Oh, and ALL of our assumptions about cryptography in general are being challenged by Quantum Computing, but we'll leave that for people much cleverer than I.


Disclaimer: The information on this site is provided "AS IS" with no warranties, confers no rights, and is not supported by the authors or Microsoft Corporation. Use of included script samples are subject to the terms specified in the Terms of Use.

This post was contributed by Jason Wallace, a Premier Field Engineer with Microsoft Premier Field Engineering, UK