Elliptic Curve Cryptography - Security Considerations

• Communications
• Applied Math
• Algorithms

Quick Links

• Part 1: New book on Elliptic Curve Cryptography
• Part 2: Elliptic Curve Cryptography - Basic Math
• Part 3: Elliptic Curve Cryptography - Security Considerations
• Part 4: Elliptic Curve Cryptography - Key Exchange and Signatures
• Part 5: Elliptic Curve Cryptography - Extension Fields
• Part 6: Elliptic Curve Cryptography - Multiple Signatures

Cryptographic security has a lot of components. The simple stuff is the mathematics which is what I want to talk about. The hard stuff is preventing people from giving away things that should be secret (Loose lips sink ships still holds today!). The cryptographic security I want to talk about here comes from solving a mathematical problem to find a secret. The assumption is the attacker only knows public information and the algorithm, but not the key.

Over the real numbers, an equation like $$y = e^x$$ is simple to solve when we know $y$. We can find $x$ using the formula $$log(x) = \left[ \frac{x-1}{x+1} +\frac{1}{3}\left(\frac{x-1}{x+1}\right)^3 +\frac{1}{5}\left(\frac{x-1}{x+1}\right)^5 + ...\right].$$

Over a finite field when we have $$y = g^x \text{mod }p$$with $y$ and $g$ known, finding $x$ is called the Discrete Log Problem. This is not so easy to do, but after many decades of research methods such as Index Calculus and Function Field Sieve have sub exponential algorithms to find $x$.

For elliptic curve algebra over a finite field the equation $$Y = x G$$ with known points $Y$ and $G$, finding $x$ is called the Elliptic Curve Discrete Log Problem (ECDLP). This is really hard to do with the best algorithms solving for $x$ being proportional to the $\sqrt r$, where $r$ is the order of the point $G$. This is fully exponential and it is comparable to the security of symmetric key algorithms, you just need twice as many bits because of the square root.

When we get to elliptic curves over extension fields $F_{q^k}$ where $q$ is large and $k$ is small the present day algorithms are still exponential. However, the assumption is made that Index Calculus methods could apply and a sub exponential algorithm might be developed. This paper "On the discrete logarithm problem in elliptic curves", C. Diem, Compositio Math. 147 (2011), 75–104 explains why it is still an exponential problem for field extension curves.

Here's a table from Elliptic Curve Cryptography for Developers which gives the number of bits for each level of security:

The first column is the symmetric key security level, what AES encryption would be. The second column is the required number of bits to ensure the ECDLP is the same level of security as AES. Because it goes as the square root, there are twice as many bits as the symmetric key. The third column shows the number of bits for an elliptic curve over an extension field with the assumption that a sub exponential algorithm could find $x$ with $Y$ and $G$ known in $Y = xG$ over an extension field curve. 

The last column in the table is labeled "Embedding Degree". This is the value of $k$ in $F_{q^k}$. The elliptic curve defined over $F_q$ is $$y^2 = x^3 + a x + b \text{ mod }q$$and we expect that the number of points on the curve has a very large prime factor. The embedding degree is the smallest value of $k$ for an elliptic curve over $F_{q^k}$ that has the same very large prime factor.

Take the large prime factor to be $r$. Then the formula for the embedding degree is the smallest value of $k$ for which $$q^k \cong 1\text{ mod }r.$$For most elliptic curves defined over $F_q$ the value of $k$ is approximately $r$. This is fortunate because it makes the curves exceptionally secure. However, for algorithms which use the pairing of elliptic curve points we want small values of $k$ such as those listed in the above table.

One of the main tricks used in solving the ECDLP is to take advantage of small factors. The first method for breaking elliptic curve cryptography used an extension field with this property. To prevent an adversary from gaining a mathematical foothold, the value of the extension field $k$ in $F_{q^k}$ should be a prime number. The last column in the above table lists the values of $k$ one should use for security, but only prime numbers in that range should be chosen.

The process of finding elliptic curves useful for pairing operations which meet all the requirements 

1. level of security
2. large enough prime on base curve
3. large enough prime embedding degree

takes a lot of compute time. But for any given system, it only has to be done once. The higher the level of security, the longer the search process takes. For 128 bit level of security it's not too bad. For 256 bit level of security, it might take a week on a fast desktop. Fortunately the process can be done in parallel, so a lot of processors running in parallel can find good solutions in a much shorter time span.

For key exchange and simple signing algorithms only the first two steps in the above list are required. The process of finding good curves can be found in chapter 6 in Elliptic Curve Cryptography for Developers. The choice of $q$ can help with computational efficiency. But that is another topic for another day.

Elliptic curve cryptography is secure because solving the ECDLP is exponential in the size of $r$ (or $q$). This means over all fewer bits are needed for transmitting key information. I'll discuss key exchange and digital signatures in another blog.

Sign in