Cryptography Reference
In-Depth Information
to the square root of the group cardinality, a group order of at least 2
160
should be
used. According to Hasse's theorem, this requires that the prime
p
used for the el-
liptic curve must be roughly 160-bit long. If we attack such a group with generic
algorithms, we need around
√
2
160
= 2
80
steps. A security level of 80 bit provides
medium-term security. In practice, elliptic curve bit lengths up to 256 bit are com-
monly used, which provide security levels of up to 128 bit.
It should be stressed that this security is only achieved if cryptographically strong
elliptic curves are used. There are several families of curves that possess crypto-
graphic weaknesses, e.g., supersingular curves. They are relatively easy to spot,
however. In practice, often standardized curves such as ones proposed by the Na-
tional Institute of Standards and Technology (NIST) are being used.
9.5 Implementation in Software and Hardware
Before using ECC, a curve with good cryptographic properties needs to be identi-
fied. In practice, a core requirement is that the cyclic group (or subgroup) formed
by the curve points has prime order. Moreover, certain mathematical properties that
lead to cryptographic weaknesses must be ruled out. Since assuring all these prop-
erties is a nontrivial and computationally demanding task, often standardized curves
are used in practice.
When implementing elliptic curves it is useful to view an ECC scheme as a struc-
ture with four layers. On the bottom layer modular arithmetic, i.e., arithmetic in the
prime field
GF
(
p
), is performed. We need all four field operations: addition, sub-
traction, multiplication and inversion. On the next layer, the two group operations,
point doubling and point addition, are realized. They make use of the arithmetic pro-
vided in the bottom layer. On the third layer, scalar multiplication is realized, which
uses the group operations of the previous layer. The top layer implements the actual
protocol, e.g., ECDH or ECDSA. It is important to note that two entirely different
finite algebraic structures are involved in an elliptic curve cryptosystem. There is
a
finite field GF
(
p
) over which the curve is defined, and there is the
cyclic group
which is formed by the points on the curve.
In software, a highly optimized 256-bit ECC implementation on a 3-GHz, 64-bit
CPU can take approximately 2 ms for one point multiplication. Slower through-
puts due to smaller microprocessors or less optimized algorithms are common with
performances in the range of 10 ms. For high-performance applications, e.g., for
Internet servers that have to perform a large number of elliptic curve signatures per
second, hardware implementations are desirable. The fastest implementations can
compute a point multiplication in the range of 40
μ
s, while speeds of several 100
μ
s are more common.
On the other side of the performance spectrum, ECC is the most attractive public-
key algorithm for lightweight applications such as RFID tags. Highly compact ECC
engines are possible which need as little as 10,000 gate equivalences and run at a
speed of several tens of milliseconds. Even though ECC engines are much larger
