Thursday, June 18, 2009

How (Most) Computer Security Really Works

Prime numbers, you know those number the Greeks called πρώτοι αριθμοί. Well they are important, in fact very important to the modern world. In fact the protection of all of the world's important data rest on their backs.

First lets review what a prime number is, simply put a prime number is any number which cannot be divided by any number evenly except for its self and 1. Stated more formally, x is prime if and only if its x/y is not integer except for when y = 1 or y = x. This means that 2, 3, 5, 7, 11, 13, 17, 23, ... are prime number while 4, 6, 8, 10, 12, 14, 16, ... are not (4/2 = 2, 6/2 = 3, ...).

So what does this really mean. Well there is a theory, a theory which states that any positive integer greater than 1 can be represented by the product of at least one prime number. This means that every integer greater than 1 is made up of prime numbers.

Examples:
2 = 2
3 = 3
4 = 2 * 2
5 = 5
6 = 2 * 3
...
195 = 3 * 5 * 13
...
8961 = 3 * 29 * 103
...
121980 = 2 * 2 * 5 * 7 * 11 * 787
...

This theory is called the Fundamental Theorem of Arithmetic. This theorem is more than just fundamental to arithmetic, this theorem is fundamental to computer security.

You see computer security is based on encryption. Encryption is used to transform information into an unreadable form. Encryption is undone by decryption, which is used to transform the unreadable encrypted information back into the original form of the information.

Now is when prime numbers and the fundamental theory of arithmetic come into play, you see most encryption methods use the product of two prime numbers. As the fundamental theory of arithmetic shows us, the product of two prime numbers can only be dividable by those two prime numbers and 1. This product of two prime numbers is used in different algorithms in order to generate encrypted text.

Now you know the world of computer security's deep dark secret, most of computer security is based on the fact that it is hard to do prime factorization on very large numbers.