CS260 Study Guide

7a. Explain the Weierstrass form of an elliptic curve

• What is the Weierstrass form of an elliptic curve?
• How are congruences modulo p used when applying the Weierstrass form in cryptographic applications?
• What are some mathematical traits of the Weierstrass form of an elliptic curve?

Elliptic curves can be used to form cryptographic systems. One type of elliptic curve that can be understood, given all you know from this course, is the Weierstrass form:

$y^2=x^3+ax+b \text{ mod p}$

where a and b are parameters that define a specific curve, and p is a prime number. Given a prime value of p, every element in the congruence will have a multiplicative inverse. This property forges a well-posed path to formulating arithmetic operations (such as point addition) on the elliptic curve.

One important point to note about the Weierstrass form is that the same value of x can generate two y values. In an analogy to the square root function for real numbers, both a positive and negative root will satisfy the curve equation. This means that, given some x for which a value y satisfies the equality, then

$text{p-y mod p}$

will also satisfy the equality for the same x. Because of this property, just as with real square root functions, the graph of the Weierstrass form will be symmetric about some y value. You can gain some intuition about the Weierstrass form by choosing a small value of p (such as p=17) along with values of a and b and then plotting some points on the curve.

To review, see:

• Introduction to the Weierstrass Curve

7b. Solve problems involving elliptic curve groups

• What is point addition
• What is the point at infinity?
• How are these concepts related to forming a group on an elliptic curve?

The starting point for performing algebraic operations on an elliptic curve requires point addition, point doubling, and the point at infinity.

• Point addition involves adding two different points, P and Q, contained on the curve: P+Q.
• Point doubling involves adding a point P to itself: P+P.
• Point at infinity: The result of adding a point P and its mirror image P + (-P) = 0. It is used as the identity element for adding points on an elliptic curve.

You should understand that this set of operations leads to a cyclic group. Furthermore, you should understand how a generator can yield all elements within the group defined on the Weierstrass Curve. To do this, it is important to review the equations for point addition and point doubling and understand how they can be applied within a congruence modulo p.

To review, see:

• The Details Behind Point Addition
• Computing Point Addition

7c. Write programs to implement ECC

• How is point addition implemented in Python?
• How is point doubling implemented in Python?
• How is a mirror image recognized in Python?

To implement ECC, it will be necessary to implement arithmetic operations on the elliptic curve. This unit focuses on the Weierstrass Curve and the equations associated with this curve. For example, to verify a generator, successive additions must be applied until all elements of the group have been generated. This implies that point addition, point doubling, and the point at infinity must be programmed. A key numerical step in implementing point doubling and point addition requires that multiplicative inverses of elements modulo p must be computed. One way to program this step is to apply the extended Euclidean algorithm.

The point at infinity occurs because a point P has been added to its own inverse (-P), which is the mirror image of P. It should be clear that the equation for point addition will be undefined if used to compute P+(-P). Therefore, the mirror image should be checked before applying the P+Q point addition. Such a condition could be encountered, for example, while using a generator to generate all points within the group. So, to create a suite that can implement arithmetic on an elliptic curve, your code must be prepared to compute P+P, P+Q, and handle the condition P+(-P).

To review, see:

• Python Implementation

7d. Apply the elliptic curve discrete logarithm problem

• How is scalar multiplication used in the EC discrete logarithm problem (ECDLP)?
• What is the Elliptic Curve Diffie-Hellman (ECDH) protocol?
• How is the DLP problem related to the ECDLP problem?

Given the cyclic group formulation using the addition of points on an elliptic curve, scalar multiplication can be achieved by successive addition. In other words, given a point P, a computation such as 3P can be achieved by computing P+P+P. Given a generator 𝛼 for this group, the pattern of how group elements will be generated is not known. Assume that $T=K𝛼$, where it takes K "hops" to arrive at the point T on an elliptic curve. If T is given, but K is not, determining K is a computationally difficult problem. In analogy to the DLP, the elliptic curve discrete logarithm problem (ECDLP) refers to determining the value of K (the number of hops).

For the most part, any cryptosystem based upon the DLP can be translated to the ECDLP. One important application of the ECDLP is the Elliptic Curve Diffie-Hellman (ECDH) protocol. Instead of using exponentials, scalar multiplication is used to generate the keys. Alice and Bob still choose secret values x and y, but now Alice forms $YA=x𝛼$ and Bob forms $YB=y𝛼$. Alice sends Bob YA, and Bob sends Alice YB. Both parties can form the quantity $K=xy𝛼$ to achieve the key exchange. For groups containing many points on an elliptic curve, determining x from YA and y from YB is considered computationally difficult. You should be able to generate points on a Weierstrass curve for small values of P. Furthermore, with this code in place, for small values of p, you should be able to determine Alice and Bob's values of x and y if an eavesdropper intercepts YA and YB.

Additionally, given $T=K𝛼$ and the generator 𝛼, you should have code in place to determine K from the value of T using a brute force approach (that is, solve the ECDLP). This framework can also be extended to digital signatures. Elliptic Curve Digital Signature Algorithms (ECDSA) refer to the process where a user's private key from an elliptic curve encryption is used to sign a message.

To review, see:

• Overview
• Elliptic Curve Diffie-Hellman (ECDH)
• Elliptic Curve Digital Signature Algorithm (ECDSA)

7e. Contrast the computational security of elliptic curves versus discrete logs

• Why is ECC considered to be secure?
• How does the computational security of RSA compare with ECC?
• How does the computational security of DL compare with ECC?

The security of ECC depends upon the computational difficulty of solving the ECDLP. One theme is consistent across public key systems based upon factoring, the DLP, and the ECDLP. The security of these problems is rooted in the difficulty of determining the sequence of how a generator generates all elements of the group. If this problem can be solved, such cryptosystems would be rendered unusable.

It is important to compare the performance of RSA and systems based on the DLP with systems based on the ECDLP. For example, key exchange systems based on the ECDH are considered to be faster than those based on the DH protocol. It is also generally true that the same amount of security can be achieved with fewer bits when using ECC approaches. From the materials in the course, you should be aware that computational security using fewer bits and computational efficiency are two major reasons why ECC techniques have been adopted.

To review, see:

• Public Key System Comparisons

Unit 7 Vocabulary

This vocabulary list includes terms you will need to know to successfully complete the final exam.

• Elliptic Curve Diffie-Hellman (ECDH)
• Elliptic Curve Digital Signature Algorithms (ECDSA)
• elliptic curve discrete logarithm problem (ECDLP)
• point addition
• point at infinity
• point doubling
• Weierstrass form