Bob, Alice and Eve
Computer Security is subject a great subject to study, especially that the area is ever changing, and basically involves the understanding of virtually everything to do with computing … including networks, software, embedded systems, people, crime, and so much more. The thing I love most is cryptography, especially that it is the continual battle between man and computer. A computers get more powerful by the day, and the cloud can distribute both the storage of information and also the processing, it gets more challenging for humans to keep anything secret from them. They thus can determine where we have been, what we have been watching, what we like to have for lunch, and what type of coffee we like, so it’s nice to know that we can still be them at cryptography. Well, we don’t actually beat them, we just make it so difficult, that eventually the humans controlling them will give up. In past times, as you can see from Figure 1, we could code our messages in a way that only Bob and Alice knew the secret code. Unfortunately there was no way of knowing that Eve had actually discovered the code. So humans have had to derive task which are so simple when you know a secret, but extremely difficult if you do not know it.
Big Numbers and Primes
When I first started in computing computers could only deal with 8 bits at a time – known as the 8-bit processors, such as the Intel 8008. Microprocessor technology then evolved through 16-bit processors (such as with the Intel 8086) and onto 32-bit ones (Intel 80386), and finally to 64-bit processors. Our current hardware architecture for most PCs and mobile devices runs on a 64-bit processor, even though much of the software still runs in a 32-bit mode. Thus most computers are optimized to run with values that are 64-bits long. So one of the ways to make life difficult for computers is to force them to deal with numbers that are much longer than this, such as for 256 bits (for private-key encryption) or 1,024 bit (for public-key encryption). These sizes of numbers make even the addition of two numbers a challenge task, taking many ticks of the clock. For a normal add operation the computer could, with two 64-bit numbers, do it in a fraction of a nano-second, whereas with 1,024 bits it becomes a major task to split the numbers up into chunks, and then perform the addition on the chunks, and with associated carry-over taken into account.
So we end up with the concept of Big Integers in cryptography. These are whole numbers who can be any size we want, and we can undertake some basic operations such as raising to a power, taking the modulus, adding, and so on.
So what does a Big Integer look like? Well for 512-bits we get numbers such as [Example]:
16,051,676,583,321,910,517,842,912,514,242,120,458,388,544,526,515,804,467,341,482,346, 206,707,182,147,774,421,857,300,872,391,674,336,841,094,767,996,574,497,015,038,851,049, 971,545,273,239,933,642,180,743,111,921,076,030,627,772,076,959,051,769,002,395,221,544, 838,304,706,428,767,230,398,563,872,098,020,125,093,711,002,252,870,755,574,445,367,073, 595,571,270,521,653,567,709,801,758,861,271,551,464,325,540
and the challenge for a computer is actually to determine the two prime numbers that when multiplied together actually provides this value. If you’re interested, in this case, they are:
8,044,675,477,712,008,752,023,823,019,578,452,312,930,831,161,771,900,648,214,214,337,291, 200,072,984,849,707,468,990,717,567,849,714,452,612,612,027,658,352,992,397,524,927,866, 652,768,863,179,707,737,287
and:
1,995,316,856,198,054,868,182,625,824,794,282,420,425,397,624,446,426,871,607,556,212,261, 659,943,148,990,748,085,163,805,134,774,302,595,456,418,515,934,616,814,703,707,291,062, 474,935,597,665,671,744,391
This might not seem a difficult task, as surely computers know all the prime numbers possible? Well the answer is no, it takes a great deal of computing power to determine if a number if prime, and we haven’t found them all yet. So normally what we do when we are selecting one is we pick a number, and test if it is prime, if not, take one away, and re-test, and so on, and eventually we will find one. For 1 to 100, here’s the list of primes:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 91 97 101 103 107 109
A sample page to determine the prime numbers is here, and to test is here.
Lots of Keys
In standard key-based encryption, we can have a single key, which is secret between Bob and Alice, and then Bob will use it to encrypt his plaintext, and then Alice will use the same key to decrypt. If Bob and Alice know the key, it will be easy for them to encrypt and decrypt, but will be difficult for Eve, and she would have to search for all the possible keys. Thus the other thing we can do to defeat computers is to have lots of different keys – the more the better. Just like when you come home, and you’ve got lots of keys on your key ring, it can take a while to find the right key, the same happens for brute force cracking of encryption. For this the more bits that we have in a key, the more keys that will be possible. So it we had a four bit key, we could have 16 (2 to the power of 4) different keys: 0000, 0001, … 1110 and 1111). In this way we can calculate the key space, and where the average number of keys tried will be half the key space size (as you may be lucky at get it first time, or you may have to search to the end, but, on average, it will take half the key space size).
So we have a lot of keys, but we know that computers are actually very powerful in doing repetitive tasks, so lets determine how long it would take a standard computer to crack some codes which has a certain key size. Let’s start with 32 bits, which gives 4,294,967,296 keys. If we assume that it will take 1 nano seconds to try each key it will take:
T = 4,294,967,296 x 1 x 10^-9 /2 = 2.15 seconds
So it only takes 2 seconds to crack. Let’s try 56 bits (which is the basis of the DES encryption method). Now we have 72,057,594,037,927,936 keys and it will take 1.14 years to crack, on average. For 64-bits we have 18,446,744,073,709,551,616 keys and it will now take 292.47 years, on average, which should be enough to keep more messages secret.
But what about parallel processing and improving computing power? Check back for the next part of this discussion for more details on this.
If you are interested?
If you are interested in anything related to this subject, I’ve created a new presentation at:
billatnapier 
2 thoughts on “For the Love of Cryptography”