Mathematical advances strengthen IT security

May 12, 2009 – 12:34 PM

Rapidly rising cyber crime and the growing prospect of the Internet being used as a medium for terrorist attacks pose a major challenge for IT security. Cryptography is central to this challenge, since it underpins privacy, confidentiality, and identity, which together provide the fabric for e-commerce and secure communications. Cryptography since the beginning of the Internet has been based extensively on the RSA public key system, used for digital signatures and the exchange of private keys that in turn encrypt message content. The RSA cryptosystem, introduced by Rivest, Shamir, and Adlement in 1977, relies for its security on the difficulty of working out the factors dividing large integers (whole numbers). RSA has performed well until now, but the level of protection it provides has been eroded by constant efforts to develop more efficient methods for breaking it.

However a different approach based on the mathematical theory of elliptic curves has emerged as a leading candidate for more efficient cryptography capable of providing the optimum combination of security and processing efficiency. Elliptic curves* are equations with two variables, say x and y, including terms where both x and y are raised to powers of two or more. The theory of elliptic curves played an important role in the solution of the famous problem, Fermat’s Last Theorem, in the early 1990s, and also ironically has been exploited for attacks on RSA cryptography.

The potential for elliptic curves and other modern techniques of mathematics were discussed at a recent workshop organised by the European Science Foundation (ESF), which set the stage for development of a programme of European-wide research on the field.

“The impact of the elliptic curve method for integer factorisation (developed by my PhD advisor Hendrik Lenstra) has played a role in introducing elliptic curves to cryptographers, albeit for attacking the underlying problem on which RSA is based (the difficulty of factoring integers),” said David Kohel, convenor of the ESF workshop, from the Institut de Mathematiques de Luminy in Marseille, France.

Indeed it so happened that elliptic curves started to be applied to both number factorisation and cryptography at about the same time, in the late 1980s. At first the application to factorisation advanced much more quickly, while the technical difficulty involved held back elliptic curve cryptography. But the very success of elliptic curve factorisation started to undermine the security of RSA, since this relies on the difficulty of factorising the product of two prime numbers. This in turn has stimulated development of elliptic curve cryptography in more recent years, said Kohel. So having first undermined the prevailing RSA method of cryptography, the sophisticated mathematics of elliptic curves has itself come to the rescue.

As Kohel noted, the advantage of elliptic curve cryptography lies in its immunity to the specialised attacks that have eroded the strength of RSA, with the result that smaller keys can be used to provide a given level of protection. “The size of the parameters (essentially the key size) for elliptic curve cryptography (ECC) needed to ensure security (under our current state of understanding) is much lower for ECC than for RSA or ElGamal (another alternative cryptographic method,” said Kohel. Indeed keys 160 bits long provide ECC with the same level of security as 1024 bit keys for RSA.

Source:
http://www.eurekalert.org/pub_releases/2009-05/esf-mas051109.php