What is the ECPC suite?

ArgoTech has developed a suite of programs using new mathematical breakthroughs which dramatically speed up the generation of secure curves for elliptic curve cryptography. The suite is dubbed ECPC, for Elliptic Curve Point Counting. It will allow a significant advance in the quality of security offered, with particular application to low-power devices.

Why use cryptography?

Businesses are moving en masse to the Net, hundreds of millions of people are online and there is no doubt that in the 21st century the Internet economy will be worth trillions of dollars annually. All this activity is vulnerable unless properly secured. Privacy of communications, security of transactions and confidence in their strength are crucial ingredients for the growth of electronic commerce.

As a result there is strong demand for cryptographic software and related services, and this sector is on course to continue its very rapid growth. Among companies currently specialized in securing business-to-business transactions on the Internet: Verisign, RSA Security, Entrust Technologies and Baltimore Technologies have a combined market capitalization of about $10 billion.

Why use elliptic curves?

Public-key cryptography, is a vital component for securing electronic communications and transactions, for user authentication, for digital signatures and so on. This is a system under which each participant generates an encoding key and makes it public, while keeping an accompanying decoding key private. The alternative system is to generate a single secret key and communicate it only to selected recipients; the secret key is typically communicated using a public key!

The security of public-key systems is built on the difficulty of solving certain hard mathematical problems. The three principal systems are based on integer factorization (for the RSA algorithm), elliptic curves (for ECC i.e., elliptic-curve cryptography) and discrete logarithms in finite fields. Each method involves a function that is easy to compute but whose inverse is extremely difficult to compute. The size of the key to be used must be chosen so that the inverse is totally impossible to compute in practice, both now and throughout the useful lifetime of the data.

In the case of ECC the difficulty of the underlying problem grows exponentially with the key-size. This means that ECC offers high levels of security, even with small keys. For instance, RSA requires keys of at least 1000 bits to be secure whereas ECC is secure with keys six times smaller. Small keys have many advantages including faster calculations that use less CPU time and battery power. These advantages become especially significant in low-power devices such as mobile phones, PDAs, palm-top computers, and numerous embedded chips.

Why generate elliptic curves with ECPC?

The initial step in cryptographic protocols based on ECC is to choose a secure elliptic curve to form part of the key. It is essential to know the cardinality i.e., the number of points on the curve, in order to check that it is divisible by a large prime number. Before ECPC, computing the cardinality was a time consuming and cumbersome process.

In order to circumvent this problem, vendors of ECC software have resorted to various compromises. One involves the selection of curves with special mathematical properties which make it easy to determine their cardinality. However this is now understood to be a risky proposition because the very same properties are likely to make such special curves vulnerable to attack by sophisticated mathematical methods. One example of such a weakness has been demonstrated by ArgoTech’s expert mathematician Robert Harley.

Another more recent approach is selection from a short-list of standard curves drawn up by the U.S. National Security Agency. This list is the subject of intense scrutiny and wide-spread use of such a small number of curves could lead to wide-spread failure if any weaknesses are discovered.

It is now widely accepted among researchers in cryptography that the ideal method for generating the most secure curves is to pick arbitrary curves at random and select those whose cardinality is divisible by a large prime. Previously this ideal process took hours of computation on a powerful workstation, whereas now with ECPC it can be performed in one minute on an ordinary server or PC.

Commercial implications of the ECPC suite.

The ECPC suite employs the fastest algorithms recently developed by Robert Harley with academic colleagues at École Polytechnique and University of Paris. ArgoTech’s proprietary implementation, ECPC, dramatically increases the speed of computing cardinalities and selecting secure curves suitable for cryptographic use.

ECPC is the only high-performance implementation of these methods that is available. It uses state of the art computational techniques to make it the fastest and most compact implementation likely to appear for several years. ECPC is also a tool of considerable interest to researchers, who could use it to explore computational aspects of elliptic curves not previously within reach. Previous records in determining the cardinality of elliptic curves have been shattered using ECPC with the record now standing at a key-size of 15013 bits, set by Robert Harley and colleagues.

For commercial cryptographic purposes, keys of 200 bits are more than sufficient. With ECPC it is now possible to generate a secure random curve of such a size in 8 seconds on average. The smallest useful curves e.g., the 113-bit ones recommended for short-term security during key-exchange in the WAP standard, can even be generated in ten seconds on a low-power StrongARM chip using 36 K of RAM.

One can envisage, for example, a company such as a bank managing sensitive information over a closed network, generating optimally secure curves in-house on a daily basis. The enhancement in security and in the perception of security would be significant.

It is now possible to create ECC systems many times faster than before, with the highest possible level of security, guaranteed free from external interference; they can be customized to individual workgroups and updated at will. In addition, this security and flexibility can be incorporated in the rapidly growing network of low-power clients using the small key sizes enabled by ECC.