A presentation at this year's Black Hat security conference makes good arguments for the current foundation of our public key crypto system having a life of around five years. Its main message is that we have to develop more agile crypto systems.

At the moment, our public key cryptographic systems are based on one of two related mathematical problems - integer factorization or the discrete logarithm. These problems are used to create "trap-door" functions which are difficult to undo if you don't have an extra piece of information - the private key. The whole security of cryptography is based on the simple fact that there is no quick way of solving either problem.

Integer factorization is easy to understand: if you have a value d which is the product of two big prime numbers, p and q,  it takes a long time to discover either prime by trial division. However, if I give you one of the primes finding the other is very quick. 

The discrete logarithm problem is a little more difficult to follow but at its simplest it comes down to "find x so that h=g^x given h and g". 

Currently both integer factorization and the discrete logarithm have no polynomial time algorithmic solutions. The reason why it is important for the solution not to be polynomial in time is that if someone invents a faster computer or algorithm then, as long as it isn't polynomial, you can push your problem beyond its reach by increasing the size of the problems - i.e. increasing the number of bits in the primes or the keys. 

It has long been assumed that if either problem was cracked by the production of a polynomial time algorithm it would be a sudden, and possibly mostly secret, affair. Some government cryptographer would suddenly prove a deep result that would allow the reading of all encrypted traffic, or a quantum computer would be built in secret and at huge cost and all code would again be readable. In either case, there wouldn't be a huge impact on the commercial crypto system - until the news was leaked that is. 

However, it is now proposed in a presentation from iSECpartners titled "The Factoring Dead - Preparing For the Cryptopocalypse" that the downfall could come in slow and steady public steps towards better algorithms made by a number of researchers worldwide. The new algorithms might not even be polynomial, just fast enough to push the key size to something unacceptable. The research that is worrying is attacking the discrete logarithm problem, but as already mentioned the integer factorization problem is related. In the last six months new algorithms have been produced that run in polynomial time for restricted types of problem. If the restrictions can be removed then cryptography based on the discrete logarithm problem, such as Diffie-Hellman, DSA and El-Gamal, are no longer useful. If the algorithm can be adapted to integer factorization, then RSA falls as well. 

The presentation goes on to point out that there is a long term alternative to using encryption based on integer factorization or the discrete logarithm problem - Elliptic Curve Cryptography (ECC). 

An elliptic curve is a polynomial like y²=x³+ax+b and the set of points which satisfy the equation forms a group under an operation that behaves like addition. The basis of ECC is that you are given two points P and Q on the curve and you have to find the integer n such that Q=nP (where nP means adding P to itself n times). This is a problem that takes exponential time and is the basis for the trap door function. 

ECC is a more difficult problem than factoring and the discrete logarithm and key sizes can be smaller. It also isn't likely to be affected by any breakthroughs in solving the discrete logarithm problems so it is an ideal alternative. Unfortunately the cryptographic system we have in place isn't flexible enough to accommodate much bigger keys, let alone a new form of encryption. There is also the small problem that Blackberry holds important patents on the technology and is enforcing its rights. This has resulted in a slow take up of the technology.

What the presentation draws attention to isn't that our current crypto system has been breached but that if it was it would be difficult to react to any changes and continue working. The call is to make the framework more able to change and use different key sizes and cryptographic principles. The next move might be to ECC, but in time it too will need to be replaced.