A Business Solutions Manager at TeleCayman, Andy Tybell has a background in engineering and has extensive experience in the telecoms arena. He is the latest columnists to join the Cayman Net News team and he will be taking a weekly look at the communications world and how best to use it.
At school you probably learnt that prime numbers are numbers that can be divided only by themselves and one and that was it unless you were asked a question in the exam.
Well prime numbers do actually have applications and are in fact very important to every body every day. This is especially the case when you are communicating on the internet.
Why are prime numbers important?
Well prime numbers are used extensively in encryption mechanisms used on the internet.
Encryption is used extensively when communicating private information over a public medium, such as the internet. This may be transactions between your home computer and your work network or when connecting to the bank web site to transfer money.
Encryption is used to mask data in some way or another. It has been used for thousands of years to encode data so that other parties cannot find out the information you are passing. In the past, the application of these methods has been primarily for military purposes. Some very famous examples of cryptography you may be familiar with include the Cease Cipher used in Roman times and the famous Enigma machine used in the Second World War (for more information see http://www.nsa.gov/publications/publi00004.cfm).
The process of encryption involves three components. The private data you are going to encrypt, a cipher which is in algorithm applied to the data to make it secret and a key which is used in conjunction with the cipher.
A very simple example of encryption is called a Shift Cipher. When applied to a string of words the Shift Cipher first applies a number to each letter of the alphabet (a=1, b=2, c=3.....z=26).
At the time when you would like to encrypt a sentence it is simply a matter of taking a sentence, converting each letter to the equivalent number and then offsetting it by a certain number called a shift.
For instance a shift of 1 for the "a" would make this letter become "b". In this particular example the key is in fact the shift itself.
When the message is delivered to the other trusted person they need to be able to de-cipher (un-code) the message by using the cipher and the key.
One of the big problems with encryption is getting the key to the other party without the key being intercepted. This is a problem when you are tyring to get the information across enemy territory, a monitored radio link or even the public Internet.
This scenario is often referred to as the chicken and egg problem of cryptography. A secure conversation is initiated by first sending the key, but you need to encrypt this key which would involve needing to send another key to decrypt the original key and so on and so on.
Well a couple of very clever mathematicians worked out another way of encrypting the key itself so that exchanging the information is simple.
This method is called Public Key Encryption (PKE).
PKE method uses some special properties of prime numbers and exponents (for example a squared number 16 has an exponent of 2 and a base of 4) to keep components of information concealed.
Now say you would like to communicate a secret key. The two parties start by exchanging a public key which gives you information about the prime number being used and the base for the exponent. The two parties then randomly select and do not share two numbers which are called the private keys.
Instead of sending the private key itself, the outcome of a product of the algorithm involving the prime number, private key and a base is sent. The result of this algorithm could lead to a wide number of results.
The party receiving this information can then use their random number applied to the algorithm to find out what the original private key is. This result is then applied to the algorithm again to determine the secret key.
A party that eaves drop can only know part of the encryption method (i.e. the prime number) but not the random number or the secret key.
If you were to use a very small prime number it would not be too difficult for a clever person to work out what you are trying to find out. The best method to avoid this scenario is to select a sufficiently large prime number such that it would require a super computer a very long time to unlock the code.
To find large prime numbers is not very easy and in fact they are very difficult to calculate. The reason for this is that the larger the number the more likely that it will be a multiple of a number that proceeded it. To give you an example from 1 to 100 there are 25 prime numbers. But from 3000 to 3100 there are only 12 prime numbers.
Instead of taking all of these numbers and dividing those by all the proceeding numbers to see if they divide, large computers using very intelligent methods are used.
Another simpler way of explaining the way PKE works is by using the analogy of sending a box in the mail. Say Joe wanted Sally to send him a box safely and in the mail. To do this Joe would first send Sally a padlock and he would keep the key. Sally would then lock the package with Joes padlock and then send it to Joe. He would then use his key to unlock the parcel.
So how does this all fit into the internet. Well one of the important security issues on the internet is verifying the identity of parties. Using PKE a party can substantiate who they say they are by sharing an encrypted secret.
Often PKE is used in conjunction with passwords and digital certificates to increase the security of this method.
If you would like to find out more about PKE or RSA (another related form of encryption) I would suggest the following web sites looking at http://www.cryptographyworld.com/ . They contain information and diagrams that explain the process a little better.
Web site of the week: Here is a very funny website I found care of the BBC and is about people who like to attach themselves to small balloons and try to fly http://www.clusterballoon.org/.
