Search Network

Optimising the Speed of Encryption

30 November 2011
print version share on facebook share on linkedin

Executive summary

A new mathematical development in the theory of elliptic curves was translated into a speedup in the implementation of elliptic curve cryptography.

Challenge overview

The challenge is to find an equation that optimizes the speed of encryption, in both software and hardware. Another challenge is to find such equations quickly, because in some applications each user requires a different curve.

Elliptic Curve Cryptography (ECC) is a widely used form of public key cryptography. The implementation depends on the speed of the mathematical operations carried out on an elliptic curve over a finite field. Different forms of the equation of the curve give rise to different speeds of implementation, because the encryption operations depend on the equation.

Implementation of the initiative

In 2007 Harold Edwards published a theoretical paper in the Bulletin of the American Mathematical Society. He proposed a new form of the equation for an elliptic curve. In 2008 Daniel Bernstein, Tanja Lange and Reza Rezaeian Farashahi wrote a theoretical paper in which they proposed a new form of the equation for an elliptic curve over fields of characteristic two. Cryptographers then studied this paper from the point of view of cryptography, especially in software. Researchers at the Claude Shannon Institute collaborated with researchers at Intel to study the implementation of the new equations in hardware. We found a deterministic algorithm for converting points on an ordinary elliptic curve to points on a complete Edwards curve. This avoids the problem of choosing curve parameters at random.

Results and achievements

The new Edwards elliptic curves gave a significant speedup, and will be implemented in a forthcoming version of Intel's EP80579 processor. When implemented on a large hardware multiplier, computation of point multiplication using this algorithm performs significantly better, in terms of code complexity, code coverage and timing, than the standard implementation.


Figure 1. The addition operation on an Edwards elliptic curve.

Lessons learned and replicability

New developments in the theory of elliptic curves can lead to improvements in real implementations of elliptic curve cryptography. The industry partners found it very difficult to implement the results from an academic paper without collaborating with mathematicians. Aidan O'Mahony
Intel Shannon, Dromore House,
East Park, Shannon, Co Clare,
Ireland


Gary McGuire and Richard Moloney
Claude Shannon Institute for Discrete Mathematics, Coding, Cryptography and Information Security.
School of Mathematical Sciences
University College Dublin Belfield, Dublin 4,
Ireland

Attached Documents

PDF icon Irish Mathematics and Industry (Irish_Mathematics_and_Industry.pdf | 1.42 MB)