cracking pke
As far as codebreakers are concerned, the key to cracking messages encrypted with systems based on PKE is how strong a key the people sending messages to each other have chosen. For encryption based on prime numbers, if two low prime numbers are chosen, it will take relatively little time for a determined would-be cryptanalyst to crack it.
However, the encryption used in commercial applications of PKE uses keys that are considerably longer than the trivial example given above.
When you see people talking about 64-bit and 128-bit encryption on the internet, this refers to the length of the key. A 64-bit (or binary digit) key would have as many as 20 digits. Imagine trying to find the prime factors of the number 44019146190022537727 without a computer. (Before you spend too much time on this, they are 5926535897 and 7427466391.) Interestingly RSA Security runs several challenges with prizes for cryptanalysts.
On the face of it, that the company offers up such challenges seems odd. Why should they encourage people to crack their encryption system? In fact, the challenges have a very practical advantage - the company can quickly see how strong their keys need to be to remain secure.
The first of the challenges focuses on factorisation. When it was launched, the challenge took the form of ten very large numbers. The first two numbers have already been factorised – the first in December 2003 and the most recent in November 2005. The latter took just over five calendar months to achieve but would have taken more than 30 years of processing time had they not used a network of linked computers to achieve it in the shorter timescale. Of the eight remaining numbers, even the smallest has 174 digits, while the largest has 617. Prizes ranging from US$10,000 to US$200,000 are offered to the codebreakers who can find their factors. Visit www.rsasecurity.com if you fancy having a go.
In setting the challenge the company says: “Given the amount of computation required for such a factorisation, the prizes are mainly symbolic. They serve as a small incentive for public demonstrations of factoring on a large scale.”
Working out the factors of numbers can be done in many ways. The most obvious is by trial division. This is dividing the target number by every whole number from 2 upwards until you find one that leaves no remainder – this is then one of the factors of the target number. If you find no factor, then you have a prime number. This is the most time-consuming method of factorisation as you have try virtually every number to check to see whether your target number is prime. ‘Virtually’ because there is no need to try dividing by whole numbers larger than half the target number since these will always produce a remainder.
Imagine the target number was 12. Dividing by 2 gives 6 with no remainder. This means 2 is a factor of 12. As you try the next numbers, you realise that both 3 and 4 are also factors but 5 is not since 12 divided by 5 is 2 but with a remainder of 2. 6 is also a factor of 12. We have now finished our factorisation of 12 since we have reached 6, which is half of 12 and we need to test no more numbers. That took only a few seconds but doing very large number takes a huge amount of time. The sort of numbers that are used as modern day keys have huge numbers of digits and it would take a lifetime to factor them.
Thankfully for the codebreaker, there are other methods of factorisation than trial by division although these typically involve extremely complex mathematics.
The elliptic curve method is used to factorise numbers of up to 25 digits long. A method called the quadratic sieve is used for numbers between around 50 and 100 digits long while the so-called number field sieve method is used for larger numbers.