Privacy by Geometry

Elliptic curves and low cost-per-bit crypto strength.

Networked computers require strong cryptography, but strong cryptography comes at the expense of bandwidth and processing power – scarce resources today, and increasingly so in the slimmed-down smartcards, wireless phones, and mobile devices of tomorrow. This is the modern cryptographer’s efficiency conundrum: How do you squeeze more security out of less demanding crypto models?

Born in 1976, public key cryptography has become the de facto answer for ensuring privacy and data integrity between two anonymous parties. Under these systems, a person makes one key publicly available and holds a second, private key. A message is encrypted with the public key, sent, and decrypted with the private key. These systems bank mostly on long key sizes and complex mathematical problems to ensure security. But now cryptographers are looking to a mathematical system known as an elliptic curve to solve the efficiency conundrum. They believe that Elliptical Curve Cryptography (ECC) demands less computational power and, therefore, offers more security per bit.

Every well-established public key algorithm relies on a one-way mathematical problem, which makes it easy to generate a public key from a private key but difficult to deduce the private key, given the public key. The RSA system, for instance, hinges on the fact that it’s easy to find the product of two numbers, but it’s difficult to deduce the factors given the product. While the Digital Signature Algorithm (DSA) and the Diffie-Hellman key exchange algorithm rely on a discrete logarithm problem, where it’s simple to raise a number to the exponent of another number but difficult to find the exponent, given the result. Both factorization and discrete logarithm problems forge strong cryptographic systems when they employ numbers that exceed 300 digits – or about 1,000 bits.

Elliptic curve systems use a variation of the discrete logarithm problem. But instead of straight integer algebra, elliptic curve systems use an algebraic formula to determine the relationship between public and private keys within the universe created by an elliptic curve.

An elliptic curve can be roughly visualized by thinking of a doughnut. Looking at it from above, the doughnut forms a circle. Slice it top to bottom and this cross-section creates a second circle. These two perpendicular circles serve as the x and y axis of an elliptic curve. The important thing to remember is that there are a limited number of usable points within the area formed by the curve’s two planes, and, consequently, there is a finite field of coordinates.

Let’s put down the doughnut and instead look at the math behind ECC. Two hypothetical strangers, Alice and Bob, wish to swap encrypted email. Having just met, they require ECC to generate and exchange a single secret key. First Alice and Bob agree on a shared point P on an elliptic curve. Then, they each choose a secret integer – Alice picks integer a, and Bob chooses integer b. Alice multiplies her integer a times the point P, and in a manner exclusive to the behavior of elliptic curves, generates a second point on the curve. Bob does the same with b x P, and each sends the other the result. Bob takes the new point Alice generated from a x P and multiplies it by his original secret integer b. Alice does likewise, performing the function a (b x P). These calculations generate the same point on the curve.

The multiplication of P and the integers can be thought of as a process of successive addition, since it moves P through different points on the elliptic curve, until P comes to rest at its final location. This final point, when converted to an integer, acts as the secret key and can be used to pass information securely.

Elliptic curve cryptography is secure because it employs big, hidden numbers. Someone eavesdropping on Alice and Bob’s calculations would be privy only to the values transmitted publicly – the initial point P, a x P, and b x P. But this snoop wouldn’t know anything else, including the initial integers a and b. The final point, a (b x P), and more important, how P arrived at its final point, would also be unknown.

Since the elliptic curve contains a huge number of points, the initial point is multiplied by numbers larger than 50 digits long to move around the elliptic curve. But the final point on the curve could end up anywhere, and how it got there is just as much a mystery. Thus, a version of ECC concocted with 50-digit numbers couldn’t be broken by the strongest known attack algorithm in a million years using today’s computers.

Critics of ECC, however, lament the relatively small amount of time it has been around and predict that improvements in attack algorithms will push these curves back into obscurity. Elliptic curves themselves are nothing new – they’ve been studied for more than 100 years and were even employed to solve Fermat’s Last Theorem. It’s precisely the inability of the attack algorithms to solve the elliptic logarithm problem that allows a user to get essentially the same security from a 163-bit ECC system as they would from a 1024-bit RSA or DSA system.

“Let’s say computer processing power increases by a factor of a million,” imagines Neal Koblitz, a University of Washington professor and ECC’s co-inventor. “With elliptic curve cryptography, you still only have to add a handful of digits to the numbers involved. So instead of using 50-digit numbers, we’ll use 60 or 70.” The smaller numbers translate to more efficient crypto, and cryptographers like Koblitz believe that ECC’s size will stay relatively small even as it is challenged by the supercomputing phreaks and spooks of the next millennium.

Still, this efficiency is needed today. Wireless gadgets are rapidly becoming smaller and lighter, while still being forced to rely on minimal bandwidth and processing power. Philip Deck, president and CEO of Certicom, a Canadian company championing ECC in the marketplace, claims that Certicom’s recent benchmark tests clocked 163-bit ECC at 100 times faster than a 1024-bit RSA system in signing digital signatures, the authentication aspect of digital transactions. Says Deck, “Maybe it’s just luck, but the nature of elliptic curve systems maps right onto the financial-transaction needs of the future.”