The Magic of Primes in PKI

     Almost all of us that live in an internet enabled world have used PKI (Public Key Infrastructure) in some form or fashion. If you work in the information technology field, more specifically on the security side of the house, you would have definitely heard of PKI. Every time we use email, do our online banking or connect to our offices networks using VPN we could possibly be using PKI. The PKI framework itself is so pervasive and robust that it is abstracted from the general user community. In the bargain we have forgotten that it evens exists or bother to think about how it works.

     From a high level perspective it is fairly easy to understand how PKI functions. It is essentially a two key (asymmetric) encryption system that provides authentication and confidentiality. Lets assume two users (Andy and Bob) want to communicate securely over a public network where transmitted data can by spied upon easily. To prevent the spying Andy can encrypt the message he sends to Bob using key X. The issue we now have is that if Andy encrypted the data using key X, how does he send the key to Bob to decrypt it without it being compromised. This problem is what the PKI framework solves. It does this by generating two keys per user (a public key and a private key) that are mathematically linked to each other. The public key as its name implies is public and can be shared with others. Now if Andy needs to communicate with Bob he requests the public key for Bob. Once Andy receives the key he encrypts the message and sends it to Bob. This message can only be decrypted using Bob's private key which never leaves his person. A hacker that compromised the encrypted message and Bob's public key will never be able to decrypt Andy's message leaving him rather perplexed.

     Lets take a look at the actual math behind PKI, because that is where it gets really interesting. Before we do that, we have to understand that PKI is a framework and not a technology implementation, therefore I am going to show you how the RSA algorithm that implements the PKI framework functions. The public key is actually made up of two parts. One is a composite of two primes (two primes multiplied by each other) which you will see below referenced as k1 and the second is an exponent which will be referenced as e. This is a special exponent that needs to fulfill the following requirements. The exponent needs to be an integer. The exponent cannot be a factor of k1. In addition it needs to be greater than 1 but less than φ(k1). What exactly is φ(k1) you ask ? It is all the numbers that are less than k1 but greater than 1 and do not share a common factor with k1.  It all sounds too complicated but lets take a look at φ(9) as an example.

1. Lets list out all the numbers that are lesser or equal to 9 = (1,2,3,4,5,6,7,8)
2. Now we will mark in red all the numbers that share a factor with 9 except for the number 1 and erase them (1,2,3,4,5,6,7,8)
3. We are now left with 6 numbers (1,2,4,5,7,8 ) 
4. So the φ(9) =  6

Step 1 - Generate Public Key

To generate a public key we pick two large primes and multiply them together to form a composite. For this example we will pick small primes so that it becomes easier to work with.

• k1 = PrA x PrB
• k1 = 23 x 29
• k1 = 667

Lets also pick an exponent that meets the requirements such that 1 < e < φ(k1). For this example I am going to pick  the number 3. What we are left with is two numbers k1 = 667 and e = 3. These two numbers together make up the public key.

Step 2 - Generate Private Key

• k2 = 2(φ(k1))+1 / e
• k2 = 2(φ(667))+1 / 3
• k2 = 2(616)+1 / 3
• k2 = 1232+1 / 3
• k2 = 1233 / 3
• k2 = 411

Remember that k2 is the private key that is never distributed to anyone, It is only used to decrypt messages that are sent to you which is encrypted by k1 and e which together make up your public key.

Step 3 - Data Encryption

Now that we have both a public and private key we can begin to encrypt data. We will attempt to encrypt the word "bag" as an example. Firstly we need to convert the word "bag" to some sort of numerical value so that we can do calculations against it. The easiest way to do this is to find the numerical place value of the letters. For example "b" will have a value of 2 as it is the second letter in the English alphabet. By that logic the word bag = 217. Now we can begin the encryption process.

• ed = data^e mod k1
• ed = 217^3 mod 667
• ed = 10218313 mod 667
• ed = 540

Step 4 - Data Decryption

If you are attempting to do this on a calculator even with the fairly small numbers that I have shown here the calculations are going to be huge. I am including a link for a big integer calculator here which will help you make these calculations (http://goo.gl/GXSdCv)

• dd = ed^k2 mod k1
• dd = 540^411 mod 667
• dd= 10323697896242668219954362115926597275247250862687291172394408598235646340560963277503503134090563294398280979796545134818573213064741511000526138653105369880225616050484894381599128674424417000626405170045975711797996349495340567543681315349755878142749780282862273187818683269529600679603730315376728985279076969364683520463773650596665685647638324598792650556617337357191019481317184045352277937331907517838610430973762375649970512352333359870591860750640525281545205463597201920722441526847683758018612285502996206303677486482364237501952886563083240964158025078640998912337940214285221812259921170151592015645065351114155483987914299497389946764598690494890769755112018882602072423747515993913989410381103104000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 mod 667
• dd = 217

Our decrypted message is 217. If we pass his through our letter place value calculation we will come up with the word "bag".